時計を壊せ

駆け出してからそこそこ経ったWebプログラマーの雑記

Mustache Templateの実装を書いた

この記事はPerl Advent Calendar 15日目の記事です。

qiita.com

さて

ということで、ひさしぶりにCPANizeしました。なんか早速bug fixが見つかって早々に0.02です。

metacpan.org

今のPCでは初めてのCPANizeだったようで ~/.pause がなくてちょっと焦った。

なんで?

人生色々。様々があります。 たとえば、やることに追われたり、悩ましい考え事に苛まれたり、やることに追われたり、やることに追われたり、様々があります。

一方でISUCONも迫っていました。PerlでISUCONに勝ちたいので日頃の仕事でなかなか書く機会が減ってしまったPerlを素振りしたくなってきます。 気分転換がてら、Perlでちまちまなんかを作ってみるのは良いかもしれないと思いました。

そんななか、趣味でプログラミングするのにちょうど良さそうな題材として、Mustache Templateが出てきました。

Template::Mustacheが1.0系になってめっちゃ遅くなったことに困っていそうな人をみかけたのです。 確かにめちゃくちゃ遅くなったのは知っていて、たしかに調べてみても代替モジュールによさげなのがなかったのです。

まあ簡単そうだしちょうどよいだろう。ミニマルなものを作っていい感じにしよう。と実装しながらMustache Templateの仕様を追っていきます。

すると、なんとも色々な仕様がでてくるではありませんか。

lambdaとか継承テンプレートとかmustacheで1回も使ったことないぞ!などとと思いましたが、それは自分はText::XslateやText::MicroTemplateを使っていたのでまあそれはそう。

まあ必要なひともいるんだろう、そうなるとこれもたぶんほしいんだろう、これを実装するならこれもまあ実装されていて然るべきだろう、などとうっかり色々実装していくと、あれよあれよと芋づる式に全部の仕様を実装してしまいました。

なんで????

実装

Lexerでトークンに分割して、ParserでAST*1を作り、Compilerでコンパイルするという王道な実装となっております。

Lexerといってもそんなに丁寧なものではなくて、素朴なLexerとしてはたとえば "foo{{bar}}" があったときに、これを ["foo", "{{", "bar", "}}"] と分割するのが一般的かと思います。 もうちょっとParser寄りな感じで、["foo", "{{bar}}"] という感じでタグの構文そのものだけ解釈してトークン分割をする実装にしました。

これにはちょっと理由があって、Mustacheって{{}}というデリミタでタグを構成するのがデフォルトなのですが、このデリミタを変更するタグが存在するので、Lexerはそれを解釈しないと正しくトークン分割ができないのです。すると、まあそこまでしてるのに {{bar}} を分ける必要もなかろうということで自ずとそれらを一緒のトークンにまとめて扱うことにしました。

そして、Parserはその一列のトークンを解釈してMustache Templateとしての文法の構造をデータ構造上の構造に構造化します。いわゆるASTというやつですね。 たとえば、Mustacheには{{#condition}}yes{{/condition}}みたいな複数のタグを使って1つの構造を作るみたいな文法をもっているので、これはAST上もこの分岐の子要素みたいな感じで整理してあげます。

ASTを使うとめっちゃ簡単にレンダリング処理が実装できます。 素朴にレンダリングする事もできると思いますが、今回はせっかくなのでキャッシュしたテンプレートの実行効率を高めるべくCompilerとして実装しようと思います。

Compilerってなんやねんとなると思いますが、これはText::MicroTemplateよろしくテンプレートに合わせたパターンの文字列を生成するPerlのコードを文字列で作り上げてevalすることで、事前に分岐などが最適化されたコードを作る操作を指しています。

Perlコードの生成時はASTを解釈して細かい分岐をたくさん辿りますが、生成されたPerlコードはある程度の分岐が事前に解決されたものになるので直にASTを毎度解釈するより高速に実行することができるという寸法です。

Apache::LogFormat::Compilerなど様々なCPANモジュールでこのアプローチは取られています。 なんなら、こういうコードを簡単に作るためのSub::Quoteってやつまであり、これはMooの実装で使われていたりもします。

ほか、render というテンプレートをパースして即レンダリングするというインターフェースもあるんですが、このケースではコンパイルしたものが1度実行したら廃棄される前提がありかつコンテキスト変数*2がコンパイル前にすでに決定しているという特徴があるので、コンテキスト変数をヒントにASTを最適化することが可能です。 ということで、そういう処理を挟んであり、うまくいくケースではこの最適化をやらない場合と比べて3倍くらい速くなるようになることがわかっています。

ほかにも、正規表現を最適化していたりなど、地味な高速化を測っている箇所がちょいちょいあったりします。

出来栄え

github.com

このテストケースをすべてPASSしています。やったね。 ついでにテストカバレッジもステートメントレベルでは100%*3で、ほかも90%台後半まで網羅してあります。

パフォーマンスも簡単なテンプレートをレンダリングするベンチマークで比較してみました。 Template::Mustacheに比べてパースの速度が10倍、レンダリングする速度がパース済のテンプレートをキャッシュしているケースで3倍、キャッシュしていないケースで40倍となることがわかっています。 やったね。

なお、Mustache::Simpleというモジュールがあるのですが、これはテストケースをpassしなかったので比較していません。(存在しない変数を無視せずにエラーにしてくる仕様非準拠な挙動だけ確認してあとは確認してない)

ということで、まあそれなりに実用に耐える品質ではあろうと思ったのでCPANnizeしておきました。

これを作る時間でISUCONの素振りすればよかったのでは?

ISUCONの素振りってまとまった時間が必要じゃないですか……。 これ細切れの微妙な時間でちまちま進めたのです。素振りもしたかった……。

そんなわけで

まあ、完成したのでもしご入用の方はお試し下さい。

*1:Abstract Syntax Tree

*2:テンプレートに与える変数

*3:普通は絶対にこのパスは通らないところとかは除いているのでちょっとズルかも