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

コミット

コミットハッシュ: 604e10c34d359f6522b076e488dccd7b075f4bc7
Author: Andrew Balholm andybalholm@gmail.com
Date: Sat Oct 29 10:51:59 2011 +1100

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

https://github.com/golang/go/commit/604e10c34d359f6522b076e488dccd7b075f4bc7

元コミット内容

html: adjust bookmark in "adoption agency" algorithm

In the adoption agency algorithm, the formatting element is sometimes
removed from the list of active formatting elements and reinserted at a later index.
In that case, the bookmark showing where it is to be reinserted needs to be moved,
so that its position relative to its neighbors remains the same
(and also so that it doesn't become out of bounds).

Pass tests1.dat, test 70:
<DIV> abc <B> def <I> ghi <P> jkl </B>

| <html>
|   <head>
|   <body>
|     <div>
|       " abc "
|       <b>
|         " def "
|         <i>
|           " ghi "
|       <i>
|         <p>
|           <b>
|             " jkl "

Also pass tests through test 76:
<test attribute---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------->

R=nigeltao
CC=golang-dev
https://golang.org/cl/5322052

変更の背景

このコミットは、HTMLパーシングにおける「adoption agency algorithm（養子縁組アルゴリズム）」の動作を修正することを目的としています。このアルゴリズムでは、特定のフォーマット要素（例: , ）がアクティブなフォーマット要素のリストから一時的に削除され、後で別のインデックスに再挿入されることがあります。

問題は、この再挿入の際に使用される「ブックマーク」が、リスト内の要素の移動に合わせて適切に調整されないことでした。ブックマークが調整されないと、再挿入される要素の相対的な位置がずれたり、ブックマーク自体がリストの範囲外になってしまう可能性がありました。

このコミットは、このブックマークの調整不足による問題を解決し、HTMLパーシングの正確性を向上させるために導入されました。具体的には、tests1.dat のテスト70およびテスト76までのテストケースがこの変更によってパスするようになります。

前提知識の解説

HTMLパーシング

HTMLパーシングとは、WebブラウザがHTMLドキュメントを読み込み、それをコンピュータが理解できる構造（DOMツリー）に変換するプロセスです。このプロセスは、大きく分けて「トークン化（Tokenization）」と「ツリー構築（Tree Construction）」の2つのフェーズに分かれます。

トークン化: HTMLの文字列を、タグ（, <div>など）、属性、テキストなどの意味のある単位（トークン）に分解します。
ツリー構築: トークンストリームを処理し、DOM（Document Object Model）ツリーを構築します。DOMツリーは、HTMLドキュメントの論理的な構造を表すツリー状のデータ構造です。

アクティブなフォーマット要素のリスト (List of Active Formatting Elements)

HTMLパーシングのツリー構築フェーズにおいて、ブラウザは「アクティブなフォーマット要素のリスト」という内部的なデータ構造を維持します。このリストは、現在開いている（まだ閉じられていない）フォーマット関連の要素（例: , , <a>, など）を追跡するために使用されます。このリストは、HTMLのネストが正しくない場合でも、要素の正しい親子関係を推測し、DOMツリーを適切に構築するために重要です。

Adoption Agency Algorithm (養子縁組アルゴリズム)

「Adoption Agency Algorithm（養子縁組アルゴリズム）」は、HTMLパーシング仕様の非常に複雑な部分であり、特に誤ってネストされたHTMLタグを適切に処理するために設計されています。XMLとは異なり、HTMLは非常にエラーに寛容であり、ブラウザは不正な形式のHTMLでもレンダリングすることが期待されています。このアルゴリズムは、text のようにタグが誤って閉じられたり、オーバーラップしたりするような一般的な記述ミスがあった場合でも、ブラウザが矛盾のないDOMツリーを作成するのに役立ちます。

このアルゴリズムの主な目的は、タグが誤ってネストされたときに要素の親子関係を修正することです。パーサーが誤ってネストされたタグに遭遇すると、アルゴリズムは本質的に誤ってネストされた要素を「養子縁組」し、DOMツリー内の正しい親の下に配置します。これには、多くの場合、開いている要素のスタックを検索して適切な親を見つける作業が伴います。

このアルゴリズムは、Webブラウザが高いレベルの耐障害性を実現し、構文エラーのあるHTMLドキュメントでも表示できるようにするための重要なコンポーネントです。

ブックマーク (Bookmark)

養子縁組アルゴリズムにおいて、「ブックマーク」は、アクティブなフォーマット要素のリスト内で、特定の要素が再挿入されるべき位置を示すマーカーとして機能します。要素がリストから一時的に削除され、後で再挿入される際に、このブックマークがその再挿入位置を決定するために使用されます。

技術的詳細

このコミットが修正する具体的な問題は、養子縁組アルゴリズム内でフォーマット要素がアクティブなフォーマット要素のリストから削除され、後で再挿入される際に発生します。

元の実装では、フォーマット要素がリストから削除されると、その要素が元々存在していた位置よりも前のインデックスにブックマークが設定されている場合、そのブックマークの位置がずれてしまう可能性がありました。これは、リストから要素が削除されることで、リスト全体のインデックスがシフトするためです。ブックマークがこのシフトに合わせて調整されないと、以下の問題が発生します。

相対位置のずれ: 再挿入される要素が、期待される隣接要素との相対的な位置関係を維持できなくなります。
範囲外エラー: ブックマークがリストの有効なインデックス範囲外を指してしまう可能性があります。

このコミットでは、この問題を解決するために、フォーマット要素が削除される前に、ブックマークの位置を調整するロジックが追加されました。具体的には、削除される要素の元の位置（oldLoc）がブックマーク（bookmark）よりも前にある場合、ブックマークをデクリメント（bookmark--）することで、リストのインデックスシフトを考慮し、ブックマークが常に正しい相対位置を指すようにします。これにより、要素が再挿入される際に、その位置が正確に保たれ、DOMツリーの整合性が維持されます。

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

src/pkg/html/parse.go

--- a/src/pkg/html/parse.go
+++ b/src/pkg/html/parse.go
@@ -756,6 +756,10 @@ func (p *parser) inBodyEndTagFormatting(tag string) {
 		furthestBlock.Add(clone)
 
 		// Step 14. Fix up the list of active formatting elements.
+		if oldLoc := p.afe.index(formattingElement); oldLoc != -1 && oldLoc < bookmark {
+			// Move the bookmark with the rest of the list.
+			bookmark--
+		}
 		p.afe.remove(formattingElement)
 		p.afe.insert(bookmark, clone)

src/pkg/html/parse_test.go

--- a/src/pkg/html/parse_test.go
+++ b/src/pkg/html/parse_test.go
@@ -132,7 +132,7 @@ func TestParser(t *testing.T) {
 		rc := make(chan io.Reader)
 		go readDat(filename, rc)
 		// TODO(nigeltao): Process all test cases, not just a subset.
-		for i := 0; i < 70; i++ {
+		for i := 0; i < 77; i++ {
 			// Parse the #data section.
 			b, err := ioutil.ReadAll(<-rc)
 			if err != nil {\

コアとなるコードの解説

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

この変更は、parser構造体のinBodyEndTagFormattingメソッド内で行われています。このメソッドは、HTMLパーシングの「in body」モードでフォーマット要素の終了タグが処理される際に呼び出されます。

追加されたコードブロックは以下の通りです。

		if oldLoc := p.afe.index(formattingElement); oldLoc != -1 && oldLoc < bookmark {
			// Move the bookmark with the rest of the list.
			bookmark--
		}

p.afe.index(formattingElement): これは、formattingElement（現在処理中のフォーマット要素）がアクティブなフォーマット要素のリスト（p.afe）内で現在どのインデックスにあるかを調べます。結果はoldLocに代入されます。
oldLoc != -1: indexメソッドは、要素が見つからない場合に-1を返します。この条件は、要素がリスト内に存在することを確認します。
oldLoc < bookmark: この条件が最も重要です。これは、削除されるformattingElementの現在の位置（oldLoc）が、再挿入のブックマーク（bookmark）よりも前にあるかどうかをチェックします。
bookmark--: もし上記の条件が真であれば、つまり、削除される要素がブックマークよりも前の位置にあった場合、リストから要素が削除されることで、ブックマーク以降のすべての要素のインデックスが1つ前にシフトします。このシフトを補正するために、bookmarkの値を1つ減らします。これにより、ブックマークが常に正しい相対位置を指すようになります。

この修正により、p.afe.remove(formattingElement)によって要素が削除された後でも、p.afe.insert(bookmark, clone)で要素が再挿入される際に、ブックマークが指す位置が正確に保たれ、DOMツリーの整合性が保証されます。

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

テストファイルでは、TestParser関数内のループ条件が変更されています。

-		for i := 0; i < 70; i++ {
+		for i := 0; i < 77; i++ {

元のループはi < 70、つまりテストケース0から69までを実行していました。
変更後はi < 77、つまりテストケース0から76までを実行するようになっています。

この変更は、新しいロジックが正しく機能することを確認するために、より多くのテストケース（特にコミットメッセージで言及されているテスト70およびテスト76までのテスト）を実行するようにテストスイートを拡張したことを示しています。これにより、修正が意図した通りに動作し、既存のテストを壊していないことが検証されます。

comemo