[インデックス 10075] GoのHTMLパーサーにselect要素の解析機能を追加

コミット

コミットハッシュ: 2f352ae48abf1a714f7b3bfb097fab6451067599
著者: Nigel Tao nigeltao@golang.org
日時: 2011年10月22日 20:18:12 +1100
メッセージ: html: parse <select> tags.

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

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

元コミット内容

このコミットは、GoのHTMLパーサーに<select>タグの解析機能を実装したものです。主な変更は以下の通りです：

resetInsertionMode()関数の新規追加
inSelectIM（select要素内挿入モード）の実装
inBodyIMでの<select>タグ処理の追加
inTableIMでの挿入モードリセット処理の改善
テストケースの追加：<select><b><option><select><option></b></select>X

変更の背景

HTML5仕様の準拠

2011年当時、GoのHTMLパーサーはHTML5仕様に準拠した実装を目指していました。HTML5仕様では、<select>要素は特別な解析ルールを持つ要素の一つとして定義されており、専用の挿入モード（insertion mode）が必要でした。

select要素の特殊性

<select>要素は以下の理由で特別な処理が必要です：

限定的な子要素: <option>、<optgroup>、スクリプト系要素のみを子要素として持つことができる
ネストの禁止: <select>要素内に別の<select>要素をネストすることはできない
フォーマッティング要素の無視: <b>、<i>などのフォーマッティング要素は無視される
テーブル内での特別な挙動: テーブル要素内での<select>の処理には追加の考慮が必要

パーサーの完成度向上

このコミット以前は、<select>要素は適切に解析されておらず、TODO項目として残されていました。Web標準への準拠とパーサーの完成度を高めるため、この実装が必要でした。

前提知識の解説

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

HTML5パーシングアルゴリズムは、HTMLドキュメントを一貫性のあるDOM（Document Object Model）ツリーに変換するための詳細な手順を定義しています。このアルゴリズムは以下の主要なコンポーネントで構成されています：

トークナイザー（Tokenizer）: HTML文字列をトークン（開始タグ、終了タグ、テキスト、コメントなど）に分解
ツリー構築器（Tree Constructor）: トークンを受け取ってDOMツリーを構築
挿入モード（Insertion Mode）: パーサーの現在の状態を表し、トークンの処理方法を決定

挿入モード（Insertion Mode）

挿入モードはHTML5パーシングアルゴリズムの中核概念です。パーサーは常にいずれかの挿入モードにあり、受け取ったトークンをそのモードに応じて処理します。主な挿入モードには以下があります：

initialIM: 初期モード
beforeHeadIM: head要素の前
inHeadIM: head要素内
inBodyIM: body要素内
inTableIM: table要素内
inSelectIM: select要素内（このコミットで追加）
afterBodyIM: body要素の後

オープン要素スタック（Open Elements Stack）

パーサーは現在開いている要素のスタック（p.oe）を維持します。これは、どの要素が現在開いていて、どの要素内にいるかを追跡するために使用されます。

アクティブフォーマッティング要素リスト

<b>、<i>、<strong>などのフォーマッティング要素は特別な処理が必要で、アクティブフォーマッティング要素リストで管理されます。

技術的詳細

resetInsertionMode()関数の実装

この関数はHTML5仕様のセクション11.2.3.1「reset the insertion mode」を実装しています。オープン要素スタックを逆順に走査し、各要素に応じて適切な挿入モードを決定します：

func (p *parser) resetInsertionMode() insertionMode {
    for i := len(p.oe) - 1; i >= 0; i-- {
        n := p.oe[i]
        // スタックの各要素をチェックして適切なモードを返す
        switch n.Data {
        case "select":
            return inSelectIM
        case "td", "th":
            return inCellIM
        // ... 他の要素の処理
        }
    }
    return inBodyIM // デフォルト
}

inSelectIM関数の実装

inSelectIM関数は、パーサーが<select>要素内にいるときのトークン処理を定義します：

テキストトークン: そのまま追加
option要素: 既存のoption要素があれば閉じてから新しいものを追加
select要素: 現在のselect要素を終了
その他の要素: 基本的に無視（HTML5仕様に準拠）
コメント: コメントノードとして追加

select要素の終了処理

<select>要素を終了する際、オープン要素スタックを逆順に走査し、最初に見つかった<select>要素までのすべての要素を削除します。これにより、不正なネスト構造が自動的に修正されます。

テーブル内でのselect要素の処理

TODO項目として残されていますが、テーブル内での<select>要素は特別な処理が必要です。将来的には「in select in table」モードの実装が予定されています。

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

