lower: O(n²) scope resolution — per-reference linear scope lookup stalls check-lower on large single-scope modules/bundles

[proggeramlug]

Summary

Expression/call lowering does a linear scope lookup per identifier reference, so a scope containing N bindings with N references lowers in O(n²) time. Real minified/bundled JS puts tens of thousands of bindings and references in a single module (or single wrapper function) scope, so the check-lower stage stalls for many minutes and never finishes on large bundles.

This is a different root cause from the nested-literal recursion already fixed (#5258) and the deep-chain stack guard (#5259) — those were depth-bounded; this one is breadth (scope size) and shows up only at large N.

Minimal repro

// gen.js
const n = 20000;
let s = "function g(a){return a}\nfunction big(){\n";
for (let i = 0; i < n; i++) s += `var v${i}=${i};`;   // N bindings in one scope
for (let i = 0; i < n; i++) s += `g(v${i});`;          // N references / calls in that scope
s += "return 0}\n";
require("fs").writeFileSync("scope.ts", s);

$ perry check scope.ts     # parse instant; all time in check-lower

Measured scaling (≈ O(n²))

N (bindings + refs in one scope)	perry check wall
2500	0.12 s
5000	0.30 s
10000	1.08 s
20000	3.44 s

8× the size → ~29× the time. Extrapolated to a 13 MB minified bundle (hundreds of thousands of references in one module scope), check-lower runs >600 s and gets killed with no diagnostic. A plain "many statements in one function/block/top-level" program shows the same super-linear curve, since it's the same single-scope effect.

Profile (symbol-preserving release build, sampled mid-check-lower)

The stuck stack is a recursive expression/call-lowering cycle; the hot frames are:

perry_hir::lower::lower_expr::lower_expr_impl
perry_hir::lower::expr_call::lower_call_inner
perry_hir::lower::expr_call::static_and_instance::try_static_method_and_instance
perry_hir::lower::expr_member::lower_member_inner
lookup_local                       <-- per-reference scope scan
active_with_envs_for_ident         <-- per-reference env-chain scan

lookup_local / active_with_envs_for_ident being hot under lower_call_inner / try_static_method_and_instance is the tell: each reference resolves by scanning the scope/env, and that scan grows with the number of bindings already in scope → O(n²) overall.

Suggested direction

• Make local/scope resolution O(1) — index bindings in a per-scope hash map (name → id) instead of a linear scan, and avoid re-walking the env chain per reference.
• If try_static_method_and_instance re-derives per-call info that depends only on the callee identifier, consider memoizing it per binding.

Target: linear-time lowering of a large single scope, so big bundles clear check-lower.

Environment

• perry 0.5.1175, built from main @ c82b6eced (with lower: nested object literals lower in O(n²) time — large/minified bundles stall in check-lower #5258 and lower: deeply-nested expressions (a+b+c+…, o.a.a.…) overflow the stack → fatal abort instead of a diagnostic #5259 already in)