codeobject: == on code objects takes exponential time in scope nesting depth (30 nested classes still running after 120 s) #160788

Comparing two equal code objects with == takes time that doubles with each level of nested class or def scope, so a 30-deep nest is still running after 2 minutes.

import ast
depth = 30
source = ''.join(' ' * d + 'class C%d:\n' % d for d in range(depth)) + ' ' * depth + 'pass\n'
tree = ast.parse(source)
a = compile(tree, 'f.py', 'exec'); b = compile(tree, 'f.py', 'exec')
print(a == b)

Saved as input.py and run with python input.py, it printed nothing within 120 s and was killed by timeout (exit 124). With smaller depth, a == b on a release build took about 0.3 s at depth 16, 3.6 s at 20 and 14 s at 22 (the host was heavily loaded, so only the factor of about 2 per level matters).

It should print True promptly, since the two code objects come from the same tree and are equal, with time roughly linear in the nesting depth.

Found at commit 3646ea5; it still reproduces at 3acc941 (latest upstream, release build: killed at the timeout). Both the checking build (ASan/UBSan) and the release build hang the same way, with no assertion or sanitizer report. Nested defs and annotated class bodies show the same growth.

Looks like code_richcompare in Objects/codeobject.c compares _PyCode_ConstantKey(co_consts). For a tuple the key is the pair (tuple_of_item_keys, original_tuple), so comparing two keys recurses into each nested code object twice (once through the item keys, once through the original tuple), which doubles the work per level.

Related: #101346 ("The hash and equals methods of code objects are large, complex and unnecessary").

The deep nesting comes from a generated test, not from a real program.

Found with an LLM-based testing tool; I used Claude to reduce it and look for the cause.

Linked PRs

• gh-160788: Fix exponential time in code object comparison #160849