Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 10076] ファイルの概要

このコミットは、Go言語のHTMLパーサーにおける重要な改善を導入しています。特に、HTML5の仕様で定義されている「フォスターペアレンティング (foster parenting)」アルゴリズムの実装と、アクティブフォーマット要素の再構築に関するバグ修正が主な内容です。これにより、テーブル内に不適切に配置された要素の処理が改善され、より堅牢なHTMLパースが可能になります。

コミット

commit 2aa589c843debaef249e7fbcd9dd3fa0546c9c8
Author: Andrew Balholm <andybalholm@gmail.com>
Date:   Sun Oct 23 18:36:01 2011 +1100

    html: implement foster parenting
    
    Implement the foster-parenting algorithm for content that is inside a table
    but not in a cell.
    
    Also fix a bug in reconstructing the active formatting elements.
    
    Pass test 30 in tests1.dat:
    <a><table><td><a><table></table><a></tr><a></table><b>X</b>C<a>Y
    
    R=nigeltao
    CC=golang-dev
    https://golang.org/cl/5309052

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/2aa589c843debaef249e7fbcd9dd3fa0546c9c8

元コミット内容

このコミットは、Go言語のhtmlパッケージにおいて、以下の2つの主要な変更を導入しています。

  1. フォスターペアレンティング (foster parenting) の実装: テーブル要素（<table>、<tbody>、<thead>、<tfoot>、<tr>）の内部に、セル（<td>、<th>）ではない要素が誤って配置された場合の処理を、HTML5の仕様に従って実装します。これにより、不正なマークアップに対するパーサーの挙動がより予測可能で、標準に準拠したものになります。
  2. アクティブフォーマット要素の再構築に関するバグ修正: パーサーがアクティブフォーマット要素のスタックを再構築する際に発生していたバグを修正します。これにより、HTMLドキュメントの解析中に適用されるテキストフォーマット（例: <b>, <i>）が正しく処理されるようになります。

この変更は、tests1.datのテストケース30、具体的には<a><table><td><a><table></table><a></tr><a></table><b>X</b>C<a>Yという複雑で不正なHTMLマークアップを正しくパースできるようになることを目的としています。

変更の背景

HTMLは非常に寛容な言語であり、ブラウザは不正なマークアップに対しても可能な限りレンダリングを試みます。この「エラー回復」の挙動は、HTML5の仕様で詳細に定義されており、すべてのHTMLパーサーはこれに準拠することが求められます。

このコミットの背景には、特にテーブル要素のパースにおける複雑なルールがあります。HTMLのテーブル構造は厳格であり、<table>タグの直下に<td>や<th>のようなセル要素以外の要素が来ることは通常ありません。しかし、開発者が誤ってそのようなマークアップを記述した場合、ブラウザはそれを無視するのではなく、特定のルールに従ってDOMツリーの別の場所に「移動」させて処理します。このルールが「フォスターペアレンティング」です。

Go言語のhtmlパッケージは、HTML5の仕様に準拠したパーサーを提供することを目指しており、このコミットは、その準拠度を高めるための重要なステップでした。特に、不正なテーブル構造に対する堅牢性を向上させることで、より多くの種類のHTMLドキュメントを正確にパースできるようになります。

また、「アクティブフォーマット要素」の処理は、HTMLのネストされたフォーマットタグ（例: <b><b>text</b></b>）を正しく扱うために不可欠です。この部分にバグがあると、テキストの表示が意図しないものになる可能性があります。このコミットは、そのバグを修正し、パーサーの正確性を向上させています。

前提知識の解説

HTML5パーシングアルゴリズム

HTML5のパーシングアルゴリズムは、非常に詳細かつ複雑なステートマシンとして定義されています。これは、ブラウザがどのようにHTMLドキュメントを読み込み、DOMツリーを構築するかを厳密に規定しています。主な概念には以下があります。

  • トークナイゼーション (Tokenization): 入力ストリームをタグ、属性、テキストなどのトークンに分解するプロセス。
  • ツリー構築 (Tree Construction): トークンを受け取り、DOMツリーを構築するプロセス。このプロセスは、現在の「挿入モード (insertion mode)」に基づいて動作します。
  • 挿入モード (Insertion Mode): パーサーが現在どのHTML要素のコンテキストで動作しているかを示す状態。例えば、in bodyモード、in tableモードなどがあります。各モードには、特定のトークンが来た場合の処理ルールが定義されています。
  • スタック (Stack of Open Elements): 現在開いている要素（まだ終了タグが来ていない要素）を追跡するためのスタック。DOMツリーの階層構造を管理するために使用されます。
  • アクティブフォーマット要素 (List of Active Formatting Elements): <b>, <i>, <a>などのフォーマット要素が、開始タグが来たときにこのリストに追加され、対応する終了タグが来たときに削除されます。これにより、ネストされたフォーマット要素や、不正にネストされたフォーマット要素の処理が複雑なルールに基づいて行われます。

フォスターペアレンティング (Foster Parenting)

フォスターペアレンティングは、HTML5パーシングアルゴリズムの重要なエラー回復メカニズムの一つです。これは、特定の要素（特にテーブル関連の要素）が、本来あるべきではない場所に挿入されようとした場合に適用されます。

具体的には、<table>、<tbody>、<thead>、<tfoot>、<tr>といったテーブル関連の要素の内部に、<td>や<th>のようなセル要素ではないコンテンツ（例: テキスト、<div>、<img>など）が直接挿入されようとした場合に発動します。

