尝试翻译 Inside The Python Virtual Machine

书籍地址：https://leanpub.com/insidethepythonvirtualmachine/read

原书作者：@obi_inc，翻译：@NaNg

学习目的，水平有限，有错误请指正。本文以 CPython3.5 源码为标准。

1. Python程序的执行过程

根据解释器调用方式的不同，一个Python程序的执行可以分为二或三个阶段：

1. 初始化（Initialization）：这个阶段涉及到对于python进程所需要的一系列数据结构的初始化。此阶段在交互模式下不会进行。

2. 编译（Compiling）：该阶段涉及到将源代码解析成语法树，创建 AST(Abstract Syntax Tree，抽象语法树)对象，创建 symbol tables以及生成 code objects。

3. 解释运行（Interpreting）：这个阶段涉及到在一些环境（context）下对 code object 的执行。

图1. python 代码执行过程示意图

1.a 补充知识：CPython 的项目结构：

参考 CPython 开发指南（Python Developer's Guide），（CPython source code）。CPython项目中的大多数C代码位于少数几个文件夹中：

Include：一些头文件。
Objects：包括从 int 到 type的一系列对象（object）的实现。
Python：解释器、字节码编译器以及一些其它的基础设施。
Parser：parser，lexer 以及 parser generator。
Modules：stdlib 扩展模块，以及 main.c。
Programs：内容不多，主要是作为程序入口的 main 函数。

1.1 初始化

当以非交互模式运行一个Python 程序的时候，比如 :

 
$ python test.py

C runtime 会首先进行一些初始化，比如包载入、环境变量的设置与检查，然后会执行python的main函数（Programs/python.c）。接着 main 函数会进一步调用 Py_Main 函数（Modules/main.c）进行包括解析命令行参数设置flags、读取环境变量（详见此处）、running hooks、哈希随机化等在内的一些解释器初始化操作。在此过程中 Py_Initialize 函数（Python/pylifecycle.c）会被调用，它会初始化两个非常重要的数据结构：interpreter state 和 thread state。

可以看一下 interpreter state data structure 的在源码中的定义（Include/pystate.h）：

 
typedef struct _is {
    struct _is *next;
    struct _ts *tstate_head;
    PyObject *modules;
    PyObject *modules_by_index;
    PyObject *sysdict;
    PyObject *builtins;
    PyObject *importlib;
    PyObject *codec_search_path;
    PyObject *codec_search_cache;
    PyObject *codec_error_registry;
    int codecs_initialized;
    int fscodec_initialized;
    PyObject *builtins_copy;
} PyInterpreterState;

*next 字段为一个指向另一个解释器实例的引用（多个解释器可以同时存在于一个进程当中，译注：这个特性有望用于解决 CPython 的 GIL 问题，参考 PEP554）
*tstate_head 字段指向 main thread of execution。
modules, modules_by_index, sysdict, builtins 以及 importlib 从它们的名字就能理解。它们都被定义为 PyObject 的实例，在 Python 虚拟机中 PyObject 为最基本的对象类型。
codec* 相关的字段持有用于定位、加载编码方式（encodings）的信息，对于字节解码（decoding bytes）非常重要。

程序的运行必须在一个线程之中进行，thread state structure 包含了一个线程执行 python code object 所需的信息，关于 thread state 定义的其中一部分代码如下（Include/pystate.h）：

 
typedef struct _ts {
    struct _ts *prev; 
    struct _ts *next; 
    PyInterpreterState *interp;
    struct _frame *frame;
    int recursion_depth;
    char overflowed;
    char recursion_critical;
    int tracing;
    int use_tracing;
    Py_tracefunc c_profilefunc;
    Py_tracefunc c_tracefunc;
    PyObject *c_profileobj;
    PyObject *c_traceobj;
    PyObject *curexc_type;
    PyObject *curexc_value;
    PyObject *curexc_traceback;
    PyObject *exc_type;
    PyObject *exc_value;
    PyObject *exc_traceback;
    PyObject *dict;  /* Stores per-thread state */
    int gilstate_counter;
    ... 
} PyThreadState;

初始化过程还会设置一些重要的机制，比如基本的 stdio。

1.2 简单描述：从编译到代码运行

一旦完成了所有的初始化，Py_Main 函数会调用 run_file 函数，随后以下的将发生调用：

PyRun_AnyFileExFlags -> PyRun_SimpleFileExFlags->PyRun_FileExFlags->PyParser_ASTFromFileObject

