| Oct | NOV | Dec |
| 14 | ||
| 2019 | 2020 | 2021 |
●Python »
Python Developer's Guide »
Parser/tokenizer.c)
(二)Parse the stream of tokens into an Abstract Syntax Tree (Parser/parser.c)
(三)Transform AST into a Control Flow Graph (Python/compile.c)
(四)Emit bytecode based on the Control Flow Graph (Python/compile.c)
The purpose of this document is to outline how these steps of the process work.
This document does not touch on how parsing works beyond what is needed
to explain what is needed for compilation. It is also not exhaustive
in terms of the how the entire system works. You will most likely need
to read some source to have an exact understanding of all details.
Grammar/python.gram. The definitions for literal tokens
(such as :, numbers, etc.) can be found in Grammar/Tokens.
Various C files, including Parser/parser.c are generated from
these (see Changing CPython’s Grammar).
Parser/Python.asdl.
Each AST node (representing statements, expressions, and several
specialized types, like list comprehensions and exception handlers) is
defined by the ASDL. Most definitions in the AST correspond to a
particular source construct, such as an ‘if’ statement or an attribute
lookup. The definition is independent of its realization in any
particular programming language.
The following fragment of the Python ASDL construct demonstrates the
approach and syntax:
module Python
{
stmt = FunctionDef(identifier name, arguments args, stmt* body,
expr* decorators)
| Return(expr? value) | Yield(expr? value)
attributes (int lineno)
}
The preceding example describes two different kinds of statements and an
expression: function definitions, return statements, and yield expressions.
All three kinds are considered of type stmt as shown by | separating
the various kinds. They all take arguments of various kinds and amounts.
Modifiers on the argument type specify the number of values needed; ?
means it is optional, * means 0 or more, while no modifier means only one
value for the argument and it is required. FunctionDef, for instance,
takes an identifier for the name, arguments for args, zero or more
stmt arguments for body, and zero or more expr arguments for
decorators.
Do notice that something like ‘arguments’, which is a node type, is
represented as a single AST node and not as a sequence of nodes as with
stmt as one might expect.
All three kinds also have an ‘attributes’ argument; this is shown by the
fact that ‘attributes’ lacks a ‘|’ before it.
The statement definitions above generate the following C structure type:
typedef struct _stmt *stmt_ty; struct _stmt { enum { FunctionDef_kind=1, Return_kind=2, Yield_kind=3 } kind; union { struct { identifier name; arguments_ty args; asdl_seq *body; } FunctionDef; struct { expr_ty value; } Return; struct { expr_ty value; } Yield; } v; int lineno; }Also generated are a series of constructor functions that allocate (in this case) a
stmt_ty struct with the appropriate initialization. The
kind field specifies which component of the union is initialized. The
FunctionDef() constructor function sets ‘kind’ to FunctionDef_kind and
initializes the name, args, body, and attributes fields.
Include/pyarena.horPython/pyarena.c.
PyArena_New() will create a new arena. The returned PyArena structure
will store pointers to all memory given to it. This does the bookkeeping of
what memory needs to be freed when the compiler is finished with the memory it
used. That freeing is done with PyArena_Free(). This only needs to be
called in strategic areas where the compiler exits.
As stated above, in general you should not have to worry about memory
management when working on the compiler. The technical details have been
designed to be hidden from you for most cases.
The only exception comes about when managing a PyObject. Since the rest
of Python uses reference counting, there is extra support added
to the arena to cleanup each PyObject that was allocated. These cases
are very rare. However, if you’ve allocated a PyObject, you must tell
the arena about it by calling PyArena_AddPyObject().
Python/ast.c) using the
function PyAST_FromNode().
The function begins a tree walk of the parse tree, creating various AST
nodes as it goes along. It does this by allocating all new nodes it
needs, calling the proper AST node creation functions for any required
supporting functions, and connecting them as needed.
Do realize that there is no automated nor symbolic connection between
the grammar specification and the nodes in the parse tree. No help is
directly provided by the parse tree as in yacc.
For instance, one must keep track of which node in the parse tree
one is working with (e.g., if you are working with an ‘if’ statement
you need to watch out for the ‘:’ token to find the end of the conditional).
The functions called to generate AST nodes from the parse tree all have
the name ast_for_xx where xxis the grammar rule that the function
handles (alias_for_import_name is the exception to this). These in turn
call the constructor functions as defined by the ASDL grammar and
contained in Python/Python-ast.c (which was generated by
Parser/asdl_c.py) to create the nodes of the AST. This all leads to a
sequence of AST nodes stored in asdl_seq structs.
Function and macros for creating and using asdl_seq * types as found
in Python/asdl.c and Include/asdl.h are as follows:
_Py_asdl_seq_new(Py_ssize_t, PyArena *)
Allocate memory for an asdl_seq for the specified length
asdl_seq_GET(asdl_seq *, int)
Get item held at a specific position in an asdl_seq
asdl_seq_SET(asdl_seq *, int, stmt_ty)
Set a specific index in an asdl_seq to the specified value
asdl_seq_LEN(asdl_seq *)
Return the length of an asdl_seq
If you are working with statements, you must also worry about keeping
track of what line number generated the statement. Currently the line
number is passed as the last parameter to each stmt_ty function.
NULL), each of which are
their own basic blocks. Both of those blocks in turn point to the
basic block representing the code following the entire ‘if’ statement.
CFGs are usually one step away from final code output. Code is directly
generated from the basic blocks (with jump targets adjusted based on the
output order) by doing a post-order depth-first search on the CFG
following the edges.
PyAST_CompileObject()inPython/compile.c. This function does both the
conversion of the AST to a CFG and outputting final bytecode from the CFG.
The AST to CFG step is handled mostly by two functions called by
PyAST_CompileObject(); PySymtable_BuildObject() and compiler_mod(). The former
is in Python/symtable.c while the latter is in Python/compile.c.
PySymtable_BuildObject() begins by entering the starting code block for the
AST (passed-in) and then calling the proper symtable_visit_xx function
(with xxbeing the AST node type). Next, the AST tree is walked with
the various code blocks that delineate the reach of a local variable
as blocks are entered and exited using symtable_enter_block() and
symtable_exit_block(), respectively.
Once the symbol table is created, it is time for CFG creation, whose
code is in Python/compile.c. This is handled by several functions
that break the task down by various AST node types. The functions are
all named compiler_visit_xx where xxis the name of the node type (such
as stmt, expr, etc.). Each function receives a struct compiler *
and xx_ty where xxis the AST node type. Typically these functions
consist of a large ‘switch’ statement, branching based on the kind of
node type passed to it. Simple things are handled inline in the
‘switch’ statement with more complex transformations farmed out to other
functions named compiler_xx with xxbeing a descriptive name of what is
being handled.
When transforming an arbitrary AST node, use the VISIT() macro.
The appropriate compiler_visit_xx function is called, based on the value
passed in for <node type> (soVISIT(c, expr, node) calls
compiler_visit_expr(c, node)). The VISIT_SEQ() macro is very similar,
but is called on AST node sequences (those values that were created as
arguments to a node that used the ‘*’ modifier). There is also
VISIT_SLICE() just for handling slices.
Emission of bytecode is handled by the following macros:
ADDOP(struct compiler *, int)
add a specified opcode
ADDOP_I(struct compiler *, int, Py_ssize_t)
add an opcode that takes an integer argument
ADDOP_O(struct compiler *, int, PyObject *, TYPE)
add an opcode with the proper argument based on the position of the
specified PyObject in PyObject sequence object, but with no handling of
mangled names; used for when you
need to do named lookups of objects such as globals, consts, or
parameters where name mangling is not possible and the scope of the
name is known; TYPE is the name of PyObject sequence
(namesorvarnames)
ADDOP_N(struct compiler *, int, PyObject *, TYPE)
just like ADDOP_O, but steals a reference to PyObject
ADDOP_NAME(struct compiler *, int, PyObject *, TYPE)
just like ADDOP_O, but name mangling is also handled; used for
attribute loading or importing based on name
ADDOP_LOAD_CONST(struct compiler *, PyObject *)
add the LOAD_CONST opcode with the proper argument based on the
position of the specified PyObject in the consts table.
ADDOP_LOAD_CONST_NEW(struct compiler *, PyObject *)
just like ADDOP_LOAD_CONST_NEW, but steals a reference to PyObject
ADDOP_JABS(struct compiler *, int, basicblock *)
create an absolute jump to a basic block
ADDOP_JREL(struct compiler *, int, basicblock *)
create a relative jump to a basic block
Several helper functions that will emit bytecode and are named
compiler_xx() where xxis what the function helps with (list,
boolop, etc.). A rather useful one is compiler_nameop().
This function looks up the scope of a variable and, based on the
expression context, emits the proper opcode to load, store, or delete
the variable.
As for handling the line number on which a statement is defined, this is
handled by compiler_visit_stmt() and thus is not a worry.
In addition to emitting bytecode based on the AST node, handling the
creation of basic blocks must be done. Below are the macros and
functions used for managing basic blocks:
NEXT_BLOCK(struct compiler *)
create an implicit jump from the current block
to the new block
compiler_new_block(struct compiler *)
create a block but don’t use it (used for generating jumps)
compiler_use_next_block(struct compiler *, basicblock *block)
set a previously created block as a current block
Once the CFG is created, it must be flattened and then final emission of
bytecode occurs. Flattening is handled using a post-order depth-first
search. Once flattened, jump offsets are backpatched based on the
flattening and then a PyCodeObject is created. All of this is
handled by calling assemble().
Lib/opcode.py. If the opcode is to
take an argument, it must be given a unique number greater than that assigned to
HAVE_ARGUMENT (as found in Lib/opcode.py).
Once the name/number pair has been chosen and entered in Lib/opcode.py,
you must also enter it into Doc/library/dis.rst, and regenerate
Include/opcode.h and Python/opcode_targets.h by running
make regen-opcode regen-opcode-targets.
With a new bytecode you must also change what is called the magic number for
.pyc files. The variable MAGIC_NUMBERinLib/importlib/_bootstrap_external.py contains the number.
Changing this number will lead to all .pyc files with the old MAGIC_NUMBER
to be recompiled by the interpreter on import. Whenever MAGIC_NUMBER is
changed, the ranges in the magic_values array in PC/launcher.c
must also be updated. Changes to Lib/importlib/_bootstrap_external.py
will take effect only after running make regen-importlib. Running this
command before adding the new bytecode target to Python/ceval.c will
result in an error. You should only run make regen-importlib after the new
bytecode target has been added.
Finally, you need to introduce the use of the new bytecode. Altering
Python/compile.c and Python/ceval.c will be the primary places
to change. You must add the case for a new opcode into the ‘switch’
statement in the stack_effect() function in Python/compile.c.
If the new opcode has a jump target, you will need to update macros and
‘switch’ statements in Python/peephole.c. If it affects a control
flow or the block stack, you may have to update the frame_setlineno()
function in Objects/frameobject.c. Lib/dis.py may need
an update if the new opcode interprets its argument in a special way (like
FORMAT_VALUEorMAKE_FUNCTION).
If you make a change here that can affect the output of bytecode that
is already in existence and you do not change the magic number constantly, make
sure to delete your old .py(c|o) files! Even though you will end up changing
the magic number if you change the bytecode, while you are debugging your work
you will be changing the bytecode output without constantly bumping up the
magic number. This means you end up with stale .pyc files that will not be
recreated.
Running find . -name '*.py[co]' -exec rm-f '{}' + should delete all .pyc
files you have, forcing new ones to be created and thus allow you test out your
new bytecode properly. Run make regen-importlib for updating the
bytecode of frozen importlib files. You have to run make again after this
for recompiling generated C files.
PyAST_CompileObject() is a PyCodeObject which is defined in
Include/code.h. And with that you now have executable Python bytecode!
The code objects (byte code) are executed in Python/ceval.c. This file
will also need a new case statement for the new opcode in the big switch
statement in _PyEval_EvalFrameDefault().
Python/Python-ast.c and Include/Python-ast.h.
Python/
Python-ast.c
Creates C structs corresponding to the ASDL types. Also
contains code for marshalling AST nodes (core ASDL types have
marshalling code in asdl.c). “File automatically generated by
Parser/asdl_c.py”. This file must be committed separately
after every grammar change is committed since the __version__
value is set to the latest grammar change revision number.
asdl.c
Contains code to handle the ASDL sequence type. Also has code
to handle marshalling the core ASDL types, such as number and
identifier. Used by Python-ast.c for marshalling AST nodes.
ast.c
Converts Python’s parse tree into the abstract syntax tree.
ast_opt.c
Optimizes the AST.
ast_unparse.c
Converts the AST expression node back into a string
(for string annotations).
ceval.c
Executes byte code (aka, eval loop).
compile.c
Emits bytecode based on the AST.
symtable.c
Generates a symbol table from AST.
peephole.c
Optimizes the bytecode.
pyarena.c
Implementation of the arena memory manager.
wordcode_helpers.h
Helpers for generating bytecode.
opcode_targets.h
One of the files that must be modified if Lib/opcode.py is.
Include/
Python-ast.h
Contains the actual definitions of the C structs as generated by
Python/Python-ast.c.
“Automatically generated by Parser/asdl_c.py”.
asdl.h
Header for the corresponding Python/ast.c.
ast.h
Declares PyAST_FromNode() external (from Python/ast.c).
code.h
Header file for Objects/codeobject.c; contains definition of
PyCodeObject.
symtable.h
Header for Python/symtable.c. struct symtable and
PySTEntryObject are defined here.
pyarena.h
Header file for the corresponding Python/pyarena.c.
opcode.h
One of the files that must be modified if Lib/opcode.py is.
Objects/
codeobject.c
Contains PyCodeObject-related code (originally in
Python/compile.c).
frameobject.c
Contains the frame_setlineno() function which should determine
whether it is allowed to make a jump between two points in a bytecode.
Lib/
opcode.py
Master list of bytecode; if this file is modified you must modify
several other files accordingly (see “Introducing New Bytecode”)
importlib/_bootstrap_external.py
Home of the magic number (named MAGIC_NUMBER) for bytecode
versioning.
LOAD_ATTR/CALL_FUNCTION was
created named CALL_ATTR [3]. Currently only works for classic
classes and for new-style classes rough benchmarking showed an actual slowdown
thanks to having to support both classic and new-style classes.
| [Wang97] | Daniel C. Wang, Andrew W. Appel, Jeff L. Korn, and Chris S. Serra. The Zephyr Abstract Syntax Description Language. In Proceedings of the Conference on Domain-Specific Languages, pp. 213–227, 1997. |
| [1] | Skip Montanaro’s Peephole Optimizer Paper (https://drive.google.com/open?id=0B2InO7qBBGRXQXlDM3FVdWZxQWc) |
| [2] | Bytecodehacks Project (http://bytecodehacks.sourceforge.net/bch-docs/bch/index.html) |
| [3] | CALL_ATTR opcode (https://bugs.python.org/issue709744) |
●Python »
Python Developer's Guide »