Bring compiler docs up to speed with Python 3.10 (python#706)

Fidget-Spinner · web-flow · commit d84dd7a9b0b2 · 2021-05-24T23:29:33.000+01:00
diff --git a/compiler.rst b/compiler.rst
@@ -139,8 +139,8 @@ that is needed to completely free all memory used by the compiler.
 In general, unless you are working on the critical core of the compiler, memory
 management can be completely ignored.  But if you are working at either the
 very beginning of the compiler or the end, you need to care about how the arena
-works.  All code relating to the arena is in either :file:`Include/pyarena.h` or
-:file:`Python/pyarena.c`.
+works.  All code relating to the arena is in either
+:file:`Include/Internal/pycore_pyarena.h` or :file:`Python/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
@@ -159,49 +159,131 @@ are very rare.  However, if you've allocated a PyObject, you must tell
 the arena about it by calling ``PyArena_AddPyObject()``.
 
 
-Parse Tree to AST
------------------
+Source Code to AST
+------------------
+
+The AST is generated from source code using the function
+``_PyParser_ASTFromString()`` or ``_PyParser_ASTFromFile()``
+(from :file:`Parser/peg_api.c`) depending on the input type.
+
+After some checks, a helper function in :file:`Parser/parser.c` begins applying
+production rules on the source code it receives; converting source code to
+tokens and matching these tokens recursively to their corresponding rule.  The
+rule's corresponding rule function is called on every match.  These rule
+functions follow the format :samp:`xx_rule`.  Where *xx* is the grammar rule
+that the function handles and is automatically derived from
+:file:`Grammar/python.gram` by :file:`Tools/peg_generator/pegen/c_generator.py`.
+
+Each rule function in turn creates an AST node as it goes along.  It does this
+by allocating all the new nodes it needs, calling the proper AST node creation
+functions for any required supporting functions and connecting them as needed.
+This continues until all nonterminal symbols are replaced with terminals.  If an
+error occurs, the rule functions backtrack and try another rule function.  If
+there are no more rules, an error is set and the parsing ends.
+
+The AST node creation helper functions have the name :samp:`_PyAST_{xx}`
+where *xx* is the AST node that the function creates.  These are defined by the
+ASDL grammar and contained in :file:`Python/Python-ast.c` (which is generated by
+:file:`Parser/asdl_c.py` from :file:`Parser/Python.asdl`).  This all leads to a
+sequence of AST nodes stored in ``asdl_seq`` structs.
+
+To demonstrate everything explained so far, here's the
+rule function responsible for a simple named import statement such as
+``import sys``.  Note that error-checking and debugging code has been
+omitted.  Removed parts are represented by ``...``.
+Furthermore, some comments have been added for explanation.  These comments
+may not be present in the actual code.
+
+.. code-block:: c
 
-The AST is generated from the parse tree (see :file:`Python/ast.c`) using the
-function ``PyAST_FromNode()``.
+   // This is the production rule (from python.gram) the rule function
+   // corresponds to:
+   // import_name: 'import' dotted_as_names
+   static stmt_ty
+   import_name_rule(Parser *p)
+   {
+       ...
+       stmt_ty _res = NULL;
+       { // 'import' dotted_as_names
+           ...
+           Token * _keyword;
+           asdl_alias_seq* a;
+           // The tokenizing steps.
+           if (
+               (_keyword = _PyPegen_expect_token(p, 513))  // token='import'
+               &&
+               (a = dotted_as_names_rule(p))  // dotted_as_names
+           )
+           {
+               ...
+               // Generate an AST for the import statement.
+               _res = _PyAST_Import ( a , ...);
+               ...
+               goto done;
+           }
+           ...
+       }
+       _res = NULL;
+     done:
+       ...
+       return _res;
+   }
 
-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.
+To improve backtracking performance, some rules (chosen by applying a
+``(memo)`` flag in the grammar file) are memoized.  Each rule function checks if
+a memoized version exists and returns that if so, else it continues in the
+manner stated in the previous paragraphs.
 
-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).
+There are macros for creating and using ``asdl_xx_seq *`` types, where *xx* is
+a type of the ASDL sequence.  Three main types are defined
+manually -- ``generic``, ``identifier`` and ``int``.  These types are found in
+:file:`Python/asdl.c` and its corresponding header file
+:file:`Include/Internal/pycore_asdl.h`.  Functions and macros
+for creating ``asdl_xx_seq *`` types are as follows:
 
-The functions called to generate AST nodes from the parse tree all have
-the name :samp:`ast_for_{xx}` where *xx* is 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 :file:`Python/Python-ast.c` (which was generated by
-:file:`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.
+``_Py_asdl_generic_seq_new(Py_ssize_t, PyArena *)``
+        Allocate memory for an ``asdl_int_seq`` of the specified length
+``_Py_asdl_identifier_seq_new(Py_ssize_t, PyArena *)``
+        Allocate memory for an ``asdl_identifier_seq`` of the specified length
+``_Py_asdl_int_seq_new(Py_ssize_t, PyArena *)``
+        Allocate memory for an ``asdl_generic_seq`` of the specified length
 
-Function and macros for creating and using ``asdl_seq *`` types as found
-in :file:`Python/asdl.c` and :file:`Include/asdl.h` are as follows:
+In addition to the three types mentioned above, some ASDL sequence types are
+automatically generated by :file:`Parser/asdl_c.py` and found in
+:file:`Include/Internal/pycore_ast.h`.  Macros for using both manually defined
+and automatically generated ASDL sequence types 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)``
+``asdl_seq_GET(asdl_xx_seq *, int)``
+        Get item held at a specific position in an ``asdl_xx_seq``
+``asdl_seq_SET(asdl_xx_seq *, int, stmt_ty)``
+        Set a specific index in an ``asdl_xx_seq`` to the specified value
+
+Untyped counterparts exist for some of the typed macros.  These are useful
+when a function needs to manipulate a generic ASDL sequence:
+
+``asdl_seq_GET_UNTYPED(asdl_seq *, int)``
         Get item held at a specific position in an ``asdl_seq``
