Python/シンボルテーブル作成を読む

PyAST_CompileObject (Python/compile.c)
PySymtable_BuildObject (Python/symtable.c)

PyAST_CompileObject (Python/compile.c) †

ASTができたので続いてバイトコード生成です。トップレベルのPyAST_CompileObjectを眺めるとPySymtable_BuildObjectを呼び出した後にcompiler_modを呼び出しています。というかファイルの先頭にステップが書いてあるので見ていましょう。

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

/*
 * This file compiles an abstract syntax tree (AST) into Python bytecode.
 *
 * The primary entry point is PyAST_Compile(), which returns a
 * PyCodeObject.  The compiler makes several passes to build the code
 * object:
 *   1. Checks for future statements.  See future.c
 *   2. Builds a symbol table.  See symtable.c.
 *   3. Generate code for basic blocks.  See compiler_mod() in this file.
 *   4. Assemble the basic blocks into final code.  See assemble() in this file.
 *   5. Optimize the byte code (peephole optimizations).  See peephole.c
 */

というわけでまずシンボルテーブルを作るようです、

↑

PySymtable_BuildObject (Python/symtable.c) †

PySymtable_BuildObjectを見ていくとまずtopを引数にsymtable_enter_blockを読んでいます。topは名前通りトップレベルなのでしょう。下を見るとsymtable_exit_blockがあるのでブロックに入る前にenterしてブロックが終わったらexitしているようです（そのまんまですが）

symtable_enter_blockを見てみます。

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

static int
symtable_enter_block(struct symtable *st, identifier name, _Py_block_ty block,
                     void *ast, int lineno, int col_offset)
{
    PySTEntryObject *prev = NULL, *ste;
 
    ste = ste_new(st, name, block, ast, lineno, col_offset);
    if (ste == NULL)
        return 0;
    if (PyList_Append(st->st_stack, (PyObject *)ste) < 0) {
        Py_DECREF(ste);
        return 0;
    }
    prev = st->st_cur;
    /* The entry is owned by the stack. Borrow it for st_cur. */
    Py_DECREF(ste);
    st->st_cur = ste;
    if (block == ModuleBlock)
        st->st_global = st->st_cur->ste_symbols;
    if (prev) {
        if (PyList_Append(prev->ste_children, (PyObject *)ste) < 0) {
            return 0;
        }
    }
    return 1;
}

STEntryという名前にだまされ気味ですが、このオブジェクトはシンボルテーブルの1エントリではなく、あるブロックに存在する全変数を保持しています。ste_newを載せると長いので要点だけ抜き出すと、

 
 
 
-
|
|
|
|
|
|
|
|
|
!

static PySTEntryObject *
ste_new(struct symtable *st, identifier name, _Py_block_ty block,
        void *key, int lineno, int col_offset)
{
    PySTEntryObject *ste = NULL;
    PyObject *k = NULL;
 
    k = PyLong_FromVoidPtr(key);
    ste = PyObject_New(PySTEntryObject, &PySTEntry_Type);
    ste->ste_id = k; /* ste owns reference to k */
    ste->ste_symbols = PyDict_New();
    PyDict_SetItem(st->st_blocks, ste->ste_id, (PyObject *)ste);
    return ste;
}

PyObjectとか出てきてますが深くは気にしません。とりあえずシンボルテーブルにブロックが登録されているということだけ覚えておきます。

↑

symtable_visit_stmt †

さて、というわけでsymtableの仕組みがわかったので次に実際にシンボルテーブルにシンボルが登録されていく様子を見てきましょう。PySymtable_BuildObjectではsymtable_visit_stmtが呼び出されています。symtable_visit_stmtの中身はswitch文、今回は見ませんが関数定義やクラス定義でsymtable_enter_blockを呼んでおり新しいブロックを作成しています。

対象としているASTは以下。

 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)

Exprなので以下のコードが実行されます。

  1
  2
  3

case Expr_kind:
    VISIT(st, expr, s->v.Expr.value);
    break;

なんとなくわかりますが一応VISITの定義を見ると、

  1
  2
  3

