CPython源码阅读笔记(1)

./configure --with-pydebug

make -j2

// Modules/python.c
#include "Python.h"

int
main(int argc, char **argv)
{
	return Py_Main(argc, argv);
}

// Python/pythonrun.c PyRun_StringFlags
PyObject *
PyRun_StringFlags(const char *str, int start, PyObject *globals,
                  PyObject *locals, PyCompilerFlags *flags)
{
    PyObject *ret = NULL;
    mod_ty mod;
    PyArena *arena = PyArena_New(); /* 为编译阶段申请一块内存池 */
    if (arena == NULL)
        return NULL;

    mod = PyParser_ASTFromString(str, "<string>", start, flags, arena); /* 将语句解析为 AST */
    if (mod != NULL)
        ret = run_mod(mod, "<string>", globals, locals, flags, arena); /* 调用 run_mod */
    PyArena_Free(arena);
    return ret;
}

// Python/pythonrun.c 54 行 引用了 graminit 中的 grammar 结构，该结构将在下面几个函数中以 `g` 变量名传递 
extern grammar _PyParser_Grammar; /* From graminit.c */ 
// Python/pythonrun.c PyParser_ASTFromString
mod_ty
PyParser_ASTFromString(const char *s, const char *filename, int start,
                       PyCompilerFlags *flags, PyArena *arena)
{
    mod_ty mod;
    PyCompilerFlags localflags;
    perrdetail err;
    int iflags = PARSER_FLAGS(flags);

    // 将源码解析为了 Parser Tree
    node *n = PyParser_ParseStringFlagsFilenameEx(s, filename,
                                    &_PyParser_Grammar, start, &err,
                                    &iflags);
    if (flags == NULL) {
        localflags.cf_flags = 0;
        flags = &localflags;
    }
    if (n) {
        flags->cf_flags |= iflags & PyCF_MASK;
        // 将 Parser Tree 转换为 AST
        mod = PyAST_FromNode(n, flags, filename, arena);
        PyNode_Free(n);
        return mod; // 返回 AST
    }
    else {
        err_input(&err);
        return NULL;
    }
}

