まもなくRuby 3.3.0がリリースされますね。

LramaによるBisonの置き換え、named referencesによるparse.yのリファクタリングなど、parser本体の大きな改善が入ったバージョンになります。

今回はRuby 3.3向けに行った改善のうち「Rubyの抽象構文木のデータ構造の改善」という内部的な改善を紹介します。

問題の背景

RubyのNodeはかつてGCで管理されていました。そのころの名残で全ての種類のNodeがたった一つのRNode構造体を共有しています。 他のNodeへのポインタやメソッド名を表すIDなどはu1, u2, u3という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;

これには三つの問題点があります。 メモリを無駄遣いしていること、一部のNodeが複雑な構造になっていること、Nodeの種類とそのフィールドの対応が一目で分からないことです。

メモリの無駄遣い

例えばtrueを表すNODE_TRUEやnilを表すNODE_NILなどは他のNodeへの参照といった付加的な情報をもちません。 ということはRNode構造体分のメモリを確保していても、それらのu1, u2, u3といったフィールドは使われていません。

複雑な構造のNode

一方でstruct.field += fooを表すNODE_OP_ASGN2はstruct, field, +=, fooと4つのフィールドを必要としており、u1からu3では足りません。 そのため2つのNodeを組み合わせてNODE_OP_ASGN2を表現しています。

Nodeの種類とそのフィールドの対応

Unionとして定義されているu1, u2, u3の実際の型はNodeの種類によって変わります。 例えばNODE_IFであれば3つとも他のNodeへの参照ですし、NODE_CALLの場合はNodeとidが混在しています。 実際にNodeを使うときは、Nodeの種類に応じて適切なマクロを使い分ける必要があります。

// NODE_IFの場合は3つとも他のNodeのポインタになっている
#define nd_cond  u1.node
#define nd_body  u2.node
#define nd_else  u3.node

// NODE_CALLの場合はメソッド名がidで他はNodeのポインタ
#define nd_recv  u1.node
#define nd_mid   u2.id
#define nd_args  u3.node

Ruby Parser Roadmapとの関係

これらの問題は"Union to Struct (Node)"および"Optimize Node memory management"という目標としてRuby Parser Roadmapにも組み込まれています。 とくにNodeのデータ構造を改善する"Union to Struct (Node)"は、LSP向けにより使い勝手のよいASTを返すという大目標の前提となる目標です。

docs.google.com

やったこと

UnionからStructへ

github.com

まずはNODE_TRUEであればstruct RNode_TRUE、NODE_OP_ASGN2であればstruct RNode_OP_ASGN2といったように、Nodeの種類ごとに対応する構造体を用意します。 struct RNodeは各種構造体の先頭のフィールドとしてflagsやnd_locなど共通する要素のみを含む構造体にします。 Node全体はstruct RNodeで扱い、必要に応じてそのtypeをみてRNODE_TRUEなどのマクロでキャストして使います。

ここでは使っていないフィールドもnot_usedという名前のフィールドとしていままで通り確保するようにしておきます。 この時点では"parse.y"や"compile.c"の一部のロジックがNODE_CALL系のNodeを一律NODE_CALLにキャストしていたりするので、not_usedなフィールドを手当たり次第消してしまうとSEGVすることがあるためです¹。

typedef struct RNode_TRUE {
    NODE node;

    // 実際は使っていないがnot_usedという名前にして確保しておく
    VALUE not_used;
    VALUE not_used2;
    VALUE not_used3;
} rb_node_true_t;

また今後構造体ごとのサイズが変わることを想定して、Node用のバッファで異なるサイズの構造体を管理できるように変更します。

not_usedなフィールドを消していく

準備は完了しました。not_usedを消していきましょう!

SELF, NIL, TRUE, FALSEやALIAS, VALIAS, UNDEFなどは単純に構造体からフィールドを消すだけでよいので対応は簡単です。一方でNODE_CALLなどメソッド呼び出しに関するNodeは複数種類のNodeを共通して扱う箇所があるので、補助的な関数を書いてフィールドアクセスを隠蔽する必要がありました。例えばレシーバーを取り出すget_nd_recvやメソッドのidを取り出すget_nd_midなどを実装する必要がありました。

このPRをもって全てのNodeからnot_usedなフィールドの削除を完了しています。

github.com

複数のNodeで表現していたものを一つにまとめる

たびたび話題にあがるNODE_OP_ASGN2もついに一つのNodeへと統合されました。

またパターンマッチングに使うNODE_ARYPTNとNODE_FNDPTNではそれぞれ専用の構造体を使ってNodeに収まらないデータを管理していましたが、今回の改善でそれらもNodeの中に埋め込むことができました。

まとめ

たった一つのRNode構造体で管理していたRubyのNodeを、その種類に応じたNodeを定義してそれらを使うように変更しました。そしてNodeごとに必要なフィールドだけを定義するようにリファクタリングを行いました。

これらのリファクタリングによって以下の3つの点が改善されました。

1. 各Nodeが必要十分なメモリを使うようになった
2. Nodeのネストのような複雑な構造が解消された
3. 各Nodeの構造体を見るだけでどのような型のフィールドがあるのか一目でわかるようになった

これらの改善をもとに、次はいよいよLSP向けに使いやすいNodeを提供するために、Nodeの構造を変更していきます。

この改善は遠藤さんが2017年に行った改善の延長にあるものです。"抽象構文木の表現のムリ・ムダを省いていける準備ができた"にあるように、準備はできていたのですがなかなか着手する機会がなく今日まできていました。2017年以来いつかやろうとおもっていた改善でしたが、今年ついに達成することができました。2017年にNodeのメモリ管理を整理していただき、ありがとうございました²。

techlife.cookpad.com