12. Generators: Behind the scenes.

Generators are one of the beautiful concepts in Python. A generator function is one that contains a yield statement, and when called, it returns a generator. A simple use of generators in Python is as an iterator that produces values for an iteration on demand. Listing 12.0 is a simple example of a generator function that produces values from 0 up to n.

def firstn(n):
    num = 0
    while num < n:
        v = yield num
        print(v)
        num += 1

firstn contains the yield statement, so calling it will not return a simple value as a conventional function would do. Instead, it will return a generator object which captures the continuation of the computation. We can then use the next function to get successive values from the returned generator object or send values into the generator using the send method of the generator object.

In this chapter, we are not interested in the semantics of the generators objects or the right way to use them. Our interest is in how generators are implemented under the covers in CPython. We are interested in how it is possible to suspend a computation and then subsequently resume such computation. We look at the data structures and ideas behind this concept, and surprisingly, they are not too complicated. First, we look at the C implementation of a generator object.

12.1 The Generator object

Listing 12.1 is the definition of a generator object, and going through this definition provides some intuition into how a generator execution can be suspended or resumed. We can see that a generator object contains a frame object and a code object, two objects that are essential to the execution of Python bytecode.

/* _PyGenObject_HEAD defines the initial segment of generator 
and coroutine objects. */
#define _PyGenObject_HEAD(prefix)                                           \
    PyObject_HEAD                                                           \
    /* Note: gi_frame can be NULL if the generator is "finished" */         \
    struct _frame *prefix##_frame;                                          \
    /* True if generator is being executed. */                              \
    char prefix##_running;                                                  \
    /* The code object backing the generator */                             \
    PyObject *prefix##_code;                                                \
    /* List of weak reference. */                                           \
    PyObject *prefix##_weakreflist;                                         \
    /* Name of the generator. */                                            \
    PyObject *prefix##_name;                                                \
    /* Qualified name of the generator. */                                  \
    PyObject *prefix##_qualname;

typedef struct {
    /* The gi_ prefix is intended to remind of generator-iterator. */
    _PyGenObject_HEAD(gi)
} PyGenObject;

The following comprise the main attributes of a generator object.

1. prefix##_frame: This field references a frame object. This frame object contains the code object of a generator and it is within this frame that the execution of the generator object’s code object takes place.
2. prefix##_running: This is a boolean field that indicates whether the generator is running.
3. prefix##_code: This field references the code object associated with the generator. This is the code object that executes whenever the generator is running.
4. prefix##_name: This is the name of the generator - in listing 12.0, the value is firstn.
5. prefix##_qualname: This is the fully qualified name of the generator. Most times this value is the same as that of prefix##_name.

Creating generators

When we call a generator function, the generator function does not run to completion and return a value; instead, it produces a generator object. This is due to the CO_GENERATOR flag that gets set when compiling a generator function. This flag comes in very useful during the setup process that happens just before the code object execution.

During the execution of the code object for the function, recall the _PyEval_EvalCodeWithName is invoked to perform some setup. During this setup process, the interpreter checks if the CO_GENERATOR flag; if set, it creates and returns a generator object rather than call the evaluation loop function. The magic happens at the last code block of the _PyEval_EvalCodeWithName as shown in listing 12.2.

 /* Handle generator/coroutine/asynchronous generator */
    if (co->co_flags & (CO_GENERATOR | CO_COROUTINE | CO_ASYNC_GENERATOR)) {
        PyObject *gen;
        PyObject *coro_wrapper = tstate->coroutine_wrapper;
        int is_coro = co->co_flags & CO_COROUTINE;

        if (is_coro && tstate->in_coroutine_wrapper) {
            assert(coro_wrapper != NULL);
            PyErr_Format(PyExc_RuntimeError,
                         "coroutine wrapper %.200R attempted "
                         "to recursively wrap %.200R",
                         coro_wrapper,
                         co);
            goto fail;
        }

        /* Don't need to keep the reference to f_back; it will be set
         * when the generator is resumed. */
        Py_CLEAR(f->f_back);

        PCALL(PCALL_GENERATOR);

        /* Create a new generator that owns the ready to run frame
         * and return that as the value. */
        if (is_coro) {
            gen = PyCoro_New(f, name, qualname);
        } else if (co->co_flags & CO_ASYNC_GENERATOR) {
            gen = PyAsyncGen_New(f, name, qualname);
        } else {
            gen = PyGen_NewWithQualName(f, name, qualname);
        }
        if (gen == NULL)
            return NULL;

        if (is_coro && coro_wrapper != NULL) {
            PyObject *wrapped;
            tstate->in_coroutine_wrapper = 1;
            wrapped = PyObject_CallFunction(coro_wrapper, "N", gen);
            tstate->in_coroutine_wrapper = 0;
            return wrapped;
        }

        return gen;
    }

