pymwp Analysis

from pymwp import Analysis

Analysis

MWP analysis implementation.

binary_op staticmethod

binary_op(index: int, node: Assignment) -> COM_RES

Analyze binary operation, e.g. x = y + z.

Parameters:

Name	Type	Description	Default
index	int	delta index	required
node	Assignment	AST node representing a binary operation	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

cmds staticmethod

cmds(
    relations: RelationList, index: int, nodes: List[Node], stop: bool = True
) -> Tuple[bool, int]

Analyze some list of commands, typically body block statements.

Parameters:

Name	Type	Description	Default
relations	RelationList	Initialized relation list.	required
index	int	Derivation index.	required
nodes	List[Node]	List of AST nodes to analyze.	required
stop	bool	Set True to terminate early.	True

Returns:

Type	Description
Tuple[bool, int]	True if nodes lead to infinity by delta graph.

compound staticmethod

compound(index: int, node: Compound, dg: DeltaGraph) -> COM_RES

Compound AST node contains zero or more children and is created by braces in source code.

We analyze such compound node by recursively analysing its children.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	Compound	Compound AST node.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

compute_relation staticmethod

compute_relation(index: int, node: Node, dg: DeltaGraph) -> COM_RES

Create a relation list corresponding for all possible matrices of an AST node.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	Node	AST node to analyze.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

constant staticmethod

constant(index: int, variable_name: str) -> COM_RES

Analyze a constant assignment of form x = c where x is some variable and c is constant.

From "A Flow Calculus of mwp-Bounds..."

To deal with constants, just replace the program’s constants by variables and regard the replaced constants as input to these variables.

Parameters:

Name	Type	Description	Default
index	int	delta index	required
variable_name	str	name of variable to which constant is being assigned	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

create_vector staticmethod

create_vector(
    index: int, op: str, variables: Tuple[str, ...]
) -> Tuple[int, List[Polynomial]]

Build a polynomial vector based on operator and the operands of a binary operation statement that has form x = y (operator) z.

For an AST node that represents a binary operation, this method generates a vector of polynomials based on the properties of that operation. The returned vector depends on the type of operator, how many operands are constants, and if the operands are equal.

Parameters:

Name	Type	Description	Default
index	int	delta index	required
op	str	operator	required
variables	Tuple[str, ...]	variables in this operation x = y (op) z in order, where y or z is None if constant	required

Returns:

Type	Description
Tuple[int, List[Polynomial]]	Updated index, list of Polynomial vectors

for_loop staticmethod

for_loop(index: int, node: For, dg: DeltaGraph) -> COM_RES

Analyze for loop node.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	For	for loop node.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

func staticmethod

func(node: FuncDef, stop: bool) -> FuncResult

Analyze a function.

Parameters:

Name	Type	Description	Default
node	FuncDef	parsed C source code function node	required
stop	bool	terminate if no bound exists	required

Returns:

Type	Description
FuncResult	Analysis result for provided function.

id staticmethod

id(index: int, node: Assignment) -> COM_RES

Analyze x = y, where data flows between two variables.

Parameters:

Name	Type	Description	Default
index	int	delta index	required
node	Assignment	AST node representing a simple assignment	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

if_branch staticmethod

if_branch(
    index: int, node: If, relation_list: RelationList, dg: DeltaGraph
) -> Tuple[int, bool]

Analyze if or else branch of a conditional statement.

This method will analyze the body of the statement and update the provided relation. It can handle blocks with or without surrounding braces. It will return the updated index value.

If branch does not exist (when else case is omitted) this method does nothing and returns the original index value without modification.

Parameters:

Name	Type	Description	Default
index	int	Current delta index value.	required
node	If	AST if statement branch node.	required
relation_list	RelationList	Current relation list state.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
Tuple[int, bool]	Updated index value, relation list, and an exit flag.

if_stmt staticmethod

if_stmt(index: int, node: If, dg: DeltaGraph) -> COM_RES

Analyze an if statement.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	If	if-statement AST node.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

