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 let resolution = 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 self.enforce_kernel_export_syscall_only(context, target, resolution)
200 }
201
202 fn enforce_kernel_export_syscall_only(
203 &self,
204 context: &SymbolResolutionContext,
205 target: &InvocationTarget,
206 resolution: SymbolResolution,
207 ) -> Result<SymbolResolution, LinkerError> {
208 if matches!(target, InvocationTarget::MastRoot(_)) {
209 return Ok(resolution);
210 }
211 if let SymbolResolution::Exact { gid, ref path } = resolution
212 && context.kind.is_some()
213 && !context.in_syscall()
214 {
215 // Root kernel attached via `with_kernel` is stored as ModuleKind::Library (MAST);
216 // `kernel_index` identifies it. AST kernel modules use ModuleKind::Kernel.
217 let target_is_kernel = self.graph.kernel_index.is_some_and(|ki| ki == gid.module)
218 || self.graph[gid.module].kind().is_kernel();
219 let caller_is_kernel = self.graph.kernel_index.is_some_and(|ki| ki == context.module)
220 || self.graph[context.module].kind().is_kernel();
221 if target_is_kernel && !caller_is_kernel {
222 return Err(LinkerError::KernelProcNotSyscall {
223 span: context.span,
224 source_file: self.graph.source_manager.get(context.span.source_id()).ok(),
225 callee: path.clone().into_inner(),
226 });
227 }
228 }
229 Ok(resolution)
230 }
231
232 fn validate_syscall_digest(
233 &self,
234 context: &SymbolResolutionContext,
235 mast_root: Span<Word>,
236 ) -> Result<(), LinkerError> {
237 if !context.in_syscall() {
238 return Ok(());
239 }
240 // Syscalls must be validated against an attached kernel at assembly time.
241 if !self.graph.has_nonempty_kernel() {
242 return Err(LinkerError::InvalidSysCallTarget {
243 span: context.span,
244 source_file: self.source_manager().get(context.span.source_id()).ok(),
245 callee: Arc::<Path>::from(Path::new("syscall")),
246 });
247 }
248 // Kernel digests only contain exported kernel procedures.
249 if !self.graph.kernel().contains_proc(*mast_root.inner()) {
250 let digest_path = format!("{mast_root}");
251 return Err(LinkerError::InvalidSysCallTarget {
252 span: context.span,
253 source_file: self.source_manager().get(context.span.source_id()).ok(),
254 callee: Arc::<Path>::from(Path::new(&digest_path)),
255 });
256 }
257 Ok(())
258 }
259
260 /// Resolve `target`, a possibly-resolved symbol reference, to a [SymbolResolution], using
261 /// `context` as the context.
262 pub fn resolve_alias_target(
263 &self,
264 context: &SymbolResolutionContext,
265 alias: &Alias,
266 ) -> Result<SymbolResolution, LinkerError> {
267 match alias.target() {
268 target @ AliasTarget::MastRoot(mast_root) => {
269 log::debug!(target: "name-resolver::alias", "resolving alias target {target}");
270 match self.graph.get_procedure_index_by_digest(mast_root) {
271 None => Ok(SymbolResolution::MastRoot(*mast_root)),
272 Some(gid) => Ok(SymbolResolution::Exact {
273 gid,
274 path: Span::new(mast_root.span(), self.item_path(gid)),
275 }),
276 }
277 },
278 AliasTarget::Path(path) => {
279 log::debug!(target: "name-resolver::alias", "resolving alias target '{path}'");
280 // We ensure that we do not unintentionally recursively expand an alias target using
281 // its own definition, e.g. with something like `use lib::lib` which without this,
282 // will expand until the stack blows
283 let mut ignored_imports = BTreeSet::from_iter([alias.name().clone().into_inner()]);
284 self.expand_path(context, path.as_deref(), &mut ignored_imports)
285 },
286 }
287 }
288
289 pub fn resolve_path(
290 &self,
291 context: &SymbolResolutionContext,
292 path: Span<&Path>,
293 ) -> Result<SymbolResolution, LinkerError> {
294 let mut ignored_imports = BTreeSet::default();
295 self.expand_path(context, path, &mut ignored_imports)
296 }
297
298 fn expand_path(
299 &self,
300 context: &SymbolResolutionContext,
301 path: Span<&Path>,
302 ignored_imports: &mut BTreeSet<Arc<str>>,
303 ) -> Result<SymbolResolution, LinkerError> {
304 let span = path.span();
305 let mut path = path.into_inner();
306 let mut context = context.clone();
307 loop {
308 log::debug!(target: "name-resolver::expand", "expanding path '{path}' (absolute = {})", path.is_absolute());
309 if path.is_absolute() {
310 // An absolute path does not reference any aliases in the current module, but may
311 // refer to aliases in any of its non-root components.
312 //
313 // However, if the root component of the path is not a known module, then we have to
314 // proceed as if an actual module exists, just one that incorporates more components
315 // of the path than just the root.
316 //
317 // To speed this up, we search for a matching "longest-prefix" of `path` in the
318 // global module list. If we find an exact match, we're done. If we
319 // find a partial match, then we resolve the rest of `path` relative
320 // to that partial match. If we cannot find any match at all, then
321 // the path references an undefined module
322 let mut longest_prefix: Option<(ModuleIndex, Arc<Path>)> = None;
323 for module in self.graph.modules.iter() {
324 let module_path = module.path().clone();
325 if path == &*module_path {
326 log::debug!(target: "name-resolver::expand", "found exact match for '{path}': id={}", module.id());
327 return Ok(SymbolResolution::Module {
328 id: module.id(),
329 path: Span::new(span, module_path),
330 });
331 }
332
333 if path.starts_with_exactly(module_path.as_ref()) {
334 if let Some((_, prev)) = longest_prefix.as_ref() {
335 if prev.components().count() < module_path.components().count() {
336 longest_prefix = Some((module.id(), module_path));
337 }
338 } else {
339 longest_prefix = Some((module.id(), module_path));
340 }
341 }
342 }
343
344 match longest_prefix {
345 // We found a module with a common prefix, attempt to expand the subpath of
346 // `path` relative to that module. If this fails, the path
347 // is an undefined reference.
348 Some((module_id, module_path)) => {
349 log::trace!(target: "name-resolver::expand", "found prefix match for '{path}': id={module_id}, prefix={module_path}");
350 let subpath = path.strip_prefix(&module_path).unwrap();
351 context.module = module_id;
352 ignored_imports.clear();
353 path = subpath;
354 },
355 // No matching module paths found, path is undefined symbol reference
356 None => {
357 log::trace!(target: "name-resolver::expand", "no prefix match found for '{path}' - path is undefined symbol reference");
358 break Err(
359 SymbolResolutionError::undefined(span, self.source_manager()).into()
360 );
361 },
362 }
363 } else if let Some(symbol) = path.as_ident() {
364 // This is a reference to a symbol in the current module, possibly imported.
365 //
366 // We first resolve the symbol in the local module to either a local definition, or
367 // an imported symbol.
368 //
369 // If the symbol is locally-defined, the expansion is the join of the current module
370 // path and the symbol name.
371 //
372 // If the symbol is an imported item, then we expand the imported path recursively.
373 break match self
374 .resolve_local_with_index(context.module, Span::new(span, symbol.as_str()))?
375 {
376 SymbolResolution::Local(item) => {
377 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to local symbol: {}", context.module + item.into_inner());
378 let path = self.module_path(context.module).join(&symbol);
379 Ok(SymbolResolution::Exact {
380 gid: context.module + item.into_inner(),
381 path: Span::new(span, path.into()),
382 })
383 },
384 SymbolResolution::External(path) => {
385 log::trace!(target: "name-resolver::expand", "expanded '{symbol}' to unresolved external path '{path}'");
386 self.expand_path(&context, path.as_deref(), ignored_imports)
387 },
388 resolved @ (SymbolResolution::MastRoot(_) | SymbolResolution::Exact { .. }) => {
389 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to exact definition");
390 Ok(resolved)
391 },
392 SymbolResolution::Module { id, path: module_path } => {
393 log::trace!(target: "name-resolver::expand", "resolved '{symbol}' to module: id={id} path={module_path}");
394 Ok(SymbolResolution::Module { id, path: module_path })
395 },
396 };
397 } else {
398 // A relative path can be expressed in four forms:
399 //
400 // 1. A reference to a symbol in the current module (possibly imported)
401 // 2. A reference to a symbol relative to an imported module, e.g. `push.mod::CONST`
402 // 3. A reference to a nested symbol relative to an imported module, e.g.
403 // `push.mod::submod::CONST`
404 // 4. An absolute path expressed relatively, e.g. `push.root::mod::submod::CONST`,
405 // which should have been expressed as `push.::root::mod::submod::CONST`, but the
406 // `::` prefix was omitted/forgotten.
407 //
408 // 1 and 4 are easy to handle (4 is technically a degenerate edge case of 3, but has
409 // an easy fallback path).
410 //
411 // 3 is where all the complexity of relative paths comes in, because it requires us
412 // to recursively expand paths until we cannot do so any longer, and then resolve
413 // the originally referenced symbol relative to that expanded path (which may
414 // require further recursive expansion).
415 //
416 // We start by expecting that a relative path refers to an import in the current
417 // module: if this is not the case, then we fall back to attempting to resolve the
418 // path as if it was absolute. If this fails, the path is considered to refer to an
419 // undefined symbol.
420 //
421 // If the path is relative to an import in the current module, then we proceed by
422 // resolving the subpath relative to the import target. This is the recursive part,
423 // and the result of this recursive expansion is what gets returned from this
424 // function.
425 let (imported_symbol, subpath) = path.split_first().expect("multi-component path");
426 if ignored_imports.contains(imported_symbol) {
427 log::trace!(target: "name-resolver::expand", "skipping import expansion of '{imported_symbol}': already expanded, resolving as absolute path instead");
428 let path = path.to_absolute();
429 break self.expand_path(
430 &context,
431 Span::new(span, path.as_ref()),
432 ignored_imports,
433 );
434 }
435 match self
436 .resolve_local_with_index(context.module, Span::new(span, imported_symbol))
437 {
438 Ok(SymbolResolution::Local(item)) => {
439 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to local definition");
440 // This is a conflicting symbol reference that we would've expected to be
441 // caught during semantic analysis. Raise a
442 // diagnostic here telling the user what's wrong
443 break Err(SymbolResolutionError::invalid_sub_path(
444 span,
445 item.span(),
446 self.source_manager(),
447 )
448 .into());
449 },
450 Ok(SymbolResolution::Exact { path: item, .. }) => {
451 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to item at '{item}'");
452 // This is a conflicting symbol reference that we would've expected to be
453 // caught during semantic analysis. Raise a
454 // diagnostic here telling the user what's wrong
455 break Err(SymbolResolutionError::invalid_sub_path(
456 span,
457 item.span(),
458 self.source_manager(),
459 )
460 .into());
461 },
462 Ok(SymbolResolution::MastRoot(item)) => {
463 log::trace!(target: "name-resolver::expand", "cannot expand '{path}': path is relative to imported procedure root");
464 // This is a conflicting symbol reference that we would've expected to be
465 // caught during semantic analysis. Raise a
466 // diagnostic here telling the user what's wrong
467 break Err(SymbolResolutionError::invalid_sub_path(
468 span,
469 item.span(),
470 self.source_manager(),
471 )
472 .into());
473 },
474 Ok(SymbolResolution::Module { id, path: module_path }) => {
475 log::trace!(target: "name-resolver::expand", "expanded import '{imported_symbol}' to module: id={id} path={module_path}");
476 // We've resolved the import to a known module, resolve `subpath` relative
477 // to it
478 context.module = id;
479 ignored_imports.clear();
480 path = subpath;
481 },
482 Ok(SymbolResolution::External(external_path)) => {
483 // We've resolved the imported symbol to an external path, but we don't know
484 // if that path is valid or not. Attempt to expand
485 // the full path produced by joining `subpath` to
486 // `external_path` and resolving in the context of the
487 // current module
488 log::trace!(target: "name-resolver::expand", "expanded import '{imported_symbol}' to unresolved external path '{external_path}'");
489 let partially_expanded = external_path.join(subpath);
490 log::trace!(target: "name-resolver::expand", "partially expanded '{path}' to '{partially_expanded}'");
491 ignored_imports.insert(imported_symbol.to_string().into_boxed_str().into());
492 break self.expand_path(
493 &context,
494 Span::new(span, partially_expanded.as_path()),
495 ignored_imports,
496 );
497 },
498 Err(err)
499 if matches!(
500 err.as_ref(),
501 SymbolResolutionError::UndefinedSymbol { .. }
502 ) =>
503 {
504 // Try to expand the path by treating it as an absolute path
505 let absolute = path.to_absolute();
506 log::trace!(target: "name-resolver::expand", "no import found for '{imported_symbol}' in '{path}': attempting to resolve as absolute path instead");
507 break self.expand_path(
508 &context,
509 Span::new(span, absolute.as_ref()),
510 ignored_imports,
511 );
512 },
513 Err(err) => {
514 log::trace!(target: "name-resolver::expand", "expansion failed due to symbol resolution error");
515 break Err(err.into());
516 },
517 }
518 }
519 }
520 }
521
522 pub fn resolve_local(
523 &self,
524 context: &SymbolResolutionContext,
525 symbol: &str,
526 ) -> Result<SymbolResolution, Box<SymbolResolutionError>> {
527 let module = if context.in_syscall() {
528 // Resolve local names relative to the kernel
529 match self.graph.kernel_index {
530 Some(kernel) => kernel,
531 None => {
532 return Err(Box::new(SymbolResolutionError::UndefinedSymbol {
533 span: context.span,
534 source_file: self.source_manager().get(context.span.source_id()).ok(),
535 }));
536 },
537 }
538 } else {
539 context.module
540 };
541 self.resolve_local_with_index(module, Span::new(context.span, symbol))
542 }
543
544 fn resolve_local_with_index(
545 &self,
546 module: ModuleIndex,
547 symbol: Span<&str>,
548 ) -> Result<SymbolResolution, Box<SymbolResolutionError>> {
549 let module = &self.graph[module];
550 log::debug!(target: "name-resolver::local", "resolving '{symbol}' in module {}", module.path());
551 log::debug!(target: "name-resolver::local", "module status: {:?}", &module.status());
552 module.resolve(symbol, self)
553 }
554
555 #[inline]
556 pub fn module_path(&self, module: ModuleIndex) -> &Path {
557 self.graph[module].path()
558 }
559
560 pub fn item_path(&self, item: GlobalItemIndex) -> Arc<Path> {
561 let module = &self.graph[item.module];
562 let name = module[item.index].name();
563 module.path().join(name).into()
564 }
565}