jq: recurse's f is not suspended between its own outputs, so a node's later f outputs still fire (#2693 residual)

[newhoggy]

Severity: Low (side-effect count and stderr ordering; delivered values are correct)

Summary

#2693 stopped recurse from
evaluating f at a node the consumer was already satisfied by — limit(1; recurse(f)) went
from running f at 10000 nodes to running it at none. What it did not change: at the node
the traversal is at, f runs to completion before any of its outputs is descended into.

jq's def r: ., (f | r); r; interleaves instead: the first output of f has its whole subtree
traversed before f is asked for its second. So jq stops between f's outputs, and
succinctly cannot.

Repro

Confirmed live against jq 1.7.1 and succinctly at 81209f1ab (post-#2693). Values match in
every row; only stderr differs.

Under a bound — one node's fan-out too many (it was the whole remaining tree before #2693):

$ echo '[1,[2,[3]]]' | jq -c '[limit(2; recurse(.[]?|debug))]'
["DEBUG:",1]                                  # succinctly: ["DEBUG:",1] ["DEBUG:",[2,[3]]]

Unbounded, it shows as stderr ordering, because a node's whole fan-out is evaluated before
its first child is descended into:

$ echo '{"a":{"x":1},"b":{"y":2}}' | jq -c '[recurse(.[]?|debug)]'
["DEBUG:",{"x":1}] ["DEBUG:",1] ["DEBUG:",{"y":2}] ["DEBUG:",2]
# succinctly:
["DEBUG:",{"x":1}] ["DEBUG:",{"y":2}] ["DEBUG:",1] ["DEBUG:",2]

And once through ?, an extra f run at the node that errors:

$ echo '{"a":1}' | jq -c '[recurse(.[]?, ("x"|stderr|error("f")))?]'
x                                             # succinctly: xx

Both evaluators are affected identically (each_recurse_walk is shared), and
resolve_recurse_sink has the same residual on the path side —
path(limit(2; recurse((.a|debug), (.b|debug)))) on {"a":1,"b":2} writes one DEBUG line in
jq and two here.

Why it is not a small fix

The traversal is an explicit LIFO stack of materialized nodes, in all three walkers. To stop
between f's outputs the stack would have to hold f's suspended generator at each level,
and f is driven by a push-based sink that cannot be resumed. The natural expression is
recursion inside f's own sink callback — child N's subtree runs before f yields child N+1 —
but that makes native stack depth equal to traversal depth, and RECURSE_MAX_ITEMS allows
10000. This repo has measured numbers for that hazard: MAX_EXPR_DEPTH's note records the
parser — a much smaller frame — aborting at around 96 levels in debug on cargo's 2 MiB test
thread.

So the options are materially different and none is obviously right:

1. Bounded native recursion with a fallback. Recurse in the callback while depth ≤ D, and
   use today's collecting walk past D. Exact for every realistic shape (a fan-out deeper than
   ~13 exceeds RECURSE_MAX_ITEMS anyway), but adds a second traversal shape to each of the
   three walkers — each of which carries jq: recurse/recurse(f) drop a null child and flatten a single array-valued child #490/jq: recurse(f)/recurse(f;cond) use breadth-first queue order, diverging from jq's depth-first definition #635/jq: recurse(f; cond) silently prunes on a cond/f error instead of propagating it like jq does #636/jq: recurse(f) drops f's own partial fan-out when a later f output errors (value + path evaluators) #842/jq: recurse(f; cond) drops cond's already-approved siblings on a later cond error #854's rules — which is the
   "duplicated predicates diverge silently" hazard CLAUDE.md names.
2. A pull-based generator protocol for the evaluator/resolver, so a generator can be
   suspended rather than only stopped. This closes the whole class at once — this issue,
   jq: path()'s own consumer side still collects, so a bound outside path() can't stop the fold (#2694 residual) #2908, and resolve_recurse_sink's own half — but is architecture-level (new ADR,
   invasive).
3. Leave it. The values are right; the cost is a bounded side-effect over-fire and stderr
   ordering.

Filing rather than choosing, since option 2's scope is a different tier from this issue's.

[newhoggy]

Plan (2026-09-16)

Decision: option 1, but built so there is one traversal with two orders, not a second traversal in each walker. Option 2 is not needed for this: nothing here requires resuming a suspended generator, only nesting the child's subtree inside the generator's own callback, and both domains already have the push-based f driver that makes that expressible. Option 3 is rejected because the fix is contained.

Facts the issue did not have

1. Both domains already have a sink form of f. eval_each_owned(f, &node, false, sink) (value domain) and resolve_against_cow_sink(f, node, .., sink) (path domain) both exist and are already what the pipe arm and the fold sources drive. Recursing into the child from inside that callback gives jq's interleaving exactly: child N's whole subtree runs before f is asked for N+1, f is never asked for another output once the consumer stops, and an escape from inside the subtree stops f before it can produce a later sibling. That last point is queue_recurse_children's stack.clear() rule falling out of the shape rather than being enforced.

2. The stack hazard is sized already, and not at 2 MiB. The CLI evaluates on its own thread: EVAL_STACK_SIZE in src/bin/succinctly/main.rs is 256 MB in release and 2 GB in debug, provisioned for MAX_EVAL_FRAMES = 40,000 def levels at a measured ~4.4 KB/level release (spike(jq): measure per-call native stack cost to decide #1371's evaluator architecture — ~4.4 KB/level, linear #2080). The 96-level figure the issue cites is the parser on cargo's 2 MiB harness thread, which is the in-process unit-test case, not the shipped binary. Native recursion bounded by document depth is also already precedent: each_recurse_cursor_generic (.. on a cursor) and path_context_step_recurse both recurse natively under MAX_NESTING_DEPTH (256).

3. The residual is wider than the three rows filed: cond has the same shape. Captured live, jq 1.7.1 vs succinctly (release binary at the jq: the parser panics on a multi-byte character after a field, instead of reporting a compile error #2975 tip's parent; values identical in every row):

   input	filter	jq stderr	succinctly stderr
   {"a":1,"b":2,"c":3}	[limit(2; recurse(.[]?; (true, ("c"|stderr|true))))]	(empty)	ccc
   [0,1]	[limit(3; recurse(.[]?|debug; (.|debug|true)))]	DEBUG 0, 0, 1, 1	DEBUG 0, 1, 0, 1
   0	[limit(3; recurse(.+1, ("s"|stderr|.+100)))]	(empty)	ss
   {"a":1,"b":2}	path(limit(2; recurse((.a|debug), (.b|debug))))	1 DEBUG line	2 DEBUG lines

   jq stops between cond's outputs too (select(cond) | r recurses into the child before cond is asked again), so cond has to move to the sink form as well, not only f. The third row is the chain shape, which is also the deep shape: the fix and the depth budget meet on the same input. [recurse(.[]; (true, error("x")))] already answers Cannot iterate over number (1) in both (the pending_error overwrite rule from jq: recurse(f; cond) drops cond's already-approved siblings on a later cond error #854); the recursive form gets it for free, since cond's error("x") is simply never evaluated.

4. Memory shape changes on one route. Today's explicit stack holds unvisited siblings, O(document). The recursive form keeps each ancestor's suspended f alive down the current path. For an f that eval_owned_fast_path handles that is an iterator; for an f that takes eval_each_owned's reindex route it is the ancestor's serialized JSON plus its JsonIndex, per live level, so worst case O(depth × size) for a deep document whose bulk sits at the leaf. This needs a measurement (step C2), not a guess.

A. Shape

One generic walker, two node adapters, two orders:

fn recurse_walk<N>(
    root: N,
    expand: &dyn Fn(&N, &mut dyn FnMut(N) -> Demand) -> Option<EvalEscape>,
    emit:   &mut dyn FnMut(N) -> Demand,
) -> RecurseWalkEnd

• expand(node, on_child) runs f on one node through the sink form, gates each output through cond (forking once per truthy output, still evaluated when the gate is closed so yq/jq: resolve_recurse's null-child guard discards the null child's own path entirely #856's side effects fire), calls on_child once per approved child in order, and returns f/cond's own escape if it ended in one. It is Fn, not FnMut, so the callback can re-enter it for the child; emit is captured mutably by the callback the same way eval_each_pipe's driver captures its sink.
• Native order (depth below budget): on_child emits the child and recurses. An escape from the subtree is stashed out of band and answered with Demand::Stop (the downstream: Option<Flow> idiom in eval_each_pipe), then reported as Escaped once expand returns.
• Fallback order (depth at budget): today's loop verbatim. on_child pushes into next, queue_recurse_children pushes reversed, the loop pops. Byte-for-byte the current behaviour, residual included, for the levels past the budget only.
• Shared state threaded through both: emitted against RECURSE_MAX_ITEMS (a cap hit stops every ancestor's generator, drained: false, no error raised, unchanged rule), pending_error, and the stop/escape stash.
• Adapters: value domain (N = OwnedValue, f and cond via eval_each_owned::<S>) and path domain (N = PathBranch<'a>, f via resolve_against_cow_sink, cond via eval_each_owned on the branch value, is_null_current gate and frame.extend(&prefix) exactly as today). each_recurse_walk and resolve_recurse_sink become those adapters; builtin_recurse_f/builtin_recurse_cond, each_recurse, each_recurse_generic and recurse_walk_flow do not change. eval_recurse_cond (collecting) goes away.

Where each existing rule ends up, so the review can check them one by one:

rule	lives in
#490 one output, one child; null is a child	expand (both orders)
#635 DFS sibling order	native: recursion order; fallback: reversed push. Pinned by the recurse_f_dfs_sibling_order/recurse_cond_dfs_sibling_order goldens and by the differential test in D
#636 f/cond escape aborts the traversal	native: stash + Stop propagates up every level; fallback: queue_recurse_children
#842/#854 earlier children still get their subtree before the escape surfaces	native: they already ran inside the callback; fallback: next queued before pending_error
#854 cond escape precedes f's at the same node	native: f is stopped, its escape never computed; fallback: overwrite as today
#856 cond evaluated on a null node's children, none queued	expand, gate closed
#1755 root decode must raise	untouched, in the callers
RECURSE_MAX_ITEMS, pending error only if drained	walker state, both orders
Flow::Stopped { pending }	native order can produce no pending (f is stopped before its escape exists), which is what jq does; fallback unchanged

B. Depth budget

Two bounds, both fall back, neither errors (values must survive: [limit(5000; recurse(.+1))] | length is 5000 in jq and in succinctly today):

1. A local depth cap RECURSE_NATIVE_DEPTH, the walker's own recursion depth, sized by measurement (C1). This is the only bound no_std has (its ambient_frame_depth is a constant 0).
2. A charge on the existing frame guard. Each native level calls ambient_frame_depth::enter(current + k) for its scope, k = measured walker-level cost in def-level units, so a def reached inside f sees the stack the walk already consumed, and a walk started deep inside def recursion starts with less headroom. The fallback predicate also reads it: if the next level would put the ambient depth past MAX_EVAL_FRAMES less its margin, use the fallback order. This keeps one ceiling for the whole evaluator rather than a second constant that composes with the first only by luck (enter_def_call_frame is the precedent).

Realistic reach: JSON nesting is capped at MAX_NESTING_DEPTH (256) and YAML at its own limit, so every document-navigation f is exact if the cap lands at or above that; if RECURSE_NATIVE_DEPTH can be made 10,000 or more on the CLI thread with the standard 6x margin, the fallback is unreachable in the shipped binary and exists for library callers on small threads. Either way, past the cap the residual returns for those levels, and that is documented and pinned (D5).

Considered and rejected: a bigger thread per recurse call (not no_std, 'a across threads, heavyweight per call); stacker-style segmented stacks (new dependency, out of proportion).

C. Measurements before any number is chosen

1. Bytes per native level. Build with the fallback disabled; bisect the deepest [limit(N; 0 | recurse(.+1))] | length that survives on the CLI thread, release and debug, the way spike(jq): measure per-call native stack cost to decide #1371's evaluator architecture — ~4.4 KB/level, linear #2080 did for def (two stack sizes 8x apart, confirm linear). Repeat for path mode (path(limit(N; ..)), PathBranch frames are bigger), and for an f that misses eval_owned_fast_path so the reindex route's frames are counted. k and RECURSE_NATIVE_DEPTH come from the worst of those with the 6x margin MAX_EVAL_FRAMES uses.
2. Peak memory, fact 4. /usr/bin/time -l on [recurse(.[]?)] | length and on a reindex-route f, pre and post, over a generated document with depth near 256 and its bulk at the leaf, plus the ordinary users/nested shapes. If the reindex route retains ancestors measurably, record the bound (≤ depth × size) in the walker's doc comment; it is not a reason to keep the residual, since today's walk already pays the same reindex work per level.
3. Compositions, both profiles: recurse inside a def recursing to just under MAX_EVAL_FRAMES, and a deep def inside f. Each must fall back or raise the resource-limit error, never abort.
4. Timing, per docs/guides/benchmarking.md: interleaved A/B, inputs of 1 MB and up, on the parameterised spellings ([recurse(.[]?)]|length, [recurse(.children[]?)], path(recurse(..))) on ARM and x86_64. Bare .. on a cursor is each_recurse_cursor_generic and does not move. Expect neutral-or-better (the native order has no next buffer and no reversed push); the perf-guard fails on any drift including improvements, so plan a rebaseline.

D. Tests

1. Move the three rows of recurse_still_finishes_a_nodes_f_before_descending_2918 into recurse_runs_f_only_on_demand_2693 with jq's own stderr; that test is written to trip when the residual closes.
2. Add the four rows from fact 3, each captured whole (stdout, stderr, exit) from jq 1.7.1, plus [recurse(.[]; (true, error("x")))] as a stays-the-same row.
3. Differential native-vs-fallback: for a corpus of f/cond/document shapes, force the cap to 0 and to unbounded and assert identical delivered values and identical terminal Flow/ResolveFlow. That is the guard against the "duplicated predicates diverge silently" hazard, the same trick collect_each uses for lazy arms.
4. All existing jq: recurse/recurse(f) drop a null child and flatten a single array-valued child #490/jq: recurse(f; cond)'s cond argument still collapses multi-output via eval_owned_expr, breaks truthiness check #627/jq: recurse(f)/recurse(f;cond) use breadth-first queue order, diverging from jq's depth-first definition #635/jq: recurse(f; cond) silently prunes on a cond/f error instead of propagating it like jq does #636/jq: recurse(f) drops f's own partial fan-out when a later f output errors (value + path evaluators) #842/jq: recurse(f; cond) drops cond's already-approved siblings on a later cond error #854/yq/jq: resolve_recurse's null-child guard discards the null child's own path entirely #856/jq: eval.rs's ~50 remaining read-only builtins never got #1746's decode-failure fix #1755 pins pass unchanged; they are the rule pins the table in A promises.
5. One row past the cap (limit deeper than RECURSE_NATIVE_DEPTH on the chain shape) showing the residual is still there, so a change to the cap trips a test rather than passing silently.
6. Stack safety on an explicitly sized thread (the parser.rs precedent): the deep chain with the fallback engaged, and both compositions from C3.
7. succinctly yq shares the walker: capture from yq v4.53.3 whether recurse(f)/recurse(f; cond) are accepted at all, and add yq rows only if they are (never from memory, ADR-0018).

E. Docs

• docs/compliance/jq/limitations.md, the "What remains" paragraph of the recurse bullet: closed within the native budget; residual only past the cap; drop the "cannot suspend a push-driven f" claim; cite jq: recurse's f is not suspended between its own outputs, so a node's later f outputs still fire (#2693 residual) #2918.
• each_recurse_walk's "What this does not fix" and resolve_recurse_sink's "What this does not close" paragraphs, and queue_recurse_children's doc (fallback-only now).
• No ADR: no new protocol, and the depth budget rides the existing frame guard. The decision and the measured numbers go in the walker's doc comment.

F. PR shape

One PR, three commits so the review can separate the refactor from the behaviour change:

1. refactor(jq): extract expand per domain and the generic walker with the fallback order only. Byte-identical; the jq: recurse's f is not suspended between its own outputs, so a node's later f outputs still fire (#2693 residual) #2918 pin test still passes; goldens unchanged.
2. fix(jq): add the native order, the cap and the charge; move the rows (D1, D2, D5); differential test (D3).
3. docs(jq): E.

Risks

• The generic walker's &dyn Fn re-entrancy with PathBranch<'a> may fight the borrow checker. If it does, keep two walkers, one per domain, each on its own single expand; the differential test still guards both.
• resolve_leaf is the one consumer that keeps a Halt from Flow::Stopped { pending }; the native order cannot produce one. Re-run test_short_circuit_side_effect_leaks_820_932_987 and the halt rows; a halt reached inside an already-descended subtree still propagates as Escaped, which is the case that matters.
• Fact 4's memory bound on the reindex route is the one place this could be a regression rather than a wash; C2 decides, before the numbers are chosen.

[newhoggy]

🔧 Claimed by agent Miles — branch issue-2918-recurse-suspend-f-between-outputs

[newhoggy]

Follow-up filed while implementing: #3047 (pre-existing yq read-only operand scope leak into a nested operand's as body; the #2918 branch restores the walk's own scope per native level, so recurse stays consistent, but the underlying bug reproduces on main without recurse).