fix(wire): recursive Serialize/Drop on FuncSpace lack the #700 de-recursion

[dekobon]

Summary

Issues #700 / #709 systematically converted every AST traversal to an
explicit work stack, with regression tests pinned to small (256-512 KiB)
stacks. That work did not cover the recursive types, which still recurse
one frame per nesting level with no depth cap.

Sites

• src/wire.rs:411-423 — impl From<&spaces::FuncSpace> for wire::FuncSpace
  is directly recursive:

  spaces: f.spaces.iter().map(FuncSpace::from).collect(),

• Derived Serialize on FuncSpace { spaces: Vec<FuncSpace> }
  (src/spaces.rs:207) and on wire::Ops (src/wire.rs:425).
• Compiler-generated Drop glue for FuncSpace and AstNode
  (src/ast.rs:151) — no hand-written iterative Drop.

Nesting depth is attacker-controlled via nested functions / classes /
closures, which are ordinary legal constructs in every supported language.

Deserialize is protected by serde_json's built-in 128-depth recursion
limit. Serialize has no such guard.

Why file this now

Fixing #1052 may unmask it. Today the depth needed to overflow the stack
cannot be reached, because the O(leaves x depth^2) cost in
src/metrics/tokens.rs makes such input time out long before serialization
runs. Once the metric cost is linear, deep inputs will actually complete and
reach these recursive paths. The DoS is currently masking the stack hazard.

This was not demonstrated to overflow — the attempt timed out first, exactly
as described above. Treat it as a real but currently-unreachable hazard, and
re-test after #1052 lands.

Precedent in-tree

The project already knows the shape of this problem and works around it
elsewhere: src/output/dump_metrics.rs:368-375 and
src/output/dump_ops.rs:245-252 flatten trees before drop specifically to
avoid stack overflow, and big-code-analysis-cli/src/markdown_report.rs:1489-1493
resorts to std::mem::forget past depth 50,000. The production
FuncSpace / AstNode paths do none of this.

Suggested direction

• Iterative Drop for FuncSpace and AstNode, matching the existing
  flatten-before-drop pattern.
• A depth cap or iterative serializer for the wire conversion and
  Serialize impls, mirroring serde_json's Deserialize guard.
• Extend the Terminal dumps: unbounded recursion + selection-mask ignored + tree-connector glitches #700/Library misc correctness: emacs-mode window off-by-one, Count NaN%, cfg_predicate recursion, threshold/vcs_command items #709 small-stack regression tests to cover
  serialize and drop, not just traversal — re-run after perf(metrics/tokens): O(leaves x depth^2) ancestor walk is a DoS vector #1052.

---

Scope correction (see comments)

The Drop half of this title is not implicated. bca check builds and
drops a 10 000-deep FuncSpace chain without overflowing; bca metrics -O json aborts at 1 000. The bug is the recursive Serialize path —
wire.rs's From<&spaces::FuncSpace> and the derived Serialize on
FuncSpace { spaces: Vec<FuncSpace> }.

Reproducer: 1 000 nested fns (~11 KB) -> fatal runtime error: stack overflow, aborting, exit 134. Scales with FuncSpace nesting, not AST
depth — nested parens at depth 200 000 (400 KB) finish in 272 ms.

SIGABRT, not a catchable panic, so bca-web's spawn_blocking panic
handling does not contain it: the whole process dies with every in-flight
request.

The three existing small-stack tests from #700/#709 all pass — they cover the
dump walk and construct FuncSpace values directly, so nothing exercises
serialization.

---

Fix in review — #1082

Fixed in 3fd01c70, workspace bumped to 2.1.0 in 7b8f3fd6, both on
fix/1056-recursive-serialize-drop. Open for review as #1082; this
issue closes on merge. See the
findings comment for measurements and
verification.

• Iterative Drop for FuncSpace and AstNode — and for Ops,
  wire::FuncSpace, wire::Ops. The scope-correction note above was
  wrong to write Drop off: re-measured, it aborts at ~16 000 levels
  in a debug build and ~65 000 in release, which fits inside
  bca-web's 4 MiB body cap.