// Parser/parsetok.c PyParser_ParseStringFlagsFilenameEx
node *
PyParser_ParseStringFlagsFilenameEx(const char *s, const char *filename,
                          grammar *g, int start,
                          perrdetail *err_ret, int *flags)
{
    struct tok_state *tok;

    initerr(err_ret, filename);
    // 初始化词法分析模块
    if ((tok = PyTokenizer_FromString(s, start == file_input)) == NULL) {
        err_ret->error = PyErr_Occurred() ? E_DECODE : E_NOMEM;
        return NULL;
    }

    tok->filename = filename ? filename : "<string>";
    if (Py_TabcheckFlag || Py_VerboseFlag) {
        tok->altwarning = (tok->filename != NULL);
        if (Py_TabcheckFlag >= 2)
            tok->alterror++;
    }
    // 调用 parsetok ，将源码转换为 token 序列
    return parsetok(tok, g, start, err_ret, flags);

// Parser/parsetok.c parsetok
static node *
parsetok(struct tok_state *tok, grammar *g, int start, perrdetail *err_ret,
         int *flags)
{
    // 初始化 parser 
    if ((ps = PyParser_New(g, start)) == NULL) {
    ....
    // 获取 token type
    type = PyTokenizer_Get(tok, &a, &b);
    ....
    // 将 token 赋值给 str
    len = b - a; /* XXX this may compute NULL - NULL */
    str = (char *) PyObject_MALLOC(len + 1);
    if (len > 0)
        strncpy(str, a, len);
    str[len] = '\0';
    ....
    // 将 token 添加到 parser tree 中
    if ((err_ret->error =
             PyParser_AddToken(ps, (int)type, str, tok->lineno, col_offset,
                               &(err_ret->expected))) != E_OK) {
            if (err_ret->error != E_DONE) {
                PyObject_FREE(str);
                err_ret->token = type;
            }
            break;
        }
    ....
    if (err_ret->error == E_DONE) {
        n = ps->p_tree;
        ps->p_tree = NULL;
    }
    else
        n = NULL;
    ....
    done:
        PyTokenizer_Free(tok); // 释放词法分析器
    return n; // 返回 parser->p_tree
}

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

./Python-2.7.12/python -d -c 'a = 1'
Token NAME/'a' ... It's a token we know
....
 DFA 'atom', state 0: Shift.
  DFA 'atom', state 5: Direct pop.
Token EQUAL/'=' ... It's a token we know
....
 DFA 'expr_stmt', state 1: Shift.
Token NUMBER/'1' ... It's a token we know
....
  DFA 'atom', state 5: Direct pop.
Token NEWLINE/'' ... It's a token we know
....
  DFA 'simple_stmt', state 3: Direct pop.
  DFA 'stmt', state 1: Direct pop.
Token NEWLINE/'' ... It's a token we know
 DFA 'file_input', state 0: Shift.
Token ENDMARKER/'' ... It's a token we know
 DFA 'file_input', state 0: Shift.
  DFA 'file_input', state 1: Direct pop.
  ACCEPT.
[35150 refs]

// Parser/parser.c PyParser_AddToken
int
PyParser_AddToken(register parser_state *ps, register int type, char *str,
                  int lineno, int col_offset, int *expected_ret)
{
    ...
    /* Loop until the token is shifted or an error occurred */
    for (;;) {
        ...
        /* Pop while we are in an accept-only state */
                while (s = &d->d_state
                                [ps->p_stack.s_top->s_state],
                    s->s_accept && s->s_narcs == 1) {
                    D(printf("  DFA '%s', state %d: "
                             "Direct pop.\n",
                             d->d_name,
                             ps->p_stack.s_top->s_state));
        ...
    }
}

// ast.c PyAST_FromNode
mod_ty
PyAST_FromNode(const node *n, PyCompilerFlags *flags, const char *filename,
               PyArena *arena)
{
    ...
    stmts = asdl_seq_new(num_stmts(n), arena); /* 为 AST 申请内存 */
    if (!stmts)
        return NULL;
    for (i = 0; i < NCH(n) - 1; i++) {
        ch = CHILD(n, i);
        if (TYPE(ch) == NEWLINE)
            continue;
        REQ(ch, stmt);
        num = num_stmts(ch);
        if (num == 1) {
            s = ast_for_stmt(&c, ch); /* 生成对应的 AST Node */
            if (!s)
                goto error;
            asdl_seq_SET(stmts, k++, s); /* 将对应的 AST Node 设置到 asdl_seq 中对应的位置 */
        }
        ...
        return Module(stmts, arena); /* 转换 asdl_seq 为 mod_ty， mod_ty 事实上只是一个对
                                        asdl_seq 的简单封装，给 asdl_seq 加上了类型而已 */
    }
    ...
}

/* It would be nice if the code generated by asdl_c.py was completely
   independent of Python, but it is a goal the requires too much work
   at this stage.  So, for example, I'll represent identifiers as
   interned Python strings.
*/

/* XXX A sequence should be typed so that its use can be typechecked. */

typedef struct {
    int size;
    void *elements[1];
} asdl_seq;

import ast
t = ast.parse('a = 1')
ast.dump(t)

>>> "Module(body=[Assign(targets=[Name(id='a', ctx=Store())], value=Num(n=1))])"

// Python/pythonrun.c run_mod
static PyObject *
run_mod(mod_ty mod, const char *filename, PyObject *globals, PyObject *locals,
         PyCompilerFlags *flags, PyArena *arena)
{
    PyCodeObject *co;
    PyObject *v;
    co = PyAST_Compile(mod, filename, flags, arena);
    if (co == NULL)
        return NULL;
    v = PyEval_EvalCode(co, globals, locals);
    Py_DECREF(co);
    return v;
}

// Python/compile.c PyAST_Compile
PyCodeObject *
PyAST_Compile(mod_ty mod, const char *filename, PyCompilerFlags *flags,
              PyArena *arena)
{
    struct compiler c; // 初始化 compiler 结构
    PyCodeObject *co = NULL;
    PyCompilerFlags local_flags;
    ...

    if (!compiler_init(&c))
        return NULL;
    c.c_filename = filename;
    c.c_arena = arena;
    c.c_future = PyFuture_FromAST(mod, filename);
    ...

    c.c_st = PySymtable_Build(mod, filename, c.c_future);

    co = compiler_mod(&c, mod);

 finally:
    compiler_free(&c);
    assert(co || PyErr_Occurred());
    return co;
}

struct symtable {
    const char *st_filename; /* name of file being compiled */
    struct _symtable_entry *st_cur; /* current symbol table entry */
    struct _symtable_entry *st_top; /* module entry */
    PyObject *st_symbols;    /* dictionary of symbol table entries */
    PyObject *st_stack;      /* stack of namespace info */
    PyObject *st_global;     /* borrowed ref to MODULE in st_symbols */
    int st_nblocks;          /* number of blocks */
    PyObject *st_private;        /* name of current class or NULL */
    PyFutureFeatures *st_future; /* module's future features */
};

typedef struct _symtable_entry {
    PyObject_HEAD
    PyObject *ste_id;        /* int: key in st_symbols */
    PyObject *ste_symbols;   /* dict: name to flags */
    PyObject *ste_name;      /* string: name of block */
    PyObject *ste_varnames;  /* list of variable names */
    PyObject *ste_children;  /* list of child ids */
    _Py_block_ty ste_type;   /* module, class, or function */
    int ste_unoptimized;     /* false if namespace is optimized */
    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 */
    int ste_lineno;          /* first line of block */
    int ste_opt_lineno;      /* lineno of last exec or import * */
    int ste_tmpname;         /* counter for listcomp temp vars */
    struct symtable *ste_table;
} PySTEntryObject;

// Python/compiler.c compiler_mod 
static PyCodeObject *
compiler_mod(struct compiler *c, mod_ty mod)
{
    PyCodeObject *co;
    int addNone = 1;
    ...
    if (!compiler_enter_scope(c, module, mod, 0))
        return NULL;
    switch (mod->kind) {
    case Module_kind:
        if (!compiler_body(c, mod->v.Module.body)) {
            compiler_exit_scope(c);
            return 0;
        }
        break;
    ...
    }
    co = assemble(c, addNone);
    compiler_exit_scope(c);
    return co;
}

// Python/compiler.c compiler_body
static int
compiler_body(struct compiler *c, asdl_seq *stmts)
{
    ...
    for (; i < asdl_seq_LEN(stmts); i++)
        VISIT(c, stmt, (stmt_ty)asdl_seq_GET(stmts, i));
    ...
}

#define VISIT(C, TYPE, V) {\
    if (!compiler_visit_ ## TYPE((C), (V))) \
        return 0; \
}

// Python/compiler.c compiler_visit_stmt
static int
compiler_visit_stmt(struct compiler *c, stmt_ty s)
{
    ...
    switch (s->kind) {
        case Assign_kind:
            n = asdl_seq_LEN(s->v.Assign.targets);
            VISIT(c, expr, s->v.Assign.value);
            for (i = 0; i < n; i++) {
                if (i < n - 1)
                    ADDOP(c, DUP_TOP);
                VISIT(c, expr,
                    (expr_ty)asdl_seq_GET(s->v.Assign.targets, i));
            }
            break;
    }
    ...
}

>> p e.kind
$2 = Num_kind

// Python/compiler.c compiler_visit_expr
static int
compiler_visit_expr(struct compiler *c, expr_ty e)
{
    switch (e->kind) {
        case Num_kind:
        ADDOP_O(c, LOAD_CONST, e->v.Num.n, consts);
        break;
    }
}

// 添加一个 opcode
#define ADDOP(C, OP) { \
    if (!compiler_addop((C), (OP))) \
        return 0; \
}


#define ADDOP_IN_SCOPE(C, OP) { \
    if (!compiler_addop((C), (OP))) { \
        compiler_exit_scope(c); \
        return 0; \
    } \
}

// 添加一个 opcode ，带一个没有具体名字的参数，`a=1` 中的 value(Num(1))
#define ADDOP_O(C, OP, O, TYPE) { \
    if (!compiler_addop_o((C), (OP), (C)->u->u_ ## TYPE, (O))) \
        return 0; \
}

// 添加一个 opcode， 带一个有名字的参数，如变量名
#define ADDOP_NAME(C, OP, O, TYPE) { \
    if (!compiler_addop_name((C), (OP), (C)->u->u_ ## TYPE, (O))) \
        return 0; \
}

#define ADDOP_I(C, OP, O) { \
    if (!compiler_addop_i((C), (OP), (O))) \
        return 0; \
}

#define ADDOP_JABS(C, OP, O) { \
    if (!compiler_addop_j((C), (OP), (O), 1)) \
        return 0; \
}

#define ADDOP_JREL(C, OP, O) { \
    if (!compiler_addop_j((C), (OP), (O), 0)) \
        return 0; \
}

