Ruby のパターンマッチングがどうやって実装されているのかわからないので実装を読んでわかったことを書いていく覚え書きです。
もともとは、パターンマッチング文法のコンパイル結果の命令列を見ていて、なんだかおかしいような気がしたけれども自信がないので、もうちょっと読んでおかしいかおかしくないか判断しよう、というのが動機です。
結論として「動きはするし顕在化とは思うが、微妙にまずそう」というところを見つけたのでそこまでの道筋を書きます。
parse.y の中ではこんな感じで表現されていました。
| k_case expr_value opt_terms
p_case_body
k_end
キーワード case で始まり、式が次に来て、改行がいくつか挟まって、p_case_body というパターンが挟まって、最後にキーワード end で終わり。
では p_case_body が何者かというと
p_case_body : keyword_in
{
（中略）
}
p_top_expr then
{
（中略）
}
compstmt
p_cases
{
（中略）
}
;
キーワード in のあとに p_top_expr があって、キーワード then か ; か改行が入って、文が終わったら p_cases パターン。p_cases は
p_cases : opt_else
| p_case_body
;
こんな感じなので、case が続くか、else か、そこで終わりか、という感じです。
p_top_expr は種類がたくさんあるけどそこまで興味がわかないので割愛。あと arg keyword_in p_expr パターンもあるけれどこちらも割愛。
要するに case val; in pat1; stmt1 .... end のような形をしている、ようです。
new_case3() 関数で作成される NODE_CASE3 で表現されるようです。
NODE_CASE3 の nd_head には case 直後の expr_value が入り、nd_body には NODE_IN なるノードが入っていました。
NODE_IN の nd_head にはパターンつまり上でいうところの p_top_expr が、nd_body には同じく上の compstmt が入っていました。
またその次の条件があるときにはさらに nd_next に NODE_IN が入り以下同様、else があるときには nd_next に else 以下の文そのものが入る形でした。
ここからが今回一番知りたかったところでした。 上の NODE_CASE3 がどういう命令列になってどう実行されるのか。 また実行されるときにはスタックはどうなるのか。
NODE_CASE3 の解釈は compile.c の中の compile_case3() が担当しているようでした。
最初に head, body_seq, cond_seq という 3 つのアンカーが初期化されています。
（なんで head だけ head_seq じゃないんでしょう。慣習みたいなものかな）
まず最初にさらっと COMPILE(head, "case base", node->nd_head) されています。
なのでこの時点でスタックには expr_value の値が積まれます。スタックの状態は以下のような感じです。
sp : 0 => 1
stack: [] => [expr_value]
次に以下のように書かれています。
ADD_INSN(head, line, putnil); /* allocate stack for cached #deconstruct value */
ADD_INSN(head, line, swap);
ADD_SEQ(ret, head); /* case VAL */
deconstruct のために領域を確保し、先ほどの expr_value と取り替え、またここまでのコンパイル結果を本来の位置につなげています。 スタックは以下のようになっています。
sp : 1 => 2
stack: [expr_value] => [nil expr_value]
（しかしちょっとした疑問なんですが、先に expr_value を積んでから nil を積んで取り替えるくらいなら、なんで nil を積んでから expr_value を積むようになっていないんでしょう。
あと直接 ret を使えば head って必要なかったのでは？ちょっとこのあたり理解が出来なくて、誤読している可能性が高いです）
NODE_IN の読み込みはざっくり以下のような while 文で構成されていました。
node = node->nd_body;
（中略）
line = nd_line(node);
（中略）
while (type == NODE_IN) {
（node->nd_body から body_seq 構築部分）
pattern = node->nd_head;
（node->nd_head から cond_seq 構築部分）
node = node->nd_next;
if (!node) {
break;
}
type = nd_type(node);
line = nd_line(node);
}実際には nd_body から先に処理されていますが、Ruby の文法的には nd_head つまり p_top_expr が先なので、まずこちらから見ていきます。
ADD_INSN(cond_seq, pat_line, dup) してから iseq_compile_pattern_each(iseq, cond_seq, pattern, l1, next_pat, FALSE, 2) と関数呼び出しをし、その次の場所に対して ADD_LABEL(cond_seq, next_pat) していました。
iseq_compile_pattern_each がわからないとどうしようもなさそうです。ひとまずその直前のスタックの状態を示します。
sp : 2 => 3
stack: [expr_value] => [nil expr_value expr_value]
この関数は switch(nd_type(node)) { ... } という大きな switch 文の形になっていました。
ここの node は前述の「NODE_IN の nd_head 部分」のことです。
分岐がものすごい数があってとても全部追いきれないので、まずは値がそのままパターンとして書かれているパターン、NODE_TRUE などの場合を見ていきます。
CHECK(COMPILE(ret, "case in literal", node));
ADD_INSN1(ret, line, checkmatch, INT2FIX(VM_CHECKMATCH_TYPE_CASE));
ADD_INSNL(ret, line, branchif, matched);
ADD_INSNL(ret, line, jump, unmatched);
true など単一の値を置いて、checkmatch -> branchif -> jump と繋がります。 checkmatch はスタックから 2 つ値を取り出して、パターンに一致したかどうかの真偽値をスタックに置く命令です。 branchif はスタックから 1 つ取り出して真ならジャンプする命令なので、スタックは以下のように動きます。
sp : 3 => 4 => 3 => 2
stack: [nil expr_value expr_value] => [nil expr_value expr_value p_top_expr] => [nil expr_value match_or_unmatch] => [nil expr_value]
ちょうど上の「NODE_CASE3 の nd_body == NODE_IN の部分」のときと同じスタック状態になりました。
ADD_INSN(body_seq, line, pop);
ADD_INSN(body_seq, line, pop); /* discard cached #deconstruct value */
（中略、カバレッジ関連部分）
CHECK(COMPILE_(body_seq, "in body", node->nd_body, popped));
ADD_INSNL(body_seq, line, jump, endlabel);
上の branchif, matched から飛んでくる部分です。
スタックから 2 つ捨てて、body 部分を展開します。
そもそもの case 文が値を捨てる場合 = popped な場合には実行だけして値は捨てられます。値を返す場合 = popped でない場合にはスタックに値が置かれます。
その状態で endlabel にジャンプします。
そのため popped かそうでないかでスタックの動きが異なります。
popped の場合
sp : 2 => 1 => 0
stack: [nil expr_value] => [nil] => []
popped でない場合
sp : 2 => 1 => 0 => 1
stack: [nil expr_value] => [nil] => [] => [compstmt_value]
else 節はこのように処理されます。
ADD_LABEL(cond_seq, elselabel);
ADD_INSN(cond_seq, line, pop);
ADD_INSN(cond_seq, line, pop); /* discard cached #deconstruct value */
（中略、カバレッジ関連部分）
CHECK(COMPILE_(cond_seq, "else", node, popped));
ADD_INSNL(cond_seq, line, jump, endlabel);
compstmt の場合とよく似た形をしています。そのため説明は省略します。
popped の場合
sp : 2 => 1 => 0
stack: [nil expr_value] => [nil] => []
popped でない場合
sp : 2 => 1 => 0 => 1
stack: [nil expr_value] => [nil] => [] => [opt_else_value]
さてそうすると、この部分にまずそうな箇所が存在します。 VM 実行時には endlabel に飛んでしまうので関係ないですが、iseq の構築時にこれだと sp がずれてしまいそうです。
私はつい最近まで知らなかったんですが、CRuby VM の命令列は基本的に「ジャンプを考慮せずに頭から順に読んで、ある番地に来たときの正しい sp の値がわかるように出来ている」らしいです。 ちょっとややこしいんですが、つまりたとえば
getlocal 1 # sp: 0 -> 1
branchif L001 # sp: 1 -> 0
putobject false # sp: 0 -> 1
jump L002 # sp: 1
L001:
putnil # sp: ??? (ジャンプ元で考えると 0->1 だが、頭から読むと 1 -> 2)
leave
L002:
leave
のような命令列の並びにはならないはず、ということです。なので上の命令列を是正する場合
getlocal 1 # sp: 0 -> 1
branchif L001 # sp: 1 -> 0
putobject false # sp: 0 -> 1
jump L002 # sp: 1
pop # sp: 1 -> 0 （実際には到達し得ない dead code）
L001:
putnil # sp: 0 -> 1 （ジャンプ元から数えても頭から数えても同じ）
leave # sp: 1
L002:
leave # sp: 1（ジャンプ元から数えても頭から数えても同じ）
こんな感じで、pop/putnil なんかを置いて sp を調節することになります。
ここで元のパターンマッチングの else 節に戻ると、cond_seq の終わりの sp の値が 0 または 1 になっています。 命令の並びとしては cond_seq -> body_seq の順になるので、body_seq の始まりと sp が一致している必要があります。 body_seq は上の compstmt の部分ですので始まりは sp:2 でなければいけないので、2 または 1 ずれています。 このままでは sp 計算が正しく出来ないはずです。
ではなぜ正しく動いてくれるかというと、上で「基本的に」と書いたところがミソで、実は多少の sp のずれはうまいこと直したり無視したりしてくれる「ことがある」のでした。 fix_sp_depth() という関数がずれの修正を担当していて、あるラベルより前の番地にそのラベルへのジャンプ命令があった場合、そのラベルの sp の値をそこで固定してしまいます。つまり上の例で言えば
getlocal 1 # sp: 0 -> 1
branchif L001 # sp: 1 -> 0, ここで L001 の sp 決定
putobject false # sp: 0 -> 1
jump L002 # sp: 1, ここで L002 の sp 決定
L001:
putnil # sp: 0-> 1 (頭から読むと 1 -> 2 だが、ジャンプ命令の方の sp を優先して使う)
leave
L002:
leave
こういう感じです。
繰り返しになりますが「基本的には」頭から読んで sp が決定できるようになっているはずで、この fix_sp_depth() はやや強引な救済措置といえます。
最適化などでラベルが存在しなくなることは十分考えられることで、そのときに急に問題が顕在化しえます。
この部分、今はうまく動いているけれど潜在的にまずそうなので、直したほうがよさそうです。 他にも似たような sp ずれがありそうなので、探せるだけ探してまとめて Pull Request しようかなと考えています。どれだけ探せるかな。
- NODE_CASE3
- 0 で始まる
- 非 popped なら 1, popped なら 0 で終わる
- NODE_CASE3 の nd_head
- 0 で始まる
- 2 で終わる
- NODE_CASE3 の nd_body == NODE_IN
- NODE_IN の nd_head
- 3 で始まる
- 2 で終わる
- （ただし OR などで入れ子構造になっている子の場合は 3 で始まらないこともある。その場合、始まりの sp - 1 で終わる）
- NODE_IN の nd_body
- 2 で始まる
- 非 popped なら 1, popped なら 0 で終わる
- NODE_IN の nd_next で、かつ NODE_IN の場合（後続の in の場合）
- 『NODE_IN の nd_head』と同様
- 3 で始まる
- 2 で終わる
- NODE_IN の nd_next で、かつ NODE_IN でない場合（else の場合）
- 2 で始まる
- 非 popped なら 1, popped なら 0 で終わる
- NODE_IN の nd_next が NULL、つまりelse 節が存在しない場合の暗黙の else 処理
- 2 で始まる
- 非 popped なら 1, popped なら 0 で終わる
- NODE_IN の nd_head
この形に沿っている必要があります。 ここから、後続の in の処理をする前に sp + 1 しておく必要があること、iseq_compile_pattern_each() で構築される iseq はすべて呼び出し前と比較して sp - 1 する処理である必要があること、がわかります。