Skip to main content

raf_source/
syntax_storage.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 storage of a parsed syntax tree: a bound computed before the parse and a
5//! retained-tree estimate read from the tree after it.
6
7use std::fmt::{self, Write as _};
8
9use syn::visit::{self, Visit};
10
11use crate::budget::{SYNTAX_BYTES_PER_BYTE_DEN, SYNTAX_BYTES_PER_BYTE_NUM, SYNTAX_BYTES_PER_NODE};
12
13/// The per-node and per-byte terms of a syntax-tree storage bound.
14///
15/// The bound is `nodes * per_node + ceil(text_bytes * byte_num / byte_den)`, where `nodes` is the
16/// exact native token-tree node count of the lexed stream and `text_bytes` is
17/// the source length. It is computed before the parser runs, so a caller can
18/// admit it first. The production terms are measured, not proven; see
19/// [`SYNTAX_BYTES_PER_NODE`](crate::SYNTAX_BYTES_PER_NODE).
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub struct SyntaxBound {
22    /// Bytes of peak parse storage per native token-tree node.
23    pub per_node: usize,
24    /// Numerator of the bytes of peak parse storage per source byte.
25    pub byte_num: usize,
26    /// Denominator of the bytes of peak parse storage per source byte.
27    pub byte_den: usize,
28}
29
30impl SyntaxBound {
31    /// The measured production terms.
32    pub const MEASURED: Self = Self {
33        per_node: SYNTAX_BYTES_PER_NODE,
34        byte_num: SYNTAX_BYTES_PER_BYTE_NUM,
35        byte_den: SYNTAX_BYTES_PER_BYTE_DEN,
36    };
37
38    /// The bound for `nodes` native nodes over `text_bytes` source bytes, or
39    /// `None` when any step overflows `usize` or the denominator is zero.
40    #[must_use]
41    pub const fn bytes(self, nodes: usize, text_bytes: usize) -> Option<usize> {
42        let Some(by_node) = nodes.checked_mul(self.per_node) else {
43            return None;
44        };
45        let Some(scaled) = text_bytes.checked_mul(self.byte_num) else {
46            return None;
47        };
48        let Some(rounded) = scaled.checked_add(self.byte_den.saturating_sub(1)) else {
49            return None;
50        };
51        let Some(by_byte) = rounded.checked_div(self.byte_den) else {
52            return None;
53        };
54        by_node.checked_add(by_byte)
55    }
56}
57
58/// The node enums the retained-tree estimate counts, each with its size and the
59/// fewest native token-tree nodes that one element of the enum takes to parse
60/// (a statement or expression takes one, an item or a macro member three, a
61/// match arm four).
62///
63/// One list serves the walk and the structural size check of the bound.
64pub const SYNTAX_NODE_SIZES: [(&str, usize, usize); 9] = [
65    ("Expr", size_of::<syn::Expr>(), 1),
66    ("Stmt", size_of::<syn::Stmt>(), 1),
67    ("Item", size_of::<syn::Item>(), 3),
68    ("Pat", size_of::<syn::Pat>(), 1),
69    ("Type", size_of::<syn::Type>(), 1),
70    ("ImplItem", size_of::<syn::ImplItem>(), 3),
71    ("TraitItem", size_of::<syn::TraitItem>(), 3),
72    ("ForeignItem", size_of::<syn::ForeignItem>(), 3),
73    ("Arm", size_of::<syn::Arm>(), 4),
74];
75
76const EXPR: usize = 0;
77const STMT: usize = 1;
78const ITEM: usize = 2;
79const PAT: usize = 3;
80const TYPE: usize = 4;
81const IMPL_ITEM: usize = 5;
82const TRAIT_ITEM: usize = 6;
83const FOREIGN_ITEM: usize = 7;
84const ARM: usize = 8;
85
86/// A retained-tree estimate read from a parsed tree.
87///
88/// It sums `size_of` of each visited node enum plus the spelling bytes of
89/// identifiers and of string, byte-string, integer and float literals. It does
90/// not see vector capacity or growth slack, transient parse storage, or the heap
91/// behind types outside [`SYNTAX_NODE_SIZES`]; it counts a node held inline in
92/// another twice. It is an estimate for detecting a wrong bound, not a heap
93/// account.
94#[derive(Clone, Copy, Debug, PartialEq, Eq)]
95pub struct SyntaxHeld {
96    bytes: usize,
97    counts: [usize; 9],
98}
99
100impl SyntaxHeld {
101    /// Estimated retained bytes.
102    #[must_use]
103    pub const fn bytes(&self) -> usize {
104        self.bytes
105    }
106
107    /// The most numerous visited node kind, the larger type on a tie, and its
108    /// count. An empty tree names `Item` with zero.
109    #[must_use]
110    pub fn dominant(&self) -> (&'static str, usize) {
111        let mut best = ITEM;
112        for index in 0..self.counts.len() {
113            let better = (self.counts[index], SYNTAX_NODE_SIZES[index].1)
114                > (self.counts[best], SYNTAX_NODE_SIZES[best].1);
115            if better {
116                best = index;
117            }
118        }
119        (SYNTAX_NODE_SIZES[best].0, self.counts[best])
120    }
121}
122
123/// Read the retained-tree estimate of `tree`. The walk allocates nothing, apart
124/// from one transient copy of each counted literal's native spelling, which
125/// `syn` hands out only by value and which dies before the next node.
126#[must_use]
127pub fn syntax_held(tree: &syn::File) -> SyntaxHeld {
128    let mut walk = Walk {
129        held: SyntaxHeld {
130            bytes: 0,
131            counts: [0; 9],
132        },
133    };
134    walk.visit_file(tree);
135    walk.held
136}
137
138/// Counts the bytes of what is written, retaining none of it.
139struct Length(usize);
140
141impl fmt::Write for Length {
142    fn write_str(&mut self, text: &str) -> fmt::Result {
143        self.0 = self.0.saturating_add(text.len());
144        Ok(())
145    }
146}
147
148struct Walk {
149    held: SyntaxHeld,
150}
151
152impl Walk {
153    fn node(&mut self, kind: usize) {
154        self.held.bytes = self.held.bytes.saturating_add(SYNTAX_NODE_SIZES[kind].1);
155        self.held.counts[kind] = self.held.counts[kind].saturating_add(1);
156    }
157
158    fn spelling(&mut self, bytes: usize) {
159        self.held.bytes = self.held.bytes.saturating_add(bytes);
160    }
161
162    fn token(&mut self, token: &impl fmt::Display) {
163        let mut length = Length(0);
164        // Writing to a counting sink cannot fail.
165        let _ = write!(length, "{token}");
166        self.spelling(length.0);
167    }
168}
169
170impl<'ast> Visit<'ast> for Walk {
171    fn visit_expr(&mut self, node: &'ast syn::Expr) {
172        self.node(EXPR);
173        visit::visit_expr(self, node);
174    }
175    fn visit_stmt(&mut self, node: &'ast syn::Stmt) {
176        self.node(STMT);
177        visit::visit_stmt(self, node);
178    }
179    fn visit_item(&mut self, node: &'ast syn::Item) {
180        self.node(ITEM);
181        visit::visit_item(self, node);
182    }
183    fn visit_pat(&mut self, node: &'ast syn::Pat) {
184        self.node(PAT);
185        visit::visit_pat(self, node);
186    }
187    fn visit_type(&mut self, node: &'ast syn::Type) {
188        self.node(TYPE);
189        visit::visit_type(self, node);
190    }
191    fn visit_impl_item(&mut self, node: &'ast syn::ImplItem) {
192        self.node(IMPL_ITEM);
193        visit::visit_impl_item(self, node);
194    }
195    fn visit_trait_item(&mut self, node: &'ast syn::TraitItem) {
196        self.node(TRAIT_ITEM);
197        visit::visit_trait_item(self, node);
198    }
199    fn visit_foreign_item(&mut self, node: &'ast syn::ForeignItem) {
200        self.node(FOREIGN_ITEM);
201        visit::visit_foreign_item(self, node);
202    }
203    fn visit_arm(&mut self, node: &'ast syn::Arm) {
204        self.node(ARM);
205        visit::visit_arm(self, node);
206    }
207    fn visit_ident(&mut self, node: &'ast proc_macro2::Ident) {
208        self.token(node);
209    }
210    fn visit_lit(&mut self, node: &'ast syn::Lit) {
211        match node {
212            syn::Lit::Str(literal) => self.token(&literal.token()),
213            syn::Lit::ByteStr(literal) => self.token(&literal.token()),
214            syn::Lit::Int(literal) => self.token(&literal.token()),
215            syn::Lit::Float(literal) => self.token(&literal.token()),
216            _ => {}
217        }
218    }
219}