miden_assembly_syntax/sema/passes/
verify_invoke.rs

1use alloc::{boxed::Box, collections::BTreeSet, sync::Arc};
2use core::ops::ControlFlow;
3
4use miden_debug_types::{SourceSpan, Span, Spanned};
5
6use crate::{
7    PathBuf,
8    ast::*,
9    sema::{AnalysisContext, SemanticAnalysisError},
10};
11
12/// This visitor visits every `exec`, `call`, `syscall`, and `procref`, and ensures that the
13/// invocation target for that call is resolvable to the extent possible within the current
14/// module's context.
15///
16/// This means that any reference to an external module must have a corresponding import, and that
17/// the invocation kind is valid in the current module.
18///
19/// We attempt to apply as many call-related validations as we can here, however we are limited
20/// until later stages of compilation on what we can know in the context of a single module.
21/// As a result, more complex analyses are reserved until assembly.
22pub struct VerifyInvokeTargets<'a> {
23    analyzer: &'a mut AnalysisContext,
24    module: &'a mut Module,
25    procedures: &'a BTreeSet<Ident>,
26    current_procedure: Option<ProcedureName>,
27    invoked: BTreeSet<Invoke>,
28}
29
30impl<'a> VerifyInvokeTargets<'a> {
31    pub fn new(
32        analyzer: &'a mut AnalysisContext,
33        module: &'a mut Module,
34        procedures: &'a BTreeSet<Ident>,
35        current_procedure: Option<ProcedureName>,
36    ) -> Self {
37        Self {
38            analyzer,
39            module,
40            procedures,
41            current_procedure,
42            invoked: Default::default(),
43        }
44    }
45}
46
47impl VerifyInvokeTargets<'_> {
48    fn resolve_local(&mut self, name: &Ident) -> ControlFlow<()> {
49        if !self.procedures.contains(name) {
50            self.analyzer.error(SemanticAnalysisError::SymbolResolutionError(Box::new(
51                SymbolResolutionError::undefined(name.span(), &self.analyzer.source_manager()),
52            )));
53        }
54        ControlFlow::Continue(())
55    }
56    fn resolve_external(&mut self, span: SourceSpan, path: &Path) -> Option<InvocationTarget> {
57        log::debug!(target: "verify-invoke", "resolving external symbol '{path}'");
58        let Some((module, rest)) = path.split_first() else {
59            self.analyzer.error(SemanticAnalysisError::InvalidInvokePath { span });
60            return None;
61        };
62        log::debug!(target: "verify-invoke", "attempting to resolve '{module}' to local import");
63        if let Some(import) = self.module.get_import_mut(module) {
64            log::debug!(target: "verify-invoke", "found import '{}'", import.target());
65            import.uses += 1;
66            match import.target() {
67                AliasTarget::MastRoot(_) => {
68                    self.analyzer.error(SemanticAnalysisError::InvalidInvokeTargetViaImport {
69                        span,
70                        import: import.span(),
71                    });
72                    None
73                },
74                // If we have an import like `use lib::lib`, the base `lib` has been shadowed, so
75                // we cannot attempt to resolve further. Instead, we use the target path we have.
76                // In the future we may need to support exclusions from import resolution to allow
77                // chasing through shadowed imports, but we do not do that for now.
78                AliasTarget::Path(shadowed) if shadowed.as_deref() == path => {
79                    Some(InvocationTarget::Path(
80                        shadowed.as_deref().map(|p| p.to_absolute().join(rest).into()),
81                    ))
82                },
83                AliasTarget::Path(path) => {
84                    let path = path.clone();
85                    let resolved = self.resolve_external(path.span(), path.inner())?;
86                    match resolved {
87                        InvocationTarget::MastRoot(digest) => {
88                            self.analyzer.error(
89                                SemanticAnalysisError::InvalidInvokeTargetViaImport {
90                                    span,
91                                    import: digest.span(),
92                                },
93                            );
94                            None
95                        },
96                        // We can consider this path fully-resolved, and mark it absolute, if it is
97                        // not already
98                        InvocationTarget::Path(resolved) => Some(InvocationTarget::Path(
99                            resolved.with_span(span).map(|p| p.to_absolute().join(rest).into()),
100                        )),
101                        InvocationTarget::Symbol(_) => {
102                            panic!("unexpected local target resolution for alias")
103                        },
104                    }
105                },
106            }
107        } else {
108            // We can consider this path fully-resolved, and mark it absolute, if it is not already
109            Some(InvocationTarget::Path(Span::new(span, path.to_absolute().into_owned().into())))
110        }
111    }
112    fn track_used_alias(&mut self, name: &Ident) {
113        if let Some(alias) = self.module.aliases_mut().find(|a| a.name() == name) {
114            alias.uses += 1;
115        }
116    }
117}
118
119impl VisitMut for VerifyInvokeTargets<'_> {
120    fn visit_mut_alias(&mut self, alias: &mut Alias) -> ControlFlow<()> {
121        if alias.visibility().is_public() {
122            // Mark all public aliases as used
123            alias.uses += 1;
124            assert!(alias.is_used());
125        }
126        self.visit_mut_alias_target(alias.target_mut())
127    }
128    fn visit_mut_procedure(&mut self, procedure: &mut Procedure) -> ControlFlow<()> {
129        let result = visit::visit_mut_procedure(self, procedure);
130        procedure.extend_invoked(core::mem::take(&mut self.invoked));
131        result
132    }
133    fn visit_mut_syscall(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
134        match target {
135            // Syscalls to a local name will be rewritten to refer to implicit exports of the
136            // kernel module.
137            InvocationTarget::Symbol(name) => {
138                let span = name.span();
139                let path = Path::kernel_path().join(name).into();
140                *target = InvocationTarget::Path(Span::new(span, path));
141            },
142            // Syscalls which reference a path, are only valid if the module id is $kernel
143            InvocationTarget::Path(path) => {
144                let span = path.span();
145                if let Some(name) = path.as_ident() {
146                    let new_path = Path::kernel_path().join(&name).into();
147                    *path = Span::new(span, new_path);
148                } else {
149                    self.analyzer.error(SemanticAnalysisError::InvalidSyscallTarget { span });
150                }
151            },
152            // We assume that a syscall specifying a MAST root knows what it is doing, but this
153            // will be validated by the assembler
154            InvocationTarget::MastRoot(_) => (),
155        }
156        self.invoked.insert(Invoke::new(InvokeKind::SysCall, target.clone()));
157        ControlFlow::Continue(())
158    }
159    fn visit_mut_call(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
160        self.visit_mut_invoke_target(target)?;
161        self.invoked.insert(Invoke::new(InvokeKind::Call, target.clone()));
162        ControlFlow::Continue(())
163    }
164    fn visit_mut_exec(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
165        self.visit_mut_invoke_target(target)?;
166        self.invoked.insert(Invoke::new(InvokeKind::Exec, target.clone()));
167        ControlFlow::Continue(())
168    }
169    fn visit_mut_procref(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
170        self.visit_mut_invoke_target(target)?;
171        // We intentionally use `InvokeKind::Exec` here rather than `InvokeKind::ProcRef`.
172        // A `procref` instruction captures a procedure reference for *later* invocation,
173        // but we must pessimistically treat it as an actual invocation because we cannot
174        // know the specific call kind at this point. `Exec` is the most general invocation
175        // kind, and the linker relies on this signal to correctly track procedure
176        // dependencies. Using `ProcRef` would only indicate "named somewhere" and would
177        // not carry the full weight of "this procedure is invoked".
178        self.invoked.insert(Invoke::new(InvokeKind::Exec, target.clone()));
179        ControlFlow::Continue(())
180    }
181    fn visit_mut_invoke_target(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
182        let span = target.span();
183        let path = match &*target {
184            InvocationTarget::MastRoot(_) => return ControlFlow::Continue(()),
185            InvocationTarget::Path(path) => path.clone(),
186            InvocationTarget::Symbol(symbol) => {
187                Span::new(symbol.span(), PathBuf::from(symbol.clone()).into())
188            },
189        };
190        let current = self.current_procedure.as_ref().map(|p| p.as_ident());
191        if let Some(name) = path.as_ident() {
192            let name = name.with_span(span);
193            if current.is_some_and(|curr| curr == name) {
194                self.analyzer.error(SemanticAnalysisError::SelfRecursive { span });
195            } else {
196                return self.resolve_local(&name);
197            }
198        } else if path.parent().unwrap() == self.module.path()
199            && current.is_some_and(|curr| curr.as_str() == path.last().unwrap())
200        {
201            self.analyzer.error(SemanticAnalysisError::SelfRecursive { span });
202        } else if self.resolve_external(target.span(), &path).is_none() {
203            self.analyzer
204                .error(SemanticAnalysisError::MissingImport { span: target.span() });
205        }
206        ControlFlow::Continue(())
207    }
208    fn visit_mut_alias_target(&mut self, target: &mut AliasTarget) -> ControlFlow<()> {
209        match target {
210            AliasTarget::MastRoot(_) => ControlFlow::Continue(()),
211            AliasTarget::Path(path) => {
212                if path.is_absolute() {
213                    return ControlFlow::Continue(());
214                }
215
216                let Some((ns, _)) = path.split_first() else {
217                    return ControlFlow::Continue(());
218                };
219
220                if let Some(via) = self.module.get_import_mut(ns) {
221                    via.uses += 1;
222                    assert!(via.is_used());
223                }
224                ControlFlow::Continue(())
225            },
226        }
227    }
228    fn visit_mut_immediate_error_message(&mut self, code: &mut ErrorMsg) -> ControlFlow<()> {
229        if let Immediate::Constant(name) = code {
230            self.track_used_alias(name);
231        }
232        ControlFlow::Continue(())
233    }
234    fn visit_mut_immediate_felt(
235        &mut self,
236        imm: &mut Immediate<miden_core::Felt>,
237    ) -> ControlFlow<()> {
238        if let Immediate::Constant(name) = imm {
239            self.track_used_alias(name);
240        }
241        ControlFlow::Continue(())
242    }
243    fn visit_mut_immediate_u32(&mut self, imm: &mut Immediate<u32>) -> ControlFlow<()> {
244        if let Immediate::Constant(name) = imm {
245            self.track_used_alias(name);
246        }
247        ControlFlow::Continue(())
248    }
249    fn visit_mut_immediate_u16(&mut self, imm: &mut Immediate<u16>) -> ControlFlow<()> {
250        if let Immediate::Constant(name) = imm {
251            self.track_used_alias(name);
252        }
253        ControlFlow::Continue(())
254    }
255    fn visit_mut_immediate_u8(&mut self, imm: &mut Immediate<u8>) -> ControlFlow<()> {
256        if let Immediate::Constant(name) = imm {
257            self.track_used_alias(name);
258        }
259        ControlFlow::Continue(())
260    }
261    fn visit_mut_immediate_push_value(
262        &mut self,
263        imm: &mut Immediate<crate::parser::PushValue>,
264    ) -> ControlFlow<()> {
265        if let Immediate::Constant(name) = imm {
266            self.track_used_alias(name);
267        }
268        ControlFlow::Continue(())
269    }
270    fn visit_mut_immediate_word_value(
271        &mut self,
272        imm: &mut Immediate<crate::parser::WordValue>,
273    ) -> ControlFlow<()> {
274        if let Immediate::Constant(name) = imm {
275            self.track_used_alias(name);
276        }
277        ControlFlow::Continue(())
278    }
279    fn visit_mut_type_ref(&mut self, path: &mut Span<Arc<Path>>) -> ControlFlow<()> {
280        if let Some(name) = path.as_ident() {
281            self.track_used_alias(&name);
282        } else if let Some((module, _)) = path.split_first()
283            && let Some(alias) = self.module.aliases_mut().find(|a| a.name().as_str() == module)
284        {
285            alias.uses += 1;
286        }
287        ControlFlow::Continue(())
288    }
289    fn visit_mut_constant_ref(&mut self, path: &mut Span<Arc<Path>>) -> ControlFlow<()> {
290        if let Some(name) = path.as_ident() {
291            self.track_used_alias(&name);
292        } else if let Some((module, _)) = path.split_first()
293            && let Some(alias) = self.module.aliases_mut().find(|a| a.name().as_str() == module)
294        {
295            alias.uses += 1;
296        }
297        ControlFlow::Continue(())
298    }
299}
miden_assembly_syntax/sema/passes/verify_invoke.rs

miden_assembly_syntax/sema/passes/
verify_invoke.rs