• A depth cap for the wire conversion and the Serialize impls.
  The conversion (From<&spaces::FuncSpace>) needed no cap — it is
  now iterative, and was in fact the site of the reported
  1 000-level abort. Serialize cannot be de-recursed through
  serde, so it is bounded by wire::MAX_SPACE_SERIALIZE_DEPTH
  (128) and MAX_AST_SERIALIZE_DEPTH (512).
• Small-stack regression tests covering serialize and drop, each
  verified to fail against the pre-fix code.

Also fixed, not in the original list: the derived Serialize on
AstNode (src/ast.rs). /ast aborted on an 80 KB payload of
nested parentheses — cheaper to reach than the FuncSpace path, since
AST depth costs no space nesting.

Deliberate SemVer exception: the Drop impls forbid moving fields
out of these types by value (E0509). Landed under a minor bump rather
than held for 3.0; recorded under (breaking) in CHANGELOG.md and
in STABILITY.md.

Left open (not reachable today): the derived Clone on FuncSpace /
Ops is still recursive. No production path clones a whole tree.

[dekobon]

Reproducer, and a severity correction

This is reachable today with an ~11 KB file, and it aborts the process
rather than panicking.

$ python3 -c "n=1000; open('/tmp/nf.rs','w').write(''.join('fn f%d(){'%i for i in range(n)) + '}'*n)"
$ bca metrics --no-config --metrics sloc -p /tmp/nf.rs -O json
thread 'Consumer 0' (2461013) has overflowed its stack
fatal runtime error: stack overflow, aborting
$ echo $?
134

Threshold on this machine: 500 nested functions fine, 1000 aborts. Scales
with FuncSpace nesting depth, not AST depth — nested parentheses at depth
200 000 (400 KB) complete in 272 ms without incident, because they open a
single space.

Why this is worse than the DoS in #1052 / #1062

A stack overflow is SIGABRT, not a catchable panic. bca-web wraps every
analysis in spawn_blocking, so a panic becomes a JoinError and costs one
request (web/server.rs:136-143) — but an abort takes the whole process
down, every in-flight request with it. The 4 MiB body cap does not help: the
payload here is kilobytes.

Not caused by the recent perf work

I had predicted the #1052 / #1062 fixes might unmask this by letting deep
input finish instead of timing out. That is wrong, and worth recording so
nobody bisects toward those commits: the reproducer above uses
--metrics sloc, which computes neither tokens nor cognitive, so neither
quadratic path was ever in the way. It reproduces on main independent of
that work.

Scope note

The #700 / #709 de-recursion converted every AST traversal to an explicit
work stack, with small-stack regression tests. It did not cover the recursive
types: wire.rs's From<&spaces::FuncSpace>, the derived Serialize on
FuncSpace { spaces: Vec<FuncSpace> }, and the compiler-generated Drop
glue. The prior art for the fix is already in-tree —
src/output/dump_metrics.rs:368-375 and dump_ops.rs:245-252 flatten before
drop for exactly this reason, and markdown_report.rs:1489-1493 resorts to
std::mem::forget past depth 50 000.

Worth a security label alongside bug, given the bca-web exposure.

[dekobon]

Narrowing: it is Serialize, not Drop

Isolated the two halves of this issue's title. Only serialization overflows —
Drop survives a far deeper FuncSpace chain than the reproducer needs.

bca check builds and drops the identical space tree without serializing it;
bca metrics -O json serializes it. Same input, release binary:

nested fns	check (build + drop)	metrics -O json
1 000	ok	abort (134)
2 000	ok	abort
5 000	ok	abort
10 000	ok	abort
30 000	timeout, not overflow	abort

-O toml aborts identically, so it is not json-specific.

So the fix should target wire.rs's impl From<&spaces::FuncSpace> and the
derived Serialize on FuncSpace { spaces: Vec<FuncSpace> }. The
compiler-generated Drop glue is not implicated at these depths — worth
re-measuring before spending effort there.

