🍱

HTMLパーサーの設計・実装ノート (1) 字句解析

2022/05/03に公開

HTML

Web

tech

ふと思いつきでHTMLパーサーを書いているので、どのようなことを考えながら実装したかの記録を残します。

(1) 字句解析
(2) 構文解析

おことわり

偏ったこだわりや早すぎる最適化もあるかもしれませんが、あくまで趣味で書いているものなのでご理解ください。そういったもののなかにも、他の人の発想のヒントになるものも含まれると考えています。
途中の試行錯誤のサイクルを省いて結論だけを紹介している箇所もあります。ご了承ください。
ソースコードは https://github.com/qnighy/htstream に上げていますが、現在のところ完成度はそれほど高くありません。ドキュメントもほぼありませんがご了承ください。

HTMLについて

HTMLの管轄をめぐっては紆余曲折がありましたが、現在はWebブラウザベンダーを中心とする標準化団体であるWHATWGが制定するHTML StandardがHTMLの仕様であると考えられています。この標準はバージョン番号を持たず、その時点での最新版が権威的な標準であると考えられています。

現代のHTMLにおいて、マークアップ文書はDOMとよばれる木構造としてモデル化されています。このDOMをテキストで表現するための仕組みがHTMLですが、実はHTMLにはHTML構文とXML構文 (XHTML構文) の2種類の構文があります。XML構文は汎用のXMLパーサーでも扱えるので、今回のプロジェクトでは対象外 (余裕があったら実装する) としています。

HTML構文は歴史的な経緯から、XMLでもなければSGMLですらない独立した言語となっています。レガシー機能の宝庫となっているため、HTML文書を作成する側向けの仕様とパーサー向けの仕様が分離されています。パーサー向けの仕様には以下のような特徴があります。

<frameset>, <plaintext> などレガシー機能のために必要な処理も全て記載されている。
構文的に誤りの場合も含めた全てのケースに対してパース結果が定義されている。
- パースエラーと記載されている箇所も全てそのまま処理が続行できるように書かれている。

設計目標

以下を目標に置きました。

特別な技術的制約のある部分を除き、HTML Standardの指示に準拠すること。
ストリーミングパーサーとして動作すること。つまり、全体の読み込み完了を待たずに逐次処理ができること。
ストリーミングトランスデューサーとして動作すること。つまり、ストリーミングパーサー中で文書に変更を加え、変更後の文書をその完成を待たずに逐次的に出力することができること。
ストリーミングトランスデューサーとして実行した場合、任意のUnicode文字列に対してラウンドトリップ (読み込んだものをそのままシリアライズすると元の結果に戻る) が成立すること。
一般的なHTML文書に対して高速に動作すること。
悪意のあるHTML文書に対しても極端に (たとえば $\Omega(n^{1.5})$ で) 遅くなることはないこと。
- ただし、メモリ消費量は最悪ケースで $\Omega(n)$ で増加してもよい。
ストリーミングパーサーとしての動作のレイテンシ (判明している入力に対して、どこまでの出力を確定させるか) についてもHTML Standardの記述に準拠すること。

ただし、JavaScriptで実装する都合上、バイト列の処理は避け、デコード済みの文字列 (内部的にはUTF-16) に対して処理を行うこととします。

基本的な設計

HTML StandardではHTMLパーサーをトークナイザとパーサー本体に役割分担する典型的なパーサーパイプラインとして定義しています。HTMLの構文上の細かい仕様もこのパーサーパイプラインに合わせて決まっているため、今回作るパーサーもこのパーサーパイプラインに基本的に準拠します。

ただし、今回はラウンドトリップが成立することを要件に含めているので、トークナイザが出力する全てのトークンには生文字列を含むという設計にします。また、仕様上はトークナイザによって捨てられてしまう部分が稀に存在するので、それらに対しては追加のトークンを与えます。

仕様上文字トークンとして定義されている部分は、隣接する文字トークンを可能な限りまとめてテキストトークンとして提供することにします。

以上のことから、トークナイザは以下のトークンを出力します。

