lower: nested object literals lower in O(n²) time — large/minified bundles stall in check-lower

[proggeramlug]

Summary

Lowering a nested object literal is O(n²) in nesting depth. Past a few thousand levels of nesting, perry check/perry compile spend minutes in the check-lower stage and effectively never finish on real inputs. This is the dominant wall when compiling large minified/bundled JS, which is wall-to-wall deeply-nested object literals.

Minimal repro

// gen.js — write an N-deep nested object literal
const n = 8000;
require("fs").writeFileSync("obj.ts", "var x=" + "{a:".repeat(n) + "0" + "}".repeat(n) + ";\n");
// => var x={a:{a:{a:…0…}}};

$ perry check obj.ts        # parse is instant; all the time is in check-lower

Measured scaling (≈ quadratic, ~4× per 2× depth)

nesting depth	perry check wall time
1000	0.30 s
2000	1.12 s
3000	2.48 s
4000	4.41 s
6000	11.8 s
8000	23.8 s

Doubling depth ~quadruples the time → O(n²). A real 13 MB minified bundle never clears check-lower (killed at >300 s with no error and no output).

Nested arrow functions (()=>()=>…0) show the same super-linear shape, milder (1k→0.1 s, 6k→1.4 s) — likely the same underlying cause, so worth checking together.

Localization

-vv shows stage=check-parse completing immediately, then stage=check-lower running unbounded:

[progress] stage=check-parse module=obj.ts visited=1/1
[progress] stage=check-lower module=obj.ts visited=1/1     # <- all time spent here

A sampling profile of the stuck process is a single deep recursive cycle of three mutually-recursive functions (object-literal/expr lowering descending one nesting level per cycle), 100% of samples — consistent with per-level work that is itself linear in the remaining subtree (the classic O(n²) recursive-descent shape: copying/re-walking the tail at each level rather than once).

Suggested direction

Audit the object-literal (and expression) lowering path for per-node work that scales with the remaining subtree size — e.g. cloning/re-traversing/re-collecting the nested value at each level instead of lowering each node exactly once. Goal: linear-time lowering of nested literals.

Environment

• perry 0.5.1175, built from main @ 690e4e5ea