python_graphs.control_flow.ControlFlowVisitor

class documentation

class ControlFlowVisitor(object): (source)

A visitor for determining the control flow of a Python program from an AST.

The main function of interest here is visit, which causes the visitor to construct the control flow graph for the node passed to visit.

Basic control flow: The state of the Visitor consists of a sequence of frames, and a current basic block. When an AST node is visited by visit, it is added to the current basic block. When a node can indicate a possible change in control, new basic blocks are created and exits between the basic blocks are added as appropriate.

For example, an If statement introduces two possibilities for control flow. Consider the program:

if a > b:: c = 1
else:: c = 2

return c

There are four basic blocks in this program: let's call them compare, c = 1, c = 2, and return. The exits between the blocks are: compare -> c = 1, compare -> c = 2, c = 1 -> return, and c = 2 -> return.

Frames: There are four kinds of frames: function frames, loop frames, try-except, and try-finally frames. All AST nodes in a function definition are in that function's function frame. All AST nodes in the body of a loop are in that loop's loop frame. And all AST nodes in the try and except blocks of a try/except/finally are in that try's try-finally frame.

A function frame contains information about where control should flow to in the case of a return statement or an uncaught exception.

A loop frame contains information about where control should pass to in the case of a continue or break statement.

A try-except frame contains information about where control should flow to in the case of an exception.

A try-finally frame contains information about where control should flow to in the case of an exit (such as a finally block that must run before a return, continue, or break statement can be executed).

Method	`__init__`	Undocumented
Method	`add_instruction`	Undocumented
Method	`add_new_instruction`	Undocumented
Method	`enter_function_frame`	Undocumented
Method	`enter_loop_frame`	Undocumented
Method	`enter_module_frame`	Undocumented
Method	`enter_try_except_frame`	Undocumented
Method	`enter_try_finally_frame`	Undocumented
Method	`exit_frame`	Exits the innermost current frame.
Method	`get_current_exception_handling_frames`	Get all exception handling frames containing the current block.
Method	`get_current_function_frame`	Gets the current function frame and contained current try-finally frames.
Method	`get_current_loop_frame`	Gets the current loop frame and contained current try-finally frames.
Method	`handle_argument_defaults`	Add Instructions for all of a FunctionDef's default values.
Method	`handle_argument_writes`	Add Instructions for all of a FunctionDef's arguments.
Method	`handle_ExceptHandler`	Create the blocks appropriate for an exception handler.
Method	`handle_ExitStatement`	A helper fn for Return, Continue, and Break.
Method	`handle_function_definition`	A helper fn for Lambda and FunctionDef.
Method	`handle_Loop`	A helper fn for For and While.
Method	`new_block`	Create a new block.
Method	`raise_through_frames`	Adds exits for the control flow of a raised exception.
Method	`run`	Undocumented
Method	`visit`	Visit node, either an AST node or a list.
Method	`visit_Break`	Visit a Break node of the AST.
Method	`visit_ClassDef`	Visit a ClassDef node of the AST.
Method	`visit_Continue`	Visit a Continue node of the AST.
Method	`visit_For`	Visit a For node of the AST.
Method	`visit_FunctionDef`	Visit a FunctionDef node of the AST.
Method	`visit_If`	Visit an If node of the AST.
Method	`visit_Lambda`	Visit a Lambda node of the AST.
Method	`visit_list`	Visit each of the items in a list from the AST.
Method	`visit_Module`	Undocumented
Method	`visit_Raise`	Visit a Raise node of the AST.
Method	`visit_Return`	Visit a Return node of the AST.
Method	`visit_Try`	Visit a Try node of the AST.
Method	`visit_While`	Visit a While node of the AST.
Method	`visit_Yield`	Visit a Yield node of the AST.
Instance Variable	`frames`	The current frames. Each frame in this list contains all frames that come after it in the list.
Instance Variable	`graph`	The control flow graph being generated by the visitor.

def __init__(self): (source) ¶

Undocumented

def add_instruction(self, block, instruction): (source) ¶

Undocumented

def add_new_instruction(self, block, node, accesses=None, source=None): (source) ¶

Undocumented

def enter_function_frame(self, return_block, raise_block): (source) ¶

Undocumented

def enter_loop_frame(self, continue_block, break_block): (source) ¶

Undocumented

def enter_module_frame(self, exit_block, raise_block): (source) ¶

Undocumented

def enter_try_except_frame(self, handler_block): (source) ¶

Undocumented

def enter_try_finally_frame(self, final_block, final_block_end): (source) ¶

Undocumented

def exit_frame(self): (source) ¶

Exits the innermost current frame.

