pub struct Budget(/* private fields */);Expand description
How much backtracking one parse may do before AtomStream declares the
input unparseable and reports end of input.
The unit is a serve: one atom handed out by ParseStream::next,
counting every re-read a rollback causes. A count and not a clock, so the
same source produces the same verdict on a fast machine, on a slow one, in
a test and in a browser.
§Why a compiler has one at all
Because without it the compiler does not report anything. Measured on a
release build, over chains of let vN = N in ending in a let with no
right-hand side:
| file | error on | before |
|---|---|---|
| 9 lines | line 6 | exit 1, 7 ms |
| 15 lines | line 12 | exit 1, 32 ms |
| 35 lines | line 32 | still running after 100 s |
The cause was a plain unfactored common prefix: Expr::LetIn and
Expr::LetPatternIn both began let ‹target› = ‹expr› in ‹body›, so a
failure in the innermost body was re-derived exactly twice per enclosing
let. Measured, serves against chain length: 1,115 at 3, 9,459 at 6,
76,211 at 9, 610,227 at 12, 4,882,355 at 15 — ×2.000 each time.
That prefix is now factored and the table above is history:
cst::PatNonVarErased refuses a bare-variable destructuring target — the
restriction upstream 0.1 spells pattern_non_var — which makes the two
alternatives disjoint at the token after let. The same chain costs 411,
750, 1,089, 1,428, 1,767: an arithmetic progression, +113 per let,
pinned as an exact equality by parse_errors.rs’s
one_more_let_costs_a_constant_number_of_serves. No input is known that
reaches this cap any more.
The cap stays anyway, and the row above is why it was worth having: the
0.1 grammar was separately observed to blow up ×5 per 200 bytes on
truncated prefixes of the bundled std-ja.satyh, from a different
prefix that has not been chased down. What a budget buys, and a grammar
fix does not, is that the next such prefix is a slow error instead of a
hang.
The give-up is reported as a give-up
(crate::ParseFailureKind::GaveUp), never as a claim about the token
the parse happened to stop at — and it still carries the high-water mark’s
position, which in every case measured is the line the author must look at.
§Why it scales with the input
A cap has to be unreachable by any honest parse of any honest file, and “honest” is a property per token, not per file: a fixed ceiling that a 300-line file cannot reach is one a generated 30,000-line file can. So the cap is a per-atom allowance, and only superlinear backtracking can outrun it.
Implementations§
Source§impl Budget
impl Budget
Sourcepub const PER_ATOM: u64 = 2_048
pub const PER_ATOM: u64 = 2_048
Serves per atom an honest parse is allowed.
Calibrated from measurement, not guessed: a clean parse costs 14–17
serves per atom, and the worst of the 77 files in the bundled corpus
(dist-v01/packages/tabular.satyh) costs 34.7. This is roughly sixty
times that, and parse_errors.rs’s
the_bundled_corpus_stays_far_under_the_per_atom_budget re-measures
the corpus on every run rather than trusting the figure.
Sourcepub const FLOOR: u64 = 8_000_000
pub const FLOOR: u64 = 8_000_000
Floor, so that a small file still gets the allowance a mid-sized one would.
Without it a ten-line file would be capped at a few thousand serves and would give up on constructs a hundred-line file resolves. At roughly 10M serves per second this is about a second of trying.
Do not raise this to fix a give-up. While the let prefix above
was unfactored, the floor bought a broken chain of fifteen lets a
real verdict and each further doubling bought exactly one more let —
which is the shape of the argument in general: against a superlinear
grammar the budget cannot buy diagnostic quality, only bound the
damage. A give-up means a production needs left-factoring; the number
to change is in cst.rs, not here.
Sourcepub const fn exactly(serves: u64) -> Self
pub const fn exactly(serves: u64) -> Self
An explicit allowance, for a caller with its own responsiveness requirement — a language server spends less than a compiler, because a human is waiting on every keystroke.