Ruby Parser開発日誌 (10) - parse.y リファクタリングチャレンジ はじめました

前回のあらすじ

Ruby Parser開発日誌 (9) - RubyKaigi 2023で発表してきた ~ 世はまさに”大パーサー時代” ~ - かねこにっき

RubyKaigiにいってきました。スライドや登壇時の動画は以下のリンクから参照できます。ぜひご覧ください。

rubykaigi.org

parse.y リファクタリングチャレンジ

"parse.y"を読んでいる時にrb_obj_hideã‚„rb_builtin_class_name、RB_OBJ_WRITTENといった関数やマクロが出てきて驚いたことのある人は少なくないでしょう。RubyのparserではGCã‚„RubyのObjectなどRuby本体の機能が多く使われています。それらはRubyの長い歴史のなかで洗練されてきた機能である一方、一定の御作法に従って使う必要があります。たとえばRB_OBJ_WRITEã‚„RB_OBJ_WRITTENを書き忘れた結果、思わぬところでGCによって必要なオブジェクトが回収されてしまったというバグは誰しも一度は踏むものでしょう。

またRubyのAST Node(struct RNode)は多様なNodeã‚’unionで管理しているため、どのNodeのどのフィールドがどの型であるかわからなくて途方にくれたこともあると思います。

ruby/rubyにいくつかのpatchをいれて準備が整ったので、このような状況を改善するために"parse.y"を本格的にリファクタリングしていきます。

リファクタリングのアイデア

リテラルオブジェクトをRubyのオブジェクトから卒業させる

1ã‚„"abc"といったリテラルはparserのなかでRubyのオブジェクトに変換されています。このままではC言語のintã‚’RubyのInteger(Fixnum)に変換する関数などが必要になりますし、Rubyのオブジェクトを扱っている限りGCからも離れられません。リテラルオブジェクトについては"123"というStringとしてNodeに持たせるようにし、"parse.y"の外側(たとえば"compile.c")でRubyのオブジェクトに変換するように書き換える必要があります。

これを

# +- nd_body:
#     @ NODE_LIT (id: 0, line: 1, location: (1,0)-(1,3))*
#     +- nd_lit: 123 (これはCRubyのInteger object)

こうする

# +- nd_body:
#     @ NODE_LIT (id: 0, line: 1, location: (1,0)-(1,3))*
#     +- nd_lit: "123" (char *)
#        len: 3
#        type: Integer

Fixnum, Bignum, Float, Rational, Complex, Stringなどが対象です。 ちなみに"123"というStringと書きましたが、これもRubyのStringを使わずにparser用に自前のString構造体と関連する関数を用意します¹ã€‚

Nodeを1つのunionから別々の構造体にする

冒頭にも書いたようにRubyのAST Node(struct RNode)は多様なNodeã‚’unionで管理しています。そのためNodeの種類と各フィールド(u1, u2, u3)の型の対応を理解するのが難しいです。 たとえばメソッド呼び出しのNODE_CALLの場合、レシーバーがu1にRNodeとして、メソッドのidがu2にIDとして、引数がu3にRNodeとしてそれぞれ入っています。

この対応を調べるときにnode_dump関数や、node_children関数を見ている人も多いのではないでしょうか。

この実装をそれぞれNodeの種類ごとに構造体を定義して整理していきます。

// 現在の実装では3つのunionがあり、この構造体だけをみても実際のフィールドの型を判別するのが難しい
typedef struct RNode {
    VALUE flags;
    union {
        struct RNode *node;
        ID id;
        VALUE value;
        rb_ast_id_table_t *tbl;
    } u1;
    union {
        struct RNode *node;
        ID id;
        long argc;
        VALUE value;
    } u2;
    union {
        struct RNode *node;
        ID id;
        long state;
        struct rb_args_info *args;
        struct rb_ary_pattern_info *apinfo;
        struct rb_fnd_pattern_info *fpinfo;
        VALUE value;
    } u3;
    rb_code_location_t nd_loc;
    int node_id;
} NODE;

...
#define nd_recv  u1.node
#define nd_mid   u2.id
#define nd_args  u3.node
...

parserレベルの最適化とASTを変換するロジックを削除する

おそらくCRubyの評価機がVMになる前の名残だと思いますが、parserの内部で細かい最適化を行っています。

たとえばリテラルだけが書かれた行が途中にあったとき、その行はプログラムの実行結果に何も影響しません。このような行はparserのレベルで最適化されASTには残りません(block_append関数を参照)。

def m
  :a
  :b
end

# :aがどこにもない

# @ NODE_SCOPE (id: 6, line: 1, location: (1,0)-(4,3))
# +- nd_tbl: (empty)
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_DEFN (id: 1, line: 1, location: (1,0)-(4,3))*
#     +- nd_mid: :m
#     +- nd_defn:
#         @ NODE_SCOPE (id: 5, line: 4, location: (1,0)-(4,3))
#         +- nd_tbl: (empty)
#         +- nd_args:
#         |   @ NODE_ARGS (id: 2, line: 1, location: (1,5)-(1,5))
#         |   +- nd_ainfo->pre_args_num: 0
#         |   +- nd_ainfo->pre_init:
#         |   |   (null node)
#         |   +- nd_ainfo->post_args_num: 0
#         |   +- nd_ainfo->post_init:
#         |   |   (null node)
#         |   +- nd_ainfo->first_post_arg: (null)
#         |   +- nd_ainfo->rest_arg: (null)
#         |   +- nd_ainfo->block_arg: (null)
#         |   +- nd_ainfo->opt_args:
#         |   |   (null node)
#         |   +- nd_ainfo->kw_args:
#         |   |   (null node)
#         |   +- nd_ainfo->kw_rest_arg:
#         |       (null node)
#         +- nd_body:
#             @ NODE_LIT (id: 4, line: 3, location: (3,2)-(3,4))*
#             +- nd_lit: :b