在 PyRun_SimpleFileExFlags 函数调用中，__main__ namespace 将被创建，文件内容将在其中被运行。它也将检查文件的 pyc 版本是否存在（pyc 文件即一个储存了已经被执行过的py文件编译后的代码（字节码）的文件）。当文件的 pyc 版本存在的时候，将会尝试以二进制形式读取并执行它。而当 pyc 文件不存在的时候，会顺着 PyRun_FileExFlags 向下调用，PyParser_ASTFromFileObject 函数会接着调用 PyParser_ParseFileObject 函数，它会读取被执行模块的内容并建立 parse tree，然后将 parse tree 传递给 PyAST_FromNodeObject 根据 parse tree 创建 AST。

AST 生成后会被传给 run_mod 函数，这个函数会接着调用 PyAST_CompileObject 根据 AST 生成 code object。并且在调用 PyAST_CompileObject 生成字节码的时候会经过一个简单的 peephole optimizer 进行字节码优化。随后 run_mod 会调用 PyEval_EvalCode 随之产生一系列的 function call:

PyEval_EvalCode->PyEval_EvalCodeEx->_PyEval_EvalCodeWithName->PyEval_EvalFrameEx

在 PyEval_EvalFrameEx 中的解释器循环（interpreter loop）才会实际进行对 code object 的运行处理。它不只是将 code object 作为参数而是使用一个 frame object，它有一个字段用来保存到 code object 的引用。简单来说，解释器循环会不断读取储存在一个指令数组中的下一个指令进行执行，增加或者删除位于栈上的对象，直到没有新的指令或者中途发生异常中断了循环。

Python 提供了一系列可以用于探索 code object 的函数。比如说，一个简单的程序可以被编译为一个 code object 和反编译（disassembled）成被python虚拟机执行的 opcodes：

 
>>> import dis
>>> def square(x):
...     return x*x
... 
>>> dis.dis(square)
  2           0 LOAD_FAST                0 (x)
              2 LOAD_FAST                0 (x)
              4 BINARY_MULTIPLY
              6 RETURN_VALUE

头文件 Include/opcode.h 中包含了 python 虚拟机支持的 instruction/opcodes 清单。其实 opcodes 的概念很容易理解，在上面的例子中有4条 instruction：LOAD_FAST 将它的参数对应的值（这里对应x）加载到栈上。python 虚拟机是基于栈的（stack based），也就是说 opcode 进行求值的对象以及求值得到的结果都会保存在栈上。BINARY_MULTIPLY opcode 会将前两条指令的结果从栈中弹出（pop），执行二进制乘法运算然后将结果放（push）回栈顶。RETURN_VALUE 指令会从栈中弹出设置为返回值并中断解释器循环。

这里还涉及到几个暂时没有被解答的问题：

LOAD_FAST 加载的值来自于哪里？
指令中使用的参数来自于哪里？
嵌套的函数与方法调用是如何被管理的？
解释器循环是如何进行异常处理的？

当所有的指令都被执行以后，Py_Main 将继续执行一些清理（clean up）过程。就像 Py_Initialize 所做的那样，Py_Finalize 会被调用完成一些清理任务，比如等待线程退出、调用 exit hooks、清理解释器分配的仍然被使用的内存等等。

1.3 编译 Python 源代码

尽管一般并不认为 Python 是一门编译性的语言，但实际上在代码执行前 Python 源码仍会被编译成可以被 python 虚拟机执行的字节码。python 的编译过程非常直接，并不涉及到很多复杂的步骤。一个完整的 python 程序编译过程有以下几个步骤：

将源代码 parsing 成一个 parse tree。
将 parse tree 转化为 AST（抽象语法树， abstract syntax tree）。
生成符号表（symbol table）。
从 AST 生成 code object，这一步包含：

将 AST 转化为一个 flow control graph。
从 control flow graph 产生 code object。

其中将从源码到 AST 是一个标准的过程，python 这里并没有什么特别的，所以本书会把关注点更多放在 symbol tables 以及 code objects 的生成过程上。如果你对于 Parsing 的详细原理比较感兴趣，推荐阅读经典的《龙书》（dragon book）。

1.3.1 从源码到 parse tree

按照 Dragon book 中的描述 python 的 parser 属于一种 LL(1) parser。CPython 目录下的 Grammar/Grammer 文件中包含了 Python 语言文法的 EBNF（Extended Backus–Naur Form，扩展巴科斯范式）：

 
...
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]
...

每次从命令行中运行一个 python 模块的时候，PyParser_ParseFileObject 函数会启动对这个模块的 parsing过程，它会调用 tokenization 函数 PyTokenizer_FromFile ，它接受模块的文件名作为参数，将模块文件的内容分解为一个个合法的 python tokens 或者发现语法错误时进行报错。

