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