以下の内容はhttps://yui-knk.hatenablog.com/entry/2026/02/09/104635より取得しました。

Ruby Parser開発日誌 (24-31) - parse.yが生成するノードを変える ー arrayリテラル

31日目: arrayリテラル

前回はhashに対応したので今回はarrayに対応しましょう1。

parserはできている

見出しのとおりparserはできているのでいいとして、問題はコンパイラです。

# @ ArrayNode (location: (1,0)-(1,2))*
# +-- elements: (length: 0)
[]

# @ ArrayNode (location: (2,0)-(2,8))*
# +-- elements: (length: 2)
# |   +-- @ SymbolNode (location: (2,1)-(2,3))
# |   |   +-- unescaped: "a"
# |   +-- @ SymbolNode (location: (2,5)-(2,7))
# |       +-- unescaped: "b"
[:a, :b]

# @ ArrayNode (location: (3,0)-(3,15))*
# +-- ArrayNodeFlags: nil
# +-- elements: (length: 3)
# |   +-- @ SymbolNode (location: (3,1)-(3,3))
# |   |   +-- unescaped: "a"
# |   +-- @ SymbolNode (location: (3,5)-(3,7))
# |   |   +-- unescaped: "b"
# |   +-- @ KeywordHashNode (location: (3,9)-(3,14))
# |       +-- elements: (length: 1)
# |           +-- @ AssocNode (location: (3,9)-(3,14))
# |               +-- key:
# |               |   @ SymbolNode (location: (3,9)-(3,11))
# |               |   +-- unescaped: "k"
# |               +-- value:
# |               |   @ SymbolNode (location: (3,12)-(3,14))
# |               |   +-- unescaped: "v"
[:a, :b, k: :v]

2つ目の例からわかるように最適化が全くされていません。 またSplatNodeやKeywordHashNodeの対応も必要です。 それぞれやっていきましょう。

# 0000 newarray                               0                         (   1)[Li]
[]

# 0000 putobject                              :a                        (   3)[Li]
# 0002 putobject                              :b
# 0004 newarray                               2
[:a, :b]

[a, *b, c]
#=> iseq_compile_each: unknown node (RB_SPLAT_NODE)

[:a, :b, k: :v]
#=> iseq_compile_each: unknown node (RB_KEYWORD_HASH_NODE)

compile_array関数を最適化する

いまのcompile_array関数は実引数をコンパイルするときに必要最低限の実装をしたものです。

static int
compile_array(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *node, const rb_node_list2_t *list, int popped, bool first_chunk)
{
    const NODE *line_node = node;

    if (list->size == 0) {
        if (!popped) {
            ADD_INSN1(ret, line_node, newarray, INT2FIX(0));
        }
        return 0;
    }

    if (popped) {
        for (size_t i = 0; i < list->size; i++) {
            NO_CHECK(COMPILE_(ret, "array element", list->nodes[i], popped));
        }
        return 1;
    }

    // TODO: Optimize
    for (size_t i = 0; i < list->size; i++) {
        NO_CHECK(COMPILE_(ret, "array element", list->nodes[i], popped));
    }
    ADD_INSN1(ret, line_node, newarray, INT2FIX(list->size));

    return 1;
}

配列が空のケース(if (list->size == 0))、配列をスタックに乗せる必要がないケース(if (popped))はそのままにして、それ以降の部分を最適化していきましょう。 書き換え前のcompile_array関数と現在のcompile_hash関数を参考に書き換えたcompile_array関数は以下の通りです。

static int
compile_array(rb_iseq_t *iseq, LINK_ANCHOR *const ret, const NODE *line_node, const rb_node_list2_t *list, int popped, bool first_chunk)
{
    const NODE *node;

    if (list->size == 0) {
        if (!popped) {
            ADD_INSN1(ret, line_node, newarray, INT2FIX(0));
        }
        return 0;
    }

    if (popped) {
        for (size_t i = 0; i < list->size; i++) {
            NO_CHECK(COMPILE_(ret, "array element", list->nodes[i], popped));
        }
        return 1;
    }

    const int max_stack_len = 0x100;
    const int min_tmp_ary_len = 0x40;
    int stack_len = 0;

    /* Either create a new array, or push to the existing array */
#define FLUSH_CHUNK \
    if (stack_len) {                                            \
        if (first_chunk) ADD_INSN1(ret, line_node, newarray, INT2FIX(stack_len)); \
        else ADD_INSN1(ret, line_node, pushtoarray, INT2FIX(stack_len));     \
        first_chunk = FALSE; \
        stack_len = 0;                            \
    }

    for (size_t i = 0; i < RB_NODE_LIST_LEN(list);) {
        int count = 1;
        node = list->nodes[i];

        // symbolなどのstatic literalが並んでいる部分を1つの`duparray`命令にする
        //
        /* pre-allocation check (this branch can be omittable) */
        if (static_literal_node_p(node, iseq, false)) {
            /* count the elements that are optimizable */
            size_t j = i + 1;
            for (; j < RB_NODE_LIST_LEN(list) && static_literal_node_p(list->nodes[j], iseq, false); j++)
                count++;

            if ((first_chunk && stack_len == 0 && (j == RB_NODE_LIST_LEN(list))) || count >= min_tmp_ary_len) {
                /* The literal contains only optimizable elements, or the subarray is long enough */
                VALUE ary = rb_ary_hidden_new(count);

                /* Create a hidden array */
                for (; count; count--, i++) {
                    node = list->nodes[i];
                    rb_ary_push(ary, static_literal_value(node, iseq));
                }
                RB_OBJ_SET_FROZEN_SHAREABLE(ary);

                /* Emit optimized code */
                FLUSH_CHUNK;
                if (first_chunk) {
                    ADD_INSN1(ret, line_node, duparray, ary);
                    first_chunk = FALSE;
                }
                else {
                    ADD_INSN1(ret, line_node, putobject, ary);
                    ADD_INSN(ret, line_node, concattoarray);
                }
                RB_OBJ_SET_SHAREABLE(ary);
                RB_OBJ_WRITTEN(iseq, Qundef, ary);
            }
        }

        /* Base case: Compile "count" elements */
        for (; count; count--, i++) {
            node = list->nodes[i];

            // `[:a, k: :v]`のようにキーワード引数があるときはキーワード引数部分をコンパイルして
            // `pushtoarraykwsplat`命令で配列に追加する
            //
            if ((i == RB_NODE_LIST_LEN(list) - 1) && nd_type_p(node, RB_KEYWORD_HASH_NODE)) {
                /* Create array or push existing non-keyword elements onto array */
                if (stack_len == 0 && first_chunk) {
                    ADD_INSN1(ret, line_node, newarray, INT2FIX(0));
                }
                else {
                    FLUSH_CHUNK;
                }
                NO_CHECK(COMPILE_(ret, "array element", node, 0));
                ADD_INSN(ret, line_node, pushtoarraykwsplat);
                return 1;
            }
            else {
                // 最適化できないケースでは、通常通り配列の要素をコンパイルする
                //
                NO_CHECK(COMPILE_(ret, "array element", node, 0));
                stack_len++;
            }

            /* If there are many pushed elements, flush them to avoid stack overflow */
            if (stack_len >= max_stack_len) FLUSH_CHUNK;
        }
    }

    FLUSH_CHUNK;
#undef FLUSH_CHUNK
    return 1;
}

またiseq_compile_each0関数がKeywordHashNodeをコンパイルできるようにしておきます。 実際の処理はcompile_hash関数に任せればよいでしょう。

      case RB_KEYWORD_HASH_NODE: {
        CHECK(compile_hash(iseq, ret, node, &RB_NODE_KEYWORD_HASH(node)->elements, FALSE, popped) >= 0);
        break;
      }

ためしにいくつか配列を作ってみましょう。

# newarray 0
[]

# duparray [:a]
[:a]

