Builder

Control flow graph builder.

class py2cfg.builder.CFGBuilder(short: bool = True, treebuf: Optional[DefaultDict[str, Deque]] = None)

Control flow graph builder.

A control flow graph builder is an ast.NodeVisitor that can walk through a program’s AST and iteratively build the corresponding CFG.

add_exit(block: py2cfg.model.Block, nextblock: py2cfg.model.Block, exitcase: Union[_ast.Compare, None, _ast.BoolOp, _ast.expr] = None) → None

Add a new exit to a block.

Parameters

• block – A block to which an exit must be added.

• nextblock – The block to which control jumps from the new exit.

• exitcase – An AST node representing the ‘case’ (or condition) leading to the exit from the block in the program.

add_statement(block: py2cfg.model.Block, statement: Union[_ast.stmt, _ast.Call]) → None

Add a statement to a block.

Parameters

• block – A Block object to which a statement must be added.

• statement – An AST node representing the statement that must be added to the current block.

build(name: str, tree: _ast.Module, asynchr: bool = False, entry_id: int = 0) → py2cfg.model.CFG

Build a CFG from an AST.

Parameters

• name – The name of the CFG being built.

• tree – The root of the AST from which the CFG must be built.

• async – Boolean indicating whether the CFG being built represents an asynchronous function or not. When the CFG of a Python program is being built, it is considered like a synchronous ‘main’ function.

• entry_id – Value for the id of the entry block of the CFG.

Returns

The CFG produced from the AST.

build_from_file(name: str, filepath: str) → py2cfg.model.CFG

Build a CFG from some Python source file.

Parameters

• name – The name of the CFG being built.

• filepath – The path to the file containing the Python source code to build the CFG from.

Returns

The CFG produced from the source file.

build_from_src(name: str, src: str) → py2cfg.model.CFG

Build a CFG from some Python source code.

Parameters

• name – The name of the CFG being built.

• src – A string containing the source code to build the CFG from.

Returns

The CFG produced from the source code.