We can see from Listing 12.2 that bytecode for a generator function code object is never executed at the point of the function call - the execution of bytecode only happens when the returned generator object is running, and we look at this next.

12.2 Running a generator

We can run a generator object by passing it as an argument to the next builtin function. This will cause the generator to execute until it hits a yield expression then it suspends execution. The critical question here is how the generators can capture the execution state and update those at will.

Looking back at the generator object definition in Listing 12.1, we see that generators have a field that references a frame object, and this gets filled when the generator is created as shown in listing 12.2. The frame object as we recall has all the state that is required to execute a code object so by having a reference to that execution frame, the generator object can capture all the state required for its execution.

Now that we know how a generator object captures execution state, we move to the question of how the execution of a suspended generator object is resumed, and this is not too hard to figure out given the information that we have already. When the next builtin function is called with a generator as an argument, the next function dereferences the tp_iternext field of the generator type and invokes whatever function that field references. In the case of a generator object, that field references a function, gen_iternext, which calls the gen_send_ex function, that does the actual work of resuming the execution of the generator object. Before the generator object was created, the initial setup of the frame object and variables was carried out by the _PyEval_EvalCodeWithName function, so the execution of the generator object involves calling the PyEval_EvalFrameEx with the frame object contained within the generator object as the frame argument. The execution of the code object contained within the frame then proceeds as explained the chapter on the evaluation loop.

To get a more in-depth look at a generator function, we look at the generator function in listing 12.0. The disassembly of the generator function in listing 12.0 results in the set of bytecode shown in listing 12.3.

  4           0 LOAD_CONST               1 (0)
              2 STORE_FAST               1 (num)

  5           4 SETUP_LOOP              34 (to 40)
        >>    6 LOAD_FAST                1 (num)
              8 LOAD_FAST                0 (n)
             10 COMPARE_OP               0 (<)
             12 POP_JUMP_IF_FALSE       38

  6          14 LOAD_FAST                1 (num)
             16 YIELD_VALUE
             18 STORE_FAST               2 (v)

  7          20 LOAD_GLOBAL              0 (print)
             22 LOAD_FAST                2 (v)
             24 CALL_FUNCTION            1
             26 POP_TOP

  8          28 LOAD_FAST                1 (num)
             30 LOAD_CONST               2 (1)
             32 INPLACE_ADD
             34 STORE_FAST               1 (num)
             36 JUMP_ABSOLUTE            6
        >>   38 POP_BLOCK
        >>   40 LOAD_CONST               0 (None)
             42 RETURN_VALUE

When the execution of the bytecode shown in listing 12.3 for the generator function gets to the YIELD_VALUE opcode at byte offset 16, that opcode causes the evaluation to suspend and return the value on the top of the stack to the caller. By suspend, we mean the evaluation loop for the currently executing frame is exited however this frame is not deallocated because it is still referenced by the generator object so the execution of the frame can continue again when PyEval_EvalFrameEx is invoked with the frame as one of its arguments.

Python generators do more than just generate values; they can also consume values by using the generator send method. This is possible because yield is an expression that evaluates to a value. When the send method is called on a generator with a value, the gen_send_ex method places the value onto the evaluation stack of the generator object frame before the evaluation of the frame object resumes. Listing 12.3 shows the STORE_FAST instruction comes after YIELD_VALUE; this stores the value at the top of the stack to the provided name. In the case where there is no send function call, then the None value is placed on the top of the stack.