このアルゴリズムが発動すると、パーサーは以下のいずれかの場所を「フォスターペアレント (foster parent)」として探し、その要素をそこに挿入します。

  1. テーブルの直前の兄弟要素: テーブルの直前に兄弟要素が存在し、それがテキストノードでない場合、その要素の末尾に挿入されます。
  2. テーブルの親要素: テーブルの親要素の末尾に挿入されます。
  3. <html>要素: 上記のいずれも見つからない場合、最終的に<html>要素の末尾に挿入されます。

このメカニズムにより、不正なマークアップであってもコンテンツが失われることなく、DOMツリーの論理的に適切な場所に配置されることが保証されます。

アクティブフォーマット要素の再構築 (Reconstructing the List of Active Formatting Elements)

アクティブフォーマット要素のリストは、HTMLパーサーがテキストのフォーマット（太字、斜体、リンクなど）を正しく適用するために使用する重要なデータ構造です。このリストは、開始タグが来たときに要素を追加し、終了タグが来たときに要素を削除します。

しかし、HTMLのマークアップが不正な場合（例: <b><i>テキスト</b></i>のようにタグが正しくネストされていない場合）、このリストの整合性が失われる可能性があります。HTML5の仕様では、このような状況でリストを「再構築」するための複雑なアルゴリズムが定義されています。これは、パーサーがDOMツリーを構築する際に、フォーマット要素の正しい適用範囲を決定するために行われます。

この再構築プロセスでは、リスト内の要素がDOMツリーに正しく反映されているかを確認し、必要に応じて新しい要素をDOMツリーに追加したり、既存の要素を再利用したりします。

技術的詳細

このコミットは、src/pkg/html/parse.goとsrc/pkg/html/parse_test.goの2つのファイルを変更しています。

src/pkg/html/parse.goの変更点

  1. parser構造体へのfosterParentingフィールドの追加:

    type parser struct {
    // ...
    // fosterParenting is whether new elements should be inserted according to
    // the foster parenting rules (section 11.2.5.3).
    fosterParenting bool
}

    このブール値のフラグは、現在フォスターペアレンティングモードが有効になっているかどうかを示します。

  2. addChildメソッドの変更:

    func (p *parser) addChild(n *Node) {
    if p.fosterParenting {
        p.fosterParent(n)
    } else {
        p.top().Add(n)
    }
    if n.Type == ElementNode {
        p.oe = append(p.oe, n)
    }
}

    新しいノードを追加する際に、fosterParentingフラグがtrueであれば、新しく追加されたfosterParent関数を呼び出すように変更されました。そうでなければ、通常のtop().Add(n)が実行されます。

  3. fosterParent関数の追加:

    func (p *parser) fosterParent(n *Node) {
    var table, parent *Node
    var i int
    for i = len(p.oe) - 1; i >= 0; i-- {
        if p.oe[i].Data == "table" {
            table = p.oe[i]
            break
        }
    }

    if table == nil {
        // The foster parent is the html element.
        parent = p.oe[0] // p.oe[0] is always the <html> element
    } else {
        parent = table.Parent
    }
    if parent == nil { // This case handles if table is the root or has no parent
        parent = p.oe[i-1] // Fallback to the element before the table in the stack
    }

    var child *Node
    for i, child = range parent.Child {
        if child == table {
            break
        }
    }

    if i == len(parent.Child) {
        parent.Add(n)
    } else {
        // Insert n into parent.Child at index i.
        parent.Child = append(parent.Child[:i+1], parent.Child[i:]...)
        parent.Child[i] = n
        n.Parent = parent
    }
}

    この関数は、HTML5のフォスターペアレンティングアルゴリズムを実装しています。

    • まず、スタックを逆順に走査し、最も近い<table>要素を探します。
    • <table>が見つからない場合、フォスターペアレントは<html>要素（スタックの最初の要素）になります。
    • <table>が見つかった場合、その<table>の親要素がフォスターペアレントになります。もし<table>が親を持たない場合（例: ドキュメントのルート要素である場合）、スタック内の<table>の直前の要素がフォスターペアレントとして選ばれます。
    • フォスターペアレントが決まったら、新しいノードnをそのフォスターペアレントの子として挿入します。挿入位置は、<table>要素が見つかった場合はその直前、それ以外の場合は末尾になります。

  4. reconstructActiveFormattingElementsのバグ修正:

    // Before:
// i++
// n = p.afe[i]
// p.addChild(n.clone())
// p.afe[i] = n // Bug: original 'n' is kept, not the clone added to DOM

