'(you lisp me)

Lispって何だ

ブラウザを作ろうとしてたらいつの間にか正規表現エンジンもどきを作り始めていた話

題の通りです。
ブラウザって言うと語弊があって、正確にはHTMLレンダリングエンジンを作ろうとしていました。
WebkitGeckoなどに相当するものですね。

経緯

最近、MozillaServoという新しいレンダリングエンジンを開発しているのはご存知でしょうか。
並列性やパフォーマンスを重視しているそうで、どんな実装になっているか興味を持つのは当然ですよね。
まだ若いプロジェクトだし、自分でも理解出来るんじゃないかと思ってソースコードを読んだりもしました。
まあ、ほとんど理解出来ませんでしたけどね!そもそもRustの知識が足りなかった……。

そして、とりあえず自分でレンダリングエンジンっぽいものを実装してみようと考えました。
Rustは追々勉強して行くということで、その構造だけでも理解してやろうというわけです。

言語は最近ハマったCommon Lispで書こうということで始まりました。
さらに若気の至りでGithubにOrganizationまで作って……実はこれ去年作ったんですよね(汗)

github.com

ちなみに開発にあたって、以下のページを大いに参考にさせていただいています。

ブラウザのしくみ: 最新ウェブブラウザの内部構造 - HTML5 Rocks
Let's build a browser engine! Part 1: Getting started

実際に開発を始めたのは先々月辺りからで、まずはHTMLをパースしてレイアウティングするところから始めました。
Geckoは描画バックエンドにCairoを使っているようなので、とりあえずそれを真似てcl-cffi-gtkに入っているCairoを使うようにしました。
が、しかし何故かcairo-show-glyphs関数が見当たらず。これが無いとテキスト表示位置を細かく制御出来ない……。

だったらバックエンドも自分で作ってしまえ、ということでOpenGLのシェーダーを利用して文字列を描画するライブラリも開発中です。

github.com

モチベーションは以下の2つ。

lab.sonicmoov.com

GLyphy: high-quality glyph rendering using OpenGL ES2 shaders - Behdad Esfahbod from Behdad Esfahbod on Vimeo.

これについてはLisp Advent Calendar 2016の方で取り上げようと思っています。
正直どの程度のパフォーマンスで描画出来るのか未知数ですが、面白そうなのでやってるという感じです。

さあこれで開発が振り出しに戻ったどうしよう。とりあえずレンダーツリーを作れるようにしようか。
しかしブラウザ内部で使われているHTML・CSSパーサーはどうやら普通のやつとはちょっと違うみたいで、パースしながらレンダーツリーを構築している(?)らしいです。あと、多少記述が不正でも良い感じに解釈して処理してくれるとか。

ということは、パーサーも自分で作らないといけない感じですか。

常人ならこの辺で諦めそうですが、僕はしつこい男なので、なんとかやり遂げたい。
こんなことする暇あるのって学生のうちだけだろうし。

というわけでやっと本題に辿り着きましたね。
HTMLはcl-html5-parserというのがあったので、ひとまずそっちで処理しています。
CSSパーサーは自分で作ることにしました。今回はその話です。

CSSパーサーを作る

構文解析器を作る前にまず字句解析器を作らないとですね。
詳しい構文とかトークンについてはCSSの仕様書を読みました。

これを見るとLex前提で書かれているのでcl-lexを使えば早そうだなと思ったんですが、使い方がよく分からなかったので自前で実装することにしました。

なんとなく、正規表現が羅列されていることからcl-ppcreを使えば余裕だろうと踏んで、まずはそれを書き出してみました。

(defparameter +h+ "[0-9a-f]")
(defparameter +num+ "[+-]?([0-9]+|[0-9]*\.[0-9]+)(e[+-]?[0-9]+)?")
(defparameter +nonascii+ "[^\\0-\\177]")
(defparameter +unicode+ "\\\\[0-9a-f]{1,6}(\\r\\n|[ \\n\\r\\t\\f])?")
(defparameter +escape+
  (format nil "(~A)|\\\\[^\\r\\n\\f0-9a-f]" +unicode+))