Note: Each enter_* function must be matched to exactly one exit_frame call in reverse order.

Returns
The frame being exited.

def get_current_exception_handling_frames(self): (source) ¶

Get all exception handling frames containing the current block.

Returns

A list of frames, all of which are exception handling frames containing the current block. Any instruction contained in a try-except frame may exit to the frame's exception handling block, with the caveat that an instruction cannot exit through a TRY_FINALLY frame without passing first through the frame's finally block. (The instruction will exit to the finally block, and the finally block in turn will exit to the exception handler.) A function frame's raise block serves to catch exceptions as well.

def get_current_function_frame(self): (source) ¶

Gets the current function frame and contained current try-finally frames.

In order to exit the current function frame, we must first enter the finally blocks of all current contained try-finally frames.

Returns
A list of frames, all of which are try-finally frames except for the last, which is the current function frame. Each of the returned try-finally frames is contained within the current function frame.

def get_current_loop_frame(self): (source) ¶

Gets the current loop frame and contained current try-finally frames.

In order to exit the current loop frame, we must first enter the finally blocks of all current contained try-finally frames.

Returns
A list of frames, all of which are try-finally frames except for the last, which is the current loop frame. Each of the returned try-finally frames is contained within the current loop frame.

def handle_argument_defaults(self, node, current_block): (source) ¶

Add Instructions for all of a FunctionDef's default values.

Note that these instructions are in the block containing the function, not in the function definition itself.

def handle_argument_writes(self, node, current_block): (source) ¶

Add Instructions for all of a FunctionDef's arguments.

These instructions are part of a function's body.

def handle_ExceptHandler(self, handler, handler_block, handler_body_block, final_block, previous_handler_block_end=None): (source) ¶

Create the blocks appropriate for an exception handler.

Note that rather than having a visit_ExceptHandler function, we instead use the following logic. This is because except statements don't follow the visitor pattern exactly. Specifically, a handler may exit to either its body or to the next handler, but under the visitor pattern the handler would not know the block belonging to the next handler.

Parameters
handler	The AST ExceptHandler node.
handler_block	The block corresponding the ExceptHandler header.
handler_body_block	The block corresponding to the ExceptHandler body.
final_block	Where the handler body should exit to when it executes successfully.
previous_handler_block_end	The last block corresponding to the previous ExceptHandler header, if there is one, or None otherwise. The previous handler's header should exit to this handler's header if the exception doesn't match the previous handler's header.
Returns
The last (usually the only) block in the handler's header.

def handle_ExitStatement(self, node, next_block, try_finally_frames, current_block): (source) ¶

A helper fn for Return, Continue, and Break.

An exit statement is a statement such as return, continue, break, or raise. Such a statement causes control to leave through a frame's exit. Any instructions immediately following an exit statement will be unreachable.

Blocks:

current_block: This is where the exit statement resides. next_block: The block the exit statement exits to (after first passing

through all the finally blocks.)

final_block: The start of a finally section that control must pass: through on the way to next_block.
final_block_end: The end of a finally section that control must pass: through on the way to next_block.
after_block: An unreachable block for code that follows the raise: statement.

Parameters
node	The AST node of the exit statement.
next_block	The block the exit statement exits to.
try_finally_frames	A possibly empty list of try-finally frames whose finally blocks must be executed before control can pass to next_block.
current_block	The block the exit statement resides in.

def handle_function_definition(self, node, name, args, body): (source) ¶

A helper fn for Lambda and FunctionDef.

Note that this function doesn't require a block as input, since it doesn't modify the blocks where the function definition resides.

Blocks:

entry_block: The block where control flow starts when the function is: called.

return_block: The block the function returns to. raise_block: The block the function raises uncaught exceptions to. fn_block: The first used block of the FunctionDef.

Parameters
node	The AST node of the function definition, either a FunctionDef or Lambda node.
name	The function's name, a string.
args	The function's args, an ast.arguments node.
body	The function's body, a list of AST nodes.

def handle_Loop(self, node, loop_instruction, current_block): (source) ¶

A helper fn for For and While.

Blocks:

current_block: This is where the loop resides. test_block: Contains the part of the loop header that is repeated. For a

While, this is the loop condition. For a For, this is assignment to the target variable.

test_block_end: The last block in the test (often the same as test_block.) body_block: The body of the loop. else_block: Executed if the loop terminates naturally. after_block: Follows the completion of the loop.

Parameters
node	The AST node representing the loop.
loop_instruction	The Instruction in the loop header, such as a test or an assignment from an iterator.
current_block	The BasicBlock containing the loop.