/* Add an opcode with an integer argument.
   Returns 0 on failure, 1 on success.
*/
static int
compiler_addop_i(struct compiler *c, int opcode, int oparg)
{
    struct instr *i;
    int off;
    off = compiler_next_instr(c, c->u->u_curblock);
    if (off < 0)
        return 0;
    i = &c->u->u_curblock->b_instr[off];
    i->i_opcode = opcode;
    i->i_oparg = oparg;
    i->i_hasarg = 1;
    compiler_set_lineno(c, off);
    return 1;
}

static PyCodeObject *
assemble(struct compiler *c, int addNone)
{
    basicblock *b, *entryblock;
    struct assembler a;
    int i, j, nblocks;
    PyCodeObject *co = NULL;

    /* Make sure every block that falls off the end returns None.
       XXX NEXT_BLOCK() isn't quite right, because if the last
       block ends with a jump or return b_next shouldn't set.
     */
    if (!c->u->u_curblock->b_return) {
        NEXT_BLOCK(c);
        if (addNone)
            ADDOP_O(c, LOAD_CONST, Py_None, consts);
        ADDOP(c, RETURN_VALUE);
    }

    // 找到 entryblock
    nblocks = 0;
    entryblock = NULL;
    for (b = c->u->u_blocks; b != NULL; b = b->b_list) {
        nblocks++;
        entryblock = b;
    }
    ...
    if (!assemble_init(&a, nblocks, c->u->u_firstlineno))
        goto error;
    dfs(c, entryblock, &a);

    /* Can't modify the bytecode after computing jump offsets. */
    assemble_jump_offsets(&a, c);

    /* Emit code in reverse postorder from dfs. */
    for (i = a.a_nblocks - 1; i >= 0; i--) {
        b = a.a_postorder[i];
        for (j = 0; j < b->b_iused; j++)
            if (!assemble_emit(&a, &b->b_instr[j]))
                goto error;
    }

    if (_PyString_Resize(&a.a_lnotab, a.a_lnotab_off) < 0)
        goto error;
    if (_PyString_Resize(&a.a_bytecode, a.a_offset) < 0)
        goto error;

    co = makecode(c, &a);
 error:
    assemble_free(&a);
    return co;
}

