fix(parser): reject over-deep and oversized input instead of overflowing the stack - #295

Problem

An authenticated client of any role could abort the whole server with one frame. A 20 KB program of 4,000 nested calls (+nr(abs(abs(...abs(1)...)))) overflowed the tokio worker's 2 MiB stack in the recursive term parser. Rust aborts the process on a stack overflow, so every connection and subscription in the cell went down with it.

The audit of other recursion over client input found more of the same:

• Rule and query bodies. The plan nests one level per body predicate and per constant. A body of 128 atoms already overflowed a 2 MiB stack.
• Rule chains. Stratification's recursive Tarjan walk overflowed on a chain of about 8,000 rules.
• Type expressions. list[list[...]] had no depth limit.
• Restart. A persisted rule with 40 or more nested calls overflowed serde_json's 128-level limit on reload, so StorageEngine::new failed with WalUnreadable and the engine would not start.

Fix

• Terms and type expressions nest at most storage.performance.max_nesting_depth levels. The default is 128 and the cap is 1024; 0 resets to the default. Each call, arithmetic operator, parenthesized group, list[...] and record adds a level.
  • Deeper input fails with a validation error: Expression nesting exceeds the limit of 128 levels (storage.performance.max_nesting_depth).
  • An O(n) parenthesis-depth check refuses deep calls and groups before descending.
• A rule or query body may hold at most 4,096 elements, counting each predicate plus each body-atom argument (Rule body is too large: N elements (body predicates plus body-atom arguments); the limit is 4096). The widest rule in the repo's examples is about 21.
  • Without the cap, 4,096-element bodies of every shape complete without overflow on a 16 MiB stack in release. These include 2,048 self-joins and 2,048 distinct atoms, which take about 150 s of CPU but don't crash.
  • On a 64 MiB stack in debug, 4,096 comparisons, constants and negations complete, as does a 4,096-element body holding a 1,024-deep term. 8,192 elements overflow there.
• Tarjan SCC walks with an explicit frame stack.
• The server runtime and the incremental worker run on 64 MiB stacks (ENGINE_THREAD_STACK_BYTES). This is the budget the limits were measured against. The extra space is virtual and only committed when used. The server's startup, including WAL and catalog replay, also runs as a runtime task, so it gets the same stack.
• WAL records and the rule catalog decode through storage::nested_json. JSON within serde_json's limit takes the old path. Deeper records, up to a bound derived from the nesting ceiling, decode on an engine-sized stack using serde_json's unbounded_depth feature.

Evidence

Live, release build, over /ws:

Cheap query ?r(X), three alternating rounds of 300 queries: p50 was 0.137-0.145 ms on this branch and 0.138-0.151 ms on main. That is the same within noise.

Tests:

• tests/nesting_depth_tests.rs checks deep input on every statement form, that each limit is inclusive (at the limit evaluates, one past is refused), the configured limit up to the ceiling, type expressions, and a restart with rules at both limits. It runs on a runtime set up like the server's.
• Parser unit tests cover depth 4,000 and 100,000.
• A proptest fuzz target, deep_nesting_is_refused_not_overflowed, generates nested calls, groups and operator chains (seeded around the limit, at 4,000, and up to 20,000) in five statement forms.
• Also added: a 200,000-node chain SCC test and nested_json bound tests.

Follow-ups filed while landing: #301 (fuzz harness) and #302 (HNSW recall test flake). The CI sharing-test flake is tracked in #289.