1.3.2 Python tokens

Python 源码可以看作是一系列的 tokens，比如说 return 就是一个 keyword token，字面量 -2 是一个数值字面量 token 等等。Parsing python 源码的第一步就是将源码分割为一个个的 token。Python 中存在以下几种 token：

identifiers：由程序员定义的“名字”，包括函数名、变量名、类名等等。它们必须符合 python 文档中指定的规范。
operators：一些特殊的符号比如 +, * 能够对值进行运算产生结果。
delimiters：这类符号用来给表达式分组、提供标点、赋值操作，包括 (, ), {,}, =, *= 等。
literals：字面量，这类符号用于提供一些类型的常量。比如字符串、bytes 类型的字面量："Fred", b"Fred" 、数值类型的字面量 2 、浮点类型字面量 1e100 、虚数字面量 10j 。
comments：以 # 开头的字符串字面量，用户代码注释。comments 总是位于一个 physical line 的结尾。（译注：关于什么是 physical line 与 logical line 可以参考这里）
NEWLINE：用于指示一行（logical line）的结束。
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 生成算法的伪代码如下：

 
使用 0 初始化 indent 栈
for 每一个 logical line:
    if (当前行的缩进级别 > 栈顶的级别):
        push(当前缩进级别)
        生成一个 INDENT token
    if (当前行的缩进级别 < 栈顶的级别):
        if (栈中不存在一个缩进级别 == 当前缩进级别):
            报告一个错误
        for 栈顶的每一个 != 当前行缩进级的值:
            移除这个值
            生成一个 DEDENT token
    tokenize(当前行)
对每一个栈上的值（除了0）生成 DEDENT token

CPython 的实现中 PyTokenizer_FromFile 函数会按照从左到右，从上到下的对 python 源码文件进行扫描并进行 tokenize。空格字符除了终止符被用来分隔开 token，但这不是必须的。如果其中存在歧义，则按照从右到左合法的可能的最长字符串来理解。比如说 2+2 ，是一个字面量 2，一个 operator +，另一个字面量 2。

1.3.a 补充知识：调用 python tokenize

在 python 中提供了 tokenize 的接口（标准模块函数 tokenize.tokenize）可以使用它对 python 源代码进行 tokenize，它接受一个 ByteIO.readline 的 callable 对象返回一个 tokens 的 generator，对这个 generator 进行迭代就能得到被解析模块的 tokens 序列，比如：

 
>>> 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='')

此外，还可以在命令行中调用 tokenize：

 
$ 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 模块提供了对 parse tree 的有限访问：

 
>>> 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, ''],
 [0, '']]

代码清单 1.3.2

函数调用 parser.suite(source) 会返回一个 python 中对 parser tree 的中间表示即 parser tree (ST) 对象。之后的调用 parser.st2list 会将 parser 以 list 的形式返回。list 中第一个元素为一个 int 类型的数字表示 python grammar 中对应的 identifier 编号。

Figure 3.0: A parse tree for listing 3.2 (function that returns the 'hello world' string)

图1.3.2：代码清单 1.3.2 中所展示的 parse tree 的图形化展示

上图展示了代码清单1.3.2中产生的 parse tree 结构，可以看到其中每个节点的类型可以用一个整数来表示，这些对于这些整数的定义位于头文件 Include/token.h 和 Include/graminit.h 中。

在 CPython 虚拟机中，使用树数据结构来对 parser tree 进行表示。每一个产生式规则（production rule）是树中的一个节点（node）。对 node 的定义位于头文件 Include/node.h 中。

 
typedef struct _node {
    short       n_type;
    char        *n_str;
    int         n_lineno;
    int         n_col_offset;
    int         n_nchildren;
    struct _node    *n_child;
} node;

可以对 parser tree 进行遍历，访问节点的类型、子节点、行号等等，这些操作以宏（macro）的形式定义在头文件 Include/node.h 中，用于与 parse tree 的节点进行交互。

1.3.3 从 parse tree 到 AST

生成 parse tree 之后的下一步是将其转换成 AST（抽象语法树，Abstract Syntax Tree）。AST 是一种与语法细节无关的代码表示，比如说图1.3.2中的 parse tree 中有一个逗号节点（colon node），因为它属于其中的语法构造（syntax construct），但是 AST 中将不会包含这样的语法构造：

 
>>> 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)])"

