Python/シンボルテーブル作成を読む
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[Pythonを読む]]
#contents
*PyAST_CompileObject (Python/compile.c) [#wbc46e7b]
ASTができたので続いてバイトコード生成です。トップレベルの...
#code(C){{
/*
* This file compiles an abstract syntax tree (AST) into ...
*
* The primary entry point is PyAST_Compile(), which retu...
* PyCodeObject. The compiler makes several passes to bu...
* 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...
* 4. Assemble the basic blocks into final code. See a...
* 5. Optimize the byte code (peephole optimizations). ...
*/
}}
というわけでまずシンボルテーブルを作るようです、
*PySymtable_BuildObject (Python/symtable.c) [#m2762852]
PySymtable_BuildObjectを見ていくとまずtopを引数にsymtable...
symtable_enter_blockを見てみます。
#code(C){{
static int
symtable_enter_block(struct symtable *st, identifier name...
void *ast, int lineno, int col_offset)
{
PySTEntryObject *prev = NULL, *ste;
ste = ste_new(st, name, block, ast, lineno, col_offse...
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_...
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 *...
return 0;
}
}
return 1;
}
}}
STEntryという名前にだまされ気味ですが、このオブジェクトは...
#code(C){{
static PySTEntryObject *
ste_new(struct symtable *st, identifier name, _Py_block_t...
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 ...
return ste;
}
}}
PyObjectとか出てきてますが深くは気にしません。とりあえず...
**symtable_visit_stmt [#oa193cb0]
さて、というわけでsymtableの仕組みがわかったので次に実際...
対象としている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なので以下のコードが実行されます。
#code(C){{
case Expr_kind:
VISIT(st, expr, s->v.Expr.value);
break;
}}
なんとなくわかりますが一応VISITの定義を見ると、
#code(C){{
#define VISIT(ST, TYPE, V) \
if (!symtable_visit_ ## TYPE((ST), (V))) \
VISIT_QUIT((ST), 0);
}}
というわけで、symtable_visit_exprに続く。symtable_visit_e...
#code(C){{
static int
symtable_handle_comprehension(struct symtable *st, expr_t...
identifier scope_name, asdl...
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(generato...
/* 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, FunctionBlo...
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)、i...
**symtable_add_def [#md462267]
さて、というわけで内包表記の各要素についてVISITされ最終的...
#code(C){{
case Name_kind:
if (!symtable_add_def(st, e->v.Name.id, e->v.Name.ctx...
VISIT_QUIT(st, 0);
}}
コンテキストがLoadの場合はUSEを設定、それ以外（Storeなど...
symtable_add_defは以下のような感じでシンボルテーブルに名...
#code(C){{
static int
symtable_add_def(struct symtable *st, PyObject *name, int...
{
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;
}
}}
最終的にシンボルテーブルには以下のようにブロックが登録さ...
-top
--range USE
-listcomp
--_[0] DEF_LOCAL
--n USE, DEF_LOCAL
**symtable_analyze [#i19595af]
シンボルテーブルができたら次にsymtable_analyzeが呼ばれて...
#code(C){{
/* Analyze raw symbol information to determine scope of e...
The next several functions are helpers for symtable_an...
which determines whether a name is local, global, or f...
it determines which local variables are cell variables...
bindings that are used for free variables in enclosed ...
*/
}}
freeというのがいまいちわかりません。コードを見ていくこと...
#code(C){{
static int
analyze_block(PySTEntryObject *ste, PyObject *bound, PyOb...
PyObject *global)
{
PyObject *name, *v, *local = NULL, *scopes = NULL, *n...
PyObject *newglobal = NULL, *newfree = NULL, *allfree...
PyObject *temp;
int i, success = 0;
Py_ssize_t pos = 0;
local = PySet_New(NULL); /* collect new names bound ...
scopes = PyDict_New(); /* collect scopes defined for...
/* Allocate new global and bound variable dictionarie...
dictionaries hold the names visible in nested bloc...
ClassBlocks, the bound and global names are initia...
before analyzing names, because class bindings are...
visible in methods. For other blocks, they are in...
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...
goto error;
}
/* Populate global and bound sets to be passed to chi...
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 chi...
newbound, newglobal now contain the names visible in
nested blocks. The free variables in the children...
be collected in allfree.
*/
allfree = PySet_New(NULL);
for (i = 0; i < PyList_GET_SIZE(ste->ste_children); +...
PyObject *c = PyList_GET_ITEM(ste->ste_children, ...
PySTEntryObject* entry;
entry = (PySTEntryObject*)c;
if (!analyze_child_block(entry, newbound, newfree...
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 ...
if (ste->ste_type == FunctionBlock && !analyze_cells(...
goto error;
/* Records the results of the analysis in the symbol ...
if (!update_symbols(ste->ste_symbols, scopes, bound, ...
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 [#l33529eb]
まず、analyze_name。global指定されている場合の処理とかが...
#code(C){{
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なんてセットしているところないぞ？と思ったらIncl...
#code(C){{
#define DEF_BOUND (DEF_LOCAL | DEF_PARAM | DEF_IMPORT)
}}
というわけで内包表記内で定義されているnはlocalに設定され...
analyze_blockおよび上記のコメントを参考にするとboundは親...
#code(Python){{
a = [1, 2, 3]
[e * e for e in a]
}}
みたいに書くとaがfreeになるようです。
rangeはGLOBAL_IMPLICITになります。言語仕様を考えると当た...
analyze_child_blockでは子ブロック用にbound, free, global...
だいぶ長くなったのでいったんここまでで区切りとします。
終了行:
[[Pythonを読む]]
#contents
*PyAST_CompileObject (Python/compile.c) [#wbc46e7b]
ASTができたので続いてバイトコード生成です。トップレベルの...
#code(C){{
/*
* This file compiles an abstract syntax tree (AST) into ...
*
* The primary entry point is PyAST_Compile(), which retu...
* PyCodeObject. The compiler makes several passes to bu...
* 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...
* 4. Assemble the basic blocks into final code. See a...
* 5. Optimize the byte code (peephole optimizations). ...
*/
}}
というわけでまずシンボルテーブルを作るようです、
*PySymtable_BuildObject (Python/symtable.c) [#m2762852]
PySymtable_BuildObjectを見ていくとまずtopを引数にsymtable...
symtable_enter_blockを見てみます。
#code(C){{
static int
symtable_enter_block(struct symtable *st, identifier name...
void *ast, int lineno, int col_offset)
{
PySTEntryObject *prev = NULL, *ste;
ste = ste_new(st, name, block, ast, lineno, col_offse...
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_...
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 *...
return 0;
}
}
return 1;
}
}}
STEntryという名前にだまされ気味ですが、このオブジェクトは...
#code(C){{
static PySTEntryObject *
ste_new(struct symtable *st, identifier name, _Py_block_t...
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 ...
return ste;
}
}}
PyObjectとか出てきてますが深くは気にしません。とりあえず...
**symtable_visit_stmt [#oa193cb0]
さて、というわけでsymtableの仕組みがわかったので次に実際...
対象としている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なので以下のコードが実行されます。
#code(C){{
case Expr_kind:
VISIT(st, expr, s->v.Expr.value);
break;
}}
なんとなくわかりますが一応VISITの定義を見ると、
#code(C){{
#define VISIT(ST, TYPE, V) \
if (!symtable_visit_ ## TYPE((ST), (V))) \
VISIT_QUIT((ST), 0);
}}
というわけで、symtable_visit_exprに続く。symtable_visit_e...
#code(C){{
static int
symtable_handle_comprehension(struct symtable *st, expr_t...
identifier scope_name, asdl...
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(generato...
/* 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, FunctionBlo...
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)、i...
**symtable_add_def [#md462267]
さて、というわけで内包表記の各要素についてVISITされ最終的...
#code(C){{
case Name_kind:
if (!symtable_add_def(st, e->v.Name.id, e->v.Name.ctx...
VISIT_QUIT(st, 0);
}}
コンテキストがLoadの場合はUSEを設定、それ以外（Storeなど...
symtable_add_defは以下のような感じでシンボルテーブルに名...
#code(C){{
static int
symtable_add_def(struct symtable *st, PyObject *name, int...
{
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;
}
}}
最終的にシンボルテーブルには以下のようにブロックが登録さ...
-top
--range USE
-listcomp
--_[0] DEF_LOCAL
--n USE, DEF_LOCAL
**symtable_analyze [#i19595af]
シンボルテーブルができたら次にsymtable_analyzeが呼ばれて...
#code(C){{
/* Analyze raw symbol information to determine scope of e...
The next several functions are helpers for symtable_an...
which determines whether a name is local, global, or f...
it determines which local variables are cell variables...
bindings that are used for free variables in enclosed ...
*/
}}
freeというのがいまいちわかりません。コードを見ていくこと...
#code(C){{
static int
analyze_block(PySTEntryObject *ste, PyObject *bound, PyOb...
PyObject *global)
{
PyObject *name, *v, *local = NULL, *scopes = NULL, *n...
PyObject *newglobal = NULL, *newfree = NULL, *allfree...
PyObject *temp;
int i, success = 0;
Py_ssize_t pos = 0;
local = PySet_New(NULL); /* collect new names bound ...
scopes = PyDict_New(); /* collect scopes defined for...
/* Allocate new global and bound variable dictionarie...
dictionaries hold the names visible in nested bloc...
ClassBlocks, the bound and global names are initia...
before analyzing names, because class bindings are...
visible in methods. For other blocks, they are in...
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...
goto error;
}
/* Populate global and bound sets to be passed to chi...
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 chi...
newbound, newglobal now contain the names visible in
nested blocks. The free variables in the children...
be collected in allfree.
*/
allfree = PySet_New(NULL);
for (i = 0; i < PyList_GET_SIZE(ste->ste_children); +...
PyObject *c = PyList_GET_ITEM(ste->ste_children, ...
PySTEntryObject* entry;
entry = (PySTEntryObject*)c;
if (!analyze_child_block(entry, newbound, newfree...
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 ...
if (ste->ste_type == FunctionBlock && !analyze_cells(...
goto error;
/* Records the results of the analysis in the symbol ...
if (!update_symbols(ste->ste_symbols, scopes, bound, ...
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 [#l33529eb]
まず、analyze_name。global指定されている場合の処理とかが...
#code(C){{
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なんてセットしているところないぞ？と思ったらIncl...
#code(C){{
#define DEF_BOUND (DEF_LOCAL | DEF_PARAM | DEF_IMPORT)
}}
というわけで内包表記内で定義されているnはlocalに設定され...
analyze_blockおよび上記のコメントを参考にするとboundは親...
#code(Python){{
a = [1, 2, 3]
[e * e for e in a]
}}
みたいに書くとaがfreeになるようです。
rangeはGLOBAL_IMPLICITになります。言語仕様を考えると当た...
analyze_child_blockでは子ブロック用にbound, free, global...
だいぶ長くなったのでいったんここまでで区切りとします。
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