echo 'a=1' > test.py
python2 -m dis test.py                                                   
  1           0 LOAD_CONST               0 (1)
              3 STORE_NAME               0 (a)
              6 LOAD_CONST               1 (None)
              9 RETURN_VALUE

/* Bytecode object */
typedef struct {
    PyObject_HEAD
    int co_argcount;		/* #arguments, except *args */
    int co_nlocals;		/* #local variables */
    int co_stacksize;		/* #entries needed for evaluation stack */
    int co_flags;		/* CO_..., see below */
    PyObject *co_code;		/* instruction opcodes */
    PyObject *co_consts;	/* list (constants used) */
    PyObject *co_names;		/* list of strings (names used) */
    PyObject *co_varnames;	/* tuple of strings (local variable names) */
    PyObject *co_freevars;	/* tuple of strings (free variable names) */
    PyObject *co_cellvars;      /* tuple of strings (cell variable names) */
    /* The rest doesn't count for hash/cmp */
    PyObject *co_filename;	/* string (where it was loaded from) */
    PyObject *co_name;		/* string (name, for reference) */
    int co_firstlineno;		/* first source line number */
    PyObject *co_lnotab;	/* string (encoding addr<->lineno mapping) See
				   Objects/lnotab_notes.txt for details. */
    void *co_zombieframe;     /* for optimization only (see frameobject.c) */
    PyObject *co_weakreflist;   /* to support weakrefs to code objects */
} PyCodeObject;

