compile.cの変更

Python/compile.cを探る

compile.cの改良を試みるため、まずはcompile.cの中身を探っていく。VSCodeの検索機能を用いてbreakを探すと、3024行に次のようなcompiler_breakが見つかる。

Python/compile.c: L3024

static int
compiler_break(struct compiler *c)
{
    struct fblockinfo *loop = NULL;
    /* Emit instruction with line number */
    ADDOP(c, NOP);
    if (!compiler_unwind_fblock_stack(c, 0, &loop)) {
        return 0;
    }
    if (loop == NULL) {
        return compiler_error(c, "'break' outside loop");
    }
    if (!compiler_unwind_fblock(c, loop, 0)) {
        return 0;
    }
    ADDOP_JUMP(c, JUMP_ABSOLUTE, loop->fb_exit);
    NEXT_BLOCK(c);
    return 1;
}

これは明らかにbreakの動作を決めている関数である。中身を見ていくと、

  • compiler_unwind_fblock_stackという関数があり、ここで何らかの処理をしている
  • compiler_errorのエラー文を見ると、ループが存在しない場合のエラー処理をしている
  • compiler_unwind_fblockで何らかの処理をしている
  • ADDOP_JUMPbreakの動作をするジャンプ命令のバイトコードを生成
  • NEXT_BLOCKで次のブロックに移動

だと読み取れる。また、compiler_breakで検索すると、compiler_visit_stmtという関数内で、3566行に、

Python/compile.c: compiler_visit_stmt L3566

    case Break_kind:
        return compiler_break(c);

という場所があるので、compiler_breakと似た関数を作る場合は、ここも忘れずに同様な記述をする必要がある。

compiler_breakだけでは動作がよく分からないので、compiler_unwind_fblock_stackの中を見ていく。

Python/compile.c: L1871

/** Unwind block stack. If loop is not NULL, then stop when the first loop is encountered. */
static int
compiler_unwind_fblock_stack(struct compiler *c, int preserve_tos, struct fblockinfo **loop) {
    if (c->u->u_nfblocks == 0) {
        return 1;
    }
    struct fblockinfo *top = &c->u->u_fblock[c->u->u_nfblocks-1];
    if (loop != NULL && (top->fb_type == WHILE_LOOP || top->fb_type == FOR_LOOP)) {
        *loop = top;
        return 1;
    }
    struct fblockinfo copy = *top;
    c->u->u_nfblocks--;
    if (!compiler_unwind_fblock(c, &copy, preserve_tos)) {
        return 0;
    }
    if (!compiler_unwind_fblock_stack(c, preserve_tos, loop)) {
        return 0;
    }
    c->u->u_fblock[c->u->u_nfblocks] = copy;
    c->u->u_nfblocks++;
    return 1;
}

中身を見ていくと、

  • c->u->u_nfblocksはもっとも外側のframe block(for while tryなど)から数えたframe blockの数
  • c->u->u_fblockはframe blockを、もっとも外側をc->u->u_fblock[0], 現在地(breakの場合はbreakがある位置)をc->u->u_fblock[c->u->u_nfblocks-1]として積んでいる配列
  • topに現在のframe blockの情報を渡す
  • topを参照し、forwhileならばlooptopを渡し関数を出る(loopに渡されたものを抜ける処理がbreakである)
  • forwhileでなかった場合、c->u->u_nfblocksを1下げることで、一つ外側のframe blockについてcompiler_unwind_fblockcompiler_unwind_fblock_stackをもう一度実行している(forwhileでなければbreakで抜けることができないので、より外側のframe blockを探しにいくイメージ)

といった構造になっている。ここから、多重ループを抜け出すbreakを実現するには、このcompiler_unwind_fblock_stackをうまく改造することが中心の作業となることが予想される。特に、loopに渡すものをうまく制御できれば、我々が実装したい複数ループを抜けるbreakを実装できると思われる。

次に、compiler_unwind_fblockを見ていく。(話の流れ的に書いたけど、長いし変更するわけでもないからいらないかも?)

Python/compile.c: L1769

/* Unwind a frame block.  If preserve_tos is true, the TOS before
 * popping the blocks will be restored afterwards, unless another
 * return, break or continue is found. In which case, the TOS will
 * be popped.
 */