// After:
i++
clone := p.afe[i].clone() // Clone the element
p.addChild(clone)         // Add the clone to the DOM
p.afe[i] = clone          // Update the AFE list with the clone

    以前のコードでは、アクティブフォーマット要素のリスト(p.afe)に格納されている要素のクローンをDOMに追加していましたが、リスト自体は元の要素への参照を保持していました。これにより、DOMとリストの間で不整合が生じる可能性がありました。修正後は、DOMに追加されたクローンをリストにも格納することで、両者の整合性を保っています。

  5. inBodyIMおよび関連メソッドの変更:

    • inBodyIMのdefaultケースで、p.inBodyEndTagOther(p.tok.Data)が呼び出されるようになりました。これは、特定の終了タグにマッチしない場合の一般的な処理をカプセル化しています。
    • inBodyEndTagFormatting内で、formattingElement == nilの場合にp.inBodyEndTagOther(tag)を呼び出すようになりました。
    • inBodyEndTagFormattingのswitch commonAncestor.Dataブロックで、テーブル関連の要素（table, tbody, tfoot, thead, tr）の場合にp.fosterParent(lastNode)を呼び出すようになりました。これは、テーブル内で不正にネストされたノードをフォスターペアレンティングルールに従って処理するためのものです。

  6. inBodyEndTagOther関数の追加:

    func (p *parser) inBodyEndTagOther(tag string) {
    for i := len(p.oe) - 1; i >= 0; i-- {
        if p.oe[i].Data == tag {
            p.oe = p.oe[:i]
            break
        }
        if isSpecialElement[p.oe[i].Data] {
            break
        }
    }
}

    この関数は、inBodyIMにおける「その他の終了タグ」の処理を実装しています。スタックを逆順に走査し、マッチするタグが見つかるか、または特殊な要素（例: html, body, pなど、特定のコンテキストでスタックから削除されない要素）が見つかるまで要素をポップします。

  7. inTableIMの変更:

    • テーブル関連の開始タグ（tbody, tfoot, thead, td, th, tr, table）の処理が大幅に修正されました。
    • 特に、td, th, trの開始タグが来た場合、clearStackToTableContext()を呼び出し、tbody要素を追加してからinTableBodyIMに遷移するようになりました。
    • table開始タグが来た場合、スタックをtableスコープの停止タグまでポップし、挿入モードをリセットするようになりました。
    • 最も重要な変更は、inTableIMの最後にフォスターペアレンティングを有効にするロジックが追加されたことです。 
      switch p.top().Data {
case "table", "tbody", "tfoot", "thead", "tr":
    p.fosterParenting = true
    defer func() { p.fosterParenting = false }()
}
return useTheRulesFor(p, inTableIM, inBodyIM)
      これにより、テーブル関連の要素が現在のトップ要素である場合、その後の要素の挿入はフォスターペアレンティングルールに従うようになります。deferキーワードにより、この挿入モードが終了した後にfosterParentingフラグが自動的にfalseに戻されます。

  8. clearStackToTableContext関数の追加:

    func (p *parser) clearStackToTableContext() {
    for i := len(p.oe) - 1; i >= 0; i-- {
        if x := p.oe[i].Data; x == "table" || x == "html" {
            p.oe = p.oe[:i+1]
            return
        }
    }
}

    このヘルパー関数は、スタックを逆順に走査し、最も近いtable要素またはhtml要素が見つかるまで、その要素より上のすべての要素をスタックから削除します。これは、テーブル関連の要素を挿入する前に、スタックを適切なコンテキストにリセットするために使用されます。

src/pkg/html/parse_test.goの変更点

  1. テストループの範囲変更:

    // Before:
// for i := 0; i < 30; i++ {
// After:
for i := 0; i < 31; i++ {

    TestParser関数内のテストケースを処理するループが、30番目のテストケース（インデックス29）までではなく、31番目のテストケース（インデックス30）まで実行されるように変更されました。これは、このコミットが修正する特定のテストケース30をカバーするためです。

  2. テストケース30のレンダリングスキップ:

    if filename == "tests1.dat" && i == 30 {
    // Test 30 in tests1.dat is such messed-up markup that a correct parse
    // results in a non-conforming tree (one <a> element nested inside another).
    // Therefore when it is rendered and re-parsed, it isn't the same.
    // So we skip rendering on that test.
    continue
}

    tests1.datのテストケース30は、<a><table><td><a><table></table><a></tr><a></table><b>X</b>C<a>Yという非常に複雑で不正なマークアップを含んでいます。このマークアップは、HTML5のパースルールに従って正しくパースされたとしても、結果として生成されるDOMツリーが「非準拠」な状態（例: <a>要素が別の<a>要素の中にネストされている）になることがあります。このような非準拠なツリーを再度レンダリングし、それを再度パースすると、元のツリーと同一にならない可能性があるため、この特定のテストケースではレンダリングと再パースの検証ステップがスキップされるようになりました。これは、パーサーが仕様通りに動作していることを確認しつつ、テストの制約を考慮した現実的な対応です。

コアとなるコードの変更箇所

このコミットのコアとなる変更は、src/pkg/html/parse.goファイル内の以下の関数とロジックに集約されます。

  1. fosterParent関数の追加: フォスターペアレンティングアルゴリズムの具体的な実装。
  2. addChildメソッドの変更: fosterParentingフラグに基づいてfosterParentを呼び出すロジック。
  3. reconstructActiveFormattingElementsの修正: アクティブフォーマット要素のリストとDOMの整合性を保つためのバグ修正。
  4. inTableIMの変更: テーブル挿入モードにおけるフォスターペアレンティングの有効化と、テーブル関連要素のパースロジックの改善。
  5. clearStackToTableContext関数の追加: テーブルコンテキストへのスタッククリアのヘルパー関数。

これらの変更が連携して、HTML5の複雑なエラー回復ルール、特にテーブル内の不正なマークアップの処理と、フォーマット要素の正確な管理を実現しています。

コアとなるコードの解説

fosterParent関数

この関数は、HTML5のフォスターペアレンティングアルゴリズムを直接実装しています。

  • フォスターペアレントの特定:

    • まず、現在のオープン要素のスタック(p.oe)を逆順に走査し、最も近い<table>要素を探します。
    • <table>が見つからない場合、フォスターペアレントはドキュメントのルートである<html>要素（p.oe[0]）になります。
    • <table>が見つかった場合、その<table>の親要素がフォスターペアレントになります。これは、テーブルの外部に要素を「養子縁組」させるためです。
    • もし<table>が親を持たない（例: ドキュメントのルート要素である）場合、または何らかの理由でtable.Parentがnilの場合、スタック内の<table>の直前の要素（p.oe[i-1]）がフォスターペアレントとして選ばれます。これは、テーブルの直前に要素を挿入するためのフォールバックメカニズムです。

  • ノードの挿入:

    • フォスターペアレントの子ノードリストを走査し、見つかった<table>要素のインデックスiを特定します。
    • もし<table>がフォスターペアレントの子として見つからない場合（i == len(parent.Child)）、新しいノードnはフォスターペアレントの末尾に単純に追加されます。
    • <table>が見つかった場合、新しいノードnは、その<table>の直前の位置（インデックスi）に挿入されます。これは、スライス操作append(parent.Child[:i+1], parent.Child[i:]...)とparent.Child[i] = nによって実現されます。これにより、<table>の前に要素が挿入され、<table>自体は後続の要素として維持されます。

reconstructActiveFormattingElementsの修正

この修正は、アクティブフォーマット要素のリスト(p.afe)と、実際にDOMツリーに追加されるノードの間の参照の整合性を確保するために重要です。

以前のコードでは、p.afe[i]からクローンを作成し、そのクローンをDOMに追加していましたが、p.afe[i]自体は元の要素への参照を保持していました。これは、もし元の要素が後で変更された場合、p.afeリスト内の参照がDOMツリー内の実際のノードと一致しなくなるという潜在的なバグを引き起こしていました。

修正後は、クローンを作成し、そのクローンをDOMに追加した後、そのクローン自体をp.afe[i]に代入しています。これにより、p.afeリスト内の参照が常にDOMツリー内の対応するノードと一致するようになり、フォーマット要素の再構築がより正確かつ堅牢になります。

inTableIMにおけるフォスターペアレンティングの有効化

inTableIM（テーブル内部の挿入モード）の変更は、テーブル内で不正なコンテンツが検出された場合に、フォスターペアレンティングを自動的に有効にするためのものです。

switch p.top().Data {
case "table", "tbody", "tfoot", "thead", "tr":
    p.fosterParenting = true
    defer func() { p.fosterParenting = false }()
}
return useTheRulesFor(p, inTableIM, inBodyIM)

このコードブロックは、現在のオープン要素のスタックのトップがtable、tbody、tfoot、thead、またはtrである場合に、p.fosterParentingフラグをtrueに設定します。そして、deferキーワードを使用することで、このinTableIM関数が終了する際に自動的にp.fosterParentingをfalseに戻すことを保証しています。これにより、テーブル内部でのみフォスターペアレンティングが一時的に有効になり、他のコンテキストに影響を与えないようになっています。

useTheRulesFor(p, inTableIM, inBodyIM)は、HTML5パーシングアルゴリズムの「別の挿入モードのルールを使用する」という概念を実装しており、この場合はinTableIMのルールが適用できない場合にinBodyIMのルールにフォールバックすることを示唆しています。

関連リンク

参考にした情報源リンク

[インデックス 10076] ファイルの概要

このコミットは、Go言語のhtmlパッケージにおけるHTMLパーサーの重要な改善を導入しています。主な目的は、HTML5の仕様で定義されている「フォスターペアレンティング (foster parenting)」アルゴリズムを実装すること、およびアクティブフォーマット要素の再構築に関する既存のバグを修正することです。これにより、テーブル内に不適切に配置された要素の処理が改善され、また、HTMLドキュメントの解析中に適用されるテキストフォーマットがより正確に処理されるようになり、結果としてより堅牢で標準に準拠したHTMLパースが可能になります。

コミット

commit 2aa589c843debaef249e7fbcd9dd3fa0546c9c8
Author: Andrew Balholm <andybalholm@gmail.com>
Date:   Sun Oct 23 18:36:01 2011 +1100

    html: implement foster parenting
    
    Implement the foster-parenting algorithm for content that is inside a table
    but not in a cell.
    
    Also fix a bug in reconstructing the active formatting elements.
    
    Pass test 30 in tests1.dat:
    <a><table><td><a><table></table><a></tr><a></table><b>X</b>C<a>Y
    
    R=nigeltao
    CC=golang-dev
    https://golang.org/cl/5309052

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/2aa589c843debaef249e7fbcd9dd3fa0546c9c8

元コミット内容

このコミットは、Go言語のhtmlパッケージに対して以下の主要な変更を加えています。

  1. フォスターペアレンティングの実装: HTML5の仕様に従い、テーブル要素（<table>、<tbody>、<thead>、<tfoot>、<tr>など）の内部に、セル要素（<td>、<th>）ではないコンテンツが誤って配置された場合の処理ロジックを導入します。これにより、不正なHTMLマークアップに対しても、ブラウザが通常行うエラー回復動作を模倣し、コンテンツが失われることなくDOMツリーの適切な場所に「養子縁組」されるようになります。
  2. アクティブフォーマット要素の再構築に関するバグ修正: HTMLパーサーが、<b>や<i>などのフォーマット要素の適用範囲を管理する「アクティブフォーマット要素のリスト」を再構築する際に発生していたバグを修正します。この修正により、ネストされたフォーマットタグや、不正にネストされたフォーマットタグがより正確に処理され、DOMツリーの整合性が保たれます。

これらの変更は、特にtests1.datというテストデータセットに含まれるテストケース30（<a><table><td><a><table></table><a></tr><a></table><b>X</b>C<a>Y）のような、複雑で意図的に不正なHTMLマークアップを正しくパースできるようになることを目的としています。

変更の背景

Webブラウザは、たとえHTMLマークアップがW3CやWHATWGの仕様に厳密に準拠していなくても、可能な限りコンテンツをレンダリングしようとします。この「エラー回復」の挙動は、HTMLの普及に大きく貢献しましたが、その一方で、ブラウザ間の互換性の問題を引き起こす原因ともなりました。HTML5の仕様は、このエラー回復の挙動を詳細に標準化することで、すべてのブラウザが同じように不正なマークアップを処理し、同じDOMツリーを構築できるようにすることを目指しました。

このコミットの背景には、Go言語のhtmlパッケージが、このHTML5の厳格なパーシングアルゴリズムに完全に準拠することを目指しているという目標があります。特に、以下の点が重要でした。

  • テーブル構造の厳格さとエラー回復: HTMLのテーブル構造は非常に厳格であり、<table>タグの直下には<caption>, colgroup, <thead>, <tbody>, <tfoot>のみが許可され、それ以外の要素は<tr>や<td>などのセル要素の中にネストされるべきです。しかし、開発者が誤って<table><div>...</div></table>のように記述した場合、ブラウザは<div>要素を無視するのではなく、テーブルの外に「移動」させてレンダリングします。この挙動が「フォスターペアレンティング」であり、Goのパーサーもこれを模倣する必要がありました。
  • アクティブフォーマット要素の複雑な管理: <b>, <i>, <a>などのインラインフォーマット要素は、開始タグと終了タグのペアによってテキストのスタイルを定義します。しかし、<b><i>テキスト</b></i>のようにタグが正しくネストされていない場合、ブラウザは特定のアルゴリズム（「アクティブフォーマット要素の再構築」または「養子縁組機関アルゴリズム」とも呼ばれる）に従って、DOMツリーの整合性を保ちながらフォーマットを適用します。このアルゴリズムにバグがあると、テキストの表示が崩れたり、意図しないフォーマットが適用されたりする可能性があります。

このコミットは、これらのHTML5パーシングアルゴリズムの複雑な側面をGoのパーサーに組み込むことで、より多くの種類のHTMLドキュメントを正確かつ予測可能にパースできるようにし、Go言語のHTML処理能力を向上させることを目的としています。

前提知識の解説

HTML5パーシングアルゴリズム

HTML5のパーシングアルゴリズムは、Webブラウザが生のHTMLバイトストリームを読み込み、構造化されたDOM（Document Object Model）ツリーに変換するための標準化されたプロセスです。このアルゴリズムは、非常に詳細なステートマシンとして定義されており、以下の主要な段階と概念を含みます。

  1. トークナイゼーション (Tokenization): 入力されたHTMLバイトストリームを、意味のある単位である「トークン」（例: 開始タグ、終了タグ、テキスト、コメント、DOCTYPEなど）に分解するプロセスです。
  2. ツリー構築 (Tree Construction): トークナイザーから受け取ったトークンに基づいて、DOMツリーを構築するプロセスです。この段階は、現在の「挿入モード (insertion mode)」と、オープン要素のスタック、アクティブフォーマット要素のリストなどの内部データ構造によって制御されます。
    • 挿入モード (Insertion Mode): パーサーが現在どのHTML要素のコンテキストで動作しているかを示す状態です。例えば、initial（初期状態）、before html、in head、in body、in tableなど、多くのモードが存在します。各モードには、特定のトークンが来た場合の処理ルールが厳密に定義されており、これによりDOMツリーへの要素の追加方法や、エラー回復の挙動が決定されます。
    • オープン要素のスタック (Stack of Open Elements): まだ終了タグが来ていない、現在開いているHTML要素を追跡するためのスタックデータ構造です。DOMツリーの階層構造を正確に反映し、要素のネスト関係を管理するために使用されます。新しい要素が追加されるとスタックにプッシュされ、対応する終了タグが来るとポップされます。

フォスターペアレンティング (Foster Parenting)

フォスターペアレンティングは、HTML5パーシングアルゴリズムにおける重要なエラー回復メカニズムの一つです。これは、特定の要素、特にテーブル関連の要素（<table>, <tbody>, <thead>, <tfoot>, <tr>）の内部に、本来その場所には挿入されるべきではないコンテンツ（例: テキストノード、<div>要素など、セル要素ではないもの）が挿入されようとした場合に発動します。

このアルゴリズムが発動すると、パーサーは以下のルールに従って、その「迷子」の要素をDOMツリー内の別の「養子縁組先（フォスターペアレント）」に移動させます。

  1. テーブルの直前の兄弟要素: もしテーブルの直前に兄弟要素が存在し、それがテキストノードでない場合、その兄弟要素の末尾に挿入されます。
  2. テーブルの親要素: 上記の条件に合致しない場合、テーブルの親要素の末尾に挿入されます。
  3. <html>要素: 上記のいずれの条件にも合致しない場合、最終的にドキュメントのルートである<html>要素の末尾に挿入されます。

このメカニズムにより、不正なマークアップであってもコンテンツが失われることなく、DOMツリーの論理的に適切な場所に配置されることが保証され、ブラウザはユーザーにコンテンツを表示し続けることができます。

アクティブフォーマット要素のリストと再構築 (List of Active Formatting Elements and Reconstruction)

「アクティブフォーマット要素のリスト (List of Active Formatting Elements)」は、HTMLパーサーが<a>, <b>, <i>, <strong>, <em>, font, s, strike, u, tt, big, small, code, nobrといった特定のフォーマット要素の適用範囲を管理するために使用するデータ構造です。

  • リストの役割: これらのフォーマット要素の開始タグが検出されると、その要素はリストに追加されます。対応する終了タグが検出されると、リストから削除されます。これにより、パーサーは現在どのフォーマットが「アクティブ」であるかを追跡し、後続のテキストノードに適切に適用することができます。
  • マーカー: リストには、特定の要素（例: pやformの終了タグ、templateの開始タグなど）が処理された際に挿入される「マーカー」と呼ばれる特殊なエントリも含まれることがあります。これらのマーカーは、フォーマット要素が特定の境界を超えて「養子縁組」されるのを防ぐ役割を果たします。
  • 再構築アルゴリズム: HTMLマークアップが不正な場合（例: <b><i>テキスト</b></i>のようにタグが正しくネストされていない場合や、フォーマット要素が暗黙的に閉じられた場合など）、アクティブフォーマット要素のリストの整合性が失われる可能性があります。このような状況で、パーサーは「アクティブフォーマット要素を再構築するアルゴリズム」を実行します。このプロセスは、リスト内の要素を反復処理し、必要に応じて要素を移動したり、クローンを作成してDOMツリーに再配置したりすることで、HTMLパースルールに従ってDOMツリーが正しく構築され、フォーマットが意図通りに適用されるようにします。このアルゴリズムは、その複雑な挙動から「養子縁組機関アルゴリズム (adoption agency algorithm)」とも呼ばれます。

これらのメカニズムは、HTMLの寛容性と、ブラウザが不正なマークアップに対しても一貫した方法でエラー回復を行う能力の基盤となっています。

技術的詳細

このコミットは、Go言語のhtmlパッケージの主要なパーシングロジックを含むsrc/pkg/html/parse.goファイルと、そのテストケースを定義するsrc/pkg/html/parse_test.goファイルに修正を加えています。

src/pkg/html/parse.goの変更点

  1. parser構造体へのfosterParentingフィールドの追加:

    type parser struct {
    // ...
    // fosterParenting is whether new elements should be inserted according to
    // the foster parenting rules (section 11.2.5.3).
    fosterParenting bool
}

    parser構造体にfosterParentingというブール型のフィールドが追加されました。このフラグは、新しい要素がフォスターペアレンティングのルールに従って挿入されるべきかどうかを制御します。

  2. addChildメソッドの変更:

    func (p *parser) addChild(n *Node) {
    if p.fosterParenting {
        p.fosterParent(n)
    } else {
        p.top().Add(n)
    }
    if n.Type == ElementNode {
        p.oe = append(p.oe, n)
    }
}

    要素をDOMツリーに追加するaddChildメソッドが修正されました。p.fosterParentingフラグがtrueの場合、新しく追加されたfosterParent関数を呼び出して要素を挿入します。そうでなければ、従来のp.top().Add(n)（現在のトップ要素の子として追加）が実行されます。これにより、フォスターペアレンティングのロジックが条件付きで適用されるようになります。

  3. fosterParent関数の追加:

    func (p *parser) fosterParent(n *Node) {
    var table, parent *Node
    var i int
    // Find the nearest "table" element in the stack of open elements
    for i = len(p.oe) - 1; i >= 0; i-- {
        if p.oe[i].Data == "table" {
            table = p.oe[i]
            break
        }
    }

    if table == nil {
        // If no "table" element is found, the foster parent is the <html> element (root)
        parent = p.oe[0]
    } else {
        // If a "table" element is found, the foster parent is its parent
        parent = table.Parent
    }
    // Fallback if table has no parent or is the root
    if parent == nil {
        parent = p.oe[i-1] // Use the element before the table in the stack
    }

    var child *Node
    // Find the index of the "table" element within its foster parent's children
    for i, child = range parent.Child {
        if child == table {
            break
        }
    }

    if i == len(parent.Child) {
        // If "table" is not found among children, add the new node at the end
        parent.Add(n)
    } else {
        // Insert the new node 'n' before the "table" element
        parent.Child = append(parent.Child[:i+1], parent.Child[i:]...)
        parent.Child[i] = n
        n.Parent = parent
    }
}

    この関数は、HTML5のフォスターペアレンティングアルゴリズムを実装しています。

    • まず、オープン要素のスタックを逆順に走査し、最も近い<table>要素を探します。
    • <table>が見つからない場合、フォスターペアレントは<html>要素（スタックの最初の要素）になります。
    • <table>が見つかった場合、その<table>の親要素がフォスターペアレントになります。もし<table>が親を持たない場合（例: ドキュメントのルート要素である場合）、スタック内の<table>の直前の要素がフォスターペアレントとして選ばれます。
    • フォスターペアレントが決まったら、新しいノードnをそのフォスターペアレントの子として挿入します。挿入位置は、<table>要素が見つかった場合はその直前、それ以外の場合は末尾になります。

  4. reconstructActiveFormattingElementsのバグ修正:

    // 修正前:
// i++
// n = p.afe[i]
// p.addChild(n.clone())
// p.afe[i] = n // ここがバグ。クローンではなく元の要素への参照を保持していた。

// 修正後:
i++
clone := p.afe[i].clone() // 要素をクローン
p.addChild(clone)         // クローンをDOMに追加
p.afe[i] = clone          // AFEリストをクローンで更新

    アクティブフォーマット要素のリストを再構築する際、以前のコードでは、DOMツリーに追加された要素のクローンではなく、元の要素への参照をリスト内に保持していました。これにより、DOMとリストの間で不整合が生じる可能性がありました。修正後は、DOMに追加されたクローン自体をリストにも格納することで、両者の整合性を保ち、フォーマット要素の正確な管理を保証します。

  5. inBodyIMおよび関連メソッドの変更:

    • inBodyIMのdefaultケースで、p.inBodyEndTagOther(p.tok.Data)が呼び出されるようになりました。これは、特定の終了タグにマッチしない場合の一般的な処理をカプセル化しています。
    • inBodyEndTagFormatting内で、formattingElement == nilの場合にp.inBodyEndTagOther(tag)を呼び出すようになりました。
    • inBodyEndTagFormattingのswitch commonAncestor.Dataブロックで、テーブル関連の要素（table, tbody, tfoot, thead, tr）の場合にp.fosterParent(lastNode)を呼び出すようになりました。これは、テーブル内で不正にネストされたノードをフォスターペアレンティングルールに従って処理するためのものです。

  6. inBodyEndTagOther関数の追加:

    func (p *parser) inBodyEndTagOther(tag string) {
    for i := len(p.oe) - 1; i >= 0; i-- {
        if p.oe[i].Data == tag {
            p.oe = p.oe[:i]
            break
        }
        if isSpecialElement[p.oe[i].Data] {
            break
        }
    }
}

    この関数は、inBodyIMにおける「その他の終了タグ」の処理を実装しています。スタックを逆順に走査し、マッチするタグが見つかるか、または特殊な要素（例: html, bodyなど、特定のコンテキストでスタックから削除されない要素）が見つかるまで要素をポップします。

  7. inTableIMの変更:

    • テーブル関連の開始タグ（tbody, tfoot, thead, td, th, tr, table）の処理が大幅に修正されました。特に、td, th, trの開始タグが来た場合、clearStackToTableContext()を呼び出し、tbody要素を追加してからinTableBodyIMに遷移するようになりました。
    • table開始タグが来た場合、スタックをtableスコープの停止タグまでポップし、挿入モードをリセットするようになりました。
    • 最も重要な変更は、inTableIMの最後にフォスターペアレンティングを有効にするロジックが追加されたことです。 
      switch p.top().Data {
case "table", "tbody", "tfoot", "thead", "tr":
    p.fosterParenting = true
    defer func() { p.fosterParenting = false }()
}
return useTheRulesFor(p, inTableIM, inBodyIM)
      これにより、テーブル関連の要素が現在のトップ要素である場合、その後の要素の挿入はフォスターペアレンティングルールに従うようになります。deferキーワードにより、この挿入モードが終了した後にfosterParentingフラグが自動的にfalseに戻され、フォスターペアレンティングがテーブル内部でのみ一時的に有効になることを保証します。

  8. clearStackToTableContext関数の追加:

    func (p *parser) clearStackToTableContext() {
    for i := len(p.oe) - 1; i >= 0; i-- {
        if x := p.oe[i].Data; x == "table" || x == "html" {
            p.oe = p.oe[:i+1]
            return
        }
    }
}

    このヘルパー関数は、スタックを逆順に走査し、最も近いtable要素またはhtml要素が見つかるまで、その要素より上のすべての要素をスタックから削除します。これは、テーブル関連の要素を挿入する前に、スタックを適切なコンテキストにリセットするために使用されます。

src/pkg/html/parse_test.goの変更点

  1. テストループの範囲変更:

    // 修正前: for i := 0; i < 30; i++ {
// 修正後: for i := 0; i < 31; i++ {

    TestParser関数内のテストケースを処理するループが、30番目のテストケース（インデックス29）までではなく、31番目のテストケース（インデックス30）まで実行されるように変更されました。これにより、このコミットが修正する特定のテストケース30がテストスイートに含まれるようになります。

  2. テストケース30のレンダリングスキップ:

    if filename == "tests1.dat" && i == 30 {
    // Test 30 in tests1.dat is such messed-up markup that a correct parse
    // results in a non-conforming tree (one <a> element nested inside another).
    // Therefore when it is rendered and re-parsed, it isn't the same.
    // So we skip rendering on that test.
    continue
}

    tests1.datのテストケース30は、非常に複雑で不正なHTMLマークアップを含んでいます。このマークアップは、HTML5のパースルールに従って正しくパースされたとしても、結果として生成されるDOMツリーが「非準拠」な状態（例: <a>要素が別の<a>要素の中にネストされている）になることがあります。このような非準拠なツリーを再度レンダリングし、それを再度パースすると、元のツリーと同一にならない可能性があるため、この特定のテストケースではレンダリングと再パースの検証ステップがスキップされるようになりました。これは、パーサーが仕様通りに動作していることを確認しつつ、テストの制約を考慮した現実的な対応です。

コアとなるコードの変更箇所

このコミットのコアとなるコードの変更箇所は、主にsrc/pkg/html/parse.goファイル内の以下の部分です。

  • parser構造体へのfosterParentingフィールドの追加: フォスターペアレンティングの有効/無効を制御するフラグ。
  • addChildメソッドの条件分岐: fosterParentingフラグに基づいて要素の挿入方法を切り替える。
  • fosterParent関数の新規追加: HTML5のフォスターペアレンティングアルゴリズムの具体的な実装。
  • reconstructActiveFormattingElementsメソッドの修正: アクティブフォーマット要素のリストとDOMツリーの整合性を保つためのバグ修正。
  • inTableIMにおけるフォスターペアレンティングの有効化ロジック: テーブル挿入モードでフォスターペアレンティングを一時的に有効にする。
  • clearStackToTableContext関数の新規追加: テーブルコンテキストへのスタッククリアのヘルパー関数。

これらの変更が連携して、HTML5の複雑なエラー回復ルール、特にテーブル内の不正なマークアップの処理と、フォーマット要素の正確な管理を実現しています。

コアとなるコードの解説

fosterParent関数の詳細

fosterParent関数は、HTML5のフォスターペアレンティングアルゴリズムの核心部分です。この関数は、不正な位置に挿入されようとしているノードnを受け取り、それをDOMツリー内の適切な「養子縁組先」に移動させます。

  1. フォスターペアレントの探索:

    • 関数はまず、現在のオープン要素のスタック（p.oe）を逆順に走査し、最も近い<table>要素を探します。これは、テーブルの内部で不正なコンテンツが検出された場合に、そのテーブルの外部にコンテンツを移動させるためです。
    • もしスタック内に<table>要素が見つからない場合、フォスターペアレントはドキュメントのルート要素である<html>（p.oe[0]）になります。これは、テーブル以外のコンテキストでフォスターペアレンティングがトリガーされた場合のフォールバックです。
    • <table>要素が見つかった場合、その<table>の親要素がフォスターペアレントとして選ばれます。これは、テーブルの直前の兄弟要素またはテーブルの親要素にコンテンツを移動させるというHTML5の仕様に準拠しています。
    • もしtable.Parentがnilの場合（例: <table>がドキュメントのルート要素であるか、何らかの理由で親を持たない場合）、スタック内の<table>の直前の要素（p.oe[i-1]）がフォスターペアレントとして選ばれます。これは、テーブルの直前に要素を挿入するためのフォールバックメカニズムであり、HTML5の仕様の複雑なケースに対応しています。

  2. ノードの挿入:

    • フォスターペアレントが特定された後、関数はフォスターペアレントの子ノードリストを走査し、見つかった<table>要素のインデックスiを特定します。
    • もし<table>がフォスターペアレントの子として見つからない場合（i == len(parent.Child)）、新しいノードnはフォスターペアレントの末尾に単純に追加されます。
    • <table>が見つかった場合、新しいノードnは、その<table>の直前の位置（インデックスi）に挿入されます。これは、Goのスライス操作append(parent.Child[:i+1], parent.Child[i:]...)とparent.Child[i] = nによって実現されます。この操作により、<table>の前に要素が挿入され、<table>自体は後続の要素として維持されます。

reconstructActiveFormattingElementsのバグ修正の詳細

この修正は、アクティブフォーマット要素のリスト（p.afe）と、実際にDOMツリーに追加されるノードの間の参照の整合性を確保するために非常に重要です。

HTML5のパーシングアルゴリズムでは、アクティブフォーマット要素のリストは、フォーマット要素の適用範囲を追跡するために使用されます。このリストには、DOMツリーに実際に追加された要素の参照が格納されるべきです。しかし、修正前のコードでは、p.afe[i]から要素をクローンし、そのクローンをDOMに追加していましたが、p.afe[i]自体は元の要素への参照を保持していました。

この問題は、もし元の要素が後で変更された場合（例えば、属性が追加されたり、テキストコンテンツが変更されたりした場合）、p.afeリスト内の参照がDOMツリー内の実際のノードと一致しなくなり、結果としてフォーマットの適用が誤ったり、DOMツリーの整合性が失われたりする潜在的なバグを引き起こしていました。

修正後は、クローンを作成し、そのクローンをDOMに追加した後、そのクローン自体をp.afe[i]に代入しています。これにより、p.afeリスト内の参照が常にDOMツリー内の対応するノードと一致するようになり、フォーマット要素の再構築がより正確かつ堅牢になります。これは、HTMLパーサーの正確性と信頼性を向上させる上で不可欠な変更です。

inTableIMにおけるフォスターペアレンティングの有効化ロジック

inTableIM（テーブル内部の挿入モード）の変更は、テーブル内で不正なコンテンツが検出された場合に、フォスターペアレンティングを自動的に有効にするためのものです。

switch p.top().Data {
case "table", "tbody", "tfoot", "thead", "tr":
    p.fosterParenting = true
    defer func() { p.fosterParenting = false }()
}
return useTheRulesFor(p, inTableIM, inBodyIM)

このコードブロックは、現在のオープン要素のスタックのトップがtable、tbody、tfoot、thead、またはtrである場合に、p.fosterParentingフラグをtrueに設定します。これは、これらの要素の内部で、セル要素ではないコンテンツが挿入されようとしている状況を示唆しています。

そして、defer func() { p.fosterParenting = false }()という行が重要です。deferキーワードは、囲んでいる関数（この場合はinTableIM）がリターンする直前に、指定された関数を実行することを保証します。これにより、p.fosterParentingフラグは、テーブル内部での処理が完了した後に自動的にfalseに戻されます。このメカニズムにより、フォスターペアレンティングはテーブル内部でのみ一時的に有効になり、パーサーの他の部分や他の挿入モードに意図しない影響を与えることを防ぎます。

useTheRulesFor(p, inTableIM, inBodyIM)は、HTML5パーシングアルゴリズムの「別の挿入モードのルールを使用する」という概念を実装しており、この場合はinTableIMのルールが適用できない場合にinBodyIMのルールにフォールバックすることを示唆しています。

関連リンク

参考にした情報源リンク