clean_cfg(block: py2cfg.model.Block, visited: List[py2cfg.model.Block] = [block:3@5 with 1 exits, body=[Assign(targets=[Tuple(elts=[Name(id='a', ctx=Store()), Name(id='b', ctx=Store())], ctx=Store())], value=Tuple(elts=[Constant(value=0, kind=None), Constant(value=1, kind=None)], ctx=Load()), type_comment=None)], block:4@6 with 1 exits, body=[While(test=Constant(value=True, kind=None), body=[Expr(value=Yield(value=Name(id='a', ctx=Load()))), Assign(targets=[Tuple(elts=[Name(id='a', ctx=Store()), Name(id='b', ctx=Store())], ctx=Store())], value=Tuple(elts=[Name(id='b', ctx=Load()), BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Name(id='b', ctx=Load()))], ctx=Load()), type_comment=None)], orelse=[])], block:5@7 with 1 exits, body=[Expr(value=Yield(value=Name(id='a', ctx=Load())))], block:7@8 with 1 exits, body=[Assign(targets=[Tuple(elts=[Name(id='a', ctx=Store()), Name(id='b', ctx=Store())], ctx=Store())], value=Tuple(elts=[Name(id='b', ctx=Load()), BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Name(id='b', ctx=Load()))], ctx=Load()), type_comment=None)], empty block:6 with 0 exits, block:1@4 with 1 exits, body=[FunctionDef(name='fib', args=arguments(posonlyargs=[], args=[], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Tuple(elts=[Name(id='a', ctx=Store()), Name(id='b', ctx=Store())], ctx=Store())], value=Tuple(elts=[Constant(value=0, kind=None), Constant(value=1, kind=None)], ctx=Load()), type_comment=None), While(test=Constant(value=True, kind=None), body=[Expr(value=Yield(value=Name(id='a', ctx=Load()))), Assign(targets=[Tuple(elts=[Name(id='a', ctx=Store()), Name(id='b', ctx=Store())], ctx=Store())], value=Tuple(elts=[Name(id='b', ctx=Load()), BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Name(id='b', ctx=Load()))], ctx=Load()), type_comment=None)], orelse=[])], decorator_list=[], returns=None, type_comment=None), Assign(targets=[Name(id='fib_gen', ctx=Store())], value=Call(func=Name(id='fib', ctx=Load()), args=[], keywords=[]), type_comment=None)], block:10@12 with 1 exits, body=[For(target=Name(id='_', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=10, kind=None)], keywords=[]), body=[Expr(value=Call(func=Name(id='next', ctx=Load()), args=[Name(id='fib_gen', ctx=Load())], keywords=[]))], orelse=[], type_comment=None)], block:12@13 with 1 exits, body=[Expr(value=Call(func=Name(id='next', ctx=Load()), args=[Name(id='fib_gen', ctx=Load())], keywords=[]))], empty block:13 with 0 exits, block:5@3 with 1 exits, body=[Assign(targets=[Name(id='i', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='arr', ctx=Store())], value=List(elts=[], ctx=Load()), type_comment=None), Assign(targets=[Name(id='size', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), op=Add(), right=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])), type_comment=None)], block:8@7 with 2 exits, body=[For(target=Name(id='k', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=0, kind=None), Name(id='size', ctx=Load())], keywords=[]), body=[Assign(targets=[Name(id='lSentinel', ctx=Store())], value=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), type_comment=None), Assign(targets=[Name(id='rSentinel', ctx=Store())], value=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), type_comment=None), If(test=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])])])], orelse=[], type_comment=None)], block:10@8 with 1 exits, body=[Assign(targets=[Name(id='lSentinel', ctx=Store())], value=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), type_comment=None), Assign(targets=[Name(id='rSentinel', ctx=Store())], value=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), type_comment=None)], block:14@10 with 2 exits, body=[If(test=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])])])], block:16@11 with 1 exits, body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], empty block:17 with 0 exits, block:18@13 with 2 exits, body=[If(test=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])])], block:20@14 with 1 exits, body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], empty block:21 with 0 exits, block:22@16 with 2 exits, body=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])], block:23@17 with 1 exits, body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], empty block:24 with 0 exits, block:25@20 with 1 exits, body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], block:11@23 with 0 exits, body=[Return(value=Name(id='arr', ctx=Load()))], block:33@26 with 1 exits, body=[Assign(targets=[Name(id='n', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[]), op=Div(), right=Constant(value=2, kind=None)), type_comment=None), Assign(targets=[Name(id='l', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Constant(value=0, kind=None), upper=Name(id='n', ctx=Load()), step=None), ctx=Load()), type_comment=None), Assign(targets=[Name(id='r', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Name(id='n', ctx=Load()), upper=None, step=None), ctx=Load()), type_comment=None)], block:35@29 with 2 exits, body=[If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='l', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), type_comment=None)], orelse=[])], block:37@30 with 1 exits, body=[Assign(targets=[Name(id='l', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), type_comment=None)], block:38@31 with 2 exits, body=[If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='r', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), type_comment=None)], orelse=[])], block:41@32 with 1 exits, body=[Assign(targets=[Name(id='r', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), type_comment=None)], block:42@34 with 1 exits, body=[Assign(targets=[Name(id='src', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge', ctx=Load()), args=[Name(id='l', ctx=Load()), Name(id='r', ctx=Load())], keywords=[]), type_comment=None)], block:45@35 with 0 exits, body=[Return(value=Name(id='src', ctx=Load()))], block:49@38 with 1 exits, body=[Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=1, kind=None), type_comment=None)], block:50@39 with 2 exits, body=[For(target=Name(id='j', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=1, kind=None), Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[])], keywords=[]), body=[Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='j', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Name(id='key', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load()), type_comment=None)], orelse=[], type_comment=None)], block:53@40 with 1 exits, body=[Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='j', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Name(id='key', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load()), type_comment=None)], block:54@42 with 2 exits, body=[While(test=BoolOp(op=And(), values=[Compare(left=Name(id='i', ctx=Load()), ops=[GtE()], comparators=[Constant(value=0, kind=None)]), Compare(left=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[GtE()], comparators=[Name(id='key', ctx=Load())])]), body=[Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), type_comment=None), Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='i', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Name(id='key', ctx=Load()), type_comment=None)], orelse=[])], block:55@43 with 1 exits, body=[Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), type_comment=None), Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='i', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Name(id='key', ctx=Load()), type_comment=None)], block:56@46 with 0 exits, body=[Return(value=Name(id='src', ctx=Load()))], block:3@2 with 0 exits, body=[FunctionDef(name='merge', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='l', annotation=None, type_comment=None), arg(arg='r', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='i', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='arr', ctx=Store())], value=List(elts=[], ctx=Load()), type_comment=None), Assign(targets=[Name(id='size', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), op=Add(), right=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])), type_comment=None), For(target=Name(id='k', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=0, kind=None), Name(id='size', ctx=Load())], keywords=[]), body=[Assign(targets=[Name(id='lSentinel', ctx=Store())], value=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), type_comment=None), Assign(targets=[Name(id='rSentinel', ctx=Store())], value=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), type_comment=None), If(test=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])])])], orelse=[], type_comment=None), Return(value=Name(id='arr', ctx=Load()))], decorator_list=[], returns=None, type_comment=None), FunctionDef(name='merge_sort', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='src', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='n', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[]), op=Div(), right=Constant(value=2, kind=None)), type_comment=None), Assign(targets=[Name(id='l', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Constant(value=0, kind=None), upper=Name(id='n', ctx=Load()), step=None), ctx=Load()), type_comment=None), Assign(targets=[Name(id='r', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Name(id='n', ctx=Load()), upper=None, step=None), ctx=Load()), type_comment=None), If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='l', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), type_comment=None)], orelse=[]), If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='r', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), type_comment=None)], orelse=[]), Assign(targets=[Name(id='src', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge', ctx=Load()), args=[Name(id='l', ctx=Load()), Name(id='r', ctx=Load())], keywords=[]), type_comment=None), Return(value=Name(id='src', ctx=Load()))], decorator_list=[], returns=None, type_comment=None), FunctionDef(name='insertion_sort', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='src', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=1, kind=None), type_comment=None), For(target=Name(id='j', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=1, kind=None), Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[])], keywords=[]), body=[Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='j', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Name(id='key', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load()), type_comment=None)], orelse=[], type_comment=None), While(test=BoolOp(op=And(), values=[Compare(left=Name(id='i', ctx=Load()), ops=[GtE()], comparators=[Constant(value=0, kind=None)]), Compare(left=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[GtE()], comparators=[Name(id='key', ctx=Load())])]), body=[Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), type_comment=None), Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='i', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Name(id='key', ctx=Load()), type_comment=None)], orelse=[]), Return(value=Name(id='src', ctx=Load()))], decorator_list=[], returns=None, type_comment=None)], block:1@1 with 0 exits, body=[ClassDef(name='Sort', bases=[], keywords=[], body=[FunctionDef(name='merge', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='l', annotation=None, type_comment=None), arg(arg='r', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='i', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=0, kind=None), type_comment=None), Assign(targets=[Name(id='arr', ctx=Store())], value=List(elts=[], ctx=Load()), type_comment=None), Assign(targets=[Name(id='size', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), op=Add(), right=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])), type_comment=None), For(target=Name(id='k', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=0, kind=None), Name(id='size', ctx=Load())], keywords=[]), body=[Assign(targets=[Name(id='lSentinel', ctx=Store())], value=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), type_comment=None), Assign(targets=[Name(id='rSentinel', ctx=Store())], value=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), type_comment=None), If(test=Compare(left=Name(id='i', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Name(id='j', ctx=Load()), ops=[Eq()], comparators=[Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[])]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[If(test=Compare(left=Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[LtE()], comparators=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())]), body=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='l', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='i', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))], orelse=[Expr(value=Call(func=Attribute(value=Name(id='arr', ctx=Load()), attr='append', ctx=Load()), args=[Subscript(value=Name(id='r', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load())], keywords=[])), AugAssign(target=Name(id='j', ctx=Store()), op=Add(), value=Constant(value=1, kind=None))])])])], orelse=[], type_comment=None), Return(value=Name(id='arr', ctx=Load()))], decorator_list=[], returns=None, type_comment=None), FunctionDef(name='merge_sort', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='src', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='n', ctx=Store())], value=BinOp(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[]), op=Div(), right=Constant(value=2, kind=None)), type_comment=None), Assign(targets=[Name(id='l', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Constant(value=0, kind=None), upper=Name(id='n', ctx=Load()), step=None), ctx=Load()), type_comment=None), Assign(targets=[Name(id='r', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Slice(lower=Name(id='n', ctx=Load()), upper=None, step=None), ctx=Load()), type_comment=None), If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='l', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='l', ctx=Load())], keywords=[]), type_comment=None)], orelse=[]), If(test=Compare(left=Call(func=Name(id='len', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), ops=[Gt()], comparators=[Constant(value=1, kind=None)]), body=[Assign(targets=[Name(id='r', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge_sort', ctx=Load()), args=[Name(id='r', ctx=Load())], keywords=[]), type_comment=None)], orelse=[]), Assign(targets=[Name(id='src', ctx=Store())], value=Call(func=Attribute(value=Name(id='self', ctx=Load()), attr='merge', ctx=Load()), args=[Name(id='l', ctx=Load()), Name(id='r', ctx=Load())], keywords=[]), type_comment=None), Return(value=Name(id='src', ctx=Load()))], decorator_list=[], returns=None, type_comment=None), FunctionDef(name='insertion_sort', args=arguments(posonlyargs=[], args=[arg(arg='self', annotation=None, type_comment=None), arg(arg='src', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[Assign(targets=[Name(id='j', ctx=Store())], value=Constant(value=1, kind=None), type_comment=None), For(target=Name(id='j', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=1, kind=None), Call(func=Name(id='len', ctx=Load()), args=[Name(id='src', ctx=Load())], keywords=[])], keywords=[]), body=[Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='j', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Name(id='key', ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='j', ctx=Load())), ctx=Load()), type_comment=None)], orelse=[], type_comment=None), While(test=BoolOp(op=And(), values=[Compare(left=Name(id='i', ctx=Load()), ops=[GtE()], comparators=[Constant(value=0, kind=None)]), Compare(left=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), ops=[GtE()], comparators=[Name(id='key', ctx=Load())])]), body=[Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=Name(id='i', ctx=Load())), ctx=Load()), type_comment=None), Assign(targets=[Name(id='i', ctx=Store())], value=BinOp(left=Name(id='i', ctx=Load()), op=Sub(), right=Constant(value=1, kind=None)), type_comment=None), Assign(targets=[Subscript(value=Name(id='src', ctx=Load()), slice=Index(value=BinOp(left=Name(id='i', ctx=Load()), op=Add(), right=Constant(value=1, kind=None))), ctx=Store())], value=Name(id='key', ctx=Load()), type_comment=None)], orelse=[]), Return(value=Name(id='src', ctx=Load()))], decorator_list=[], returns=None, type_comment=None)], decorator_list=[])]]) → None

Remove the useless (empty) blocks from a CFG.

Parameters

• block – The block from which to start traversing the CFG to clean it.

• visited – A list of blocks that already have been visited by clean_cfg (recursive function).

new_block(statement=None) → py2cfg.model.Block

Create a new block with a new id.

Returns

A Block object with a new unique id.

new_classCFG(node: _ast.ClassDef, asynchr: bool = False) → None

Create a new sub-CFG for a class definition and add it to the class CFGs of the CFG being built.

Parameters

• node – The AST node containing the class definition.

• async – Boolean indicating whether the class for which the CFG is being built is asynchronous or not.

new_func_block() → py2cfg.model.FuncBlock

Create a new function block with a new id.

Returns

A FuncBlock object with a new unique id.

new_functionCFG(node: _ast.FunctionDef, asynchr: bool = False) → None

Create a new sub-CFG for a function definition and add it to the function CFGs of the CFG being built.

Parameters

• node – The AST node containing the function definition.

• async – Boolean indicating whether the function for which the CFG is being built is asynchronous or not.

new_loopguard() → py2cfg.model.Block

Create a new block for a loop’s guard if the current block is not empty. Links the current block to the new loop guard.

Returns

The block to be used as new loop guard.

class py2cfg.builder.TryEnum(value)

An enumeration.

py2cfg.builder.invert(node: Union[_ast.Compare, _ast.expr]) → Union[ast.NameConstant, _ast.UnaryOp, _ast.Compare]

Invert the operation in an ast node object (get its negation).

Parameters

node – An ast node object.

Returns

An ast node object containing the inverse (negation) of the input node.

py2cfg.builder.merge_exitcases(exit1: Optional[Union[_ast.Compare, _ast.BoolOp, _ast.expr]], exit2: Optional[Union[_ast.Compare, _ast.BoolOp, _ast.expr]]) → Optional[Union[_ast.Compare, _ast.BoolOp, _ast.expr]]

Merge the exitcases of two Links.

Parameters

• exit1 – The exitcase of a Link object.

• exit2 – Another exitcase to merge with exit1.

Returns

The merged exitcases.