064. Grammar Complexity: a Cost Model, a Classifier and Safeguards
- Status: Partially Implemented
- Author: @ornew
- Date: 2026-10-28
Summary
A SyntaxIR parse does not always run in linear time. Packrat memoization bounds how often a rule body runs at a position, but parts of the language have a cost that the memo does not share, so a small grammar can take quadratic, cubic or exponential time, or build values of exponential size. This record defines what a parse costs, per construct. It proposes:
- a sound static classifier that labels each start rule
Linear,Linear·Env,Unknown,Poly(k)orExp, with a witness or a reason; - two runtime changes that make linear what can be made linear: memoizing the members of left-recursion cycles, and reusing a repetition's run after backtracking;
- a lint warning for variables that grow themselves;
- a regression suite that measures cost at n, 2n, 4n and 8n;
- an opt-in automatic budget of c·n.
The remaining super-linear constructs are reported and bounded by the budget instead.
Motivation
The current claim
The runtime comment on deferred memoization says that evaluating a memoized rule at most twice per position keeps
"parse time" linear (internal/runtime/state/runtime.go:490-495). The bound on evaluations is correct. Linear time does not
follow from it. Ford's linearity argument assumes that every nonterminal has a constant cost per position
besides its calls, and that every repetition is desugared into a memoized right-recursive nonterminal. SyntaxIR deviates in
four ways:
- Repetitions are loops inside a rule body (Repetition). One evaluation of a body can scan any amount of input, and the memo does not share that scan with evaluations that start at later positions.
- Rules on a left-recursion cycle that are not its leader are not memoized while a growth at their position can change their result (Evaluations of Rules); they are evaluated again at each step of that growth.
- A left-recursion leader grows a seed at each position, and Operators Rules fold operators at each position. The result at p shares nothing with the result at p+1.
- Rules that read variables are memoized per combination of values (Interaction with memoization). Bindings can make the combinations diverge without bound, and value actions can build values of any size.
Measured growth
Revision 8acf9918, Go 1.27.1, darwin/arm64, closure backend, code points. Each figure gives:
- the exact threshold of
Limits.Budget, found by bisection to 0.5%; - the rule evaluations reported by
Profile.Evals; - the bytes allocated per parse.
Steps are deterministic for a fixed artifact, input and options (Cancellation and budget limits). The ratios therefore do not depend on timing noise.
| Grammar | Input family | Steps as n grows | Order | |
|---|---|---|---|---|
| E0 (control) | main = (A / "a")* $$; A = "a" "c" |
a^n |
n=1k…8k: 15,040 → 30,080 → 60,160 → 120,320 | n |
| E1 | main = (A / "a")* $$; A = "a"* "c" |
a^n |
n=1k…4k: 2.02M → 8.06M → 32.1M; 3.6 GB allocated at 8k | n² |
| E7 | main = (A / "a")* $$; A = (B / "a")* "c"; B = "a"* "d" |
a^n |
n=100…400: 0.78M → 5.77M → 44.4M | n³ |
| E9 | main = ("a" !Rest)* "a"* $$; Rest = "a"* "c" |
a^n |
1.02M → 4.03M → 16.1M | n² |
| E8 | main = (X / "a")* $$; X = (Y #recover(skip=[a]+)) "c"; Y = "b" |
a^n |
0.56M → 2.13M → 8.26M | n² |
| E6 (control) | main = (E "q" / "x")* $$; E = "x" E / "x" |
x^n |
43,136 → 86,272 → 172,544 | n |
| E6 | the same with E = E "x" / "x" |
x^n |
6.55M → 26.2M → 104M; evaluations ≈ n²/2 | n² |
| E10 | the same with E = #operators { operand "x"; level add { infix left "" } } |
x^n |
n=500…2k: 0.51M → 2.02M → 8.06M | n² |
| E2 (control) | main = C $$; A = "n"; C = "(" C ")" "y" / "(" C ")" "z" / A |
(^n n )z^n |
n=8…16: 572 → 824 → 1,076 | n |
| E2 | the same with A = C "+" / "n", which puts A and C on a left-recursion cycle led by A |
the same | n=8…16: 7,520 → 29.8k → 119k → 477k → 1.91M | 2^n |
| E3 (control) | var v string; R = "(" {v := "0"} R ")" "y" / "(" {v := "1"} R ")" "z" / "n" {len(v) >= 0} |
as E2 | 1,388 → 2,112 → 2,840 | n |
| E3 | the same with {v := v + "0"} and {v := v + "1"} |
as E2 | n=6, 8, 10: 75k → 1.52M → 29.9M; memo hits 0 | ≥ 2^n |
| E4 | var s string = "a"; R = "x" {s := s + s} R / {len(s) > 0} |
x^n |
n=16…22: 0.39M → 1.58M → 6.31M → 25.2M; evaluations linear | 2^n value size |
| E5 | main = xs:"x"* => len(foldl("a", $xs, (acc, x) => acc + acc)) |
x^n |
identical to E4, in one action | 2^n value size |
E2 grows the same way on the bytecode and iterative backends. The budget limit stops every case above in proportion to the cost, because the closure backend charges value construction by size.
A further case is a correctness defect rather than a cost. var k int; R = {k := k + 1} R "x" / "x" recurses
without consuming input until the nesting limit stops it. The time grows quadratically with the limit: 4, 14, 56 and
227 ms for limits of 1k, 2k, 4k and 8k. The left-recursion guard is found through the memo, whose key includes the
variable environment (internal/runtime/state/runtime.go:142-148). A call with a different environment therefore does not
fail as Left recursion requires. A separate change
rejects such a grammar at compile time: a binding of a variable that a left-recursion cycle reads is an error when the
binding may run before a left call into the cycle. A binding that runs only after the left call is allowed, because the
recursive call has then already been made. The same change keys the runtime guard by rule and position only. The model
below assumes both.
Why this matters
A server that parses untrusted input with a fixed grammar cannot tell from the grammar whether an attacker controls the exponent of its running time. The same is true of an editor that parses every keystroke with a user's grammar. Budget limits stop a runaway parse. They do not tell the grammar author that the grammar is the cause, or which rule to change.
Goals
- State what a parse costs in time and memory, per construct, and the conditions under which it is linear.
- Classify every start rule soundly: a
Linearverdict is never wrong. Other verdicts may be pessimistic and carry a witness path. - Make the constructs linear that can be made linear without changing results: repetitions re-scanned after backtracking, and left-recursion cycle members.
- Warn about variables whose binding grows from their own previous value.
- Offer an opt-in budget derived from the input length.
- Prove the classifier's soundness on paper, and check it by measurement with deterministic step counts.
Non-Goals
- Deciding the exact complexity of an arbitrary grammar. This is undecidable (see Soundness).
- Linear time for left-recursion growth and Operators Rule folds that a grammar backtracks over. The result at p cannot be shared with p+1; these constructs are classified and budgeted.
- Restricting what variables and actions may compute. Self-growing bindings are warned about, not rejected.
- Finite default budgets: parses stay unbounded unless the caller opts in.
Design
Cost Model
A parse is a tree of rule evaluations. Its time is the sum, over every body evaluation, of the evaluation's local cost: the terminals it matches, its loop iterations, the actions and predicates it evaluates and the memo lookups it makes, excluding the bodies of the rules it calls. Its memory is the memo table, plus the values it builds, plus the call stack. Memory never exceeds a constant times time, because every entry and every value costs at least one budget unit to create.
Per construct:
| Construct | Evaluations per position | Local cost per evaluation | Shared by the memo? |
|---|---|---|---|
Memoized rule (Memo, outside a left-recursion cycle) |
≤ 2 per (rule, position, level, environment): the first call is not stored, the second is (runtime.go:490-495) |
body size, plus loops | yes, for the whole body |
| Transient rule (called from one site, or calling no rule) | bounded by its caller's evaluations of that site | as above | through its caller |
| Left-recursion leader | 1 growth per (rule, position, environment) | one body evaluation per growth step; steps ≤ span + 1 | the final result only |
| Non-leader member of a left-recursion cycle | every call, and once per growth step of its leader | as above | no |
Repetition, Scan, ClassRun |
once per evaluation of the enclosing body | proportional to the span it matches | no |
| Lookahead | once per evaluation of the enclosing body | the cost of its body; consumes nothing | no |
#recover(skip=e) |
once per failure of its base | the base's cost plus the skip's span | no |
| Operators Rule | as a memoized rule, per binding level | proportional to the operators folded | the result per level only |
| Predicate or value action | once per evaluation of its body | proportional to the sizes of the values it reads and builds | no |
| Variable environment | multiplies memo keys by the number of distinct environments at a position | equality of the environment | per environment |
Spans are what makes local cost unbounded. A construct whose local cost grows with its span is called a scanning
construct: an unbounded repetition, Scan, a left-recursion leader, an Operators Rule, a recovery skip whose walks are
not shared, and a lookahead whose body contains one. A parse is linear when no input position is covered by the spans
of more than a constant number of evaluations of each scanning construct, and the number of environments per position
is bounded.
Conditions for Linearity
A start rule is Linear when every rule reachable from it satisfies these four conditions.
-
L1, finite environments. No variable that a memoized rule reads is bound, along a recursion of the call graph, from an expression that reads the variable's own previous value. Bindings from literals, from captures and from other variables are allowed; their number of distinct values at one position is treated as a constant K. When K depends on the input, the verdict is
Linear·Env, linear times the number of environments that occur at one position. An example isindent := len($s), whose values are bounded by the line length. A binding such asv := v + "0"along a recursion (E3) violates L1 and givesExp. -
L2, memoized cycles. Every rule that can be evaluated twice at one position, outside its own left-recursion growth, is memoized. A non-leader member of a left-recursion cycle with two call sites that can reach the same later position (E2) satisfies L2 because members are memoized outside the growth at their position.
-
L3, non-overlapping scans. No scanning construct stands in a backtracking context. A backtracking context is one where its evaluation can be abandoned and the parser can then start another evaluation of the same construct strictly inside the span it covered:
- a choice alternative that is not the last;
- a repetition element or a sequence item that something able to fail follows;
- a lookahead body;
- the base of a
#recover.
The context of a construct is the chain of such contexts from it through the callers of its rule, memoized or not. A memoized call does not end the context: the memo shares the result of a rule at one position, not its scan between positions. In
main = (a "y" / "q" a / .)*witha = x+andx = "x", every rule that scans is memoized, yet aftera "y"fails,.consumes one character and the next iteration callsaone position later, which scans the rest of the input again: n x's cost about n²/2 steps. A memoized recursion brings the scan back in the same way, as int = a t "!" / . t / "". A context is safe if it is committing:- the alternatives that follow have first terminals disjoint from the construct's continuation;
- or a cut follows the first terminal of the alternative;
- or what can fail after the construct cannot fail after the construct has consumed input.
A repetition after the run-reuse change below is not a scanning construct for L3, because a restart inside its run reuses the run.
-
L4, bounded values. No predicate or value action makes a value whose size can double per evaluation. Examples are
s + son a value that flows back into the same binding (E4), andacc + accorconcat(acc, acc)on a fold accumulator (E5). An accumulator extended by bounded pieces (acc + text(x)) is quadratic in time because strings are copied, and givesPoly(2)for that action. Record 071 states when copies of a value of a recursion double it: only when they become part of the value of the rule that the next level copies again.
Classifier
Verdicts form a chain, from best to worst:
Linear < Linear·Env(vars) < Unknown(reason) < Poly(k, witness) < Exp(witness)
-
Unknownis assigned when a condition fails without a witness of growth, as when units that are not committing nest without bound through a recursion of rule calls. A witnessedPolyorExpcause outranks it: a witness is evidence of growth, whileUnknownis only the absence of a proof. Record 070 revises this chain: a reason outranks polynomial causes, so that the degree ofPoly(k)bounds every condition that fails, andUnknownreports the largest degree of its polynomial witnesses only as a lower estimate. -
Poly(k)is assigned when L3 or L4 fails. k is one more than the deepest nesting of unsafe scanning constructs along a path of the call graph: E1 has k = 2 and E7 has k = 3. Each unsafe level multiplies the input positions where an inner scan can restart. -
Expis assigned when L1 fails, when L2 fails on a cycle whose re-entry multiplies, or when L4 finds a doubling. The witness names the rules, the binding or the call sites involved. -
A start rule's verdict is the worst verdict of the rules it reaches. A rule's verdict also feeds the verdicts of its callers, because it is part of their local cost.
The automatic budget needs, for a Linear start rule, a constant c_G, an upper bound on cost per input position. It is
the sum, over memoized and transient rules, of twice the local cost of one body evaluation without loops, plus the
per-iteration cost of each loop. Record 079 defines the constant that the classifier computes, in the units of
record 076, and its report.
Soundness argument (sketch). The cost of a parse is the sum, over every body evaluation, of its local cost. For a grammar that satisfies L1–L4, with the left-recursion guard keyed by rule and position:
- A memoized rule is evaluated at most 2K times per (position, level) outside growth, by deferred memoization and L1. A transient rule is evaluated at most as often as the call site in its unique caller. The chain of callers ends at a memoized rule or the start rule. Under L2 no other rule is evaluated more than once per growth step.
- The non-loop local cost of one evaluation is bounded by the size of its body.
- Loop and scan cost is bounded by spans. Under L3, the evaluations of one scanning construct at distinct starts have spans that overlap only at their ends, or the overlap is answered by a memo hit or a reused run. Summed over a parse, each construct therefore covers each position a constant number of times. Left-recursion growth is a scanning construct, so the same argument bounds its steps.
- Under L4 every value built is at most linear in the spans of the captures it reads, and its construction is charged to the evaluation that builds it.
Summing gives cost ≤ c_G · K · (n + 1), and memory ≤ cost.
The conditions are sufficient, not necessary. They over-approximate in these ways:
- Predicates are assumed to be able to both succeed and fail.
- First terminals are path-insensitive.
- A backtracking context is assumed to be reachable even when the input can never reach it.
Exact classification is undecidable. For a well-formed grammar G, consider main = W Gadget, where W must parse a word
of L(G) and Gadget is E1. This grammar is super-linear exactly when L(G) is non-empty, and emptiness of a PEG's language
is undecidable [Ford 2004]. The classifier can only be sound in one direction. A Poly or Exp verdict is therefore a
hint with a witness, not a proof that a slow input exists.
Where It Plugs In
- The classifier (the classifier files of the complexity package) is a pass over the grammar that the compiler runs: inline actions
lowered to hidden rules and attributes normalized. It reuses the rule facts of the Core IR (
internal/middleend/corepass/facts.go) (nullability, rules that always succeed, the left-call graph, its SCCs, leaders and cycle members) and runs only when asked, not at every compile. It assumes that the memo answers exactly the rules that every parse memoizes, and a test compares that assumption with the flags of the compiled rules, so the two cannot drift apart. Findings in hidden rules are reported in the rules that hold the inline actions. sxir lintreports the results through two checks:growing-variable, a warning on by default: a binding of astringvariable that joins the variable's own value at least twice (s := s + s), when the variable can hold a non-empty value there and the bound value reaches a later evaluation of the same binding. Growth by a bounded piece, such asindent := indent + " ", is not reported, nor areintandboolbindings, whose effect is on cost. This is a certain fact about the grammar, so it meets the warning contract of Severities. It needs only the bindings that the classifier collects, so a default lint run skips the rest of the classification.super-linear, a hint at each cause of aPoly(k)orExpverdict, with its witness path. A hint because the slow input may not exist. It runs only when the classification is requested, withsxir lint -classifyorlint.Config.Classify, which also shows the verdict, the degree of a polynomial verdict and the first witnesses or reasons.
- The
right-recursionhint gains a caveat. Right recursion stays linear under memoization in batch parses (E6 control). The repetition or left recursion it suggests is a scanning construct that L3 must check.
Runtime Improvements
Memoizing left-recursion cycle members. A non-leader member of a left-recursion cycle is memoized (optimization record 130). Instead of stamping entries with a growth generation, the parser never stores a result that depends on a seed that can still change:
- a result that read the seed of a growth in progress when its call started is not stored;
- while a leader grows at a position, a member result there is evaluated again instead of reused;
- a result that read the result of a leader that can grow again at its position with another result is not stored.
Documents and interruption already discard state that depends on unfinished growth, and keep doing so. Cost: one memo entry per stored call of a cycle member, and the depth bookkeeping of each memoized call, which grammars without left recursion also pay. E2 is linear.
Reusing a repetition's run after backtracking. A Document already records the run of a repetition of 16 or more
elements: positions, examined range, expectations and values per element, about 80 bytes per element. It reuses the
run after an edit (docs/optimizations/054, 059, 070). Batch parses can use the same records to answer a restart
inside a run:
- When a repetition site starts at a position that is an element boundary of a recorded run of the same site, with the same environment and the same remaining count for bounded repetitions, the suffix of the run is the result.
- The elements before the restart are dropped; element values are shared.
- Recording is deferred like memo entries: a site records its runs only after it has restarted inside an earlier run once.
Cost: nothing on a grammar that never restarts inside a run. On one that does, 80 bytes per element of the runs it records. E1, E7, E8 and E9 become linear, because the inner scan at p+1 is the suffix of the scan at p. A run cannot be reused across a capture scope boundary whose captures the elements read, nor while a left-recursion seed it depends on is growing; such runs are not recorded.
What stays super-linear. Left-recursion growth and Operators Rule folds that a grammar abandons and restarts (E6,
E10) build a different result at each position. They stay Poly(2). The classifier names the rule and the
backtracking context, and the budget bounds them. Variables violating L1 and doubling values violating L4 stay
exponential by design, and are warned about.
Budgets
The single budget keeps charges for value construction
proportional to the size built: string concatenation, concat and list materialization, and fold accumulators. A
per-call or per-iteration charge alone lets E4 cost 2^n while charging n.
The budget of a Linear start rule is c · (n + 1) + k for the input length n, derived by the classifier
(record 079); record 066 makes every parse budgeted by
default, so the opt-in option of this record is replaced by the default of Compute. For other verdicts the caller gives
the budget. Exhausting the budget returns the ordinary limit error. When the parse has a profile, the error names its
hotspot, the rule with the most repeated evaluations at one position (MaxEvals of the rule rows of Profile), as
record 078 specifies.
Specification
Time and Memory specifies the cost of a parse, the conditions for
linear cost and the classification; Grammar Lint specifies the two checks. The
specification promises linear cost only for the classes Linear and Linear·Env, under the memoization that it
describes.
Compatibility and Backend Support
The classifier and the lint checks add findings and change no parse. Memoizing cycle members and reusing runs change only cost, which Memoization permits. Node identity becomes different where entries are shared, and it is already unspecified. The closure backend, both VMs and generated Go implement the runtime changes. Generated TypeScript follows when it implements Documents, whose run records it lacks. Compiled grammars carry the memo flag of cycle members, and the format may change before the first release.
Implementation Sequence
- The step-ratio regression suite, with the E-series as negative controls (no behavior change).
- Memoizing left-recursion cycle members; E2 moves to the positive set.
- Repetition-run reuse in batch parses and streams on the engine backends, under which E1, E7, E8 and E9 measure linear; E8 is a positive control through the recovery-skip refinement, and E1, E7 and E9 stay classified polynomial.
- The classifier over the grammar that the compiler runs, and the
growing-variableandsuper-linearlint checks. - The automatic budget option, after the single budget lands.
- The Complexity section of the specification, and corrected comments where the code claims linear time.
Steps 1, 2, 3 and 4 and the specification of step 6 are implemented, and E2 is a positive control. The closure and
bytecode backends keep run records for the walks of #recover skips
(Optimization 132) and of restartable repetitions
(Optimization 133) in batch parses and streams, so
E1, E7, E8 and E9 measure linear there. Generated parsers keep no run records. The classifier relies on none, so E8 is a
positive control through the recovery-skip refinement, while E1, E7 and E9 stay classified polynomial. The automatic
budget is not implemented.
Alternatives Considered
- Memoize every repetition suffix, as Ford's desugaring does. This gives linear time for all of L3 except left-recursion growth. It costs a memo entry per element of every repetition. Optimization 018 measured that most memo entries are never used, so this is rejected as the default. Deferred run reuse obtains the same bound only where restarts happen.
- Elastic or bounded memo tables [Kuramitsu 2015] and cut-driven memo release [Mizushima et al. 2010]. These bound memory, not time. The memo never changes results, so eviction is semantically safe and stays open as a later memory control (see Decisions).
- Per-construct budgets (left-recursion growth steps, recovery skip length). These add options a user cannot calibrate. A single budget plus a verdict naming the construct gives the same protection with one knob.
- Rejecting super-linear grammars. Classification is pessimistic and many such grammars are fine on real inputs, so rejection would refuse correct grammars. Lint findings and budgets keep the choice with the author.
- Analysis on Core IR. It would judge the module after rewrites such as
Scans, but Core IR is built only for generated parsers, and the conditions are stated on the grammar. The grammar after lowering and normalization is what every backend compiles; the memo-policy test keeps the classifier aligned with the compiled rules.
Testing
- Step-ratio suite (the complexity test support). Each E-series control and each corpus grammar is measured at input sizes n, 2n and 4n on the three backends, with steps found by bisection over the budget limit. A control must show its order from the table above; a corpus grammar's worst cost per byte may grow by at most 1.1 from 2n to 4n. Steps are deterministic, so the suite is stable without timing.
- Classifier verdicts on the controls. Each control has an expected class: a positive control is classified
LinearorLinear·Env, a negative control never is, and a polynomial degree matches the measured order. - Classifier soundness by differential testing. Random grammars over a small alphabet, in the shapes of the
E-series and with string and list rules whose actions and predicates copy, index, measure and compare the values of
their recursions, are classified, and every grammar classified linear is measured on several input families on the
closure and bytecode backends: its cost per byte at 4n stays within 1.2 times that at n or 2n. A
Linearverdict with super-linear growth is a classifier bug. A negative control treats the grammars classifiedPolyorExpas linear and must fail, so the test can catch a classifier that claims too much.
Not yet in place:
- Worst-case search. Mutate inputs to maximize steps per input length, in the manner of SlowFuzz and PerfFuzz [unverified citations], for corpus grammars classified non-linear. Confirmed witnesses become fixtures.
- Equivalence. The runtime changes keep values, errors and recovered errors identical with and without them, on every backend, in Documents across edits, and under interruption during left-recursion growth.
Classification of the Bundled Grammars
The grammars in testdata/grammars/ and examples/, except json and the two calculators, are classified Poly, Exp or
Unknown. The verdicts are upper bounds and the witnesses are paths, not slow inputs, and the corpus inputs are benign,
so a verdict alone does not tell whether a cause is imprecision of the classifier, a cost that the runtime can remove,
or a cost inherent in the language. Every cause is therefore sorted by measurement.
The causes of each grammar are grouped by shape, and every witness and every reason belongs to exactly one group.
the testdata/triage/<grammar>.txt files of the complexity test support lists the causes of each group, and TestTriageCoverage keeps
the lists complete and current. Each group has adversarial input families derived from its witness paths, in
the triage files of the complexity test support. Each family is measured at three or four doubling sizes, with steps found by
bisection over the budget limit, on the closure backend, both bytecode VMs and a generated Go parser:
SXIR_TRIAGE=. SXIR_TRIAGE_GO=1 go test -run TestTriageMeasure -v ./internal/testing/complexitytest
The variable is a regular expression over grammar/group/family. The test prints one row per family and backend, and
fails when a measured order differs from the recorded one. The exponent is the logarithm of the cost ratio over the
logarithm of the input length ratio between consecutive sizes, so families whose length is not proportional to their
size parameter, such as indentation staircases, are judged against the input length. The backends agree on the order of
every family except duckdb's runs of signs and minilang's nested operators, which the run records keep linear on the
engine backends and which a generated Go parser, keeping no such records, runs in n². The table gives the worst exponent
of each group over its families and backends.
The groups are addressed by these mechanisms:
- Token-scan refinement of the classifier. Token alternatives that scan the same prefix again, and whitespace, comment or name scans that a failed alternative gives back to a continuation starting with the same characters, cost a bounded amount per position. They measure linear.
- Units nested through a memoized recursion (open). Units that are not committing, nested through a memoized
recursion, and a source reached again at one position through memoized calls, measure linear in the bundled
grammars, but the memo does not bound them: in
t = a t "!" / . t / ""witha = x+andx = "x", the unita t "!"is nested in itself through the memoizedt, every rule that scans is memoized, and the cost is quadratic, since each restart callsaone position later. Re-evaluating the same calls at the same position (shared literals, continuation paths split at a shared call) removes few of these causes. Their linearity depends on how much input a failing unit examines, as in CEL, where a failingmemberexamines only a constant amount at-beforeneg_unarycallsmemberone position later; no condition captures this yet, and the causes stay reasons for the class Unknown. - Bounded-binding refinement of the classifier. A binding that reads its own earlier value is not exponential when
its values come from a set bounded by a constant. Condition 1 exempts a variable with finite values: a
bool, a variable bound only to constants, as YAML's context stringc, or anintwhose values reachable from its initial value form a finite set, each with at most 65536 values (Lemma 8). The product of the sizes of the sets is the bound on K that the class Linear reports, so a large constant is visible instead of being refused; the sets are admitted from the smallest up to a product of 2^32, and a variable left out loses only its own exemption. Anintbinding is evaluated when it reads only itself, literals and the lengths of captures bounded by a constant; any other binding is bounded by its guard, tests next to it with only predicates between, so that no value that a test rejects reaches a call or a later binding:{v := e} {lo <= v && v <= hi}or{lo <= e && e <= hi} {v := e}. The language has no declared ranges; a grammar states a range with the predicates it already has. The values that reach a binding are those after the earlier elements of its sequence, so the order matters: TypeScript's start rule sets its context flagsctxto 64 or 0 by a choice and then adds 2, which a closure over every value found would repeat without end, and its other bindings clear and set bits, addinglenof the captures"*","async"andlist($m). The flags take 128 values, and the TypeScript class is the polynomial of its identifier scans. This also covers Python'sisdict. Python'slvcounts the format specs around a replacement field withlv := lv + 8192in its format spec rule, and the nesting limit is tested in the replacement field that calls the rule, which bounds the field's own binding but not this one; the test{lv / 8192 <= 3}after the binding, which never fails, bounds it as well, and the classifier reports K of at most 32080. Python'sind, CUE'ssvand YAML'snread the lengths of unbounded captures. For TypeScript the profile shows a constant number of evaluations per byte and at most four evaluations of a memoized rule per position at every nesting depth, so no exponential input exists. Memoizing across variable values that a rule does not read would lower a constant, not the order. A recursive call that follows consumed input does not bound the values: inmain = (r / .)* $$withr = "#" {v := v + 1} r / "y" {v >= 0}, each start reaches every later position with a different value ofv, and the cost on n characters#is cubic. - Lambdas over bounded lists. A fold or map over a list with a constant bound on its number of elements runs its
lambda a constant number of times, so condition 4 checks its copies as copies outside the lambda
(Lemma 7). Python's parameter lists and
dictionary displays fold over the
/marker and a#repeat(,1)value, and they carry no cause; the corpus measures them linear. A bounded fold inside a map over a list that is not bounded still copies its outer values once for each element of that list, and a fold whose accumulator doubles stays exponential, since its factor is exponential in the bound. Whether an accumulator can double is decided by the step matrix of the fold: the size, the largest element and the number of elements of the value of the lambda, each bounded by terms in the same three quantities of the accumulator, times powers of the sizes of the values read from outside the fold and of the element of the step. Counting copies of the accumulator alone cannot tellfoldl(list(), acc, (s, l) => list(l, l)), which keeps one element twice and does not grow, fromfoldl(list(), map(acc, (e) => list(e, "x")), (s, l) => concat(s, l)), which pads every element and doubles the number of elements on each step; the three quantities can. The matrix doubles the accumulator when a cycle of its graph has a coefficient above 1 or a factor of a size, or two cycles share a quantity. Otherwise it bounds each quantity by a polynomial in the input, and a value read from outside counts as large as its size degree allows on every step, while the elements of the step add up to the size of the list over all steps, soacc + text($c)grows quadratically andacc + text(y)linearly. The cost of the steps follows from the same terms, with comparisons andlenof a string examining their operands, multiplied where a fold inside the lambda copies its own accumulator once for each of its elements, and a fold over a list that is not bounded is reported with its degree when that is 3 or more. The size degrees of the initial value, the list and the values read from outside come from what the classifier knows of them: an own value, at most a constant times the input its match consumes, has degree 1, and own values of distinct matches add up to the input; a value built by an action has the degree that the same forms give it from what it reads, through the rules it calls, so a rule that joins its whole text once for each of its elements has a quadratic value, and a fold that adds that value on each step costs n^4; a recursion whose values are not own has one more degree than one level adds when it holds each value of the recursion once, and no known degree otherwise. The same sizes bound the copies of elements in a lambda over a list that is not bounded:map(map($b, (q) => text($b)), (y) => y + "x")copies elements that add up to n^2 characters. The matrix is an upper bound: a term it does not follow, such as a block, counts as many copies of what it reads, and an exponential class may over-approximate. A fold inside lambdas over lists that are not bounded runs once for each of their elements, so each of them adds the size degree of its number of elements, except the innermost when the fold runs over its elements, those are own captures of a repetition, with no capture in a positive lookahead, and the list has size degree 1, so that their sizes add up to the input. The accumulator of a bounded fold is taken to hold what any number of steps can add, not at most the bound: a fold over#repeat(,1)that adds the value of the rule's own recursion on each step is reported exponential, though it runs at most once and holds that value once, which condition 4 classes polynomial. - Recovery-skip refinement of the classifier. A
#recoverskip whose unbounded repetitions are skip-run sites, with elements that examine a constant amount of the input, and which calls no rule and has no predicate, is not a scanning source: the walks of its sites evaluate their elements a number of times linear in the input plus a constant per walk (Lemma 9), whatever the width of an iteration. A skip that calls a rule stays a source, since a called rule can examine any amount of the input. The nested recoverys = ("(" s ")") #recover(skip=[a(]+)is then linear. minilang keeps a reason for its recovery: when a statement fails inside a block, its skip stops before the{, and the next statements parse the block again, which only the memoizedstmtkeeps linear. - Constant-cost text in the cost model. The cost model guarantees that the text of a node costs a constant in a whole-input parse and a Document, and that a string comparison costs at most its shorter operand, so the classifier does not count a text as a copy. The text of a recursive capture, as in Python's f-string replacement fields, is then linear, and a scan under a text (the body of a CUE string, a CUE name, a comment in the XML prolog, a DuckDB dollar-quote tag) is reported as the scan itself, which belongs to the token-scan groups or to the open groups of nested units.
- Repetition-run reuse. duckdb's operator lookahead reads the run of
+and-after an operator character, and a prefix operator at each character of the run reads the rest again. The run records make this linear on the engine backends, whereSELECT++^n +1costs 51.7k, 102k and 203k steps for 210, 410 and 810 bytes; a generated Go parser keeps none and spends 334k, 1.19M and 4.45M. The same repetition arises in the operator parts after an operand that prefix operators or a right-associative operator nest: each enclosing operator part tries them again where the nested operands end, and a skip that repeats one character class, which no record answers, scans the same whitespace each time. In CEL,-^naanda?b:^nafollowed by n spaces measure n² on a generated Go parser (thespacegroup). minilang's skip repeats a choice, so it is a run site, and its families measure linear on the engine backends; a generated Go parser keeps no run records for it and measures them n², which the classifier, relying on no records, reports. - In-place fold accumulators. Python folds that copy their accumulator in each step (
acc + "." + name,concat(acc, x)) are quadratic in the list length: a dotted import name of 2k, 4k and 8k bytes costs 2.07M, 8.15M and 32.3M steps. Extending the accumulator in place when the old one is dead makes them linear. - Grammar rewrites. Python's
try_stmtmaps itsexcept*handlers inside a fold over the same handlers (1.63M, 5.78M and 21.6M steps for 6k, 12k and 24k bytes), and CUE builds the elements of an interpolation by a right recursion whose action copies the list of the rest at every level (1.26M, 4.70M and 18.1M steps for 4k, 8.2k and 17k bytes). Replacing the action of the CUE recursion with its tail alone measures 205k, 410k and 824k steps for the multi-line family, so a repetition with one flat concatenation is linear. The classifier reports this copy of a recursion's own value as a polynomial witness of degree 2 in each rule of the recursion, and in each rule that starts an interpolation, which copies the list of the rest once but counts as a copy of the recursion, because the rest is a value on a cycle of such values. CUE's plain multi-line strings test the indentation of each line in a fold that joins the closing indentation with U+10FFFF for every line. Every line that the fold reaches starts with the closing indentation, so the joins copy no more than the input and the families measure linear, but the classifier sees a copy of a value from outside the lambda for each element. Testing the indentation in the check that already tests strings with interpolations removes the fold. - Value-size refinement. Folds that read values of a recursion whose size the classifier does not bound: Python's
keyword arguments and implicitly joined strings read the values of
star_expressions, and TypeScript's union and intersection folds read values of a type recursion. TypeScript's families measure linear; Python's measure n² because of the accumulator copy of the in-place fold group. - Lookahead-capture refinement. A value that can hold a capture in a positive lookahead is not bounded by the input that the match consumes. TypeScript's JSX element names compare the capture of the opening tag with the closing tag, which is a false positive: each tag consumes its name right after the lookahead that captures it, and the families measure linear.
- Unassigned groups. TypeScript's literals (the digits of a decimal literal and the characters of a string, read
again by the alternative that follows) measure linear. DuckDB's block comments nest through a recursion in which the
alternative that opens a comment is not committing against the one that consumes a character, so a run of
/*xthat is never closed measures n² (2.00 on the closure backend and the others); no mechanism is assigned to it yet.
| Grammar | Group | Causes | Addressed by | Families | Worst exponent | Order |
|---|---|---|---|---|---|---|
| csv | quoted-field | 1 | token-scan refinement | 2 | 1.00 | n |
| xml | nested | 3 | open | 3 | 1.02 | n |
| xml | prolog-misc | 1 | open | 4 | 1.00 | n |
| xml | name-scan | 4 | token-scan refinement | 3 | 1.00 | n |
| xml | ws-option | 4 | token-scan refinement | 2 | 1.00 | n |
| cel | nested | 19 | open | 6 | 1.00 | n |
| cel | names | 1 | token-scan refinement | 2 | 1.00 | n |
| cel | space | 2 | repetition-run reuse | 2 | 1.81 | n² |
| cel | number-tokens | 5 | token-scan refinement | 2 | 1.00 | n |
| cel | string-tokens | 2 | token-scan refinement | 1 | 1.04 | n |
| outline | nested | 2 | open | 1 | 0.97 | n |
| outline | blank-lines | 2 | token-scan refinement | 2 | 1.00 | n |
| minilang | recover | 2 | open | 3 | 1.01 | n |
| minilang | nested-operators | 1 | open | 2 | 1.99 | n² |
| minilang | nested-operator-parts | 8 | open | 2 | 1.99 | n² |
| golang | nested | 157 | open | 14 | 1.01 | n |
| golang | comments | 16 | token-scan refinement | 7 | 1.01 | n |
| golang | identifiers | 1 | token-scan refinement | 2 | 1.00 | n |
| golang | line-directives | 4 | token-scan refinement | 2 | 1.01 | n |
| golang | numbers | 3 | token-scan refinement | 2 | 1.00 | n |
| duckdb | nested | 624 | open | 16 | 1.01 | n |
| duckdb | operator-tails | 15 | repetition-run reuse | 5 | 1.96 | n² |
| duckdb | strings | 4 | token-scan refinement | 5 | 1.00 | n |
| python | bounded-variables | 2 | bounded-binding refinement | 5 | 1.01 | n |
| python | except-star-handlers | 4 | grammar rewrite | 2 | 1.91 | n² |
| python | fold-copies | 16 | in-place fold accumulators | 4 | 2.00 | n² |
| python | nested | 146 | open | 11 | 1.03 | n |
| python | module-whitespace | 4 | token-scan refinement | 1 | 1.00 | n |
| python | tokens | 17 | token-scan refinement | 8 | 1.00 | n |
| python | whitespace | 53 | token-scan refinement | 5 | 1.00 | n |
| typescript | nested | 257 | open | 28 | 1.01 | n |
| typescript | identifiers | 5 | token-scan refinement | 5 | 1.00 | n |
| typescript | whitespace-and-templates | 2 | token-scan refinement | 3 | 1.00 | n |
| cue | hash-count | 1 | bounded-binding refinement | 2 | 1.00 | n |
| cue | multi-line-indentation | 1 | grammar rewrite | 2 | 1.00 | n |
| cue | string-bodies | 6 | token-scan refinement | 5 | 1.00 | n |
| cue | interpolation-copies | 10 | grammar rewrite | 0 | – | n² |
| cue | file-clauses | 2 | open | 2 | 0.99 | n |
| cue | nested | 52 | open | 8 | 1.01 | n |
| cue | definitions | 5 | token-scan refinement | 3 | 1.00 | n |
| cue | numbers | 5 | token-scan refinement | 6 | 1.00 | n |
| cue | raw-strings | 10 | token-scan refinement | 5 | 1.00 | n |
| cue | whitespace | 12 | token-scan refinement | 5 | 1.00 | n |
| yaml | indentation-bindings | 2 | bounded-binding refinement | 3 | 0.99 | n |
| yaml | nested | 36 | open | 5 | 1.00 | n |
| yaml | block-scalars | 4 | token-scan refinement | 3 | 1.00 | n |
| yaml | directives-and-tags | 2 | token-scan refinement | 3 | 1.00 | n |
| yaml | scalars | 4 | token-scan refinement | 4 | 1.00 | n |
| yaml | separation | 15 | token-scan refinement | 6 | 1.00 | n |
| yaml | stream-prefix | 1 | token-scan refinement | 1 | 1.00 | n |
| duckdb | nested-comments | 1 | unassigned | 1 | 2.00 | n² |
| python | value-sizes | 8 | value-size refinement | 1 | 1.97 | n² |
| typescript | literals | 6 | unassigned | 2 | 0.99 | n |
| typescript | value-sizes | 2 | value-size refinement | 2 | 0.98 | n |
| typescript | jsx-names | 1 | lookahead-capture refinement | 2 | 1.00 | n |
No cause is inherent. Every group either measures linear on every family derived from its witnesses, or its super-linear cost comes from a construct of the grammar or the runtime (a restarted scan, a copied accumulator, a recursion that copies its own list, the nesting of block comments) that a linear formulation of the same language avoids. No family needs a budget beyond the linear one, so no group carries budget guidance.
Literature
Citations are from memory and are not verified against the publications; titles and venues should be checked before this record is accepted.
- B. Ford. Packrat Parsing: Simple, Powerful, Lazy, Linear Time. ICFP 2002. Linear time when every nonterminal, including desugared repetitions, is memoized.
- B. Ford. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. POPL 2004. Well-formedness implies termination. Emptiness of a PEG's language is undecidable.
- A. Warth, J. Douglass, T. Millstein. Packrat Parsers Can Support Left Recursion. PEPM 2008. Seed growing. Linearity is not preserved in general.
- S. Medeiros, F. Mascarenhas, R. Ierusalimschy. Left Recursion in Parsing Expression Grammars. Science of Computer Programming, 2014.
- K. Mizushima, A. Maeda, Y. Yamaguchi. Packrat Parsers Can Handle Practical Grammars in Mostly Constant Space. PASTE 2010. Cut releases the memo table; cuts are inserted where first sets are disjoint.
- K. Kuramitsu. Packrat Parsing with Elastic Sliding Window. Journal of Information Processing, 2015.
- R. Grimm. Better Extensibility through Modular Syntax. PLDI 2006. Selective memoization with transient productions.
- R. Becket, Z. Somogyi. DCGs + Memoing = Packrat Parsing, but Is It Worth It? PADL 2008.
- N. Weideman, B. van der Merwe, M. Berglund, B. Watson. Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA. CIAA 2016. Exponential and polynomial degrees from ambiguity.
- V. Wüstholz, O. Olivo, M. Heule, I. Dillig. Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions. TACAS 2017.
- Y. Shen et al. ReScue: Crafting Regular Expression DoS Attacks. ASE 2018.
- J. Davis, F. Servant, D. Lee. Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS). IEEE S&P 2021. Memoizing selected states gives linear-time backtracking; the closest analogue of this design.
- T. Petsios et al. SlowFuzz, CCS 2017; C. Lemieux et al. PerfFuzz, ISSTA 2018. Worst-case input search.
None of these analyzes PEG grammars for super-linear behavior. The regex results transfer in shape: a polynomial degree
comes from nested scanning constructs that can restart inside each other, as in E1 and E7, and that degree is what
Poly(k) reports. Ordered choice and greedy repetition remove the ambiguity within one construct that drives regex
blow-ups. That leaves unmemoized re-entry and diverging state as the exponential sources.
Decisions
- The specification promises a bound only for certified grammars. A parse of a grammar that the classifier certifies as linear has a cost proportional to the input length. Other grammars carry no promise beyond termination. The classifier's soundness is therefore normative. The alternatives were no promise, which leaves users nothing to check, and a promise for every grammar, which restarted left-recursion growth and Operators Rule folds make impossible.
super-linearis a hint, shown only on request. The lint contract requires a warning to be certain, and aPolyorExpverdict may be pessimistic. The finding carries the witness path. Because many grammars that work well on real input are classifiedPoly, the hint and the verdict appear only withsxir lint -classifyorlint.Config.Classify, and a default lint run stays free of estimates.growing-variableis certain and stays on.- Run reuse is on by default. Recording is deferred until a site restarts inside an earlier run, and an optimization control disables it, as the memo has. It is adopted only if the corpora and benchmark grammars, which never restart inside runs, show no slowdown. Without that evidence it stays behind the control.
- Memory has no bound beyond cost. Budget bounds memory linearly. A memo-entry cap with eviction, which is semantically safe except for growing seeds and Documents, is reconsidered when a Document or stream workload shows memo memory as the limit. A byte budget for values is not added. Record 066 revises this decision: a memory measure bounds what the parser holds, beside the compute measure.
- The automatic budget uses c_G times a safety factor. The factor is documented, and the caller can override c. For grammars that are not certified linear, the caller must give c. A corpus-measured constant was rejected because it is wrong for unusual grammars.
- Restarted left-recursion growth and Operators Rule folds are classified and budgeted. E6 and E10 stay
Poly(2), reported with a witness and bounded by the budget. Reusing end positions in recognition mode was rejected: it would be linear only without values, and would add a second growth path to maintain.
Limitations
- The classifier is sound only in one direction. A
PolyorExpverdict may have no slow input. - The soundness argument is a proof sketch. The regression and differential tests check it; it is not mechanized.
- The constant c_G is in the units of record 076, which are the same on every backend, and depends on the constants of that record's table, so a change of the table changes the budget between releases.
- The citations in the Literature section are unverified.