def new_block(self, node=None, label=None, prunable=True): (source) ¶

Create a new block.

def raise_through_frames(self, block, interrupting=True, except_branch=None): (source) ¶

Adds exits for the control flow of a raised exception.

interrupting means the exit can occur at any point (exit_from_middle). not interrupting means the exit can only occur at the end of the block.

The reason to raise_through_frames with interrupting=False is for an exception that already has been partially raised, but has passed control to a finally block, and is now being raised at the end of that finally block.

Parameters
block	The block where the exception's control flow begins.
interrupting	Whether the exception can be raised from any point in block. If False, the exception is only raised from the end of block.
except_branch	False indicates the node raising is doing so the because an exception header did not match the raised error. None indicates otherwise.

def run(self, node): (source) ¶

Undocumented

def visit(self, node, current_block): (source) ¶

Visit node, either an AST node or a list.

Parameters
node	The AST node being visited. Not necessarily an instance of ast.AST; node may also be a list, primitive, or Instruction.
current_block	The basic block whose execution necessarily precedes the execution of `node`.
Returns
The final basic block for the node.

def visit_Break(self, node, current_block): (source) ¶

Visit a Break node of the AST.

Blocks:: current_block: This is where the break statement resides. break_block: The block that the containing loop exits to.

Raises
`RuntimeError`	If a break AST node is visited while not in a loop frame.

def visit_ClassDef(self, node, current_block): (source) ¶

Visit a ClassDef node of the AST.

Blocks:: current_block: The block in which the class is defined.

def visit_Continue(self, node, current_block): (source) ¶

Visit a Continue node of the AST.

Blocks:: current_block: This is where the continue statement resides. continue_block: The block of the containing loop's header. For a For,

this is the target variable assignment. For a While, this is the loop condition.

Raises
`RuntimeError`	If a continue AST node is visited while not in a loop frame.

def visit_For(self, node, current_block): (source) ¶

Visit a For node of the AST.

Blocks:: current_block: This is where the for statement resides.

def visit_FunctionDef(self, node, current_block): (source) ¶

Visit a FunctionDef node of the AST.

Blocks:: current_block: The block in which the function is defined.

def visit_If(self, node, current_block): (source) ¶

Visit an If node of the AST.

Blocks:

current_block: This is where the if statement resides. The if statement's: test is added here.
after_block: The block to which control is passed after the if statement: is completed.

true_block: The true branch of the if statements. false_block: The false branch of the if statements.

def visit_Lambda(self, node, current_block): (source) ¶

Visit a Lambda node of the AST.

Blocks:: current_block: The block in which the lambda is defined.

def visit_list(self, items, current_block): (source) ¶

Visit each of the items in a list from the AST.

def visit_Module(self, node, current_block): (source) ¶

Undocumented

def visit_Raise(self, node, current_block): (source) ¶

Visit a Raise node of the AST.

Blocks:: current_block: This is where the raise statement resides. after_block: An unreachable block for code that follows the raise

statement.

def visit_Return(self, node, current_block): (source) ¶

Visit a Return node of the AST.

Blocks:: current_block: This is where the return statement resides. return_block: The containing function's return block. All successful exits

from the function lead here.

Raises
`RuntimeError`	If a return AST node is visited while not in a function frame.

def visit_Try(self, node, current_block): (source) ¶

Visit a Try node of the AST.

Blocks:

current_block: This is where the try statement resides. after_block: The block to which control flows after the conclusion of the

full try statement (including e.g. the else and finally sections, if present).

handler_blocks: A list of blocks corresponding to the except statements. bare_handler_block: The handler block corresponding to a bare except

statement. One of handler_blocks or None.

handler_body_blocks: A list of blocks corresponding to the bodies of the: except sections.

final_block: The block corresponding to the finally section. final_block_end: The last block corresponding to the finally section. try_block: The block corresponding to the try section. try_block_end: The last block corresponding to the try section. else_block: The block corresponding to the else section.

def visit_While(self, node, current_block): (source) ¶

Visit a While node of the AST.

Blocks:: current_block: This is where the while statement resides.

def visit_Yield(self, node, current_block): (source) ¶

Visit a Yield node of the AST.

The current implementation of yields allows control to flow directly through a yield statement. TODO(dbieber): Introduce a <yield> node in between yielding and resuming execution. TODO(dbieber): Yield nodes aren't even visited since they are contained in Expr nodes. Determine if Yield can occur outside of an Expr. Check for Yield when visiting Expr.

frames: list = (source) ¶

The current frames. Each frame in this list contains all frames that come after it in the list.

graph = (source) ¶

The control flow graph being generated by the visitor.