PyObject *
PyEval_EvalCode(PyCodeObject *co, PyObject *globals, PyObject *locals)
{
    return PyEval_EvalCodeEx(co,
                      globals, locals,
                      (PyObject **)NULL, 0,
                      (PyObject **)NULL, 0,
                      (PyObject **)NULL, 0,
                      NULL);
}

// Python/ceval.c PyEval_EvalCodeEx

PyObject *
PyEval_EvalCodeEx(PyCodeObject *co, PyObject *globals, PyObject *locals,
           PyObject **args, int argcount, PyObject **kws, int kwcount,
           PyObject **defs, int defcount, PyObject *closure)
{
    register PyFrameObject *f;
    ...
    retval = PyEval_EvalFrameEx(f,0);
    ...
    return retval;
}

typedef struct _frame {
    PyObject_VAR_HEAD
    struct _frame *f_back;	/* previous frame, or NULL */
    PyCodeObject *f_code;	/* code segment */
    PyObject *f_builtins;	/* builtin symbol table (PyDictObject) */
    PyObject *f_globals;	/* global symbol table (PyDictObject) */
    PyObject *f_locals;		/* local symbol table (any mapping) */
    PyObject **f_valuestack;	/* points after the last local */
    /* Next free slot in f_valuestack.  Frame creation sets to f_valuestack.
       Frame evaluation usually NULLs it, but a frame that yields sets it
       to the current stack top. */
    PyObject **f_stacktop;
    PyObject *f_trace;		/* Trace function */

    /* If an exception is raised in this frame, the next three are used to
     * record the exception info (if any) originally in the thread state.  See
     * comments before set_exc_info() -- it's not obvious.
     * Invariant:  if _type is NULL, then so are _value and _traceback.
     * Desired invariant:  all three are NULL, or all three are non-NULL.  That
     * one isn't currently true, but "should be".
     */
    PyObject *f_exc_type, *f_exc_value, *f_exc_traceback;

    PyThreadState *f_tstate;
    int f_lasti;		/* Last instruction if called */
    /* Call PyFrame_GetLineNumber() instead of reading this field
       directly.  As of 2.3 f_lineno is only valid when tracing is
       active (i.e. when f_trace is set).  At other times we use
       PyCode_Addr2Line to calculate the line from the current
       bytecode index. */
    int f_lineno;		/* Current line number */
    int f_iblock;		/* index in f_blockstack */
    PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */
    PyObject *f_localsplus[1];	/* locals+stack, dynamically sized */
} PyFrameObject;

typedef struct {
    int b_type;			/* what kind of block this is */
    int b_handler;		/* where to jump to find handler */
    int b_level;		/* value stack level to pop to */
} PyTryBlock;

// Python/ceval.c PyEval_EvalFrameEx

