15791974148

Committed 21 Jun 2025 04:11AM UTC coverage: 92.849% (+0.03%) from 92.821%

Build # 15791974148

Build Type

Pull #1190

github

Committed by

web-flow

Commit Message

Merge b652ed720 into 02ddeab02

Pull Request Pull Request #1190: Simplify Combined Z3 Preconditions in z3_visitor.py Using z3.simplify

Run Details

4 of 4 new or added lines in 1 file covered. (100.0%)

26 existing lines in 5 files now uncovered.

3428 of 3692 relevant lines covered (92.85%)

17.54 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.95

/python_ta/cfg/cfg_generator.py

"""
Provides a function to generate and display the control flow graph of a given module.
"""

from __future__ import annotations

import html
import importlib.util
import os.path
import sys
from typing import TYPE_CHECKING, Any, Optional

import graphviz
from astroid import nodes
from astroid.builder import AstroidBuilder

try:
    from ..transforms.z3_visitor import Z3Visitor

    z3_dependency_available = True
except ImportError:
    Z3Visitor = Any
    z3_dependency_available = False
from .visitor import CFGVisitor

if TYPE_CHECKING:
    from .graph import CFGBlock, ControlFlowGraph

GRAPH_OPTIONS = {"format": "svg", "node_attr": {"shape": "box", "fontname": "Courier New"}}
SUBGRAPH_OPTIONS = {"fontname": "Courier New"}


def generate_cfg(
    mod: str = "", auto_open: bool = False, visitor_options: Optional[dict[str, Any]] = None
) -> None:
    """Generate a control flow graph for the given module.

    Supported Options:
      - "separate-condition-blocks": bool
            This option specifies whether the test condition of an if statement gets merged with any
            preceding statements or placed in a new block. By default, it will merge them.
      - "functions": list[str]
            This option specifies whether to restrict the creation of cfgs to just top-level
            function definitions or methods provided in this list. By default, it will create the
            cfg for the entire file.

    Args:
        mod (str): The path to the module. `mod` can either be the path of a file (must have `.py`
            extension) or have no argument (generates a CFG for the Python file from which this
            function is called).
        auto_open (bool): Automatically open the graph in your browser.
        visitor_options (dict): An options dict to configure how the cfgs are generated.
    """
    _generate(mod=mod, auto_open=auto_open, visitor_options=visitor_options)


def _generate(
    mod: str = "", auto_open: bool = False, visitor_options: Optional[dict[str, Any]] = None
) -> None:
    """Generate a control flow graph for the given module.

    `mod` can either be:
      - the path of a file (must have `.py` extension).
      - no argument -- generate a CFG for the Python file from which this function is called.
    """
    # Generate a control flow graph for the given file
    abs_path = _get_valid_file_path(mod)
    # Print an error message if the file is not valid and early return
    if abs_path is None:  # _get_valid_file_path returns None in case of invalid file
        return

    file_name = os.path.splitext(os.path.basename(abs_path))[0]
    module = AstroidBuilder().file_build(abs_path)

    # invoke Z3Visitor if z3 dependency is available
    if z3_dependency_available:
        z3v = Z3Visitor()
        module = z3v.visitor.visit(module)

    visitor = CFGVisitor(options=visitor_options)
    module.accept(visitor)

    _display(visitor.cfgs, file_name, auto_open=auto_open)


def _get_valid_file_path(mod: str = "") -> Optional[str]:
    """Return the valid absolute path of `mod`, a path to the target file."""
    # Allow call to check with empty args
    if mod == "":
        m = sys.modules["__main__"]
        spec = importlib.util.spec_from_file_location(m.__name__, m.__file__)
        mod = spec.origin
    # Enforce the API to only except `mod` type as str
    elif not isinstance(mod, str):
        print(
            "No CFG generated. Input to check, `{}`, has invalid type, must be a string.".format(
                mod
            )
        )
        return

    # At this point, `mod` is of type str
    if not os.path.isfile(mod):
        # `mod` is not a file so print an error message
        print("Could not find the file called, `{}`\n".format(mod))
        return

    # `mod` may be a relative path to a valid file so return its absolute path
    return os.path.abspath(mod)


