Skip to main content

raf_source/
budget.rs

1// SPDX-FileCopyrightText: 2026 Blackcat InformaticsĀ® Inc. <paudley@blackcatinformatics.ca>
2// SPDX-License-Identifier: MIT OR Apache-2.0 OR MulanPSL-2.0
3
4//! The budgets of a load, in one table: the recursion budgets of the pre-scan,
5//! the bounds of the module walk and of discovery, and the work and memory
6//! bounds of one load.
7
8use std::fmt;
9
10/// A budget of a load.
11///
12/// The first six bound shapes that make `syn` recurse and are enforced by the
13/// pre-scan before a file is parsed. The others bound the module walk,
14/// discovery, the tokens of one file, the bytes one load reads and keeps and
15/// the steps of glob table work one load makes. The limits live in one table,
16/// [`Budget::limit`], which the code and the documentation share. The token
17/// budget, the four byte budgets and the work budget are defaults that
18/// [`LoadOptions`](crate::LoadOptions) can change.
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
20#[non_exhaustive]
21pub enum Budget {
22    /// Open delimiters (`(`, `[`, `{`) nested at one point.
23    Delimiters,
24    /// Open `<` brackets nested in one delimiter level.
25    Angles,
26    /// Consecutive prefix operators (`!`, `-`, `*`, `&`, `&&`).
27    PrefixOperators,
28    /// Back-to-back closure heads (`||` or `|...|` with no body between).
29    ClosureBars,
30    /// Chained `else if` links.
31    ElseIf,
32    /// The nesting that the parser builds by recursion, counted additively
33    /// over every open delimiter level: the counted tokens of each open level
34    /// since its count last returned to zero, plus one for each open
35    /// delimiter. Parsing a file, reading its facts and dropping its syntax
36    /// tree take at most [`RECURSION_UNIT_BYTES`] of the parse stack for each
37    /// unit, so the limit keeps them within half of
38    /// [`PARSE_STACK_BYTES`](crate::PARSE_STACK_BYTES).
39    Recursion,
40    /// Modules nested along one path from a target root, files and inline
41    /// modules together. Unlike the others it is counted by the module walk
42    /// and not by the pre-scan.
43    ModuleDepth,
44    /// Module paths recorded in one load: every arrival of the module walk at
45    /// a file, counted over all targets. Counted by the module walk.
46    ModulePaths,
47    /// Directories nested below a root, counted by package discovery and by
48    /// the expansion of `workspace.members` patterns.
49    DirectoryDepth,
50    /// Guard token units of one file, counted by the pre-scan. A doc comment
51    /// counts as its attribute. A numeric run may fuse up to three native leaves;
52    /// [`PreparedSource::native_token_bound`](crate::PreparedSource::native_token_bound)
53    /// gives a separate checked native ceiling. This bounds token structure,
54    /// not the complete native parser heap or work. [`PARSE_BYTES_PER_TOKEN`]
55    /// is an empirical reference for the measured statement shape.
56    FileTokens,
57    /// Bytes read in one load: every source file and manifest.
58    TotalBytes,
59    /// Bytes the symbol index keeps: every item record and the index entries
60    /// built for each module path, each shared string once, and cumulative
61    /// native load traversal spills, and immutable derived glob reach/broken
62    /// facts with their shared allocation header.
63    ItemBytes,
64    /// Bytes of the facts read from the files of one load, counted on the
65    /// parse thread as they are built.
66    FactBytes,
67    /// Bytes of the glob scope tables held at once: what each module exports
68    /// to glob imports, kept once for every class of importers that see the
69    /// same of it and shared by them, the glob imports that read each table,
70    /// and the changes waiting to be passed on as the tables grow. Also
71    /// bounds retained named-import reads, queues, subscriptions and graph
72    /// scratch used to settle imports, including loads without globs, scratch
73    /// for impl self-type and trait-path traversal and derived glob-fact
74    /// construction, and
75    /// the live scratch of selected-route proofs in a query after the load.
76    GlobBytes,
77    /// Steps of glob table work in one load, counted as they are made and
78    /// never given back: each queue, subscription and import-graph step,
79    /// derived glob-fact construction and traversal, admitted buffer growth,
80    /// each retained-read traversal, impl self-type and trait-path traversal
81    /// and its retained path segments and bytes, each glob read listed and each name gathered when a
82    /// view is built, each name a new reader is given, each reader a change is
83    /// passed on to, each glob read read again when what a module's globs
84    /// bring in under a name is read again, each step of the search for the modules that hold an item
85    /// apart from a reading module, and each glob read a lookup of what the
86    /// globs of a module bring in looks at, with each view looked at to find
87    /// those reads, charged at the next checkpoint of the load. These are the
88    /// steps whose number grows faster than the bytes of the tables on some
89    /// shapes of globs, so the budget bounds the work of settling them
90    /// whatever their bytes. A query after the load counts the steps of its
91    /// own lookups and selected-route determinacy proofs against the same budget, with the limit
92    /// [`LoadOptions::max_query_work`](crate::LoadOptions::max_query_work).
93    Work,
94}
95
96/// One mebibyte.
97const MIB: usize = 1024 * 1024;
98
99/// The limit of each budget, indexed by the budget's position.
100const BUDGETS: [(Budget, usize); 15] = [
101    (Budget::Delimiters, 128),
102    (Budget::Angles, 64),
103    (Budget::PrefixOperators, 256),
104    (Budget::ClosureBars, 128),
105    (Budget::ElseIf, 256),
106    (Budget::Recursion, RECURSION),
107    (Budget::ModuleDepth, 128),
108    (Budget::ModulePaths, 262_144),
109    (Budget::DirectoryDepth, 128),
110    (Budget::FileTokens, FILE_TOKENS),
111    (Budget::TotalBytes, 256 * MIB),
112    (Budget::ItemBytes, 512 * MIB),
113    (Budget::FactBytes, 256 * MIB),
114    (Budget::GlobBytes, 512 * MIB),
115    (Budget::Work, WORK),
116];
117
118/// Empirical peak bytes per token for the measured empty-statement shape.
119///
120/// Measured on one function body
121/// of 2^k + 1 empty statements, whose list of statements doubles its storage
122/// for the last one: 1,602 bytes per token at every k from 14 to 20, counting
123/// a grown block as held beside the block it replaces until that is freed.
124/// This reference adds about 4% to that measurement. It is not a hard bound
125/// for arbitrary accepted Rust: identifier, literal and documentation payloads,
126/// native source maps and other transient storage also depend on source bytes.
127/// Token count alone does not bound native parsing work, either. The figure
128/// spans the whole parse step, lexing included; the syntax tree alone is
129/// bounded per node and per byte by [`SYNTAX_BYTES_PER_NODE`].
130pub const PARSE_BYTES_PER_TOKEN: usize = 1664;
131
132/// Measured peak bytes of syntax-tree storage per native token-tree node.
133///
134/// The syntax parse of a function body of 2^k + 1 empty statements, the worst
135/// shape of the reference table, peaks at a measured maximum of 939.98 bytes per
136/// node, at k = 17 (131,077 nodes); k = 14 gives 939.8 and k = 10 gives 937.5.
137/// The residual is taken beyond the measured per-byte rate of 4.000389 bytes per
138/// source byte, that is `(peak - 4.000389 * text_bytes) / nodes`, with the
139/// counting allocator, which counts a reallocation as growth in place, so the
140/// peak is twice the final capacity of the statement list and the replaced block
141/// is not counted beside the new one. The constant is 978: a margin of 38.02
142/// bytes per node, 4.04% above the maximum. It is measured over a closed table
143/// of shapes, not proven for arbitrary accepted Rust. A tree whose retained-tree
144/// estimate ([`syntax_held`](crate::syntax_held)) exceeds the bound is detected
145/// after the fact and charged; the estimate misses vector capacity, transient
146/// parse storage and the heap behind unlisted types. See
147/// [`SyntaxBound`](crate::SyntaxBound).
148pub const SYNTAX_BYTES_PER_NODE: usize = 978;
149
150/// Numerator of the bytes of syntax-tree storage charged per source byte.
151///
152/// The per-byte charge is the ratio `SYNTAX_BYTES_PER_BYTE_NUM /
153/// SYNTAX_BYTES_PER_BYTE_DEN`, 417/100 = 4.17, taken as `ceil(text_bytes * num /
154/// den)` in checked integer arithmetic. A single 1 MiB documentation comment
155/// peaks at a measured maximum of 4.000389 bytes per source byte (4,194,764 bytes
156/// over 1,048,589), the most of the byte-dense shapes (string literals 3, an
157/// identifier 2). The ratio 4.17 is 0.1696 bytes per byte, 4.24%, above that
158/// maximum, the same order as the margin of [`SYNTAX_BYTES_PER_NODE`].
159pub const SYNTAX_BYTES_PER_BYTE_NUM: usize = 417;
160
161/// Denominator of the per-byte charge; see [`SYNTAX_BYTES_PER_BYTE_NUM`].
162pub const SYNTAX_BYTES_PER_BYTE_DEN: usize = 100;
163
164/// The most stack of the parse thread that one unit of [`Budget::Recursion`]
165/// takes in a debug build, rounded up: parsing, reading the facts and dropping
166/// the syntax tree, measured on the costliest counted shape, generic arguments
167/// nested in a type (`A<A<...>>`), at 16,481 bytes a unit.
168pub const RECURSION_UNIT_BYTES: usize = 17 * 1024;
169
170/// The recursion limit, 1927: half of the parse stack over the cost of one
171/// unit.
172const RECURSION: usize = crate::parse::PARSE_STACK_BYTES / (2 * RECURSION_UNIT_BYTES);
173
174/// The default token limit of one file. It admits the largest generated source
175/// files of real crates (a time-zone table of 1.5 million tokens); a caller on
176/// a smaller host lowers it through [`LoadOptions`](crate::LoadOptions).
177/// This limits token structure without establishing a native parser heap bound.
178const FILE_TOKENS: usize = 2_000_000;
179
180/// The default limit of import settling and derived graph work in one load,
181/// 2^31 steps, and of lookup and proof work in one query after it. The constant
182/// is the same on every target; the counted operations are stated by
183/// [`Budget::Work`].
184const WORK: usize = 1 << 31;
185
186impl Budget {
187    /// Every budget, in table order.
188    pub const ALL: [Budget; 15] = [
189        BUDGETS[0].0,
190        BUDGETS[1].0,
191        BUDGETS[2].0,
192        BUDGETS[3].0,
193        BUDGETS[4].0,
194        BUDGETS[5].0,
195        BUDGETS[6].0,
196        BUDGETS[7].0,
197        BUDGETS[8].0,
198        BUDGETS[9].0,
199        BUDGETS[10].0,
200        BUDGETS[11].0,
201        BUDGETS[12].0,
202        BUDGETS[13].0,
203        BUDGETS[14].0,
204    ];
205
206    /// The most the budget allows; one more is refused. For the token budget,
207    /// the four byte budgets and the work budget this is the default of the
208    /// matching [`LoadOptions`](crate::LoadOptions) field.
209    #[must_use]
210    pub const fn limit(self) -> usize {
211        BUDGETS[self as usize].1
212    }
213
214    /// The budget's name as it appears in messages.
215    #[must_use]
216    pub const fn name(self) -> &'static str {
217        match self {
218            Self::Delimiters => "delimiter nesting",
219            Self::Angles => "nested `<`",
220            Self::PrefixOperators => "prefix operator run",
221            Self::ClosureBars => "closure bar chain",
222            Self::ElseIf => "`else if` chain",
223            Self::Recursion => "parser recursion",
224            Self::ModuleDepth => "module nesting",
225            Self::ModulePaths => "module paths",
226            Self::DirectoryDepth => "directory nesting",
227            Self::FileTokens => "tokens in one file",
228            Self::TotalBytes => "bytes read in one load",
229            Self::ItemBytes => "bytes of index records",
230            Self::FactBytes => "bytes of file facts",
231            Self::GlobBytes => "bytes of glob tables",
232            Self::Work => "glob table work steps",
233        }
234    }
235}
236
237impl fmt::Display for Budget {
238    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
239        f.write_str(self.name())
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use super::*;
246
247    #[test]
248    fn the_table_is_indexed_by_each_budgets_position() {
249        for (index, (budget, _)) in BUDGETS.iter().enumerate() {
250            assert_eq!(*budget as usize, index);
251        }
252        assert_eq!(Budget::ALL.len(), BUDGETS.len());
253        assert_eq!(Budget::Delimiters.limit(), 128);
254        assert_eq!(Budget::Angles.limit(), 64);
255        assert_eq!(Budget::PrefixOperators.limit(), 256);
256        assert_eq!(Budget::ClosureBars.limit(), 128);
257        assert_eq!(Budget::ElseIf.limit(), 256);
258        assert_eq!(Budget::Recursion.limit(), 1927);
259        assert_eq!(
260            RECURSION,
261            crate::PARSE_STACK_BYTES / (2 * RECURSION_UNIT_BYTES)
262        );
263        assert_eq!(Budget::ModuleDepth.limit(), 128);
264        assert_eq!(Budget::ModulePaths.limit(), 262_144);
265        assert_eq!(Budget::DirectoryDepth.limit(), 128);
266        assert_eq!(Budget::FileTokens.limit(), FILE_TOKENS);
267        assert_eq!(Budget::TotalBytes.limit(), 256 * MIB);
268        assert_eq!(Budget::ItemBytes.limit(), 512 * MIB);
269        assert_eq!(Budget::FactBytes.limit(), 256 * MIB);
270        assert_eq!(Budget::GlobBytes.limit(), 512 * MIB);
271        assert_eq!(Budget::Work.limit(), 1 << 31);
272        assert_eq!(Budget::Work.name(), "glob table work steps");
273        assert_eq!(Budget::ALL.last(), Some(&Budget::Work));
274    }
275}