miden_assembly/linker/resolver/symbol_resolver.rs
1use alloc::{boxed::Box, collections::BTreeSet, string::ToString, sync::Arc};
2
3use miden_assembly_syntax::{
4 ast::{
5 Alias, AliasTarget, InvocationTarget, InvokeKind, Path, SymbolResolution,
6 SymbolResolutionError,
7 },
8 debuginfo::{SourceManager, SourceSpan, Span, Spanned},
9};
10use miden_core::Word;
11
12use crate::{GlobalItemIndex, LinkerError, ModuleIndex, linker::Linker};
13
14// HELPER STRUCTS
15// ================================================================================================
16
17/// Represents the context in which symbols should be resolved.
18///
19/// A symbol may be resolved in different ways depending on where it is being referenced from, and
20/// how it is being referenced.
21#[derive(Debug, Clone)]
22pub struct SymbolResolutionContext {
23 /// The source span of the caller/referent
24 pub span: SourceSpan,
25 /// The "where", i.e. index of the caller/referent's module node in the [Linker] module graph.
26 pub module: ModuleIndex,
27 /// The "how", i.e. how the symbol is being referenced/invoked.
28 ///
29 /// This is primarily relevant for procedure invocations, particularly syscalls, as "local"
30 /// names resolve in the kernel module, _not_ in the caller's module. Non-procedure symbols are
31 /// always pure references.
32 pub kind: Option<InvokeKind>,
33}
34
35impl SymbolResolutionContext {
36 #[inline]
37 pub fn in_syscall(&self) -> bool {
38 matches!(self.kind, Some(InvokeKind::SysCall))
39 }
40}
41
42// SYMBOL RESOLVER
43// ================================================================================================
44
45/// A [SymbolResolver] is used to resolve a procedure invocation target to its concrete definition.
46///
47/// Because modules can re-export/alias the procedures of modules they import, resolving the name of
48/// a procedure can require multiple steps to reach the original concrete definition of the
49/// procedure.
50///
51/// The [SymbolResolver] encapsulates the tricky details of doing this, so that users of the
52/// resolver need only provide a reference to the [Linker], a name they wish to resolve, and some
53/// information about the caller necessary to determine the context in which the name should be
54/// resolved.
55pub struct SymbolResolver<'a> {
56 /// The graph containing already-compiled and partially-resolved modules.
57 graph: &'a Linker,
58}
59
60impl<'a> SymbolResolver<'a> {
61 /// Create a new [SymbolResolver] for the provided [Linker].
62 pub fn new(graph: &'a Linker) -> Self {
63 Self { graph }
64 }
65
66 #[inline(always)]
67 pub fn source_manager(&self) -> &dyn SourceManager {
68 &self.graph.source_manager
69 }
70
71 #[inline(always)]
72 pub fn source_manager_arc(&self) -> Arc<dyn SourceManager> {
73 self.graph.source_manager.clone()
74 }
75
76 #[inline(always)]
77 pub(crate) fn linker(&self) -> &Linker {
78 self.graph
79 }
80
81 /// Resolve `target`, a possibly-resolved symbol reference, to a [SymbolResolution], using
82 /// `context` as the context.
83 pub fn resolve_invoke_target(
84 &self,
85 context: &SymbolResolutionContext,
86 target: &InvocationTarget,
87 ) -> Result<SymbolResolution, LinkerError> {
88 match target {
89 InvocationTarget::MastRoot(mast_root) => {
90 log::debug!(target: "name-resolver::invoke", "resolving {target}");
91 self.validate_syscall_digest(context, *mast_root)?;
92 match self.graph.get_procedure_index_by_digest(mast_root) {
93 None => Ok(SymbolResolution::MastRoot(*mast_root)),
94 Some(gid) if context.in_syscall() => {
95 if self.graph.kernel_index.is_some_and(|k| k == gid.module) {
96 Ok(SymbolResolution::Exact {
97 gid,
98 path: Span::new(mast_root.span(), self.item_path(gid)),
99 })
100 } else {
101 Err(LinkerError::InvalidSysCallTarget {
102 span: context.span,
103 source_file: self
104 .source_manager()
105 .get(context.span.source_id())
106 .ok(),
107 callee: self.item_path(gid),
108 })
109 }
110 },
111 Some(gid) => Ok(SymbolResolution::Exact {
112 gid,
113 path: Span::new(mast_root.span(), self.item_path(gid)),
114 }),
115 }
116 },
117 InvocationTarget::Symbol(symbol) => {
118 let path = Path::from_ident(symbol);
119 let mut context = context.clone();
120 // Force the resolution context for a syscall target to be the kernel module
121 if context.in_syscall() {
122 if let Some(kernel) = self.graph.kernel_index {
123 context.module = kernel;
124 } else {
125 return Err(LinkerError::InvalidSysCallTarget {
126 span: context.span,
127 source_file: self.source_manager().get(context.span.source_id()).ok(),
128 callee: Path::from_ident(symbol).into_owned().into(),
129 });
130 }
131 }
132 match self.resolve_path(&context, Span::new(symbol.span(), path.as_ref()))? {
133 SymbolResolution::Module { id: _, path: module_path } => {
134 Err(LinkerError::InvalidInvokeTarget {
135 span: symbol.span(),
136 source_file: self
137 .graph
138 .source_manager
139 .get(symbol.span().source_id())
140 .ok(),
141 path: module_path.into_inner(),
142 })
143 },
144 resolution => Ok(resolution),
145 }
146 },
147 InvocationTarget::Path(path) => match self.resolve_path(context, path.as_deref())? {
148 SymbolResolution::Module { id: _, path: module_path } => {
149 Err(LinkerError::InvalidInvokeTarget {
150 span: path.span(),
151 source_file: self.graph.source_manager.get(path.span().source_id()).ok(),
152 path: module_path.into_inner(),
153 })
154 },
155 SymbolResolution::Exact { gid, path } if context.in_syscall() => {
156 if self.graph.kernel_index.is_some_and(|k| k == gid.module) {
157 Ok(SymbolResolution::Exact { gid, path })
158 } else {
159 Err(LinkerError::InvalidSysCallTarget {
160 span: context.span,
161 source_file: self.source_manager().get(context.span.source_id()).ok(),
162 callee: path.into_inner(),
163 })
164 }
165 },
166 SymbolResolution::MastRoot(mast_root) => {
167 self.validate_syscall_digest(context, mast_root)?;
168 match self.graph.get_procedure_index_by_digest(&mast_root) {
169 None => Ok(SymbolResolution::MastRoot(mast_root)),
170 Some(gid) if context.in_syscall() => {
171 if self.graph.kernel_index.is_some_and(|k| k == gid.module) {
172 Ok(SymbolResolution::Exact {
173 gid,
174 path: Span::new(mast_root.span(), self.item_path(gid)),
175 })
176 } else {
177 Err(LinkerError::InvalidSysCallTarget {
178 span: context.span,
179 source_file: self
180 .source_manager()
181 .get(context.span.source_id())
182 .ok(),
183 callee: self.item_path(gid),
184 })
185 }
186 },
187 Some(gid) => Ok(SymbolResolution::Exact {
188 gid,
189 path: Span::new(mast_root.span(), self.item_path(gid)),
190 }),
191 }
192 },
193 // NOTE: If we're in a syscall here, we can't validate syscall targets that are not
194 // fully resolved - but such targets will be revisited later at which point they
195 // will be checked
196 resolution => Ok(resolution),
197 },
198 }
199 }
200
201 fn validate_syscall_digest(
202 &self,
203 context: &SymbolResolutionContext,
204 mast_root: Span<Word>,
205 ) -> Result<(), LinkerError> {
206 if !context.in_syscall() {
207 return Ok(());
208 }
209 // Syscalls must be validated against an attached kernel at assembly time.
210 if !self.graph.has_nonempty_kernel() {
211 return Err(LinkerError::InvalidSysCallTarget {
212 span: context.span,
213 source_file: self.source_manager().get(context.span.source_id()).ok(),
214 callee: Arc::<Path>::from(Path::new("syscall")),
215 });
216 }
217 // Kernel digests only contain exported kernel procedures.
218 if !self.graph.kernel().contains_proc(*mast_root.inner()) {
219 let digest_path = format!("{mast_root}");
220 return Err(LinkerError::InvalidSysCallTarget {
221 span: context.span,
222 source_file: self.source_manager().get(context.span.source_id()).ok(),
223 callee: Arc::<Path>::from(Path::new(&digest_path)),
224 });
225 }
226 Ok(())
227 }
228
229 /// Resolve `target`, a possibly-resolved symbol reference, to a [SymbolResolution], using
230 /// `context` as the context.
231 pub fn resolve_alias_target(
232 &self,
233 context: &SymbolResolutionContext,
234 alias: &Alias,
235 ) -> Result<SymbolResolution, LinkerError> {
236 match alias.target() {
237 target @ AliasTarget::MastRoot(mast_root) => {
238 log::debug!(target: "name-resolver::alias", "resolving alias target {target}");
239 match self.graph.get_procedure_index_by_digest(mast_root) {
240 None => Ok(SymbolResolution::MastRoot(*mast_root)),
241 Some(gid) => Ok(SymbolResolution::Exact {
242 gid,
243 path: Span::new(mast_root.span(), self.item_path(gid)),
244 }),
245 }
246 },
247 AliasTarget::Path(path) => {
248 log::debug!(target: "name-resolver::alias", "resolving alias target '{path}'");
249 // We ensure that we do not unintentionally recursively expand an alias target using
250 // its own definition, e.g. with something like `use lib::lib` which without this,
251 // will expand until the stack blows
252 let mut ignored_imports = BTreeSet::from_iter([alias.name().clone().into_inner()]);
253 self.expand_path(context, path.as_deref(), &mut ignored_imports)
254 },
255 }
256 }
257
258 pub fn resolve_path(
259 &self,
260 context: &SymbolResolutionContext,
261 path: Span<&Path>,
262 ) -> Result<SymbolResolution, LinkerError> {
263 let mut ignored_imports = BTreeSet::default();
264 self.expand_path(context, path, &mut ignored_imports)
265 }
266
267 fn expand_path(
268 &self,
269 context: &SymbolResolutionContext,
270 path: Span<&Path>,
271 ignored_imports: &mut BTreeSet<Arc<str>>,
272 ) -> Result<SymbolResolution, LinkerError> {
273 let span = path.span();
274 let mut path = path.into_inner();
275 let mut context = context.clone();
276 loop {
277 log::debug!(target: "name-resolver::expand", "expanding path '{path}' (absolute = {})", path.is_absolute());
278 if path.is_absolute() {
279 // An absolute path does not reference any aliases in the current module, but may
280 // refer to aliases in any of its non-root components.
281 //
282 // However, if the root component of the path is not a known module, then we have to
283 // proceed as if an actual module exists, just one that incorporates more components
284 // of the path than just the root.
285 //
286 // To speed this up, we search for a matching "longest-prefix" of `path` in the
287 // global module list. If we find an exact match, we're done. If we
288 // find a partial match, then we resolve the rest of `path` relative
289 // to that partial match. If we cannot find any match at all, then
290 // the path references an undefined module
291 let mut longest_prefix: Option<(ModuleIndex, Arc<Path>)> = None;
292 for module in self.graph.modules.iter() {
293 let module_path = module.path().clone();
294 if path == &*module_path {
295 log::debug!(target: "name-resolver::expand", "found exact match for '{path}': id={}", module.id());
296 return Ok(SymbolResolution::Module {
297 id: module.id(),
298 path: Span::new(span, module_path),
299 });
300 }
301
302 if path.starts_with_exactly(module_path.as_ref()) {
303 if let Some((_, prev)) = longest_prefix.as_ref() {
304 if prev.components().count() < module_path.components().count() {
305 longest_prefix = Some((module.id(), module_path));
306 }
307 } else {
308 longest_prefix = Some((module.id(), module_path));
309 }
310 }
311 }
312
313 match longest_prefix {
314 // We found a module with a common prefix, attempt to expand the subpath of
315 // `path` relative to that module. If this fails, the path
316 // is an undefined reference.
317 Some((module_id, module_path)) => {
318 log::trace!(target: "name-resolver::expand", "found prefix match for '{path}': id={module_id}, prefix={module_path}");
319 let subpath = path.strip_prefix(&module_path).unwrap();
320 context.module = module_id;
321 ignored_imports.clear();
322 path = subpath;
323 },
324 // No matching module paths found, path is undefined symbol reference
325 None => {
326 log::trace!(target: "name-resolver::expand", "no prefix match found for '{path}' - path is undefined symbol reference");
327 break Err(
328 SymbolResolutionError::undefined(span, self.source_manager()).into()
329 );
330 },
331 }
332 } else if let Some(symbol) = path.as_ident() {
333 // This is a reference to a symbol in the current module, possibly imported.
334 //
335 // We first resolve the symbol in the local module to either a local definition, or
336 // an imported symbol.
337 //
338 // If the symbol is locally-defined, the expansion is the join of the current module
339 // path and the symbol name.
340 //
341 // If the symbol is an imported item, then we expand the imported path recursively.
342 break match self
343 .resolve_local_with_index(context.module, Span::new(span, symbol.as_str()))?
344 {
345 SymbolResolution::Local(item) => {
346 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to local symbol: {}", context.module + item.into_inner());
347 let path = self.module_path(context.module).join(&symbol);
348 Ok(SymbolResolution::Exact {
349 gid: context.module + item.into_inner(),
350 path: Span::new(span, path.into()),
351 })
352 },
353 SymbolResolution::External(path) => {
354 log::trace!(target: "name-resolver::expand", "expanded '{symbol}' to unresolved external path '{path}'");
355 self.expand_path(&context, path.as_deref(), ignored_imports)
356 },
357 resolved @ (SymbolResolution::MastRoot(_) | SymbolResolution::Exact { .. }) => {
358 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to exact definition");
359 Ok(resolved)
360 },
361 SymbolResolution::Module { id, path: module_path } => {
362 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to module: id={id} path={module_path}");
363 Ok(SymbolResolution::Module { id, path: module_path })
364 },
365 };
366 } else {
367 // A relative path can be expressed in four forms:
368 //
369 // 1. A reference to a symbol in the current module (possibly imported)
370 // 2. A reference to a symbol relative to an imported module, e.g. `push.mod::CONST`
371 // 3. A reference to a nested symbol relative to an imported module, e.g.
372 // `push.mod::submod::CONST`
373 // 4. An absolute path expressed relatively, e.g. `push.root::mod::submod::CONST`,
374 // which should have been expressed as `push.::root::mod::submod::CONST`, but the
375 // `::` prefix was omitted/forgotten.
376 //
377 // 1 and 4 are easy to handle (4 is technically a degenerate edge case of 3, but has
378 // an easy fallback path).
379 //
380 // 3 is where all the complexity of relative paths comes in, because it requires us
381 // to recursively expand paths until we cannot do so any longer, and then resolve
382 // the originally referenced symbol relative to that expanded path (which may
383 // require further recursive expansion).
384 //
385 // We start by expecting that a relative path refers to an import in the current
386 // module: if this is not the case, then we fall back to attempting to resolve the
387 // path as if it was absolute. If this fails, the path is considered to refer to an
388 // undefined symbol.
389 //
390 // If the path is relative to an import in the current module, then we proceed by
391 // resolving the subpath relative to the import target. This is the recursive part,
392 // and the result of this recursive expansion is what gets returned from this
393 // function.
394 let (imported_symbol, subpath) = path.split_first().expect("multi-component path");
395 if ignored_imports.contains(imported_symbol) {
396 log::trace!(target: "name-resolver::expand", "skipping import expansion of '{imported_symbol}': already expanded, resolving as absolute path instead");
397 let path = path.to_absolute();
398 break self.expand_path(
399 &context,
400 Span::new(span, path.as_ref()),
401 ignored_imports,
402 );
403 }
404 match self
405 .resolve_local_with_index(context.module, Span::new(span, imported_symbol))
406 {
407 Ok(SymbolResolution::Local(item)) => {
408 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to local definition");
409 // This is a conflicting symbol reference that we would've expected to be
410 // caught during semantic analysis. Raise a
411 // diagnostic here telling the user what's wrong
412 break Err(SymbolResolutionError::invalid_sub_path(
413 span,
414 item.span(),
415 self.source_manager(),
416 )
417 .into());
418 },
419 Ok(SymbolResolution::Exact { path: item, .. }) => {
420 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to item at '{item}'");
421 // This is a conflicting symbol reference that we would've expected to be
422 // caught during semantic analysis. Raise a
423 // diagnostic here telling the user what's wrong
424 break Err(SymbolResolutionError::invalid_sub_path(
425 span,
426 item.span(),
427 self.source_manager(),
428 )
429 .into());
430 },
431 Ok(SymbolResolution::MastRoot(item)) => {
432 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to imported procedure root");
433 // This is a conflicting symbol reference that we would've expected to be
434 // caught during semantic analysis. Raise a
435 // diagnostic here telling the user what's wrong
436 break Err(SymbolResolutionError::invalid_sub_path(
437 span,
438 item.span(),
439 self.source_manager(),
440 )
441 .into());
442 },
443 Ok(SymbolResolution::Module { id, path: module_path }) => {
444 log::trace!(target: "name-resolver::expand", "expanded import '{imported_symbol}' to module: id={id} path={module_path}");
445 // We've resolved the import to a known module, resolve `subpath` relative
446 // to it
447 context.module = id;
448 ignored_imports.clear();
449 path = subpath;
450 },
451 Ok(SymbolResolution::External(external_path)) => {
452 // We've resolved the imported symbol to an external path, but we don't know
453 // if that path is valid or not. Attempt to expand
454 // the full path produced by joining `subpath` to
455 // `external_path` and resolving in the context of the
456 // current module
457 log::trace!(target: "name-resolver::expand", "expanded import '{imported_symbol}' to unresolved external path '{external_path}'");
458 let partially_expanded = external_path.join(subpath);
459 log::trace!(target: "name-resolver::expand", "partially expanded '{path}' to '{partially_expanded}'");
460 ignored_imports.insert(imported_symbol.to_string().into_boxed_str().into());
461 break self.expand_path(
462 &context,
463 Span::new(span, partially_expanded.as_path()),
464 ignored_imports,
465 );
466 },
467 Err(err)
468 if matches!(
469 err.as_ref(),
470 SymbolResolutionError::UndefinedSymbol { .. }
471 ) =>
472 {
473 // Try to expand the path by treating it as an absolute path
474 let absolute = path.to_absolute();
475 log::trace!(target: "name-resolver::expand", "no import found for '{imported_symbol}' in '{path}': attempting to resolve as absolute path instead");
476 break self.expand_path(
477 &context,
478 Span::new(span, absolute.as_ref()),
479 ignored_imports,
480 );
481 },
482 Err(err) => {
483 log::trace!(target: "name-resolver::expand", "expansion failed due to symbol resolution error");
484 break Err(err.into());
485 },
486 }
487 }
488 }
489 }
490
491 pub fn resolve_local(
492 &self,
493 context: &SymbolResolutionContext,
494 symbol: &str,
495 ) -> Result<SymbolResolution, Box<SymbolResolutionError>> {
496 let module = if context.in_syscall() {
497 // Resolve local names relative to the kernel
498 match self.graph.kernel_index {
499 Some(kernel) => kernel,
500 None => {
501 return Err(Box::new(SymbolResolutionError::UndefinedSymbol {
502 span: context.span,
503 source_file: self.source_manager().get(context.span.source_id()).ok(),
504 }));
505 },
506 }
507 } else {
508 context.module
509 };
510 self.resolve_local_with_index(module, Span::new(context.span, symbol))
511 }
512
513 fn resolve_local_with_index(
514 &self,
515 module: ModuleIndex,
516 symbol: Span<&str>,
517 ) -> Result<SymbolResolution, Box<SymbolResolutionError>> {
518 let module = &self.graph[module];
519 log::debug!(target: "name-resolver::local", "resolving '{symbol}' in module {}", module.path());
520 log::debug!(target: "name-resolver::local", "module status: {:?}", &module.status());
521 module.resolve(symbol, self)
522 }
523
524 #[inline]
525 pub fn module_path(&self, module: ModuleIndex) -> &Path {
526 self.graph[module].path()
527 }
528
529 pub fn item_path(&self, item: GlobalItemIndex) -> Arc<Path> {
530 let module = &self.graph[item.module];
531 let name = module[item.index].name();
532 module.path().join(name).into()
533 }
534}