static int
compiler_unwind_fblock(struct compiler *c, struct fblockinfo *info,
                       int preserve_tos)
{
    switch (info->fb_type) {
        case WHILE_LOOP:
        case EXCEPTION_HANDLER:
        case ASYNC_COMPREHENSION_GENERATOR:
            return 1;

        case FOR_LOOP:
            /* Pop the iterator */
            if (preserve_tos) {
                ADDOP(c, ROT_TWO);
            }
            ADDOP(c, POP_TOP);
            return 1;

        case TRY_EXCEPT:
            ADDOP(c, POP_BLOCK);
            return 1;

        case FINALLY_TRY:
            /* This POP_BLOCK gets the line number of the unwinding statement */
            ADDOP(c, POP_BLOCK);
            if (preserve_tos) {
                if (!compiler_push_fblock(c, POP_VALUE, NULL, NULL, NULL)) {
                    return 0;
                }
            }
            /* Emit the finally block */
            VISIT_SEQ(c, stmt, info->fb_datum);
            if (preserve_tos) {
                compiler_pop_fblock(c, POP_VALUE, NULL);
            }
            /* The finally block should appear to execute after the
             * statement causing the unwinding, so make the unwinding
             * instruction artificial */
            c->u->u_lineno = -1;
            return 1;

        case FINALLY_END:
            if (preserve_tos) {
                ADDOP(c, ROT_FOUR);
            }
            ADDOP(c, POP_TOP);
            ADDOP(c, POP_TOP);
            ADDOP(c, POP_TOP);
            if (preserve_tos) {
                ADDOP(c, ROT_FOUR);
            }
            ADDOP(c, POP_EXCEPT);
            return 1;

        case WITH:
        case ASYNC_WITH:
            SET_LOC(c, (stmt_ty)info->fb_datum);
            ADDOP(c, POP_BLOCK);
            if (preserve_tos) {
                ADDOP(c, ROT_TWO);
            }
            if(!compiler_call_exit_with_nones(c)) {
                return 0;
            }
            if (info->fb_type == ASYNC_WITH) {
                ADDOP(c, GET_AWAITABLE);
                ADDOP_LOAD_CONST(c, Py_None);
                ADDOP(c, YIELD_FROM);
            }
            ADDOP(c, POP_TOP);
            /* The exit block should appear to execute after the
             * statement causing the unwinding, so make the unwinding
             * instruction artificial */
            c->u->u_lineno = -1;
            return 1;

        case HANDLER_CLEANUP:
            if (info->fb_datum) {
                ADDOP(c, POP_BLOCK);
            }
            if (preserve_tos) {
                ADDOP(c, ROT_FOUR);
            }
            ADDOP(c, POP_EXCEPT);
            if (info->fb_datum) {
                ADDOP_LOAD_CONST(c, Py_None);
                compiler_nameop(c, info->fb_datum, Store);
                compiler_nameop(c, info->fb_datum, Del);
            }
            return 1;

        case POP_VALUE:
            if (preserve_tos) {
                ADDOP(c, ROT_TWO);
            }
            ADDOP(c, POP_TOP);
            return 1;
    }
    Py_UNREACHABLE();
}

これは、frame blockにはforwhileのほかに、try, withなどいろいろなものが入っているので、それぞれに対して別々の処理を行なっている。今回私たちが実装するのはbreakの挙動に関するものなので、forなどのframe block自体をいじる必要はなく、ここは変更を加える必要はないと判断した。

compile.cの変更

これからcompile.cに変更、追加をしていく。実装の方向性は、

  • 例えばbreak 3のような形で、抜け出したいループの数を受け取る(この場合は3つのループを抜ける)
  • その引数の数だけcompiler_unwind_fblock_stackと同様の処理を実行する
  • 引数が0の場合は、全てのループを抜ける
  • 引数がない(breakのみ)の場合は、通常のbreakとして動作する

といったイメージである。まずはcompiler_unwind_fblock_stackを参考にして作成したcompiler_unwind_fblock_stack_countを次に示す。 compiler_unwind_fblock_stackのすぐ下に書き加えれば良い。(compiler_unwind_fblock_stackは必要なので、手を加えてはならない)

static int
compiler_unwind_fblock_stack_count(struct compiler *c, int count, struct fblockinfo **loop) {
    if (c->u->u_nfblocks == 0 || count <= 0) {
        return 1;
    }

    struct fblockinfo *top = &c->u->u_fblock[c->u->u_nfblocks-1];
    if (loop != NULL && (top->fb_type == WHILE_LOOP || top->fb_type == FOR_LOOP)) {
        count--;
        if (count <= 0){
            *loop = top;
            return 1;
        }
    }
    struct fblockinfo copy = *top;
    c->u->u_nfblocks--;
    if (!compiler_unwind_fblock(c, &copy, 0)) {
        return 0;
    }
    if (!compiler_unwind_fblock_stack_count(c, count, loop)) {
        return 0;
    }
    c->u->u_fblock[c->u->u_nfblocks] = copy;
    c->u->u_nfblocks++;
    return 1;
}

関数の内容について、compiler_unwind_fblock_stackとの違いを中心に説明する。

  • 引数がint preserve_tosが消えint countを追加