生のテキストトークン
生のRCDATAテキストトークン
生のRAWTEXTテキストトークン (script data, plaintext, CDATA sectionを含む)
生のDOCTYPEトークン
生の開始タグトークン
生の終了タグトークン
生のコメントタグトークン (bogus commentを含む)
ガーベージトークン

各トークンが生文字列を含むため、トークナイザは以下の処理を極力省くように設計します。

タグ中の属性値の解析
文字参照の解析

また、仕様ではトークナイザの前段にデコーダーと改行正規化がありますが、これについては以下のようにします。

デコーダーは今回の実装対象外とする。利用側でTextDecoderStreamなどを適宜アタッチして使う。
- そのため、encoding sniffing algorithmも今回の実装対象外。
トークナイザは改行正規化前のテキストを対象に処理を行う。改行正規化処理は各トークンごとに必要に応じて行う。

以下の点については仕様上の役割分担とは異なり、トークナイザの責務とします。

特別な開始タグ (<xmp>, <style>, <title> など) に基づく状態遷移
- ただし、CDATAセクションが有効かどうかの判定情報はパーサーから供給する。
<pre>, <listing>, <textarea> 直後の改行の削除

トークナイザのAPI

トークナイザは以下のようなAPIにします。

class Tokenizer {
  public addChunk(chunk: string, addToken: (token: RawToken) => void);
  public finish(addToken: (token: RawToken) => void);
}

アプリケーション側が主導権を握る形のAPIにしています。 addChunk(chunk: string): RawToken[] としていない理由のひとつは、トークン生成時にアプリケーション定義の処理を行う必要があるからです。具体的にはパーサー側の状態に応じてCDATAセクションの処理設定を変える必要があるのですが、これはチャンクの処理が全て終わってからでは遅い可能性があります。 (たとえば <svg><![CDATA[</svg>]]></svg> のようなテキストが1チャンク内に含まれていると意図した通りにならない)

このAPIはWHATWG StreamsのTransformer interfaceに含まれる transform / flush を参考にしていますが、今回作るトークナイザは必ず同期的に処理が完了する (addToken コールバックは必ず addChunk / finish 内でのみ呼ばれる) などの違いがあるため、あえて別のAPIとして提供しています。

トークナイザの状態設計

仕様上、テキストは届くたびに出力していくような形で書かれています。たとえば Hello, world! の Hello, wo までが確定しているとき、 Hello, wo はその時点でパーサーに渡されます。一方、テキスト以外のもの (開始タグ、終了タグ、コメントなど) はそれが閉じられるまで入力を待つような形になっています。たとえば、

<img src="https://example.com/avatar.jpg"

という入力があっても、この時点で「img タグがある」という情報はパーサーには渡されません。実際、もしここでEOFが来た場合は img は存在しなかったことになります。

これは必ずしも最適ではない (たとえば <!-- が入力されたらコメントがあることは確定するのでコメントの本文をストリーミングで出力することは可能) ですが、これらのトークンは一般的にはそこまで大きくなることはないと期待されることもあり、今回は仕様内で使われているようなトークナイザの振舞いを模倣しています。

これを踏まえて、テキストノード内とそれ以外の場合で以下のように異なる状態を持つことにします。

テキストノード内では原則として入力を全て消費し、トークナイザの状態としては残さない。
- href="https://example.com">Click が来た場合、入力文字列は全て消費され、トークナイザの状態は残らない。
それ以外の箇所では未出力部分を状態として残しておく。
- here!</ が来た場合、 </ をトークナイザの状態として残しておく。

また、テキストノード中でも文字参照の途中などいくつかのケースでは全てを出力せずに次の機会に回す場合があります。たとえば &am が入力されているとき、次のチャンクに p; が含まれていると文字トークンの境界で区切ってしまうことになるので、 &am はまだ出力せずに残すことになります。

さて、このようにすると未出力部分のテキストを検査することで前回の状態を復元できることが期待されます。しかしそれをそのまま実装すると非常に長いトークンが入力されたときに二乗の時間が発生してしまう場合があります。たとえば、

