079. Derived Compute Budget

  • Status: Partially Implemented: the derivation and its report have landed, and the derived value is not the default until the linear-cost proof confirms its constants
  • Author: @ornew
  • Date: 2026-11-22

Summary

For a start rule that the classifier classifies as Linear, the classifier derives a bound on the compute units of a parse, c * n + k, from the structure of the grammar, in the logical events of record 076. sxir lint -classify and lint.Classify report it. The default of Limits.Compute stays max(2^20, 1024 * n) until the linear-cost proof confirms the constants of the derivation; then the derived bound, with a stated safety factor, replaces the default for a Linear grammar. A parse that exceeds its compute limit names the rule that was being evaluated when the limit was found exceeded.

Motivation

The default max(2^20, 1024 * n) is a guess. It is too small for a grammar whose single evaluation costs more than it (a grammar with 280 variables needs about 6.57 million units on a one-character input, because the memo key of each call reads every variable), and too loose to stop an attack on a small grammar. Record 064 planned a constant c_G from the classifier, and record 066 reserved the place for it in the defaults of Compute. Neither fixed the units or the formula. Record 076 fixes the units: the logical events, the same on every backend. A default tighter than the true bound would reject valid inputs, so the bound must come from the proof and not from measurements.

Goals

  • A bound that is a function of the grammar alone, in the units of record 076, the same on every backend.
  • A bound that is reported before it is applied, so that its soundness can be tested against measured units.
  • No effect on a parse until the proof confirms the constants: the default stays as it is and Unlimited stays explicit.
  • An exceeded limit tells the user where to look, at no cost to a parse that stays within its limits.

Non-Goals

  • A derived bound for a grammar that is not Linear. A class of linear given an environment bound depends on the bound of the environment, and the other classes have no bound that a constant of the grammar gives. The caller sets Compute for them.
  • Naming the rule that repeats its work when a limit is exceeded. Record 078 does.
  • Changing the proof. The constants below are the classifier's reading of the lemmas, to be confirmed.

Design

The Bound

For a grammar of the class Linear, with K the bound that the classification reports on the combinations of the values of variables with finite values, the units of a parse of n position units are at most

c * n + k, with c = K * sum over rules r of E(r) * B(r) and k = c + 2.

n is the length of the input in the position unit of the parse, as it is for the default of Compute. The constants count a literal in bytes and a character, class or . as four, the widest UTF-8 encoding, which is at least what a code-point position unit advances, so one bound holds for both units.

k has two terms. The first is c: the proof bounds the cost by K * (n + 1) times a constant, and the + 1 is the position at the start (and after the last unit) where the cost of a parse does not depend on the input. This is the grammar-size term. c sums E(r) * B(r) over every rule that the start rule reaches, and E(r) is at least 1 for each of them, so c contains one evaluation of every reached rule with the memo keys of its calls: a grammar whose memo keys read 280 variables has a large c and therefore a large k, which is why the default of 2^20 rejects it on a one-character input. The second term, 2, is the two events that no position carries: the entry call of the start rule and the final syntax error of a failed parse (the first and the eighth rows of the table of record 076).

B(r) is the events of one evaluation of the body of r:

Part of the body Events
A call of a rule 1, and 1 more for each variable of the callee's memo key if the callee is memoized
A literal its length in bytes, and 1 for the syntax error that a failed match can build
A character, a class or . 4, and 1 for the error
A recovery, a capture, a predicate, an inline action 1
The action of the rule 1
Inside a repetition the events of its body count once more, for the iterations cover each position twice, and once more for each repetition that encloses it

E(r) is the evaluations of the body of r at one position and level, for each combination of the variables:

Rule Evaluations
Memoized, or the start rule 2
In a left-recursion cycle of m rules 2 * (m + 1)
Any other the sum, over its call sites, of the evaluations of the rule that holds the site

Every constant comes from a lemma of the proof and is to be confirmed by it:

Constant Value Lemma
Evaluations of a memoized rule 2 per combination, so 2K in all Lemma 3
Cover of a repetition 2: the spans of one scanning construct overlap only at their ends Lemmas 4 and 13
Growth steps of a cycle one for each rule of the cycle, plus one Lemma 5
Evaluations of a rule that is not memoized as often as its call sites in its callers Lemma 10
The memo key 1 per variable, a constant for a grammar with no string variable Lemma 2 and record 076
A value that an action builds at most linear in the spans of the captures it reads, counted 1 per node Lemma 6
The width of a class 4 the UTF-8 encoding

The derivation applies to the class Linear only, where there is no string variable and L = 0 in the theorem. A count that passes what a counter holds makes the bound absent, not wrong.

The Report

sxir lint -classify prints a line budget: at most c * n + k compute units for an input of n position units, and its JSON output has a member budget with perUnit and fixed. lint.Classification.Budget carries the same two numbers. All three are absent for a class other than Linear. They state that the bound is derived and is not the default.

The Default

The default stays max(2^20, 1024 * n). When the proof confirms the constants, the default of a parse of a grammar that is Linear becomes the derived bound times a documented safety factor, and a grammar that is not Linear keeps max(2^20, 1024 * n) with the class reported by sxir lint -classify. Unlimited disables the bound as it does today. The measured soundness of the bound (below) stays as a test after the switch.

Alternatives

  • Calibrating c from measured units. It would be tight on the corpus and unsound for any input that the corpus does not hold. Rejected: a default tighter than the true bound rejects valid inputs.
  • A bound for every class. For the other classes no constant of the grammar bounds the cost.

Validation

  • The derivation has unit tests for each part of the table, with the memo key term checked against a grammar with and without a variable.

  • The bound is at least the measured units of the Linear grammars of the logical-unit corpus on generated Go, in the units of record 076 (the benchmark package's soundness test): valid, truncated and damaged inputs, at several sizes, in both position units, for Parse and ParseValue. XML (unknown), chain (polynomial) and keyed (linear-env) have no budget. The test logs the largest ratio of measured units to the bound:

    Grammar Bound Inputs Largest measured / bound
    JSON 634 * n + 636 68 0.019
    policy 54 * n + 56 5 0.055

    The bound is 18 to 53 times the largest count. A bound with half the constants still holds on this corpus, so the mutant divides them by 64 and must be exceeded by some parse of each grammar; this also fails a derivation that grows looser than that.

  • The proof's confirmation of each constant is the gate of the default.

Limitations

  • The bound is on the units of record 076 and of the Cost section that adopts them. A backend that still charges the earlier per-operation units can report Used above it; the report is true of a backend once it has adopted them, and the measured-soundness test (Validation) is its check on generated Go.
  • The bound is loose: it adds every part of every rule, and takes 2K for each rule.
  • It holds only if the constants of the table hold. Until the proof confirms them it is a report.