Python虚拟机中的for循环控制流
在Python虚拟机之if控制流(一)这一章中,我们了解if控制流的字节码实现,在if控制结构中,虽然Python虚拟机会在不同的分支摇摆,但大体还是向前执行,但是在for循环控制结构中,我们将会看到一种新的指令跳跃方式,即指令回退。在if控制流章节中,我们看到了指令跳跃时,通常跳跃的距离都是当前指令与目标指令之间的距离。如果按照这种逻辑,进行回退时,这个跳跃是否是负数呢?别急,我们下面一点一点来剖析for循环控制流的实现
# cat demo3.py lst = [1, 2] for i in lst: print(i) # python2.5 …… >>> source = open("demo3.py").read() >>> co = compile(source, "demo3.py", "exec") >>> import dis >>> dis.dis(co) 1 0 LOAD_CONST 0 (1) 3 LOAD_CONST 1 (2) 6 BUILD_LIST 2 9 STORE_NAME 0 (lst) 2 12 SETUP_LOOP 19 (to 34) 15 LOAD_NAME 0 (lst) 18 GET_ITER >> 19 FOR_ITER 11 (to 33) 22 STORE_NAME 1 (i) 3 25 LOAD_NAME 1 (i) 28 PRINT_ITEM 29 PRINT_NEWLINE 30 JUMP_ABSOLUTE 19 >> 33 POP_BLOCK >> 34 LOAD_CONST 2 (None) 37 RETURN_VALUE
第一条指令这里不再介绍,就是一条创建一个列表对象,如果有疑问的同学可以看Python虚拟机中的一般表达式(二)这一章节关于列表对象创建的介绍,我们主要看"12 SETUP_LOOP 19"这条指令,它在Python虚拟机中为for循环控制结构起着至关重要的作用
ceval.c
- case SETUP_LOOP:
- case SETUP_EXCEPT:
- case SETUP_FINALLY:
- PyFrame_BlockSetup(f, opcode, INSTR_OFFSET() + oparg,
- STACK_LEVEL());
- continue;
在SETUP_LOOP指令的实现中,仅仅简单调用了一个PyFrame_BlockSetup函数,那么,我们来看一下这个函数的实现
frameobject.c
- void
- PyFrame_BlockSetup(PyFrameObject *f, int type, int handler, int level)
- {
- PyTryBlock *b;
- if (f->f_iblock >= CO_MAXBLOCKS)
- Py_FatalError("XXX block stack overflow");
- b = &f->f_blockstack[f->f_iblock++];
- b->b_type = type;
- b->b_level = level;
- b->b_handler = handler;
- }
在这里,我们第一次使用PyFrameObject中的f_blockstack
frameobject.h
- typedef struct _frame {
- ……
- int f_iblock; /* index in f_blockstack */
- PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */
- ……
- } PyFrameObject;
CO_MAXBLOCKS在Python2.5中被定义为20,f_iblock在调用PyFrame_New时被初始化为0,而那个至关重要的PyTryBlock定义如下:
frameobject.h
- 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;
显然,PyFrameObject对象中的f_blockstack是一个PyTryBlock结构的数组,而SETUP_LOOP指令所做的就是从这个数组中获得一块PyTryBlock结构,并在这个结构中存放一些Python虚拟机当前的状态信息。比如当前执行的字节码指令,当前运行时栈的深度等等
PyTryBlock结构中有一个b_type域,这意味着实际上存在着几种不同用途的PyTryBlock对象。从PyFrame_BlockSetup中可以看到,这个b_type实际上被设置为当前Python虚拟机正在执行的字节码指令,以字节码指令作为区分PyTryBlock的不同用途。从上面的SETUP_LOOP的实现我们可以知道,除了循环,异常机制也会用到PyTryBlock
list迭代器
在SETUP_LOOP指令从PyFrameObject的f_blockstack中申请了一块PyTryBlock结构的空间之后,Python虚拟机通过"15 LOAD_NAME 0"指令,将刚创建的PyListObject对象压入运行时栈,再执行"18 GET_ITER"指令来获得PyListObject对象的迭代器
ceval.c
- case GET_ITER:
- //从运行时栈获得PyListObject对象
- v = TOP();
- x = PyObject_GetIter(v);
- Py_DECREF(v);
- if (x != NULL)
- {
- //将PyListObject对象的iterator压入运行时栈
- SET_TOP(x);
- PREDICT(FOR_ITER);
- continue;
- }
- STACKADJ(-1);
- break;
在GET_ITER的指令代码中,Python虚拟机首先会获得位于运行时栈的栈顶的PyListObject对象,然后通过PyObject_GetIter获得PyListObject对象的迭代器
object.h
typedef PyObject *(*getiterfunc) (PyObject *);
abstract.c
- PyObject *
- PyObject_GetIter(PyObject *o)
- {
- PyTypeObject *t = o->ob_type;
- getiterfunc f = NULL;
- if (PyType_HasFeature(t, Py_TPFLAGS_HAVE_ITER))
- f = t->tp_iter;//获得类型对象中的tp_iter操作
- if (f == NULL) {
- if (PySequence_Check(o))
- return PySeqIter_New(o);
- return type_error("'%.200s' object is not iterable", o);
- }
- else {
- //通过tp_iter操作获得iterator
- PyObject *res = (*f)(o);
- if (res != NULL && !PyIter_Check(res)) {
- PyErr_Format(PyExc_TypeError,
- "iter() returned non-iterator "
- "of type '%.100s'",
- res->ob_type->tp_name);
- Py_DECREF(res);
- res = NULL;
- }
- return res;
- }
- }
显然,PyObject_GetIter是通过调用对象对应的类型对象中的tp_iter操作来获得与对象关联的迭代器,在Python中,不光PyListObject对象是PyObject对象,就连listiterobject迭代器对象也是PyObject对象
listobject.c
- typedef struct {
- PyObject_HEAD
- long it_index;
- PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
- } listiterobject;
既然迭代器是是PyObject对象,那么显然,它也一定拥有类型对象。迭代器listiterobject对象所对应的类型对象为PyListIter_Type
listobject.c
- PyTypeObject PyListIter_Type = {
- PyObject_HEAD_INIT(&PyType_Type)
- 0, /* ob_size */
- "listiterator", /* tp_name */
- sizeof(listiterobject), /* tp_basicsize */
- 0, /* tp_itemsize */
- /* methods */
- (destructor)listiter_dealloc, /* tp_dealloc */
- 0, /* tp_print */
- 0, /* tp_getattr */
- 0, /* tp_setattr */
- 0, /* tp_compare */
- 0, /* tp_repr */
- 0, /* tp_as_number */
- 0, /* tp_as_sequence */
- 0, /* tp_as_mapping */
- 0, /* tp_hash */
- 0, /* tp_call */
- 0, /* tp_str */
- PyObject_GenericGetAttr, /* tp_getattro */
- 0, /* tp_setattro */
- 0, /* tp_as_buffer */
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
- 0, /* tp_doc */
- (traverseproc)listiter_traverse, /* tp_traverse */
- 0, /* tp_clear */
- 0, /* tp_richcompare */
- 0, /* tp_weaklistoffset */
- PyObject_SelfIter, /* tp_iter */
- (iternextfunc)listiter_next, /* tp_iternext */
- listiter_methods, /* tp_methods */
- 0, /* tp_members */
- };
PyListObject对象的类型对象PyList_Type中,tp_iter域被设置为list_iter。这个list_iter正是PyObject_GetIter中所获得的那个f,也正是创建迭代器对象的函数:
listobject.c
- static PyObject *
- list_iter(PyObject *seq)
- {
- listiterobject *it;
-
- if (!PyList_Check(seq)) {
- PyErr_BadInternalCall();
- return NULL;
- }
- it = PyObject_GC_New(listiterobject, &PyListIter_Type);
- if (it == NULL)
- return NULL;
- it->it_index = 0;
- Py_INCREF(seq);
- it->it_seq = (PyListObject *)seq;
- _PyObject_GC_TRACK(it);
- return (PyObject *)it;
- }
PyListObject对象的迭代器只是对原来的PyListObject对象做了一层简单的包装,在迭代器中,维护了当前访问的元素在PyListObject对象中的序号:it_index。通过这个序号,listiterobject对象就可以实现对PyListObject的遍历
GET_ITER指令在获得了PyListObject对象的迭代器之后,通过SET_TOP宏强制将这个迭代器对象设置为运行时栈的栈顶元素:
图1-1创建迭代器时运行时栈的变化
在指令"18 GET_ITER"完成之后,Python虚拟机开始了FOR_ITER指令的预测动作,这样做是为了提高效率
迭代控制
迭代器是一个对容器实现遍历的工具,遍历,就是循环的另一种说法。从"19 FOR_ITER 11"指令开始,我们开始进入Python虚拟机的for循环:
ceval.c
- case FOR_ITER:
- //从运行时栈的栈顶获得iterator对象
- v = TOP();
- //通过iterator对象获得集合中的下一个元素对象
- x = (*v->ob_type->tp_iternext)(v);
- if (x != NULL)
- {
- //将获得的元素对象压入运行时栈
- PUSH(x);
- PREDICT(STORE_FAST);
- PREDICT(UNPACK_SEQUENCE);
- continue;
- }
- //x == NULL,意味着iterator的迭代已经结束
- if (PyErr_Occurred())
- {
- if (!PyErr_ExceptionMatches(PyExc_StopIteration))
- break;
- PyErr_Clear();
- }
- /* iterator ended normally */
- x = v = POP();
- Py_DECREF(v);
- JUMPBY(oparg);
- continue;
FOR_ITER的指令代码首先从运行时栈中获得PyListObject对象的迭代器,然后调用tp_iternext开始进行迭代。迭代器的tp_iternext操作总是返回与迭代器关联的容器对象的下一个元素,如果当前已经抵达了容器对象的结束位置,那么tp_iternext将返回NULL,这个结果代表遍历结束
FOR_ITER的指令代码会检查tp_iternext的返回结果,如果得到的是一个有效的元素,即x != NULL,那么将获得的元素压入到运行时栈中,并开始一系列字节码预测的动作。在demo3.py编译后的FOR_ITER指令中,PREDICT(STORE_FAST)和PREDICT(UNPACK_SEQUENCE)这两个预测动作都会失败,所以在continue处,Python虚拟机会重新进入对下一条字节码指令——"22 STORE_NAME 1"的执行过程
对于PyListObject对象的迭代器,其获取下一个元素的操作如下:
listobject.c
- static PyObject *
- listiter_next(listiterobject *it)
- {
- PyListObject *seq;
- PyObject *item;
-
- assert(it != NULL);
- //seq是PyListObject对象
- seq = it->it_seq;
- if (seq == NULL)
- return NULL;
- assert(PyList_Check(seq));
-
- if (it->it_index < PyList_GET_SIZE(seq)) {
- //获得序号为it_index的元素对象
- item = PyList_GET_ITEM(seq, it->it_index);
- //调整it_index,使其指向下一个元素对象
- ++it->it_index;
- Py_INCREF(item);
- return item;
- }
- //迭代结束
- Py_DECREF(seq);
- it->it_seq = NULL;
- return NULL;
- }
在获取当前it_index对应的PyListObject对象的元素后,将it_index递增,为下一个迭代动作做好准备。在我们的例子中,这里会返回一个PyIntObject对象1
图1-2展示了直到"22 STORE_NAME 1"之前,运行时栈及local名字空间的变化情况
图1-2 迭代过程中虚拟机的状态变化
在这之后,Python虚拟机将沿着字节码的顺序一条一条执行下去,从而完成输出的动作。按照demo3.py中Python源代码所定义的行为,应该获得PyListObject对象中的下一个元素,并继续进行输出操作。直观上,这里需要一个向后回退的指令,这个指令正是"30 JUMP_ABSOLUTE 19"
ceval.c
- case JUMP_ABSOLUTE:
- JUMPTO(oparg);
- continue;
前面我们提到,如果for循环沿用JUMPBY的逻辑,那么参数必须是一个负数,因为涉及到一个指令回退的过程。但这里Python采用的是另一种做法,不再使用相对距离进行跳跃,而是使用基于字节码指令序列开始位置的绝对距离跳跃,而完成这一动作的,正是JUMP_ABSOLUTE指令
JUMP_ABSOLUTE指令的行为是强制设定next_instr的值,将next_instr设定到距离f->f_code->co_code开始地址的某一特定偏移的位置。这个偏移的量由JUMP_ABSOLUTE的指令参数决定。所以,这条参数就成了for循环中指令回退动作最关键的一点,在我们编译后的字节码指令中,JUMP_ABSOLUTE的指令参数是19,那么这个19是代表什么呢?
我们把眼光放回编译后的字节码指令开始初,字节码指令的第二列代表偏移,那么这个19即为偏移位为19的位置,于是我们到达了"19 FOR_ITER 11"这条指令,那么Python虚拟机下一步动作就是执行FOR_ITER,即通过PyListObject对象中的迭代器获取下一个元素,然后继续向前,打印元素
可见,在JUMP_ABSOLUTE指令处,Python虚拟机实现了字节码的向后回退动作。而Python虚拟机也在FOR_ITER指令和JUMP_ABSOLUTE指令之间成功地构造处了一个循环结构,正是这个循环结构对应着demo3.py中的那个for循环结构
终止迭代
可能你会好奇,为什么"19 FOR_ITER 11"中的字节码FOR_ITER也会有参数,其实,这个11是和终止迭代有关。一个列表不管再长,也有迭代完毕的一天,在FOR_ITER检查到PyListObject对象的迭代器获得的下一个元素为NULL时,就意味着迭代结束了。这个结果将导致Python虚拟机会将迭代器从运行时栈中弹出,同时执行一个JUMPBY的动作,向前飞跃
ceval.c
#define JUMPBY(x) (next_instr += (x))
向前飞跃的距离即为FOR_ITER的参数,即为11。我们从FOR_ITER后的STORE_NAME前进11个字节,正好达到POP_BLOCK
ceval.c
- case POP_BLOCK:
- {
- PyTryBlock *b = PyFrame_BlockPop(f);
- while (STACK_LEVEL() > b->b_level)
- {
- v = POP();
- Py_DECREF(v);
- }
- }
frameobject.c
- PyTryBlock *
- PyFrame_BlockPop(PyFrameObject *f)
- {
- PyTryBlock *b;
- if (f->f_iblock <= 0)
- Py_FatalError("XXX block stack underflow");
- //向f_blockstack中归还PyTryBlock
- b = &f->f_blockstack[--f->f_iblock];
- return b;
- }
还记得在SETUP_LOOP处,Python虚拟机从f->f_blockstack中申请了一个PyTryBlock结构吗?Python虚拟机会将一些状态信息保存到所获得的PyTryBlock结构中,在执行POP_BLOCK指令时,实际上就是把PyTryBlock归还给f->f_blockstack。同时,Python虚拟机抽取在SETUP_LOOP指令处保存在PyTryBlock中的信息,并根据其中存储的SETUP_LOOP指令、运行时栈的深度信息将运行时栈恢复到SETUP_LOOP之前的状态,从而完成整个for循环结构。
在执行SETUP_LOOP指令时,Python虚拟机保存了许多信息,而在执行POP_BLOCK指令时,却只能使用栈深度信息来恢复运行时栈啊,为什么会有这种不对称呢?这是因为,PyTryBlock并不是专门为for循环准备的,Python中还会有一些机制用到这个结构,为了避免代码过于复杂,Python不管三七二十一,在PyFrame_BlockSetup中一股脑将所有机制可能用到的参数全部放在PyTryBlock结构中,各个机制需要什么参数,取用需要的参数即可,对于其他参数,可以不用理会
最后,让我们修改一下GET_ITER、FOR_ITER、JUMP_ABSOLUTE的实现,来实时观察一下for循环的执行流程
ceval.c
case GET_ITER: v = TOP(); x = PyObject_GetIter(v); Py_DECREF(v); if (x != NULL) { SET_TOP(x); printf("[GET_ITER]:Get iterator...\n"); PREDICT(FOR_ITER); continue; } STACKADJ(-1); break; …… case FOR_ITER: v = TOP(); x = (*v->ob_type->tp_iternext)(v); if (x != NULL) { PUSH(x); if (PyInt_CheckExact(x)) { register long i; i = PyInt_AS_LONG(x); printf("[FOR_ITER]:Get next item -> %ld...\n", i); } PREDICT(STORE_FAST); PREDICT(UNPACK_SEQUENCE); continue; } else { printf("[FOR_ITER]:Get next item -> NULL...\n"); } if (PyErr_Occurred()) { if (!PyErr_ExceptionMatches(PyExc_StopIteration)) break; PyErr_Clear(); } x = v = POP(); Py_DECREF(v); JUMPBY(oparg); continue; …… case JUMP_ABSOLUTE: JUMPTO(oparg); if (*next_instr == FOR_ITER){ printf("[JUMP_ABSOLUTE]:Go back to FOR_ITER...\n"); } continue;
重新编译Python,然后进入Python的命令行模式
>>> lst = [6, 5, 4, 3, 2, 1] >>> for i in lst: ... pass ... [GET_ITER]:Get iterator... [FOR_ITER]:Get next item -> 6... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> 5... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> 4... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> 3... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> 2... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> 1... [JUMP_ABSOLUTE]:Go back to FOR_ITER... [FOR_ITER]:Get next item -> NULL... >>>