def _display(
    cfgs: dict[nodes.NodeNG, ControlFlowGraph], filename: str, auto_open: bool = False
) -> None:
    graph = graphviz.Digraph(name=filename + ".gv", **GRAPH_OPTIONS)
    for node, cfg in cfgs.items():
        if isinstance(node, nodes.Module):
            subgraph_label = "__main__"
        elif isinstance(node, nodes.FunctionDef):
            scope_parent = node.scope().parent
            subgraph_label = node.name
            # Update the label to the qualified name if it is a method
            if isinstance(scope_parent, nodes.ClassDef):
                subgraph_label = scope_parent.name + "." + subgraph_label
        else:
            continue
        with graph.subgraph(name=f"cluster_{cfg.cfg_id}") as c:
            visited = set()
            _visit(cfg.start, c, visited, cfg.end)
            for block in cfg.unreachable_blocks:
                _visit(block, c, visited, cfg.end)
            c.attr(label=subgraph_label, **SUBGRAPH_OPTIONS)

    graph.render(outfile=filename + ".svg", view=auto_open)


def _visit(block: CFGBlock, graph: graphviz.Digraph, visited: set[int], end: CFGBlock) -> None:
    """
    Visit a CFGBlock and add it to the control flow graph.
    """
    node_id = f"{graph.name}_{block.id}"
    if node_id in visited:
        return

    label = ""
    fill_color = "white"

    # Identify special cases
    if len(block.statements) == 1:
        stmt = block.statements[0]
        if isinstance(stmt, nodes.Arguments):
            label = f"{stmt.as_string()}\n"
            fill_color = "palegreen"
        elif isinstance(stmt.parent, nodes.If) and stmt is stmt.parent.test:
            label = f"< if<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"
        elif isinstance(stmt.parent, nodes.While) and stmt is stmt.parent.test:
            label = f"< while<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"
        elif isinstance(stmt.parent, nodes.For) and stmt is stmt.parent.iter:
            label = f"< for {html.escape(stmt.parent.target.as_string())} in<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"
        elif isinstance(stmt.parent, nodes.For) and stmt is stmt.parent.target:
            label = f"< for<U><B>{html.escape(stmt.as_string())} </B></U> in {html.escape(stmt.parent.iter.as_string())}<BR/> >"

    if not label:  # Default
        label = "\n".join([s.as_string() for s in block.statements]) + "\n"

    # Need to escape backslashes explicitly.
    label = label.replace("\\", "\\\\")
    # \l is used for left alignment.
    label = label.replace("\n", "\\l")

    # Change the fill colour if block is the end of the cfg or unreachable
    if block == end:
        fill_color = "black"
    elif not block.reachable:
        fill_color = "grey93"

    graph.node(node_id, label=label, fillcolor=fill_color, style="filled")
    visited.add(node_id)

    for edge in block.successors:
        color = "black" if edge.is_feasible else "lightgrey"
        if edge.get_label() is not None:
            graph.edge(
                node_id, f"{graph.name}_{edge.target.id}", label=edge.get_label(), color=color
            )
        else:
            graph.edge(node_id, f"{graph.name}_{edge.target.id}", color=color)
        _visit(edge.target, graph, visited, end)