AST 节点的定义可以在 Parser/Python.asdl 文件中找到（译注：ASDL 是一种用来描述 AST 的语言，可以参考 Eli Bendersky 的这篇博文）。AST 中几乎所有的定义都与特定的语法构造有关比如 if 语句或者属性查找（attribute lookup）。python 的 ast 模块通过与解释器的绑定为我们提供了操作 AST 的能力。还有一些像 codegen 这样的工具可以接受一个 AST 对象然后输出对应的 python 源代码。在 CPython 的实现中 AST 节点以 C 结构体的形式定义在 Include/Python-ast.h 之中。实际上，这些结构体是通过 python 代码生成的，Parser/asdl_c.py 模块可以根据 AST 的 asdl 定义来生成它们。比如说，语句（statement）节点的结构体一部分定义如下：

 
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;
};

上面的代码中， union 类型用来表示任意一个位于其中的 C 类型。文件 Python/ast.c 中的 PyAST_FromNode 函数能够根据一个 parse_tree 来生成 AST。生成 AST 之后，下一步就是根据 AST 来生成字节码了。

1.3.4 构建符号表

生成 AST 之后的下一步是生成符号表（symbol table）。符号表就如同它的名字所暗示的那样，是一个代码块（code block）与上下文（context）中所使用到的名字的集合。符号表的构建过程涉及到对一个代码块中所包含的所有名字以及对这些名字正确作用域赋值的分析。为了避免误解，在讨论复杂的符号表生成之前，我们要首先对一些与名字（names）、绑定（bindings）相关的概念进行讨论：

1.3.4.1 Names and binding

在 python 中，对象通过名字进行引用，虽然有点像，但 names 与 C++ 与 Java 中变量并不一样。

 
>>> x = 5

在上面的代码中，x 其实是一个对于对象 5 的引用。将对象 5 的引用赋值给名字（name） x 的过程称之为绑定（binding）。一个绑定行为所产生的结果是一个名字在执行过程中最内层的作用域中与一个对象产生关联。绑定可能发生在几个不同的情况下，比如在变量赋值过程中，或是发生在函数或者方法调用时实参与型参的绑定。有一点很重要的，需要注意的是名字只是符号，它们并没有与类型相关联，名字只是对带有类型的对象的引用而已。

1.3.4.1.1 Code Blocks

代码块（code blocks）是 python 程序的重要概念之一，对它的理解对于理解 python 虚拟机的内部机制来说非常重要。代码块是一个能够在 python 中作为一个独立单元执行的代码片段，比如模块、函数和类。REPL 中的命令类型，命令行中使用 -c 参数执行的脚本命令也是代码块。一个代码块由多个与它相关的 namespace ，比如说，一个模块代码块能够访问 global namespace，一个函数代码块可以同时访问 local 和 global namespace。

1.3.4.1.2 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。

1.3.4.1.3 Scopes

一个作用域（scope）是程序中的一块区域，在作用域中 namespace 可以不通过任何的 . （dot notaion）直接访问。在运行时（runtime）中存在以下几种作用域：

局部命名空间的最内层的作用域。
闭合函数（enclosing functions）作用域（在存在嵌套函数时有用）。
当前模块的 globals 作用域。
包含 builtin namespace 的作用域。

当一个名字在 python 中可用时，解释器会在 scope 的 namespace 中以由内到外的顺序进行搜索，如果在所有的 namespaces 中都没有找到，就会抛出一个 NameError 异常。 Python 支持静态作用域（static scoping）也被称之为词法作用域（lexical scoping），也就是说仅通过对程序代码的检查就可以推导出命名绑定。

1.3.4.a 补充：未定义行为，在函数内修改 locals()

请思考以下代码为什么会报错：

 
>>> def func1():
...     locals()['a'] = 1
...     print(locals()['a'])
...     print(a)
...     return locals()
... 
>>> func1()
1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in func1
NameError: name 'a' is not defined

这是一个 Python 中的未定义行为，可以参考 PEP558 。

注意：

Python 中存在一个作用域规则看起来有些奇怪，它会阻止在 local 作用域中修改 global 作用域中的对象。如果发现有这样的行为，解释器会抛出一个 UnboundLocalError 异常：

 
>>> a = 1
>>> def inc_a(): a += 1
... 
>>> inc_a()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in inc_a
UnboundLocalError: local variable 'a' referenced before assignment

为了能够在局部作用域中对全局作用域中的对象进行修改，需要使用 global 关键字：

 
>>> a = 1
>>> def inc_a():
...     global a
...     a += 1
... 
>>> inc_a()
>>> a
2

Python 中还有一个 nonlocal 关键字用来在内层的作用域中修改一个外层的非全局作用域。这在编写嵌套函数（或者说是闭包（closure））时非常有用。下面是一个简单的例子对 nonlocal 的行为进行说明：

 
>>> 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

