perf(jq): transitively included modules compound in memory when a module's defs each call more than one def below

[newhoggy]

Severity: Low

Summary

Found by code review on PR #2954 (#2865). #2865 makes a module's own includes
load transitively by wrapping each exported def's body in the defs it reaches.
Because that wrap copies the AST, a chain of modules compounds: each level's
bodies already carry the level below.

#2865 mitigates this with jq's own block_bind_referenced rule (wrap only what
the body transitively calls), which flattens the common shape completely. It does
not cure the general case: as soon as each def calls more than one def from
the level below, the referenced closure is itself exponential in chain depth.

Output is correct throughout — this is a memory/time scalability gap, not a
wrong answer, and not a regression (before #2865 these programs did not compile
at all).

Repro

Synthetic chains of modules, each def calling F defs from the level below,
resolving one def at the top. Apple M-series, release build, measured with
/usr/bin/time -l at PR #2954's head:

chain	fan-out	levels x defs	succinctly peak RSS	jq peak RSS
flat	1	6 x 40	10 MB	2.5 MB
wide	3	8 x 6	91 MB	2.6 MB
wide	2	14 x 4	361 MB	2.6 MB

Generator:

def gen(L, D, F, d):
    with open(f"{d}/m0.jq", "w") as f:
        for i in range(D):
            f.write(f"def f0_{i}: {i};\n")
    for lvl in range(1, L):
        with open(f"{d}/m{lvl}.jq", "w") as f:
            f.write(f"include \"m{lvl-1}\";\n")
            for i in range(D):
                calls = " + ".join(f"f{lvl-1}_{(i+k)%D}" for k in range(F))
                f.write(f"def f{lvl}_{i}: {calls};\n")

Then succinctly jq -L <dir> -nc 'include "m13"; f13_0'.

Root cause

ModuleLoader::load_and_bind_module / visible_defs_for
(src/bin/succinctly/jq_runner.rs): binding is done by cloning each
reachable def's Expr into the wrapping body. Real jq binds symbolically — its
block values are shared, so a def reachable by many paths exists once.
succinctly's module support is AST inlining, where "reachable by K paths" means
K copies.

Suggested fix direction

Three shapes, roughly in increasing order of cost:

1. Share the bound bodies. Expr already has an Rc-shaded variant for
   exactly this purpose (the opaque already-substituted sub-expression jq: self-recursive user-defined functions can't work at any real depth under static AST substitution #1371
   introduced to stop recursive calls growing with depth). If a bound def body
   could be spliced by handle rather than by clone, the copies collapse to
   pointers. Needs a check that every later pass over the tree treats it
   correctly.
2. Bind a module once into a single shared scope rather than per exported
   def — closer to jq's own block model, but it is the per-body wrapping that
   buys jq: a module's own include directive is silently ignored (transitive include not processed) #2865 its scoping rows (a dependency visible inside the module, not
   re-exported, outranking a same-name sibling), so this needs the scope
   boundary from jq: a module body sees names it should not — ~/.jq's defs, and sibling included modules' defs in declaration order #2951 to exist first.
3. A depth/size guard that refuses with a clear error rather than
   exhausting memory, in the spirit of the other resource caps in
   docs/compliance/jq/limitations.md. A stopgap, not a fix.

Option 1 is the one worth costing first; #2951's sealed-scope work would
subsume option 2.

Why this is separate from #2865, #2951

#2865 is the functional gap (transitive includes not processed at all) and
ships the mitigation that handles the common shape; this is the residual
scalability limit of the mechanism it uses. #2951 is a scoping-correctness gap
whose fix would likely also change this mechanism, but it is not itself about
memory.

[newhoggy]

Triage plan (2026-09-17)

Premise check (main @ b509a8019, release build, Apple M-series)

Same generator as the issue body; succinctly jq -L <dir> -nc 'include "m<L-1>"; f<L-1>_0', /usr/bin/time -l:

chain (levels x defs, fan-out)	succinctly peak RSS	wall	jq 1.7.1 peak RSS	output
6 x 40, 1	12.5 MB	0.01s	2.3 MB	same
8 x 40, 1	14.1 MB	0.02s	—	—
8 x 6, 3	143.2 MB	0.16s	2.5 MB	same
10 x 4, 2	44.8 MB	0.05s	2.5 MB	same
12 x 4, 2	166.8 MB	0.18s	2.5 MB	same
14 x 4, 2	699.0 MB	1.07s	2.5 MB	same

The premise holds, and the problem has grown since filing. The 14 x 4 x 2 row is 699 MB now against the 361 MB measured at #2954's head (ADR-0023's barrier markers add two defs per dependency group, and every one of them is copied too). Growth is ~2x per level at fan-out 2, as F^L predicts. The flat shape is still flat. Every answer is correct.

Root cause (confirmed by reading, current names)

ModuleLoader::load_and_bind_module (src/bin/succinctly/jq_runner.rs): for each of a module's own defs, visible_deps_for picks the dependency defs the body transitively reaches, and wrap_barrier_run → wrap_defs nests owned copies of them around the body. load_module returns ensure_module_loaded(..).cloned(), and those dependency bodies already carry their dependencies. So a def reachable by K paths exists K times. After that, process_program, substitute_vars and resolve_all each walk (and rewrite_namespaced_calls / substitute_vars rebuild) the whole expanded tree. The exponential shows up in time as well as memory.

(visible_defs_for in the issue body is now visible_deps_for, and dependency groups are now bracketed in barrier runs per ADR-0023 decision 4.)

Why the issue's option 1 (Rc/Expr::Shared splicing) does not work as stated

Three things in the tree today assume one scope per node, and a shared dependency body breaks all of them:

1. Free names in a spliced dependency body resolve against the scope it is spliced into. A barrier does not floor visibility (ADR-0023 decision 4), so the same Rc body resolves differently at different sites. That is exactly jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962's capture family. So sharing is only sound for a scope-closed body, and nothing produces one today.
2. resolve::check reaches Expr::Shared through Rc::make_mut. It deliberately clones a multi-owner Rc and re-keys jq: an undefined name inside a never-called def is rejected at compile time; jq accepts the program #2740's reachability set (keyed by body heap address) onto the copy (jq: a def inside a builtin argument is never compile-checked (reachability keyed on an address check clones away) #2971). A shared body gets un-shared again at compile time, so the memory comes back.
3. The evaluator's bind caches live on the node. FuncDefBound (jq: def declared inside a loop body re-substitutes on every iteration (no BoundBody-style cache for FuncDef) #2094) is keyed by ambient depth only, and BoundBody is write-once. A FuncDef node reached from two scopes would serve one scope's installed tree to the other.

