ブラウザはCSSのセレクタを右から読む、ほんまか？

先日、 ブラウザ君「ワイはCSSのセレクタを右から読むんや」 という記事を読みまして、ちょっと気になったので後で確かめようと思っていたのですが、なんとなくそのままになってしまいやや旬を逃した感がありつつ、ツッコミを入れてみようと思います。
なお『ワイ「ほげほげ」』みたいな形式は使いません¹。恥ずかしいので。

私は仕事でChromiumのソースコードをよく読んでいるので、ChromiumのソースコードからCSSの処理を見つけて、それを基準にして解説しようと思います²。そのため、他のブラウザのレンダリングエンジンと異なる最適化が施されている可能性があります。また、現在のソースコードがそうでも、将来的に別の方法に変更される可能性もあります。あくまで、ブラウザの処理の一例であることをご了承ください。

ChromiumはC++で開発されていて、私もC++畑の猫ですが、今回の記事は随所にリンクを挿入しつつも、具体的なC++のコードはなるべく持ってこないようにしようと思います。Chromiumのソースコードを確認したい方はリンク先を見てください。

なおChromiumプロジェクトはChromium Code SearchというWebサイトをホストしていて、膨大なソースコードをWeb上で検索できます。ソースコード内部は識別子などすべてリンクが張られていて、ソースコードが膨大すぎて並のマシンでは解析だけでもだいぶ時間がかかる上にものすごい速度で積み上がっていくコミットに追従しないといけないのでこんな真似は計算資源を余るほど持っていないとできません。さすが天下のGoogleのマシンパワーと言ったところですが、僻んでも仕方ないし便利なので有り難く使わせてもらいましょう。

要素のマッチの仕組み

CSSセレクタを使ってDOM要素を抽出するというのは、言い換えれば「あるDOM要素がCSSセレクタにマッチしているか」という判定が必要になるということです。

Chromiumの内部でCSSセレクタは blink::CSSSelector というクラスで定義されています。
https://cs.chromium.org/chromium/src/third_party/blink/renderer/core/css/css_selector.h?g=0

ただ、ややこしいのは、我々がイメージするいわゆるCSSセレクタ、つまり #i .c a > b のようなもののうち、一個の blink::CSSSelector が表現するのは #i や a などの単一の構文要素からなるセレクタだけであり、いわゆるCSSセレクタは blink::CSSSelector の配列で表されます。
そしてここが重要なのですが、 blink::CSSSelector の配列は、基本的に右側の構文要素が先頭に来ます。この点で、ブラウザがCSSセレクタを右から読むというのは部分的には間違いではありません。
例に上げた #i .c a > bであれば、 |>b| a| .c|#i| のような配列になります（あくまでイメージです） | で区切られているのが一つの blink::CSSSelector で、一つの要素は一つのセレクタと、次セレクタとの関係性を保持しています。

ただし、物事には例外があって、この順序が逆転しない関係性もあります。 .c1.c2 のように、2つの単一セレクタを間を開けずに書くことがありますが、その場合は |.c1|.c2| という風に blink::CSSSelector の配列に並びます。

要素のマッチはChromiumのソースコードでは blink::SelectorChecker というクラスを使って行われます。
https://cs.chromium.org/chromium/src/third_party/blink/renderer/core/css/selector_checker.h?g=0
例えば、 |>b| a| .c|#i| で表されるCSSセレクタが要素とマッチするかどうかを確認するには、こんな手順になります。

1. 要素のタグ名が >b に一致するかどうかを調べる。一致していなかったらその時点でミスマッチと判定する。
2. 関係性が >（子要素） なので、親要素のタグ名が a に一致するかどうか調べる。一致していなかったらその時点でミスマッチと判定する。
3. 関係性が （子孫要素） なので、一致するまでclass 属性に c が含まれるかどうか調べながら親要素を遡る。一致するものが見つからなかったらミスマッチと判定する。
4. 関係性が なので、一致するまでid 属性が i に一致するかどうか調べながら親要素を遡る。一致するものが見つからなかったらミスマッチと判定する。

もちろん実際はもっと汎用的なアルゴリズムですが、配列先頭から順に親ノードをたどりながら一致するかどうか調べるという手順なのは間違いありません。
最悪計算量はセレクタの長さNとDOM要素の深さMに対してΟ(N+M)ですね。

一番遅いクエリ

ChromiumでCSSセレクタを使用したクエリは blink::SelectorQuery というクラスで実装されています。
https://cs.chromium.org/chromium/src/third_party/blink/renderer/core/css/selector_query.h?g=0
このクラスの中で、クエリを実行するアルゴリズムはいくつかあり、Chromiumはセレクタの内容によってどの方法を使うかを変えています。その中で、一番遅いクエリ（ソースコードでも ExecuteSlow という名前が付いています）からまずは紹介しようと思います。

このクエリは、検索範囲に含まれる全てのDOM要素をトラバースします。
DOM要素のトラバースは、基準となるノード以下の深さ優先探索です。トラバース中に列挙した全ての要素に対し、上記の要素マッチアルゴリズムを適用して、マッチした要素を結果の配列に入れていく、という処理を行います。
ただしこの操作はDOM要素数Nに対しΟ(N)かかってしまうので、ページの内容にもよりますが、毎回実行するには遅すぎるケースがあるだろうことは容易に想像がつきます。
そこで、最適化が可能な場合は次の処理を行います。

キャッシュを利用したクエリ

ブラウザは、id, クラス, 要素名を使ってキャッシュを作っています。昔から存在する getElementById 、 getElementsByClassName や getElementsByTagName のためのものですが、このキャッシュはCSSセレクタにも利用することができます。
元記事の方で、

ブラウザ君「まず、このページにあるa要素を全部探すで！」

とやっていましたが、a要素のキャッシュはDOMが構築された時、あるいは更新された時に同時に作成されているので探すまでもないわけです（もっともこれは、キャッシュを構築する時の様子を表現しているのかもしれないですが）。
つまり、セレクタの右端が要素もしくはクラス名（[class~="hoge"] のようなパターンも含む）の場合は、キャッシュの中から上記のマッチアルゴリズムで一致するケースを探すことになります。

idを利用したクエリ

さて、ここからが問題なのですが、元記事にある #header a のようなCSSセレクタでは、上記の遅いクエリは実行されませんし、要素名のキャッシュを利用したクエリも実行されません。
なぜなら、上述したようにidはキャッシュされていて、idはドキュメント内でユニークであることが期待できるからです。同じidを複数の要素に振ってもブラウザは解釈してくれますが、この節のアルゴリズムは実行できなくなります。
idがユニークなら、その要素の下から探索した方が早い可能性が高いです。よって、 #header a というCSSセレクタの場合はidが先に読まれ、idが付いた要素の下でセレクタに一致する物を探すという処理が行われます。

このケースがあるので、「右から読む」と言われると、そうとも言えないよ、と言いたくなってしまいます。

でもやっぱりBEMを使おう

クラスを利用したセレクタはキャッシュを使えるし、セレクタが単純なほどマッチも軽くなるので、結局のところ単一のクラスは最速のセレクタであることがわかると思います。
もちろん同じように単一のタグ名や単一のidも最速ではありますが、クラスは一つの要素に複数つけることも出来るし、クラスを付ける・付けないはマークアップで制御できます。
なので、BEMを使うと最適化されたCSSが書ける、という元記事の主張は間違っていません。

1. タイトルにちょっと影響が…… ↩

2. というか他のブラウザのソースコードをまともに読んだことがないので大量のソースコードからCSSの処理を見つけるだけで一苦労だしめんどい ↩