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}