開始タグが非常に長い場合、入力中の > がタグを終端するかどうかはタグ全体を見ないとわからない。
文字参照も数値文字参照の場合に0埋めで際限なく長いトークンを作ることができる (&#x000000000....000A0;)。この状態チェックを素朴に実装すると全体で二乗の時間がかかってしまう。

これらの問題に対して複雑な対応をとるよりも、有限オートマトンを明示的に書いて状態管理をしたほうが結果としては見通しがよくなると考えたため、状態管理のために「未出力文字列のキュー」と「有限オートマトン」を併用することにします。

もともとHTML標準のパーサー向け仕様ではオートマトンの状態をある程度明示する形で字句解析器を定義しているので、この状態集合を参考にしつつ、必要ない状態を削るなどの最適化をして実装することにします。

トークナイザのホワイトボックステスト

以上のように、トークナイザの実装の骨格は1文字単位のオートマトンなので、大部分ではチャンクの区切りに関係なく同じ動作をするはずです。しかし実際には最適化のために以下のような工夫をしている場所があります。

チャンクから1文字ずつ切り出して未処理文字列に追加していくのではなく、チャンク内の位置をポインタとして持っておいてその値をインクリメントすることでアロケーションなどのコストを削減する。
特定のケースで、チャンク内の文字列をまとめて読むことでオートマトンの処理をスキップする。

これらの実装に間違いがないことを確認するには、チャンクの区切りを変えながら色々なケースをテストする必要があります。これをそのまま実装するのは大変です。原理的には指数的に多くの区切りパターンが存在するし、どのような区切りパターンが本質的に重要なケースかを手作業で指定するのもまた大変だからです。

そこで今回はホワイトボックステスト (実装内部の構造を理解した上で行うテスト) を併用します。今回作るトークナイザは状態を明示的に持つため状態の複製が可能です。そこで入力中の各位置でのトークナイザの状態を保存しておき、DP (動的計画法) を用いて局所的に必要なものだけをテストします。

たとえば入力文字列が4文字 </a> の場合を考えます。この場合入力区切り位置のパターンを全て列挙すると以下のようになります。

</a>
</a, >
</, a>
</, a, >
<, /a>
<, /a, >
<, /, a>
<, /, a, >

この場合、たとえば </, a> の2チャンクでのテストは実際には </, a, > の場合と <, /, a> の場合のテストで代替する余地があると考えられます。このような局所化を正しく行うには、入力途中での状態が経路によらず同じであることを確認すればよいはずです。そこで、まず1文字ずつ入力したときのトークナイザの状態を確認しておきます。

状態A → < → 状態B → / → 状態C → a → 状態D → > → 状態E

あとは、入力の各部分文字列について、あらかじめ保存していた状態と同じ遷移をすることを確認します。つまり以下の組み合わせを確認します。 (実際には状態遷移だけではなく出力の等価性も確認します)

状態A → </ → 状態C
状態B → /a → 状態D
状態C → a> → 状態E
状態A → </a → 状態D
状態B → /a> → 状態E
状態A → </a> → 状態E

これなら入力サイズに対して高々多項式程度の組み合わせで済むことになります。より少ない計算量で、コーナーケースのミスを網羅的に確認することができるはずです。

テキストトークンの状態管理

仕様上文字トークンとして定義されているものを、今回の実装ではテキストトークン (連続する文字トークンを並べたもの) として扱うことにします。

テキストトークンは基本的には「< かチャンクの終わりまでをまとめて出力する」という戦略でOKです。しかし、いくつかの例外的な条件があります。

複数文字で単一の文字トークンを構成する可能性がある場合
- チャンクが &am で終わっている場合、 &am がテキストトークンの一部であることは確定していますが、これが & の一部である可能性がまだ残されています。このような場合はテキストを分断するのは好ましくないので &am の手前までで出力を一旦止めたいです。
- チャンクがキャリッジリターン ("\r") で終わっている場合、これはCRLF ("\r\n") の一部の場合があります。これを分割してしまうと意図に反して2つの改行として処理してしまう可能性があるため、やはりCRの前で出力を止めたいです。
テキストトークンの一部かどうかが曖昧な場合
- チャンクが < で終わっている場合、 < がテキストトークンの一部かどうかはその時点ではわからないため、 < の手前までで出力を一旦止めたいです。
  - たとえば a < b は構文エラーですが、エラーの有無とは別にこの場合は < を文字通り解釈するよう規定されています。
  - いっぽう a <b の場合は < はタグの一部です。

こういったパターンを正しく扱うために、上記のようなパターンに対してはオートマトン上で専用の状態を付与しておきます。そして、最後に基本状態 (data state) だったのはいつかを別途記憶しておきます。以下のどちらかに該当したときにテキストトークンを出力します。

< の次の文字が英字、?, !, / のいずれかだったとき
- < の直前までがテキストトークンになる。
チャンクの終わりに到達したとき
- 最後に基本状態 (data state) だった位置までがテキストトークンになる。

たとえば……

チャンクが a < だった場合は < の直後にdata stateからtag open stateに遷移するため、 a までがテキストトークンとして出力されます。
チャンクが a < b だった場合は < の次の空白でtag open stateからdata stateに復帰するため、 a < b 全体がテキストトークンとして出力されます。
チャンクが a <b だった場合は b でtag open stateからtag name stateに遷移します。この時点で < がタグの一部であることが確定するため、チャンクの終わりを待たずに a がテキストトークンとして出力されます。

注意すべき点として、 &, <, \r などテキストから一時的に離脱している状態からテキストに復帰するとき、次の文字をdata stateで再消費する必要があるという点があります。そうしないと &a<, <<, \r< などのケースを正しくハンドルできません。

文字参照の状態管理

文字参照は全体で1つの文字トークンとなるため、文字参照の一部かもしれないテキストは終端が判明するまではテキストトークンとして出力できません。

文字参照のうち数値文字参照は /&#(?:[xX][0-9a-fA-F]+|[0-9]+);?/ (セミコロンを持たない場合は最長一致) と表せるため、オートマトンで普通に扱えます。一方、名前つき文字参照は /&[0-9a-zA-Z]+;?/ に含まれるものの、実際に受理可能な文字参照は2231個が仕様中に定義されており、それらに該当しない場合はリテラルな & にフォールバックするため、内容次第では形式的に終端が明らかではなくても処理を切り上げることができる場合があります。

&Al → Α の一部かもしれないのでこの時点では出力できない
&Alpha → Α の一部かもしれないのでこの時点では出力できない
&amp → & の一部かもしれないのでこの時点では出力できない
- &amp または & のいずれかであることは確定しているが、終端位置が未確定なので保留する
& → 出力できる
&ampe → &amp までで区切られることが確定しているので出力できる
&amq → これを接頭辞にもつ文字参照は存在しないため、 &amq までで区切って出力してしまって問題ない

名前つき文字参照も有限個しかないため原理的には有限オートマトンで書けますが、状態を書き下したくないので別途判定して離脱する特別ルールを実装します。

現状では文字参照名の入ったソート済みの配列から二分探索し、探索対象文字列が隣接要素の接頭辞であるかどうかを調べています。

タグの状態管理

開始タグと終了タグの字句解析上の扱いは大部分で同じです。たとえば以下の4つはエラーの有無の違いはあるものの、どこでトークンを区切るべきかという観点からは同じ扱いを受けます。

<div id=">">
<div id=">"/>
</div id=">">
</div id=">"/>

唯一異なるのが、2文字目 (3文字目) に対する挙動です。

入力	tag open	end tag open
`/[a-zA-Z]/`	→tag name	→tag name
`"/"`	→end tag open	`<//` はbogus comment
`"!"`	→markup declaration open	`</!` はbogus comment
`"?"`	`<?` はbogus comment	`</?` はbogus comment
`">"`	`<>` はテキスト	`</>` は破棄
それ以外	`<` はテキスト	`</` はbogus comment

今回の実装ではタグの内容は (タグ名以外は) 使わないので、タグの終端である > を発見するのが最終的な目的になります。しかし上の例でも挙げたように、引用符内の属性値には > がリテラルに出現する可能性があります。そのため、単純に > の出現を検索するだけでは不十分です。

少なくとも、現在の位置が引用符内かそうでないかを知る必要があることになりますが、不正なHTMLでは引用符の記号自体が場所によって異なる解釈を与えられるため、この発見は容易ではありません。

正当な例
- 属性値の一部として出現する場合 <div class='"'>
不正な例
- タグ名の一部として出現する場合 <d"iv>
- 属性名の一部として出現する場合 <div cl"ass="">
- 属性値の一部として出現する場合 <div class=f"oo>

これらを正しく区別するには、現在の位置が属性値の開始位置かどうかを知る必要があります。しかし、属性値を開始する = も不正なHTMLでは異なる解釈を与えられることがあります。

正当な例
- 属性値の一部として出現する場合 <div class="=">
不正な例
- タグ名の一部として出現する場合 <d=iv>
- 属性名の1文字目として出現する場合 <div =class="">
- 属性値の一部として出現する場合 <div class=f=oo>

これらを正しく区別するためには、属性名の1文字目 (before attribute name state) と2文字目以降 (attribute name state) を区別する必要があります。

以上の議論から、タグを字句解析する上ではHTML標準に記載されている状態の多くを維持する必要があることがわかります。一方で、以下の状態は統合できます。

before attribute name 系の状態
- before attribute name state (<div )
- self-closing start tag state (<div/)
  - 正当なHTMLでは > を期待するが、それ以外を入力したときはエラーにはなるもののbefore attribute name stateとほぼ同様の動作になる。
- after attribute value (quoted) state (<div class="")
  - 正当なHTMLでは属性間を空白で区切る必要があるが、そうでない場合はエラーにはなるもののbefore attribute name stateとほぼ同様の動作になる。
attribute name 系の状態
- attribute name state (<div class)
- after attribute name state (<div class )
  - 次の文字がたとえば a だった場合 <div class a と <div classa では意味が異なる。しかし、タグの終端を探す目的ではこの2つの状態を区別する必要はない。

また、属性中の文字参照はトークンの区切り位置には影響しないため無視します。

doctypeとbogus commentの状態管理

小なり記号 < で始まるものがタグ以外にもいくつかあります。

コメント (<!--)
doctype宣言 (<!DOCTYPE)
CDATAセクション (<![CDATA[)
bogus comment: コメントに準じて扱われる不正な宣言 (<!, <?, </)

これらのうちCDATAセクションの内部はテキストトークンとして扱う必要があり、それ以外は開始 (<) から終端 (>) までで1つのトークンを形成します。

まず、それぞれの終端がどのようなルールで決まっているのかを確認します。

実は、bogus commentとdoctype宣言は次の > で確実に終端されます。bogus comment stateについては仕様の記載から明らかです (> でしか脱出できないが、 > が来たら確実に脱出できるような状態遷移になっている)

doctypeは一見するとより複雑そうに見えますが、実はHTMLではdoctypeも > で必ず終端されるルールになっています。特に DOCTYPE public identifier (double-quoted) state, DOCTYPE public identifier (single-quoted) state, DOCTYPE system identifier (double-quoted) state, DOCTYPE system identifier (single-quoted) state では引用符中であるにもかかわらず > を発見するとdoctypeから脱出するルールになっています。

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML <4.01> Transitional//EN">
<!--                                         ^ ここで終端される (parse error) -->

明らかに > を最初に探すことを想定するルールになっています。わざわざこのような構造になっているのを使わない手はないので、オートマトン上ではdoctypeトークンはbogus commentトークンと同一視してしまうことにします。これにより、最初の <!DOCTYPE を検出するために専用の状態を持つ必要がなくなります。

コメントの状態管理

コメントはscript dataと並んでサブ状態の多い状態のひとつです。しかし、エラー条件を無視して丁寧にオートマトンをほどいてみると、終端条件は以下のように記述できることがわかります。

末尾が --> の場合。ただし、 -- がコメント開始の -- と重複しているケース () も許可する。
末尾が --!> の場合。ただし、 -- がコメント開始の -- と重複しているケースは許さない。 (<!--!>, <!---!> は終端されていない)

この条件であれば、途中の文字列を全て確認しなくてもコメントの終端かどうかを判定することができるため、必ずしも明示的にサブ状態を持つ必要はありません。 <!-- とそれ以外の <! を区別するために <!- などの途中状態を持つのも面倒なので、今回は以下のように実装します。

オートマトン上ではbogus commentと同一視する。
> によって終端されそうになったときにコメント形式かどうかを調べ、コメントとして開始されているのにコメントとして終端されていないときは状態をbogus commentに戻して再開する。

コメントトークンの扱い

コメントノードはDOM上に実体として存在し、中身をdataとして取得できます。 (ReactDOMがテキストノードを区切るために使ったりする)

このdataというのは真っ当なコメントの場合は  で挟まれた部分のテキストがそのまま入っています (たとえば  であれば両端の空白を含めた foo がdataになる) が、例によってHTML構文では真っ当ではないコメントが色々あるので正しくdataを計算できる必要があります。正しく閉じられていないコメント、bogus comment, また途中でEOFに遭遇してしまったコメントのことも考慮に入れる必要があります。EOFに遭遇した場合は、最短で閉じた場合に入っていたであろうdataが使われます。

正しく開始されているコメント ( で終端されている)
  - 普通に部分文字列を取ればよい
- 短すぎるコメント ()
  - 空文字列を返す
- 不正に終端されているコメント (--!> で終端されている)
  - <!-- と --!> で挟まれている部分文字列を返す
- 上記が途中でEOFに遭遇してしまった場合
  - 6文字以上で -- で終わっている場合
    - <!-- から -- までの間
  - 5文字以上で - で終わっているが -- で終わっていない場合
    - <!-- から - までの間
  - 7文字以上で --! で終わっている場合
    - <!-- から --! までの間
  - それ以外の場合
    - <!-- から末尾までの間
<! または </ で始まるbogus comment
- > で終わっていれば、 <! から > までの間 (</ も同様)
- EOFに遭遇してしまった場合は <! から末尾まで (</ も同様)
<? で始まるbogus comment
- > で終わっていれば、 < から > までの間
- EOFに遭遇してしまった場合は < から末尾まで

<!, </ は2文字分が開始として取り除かれるのに対し、 <? の場合は2文字目の ? がdataに含まれる点が罠です。

CDATAの状態管理

SVGまたはMathMLの文脈内で <![CDATA[ が出現するとCDATAセクションとなり、 ]]> が発見されるまでは & や < によるエスケープが無効になります。内部のテキストはリテラルな文字トークンとして解釈されます。

CDATAセクション内部の解釈はRAWTEXT (後述) とよく似ているので、これに準じて扱うことができます。それ以外に問題は2つあります。

SVGまたはMathMLの文脈内であることの判定 …… これはパーサーからフィードバックを受け取る形にする。 (未実装)
CDATAセクションの開始 (<![CDATA[) の検出 …… bogus comment状態で開始し、未出力テキストの先頭が <![CDATA[ になっていたらRAWTEXT系の状態に切り替えるという実装方法を取る。 (未実装)

RCDATAの状態管理

title, textarea の2つの要素は内部がRCDATAという特別なテキスト領域になり、対応する終了タグを除いて < によるエスケープが無効になります。

<title>
  <a> ← そのまま
  </b> ← そのまま
  <!doctype html> ← そのまま
  <!-- --> ← そのまま
  &quot; ← これは解釈される
</title> <!-- ←これは有効 -->

RCDATAをオートマトンのメイン状態の1つとして足してもよいのですが、文字参照なども含めた広汎な状態を複製しないといけないという問題があります。また、titleによってRCDATAに入った場合は </title> を、textareaによってRCDATAに入った場合は </textarea> を認識するため、どのタグだったかはいずれにしても記憶させないといけません。そこで、dataとRCDATAの区別は (タグの記憶も含めて) オートマトンのメイン状態とは別に直交した状態空間で管理することにします。具体的にはトークナイザに _endTagName という新たなフィールドを足し、その有無でRCDATAを区別します。

RCDATAが有効な場合は、オートマトンの状態遷移の一部を強制的に上書きすることになります。具体的には以下のようにします。

tag open stateの挙動をRCDATA less than sign stateのものに置き換える。つまり、 / 以外の全ての文字でテキストに復帰する。
end tag open stateの挙動をRCDATA end tag open stateのものに置き換える。
- 通常は </> を破棄するが、RCDATAでは破棄せずテキストの一部として扱う。
- それ以外の不正なタグは通常bogus commentの開始として扱われるが、RCDATAではテキストの一部として扱う。
tag name stateの挙動をRCDATA end tag name stateのものに置き換える。
- 期待した閉じタグでなかった場合は、ここまでの部分をテキストの一部として再解釈する。
- 期待した閉じタグだった場合は、RCDATAから脱出する。パース途中だった閉じタグは通常のタグと同じ状態に戻ってそのままパースされる。

仕様の記述上、このときの復帰タイミングが最適ではない点は注目に値します。具体的には、タグ名は英字の範囲内で全て読み切ってから比較を行うようになっています。たとえば <title> 内のRCDATAでタグを読み取るとき、以下のような挙動になります。

</title> → 閉じタグとして認識される
</titlename> → </titlename> まで読んだ時点で諦める
- 原理的には </titlen までで確定できるはず
</foo-bar> → </foo- まで読んだ時点で諦める
- 原理的には </f までで確定できるはず

実際のところ、この部分の子細が重要であるとはあまり考えられませんが、今回はこの記述にできるだけ忠実に実装します。

RCDATAのテキストトークンの扱い

通常のテキストトークンとRCDATA由来のテキストトークンでは、解釈すべきエスケープはほとんど同じですが、実は一点だけ異なるものがあります。それはNUL文字 (U+0000 NULL) の扱いです。

責務		data	RCDATA	RAWTEXT
tokenizer	`&`	✓	✓	×
tokenizer	`<`	✓	閉じタグのみ	閉じタグのみ
token	文字参照	✓	✓	×
token	改行の正規化	✓	✓	✓
token	NULの除去	読み飛ばす	U+FFFD	U+FFFD

NUL文字は以下のいずれかが満たされているときはU+FFFD REPLACEMENT CHARACTERに置換されます。 (いずれも構文エラー扱い)

文字参照 (,  など) として出現した場合。
または、RCDATA, RAWTEXT, PLAINTEXT, CDATA, script data など特殊なテキストの一部として出現した場合。
または、属性名・属性値の一部として出現した場合。

一方、リテラルなNUL文字が通常のテキストノードの一部として出現した場合の挙動は以下のようになります。 (こちらも構文エラー扱い)

<body> 内でなければ、 <body> 内に遷移する。 (他の非空白文字が出現したときと同様)
その後、当該NUL文字は読み飛ばす。 (U+FFFDは出力しない)

この差異に対応するため、data由来の生テキストトークンとRCDATA由来の生テキストトークンは区別する必要があります。

data由来の生テキストトークンにおいて、NULの除去をテキストトークン側の責務にするか、パーサー側の責務にするかは悩ましいところです。テキストトークン側の責務にしたほうが他と一貫性が取れている上、テキストの走査を1回でできてお得ですが、パーサー側はNULの有無を知る必要があるため、生トークンを解釈するとパーサーにとって必要な情報が欠落するというリーキアブストラクションが発生してしまいます。

RAWTEXT, PLAINTEXT, CDATAの状態管理

以下の要素内では開きタグだけではなく文字参照も無効です。

RAWTEXT内容モデルを持つ要素
- iframe
- noembed
- noframes
- noscript (<script> を実行するユーザーエージェントの場合のみ。 <script> を実行しないユーザーエージェントは noscript の内容を通常通り解釈する)
- style
RAWTEXTに準ずる要素
- script
PLAINTEXT内容モデルを持つ要素
- plaintext
CDATAセクションの内部 (<![CDATA[ ... ]]>)

RAWTEXTは文字参照が無効である点以外はRCDATAと同様です。

PLAINTEXTはRAWTEXTに加えて閉じタグを持たないため、より単純です。 (< なども全てそのまま出力すればよい)

CDATAセクションは終端の構文こそ異なるものの基本的にはRAWTEXTと類似の仕組みで扱うことができます。

script dataの状態管理

script要素はRAWTEXTに似ていますが、微妙にアレンジが加えられています。ユーザーにとっては些細な違いですが、パーサー実装には非常に大きな負担が強いられます。

以前に書いた<script>要素の構文という記事でも扱いましたが、ここでもあらためて説明します。

<script> タグを終端できるのは対応する閉じタグ </script> のみです。しかし、 </script> が出現すれば必ず閉じられるわけではなく、 <script> のネストが認識される場合があります。

大まかには、 <script> 内では以下のように最大2段階のネストを認識する必要があります。

<script>
  // 第1のネスト: HTMLコメント風の構文
  <!--
    // 第2のネスト: script要素風の構文
    <script>
    </script> // これによって外側のscript要素は閉じられない
  -->
</script>

この構造に反する開始構文 ( は最内部からコメントの外まで一気に脱出できます。

さて、このscript要素内の構文の困ったところは、構文自体は認識するが結果はテキストトークンとして出力しなければならないという点です。上の例だと  は全てテキストの一部なので、1文字ずつ入力されたら1文字ずつ出力する必要があります。

通常のコメントやタグは未出力文字列を調べることで多くの情報を復元できますが、script要素内の場合はほぼ全ての文字を出力し切った状態で入力を処理する必要があるため厄介です。

普通に状態機械を書くなら以下のようになります。

ネストなし
- 基本状態 (script data)
- 閉じタグ候補状態 —— 未出力文字列にデータが保持されているため、陽に状態を持たなくても何とかなる
  - < で終わるとき (script data less-than sign)
  - </ で終わるとき (script data end tag open)
  - </ + タグ名 (script data end tag name)
- <! で終わるとき (script data escape start)
- <!- で終わるとき (script data escape start dash)
コメント風構文内
- 基本状態 (script data escaped)
- - で終わるとき (script data escaped dash)
- -- で終わるとき (script data escaped dash dash)
- 閉じタグ候補状態 —— 未出力文字列にデータが保持されているため、陽に状態を持たなくても何とかなる
  - < で終わるとき (script data escaped less-than sign)
  - </ で終わるとき (script data escaped end tag open)
  - </ + タグ名 (script data escpaed end tag name)
- <s で終わるとき (script data double escape start -- "s")
- <sc で終わるとき (script data double escape start -- "sc")
- <scr で終わるとき (script data double escape start -- "scr")
- <scri で終わるとき (script data double escape start -- "scri")
- <scrip で終わるとき (script data double escape start -- "scrip")
- <script で終わるとき (script data double escape start -- "script")
コメント風構文内、ネストした <script> 内
- 基本状態 (script data double escaped)
- - で終わるとき (script data double escaped dash)
- -- で終わるとき (script data double escaped dash dash)
- < で終わるとき (script data double escaped less-than sign)
- </ で終わるとき (script data double escape end -- "")
- </s で終わるとき (script data double escape end -- "s")
- </sc で終わるとき (script data double escape end -- "sc")
- </scr で終わるとき (script data double escape end -- "scr")
- </scri で終わるとき (script data double escape end -- "scri")
- </scrip で終わるとき (script data double escape end -- "scrip")
- </script で終わるとき (script data double escape end -- "script")

オートマトン上に状態を陽に持ちたくなければ、出力済み文字列から必要な接尾辞だけを取り出して保存しておくという方法が考えられます。

pre, listing, textareaの状態管理

あとでかく

EOFの処理

タグ等の途中でEOFになった場合の結果はトークンにより異なります。

中途半端な開始タグ、終了タグは破棄されます。
中途半端なDOCTYPE, コメント、bogus commentはその時点での内容のまま出力されます。

ただし、トークンがテキストトークンに戻る可能性があるケースではテキストトークンとしての性質が優先されます。これには以下が含まれます。

< の直後にEOFになった場合は、 < はテキストとして出力されます。
RCDATAやRAWTEXTの終了タグが未確定の状態でEOFになった場合には、終了タグがテキストとして再解釈されて出力されます。
- たとえば </title の直後にEOFになった場合は </title はテキストとして出力されます。
- 一方、 </title (←空白に注意) の直後にEOFになった場合は </title は終了タグであることが確定しているので破棄されます。

また、 </ の直後にEOFになった場合も </ はテキストとして出力されます。