至此，我们对 python 中的名字（names）与绑定（binding）相关的一些概念进行了讨论，我们接着来看如何根据 AST 生成符号表。

符号表的创建涉及到一系列的函数调用：

run_mod -> PyAST_CompileObject -> PySymtable_BuildObject

函数 PySymtable_BuildObject 所接受的两个参数分别是之前生成的 AST 对象与该模块的文件名。符号表创建算法可以分为两个步骤。在第一个步骤中，被作为参数传递给 PySymtable_BuildObject 的 AST 中的每个节点会被按照顺序遍历，然后创建出一系列在 AST 中被使用的符号。下面的伪代码对这个过程进行了简单的描述，关于其中涉及到的术语，比如符号表（symbol table）与符号表项目（symbol table entry）在后面会有更详细的说明：

 
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) 创建符号加入符号表

在第一轮在 AST 上进行的算法完成后，符号表内已经包含了模块中使用的所有名字，但并不包含这些名字的上下文信息。比如说，解释器不能告诉你一个给定的变量是一个全局变量，局部变量还是自由变量（free variables）。符号表生成的第二阶段从一个对 Python/symtable.c 中 symtable_analyze 函数的调用开始。这个阶段的算法将对第一个阶段中产生的符号分配作用域（local, global, free）。Parser/symtable.c 文件中的注释的信息十分丰富，特别是下面的这些节选，对第二阶段进行了很好的说明：

The symbol table requires two passes to determine the scope of each name. The first pass collects raw facts from the AST via the symtable_visit_* functions while the second pass analyzes these facts during a pass over the PySTEntryObjects created during pass 1.

When a function is entered during the second pass, the parent passes the set of all name bindings visible to its children. These bindings are used to determine if non-local variables are free or implicit globals. Names which are explicitly declared nonlocal must exist in this set of visible names - if they do not, a syntax error is raised. After doing the local analysis, it analyzes each of its child blocks using an updated set of name bindings.

There are also two kinds of global variables, implicit and explicit. An explicit global is declared with the global statement. An implicit global is a free variable for which the compiler has found no binding in an enclosing function scope. The implicit global is either a global or a builtin.
Python’s module and class blocks use the xxx_NAME opcodes to handle these names to implement slightly odd semantics. In such a block, the name is treated as global until it is assigned to; then it is treated as a local.

The children update the free variable set. If a local variable is added to the free variable set by the child, the variable is marked as a cell. The function object being defined must provide runtime storage for the variable that may outlive the function’s frame. Cell variables are removed from the free set before the analyze function returns to its parent.

尽管这些注释试图用清晰的语言来解释这个过程，但其中仍然存在一些歧义，比如： passes the set of all name bindings visible to its children ，这里的 parent 与 children 指的到底是什么？为了理解这些术语，我们来看一看符号表的数据结构。

1.3.5 符号表数据结构

符号表生成过程中有两个核心的数据结构：

The symbol table data structure.（符号表）
The symbol table entry data structure.（符号表项目）

符号表数据结构定义在头文件 Include/symtable.h 中，我们可以认为符号表由一系列持有给定模块中不同 code blocks 信息的表项所组成。

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 */
};

 
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 */
};

一个 python 模块可能包含多个 code block，比如多个函数定义。结构体中的 st_blocks 字段是一个所有 code block （AST node）到符号表项的映射。st_top 字段是一个符号表项，对应于一个被编译的模块（注意模块也是一个 code block），所以它将包含所有定义在模块 global namespace 中的名字。st_cur 字段指向一个符号表项目，该表项对应于正在被处理的 code block（AST node）。模块中的每一个 code block 有一个它自己的符号表项，它持有所有定义在其中的符号。

Figure 3.1: A Symbol table and symbol table entries.

图1.3.5: 一个符号表（symbol table）与符号表项（symbol table entry）的图形化展示

再来看一下 Include/symtable.h 中 _symtable_entry 的定义，对于理解这个数据结构的作用很有帮助：

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;

 
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;

源码中每个字段后的注释对其进行了解释，ste_symbols 字段是一个包含了该 code block 中所确认到的所有符号到 flag 的映射，其中 flag 是一个数值类型的值，它提供了符号在该环境中所具有的含义。比如，一个符号可能是一个函数参数或者是一个全局定义。flag 具体被定义在文件 Include/symtable.h 中，这里列出一部分作为示例：

 
/* 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 */

回到我们对于符号表的讨论上，假设一个模块包含如下代码：

 
def make_counter():
    count = 0
    def counter():
        nonlocal count
        count += 1
        return count
    return counter

