Rubyのparserを語る上で忘れてはいけない存在としてRipperというライブラリがあります。
RipperはRubyのコードを構文解析するためのライブラリとしてirbやrdocなどで長く使われてきました。 一方でBug #10436のように長い間未解決のバグがあったり、Bug #18988のようにパーサーと挙動が異なる箇所があったりと完璧でない部分があります。
今回Ripperのアーキテクチャを見直すことでRipperの抱えている問題を解決することができたので、この記事で紹介したいと思います。
関連するPRとticketはそれぞれ以下のとおりです。
Ripperとは
RipperはRubyのパーサーライブラリです。入力されたコードに対応するS式を返すRipper.sexpを使ったことがある人もいるのではないでしょうか。
Ripperの最もプリミティブなAPIはon_XXXというメソッド群で、on_ifやon_opといったparserやscanner(lexer)のイベントに対応したコールバックを設定することができます。
Ripper.sexpもこれらon_XXXメソッドをオーバーライドすることで実装されています。
簡単な例をもとにRipperのAPIの挙動を確認しておきましょう。
各種on_XXXメソッドが呼ばれるたびに以下の3つを行うParserclassを定義します。
- 内部のcounter(
@count)を1つ増やす - イベント名(
n)、引数(args)、その時点でのcounterの値(c)を表示する - メソッドからはcounterの値(
c)を返す
require "ripper" class Parser < Ripper def count @count ||= 0 @count += 1 "count #{@count}" end PARSER_EVENTS.each {|n| eval "def on_#{n}(*args) c = count; p [[:parser, :#{n}, *args], '=>', c]; c end" } SCANNER_EVENTS.each {|n| eval "def on_#{n}(*args) c = count; p [[:scanner, :#{n}, *args], '=>', c]; c end" } end p Parser.new("1 + 2").parse # => # [[:scanner, :int, "1"], "=>", "count 1"] # [[:scanner, :sp, " "], "=>", "count 2"] # [[:scanner, :op, "+"], "=>", "count 3"] # [[:scanner, :sp, " "], "=>", "count 4"] # [[:scanner, :int, "2"], "=>", "count 5"] # [[:parser, :binary, "count 1", :+, "count 5"], "=>", "count 6"] # [[:parser, :stmts_new], "=>", "count 7"] # [[:parser, :stmts_add, "count 7", "count 6"], "=>", "count 8"] # [[:parser, :program, "count 8"], "=>", "count 9"] # "count 9"
1, , +, , 2とそれぞれのtokenに対応するイベントが発生します1。そして1 + 2に対応する:binaryというイベントが発生します。先ほどのtokenのイベントのときの戻り値がここでの引数になるので、"count 1"と"count 5"が渡ってきます。:binaryイベントの戻り値である"count 6"は:stmts_addイベントに渡ります。そして:stmts_addイベントの戻り値である"count 8"は:programイベントに渡ります。このように以前のイベントで呼び出したメソッドの戻り値が、その後のイベントのメソッド呼び出しの引数になります。
現在の実装の問題点
Ripperとparserは構文解析のロジックを共有しているものの、それぞれが独自のコードを持っているので全体像はなかなかに複雑です。 どのように複雑であるかを2つの視点から見ていきましょう。
1. コールバックの戻り値をparserが使用しているスタックで管理している
通常のparserは構文解析をしながらその結果に対応したAST(抽象構文木)を構築していきます。
下の図のように1、2それぞれにNODE_INTEGERというNodeを紐づけておき、1 + 2全体をargだと認識するときにNODE_OPCALLというNodeをつくり、その子要素としてNODE_INTEGERを紐付けます2。これを繰り返すことで入力されたコードを1つの大きな木構造に変換していきます。
一方でRipperの場合は1、2それぞれにコールバックメソッドの戻り値を紐づけています。このようにしておくことで、前のコールバックメソッドの戻り値を次のコールバックメソッドの引数として渡すことができます。
ここで一つ問題があります。Nodeやコールバックメソッドの戻り値はparser generatorが提供するスタックで管理しています。しかしparser generatorは一個しかスタックを提供していないので、RipperではNodeを構築・管理することができません。
一方でRubyの構文解析中に行われる意味解析の一部は構築中のNodeをチェックして行われます。
Bug #10436をみてみましょう。このチケットはm(&nil) {}というコードが通常のparserではエラーになるのに、Ripperではエラーにならないというバグに関するものです。
both block arg and actual block givenというエラーはblock_dup_checkという関数でチェックしています。この関数はメソッドの引数とその後ろに続くブロックの2つのNodeをチェックして両方でブロックを渡していないかを確認します。
つまりこのチェックにはNodeが必要であり、Nodeを構築・管理できないRipperではチェックすることができません。
2. parserとRipperで関数が分離している
parserとRipperでスタックで扱っている値が違うということは、その値を扱うためのロジックもそれぞれ存在します。
例えばpattern matchingで配列を扱うnew_array_pattern関数の場合、parser用の関数とRipper用の関数が存在します。
このように同じ名前で異なる振る舞いをする関数がparse.yには定義されており、複雑さを増しています。
複雑さが増すというのはバグが入り込みやすくなるということでもあります。例えば次のコードの2つ目のbarをパースするときに、parserはlex stateをEXPR_END|EXPR_LABELに更新しますが、現在のRipperはEXPR_ARGに更新します。
def foo(bar: bar()) end
1つ目のbarをパースしたときにbarをローカル変数のテーブルに入れておくことで、2つ目のbarのパース時に特定の分岐に入るようになりlex stateが変化します。
しかし1つ目のbarをローカル変数のテーブルに入れるところで使っているformal_argumentにバグがあり、Ripperの場合はbarがローカル変数のテーブルに登録されなくなっています3。
新しいアーキテクチャ
これらの問題を解決するためにはどうしたらよいでしょうか。 スタックが一つしかないのが問題なので、スタックをもう一つ足すことでこの問題は解決できます。
Bisonにはそのような機能はありませんでしたが、Lramaであれば新しく機能を足せば実現できます。 今回はLramaに5つのcallbackと1つの新しい記法を追加することで、Ripper用に新しくスタックを追加できるようにします。
Lramaの5つのcallback
Lramaから生成したparserに対して以下の5つのcallbackを設定できるようにします。
%after-shift: shiftをしたあとに呼び出す関数を指定できる%before-reduce: reduceをするまえに呼び出す関数を指定できる%after-reduce: reduceをしたあとに呼び出す関数を指定できる%after-shift-error-token: エラー発生時にerrorというトークンが追加されるので、そのタイミングで呼び出す関数を指定できる%after-pop-stack: エラー発生時にスタックを複数回popするので、そのタイミングで呼び出す関数を指定できる
それぞれのcallbackについて使い方をみていきます。
%after-shiftの使い方
本体のparserがshiftをしたときには、Ripper用のスタックにもオブジェクトをpushします。 具体的なコードはこちら。
いま1 +までparserが終わっていて次のトークンが2だとします。2をlexerがスキャンしたときにRipperのon_intメソッドが呼び出されます。ここでは"count 5"が返ってきたとしましょう。%after-shiftでは"count 5"をRipper用のスタックにpushします。
%before-reduceの使い方
本体のparserがreduceする直前に$:$ = $:1のように初期化をしておきます。
こうしておくと、expr : command_callなどのように右辺が1つのときにアクションを省略することができます。
具体的なコードはこちら。
%after-reduceの使い方
本体がreduceをしたらRipperもreduceをします。ルールの右辺の要素数に対応する数だけスタックからオブジェクトをpopし、左辺に対応するオブジェクトをpushします。 具体的なコードはこちら。
1 + 2のケースでは"count 1"と"count 5"を引数にしてon_binaryを呼び出します。ここでは"count 6"が返ってきたとしましょう。%after-reduceでは右辺に対応する3つの要素をスタックからpopし、"count 6"をpushします。
%after-shift-error-tokenと%after-pop-stackの使い方
この2つは構文エラーのときのparserの挙動を真似するために使います。現在のparse.yでは昔からあるpanic modeによるエラーリカバリーを行っているところがあります。panic modeによるエラーリカバリーでは構文エラーに遭遇したときに構文エラーの周辺(前後)をなかったことにして、無視した部分をerrorという特殊なトークンで置き換えるという挙動をします。スタックの操作としてはいまスタックにのっている要素のいくつかをpopし、代わりにerrorトークンをpushするという挙動になります。これらを真似するために%after-pop-stackと%after-shift-error-tokenでそれぞれ適切な処理を行います。
具体的なコードはこちら。
たとえばif 1 + ; then :t endが入力されたとします。;まで処理が進んだときに構文エラーがみつかります。このケースでは1 +をerrorに置き換えif error then :t endとすることでリカバリーを行い、処理を継続できるようにします。
$:1 という記法をLramaに追加する
普段Nodeなどにアクセスするときは$1や$2というようにLramaの提供する特殊な変数を使ってアクセスしています。
| arg '+' arg { $$ = call_bin_op(p, $1, '+', $3, &@2, &@$); }
Ripper用に新しく追加したスタックにアクセスするために、新しい記法を導入する必要があります。
今回は$:1という記法を導入することにしました。これは最終的にはスタックのトップからみたときのマイナスのインデックスに展開されます。
そうすることでstack[-3]やstack[-1]というようにRubyのArray#[]と同じ感覚でスタックにアクセスできるようになります。
parserのデータ構造
最後にparserのデータ構造であるstruct parser_paramsについてもみておきましょう。今回新しくRipper用に3つのフィールドを追加しました。
VALUE s_value; /* Token VALUE */ VALUE s_lvalue; /* VALUE generated by rule action (reduce) */ VALUE s_value_stack;
VALUE s_valueはlexerとparserの間でRubyのObjectを受け渡すのに使います。たとえば"2"を引数としてon_intを呼び出し、そのときの戻り値が"count 5"だったとします。on_intはlexerのイベントなので、"count 5"をparserに渡す必要があります。このとき使われるのがVALUE s_valueです。
VALUE s_lvalueはparserでreduceが発生したときに左辺に対応する値をいれておくためのフィールドです。通常のparserの$$に相当します。
VALUE s_value_stackはRipperのスタックのことで、具体的にはRubyのArrayです。RipperはRubyのObjectを扱うので、スタックにある間は適切にmarkをするなどGCのことを考慮する必要があります。RubyのArrayに格納しておけばVALUE s_value_stackだけをmarkすればよくなるので実装が簡単になります。
解決した問題
今回のアーキテクチャの見直しでparserとRipperが分離していることに起因するバグチケットを全て解決することができました。 具体的には以下の3つのチケットをcloseしました。
- https://bugs.ruby-lang.org/issues/10436
- https://bugs.ruby-lang.org/issues/18988
- https://bugs.ruby-lang.org/issues/20055
また今までレポートはされていませんでしたが他にもさまざまなバグが修正されています。
例えばネストしたnumbered parameterに関するエラーや、リテラルをifの条件に書いた時の警告がRipperで取れるようになるなど、意味解析に関するparserとRipperの差異がなくなりました。
parserとRipperが共通の意味解析を行うので、itのように新しく追加された構文についても基本的にはparser側の実装を更新するだけでRipper側でもサポートされます。
10.times do _1 10.times do _1 end end # => [:compile_error, ["numbered parameter is already used in\n(ripper):2: outer block here"]] 10.times do |i| it end # => [:compile_error, ["ordinary parameter is defined"]]
if 1 else end # => [:warning, ["literal in condition"]]
ほかにはパターンマッチングで変数が定義されたときに正しくvar_refイベントが発火するようになりました。
case i in **a a == {} # aに関するイベントが修正されてvcallからvar_refになった end
まとめ
長い間未解決であったBug #10436などを取り上げ、いままでのRipperの実装とその限界点について分析をしました。RipperではNodeを管理するスタックとRubyのObjectを管理するスタックの2つが必要なのに、過去に使っていたBisonの制約からそれらを1つのスタックで管理するアーキテクチャになっていました。現在はBisonのかわりにLramaを使っているので、Lramaにちょっとした機能を追加することでRipper用にスタックを追加できるようにしました。その結果、既知のバグを全て直すことができました。また今後parserに意味解析が追加された場合にも、Ripperは自動的に追従できるようになりました。
スタックが足らないならスタックを追加すればいいのです。そう、Lramaならね。
- この例ではscannerのイベントが全て発生したのちにparserのイベントが発生していますが、基本的にはscannerとparserのイベントが入り乱れて発生します。↩
-
正確には右の子要素は
NODE_LISTでその下にNODE_INTEGERが紐づくのですが、ここでは説明を簡単にするために一部を省略しています。↩ -
9168行目で
lhsから取り出しているidを返すのが正しいです。ここではRipperはRubyのオブジェクトとidの両方を管理しないといけないので、NODE_RIPPERという特殊なNODEをつくって、そこにRubyのオブジェクトとidの両方を保存しています。なのでformal_argumentの引数の型がparserとRipperで異なります。↩