# putself
# opt_send_without_block <calldata!mid:m, argc:0, ...>
# newarray               1
[m]

# putobject           :a
# putobject           :b
# newarray            2
# duphash             {k: :v}
# pushtoarraykwsplat
[:a, :b, k: :v]

また一時的にmin_tmp_ary_lenを2にして最適化が行われるか見ておきましょう。

# duparray                               [:a, :b]                  (   1)[Li]
# putself
# opt_send_without_block                 <calldata!mid:m, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# pushtoarray                            1
# putobject                              [:c, :d]
# concattoarray
[:a, :b, m, :c, :d]

SplatNodeに対応する

[a, *b, c]の*bのようにsplatがあるケースを考えます。 splatする要素が先頭のときと、それ以外とで生成されるバイトコードが変わります。

# 0000 putself                                                          (   1)[Li]
# 0001 opt_send_without_block                 <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0003 splatarray                             true
# 0005 putself
# 0006 opt_send_without_block                 <calldata!mid:b, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0008 pushtoarray                            1
[*a, b]

# 0000 putself                                                          (   1)[Li]
# 0001 opt_send_without_block                 <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0003 newarray                               1
# 0005 putself
# 0006 opt_send_without_block                 <calldata!mid:b, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0008 concattoarray
[a, *b]

splatが先頭でないときはそれ以前のバイトコードでスタック上にarrayがある状態になっているのでそこにconcattoarrayをすることになります。 一方でsplatが先頭のときはスタック上にconcatすべきarrayがないのでsplatarray命令でarrayを生成します。

以上をふまえてcompile_array関数のBase caseにelse ifの分岐を追加します。

        /* Base case: Compile "count" elements */
        for (; count; count--, i++) {
            node = list->nodes[i];

            if ((i == RB_NODE_LIST_LEN(list) - 1) && nd_type_p(node, RB_KEYWORD_HASH_NODE)) {
                /* Create array or push existing non-keyword elements onto array */
                if (stack_len == 0 && first_chunk) {
                    ADD_INSN1(ret, line_node, newarray, INT2FIX(0));
                }
                else {
                    FLUSH_CHUNK;
                }
                NO_CHECK(COMPILE_(ret, "array element", node, 0));
                ADD_INSN(ret, line_node, pushtoarraykwsplat);
                return 1;
            }
            else if (nd_type_p(node, RB_SPLAT_NODE)) {
                FLUSH_CHUNK;

                NO_CHECK(COMPILE_(ret, "array element", RB_NODE_SPLAT(node)->expression, 0));
                if (first_chunk) {
                    /* [*ary, ...] */
                    ADD_INSN1(ret, node, splatarray, Qtrue);
                    first_chunk = FALSE;
                }
                else {
                    /* [..., *ary, ...] */
                    ADD_INSN(ret, node, concattoarray);
                }
            }
            else {
                NO_CHECK(COMPILE_(ret, "array element", node, 0));
                stack_len++;
            }

            /* If there are many pushed elements, flush them to avoid stack overflow */
            if (stack_len >= max_stack_len) FLUSH_CHUNK;
        }
    }

minirubyをビルドしてバイトコードを生成すると期待通りの結果になっています。

# 0000 putself                                                          (   1)[Li]
# 0001 opt_send_without_block                 <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0003 splatarray                             true
# 0005 putself
# 0006 opt_send_without_block                 <calldata!mid:b, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0008 pushtoarray                            1
[*a, b]

# 0000 putself                                                          (   1)[Li]
# 0001 opt_send_without_block                 <calldata!mid:a, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0003 newarray                               1
# 0005 putself
# 0006 opt_send_without_block                 <calldata!mid:b, argc:0, FCALL|VCALL|ARGS_SIMPLE>
# 0008 concattoarray
[a, *b]

まとめ

今日の成果です。

  1. arrayのほうがあとなのはhashより面倒そうだったからです...↩


以上の内容はhttps://yui-knk.hatenablog.com/entry/2026/02/09/104635より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14