🧊

ECMAScript `RegExp`パーサー実装の手引き Part.3

続きもこれで最後。

ECMAScript RegExpパーサー実装の手引き Part.2 | Memory ice cubes https://leaysgur.github.io/posts/2024/08/27/093543/

仕上げとして、パースしたはいいが、意味的に問題ないか？をチェックするEarly Errorsの部分。

Early Errorsとは

https://tc39.es/ecma262/2024/multipage/text-processing.html#sec-patterns-static-semantics-early-errors

ここに計21項目のチェックリストがあって、パターンをパースできたとしても、これに違反してるとSyntax errorにしないといけない決まり。

Annex Bをサポートする場合は、1項目の追加と、2項目の変更がある。

読めばわかるものも多いので、個別ではなくざっくり書いていく。

キャプチャグループ関連

  • キャプチャグループを形成する(の数が、2^32-1より多いとエラー
  • 名前付きキャプチャグループで、同じ名前が使われてたらエラー
    • ES2025では、特定条件下ではエラーにならない書き方もできるようになる
  • 名前付き後方参照で、参照されるべきキャプチャグループが存在してないとエラー
  • インデックス後方参照で、存在するキャプチャグループの数より大きいインデックスを指定してたらエラー

並び関連

  • {2,1}みたく、数量詞の大きさが逆順だとエラー
  • [z-a]みたく、レンジの並びが逆だとエラー
  • [a-\d]みたく、文字クラスエスケープがレンジに入っててもエラー

ちなみに、\d{4}の数字に使える最大の値は、2^53-1になってて途方もない。

サロゲートペア関連

  • Unicodeのコードポイントを直接書くとき、それが順当なコードポイントの並びになっていないとエラー

説明が難しいけど、たとえば、/(?<\uD800\uDBFF>)/相当（本当はそういう文字）はエラーになる。

Unicodeプロパティ関連

  • \p{}で、無効なプロパティを書くとエラー
  • \p{}で、UnicodeSetsModeじゃないとき、UnicodeSetsMode専用のプロパティを使うとエラー

有効なプロパティは、ユニコード本体のデータベースで管理されてる。

https://tc39.es/ecma262/2024/multipage/text-processing.html#table-nonbinary-unicode-properties https://unicode.org/Public/UCD/latest/ucd/PropertyValueAliases.txt

この長大な文字列の塊が、パーサーの実装サイズを圧迫してくる。

MayContainStrings関連

実装の手間という意味では、これが一番大変だった。

https://tc39.es/ecma262/2024/multipage/text-processing.html#sec-static-semantics-maycontainstrings

これは、パースした特定のノードがMayContainStringsという条件に合致する場合があり、それが出現場所によってはエラーになるというもの。

CharacterClassEscape :: P{ UnicodePropertyValueExpression } It is a Syntax Error if MayContainStrings of the UnicodePropertyValueExpression is true.

これは、

  • \P{}のネガティブな指定をしてるとき
  • その指定プロパティが、UnicodeSetsModeでのみ利用できるbinary property of stringsという種類だったら

というもので、たとえば、/\P{Basic_Emoji}/vがエラーになる。

CharacterClass :: [^ ClassContents ] It is a Syntax Error if MayContainStrings of the ClassContents is true.

これも同様に、文字クラスを否定で使ってるとき、中に上述のユニコードプロパティエスケープがあったらエラーになる。つまり、/[^\p{Basic_Emoji}]/vはエラーになる。

NestedClass :: [^ ClassContents ] It is a Syntax Error if MayContainStrings of the ClassContents is true.

最後、これが一番面倒くさいやつ。

まず、NestedClassはUnicodeSetsModeでのみ登場する記法。

で、UnicodeSetsMode時のClassContentsは、中身になりうる3つのパターンが、それぞれで異なる判定の仕方になる。

  • ClassUnion
    • 構成するClassOperandが、1つでもMayContainStringsならエラー
  • ClassIntersection
    • 構成するClassOperandが、すべてMayContainStringsならエラー
  • ClassSubtraction
    • 構成するClassOperandの、先頭がMayContainStringsならエラー

で、ここでMayContainStringsになるのは、

  • 上述のstringsなユニコードプロパティを含む
  • ClassStringDisjunctionを含んでいて、
    • \q{}: それが空っぽである
    • \q{a|bc}: 文字列を含む
    • \q{a|}: 空っぽを含む

という場合になってる。

実装として悩ましいのは、

  • それぞれ個別の要素をパースした時に、それがMayContainStringsかどうかはわかっても
  • その親でネガティブ指定がされているか、NestedClassならどのタイプのClassContentsなのかがわかってないと

その場でエラーにはできないところ。

考えられる実装パターンとして、即座にエラーにしたい場合は、

  • どこまでも親からのフラグをバケツリレーしていく必要がある
  • あらゆる処理の返り値にMayContainStrings: booleanを足す必要がある

という、コードの煩雑さがつきまとうデメリットがある。（なら、コンテキストで動的に状態管理するほうがマシかも）

もしくは、即座にエラーにしない案で、後で材料が揃ってからチェックする。 こっちはコードが圧倒的にクリーンになる代償に、パフォーマンスが少し犠牲になる可能性がある。

まとめ

パーサー実装の勘所をまとめるならば、

  • UnicodeModeによって、処理ユニットがUTF-16かUnicode単位かを決める部分
  • キャプチャグループのEarly Errorsのために、パターン全体を2度パースする必要がある部分
  • UnicodeSetsModeに関するMayContainStringsのEarly Errorsを処理する部分

というあたりを、コードの簡潔さを取るか、どこまでもパフォーマンスを優先するのかで設計することくらいか。

Annex BやEarly Errorsを実装しない判断をすることもあるはずで、それならもっと工数を減らせる。

というわけで・・・、

  • 仕様書の読み方も知らず
  • パーサーなんか書いたこともない
  • Rustもそこまで書けるわけでもない

そんな人間のソロでも1ヶ月そこそこで形にはできたので、そんなに難易度は高くないトピックなんやろうなと思う。ただ、やってる人が少ないだけで。

Part.1から3まで通して、なんか間違ってたらこっそり教えてください。