rewrite_id_inc_dec staticmethod

rewrite_id_inc_dec(node: UnaryOp)

Converts unary ++/-- operators to binary: x = x (op) 1.

rm_cast staticmethod

rm_cast(node: Node) -> Node

If Cast node, returns the expression of cast.

run staticmethod

run(
    ast: Node,
    res: Result = None,
    fin: bool = False,
    strict: bool = False,
    **kwargs
) -> Result

Run MWP analysis on AST.

Parameters:

Name	Type	Description	Default
ast	Node	Parsed C source code AST Node.	required
res	Result	Pre-initialized result object.	None
fin	bool	Always run to completion.	False
strict	bool	Require supported syntax.	False

Returns:

Type	Description
Result	Analysis Result object.

syntax_check staticmethod

syntax_check(node: Node, strict: bool) -> bool

Analyze function syntax and conditionally modify the AST.

Parameters:

Name	Type	Description	Default
node	Node	An AST node.	required
strict	bool	When true, AST will not be modified.	required

Returns:

Type	Description
bool	True if analysis can be performed and False otherwise.

take_counts staticmethod

take_counts(ast: Node, result: Result) -> None

Calculate program statistics: functions, loops, and variables.

Parameters:

Name	Type	Description	Default
ast	Node	Parsed C source code AST Node.	required
result	Result	Pre-initialized result object.	required

unary_asgn staticmethod

unary_asgn(index: int, node: Assignment, dg: DeltaGraph) -> COM_RES

Assignment where right-hand-size is a unary op e.g. x = y++;.

Parameters:

Name	Type	Description	Default
index	int	delta index	required
node	Assignment	Node with right-side unary operation.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

unary_op staticmethod

unary_op(index: int, node: UnaryOp) -> COM_RES

Analyze a standalone unary operation.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	UnaryOp	AST node to analyze.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

while_loop staticmethod

while_loop(index: int, node: While, dg: DeltaGraph) -> COM_RES

Analyze a while loop.

Parameters:

Name	Type	Description	Default
index	int	Delta index.	required
node	pr.while	While loop node.	required
dg	DeltaGraph	DeltaGraph instance.	required

Returns:

Type	Description
COM_RES	Updated index value, relation list, and an exit flag.

LoopAnalysis

Bases: Analysis

MWP analysis for loops.

get_result staticmethod

get_result(relation: Relation, index: int, v_name: str) -> VResult

Find variable bounds when they are known to exist.

Parameters:

Name	Type	Description	Default
relation	Relation	Relation object.	required
index	int	Degree of analysis choice.	required
v_name	str	Name of variable to evaluate.	required

Returns:

Type	Description
VResult	Evaluation result for identified variable.

inspect staticmethod

inspect(node: LoopT) -> LoopResult

Analyze a loop.

Parameters:

Name	Type	Description	Default
node	LOOP_T	A loop node.	required

Returns:

Type	Description
LoopResult	Loop analysis result.

maybe_result staticmethod

maybe_result(relation: Relation, index: int) -> Dict[str, VResult]

Evaluate variables when some variables are known to fail.

Parameters:

Name	Type	Description	Default
relation	Relation	Relation object.	required
index	int	Degree of analysis choice.	required

Returns:

Type	Description
Dict[str, VResult]	Dictionary of results, for each variable in relation.

run staticmethod

run(ast: Node, res: Result = None, strict: bool = False, **kwargs) -> Result

Run loop analysis.

Parameters:

Name	Type	Description	Default
ast	Node	Parsed C source code as an AST.	required
res	Result	Pre-initialized result object.	None
strict	bool	Require supported syntax.	False

Returns:

Type	Description
Result	Analysis Result object.

syntax_check staticmethod

syntax_check(node: LoopT, strict: bool) -> bool

Analyze function syntax and conditionally modify the AST.

Parameters:

Name	Type	Description	Default
node	LOOP_T	An AST loop node.	required
strict	bool	When true, AST will not be modified.	required

Returns:

Type	Description
bool	True if analysis can be performed and False otherwise.