Python/AST作成を読む

PyAST_FromNodeObject (Python/ast.c)
ast_for_stmt
ast_for_expr
ast_for_atom
ast_for_itercomp
ast_for_trailer
comparison(ast_for_expr)
ast_for_binop
最終結果

PyAST_FromNodeObject (Python/ast.c) †

スクリプトをノードにできたので次に進みます。Rubyだとこの後バイトコードに変換していましたがPythonはノードをさらにASTというものに変換するようです。その処理は見出しに書いたようにPython/ast.cに書かれています。

AST変換のトップレベル関数であるPyAST_FromNodeObjectではノードがファイルを読んだものなのか、evalなのか、シェルで打ち込んだものなのかで場合分けしていますが基本的な流れは同じようです。今回のケースについて考えていると、

 single_input
   simple_stmt
     small_stmt
       expr_stmt
         （以下略）

以下のコードが実行されることがわかります。

 
-
-
!
-
 
 
 
-
|
|
!
-
-
!
|
!
|

case single_input:
    if (TYPE(CHILD(n, 0)) == NEWLINE) {
        // こっちじゃない
    }
    else {
        n = CHILD(n, 0);
        num = num_stmts(n);
        stmts = _Py_asdl_seq_new(num, arena);
        if (num == 1) {
            s = ast_for_stmt(&c, n);
            asdl_seq_SET(stmts, 0, s);
        }
        else {
            // こっちじゃない
        }
        res = Interactive(stmts, arena);
    }
    break;

simple_stmtを引数にしてast_for_stmtが呼び出されます。

↑

ast_for_stmt †

ここからはノードに対応するast_*関数を使って変換が行われていきます。今回の場合、

 
 
-
-
|
|
!
-
|
|
!
-
|
-
|
!
-
|
|

