mruby/スクリプト解析を読む

mrubyを読む

はじめに †

スクリプト解析は文字列を解析する関数とファイルを解析する関数がありますが、それらの違いは所詮、入力の違いなのでmrb_parse_string()をスクリプト解析のエントリポイントとして読み進めていきたいと思います。

mrb_parse_nstring(src/parse.y) †

mrb_parse_string()は渡された文字列をstrlenしてmrb_parse_nstring()に渡しているだけなのでmrb_parse_nstring()を見てみましょう。

1 2 3 4 5 6 7 8 9 10 11 12 13

- | | | | | | | | | !

parser_state* mrb_parse_nstring(mrb_state *mrb, const char *s, size_t len) { parser_state *p; p = mrb_parser_new(mrb); if (!p) return 0; p->s = s; p->send = s + len; mrb_parser_parse(p); return p; }

スクリプト解析で鍵となるのはmrb_parser_state構造体のようです。mrb_parser_stateはinclude/compile.hに書かれています。なお、上記ではparser_stateになっていますが、parser_stateはmrb_parser_stateをtypedefしたものです。

次にmrb_parser_parse()を見てみます。ちょっと長めですが全部貼り付け。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

- | | - | | | | ! | | | | | | | | - - | ! - | ! ! - - | ! - | | ! ! !

void mrb_parser_parse(parser_state *p) { node *tree; if (setjmp(p->jmp) != 0) { yyerror(p, "memory allocation error"); p->nerr++; p->tree = p->begin_tree = 0; return; } p->cmd_start = TRUE; p->in_def = p->in_single = FALSE; p->nerr = p->nwarn = 0; p->sterm = 0; yyparse(p); tree = p->tree; if (!tree) { if (p->begin_tree) { tree = p->begin_tree; } else { tree = new_nil(p); } } else { if ((intptr_t)tree->car == NODE_SCOPE) { p->locals = cons(tree->cdr->car, 0); } if (p->begin_tree) { tree = new_begin(p, p->begin_tree); append(tree, p->tree); } } }

関数を眺めると、

yyparse()を実行するとmrb_parser_state.treeに解析結果が格納される

ということがわかります。node（mrb_ast_nodeがtypedefされたもの）は上記のmrb_parser_parse()を見てもわかるとおり、LISPのリスト構造と同じになっています。*1

1 2 3

- | !

typedef struct mrb_ast_node { struct mrb_ast_node *car, *cdr; } mrb_ast_node;

CRubyのNODE構造体に比べると驚くほどシンプルです。シンプルな分は運用で回避。parse.yの前半部分にはリスト操作、およびそれを使って解析ツリーを作るための関数群が定義されています。例えばこんな感じ、

1 2 3 4 5 6

- ! - | !

// (:scope (vars..) (prog...)) static node* new_scope(parser_state *p, node *body) { return cons((node*)NODE_SCOPE, cons(p->locals->car, body)); }

解析してみる †

具体的にスクリプトをNODEに変換してみましょう。対象とするスクリプトはRuby1.9のスクリプト解析で変換してみたものと同じスクリプトを使います*2。

class MonteCarlo
  def pi(n)
    count = 0
    (1..n).each do
      x = rand
      y = rand
      if x * x + y * y <= 1
        count += 1
      end
    end
    (count.to_f / n) * 4
  end
end

n = 10000 * 10000
pi = MonteCarlo.new.pi(n)
puts "pi = #{pi}"

bin/mrubyは--verboseオプションを付けるとNODEツリーがダンプされます*3。上記のスクリプトを食わせると以下のNODEツリーが出力されました。

$ ./mruby.exe -c --verbose ../../montecarlo.rb
NODE_SCOPE:
  local variables:
    n
    pi
  NODE_BEGIN:
    NODE_CLASS:
      :MonteCarlo
      body:
        NODE_BEGIN:
          NODE_DEF:
            pi
            local variables:
              n
                            count
            mandatory args:
              NODE_ARG n
            NODE_BEGIN:
              NODE_ASGN:
                lhs:
                  NODE_LVAR count
                rhs:
                  NODE_INT 0 base 10
              NODE_CALL:
                NODE_BEGIN:
                  NODE_DOT2:
                    NODE_INT 1 base 10
                    NODE_LVAR n
                method='each' (170)
                args:
                block:
                  NODE_BLOCK:
                    body:
                      NODE_BEGIN:
                        NODE_ASGN:
                          lhs:
                            NODE_LVAR x
                          rhs:
                            NODE_CALL:
                              NODE_SELF
                              method='rand' (330)
                        NODE_ASGN:
                          lhs:
                            NODE_LVAR y
                          rhs:
                            NODE_CALL:
                              NODE_SELF
                              method='rand' (330)
                        NODE_IF:
                          cond:
                            NODE_CALL:
                              NODE_CALL:
                                NODE_CALL:
                                  NODE_LVAR x
                                  method='*' (80)
                                  args:
                                    NODE_LVAR x
                                method='+' (76)
                                args:
                                  NODE_CALL:
                                    NODE_LVAR y
                                    method='*' (80)
                                    args:
                                      NODE_LVAR y
                              method='<=' (300)
                              args:
                                NODE_INT 1 base 10
                          then:
                            NODE_BEGIN:
                              NODE_OP_ASGN:
                                lhs:
                                  NODE_LVAR count
                                op='+' (76)
                                NODE_INT 1 base 10
              NODE_CALL:
                NODE_BEGIN:
                  NODE_CALL:
                    NODE_CALL:
                      NODE_LVAR count
                      method='to_f' (109)
                    method='/' (148)
                    args:
                      NODE_LVAR n
                method='*' (80)
                args:
                  NODE_INT 4 base 10
    NODE_ASGN:
      lhs:
        NODE_LVAR n
      rhs:
        NODE_CALL:
          NODE_INT 10000 base 10
          method='*' (80)
          args:
            NODE_INT 10000 base 10
    NODE_ASGN:
      lhs:
        NODE_LVAR pi
      rhs:
        NODE_CALL:
          NODE_CALL:
            NODE_CONST MonteCarlo
            method='new' (6)
          method='pi' (326)
          args:
            NODE_LVAR n
    NODE_CALL:
      NODE_SELF
      method='puts' (286)
      args:
        NODE_DSTR
          NODE_STR "pi = " len 5
          NODE_BEGIN:
            NODE_LVAR pi
          NODE_STR "" len 0

