miden_assembly_syntax/ast/item/resolver/
symbol_table.rs

1use alloc::{collections::BTreeMap, sync::Arc, vec::Vec};
2
3use miden_debug_types::{SourceManager, SourceSpan, Span, Spanned};
4
5use super::{SymbolResolution, SymbolResolutionError};
6use crate::ast::{Ident, Import, ItemIndex};
7
8/// This trait abstracts over any type which acts as a symbol table, e.g. a [crate::ast::Module].
9///
10/// Resolver construction uses [Self::checked_symbols], which must either return the full symbol
11/// set or a structured error.
12pub trait SymbolTable {
13    /// The concrete iterator type for the container.
14    type SymbolIter: Iterator<Item = LocalSymbol>;
15
16    /// Get an iterator over the symbols in this symbol table, using the provided [SourceManager]
17    /// to emit errors for symbols which are invalid/unresolvable.
18    fn symbols(&self, source_manager: Arc<dyn SourceManager>) -> Self::SymbolIter;
19
20    /// Get an iterator over the symbols in this symbol table, returning a structured error if the
21    /// full symbol set cannot be represented exactly.
22    ///
23    /// Override this when exact resolver construction needs validation, such as rejecting oversized
24    /// symbol sets.
25    fn checked_symbols(
26        &self,
27        source_manager: Arc<dyn SourceManager>,
28    ) -> Result<Self::SymbolIter, SymbolResolutionError> {
29        Ok(self.symbols(source_manager))
30    }
31}
32
33impl SymbolTable for &crate::module::ModuleInfo {
34    type SymbolIter = alloc::vec::IntoIter<LocalSymbol>;
35
36    fn symbols(&self, _source_manager: Arc<dyn SourceManager>) -> Self::SymbolIter {
37        let mut items = Vec::with_capacity(self.raw_items().len());
38
39        for (i, item) in self.raw_items().iter().enumerate() {
40            let name = item.name().clone();
41            let span = name.span();
42            items.push(LocalSymbol::Item {
43                name,
44                resolved: SymbolResolution::Local(Span::new(span, ItemIndex::new(i))),
45            });
46        }
47
48        items.into_iter()
49    }
50
51    fn checked_symbols(
52        &self,
53        source_manager: Arc<dyn SourceManager>,
54    ) -> Result<Self::SymbolIter, SymbolResolutionError> {
55        if self.raw_items().len() > ItemIndex::MAX_ITEMS {
56            Err(SymbolResolutionError::too_many_items_in_module(
57                SourceSpan::UNKNOWN,
58                &*source_manager,
59            ))
60        } else {
61            Ok(self.symbols(source_manager))
62        }
63    }
64}
65
66impl SymbolTable for &crate::ast::Module {
67    type SymbolIter = alloc::vec::IntoIter<LocalSymbol>;
68
69    fn symbols(&self, _source_manager: Arc<dyn SourceManager>) -> Self::SymbolIter {
70        let mut items = Vec::with_capacity(self.items.len() + self.imports.len());
71
72        for (i, item) in self.items.iter().enumerate() {
73            let id = ItemIndex::new(i);
74            let name = item.name().clone();
75            let span = name.span();
76            let name = name.into_inner();
77
78            items.push(LocalSymbol::Item {
79                name: Ident::from_raw_parts(Span::new(span, name)),
80                resolved: SymbolResolution::Local(Span::new(span, id)),
81            });
82        }
83
84        items.extend(self.imports.iter().filter_map(|import| {
85            let Import::Item(item) = import else {
86                return None;
87            };
88            let local_name = import.local_name().clone();
89            let span = local_name.span();
90            let name = Span::new(span, local_name.into_inner());
91            Some(LocalSymbol::Import {
92                name,
93                resolution: Ok(SymbolResolution::External(item.target_path())),
94            })
95        }));
96
97        items.into_iter()
98    }
99
100    fn checked_symbols(
101        &self,
102        source_manager: Arc<dyn SourceManager>,
103    ) -> Result<Self::SymbolIter, SymbolResolutionError> {
104        if self.items.len() + self.imports.len() > ItemIndex::MAX_ITEMS {
105            Err(SymbolResolutionError::too_many_items_in_module(self.span(), &*source_manager))
106        } else {
107            Ok(self.symbols(source_manager))
108        }
109    }
110}
111
112/// Represents a symbol within the context of a single module
113#[derive(Debug)]
114pub enum LocalSymbol {
115    /// This symbol is a declaration, with the given resolution.
116    Item { name: Ident, resolved: SymbolResolution },
117    /// This symbol is an import of an externally-defined item.
118    Import {
119        name: Span<Arc<str>>,
120        resolution: Result<SymbolResolution, SymbolResolutionError>,
121    },
122}
123
124impl LocalSymbol {
125    pub fn name(&self) -> &str {
126        match self {
127            Self::Item { name, .. } => name.as_str(),
128            Self::Import { name, .. } => name,
129        }
130    }
131}
132
133/// The common local symbol table/registry implementation
134pub(super) struct LocalSymbolTable {
135    source_manager: Arc<dyn SourceManager>,
136    symbols: BTreeMap<Arc<str>, ItemIndex>,
137    items: Vec<LocalSymbol>,
138}
139
140impl core::ops::Index<ItemIndex> for LocalSymbolTable {
141    type Output = LocalSymbol;
142
143    #[inline(always)]
144    fn index(&self, index: ItemIndex) -> &Self::Output {
145        &self.items[index.as_usize()]
146    }
147}
148
149impl LocalSymbolTable {
150    fn build<I>(iter: I, source_manager: Arc<dyn SourceManager>) -> Self
151    where
152        I: Iterator<Item = LocalSymbol>,
153    {
154        let mut symbols = BTreeMap::default();
155        let mut items = Vec::with_capacity(16);
156
157        for (i, symbol) in iter.enumerate() {
158            let id = ItemIndex::try_new(i)
159                .expect("symbol iterators used by LocalSymbolTable::build must be pre-validated");
160            let symbol = match symbol {
161                LocalSymbol::Item {
162                    name,
163                    resolved: SymbolResolution::Local(local),
164                } => LocalSymbol::Item {
165                    name,
166                    resolved: SymbolResolution::Local(Span::new(local.span(), id)),
167                },
168                symbol => symbol,
169            };
170            log::debug!(target: "symbol-table::new", "registering {} symbol: {}", match symbol {
171                LocalSymbol::Item { .. } => "local",
172                LocalSymbol::Import { .. } => "imported",
173            }, symbol.name());
174            let name = match &symbol {
175                LocalSymbol::Item { name, .. } => name.clone().into_inner(),
176                LocalSymbol::Import { name, .. } => name.clone().into_inner(),
177            };
178
179            if let Some(prev) = symbols.get(&name).copied() {
180                debug_assert!(
181                    false,
182                    "duplicate symbol '{name}' reached local resolver construction (previous={prev:?}, current={id:?})"
183                );
184            } else {
185                symbols.insert(name.clone(), id);
186            }
187            items.push(symbol);
188        }
189
190        Self { source_manager, symbols, items }
191    }
192
193    pub fn new<S>(
194        iter: S,
195        source_manager: Arc<dyn SourceManager>,
196    ) -> Result<Self, SymbolResolutionError>
197    where
198        S: SymbolTable,
199    {
200        let symbols = iter.checked_symbols(source_manager.clone())?;
201        Ok(Self::build(symbols, source_manager))
202    }
203}
204
205impl LocalSymbolTable {
206    /// Get the symbol `name` from this table, if present.
207    ///
208    /// Returns `Ok(None)` if the symbol is undefined in this table.
209    ///
210    /// Returns `Ok(Some)` if the symbol is defined, and we were able to resolve it to either a
211    /// local or external item without encountering any issues.
212    ///
213    /// Returns `Err` if the symbol cannot possibly be resolved, e.g. the expanded path refers to
214    /// a child of an item that cannot have children, such as a procedure.
215    pub fn get(&self, name: Span<&str>) -> Result<SymbolResolution, SymbolResolutionError> {
216        log::debug!(target: "symbol-table", "attempting to resolve '{name}'");
217        let (span, name) = name.into_parts();
218        let Some(item) = self.symbols.get(name).copied() else {
219            return Err(SymbolResolutionError::undefined(span, &self.source_manager));
220        };
221        match &self.items[item.as_usize()] {
222            LocalSymbol::Item { resolved, .. } => {
223                log::debug!(target: "symbol-table", "resolved '{name}' to {resolved:?}");
224                Ok(resolved.clone())
225            },
226            LocalSymbol::Import { name, resolution } => {
227                log::debug!(target: "symbol-table", "'{name}' refers to an import");
228                match resolution {
229                    Ok(resolved) => {
230                        log::debug!(target: "symbol-table", "resolved '{name}' to {resolved:?}");
231                        Ok(resolved.clone())
232                    },
233                    Err(err) => {
234                        log::error!(target: "symbol-table", "resolution of '{name}' failed: {err}");
235                        Err(err.clone())
236                    },
237                }
238            },
239        }
240    }
241}
242
243#[cfg(test)]
244mod tests {
245    use alloc::sync::Arc;
246
247    use miden_debug_types::DefaultSourceManager;
248
249    use super::*;
250    use crate::Path;
251
252    #[test]
253    fn checked_symbols_rejects_oversized_module() {
254        let source_manager: Arc<dyn SourceManager> = Arc::new(DefaultSourceManager::default());
255        let mut module =
256            crate::ast::Module::new(crate::ast::ModuleKind::Library, Path::new("::m::huge"));
257
258        for i in 0..=ItemIndex::MAX_ITEMS {
259            module.items.push(crate::ast::Item::Constant(crate::ast::Constant::new(
260                SourceSpan::UNKNOWN,
261                crate::ast::Visibility::Private,
262                Ident::new(format!("A{i}")).expect("valid identifier"),
263                crate::ast::ConstantExpr::Int(Span::unknown(crate::parser::IntValue::from(0u8))),
264            )));
265        }
266
267        let result = (&module).checked_symbols(source_manager);
268
269        assert!(matches!(result, Err(SymbolResolutionError::TooManyItemsInModule { .. })));
270    }
271
272    #[test]
273    fn checked_symbols_guard_custom_symbol_table_exact() {
274        struct ExactTooManySymbols;
275
276        impl SymbolTable for ExactTooManySymbols {
277            type SymbolIter = alloc::vec::IntoIter<LocalSymbol>;
278
279            fn symbols(&self, _source_manager: Arc<dyn SourceManager>) -> Self::SymbolIter {
280                panic!("exact construction must not request unchecked symbols")
281            }
282
283            fn checked_symbols(
284                &self,
285                source_manager: Arc<dyn SourceManager>,
286            ) -> Result<Self::SymbolIter, SymbolResolutionError> {
287                Err(SymbolResolutionError::too_many_items_in_module(
288                    SourceSpan::UNKNOWN,
289                    &*source_manager,
290                ))
291            }
292        }
293
294        let source_manager: Arc<dyn SourceManager> = Arc::new(DefaultSourceManager::default());
295        let result = LocalSymbolTable::new(ExactTooManySymbols, source_manager);
296
297        assert!(matches!(result, Err(SymbolResolutionError::TooManyItemsInModule { .. })));
298    }
299
300    #[cfg(test)]
301    struct DuplicateSymbolsForInvariantTest;
302
303    #[cfg(test)]
304    impl SymbolTable for DuplicateSymbolsForInvariantTest {
305        type SymbolIter = alloc::vec::IntoIter<LocalSymbol>;
306
307        fn symbols(&self, _source_manager: Arc<dyn SourceManager>) -> Self::SymbolIter {
308            let first = LocalSymbol::Item {
309                name: Ident::new("dup").expect("valid identifier"),
310                resolved: SymbolResolution::Local(Span::unknown(ItemIndex::new(0))),
311            };
312            let second = LocalSymbol::Item {
313                name: Ident::new("dup").expect("valid identifier"),
314                resolved: SymbolResolution::Local(Span::unknown(ItemIndex::new(1))),
315            };
316            alloc::vec![first, second].into_iter()
317        }
318    }
319
320    #[cfg(debug_assertions)]
321    #[test]
322    #[should_panic(expected = "duplicate symbol 'dup' reached local resolver construction")]
323    fn local_symbol_table_rejects_duplicate_symbols() {
324        let source_manager: Arc<dyn SourceManager> = Arc::new(DefaultSourceManager::default());
325        let _table = LocalSymbolTable::new(DuplicateSymbolsForInvariantTest, source_manager);
326    }
327
328    #[test]
329    fn local_symbol_table_duplicate_symbols_have_explicit_behavior() {
330        use std::panic::{AssertUnwindSafe, catch_unwind};
331
332        let source_manager: Arc<dyn SourceManager> = Arc::new(DefaultSourceManager::default());
333        let result = catch_unwind(AssertUnwindSafe(|| {
334            LocalSymbolTable::new(DuplicateSymbolsForInvariantTest, source_manager)
335        }));
336
337        if cfg!(debug_assertions) {
338            assert!(
339                result.is_err(),
340                "debug builds should panic when duplicates reach local resolver construction"
341            );
342        } else {
343            let table = result
344                .expect("release builds should not panic on duplicate symbols")
345                .expect("release builds should still construct a table");
346            let resolved = table
347                .get(Span::unknown("dup"))
348                .expect("release behavior should keep a deterministic symbol mapping");
349            match resolved {
350                SymbolResolution::Local(id) => assert_eq!(id.into_inner(), ItemIndex::new(0)),
351                other => panic!("expected local symbol resolution, got {other:?}"),
352            }
353        }
354    }
355}
miden_assembly_syntax/ast/item/resolver/symbol_table.rs

miden_assembly_syntax/ast/item/resolver/
symbol_table.rs