連続したstringリテラルは連結した1つのstringになりますが、これもまたparserレベルの最適化で結合が行われています(literal_concat関数を参照)。

"a" "b"

# "a" "b" ではなく"ab"になっている

# @ NODE_SCOPE (id: 2, line: 1, location: (1,0)-(1,7))
# +- nd_tbl: (empty)
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_STR (id: 0, line: 1, location: (1,0)-(1,3))*
#     +- nd_lit: "ab"

またshareable_constant_valueマジックコメントはASTのNodeを追加することで実装されています(nd_mid: :make_shareableのあたり)。この手の実装は"parse.y"の外側、たとえば"compile.c"へもっていきます。

# shareable_constant_value: experimental_everything
FOO = Set[1, 2, {foo: []}]

$ ruby -v --dump=p test.rb
ruby 3.2.0 (2022-12-25 revision a528908271) [arm64-darwin21]
...
# +- nd_body:
#     @ NODE_CDECL (id: 0, line: 2, location: (2,0)-(2,26))*
#     +- nd_vid: :FOO
#     +- nd_else: not used
#     +- nd_value:
#         @ NODE_CALL (id: 15, line: 2, location: (2,0)-(2,26))
#         +- nd_mid: :make_shareable
#         +- nd_recv:
#         |   @ NODE_LIT (id: 13, line: 2, location: (2,0)-(2,26))
#         |   +- nd_lit: #<Class:0x000000010322cd20>
#         +- nd_args:
#             @ NODE_LIST (id: 14, line: 2, location: (2,0)-(2,26))
...

リファクタリングの先にあるもの

これらのリファクタリングが完了したとき、大きく3つの恩恵を得ることができると考えています。

1. 素直なASTが手に入る

Abstract Syntax Tree(抽象構文木)はその名のとおり抽象化されたものです。しかし各種解析ツールのことを踏まえ、昨今ではより情報を付与する方向にASTを整理することが求められているように感じます。入力されたコードを素直に構造化したデータとしてのASTが手に入ることは、各種ツールの実装者に必要な情報を提供することに繋がります。

2. parse.yの可読性が上がる

以前 Ruby Parser開発日誌 (6) - parse.yのMaintainabilityの話 - かねこにっき ではparserとlexerの密結合という観点から"parse.y"のMaintainabilityの話をしました。この密結合の解消以外にもNodeの構造を整理したり、parserにおける最適化(Nodeの変形)を削除することもMaintainabilityや可読性の向上につながります。

3. Universal Parser への貢献

Universal ParserとはTypeProf, Sorbetといった解析ツールや、mrubyなどCRuby以外のRuby実装でもCRubyのparserを使えるようにするというプロジェクトです²ã€‚そのためにはいまのparserからCRubyの機能への依存を消していく必要があります。"parse.y"がRubyのObjectに依存しなくなったときUniversal Parserが手に入ります。

目標としては今年のRubyのリリース(2023/12/25)までにCRubyの関数への依存を全部消したいと思っています³ã€‚

まとめ

ここまでみてきたようにこのチャレンジには

• RubyのStringのサブセットを実装する
• ASTの構造や組み立て方を変更する
• "parse.y"の変更にあわせて"compile.c"を変更する
• parserの内部データ構造をGCから卒業させる(メモリ管理の変更)

などの幅広いジャンルの課題があります。これらはparserの構文規則をいじるというよりは、parserの扱うデータ構造やロジックといったC言語で書かれた部分のリファクタリングが中心です。ということはparser generatorに詳しくなくても、構文規則を変更しなくても、"parse.y"に手を入れるチャンスが広がっているということです。またASTをいじると結構な確率で"compile.c"を調整することになるはずなので、"compile.c"についても詳しくなれるはずです。

"parse.y"を実質書き直すといっても過言ではないプロジェクトにあなたも参加してみませんか?

挑戦者求む!!

これらを全部一人で進めるのはやることがいろいろあって大変です。もし興味をお持ちの方がいたら、ぜひ手伝っていただきたいです。ruby-jp.slack.com | ruby-jpに#lr-parser というチャンネルがありますので、詳しい話が聞きたいという方はお越しください。

---

1. ということはEncodingは? と思った人はするどいですね。Stringリテラルを移植するさいには、どのEncodingが指定されていたかという情報をもたせてCRubyのEncodingと対応づける必要があります。↩
2. Universal Parserについて詳しくはRuby Parser開発日誌 (8) - Universal Parserへの道 - かねこにっきをみてください。↩
3. 最終的に残るmallocã‚„freeはoptionalに渡すことができる状態にします。なのでこの目標を達成すれば外からなにも渡さなくてもparserをつくってparseしてAST Nodeが手に入るようになります。↩