miden_assembly_syntax/sema/
mod.rs

1mod context;
2mod errors;
3mod passes;
4#[cfg(test)]
5mod tests;
6
7use alloc::{
8    boxed::Box,
9    collections::{BTreeSet, VecDeque},
10    sync::Arc,
11    vec::Vec,
12};
13
14use miden_core::{Word, crypto::hash::Poseidon2};
15use miden_debug_types::{SourceFile, SourceManager, Span, Spanned};
16use smallvec::SmallVec;
17
18pub use self::{
19    context::AnalysisContext,
20    errors::{SemanticAnalysisError, SyntaxError},
21    passes::{ConstEvalVisitor, VerifyInvokeTargets, VerifyRepeatCounts},
22};
23use crate::{ast::*, parser::WordValue};
24
25/// Constructs and validates a [Module], given the forms constituting the module body.
26///
27/// As part of this process, the following is also done:
28///
29/// * Documentation comments are attached to items they decorate
30/// * Import table is constructed
31/// * Symbol resolution is performed:
32///   * Constants referenced by name are replaced with the value of that constant.
33///   * Calls to imported procedures are resolved concretely
34/// * Semantic analysis is performed on the module to validate it
35pub fn analyze(
36    source: Arc<SourceFile>,
37    kind: ModuleKind,
38    path: &Path,
39    forms: Vec<Form>,
40    warnings_as_errors: bool,
41    source_manager: Arc<dyn SourceManager>,
42) -> Result<Box<Module>, SyntaxError> {
43    log::debug!(target: "sema", "starting semantic analysis for '{path}' (kind = {kind})");
44    let mut analyzer = AnalysisContext::new(source.clone(), source_manager);
45    analyzer.set_warnings_as_errors(warnings_as_errors);
46
47    let mut module = Box::new(Module::new(kind, path).with_span(source.source_span()));
48
49    let mut forms = VecDeque::from(forms);
50    let mut enums = SmallVec::<[EnumType; 1]>::new_const();
51    let mut docs = None;
52    while let Some(form) = forms.pop_front() {
53        match form {
54            Form::ModuleDoc(docstring) => {
55                assert!(docs.is_none());
56                module.set_docs(Some(docstring));
57            },
58            Form::Doc(docstring) => {
59                if let Some(unused) = docs.replace(docstring) {
60                    analyzer.error(SemanticAnalysisError::UnusedDocstring { span: unused.span() });
61                }
62            },
63            Form::Type(ty) => {
64                if let Err(err) = module.define_type(ty.with_docs(docs.take())) {
65                    analyzer.error(err);
66                }
67            },
68            Form::Enum(ty) => {
69                // Ensure the constants defined by the enum are made known to the analyzer
70                for variant in ty.variants() {
71                    let Variant { span, name, discriminant, .. } = variant;
72                    analyzer.register_constant(Constant {
73                        span: *span,
74                        docs: None,
75                        visibility: ty.visibility(),
76                        name: name.clone(),
77                        value: discriminant.clone(),
78                    });
79                }
80
81                // Defer definition of the enum until we discover all constants
82                enums.push(ty.with_docs(docs.take()));
83            },
84            Form::Constant(constant) => {
85                analyzer.define_constant(&mut module, constant.with_docs(docs.take()));
86            },
87            Form::Alias(item) if item.visibility().is_public() => match kind {
88                ModuleKind::Kernel if module.is_kernel() => {
89                    docs.take();
90                    analyzer.error(SemanticAnalysisError::ReexportFromKernel { span: item.span() });
91                },
92                ModuleKind::Executable => {
93                    docs.take();
94                    analyzer.error(SemanticAnalysisError::UnexpectedExport { span: item.span() });
95                },
96                _ => {
97                    define_alias(item.with_docs(docs.take()), &mut module, &mut analyzer)?;
98                },
99            },
100            Form::Alias(item) => {
101                define_alias(item.with_docs(docs.take()), &mut module, &mut analyzer)?
102            },
103            Form::Procedure(export) => match kind {
104                ModuleKind::Executable
105                    if export.visibility().is_public() && !export.is_entrypoint() =>
106                {
107                    docs.take();
108                    analyzer.error(SemanticAnalysisError::UnexpectedExport { span: export.span() });
109                },
110                _ => {
111                    define_procedure(export.with_docs(docs.take()), &mut module, &mut analyzer)?;
112                },
113            },
114            Form::Begin(body) if matches!(kind, ModuleKind::Executable) => {
115                let docs = docs.take();
116                let procedure =
117                    Procedure::new(body.span(), Visibility::Public, ProcedureName::main(), 0, body)
118                        .with_docs(docs);
119                define_procedure(procedure, &mut module, &mut analyzer)?;
120            },
121            Form::Begin(body) => {
122                docs.take();
123                analyzer.error(SemanticAnalysisError::UnexpectedEntrypoint { span: body.span() });
124            },
125            Form::AdviceMapEntry(entry) => {
126                add_advice_map_entry(&mut module, entry.with_docs(docs.take()), &mut analyzer)?;
127            },
128        }
129    }
130
131    if let Some(unused) = docs.take() {
132        analyzer.error(SemanticAnalysisError::UnusedDocstring { span: unused.span() });
133    }
134
135    // Simplify all constant declarations
136    analyzer.simplify_constants();
137    for item in module.items_mut().iter_mut() {
138        let Export::Constant(constant) = item else {
139            continue;
140        };
141        constant.value = analyzer
142            .get_constant(&constant.name)
143            .expect("semantic analysis tracks all module constants")
144            .clone();
145    }
146
147    // Define enums now that all constant declarations have been discovered
148    for mut ty in enums {
149        for variant in ty.variants_mut() {
150            variant.discriminant = analyzer.get_constant(&variant.name).unwrap().clone();
151        }
152
153        if let Err(err) = module.define_enum(ty) {
154            analyzer.error(err);
155        }
156    }
157
158    if matches!(kind, ModuleKind::Executable) && !module.has_entrypoint() {
159        analyzer.error(SemanticAnalysisError::MissingEntrypoint);
160    }
161
162    analyzer.has_failed()?;
163
164    // Run item checks
165    visit_items(&mut module, &mut analyzer)?;
166
167    // Check unused imports
168    for import in module.aliases() {
169        if !import.is_used() {
170            analyzer.error(SemanticAnalysisError::UnusedImport { span: import.span() });
171        }
172    }
173
174    analyzer.into_result().map(move |_| module)
175}
176
177/// Visit all of the items of the current analysis context, and apply various transformation and
178/// analysis passes.
179///
180/// When this function returns, all local analysis is complete, and all that remains is construction
181/// of a module graph and global program analysis to perform any remaining transformations.
182fn visit_items(module: &mut Module, analyzer: &mut AnalysisContext) -> Result<(), SyntaxError> {
183    let is_kernel = module.is_kernel();
184    let locals = BTreeSet::from_iter(module.items().iter().map(|p| p.name().clone()));
185    let mut items = VecDeque::from(core::mem::take(&mut module.items));
186    while let Some(item) = items.pop_front() {
187        match item {
188            Export::Procedure(mut procedure) => {
189                // Rewrite visibility for exported kernel procedures
190                if is_kernel && procedure.visibility().is_public() {
191                    procedure.set_syscall(true);
192                }
193
194                // Evaluate all named immediates to their concrete values
195                log::debug!(target: "const-eval", "visiting procedure {}", procedure.name());
196                {
197                    let mut visitor = ConstEvalVisitor::new(analyzer);
198                    let _ = visitor.visit_mut_procedure(&mut procedure);
199                    if let Err(errs) = visitor.into_result() {
200                        for err in errs {
201                            log::error!(target: "const-eval", "error found in procedure {}: {err}", procedure.name());
202                            analyzer.error(err);
203                        }
204                    }
205                }
206
207                // Ensure repeat counts are within acceptable bounds.
208                log::debug!(target: "verify-repeat", "visiting procedure {}", procedure.name());
209                {
210                    let mut visitor = VerifyRepeatCounts::new(analyzer);
211                    let _ = visitor.visit_procedure(&procedure);
212                }
213
214                // Next, verify invoke targets:
215                //
216                // * Mark imports as used if they have at least one call to a procedure defined in
217                //   that module
218                // * Verify that all external callees have a matching import
219                log::debug!(target: "verify-invoke", "visiting procedure {}", procedure.name());
220                {
221                    let mut visitor = VerifyInvokeTargets::new(
222                        analyzer,
223                        module,
224                        &locals,
225                        Some(procedure.name().clone()),
226                    );
227                    let _ = visitor.visit_mut_procedure(&mut procedure);
228                }
229                module.items.push(Export::Procedure(procedure));
230            },
231            Export::Alias(mut alias) => {
232                log::debug!(target: "verify-invoke", "visiting alias {}", alias.target());
233                {
234                    let mut visitor = VerifyInvokeTargets::new(analyzer, module, &locals, None);
235                    let _ = visitor.visit_mut_alias(&mut alias);
236                }
237                module.items.push(Export::Alias(alias));
238            },
239            Export::Constant(mut constant) => {
240                log::debug!(target: "verify-invoke", "visiting constant {}", constant.name());
241                {
242                    let mut visitor = VerifyInvokeTargets::new(analyzer, module, &locals, None);
243                    let _ = visitor.visit_mut_constant(&mut constant);
244                }
245                module.items.push(Export::Constant(constant));
246            },
247            Export::Type(mut ty) => {
248                log::debug!(target: "verify-invoke", "visiting type {}", ty.name());
249                {
250                    let mut visitor = VerifyInvokeTargets::new(analyzer, module, &locals, None);
251                    let _ = visitor.visit_mut_type_decl(&mut ty);
252                }
253                module.items.push(Export::Type(ty));
254            },
255        }
256    }
257
258    Ok(())
259}
260
261fn define_alias(
262    item: Alias,
263    module: &mut Module,
264    context: &mut AnalysisContext,
265) -> Result<(), SyntaxError> {
266    let name = item.name().clone();
267    if let Err(err) = module.define_alias(item, context.source_manager()) {
268        match err {
269            SemanticAnalysisError::SymbolConflict { .. } => {
270                // Proceed anyway, to try and capture more errors
271                context.error(err);
272            },
273            err => {
274                // We can't proceed without producing a bunch of errors
275                context.error(err);
276                context.has_failed()?;
277            },
278        }
279    }
280
281    context.register_imported_name(name);
282
283    Ok(())
284}
285
286fn define_procedure(
287    procedure: Procedure,
288    module: &mut Module,
289    context: &mut AnalysisContext,
290) -> Result<(), SyntaxError> {
291    let name = procedure.name().clone();
292    if let Err(err) = module.define_procedure(procedure, context.source_manager()) {
293        match err {
294            SemanticAnalysisError::SymbolConflict { .. } => {
295                // Proceed anyway, to try and capture more errors
296                context.error(err);
297            },
298            err => {
299                // We can't proceed without producing a bunch of errors
300                context.error(err);
301                context.has_failed()?;
302            },
303        }
304    }
305
306    context.register_procedure_name(name);
307
308    Ok(())
309}
310
311/// Inserts a new entry in the Advice Map and defines a constant corresposnding to the entry's
312/// key.
313///
314/// Returns `Err` if the symbol is already defined
315fn add_advice_map_entry(
316    module: &mut Module,
317    entry: AdviceMapEntry,
318    context: &mut AnalysisContext,
319) -> Result<(), SyntaxError> {
320    let key = match entry.key {
321        Some(key) => Word::from(key.inner().0),
322        None => Poseidon2::hash_elements(&entry.value),
323    };
324    let cst = Constant::new(
325        entry.span,
326        Visibility::Private,
327        entry.name.clone(),
328        ConstantExpr::Word(Span::new(entry.span, WordValue(*key))),
329    );
330    context.define_constant(module, cst);
331    match module.advice_map.get(&key) {
332        Some(_) => {
333            context.error(SemanticAnalysisError::AdvMapKeyAlreadyDefined { span: entry.span });
334        },
335        None => {
336            module.advice_map.insert(key, entry.value);
337        },
338    }
339    Ok(())
340}
miden_assembly_syntax/sema/mod.rs

miden_assembly_syntax/sema/
mod.rs
