17896878507

Committed 21 Sep 2025 05:38PM UTC coverage: 94.933% (+1.2%) from 93.738%

Build # 17896878507

Build Type

Pull #1231

github

Committed by

web-flow

Commit Message

Merge 33bce911a into 2237d93b1

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

Run Details

51 of 53 new or added lines in 1 file covered. (96.23%)

7 existing lines in 1 file now uncovered.

3616 of 3809 relevant lines covered (94.93%)

18.04 hits per line

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

90.23

/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

IMMUTABLE_TYPES = (
    int,
    float,
    bool,
    complex,
    str,
    bytes,
    tuple,
    type(None),
)


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
        inferred_test = infer_condition(node)
        if not inferred_test:
            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, confidence=INFERENCE)
            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 = get_safely_inferred(node.test)
        if 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 = get_safely_inferred(exit_node.func.expr)
                    if (
                        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_vars = set()
        for child in node.test.nodes_of_class(nodes.Name):
            if isinstance(child.parent, nodes.Call) and child.parent.func is child:
                continue
            try:
                inferred_values = list(child.infer())
            except InferenceError:
                return False
            for inferred in inferred_values:
                if not _is_immutable_node(inferred):
                    # Return False when the node may evaluate to a mutable object
                    return False
            immutable_vars.add(child.name)
        if not immutable_vars:
            return False

        inferred_test = infer_condition(node)
        if not inferred_test:
            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 _is_immutable_node(node: nodes.NodeNG) -> bool:
    """Helper used to check whether node represents an immutable type."""
    return (isinstance(node, nodes.Const) and type(node.value) in IMMUTABLE_TYPES) or isinstance(
        node, nodes.Tuple
    )


def get_safely_inferred(node: nodes.NodeNG) -> Optional[nodes.NodeNG]:
    """Helper used to safely infer a node with `astroid.safe_infer`. Return None if inference failed."""
    inferred = utils.safe_infer(node)
    if isinstance(inferred, util.UninferableBase) or inferred is None:
        return None
    else:
        return inferred


def infer_condition(node: nodes.While) -> bool:
    """Helper used to safely infer the value of a loop condition. Return False if inference failed or condition
    evaluated to be false."""
    inferred_test = get_safely_inferred(node.test)
    if inferred_test is None:
        return False
    return not (isinstance(inferred_test, nodes.Const) and inferred_test.value is False)


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

pyta-uoft / pyta / 17896878507

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