pytype.typegraph.cfg_utils

module documentation
(source)

Utilities for working with the CFG.

Class ComplexityLimit A class that raises TooComplexError if we hit a limit.
Exception TooComplexError Thrown if we determine that something in our program is too complex.
Function compute_predecessors Build a transitive closure.
Function deep_variable_product Take the deep Cartesian product of a list of Variables.
Function merge_bindings Create a combined Variable for a list of bindings.
Function merge_variables Create a combined Variable for a list of variables.
Function order_nodes Build an ancestors first traversal of CFG nodes.
Function topological_sort Sort a list of nodes topologically.
Function variable_product Take the Cartesian product of a number of Variables.
Function variable_product_dict Take the Cartesian product of variables in the values of a dict.
Function walk_binding Helper function to walk a binding's origins.
Constant DEEP_VARIABLE_LIMIT Undocumented
Function _deep_values_list_product Take the deep Cartesian product of a list of list of Values.
Function _variable_product_items Take the Cartesian product of a list of (key, value) tuples.
def compute_predecessors(nodes): (source)

Build a transitive closure. For a list of nodes, compute all the predecessors of each node. Args: nodes: A list of nodes or blocks. Returns: A dictionary that maps each node to a set of all the nodes that can reach that node.

def deep_variable_product(variables, limit=DEEP_VARIABLE_LIMIT): (source)

Take the deep Cartesian product of a list of Variables. For example: x1.children = {v2, v3} v1 = {x1, x2} v2 = {x3} v3 = {x4, x5} v4 = {x6} then deep_variable_product([v1, v4]) will return: [[x1, x3, x4, x6], [x1, x3, x5, x6], [x2, x6]] . Args: variables: A sequence of Variables. limit: How many results we allow before aborting. Returns: A list of lists of Values, where each sublist has one Value from each of the corresponding Variables and the Variables of their Values' children. Raises: TooComplexError: If we expanded too many values.

def merge_bindings(program, node, bindings): (source)

Create a combined Variable for a list of bindings. Args: program: A cfg.Program instance. node: The current CFG node. bindings: A list of cfg.Bindings. Returns: A cfg.Variable.

def merge_variables(program, node, variables): (source)

Create a combined Variable for a list of variables. The purpose of this function is to create a final result variable for functions that return a list of "temporary" variables. (E.g. function calls). Args: program: A cfg.Program instance. node: The current CFG node. variables: A list of cfg.Variables. Returns: A cfg.Variable.

def order_nodes(nodes): (source)

Build an ancestors first traversal of CFG nodes. This guarantees that at least one predecessor of a block is scheduled before the block itself, and it also tries to schedule as many of them before the block as possible (so e.g. if two branches merge in a node, it prefers to process both the branches before that node). Args: nodes: A list of nodes or blocks. They have two attributes: "incoming" and "outgoing". Both are lists of other nodes. Returns: A list of nodes in the proper order.

def topological_sort(nodes): (source)

Sort a list of nodes topologically. This will order the nodes so that any node that appears in the "incoming" list of another node n2 will appear in the output before n2. It assumes that the graph doesn't have any cycles. If there are multiple ways to sort the list, a random one is picked. Args: nodes: A sequence of nodes. Each node may have an attribute "incoming", a list of nodes (every node in this list needs to be in "nodes"). If "incoming" is not there, it's assumed to be empty. The list of nodes can't have duplicates. Yields: The nodes in their topological order. Raises: ValueError: If the graph contains a cycle.

def variable_product(variables): (source)

Take the Cartesian product of a number of Variables. Args: variables: A sequence of Variables. Returns: A list of lists of Values, where each sublist has one element from each of the given Variables.

def variable_product_dict(variabledict, limit=DEEP_VARIABLE_LIMIT): (source)

Take the Cartesian product of variables in the values of a dict. This Cartesian product is taken using the dict keys as the indices into the input and output dicts. So: variable_product_dict({"x": Variable(a, b), "y": Variable(c, d)}) == [{"x": a, "y": c}, {"x": a, "y": d}, {"x": b, "y": c}, {"x": b, "y": d}] This is exactly analogous to a traditional Cartesian product except that instead of trying each possible value of a numbered position, we are trying each possible value of a named position. Args: variabledict: A dict with variable values. limit: How many results to allow before aborting. Returns: A list of dicts with Value values.

def walk_binding(binding, keep_binding=(lambda _: True)): (source)

Helper function to walk a binding's origins. Args: binding: A cfg.Binding. keep_binding: Optionally, a function, cfg.Binding -> bool, specifying whether to keep each binding found. Yields: A cfg.Origin. The caller must send the origin back into the generator. To stop exploring the origin, send None back.

DEEP_VARIABLE_LIMIT: int = (source)

Undocumented

Value
1024
def _deep_values_list_product(values_list, seen, complexity_limit): (source)

Take the deep Cartesian product of a list of list of Values.

def _variable_product_items(variableitems, complexity_limit): (source)

Take the Cartesian product of a list of (key, value) tuples. See variable_product_dict below. Args: variableitems: A dict mapping object to cfg.Variable. complexity_limit: A counter that tracks how many combinations we've yielded and aborts if we go over the limit. Yields: A sequence of [(key, cfg.Binding), ...] lists.