-``asdl_seq_SET(asdl_seq *, int, stmt_ty)``
+``asdl_seq_SET_UNTYPED(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``
+        Return the length of an ``asdl_seq`` or ``asdl_xx_seq``
+
+Note that typed macros and functions are recommended over their untyped
+counterparts.  Typed macros carry out checks in debug mode and aid
+debugging errors caused by incorrectly casting from ``void *``.
 
 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.
 
+.. versionchanged:: 3.9
+   The new PEG parser generates an AST directly without creating a
+   parse tree. ``Python/ast.c`` is now only used to validate the AST for
+   debugging purposes.
+
+.. seealso:: :pep:`617` (PEP 617 -- New PEG parser for CPython)
+
 
 Control Flow Graphs
 -------------------
@@ -248,13 +330,13 @@ global).  With that done, the second pass essentially flattens the CFG
 into a list and calculates jump offsets for final output of bytecode.
 
 The conversion process is initiated by a call to the function
-``PyAST_CompileObject()`` in :file:`Python/compile.c`.  This function does both the
+``_PyAST_Compile()`` in :file:`Python/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
+``_PyAST_Compile()``; ``_PySymtable_Build()`` and ``compiler_mod()``.  The former
 is in :file:`Python/symtable.c` while the latter is in :file:`Python/compile.c`.
 
-``PySymtable_BuildObject()`` begins by entering the starting code block for the
+``_PySymtable_Build()`` begins by entering the starting code block for the
 AST (passed-in) and then calling the proper :samp:`symtable_visit_{xx}` function
 (with *xx* being the AST node type).  Next, the AST tree is walked with
 the various code blocks that delineate the reach of a local variable
@@ -369,6 +451,9 @@ command before adding the new bytecode target to :file:`Python/ceval.c` will
 result in an error. You should only run ``make regen-importlib`` after the new 
 bytecode target has been added.
 
+.. note:: On Windows, running the ``./build.bat`` script will automatically
+   regenerate the required files without requiring additional arguments.
+
 Finally, you need to introduce the use of the new bytecode.  Altering
 :file:`Python/compile.c` and :file:`Python/ceval.c` will be the primary places
 to change. You must add the case for a new opcode into the 'switch'
@@ -419,7 +504,28 @@ Important Files
 
     asdl_c.py
         "Generate C code from an ASDL description."  Generates
-        :file:`Python/Python-ast.c` and :file:`Include/Python-ast.h`.
+        :file:`Python/Python-ast.c` and :file:`Include/Internal/pycore_ast.h`.
+
+    parser.c
+        The new PEG parser introduced in Python 3.9.
+        Generated by :file:`Tools/peg_generator/pegen/c_generator.py`
+        from the grammar :file:`Grammar/python.gram`.  Creates the AST from
+        source code.  Rule functions for their corresponding production rules
+        are found here.
+
+    peg_api.c
+        Contains high-level functions which are used by the interpreter to
+        create an AST from source code .
+
+    pegen.c
+        Contains helper functions which are used by functions in
+        :file:`Parser/parser.c` to construct the AST.  Also contains helper
+        functions which help raise better error messages when parsing source
+        code.
+
+    pegen.h
+        Header file for the corresponding :file:`Parser/pegen.c`. Also contains
+        definitions of the ``Parser`` and ``Token`` structs.
 
 + Python/
 
@@ -437,7 +543,7 @@ Important Files
         identifier.  Used by :file:`Python-ast.c` for marshalling AST nodes.
 
     ast.c
-        Converts Python's parse tree into the abstract syntax tree.
+        Used for validating the AST.
 
     ast_opt.c
         Optimizes the AST.
@@ -469,31 +575,37 @@ Important Files
 
 + Include/
 
-    Python-ast.h
-        Contains the actual definitions of the C structs as generated by
-        :file:`Python/Python-ast.c`.
-        "Automatically generated by :file:`Parser/asdl_c.py`".
-
-    asdl.h
-        Header for the corresponding :file:`Python/ast.c`.
-
-    ast.h
-        Declares ``PyAST_FromNode()`` external (from :file:`Python/ast.c`).
-
     code.h
         Header file for :file:`Objects/codeobject.c`; contains definition of
         ``PyCodeObject``.
 
-    symtable.h
-        Header for :file:`Python/symtable.c`.  ``struct symtable`` and
-        ``PySTEntryObject`` are defined here.
-
-    pyarena.h
-        Header file for the corresponding :file:`Python/pyarena.c`.
-
     opcode.h
         One of the files that must be modified if :file:`Lib/opcode.py` is.
 
+    + Internal/
+
+        pycore_ast.h
+            Contains the actual definitions of the C structs as generated by
+            :file:`Python/Python-ast.c`.
+            "Automatically generated by :file:`Parser/asdl_c.py`".
+
+        pycore_asdl.h
+            Header for the corresponding :file:`Python/ast.c`
+
+        pycore_ast.h
+            Declares ``_PyAST_Validate()`` external (from :file:`Python/ast.c`).
+
+        pycore_symtable.h
+            Header for :file:`Python/symtable.c`.  ``struct symtable`` and
+            ``PySTEntryObject`` are defined here.
+
+        pycore_parser.h
+            Header for the corresponding :file:`Parser/peg_api.c`.
+
+        pycore_pyarena.h
+            Header file for the corresponding :file:`Python/pyarena.c`.
+
+
 + Objects/
 
     codeobject.c
