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.