#define VISIT(ST, TYPE, V) \
    if (!symtable_visit_ ## TYPE((ST), (V))) \
        VISIT_QUIT((ST), 0);

というわけで、symtable_visit_exprに続く。symtable_visit_exprもswitch文です。ListCompなのでsymtable_visit_listcompに進んで各種comprehensionを処理しているsymtable_handle_comprehensionへ。

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

static int
symtable_handle_comprehension(struct symtable *st, expr_ty e,
                              identifier scope_name, asdl_seq *generators,
                              expr_ty elt, expr_ty value)
{
    int is_generator = (e->kind == GeneratorExp_kind);
    int needs_tmp = !is_generator;
    comprehension_ty outermost = ((comprehension_ty)
                                    asdl_seq_GET(generators, 0));
    /* Outermost iterator is evaluated in current scope */
    VISIT(st, expr, outermost->iter);
    /* Create comprehension scope for the rest */
    if (!scope_name ||
        !symtable_enter_block(st, scope_name, FunctionBlock, (void *)e,
                              e->lineno, e->col_offset)) {
        return 0;
    }
    st->st_cur->ste_generator = is_generator;
    /* Outermost iter is received as an argument */
    if (!symtable_implicit_arg(st, 0)) {
        symtable_exit_block(st, (void *)e);
        return 0;
    }
    /* Allocate temporary name if needed */
    if (needs_tmp && !symtable_new_tmpname(st)) {
        symtable_exit_block(st, (void *)e);
        return 0;
    }
    VISIT(st, expr, outermost->target);
    VISIT_SEQ(st, expr, outermost->ifs);
    VISIT_SEQ_TAIL(st, comprehension, generators, 1);
    if (value)
        VISIT(st, expr, value);
    VISIT(st, expr, elt);
    return symtable_exit_block(st, (void *)e);
}

outermostはComprephensionでiterはCall、targetはName(n)、ifsはCompareです。また、eltもName(n)です（ListComp直下の方）。ここでポイントなのは内包表記はFunctionのブロックが新しく作られるということ、テンポラリな名前が割り当てられていることです。symtable_new_tmpnameを見るとわかりますがその名前は_[0]なようです。

↑

symtable_add_def †

さて、というわけで内包表記の各要素についてVISITされ最終的にsymtable_visit_exprでNameが処理されます。

  1
  2
  3

case Name_kind:
    if (!symtable_add_def(st, e->v.Name.id, e->v.Name.ctx == Load ? USE : DEF_LOCAL))
        VISIT_QUIT(st, 0);

コンテキストがLoadの場合はUSEを設定、それ以外（Storeなど）の場合はローカル変数として定義、と読み取れます。

symtable_add_defは以下のような感じでシンボルテーブルに名前が登録されます。

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

static int
symtable_add_def(struct symtable *st, PyObject *name, int flag)
{
    PyObject *o;
    PyObject *dict;
    long val;
    PyObject *mangled = _Py_Mangle(st->st_private, name);
 
    dict = st->st_cur->ste_symbols;
    if ((o = PyDict_GetItem(dict, mangled))) {
        val = PyLong_AS_LONG(o);
        val |= flag;
    } else
        val = flag;
    o = PyLong_FromLong(val);
    if (PyDict_SetItem(dict, mangled, o) < 0) {
        Py_DECREF(o);
        goto error;
    }
    Py_DECREF(o);
 
    Py_DECREF(mangled);
    return 1;
 
error:
    Py_DECREF(mangled);
    return 0;
}

最終的にシンボルテーブルには以下のようにブロックが登録されます。listcompはtopの子供になります。

top
- range USE
listcomp
- _[0] DEF_LOCAL
- n USE, DEF_LOCAL

↑

symtable_analyze †

シンボルテーブルができたら次にsymtable_analyzeが呼ばれています。symtable_analyzeで何をやっているかの説明は400行目ぐらい（3.5.1の場合）に書いてあります。

-
|
|
|
|
|
!

/* Analyze raw symbol information to determine scope of each name.
 
   The next several functions are helpers for symtable_analyze(),
   which determines whether a name is local, global, or free.  In addition,
   it determines which local variables are cell variables; they provide
   bindings that are used for free variables in enclosed blocks.
 */

freeというのがいまいちわかりません。コードを見ていくことにしましょう。symtable_analyzeはトップレベルのSTEntryに対してanalyze_blockを呼んでいるだけです。analze_blockは長いので要点だけ取り出すと、

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

static int
analyze_block(PySTEntryObject *ste, PyObject *bound, PyObject *free,
              PyObject *global)
{
    PyObject *name, *v, *local = NULL, *scopes = NULL, *newbound = NULL;
    PyObject *newglobal = NULL, *newfree = NULL, *allfree = NULL;
    PyObject *temp;
    int i, success = 0;
    Py_ssize_t pos = 0;
 
    local = PySet_New(NULL);  /* collect new names bound in block */
    scopes = PyDict_New();  /* collect scopes defined for each name */
 
    /* Allocate new global and bound variable dictionaries.  These
       dictionaries hold the names visible in nested blocks.  For
       ClassBlocks, the bound and global names are initialized
       before analyzing names, because class bindings aren't
       visible in methods.  For other blocks, they are initialized
       after names are analyzed.
     */
    newglobal = PySet_New(NULL);
    newfree = PySet_New(NULL);
    newbound = PySet_New(NULL);
 
    while (PyDict_Next(ste->ste_symbols, &pos, &name, &v)) {
        long flags = PyLong_AS_LONG(v);
        if (!analyze_name(ste, scopes, name, flags, bound, local, free, global))
            goto error;
    }
 
    /* Populate global and bound sets to be passed to children. */
    if (ste->ste_type != ClassBlock) {
        /* Add function locals to bound set */
        if (ste->ste_type == FunctionBlock) {
            temp = PyNumber_InPlaceOr(newbound, local);
            Py_DECREF(temp);
        }
        /* Pass down previously bound symbols */
        if (bound) {
            temp = PyNumber_InPlaceOr(newbound, bound);
            Py_DECREF(temp);
        }
        /* Pass down known globals */
        temp = PyNumber_InPlaceOr(newglobal, global);
        Py_DECREF(temp);
    }
 
    /* Recursively call analyze_child_block() on each child block.
 
       newbound, newglobal now contain the names visible in
       nested blocks.  The free variables in the children will
       be collected in allfree.
    */
    allfree = PySet_New(NULL);
    for (i = 0; i < PyList_GET_SIZE(ste->ste_children); ++i) {
        PyObject *c = PyList_GET_ITEM(ste->ste_children, i);
        PySTEntryObject* entry;
        entry = (PySTEntryObject*)c;
        if (!analyze_child_block(entry, newbound, newfree, newglobal, allfree))
            goto error;
        /* Check if any children have free variables */
        if (entry->ste_free || entry->ste_child_free)
            ste->ste_child_free = 1;
    }
 
    temp = PyNumber_InPlaceOr(newfree, allfree);
    Py_DECREF(temp);
 
    /* Check if any local variables must be converted to cell variables */
    if (ste->ste_type == FunctionBlock && !analyze_cells(scopes, newfree))
        goto error;
    /* Records the results of the analysis in the symbol table entry */
    if (!update_symbols(ste->ste_symbols, scopes, bound, newfree,
                        ste->ste_type == ClassBlock))
        goto error;
 
    temp = PyNumber_InPlaceOr(free, newfree);
    Py_DECREF(temp);
    success = 1;
 error:
    Py_XDECREF(scopes);
    Py_XDECREF(local);
    Py_XDECREF(newbound);
    Py_XDECREF(newglobal);
    Py_XDECREF(newfree);
    Py_XDECREF(allfree);
    return success;
}

削っても長いですが、

ブロックにあるシンボルを収集して(analyze_name)
子シンボルにその情報を渡して解析(analyze_child_block)
最後に情報を更新(update_symbols)

ということをやっているようです。まだよくわからないので先に進みましょう。

↑

analyze_name †

まず、analyze_name。global指定されている場合の処理とかが行われていますがサクッと無視して、

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

if (flags & DEF_BOUND) {
    SET_SCOPE(scopes, name, LOCAL);
    if (PySet_Add(local, name) < 0)
        return 0;
    if (PySet_Discard(global, name) < 0)
        return 0;
    return 1;
}
/* If an enclosing block has a binding for this name, it
   is a free variable rather than a global variable.
   Note that having a non-NULL bound implies that the block
   is nested.
*/
if (bound && PySet_Contains(bound, name)) {
    SET_SCOPE(scopes, name, FREE);
    ste->ste_free = 1;
    return PySet_Add(free, name) >= 0;
}
SET_SCOPE(scopes, name, GLOBAL_IMPLICIT);

DEF_BOUNDなんてセットしているところないぞ？と思ったらInclude/symtable.hで次のように定義されていました。

#define DEF_BOUND (DEF_LOCAL | DEF_PARAM | DEF_IMPORT)

というわけで内包表記内で定義されているnはlocalに設定されます。

analyze_blockおよび上記のコメントを参考にするとboundは親ブロックのローカル変数集合です。親ブロックの変数を参照しているとfreeという集合に入れられるようです。今回はありませんが、

  1
  2

a = [1, 2, 3]
[e * e for e in a]

みたいに書くとaがfreeになるようです。

rangeはGLOBAL_IMPLICITになります。言語仕様を考えると当たり前ですがこれらのことが行われています。

analyze_child_blockでは子ブロック用にbound, free, globalを作ってanalyze_blockを再帰呼び出し、update_symbolsは判明したスコープを各シンボル情報を格納したdictに設定しています。

だいぶ長くなったのでいったんここまでで区切りとします。