PyObject *
PyEval_EvalFrameEx(PyFrameObject *f, int throwflag)
{
    ...
    register PyObject **stack_pointer;  /* Next free slot in value stack */
    register unsigned char *next_instr;
    register int opcode;        /* Current opcode */
    register int oparg;         /* Current opcode argument, if any */
    register enum why_code why; /* Reason for block stack unwind */
    register int err;           /* Error status -- nonzero if error */
    register PyObject *x;       /* Result object -- NULL if error */
    register PyObject *v;       /* Temporary objects popped off stack */
    register PyObject *w;
    register PyObject *u;
    register PyObject *t;
    register PyObject *stream = NULL;    /* for PRINT opcodes */
    register PyObject **fastlocals, **freevars;
    PyObject *retval = NULL;            /* Return value */
    PyThreadState *tstate = PyThreadState_GET();
    PyCodeObject *co;

    unsigned char *first_instr;
    PyObject *names;
    PyObject *consts;
    ...
    /* Start of code */

    if (f == NULL)
        return NULL;

    /* push frame */
    if (Py_EnterRecursiveCall(""))
        return NULL;

    tstate->frame = f;
    ...
    co = f->f_code;
    names = co->co_names;
    consts = co->co_consts;
    fastlocals = f->f_localsplus;
    freevars = f->f_localsplus + co->co_nlocals;
    first_instr = (unsigned char*) PyString_AS_STRING(co->co_code);
    next_instr = first_instr + f->f_lasti + 1;
    stack_pointer = f->f_stacktop;
    assert(stack_pointer != NULL);
    f->f_stacktop = NULL;       /* remains NULL unless yield suspends frame */
    ...
    why = WHY_NOT;
    err = 0;
    x = Py_None;        /* Not a reference, just anything non-NULL */
    w = NULL;

    for (;;) {
        ...
            if (interpreter_lock) {
                /* Give another thread a chance */

                if (PyThreadState_Swap(NULL) != tstate)
                    Py_FatalError("ceval: tstate mix-up");
                PyThread_release_lock(interpreter_lock);

                /* Other threads may run now */

                PyThread_acquire_lock(interpreter_lock, 1);

                if (PyThreadState_Swap(tstate) != NULL)
                    Py_FatalError("ceval: orphan tstate");

                /* Check for thread interrupts */

                if (tstate->async_exc != NULL) {
                    x = tstate->async_exc;
                    tstate->async_exc = NULL;
                    PyErr_SetNone(x);
                    Py_DECREF(x);
                    why = WHY_EXCEPTION;
                    goto on_error;
                }
            }
        ...
         /* Extract opcode and argument */

        opcode = NEXTOP();
        oparg = 0;   /* allows oparg to be stored in a register because
            it doesn't have to be remembered across a full loop */
        if (HAS_ARG(opcode))
            oparg = NEXTARG();
    dispatch_opcode:
        /* Main switch on opcode */

        switch (opcode) {

        /* BEWARE!
           It is essential that any operation that fails sets either
           x to NULL, err to nonzero, or why to anything but WHY_NOT,
           and that no operation that succeeds does this! */

        /* case STOP_CODE: this is an error! */

        TARGET_NOARG(NOP)
        {
            FAST_DISPATCH();
        }

        TARGET(LOAD_FAST)
        {
            x = GETLOCAL(oparg);
            if (x != NULL) {
                Py_INCREF(x);
                PUSH(x);
                FAST_DISPATCH();
            }
            format_exc_check_arg(PyExc_UnboundLocalError,
                UNBOUNDLOCAL_ERROR_MSG,
                PyTuple_GetItem(co->co_varnames, oparg));
            break;
        }
        ... // 省略剩余 opcode 对应的 case
    }/* switch */

        /* End the loop if we still have an error (or return) */

        if (why != WHY_NOT)
            break;

    } /* main loop */

    assert(why != WHY_YIELD);
    /* Pop remaining stack entries. */
    while (!EMPTY()) {
        v = POP();
        Py_XDECREF(v);
    }

    if (why != WHY_RETURN)
        retval = NULL;

    return retval;
}

/* Status code for main loop (reason for stack unwind) */
enum why_code {
        WHY_NOT =       0x0001, /* No error */
        WHY_EXCEPTION = 0x0002, /* Exception occurred */
        WHY_RERAISE =   0x0004, /* Exception re-raised by 'finally' */
        WHY_RETURN =    0x0008, /* 'return' statement */
        WHY_BREAK =     0x0010, /* 'break' statement */
        WHY_CONTINUE =  0x0020, /* 'continue' statement */
        WHY_YIELD =     0x0040  /* 'yield' operator */
};