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        self.invoked.insert(Invoke::new(InvokeKind::Exec, target.clone()));
172        ControlFlow::Continue(())
173    }
174    fn visit_mut_invoke_target(&mut self, target: &mut InvocationTarget) -> ControlFlow<()> {
175        let span = target.span();
176        let path = match &*target {
177            InvocationTarget::MastRoot(_) => return ControlFlow::Continue(()),
178            InvocationTarget::Path(path) => path.clone(),
179            InvocationTarget::Symbol(symbol) => {
180                Span::new(symbol.span(), PathBuf::from(symbol.clone()).into())
181            },
182        };
183        let current = self.current_procedure.as_ref().map(|p| p.as_ident());
184        if let Some(name) = path.as_ident() {
185            let name = name.with_span(span);
186            if current.is_some_and(|curr| curr == name) {
187                self.analyzer.error(SemanticAnalysisError::SelfRecursive { span });
188            } else {
189                return self.resolve_local(&name);
190            }
191        } else if path.parent().unwrap() == self.module.path()
192            && current.is_some_and(|curr| curr.as_str() == path.last().unwrap())
193        {
194            self.analyzer.error(SemanticAnalysisError::SelfRecursive { span });
195        } else if self.resolve_external(target.span(), &path).is_none() {
196            self.analyzer
197                .error(SemanticAnalysisError::MissingImport { span: target.span() });
198        }
199        ControlFlow::Continue(())
200    }
201    fn visit_mut_alias_target(&mut self, target: &mut AliasTarget) -> ControlFlow<()> {
202        match target {
203            AliasTarget::MastRoot(_) => ControlFlow::Continue(()),
204            AliasTarget::Path(path) => {
205                if path.is_absolute() {
206                    return ControlFlow::Continue(());
207                }
208
209                let Some((ns, _)) = path.split_first() else {
210                    return ControlFlow::Continue(());
211                };
212
213                if let Some(via) = self.module.get_import_mut(ns) {
214                    via.uses += 1;
215                    assert!(via.is_used());
216                }
217                ControlFlow::Continue(())
218            },
219        }
220    }
221    fn visit_mut_immediate_error_message(&mut self, code: &mut ErrorMsg) -> ControlFlow<()> {
222        if let Immediate::Constant(name) = code {
223            self.track_used_alias(name);
224        }
225        ControlFlow::Continue(())
226    }
227    fn visit_mut_immediate_felt(
228        &mut self,
229        imm: &mut Immediate<miden_core::Felt>,
230    ) -> ControlFlow<()> {
231        if let Immediate::Constant(name) = imm {
232            self.track_used_alias(name);
233        }
234        ControlFlow::Continue(())
235    }
236    fn visit_mut_immediate_u32(&mut self, imm: &mut Immediate<u32>) -> ControlFlow<()> {
237        if let Immediate::Constant(name) = imm {
238            self.track_used_alias(name);
239        }
240        ControlFlow::Continue(())
241    }
242    fn visit_mut_immediate_u16(&mut self, imm: &mut Immediate<u16>) -> ControlFlow<()> {
243        if let Immediate::Constant(name) = imm {
244            self.track_used_alias(name);
245        }
246        ControlFlow::Continue(())
247    }
248    fn visit_mut_immediate_u8(&mut self, imm: &mut Immediate<u8>) -> ControlFlow<()> {
249        if let Immediate::Constant(name) = imm {
250            self.track_used_alias(name);
251        }
252        ControlFlow::Continue(())
253    }
254    fn visit_mut_immediate_push_value(
255        &mut self,
256        imm: &mut Immediate<crate::parser::PushValue>,
257    ) -> ControlFlow<()> {
258        if let Immediate::Constant(name) = imm {
259            self.track_used_alias(name);
260        }
261        ControlFlow::Continue(())
262    }
263    fn visit_mut_immediate_word_value(
264        &mut self,
265        imm: &mut Immediate<crate::parser::WordValue>,
266    ) -> ControlFlow<()> {
267        if let Immediate::Constant(name) = imm {
268            self.track_used_alias(name);
269        }
270        ControlFlow::Continue(())
271    }
272    fn visit_mut_type_ref(&mut self, path: &mut Span<Arc<Path>>) -> ControlFlow<()> {
273        if let Some(name) = path.as_ident() {
274            self.track_used_alias(&name);
275        } else if let Some((module, _)) = path.split_first()
276            && let Some(alias) = self.module.aliases_mut().find(|a| a.name().as_str() == module)
277        {
278            alias.uses += 1;
279        }
280        ControlFlow::Continue(())
281    }
282    fn visit_mut_constant_ref(&mut self, path: &mut Span<Arc<Path>>) -> ControlFlow<()> {
283        if let Some(name) = path.as_ident() {
284            self.track_used_alias(&name);
285        } else if let Some((module, _)) = path.split_first()
286            && let Some(alias) = self.module.aliases_mut().find(|a| a.name().as_str() == module)
287        {
288            alias.uses += 1;
289        }
290        ControlFlow::Continue(())
291    }
292}
miden_assembly_syntax/sema/passes/verify_invoke.rs

miden_assembly_syntax/sema/passes/
verify_invoke.rs