それではどういうルールを通ることでこのようなNODEツリーが構築されるのかを追っていくことにします。

primary(keyword_class cpath superclass) †

まずクラス定義があります。これは、program → top_compstmt → top_stmts → top_stmt → stmt → expr → arg → primary → keyword_class、とルールが進んでいきます。忘れてましたがそういえばRubyではクラス定義も式でしたね。

primary(keyword_def fname) †

次のメソッド定義は、bodystmt → compstmt → stmts → stmt → expr → arg → primary → keyword_defと進みます。

f_arglist †

続いて、引数記述の解析に移ります。Rubyは、通常引数、オプション引数、残余引数、ブロック引数と引数の種類がたくさんあるので引数解析のルールも様々なパターンが書かれています。

今回は通常引数のみの一番単純なケースなので、f_arglist → f_args → f_arg → f_arg_item → f_norm_arg、とルールが進んでいきます。

primary(method_call brace_block) †

代入は飛ばしてブロック付きメソッド実行に移ります。

メソッド呼び出し全体にマッチするルールは「method_call brace_block」です。brace_blockとなっていますが、do〜endを使った場合もマッチします。

次に「(1..n).each」の部分はmethod_callの「primary_value '.' operation2 opt_paren_args」にマッチします。

最後に(1..n)の部分は、primary_value → primary → tLPAREN compstmt ')' → (中略) → arg → arg tDOT2 arg、となります。

「method_call brace_block」の際に呼ばれるcall_with_block()を見てみましょう。

method_call brace_block
  {
    call_with_block(p, $1, $2);
    $$ = $1;
  }

1 2 3 4 5 6 7 8 9 10

- | | | - | ! !

static void call_with_block(parser_state *p, node *a, node *b) { node *n = a->cdr->cdr->cdr; if (!n->car) n->car = cons(0, b); else { args_with_block(p, n->car, b); } }

慣れないとわかりづらいですが、carはリストの先頭要素、cdrはリストの先頭を除いたリストです。cdrのcdrのcdrは元のリストの前3要素を除いたリストになります。例えば元リストが(a b c d)とすると結果は以下のようになります。

cdr

(b c d)

cdrのcdr

(c d)

cdrのcdrのcdr

(d)

で、aとはNODE_CALLなので、

primary_value '.' operation2 opt_paren_args
  {
    $$ = new_call(p, $1, $3, $4);
  }

1 2 3 4 5 6

- ! - | !

// (:call a b c) static node* new_call(parser_state *p, node *a, mrb_sym b, node *c) { return list4((node*)NODE_CALL, a, (node*)b, c); }

call_with_block()中のnは引数情報を指すことがわかります。

CRubyで構築されるノードとの違いについて †

Ruby1.9のスクリプト解析のNODEと比較するとCRubyとmrubyで構築されるノードと微妙に違うことがわかります。

• CRubyではNODE_ITERがNODE_CALLを持っていたが、mrubyではブロックはブロック引数として扱われる
• CRubyではブロック内の変数はDVARとなっていたがmrubyでブロック内でもLVARとなっている

なお、CRubyと比べてNODE_SCOPEがルートにしかありませんが、あくまでNODE表現上の話であってスコープがCRubyと違うということではないようです。

おわりに †

というわけでmrubyのスクリプト解析を見てきました。わかったこととしては、

• CRubyに比べてノード構造体は非常にスリム化、ただし、各ノードごとにどういう構造になるかの把握が大変
• 文法ルールは大体CRubyと同じ（当たり前だが）

といったところでしょうか。

ちなみに、初期化のところで張った正規表現機能がオフの場合がどうなっているかですが、単純に実装されてないようです:-P（2012/6/5時点）