# 3. Compiling Python Source Code 生成 code object 过程中 4 个主要的数据结构。尽管一般并不认为 Python 是一门编译性的语言，但实际上在代码执行前 Python 源码仍会被编译成可以被 python 虚拟机执行的字节码(byte code)。python 的编译过程非常直接，并不涉及到很多复杂的步骤。一个完整的 python 程序编译过程有以下几个步骤： 1. 将源代码 parsing 成一个 parse tree。 2. 将 parse tree 转化为 AST（抽象语法树， abstract syntax tree）。 3. 生成符号表（symbol table）。 4. 从 AST 生成 code object，这一步包含： 1. 将 AST 转化为一个 flow control graph。 2. 从 control flow graph 产生 code object。 其中将从源码到 AST 是一个标准的过程，python 这里并没有什么特别的，所以本书会把关注点更多放在 symbol tables 以及 code objects 的生成过程上。如果你对于 Parsing 的详细原理比较感兴趣，推荐阅读经典的[《龙书》（dragon book）](https://www.amazon.co.uk/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886)。 ### 3.1 **从源码到 parse tree** 按照 Dragon book 中的描述 python 的 parser 属于一种 [LL(1)](https://en.wikipedia.org/wiki/LL_parser) parser。CPython 目录下的 [Grammar/Grammer](https://github.com/python/cpython/blob/3.5/Grammar/Grammar) 文件中包含了 Python 语言文法的 [EBNF](https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form)（Extended Backus–Naur Form，扩展巴科斯范式）： {% code title="代码清单3.0: Python BNF 文法（部分）" %} ``` ... stmt: simple_stmt | compound_stmt simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | nonlocal_stmt | assert_stmt) expr_stmt: testlist_star_expr (augassign (yield_expr|testlist) | ('=' (yield_expr|testlist_star_expr))*) testlist_star_expr: (test|star_expr) (',' (test|star_expr))* [','] augassign: ('+=' | '-=' | '*=' | '@=' | '/=' | '%=' | '&=' | '|=' | '^=' | '<<=' | '>>=' | '**=' | '//=') del_stmt: 'del' exprlist pass_stmt: 'pass' flow_stmt: break_stmt | continue_stmt | return_stmt | raise_stmt | yield_stmt break_stmt: 'break' continue_stmt: 'continue' return_stmt: 'return' [testlist] yield_stmt: yield_expr raise_stmt: 'raise' [test ['from' test]] import_stmt: import_name | import_from import_name: 'import' dotted_as_names import_from: ('from' (('.' | '...')* dotted_name | ('.' | '...')+) 'import' ('*' | '(' import_as_names ')' | import_as_names)) import_as_name: NAME ['as' NAME] ... ``` {% endcode %} 每次从命令行中运行一个 python 模块的时候，[PyParser\_ParseFileObject](https://github.com/python/cpython/blob/3.7/Parser/parsetok.c#L116) 函数会启动对这个模块的 parsing过程，它会调用 tokenization 函数 [PyTokenizer\_FromFile](https://github.com/python/cpython/blob/3.7/Parser/tokenizer.c#L860) ，它接受模块的文件名作为参数，将模块文件的内容分解为一个个合法的 python tokens 或者发现语法错误时进行报错。 ### 3.2 **Python tokens** Python 源码可以看作是一段由 token 组成的序列，比如说 return 就是一个 keyword token，字面量 -2 是一个数值字面量 token 等等。Parsing python 源码的第一步就是将源码分割为一个个的 token。Python 中存在以下几种 token： 1. identifiers：由程序员定义的“名字”，包括函数名、变量名、类名等等。它们必须符合 python 文档中指定的[规范](https://docs.python.org/3.5/reference/lexical_analysis.html#identifiers)。 2. operators：一些特殊的符号比如 `+`, `*` 能够对值进行运算产生结果。 3. delimiters：这类符号用来给表达式分组、提供标点、赋值操作，包括 `(, )`, `{,}`, `=`, `*=` 等。 4. literals：字面量，这类符号用于提供一些类型的常量。比如字符串、bytes 类型的字面量：`"Fred"`, `b"Fred"` 、数值类型的字面量 2 、浮点类型字面量 1e100 、虚数字面量 10j 。 5. comments：以 # 开头的字符串字面量，用户代码注释。comments 总是位于一个 physical line 的结尾。（译注：关于什么是 physical line 与 logical line 可以参考[这里](https://stackoverflow.com/questions/31572589/difference-between-logical-line-and-physical-line-in-python)） 6. NEWLINE：用于指示一行（logical line）的结束。 7. INDENT 与 DEDENT：表示一组复合语句（compound statements）的缩进层级（identation levels）。 一组 tokens 通过一个 **NEWLINE** token 被分割，组成一个 logical line，因而我们可以说一个 python 程序由一系列被 **NEWLINE** token 分割的 logical line 所组成。这些 logical line 可以映射到 python 语句（statements）。每一个 logical line 又由一系列 physical lines 所组成，physical line 的结尾是一个换行符（end-of-line）。多个 physical line 可以被连接在一起，连接可能是隐式的，比如在括号中的时候（包括 (), \[], {} 三种），也可能是显式的，也就是在行尾使用一个反斜杠 \。（译注：原文中说的是 logical line 可以被连接，这里似乎存在错误，想表达的应该是 phycial lines 被连接为 logical line）。复合语句可以跨过多个 physical line，就像图1.3.2 中所展示的那样。缩进对于 python 语句的分组非常重要，python grammar 中有一条规则用于对它进行描述：`suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT` ，因而 python tokenizer 的一项主要任务就是生成 INDENT 和 DEDENT 到 parse tree。Tokenizer 使用一个栈来保持对缩进的跟踪，INDENT 与 DEDENT token 生成算法的伪代码如下： {% code title="代码清代3.1: Python 用来生成 INDENT 与 DEDENT token 的算法伪代码" %} ``` 使用 0 初始化 indent 栈 for 每一个 logical line: if (当前行的缩进级别 > 栈顶的级别): push(当前缩进级别) 生成一个 INDENT token if (当前行的缩进级别 < 栈顶的级别): if (栈中不存在一个缩进级别 == 当前缩进级别): 报告一个错误 for 栈顶的每一个 != 当前行缩进级的值: 移除这个值 生成一个 DEDENT token tokenize(当前行) 对每一个栈上的值（除了0）生成 DEDENT token ``` {% endcode %} CPython 的实现中 [PyTokenizer\_FromFile](https://github.com/python/cpython/blob/3.7/Parser/tokenizer.c#L860) 函数会按照从左到右，从上到下的对 python 源码文件进行扫描并进行 tokenize。空格字符除了终止符被用来分隔开 token，但这不是必须的。如果其中存在歧义，则按照从右到左合法的可能的最长字符串来理解。比如说 2+2 ，是一个字面量 2，一个 operator +，另一个字面量 2。 {% hint style="info" %} **补充知识：调用 python tokenize** 在 python 中提供了 tokenize 的接口（标准模块函数 [tokenize.tokenize](https://docs.python.org/3/library/tokenize.html#tokenize.tokenize)）可以使用它对 python 源代码进行 tokenize，它接受一个 ByteIO.readline 的 callable 对象返回一个 tokens 的 generator，对这个 generator 进行迭代就能得到被解析模块的 tokens 序列，比如： {% endhint %} ```python >>> from tokenize import tokenize >>> f = open("./test.py", 'rb') # test.py 的内容只有一行 print("hello") >>> for t in tokenize(f.readline): ... print(t) ... TokenInfo(type=59 (ENCODING), string='utf-8', start=(0, 0), end=(0, 0), line='') TokenInfo(type=1 (NAME), string='print', start=(1, 0), end=(1, 5), line='print("hello")') TokenInfo(type=53 (OP), string='(', start=(1, 5), end=(1, 6), line='print("hello")') TokenInfo(type=3 (STRING), string='"hello"', start=(1, 6), end=(1, 13), line='print("hello")') TokenInfo(type=53 (OP), string=')', start=(1, 13), end=(1, 14), line='print("hello")') TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='') ``` {% hint style="info" %} 此外，还可以在命令行中调用 tokenize： {% endhint %} ```bash $ python -m tokenize test.py 0,0-0,0: ENCODING 'utf-8' 1,0-1,5: NAME 'print' 1,5-1,6: OP '(' 1,6-1,13: STRING '"hello"' 1,13-1,14: OP ')' 2,0-2,0: ENDMARKER '' ``` tokenizer 生成的 tokens 随后会被传递给 parser 根据 python 的语法来生成 parse tree 。当 parser 发现一个 token 违反了语法规则的时候就会抛出一个 SyntaxError。python 中有一个 [parser](https://docs.python.org/3.5/library/parser.html) 模块提供了有限的对 parse tree 的访问能力： {% code title="代码清单3.2: 使用 parser 模块获取 Python 代码的 parse tree" %} ```bash >>> import parser >>> from pprint import pprint >>> code_str = """ ... def hello_world(): ... return 'hello world' ... """ >>> st = parser.suite(code_str) >>> pprint(parser.st2list(st)) [257, [269, [295, [263, [1, 'def'], [1, 'hello_world'], [264, [7, '('], [8, ')']], [11, ':'], [304, [4, ''], [5, ''], [269, [270, [271, [278, [281, [1, 'return'], [331, [305, [309, [310, [311, [312, [315, [316, [317, [318, [319, [320, [321, [322, [323, [324, [3, "'hello world'"]]]]]]]]]]]]]]]]]]]], [4, '']]], [6, '']]]]], [4, ''],s [0, '']] ``` {% endcode %} 函数调用 parser.suite(source) 会返回一个 python 中对 parser tree 的中间表示即 parser tree (ST) 对象。之后的调用 parser.st2list 会将 parser 以 list 的形式返回。list 中第一个元素为一个 int 类型的数字表示 python grammar 中对应的 [identifier 编号](https://github.com/python/cpython/blob/3.7/Include/token.h)。 ![图3.0: 代码清单 1.3.2 中所展示的 parse tree 的图形化展示](https://3773612527-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LnNIujVvmLoYArfFY0O%2F-M1ItaVg-ABMB_8Lj9b8%2F-M1Iz3r_giMOeb1gWchs%2Fimage.png?alt=media\&token=1a6007e5-f155-4b2e-835c-b92cd721eded) 上图展示了代码清单1.3.2中产生的 parse tree 结构，可以看到其中每个节点的类型可以用一个整数来表示，这些对于这些整数的定义位于头文件 [Include/token.h](https://github.com/python/cpython/blob/3.7/Include/token.h) 和 [Include/graminit.h](https://github.com/python/cpython/blob/3.7/Include/graminit.h) 中。 在 CPython 虚拟机中，使用树结构来对 parser tree 进行表示。每一个产生式规则（production rule）是树中的一个节点（node）。对 node 的定义位于头文件 [Include/node.h](https://github.com/python/cpython/blob/3.7/Include/node.h#L10) 中。 {% code title="代码清单3.3: python 虚拟机中使用的节点数据结构" %} ```c typedef struct _node { short n_type; char *n_str; int n_lineno; int n_col_offset; int n_nchildren; struct _node *n_child; } node; ``` {% endcode %} 可以对 parser tree 进行遍历，访问节点的 类型、子节点、行号等等，这些操作以宏（macro）的形式定义在头文件 `Include/node.h` 中，用于与 parse tree 的节点进行交互。 ### 3.3 从 parse tree 到 AST 生成 parse tree 之后的下一步是将其转换成 AST（抽象语法树，Abstract Syntax Tree）。AST 是一种与语法细节无关的代码表示，比如说图1.3.2中的 parse tree 中有一个逗号节点（colon node），因为它属于其中的语法构造（syntax construct），但是 AST 中将不会包含这样的语法构造： {% code title="代码清单3.4: 使用 ast 模块操作源代码对应的 AST" %} ```python >>> import ast >>> node = ast.parse(code_str, mode='exec') >>> ast.dump(node) "Module(body=[FunctionDef(name='hello_world', args=arguments(args=[], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Return(value=Str(s='hello world'))], decorator_list=[], returns=None)])" ``` {% endcode %} AST 节点的定义可以在 [Parser/Python.asdl](https://github.com/python/cpython/blob/3.7/Parser/Python.asdl) 文件中找到（译注：ASDL 是一种用来描述 AST 的语言，可以参考 Eli Bendersky 的这篇[博文](https://eli.thegreenplace.net/2014/06/04/using-asdl-to-describe-asts-in-compilers)）。AST 中几乎所有的定义都与特定的语法构造有关比如 if 语句或者属性查找（attribute lookup）。python 的 [ast](https://docs.python.org/3.7/library/ast.html) 模块通过与解释器的绑定为我们提供了操作 AST 的能力。还有一些像 [codegen](https://github.com/andreif/codegen) 这样的工具可以接受一个 AST 对象然后输出对应的 python 源代码。 在 CPython 的实现中 AST 节点以 C 结构体的形式定义在 [Include/Python-ast.h](https://github.com/python/cpython/blob/3.7/Include/Python-ast.h) 之中。实际上，这些结构体是通过 python 代码生成的，[Parser/asdl\_c.py](https://github.com/python/cpython/blob/3.7/Parser/asdl_c.py) 模块可以根据 AST 的 asdl 定义来生成它们。比如说，语句（statement）节点的结构体一部分定义如下： {% code title="代码清单3.5: 语句（statement）节点的结构体定义（部分）" %} ```c struct _stmt { enum _stmt_kind kind; union { struct { identifier name; arguments_ty args; asdl_seq *body; asdl_seq *decorator_list; expr_ty returns; } FunctionDef; struct { identifier name; arguments_ty args; asdl_seq *body; asdl_seq *decorator_list; expr_ty returns; } AsyncFunctionDef; struct { identifier name; asdl_seq *bases; asdl_seq *keywords; asdl_seq *body; asdl_seq *decorator_list; } ClassDef; ... } v; int lineno; int col_offset; }; ``` {% endcode %} 上面的代码中， union 类型用来表示任意一个位于其中的 C 类型。文件 Python/ast.c 中的 [PyAST\_FromNode](https://github.com/python/cpython/blob/3.7/Python/ast.c#L879) 函数能够根据一个 parse\_tree 来生成 AST。生成 AST 之后，下一步就是根据 AST 来生成字节码了。 ### 3.4 构建符号表 生成 AST 之后的下一步是生成符号表（symbol table）。符号表就如同它的名字所暗示的那样，是一个代码块（code block）与上下文（context）中所使用到的名字的集合。符号表的构建过程涉及到对一个代码块中所包含的所有名字以及对这些名字正确作用域赋值的分析。为了避免误解，在讨论复杂的符号表生成之前，我们要首先对一些与名字（names）、绑定（bindings）相关的概念进行讨论： **名字与绑定** 在 python 中，对象通过名字进行引用，虽然有点像，但 names 与 C++ 与 Java 中变量并不一样。 ```python >>> x = 5 ``` 在上面的代码中，x 其实是一个对于对象 5 的引用。将对象 5 的引用赋值给名字（name） x 的过程称之为绑定（binding）。一个绑定行为所产生的结果是一个名字在执行过程中最内层的作用域中与一个对象产生关联。绑定可能发生在几个不同的情况下，比如在变量赋值过程中，或是发生在函数或者方法调用时实参与型参的绑定。有一点很重要的，需要注意的是名字只是符号，它们并没有与类型相关联，名字只是对带有类型的对象的引用而已。 **代码块** 代码块（code blocks）是 python 程序的重要概念之一，对它的理解对于理解 python 虚拟机的内部机制来说非常重要。代码块是一个能够在 python 中作为一个独立单元执行的代码片段，比如模块、函数和类。REPL 中的命令，命令行中使用 `-c` 参数执行的脚本命令也是代码块。一个代码块由多个与它相关的 namespace ，比如说，一个模块代码块能够访问 `global` namespace，一个函数代码块可以同时访问 `local` 和 `global` namespace。 #### Namespaces 一个 namespace 就像它的名字暗示的那样，可以理解为一个环境（context）在其中，一系列名字与对象被绑定在一起。比如说 builtin namespace 是一个包含了所有 built-in 函数的 namespace，它可以通过 `__builtins__.__dict__` 被访问。解释器能够访问多个 namespace 包括 `global`, `builtin`, `local`。这些 namespace 在不同的时间点被创建，具有不同的生命周期。比如说，一个新的 local namespace 在一个函数调用时创建，在一个函数退出或者返回时销毁。global namespace 在一个模块开始执行的时候被创建并且所有定义在其中的名字能够在模块级别上进行访问。而 built-in namespace 则是在解释器被调用的时候就被创建，并且其中包含了所有的 builtin names。这三者是 python 解释器中所主要使用的 namespace。 #### Scope 一个作用域（scope）是程序中的一块区域，在作用域中 namespace 可以不通过任何的 . （dot notaion）直接访问。在运行时（runtime）中存在以下几种作用域： 1. 局部命名空间的最内层的作用域。 2. 闭合函数（enclosing functions）作用域（在存在嵌套函数时有用）。 3. 当前模块的 globals 作用域。 4. 包含 builtin namespace 的作用域。 当一个名字在 python 中可用时，解释器会在 scope 的 namespace 中以由内到外的顺序进行搜索，如果在所有的 namespaces 中都没有找到，就会抛出一个 `NameError` 异常。 Python 支持静态作用域（static scoping）也被称之为词法作用域（lexical scoping），也就是说仅通过对程序代码的检查就可以推导出命名绑定。 {% hint style="info" %} #### 补充知识：未定义行为，在函数内修改 locals() 以下代码会发生报错： {% endhint %} ```python >>> def func1(): ... locals()['a'] = 1 ... print(locals()['a']) ... print(a) ... return locals() ... >>> func1() 1 Traceback (most recent call last): File "", line 1, in File "", line 4, in func1 NameError: name 'a' is not defined ``` {% hint style="info" %} 这是一个 Python 中的未定义行为，可以参考 [PEP558](https://www.python.org/dev/peps/pep-0558/) 。 {% endhint %} Python 中存在一个作用域规则看起来有些奇怪，它会阻止在 local 作用域中修改 `global` 作用域中的对象。如果发现有这样的行为，解释器会抛出一个 `UnboundLocalError` 异常： {% code title="代码清单A3.0: 试图在函数中修改全局变量" %} ```python >>> a = 1 >>> def inc_a(): a += 1 ... >>> inc_a() Traceback (most recent call last): File "", line 1, in File "", line 1, in inc_a UnboundLocalError: local variable 'a' referenced before assignment ``` {% endcode %} 为了能够在局部作用域中对全局作用域中的对象进行修改，需要使用 global 关键字： {% code title="代码清单A3.1: 在函数中使用 global 关键字" %} ```python >>> a = 1 >>> def inc_a(): ... global a ... a += 1 ... >>> inc_a() >>> a 2 ``` {% endcode %} Python 中还有一个 `nonlocal` 关键字用来在内层的作用域中修改一个外层的非全局作用域。这在编写嵌套函数（或者说是闭包（closure））时非常有用。下面是一个简单的例子对 `nonlocal` 的行为进行说明： {% code title="代码清单A3.2: 函数中使用 nonlocal 关键字修改外层 scope 中变量" %} ```python >>> def make_counter(): ... count = 0 ... def counter(): ... nonlocal count ... count += 1 ... return count ... return counter ... >>> counter_1 = make_counter() >>> counter_2 = make_counter() >>> counter_1() 1 >>> counter_1() 2 >>> counter_2() 1 >>> counter_2() 2 ``` {% endcode %} 至此，我们对 python 中的名字（names）与绑定（binding）相关的一些概念进行了讨论，我们接着来看如何根据 AST 生成符号表。 符号表创建涉及到的一系列的函数调用： ```python run_mod -> PyAST_CompileObject -> PySymtable_BuildObject ``` 函数 [PySymtable\_BuildObject](https://github.com/python/cpython/blob/3.7/Python/symtable.c#L251) 所接受的两个参数分别是之前生成的 AST 对象与该模块的文件名。符号表创建算法可以分为两个步骤。在第一个步骤中，被作为参数传递给 `PySymtable_BuildObject` 的 AST 中的每个节点会被按照顺序遍历，然后创建出一系列在 AST 中被使用的符号。下面的伪代码对这个过程进行了简单的描述，关于其中涉及到的术语，比如符号表（symbol table）与符号表项目（symbol table entry）在后面会有更详细的说明： {% code title="代码清单3.6: 从 AST 创建符号表的算法伪代码" %} ```python for node in AST: # 遍历 AST if (node 是一个 code block 的起始): ste = 新建符号表项目() st.st_stack.push(ste) # 新的符号表入栈 st.current_ste.children.append(st) # 将新表项加入上一个表项的子表项 st.current_ste = ste # 将符号表的 当前表项 设置为新建的符号表项 for node1 in code_block.nodes: # 遍历 code_block 里的所有节点 # 递归访问 node1 创建符号加入表项中， XXX 是 node1 的类型 symtable_visit_XXX(node1) st.st_stack.pop() # 将当前表项移出栈 st.current_st = st_stack.pop() else: 递归访问 node 与 sub_nodes(node) 创建符号加入符号表 ``` {% endcode %} 在第一轮在 AST 上进行的算法完成后，符号表内已经包含了模块中使用的所有名字 ，但并不包含这些名字的上下文信息。比如说，解释器不能告诉你一个给定的变量是一个全局变量，局部变量还是自由变量（free variables）。符号表生成的第二阶段从一个对 `Python/symtable.c` 中 [symtable\_analyze](https://github.com/python/cpython/blob/3.7/Python/symtable.c#L897) 函数的调用开始。这个阶段的算法将对第一个阶段中产生的符号分配作用域（local, global, free）。`Parser/symtable.c` 文件中的注释的信息十分丰富，特别是下面的这些节选，对第二阶段进行了很好的说明： > 符号表需要两个 pass 才能确定每个名称的范围。 第一个 pass 通过 `symtable`*`visit*`* 函数从 AST 收集原始信息，而第二个 pass 通过 pass1 中创建的`PySTEntryObject` 分析这些信息。 > > 在 pass2 中输入函数时，父级将传递对其子级可见的所有名称绑定集。 这些绑定用于确定非局部变量是自由变量还是隐式全局变量。 在这组可见名称中必须存在明确声明为非本地的名称如果不存在，则会引发语法错误。 进行局部分析后，它使用在第1遍过程中创建的一组更新的名称绑定分析每个子块。 > > 全局变量也有两种，隐式和显式。 使用全局语句声明显式全局变量。 隐式全局变量是一个自由变量，编译器在封闭的函数范围内未发现其绑定。 隐式全局是全局或内置的。 > > Python 的模块和类块使用 `xxx_NAME` 操作码来处理这些名称，以实现稍微奇怪的语义。 在这样的块中，名称被分配为全局名称，直到被分配给该名称为止。 然后将其视为本地对象。 > > 子代更新自由变量（free variable）集合。 如果将局部变量添加到子级设置的自由变量中，则该变量将标记为单元格。 定义的功能对象必须为可能超出功能范围的变量提供运行时存储。 在分析函数返回其父级之前，将单元变量从自由集中删除。 尽管这些注释试图用清晰的语言来解释这个过程，但其中仍然存在一些比较模糊的地方，比如： *passes the set of all name bindings visible to its children* ，这里的 parent 与 children 指的到底是什么？为了理解这些术语，我们来看一看符号表的数据结构。 #### 符号表数据结构 符号表生成过程中有两个核心的数据结构： 1. The symbol table data structure.（符号表） 2. The symbol table entry data structure.（符号表项目） 符号表数据结构定义在头文件 [Include/symtable.h](https://github.com/python/cpython/blob/3.7/Include/symtable.h#L18) 中，我们可以认为符号表由一系列持有给定模块中不同 code blocks 信息的表项所组成。 {% code title="代码清单3.7: 符号表数据结构" %} ```c struct symtable { PyObject *st_filename; /* name of file being compiled, decoded from the filesystem encoding */ struct _symtable_entry *st_cur; /* current symbol table entry */ struct _symtable_entry *st_top; /* symbol table entry for module */ PyObject *st_blocks; /* dict: map AST node addresses * to symbol table entries */ PyObject *st_stack; /* list: stack of namespace info */ PyObject *st_global; /* borrowed ref to st_top->ste_symbols */ int st_nblocks; /* number of blocks used. kept for consistency with the corresponding compiler structure */ PyObject *st_private; /* name of current class or NULL */ PyFutureFeatures *st_future; /* module's future features that affect the symbol table */ int recursion_depth; /* current recursion depth */ int recursion_limit; /* recursion limit */ }; ``` {% endcode %} 一个 python 模块可能包含多个 code block，比如多个函数定义。结构体中的 `st_blocks` 字段是一个所有 code block （AST node）到符号表项的映射。`st_top` 字段是一个符号表项，对应于一个被编译的模块（注意模块也是一个 code block），所以它将包含所有定义在模块 global namespace 中的名字。`st_cur` 字段指向一个符号表项目，该表项对应于正在被处理的 code block（AST node）。模块中的每一个 code block 有一个它自己的符号表项，它持有所有定义在其中的符号。 ![图3.1: 一个符号表（symbol table）与符号表项（symbol table entry）的图形化展示](https://3773612527-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LnNIujVvmLoYArfFY0O%2F-M1JagKs3YSAnKG0XnNG%2F-M1KGkJjpbCqS6RNk2t8%2Fimage.png?alt=media\&token=400e548e-9a99-4f4b-9c4a-882a316f7354) 再来看一下 Include/symtable.h 中 [\_symtable\_entry ](https://github.com/python/cpython/blob/3.7/Include/symtable.h#L37)的定义，对于理解这个数据结构的作用很有帮助： {% code title="代码清单3.8: \_symtable\_entry 数据结构" %} ```c typedef struct _symtable_entry { PyObject_HEAD PyObject *ste_id; /* int: key in ste_table->st_blocks */ PyObject *ste_symbols; /* dict: variable names to flags */ PyObject *ste_name; /* string: name of current block */ PyObject *ste_varnames; /* list of function parameters */ PyObject *ste_children; /* list of child blocks */ PyObject *ste_directives;/* locations of global and nonlocal statements */ _Py_block_ty ste_type; /* module, class, or function */ int ste_nested; /* true if block is nested */ unsigned ste_free : 1; /* true if block has free variables */ unsigned ste_child_free : 1; /* true if a child block has free vars, including free refs to globals */ unsigned ste_generator : 1; /* true if namespace is a generator */ unsigned ste_varargs : 1; /* true if block has varargs */ unsigned ste_varkeywords : 1; /* true if block has varkeywords */ unsigned ste_returns_value : 1; /* true if namespace uses return with an argument */ unsigned ste_needs_class_closure : 1; /* for class scopes, true if a closure over __class__ should be created */ int ste_lineno; /* first line of block */ int ste_col_offset; /* offset of first line of block */ int ste_opt_lineno; /* lineno of last exec or import * */ int ste_opt_col_offset; /* offset of last exec or import * */ int ste_tmpname; /* counter for listcomp temp vars */ struct symtable *ste_table; } PySTEntryObject; ``` {% endcode %} 源码中每个字段后的注释对其进行了解释，`ste_symbols` 字段是 一个包含了该 code block 中所确认到的所有符号到 flag 的映射，其中 flag 是一个数值类型的值，它提供了符号在该环境中所具有的含义。比如，一个符号可能是一个函数参数或者是一个全局定义。flag 具体被定义在文件 [Include/symtable.h](https://github.com/python/cpython/blob/3.7/Include/symtable.h#L84) 中，这里列出一部分作为示例： {% code title="代码清单3.9: 用于指示符号在环境中所具有含义的 Flag" %} ```c /* Flags for def-use information */ #define DEF_GLOBAL 1 /* global stmt */ #define DEF_LOCAL 2 /* assignment in code block */ #define DEF_PARAM 2<<1 /* formal parameter */ #define DEF_NONLOCAL 2<<2 /* nonlocal stmt */ #define USE 2<<3 /* name is used */ #define DEF_FREE 2<<4 /* name used but not defined in nested block */ #define DEF_FREE_CLASS 2<<5 /* free variable from class's method */ #define DEF_IMPORT 2<<6 /* assignment occurred via import */ #define DEF_ANNOT 2<<7 /* this name is annotated */ ``` {% endcode %} 我们回到对于符号表的讨论上，假设一个模块包含如下代码： {% code title="代码清单3.10: 一个简单的 python 函数" %} ```python def make_counter(): count = 0 def counter(): nonlocal count count += 1 return count return counter ``` {% endcode %} 那么它被编译后将产生三个符号表项。首先第一个表项是模块级别的表项，它将包含定义一个带有局部作用域的 `make_counter` 。下一个表项将进入到 `make_counter` 函数中，它将包含定义在局部作用域中的 `count` 和 `counter` 。最后一个表项将进入到嵌套定义的 `counter` 函数，它包含一个被标记为 free 的变量 `count` 。值得注意的是虽然 `make_counter` 在模块 code block 表项中是局部的，但它会被看作是被全局定义在模块 code block 中，因为符号表的 `st_global`字段指向了 `st_top` 对应的符号也就是模块 code block 下的符号（`st_top->ste_symbols`）。 ### 3.5 从 AST 到 code objects 符号表生成之后，编译过程的下一步是根据 AST 以及符号表中的信息来生成 code object。负责这个过程处理的函数定义在文件 [Python/compile.c](https://github.com/python/cpython/blob/3.7/Python/compile.c) 中。生成 code object 也是一个多步的过程。在第一步中，AST 被转化为 python 字节码指令的基础块（basic blocks）。这里使用的算法与生成符号表时的算法很相似。由一系列命名为 `compiler_visit_xx` 的函数来进行，xx 指的是节点的类型，这些函数会递归地访问每一个 AST 节点并在访问过程中产生 python 字节码指令的基础块。基础指令块以及块之间的路径被隐式的表示为图（graph）结构，也称之为控制流图（control flow graph，CFG）。这个图体现了在运行过程中的代码路径。然后进入 code object 生成的第二阶段，以后缀深度优先遍历的方式将前一步生成的控制流图扁平化（flatten）。图被扁平化之后，跳转偏移量被计算出来作为 jump 指令的参数。然后再根据这些指令生成 code object，为了更好的理解这个过程，我们来看一看下面这个函数： {% code title="代码清单3.11: 一个简单的 python 函数" %} ```python def fizzbuzz(n): if n % 3 == 0 and n % 5 == 0: return 'FizzBuzz' elif n % 3 == 0: return 'Fizz' elif n % 5 == 0: return 'Buzz' else: return str(n) ``` {% endcode %} 这个函数对应的 AST 如下图所示： ![图3.2: fizzbuzz 函数的 AST 图示（译注：这里的 AST 画的有问题，应该只有最后一个分支对应 str(n) 调用前几个分支返回的都是字面量）](https://nanguage.github.io/examples/pyvm/Inside%20The%20Python%20Virtual%20Machine%EF%BC%88%E5%89%8D%E4%B8%89%E7%AB%A0%E7%BF%BB%E8%AF%91%EF%BC%89_files/e54e7b26-9c62-45e3-9574-f93f39d8ba6a.png) 上面的 AST 编译成的 CFG 类似于下图展示的那样，空块（empty）在图中已经被忽略。仔细看一下这个图可以得到一些关于基础块的理解。基础块有单一的入口与多个不同的出口，关于它后面还会做更详细的讨论。 ![图 3.3: fizzbuzz 函数对应的控制流图（CFG），其中的直线代表代码正常的运行顺序，曲线代表跳转。](https://nanguage.github.io/examples/pyvm/Inside%20The%20Python%20Virtual%20Machine%EF%BC%88%E5%89%8D%E4%B8%89%E7%AB%A0%E7%BF%BB%E8%AF%91%EF%BC%89_files/70037a0c-2565-4ee1-a1ec-dbe78f650fdd.png) 接下来我们看一看每个 block 对应的字节码，为了让我们更专注于所讨论的内容，我们省略了指令的参数（译注：如果你使用 dis.dis 反编译 fizzbuzz 得到的结果可能与文中有所不同，很可能是由于版本导致的，但并不影响理解，翻译以原文为准）。 Block 1：这个块包含了映射到图 1.3.6.a 所示的 AST 中 `BoolOp` 节点的指令。在这个 block 中表达式 n%3==0 and n%5==0 通过以下11条指令实现： ```python LOAD_FAST LOAD_CONST BINARY_MODULO LOAD_CONST COMPARE_OP JUMP_IF_FALSE_OR_POP LOAD_FAST LOAD_CONST BINARY_MODULO LOAD_CONST COMPARE_OP ``` 注意 `if` 节点并没有包括在这个 block 中，原因将在 block2 的讨论中说明。如同图3.3 中所示的那样，有两条途径离开这个 block：直接执行完毕后离开或者通过执行 `JUMP_IF_FALSE_OR_POP` 指令跳转离开进入 block2。 Block2：这个 block 映射到第一个 if 节点，封装了 if 的测试和后续的子句（clause）。block2 包含以下几条指令： ```python POP_JUMP_IF_FALSE LOAD_CONST RETURN_VALUE JUMP_FORWARD ``` 在下面的章节中将会看到，当解释器执行 `if` 语句的字节码指令的时候，它会从栈上读取一个对象根据对象的布尔值来决定执行下一条指令或者跳转到另一个地方继续执行那里的指令。指令 `POP_JUMP_IF_FALSE` 就是一个负责这个的跳转指令（opcode），它接受一个参数作为它跳转的目标地址。你可能会疑惑为什么 `BoolOp` 节点与 `if` 语句对应的不是同一个 block。还记得吗？python 中的 and 操作符是一个短路运算，所以当 n%3==0 被求值为 False 的时候 n%5==0 将不会被求值。可以看一看 block1 中的指令，可以发现在第一个比较（comprasion）操作后面接着一条 `JUMP_IF_FALSE_OR_POP` 指令。这条指令是一种 jump 操作的变体因此需要一个跳转目标。这样子来看，第二个 block 的作用就很明显了，就是为上面的短路跳转提供一个地址，跳转的参数在扁平化的时候可以被计算出来。如果布尔表达式中的所有成份被求值完成，`BoolOp` block 中的指令全部被执行之后，也会按照正常的顺序进入 if 语句的 block。 Block3：这个 block 对应于第一个 `orElse` AST 节点，该节点包含以下9条指令： ```python LOAD_FAST LOAD_CONST BINARY_MODULO LOAD_CONST COMPARE_OP POP_JUMP_IF_FALSE LOAD_CONST RETURN_VALUE JUMP_FORWARD ``` 可以看到 `elif` 语句和 `n%3==0` 在同一个 block 中，原因很明显，因为该 block 不需要额外的 jump 出口。 Block4：和 block3 差不多，只不过指令的参数有所不同。 Block5：映射到最终的 `orElse` AST 节点，包含4条指令： ```python LOAD_GLOBAL LOAD_FAST CALL_FUNCTION RETURN_VALUE ``` `LOAD_GLOBAL` 接受一个 `str` 参数，将 `str` 函数加载到栈上。`LOAD_FAST` 将参数 `n` 加载到栈上。`RETURN_VALUE` 将把栈上调用 `CALL_FUNCTION` 后得到的值返回。 和前面的章节一样，我们再来看一下具体的数据结构。 **编译器数据结构** 下图展示了组成CFG基础块生成过程中所涉及到的主要数据结构之间的关系： ![图 3.4: 生成 code object 过程中 4 个主要的数据结构。](https://nanguage.github.io/examples/pyvm/Inside%20The%20Python%20Virtual%20Machine%EF%BC%88%E5%89%8D%E4%B8%89%E7%AB%A0%E7%BF%BB%E8%AF%91%EF%BC%89_files/8f23e180-6dd4-459f-af83-9ed883579458.png) 在顶层是一个 compiler 数据结构，它捕获了模块的全局编译过程，这个结构体定义在 [Python/compile.c](https://github.com/python/cpython/blob/3.5/Python/compile.c#L151) 文件中。 {% code title="代码清单3.12: 编译器数据结构" %} ```c struct compiler { PyObject *c_filename; struct symtable *c_st; PyFutureFeatures *c_future; /* pointer to module's __future__ */ PyCompilerFlags *c_flags; int c_optimize; /* optimization level */ int c_interactive; /* true if in interactive mode */ int c_nestlevel; struct compiler_unit *u; /* compiler state for current block */ PyObject *c_stack; /* Python list holding compiler_unit ptrs */ PyArena *c_arena; /* pointer to memory allocation arena */ }; ``` {% endcode %} 我们对其中几个字段比较感兴趣： 1. `*c_st`：指向之前生成的符号表。 2. `*u`：一个到 compiler unit 结构体的引用。这个结构体封装了与一个 code block 进行交互所需的信息。本字段指向目前正在处理的 code block 所对应的 compiler unit。 3. `*c_stack`：一个到 compiler unit 栈的引用。当一个 code block 由多个 code block 所组成时，这个字段负责当遇到一个新的 block 时 compiler unit 结构体的储存与恢复。当进入一个新的 code block 时，一个新的作用域被创建，然后 [compiler\_enter\_scope()](https://github.com/python/cpython/blob/3.7/Python/compile.c#L540) 会将当前的 compiler unit （ `*u` ）push 到栈中。同时 `*c_stack` 创建一个新的 compiler unit 对象并将其设置为当前compiler unit。当离开一个 block 的时候，`*c_stack` 会根据复原状态进行弹出。 对于每个被编译的模块，对应一个被初始化的 compiler 数据结构。当 AST 被遍历，其中每一个 code block 对应的 `compiler_unit` 数据结构会被生成。 **compiler\_unit 数据结构** [compiler\_unit](https://github.com/python/cpython/blob/3.5/Python/compile.c#L103) 结构体的定义展示在下面的代码清单中，它持有生成一个 code block 对应的字节码指令所需的信息。当查看这个结构体的定义时会发现，很多字段的名字你可能会比较熟悉。 {% code title="代码清单3.13: compiler\_unit 数据结构" %} ```c struct compiler_unit { PySTEntryObject *u_ste; PyObject *u_name; PyObject *u_qualname; /* dot-separated qualified name (lazy) */ int u_scope_type; /* The following fields are dicts that map objects to the index of them in co_XXX. The index is used as the argument for opcodes that refer to those collections. */ PyObject *u_consts; /* all constants */ PyObject *u_names; /* all names */ PyObject *u_varnames; /* local variables */ PyObject *u_cellvars; /* cell variables */ PyObject *u_freevars; /* free variables */ PyObject *u_private; /* for private name mangling */ Py_ssize_t u_argcount; /* number of arguments for block */ Py_ssize_t u_kwonlyargcount; /* number of keyword only arguments for block */ /* Pointer to the most recently allocated block. By following b_list members, you can reach all early allocated blocks. */ basicblock *u_blocks; basicblock *u_curblock; /* pointer to current block */ int u_nfblocks; struct fblockinfo u_fblock[CO_MAXBLOCKS]; int u_firstlineno; /* the first lineno of the block */ int u_lineno; /* the lineno for the current stmt */ int u_col_offset; /* the offset of the current stmt */ int u_lineno_set; /* boolean to indicate whether instr has been generated with current lineno */ }; ``` {% endcode %} 字段 `u_blocks` 与 `u_curblock` 用于引用那些组成被编译的 code block 的基础块。`*u_ste` 字段为到一个被编译的 code block 中的符号表项的引用。其余的字段从它们的名字上就比较容易理解。组成 code block 的不同节点在编译过程中会被遍历，并且根据一个节点类型是否能够起始一个 basic block，一个含有 node 对应指令的 basic block 会被创建，或者有新指令被添加到已有的 basic block 当中。能够起始一个 basic block 的节点类型包括但不限于： 1. 函数节点 2. 跳转目标 3. 异常处理 4. 布尔运算等 **basic block 与 instruction 数据结构** [basicblock\_](https://github.com/python/cpython/blob/3.5/Python/compile.c#L53) 结构体是一种在 CFG 生成过程中相当有趣的数据结构。一个 basic block 是一个具有单一入口与多个出口的指令序列。在 CPython 中它的定义如下： {% code title="代码清单3.14: basicblock\_ 数据结构" %} ```c typedef struct basicblock_ { /* Each basicblock in a compilation unit is linked via b_list in the reverse order that the block are allocated. b_list points to the next block, not to be confused with b_next, which is next by control flow. */ struct basicblock_ *b_list; /* number of instructions used */ int b_iused; /* length of instruction array (b_instr) */ int b_ialloc; /* pointer to an array of instructions, initially NULL */ struct instr *b_instr; /* If b_next is non-NULL, it is a pointer to the next block reached by normal control flow. */ struct basicblock_ *b_next; /* b_seen is used to perform a DFS of basicblocks. */ unsigned b_seen : 1; /* b_return is true if a RETURN_VALUE opcode is inserted. */ unsigned b_return : 1; /* depth of stack upon entry of block, computed by stackdepth() */ int b_startdepth; /* instruction offset for block, computed by assemble_jump_offsets() */ int b_offset; } basicblock; ``` {% endcode %} 正如之前所说的，CFG 由一系列 basic blocks 以及它们之间的连接所组成。`*b_instr` 字段引用到一个指令结构体的数组，一个指令结构体对应于一条字节码指令，字节码指令的编号可在头文件 [Include/opcode.h](https://github.com/python/cpython/blob/3.7/Include/opcode.h) 中找到。指令结构体 instr 定义在文件 [Python/compile.c](https://github.com/python/cpython/blob/3.7/Python/compile.c#L44) 中。 {% code title="代码清单3.15: instr 数据结构" %} ```c struct instr { unsigned i_jabs : 1; // 绝对跳转 jump absolute unsigned i_jrel : 1; // 相对跳转 jump relative unsigned char i_opcode; int i_oparg; struct basicblock_ *i_target; /* target block (if jump instruction) */ int i_lineno; }; ``` {% endcode %} 再回头看一下图3.3，我们可以看到由 block1 到 block2 存在两条可行的路径。第一条路径是正常执行由 block1 到 block2，第二条是在第一次比较时直接跳转到 block2 。现在跳转的目标还是 basic block，但实际执行过程中 code object 中只有字节码流（bytecodes stream） ，并且只能通过偏移量对它进行索引，与 basic block 没有关系。我们必须将使用 block 中创建的隐式图作为跳转目标，并以某种方式将这些具有偏移的 block 替换为指令数组。这就是 basic blocks 的汇编（assembling）过程。 **汇编 basic blocks** 一旦 CFG 被生成，basic blocks 包含了字节码指令，但目前这些 blocks 还不是线性排列的。跳转指令的目标仍是 basic block 而不是指令流中的绝对偏移量。[assemble](https://github.com/python/cpython/blob/3.7/Python/compile.c#L5482) 函数将会把 CFG 进行线性排列并生成 code object。 首先，`assemble` 函数会任何没有 `return` 语句的 block 的结尾添加一个 return None ，现在你知道为什么可以在函数和方法中不写 `return` 了吧。然后会以后序深度优先（post-order deep first）的方式遍历 CFG 图，以对它进行扁平化。后序遍历指的是在遍历时先访问所有的子节点再访问根节点。 {% hint style="info" %} #### 图遍历 ![图3.5a: 图遍历](https://3773612527-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LnNIujVvmLoYArfFY0O%2F-M1Lnqg5SanpAvDnaHzQ%2F-M1Lo9_nONB55LAopvj_%2Fimage.png?alt=media\&token=b7d51171-72b5-4231-a1ca-c8eff004c8be) 在对一个图进行后序深度优先遍历时，我们首先会递归地访问一个根结点的左子节点，然后是右子节点，然后才是这个根节点自己。比如以上面这个图结构作为例子，当我们以后序深度优先遍历对它进行扁平化的时候，对节点的访问顺序是：`H -> D -> I -> J -> E -> B -> K -> L -> F -> G -> C -> A` 。如果是前序（pre-order）遍历的话：`A -> B -> D -> H -> E -> I -> J -> C -> F -> K -> L -> G` 。而如果是中序（in-order）遍历：`H -> D -> B -> I -> E -> J -> A -> K -> L -> F -> C -> G` 。 {% endhint %} fizzbuzz 函数的 CFG （图3.3）相对比较简单，如果对它进行后序遍历，顺序是：block5 -> block4 -> block3 -> block2 -> block1 。当 CFG 被扁平化（或者说是线性化）以后，扁平化图的跳转指令的跳转偏移量就可以被 [assemble\_jump\_offsets](https://github.com/python/cpython/blob/3.7/Python/compile.c#L5262) 函数计算出来了。 对跳转偏移量的汇编需要两个阶段，在第一个阶段，每条指令的偏移量会被计算出来放进指令数组中，就像下面的代码清单中所展示的那样。这是一个简单的循环，它从被 CFG 扁平化后得到的数组的末尾开始从 0 开始生成每一个 block 对应的偏移量。 {% code title="代码清单3.16: 计算字节码偏移量" %} ```c ... totsize = 0; for (i = a->a_nblocks - 1; i >= 0; i--) { b = a->a_postorder[i]; bsize = blocksize(b); b->b_offset = totsize; totsize += bsize; } ... ``` {% endcode %} 在第二阶段，跳转指令的跳转目标偏移量被计算出来，这一步涉及到计算绝对跳转与相对跳转的跳转地址： {% code title="代码清单3.17: 汇编跳转目标偏移量" %} ```c ... for (b = c->u->u_blocks; b != NULL; b = b->b_list) { bsize = b->b_offset; for (i = 0; i < b->b_iused; i++) { struct instr *instr = &b->b_instr[i]; int isize = instrsize(instr->i_oparg); /* Relative jumps are computed relative to the instruction pointer after fetching the jump instruction. */ bsize += isize; if (instr->i_jabs || instr->i_jrel) { instr->i_oparg = instr->i_target->b_offset; if (instr->i_jrel) { // 相对跳转 instr->i_oparg -= bsize; } instr->i_oparg *= sizeof(_Py_CODEUNIT); if (instrsize(instr->i_oparg) != isize) { extended_arg_recompile = 1; } } } } ... ``` {% endcode %} 随着跳转地址被计算，扁平化后的 CFG 内的指令以反向后序顺序（reverse post order）被生成。反向后序顺序是对 CFG 的拓扑排序，也就是说对于 CFG 中所有的边 (u, v)，在这个排序中 u 都会排在 v 前面。这样做的原因很明显，我们一般来说想要把跳转的起点放在终点之前。当字节码生成完毕，code object 对象就可以根据这些字节码以及符号表中的信息进行生成，code object 对象返回给调用函数的时候，整个编译过程就在此结束了。