(defparameter +nmstart+
  (format nil "[_a-z]|(~A)|(~A)" +nonascii+ +escape+))
(defparameter +nmchar+
  (format nil "[_a-z0-9-]|(~A)|(~A)" +nonascii+ +escape+))
(defparameter +ident+
  (format nil "[-]?(~A)(~A)*" +nmstart+ +nmchar+))
(defparameter +name+
  (format nil "(~A)+" +nmchar+))
(defparameter +nl+ "\\n|\\r\\n|\\r|\\f")
(defparameter +string1+
  (format nil "\\\"([^\\n\\r\\f\\\\\"]|\\\\(~A)|(~A))*\\\"" +nl+ +escape+))
(defparameter +string2+
  (format nil "\\'([^\\n\\r\\f\\\\']|\\\\(~A)|(~A))*\\'" +nl+ +escape+))
(defparameter +string+
  (format nil "(~A)|(~A)" +string1+ +string2+))
(defparameter +badstring1+
  (format nil "\\\"([^\\n\\r\\f\\\\\"]|\\\\(~A)|(~A))*\\\\?" +nl+ +escape+))
(defparameter +badstring2+
  (format nil "\'([^\\n\\r\\f\\\\']|\\\\(~A)|(~A))*\\\\?" +nl+ +escape+))
(defparameter +badstring+
  (format nil "(~A)|(~A)" +badstring1+ +badstring2+))
(defparameter +badcomment1+ "\\/\\*[^*]*\\*+([^/*][^*]*\\*+)*")
(defparameter +badcomment2+ "\\/\\*[^*]*(\\*+[^/*][^*]*)*")
(defparameter +badcomment+
  (format nil "(~A)|(~A)" +badcomment1+ +badcomment2+))
(defparameter +U+ "u|\\\\0{0,4}(55|75)(\\r\\n|[ \\t\\r\\n\\f])?|\\\\u")
(defparameter +R+ "r|\\\\0{0,4}(52|72)(\\r\\n|[ \\t\\r\\n\\f])?|\\\\r")
(defparameter +L+ "l|\\\\0{0,4}(4c|6c)(\\r\\n|[ \\t\\r\\n\\f])?|\\\\l")
(defparameter +w+ "[ \\t\\r\\n\\f]*")
(defparameter +baduri1+
  (format nil "(~A)(~A)(~A)\\((~A)([!#$%&*-~~]|(~A)|(~A))*(~A)"
    +U+ +R+ +L+ +w+ +nonascii+ +escape+ +w+))
(defparameter +baduri2+
  (format nil "(~A)(~A)(~A)\\((~A)(~A)(~A)"
    +U+ +R+ +L+ +w+ +string+ +w+))
(defparameter +baduri3+
  (format nil "(~A)(~A)(~A)\\((~A)(~A)"
    +U+ +R+ +L+ +w+ +badstring+))
(defparameter +baduri+
  (format nil "(~A)|(~A)|(~A)" +baduri1+ +baduri2+ +baduri3+))

(defparameter <ident> +ident+)
(defparameter <atkeyword> (format nil "@(~A)" +ident+))
(defparameter <string> +string+)
(defparameter <bad-string> +badstring+)
(defparameter <bad-uri> +baduri+)
(defparameter <bad-comment> +badcomment+)
(defparameter <hash> (format nil "#(~A)" +name+))
(defparameter <number> +num+)
(defparameter <percentage> (format nil "(~A)%" +num+))
(defparameter <dimension> (format nil "(~A)(~A)" +num+ +ident+))
(defparameter <uri> (format nil
  "(~A)(~A)(~A)\\((~A)(~A)(~A)\\)|(~A)(~A)(~A)\\((~A)([!#$%&*-\\[\\]-~~]|(~A)|(~A))*(~A)\\)"
  +U+ +R+ +L+ +w+ +string+ +w+ +U+ +R+ +L+ +w+ +nonascii+ +escape+ +w+))
