ひとり勉強会

ひとり楽しく勉強会

NODE_CASE

YARV

次は、case文です。

case [式0]
  when 式1 then
    本体1
  when 式2 then
    本体2
  ..
  else
    ..
end

という形の式で、上から順にwhen節を調べていって、式n === 式0 が成り立つところの本体が実行されます。

この部分をコンパイルするコードのちょうおおまかな流れは、こうなっています。

case NODE_CASE:{
  DECL_ANCHOR(head);
  DECL_ANCHOR(body_seq);
  DECL_ANCHOR(cond_seq);
  ...
  if (node->nd_head == 0) {
      COMPILE_(ret, "when", node->nd_body, poped);
      break;
  }
  ...
  ADD_SEQ(ret, head);
  ...
  /* else */
  if (node) {
      ...
      COMPILE_(cond_seq, "else", node, poped);
      ...
  }
  ADD_SEQ(ret, cond_seq);
  ADD_SEQ(ret, body_seq);
  break;
}

途中にあるif文は、case式のnd_headがない場合、つまり[式0]が省略されていた場合です。この場合は、構文木の内部ノード NODE_WHEN の場合としてコンパイルされます(後述)。
それ以外の場合は、式0を評価する命令列headが最初にきて、次に、各whenの条件判定部分をぜんぶ並べたcond_seqが続きます。cond_seqのなかには、when節の値とマッチしたらbody_seqの中の対応する部分にジャンプするコードが入ります。body_seqには、when節の本体が並びます。どのwhenにも当てはまらなかったときに実行されるelse節は、cond_seqの方に並ぶようです。
Rubyソース上の見た目の順序と、命令列の並ぶ順序は違うことに注意ですね。

case head

headのコンパイルは簡単です。

COMPILE(head, "case base", node->nd_head);

式をそのまま命令列に変換して、その評価結果がスタック先頭に残るようにしておきます。

case when

node = node->nd_body;
type = nd_type(node);

endlabel = NEW_LABEL(nd_line(node));
elselabel = NEW_LABEL(nd_line(node));
while (type == NODE_WHEN) {
    ...
    (ここで各when節のコンパイル)
    ...
    node = node->nd_next;
    if (!node) {
         break;
    }
    type = nd_type(node);
}

whileループで回りながら、各when節をコンパイルしています。nodeがnullになる（else節がないとき）か、typeがNODE_WHENではなくなる（else節があるとき）ときにループが終わります。
ループの中身はこちら。まず、本体をコンパイルしてbody_seqに入れます。こっちは簡単。

  LABEL *l1;

  l1 = NEW_LABEL(nd_line(node));
  ADD_LABEL(body_seq, l1);
  ADD_INSN(body_seq, nd_line(node), pop);
  COMPILE_(body_seq, "when body", node->nd_body, poped);
  ADD_INSNL(body_seq, nd_line(node), jump, endlabel);

最初のpop命令は、headの値をスタックから除くためのものです。（条件部分ではなく本体部分でpopされます。条件部分では何度もheadの値を使う可能性があるので、そっちではpopできない(か、しにくい)んだと思います。）when節の本体が終わったらcase文全体も終わるので、最後にはendlabelへジャンプしています。

次、条件部分。

  if (nd_type(vals) == NODE_ARRAY) {
      special_literals = when_vals(iseq, cond_seq, vals, l1,
                                   special_literals);
  }
  else if (nd_type(vals) == NODE_SPLAT ||
           nd_type(vals) == NODE_ARGSCAT) {
      NODE *val = vals->nd_head;
      special_literals = 0;

      if (nd_type(vals) == NODE_ARGSCAT) {
	  when_vals(iseq, cond_seq, vals->nd_head, l1, 0);
	  val = vals->nd_body;
      }

      COMPILE(cond_seq, "when/cond splat", val);
      ADD_INSN1(cond_seq, nd_line(val), checkincludearray,
                                        Qtrue);
      ADD_INSNL(cond_seq, nd_line(val), branchif, l1);
  }

NODE_ARRAYは、when 1, 2, 3 then のように条件部分に値が並んでいる場合です。NODE_SPLATは when *arr then のように * を配列で展開した場合、NODE_ARGSCAT は when 1, *arr then のように展開した場合です。
when_vals関数は、「スタック先頭の値と引数valsの要素を===で比較して、マッチしたらl1にジャンプ」というコードを生成する補助関数です。

