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

miden_assembly_syntax/sema/passes/
verify_invoke.rs
