CMakeをSchemeにする -- S式のtokenize

意外な伏兵。。
CMakeはそれなりに高速なスクリプティング機能が有るため、やる気になればそれなりに実用的なScheme処理系にできるんじゃないかという気がしている。が、適当にやったらやっぱり遅かったのである程度は真面目にやる必要がありそうだ。

適当な実装

S式をtokenizeするには、適当な状態遷移マシンを用意して1文字づつ処理すればできる。 ...できるんだけど超遅い。以下、yuniの簡易テストコード https://github.com/okuoku/yuni/blob/cce309e917efbb7e0787e5bed7dd040996f9e452/_sanity.sps を読むのに掛かった時間で比較する。
素朴な実装はこういう感じになる: https://gist.github.com/okuoku/6a1a4ea859735cdc19779db3314bb63d

string(SUBSTRING "${${ctx}_buf}" ${${ctx}_cur} 1 __input)
...
if(("${__input}" STREQUAL " ")
           OR ("${__input}" STREQUAL "\r")
           OR ("${__input}" STREQUAL "\n")
           OR ("${__input}" STREQUAL "\t")
           OR ("${__input}" STREQUAL "\"")
           OR ("${__input}" STREQUAL ";")
           OR ("${__input}" STREQUAL "(")
           OR ("${__input}" STREQUAL ")")

つまり、単に1文字をSUBSTRINGによって取り出し、それを文字列比較で比較していけば良い。(CMakeのSUBSTRINGはSchemeと違って第二引数として長さを取る。)
が、これが超遅い。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m7.699s
user    0m7.671s
sys     0m0.015s

意外なことに、ORの部分を正規表現に置き換えると速度が向上する。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m5.849s
user    0m5.718s
sys     0m0.031s

つまり、正規表現の破棄/生成コストよりも、ORの連鎖を処理するコストの方が高いと言える。高速なCMakeスクリプトを書きたければ行数を減らすしかない。

tokenを正規表現で引く実装

正規表現のコストが文字列比較並に安いのならば、正規表現を使った方が良いに決まっているので、正規表現でtokenを引く実装が考えられる: https://gist.github.com/okuoku/2beb787118d0cff574bdc817d4c547ac

        elseif("${${ctx}_buf}" MATCHES "^(\\(|\\)|\\[\\]|'|`|#vu8|#u8|,@|,|#f|#t|#\;|#\\\\[a-z]+)(.*)")

CMakeはifコマンドに正規表現マッチ機能が有り、サブマッチを変数にバインドして直接アクセスできる。これを使用することで、tokenの抽出を行うことができ、tokenizer自体もまずまずコンパクトに書くことができる。速度の方もそれなりに改善して、

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m1.802s
user    0m1.781s
sys     0m0.015s

半分以下のコストで処理できるようになった。
...が、高々11KiB程度のコードを読むのに2秒掛かるのはちょっと。。

REGEXP MATCHALLで一気にトークンに分割する方法

たぶん文字列をちょっとづつ読むというのが構造的に重い(文字列の確保と解放を繰り返すことになる)。というわけで、処理を2パスに分割し、tokenはstring(REGEXP MATCHALL)を使用して一気にCMakeのリストに変換できるように考える。
REGEXP MATCHALLをコードに適用する前に、以下の変換を行う:

ソース中のセミコロンをescapeする。CMakeのリストは単に文字列をセミコロンで区切ったものであるため、リストの内容にセミコロンを含めたいときは適当に処理する必要がある。個人的には、printableでない適当な文字に置き換える方法をよく採用している(手抜き)。
文字列中のdouble quoteを事前にエスケープする。
SRFI-30 ネスト化コメント( https://srfi.schemers.org/srfi-30/srfi-30.html )を削除する。CMakeの正規表現にはlazy matchが無いため、ネストされたコメントにマッチさせることはできない(はず)。
通常のセミコロン行コメントを削除する。

このうち、後段のdouble quoteのエスケープ置き換えと、ネスト化コメントの削除は単一パスで実行できる。また、セミコロンやダブルクォートの変換が入ってしまうので文字定数は事前に処理する必要がある。
この前処理を実施することでトークンは単一の正規表現で表現でき、stringコマンドのREGEXP MATCHALLによってリストに変換することができる: https://gist.github.com/okuoku/7fd831c53b9bf7e970fad5bbb4301985

function(yuni_sexp_tokenize out str)
    yuni_sexp_tokenize_preprocess(prep fil)
    string(REGEX MATCHALL 
        "\"[^\"]*\"|#vu8|#u8|#t|#f|#\\[a-z]*|#\\.|#|,@|,|[()`']|[^ \r\n\t()`']+|[ \r\n\t]+"
        lis
        "${prep}")
    set(${out} "${lis}" PARENT_SCOPE)
endfunction()

これは上2つの1トークンづつマッチしていく手法よりも圧倒的に速い。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake >/dev/null

real    0m0.121s
user    0m0.093s
sys     0m0.015s

100ms程度ならまぁ許容できる速度だと思う。ただし、この方法だとトークンの行番号とか桁位置が取れないという問題がある。

次の一手

次はヒープとGCの実現を考える。
CMakeはシェルスクリプトやawk、tclと同様に全ての変数は文字列となっていて型が存在しない。このため、変数は型アノテーションを行う必要がある。また、CMakeのリストは単にセミコロンで区切られた文字列でしかないため、リストやベクタの表現にも直接使うことはできない(セミコロンを含んだ文字列を保持すると、そこでリストが分割されてしまう)。
その辺のScheme処理系と同様に、CMakeは一度internした変数シンボルを解放する手段は存在しないため、GCによって領域を回収するには変数をfunctionなりなんなりでスコープする必要がある。