不思議なもので、ここ数年は12月になるとCRuby向けに大きめなパッチを書くことが続いています。 今年はparse.yが生成するノードを一気に置き換えるかなという気持ちになり、粛々と作業をしています。 parserの生成するノードを変更するということは、当然そのノードを扱うコンパイラ(ファイルでいうとcompile.c)も書き換える必要があります。 できればparserだけいじって生きていきたいんだけどなと思ったりもしますが、コンパイラはコンパイラでいじってみるといろいろ知らなかったことがあって面白いんですよ。
という話をとあるコミッターにしたところ、「その感動や楽しさ、その時に考えたことをちゃんと記事にして公開しないとダメですよ。パッチが完成してから記事をブラッシュアップして公開しようとか考えていると思うんですが、それだと新鮮さがなくなるのでダメです。その日その日の出来事をちゃんと記事にして日々公開するのです」と無茶苦茶なことを言われてしまいました。
そんなこんなで記事を書くことになりました。 日々の作業日誌という面が強いので、あっちに行ったり、こっちに行ったりするかと思います。 また通常のブログ記事よりは説明を端折ったりすることもあるかと思いますが、なにかの参考になれば幸いです。
0日目: ゴールを設定する
なにはともあれ作業を始める前にゴールを考えておきます。 ゴールは達成が簡単でかつ、見栄えがするものだと良いでしょう。 ということで、以下の2点を達成することを目指します。
1日目: シンプルなリテラルと制御構文
最も簡単なスクリプト
それでは書き換えをはじめていきましょう。 Rubyはオブジェクト指向プログラミング言語なのだから、まずはクラス定義のノードを変更しようとか、メソッド定義こそが重要なのだからそのノードを変更しようとか、そういう難しいことをすると途中で挫折するリスクが高まります。 変数も難しいのでいきなり手をつけてはダメです。
なので最初の一歩として可能な限り簡単なRubyのスクリプトを対象にノードを変更してみましょう。
可能な限り簡単なスクリプトというと、つまり空の文字列ですがこれだとちょっと味気がないですね。
なので最も要素の少ないリテラルであるnilを対象にします。
このくらいの欲なら許されるでしょう。
parse.yの変更
実際にnilからどのような構文木が生成されるか確認してみると、NilNode以外にもProgramNodeとStatementsNodeが生成されます。
ProgramNodeは生成される構文木のルートとなるノードで、StatementsNodeは複数のノードを束ねる働きをします。
nilを扱いたいだけなのにいきなり3種類のノードが出てきました。
しかしこれはどのようなスクリプトでも出てくるノードのなので諦めて3種類のノードと向き合うことにします。
$ ruby --parser=prism --dump=p -e 'nil'
@ ProgramNode (location: (1,0)-(1,3))
+-- locals: []
+-- statements:
@ StatementsNode (location: (1,0)-(1,3))
+-- body: (length: 1)
+-- @ NilNode (location: (1,0)-(1,3))
それぞれのノードを生成するためのマクロ(と対応する関数)をparse.yに定義して、そちらを使うように書き換えていきます。
NEW_RB_PROGRAMNEW_RB_STATEMENTSNEW_RB_NIL
parse.yの生成規則でプログラム全体を表すのはprogramという規則なので、いままでNODE_SCOPEを作っていたところでProgramNodeを作るようにします。
@@ -3176,7 +3201,8 @@ program : { node = remove_begin(node); void_expr(p, node); } - p->eval_tree = NEW_SCOPE(0, block_append(p, p->eval_tree, $2), NULL, &@$); + // p->eval_tree = NEW_SCOPE(0, block_append(p, p->eval_tree, $2), NULL, &@$); + p->eval_tree = NEW_RB_PROGRAM($2, &@$); /*% ripper[final]: program!($:2) %*/ local_pop(p); }
NilNodeはgettableという関数の中で生成されているので、そこを書きえます。
@@ -12987,7 +13134,8 @@ gettable(struct parser_params *p, ID id, const YYLTYPE *loc) case keyword_self: return NEW_SELF(loc); case keyword_nil: - return NEW_NIL(loc); + // return NEW_NIL(loc); + return NEW_RB_NIL(loc); case keyword_true: return NEW_TRUE(loc); case keyword_false:
compile.cの変更
ノードを変更したのでコンパイラも変更しないといけません。
compile.cではノードの種類に応じてrb_iseq_compile_nodeもしくはiseq_compile_each0を変更することになります。
ノードのなかにはiseq(InstructionSequence)を作るものと作らないものがあります。
iseqをつくるノードの場合はrb_iseq_compile_node、そうでない場合はiseq_compile_each0にコンパイルの処理が書かれています。
今回のケースではProgramNodeではiseqをつくり、StatementsNodeとNilNodeでは新しくiseqはつくりません1。
iseqを作った場合には引数とローカル変数を格納する領域(struct rb_iseq_constant_bodyのstruct rb_iseq_parameters param)を設定する必要があります。
ProgramNodeにはローカル変数はありますが、引数はありません。
なのでローカル変数をlocalsフィールドから取得してiseq_set_local_tableに渡します。
// rb_iseq_compile_node /* iseq type of top, method, class, block */ switch (nd_type(node)) { case RB_PROGRAM_NODE: { const rb_program_node_t *cast = (const rb_program_node_t *) node; locals = cast->locals; body = (NODE *) cast->statements; break; } ... } iseq_set_local_table(iseq, locals, args); iseq_set_arguments(iseq, ret, args); iseq_set_parameters_lvar_state(iseq);
NilNodeは既存のコードをそのまま流用できます。
// iseq_compile_each0 // Before case NODE_NIL:{ if (!popped) { ADD_INSN(ret, node, putnil); } break; } // After case RB_NIL_NODE: { if (!popped) { ADD_INSN(ret, node, putnil); } break; }
最後に残ったStatementsNodeですが、これはもともとのNODE_BLOCKに対応しています。
ブロックといっても10.times do |i| expr endのブロックではなく、コードブロックを表していたノードです2。
$ ruby --parser=parse.y --dump=p -e 'nil; nil'
###########################################################
## Do NOT use this node dump for any purpose other than ##
## debug and research. Compatibility is not guaranteed. ##
###########################################################
# @ NODE_SCOPE (id: 4, line: 1, location: (1,0)-(1,8))
# +- nd_tbl: (empty)
# +- nd_args:
# | (null node)
# +- nd_body:
# @ NODE_BLOCK (id: 2, line: 1, location: (1,0)-(1,8))
# +- nd_head (1):
# | @ NODE_NIL (id: 0, line: 1, location: (1,0)-(1,3))*
# +- nd_head (2):
# @ NODE_NIL (id: 1, line: 1, location: (1,5)-(1,8))*
ruby --parser=prism --dump=p -e 'nil; nil'
@ ProgramNode (location: (1,0)-(1,8))
+-- locals: []
+-- statements:
@ StatementsNode (location: (1,0)-(1,8))
+-- body: (length: 2)
+-- @ NilNode (location: (1,0)-(1,3))
+-- @ NilNode (location: (1,5)-(1,8))
データ構造的な違いとしてはNODE_BLOCKがリスト構造であるのに対して、StatementsNodeは配列で他のノードを保持していることです。
NODE_BLOCKでは実際のノード(例えばNODE_NIL)をnd_head、次の要素をラップしているNODE_BLOCKをnd_nextで管理しています。
一方でStatementsNodeはbodyが他のノードへのポインタの配列になっています。
またstatementがまったくないときのノードの構造にも違いがあって、NODE_BLOCKの場合は要素がないときはそもそもNODE_BLOCKが作られないのに対して、StatementsNodeの場合はbodyが空配列であるノードが作られます。
要素がないときはputnilへコンパイルされてほしいことを踏まえると、StatementsNodeをコンパイルするコードは以下のようになります。
body->sizeに応じて分岐しているのは、空配列のときのケースを考慮しているためです。
最後の要素かどうかで呼び出しているマクロが異なるのはpopしてよいかどうかが最後の要素とそれ以外で異なるからです。
pop(compile.cでいうpopped引数)についてはまたどこかで詳しく取り上げるつもりです。
生成されるバイトコードを比較して差がなければよいので、コードでわからないところが多少あっても一旦飲み込んで進むことも大切です。
しばらくいじっていると、そのうち答えがわかるものです。
case RB_STATEMENTS_NODE: { // A list of statements. const rb_statements_node_t *cast = (const rb_statements_node_t *) node; const rb_node_list2_t *body = &cast->body; if (body && body->size > 0) { for (size_t index = 0; index < body->size - 1; index++) { COMPILE_POPPED(ret, "statements body", body->nodes[index]); } CHECK(COMPILE_(ret, "statements body", body->nodes[body->size - 1], popped)); } else { ADD_INSN(ret, node, putnil); } break; }
参考にまでにNODE_BLOCKをコンパイルするコードものせておきます。
こちらはcompile_blockという関数に切り出されています。
StatementsNodeの処理を関数に切り出すかどうかは今後の成り行きに任せます。
static int compile_block(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *node, int popped) { while (node && nd_type_p(node, NODE_BLOCK)) { CHECK(COMPILE_(ret, "BLOCK body", RNODE_BLOCK(node)->nd_head, (RNODE_BLOCK(node)->nd_next ? 1 : popped))); node = RNODE_BLOCK(node)->nd_next; } if (node) { CHECK(COMPILE_(ret, "BLOCK next", RNODE_BLOCK(node)->nd_next, popped)); } return COMPILE_OK; }
このような変更をすることで無事nilに対してバイトコードが生成できるようになりました。
$ ./miniruby --parser=parse.y --dump=p,i -e 'nil'
@ ProgramNode (location: (1,0)-(1,3))
+-- locals: []
+-- statements:
@ StatementsNode (location: (1,0)-(1,3))
+-- body: (length: 1)
+-- @ NilNode (location: (1,0)-(1,3))*
== disasm: #<ISeq:<main>@-e:1 (1,0)-(1,3)>
0000 putnil ( 1)[Li]
0001 leave
その他のシンプルなリテラル (self, true, false, __FILE__, __LINE__, __ENCODING__)
nil以外にもself, true, falseなどはノードが値を持たないので、nilと同様に書き換えることができます。
__FILE__に相当するSourceFileNodeはファイル名をfilepathというフィールドに保持しているので、変更前のノードと同様にノードの生成時にファイル名を渡すようにします。
static rb_source_file_node_t * rb_new_node_source_file_new(struct parser_params *p, VALUE str, const YYLTYPE *loc) { rb_source_file_node_t *n = RB_NEW_NODE_NEWNODE((enum rb_node_type)RB_SOURCE_FILE_NODE, rb_source_file_node_t, loc); n->filepath = rb_str_to_parser_string(p, str); return n; }
そのほかコンパイラの処理などはとくに難しい箇所はないので割愛します。
ifとunless
リテラルばかり実装していても飽きてしまうので、この辺で制御構文に取り組んでみましょう。
parse.yの変更
ifやunlessに対応するノードはparse.yのnew_ifやnew_unlessという関数で作られています。
static NODE* new_if(struct parser_params *p, NODE *cc, NODE *left, NODE *right, const YYLTYPE *loc, const YYLTYPE* if_keyword_loc, const YYLTYPE* then_keyword_loc, const YYLTYPE* end_keyword_loc) { if (!cc) return right; cc = cond0(p, cc, COND_IN_COND, loc, true); return newline_node(NEW_IF(cc, left, right, loc, if_keyword_loc, then_keyword_loc, end_keyword_loc)); }
ここでcond0という関数をみてみます。
if 1; e; end # => -e:1: warning: literal in conditionといった警告をだすために条件部分のノードの種類に応じて分岐していることがわかります。
static NODE* cond0(struct parser_params *p, NODE *node, enum cond_type type, const YYLTYPE *loc, bool top) { if (node == 0) return 0; if (!(node = nd_once_body(node))) return 0; assign_in_cond(p, node); switch (nd_type(node)) { case NODE_BEGIN: RNODE_BEGIN(node)->nd_body = cond0(p, RNODE_BEGIN(node)->nd_body, type, loc, top); break; case NODE_DSTR: case NODE_EVSTR: case NODE_STR: case NODE_FILE: SWITCH_BY_COND_TYPE(type, warn, "string "); break; ...
数秒考えたのですが、現時点では未対応のノードが多いので一旦cond0を呼ばないようにしてnew_if2を実装し、ここは先に進むようにしておきましょう。
作業量が多いので手が止まらないようにするのが大事。
static rb_node_t *
new_if2(struct parser_params *p, rb_node_t *cc, rb_statements_node_t *left, rb_node_t *right, const YYLTYPE *loc, const YYLTYPE* if_keyword_loc, const YYLTYPE* then_keyword_loc, const YYLTYPE* end_keyword_loc)
{
if (!cc) return right;
// TODO
// cc = cond0(p, cc, COND_IN_COND, loc, true);
return rb_new_node_newline_node(NEW_RB_IF(cc, left, right, loc, if_keyword_loc, then_keyword_loc, end_keyword_loc));
}
compile.cの変更
compile.cではcompile_ifという関数でifとunlessの両方を扱っています。
ifとunlessは条件式の値に応じて実行するブランチが逆なだけなので、1つの関数で扱うのは合理的でしょう。
compile_ifのなかでキャストする先の構造体を新しいノードの構造体に書き換えておけばいいでしょう。
一つ注意が必要なのは条件式がNODE_BLOCKかチェックしている箇所です。
static int compile_if(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *const node, int popped, const enum node_type type) { const NODE *const node_body = type == NODE_IF ? RNODE_IF(node)->nd_body : RNODE_UNLESS(node)->nd_else; const NODE *const node_else = type == NODE_IF ? RNODE_IF(node)->nd_else : RNODE_UNLESS(node)->nd_body; const int line = nd_line(node); const NODE *line_node = node; DECL_ANCHOR(cond_seq); LABEL *then_label, *else_label, *end_label; VALUE branches = Qfalse; INIT_ANCHOR(cond_seq); then_label = NEW_LABEL(line); else_label = NEW_LABEL(line); end_label = 0; NODE *cond = RNODE_IF(node)->nd_cond; // ここ if (nd_type(cond) == NODE_BLOCK) { cond = RNODE_BLOCK(cond)->nd_head; } ...
条件式がNODE_BLOCK、つまり複数の式からなるケースを考えてみます。
たとえばif (m1; m2) then 1 else 2 endのようなコードをみてみましょう。
$ ruby --parser=parse.y --dump=p -e 'if (m1; m2) then 1 else 2 end' ########################################################### ## Do NOT use this node dump for any purpose other than ## ## debug and research. Compatibility is not guaranteed. ## ########################################################### # @ NODE_SCOPE (id: 8, line: 1, location: (1,0)-(1,29)) # +- nd_tbl: (empty) # +- nd_args: # | (null node) # +- nd_body: # @ NODE_IF (id: 7, line: 1, location: (1,0)-(1,29))* # +- nd_cond: # | @ NODE_BLOCK (id: 4, line: 1, location: (1,3)-(1,11)) # | +- nd_head (1): # | @ NODE_BLOCK (id: 2, line: 1, location: (1,4)-(1,10)) # | +- nd_head (1): # | | @ NODE_VCALL (id: 0, line: 1, location: (1,4)-(1,6))* # | | +- nd_mid: :m1 # | +- nd_head (2): # | @ NODE_VCALL (id: 1, line: 1, location: (1,8)-(1,10))* # | +- nd_mid: :m2 # +- nd_body: # | @ NODE_INTEGER (id: 5, line: 1, location: (1,17)-(1,18))* # | +- val: 1 # +- nd_else: # | @ NODE_INTEGER (id: 6, line: 1, location: (1,24)-(1,25))* # | +- val: 2 # +- if_keyword_loc: (1,0)-(1,2) # +- then_keyword_loc: (1,12)-(1,16) # +- end_keyword_loc: (1,26)-(1,29)
たしかにNODE_BLOCKのなかにNODE_BLOCKがネストする構造になっています。
compile_ifのコードはこのネストを解消するためのコードだとわかります。
書き換えた後はParenthesesNodeによってラップされるようになるので、コンパイルはParenthesesNodeのコンパイル処理にまかせてcompile_ifではとくにネストを解消しなくていいかなと思います3。
ruby --parser=prism --dump=p -e 'if (m1; m2) then 1 else 2 end'
@ ProgramNode (location: (1,0)-(1,29))
+-- locals: []
+-- statements:
@ StatementsNode (location: (1,0)-(1,29))
+-- body: (length: 1)
+-- @ IfNode (location: (1,0)-(1,29))
+-- if_keyword_loc: (1,0)-(1,2) = "if"
+-- predicate:
| @ ParenthesesNode (location: (1,3)-(1,11))
| +-- ParenthesesNodeFlags: multiple_statements
| +-- body:
| | @ StatementsNode (location: (1,4)-(1,10))
| | +-- body: (length: 2)
| | +-- @ CallNode (location: (1,4)-(1,6))
| | | +-- CallNodeFlags: variable_call, ignore_visibility
| | | +-- receiver: nil
| | | +-- call_operator_loc: nil
| | | +-- name: :m1
| | | +-- message_loc: (1,4)-(1,6) = "m1"
| | | +-- opening_loc: nil
| | | +-- arguments: nil
| | | +-- closing_loc: nil
| | | +-- equal_loc: nil
| | | +-- block: nil
| | +-- @ CallNode (location: (1,8)-(1,10))
| | +-- CallNodeFlags: variable_call, ignore_visibility
| | +-- receiver: nil
| | +-- call_operator_loc: nil
| | +-- name: :m2
| | +-- message_loc: (1,8)-(1,10) = "m2"
| | +-- opening_loc: nil
| | +-- arguments: nil
| | +-- closing_loc: nil
| | +-- equal_loc: nil
| | +-- block: nil
| +-- opening_loc: (1,3)-(1,4) = "("
| +-- closing_loc: (1,10)-(1,11) = ")"
+-- then_keyword_loc: (1,12)-(1,16) = "then"
+-- statements:
| @ StatementsNode (location: (1,17)-(1,18))
| +-- body: (length: 1)
| +-- @ IntegerNode (location: (1,17)-(1,18))
| +-- IntegerBaseFlags: decimal
| +-- value: 1
+-- subsequent:
| @ ElseNode (location: (1,19)-(1,29))
| +-- else_keyword_loc: (1,19)-(1,23) = "else"
| +-- statements:
| | @ StatementsNode (location: (1,24)-(1,25))
| | +-- body: (length: 1)
| | +-- @ IntegerNode (location: (1,24)-(1,25))
| | +-- IntegerBaseFlags: decimal
| | +-- value: 2
| +-- end_keyword_loc: (1,26)-(1,29) = "end"
+-- end_keyword_loc: (1,26)-(1,29) = "end"
compile_ifはcompile_branch_conditionという関数を呼ぶのですが、これがノードの種類に応じて分岐する関数になっています。
触り始めるとハマりそうな気がするのでここも一旦見なかったことにして先にすすみましょう。
static int compile_branch_condition(rb_iseq_t *iseq, LINK_ANCHOR *ret, const NODE *cond, LABEL *then_label, LABEL *else_label) { int ok; DECL_ANCHOR(ignore); again: switch (nd_type(cond)) { case NODE_AND: CHECK(ok = compile_logical(iseq, ret, RNODE_AND(cond)->nd_1st, NULL, else_label)); cond = RNODE_AND(cond)->nd_2nd; if (ok == COMPILE_SINGLE) { INIT_ANCHOR(ignore); ret = ignore; then_label = NEW_LABEL(nd_line(cond)); } goto again; case NODE_OR: CHECK(ok = compile_logical(iseq, ret, RNODE_OR(cond)->nd_1st, then_label, NULL)); cond = RNODE_OR(cond)->nd_2nd; if (ok == COMPILE_SINGLE) { INIT_ANCHOR(ignore); ret = ignore; else_label = NEW_LABEL(nd_line(cond)); } goto again; case NODE_SYM: case NODE_LINE: ...:
elseを表すNode
else句のstatementsはElseNodeでラップされています。
else句をコンパイルする処理をcompile_ifに書いてもいいのですが、case ... else ... endのelseなどもElseNodeになることを考えると、iseq_compile_each0にElseNodeをコンパイルする処理を書いたほうがあとで楽そうです。
elseがNULLのときはiseq_compile_eachで、elseのstatementsが空のときはiseq_compile_each0のStatementsNodeの処理でputnilに変換されるので、ElseNodeの処理ではとくにstatementsの中をチェックしなくてよいでしょう。
case RB_ELSE_NODE: { const rb_else_node_t *cast = (const rb_else_node_t *) node; CHECK(COMPILE_(ret, "else", (const NODE *) cast->statements, popped)); break; }
これでifをコンパイルできるようになりました。
$ ./miniruby --parser=parse.y --dump=p,i -e 'if self; true else false end'
@ ProgramNode (location: (1,0)-(1,28))
+-- locals: []
+-- statements:
@ StatementsNode (location: (1,0)-(1,28))
+-- body: (length: 1)
+-- @ IfNode (location: (1,0)-(1,28))*
+-- if_keyword_loc: (1,0)-(1,2) = ""
+-- predicate:
| @ SelfNode (location: (1,3)-(1,7))
+-- then_keyword_loc: (1,7)-(1,8) = ""
+-- statements:
| @ StatementsNode (location: (1,9)-(1,13))
| +-- body: (length: 1)
| +-- @ TrueNode (location: (1,9)-(1,13))*
+-- subsequent:
| @ ElseNode (location: (1,14)-(1,24))
| +-- else_keyword_loc: (1,14)-(1,18) = ""
| +-- statements:
| | @ StatementsNode (location: (1,19)-(1,24))
| | +-- body: (length: 1)
| | +-- @ FalseNode (location: (1,19)-(1,24))*
| +-- end_keyword_loc: nil
+-- end_keyword_loc: (1,25)-(1,28) = ""
== disasm: #<ISeq:<main>@-e:1 (1,0)-(1,28)>
0000 putself ( 1)[Li]
0001 branchunless 6
0003 putobject true
0005 leave
0006 putobject false
0008 leave
Cコンパイラの出す警告
こんな雑に変更を加えていって問題がおきないのか心配になったかもしれません。
もちろんCコンパイラは大量の警告を出してきます。
特に多いのがincompatible pointer typesで、これは新旧のノードがあちらこちらで混ざっているため発生します。
具体的にはparse.yとcompile.cでそれぞれ300件前後の警告がでます。
とは言っても正しく変更を加えたところだけを通るスクリプトを与えていれば問題は起きないはずなので、いまのところは警告を気にせず作業を進めていきましょう。
まとめ
今日の成果です。
今後も気をつけていきたいことは以下のとおりです。
- まずゴールを決めるのが大事
- 最初の一歩は小さくするのがよい
- ハマりそうな箇所は一旦無視して進める
- 多少の警告は気にしない
-
prism_compile.cでは
rb_iseq_compile_nodeに相当するpm_scope_node_initでStatementsNodeをあつかっているのですが、現時点での理解ではStatementsNodeはiseqを作らないと思うので、一旦iseq_compile_each0で処理するようにしておきます。↩ -
do ... endのほうのブロックはNODE_ITERというノードで表現しています。ITERはiterationの略でしょう。↩ -
parse.yで
primary: tLPAREN compstmt(stmts) ')'が無条件でNODE_BLOCKでラップするようになっているので、たとえばif ((m1; m2)) then 1 else 2 endのようなコードではNODE_BLOCKが3重にネストするようになっています。ということはもとのcompile_ifの実装でもNODE_BLOCKのネストを展開しきれずに、NODE_BLOCKをiseq_compile_each0に処理させるケースがある気がします。だいぶ寄り道をしたのでこの辺で実装に戻りましょう。↩