Expr::Shared is also opaque to substitute_vars and hygiene by design (#1371/#2077), which is wrong for a dependency body that must still see named --arg variables. Option 3 (a size cap) is a stopgap, and option 2 as written waits on a boundary that ADR-0023 has since delivered.

Proposed fix: link each module once, and forward to it (hoisted sealed runs + forwarding stubs)

This is the "symbolic binding at load time" that ADR-0023 lists as the eventual answer to #2955. It can be expressed inside the existing def chain, with the evaluator untouched.

1. Hoisted link runs. Every module loaded as another module's dependency is emitted once into the top-level chain as a new kind of run, bracketed \0run:link:<id> … \0run:end:<id> with its existing run id. Inside the run go the module's own defs under their original names (so sibling calls resolve exactly as written), followed by one alias per def: def \0link:<id>:<name>(p1; …): <name>(p1; …);. The hidden, unlexable alias is the run's only public surface. Link runs are wrapped outermost in process_program (outside imports, ~/.jq and includes), in dependency post-order: a module's dependencies sit outside it, and a diamond dependency is emitted once. The loader already recurses depth-first, so recording completion order is enough. (Renaming the defs themselves instead would strand their sibling calls.)

2. Forwarding stubs replace the per-body copies. In load_and_bind_module, each def's body is wrapped in one stub per dependency (name, arity) the body calls directly: def g(a; b): \0link:<id>:g(a; b);. Arguments are forwarded as closures; the target does any $param expansion, so generator arguments keep jq's cartesian semantics. The existing direct-only exclusions (self name/arity, and a parameter's name at arity 0) are kept verbatim. The transitive closure in visible_deps_for is deleted: indirect needs are resolved inside the dependency's own sealed hoisted run, which is jq's model. Stubs contain no lexable free name, so they need no barrier and cannot be captured. Groups keep declaration order, so the last-declared dependency is still innermost.

3. Resolver: one new marker kind, two rules, both in scan_scope (src/jq/resolve.rs). Add RunMarker::Link { id } to ModuleRun's spelling (shared by loader and resolver, as today).

   • Inside an open link run, it floors exactly like Begin: a hoisted body sees its own module's defs and nothing below.
   • From outside, a closed link run shows only its \0link: aliases. Its bare-named defs are skipped. Without this rule, include "mid"; g would find inner's bare g through the closed run, which is the non-re-export leak ADR-0023 cited against name mangling.
   • A lookup for a \0link: name ignores floors. Nothing lexable can spell one, so only a stub or alias ever makes that lookup.

   Both walks (reach_in_scope for jq: an undefined name inside a never-called def is rejected at compile time; jq accepts the program #2740 reachability and check) already go through scan_scope, so they agree by construction.

   Evaluator soundness (the ADR-0023 decision 5 argument, re-derived). The evaluator only ever looks up names the resolver accepted. A \0link: name exists exactly once in the chain. A bare name resolved from main-filter, ~/.jq or include/import code hits a def inner to every link run, because link runs are outermost, so the evaluator's innermost-first scan hits that same def before any skipped one. A bare name resolved inside link run B hits one of B's own defs, which sit inside B's floor, so again nothing skipped is nearer. There is no input on which the two pick different defs.

4. Diagnostics never show a hidden name. Real recursion happens in the bare-named def, so the common message is already right. But the depth guard formats whichever def's frame trips it ("{}/{} exceeded maximum recursion depth", eval.rs, and its eval_generic.rs twin), and that can be an alias or a stub. Map \0link:<id>:name back to name in both evaluators, and pin it with a test. Compile-error attribution already rides the run id (ADR-0023 decision 6), and a hoisted run uses the module's own id, so a module-body error still names its own file with line and echo (jq: a module-body compile error names its file but not jq's line number or source echo (#2951 residual) #2991).

5. Retire the barrier if nothing else uses it once dependency bodies are no longer spliced into consumers (RunMarker::Barrier, wrap_barrier_run). Verify before deleting; there are 7 references today.

6. Top-level include/import runs stay as they are: full bodies, wrapped in stubs. That costs one extra copy per directly included module, which is linear. Turning them into stubs too is possible, but it would also retire jq: a def in an imported module cannot call its own sibling by bare name #2989's alias retry and belongs in a separate change.

Size after: Σ(module sizes) for hoisted runs, plus the directly included modules again, plus Σ(direct dependency calls) stubs. That is linear in total source, with no chain-depth or fan-out term.

What else this closes (verified live, jq 1.7.1 vs current succinctly)

fixtures	filter	jq	succinctly now	after
#2962 row 1 (inner/mid)	include "mid"; 0 | c	7	g/0 exceeded maximum recursion depth, exit 5	7
#2962 row 2 (gb/hb)	include "hb"; q	b/0 is not defined at …/gb.jq, exit 3	99, exit 0	jq's error (sealed hoisted gb)
#2962 row 3 (inner3/h3)	include "h3"; q	[7,[42]]	[7,[7]]	[7,[42]]
new: inner3 = def g: 42; def k: [g];, impk = import "inner3" as i; def h: i::k;	include "impk"; h	[42]	g/0 is not defined at …/inner3.jq, exit 3	[42]

The last row has not been filed. It is #2989's residual one level down: the closure in visible_deps_for matches k's bare g against the namespaced dependency i::g, finds nothing, drops g, and the barrier stops the alias retry. The top-level form import "inner3" as i; [i::g, i::k] already works. The hoisted run keeps bare names, so it goes away.

So #2962 should be closed by the same PR (all three rows reach jq's answer rather than trading a wrong value for a compile error, which was ADR-0023's reason for deferring the seal).

Rows that must not change (all currently pass): useunref (an unreferenced dependency calling an undefined function is not an error: 1), a diamond (include "diaA"; include "diaB"; [a, b] → [43,44]), dependency beats its own sibling (include "sib"; [h, g] → [42,7]), and non-re-export (include "sib"; k → k/0 is not defined at <top-level>, exit 3). Also the whole #2865/#2951/#2989/#2774 ($__loc__)/#2857/#2991 CLI test families.

Tests

• Flip test_dependency_capture_by_the_including_defs_scope_2962 (tests/jq_cli_tests.rs) to jq's answers, as its own doc comment anticipates.
• New CLI rows: the nested-import sibling row above; diamond; a dependency pulled in through two different including modules; import … as inside a module; a stub for a dependency with $param and closure params (generator arguments: g(1,2) cartesian); path(dep(...)) through a stub; a recursion-depth error raised inside a hoisted def printing the bare name.
• Size regression guard that cannot pass by accident: a loader-level unit test that counts Expr nodes in process_program's output for the fan-out-2 chain at L = 6, 8, 10 and asserts linear growth (a constant per-level delta). Run it once against the pre-fix loader to confirm it fails there. Do not use a wall-clock or RSS test.
• Pattern computed keys (. as {(g): $v}) and shadow-fallback calls (def limit: …) inside a module body must still produce stubs. called_func_names already handles both; keep using it for the direct set.

Docs

• ADR: amend ADR-0023 (decision 4's barrier is superseded; its "symbolic binding" alternative is taken; its "name mangling rejected" entry needs a note on why this differs: nothing exported is renamed and no call site is rewritten, the hidden name is an additional alias) — or a new ADR if the reviewer prefers. ADR-0024 is already claimed by design-2999-adr-0024, so number at land time and run update-adr-inventory.
• docs/compliance/jq/limitations.md: delete "Deeply chained modules compound in memory (perf(jq): transitively included modules compound in memory when a module's defs each call more than one def below #2955)" and "A wrapped dependency sits inside the including def's scope (jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962)". Update the visible_deps_for paragraph above them.
• Rewrite the doc comments on load_and_bind_module and visible_deps_for (or delete the latter's transitive section), plus the RunMarker::Barrier doc if kept.

Risks and what to measure

• Non-re-export must not regress. Pin include "mid"; g and include "h3"; k (names that exist only in a hoisted run) as compile errors at <top-level>, exit 3 (both confirmed live against jq 1.7.1, and both pass today). Also pin a bare call inside one link run to a name defined only in another link run as a compile error attributed to the calling module's file.
• Frame charge / recursion ceiling. A cross-module call now takes two forwarding hops (stub → alias → def). A rough proxy (a hand-written sibling forwarding def, not the real hoisted shape) did not lower the ceiling: rec(n) through a direct dependency call fails at n = 6,700 today, while the forwarded variant still succeeds at 10,000. The frame model depends on install structure rather than hop count, so measure the real shape before/after. If the ceiling drops, collapse a pure forwarding def (body is exactly a call to one name with its own params in order) at install_def_calls time, in both evaluators. Note that recursion through a dependency call is already slow at depth (7-22 s at n = 7,000-10,000); that is pre-existing and not in scope.
• Hot-path cost of the extra hop. Interleaved A/B (never-triggering holdout build per docs/guides/benchmarking.md) on a module-heavy loop, e.g. include "m"; [range(1e6) | f] where f calls a dependency, on both M4 Pro and 7950X. No-module programs (all of jq_bench) must be byte-identical and neutral: process_program does nothing new when no module has dependencies.
• Startup install cost of hoisted chains. Each FuncDef evaluation installs over its then. Time a wide library, e.g. 20 modules x 50 defs, before/after.
• Hidden-name leakage. git grep every formatter of a def name (errors, Debug in snapshot tests, unqualified_def_names) and assert no \0link: escapes. unqualified_def_names must never return one, or yq: jq: a def loaded via include/import/~/.jq cannot shadow a builtin (#2036 follow-up) #2395's shadow seeding would see it.

Dependencies

• None blocking. ADR-0023 (jq: a module body sees names it should not — ~/.jq's defs, and sibling included modules' defs in declaration order #2951) has landed and provides the floor.
• Closes jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962 in the same PR. Coordinate so nobody lands the "upgrade the barrier to a Begin" variant ADR-0023 describes; this supersedes it.
• File the nested-import sibling row as its own issue for traceability, or fold it into this PR's test list.
• jq: a module's own source is parsed with no shadow-candidate seeding, so a transitively included def can't shadow a builtin inside that module #2950 (module source parsed without shadow seeding) and jq: data imports (import "f" as $d;) are unimplemented — the $ is dropped at parse time, so they resolve as module imports and fail #2956 (data imports) are independent.

Class: Fable (was Opus)

This replaces the module-linking representation ADR-0023 chose, and supersedes that accepted ADR's decision 4 and its deferred alternative. It adds a resolver run kind with a new visibility rule (bare names hidden from outside, hidden names crossing floors), whose soundness has to be re-argued against the evaluator's dynamic lookup. The first sketch of this plan leaked non-exported names, which shows how easy that argument is to get wrong. It changes what the frame charge sees on every cross-module call, in both evaluators. And it deliberately closes a second open issue (#2962) plus an unfiled residual of #2989, while preserving the pinned rows of #2865, #2951, #2989, #2774, #2857 and #2991. The per-site edits are modest (loader, one scan_scope rule, two diagnostic formatters), but getting the design right is the work, and the issue body's own suggested fix turned out to be unsound. By the rubric (new representation plus an ADR amendment plus cross-cutting invariants), that is Fable. An Opus implementer working from this plan is plausible, but the soundness arguments in steps 1-3 are the part most likely to be gotten subtly wrong.

[newhoggy]

Plan status update from agent Miles, after PR #3057 (#2962) merged at 95e9e5e26. The PR took a different route from this plan, and three of the plan's premises have changed:

• jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962 is closed, without hoisting. Each dependency group is now wrapped as an ordinary flooring Begin run. A clashing dependency (the def's own name and arity, or a parameter's name) is renamed rather than excluded (ModuleRun::renamed_dep). See ADR-0023's jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962 amendment. So the plan's "Closes jq: a wrapped module dependency sits inside the including def's scope, so that def's own name or parameters can capture names free in it #2962" and "Flip test_dependency_capture_by_the_including_defs_scope_2962" items no longer apply. That test is now test_dependencies_are_bound_in_their_own_scope_2962, with 30 rows byte-exact against jq 1.7.1, and those rows are must-not-change for this plan.
• The barrier is gone (RunMarker::Barrier, barrier_marker, and the barrier arm of scan_scope). Step 5 is done.
• The unfiled nested-import row now matches jq: inner3 = def g: 42; def k: [g];, impk = import "inner3" as i; def h: i::k;, and include "impk"; h gives [42]. visible_deps_for now qualifies a dependency body's bare calls with the group's alias when computing the closure.
• The memory premise is unchanged. Peak RSS for the issue's generator is identical before and after fix(jq): bind a module's dependencies in their own scope (#2962) #3057 (debug builds, /usr/bin/time -l): 8×6×3 at 242.7 MB, 10×4×2 at 79.4 MB, 12×4×2 at 288.7 MB, with the same outputs. Renaming only happens on a clash, so the copy count is unchanged.

load_and_bind_module and visible_deps_for have also changed shape since this plan quoted them: groups are wrapped with wrap_run, the closure is computed from the def's original body, and rename_dep_calls exists. Whoever picks this up should re-read them first. The hoisting plan itself is still valid, and it would now also subsume the rename.

The plan classifies this issue as Fable, while the board still shows it under Opus. I left the board as it is and did not claim the issue.