(The 30 000 check timeout is a separate, known problem: the remaining
Node::parent ancestor walks tracked in #1062, not a stack issue.)

Why the existing stack tests do not catch it

#700 / #709 left three small-stack regression tests, two of which look like
they should cover this:

• dump_metrics.rs:342 deeply_nested_spaces_dump_without_stack_overflow
• dump_ops.rs:226 (same name)
• dump.rs:424 deeply_nested_ast_dumps_without_stack_overflow

All three spawn a 512 KiB-stack thread and run to DEPTH 8 000, and all three
pass. They exercise the dump walk, which #700 de-recursed, and they build
FuncSpace values directly. Nothing exercises the wire conversion or
Serialize.

A regression test should reuse their shape —
std::thread::Builder::new().stack_size(512 * 1024), per lesson #47 — but
drive analyze(..) and then serialize, rather than dump.

Note Deserialize is already protected by serde_json's built-in 128-depth
recursion limit. Serialize has no equivalent.

Reproducer

python3 -c "n=1000; open('/tmp/nf.rs','w').write(''.join('fn f%d(){'%i for i in range(n)) + '}'*n)"
bca metrics --no-config --metrics sloc -O json -p /tmp/nf.rs
# thread 'Consumer 0' has overflowed its stack
# fatal runtime error: stack overflow, aborting          -> exit 134

Threshold on this machine: 500 fine, 1 000 aborts (~11 KB of source).

It scales with FuncSpace nesting depth, not AST depth — nested
parentheses at depth 200 000 (400 KB) complete in 272 ms, because they open a
single space. Testing the wrong shape is an easy way to conclude this is
fixed when it is not.

[dekobon]

Fixed in 3fd01c70 (workspace bumped to 2.1.0 in 7b8f3fd6)

Re-measuring first: Drop is implicated

The scope-correction comment concluded Drop was clear because a
10 000-deep chain survived. It survives because the drop frame is small,
not because the glue is iterative. Measured thresholds on a default
2 MiB thread, per stage, on unmodified main:

stage	release	debug
wire::FuncSpace::from (recursive From)	~900	~380
Serialize → JSON	8 192–16 384	1 024–2 048
Serialize → YAML	4 096–8 192	1 024–2 048
Serialize → TOML	3 072–4 096	384–512
Serialize → CBOR	8 192–16 384	768–1 024
derived Drop	32 768–65 536	8 192–16 384

So the reported 1 000-level abort was the From conversion, not
Serialize — the conversion runs to completion before serialization
starts, at ~2.3 KB per frame. Serialize and Drop are both reachable
too, just needing deeper input: ~380 000 nested fns fit inside
bca-web's 4 MiB body cap.

A fourth site the issue did not list: AstNode

/ast is worse than /metrics, because AST depth is far cheaper to buy
than space depth. 40 000 levels of nested parentheses — an 80 KB
payload — aborted the process in serde_json::to_string on a release
build. The dump walk itself survived (that is #700's work); the
overflow is in the derived Serialize on AstNode, and then again in
its Drop.

The fix

• From is now iterative. wire::FuncSpace::from and
  wire::Ops::from share a map_tree helper driving an explicit work
  stack. Verified converting a 1 000 000-level chain on a 512 KiB
  thread.
• Serialize is bounded, not de-recursed. serde offers no way to
  emit a tree without one native frame per level — serialize_field
  must run the child's Serialize to completion before returning — so
  the depth is capped and a deeper tree fails with an ordinary
  serializer error naming the type and the limit. New public constants:
  wire::MAX_SPACE_SERIALIZE_DEPTH (128, for FuncSpace and Ops) and
  MAX_AST_SERIALIZE_DEPTH (512). The space limit mirrors the 128-level
  recursion limit serde_json's Deserializer already applies to the
  same documents.
• Drop is iterative. FuncSpace, Ops, AstNode, and the two
  wire mirrors hoist descendants into a flat work list. Verified at
  1 000 000 levels.

Picking the limits

Grounded against the corpus under tests/repositories (14 450 files —
TensorFlow, DeepSpeech, serde, …): deepest AST 188 levels, deepest
FuncSpace nesting 10. The limits are ~2.7× and ~13× those. On the
read side a FuncSpace document cannot be parsed back past ~61 levels
anyway (two JSON nesting levels per space against serde_json's 128), so
the emit limit is the more permissive of the two.

The Drop impls are a source-level break

Adding Drop forbids moving fields out by value: let m = space.metrics;
becomes E0509. 13 sites inside this repository needed a .clone() or a
borrow. STABILITY.md reserves source-level breaks for a major bump;
this landed under a minor as an explicit, documented exception (recorded
in both STABILITY.md and the changelog), because the alternative was
leaving a remotely-reachable process abort open until 3.0. Approved by
the maintainer before landing.

Verification

Six regression tests, each confirmed to fail against the pre-fix code
by perturbing production back to its former shape — four of them abort
the test binary with SIGABRT, exactly the reported symptom:

• wire::tests::deeply_nested_spaces_convert_to_wire_without_stack_overflow
  — 8 000 levels through analyze on a 512 KiB thread
• wire::tests::spaces_deeper_than_the_limit_fail_serialization_rather_than_abort
• wire::tests::space_nesting_at_the_serialize_limit_is_accepted_and_one_deeper_is_not
  — exact boundary across JSON / YAML / TOML / CBOR
• wire::tests::deeply_nested_ops_convert_and_serialize_without_stack_overflow
• ast::tests::ast_depth_at_the_serialize_limit_is_accepted_and_one_deeper_is_not
• ast::tests::a_pathologically_deep_ast_errors_and_tears_down_without_overflowing
• recursion::tests::depth_counter_is_restored_after_a_rejection

Per the note in the issue, these drive analyze / build FuncSpace
chains rather than reusing the dump fixtures, so they scale with space
nesting rather than AST depth.

CLI, on the original reproducer:

$ python3 -c "n=1000; open('/tmp/nf.rs','w').write(''.join('fn f%d(){'%i for i in range(n)) + '}'*n)"
$ bca metrics --no-config --metrics sloc -p /tmp/nf.rs -O json
error processing /tmp/nf.rs: FuncSpace nesting is deeper than the serialization limit of 128 levels

Live bca-web, both hostile payloads, same process:

POST /v1/ast     30 000 nested parens  -> 500 {"error_kind":"serialize_failed"}
POST /v1/metrics  5 000 nested fns     -> 500 {"error_kind":"serialize_failed"}
POST /v1/ast     shallow               -> 200
POST /v1/metrics shallow               -> 200
GET  /v1/ping                          -> 200   (process still up)

Known remaining recursion

The derived Clone on FuncSpace / wire::FuncSpace / Ops is still
recursive (aborts around 700 levels). No production path clones a whole
tree — the CLI, web, and Python crates all borrow — so it is not
reachable today, and hand-writing Clone would trade a live-bug fix for
a field-drift hazard the derive currently rules out. Worth a follow-up
issue if a tree-cloning API is ever added.

make pre-commit green.

[dekobon]

Post-merge review note, for the record.

Test cost. The regression tests initially drove analyze at depth
8 000 and cost ~25s each in a debug build — not from the code under
test, but from the quadratic Node::parent ancestor walks tracked in
#1062. Fixed in 8634dd5c: analysed fixtures dropped to depth 2 000
(still ~20x the depth at which the recursive From overflowed a 512 KiB
thread), and a hand-built 100 000-level chain took over the teardown
coverage that the 8 000-level fixture only cleared by ~2x. Seven tests
now run in 2.2s instead of 78s while pinning Drop 25x deeper.

Other recursive derives. Correcting my closing comment, which named
only Clone: Clone, PartialEq, and Debug are all still recursive
on FuncSpace / wire::FuncSpace / Ops (Debug on AstNode too).
Clone aborts around 700 levels. None is on a production path — the
CLI, web, and Python crates all borrow, and nothing compares or
{:?}-formats a whole tree — so none is reachable today, and
hand-writing them would trade a live-bug fix for a field-drift hazard
the derives currently rule out. Worth its own issue if a tree-cloning
or tree-comparing API is ever added.

[dekobon]

Reopening: I closed this when the fix was committed locally, but the
work is not merged yet — it is in review as #1082. The tracker should
reflect merge state, not local state.

Nothing about the fix or the findings above has changed. #1082 carries
Closes #1056, so this will close again on merge.