17566741199

Committed 08 Sep 2025 11:16PM UTC coverage: 93.778% (+0.04%) from 93.738%

Build # 17566741199

Build Type

Pull #1231

github

Committed by

web-flow

Commit Message

Merge fe3591a03 into 42d32a8cd

Pull Request Pull Request #1231: Add infinite-loop detection for `while` loops with immutable condition variables

Run Details

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

11 existing lines in 1 file now uncovered.

3557 of 3793 relevant lines covered (93.78%)

17.8 hits per line

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

88.89

/python_ta/checkers/infinite_loop_checker.py

"""Check for infinite while loops."""

import itertools
from typing import Optional

from astroid import BoundMethod, InferenceError, UnboundMethod, bases, nodes, util
from pylint.checkers import BaseChecker, utils
from pylint.interfaces import INFERENCE
from pylint.lint import PyLinter


class InfiniteLoopChecker(BaseChecker):
    name = "infinite-loop"
    msgs = {
        "W9501": (
            "Infinite while loop: loop does not terminate",
            "infinite-loop",
            """Used when a while loop is guaranteed to never terminate based on its current structure. This usually
            indicates a logical error leading to an unintended infinite loop.""",
        ),
    }

    def visit_while(self, node: nodes.While) -> None:
        checks = [
            self._check_condition_constant,
            self._check_condition_all_var_used,
            self._check_immutable_cond_var_reassigned,
        ]
        any(check(node) for check in checks)

    def _check_condition_all_var_used(self, node: nodes.While) -> bool:
        """Helper function that checks whether variables used in a while loop's condition
        are also used anywhere inside the loop body.

        Note: This is a basic check. It only flags loops where NONE of the condition variables
        appear in the body, which indicates an infinite loop.
        """
        # Get variable(s) used inside condition
        cond_vars = set()
        for child in node.test.nodes_of_class(nodes.Name):
            if not isinstance(child.parent, nodes.Call) or child.parent.func is not child:
                cond_vars.add(child.name)
        if not cond_vars:
            return False
        # Check to see if condition variable(s) used inside body
        for child in node.body:
            for name_node in child.nodes_of_class((nodes.Name, nodes.AssignName)):
                if name_node.name in cond_vars:
                    # At least one condition variable is used in the loop body
                    return False
        else:
            self.add_message(
                "infinite-loop",
                node=node.test,
            )
            return True

    def _check_condition_constant(self, node: nodes.While) -> bool:
        """Helper function that checks if a constant while-loop condition may lead to an infinite loop.

        This helper flags loops that meet **both** of the following criteria:
            - The `while` condition is constant (e.g., `while 1 < 2`)
            - The loop body contains no `return`, `break`, `raise`, `yield`, or `sys.exit()` calls
        """
        if not self._check_constant_loop_cond(
            node.test
        ) and not self._check_constant_form_condition(node):
            return False
        inferred = utils.safe_infer(node.test)
        if isinstance(inferred, util.UninferableBase) or inferred is None:
            return False
        if (
            (isinstance(inferred, nodes.Const) and bool(inferred.value) is False)
            or (isinstance(inferred, (nodes.List, nodes.Tuple, nodes.Set)) and not inferred.elts)
            or (isinstance(inferred, nodes.Dict) and not inferred.items)
        ):
            return False

        check_nodes = (nodes.Break, nodes.Return, nodes.Raise, nodes.Yield)
        for child in node.body:
            for exit_node in child.nodes_of_class(klass=(nodes.Call, *check_nodes)):
                if isinstance(exit_node, check_nodes):
                    return False
                # Check Call node to see if `sys.exit()` is called
                elif (
                    isinstance(exit_node, nodes.Call)
                    and isinstance(exit_node.func, nodes.Attribute)
                    and exit_node.func.attrname == "exit"
                ):
                    inferred = utils.safe_infer(exit_node.func.expr)
                    if (
                        not isinstance(inferred, util.UninferableBase)
                        and inferred is not None
                        and isinstance(inferred, nodes.Module)
                        and inferred.name == "sys"
                    ):
                        return False
        else:
            self.add_message("infinite-loop", node=node.test, confidence=INFERENCE)
            return True

    def _check_constant_form_condition(self, node: nodes.While) -> bool:
        """Helper function that checks if while loop condition is of constant form (e.g.: `1 < 2`, `5 - 1 >= 2 + 2`)"""
        return not any(node.test.nodes_of_class(nodes.Name))

    def _check_constant_loop_cond(self, test_node: Optional[nodes.NodeNG]) -> bool:
        """Helper function that checks if while loop condition is constant.

        See `https://github.com/pylint-dev/pylint/blob/main/pylint/checkers/base/basic_checker.py#L303` for further
        detail."""
        const_nodes = (
            nodes.Module,
            nodes.GeneratorExp,
            nodes.Lambda,
            nodes.FunctionDef,
            nodes.ClassDef,
            bases.Generator,
            UnboundMethod,
            BoundMethod,
        )
        structs = (nodes.Dict, nodes.Tuple, nodes.Set, nodes.List)
        except_nodes = (
            nodes.Call,
            nodes.BinOp,
            nodes.BoolOp,
            nodes.UnaryOp,
            nodes.Subscript,
        )
        inferred = None
        maybe_generator_call = None
        emit = isinstance(test_node, (nodes.Const, *structs, *const_nodes))
        if not isinstance(test_node, except_nodes):
            inferred = utils.safe_infer(test_node)
            # If we can't infer what the value is but the test is just a variable name
            if isinstance(inferred, util.UninferableBase) and isinstance(test_node, nodes.Name):
                emit, maybe_generator_call = InfiniteLoopChecker._name_holds_generator(test_node)

        # Emit if calling a function that only returns GeneratorExp (always tests True)
        elif isinstance(test_node, nodes.Call):
            maybe_generator_call = test_node

        if maybe_generator_call:
            inferred_call = utils.safe_infer(maybe_generator_call.func)
            if isinstance(inferred_call, nodes.FunctionDef):
                # Can't use all(x) or not any(not x) for this condition, because it
                # will return True for empty generators, which is not what we want.
                all_returns_were_generator = None
                for return_node in inferred_call._get_return_nodes_skip_functions():
                    if not isinstance(return_node.value, nodes.GeneratorExp):
                        all_returns_were_generator = False
                        break
                    all_returns_were_generator = True
                if all_returns_were_generator:
                    return True
        if emit:
            return True
        elif isinstance(inferred, const_nodes):
            return True
        return False

    @staticmethod
    def _name_holds_generator(test_node: nodes.Name) -> tuple[bool, Optional[nodes.Call]]:
        """Return whether `test` tests a name certain to hold a generator, or optionally
        a call that should be then tested to see if *it* returns only generators.

        See `https://github.com/pylint-dev/pylint/blob/main/pylint/checkers/base/basic_checker.py#L303` for further
        detail."""
        assert isinstance(test_node, nodes.Name)
        emit = False
        maybe_generator_call = None
        lookup_result = test_node.frame().lookup(test_node.name)
        if not lookup_result:
            return emit, maybe_generator_call
        maybe_generator_assigned = (
            isinstance(assign_name.parent.value, nodes.GeneratorExp)
            for assign_name in lookup_result[1]
            if isinstance(assign_name.parent, nodes.Assign)
        )
        first_item = next(maybe_generator_assigned, None)
        if first_item is not None:
            # Emit if this variable is certain to hold a generator
            if all(itertools.chain((first_item,), maybe_generator_assigned)):
                emit = True
            # If this variable holds the result of a call, save it for next test
            elif (
                len(lookup_result[1]) == 1
                and isinstance(lookup_result[1][0].parent, nodes.Assign)
                and isinstance(lookup_result[1][0].parent.value, nodes.Call)
            ):
                maybe_generator_call = lookup_result[1][0].parent.value
        return emit, maybe_generator_call

    def _check_immutable_cond_var_reassigned(self, node: nodes.While) -> bool:
        """Helper function that checks if a while-loop condition uses only immutable variables
        and none of them are reassigned inside the loop body.

        Flags loops that meet **both** of the following criteria:
        - All variables in the `while` condition are immutable (int, float, complex, bool,
          str, bytes, tuple, or NoneType)
        - None of these variables are reassigned in the loop body"""
        immutable_types = (
            int,
            float,
            bool,
            complex,
            str,
            bytes,
            tuple,
            type(None),
        )
        immutable_vars = set()
        for child in node.test.nodes_of_class(nodes.Name):
            if not isinstance(child.parent, nodes.Call) or child.parent.func is not child:
                inferred = utils.safe_infer(child)
                if isinstance(inferred, util.UninferableBase) or inferred is None:
                    continue
                # Check if type of inferred value is immutable
                if (
                    isinstance(inferred, nodes.Const) and type(inferred.value) in immutable_types
                ) or isinstance(inferred, nodes.Tuple):
                    immutable_vars.add(child.name)
                else:
                    return False
        if not immutable_vars:
            # There are no vars with immutables values
            return False

        # Infer the loop condition
        inferred_test = utils.safe_infer(node.test)
        if isinstance(inferred_test, util.UninferableBase) or inferred_test is None:
            return False
        if isinstance(inferred_test, nodes.Const) and inferred_test.value is False:
            # Condition is always false, loop won't run. No need to check for infinite loop.
            return False

        for child in node.body:
            for assign_node in child.nodes_of_class(nodes.AssignName):
                if assign_node.name in immutable_vars:
                    return False
        else:
            self.add_message(
                "infinite-loop",
                node=node.test,
                confidence=INFERENCE,
            )
            return True