那么它被编译后将产生三个符号表项。首先第一个表项是模块级别的表项，它将包含定义一个带有局部作用域的 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）。

1.3.6 从 AST 到 code object

符号表生成之后，编译过程的下一步是根据 AST 以及符号表中的信息来生成 code object。负责这个过程处理的函数定义在文件 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，为了更好的理解这个过程，我们来看一看下面这个函数：

 
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)

这个函数对应的 AST 如下所示：

Figure 3.2: A very simple AST for listing 3.2

图1.3.6.a fizzbuzz 函数的 AST 图示（译注：这里的 AST 画的有问题，应该只有最后一个分支对应 str(n) 调用前几个分支返回的都是字面量）

上面的 AST 编译成的 CFG 类似于下图展示的那样，空块（empty）在图中已经被忽略。仔细看一下这个图可以得到一些关于基础块的理解。基础块有单一的入口与多个不同的出口，关于它后面还会做更详细的讨论。

Figure 3.3: Control flow graph for the fizzbuzz function from listing 3.11. The straight line represent normal straight line execution of code while the curved lines represent jumps.

图1.3.6.b fizzbuzz 函数对应的控制流图（CFG），其中的直线代表代码正常的运行顺序，曲线代表跳转。

下面的描述中，为了让我们更专注于所讨论的内容，我们省略了指令的参数。

Block 1：这个块包含了映射到图 1.3.6.a 所示的 AST 中 BoolOp 节点的指令。在这个 block 中表达式 n%3==0 and n%5==0 通过以下七条指令实现：

 
             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 的讨论中说明。如同图 1.3.6.b 中所示的那样，有两条途径离开这个 block：直接执行完毕后离开或者通过执行 JUMP_IF_FALSE_OR_POP 指令跳转离开进入 block2。

Block2：这个 block 映射到第一个 if 节点，封装了 if 的测试和后续的子句（clause）。block2 包含以下几条指令：
POP_JUMP_IF_FALSE LOAD_CONST RETURN_VALUE JUMP_FORWARD
4
4

1
POP_JUMP_IF_FALSE
2
LOAD_CONST
3
RETURN_VALUE
4
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条指令：

 
             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条指令：
LOAD_GLOBAL LOAD_FAST CALL_FUNCTION RETURN_VALUE
4
4

1
LOAD_GLOBAL
2
LOAD_FAST
3
CALL_FUNCTION
4
RETURN_VALUE
LOAD_GLOBAL 接受一个 str 参数，将 str 函数加载到栈上。LOAD_FAST 将参数 n 加载到栈上。RETURN_VALUE 将把栈上调用 CALL_FUNCTION 后得到的值返回。

1.3.6.a 译注：不同 python 版本 bytecode 上存在的差异

经译者在 Python3.5 解释器上进行的测试，与上面的描述存在一些不同：

>>> dis.dis(fizzbuzz)
  2           0 LOAD_FAST                0 (n)
              2 LOAD_CONST               1 (3)
              4 BINARY_MODULO
              6 LOAD_CONST               2 (0)
              8 COMPARE_OP               2 (==)
             10 POP_JUMP_IF_FALSE       28
             12 LOAD_FAST                0 (n)
             14 LOAD_CONST               3 (5)
             16 BINARY_MODULO
             18 LOAD_CONST               2 (0)
             20 COMPARE_OP               2 (==)
             22 POP_JUMP_IF_FALSE       28

3          24 LOAD_CONST               4 ('FizzBuzz')
             26 RETURN_VALUE

4     >>   28 LOAD_FAST                0 (n)
             30 LOAD_CONST               1 (3)
             32 BINARY_MODULO
             34 LOAD_CONST               2 (0)
             36 COMPARE_OP               2 (==)
             38 POP_JUMP_IF_FALSE       44

5          40 LOAD_CONST               5 ('Fizz')
             42 RETURN_VALUE

6     >>   44 LOAD_FAST                0 (n)
             46 LOAD_CONST               3 (5)
             48 BINARY_MODULO
             50 LOAD_CONST               2 (0)
             52 COMPARE_OP               2 (==)
             54 POP_JUMP_IF_FALSE       60

7          56 LOAD_CONST               6 ('Buzz')
             58 RETURN_VALUE

9     >>   60 LOAD_GLOBAL              0 (str)
             62 LOAD_FAST                0 (n)
             64 CALL_FUNCTION            1
             66 RETURN_VALUE
             68 LOAD_CONST               0 (None)
             70 RETURN_VALUE

 