1. resetInsertionMode()関数の追加（parse.go:237-259）

// Section 11.2.3.1, "reset the insertion mode".
func (p *parser) resetInsertionMode() insertionMode {
    for i := len(p.oe) - 1; i >= 0; i-- {
        n := p.oe[i]
        if i == 0 {
            // TODO: set n to the context element, for HTML fragment parsing.
        }
        switch n.Data {
        case "select":
            return inSelectIM
        case "td", "th":
            return inCellIM
        case "tr":
            return inRowIM
        case "tbody", "thead", "tfoot":
            return inTableBodyIM
        case "caption":
            // TODO: return inCaptionIM
        case "colgroup":
            // TODO: return inColumnGroupIM
        case "table":
            return inTableIM
        case "head":
            return inBodyIM
        case "body":
            return inBodyIM
        case "frameset":
            // TODO: return inFramesetIM
        case "html":
            return beforeHeadIM
        }
    }
    return inBodyIM
}

2. inBodyIMでのselect要素処理（parse.go:516-521）

case "select":
    p.reconstructActiveFormattingElements()
    p.addElement(p.tok.Data, p.tok.Attr)
    p.framesetOK = false
    // TODO: detect <select> inside a table.
    return inSelectIM, true

3. inSelectIM関数の実装（parse.go:876-924）

// Section 11.2.5.4.16.
func inSelectIM(p *parser) (insertionMode, bool) {
    endSelect := false
    switch p.tok.Type {
    case ErrorToken:
        // TODO.
    case TextToken:
        p.addText(p.tok.Data)
    case StartTagToken:
        switch p.tok.Data {
        case "html":
            // TODO.
        case "option":
            if p.top().Data == "option" {
                p.oe.pop()
            }
            p.addElement(p.tok.Data, p.tok.Attr)
        case "optgroup":
            // TODO.
        case "select":
            endSelect = true
        case "input", "keygen", "textarea":
            // TODO.
        case "script":
            // TODO.
        default:
            // Ignore the token.
        }
    case EndTagToken:
        switch p.tok.Data {
        case "option":
            // TODO.
        case "optgroup":
            // TODO.
        case "select":
            endSelect = true
        default:
            // Ignore the token.
        }
    case CommentToken:
        p.doc.Add(&Node{
            Type: CommentNode,
            Data: p.tok.Data,
        })
    }
    if endSelect {
        for i := len(p.oe) - 1; i >= 0; i-- {
            switch p.oe[i].Data {
            case "select":
                p.oe = p.oe[:i]
                return p.resetInsertionMode(), true
            case "option", "optgroup":
                continue
            default:
                // Ignore the token.
                return inSelectIM, true
            }
        }
    }
    return inSelectIM, true
}

4. inTableIMでの改善（parse.go:714-716）

case "table":
    if p.popUntil(tableScopeStopTags, "table") {
        return p.resetInsertionMode(), true  // 以前は単にinBodyIMを返していた
    }

5. テストケースの追加（parse_test.go:166）

// TODO(nigeltao): Process all test cases, not just a subset.
for i := 0; i < 30; i++ {  // 29から30に増加

コアとなるコードの解説

resetInsertionMode()の動作原理

この関数は、オープン要素スタックを下から上に向かって走査し、各要素のタグ名に基づいて適切な挿入モードを決定します。これは、パーサーが現在のコンテキストを「再発見」する必要がある場合（例：テーブル要素の終了時）に使用されます。

重要なポイント：

スタックの最下部（インデックス0）に到達した場合、HTMLフラグメント解析のコンテキスト要素を考慮する必要がある（TODO）
各要素タイプに対して適切な挿入モードが定義されている
デフォルトはinBodyIM

inSelectIMの処理フロー

トークンタイプによる分岐: まずトークンのタイプ（開始タグ、終了タグ、テキスト、コメント）で処理を分岐
option要素の特別処理: 新しいoption要素を追加する前に、既存のoption要素があれば自動的に閉じる
select要素のネスト防止: select開始タグまたは終了タグを受け取った場合、現在のselect要素を終了
無視される要素: HTML5仕様に従い、select要素内で許可されていない要素は無視

エラー回復メカニズム

endSelect処理では、オープン要素スタックを走査して最初のselect要素を探します。途中でoption/optgroup要素があれば継続し、それ以外の要素があっても処理を続行します。これにより、不正な構造からの回復が可能になります。

パフォーマンスへの配慮

スタック走査は逆順で行われ、最も近い要素から処理される
不要なメモリアロケーションを避ける設計
条件分岐を効率的に配置

comemo