135. Shared Recovered-Error Lists
- Status: Implemented
- Date: 2026-11-08
Problem and Mechanism
A memo entry, a result of a growth and an attempt of an Operators Rule stored a copy of the errors recovered in their
call, and a call that reused the result appended the copy again, one unit of Compute for each error. In a grammar of
the class Linear whose result at each item holds the errors of all the items after it, or a left-recursive leader whose
seed holds those of all the items before, Compute and memory grew with the square of the input, and the default limits
ended the parse at about 2,000 items.
The record of recovered errors is now a sequence of entries, each an error or an immutable list, as the
operations of the Exec IR state it. rec.since
charges one unit for each entry after its mark and returns none, the one entry, or a new list that takes the place of
the entries; rec.add records a result's list as one entry for nothing. Lemma 14 bounds the charges and the entries of
the lists by a constant times the cost, and listing the errors of the outcome visits at most twice as many lists as
there are errors.
Applicability
| Execution profile | Applied / Partial / Not applied / Not applicable | Reason |
|---|---|---|
| Closure, bytecode, iterative bytecode | Applied | state/recovered.go, used by calls, growths, Operators Rules, context results and skip-run records |
| Generated Go | Applied | pkg/runtime/libgo/recovered.go; needs runtime protocol 2 or later |
| Generated TypeScript | Applied | ErrList in the TypeScript runtime |
| Documents | Applied | An entry that holds errors is not moved after an edit, so no list moves |
| Streams | Applied | A stream reports whole entries and flattens a list only when it reports it |
| Missing-token insertion | Not applied | The errors of every reused result are recorded one by one |
Reproduction
Base: the revision before the change, Go 1.27.1, Apple M3 Max, serialized with benchlock, test binaries of the bench
package (one per variant), with an identical copy of the base binary as a noise control. Compute: the least budget that
completes a parse, found by bisection, of the two grammars of the
measured controls at 250 to 4,000 items. Time:
(A) 10 interleaved rounds over all 260 rows of bench, including the incremental and stream rows, against the main
revision it was rebased onto; (B) 20 rounds over the 13 rows that an earlier comparison flagged, before that rebase;
(C) 10 rounds over the 24 bytecode rows of JSON and XML and five closure and generated rows, with a variant whose engine
memo entry is padded back to its former 168 bytes, run only while the load average stayed below 2. Tests:
TestSlopeGateCountsRecoveredErrors in the complexity test support, TestGeneratedGoRecoveredErrorsLinear and
TestGeneratedTSRecoveredErrorsLinear.
Results
Compute for each item, 250 to 4,000 items, against the base:
| Target | Right recursion | Left-recursive leader |
|---|---|---|
| Closure | 148.6–152.6 (518–6,147) | 43.0–44.1 (293–4,045) |
| Generated Go | 162.6–166.5 (532.5–6,164.5) | 48.0–49.1 (299.3–4,050.9) |
| Generated TypeScript | 178 (base rose from 546 to 1,674) | 77 (base rose from 324 to 4,078) |
Memory of a generated Go parse of the right-recursive grammar at 4,000, 8,000 and 16,000 items: 10.0, 20.3 and 41.4 MB, against 64.9, 141.4 and 313.3 MB when the default limits stopped the base.
Time against the base (medians):
| Set | Result |
|---|---|
| A, 260 rows | geometric mean −0.16% (control +0.02%), B/op −0.94%, cached bytes −4.5%. Above +1%: 15 bytecode rows of Parse, ControlledParse and BudgetControlModes (+1.0% to +1.8%) and the closure FreshDocument adoption (+1.3%); StreamDiagnosticLimit complete +5% B/op, where the result flattens the lists into a slice |
| B, 13 rows | geometric mean +1.09% (control +0.02%); generated bytes rows +0.9% to +1.5%, the generated recognizer of Recovery +1.4% (+1.2% B/op) |
| C, 29 rows | geometric mean +0.82% without the padding and +1.08% with it (control −0.14%); bytecode BudgetControlModes rows up to +2.3% without and +2.1% with it |
Correctness and Tradeoffs
Trees, errors and their order are unchanged, compared against the base on the three backends with Document edits. The bytecode rows of A and C cost 1.0% to 2.3% more time on parses that recover nothing. A CPU profile of the JSON bytecode row spreads the difference over the call protocol with no single hot spot, and restoring the former size of the memo entry does not remove it, so the cause is not established. The rows are accepted as measured for Compute and memory that stay linear in the worst case.
Decision and Limits
Adopted on every target, always on. Not covered: the missing-token mode, whose replays no lemma bounds. Lemma 16 of the linear cost proof bounds the number of errors that a result reports by a constant times the input, so listing them stays within the cost of a parse outside a Document.