>>> dis.dis(fizzbuzz)
  2           0 LOAD_FAST                0 (n)
              2 LOAD_CONST               1 (3)
              4 BINARY_MODULO
              6 LOAD_CONST               2 (0)
              8 COMPARE_OP               2 (==)
             10 POP_JUMP_IF_FALSE       28
             12 LOAD_FAST                0 (n)
             14 LOAD_CONST               3 (5)
             16 BINARY_MODULO
             18 LOAD_CONST               2 (0)
             20 COMPARE_OP               2 (==)
             22 POP_JUMP_IF_FALSE       28
  3          24 LOAD_CONST               4 ('FizzBuzz')
             26 RETURN_VALUE
  4     >>   28 LOAD_FAST                0 (n)
             30 LOAD_CONST               1 (3)
             32 BINARY_MODULO
             34 LOAD_CONST               2 (0)
             36 COMPARE_OP               2 (==)
             38 POP_JUMP_IF_FALSE       44
  5          40 LOAD_CONST               5 ('Fizz')
             42 RETURN_VALUE
  6     >>   44 LOAD_FAST                0 (n)
             46 LOAD_CONST               3 (5)
             48 BINARY_MODULO
             50 LOAD_CONST               2 (0)
             52 COMPARE_OP               2 (==)
             54 POP_JUMP_IF_FALSE       60
  7          56 LOAD_CONST               6 ('Buzz')
             58 RETURN_VALUE
  9     >>   60 LOAD_GLOBAL              0 (str)
             62 LOAD_FAST                0 (n)
             64 CALL_FUNCTION            1
             66 RETURN_VALUE
             68 LOAD_CONST               0 (None)
             70 RETURN_VALUE

从上面的代码清单可以看出，并不像书中所描述的那样，fizzbuzz 函数编译后，elif 分支也像 if 分支那样 BoolOp 与后面的子句存在于两个不同的 code block 当中。

和前面的章节一样，我们来看一下具体的数据结构。

1.3.6.1 编译器数据结构

下图展示了组成CFG基础块生成过程中所涉及到的主要数据结构之间的关系：

Figure 3.4: The four major data structures used in generating a code object.

图1.3.6.1 生成 code object 过程中 4 个主要的数据结构。

在顶层是一个 compiler 数据结构，它捕获了模块的全局编译过程，这个结构体定义在 Python/compile.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 */
};

我们对其中几个字段比较感兴趣：

*c_st：指向之前生成的符号表。
*u：一个到 compiler unit 结构体的引用。这个结构体封装了与一个 code block 进行交互所需的信息。本字段指向目前正在处理的 code block 所对应的 compiler unit。
*c_stack：一个到 compiler unit 栈的引用。当一个 code block 由多个 code block 所组成时，这个字段负责当遇到一个新的 block 时 compiler unit 结构体的储存与恢复。当进入一个新的 code block 时，一个新的作用域被创建，然后 compiler_enter_scope() 会将当前的 compiler unit *u push 到栈中。同时 *c_stack 创建一个新的 compiler unit 对象并将其设置为当前compiler unit。当离开一个 block 的时候，*c_stack 会根据复原状态进行弹出。

对于每个被编译的模块，对应一个被初始化的 compiler 数据结构。当 AST 被遍历，其中每一个 code block 对应的 compiler_unit 数据结构会被生成。

1.3.6.2 compiler_unit 数据结构

compiler_unit 结构体的定义展示在下面的代码清单中，它持有生成一个 code block 对应的字节码指令所需的信息。当查看这个结构体的定义时会发现，很多字段的名字你可能会比较熟悉。

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 */
};

 
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 */
};

字段 u_blocks 与 u_curblock 用于引用那些组成被编译的 code block 的基础块。*u_ste 字段为到一个被编译的 code block 中的符号表项的引用。其余的字段从它们的名字上就比较容易理解。组成 code block 的不同节点在编译过程中会被遍历，并且根据一个节点类型是否能够起始一个 basic block，一个含有 node 对应指令的 basic block 会被创建，或者有新指令被添加到已有的 basic block 当中。能够起始一个 basic block 的节点类型包括但不限于：

函数节点
跳转目标
异常处理
布尔运算等

1.3.6.3 basic block 与 instruction 数据结构

basicblock_ 结构体是一种在 CFG 生成过程中相当有趣的数据结构。一个 basic block 是一个具有单一入口与多个出口的指令序列。在 CPython 中它的定义如下：

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;

x
 
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;

