https://github.com/python/cpython/commit/bb9d26d8f4253e952a7ff1fbd926928189a2d61b commit: bb9d26d8f4253e952a7ff1fbd926928189a2d61b branch: main author: Timofei Ivankov <[email protected]> committer: asvetlov <[email protected]> date: 2026-11-02T13:39:49+01:00 summary:
gh-159168: Fix RecursionError in asyncio pstree on a deep chain of tasks (#159170) * gh-159168: Fix RecursionError in asyncio pstree on a deep chain of tasks * Apply suggestions from code review --------- Co-authored-by: Andrew Svetlov <[email protected]> files: A Misc/NEWS.d/next/Library/2026-10-11-13-40-44.gh-issue-159168.z3KjB8.rst M Lib/asyncio/tools.py M Lib/test/test_asyncio/test_tools.py diff --git a/Lib/asyncio/tools.py b/Lib/asyncio/tools.py index fd494912549bf8c..6bc53f4d7d3e5ff 100644 --- a/Lib/asyncio/tools.py +++ b/Lib/asyncio/tools.py @@ -128,14 +128,22 @@ def _find_cycles(graph): def dfs(v): color[v] = GREY path.append(v) - for w in graph.get(v, ()): - if color[w] == WHITE: - dfs(w) - elif color[w] == GREY: # back-edge → cycle! - i = path.index(w) - cycles.append(path[i:] + [w]) # make a copy - color[v] = BLACK - path.pop() + stack = [(v, iter(graph.get(v, ())))] + while stack: + node, children = stack[-1] + for w in children: + if color[w] == WHITE: + color[w] = GREY + path.append(w) + stack.append((w, iter(graph.get(w, ())))) + break + elif color[w] == GREY: # back-edge → cycle! + i = path.index(w) + cycles.append(path[i:] + [w]) # make a copy + else: + color[node] = BLACK + path.pop() + stack.pop() for v in list(graph): if color[v] == WHITE: @@ -167,14 +175,16 @@ def pretty(node): flag = task_emoji if node[0] == NodeType.TASK else cor_emoji return f"{flag} {labels[node]}" - def render(node, prefix="", last=True, buf=None): - if buf is None: - buf = [] - buf.append(f"{prefix}{'└── ' if last else '├── '}{pretty(node)}") - new_pref = prefix + (" " if last else "│ ") - kids = children.get(node, []) - for i, kid in enumerate(kids): - render(kid, new_pref, i == len(kids) - 1, buf) + def render(root): + buf = [] + stack = [(root, "", True)] + while stack: + node, prefix, last = stack.pop() + buf.append(f"{prefix}{'└── ' if last else '├── '}{pretty(node)}") + new_pref = prefix + (" " if last else "│ ") + kids = children.get(node, []) + for i in range(len(kids) - 1, -1, -1): + stack.append((kids[i], new_pref, i == len(kids) - 1)) return buf return [render(root) for root in _roots(labels, children)] diff --git a/Lib/test/test_asyncio/test_tools.py b/Lib/test/test_asyncio/test_tools.py index 2b8e4940333196b..164b735353de2e9 100644 --- a/Lib/test/test_asyncio/test_tools.py +++ b/Lib/test/test_asyncio/test_tools.py @@ -1,3 +1,4 @@ +import sys import unittest from asyncio import tools @@ -1465,6 +1466,77 @@ def test_deep_coroutine_chain(self): result = tools.build_async_tree(input_) self.assertEqual(result, expected) + def test_deep_task_chain(self): + # gh-159168 + n = sys.getrecursionlimit() + input_ = [ + AwaitedInfo( + thread_id=1, + awaited_by=[ + TaskInfo( + task_id=i, + task_name=f"Task-{i}", + coroutine_stack=[], + awaited_by=[ + CoroInfo( + call_stack=[FrameInfo("f", "", LocationInfo(0))], + task_name=i - 1 + ) + ] if i > 1 else [] + ) + for i in range(1, n + 1) + ] + ) + ] + tree = tools.build_async_tree(input_) + self.assertEqual(len(tree[0]), 2 * n - 1) + self.assertEqual(tree[0][-1], " " * 8 * (n - 1) + f"└── (T) Task-{n}") + + def test_cycle_below_task(self): + # gh-159168 + input_ = [ + AwaitedInfo( + thread_id=1, + awaited_by=[ + TaskInfo( + task_id=1, + task_name="Task-1", + coroutine_stack=[], + awaited_by=[] + ), + TaskInfo( + task_id=2, + task_name="Task-2", + coroutine_stack=[], + awaited_by=[ + CoroInfo( + call_stack=[FrameInfo("f", "", LocationInfo(0))], + task_name=1 + ), + CoroInfo( + call_stack=[FrameInfo("f", "", LocationInfo(0))], + task_name=3 + ) + ] + ), + TaskInfo( + task_id=3, + task_name="Task-3", + coroutine_stack=[], + awaited_by=[ + CoroInfo( + call_stack=[FrameInfo("f", "", LocationInfo(0))], + task_name=2 + ) + ] + ) + ] + ) + ] + with self.assertRaises(tools.CycleFoundException) as ctx: + tools.build_async_tree(input_) + self.assertEqual(ctx.exception.cycles, [[2, 3, 2]]) + def test_multiple_cycles_same_node(self): input_ = [ AwaitedInfo( diff --git a/Misc/NEWS.d/next/Library/2026-10-11-13-40-44.gh-issue-159168.z3KjB8.rst b/Misc/NEWS.d/next/Library/2026-10-11-13-40-44.gh-issue-159168.z3KjB8.rst new file mode 100644 index 000000000000000..54b8738e06c270a --- /dev/null +++ b/Misc/NEWS.d/next/Library/2026-10-11-13-40-44.gh-issue-159168.z3KjB8.rst @@ -0,0 +1,2 @@ +Fix :exc:`RecursionError` in ``python -m asyncio pstree`` on a deep chain of +awaiting tasks. Patch by Timofei Ivankov. _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
