functionalscript · sergey-shandar · Aug 13, 2026 · Aug 13, 2026 · Aug 13, 2026 · Aug 13, 2026
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -20,6 +20,12 @@ history.
 
 ## Unreleased
 
+- **BREAKING CHANGES:** `fjs/bnf/ll1`'s matcher runs as an explicit-stack
+  machine over a cursor into the shared input, so long or deeply nested input
+  no longer overflows the JS call stack and matching is no longer quadratic.
+  The `MatchRule` type described the recursive matcher and is removed; match
+  results are unchanged
+  [#1531](https://github.com/functionalscript/functionalscript/pull/1531)
 - `types/bigfloat`: `decToBin` no longer returns a 54-bit mantissa when
   rounding carries out of the top bit; the result is always the 53-bit
   IEEE-754 significand

diff --git a/fjs/bnf/ll1/README.md b/fjs/bnf/ll1/README.md
@@ -7,15 +7,44 @@ An LL(1) dispatch/matcher backend built over the BNF data
 `parserRuleSet()` match input into an AST. The builder throws at build time
 (`can not merge …`) when the grammar is not LL(1) — a first/first conflict.
 
-## Logical EOF
+## Logical EOF and the complete cursor
 
 The caller passes physical symbols only; the matcher synthesizes the one logical
 EOF after them ([`../README.md`](../README.md#logical-eof-in-parser-input)). A
-rule that dispatches on `eof` consumes it at the physical end of input, once —
-the match threads an `eofConsumed` flag alongside the remainder, which is the
-`(idx, eofConsumed)` cursor in this backend's remainder-shaped form.
+rule that dispatches on `eof` consumes it at the physical end of input, once.
+Internally a position is therefore a cursor over `0 .. cp.length + 1`, where
+`cp.length + 1` means the synthesized EOF has been consumed — the
+`(idx, eofConsumed)` pair of the shared design written as one number, because
+`eofConsumed` can only be true at the physical end. The same cursor used to be a
+remainder slice paired with a threaded `eofConsumed` flag; it says the same
+thing, and being a number is what lets the input array be shared instead of
+copied (see below).
 
 Remainders stay physical, so consuming EOF leaves an empty remainder rather than
 the `null` this backend reports when a match runs out of input. Since EOF sits
 below every ordinary symbol, its dispatch entry cuts at `-2`; the dispatch map
 holds decoded terminals, never stored endpoint codes.
+
+## Matching without the JS call stack
+
+The matcher is an explicit-stack machine, like the sibling
+[`../descent`](../descent) backend's: it keeps suspended rules-chain frames on
+an immutable cons-cell stack and loops, either dispatching the rule the current
+task names or feeding the pending result into the innermost frame.
+
+The JS call stack cannot do this job here. Matching recursed once per rule in a
+dispatched chain, and a right-recursive rule — which is how `repeat0Plus`
+encodes repetition — puts one such chain per repetition, so the depth grew with
+*input length*, not grammar size: a few thousand code points were enough for
+`RangeError: Maximum call stack size exceeded`. Deeply nested input reached the
+same limit through the same mechanism. The explicit stack grows on the heap
+instead, so depth is bounded by memory (see the `longInput` proof group).
+
+Positions are cursors into one shared input array for the second half of the
+same reason. Consuming a code point by re-slicing the remainder
+(`const [, ...restCp] = cp`) copied the whole rest of the input at every step,
+making a match quadratic in input length; the remainder slice a `MatchResult`
+carries is materialized once, when the match returns.
+
+LL(1) never backtracks, so a cursor only ever moves forward — which is why the
+machine needs no rewind state per frame, unlike the descent backend.
diff --git a/fjs/bnf/ll1/module.f.mjs b/fjs/bnf/ll1/module.f.mjs
@@ -21,7 +21,7 @@
  * @import { StringSet } from '../../types/string_set/types.ts'
  * @import { EmptyTag, RuleSet } from '../data/types.ts'
  * @import { Rule as FRule } from '../types.ts'
- * @import { AstSequence, AstTag, Match, MatchResult, MatchRule, Remainder, _Dispatch, _DispatchMap, _DispatchResult, _DispatchRule, _DispatchRuleCollection, _MatchResultEof } from './types.ts'
+ * @import { AstSequence, AstTag, Match, MatchResult, Remainder, _AstRule, _Dispatch, _DispatchMap, _DispatchResult, _DispatchRule } from './types.ts'
  */
 
 import { strictEqual } from '../../types/function/operator/module.f.mjs'
@@ -150,13 +150,101 @@ export const parser = fr => {
     return parserRuleSet(data[0])
 }
 
-/** @type {(tag: AstTag, sequence: AstSequence, r: Remainder) => MatchResult} */
-const mrSuccess = (tag, sequence, r) =>
-    [{tag, sequence}, true, r]
+/**
+ * A match position over the physical input: `0 .. cp.length` are the physical
+ * positions, and `cp.length + 1` is where the one synthesized EOF has been
+ * consumed.
+ *
+ * This is the `(idx, eofConsumed)` cursor written as one number: `eofConsumed`
+ * can only be true at the physical end, so the pair and the extended position
+ * hold the same information.
+ *
+ * @typedef {number} _Cursor
+ */
+
+/**
+ * Where a match stopped: a {@link _Cursor}, or `null` when it ran out of input
+ * — the `null` {@link Remainder} this backend reports for that.
+ *
+ * @typedef {_Cursor|null} _Position
+ */
+
+/**
+ * The machine's own result: a {@link MatchResult} positioned by a cursor
+ * instead of by a materialized remainder.
+ *
+ * @typedef {{
+ *     readonly ast: _AstRule
+ *     readonly success: boolean
+ *     readonly pos: _Position
+ * }} _Result
+ */
+
+/**
+ * A suspended rules-chain match: `rules[ruleIndex]` is being matched by the
+ * current task, and `seq` holds the ASTs matched so far — starting with the
+ * dispatched symbol's leaf, empty when that symbol was the synthesized EOF.
+ *
+ * @typedef {{
+ *     readonly tag: AstTag
+ *     readonly rules: readonly string[]
+ *     readonly ruleIndex: number
+ *     readonly seq: AstSequence
+ * }} _Frame
+ */
+
+/**
+ * Immutable cons-cell stack: O(1) push/pop, no array copying per step.
+ *
+ * @typedef {null | {
+ *     readonly top: _Frame
+ *     readonly rest: _Stack
+ * }} _Stack
+ */
+
+/**
+ * The rule invocation about to be evaluated, or `null` when a result is ready
+ * to resume the innermost frame instead.
+ *
+ * @typedef {{
+ *     readonly rule: _DispatchRule
+ *     readonly pos: _Cursor
+ * }} _Task
+ */
+
+/** @type {(tag: AstTag, sequence: AstSequence, pos: _Position) => _Result} */
+const mrSuccess = (tag, sequence, pos) =>
+    ({ast: {tag, sequence}, success: true, pos})
 
-/** @type {(tag: AstTag, sequence: AstSequence, r: Remainder) => MatchResult} */
-const mrFail = (tag, sequence, r) =>
-    [{tag, sequence}, false, r]
+/** @type {(tag: AstTag, sequence: AstSequence, pos: _Position) => _Result} */
+const mrFail = (tag, sequence, pos) =>
+    ({ast: {tag, sequence}, success: false, pos})
+
+/**
+ * The semantic symbol a cursor points at: a code point inside the physical
+ * input, and the synthesized {@link eofSymbol} at its end. Only meaningful
+ * where the cursor still has a symbol, `pos <= cp.length`.
+ *
+ * @type {(cp: readonly CodePoint[], pos: _Cursor) => number}
+ */
+const symbolAt = (cp, pos) => pos < cp.length ? cp[pos] : eofSymbol
+
+/**
+ * What consuming the symbol at a cursor contributes to the AST: the code point
+ * itself, and nothing for the synthesized EOF — it has no physical source
+ * element.
+ *
+ * @type {(cp: readonly CodePoint[], pos: _Cursor) => AstSequence}
+ */
+const leafAt = (cp, pos) => pos < cp.length ? [cp[pos]] : []
+
+/**
+ * The public remainder of a position. It stays physical, so consuming EOF
+ * leaves it empty; the slice is materialized once, at the end of a match.
+ *
+ * @type {(cp: readonly CodePoint[], pos: _Position) => Remainder}
+ */
+const remainderAt = (cp, pos) => pos === null ? null : cp.slice(Math.min(pos, cp.length))
 
 /**
  * Creates an LL(1) parser from an already materialized {@link RuleSet}.
@@ -166,57 +254,88 @@ const mrFail = (tag, sequence, r) =>
 export const parserRuleSet = ruleSet => {
     const map = dispatchMap(ruleSet)
 
-    // Matches the rules the dispatched symbol selected, one after another,
-    // starting from `seq0` — the AST of that symbol, empty when it was the
-    // synthesized EOF.
-    /** @type {(d: _DispatchRuleCollection, seq0: AstSequence, cp: readonly CodePoint[], eofConsumed: boolean) => _MatchResultEof} */
-    const items = ({tag, rules}, seq0, cp, eofConsumed) => {
-        let seq = seq0
-        let r = cp
-        let eofDone = eofConsumed
-        for (const i of rules) {
-            const rule = typeof i === 'string' ? /** @type {_DispatchRule} */ (map[i]) : i
-            const [res, itemEof] = f(rule, r, eofDone)
-            const [astRule, success, newR] = res
-            if (success === false) {
-                return [res, itemEof]
+    /** @type {(name: string) => _DispatchRule} */
+    const dispatched = name => /** @type {_DispatchRule} */ (map[name])
+
+    // The matcher as an explicit-stack machine: each iteration either starts the
+    // current task (dispatching one rule and pushing a frame for the rules chain
+    // that symbol selected) or feeds the pending result into the innermost frame.
+    // Semantics are identical to the former recursive matcher, but the JS call
+    // stack stays O(1) however deep the grammar recurses: a right-recursive rule
+    // (e.g. a `repeat0Plus` chain) descends once per consumed code point, so the
+    // depth used to grow with input length and overflow (see the longInput proof
+    // group). Positions are cursors into the shared input array for the same
+    // reason: re-slicing the remainder per step made a match quadratic.
+    /** @type {(dr0: _DispatchRule, cp: readonly CodePoint[]) => MatchResult} */
+    const f = (dr0, cp) => {
+        /** @type {_Stack} */
+        let stack = null
+        /** @type {_Task|null} */
+        let task = {rule: dr0, pos: 0}
+        /** @type {_Result} */
+        let result = mrFail(undefined, [], 0)
+
+        while (true) {
+            if (task !== null) {
+                // The explicit annotation cuts a control-flow inference cycle
+                // (TS7022): `task`'s narrowed type feeds `pos`, which feeds the
+                // `task` assignment below that the narrowing depends on.
+                /** @type {_Task} */
+                const current = task
+                const {rule: {emptyTag, rangeMap}, pos} = current
+                task = null
+                // The one logical EOF is available at the physical end, and only
+                // there: a rule that dispatches on it consumes it, once. Past it
+                // no symbol is left to dispatch on.
+                const dr = pos > cp.length ? null : dispatchOp.get(rangeMap)(symbolAt(cp, pos))
+                if (dr === null) {
+                    if (emptyTag !== undefined) {
+                        result = mrSuccess(emptyTag, [], pos)
+                    } else if (pos >= cp.length) {
+                        // Nothing left to reject: the match ran out of input.
+                        result = mrSuccess(emptyTag, [], null)
+                    } else {
+                        result = mrFail(emptyTag, [], pos)
+                    }
+                    continue
+                }
+                const {tag, rules} = dr
+                const seq = leafAt(cp, pos)
+                const next = pos + 1
+                if (rules.length === 0) {
+                    result = mrSuccess(tag, seq, next)
+                } else {
+                    stack = {top: {tag, rules, ruleIndex: 0, seq}, rest: stack}
+                    task = {rule: dispatched(rules[0]), pos: next}
+                }
+                continue
             }
-            seq = [...seq, astRule]
-            eofDone = itemEof
-            if (newR === null) {
-                return [mrSuccess(tag, seq, null), eofDone]
+
+            if (stack === null) {
+                const {ast, success, pos} = result
+                return [ast, success, remainderAt(cp, pos)]
             }
-            r = newR
-        }
-        return [mrSuccess(tag, seq, r), eofDone]
-    }
+            const frame = stack.top
+            stack = stack.rest
 
-    /** @type {MatchRule} */
-    const f = ({emptyTag, rangeMap}, cp, eofConsumed) => {
-        if (cp.length === 0) {
-            // The one logical EOF is available at the physical end, and only
-            // there: a rule that dispatches on it consumes it, once.
-            const eofDr = eofConsumed ? null : dispatchOp.get(rangeMap)(eofSymbol)
-            if (eofDr === null) {
-                return [mrSuccess(emptyTag, [], emptyTag === undefined ? null : cp), eofConsumed]
+            const {ast, success, pos} = result
+            // A failing item's own result propagates unchanged, exactly as the
+            // recursive version returned it through the chain.
+            if (success === false) { continue }
+            const seq = [...frame.seq, ast]
+            if (pos === null) {
+                result = mrSuccess(frame.tag, seq, null)
+                continue
+            }
+            const ruleIndex = frame.ruleIndex + 1
+            if (ruleIndex < frame.rules.length) {
+                stack = {top: {...frame, ruleIndex, seq}, rest: stack}
+                task = {rule: dispatched(frame.rules[ruleIndex]), pos}
+            } else {
+                result = mrSuccess(frame.tag, seq, pos)
             }
-            // The synthesized EOF has no physical source element, so it adds no
-            // AST leaf, and the remainder stays physical — already empty here.
-            return items(eofDr, [], cp, true)
-        }
-        const [cp0] = cp
-        const dr = dispatchOp.get(rangeMap)(cp0)
-        if (dr === null) {
-            return [
-                emptyTag === undefined
-                    ? mrFail(emptyTag, [], cp)
-                    : mrSuccess(emptyTag, [], cp),
-                eofConsumed,
-            ]
         }
-        const [, ...restCp] = cp
-        return items(dr, [cp0], restCp, eofConsumed)
     }
 
-    return (name, cp) => f(/** @type {_DispatchRule} */ (map[name]), cp, false)[0]
+    return (name, cp) => f(dispatched(name), cp)
 }
diff --git a/fjs/bnf/ll1/proof.f.mjs b/fjs/bnf/ll1/proof.f.mjs
@@ -274,6 +274,27 @@ export const proof = {
             expect('   [{ "q": [ 12, false, [}], "a"] }]  ', false)
         }
     ],
+    longInput: [
+        () => {
+            // Long right-recursive repetition: one `repeat0Plus` chain across the
+            // whole input. This is the shape that overflowed the JS call stack
+            // when the matcher recursed once per consumed code point.
+            const m = parser(repeat0Plus(set(' \n\r\t')))
+            const [, success, remainder] = m('', toArray(stringToCodePointList(' '.repeat(10000))))
+            assertEq(success, true)
+            assertEq(remainder?.length, 0)
+        },
+        () => {
+            // Deep non-repetition nesting: 5000 bracket levels in the JSON-like
+            // test grammar — a shape a repetition-specific fix would not cover.
+            const m = parser(deterministic())
+            const n = 5000
+            const cp = toArray(stringToCodePointList('['.repeat(n) + ']'.repeat(n)))
+            const [, success, remainder] = m('', cp)
+            assertEq(success, true)
+            assertEq(remainder?.length, 0)
+        },
+    ],
     logicalEof: [
         () => {
             // EOF dispatches below every ordinary symbol, so its cut point is