正如之前所说的，CFG 由一系列 basic blocks 以及它们之间的连接所组成。*b_instr 字段引用到一个指令结构体的数组，一个指令结构体对应于一条字节码指令，字节码指令的编号可在头文件 Include/opcode.h 中找到。指令结构体 instr 定义在文件 Python/compile.c 中。

 
struct instr {
    unsigned i_jabs : 1;   // 绝对跳转 jump absolute
    unsigned i_jrel : 1;   // 相对跳转 jump relative
    unsigned i_hasarg : 1;
    unsigned char i_opcode;
    int i_oparg;
    struct basicblock_ *i_target; /* target block (if jump instruction) */
    int i_lineno;
};

再回头看一下图1.3.6.b，我们可以看到由 block1 到 block2 存在两条可行的路径。第一条路径是正常执行由 block1 到 block2，第二条是在第一次比较时直接跳转到 block2 。目前这个跳转的目标时一个 basic block 但是 code object 在实际执行的时候对 basic block 并不知情。code object 中只有字节码流（bytecodes stream）并且我们只能通过偏移量对它进行索引。我们必须将使用 block 创建的隐式图作为跳转目标，并以某种方式将这些具有偏移的 block 替换为指令数组。这就是 basic blocks 的汇编（assembling）过程。

1.3.7 汇编 basic blocks

一旦 CFG 被生成，basic blocks 包含了字节码指令，但目前这些 blocks 还不是线性排列的。跳转指令的目标仍是 basic block 而不是指令流中的绝对偏移量。assemble 函数将会把 CFG 进行线性排列并生成 code object。

首先，assemble 函数会任何没有 return 语句的 block 的结尾添加一个 return None ，现在你知道为什么可以在函数和方法中不写 return 了吧。然后会以后序深度优先（post-order deep first）的方式遍历 CFG 图，以对它进行扁平化。后序遍历指的是在遍历时先访问所有的子节点再访问根节点。

图遍历：

Figure 3.5 : Depth first transversal of a graph start from root node A and moving to the left.

在对一个图进行后序深度优先遍历时，我们首先会递归地访问一个根结点的左子节点，然后是右子节点，然后才是这个根节点自己。比如以上面这个图结构作为例子，当我们以后序深度优先遍历对它进行扁平化的时候，对节点的访问顺序是：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 。

fizzbuzz 函数的 CFG （图1.3.6.b）相对比较简单，如果对它进行后序遍历，顺序是：block5 -> block4 -> block3 -> block2 -> block1 。当 CFG 被扁平化（或者说是线性化）以后，扁平化图的跳转指令的跳转偏移量就可以被 assemble_jump_offsets 函数计算出来了。

对跳转偏移量的汇编需要两个阶段，在第一个阶段，每条指令的偏移量会被计算出来放进指令数组中，就像下面的代码清单中所展示的那样。这是一个简单的循环，它从被 CFG 扁平化后得到的数组的末尾开始从 0 开始生成每一个 block 对应的偏移量。

 
        ...        
        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;
        }
        ...

在第二阶段，跳转指令的跳转目标偏移量被计算出来，这一步涉及到计算绝对跳转与相对跳转的跳转地址：

x
 
        ...
        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];
                /* Relative jumps are computed relative to
                   the instruction pointer after fetching
                   the jump instruction.
                */
                bsize += instrsize(instr);
                if (instr->i_jabs)  // 绝对跳转
                    instr->i_oparg = instr->i_target->b_offset;
                else if (instr->i_jrel) {  // 相对跳转
                    int delta = instr->i_target->b_offset - bsize;
                    instr->i_oparg = delta;
                }
                else
                    continue;
                if (instr->i_oparg > 0xffff)
                    extended_arg_count++;
            }
        }
        ...

随着跳转地址被计算，扁平化后的 CFG 内的指令以反向后序顺序（reverse post order）被生成。反向后序顺序是对 CFG 的拓扑排序，也就是说对于 CFG 中所有的边 (u, v)，在这个排序中 u 都会排在 v 前面。这样做的原因很明显，我们一般来说想要把跳转的起点放在终点之前。当字节码生成完毕，code object 对象就可以根据这些字节码以及符号表中的信息进行生成，code object 对象返回给调用函数的时候，整个编译过程就在此结束了。

其它资料：

一篇关于Py程序执行过程的博文： Python’s Innards: Introduction, Yaniv Aknin
Pycon 2012 video: Stepping Through CPython, Larry Hastings
Yet another guided tour of CPython, Guido Van
关于PEP554：Has the Python GIL been slain, Anthony Shaw
A Python Interpreter Written in Python, Allison Kaptur

后续内容的翻译将放在 GitBook 上并且使用 Python3.7 作为例子，欢迎贡献。