(defparameter <unicode-range>
  "u\\+[?]{1,6}|u\\+[0-9a-f]{1}[?]{0,5}|u\\+[0-9a-f]{2}[?]{0,4}|u\\+[0-9a-f]{3}[?]{0,3}|u\\+[0-9a-f]{4}[?]{0,2}|u\\+[0-9a-f]{5}[?]{0,1}|u\\+[0-9a-f]{6}|u\\+[0-9a-f]{1,6}-[0-9a-f]{1,6}")
(defparameter <cdo> "<!--")
(defparameter <cdc> "-->")
(defparameter <colon> ":")
(defparameter <semicolon> ";")
(defparameter <bstart> "\\{")
(defparameter <bend> "\\}")
(defparameter <pstart> "\\(")
(defparameter <pend> "\\)")
(defparameter <bbstart> "\\[")
(defparameter <bbend> "\\]")
(defparameter <s> "[ \\t\\r\\n\\f]+")
(defparameter <comment> "\\/\\*[^*]*\\*+([^/*][^*]*\\*+)*\\/")
(defparameter <function> (format nil "(~A)\\(" +ident+))
(defparameter <includes> "~=")
(defparameter <dashmatch> "\\\\|=")

うわ……。
バックスラッシュをエスケープしなくちゃいけないのが辛すぎる。というか別の正規表現を埋め込んだり出来ないんですか。
仕方がないからformatでそのまま埋め込みました。ダサい。
cl-interpolで楽をしようともしたんですが、バックスラッシュの数がどうやっても合わなかったので断念。

とりあえず、この正規表現どもを利用して処理を書いて、一度動かしてみました。
行ったのは、対象のCSS文字列の先頭位置から全ての正規表現を適用して、マッチした一番長い文字列(最長一致)をトークンベクターに追加していくという処理です。その後は適用位置をずらして同じ処理を最後まで繰り返すだけ。

それで、簡単な短いCSSなら正常にトークン化出来たのですが、どこが間違っているか分からないのでBootstrapのCSSファイルで試してみました。
で、これのベンチマーク結果とかを載せたかったんですが、処理が終わりませんでした……。

いや、bootstrap.cssをトークン化出来ないのはマズイだろと。
最適化オプション付けても変化無いし。

多分、ここで正規表現エンジンを使うべきでは無いんだろうなと思ったので、僕はここでやり方を変えることにしました。
エンジンなんてリッチなものは今回は要らないし、CSSをトークン化するのに特化したものを作ればなんとかなるだろうと。

僕が考えたのは、正規表現を絞り込んでいく感じの解析方法です。
以下のようなイメージ。

対象文字列: common-lisp

正規表現群:
"country"  -> "ountry"  -> "untry"   -> Fail...
"com+on" -> "om+on" -> "m+on"  -> "m*on" -> "m*on" -> "n" -> 6
"com"        -> "om"       -> "m"         -> 3

結果: common
残りの文字列: -lisp

これを思いついた時は、lexって実はこういうことやってるんじゃないの?と思ったんですが、実際どうなんでしょうか。
計算回数で言えば正規表現エンジンと大差無いと思うんですが、こちらでは文字列の長さは数えていません。
それが速度に影響しているとは考えにくいですが、なんとなくこっちの方が効率が良いような気がします。
根拠はありません。

というかここに書いている段階で車輪の再発明感が出てきて、今にもこの記事を消したい衝動に駆られています。
せっかくいっぱい書いたので消しませんけど。

これの実装はほぼ出来ていて、あとは正規表現をリスト形式に落とし込むだけなんですが、コードに気に入らない部分があるのでまだそこには至っていません。そのまま変換するには足りない表現もあるし({n,m}とか)。

ちなみにこれです。

よく見るとこれ正規表現エンジンと同じことやってるやん?ていうのが今回のオチです。
本当は、決定性有限オートマトンを実装したよ!とかドヤ顔で書きたかったんですが、可変長文字列にマッチするならNFAなんじゃね?とか悩んだ挙句やめました。

久しぶりに長い記事を書いたら疲れた……。