def register(linter: PyLinter) -> None:
    linter.register_checker(InfiniteLoopChecker(linter))

1	"""Check for infinite while loops."""
2
3	import itertools	20✔
4	from typing import Optional	20✔
5
6	from astroid import BoundMethod, InferenceError, UnboundMethod, bases, nodes, util	20✔
7	from pylint.checkers import BaseChecker, utils	20✔
8	from pylint.interfaces import INFERENCE	20✔
9	from pylint.lint import PyLinter	20✔
10
11
12	class InfiniteLoopChecker(BaseChecker):	20✔
13	name = "infinite-loop"	20✔
14	msgs = {	20✔
15	"W9501": (
16	"Infinite while loop: loop does not terminate",
17	"infinite-loop",
18	"""Used when a while loop is guaranteed to never terminate based on its current structure. This usually
19	indicates a logical error leading to an unintended infinite loop.""",
20	),
21	}
22
23	def visit_while(self, node: nodes.While) -> None:	20✔
24	checks = [	20✔
25	self._check_condition_constant,
26	self._check_condition_all_var_used,
27	self._check_immutable_cond_var_reassigned,
28	]
29	any(check(node) for check in checks)	20✔
30
31	def _check_condition_all_var_used(self, node: nodes.While) -> bool:	20✔
32	"""Helper function that checks whether variables used in a while loop's condition
33	are also used anywhere inside the loop body.
34
35	Note: This is a basic check. It only flags loops where NONE of the condition variables
36	appear in the body, which indicates an infinite loop.
37	"""
38	# Get variable(s) used inside condition
39	cond_vars = set()	20✔
40	for child in node.test.nodes_of_class(nodes.Name):	20✔
41	if not isinstance(child.parent, nodes.Call) or child.parent.func is not child:	20✔
42	cond_vars.add(child.name)	20✔
43	if not cond_vars:	20✔
44	return False	20✔
45	# Check to see if condition variable(s) used inside body
46	for child in node.body:	20✔
47	for name_node in child.nodes_of_class((nodes.Name, nodes.AssignName)):	20✔
48	if name_node.name in cond_vars:	20✔
49	# At least one condition variable is used in the loop body
50	return False	20✔
51	else:
52	self.add_message(	20✔
53	"infinite-loop",
54	node=node.test,
55	)
56	return True	20✔
57
58	def _check_condition_constant(self, node: nodes.While) -> bool:	20✔
59	"""Helper function that checks if a constant while-loop condition may lead to an infinite loop.
60
61	This helper flags loops that meet both of the following criteria:
62	- The `while` condition is constant (e.g., `while 1 < 2`)
63	- The loop body contains no `return`, `break`, `raise`, `yield`, or `sys.exit()` calls
64	"""
65	if not self._check_constant_loop_cond(	20✔
66	node.test
67	) and not self._check_constant_form_condition(node):
68	return False	20✔
69	inferred = utils.safe_infer(node.test)	20✔
70	if isinstance(inferred, util.UninferableBase) or inferred is None:	20✔
71	return False	20✔
72	if (	20✔
73	(isinstance(inferred, nodes.Const) and bool(inferred.value) is False)
74	or (isinstance(inferred, (nodes.List, nodes.Tuple, nodes.Set)) and not inferred.elts)
75	or (isinstance(inferred, nodes.Dict) and not inferred.items)
76	):
77	return False	20✔
78
79	check_nodes = (nodes.Break, nodes.Return, nodes.Raise, nodes.Yield)	20✔
80	for child in node.body:	20✔
81	for exit_node in child.nodes_of_class(klass=(nodes.Call, *check_nodes)):	20✔
82	if isinstance(exit_node, check_nodes):	20✔
83	return False	20✔
84	# Check Call node to see if `sys.exit()` is called
85	elif (	20✔
86	isinstance(exit_node, nodes.Call)
87	and isinstance(exit_node.func, nodes.Attribute)
88	and exit_node.func.attrname == "exit"
89	):
90	inferred = utils.safe_infer(exit_node.func.expr)	20✔
91	if (	20✔
92	not isinstance(inferred, util.UninferableBase)
93	and inferred is not None
94	and isinstance(inferred, nodes.Module)
95	and inferred.name == "sys"
96	):
97	return False	20✔
98	else:
99	self.add_message("infinite-loop", node=node.test, confidence=INFERENCE)	20✔
100	return True	20✔
101
102	def _check_constant_form_condition(self, node: nodes.While) -> bool:	20✔
103	"""Helper function that checks if while loop condition is of constant form (e.g.: `1 < 2`, `5 - 1 >= 2 + 2`)"""
104	return not any(node.test.nodes_of_class(nodes.Name))	20✔
105
106	def _check_constant_loop_cond(self, test_node: Optional[nodes.NodeNG]) -> bool:	20✔
107	"""Helper function that checks if while loop condition is constant.
108
109	See `https://github.com/pylint-dev/pylint/blob/main/pylint/checkers/base/basic_checker.py#L303` for further
110	detail."""
111	const_nodes = (	20✔
112	nodes.Module,
113	nodes.GeneratorExp,
114	nodes.Lambda,
115	nodes.FunctionDef,
116	nodes.ClassDef,
117	bases.Generator,
118	UnboundMethod,
119	BoundMethod,
120	)
121	structs = (nodes.Dict, nodes.Tuple, nodes.Set, nodes.List)	20✔
122	except_nodes = (	20✔
123	nodes.Call,
124	nodes.BinOp,
125	nodes.BoolOp,
126	nodes.UnaryOp,
127	nodes.Subscript,
128	)
129	inferred = None	20✔
130	maybe_generator_call = None	20✔
131	emit = isinstance(test_node, (nodes.Const, structs, const_nodes))	20✔
132	if not isinstance(test_node, except_nodes):	20✔
133	inferred = utils.safe_infer(test_node)	20✔
134	# If we can't infer what the value is but the test is just a variable name
135	if isinstance(inferred, util.UninferableBase) and isinstance(test_node, nodes.Name):	20✔
136	emit, maybe_generator_call = InfiniteLoopChecker._name_holds_generator(test_node)	20✔
137
138	# Emit if calling a function that only returns GeneratorExp (always tests True)
139	elif isinstance(test_node, nodes.Call):	20✔
140	maybe_generator_call = test_node	20✔
141
142	if maybe_generator_call:	20✔
143	inferred_call = utils.safe_infer(maybe_generator_call.func)	20✔
144	if isinstance(inferred_call, nodes.FunctionDef):	20✔
145	# Can't use all(x) or not any(not x) for this condition, because it
146	# will return True for empty generators, which is not what we want.
UNCOV 147	all_returns_were_generator = None	×
UNCOV 148	for return_node in inferred_call._get_return_nodes_skip_functions():	×
UNCOV 149	if not isinstance(return_node.value, nodes.GeneratorExp):	×
UNCOV 150	all_returns_were_generator = False	×
UNCOV 151	break	×
UNCOV 152	all_returns_were_generator = True	×
153	if all_returns_were_generator:	×
154	return True	×
155	if emit:	20✔
156	return True	20✔
157	elif isinstance(inferred, const_nodes):	20✔
158	return True	20✔
159	return False	20✔
160
161	@staticmethod	20✔
162	def _name_holds_generator(test_node: nodes.Name) -> tuple[bool, Optional[nodes.Call]]:	20✔
163	"""Return whether `test` tests a name certain to hold a generator, or optionally
164	a call that should be then tested to see if it returns only generators.
165
166	See `https://github.com/pylint-dev/pylint/blob/main/pylint/checkers/base/basic_checker.py#L303` for further
167	detail."""
168	assert isinstance(test_node, nodes.Name)	20✔
169	emit = False	20✔
170	maybe_generator_call = None	20✔
171	lookup_result = test_node.frame().lookup(test_node.name)	20✔
172	if not lookup_result:	20✔
UNCOV 173	return emit, maybe_generator_call	×
174	maybe_generator_assigned = (	20✔
175	isinstance(assign_name.parent.value, nodes.GeneratorExp)
176	for assign_name in lookup_result[1]
177	if isinstance(assign_name.parent, nodes.Assign)
178	)
179	first_item = next(maybe_generator_assigned, None)	20✔
180	if first_item is not None:	20✔
181	# Emit if this variable is certain to hold a generator
UNCOV 182	if all(itertools.chain((first_item,), maybe_generator_assigned)):	×
UNCOV 183	emit = True	×
184	# If this variable holds the result of a call, save it for next test
UNCOV 185	elif (	×
186	len(lookup_result[1]) == 1
187	and isinstance(lookup_result[1][0].parent, nodes.Assign)
188	and isinstance(lookup_result[1][0].parent.value, nodes.Call)
189	):
UNCOV 190	maybe_generator_call = lookup_result[1][0].parent.value	×
191	return emit, maybe_generator_call	20✔
192
193	def _check_immutable_cond_var_reassigned(self, node: nodes.While) -> bool:	20✔
194	"""Helper function that checks if a while-loop condition uses only immutable variables
195	and none of them are reassigned inside the loop body.
196
197	Flags loops that meet both of the following criteria:
198	- All variables in the `while` condition are immutable (int, float, complex, bool,
199	str, bytes, tuple, or NoneType)
200	- None of these variables are reassigned in the loop body"""
201	immutable_types = (	20✔
202	int,
203	float,
204	bool,
205	complex,
206	str,
207	bytes,
208	tuple,
209	type(None),
210	)
211	immutable_vars = set()	20✔
212	for child in node.test.nodes_of_class(nodes.Name):	20✔
213	if not isinstance(child.parent, nodes.Call) or child.parent.func is not child:	20✔
214	inferred = utils.safe_infer(child)	20✔
215	if isinstance(inferred, util.UninferableBase) or inferred is None:	20✔
216	continue	20✔
217	# Check if type of inferred value is immutable
218	if (	20✔
219	isinstance(inferred, nodes.Const) and type(inferred.value) in immutable_types
220	) or isinstance(inferred, nodes.Tuple):
221	immutable_vars.add(child.name)	20✔
222	else:
223	return False	20✔
224	if not immutable_vars:	20✔
225	# There are no vars with immutables values
226	return False	20✔
227
228	# Infer the loop condition
229	inferred_test = utils.safe_infer(node.test)	20✔
230	if isinstance(inferred_test, util.UninferableBase) or inferred_test is None:	20✔
231	return False	20✔
232	if isinstance(inferred_test, nodes.Const) and inferred_test.value is False:	20✔
233	# Condition is always false, loop won't run. No need to check for infinite loop.
234	return False	20✔
235
236	for child in node.body:	20✔
237	for assign_node in child.nodes_of_class(nodes.AssignName):	20✔
238	if assign_node.name in immutable_vars:	20✔
239	return False	20✔
240	else:
241	self.add_message(	20✔
242	"infinite-loop",
243	node=node.test,
244	confidence=INFERENCE,
245	)
246	return True	20✔
247
248
249	def register(linter: PyLinter) -> None:	20✔
250	linter.register_checker(InfiniteLoopChecker(linter))	20✔

pyta-uoft / pyta / 17566741199

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