これは、breakを実行する際にはpreserve_tosの値が常に0であったので、わざわざ引数にする必要はないと判断したため削除した。countは「ループを抜ける数」を表す引数である。

  • 最初のif文の条件に|| count<= 0を追加

これは、元々あったc->u->u_nfblocks == 0が「そもそもループが存在しない」ことを表しており、loopNULLのまま関数を終えることでcompiler_breakのエラー処理に誘導するためのif文である。よってcountが0以下(抜けたいループの数が0以下)も、エラー処理に誘導するためif分の条件に追加した。

  • 2つ目のif文の中で、countを減らし、0以下になったらlooptopを渡し抜ける

元々はtopが示すものがwhileforなどループを表すものであれば、すぐにlooptopを渡し関数を抜けていた。1つのループを抜けるならそれで良いが、複数ループを抜けるならloopに渡さずスルーする必要がある。そのため、toploopwhileならばcountを1減らし、countの値が0でなければスルー、0であればその時のtopが抜けたいループなので、loopに渡して関数を抜けるように変更した。

再帰にするための変更である。再帰にすることで、countを減らしながら目的のループを探すことができる。

以上の変更によって、compiler_unwind_fblock_stack_countを実行すれば、loopが抜け出したいループを示すようになる。

ここで、breakの引数が0の場合は全てのループを抜ける処理にしたい。そのためのcompiler_unwind_fblock_stack_allを別に作る。それを以下に示す。

static int
compiler_unwind_fblock_stack_all(struct compiler *c, struct fblockinfo **loop) {
    if (c->u->u_nfblocks == 0) {
        return 1;
    }
    int count = 0;
    for (int i = 0; i < (c->u->u_nfblocks); ++i){
        if (c->u->u_fblock[i].fb_type == WHILE_LOOP || c->u->u_fblock[i].fb_type == FOR_LOOP){
            count++;
        }
    }
    return compiler_unwind_fblock_stack_count(c, count, loop);
}

これは、c->u->u_fblockの中で、whileforの数を数え上げ、それをcompiler_unwind_fblock_stack_countcountとして渡している。こうすることで、全てのループを抜ける処理を可能としている。

つぎに、このcompiler_unwind_fblock_stack_countを用いたcompiler_breaknewを以下に示す。compiler_breakを消す必要はなく、その直後に書き加えれば良い。

static int
compiler_breaknew(struct compiler *c, stmt_ty s){
    struct fblockinfo *loop = NULL;
    ADDOP(c, NOP);
    int count = PyLong_AS_LONG(s->v.Breaknew.value->v.Constant.value);
    if (count == 0) {
        if (!compiler_unwind_fblock_stack_all(c, &loop)) {
            return 0;
        }
    } else {
        if (!compiler_unwind_fblock_stack_count(c, count, &loop)) {
            return 0;
        }
    }
    if (loop == NULL) {
        return compiler_error(c, "'break' not properly in loop");
    }
    if (!compiler_unwind_fblock(c, loop, 0)) {
        return 0;
    }
    ADDOP_JUMP(c, JUMP_ABSOLUTE, loop->fb_exit);
    NEXT_BLOCK(c);
    return 1;
}

関数の内容の説明を上から順にしていく。

  • int count = PyLong_AS_LONG(s->v.Breaknew.value->v.Constant.value);の追加

これは、s->v.Breaknew.value->v.Constant.valueが、例えばbreak 3とした時の3のような引数を表しており、PyLong_AS_LONGで特殊な形の整数に変換している。要するにbreakの引数をcountとして受け取っている。

  • countの値による処理の違い

countが0の時は、全てのループを抜ける処理をするため、compiler_unwind_fblock_stack_allを呼び足している。0でない時は、compiler_unwind_fblock_stack_countを呼び出して、指定した回数だけループを抜けるようにする。

  • 以上の処理の結果、loop == NULLのままの場合のエラー処理

compile_breakの時は、「ループが存在しない」場合にこのエラーを用いたため、"'break' outside loop"というエラー文であったが、compile_breaknewの場合は、「breakの引数が適切でない(負、ループの数より多いなど)」の場合にもこのエラーを用いることになるので、より広い意味を表すように"'break' not properly in loop"という表現にしている。

以降はcompiler_breakと同じ処理である。

最後に、compiler_visit_stmt内のcase Break_kindの後に以下のcase Breaknew_kindを追加する。わかりやすくするため、case Break_kindの部分も書いておく。(上にあげた変更を行なっていれば、おそらく3638行あたりに追加することになる)

    case Break_kind:
        return compiler_break(c);
    case Breaknew_kind:
        return compiler_breaknew(c, s);

compiler_breaknewには引数がcだけでなくsもあることに気をつける。

以上で、compile.cに関する変更が完了した。