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 is a plain unfactored common prefix, and it is worth naming
precisely so that nobody hunts for it again: Expr::LetIn and
Expr::LetPatternIn both begin let ‹target› = ‹expr› in ‹body›, so a
failure in the innermost body is 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. Deleting
LetPatternIn (which is shadowed for a bare-variable target, as its own
doc comment says) collapses the same measurements to 374, 677, 980, 1,283,
1,586: linear, 17 serves per atom.
Factoring the two into one variant is the real repair, and it is a CST
change that reaches elaborate.rs, so it is deliberately not done here.
Nor would it be the end of it — the 0.1 grammar blows up the same way on
truncated prefixes of the bundled std-ja.satyh, ×5 per 200 bytes, from a
different prefix. 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, and it is what
lets a broken chain of fifteen lets still reach a real verdict —
past which, the exponential above being what it is, each further
doubling of the floor buys exactly one more let. That is the argument
against simply raising it: the budget cannot buy diagnostic quality
here, only bound the damage.
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.