1	"""
2	Provides a function to generate and display the control flow graph of a given module.
3	"""
4
5	from __future__ import annotations	20✔
6
7	import html	20✔
8	import importlib.util	20✔
9	import os.path	20✔
10	import sys	20✔
11	from typing import TYPE_CHECKING, Any, Optional	20✔
12
13	import graphviz	20✔
14	from astroid import nodes	20✔
15	from astroid.builder import AstroidBuilder	20✔
16
17	try:	20✔
18	from ..transforms.z3_visitor import Z3Visitor	20✔
19
20	z3_dependency_available = True	10✔
21	except ImportError:	10✔
22	Z3Visitor = Any	10✔
23	z3_dependency_available = False	10✔
24	from .visitor import CFGVisitor	20✔
25
26	if TYPE_CHECKING:	20✔
UNCOV 27	from .graph import CFGBlock, ControlFlowGraph	×
28
29	GRAPH_OPTIONS = {"format": "svg", "node_attr": {"shape": "box", "fontname": "Courier New"}}	20✔
30	SUBGRAPH_OPTIONS = {"fontname": "Courier New"}	20✔
31
32
33	def generate_cfg(	20✔
34	mod: str = "", auto_open: bool = False, visitor_options: Optional[dict[str, Any]] = None
35	) -> None:
36	"""Generate a control flow graph for the given module.
37
38	Supported Options:
39	- "separate-condition-blocks": bool
40	This option specifies whether the test condition of an if statement gets merged with any
41	preceding statements or placed in a new block. By default, it will merge them.
42	- "functions": list[str]
43	This option specifies whether to restrict the creation of cfgs to just top-level
44	function definitions or methods provided in this list. By default, it will create the
45	cfg for the entire file.
46
47	Args:
48	mod (str): The path to the module. `mod` can either be the path of a file (must have `.py`
49	extension) or have no argument (generates a CFG for the Python file from which this
50	function is called).
51	auto_open (bool): Automatically open the graph in your browser.
52	visitor_options (dict): An options dict to configure how the cfgs are generated.
53	"""
54	_generate(mod=mod, auto_open=auto_open, visitor_options=visitor_options)	20✔
55
56
57	def _generate(	20✔
58	mod: str = "", auto_open: bool = False, visitor_options: Optional[dict[str, Any]] = None
59	) -> None:
60	"""Generate a control flow graph for the given module.
61
62	`mod` can either be:
63	- the path of a file (must have `.py` extension).
64	- no argument -- generate a CFG for the Python file from which this function is called.
65	"""
66	# Generate a control flow graph for the given file
67	abs_path = _get_valid_file_path(mod)	20✔
68	# Print an error message if the file is not valid and early return
69	if abs_path is None: # _get_valid_file_path returns None in case of invalid file	20✔
70	return	20✔
71
72	file_name = os.path.splitext(os.path.basename(abs_path))[0]	20✔
73	module = AstroidBuilder().file_build(abs_path)	20✔
74
75	# invoke Z3Visitor if z3 dependency is available
76	if z3_dependency_available:	20✔
77	z3v = Z3Visitor()	10✔
78	module = z3v.visitor.visit(module)	10✔
79
80	visitor = CFGVisitor(options=visitor_options)	20✔
81	module.accept(visitor)	20✔
82
83	_display(visitor.cfgs, file_name, auto_open=auto_open)	20✔
84
85
86	def _get_valid_file_path(mod: str = "") -> Optional[str]:	20✔
87	"""Return the valid absolute path of `mod`, a path to the target file."""
88	# Allow call to check with empty args
89	if mod == "":	20✔
UNCOV 90	m = sys.modules["__main__"]	×
UNCOV 91	spec = importlib.util.spec_from_file_location(m.__name__, m.__file__)	×
UNCOV 92	mod = spec.origin	×
93	# Enforce the API to only except `mod` type as str
94	elif not isinstance(mod, str):	20✔
95	print(	20✔
96	"No CFG generated. Input to check, `{}`, has invalid type, must be a string.".format(
97	mod
98	)
99	)
100	return	20✔
101
102	# At this point, `mod` is of type str
103	if not os.path.isfile(mod):	20✔
104	# `mod` is not a file so print an error message
105	print("Could not find the file called, `{}`\n".format(mod))	20✔
106	return	20✔
107
108	# `mod` may be a relative path to a valid file so return its absolute path
109	return os.path.abspath(mod)	20✔
110
111
112	def _display(	20✔
113	cfgs: dict[nodes.NodeNG, ControlFlowGraph], filename: str, auto_open: bool = False
114	) -> None:
115	graph = graphviz.Digraph(name=filename + ".gv", **GRAPH_OPTIONS)	20✔
116	for node, cfg in cfgs.items():	20✔
117	if isinstance(node, nodes.Module):	20✔
118	subgraph_label = "__main__"	20✔
119	elif isinstance(node, nodes.FunctionDef):	20✔
120	scope_parent = node.scope().parent	20✔
121	subgraph_label = node.name	20✔
122	# Update the label to the qualified name if it is a method
123	if isinstance(scope_parent, nodes.ClassDef):	20✔
124	subgraph_label = scope_parent.name + "." + subgraph_label	20✔
125	else:
UNCOV 126	continue	×
127	with graph.subgraph(name=f"cluster_{cfg.cfg_id}") as c:	20✔
128	visited = set()	20✔
129	_visit(cfg.start, c, visited, cfg.end)	20✔
130	for block in cfg.unreachable_blocks:	20✔
131	_visit(block, c, visited, cfg.end)	20✔
132	c.attr(label=subgraph_label, **SUBGRAPH_OPTIONS)	20✔
133
134	graph.render(outfile=filename + ".svg", view=auto_open)	20✔
135
136
137	def _visit(block: CFGBlock, graph: graphviz.Digraph, visited: set[int], end: CFGBlock) -> None:	20✔
138	"""
139	Visit a CFGBlock and add it to the control flow graph.
140	"""
141	node_id = f"{graph.name}_{block.id}"	20✔
142	if node_id in visited:	20✔
143	return	20✔
144
145	label = ""	20✔
146	fill_color = "white"	20✔
147
148	# Identify special cases
149	if len(block.statements) == 1:	20✔
150	stmt = block.statements[0]	20✔
151	if isinstance(stmt, nodes.Arguments):	20✔
152	label = f"{stmt.as_string()}\n"	20✔
153	fill_color = "palegreen"	20✔
154	elif isinstance(stmt.parent, nodes.If) and stmt is stmt.parent.test:	20✔
155	label = f"< if<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"	20✔
156	elif isinstance(stmt.parent, nodes.While) and stmt is stmt.parent.test:	20✔
157	label = f"< while<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"	20✔
158	elif isinstance(stmt.parent, nodes.For) and stmt is stmt.parent.iter:	20✔
159	label = f"< for {html.escape(stmt.parent.target.as_string())} in<U><B>{html.escape(stmt.as_string())}</B></U><BR/> >"	20✔
160	elif isinstance(stmt.parent, nodes.For) and stmt is stmt.parent.target:	20✔
161	label = f"< for<U><B>{html.escape(stmt.as_string())} </B></U> in {html.escape(stmt.parent.iter.as_string())}<BR/> >"	20✔
162
163	if not label: # Default	20✔
164	label = "\n".join([s.as_string() for s in block.statements]) + "\n"	20✔
165
166	# Need to escape backslashes explicitly.
167	label = label.replace("\\", "\\\\")	20✔
168	# \l is used for left alignment.
169	label = label.replace("\n", "\\l")	20✔
170
171	# Change the fill colour if block is the end of the cfg or unreachable
172	if block == end:	20✔
173	fill_color = "black"	20✔
174	elif not block.reachable:	20✔
175	fill_color = "grey93"	20✔
176
177	graph.node(node_id, label=label, fillcolor=fill_color, style="filled")	20✔
178	visited.add(node_id)	20✔
179
180	for edge in block.successors:	20✔
181	color = "black" if edge.is_feasible else "lightgrey"	20✔
182	if edge.get_label() is not None:	20✔
183	graph.edge(	20✔
184	node_id, f"{graph.name}_{edge.target.id}", label=edge.get_label(), color=color
185	)
186	else:
187	graph.edge(node_id, f"{graph.name}_{edge.target.id}", color=color)	20✔
188	_visit(edge.target, graph, visited, end)	20✔

pyta-uoft / pyta / 15791974148

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous