Ruby Parser開発日誌 (8) - Universal Parserへの道

前回のあらすじ

Ruby Parser開発日誌 (7) - doについて考える - かねこにっき

Rubyのdoのもつ複雑さを中心にMaintainabilityの改善方法について考えました。Practical LR Parser Generationで紹介されているNonterminal attributesというアプローチにprecedence(優先度)をさらに組み合わせることで、lexerの状態として管理しているものを構文に組み込むことに成功したのでした。

ところでRuby Committers vs The Worldの2022や2021をあらためてみると、おもに次の3つが解くべき問題だと言われています。

  1. Usability (Error-tolerant parser)
  2. Maintainability
  3. Universal Parser

1と2についてはすでに分析と実装をしてきました。なので今回はUniversal Parserについて考えていきたいと思います。

なぜUniversal Parserが必要なのか

端的にいえばCRuby以外でもparserを使いまわしたいからです。これまで見てきたようにCRubyのparserとlexerはそれなりに複雑で、一から実装するのは結構大変な作業になります。またRubyは毎年リリースされ、その度にparserの実装の詳細も変化します。自前で実装した場合は毎年その変更にキャッチアップする必要があります1。

CRuby以外でもparserを使いたい例としては

  • mruby, PicoRubyといったC言語による他のRuby実装
  • JRuby, TruffleRuby, rurubyといったC言語以外のRuby実装
  • sorbetなどのtool

などがあげられます。これら様々なプロジェクトで1つのparser実装を使いまわしたいというのがUniversal Parserの目的になります。

なぜ今のparserがUniversalでないのか

現在の"parse.y"から生成されるコードはCRubyの他の機能に依存しているため、これを使おうとするとrubyのバイナリ一式が必要になってしまいます。 例えばメモリ管理。parser用のデータ、AST用のデータ、パース中に使う一時的なデータ(heredocの解析用のデータ)など、入力をパースしてASTを返すまでにも様々な形でメモリを管理する必要があります。現在これらはCRubyのメモリ管理、つまりGCの仕組みによって管理されています2。

こういったCRubyの他の機能への依存を減らしていき、parserだけを共有ライブラリとして提供するのがゴールです。

Universal Parserへの道

CRubyの提供する関数やマクロへの依存を"parse.y"から剥がしていくのですが、これにはおおきく2つの方向があります。

1. "parse.y"に対して外から関数を渡す

具体的にはrb_parser_config_structという構造体を用意して、必要な関数をこの構造体経由で"parse.y"に渡すようにします。 CRubyの場合はいままでと同じ関数が使えるので、それらを使うようにします。

void
rb_parser_config_initialize(rb_parser_config_t *config)
{
    config->counter = 0;

    config->st_functions.nonempty_memcpy = nonempty_memcpy;

    config->malloc   = ruby_xmalloc;
    config->calloc   = ruby_xcalloc;

    config->ary_new           = rb_ary_new;
    config->ary_push          = rb_ary_push;
...

2. 一部の関数を切り出したりコピーしたりして共有ライブラリに含める

"node.c"の一部のようにparserに密接に関係する処理は別ファイルに切り出したうえで直接共有ライブラリに含めてしまったほうがよかったりします。また"st.c"に関しては規模が大きくないのと、他のRubyの関数への依存が比較的少ないので必要な部分を別ファイルにコピーしました。

こうして作られた"parse.o", "node2.o"と"st.c"をコピーして編集した"st2.o"をlinkしてshared libraryをつくります。

実際にshared libraryを呼び出して1 + 2をparseするために必要な関数がこちらになります。

$ ./myparser
SCOPE:
    OPCALL:
    id: +
        LIT:
        lit: (number) 1
        LIST:
            LIT:
            lit: (number) 2

必要な関数を整理する

rb_parser_config_struct構造体をみるとわかるのですが、必要とする関数は現時点で209個あります。これを全部渡してくださいというのは流石にちょっと大変なので、いくつかのパターンに分類しながら必要な関数を減らせないか考えてみましょう。

メモリ管理用の関数

mallocやfreeといった関数は外から渡せるようにしておいたほうが便利でしょう。

imemo関連

imemoというのはCRubyの内部で使うデータをGCに管理させるための仕組みです。例えば文字列リテラルやheredoc、%記法のパースのために閉じ記号やinterpolationをするかどうかといったデータを管理する必要があり、それらはimemo_parser_strtermというデータ構造で管理しています。このあたりはCRubyの内部実装なのでGCの管理から外すことでimemoへの依存を消していきたいです。

リテラルオブジェクト関連

1 や"a"といったリテラルはparserの中ですでにCRubyのオブジェクトに変換されています。ということはINT2FIXやrb_str_newといったRubyのオブジェクトをつくるための関数が必要になります。Rubyの処理系をつくるのであればそのような関数を用意することはさほど難しくないと思いますが、C, C++, Rustなどでツールを作りたい場合には必ずしも各種オブジェクトを実装しているとは限りません。例えば型などの静的解析を行う場合には各種オブジェクトの種類(Integer, Stringなど)が分かれば十分かもしれません。

そのような場合にはparserからオブジェクト生成のロジックを完全に切り離したほうがよいでしょう。

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

となっているものを、文字列で保持するように変更することでオブジェクトの生成を完全にparserから切り離すことができます。

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

GC関連

obj_write(RB_OBJ_WRITEの実態)などを渡す必要があります。これはリテラルオブジェクトとも関係するのですが、CRubyのオブジェクトを扱う場合適切にwrite barrierを設定したり、markをする必要があります。

メモリ管理の方法にもよりますが、ナイーブな実装で共有ライブラリを使う場合は特に何もしない関数を渡せばよいです。とはいえほとんどのケースで独自のobj_writeを渡したいケースはないと思うのでparserから追い出していきたいです。

文字列関連

isspaceやisalnumなどの関数は実装も複雑じゃないのでまるっとコピーするなどして共有ライブラリに含めるのがよいかなと思っています。

例外関連

SyntaxErrorについてはparserの外側で例外を発生させているのでよいとして問題はrb_eArgErrorなんですが、こちらはエラー用の処理を外から渡してもらうことになると思います。

parserで行っているobjectの操作

-1をパースするときに直接Integerを操作するnegate_litのように、objectを直接操作する箇所があります。この関数を実装するのにFIXNUM_Pなどのobjectの種類を調べる関数/マクロ、bignum_negateやrational_set_numなどobjectの種類に合わせた関数がそれぞれ必要になります。IntegerをあらわすNodeにマイナスを表すフラグをつける、もしくはNODE_NEGを導入するなどしてこの手の操作をparserから追い出していきたいところです。

その他

CRubyの機能のなかにはASTにNodeを追加してくる機能があります。例えばshareable_constant_valueマジックコメントは定数への代入時にrb_mRubyVMFrozenCoreのメソッドを呼び出すnodeを追加することがあります。make_shareable_nodeなどをみると確かにNODE_CALLなどを追加しています。こういうのは"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))
...

まとめ

Universal Parserが必要な理由およびUniversal Parserをどのように実装するかを検討し、実際に共有ライブラリをつくり、その共有ライブラリを活用して1 + 2というスクリプトをパースしてみました。

共有ライブラリの使い勝手を良くするには使う側で用意しないといけない関数の数を減らしていく必要があります。具体的には

  • メモリ管理の方法の変更
  • リテラルオブジェクトの生成の中止
  • "compile.c"へのロジックの移動

といった作業をしていかなくてはなりません。

とはいえこれで、parserにまつわる3つの問題について目処がたったと言えます。

  1. Usability (Error-tolerant parser)
  2. Maintainability
  3. Universal Parser

RubyKaigi 2023ではここまでの議論を踏まえてRuby Parserの未来の話をします。parserに興味をお持ちの方、当日お会いしましょう!

rubykaigi.org

  1. parser gemには"rubyXX.y"というファイルがversionごとに管理されており、本当にすごいと思います。↩
  2. NODEの管理は Ruby の NODE を GC から卒業させた - クックパッド開発者ブログ によってGCから切り離されていますが、rb_ast_tは引き続きimemoとしてGCが管理しています。↩