16159241666

Committed 09 Jul 2025 02:59AM UTC coverage: 92.899% (-0.006%) from 92.905%

Build # 16159241666

Build Type

Pull #1198

github

Committed by

web-flow

Commit Message

Merge 96b08cb69 into d4ea6b063

Pull Request Pull Request #1198: Added Dark Mode to PythonTA Web Reporter

Run Details

3480 of 3746 relevant lines covered (92.9%)

17.52 hits per line

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

92.23

/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 logging
import os.path
import sys
from typing import TYPE_CHECKING, Any, Optional

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

from .visitor import CFGVisitor

if TYPE_CHECKING:
    from ..transforms.z3_visitor import Z3Visitor
    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,
    z3_enabled: bool = False,
) -> 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.
        z3_enabled (bool): An option that enables z3 when True (by default False).
    """
    _generate(mod=mod, auto_open=auto_open, visitor_options=visitor_options, z3_enabled=z3_enabled)


def _generate(
    mod: str = "",
    auto_open: bool = False,
    visitor_options: Optional[dict[str, Any]] = None,
    z3_enabled: bool = False,
) -> 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 enabled
    if z3_enabled:
        try:
            from ..transforms.z3_visitor import Z3Visitor

        except ImportError:
            logging.error("Failed to import Z3Visitor. Aborting.")
            raise
        z3v = Z3Visitor()
        module = z3v.visitor.visit(module)

    visitor = CFGVisitor(options=visitor_options, z3_enabled=z3_enabled)
    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 block.statements and isinstance(block.statements[0], nodes.Pattern):
        label = f"case {html.escape(block.statements[0].as_string())}"
        label += f" if {block.statements[1].as_string()}" if len(block.statements) == 2 else ""

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

pyta-uoft / pyta / 16159241666

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