RipperでPattern Matchingを扱ったときにGC周りでinconsistencyが起きる問題を直した話 - もしくはparserのメモリ管理の話

たまにはRuby Parser開発日誌以外の話ということでRipperの話をします。

先日このようなpatchを書いたのでその話です。

github.com

ちょっと前からmaster branchでfound internal inconsistencyが発生していました。 具体的なlogは http://ci.rvm.jp/results/trunk-gc-asserts@ruby-sp2-docker/4501173 をみてください。このtestではbuild時にRGENGC_CHECK_MODE=2を設定することで、GCが起こるたびに内部的な不整合をチェックしています。

Ripperのテストの一環としてtest/ripper/test_files_test_2.rbというテストケースでtest/*以下のファイルを対象にRipperを走らせて例外が発生しないかをチェックしています。これにtest_pattern_matching.rbを与えたときにGC周りでなにかinconsistencyが起きるようになっていました。

なにがinconsistencyなのか

これを理解するためにはまずGCとくにRGenGC(世代別GC)についての理解が必要になります。私のGCに対する理解は"CRubyの実装時にもメモリ管理を意識しなくていい、最高！"くらいの理解だったので、より詳細に知りたい方は以下の論文やスライドをみるのがよいと思います。

• http://www.atdot.net/~ko1/activities/sasada-ipsj-pro101.pdf
• https://www.atdot.net/~ko1/activities/sasada-ipsj-pro101-slides.pdf

世代別GC

RGenGC (Restricted Genrational GC)とはRuby 2.1で導入されたGCを高速化する仕組みです。 RubyのGCはmark & sweep GCなので、使用中のobjectをまずmarkして、そのあとでmarkされていないobjectをsweepするという流れになります。これを毎回すべてのobjectを対象に行なっていると時間がかかるので、その改善方法の1つとしてRGenGCがあります。objectは作られて短期間で使われなくなるものと、作られて長期間使われるものに分類できることが経験的に知られています。例えばweb serverでrequestを表すobjectはそのrequestをさばいたあとは使われなくなる一方、DBへのconnectionを管理するためのobjectはプロセスが起動している間は基本的にずっと生きているといった感じです。

そこでobjectを新しい世代(young)と古い世代(old)に分けて、新しい世代のみを対象とするマイナーGCと全ての世代を対象にするメジャーGCを用意し、基本はマイナーGCを実行するという方法をとることでmark & sweepの対象を減らすことができます。なお一定期間新しい世代にいたobjectは古い世代に移動します。

inconsistency

世代別GCで気をつけないといけないのはoldなobjectがyoungなobjectへの参照をもつことがあるということです。例えば以下のような2つのobjectがあったときにarray[0] = strをするとoldからyoungへの参照が発生します。この場合arrayが生きている間はstrを回収されると困ります。ではこの状態でマイナーGCが発生するとどうなるでしょうか。マイナーGCではyoungなobjectから辿れるobjectだけをmarkするのでstrが使われていないことになってしまいます¹。

• array: old
• str: young

この問題を解決するためにwrite barrierという仕組みが用意されています。これはあるobjectから別のobjectに参照が発生したことを記録し、GCのときに参照元のobjectも考慮してmarkするようになります。CRubyのコードにときどき出てくるRB_OBJ_WRITEやRB_OBJ_WRITTENがwrite barrier用のマクロです。このマクロにarrayとstrを渡すと、arrayがoldかつstrがyoungなときにarrayをリメンバーセットに登録します。リメンバーセットに登録されたobjectはmarkするときの起点に含まれるようになるので、これでstrがmarkされるようになり、sweepされなくなります。

found internal inconsistencyとは

inconsistencyにもいろいろ種類があるのですが、今回問題になっていたのはverify_internal_consistency_iのなかでもcheck_generation_iに関するものでした。ここではRubyの管理しているobject(parent)をiterateして、そのobjectがmarkしているobject(child)をみつけ、それらparentとchildの世代を確認します。もし

• parentがold
• childがyoung
• parentがリメンバーセットに登録されていない

という条件をすべて満たす場合、それは上で議論したような状態であり、解放済みのobjectを触ってしまうという(発見の難しい)bugに繋がります。 ということで何がおきているかを知るにはparseおよびRipperがどのようにメモリを管理しているかを知る必要があります。

parser/Ripperのメモリ管理

NODEをどうやって管理するか

parserが主に管理しているものはASTのNODEです。かつては他のobjectと同じようにGCによって管理されていたNODEですが、現在はGCの管理からは外れT_IMEMO/astというobjectがまとめて管理しています²。

具体的にはrb_ast_tがAST全体を管理するための構造体で、これはRubyのGCが管理しています。その中のnode_bufferが動的にメモリを確保しておりNODEの管理もここに含まれます。

// node.c および node.h

typedef struct rb_ast_struct {
    VALUE flags;
    node_buffer_t *node_buffer;
    rb_ast_body_t body;
} rb_ast_t;

typedef struct node_buffer_struct node_buffer_t;

struct node_buffer_struct {
    node_buffer_list_t unmarkable;
    node_buffer_list_t markable;
    struct rb_ast_local_table_link *local_tables;
    VALUE mark_hash;
    // - id (sequence number)
    // - token_type
    // - text of token
    // - location info
    // Array, whose entry is array
    VALUE tokens;
};

ちなみにNODEはRubyのobjectを参照していることがあります。例えばNODE_STRはString objectへの参照をもちます。

$ ruby --dump=p -e '"abcdefg"'

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

こういったNODEの場合、NODEの参照するobjectをmarkするのはT_IMEMO/astの責務です³。objectへの参照をもつNODEをmarkable、そうでないNODEをunmarkableとして分けて管理しています。 markableなNODEにobjectを渡したときはT_IMEMO/astを親としてwrite barrierを設定する必要があります。

Ripperの場合

一方でRipperの場合はunmarkableなNODEを使い、objectはmark_hashに管理させるという方針で実装しています。unmarkableなNODEは典型的にはNODE_CDECLが使われています。この場合はrb_ast_add_mark_objectがrb_hash_asetを呼ぶので、自動的にmark_hashを親としてwrite barrierが設定されます。

ここまでのまとめ

• Parserの場合
  • markableなNODEがobjectへの参照をもつ
  • つまりT_IMEMO/astがobjectを管理している
  • なのでp->astを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼ぶ必要がある
• Ripperの場合
  • unmarkableなNODEがobjectへの参照をもつ
  • つまりmark_hashがobjectを管理している
  • なのでmark_hashを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼ぶ必要がある (これはparse.y的にはadd_mark_object呼ぶことで達成される)

今回何が問題だったか

RipperのときにNODE_ARYPTNやNODE_FNDPTNといったmarkableなNODEにobjectをもたせ、p->astを親としてRB_OBJ_WRITEやRB_OBJ_WRITTENを呼んでいなかったのが問題でした。T_IMEMO/astがoldなときを考えてみましょう。add_mark_objectはmark_hashをリメンバーセットに登録しますが、p->astについてはなにもしません。この状態でGCのconsistencyのチェックが走ると

• T_IMEMO/astはold
• objectはyoung
• T_IMEMO/astからobjectはmarkの対象

となってinconsistencyだと判定されてしまいます。 実際はadd_mark_objectを呼んでいるのでmark_hashはリメンバーセットに登録され、そちらを経由してobjectがmarkされるので参照が残っているobjectが回収されるというbugにはなっていないはずです⁴。

修正はRipperの場合の実装にあわせてunmarkableなNODE(NODE_OP_CDECL)を使うように変更しました。

余談

なんでつい最近まで見つからなかったのか不思議に思う人もいるかと思います。test_files_test_2.rbが毎回対象のファイルをサンプリングしているとはいっても、pattern matchingが入ってからおおよそ4年です。 これには理由があってpattern matchingは3.1までexperimentalな機能でtest_pattern_matching.rbは巨大なstringになっていたからでした。

まとめ

• GCがあってもobjectがどうやって管理されているか知らないといけないことがたまにある
• RubyにはいろいろなCIがあって発見の難しい問題を発見しており、すごい⁵
• Ripperのメモリ管理を改善したい or してほしい...⁶

---

1. 実際はstack上のobjectなどもmarkされますがここでは割愛↩
2. Ruby の NODE を GC から卒業させた - クックパッド開発者ブログを参照↩
3. mark_ast_value関数を参照↩
4. なのでbackportは不要なはず↩
5. Rubyの開発を支える技術 - クックパッド開発者ブログ参照。また ruby-trunk-changes 2023-03-28 - ruby trunk changesによると "安定版メンテナンスの時は TEST_RIPPER_RATIO=1 を指定して全ファイルを parse するようにしてテストしたりしています" とのこと↩
6. ふと思ったんですが、RipperのNODE/VALUE問題って、parseにもう一つsemantic value stackを追加したらNODEとVALUEを分割できて解決したりしませんかね↩

Ruby Parser開発日誌 (5) - Lrama LALR (1) parser generatorを実装した

前回のあらすじ

Ruby Parser開発日誌 (4) - かねこにっき

Error Recoveryに関する理解も深まり、Rubyのparserへ実装するために3つの実装方法を検討しましたが、どれもあまり簡単な方法ではありませんでした。この問題を解決するためにLALR parser generatorを実装したので今回はその紹介をしたいとおもいます。

Lrama LALR (1) parser generator

github.com

前回検討したとおりBisonを使ってError RecoveryをRubyに実装していくのは困難を伴います。これを解決するために自前でparser generatorを実装し、generatorおよびtemplateの両方を自分で管理するという方法を思いついたので実装しました。

名前の由来

Lramaでリャマと読みます。LALR parser generatorのYaccやBisonの流れをくむものとして、リャマという名前にしました。LR parser generatorなのでLlama (LL)ではなくLrama (LR)と綴ります。

parser generatorの概要

主な特徴は以下の通りです

• Rubyによる実装
• Bisonの入力ファイルと同じ形式のファイルを入力とし、C実装のparserを生成する
• 生成可能なparserはLALR(1) parser
• Rubyのtool ディレクトリにインストールして使う想定
• いつでもBisonをLramaに置き換えることが可能なレベルには実装が終わっている

Rubyによる実装

レポジトリをみてわかるようにRubyで実装されています。RubyをソースコードからbuildするときにはBASERUBYという形でRubyが要求されています。LramaはBASERUBYで実行されることを想定しています。

入力と出力

現在のBison用のファイル、つまりparse.yを入力にとります。出力はC実装のparser、つまりparse.cです。

ruby/rubyとの関係

gemとしても配布していますが、ruby/rubyに関していえばtoolディレクトリにインストールして使う想定です。インストールというのは定期的にLramaのソースコードをruby/rubyのtoolディレクトリにコピーしてコミットするという運用を考えています。

RubyのMakefileはYACC変数でbisonコマンドを差し替えることができるので、toolディレクトリにインストールする以外の作業なしで切り替えが可能です。具体的にはLramaのCIでRubyをbuildしているこの行をみてください。

完成度

現在のRubyのparser generatorとして必要な機能は全部実装してあります。

Ruby 3.0.5, 3.1.0, 3.2.0でBison 3.8.2と同等のCコードを出力することを確認しています。

またintegration testとして、Rubyのmaster branchでLramaを使ってRubyをbuildしmake test-allがパスすることを確認しています。

問題は解決したのか

前回明らかになった問題は大きく2つに分けられます。どちらもLramaを実装したことで解消しました。

1. Bisonのテンプレートファイルという実装の詳細に依存すると大変

今後必要な機能はLramaに実装し、LramaとRubyはparse.yで常にやり取りするようになります。なのでRuby側でparse.cをさらに編集したり、テンプレートファイルを持ったりする必要はありません。

2. Bisonのversionをコントロールするのが大変

常にtool以下にインストールされた実装にのみ依存するようになるので、ruby/rubyのコミットが決まればparser generatorの実装が一意に決まるようになります。 副次的な効果として、"(手元のBisonのversionが変わったせいで)なにもしないのに壊れた"が発生しなくなります ¹。

次回予告

拡張可能なparser generatorの実装が手に入ったので、これを利用してRubyのparse.yのMaintainabilityを改善できないか検討・実装を進めています。次回はMaintainabilityに関するお話をしたいと思います。

---

1. 例えばRuby 2.7.7 のリリースにほんのちょっとだけ関わった話 - かねこにっきを参照↩

Ruby Parser開発日誌 (4)

前回のあらすじ

Ruby Parser開発日誌 (3) - かねこにっき

LR parserの仕組みとInsert/Delete/ShiftによるError Recoveryについて、具体例を交えながら理解を深めました。 今回はいよいよError RecoveryをどうやってRubyに実装していくかを考えていきましょう。

実装方法を検討する

現状を確認する

はじめに現在のRubyのparserがどのように実装されているのか確認しましょう。 Rubyではlexerは手書き、parserの生成にはBisonを使っています¹。

大雑把にいうとparse.yをBisonに渡してparse.cとparse.hを生成して、それらをコンパイルして使っています²。

parse.y -- bison --> parse.c & parse.h

つまりError Recoveryを実装するということは何かしらの方法でparse.c(とparse.h)にError Recoveryのコードを実装するということになります。

ちなみに https://www.ruby-lang.org/ で配布されているtarやzipにはparse.cもparse.hも生成済みのものが入っていますので、リリース済みのRubyをrbenvなどでインストールする場合には手元にBisonは必要ありません。Rubyをソースからビルドするときやtarやzipを作る際にはBisonを手元にインストールしておく必要があります³。

実装しないといけない機能

最低限のError Recoveryを実装するとして、parse.cに以下のような変更が必要になります。

1) Syntax Errorに遭遇したときの状態をもとにして、Error Recoveryに必要なInsert/Delete/Shiftの組み合わせを計算する関数を実装する

例えばyyrecover関数としてこの機能を実装します。

2) Error RecoveryでInsertするトークンを初期化する関数を実装する

yyrecover関数はtIDENTIFIERやkeyword_thenといったトークンの種類については決定してくれます。しかしそのトークンのsemantic valueについてはparser generatorを使う側の我々が決めないといけません。semantic valueというのはそのトークンの具体的な値のことで、例えばexitもputsも構文解析上はtIDENTIFIERというトークンになりますが、一方で構文解析より後の工程では再びexitやputsといった情報が必要になります。Error Recoveryは生成規則という文法上の情報をもとに行うので、トークンの種類を決定することはできますが、その具体的な値について決めることはしません。なのでparser generatorの利用者がトークン初期化用の処理を書けるようにして、それをparse.cに組み込む必要があります。

3) Bisonの生成するparserと1, 2で実装した関数を統合する

parserのerror時の挙動を変更してyyrecover関数を呼び出し、その結果に対して2の初期化関数を呼ぶ必要があります。yyrecoverを呼び出す前には今もっているトークンを一時的にどこかに退避する必要もあります。またyyrecoverは複数のトークンを返すことがあるので、それらのトークンをshift仕切るまではyyrecoverの戻り値を、shiftし終わったあとはyyrecoverを呼び出す前にもっていたトークンを復旧して使うという処理を追加します。

インプットif endをif true then endに修復するという前回の例をもとに具体的な解説をしましょう。

ifをshiftしてnext tokenがendになったときにerror状態になります。このときendはすでにlexerからparserに渡っているので、Error Recoveryをする前にendを退避しておきます。

syntax error, unexpected `end' (SyntaxError)
if end
   ^~~

yyrecoverを呼び出した結果、無事にリカバリー用のトークンがみつかり、[true, then]というリカバリー用の2つのトークンが手に入りました。この2つのトークンをもとにshift/reduceをしていきます。

if true then
   ^~~ リカバリー用のトークンが見つかったときはここにいる

if true then
        ^~~ trueをshiftした

if true then
            ^~~ thenをshiftした

ここまでくると次にendがきても処理を進められるので、先ほど退避したendを復旧させます。

if true then end
             ^~~ endを復旧して処理を継続する

というわけで最低でも3つの追加・変更をparse.cに加える必要があります。

実装方法その1 (parse.cをさらに加工する)

一つ目の実装方法はsedや変換用のruby scpritを用意して、bisonコマンドが生成したparse.cをさらに加工する方法です。具体的にはこの前後に処理を追加します。

{$(srcdir)}.y.c:
    $(ECHO) generating $@
    $(Q)$(BASERUBY) $(tooldir)/id2token.rb $(SRC_FILE) > parse.tmp.y
    $(Q)$(YACC) -d $(YFLAGS) -o y.tab.c parse.tmp.y
    $(Q)$(RM) parse.tmp.y
    $(Q)sed -f $(tooldir)/ytab.sed -e "/^#/s|parse\.tmp\.[iy]|$(SRC_FILE)|" -e "/^#/s!y\.tab\.c!$@!" y.tab.c > $@.new
    # このあたりでさらにxx.rbを実行して $@.new に必要な関数を足したりする
    $(Q)$(MV) $@.new $@
    $(Q)sed -e "/^#line.*y\.tab\.h/d;/^#line.*parse.*\.y/d" y.tab.h > $(@:.c=.h)
    $(Q)$(RM) y.tab.c y.tab.h

(1)のyyrecover関数はparse.cの関数定義と関数定義の間など、適切な場所を探して追加すればよさそうです。一方(3)の統合はyyparseという巨大な関数の中身を編集しないといけないので大変そうです。詳しくは後述しますが、複数のBisonのversionをサポートするという課題もあります。

実装方法その2 (テンプレートファイルを自分で管理する)

Bisonはparse.cを生成するのにm4で書かれたテンプレートファイルを使用します。Bisonではskeleton(s)と呼ばれておりdata/skeletons以下で管理されています。Rubyの場合はc-skel.m4とそこから呼ばれているyacc.cが関係します。

またbisonコマンドには-Sというオプションがあり、これを使うとテンプレートファイルを指定することができます。このときテンプレートファイルはBisonのディレクトリ以外のものを指定することができるので、Bisonからyacc.cをRubyのレポジトリにコピーしてきて管理をしていくという方法も考えられます。

とはいえこのテンプレートファイルはBisonの実装の詳細であり、Bisonのversionが変わればテンプレートファイルで利用可能なm4マクロの種類や名前が変わることもあり得ます。現在のRubyではBison 3.0以上を要求していますが、そうはいっても3.0から3.8までversionがあり、https://rubyci.org/を眺めていてもいろいろなversionのBisonが動いています。これら複数のversionを対象にメンテナンスをしていくのは簡単ではありません。同様の理由で一つ目の方法でも、たとえ同じparse.yを与えても使用するBisonのversionによって生成されるparse.cは変わります。結局方法1も方法2も異なるversionのBisonで動くようにするための労力を払っていく必要があります。ここでいう労力とは例えば複数versionで動作する1つのyacc.cを気をつけながら管理する、各versionごとにテンプレートファイルを用意してメンテナンスする、複数version用のCI環境を用意するなどといったことを指します。

OS	Bison
Debian 10.13	3.3.2
Ubuntu 18.04.6	3.0.4
Ubuntu 20.04.4	3.5.1
CentOS 7.9	3.0.4
macOS Big Sur	3.8.2
SPARC Solaris 10	3.5.1

実装方法その3 (Bisonに機能を実装していく)

三つ目の方法はBison本体にError Recovery用のpatchを提供するという方法です。力強く説得力のある方法だと思います。とはいえこの方法もいくつか問題があります。

まずBisonがリッチなparser generatorであるという点です。BisonはC言語以外にC++/D/Javaのparserを生成することができます。またparserの種類も豊富で、LALR(1)以外にGLR, canonical LR, IELR(1)も生成可能です。詳しくは書きませんが他にもpush parserを作ることも可能です。日々Bisonのことを調べるたびにその偉大さに畏敬の念を覚えます。

RubyとしてはC実装のLALR(1)で通常のpull parserでError Recoveryができれば十分ですが、Bisonに実装をするとなると他のケースについても実装していく必要があるでしょう。

またもしBisonに実装されたとしても、各環境でほぼ最新のBisonをインストールしてもらう必要があります。可能であれば各環境でインストールされているBisonそのままでRubyがbuildできることが望ましいという要望があるので、最新のBisonを要求するというのは難しい意思決定になりそうです。

まとめ

いよいよError Recoveryを実装していくにあたって、Rubyのparserの実装およびBisonについて調べました。3つの実装方法について検討をしてきましたが、メンテナンスコストが高い(方法1 & 2)、実装コストが高い(方法3)、説得が難しい(方法3)といずれも簡単な方法ではありません。どうしたものでしょうか...

---

1. ここでYACCの値にbisonを指定しています。↩
2. 実際はさらにid2token.rbによる前処理とsedによる後処理を経てparse.cとparse.hがつくられています。↩
3. 現在はBison 3.0以上が必要です。くわしくは Ruby 3.2のParser目玉機能 - かねこにっき の"開発に必要なBisonのrequired versionを3.0にあげた"をみてください。↩

Ruby Parser開発日誌 (3)

前回のあらすじ

Ruby Parser開発日誌 (2) - かねこにっき

Error Recoveryについてまとめました。もう少し詳しくError Recoveryを説明したほうがいいと思ったので、今回は前回の内容を具体例を用いながら解説します。

最初にLR parserの仕組みについて説明し、その後Error Recoveryの仕組みについて説明します。

LR parserの仕組み

用語の解説

LR parserの仕組みの説明に入る前に、これから使う用語について簡単に説明します。

• 終端記号: Lexerが生み出す記号のことです。例えばRubyではkeyword_class ("class")という記号はLexerが生み出します。トークンと呼ぶこともあります。
• 非終端記号: Lexerが生み出さない記号です。かわりに生成規則によって定義されます。例えばprimaryという非終端記号はprimary: k_class cpath superclass bodystmt k_endというように定義されます。なおprimaryの定義はこれ一つだけではありません。一つの非終端記号が複数の定義をもつことがあります。
• 生成規則: primary: k_class cpath superclass bodystmt k_endのように記号(列)同士の関係を定義したものです。左辺が右辺を生成すると読むこともありますし、右辺が左辺へと還元されると読むこともあります。今回取り上げる例では常に左辺には非終端記号が1つだけ置かれています。

LR parserはプッシュダウン・オートマトン

プッシュダウン・オートマトン - Wikipedia の説明にあるようにプッシュダウン・オートマトン(Pushdown Automaton)とはスタックをもった有限オートマトンです。有限オートマトンとの違いとして

• "現在の状態"、"次の入力値"、"スタックのトップ"の3つの情報をもとに次の状態を決定することができます。有限オートマトンは"現在の状態"、"次の入力値"から次の状態を決定するので、そこに"スタックのトップ"が追加されています
• 次の状態に遷移するときスタックを操作することができます。スタックの操作なのでPushとPopの操作が可能です

LR parserをプッシュダウン・オートマトンとして実装したときの"状態"、"スタック"、"遷移"についてそれぞれ説明をします。

LR parserの状態

入力値はLexerの生成する(次の)トークンなのでいいとして、LR parserにおける状態とはなんなのでしょうか。それはLR項の集合です。LR項は生成規則と•という記号から作られます。ざっくりというと•はその位置にいるということを表しています。

たとえばRubyでif式は以下のような生成規則で定義されています。

primary: k_if expr_value then compstmt if_tail k_end

ここから以下のようなLR項が作られます。同じ生成規則であっても、いる場所が違えば異なる状態になるというわけです¹。

• k_if expr_value then compstmt if_tail k_end # ifの直前にいる
k_if • expr_value then compstmt if_tail k_end # ifの直後にいる
k_if expr_value • then compstmt if_tail k_end # thenの直前にいる
k_if expr_value then • compstmt if_tail k_end # thenの直後にいる
k_if expr_value then compstmt • if_tail k_end # 例えばelseの直前にいる
k_if expr_value then compstmt if_tail • k_end # endの直前にいる
k_if expr_value then compstmt if_tail k_end • # endの直後にいる

LR parserのスタック

LR parserのスタックにはLR parserの状態が積まれます²。

LR parserの遷移

LR parserの遷移は4種類に分類できます。

1) Shift

入力を一つ進め、新しい状態に遷移します。そして新しい状態をスタックにPushします。

2) Reduce

生成規則の右辺の数に応じてスタックを複数回Popします。Pop後のスタックのトップと生成規則の左辺の非終端記号に応じた状態に遷移し、新しい状態をスタックにPushします。

3) Accept

入力値がRubyの文法に従っていることがわかったので、処理を終わります。

4) Error

入力値がRubyの文法に従っていないことがわかったので、処理を終わります。Syntax Errorですね。

具体例

たとえば

if a == 1 then true else false end

という入力を解析するとします。これをトークンで表すと

keyword_if     (if)
tIDENTIFIER    (a)
tEQ            (==)
tINTEGER       (1)
keyword_then   (then)
keyword_true   (true)
keyword_else   (else)
keyword_false  (false)
keyword_end    (end)
END_OF_INPUT

となります。末尾にEND_OF_INPUTという特殊なトークンを加えておきます。

1. 初期状態

まずスタックに0という状態をPushし現在の状態を0にします。その直後に2という状態に遷移しますがこれはそういうものだと思ってください。

* 現在の状態: 0
* スタック: [0]
* 入力値: [keyword_if, tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

=>

* 現在の状態: 2
* スタック: [0, 2]
* 入力値: [keyword_if, tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

2. Shift keyword_if

次にkeyword_ifをShiftし、状態10に遷移します。Shiftしたので入力値が一つ減ります。

* 現在の状態: 10
* スタック: [0, 2, 10]
* 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 10
k_if: keyword_if •

状態10というのはkeyword_ifまで読んだという状態です。

3. Reduce keyword_if

Rubyの文法にはk_if: keyword_if、つまり非終端記号k_ifとは終端記号keyword_ifである、という生成規則があるのでこれを適用してReduceします。 生成規則の右辺に1つのシンボルがあるので、状態を1つPopし、現在の状態が2になります。

* 現在の状態: 2
* スタック: [0, 2]
* 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

生成規則の左辺が非終端記号k_ifであり、現在のスタックのトップは状態2なので状態93に遷移します。よって今回のReduceでは最終的に以下のような状態になります。

* 現在の状態: 93
* スタック: [0, 2, 93]
* 入力値: [tIDENTIFIER, tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 93
primary: k_if • expr_value then compstmt if_tail k_end

4. 条件部分の解析

ここからしばらく条件の部分(a == 1)の処理が続きます。

tIDENTIFIERをShiftして状態35に遷移。その後var_ref: user_variable, primary: var_ref, arg: primaryと右辺が1つのReduceを繰り返し、状態88になります。

* 現在の状態: 88
* スタック: [0, 2, 93, 88]
* 入力値: [tEQ, tINTEGER, keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 88
expr: arg • "==" arg

tEQとtINTEGERをShiftし、それぞれ状態347と状態41になります。

* 現在の状態: 41
* スタック: [0, 2, 93, 88, 347, 41]
* 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 41
simple_numeric: tINTEGER •

その後はtINTEGER -> simple_numeric -> numeric -> literal -> primary -> argとReduceが続きます。間にarg: arg "==" argによるReduceを挟んでexpr_valueになります。

* 現在の状態: 586
* スタック: [0, 2, 93, 88, 347, 586]
* 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 586
arg: arg "==" arg •

=> `arg: arg "==" arg`によるReduceで [88, 347, 586] をpopしたのちに88をpush

* 現在の状態: 88
* スタック: [0, 2, 93, 88]
* 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 88
expr: arg •

=> `expr: arg`そして`expr_value: expr` でReduceする

* 現在の状態: 382
* スタック: [0, 2, 93, 382]
* 入力値: [keyword_then, keyword_true, keyword_else, keyword_false, keyword_end, END_OF_INPUT]

# 状態 382
primary: k_if expr_value • then compstmt if_tail k_end

無事k_if expr_valueまで解析が終わってthenをShiftできるようになりました。条件部分を解析しているときのスタックの様子をみてみると[0, 2, 93]の部分は常にスタックにつまれています。よってprimary: k_if • ...まで解析が終わっている状態が維持され、それよりもスタックの上(図では右)で条件部分(expr_value)の解析をしていることになります。

* スタック: [0, 2, 93] # 条件部分を解析する直前
* スタック: [0, 2, 93, 88]
* スタック: [0, 2, 93, 88, 347, 41]
* スタック: [0, 2, 93, 88, 347, 586]
* スタック: [0, 2, 93, 88]
* スタック: [0, 2, 93, 382]

5. Acceptsされるまで

その後もShiftとReduceを繰り返してkeyword_endをShiftしてk_end: keyword_endでReduceするところまできました。ここからはprimary -> ... -> programとReduceを繰り返します。

* 現在の状態: 1091
* スタック: [0, 2, 93, 382, 628, 799, 972, 1091]
* 入力値: [END_OF_INPUT]

# 状態 1091
primary: k_if expr_value then compstmt if_tail k_end •

=> Reduceを繰り返す

* 現在の状態: 1
* スタック: [0, 1]
* 入力値: [END_OF_INPUT]

# 状態 1
$accept: program • END_OF_INPUT

このprogramというのがRubyの文法の頂点に存在する非終端記号です。すべてのRuby scriptはprogramといえます。状態1かつEND_OF_INPUTのときに状態3に遷移します。状態3にいけば以下のようにAcceptされます。

State 3

    0 $accept: program "end-of-input" •

    $default  accept

parser generatorの役割

BisonをはじめとしたLR parser generatorは文法定義をインプットとして、状態の計算や構文解析表(ある状態と入力に対してShift/Reduce/Accept/Errorのどれを行うかという対応表)を計算し、プッシュダウン・オートマトンのコードを生成してくれます。

構文解析表を読みやすい形にしたものの抜粋を載せておきます³。

State 93

  344        | k_if • expr_value then compstmt if_tail k_end

    error                       shift, and go to state 380
    "`class'"                   shift, and go to state 5
    "`module'"                  shift, and go to state 6
    ...
    expr              go to state 381
    defn_head         go to state 218
    ...

Error Recoveryの仕組み

プッシュダウン・オートマトンからみたError

LR parserをプッシュダウン・オートマトンとして実装したときに、Shift/Reduce/Accept/Errorの4種類の遷移があると書きました。Shift/Reduce/Acceptについては具体例を用いて説明しましたが、Errorについてはまだ説明いなかったので、Error Recoveryの仕組みに先立って説明します。 プッシュダウン・オートマトンからみたErrorというのはShift/Reduce/Acceptのいずれでもないケースです。ShiftをするかReduceをするかといった遷移は生成規則から決まるので、ある状態にいるときに来ても困るトークンが存在します。例えばif endという入力を考えると

* 現在の状態: 93
* スタック: [0, 2, 93]
* 入力値: [keyword_end, END_OF_INPUT]

# 状態 93
primary: k_if • expr_value then compstmt if_tail k_end

と、keyword_ifをShiftしてk_ifにReduceするところまではいいのですが、この次にkeyword_endがきてもShiftもReduceもできません。実際にRubyにこの入力を渡しても、endは期待してないですと言われます。

syntax error, unexpected `end' (SyntaxError)
if end
   ^~~

Error Recoveryの方法その1 (Insert)

復旧方法その1は都合の良いトークンを挿入する方法です。if endの例であればif true then endというようにtrueとthenの2つのトークンがあるものとして処理をすればAcceptされます。

* 現在の状態: 93
* スタック: [0, 2, 93]
* 入力値: [keyword_end, END_OF_INPUT]

# 状態 93
primary: k_if • expr_value then compstmt if_tail k_end

=> 入力値: [keyword_true, keyword_then, keyword_end, END_OF_INPUT] であるとして解析を進める

* 現在の状態: 1091
* スタック: [0, 2, 93, 382, 628, 799, 972, 1091]
* 入力値: [END_OF_INPUT]

# 状態 1091
primary: k_if expr_value then compstmt if_tail k_end •

=> 最終的にAccept

もちろんtrue thenのかわりにa == 1 thenと4つのトークンを挿入してもAcceptされます。

Error Recoveryの方法その2 (Delete)

if a == 1
  true
else
  false
end
end

ではこのような場合はどうするのがいいでしょうか。class A\nを追加してクラスの定義にしてしまうこともできます。

if a == 1
  true
else
  false
end
class A
end

しかし最後のendを削除してしまうほうが素直ではないでしょうか。

if a == 1
  true
else
  false
end

というわけで2つ目の方法は入力トークンを削除するという方法です。

Error Recoveryの方法その3 (Shift)

ここまでは一箇所だけが壊れているケースをみてきましたが、3つ目のケースとして二箇所が壊れているケースを考えてみましょう。

if a == 1 end
  true
else
  false

# syntax error, unexpected `end', expecting `then' or ';' or '\n' (SyntaxError)
if a == 1 end
          ^~~

一行目のendが余分で、最後の行にendが足りていません。

1. endをDeleteする
2. trueからfalseまではインプットをそのまま使用する
3. 最後にendをInsertする

if a == 1
  true
else
  false
end

という方法でこのインプットをリカバリーできます。このときの2番目の操作、つまり"インプットをそのまま使用する"というのがShiftという操作になります。Insertがインプットにないトークンを補うのに対して、Shiftはインプットに存在するトークンをShiftします。

Error Recoveryの処理というのは適切なInsert/Delete/Shiftの操作の組み合わせを見つける作業であると言えます。 ここで"適切な"というのがポイントで、次のような入力について考えてみましょう。

1 +

tINTEGER (2など)をInsertすることでリカバリーすることが可能です。しかし2 + 3や2 + 3 + 4 + 5 ...と複数のトークンをInsertすることでもリカバリーは可能です。というわけで複数のリカバリー方法があったときにどれが最も適切であるかというルールを決めておく必要があります。実際には操作の回数が少ないものほどよいというルールを用いて評価することが多いようです。10回Insertして10回Deleteするようなリカバリーよりも、1回Insertして1回Deleteするリカバリーの方が、もとの入力に近いのでよいということなのでしょう。

リカバリー方法を探すときにどのくらい時間がかかるかというのも大切なポイントです。ある状態にいるときに次に期待するトークンは複数あることが多いのでInsertの候補も複数あり得ます。インプットが残っている限りつねにDeleteを試すことが可能です。気をつけないと大量の候補を探索することになります。いつまでも候補を探し続けても困ってしまうので、例えばInsertは4回まで、Deleteは3回まで、Shiftは10回までといったように操作の回数に上限を設けることもあります。また3回連続でShiftできるようになったらリカバリーが成功したことにするなど、入力の最後まで行く前に打ち切ることもあります。探索するときのアルゴリズムも大切で、深さ優先な探索よりも幅優先な探索が好まれます。幅優先であれば操作回数の少ない候補を全部調べてから操作回数の1つ多い候補を調べるという順番になるからです。

まとめ

• プッシュダウン・オートマトンを利用してLR parserを実装します。
• 正しくないインプットを与えるとプッシュダウン・オートマトンがどこかで停止してしまいます。その状態がError状態です。
• Error状態になったときにInsert/Delete/Shiftという3種類の操作をおこなってインプットを修正することで、プッシュダウン・オートマトンが再び処理をすすめられるようにします。これがError Recoveryです。
• Insert/Delete/Shift操作の組み合わせを探すときは、計算量が大きくならないようにいろいろな工夫をする必要があります。

---

1. LR項はカーネル項(Coreとも)と非カーネル項に分類でき、正確にはカーネル項とその閉包を使って状態を定義します。↩
2. なぜスタックにも状態を積むのかという点については LR構文解析の原理 がおすすめです。↩
3. --report=states,itemsets,lookaheads,solvedといったオプションをbisonコマンドに渡すことで生成できます。↩

Ruby Parser開発日誌 (2)

前回のあらすじ

Ruby Parser開発日誌 (1) - かねこにっき

Ruby 3.3にむけてLALR parserを前提にError Recoveryを実装していくことになりました。

現在の進捗

• Corchuelo et al. のサブセットを実装した
• error recovery tokenのsemantic valueやlocationを設定できるようにした

"Repairing Syntax Errors in LR Parsers"

Don’t Panic! Better, Fewer, Syntax Errors for LR Parsers も参考にしている論文に Repairing Syntax Errors in LR Parsers があります。

この論文では

• insertions: 現在のlookahead tokenの前に1つtokenを追加する (追加したうえでそのtokenに基づいて状態を更新する)
• deletions: 現在のlookahead tokenを削除する
• shifts: N個のlookahead tokenをshiftする

という3つの操作を用いて、Syntax Errorからの復旧を試みます。

既存のShift rule (LR1)とReduce rule (LR2)に対して、Repair rule (LR3)を追加してSyntax Error時の処理を定義しています。LR3はさらに細かく

• Insertion rule (ER1)
• Deletion rule (ER2)
• Forward move rule (ER3)

の3つのruleからなります。それぞれ3つの操作と対応しています。

such that after applying it to an input string, parsing can either continue for at least N symbols or leads to an accepting configuration.

これら3つの操作をした結果、規定のN個のSymbolを処理できるような操作列が見つかれば、Error Recoveryする方法がみつかったということになります。

操作列を探す処理を制限する方法として、探索を幅優先で行うとともに

• Nt: これが何に関する上限かわかってないが、おそらくある状態に対して試すtoken数の上限?
• Ni: Insertionの上限数
• Nd: Deletionの上限数

と上限を設けることで最悪時の計算量を制限します。また論文では最終的に以下の数値にしたとあります。

we have found through experimentation that setting N = 3, Nt = 10, Ni = 4 and Nd = 3 produces good repairs.

変更点

Corchuelo et al. の方法を以下のようにさらに制限して実装をしました。

1. N = 1 つまりerror発生時のlookahead tokenがshiftできる状態になったらError Recoveryしたことにする
2. Nd = 0 つまりlookahead tokenの削除をしない
3. Ni = 5 つまり最大5つまで任意のtokenをlookahead tokenの前に追加してよい

Rubyのlexerは状態に応じて同じ文字列でも異なるtokenを切り出す可能性があります。またparserのアクションはlexerの状態を変更することがあります。しかしparserのアクションはASTの状態を更新したりするため、Error Recoveryで操作列を探索するときはparserのアクションを実行しないようにしています。現時点ではlex stateとtokenとアクションの関係を完全には把握していないので、1番目の制限をいれることでError Recoveryにlexerを動作させないようにしています。

LSPを想定しているので、最後にユーザーが編集した箇所の付近でSyntax Errorが発生しやすいと思っています。一方で最終編集箇所の周辺こそ補完などを行ってほしいはずです。なので2つ目の制限でtokenの削除をしないようにしています。

3つ目の上限は適当に決めています。

メインの実装はこちら。yyrecoverで愚直にそれぞれのtokenを幅優先で試しています。

いくつかの例を試してみましょう。test.rbにコードを書いて./miniruby --dump=y ../../test.rbしています。

# 例1. 行末に改行を含まない
obj.m(a

# repair_terms found. id: 1, length: 1
# id: 1, repair_length: 1, repair_state: 105, prev_repair_id: 0
# ')' 

obj.m(a)というようにリカバリーされています。よさそう。

# 例2. 行末に改行を含まない
class

# repair_terms found. id: 743, length: 2
# id: 743, repair_length: 2, repair_state: 90, prev_repair_id: 27
# "local variable or method" "`end'" 

class a endというようにリカバリーされています。これは実際はactionの中でSyntax Errorが発生するのですが構文的には正しいので選ばれています。これはなにか対策をしないとだめそう。

# 例3. 行末に改行を含まない
if 1

# repair_terms found. id: 9, length: 2
# id: 9, repair_length: 2, repair_state: 90, prev_repair_id: 1
# "`then'" "`end'" 

if 1 then endというようにリカバリーされています。よさそう。

# 例4. 行末に改行を含まない
def m
  obj.
end

# repair_terms found. id: 1, length: 1
# id: 1, repair_length: 1, repair_state: 90, prev_repair_id: 0
# "`end'" 

def m
  obj.
end end

つまりendメソッドの呼び出しにしたうえで、endを補ってdefを閉じています。

# 例5. 行末に改行を含まない
def

# repair_terms found. id: 1614, length: 3
# id: 1614, repair_length: 3, repair_state: 16, prev_repair_id: 91
# "`class'" '=' "`break'" 

def class = breakというようにリカバリーされています。一行メソッド定義でfnameがreswordsのclass、arg == primary == breakですね。

error tokenのsemantic valueの話

この方法でError Recoveryに必要なtokenの種類(たとえばkeyword_classとか=とか)はわかりました。しかしtokenに必要な情報はそれだけではありません。semantic valueやlocationの情報も必要です。しかしこれらは本来yylex (CRubyの場合はparser_yylex)が決定しています。なのでなにか他の方法でerror recovery tokenのsemantic valueやlocationを設定できるようにする必要があります。

Bisonには%printerという機能があるのでこれを参考に%error-tokenという機能を実装してparse.y側で各tokenの種別に応じた初期化ができるようにしましょう。例としてkeyword_classのIDをclass_erに設定してみます。

# 例5. 行末に改行を含まない
def

$ ./miniruby --dump=y ../../test.rb

# Next error recovery token is token "`class'" (0.0-0.0: class_er)
# Next token is token "`class'" (0.0-0.0: class_er)
# Shifting token "`class'" (0.0-0.0: class_er)

このようにちゃんとclass_erがsemantic valueに設定されていますね。

まとめ

• Corchuelo et al. をさらに制限したものでもそれなりに使えそう
• error recovery tokenのsemantic valueやlocationの設定も%printerと同様のインターフェイスで実装すれば良さそう
• 文法定義上はvalidだけど実際はactionでSyntax Errorを出すケース(例2)があるので、そのようなケースをリカバリーの候補にしないように情報を渡せるようにする必要がある
• N >= 2のtokenをshiftできることを期待するのであれば、lex stateと向き合う必要がある

Ruby Parser開発日誌 (1)

Error Tolerant parserに関するアイデア

9月半ばに行われたRubyKaigi 2022以来、3ヶ月くらいError Tolerant parserについて調べたり考えたり実装をしたりしています。 途中でもいいからなにかにアウトプットしておくとよいというアドバイスをもらったので、今現在の状況や考えていることを書いておこうと思います。

Error Tolerant parserとは? どうしてそれが欲しいの?

通常parserはユーザーの入力を受け取り

1. その入力がそのプログラミング言語にとって、validなものか否かをチェック
2. validな場合、その後の工程にとって都合のいいデータ構造(例えばAST)に変換し、後工程に渡す
3. invalidな場合、Syntax Errorをレポートする

といった処理を行います。

しかしIDEやLSP(Language Server Protocol)を前提にするとこの機能だけでは不十分になってきています。 補完を行うときなどには、まだ入力中のある種invalidな入力を受け取り、"なんかいい感じ"にパースしてその結果をもとに補完候補を提示したくなります。 たとえば以下の例では、3行目で引数の候補を提示してほしくなりますよね。

def m1
  a = 1
  obj.m2( # <= ここ
end

このあたりの話は Ruby Committers vs the World by CRuby Committers - RubyKaigi Takeout 2021の11:50ごろからや、同Slides P.8あたりを参照してください。

Ruby 3.2ではどうなるの?

先日書いた通り試験的な機能をRuby 3.2には導入する予定です。 この機能におけるError Recoveryは大きく二つの要素からなっています。

1). error tokenを用いたRecovery

これはBisonが提供している機能で、生成規則にerrorを書くことで特定のケースでRecoveryを行います。もとからRubyでもerror tokenは利用していたのですが、今回Ruby 3.2ではその位置を少し調整しました。

2). 明らかな場合にendを補完する

入力を読み終えた時点で明らかにendを補う必要がある場合に、lexerがendを補うようになりました。

とはいえこれで十分かというとまだまだ改善の余地はたくさんある状態です。 例えば以下のようなコードに対しては現時点では全く情報が残りません。

node = RubyVM::AbstractSyntaxTree.parse(<<-END, error_tolerant: true)
x = 1
if
END

pp node #=> (NIL@0:-1-0:-1)

Error Recoveryとは具体的になにをすることなのか

ざっくりというと入力されてきた文字列(token列)を編集して受理可能な状態にする作業といえます。 ここでいう編集とは以下の3つの操作の組み合わせになります。

1. 必要だけど書かれていないtokenを補う(insertion)
2. 書かれているtokenを捨てる(deletion)
3. それらの組み合わせ(replace)

insertionの操作を行うかどうか、deletionの操作を行うかどうか、エラーに遭遇するまでの結果に対しても編集を行うかどうかなどいくつかの選択肢があり、それに応じて必要な時間やメモリサイズが変わってきます。

どんな選択肢があるの?

パーサ(ジェネレータ)の種類によってError Recoveryの実装方法、その得手不得手が異なってくるのでPEG、ANTLR、手書きパーサ、LALRについてみていきます。

PEG

PEGといえばPythonという偉大な先人がいるので調べてみると Guide to the Parser というドキュメントを発見しました。これによるとPEGにおいては確定的にここで失敗したという情報がないので詳しいエラー情報を出すためにひと工夫しているようです。invalid_ prefixなルールを入れておき、最初はこのルールを無視してパースを行い、もしエラーがあれば再度invalid_ prefixなルールを有効にしてパースを行い、そのinvalid_ prefixなルールの中でエラー処理を行うようです。コメントでも説明されています。

たとえばifをみてみると、if_stmt, elif_stmt, else_blockにそれぞれinvalidなケースをケアするルールが定義してあり

if_stmt[stmt_ty]:
    | invalid_if_stmt
    | 'if' a=named_expression ':' b=block c=elif_stmt {
        _PyAST_If(a, b, CHECK(asdl_stmt_seq*, _PyPegen_singleton_seq(p, c)), EXTRA) }
    | 'if' a=named_expression ':' b=block c=[else_block] { _PyAST_If(a, b, c, EXTRA) }
elif_stmt[stmt_ty]:
    | invalid_elif_stmt
    | 'elif' a=named_expression ':' b=block c=elif_stmt {
        _PyAST_If(a, b, CHECK(asdl_stmt_seq*, _PyPegen_singleton_seq(p, c)), EXTRA) }
    | 'elif' a=named_expression ':' b=block c=[else_block] { _PyAST_If(a, b, c, EXTRA) }
else_block[asdl_stmt_seq*]:
    | invalid_else_stmt
    | 'else' &&':' b=block { b }

invalidなケースのルールの中ではさらに細かくinvalidなパターンを列挙しています。invalid_if_stmtのひとつ目のルールはif condで:を書かずに改行してしまったケース。ふたつ目のルールはif cond:で改行したあとにINDENTがないケース、おそらくですが直前行のindentの深さをみてlexerでINDENTを切り出すか決めているのではないでしょうか。

invalid_if_stmt:
    | 'if' named_expression NEWLINE { RAISE_SYNTAX_ERROR("expected ':'") }
    | a='if' a=named_expression ':' NEWLINE !INDENT {
        RAISE_INDENTATION_ERROR("expected an indented block after 'if' statement on line %d", a->lineno) }
invalid_elif_stmt:
    | 'elif' named_expression NEWLINE { RAISE_SYNTAX_ERROR("expected ':'") }
    | a='elif' named_expression ':' NEWLINE !INDENT {
        RAISE_INDENTATION_ERROR("expected an indented block after 'elif' statement on line %d", a->lineno) }
invalid_else_stmt:
    | a='else' ':' NEWLINE !INDENT {
        RAISE_INDENTATION_ERROR("expected an indented block after 'else' statement on line %d", a->lineno) }

PEGにおいては選択(a / b)はaを試してみて成功しなかったらbを試すというものです。つまり全ての選択肢が失敗したケースがSyntaxErrorになります。なので"if condで:を書かずに改行"というように具体的なルールとしてエラーを記述しているようです。

ANTLR

ANTLRについてはちゃんと調べていないのですが、すくなくともANTLR4はC言語の構文解析器のコードを生成できないようです(サポートするパッチを書けばいいという話はありますが一旦割愛)。

手書きパーサ

手書きパーサにすれば実装する言語(CRubyの場合はC言語になると思う)で表現できるものは扱えるようになるので、だいたいなんでもできるようになるはずです。これは非常に魅力的な点です。 一方で表現力が高すぎるのではないかという不安ももっています。LRであれば受けられている恩恵、例えば

• 入力に対してO(n)で計算可能(もしくはどの程度計算に時間がかかるか事前に把握できる)
• shift/reduceもしくはreduce/reduce conflictを検知できる
• BNFなどの"DSL"により記述できる

といった利点を失うことになります。

• kinabaさんの http://www.kmonos.net/pub/Presen/HiC.pdf P.18 より

手書きの場合のRecoveryはdeletionを関数内部に書いていくというスタイルになると思います。golangおよびrust-analyzerの実装を少し見てみましょう。

まずはgolangの場合。たとえばoperandをパースしている箇所をみてみると、deletionを行っている様子がわかります。全体がtokenのtypeによるswitch文での分岐になっており、_Name, _Literalなどでない場合のdefaultの処理でエラー時の処理を行なっています。p.badExpr()でエラー時のNodeを作成します。また同時にadvanceを呼んで特定のtokenが出現するまでtokenを捨てます。

次にrust-analyzerの場合。fn(関数定義)をパースしている箇所をみてみると、deletionを行っている様子がわかります。fn foo() {}のfooをパースするときにname_rにITEM_RECOVERY_SETを渡して呼び出します。name_rは現在のtokenがIDENT(identifier)でない場合にerr_recoverを呼び出します。err_recoverは現在のtokenがrecoveryに含まれる時はerror messageを記録だけして処理を続けます。つまり1つtokenを削除しているといえます。

複数のtokenを削除するgolangと1つのtokenだけを削除するrust-analyzerという違いはありますが、どちらもエラー遭遇時点から先のtokenを削除のみを用いて復旧を図るというアプローチになっています。

このアプローチの場合、各関数においてどのトークンまでを捨てるかを考えてチューニングしていくことになると思うので、その作業に対してどのくらい指針となるものがあるかがポイントだと思います。

LALR

現在CRubyではGNU Bisonというパーサジェネレータを使ってLALRパーサを生成して使っています。

Bisonの標準的なError Recoveryの方法はpanic-modeと呼ばれたりします。この方法で難点と感じるのは

• 今までの計算結果を一部捨ててしまう(linkでいうと(2))
• その先のtokenも一部捨ててしまう(linkでいうと(4))

今ちょうど入力した文字(列)というのがSyntax Errorを引き起こしている可能性は高いので、そこを中心に入力tokenを破棄されてしまうのはあまり都合のよいものではありません。

では他にどのようなError Recoveryの方法が考案されているかというと

• Don’t Panic! Better, Fewer, Syntax Errors for LR Parsers

およびそこで参照されているものとして

• Repairing Syntax Errors in LR Parsers
• Locally least-cost error repair in LR parsers

のようにエラーに遭遇した場合にそれ以降の全てのtokenを対象にinsertion/deletionしてvalidなtoken列にするというアイデアがあります。

• Don’t Panic! Better, Fewer, Syntax Errors for LR Parsers P.12より

これまでのアプローチのなかでこれが一番広いアプローチだと思います。また文法定義を入力としてError Recoveryするコードを書けばよいという点も魅力です。手書きパーサのところで"各関数においてどのトークンまでを捨てるかを考えてチューニングしていくことになると思う"と書きましたが、入力となる文法規則がその指針となるというイメージです。

ではどうするか

私個人としては当面はLALR parserを前提にError Recoveryを実装できないか考えていくつもりです。

開発は今どんな感じなの?

とりあえず次の一歩として、生成規則をもとに各LR項について最短で右辺をつくれるtoken列を事前に計算し、エラーになったらそのtoken列を先頭から補完するという実装を試してみています。

def m1
  a = 1
  obj.m2(
end

このような入力は以下のようなASTになります。あくまで入力をASTにすることが目的で、Recoveredは修復を行った結果をscriptとして表現した参考情報です。

=========================
Input:

def m1
  a = 1
  obj.m2(
end


=>

Recovered:

def m1
  a = 1
  obj.m2(
 ) end


AST:
(SCOPE@1:0-4:3
 tbl: []
 args: nil
 body:
   (DEFN@1:0-4:3
    mid: :m1
    body:
      (SCOPE@1:0-4:3
       tbl: [:a]
       args:
         (ARGS@1:6-1:6
          pre_num: 0
          pre_init: nil
          opt: nil
          first_post: nil
          post_num: 0
          post_init: nil
          rest: nil
          kw: nil
          kwrest: nil
          block: nil)
       body:
         (BLOCK@2:2-4:3 (LASGN@2:2-2:7 :a (LIT@2:6-2:7 1))
            (CALL@3:2-4:3 (VCALL@3:2-3:5 :obj) :m2 nil)))))
=========================

Ruby 2.7.7 のリリースにほんのちょっとだけ関わった話

11/24にRuby 2.7.7, 3.0.5, 3.1.3がリリースされました

• https://www.ruby-lang.org/ja/news/2022/11/24/ruby-2-7-7-released/
• https://www.ruby-lang.org/ja/news/2022/11/24/ruby-3-0-5-released/
• https://www.ruby-lang.org/ja/news/2022/11/24/ruby-3-1-3-released/

今まで一度もリリース作業に関わったことがなかったのですが、今回はRuby 2.7.7でripperのtestがこける! という話を聞いて、嫌な予感がしたのでデバッグに参加しました。 やったことを順番に書いていきます。

手元で再現するか確認

なにはともあれ手元で再現させないと調査も難しいので、その時点の ruby_2_7 branch をチェックアウトしてテストを実行しました。

$ git co ee8dc8a2f3ee7983d18339ea31444a981e63a874
$ make main
$ make test-all TESTS="../test/ripper/*"

Run options: "--ruby=./miniruby -I../lib -I. -I.ext/common  ../tool/runruby.rb --extout=.ext  -- --disable-gems" --excludes-dir=../test/excludes --name=!/memory_leak/

# Running tests:

[313/434] TestRipper::Ripper#test_yydebug_ident = 0.00 s
  1) Failure:
TestRipper::Ripper#test_yydebug_ident [ruby/ruby/test/ripper/test_ripper.rb:75]:
Expected "Next token is token \"local variable or method\" (1.0-1.9: )" to include "test_xxxx".

[327/434] TestRipper::Ripper::TestInput#test_yydebug_ident = 0.00 s
  2) Failure:
TestRipper::Ripper::TestInput#test_yydebug_ident [ruby/ruby/test/ripper/test_ripper.rb:75]:
Expected "Next token is token \"local variable or method\" (1.0-1.9: )" to include "test_xxxx".

Finished tests in 7.129586s, 60.8731 tests/s, 472.3977 assertions/s.
434 tests, 3368 assertions, 2 failures, 0 errors, 0 skips

ruby -v: ruby 2.7.7p220 (2022-11-24 revision ee8dc8a2f3) [arm64-darwin21]
make: *** [yes-test-all] Error 2

見事に再現しますね。

テストケースを読む

該当するテストケースは以下のようになっていて、yydebug をオンにしたときに特定の文字列が表示されるかをチェックしています。

  def test_yydebug_ident
    out = StringIO.new
    ripper = Ripper.new 'test_xxxx'
    ripper.yydebug = true
    ripper.debug_output = out
    ripper.parse
    assert_include out.string[/.*"local variable or method".*/], 'test_xxxx'
  end

どんな出力かパッとみてわからないので、--dump=yをして3.1系のRubyの出力と比較をしてみます。ripperとparserはコードを結構な部分で共有しているので、とりあえずこのオプションをつけて実行してみて、それでもわからなければちゃんとripperを使って検証しようという判断です。

$ ruby -v --dump=y -e 'test_xxxx'
ruby 3.1.3p185 (2022-11-24 revision 1a6b16756e) [arm64-darwin21]
...
Next token is token "local variable or method" (1.0-1.9: test_xxxx)
Shifting token "local variable or method" (1.0-1.9: test_xxxx)
...

$ ./miniruby -v --dump=y -e 'test_xxxx'
ruby 2.7.7p220 (2022-11-24 revision ee8dc8a2f3) [arm64-darwin21]
...
Next token is token "local variable or method" (1.0-1.9: )
Shifting token "local variable or method" (1.0-1.9: )
...

なるほど。確かにtest_xxxxがないですね。

コードを調査する

ちょうど先日この出力周りをmaster branchでいじった記憶があったので知っているのですが、この出力はBisonの %printer Directive で制御しています。 そこでparse.yの%printerを探すのですが、そのようなコードが見つかりません。なぜ？ よくわからないのでmaster branchで%printerがいつ導入されたか確認します。

$ git co master
$ git log -S printer -p parse.y

すると https://github.com/ruby/ruby/commit/fa05697e4832fbd67a4f91b9bb362471902faab3 というコミットがみつかります。つまりYYPRINTを消して%printerに置き換えています。 もう一度 ruby_2_7 branchにもどってparse.yを確認すると、たしかにYYPRINTが残っています。念の為 ripper.c (.yでない)を眺めるとYYPRINTは#defineされてますが、まったく呼び出されていないことがわかります。ripper.cの先頭行をチェックしてBisonのversionをみると /* A Bison parser, made by GNU Bison 3.8.2. */ となっており、BisonのversionがあがってYYPRINTが呼ばれなくなったのかもしれないと見当がつきました。一応他に再現できているコミッターのBisonを確認してもらったところ、みんな3.8.2を使って再現しており。限りなくこれが怪しいという雰囲気になりました。

最終的には fa05697e4832fbd67a4f91b9bb362471902faab3 がバックポートされ、無事テストが通るようになりました。

まとめ

一応Bison側のchange logを追いかけてみて3.8でYYPRINTのサポートが終了したことを確認しました。

みなさんお疲れ様でした！