A stack frame (also “interpreter frame” or just “frame”) is a key component of interpreter implementations in general, and specifically of both CPython and pytype. At a conceptual level, an interpreter executes a series of instructions within some “execution context”, roughly the environment within which variables are looked up. A function call creates a new context, which is used to execute the function’s code, and then cleaned up when it returns.
Concretely, this execution model is implemented as stack of “frame” objects, containing data like the local and global variable tables and any metadata specific to the current function. Calling a function pushes a new frame onto the stack, and returning pops it back off, leaving the calling code’s frame on top of the stack again.
The python stack frame is described in this article; since a lot of the pytype code is based on the details of the CPython interpreter it is worth being familiar with the latter.
The vm maintains a stack of frames in
vm.frames, and methods
pop_frame() to add and remove frames from the stack. Analogously to
python, the frame stack is also used when reporting errors, so that pytype can
display positional information and tracebacks if desired.
The main entry point is the
vm.run_frame() method, which adds a frame to the
stack, runs its associated bytecode, retrieves the return value and pops it back
off. Pytype also threads a state through the execution of the individual
instructions. The state, an object of type
state.FrameState, is an immutable
snapshot of the state of the frame when running the opcode, including the data
stack, the block stack and the current cfg node. (These will be detailed in a
separate section on opcode execution).
At a high level, a frame’s code consists of an ordered series of blocks, each of which consists of several opcodes. The overall execution loop is (simplified):
def run_bytecode(code): frame = make_frame(code) push_frame(frame) for block in frame.f_code.order: state = initial state for block for op in block: state = self.run_instruction(op, state) pop_frame(frame) # does cleanup as well as removing the frame from the stack return frame.return_variable, frame.f_locals, frame.f_globals
Note that unlike the frame state the frame itself is mutable; attributes like
frame.return_variable are populated or modified in the course of the execution
loop, and then returned from
run_bytecode() (the frame object goes out of
scope and is discarded).
The python VM is a “stack machine”, meaning that its opcodes operate on a stack of inputs. This stack (not to be confused with the frame stack) is how values are passed between instructions - cpython calls it the “value stack”, and pytype the “data stack”.
NOTE: The values themselves are python objects allocated and stored in the heap (explicitly by the cpython VM, and implicitly by pytype since we create abstract representations of values as python objects). The data stack contains references to these values, and does not actually create or destroy them. We refer to pushing and popping values for simplicity, but we are really pushing and popping references.
Opcodes perform a variety of operations with respect to the data stack:
The current frame state (passed as
state to all opcode implementations) stores
a reference to the data stack; pushing and popping values is done through the
state.pop rather than access the stack directly.
One reason pytype does not follow cpython in naming the data stack the “value stack” is that we do not store values directly on the stack; we store Variables with bindings to those values. This detail becomes important when we factor in control flow analysis; while the cpython VM will execute an opcode and store a single python object on the stack, pytype pushes a Variable with multiple bindings, each one representing a different potential value that the opcode might be pushing. As a quick example, given the code
if a: y = 10 else: y = None x = y
When we hit the opcode
LOAD_FAST y for the final line, we would push a
variable with bindings
<y = 10> and
<y = None> onto the stack, whereas
python would push either
None depending on what
a actually was.
LOAD_* family of opcodes typically retrieve a value from one of the
frame’s other data stores (e.g. the locals dictionary) and push them onto the
stack. Similarly, the
STORE_* family pops a value off the stack and writes it
to a heap location. So the following code:
x = a + b
would compile to
LOAD_FAST 0 (a) LOAD_FAST 1 (b) BINARY_ADD STORE_FAST 2 (x)
The pytype implementations of these opcodes can be seen in
vm.py/byte_LOAD_FAST etc. Let us do a quick code tour of the execution of
byte_LOAD_FAST when running the first opcode,
def byte_LOAD_FAST(self, state, op): """Load a local. Unlike LOAD_NAME, it doesn't fall back to globals.""" # op.arg is an index into the current frame's table of local variable names. # Use the index to look up the name of the variable to load. name = self.frame.f_code.co_varnames[op.arg] # returns 'a' # Load the variable 'a' in the current frame's `locals` dict. try: # load_local gets the current value of a in `val`. Note the common pattern # of threading an immutable state object through functions in vm.py by # having them take in a state and return an updated state. state, val = self.load_local(state, name) except KeyError: # Raise an error if we have referred to an undefined local variable val = self._name_error_or_late_annotation(name).to_variable(state.node) # Raise an error if we have referred to a deleted local variable. (We need # to do this because pytype stores deleted variables as a `Deleted` object # rather than removing them from the symbol table. self.check_for_deleted(state, name, val) # trace_opcode simply logs opcode execution. self.trace_opcode(op, name, val) # Push the value of a onto the data stack return state.push(val)
The overall stack effect is to have the data stack go from
Tracing the state of the stack through each opcode:
LOAD_FAST 0 (a) | (a) | a has been loaded from locals[a] and pushed LOAD_FAST 1 (b) | (b), (a) | b has been loaded from locals[b] and pushed BINARY_ADD | (a+b) | a and b have been popped and a+b pushed STORE_FAST 2 (x) | | a+b has been popped and stored in locals[x]
The block stack is the third of the stacks that python, and hence pytype, maintain when running bytecode. This blog post is a good introduction to it from a cpython perspective.
The block stack tracks compound
for which have an associated block of code. In python
source code, compound statements contain an indented block of code:
for x in xs: code block ...
The corresponding bytecode has paired
POP_BLOCK statements to
delimit the code block, for instance the bytecode for the
for statement above
would compile to
SETUP_LOOP LOAD_FAST xs GET_ITER FOR_ITER STORE_FAST x ... code block ... POP_BLOCK
NOTE: Some of the
SETUP_* opcodes changed in python 3.8, however the basic
principle remains the same. See
vm.py/byte_SETUP_FINALLY() for a quick look at
how pytype handles version-specific opcode differences.
Internally, pytype represents a block as an object with two fields:
Block = collections.namedtuple("Block", [ "type", # string representing the block type ("loop", "except", etc) "level" # the size of the data stack when entering the block ])
Pytype’s primary use for the block stack is to ensure the data stack is cleaned
up when exiting a block (see