static stmt_ty
ast_for_stmt(struct compiling *c, const node *n)
{
    if (TYPE(n) == stmt) {
        assert(NCH(n) == 1);
        n = CHILD(n, 0);
    }
    if (TYPE(n) == simple_stmt) {
        assert(num_stmts(n) == 1);
        n = CHILD(n, 0);
    }
    if (TYPE(n) == small_stmt) {
        n = CHILD(n, 0);
        /* small_stmt: expr_stmt | del_stmt | pass_stmt | flow_stmt
                  | import_stmt | global_stmt | nonlocal_stmt | assert_stmt
        */
        switch (TYPE(n)) {
            case expr_stmt:
                return ast_for_expr_stmt(c, n);

と、ast_for_expr_stmtに処理が回されます。なお、

simple_stmtなのでCHILD取り出す→small_stmt
small_stmtなのでCHILD取り出す→expr_stmt

と徐々にnが指すものが変わっていっているので注意してください。

↑

ast_for_expr †

関数はast_for_expr_stmt、ast_for_testlist、ast_for_exprと進んでいきます。ast_for_exprは少し長めでexprが子ノード1つだけの場合にどんどん子ノードに進んでいきます。

ここまでの知識を使って前回構築したノードをもう少しシンプルにしてみましょう。今回の場合、n * n、○ > 10以外の部分以外は全部子ノードが1つです。

 single_input
   expr_stmt
     power
       atom_expr
         atom
           testlist_comp
             power
               atom_expr
                 atom
                   NAME(n)
             comp_for
               exprlist
                 power
                   atom_expr
                     atom
                       NAME(n)
               power
                 atom_expr
                   atom
                     NAME(range)
                   trailer
                     arglist
                       argument
                         power
                           atom_expr
                             atom
                               NUMBER(10)
               comp_iter
                 comp_if
                   comparison
                     term
                       power
                         atom_expr
                           atom
                             NAME(n)
                       *
                       power
                         atom_expr
                           atom
                             NAME(n)
                     comp_op
                       >
                     power
                       atom_expr
                         atom
                           NUMBER(10)

だいぶシンプルになりました。多分ここもシンプルになるというところもありますがいったん先に進んでみましょう。comparisonやtermについては後で見ます。

↑

ast_for_atom †

処理はast_for_power、ast_for_atom_expr、ast_for_atomと進んでいきます。atom_exprはメソッド呼び出しの処理をしていますがそれは後で見ます。消してもいい（子ノードが1つの）power、atom_expr、およびatomを削除すると、

 single_input
   expr_stmt
     testlist_comp
       NAME(n)
       comp_for
         exprlist
           NAME(n)
         atom_expr
           NAME(range)
           trailer
             arglist
               argument
                 NUMBER(10)
         comp_iter
           comp_if
             comparison
               term
                 NAME(n)
                 *
                 NAME(n)
               comp_op
                 >
               NUMBER(10)

となります。一画面に収まるようになりました。

なお、NAMEの場合、

-
|
|
-
!
|
|
!

case NAME: {
    PyObject *name;
    const char *s = STR(ch);
    // None, True, Falseの処理
    name = new_identifier(s, c);
    /* All names start in Load context, but may later be changed. */
    return Name(name, Load, LINENO(n), n->n_col_offset, c->c_arena);
}

とNameが返されています。第二引数のコンテキストというものが今後ポイントになってきます。

さて、実はast_for_atomを見ていると'['などもノードの子として格納されていることがわかったのですがそれをノードに書くとまた長くなるのでここでは書かないことにします。ともかく今回の場合はast_for_listcompに処理が進みます。

↑

ast_for_itercomp †

ast_for_listcompはast_for_itercompを呼び出すだけです。エラー処理とかを削ったast_for_itercompは以下のような感じ。

 
 
-
-
!
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
!

static expr_ty
ast_for_itercomp(struct compiling *c, const node *n, int type)
{
    /* testlist_comp: (test|star_expr)
     *                ( comp_for | (',' (test|star_expr))* [','] ) */
    expr_ty elt;
    asdl_seq *comps;
    node *ch;
 
    ch = CHILD(n, 0);
    elt = ast_for_expr(c, ch);
 
    comps = ast_for_comprehension(c, CHILD(n, 1));
 
    if (type == COMP_GENEXP)
        return GeneratorExp(elt, comps, LINENO(n), n->n_col_offset, c->c_arena);
    else if (type == COMP_LISTCOMP)
        return ListComp(elt, comps, LINENO(n), n->n_col_offset, c->c_arena);
    else if (type == COMP_SETCOMP)
        return SetComp(elt, comps, LINENO(n), n->n_col_offset, c->c_arena);
}

子ノードの1つ目に対してast_for_exprが呼びだされています。今回の場合は単純に「n」なのでast_for_atomまで行ってNameが返されます。

その後、ast_for_comprehensionが呼ばれています。この部分は名前通り内包表記、つまり今回の肝です。

ast_for_comprephensionはforやifが何回も書けるのに対応するために長くなっていますがやってることはそんなに難しくありません。エラー処理省いて今回通るとこだけ抜き出すと、

 
 
-
|
|
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
-
|
|
|
|
|
|
-
|
|
|
!
|
!
|
!
|
!

static asdl_seq *
ast_for_comprehension(struct compiling *c, const node *n)
{
    int i, n_fors;
    asdl_seq *comps;
 
    n_fors = count_comp_fors(c, n);
    comps = _Py_asdl_seq_new(n_fors, c->c_arena);
    for (i = 0; i < n_fors; i++) {
        comprehension_ty comp;
        asdl_seq *t;
        expr_ty expression, first;
        node *for_ch;
 
        for_ch = CHILD(n, 1);
        t = ast_for_exprlist(c, for_ch, Store);
        expression = ast_for_expr(c, CHILD(n, 3));
 
        first = (expr_ty)asdl_seq_GET(t, 0);
        if (NCH(for_ch) == 1)
            comp = comprehension(first, expression, NULL, c->c_arena);
 
        if (NCH(n) == 5) {
            int j, n_ifs;
            asdl_seq *ifs;
 
            n = CHILD(n, 4);
            n_ifs = count_comp_ifs(c, n);
            ifs = _Py_asdl_seq_new(n_ifs, c->c_arena);
            for (j = 0; j < n_ifs; j++) {
                n = CHILD(n, 0);
                expression = ast_for_expr(c, CHILD(n, 1));
                asdl_seq_SET(ifs, j, expression);
            }
            comp->ifs = ifs;
        }
        asdl_seq_SET(comps, i, comp);
    }
    return comps;
}

n_forsもn_ifsも1です。というわけでforの直後のexprlist、inの直後のexpr、ifの部分のexprが処理されます。

exprlistは名前の通り、exprをリスト処理しています。ここではコンテキストとしてStoreが設定されています。for n inなのでinで指定したものをひとつずつnにストアしていくという予想ができます。

↑

ast_for_trailer †

次、inの後のexpr、具体的にはrange(10)、関数呼び出しです。ノードで言うと以下の部分です。

 atom_expr
   NAME(range)
   trailer
     arglist
       argument
         NUMBER(10)

ast_for_atom_exprに来た時に今度はast_for_trailerが呼び出されます。ast_for_trailerでは関数呼び出し、配列参照、属性参照が処理されます。今回は関数呼び出しなので、

 
-
-
|
|
!
|
-
|
|
|
|
|
!
!

ast_for_trailer(struct compiling *c, const node *n, expr_ty left_expr)
{
    /* trailer: '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME
       subscriptlist: subscript (',' subscript)* [',']
       subscript: '.' '.' '.' | test | [test] ':' [test] [sliceop]
     */
    REQ(n, trailer);
    if (TYPE(CHILD(n, 0)) == LPAR) {
        if (NCH(n) == 2)
            return Call(left_expr, NULL, NULL, LINENO(n),
                        n->n_col_offset, c->c_arena);
        else
            return ast_for_call(c, CHILD(n, 1), left_expr);
    }
}

が処理されます。なお、NCH(n)が2になるのは引数なしの場合なので今回はast_for_callに続きます。

ast_for_callも結構長いです。まあ関数呼び出しはプログラムの肝ですからね。そういえばオブジェクトのメソッド呼び出しってどうなってるんだと気になりましたが、ASTの時点では属性（実態は関数）の関数呼び出しって階層構造になっているなってるみたいですね。どう実行されるか気になりますが今回は深く追いかけないことにします。

で、ast_for_call。arglistに普通の引数なのかキーワード引数なのかなどに応じて処理が行われます。今回は単純に普通の引数1個だけです。

↑

comparison(ast_for_expr) †

これで「in range(10)」まで終わったので後はifの部分、「if n * n > 10」です。ノードだと以下の感じ、

 comparison
   term
     NAME(n)
     *
     NAME(n)
   comp_op
     >
   NUMBER(10)

comparisonの処理がされているのはast_for_exprです。

 
 
 
 
 
 
-
|
|
|
|
|
|
!
 
-
|
!

expr_ty expression;
asdl_int_seq *ops;
asdl_seq *cmps;
 
ops = _Py_asdl_int_seq_new(NCH(n) / 2, c->c_arena);
cmps = _Py_asdl_seq_new(NCH(n) / 2, c->c_arena);
for (i = 1; i < NCH(n); i += 2) {
    cmpop_ty newoperator;
 
    newoperator = ast_for_comp_op(c, CHILD(n, i));
    expression = ast_for_expr(c, CHILD(n, i + 1));
    asdl_seq_SET(ops, i / 2, newoperator);
    asdl_seq_SET(cmps, i / 2, expression);
}
expression = ast_for_expr(c, CHILD(n, 0));
if (!expression) {
    return NULL;
}
 
return Compare(expression, ops, cmps, LINENO(n),
               n->n_col_offset, c->c_arena);

なんでループしているのかと思ったらそういえばPythonは「0 < x < 10」みたいなコードが書けるのでした。注意としては、先頭の子ノードが最後にast_for_exprにかけられる点ですね。

↑

ast_for_binop †

というわけで先頭の子ノード、termです。ast_for_binopで処理されます。まあ特に特筆することはないでしょう。

↑

最終結果 †

以上、ノード（CSTというらしいです）がASTに変換される様子を見てきました。ASTというのはコードを見てる途中にあったInteractiveやListCompなどです。それらを書き出すと以下のようになります。

 Interactive
   Expr
     ListComp
       Name(n) Load
       Comprephension
         Name(n) Store
         Call
           Name(Range) Load
             Num(10)
         Compare
           BinOp
             Mult
             Name(n) Load
             Name(n) Load
           Gt
           Num(10)

非常にシンプルになりました。実際には単一の値ではなくシーケンス（要素数1）の部分もありますがまあいいでしょう。