perf(python): usage extraction climbs every ancestor per identifier, cubic in expression depth

[Fieldnote-Echo]

Version

built from source, main @ 2278498 (v0.11.0-186)

Platform

Linux (x64)

Install channel

Built from source

Binary variant

standard

What happened, and what did you expect?

For nearly every Python identifier, handle_usages (internal/cbm/extract_usages.c:2712) and record_lexical_binding (:2239) ask lexical_ancestor_kind (:1883) for a global/nonlocal ancestor, and usage_lexical_scope_id_for_node (:1808) asks python_default_value_reference (:1782) whether the name sits in a parameter default. Each check climbs toward the root with ts_node_parent, which itself descends from the root on every step, so an expression N terms deep costs O(N³). One long arithmetic expression is enough to stall indexing: sympy 1.14's polys/numberfields/resolvent_lookup.py (40 KB) spends about 8.7 s in the definitions pass.

On error-free trees the fix climbs the walk's occurrence cursor instead (O(1) per hop, as #2352 did for ReScript). For global/nonlocal it takes one parent step, since the grammar makes those names direct children of the statement. Trees with errors keep today's climb, and the graph is byte-identical on 8 corpora.

Reproduction

Smallest repro: a one-file repo with x = 1, c0 = 0 … c49 = 49, then r = c0*x + c1*x + … with N terms (term i is c{i % 50}*x).

Linux x86_64, 32 logical CPUs, GCC 16	main	fixed
Definitions pass, generated file, N = 1000 / 2000	16.8 s / unfinished at 90 s	40 / 150 ms
Definitions pass, sympy resolvent_lookup.py alone	8.7-8.8 s	53-54 ms
parallel_extract median, 823 / 2063 ordinary .py files	1.54 / 4.75 s	1.15 / 3.58 s

Logs

Diagnostics trajectory (memory / performance / leak issues)

Not a memory problem: CPU time in the definitions pass of one index run.

Project scale (if relevant)

No response

Confirmations

• I searched existing issues and this is not a duplicate.
• My reproduction uses shareable code (a dummy snippet or a public OSS repository), not proprietary code.