miden_assembly/linker/resolver/
mod.rs

1mod symbol_resolver;
2
3use alloc::{collections::BTreeMap, string::ToString, sync::Arc};
4
5use miden_assembly_syntax::{
6    Report,
7    ast::{
8        self, GlobalItemIndex, Ident, ItemIndex, ModuleIndex, Path, SymbolResolution,
9        SymbolResolutionError,
10        constants::{ConstEnvironment, ConstEvalError, eval::CachedConstantValue},
11        types,
12    },
13    debuginfo::{SourceFile, SourceManager, SourceSpan, Span, Spanned},
14    diagnostics::{LabeledSpan, RelatedError, Severity, diagnostic},
15    library::ItemInfo,
16};
17use smallvec::SmallVec;
18
19pub use self::symbol_resolver::{SymbolResolutionContext, SymbolResolver};
20use super::SymbolItem;
21use crate::LinkerError;
22
23/// A [Resolver] is used to perform symbol resolution in the context of a specific module.
24///
25/// It is instantiated along with a [ResolverCache] to cache frequently-referenced symbols, and a
26/// [SymbolResolver] for resolving externally-defined symbols.
27pub struct Resolver<'a, 'b: 'a> {
28    pub resolver: &'a SymbolResolver<'b>,
29    pub cache: &'a mut ResolverCache,
30    pub current_module: ModuleIndex,
31}
32
33/// A [ResolverCache] is used to cache resolutions of type and constant expressions to concrete
34/// values that contain no references to other symbols. Since these resolutions can be expensive
35/// to compute, and often represent items which are referenced multiple times, we cache them to
36/// avoid recomputing the same information over and over again.
37#[derive(Default)]
38pub struct ResolverCache {
39    pub types: BTreeMap<GlobalItemIndex, ast::types::Type>,
40    pub constants: BTreeMap<GlobalItemIndex, ast::ConstantValue>,
41    pub evaluating_constants: BTreeMap<GlobalItemIndex, SourceSpan>,
42}
43
44impl<'a, 'b: 'a> Resolver<'a, 'b> {
45    fn invalid_constant_ref(&self, span: SourceSpan) -> LinkerError {
46        LinkerError::InvalidConstantRef {
47            span,
48            source_file: self.get_source_file_for(span),
49        }
50    }
51
52    pub(super) fn materialize_constant_by_gid(
53        &mut self,
54        gid: GlobalItemIndex,
55        span: SourceSpan,
56    ) -> Result<(), LinkerError> {
57        if self.cache.constants.contains_key(&gid) {
58            return Ok(());
59        }
60
61        match self.resolver.linker()[gid].item() {
62            SymbolItem::Compiled(ItemInfo::Constant(_)) => return Ok(()),
63            SymbolItem::Constant(item) => {
64                let expr = item.value.clone();
65                let eval_span = item.value.span();
66                if let Some(start) = self.cache.evaluating_constants.get(&gid).copied() {
67                    return Err(ConstEvalError::eval_cycle(start, span, self).into());
68                }
69
70                self.cache.evaluating_constants.insert(gid, eval_span);
71                let value = self.resolver.linker().const_eval(gid, &expr, self.cache);
72                self.cache.evaluating_constants.remove(&gid);
73
74                let value = value?;
75                self.cache.constants.insert(gid, value);
76                return Ok(());
77            },
78            SymbolItem::Compiled(_) | SymbolItem::Procedure(_) | SymbolItem::Type(_) => (),
79            SymbolItem::Alias { .. } => unreachable!("resolver should have expanded all aliases"),
80        }
81
82        Err(self.invalid_constant_ref(span))
83    }
84
85    fn get_constant_by_gid(
86        &mut self,
87        gid: GlobalItemIndex,
88        span: SourceSpan,
89    ) -> Result<Option<CachedConstantValue<'_>>, LinkerError> {
90        self.materialize_constant_by_gid(gid, span)?;
91
92        if let Some(cached) = self.cache.constants.get(&gid) {
93            return Ok(Some(CachedConstantValue::Hit(cached)));
94        }
95
96        match self.resolver.linker()[gid].item() {
97            SymbolItem::Compiled(ItemInfo::Constant(info)) => {
98                Ok(Some(CachedConstantValue::Hit(&info.value)))
99            },
100            SymbolItem::Compiled(_)
101            | SymbolItem::Constant(_)
102            | SymbolItem::Procedure(_)
103            | SymbolItem::Type(_) => Err(self.invalid_constant_ref(span)),
104            SymbolItem::Alias { .. } => unreachable!("resolver should have expanded all aliases"),
105        }
106    }
107}
108
109impl<'a, 'b: 'a> ConstEnvironment for Resolver<'a, 'b> {
110    type Error = LinkerError;
111
112    fn get_source_file_for(&self, span: SourceSpan) -> Option<Arc<SourceFile>> {
113        self.resolver.source_manager().get(span.source_id()).ok()
114    }
115
116    fn get(&mut self, name: &Ident) -> Result<Option<CachedConstantValue<'_>>, Self::Error> {
117        let context = SymbolResolutionContext {
118            span: name.span(),
119            module: self.current_module,
120            kind: None,
121        };
122        let gid = match self.resolver.resolve_local(&context, name)? {
123            SymbolResolution::Exact { gid, .. } => gid,
124            SymbolResolution::Local(index) => self.current_module + index.into_inner(),
125            SymbolResolution::MastRoot(_) | SymbolResolution::Module { .. } => {
126                return Err(self.invalid_constant_ref(context.span));
127            },
128            SymbolResolution::External(path) => {
129                return Err(LinkerError::UndefinedSymbol {
130                    span: context.span,
131                    source_file: self.get_source_file_for(context.span),
132                    path: path.into_inner(),
133                });
134            },
135        };
136
137        self.get_constant_by_gid(gid, name.span())
138    }
139
140    fn get_by_path(
141        &mut self,
142        path: Span<&Path>,
143    ) -> Result<Option<CachedConstantValue<'_>>, Self::Error> {
144        let context = SymbolResolutionContext {
145            span: path.span(),
146            module: self.current_module,
147            kind: None,
148        };
149        let gid = match self.resolver.resolve_path(&context, path)? {
150            SymbolResolution::Exact { gid, .. } => gid,
151            SymbolResolution::Local(index) => self.current_module + index.into_inner(),
152            SymbolResolution::MastRoot(_) | SymbolResolution::Module { .. } => {
153                return Err(self.invalid_constant_ref(context.span));
154            },
155            SymbolResolution::External(path) => {
156                return Err(LinkerError::UndefinedSymbol {
157                    span: context.span,
158                    source_file: self.get_source_file_for(context.span),
159                    path: path.into_inner(),
160                });
161            },
162        };
163
164        self.get_constant_by_gid(gid, path.span())
165    }
166
167    /// Cache evaluated constants so long as they evaluated to a ConstantValue, and we can resolve
168    /// the path to a known GlobalItemIndex
169    fn on_eval_completed(&mut self, path: Span<&Path>, value: &ast::ConstantExpr) {
170        let Some(value) = value.as_value() else {
171            return;
172        };
173        let context = SymbolResolutionContext {
174            span: path.span(),
175            module: self.current_module,
176            kind: None,
177        };
178        let gid = match self.resolver.resolve_path(&context, path) {
179            Ok(SymbolResolution::Exact { gid, .. }) => gid,
180            Ok(SymbolResolution::Local(index)) => self.current_module + index.into_inner(),
181            _ => return,
182        };
183        self.cache.constants.insert(gid, value);
184    }
185}
186
187impl<'a, 'b: 'a> ast::TypeResolver<LinkerError> for Resolver<'a, 'b> {
188    #[inline]
189    fn source_manager(&self) -> Arc<dyn SourceManager> {
190        self.resolver.source_manager_arc()
191    }
192    #[inline]
193    fn resolve_local_failed(&self, err: SymbolResolutionError) -> LinkerError {
194        LinkerError::from(err)
195    }
196
197    fn get_type(
198        &mut self,
199        context: SourceSpan,
200        gid: GlobalItemIndex,
201    ) -> Result<types::Type, LinkerError> {
202        match self.resolver.linker()[gid].item() {
203            SymbolItem::Compiled(ItemInfo::Type(info)) => Ok(info.ty.clone()),
204            SymbolItem::Type(ast::TypeDecl::Enum(ty)) => {
205                // When resolving an EnumType, we must do three things:
206                //
207                // * Resolve the discriminant type
208                // * Resolve the discriminant value and payload type for each variant
209                // * Construct the midenc_hir_type::EnumType, and validate that the enum is valid
210                //   according to the rules it enforces
211                let mut variants = SmallVec::<[types::Variant; 4]>::new_const();
212                for variant in ty.variants() {
213                    let discriminant_value = match self.resolver.linker().const_eval(
214                        gid,
215                        &variant.discriminant,
216                        self.cache,
217                    )? {
218                        ast::ConstantValue::Int(v) => Some(v.as_canonical_u64() as u128),
219                        invalid => {
220                            return Err(LinkerError::Related {
221                                errors: vec![RelatedError::new(Report::from(diagnostic!(
222                                    severity = Severity::Error,
223                                    labels = vec![LabeledSpan::at(
224                                        invalid.span(),
225                                        "invalid enum discriminant: expected an integer"
226                                    )],
227                                    "invalid enum type"
228                                )))]
229                                .into_boxed_slice(),
230                            });
231                        },
232                    };
233                    variants.push(types::Variant {
234                        name: variant.name.clone().into_inner(),
235                        value: match variant.value_ty.as_ref() {
236                            Some(t) => t.resolve_type(self)?,
237                            None => None,
238                        },
239                        discriminant_value,
240                    });
241                }
242                types::EnumType::new(ty.name().clone().into_inner(), ty.ty().clone(), variants)
243                    .map(|t| types::Type::Enum(Arc::new(t)))
244                    .map_err(|err| LinkerError::Related {
245                        errors: vec![RelatedError::from(Report::from(diagnostic!(
246                            severity = Severity::Error,
247                            labels = vec![LabeledSpan::at(context, err.to_string())],
248                            "invalid enum type"
249                        )))]
250                        .into_boxed_slice(),
251                    })
252            },
253            SymbolItem::Type(ast::TypeDecl::Alias(ty)) => {
254                Ok(ty.ty.resolve_type(self)?.expect("unreachable"))
255            },
256            SymbolItem::Compiled(_) | SymbolItem::Constant(_) | SymbolItem::Procedure(_) => {
257                Err(LinkerError::InvalidTypeRef {
258                    span: context,
259                    source_file: self.get_source_file_for(context),
260                })
261            },
262            SymbolItem::Alias { .. } => unreachable!("resolver should have expanded all aliases"),
263        }
264    }
265
266    fn get_local_type(
267        &mut self,
268        context: SourceSpan,
269        id: ItemIndex,
270    ) -> Result<Option<types::Type>, LinkerError> {
271        self.get_type(context, self.current_module + id).map(Some)
272    }
273
274    fn resolve_type_ref(&mut self, ty: Span<&Path>) -> Result<SymbolResolution, LinkerError> {
275        let context = SymbolResolutionContext {
276            span: ty.span(),
277            module: self.current_module,
278            kind: None,
279        };
280        match self.resolver.resolve_path(&context, ty)? {
281            exact @ SymbolResolution::Exact { .. } => Ok(exact),
282            SymbolResolution::Local(index) => {
283                let (span, index) = index.into_parts();
284                let current_module = &self.resolver.linker()[self.current_module];
285                let item = current_module[index].name();
286                let path = Span::new(span, current_module.path().join(item).into());
287                Ok(SymbolResolution::Exact { gid: self.current_module + index, path })
288            },
289            SymbolResolution::MastRoot(_) | SymbolResolution::Module { .. } => {
290                Err(LinkerError::InvalidTypeRef {
291                    span: ty.span(),
292                    source_file: self.get_source_file_for(ty.span()),
293                })
294            },
295            SymbolResolution::External(path) => Err(LinkerError::UndefinedSymbol {
296                span: ty.span(),
297                source_file: self.get_source_file_for(ty.span()),
298                path: path.into_inner(),
299            }),
300        }
301    }
302}
miden_assembly/linker/resolver/mod.rs

miden_assembly/linker/resolver/
mod.rs