/* when_vals 関数の概要 */
    while (vals) {
         NODE* val;
         val = vals->nd_head;

         ... (略) ...

         COMPILE(cond_seq, "when cond", val);
         ADD_INSN1(cond_seq, nd_line(val), topn, INT2FIX(1));
         ADD_SEND(cond_seq, nd_line(val), ID2SYM(idEqq),
                                          INT2FIX(1));
         ADD_INSNL(cond_seq, nd_line(val), branchif, l1);
         vals = vals->nd_next;
    }

topn, INT2FIX(1) はスタックの先頭から0オリジンで数えて1番目の値、要するにcase文のheadを複製する命令です。その値を引数にして、valオブジェクトの===(idEqq)メソッドを呼んで条件分岐してます。

NODE_SPLATの方では、checkincludearray というcase文用の特別な命令が使われます。ここでのようにtrueを指定すると、配列に===でマッチする値が入っていたらtrue、いなければfalseを返す命令だそうです。

あとは...、special_literalsという気になるものがちらほら見えています。これについては後ほどまとめます。最適化のためのコードで、なくても動くことは動く感じです。

case else

when節のループが終わると、else部分のコンパイルです。特別なことはありません。

  /* else */
  if (node) {
      ADD_LABEL(cond_seq, elselabel);
      ADD_INSN(cond_seq, nd_line(node), pop);
      COMPILE_(cond_seq, "else", node, poped);
      ADD_INSNL(cond_seq, nd_line(node), jump, endlabel);
  }
  else {
      debugs("== else (implicit)\n");
      ADD_LABEL(cond_seq, elselabel);
      ADD_INSN(cond_seq, nd_line(tempnode), pop);
      if (!poped) {
	  ADD_INSN(cond_seq, nd_line(tempnode), putnil);
      }
      ADD_INSNL(cond_seq, nd_line(tempnode), jump, endlabel);
  }

elseがなかった場合も、else nil のような節があったのと同じようにコンパイルされます。

case special_literals

elseのうしろに、こんなコードが続いています。

  if (special_literals) {
      ADD_INSN(ret, nd_line(tempnode), dup);
      ADD_INSN2(ret, nd_line(tempnode), opt_case_dispatch,
                special_literals, elselabel);
      iseq_add_mark_object_compile_time(iseq,
                                        special_literals);
  }

この時点ではretにはheadを評価する命令列だけが入っているので、そのうしろに続くかもしれない二つの命令ということになります。dupはスタック先頭の値を複製するだけで、重要なのは opt_case_dispatch。

opt_case_dispatchは、when節の比較条件部がすべて(数値|シンボル|文字列)リテラルのときに限ってcaseを高速化する命令です。ここまでで調べた条件分岐の羅列ではなく、ハッシュテーブルでheadからジャンプ先を調べてジャンプします。

case x
  when 1 then 100
  when 2 then 200
  else 300
end

は

if 1 === x then 100
elsif 2 === x then 200
else 300
end

ではなく

{1=>100, 2=>200}.fetch(x, 300)

として実行するみたいなイメージです。（when節の本体の100や200は条件にマッチしないと評価されないので、上のHashを使った式は正確には意味が違っちゃってますが。。。）

special_literalsは、Rubyの配列オブジェクトで、コンパイル時にwhen節の値と対応するジャンプ先を交互に保存してあります。

/* case NODE_CASE: の先頭 */
VALUE special_literals = rb_ary_new();

/* when_vals の(略)した部分 */
if (special_literals &&
    (lit = case_when_optimizable_literal(val)) != Qfalse) {
    rb_ary_push(special_literals, lit);
    rb_ary_push(special_literals, (VALUE)(l1) | 1);
}
else {
    special_literals = Qfalse;
}

リテラルじゃない値が１個でもwhen節に出てきたら、（コンパイル時に値とジャンプ先の対応関係を決められないので）テーブルで高速ジャンプをするのをあきらめることになります。この場合、special_literalsをQfalseにして以降テーブル作成処理も中止します。

special_literalsはRubyのArrayオブジェクトなので、最終的にVMで実行される前に、どこかでHashオブジェクトに変換されているはず。ざっと調べたところ、set_sequence関数 @ compile.c（命令のリンクリストを、命令のバイナリ列に落とす処理）のところで配列からハッシュに変わっているようでした。詳しくはその辺りを読むときに。