miden_assembly_syntax/ast/item/
index.rs

1/// Represents the index of an item within its respective storage vector in some module
2#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
3#[repr(transparent)]
4pub struct ItemIndex(u16);
5
6#[derive(Debug, Copy, Clone, PartialEq, Eq, thiserror::Error)]
7#[error("invalid item index: too many items")]
8pub struct ItemIndexError {
9    attempted: usize,
10}
11
12impl ItemIndex {
13    pub const MAX_ITEMS: usize = u16::MAX as usize + 1;
14
15    pub fn new(id: usize) -> Self {
16        Self::try_new(id).expect("invalid item index: too many items")
17    }
18
19    pub fn try_new(id: usize) -> Result<Self, ItemIndexError> {
20        let raw = id.try_into().map_err(|_| ItemIndexError { attempted: id })?;
21        Ok(Self(raw))
22    }
23
24    #[inline(always)]
25    pub const fn const_new(id: u16) -> Self {
26        Self(id)
27    }
28
29    /// Get the raw index value of this item
30    #[inline(always)]
31    pub const fn as_usize(&self) -> usize {
32        self.0 as usize
33    }
34}
35
36impl core::fmt::Display for ItemIndex {
37    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
38        write!(f, "{}", &self.as_usize())
39    }
40}
41
42/// Uniquely identifies an item in a set of [crate::ast::Module]
43///
44/// A [GlobalItemIndex] is assigned to an item when it is added to the linker's module
45/// graph. The index uniquely identifies that item in the graph, and provides a unique,
46/// copyable, machine-word sized handle that can be trivially stored, passed around, and later used
47/// to perform constant-complexity operations against that item.
48///
49/// <div class="warning">
50/// As a result of this being just an index into a specific instance of a [super::ModuleGraph],
51/// it does not provide any guarantees about uniqueness or stability when the same module is stored
52/// in multiple graphs - each graph may assign it a unique index. You must ensure that you do not
53/// store these indices and attempt to use them with just any module graph - it is only valid with
54/// the one it was assigned from.
55/// </div>
56///
57/// In addition to the linker's module graph, these indices are also used with an instance of a
58/// `MastForestBuilder`. This is because the linker and `MastForestBuilder` instances
59/// are paired, i.e. the linker stores the syntax trees and call graph analysis for a program, while
60/// the `MastForestBuilder` caches the compiled procedures for the same program, as derived from
61/// the corresponding graph.
62///
63/// This is intended for use when we are doing global inter-procedural analysis on a (possibly
64/// growable) set of modules. It is expected that the index of a module in the set, as well as the
65/// index of an item in a module, are stable once allocated in the graph. The set of modules and
66/// items can grow, as long as growing the set only allocates unused identifiers.
67///
68/// NOTE: This struct is the same size as a u32
69#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
70pub struct GlobalItemIndex {
71    /// The index of the containing module in the global set of modules
72    pub module: ModuleIndex,
73    /// The local index of the procedure in the module
74    pub index: ItemIndex,
75}
76
77impl core::fmt::Display for GlobalItemIndex {
78    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
79        write!(f, "{}:{}", &self.module, &self.index)
80    }
81}
82
83/// A strongly-typed index into a set of [crate::ast::Module]
84#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
85#[repr(transparent)]
86pub struct ModuleIndex(u16);
87impl ModuleIndex {
88    pub fn new(index: usize) -> Self {
89        Self(index.try_into().expect("invalid module index: too many modules"))
90    }
91
92    pub const fn const_new(index: u16) -> Self {
93        Self(index)
94    }
95
96    #[inline(always)]
97    pub const fn as_usize(&self) -> usize {
98        self.0 as usize
99    }
100}
101
102impl core::ops::Add<ItemIndex> for ModuleIndex {
103    type Output = GlobalItemIndex;
104
105    fn add(self, rhs: ItemIndex) -> Self::Output {
106        GlobalItemIndex { module: self, index: rhs }
107    }
108}
109
110impl core::fmt::Display for ModuleIndex {
111    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
112        write!(f, "{}", &self.as_usize())
113    }
114}
115
116#[cfg(test)]
117mod regression_tests {
118    use std::{string::String, sync::Arc};
119
120    use miden_debug_types::{DefaultSourceManager, SourceSpan, Span};
121
122    use super::ItemIndex;
123    use crate::{
124        Parse, ParseOptions, Path,
125        ast::{
126            Constant, ConstantExpr, Export, Ident, Module, ModuleKind, SymbolResolutionError,
127            Visibility,
128        },
129        parser::IntValue,
130        sema::{LimitKind, SemanticAnalysisError, SyntaxError},
131    };
132
133    fn huge_library_masm() -> String {
134        let num_consts = usize::from(u16::MAX) + 2;
135        let mut masm = String::with_capacity(num_consts * 16);
136        for i in 0..num_consts {
137            masm.push_str("const A");
138            masm.push_str(&format!("{i}"));
139            masm.push_str(" = 0\n");
140        }
141        masm
142    }
143
144    fn oversized_module_for_resolver() -> Module {
145        let mut module = Module::new(ModuleKind::Library, Path::new("::m::huge"));
146        for i in 0..=ItemIndex::MAX_ITEMS {
147            module.items.push(Export::Constant(Constant::new(
148                SourceSpan::UNKNOWN,
149                Visibility::Private,
150                Ident::new(format!("A{i}")).expect("valid identifier"),
151                ConstantExpr::Int(Span::unknown(IntValue::from(0u8))),
152            )));
153        }
154        module
155    }
156
157    #[test]
158    fn too_many_items_in_module_is_rejected_during_analysis() {
159        let source_manager = Arc::new(DefaultSourceManager::default());
160        let err = huge_library_masm()
161            .parse_with_options(
162                source_manager,
163                ParseOptions::new(ModuleKind::Library, Path::new("::m::huge")),
164            )
165            .expect_err("expected oversized module to be rejected during analysis");
166
167        let syntax_error = err.downcast_ref::<SyntaxError>().expect("expected SyntaxError report");
168        assert!(
169            syntax_error.errors.iter().any(|error| {
170                matches!(error, SemanticAnalysisError::LimitExceeded { kind: LimitKind::Items, .. })
171            }),
172            "expected item-limit error, got {:?}",
173            syntax_error.errors
174        );
175    }
176
177    #[test]
178    fn resolving_name_in_too_large_module_returns_structured_error() {
179        let source_manager = Arc::new(DefaultSourceManager::default());
180        let module = oversized_module_for_resolver();
181        let result = module.resolve(Span::unknown("A0"), source_manager);
182
183        assert!(matches!(result, Err(SymbolResolutionError::TooManyItemsInModule { .. })));
184    }
185
186    #[test]
187    fn resolver_construction_for_too_large_module_returns_structured_error() {
188        let source_manager = Arc::new(DefaultSourceManager::default());
189        let module = oversized_module_for_resolver();
190
191        let result = module.resolver(source_manager);
192
193        assert!(matches!(result, Err(SymbolResolutionError::TooManyItemsInModule { .. })));
194    }
195}
miden_assembly_syntax/ast/item/index.rs

miden_assembly_syntax/ast/item/
index.rs
