miden_assembly/
assembler.rs

1pub(super) mod debuginfo;
2pub(crate) mod error;
3mod product;
4
5use alloc::{
6    boxed::Box,
7    collections::{BTreeMap, BTreeSet},
8    string::ToString,
9    sync::Arc,
10    vec::Vec,
11};
12
13use debuginfo::DebugInfoSections;
14use miden_assembly_syntax::{
15    ExportedTypeUse, MAX_REPEAT_COUNT, Parse, SemanticAnalysisError,
16    ast::{
17        self, AttributeSet, Ident, InvocationTarget, InvokeKind, ItemIndex, ModuleKind,
18        SymbolResolution, Visibility, types::FunctionType,
19    },
20    debuginfo::{DefaultSourceManager, SourceManager, SourceSpan, Spanned},
21    diagnostics::{IntoDiagnostic, RelatedLabel, Report},
22    module::ItemInfo,
23};
24use miden_core::{
25    WORD_SIZE, Word,
26    mast::{MastNodeExt, MastNodeId},
27    operations::{AssemblyOp, Operation},
28    program::Kernel,
29    serde::Serializable,
30};
31use miden_mast_package::{
32    ConstantExport, Package, PackageDebugInfoError, PackageExport, PackageId, PackageModule,
33    PackageSubmodule, ProcedureExport, Section, SectionId, TypeExport,
34    debug_info::DebugSourceNodeId,
35};
36use miden_project::{Linkage, TargetType};
37
38use self::{error::AssemblerError, product::AssemblyProduct};
39use crate::{
40    GlobalItemIndex, ModuleIndex, Procedure, ProcedureContext,
41    ast::Path,
42    basic_block_builder::BasicBlockBuilder,
43    fmp::{fmp_end_frame_sequence, fmp_initialization_sequence, fmp_start_frame_sequence},
44    linker::{
45        Import, LinkLibrary, Linker, LinkerError, SymbolItem, SymbolResolutionContext,
46        SymbolResolver,
47    },
48    mast_forest_builder::{
49        MastForestBuilder, MastNodeRef, SourceDebugGraph, SourceNodeId, SourceNodeRef,
50        StaticLibrary,
51    },
52};
53
54/// Maximum allowed nesting of control-flow blocks during compilation.
55///
56/// This limit is intended to prevent stack overflows from maliciously deep block nesting while
57/// remaining far above typical program structure depth.
58pub(crate) const MAX_CONTROL_FLOW_NESTING: usize = 256;
59
60/// Maximum number of locals a single procedure may allocate.
61///
62/// When emitting the frame-pointer sequence, the local count is rounded up to the nearest multiple
63/// of word size. To keep that rounding from overflowing the u16 frame counter, the
64/// maximum must itself be a multiple of word size. This mirrors the limit the assembly parser
65/// enforces on the @locals(..) attribute.
66pub(crate) const MAX_PROC_LOCALS: u16 = (u16::MAX / WORD_SIZE as u16) * WORD_SIZE as u16;
67
68#[derive(Debug)]
69enum PendingPackageExport {
70    Procedure(PendingProcedureExport),
71    Constant(ConstantExport),
72    Type(TypeExport),
73}
74
75#[derive(Debug)]
76struct PendingProcedureExport {
77    node_ref: MastNodeRef,
78    source_ref: Option<SourceNodeRef>,
79    digest: Word,
80    path: Arc<Path>,
81    signature: Option<FunctionType>,
82    attributes: AttributeSet,
83}
84
85impl PendingPackageExport {
86    fn into_package_export(
87        self,
88        node_id_by_ref: &BTreeMap<MastNodeRef, MastNodeId>,
89        source_id_by_ref: &BTreeMap<SourceNodeRef, SourceNodeId>,
90    ) -> Result<PackageExport, Report> {
91        match self {
92            Self::Procedure(export) => export.into_package_export(node_id_by_ref, source_id_by_ref),
93            Self::Constant(export) => Ok(PackageExport::Constant(export)),
94            Self::Type(export) => Ok(PackageExport::Type(export)),
95        }
96    }
97}
98
99impl PendingProcedureExport {
100    fn into_package_export(
101        self,
102        node_id_by_ref: &BTreeMap<MastNodeRef, MastNodeId>,
103        source_id_by_ref: &BTreeMap<SourceNodeRef, SourceNodeId>,
104    ) -> Result<PackageExport, Report> {
105        let node = node_id_by_ref.get(&self.node_ref).copied().ok_or_else(|| {
106            Report::msg(format!("procedure export ref {} was not finalized", self.node_ref))
107        })?;
108        let source_node = self
109            .source_ref
110            .and_then(|source_ref| source_id_by_ref.get(&source_ref).copied())
111            .map(|source_id| DebugSourceNodeId::from(u32::from(source_id)));
112        Ok(PackageExport::Procedure(ProcedureExport {
113            digest: self.digest,
114            path: self.path,
115            node: Some(node),
116            source_node,
117            signature: self.signature,
118            attributes: self.attributes,
119        }))
120    }
121}
122
123// ASSEMBLER
124// ================================================================================================
125
126/// The [Assembler] produces a _Merkelized Abstract Syntax Tree (MAST)_ from Miden Assembly sources,
127/// as a [`Package`] artifact. In general, packages come in three primary varieties:
128///
129/// * A kernel library (i.e. [`TargetType::Kernel`])
130/// * A program (see [`TargetType::Executable`])
131/// * A library (all other target types)
132///
133/// Assembled artifacts can additionally reference or include code from previously assembled
134/// libraries.
135///
136/// # Usage
137///
138/// Depending on your needs, there are multiple ways of using the assembler, starting with the
139/// type of artifact you want to produce:
140///
141/// * If you wish to produce an executable program, you will call [`Self::assemble_program`] with
142///   the source module which contains the program entrypoint.
143/// * If you wish to produce a library for use in other executables, you will call
144///   [`Self::assemble_library`] with the source module(s) whose exports form the public API of the
145///   library.
146/// * If you wish to produce a kernel library, you will call [`Self::assemble_kernel`] with the
147///   source module(s) whose exports form the public API of the kernel.
148///
149/// In the case where you are assembling a library or program, you also need to determine if you
150/// need to specify a kernel. You will need to do so if any of your code needs to call into the
151/// kernel directly.
152///
153/// * If a kernel is needed, you should construct an `Assembler` using [`Assembler::with_kernel`]
154/// * Otherwise, you should construct an `Assembler` using [`Assembler::new`]
155///
156/// <div class="warning">
157/// Programs compiled with an empty kernel cannot use the `syscall` instruction.
158/// </div>
159///
160/// Lastly, you need to provide inputs to the assembler which it will use at link time to resolve
161/// references to procedures which are externally-defined (i.e. not defined in any of the modules
162/// provided to the `assemble_*` function you called). There are a few different ways to do this:
163///
164/// * If you have source code, or a [`ast::Module`], see [`Self::compile_and_statically_link`]
165/// * If you need to reference procedures from a previously assembled package, but do not want to
166///   include the MAST of those procedures in the assembled artifact, you want to _dynamically link_
167///   that library, see [`Linkage::Dynamic`] for more.
168/// * If you want to incorporate referenced procedures from a previously assembled package into the
169///   assembled artifact, you want to _statically link_ that library, see [`Linkage::Static`] for
170///   more.
171#[derive(Clone)]
172pub struct Assembler {
173    /// The source manager to use for compilation and source location information
174    source_manager: Arc<dyn SourceManager>,
175    /// The linker instance used internally to link assembler inputs
176    linker: Box<Linker>,
177    /// The debug information gathered during assembly
178    pub(super) debug_info: DebugInfoSections,
179    /// Whether to treat warning diagnostics as errors
180    warnings_as_errors: bool,
181    /// Whether to preserve debug information in the assembled artifact.
182    pub(super) emit_debug_info: bool,
183    /// Whether to trim source file paths in debug information.
184    pub(super) trim_paths: bool,
185}
186
187impl Default for Assembler {
188    fn default() -> Self {
189        let source_manager = Arc::new(DefaultSourceManager::default());
190        let linker = Box::new(Linker::new(source_manager.clone()));
191        Self {
192            source_manager,
193            linker,
194            debug_info: Default::default(),
195            warnings_as_errors: false,
196            emit_debug_info: true,
197            trim_paths: false,
198        }
199    }
200}
201
202// ------------------------------------------------------------------------------------------------
203/// Constructors
204impl Assembler {
205    /// Start building an [Assembler]
206    pub fn new(source_manager: Arc<dyn SourceManager>) -> Self {
207        let linker = Box::new(Linker::new(source_manager.clone()));
208        Self {
209            source_manager,
210            linker,
211            debug_info: Default::default(),
212            warnings_as_errors: false,
213            emit_debug_info: true,
214            trim_paths: false,
215        }
216    }
217
218    /// Start building an [`Assembler`] with a kernel defined by the provided kernel package.
219    pub fn with_kernel(
220        source_manager: Arc<dyn SourceManager>,
221        kernel: Arc<Package>,
222    ) -> Result<Self, Report> {
223        let linker = Box::new(Linker::with_kernel(source_manager.clone(), kernel)?);
224        Ok(Self {
225            source_manager,
226            linker,
227            ..Default::default()
228        })
229    }
230
231    /// Sets the default behavior of this assembler with regard to warning diagnostics.
232    ///
233    /// When true, any warning diagnostics that are emitted will be promoted to errors.
234    pub fn with_warnings_as_errors(mut self, yes: bool) -> Self {
235        self.warnings_as_errors = yes;
236        self
237    }
238
239    #[cfg(feature = "std")]
240    pub(crate) fn with_emit_debug_info(mut self, yes: bool) -> Self {
241        self.emit_debug_info = yes;
242        self
243    }
244
245    #[cfg(feature = "std")]
246    pub(crate) fn with_trim_paths(mut self, yes: bool) -> Self {
247        self.trim_paths = yes;
248        self
249    }
250}
251
252// ------------------------------------------------------------------------------------------------
253/// Dependency Management
254impl Assembler {
255    /// Ensures `module` is compiled, and then statically links it into the final artifact.
256    ///
257    /// The given module must be a library module, or an error will be returned.
258    #[inline]
259    pub fn compile_and_statically_link(&mut self, module: impl Parse) -> Result<&mut Self, Report> {
260        self.compile_and_statically_link_all([module])
261    }
262
263    /// Ensures every module in `modules` is compiled, and then statically links them into the final
264    /// artifact.
265    ///
266    /// All of the given modules must be library modules, or an error will be returned.
267    pub fn compile_and_statically_link_all(
268        &mut self,
269        modules: impl IntoIterator<Item = impl Parse>,
270    ) -> Result<&mut Self, Report> {
271        let modules = modules
272            .into_iter()
273            .map(|module| module.parse(self.warnings_as_errors, self.source_manager.clone()))
274            .collect::<Result<Vec<_>, Report>>()?;
275
276        self.linker.link_modules(modules)?;
277
278        Ok(self)
279    }
280
281    /// Compiles and statically links all Miden Assembly modules reachable from the provided root
282    /// module. The namespace of the resulting modules will be derived from an explicit namespace
283    /// declaration in the root module, or from `namespace` if provided - if both are present, they
284    /// must agree.
285    ///
286    /// The module structure is determined by `mod` declarations reachable from the root module,
287    /// i.e. if the root module contains the line `mod foo`, then a submodule `foo` in the namespace
288    /// of the root module will be located and parsed.
289    ///
290    /// If provided `namespace` can be any valid Miden Assembly path, e.g. `std` is a valid path, as
291    /// is `std::math::u64` - there is no requirement that the namespace be a single identifier.
292    /// This allows defining multiple projects relative to a common root namespace without conflict.
293    ///
294    /// For example, let's say I call this function like so:
295    ///
296    /// ```rust
297    /// use miden_assembly::{Assembler, Path};
298    ///
299    /// let mut assembler = Assembler::default();
300    /// assembler.compile_and_statically_link_from_root("~/masm/core/lib.masm", None);
301    /// ```
302    ///
303    /// And `lib.masm` contains:
304    ///
305    /// ```text,ignore
306    /// namespace miden::core
307    ///
308    /// pub mod sys;
309    /// pub mod math;
310    /// ```
311    ///
312    /// Then either of the following directory layouts would be parsed successfully, with the
313    /// namespacing shown:
314    ///
315    /// Layout 1: Submodules are defined at the same level as the parent, named after their module
316    /// name:
317    ///
318    /// - ~/masm/core/lib.masm        -> Parsed as "miden::core"
319    /// - ~/masm/core/sys.masm        -> Parsed as "miden::core::sys"
320    /// - ~/masm/core/math.masm       -> Parsed as "miden::core::math"
321    /// - ~/masm/core/math/README.md  -> Ignored
322    ///
323    /// Layout 2: Submodules are defined in sub-directories named after their module name:
324    ///
325    /// - ~/masm/core/lib.masm        -> Parsed as "miden::core"
326    /// - ~/masm/core/sys/mod.masm    -> Parsed as "miden::core::sys"
327    /// - ~/masm/core/math/mod.masm   -> Parsed as "miden::core::math"
328    /// - ~/masm/core/math/README.md  -> Ignored
329    #[cfg(feature = "std")]
330    pub fn compile_and_statically_link_from_root(
331        &mut self,
332        root: impl AsRef<std::path::Path>,
333        namespace: Option<&Path>,
334    ) -> Result<(), Report> {
335        use miden_assembly_syntax::parser;
336
337        let (root, modules) = parser::read_modules_from_root(
338            root,
339            namespace.map(Into::into),
340            None,
341            self.source_manager.clone(),
342            self.warnings_as_errors,
343        )?;
344        self.linker.link_modules(core::iter::once(root).chain(modules))?;
345        Ok(())
346    }
347
348    /// Link against `package` with the specified linkage mode during assembly.
349    pub fn with_package(mut self, package: Arc<Package>, linkage: Linkage) -> Result<Self, Report> {
350        self.link_package(package, linkage)?;
351        Ok(self)
352    }
353
354    /// Link against `package` with the specified linkage mode during assembly.
355    pub fn link_package(&mut self, package: Arc<Package>, linkage: Linkage) -> Result<(), Report> {
356        match package.kind {
357            TargetType::Kernel => {
358                if !self.kernel().is_empty() {
359                    return Err(Report::msg(format!(
360                        "duplicate kernels present in the dependency graph: '{}@{}' conflicts with another kernel we've already linked",
361                        package.name, package.version
362                    )));
363                }
364
365                self.linker.link_with_kernel(package)?;
366                Ok(())
367            },
368            TargetType::Executable => {
369                Err(Report::msg("cannot add executable packages to an assembler"))
370            },
371            _ => {
372                self.linker
373                    .link_library(LinkLibrary::from_package(package).with_linkage(linkage))?;
374                Ok(())
375            },
376        }
377    }
378}
379
380// ------------------------------------------------------------------------------------------------
381/// Public Accessors
382impl Assembler {
383    /// Returns true if this assembler promotes warning diagnostics as errors by default.
384    pub fn warnings_as_errors(&self) -> bool {
385        self.warnings_as_errors
386    }
387
388    /// Returns a reference to the kernel for this assembler.
389    ///
390    /// If the assembler was instantiated without a kernel, the internal kernel will be empty.
391    pub fn kernel(&self) -> &Kernel {
392        self.linker.kernel()
393    }
394
395    #[cfg(any(feature = "std", all(test, feature = "std")))]
396    pub(crate) fn source_manager(&self) -> Arc<dyn SourceManager> {
397        self.source_manager.clone()
398    }
399
400    #[cfg(any(test, feature = "testing"))]
401    #[doc(hidden)]
402    pub fn linker(&self) -> &Linker {
403        &self.linker
404    }
405}
406
407// ------------------------------------------------------------------------------------------------
408/// Compilation/Assembly
409impl Assembler {
410    /// Assembles a root module, and its supporting submodules into a library [`Package`].
411    ///
412    /// # Errors
413    ///
414    /// Returns an error if parsing or compilation of the specified modules fails.
415    pub fn assemble_library(
416        self,
417        name: impl Into<PackageId>,
418        root: impl Parse,
419        support: impl IntoIterator<Item = impl Parse>,
420    ) -> Result<Box<Package>, Report> {
421        let root = root.parse(self.warnings_as_errors, self.source_manager.clone())?;
422        let support = support
423            .into_iter()
424            .map(|module| module.parse(self.warnings_as_errors, self.source_manager.clone()))
425            .collect::<Result<Vec<_>, Report>>()?;
426
427        self.assemble_library_modules(name.into(), root, support, TargetType::Library)?
428            .into_artifact()
429    }
430
431    /// Assemble a library [`Package`] from the set of modules reachable from `root`.
432    ///
433    /// See [Assembler::compile_and_statically_link_from_root] for details on how modules are
434    /// discovered and linked from `root`.
435    #[cfg(feature = "std")]
436    pub fn assemble_library_from_root(
437        self,
438        root: impl AsRef<std::path::Path>,
439        namespace: Option<&Path>,
440    ) -> Result<Box<Package>, Report> {
441        use miden_assembly_syntax::parser;
442
443        let root = root.as_ref().to_path_buf();
444        let namespace = namespace.map(Into::into);
445        let (root, support) = parser::read_modules_from_root(
446            &root,
447            namespace,
448            Some(ModuleKind::Library),
449            self.source_manager.clone(),
450            self.warnings_as_errors,
451        )?;
452
453        // Derive the package name from the namespace of the root module
454        let name = root.path().as_str().replace("::", "-");
455
456        self.assemble_library_modules(name.into(), root, support, TargetType::Library)?
457            .into_artifact()
458    }
459
460    /// Assembles the provided module into a kernel package.
461    ///
462    /// # Errors
463    ///
464    /// Returns an error if parsing or compilation of the specified modules fails.
465    pub fn assemble_kernel(
466        self,
467        name: impl Into<PackageId>,
468        root: Box<ast::Module>,
469        support: impl IntoIterator<Item = Box<ast::Module>>,
470    ) -> Result<Box<Package>, Report> {
471        self.assemble_library_modules(name.into(), root, support, TargetType::Kernel)?
472            .into_artifact()
473    }
474
475    /// Assemble a kernel [`Package`] from a standard Miden Assembly kernel project layout.
476    ///
477    /// The kernel library will export procedures defined by the module at `sys_module_path`.
478    ///
479    /// If the optional `lib_dir` is provided, all modules under this directory will be available
480    /// from the kernel module under the `$kernel` namespace. For example, if `lib_dir` is set to
481    /// "~/masm/lib", the files will be accessible in the kernel module as follows:
482    ///
483    /// - ~/masm/lib/foo.masm        -> Can be imported as "$kernel::foo"
484    /// - ~/masm/lib/bar/baz.masm    -> Can be imported as "$kernel::bar::baz"
485    ///
486    /// Note: this is a temporary structure which will likely change once
487    /// <https://github.com/0xMiden/miden-vm/issues/1436> is implemented.
488    #[cfg(feature = "std")]
489    pub fn assemble_kernel_from_root(
490        self,
491        name: impl Into<PackageId>,
492        sys_module_path: impl AsRef<std::path::Path>,
493    ) -> Result<Box<Package>, Report> {
494        let sys_module_path = sys_module_path.as_ref();
495        let namespace = Some(Path::KERNEL.into());
496        let (root, support) = miden_assembly_syntax::parser::read_modules_from_root(
497            sys_module_path,
498            namespace,
499            Some(ModuleKind::Kernel),
500            self.source_manager.clone(),
501            self.warnings_as_errors,
502        )?;
503
504        self.assemble_library_modules(name.into(), root, support, TargetType::Kernel)?
505            .into_artifact()
506    }
507
508    /// Shared code used by both [`Self::assemble_library`] and [`Self::assemble_kernel`].
509    fn assemble_library_product(
510        mut self,
511        name: PackageId,
512        module_indices: &[ModuleIndex],
513        kind: TargetType,
514    ) -> Result<AssemblyProduct, Report> {
515        let staticlibs = self.static_libraries_for_builder()?;
516        let mut mast_forest_builder = MastForestBuilder::new_with_static_libraries(staticlibs)?;
517        let exports = {
518            let mut exports = BTreeMap::new();
519
520            for module_idx in module_indices.iter().copied() {
521                let (module_kind, module_path, num_symbols, imports) = {
522                    let module = &self.linker[module_idx];
523
524                    if let Some(advice_map) = module.advice_map() {
525                        mast_forest_builder.merge_advice_map(advice_map)?;
526                    }
527
528                    (
529                        module.kind(),
530                        module.path().clone(),
531                        module.symbols().len(),
532                        module.imports().cloned().collect::<Vec<_>>(),
533                    )
534                };
535
536                for index in 0..num_symbols {
537                    let index = ItemIndex::new(index);
538                    let gid = module_idx + index;
539
540                    let path: Arc<Path> = {
541                        let symbol = &self.linker[gid];
542                        if !symbol.visibility().is_public() {
543                            continue;
544                        }
545                        module_path
546                            .join(symbol.name())
547                            .canonicalize()
548                            .into_diagnostic()?
549                            .into_boxed_path()
550                            .into()
551                    };
552                    let export = self.export_symbol(
553                        gid,
554                        module_kind,
555                        path.clone(),
556                        &mut mast_forest_builder,
557                    )?;
558                    if exports.insert(path.clone(), export).is_some() {
559                        return Err(Report::new(AssemblerError::DuplicateExportPath { path }));
560                    }
561                }
562
563                for import in imports.iter() {
564                    if !import.visibility().is_public() {
565                        continue;
566                    }
567
568                    let path: Arc<Path> = module_path
569                        .join(import.local_name())
570                        .canonicalize()
571                        .into_diagnostic()?
572                        .into_boxed_path()
573                        .into();
574                    let export = self.export_import(
575                        module_idx,
576                        module_kind,
577                        path.clone(),
578                        import,
579                        &mut mast_forest_builder,
580                    )?;
581                    if exports.insert(path.clone(), export).is_some() {
582                        return Err(Report::new(AssemblerError::DuplicateExportPath { path }));
583                    }
584                }
585            }
586
587            exports
588        };
589
590        let (mast_forest, node_id_by_ref, source_graph, source_id_by_ref) =
591            mast_forest_builder.build()?.into_parts_with_source_graph();
592        let exports = exports
593            .into_iter()
594            .map(|(path, export)| {
595                export
596                    .into_package_export(&node_id_by_ref, &source_id_by_ref)
597                    .map(|export| (path, export))
598            })
599            .collect::<Result<BTreeMap<_, _>, _>>()?;
600
601        let modules = self.package_modules(module_indices);
602        self.finish_library_product(name, mast_forest, source_graph, exports, modules, kind)
603    }
604
605    fn package_modules(&self, module_indices: &[ModuleIndex]) -> Vec<PackageModule> {
606        let mut visited = BTreeSet::new();
607        let mut stack = module_indices.to_vec();
608        let mut modules = BTreeMap::new();
609
610        while let Some(module_idx) = stack.pop() {
611            if !visited.insert(module_idx) {
612                continue;
613            }
614
615            let module = &self.linker[module_idx];
616            let mut submodules = Vec::new();
617            for decl in module.submodules() {
618                if !decl.visibility.is_public() {
619                    continue;
620                }
621
622                submodules.push(PackageSubmodule::new(decl.name.clone()));
623
624                let child_path = module.path().join(&decl.name);
625                if let Some(child_idx) = self.linker.find_module_index(child_path.as_path()) {
626                    stack.push(child_idx);
627                }
628            }
629
630            modules.insert(
631                module.path().clone(),
632                PackageModule::new(module.path().clone(), submodules),
633            );
634        }
635
636        modules.into_values().collect()
637    }
638
639    /// The purpose of this function is, for any given symbol in the set of modules being compiled
640    /// to a package, to generate a corresponding [PackageExport] for that symbol.
641    ///
642    /// For procedures, this function is also responsible for compiling the procedure, and updating
643    /// the provided [MastForestBuilder] accordingly.
644    fn export_symbol(
645        &mut self,
646        gid: GlobalItemIndex,
647        module_kind: ModuleKind,
648        symbol_path: Arc<Path>,
649        mast_forest_builder: &mut MastForestBuilder,
650    ) -> Result<PendingPackageExport, Report> {
651        log::trace!(target: "assembler::export_symbol", "exporting {} {symbol_path}", match self.linker[gid].item() {
652            SymbolItem::Compiled(ItemInfo::Procedure(_)) => "compiled procedure",
653            SymbolItem::Compiled(ItemInfo::Constant(_)) => "compiled constant",
654            SymbolItem::Compiled(ItemInfo::Type(_)) => "compiled type",
655            SymbolItem::Procedure(_) => "procedure",
656            SymbolItem::Constant(_) => "constant",
657            SymbolItem::Type(_) => "type",
658        });
659        let mut cache = crate::linker::ResolverCache::default();
660        let export = match self.linker[gid].item() {
661            SymbolItem::Compiled(ItemInfo::Procedure(item)) => {
662                let resolved = match mast_forest_builder.get_procedure(gid) {
663                    Some(proc) => ResolvedProcedure {
664                        node: proc.body_node_ref(),
665                        signature: proc.signature(),
666                    },
667                    // We didn't find the procedure in our current MAST forest. We still need to
668                    // check if it exists in one of a library dependency.
669                    None => {
670                        log::trace!(target: "assembler::export_symbol", "no procedure found in forest");
671                        let node = self.ensure_valid_procedure_mast_root(
672                            InvokeKind::ProcRef,
673                            SourceSpan::UNKNOWN,
674                            item.digest,
675                            item.source_library_commitment(),
676                            item.source_root_id(),
677                            item.source_debug_root_id().map(DebugSourceNodeId::from),
678                            mast_forest_builder,
679                        )?;
680                        ResolvedProcedure { node, signature: item.signature.clone() }
681                    },
682                };
683                let digest = item.digest;
684                let ResolvedProcedure { node, signature } = resolved;
685                let attributes = item.attributes.clone();
686                let pctx = ProcedureContext::new(
687                    gid,
688                    /* is_program_entrypoint= */ false,
689                    symbol_path.clone(),
690                    Visibility::Public,
691                    signature.clone(),
692                    module_kind.is_kernel(),
693                    self.source_manager.clone(),
694                );
695
696                let procedure = pctx.into_procedure(digest, node);
697                self.linker.register_procedure_root(gid, digest);
698                mast_forest_builder.insert_procedure(gid, procedure)?;
699                PendingPackageExport::Procedure(PendingProcedureExport {
700                    digest,
701                    path: symbol_path,
702                    node_ref: node,
703                    source_ref: mast_forest_builder.latest_source_ref_for_node_ref(node),
704                    signature: signature.map(|sig| (*sig).clone()),
705                    attributes,
706                })
707            },
708            SymbolItem::Compiled(ItemInfo::Constant(item)) => {
709                PendingPackageExport::Constant(ConstantExport {
710                    path: symbol_path,
711                    value: item.value.clone(),
712                })
713            },
714            SymbolItem::Compiled(ItemInfo::Type(item)) => {
715                PendingPackageExport::Type(TypeExport { path: symbol_path, ty: item.ty.clone() })
716            },
717            SymbolItem::Procedure(_) => {
718                self.compile_subgraph(SubgraphRoot::not_as_entrypoint(gid), mast_forest_builder)?;
719                let proc = mast_forest_builder
720                    .get_procedure(gid)
721                    .expect("compilation succeeded but root not found in cache");
722                let digest = proc.mast_root();
723                let signature = self.linker.resolve_signature(gid)?;
724                let attributes = self.linker.resolve_attributes(gid);
725                PendingPackageExport::Procedure(PendingProcedureExport {
726                    digest,
727                    path: symbol_path,
728                    node_ref: proc.body_node_ref(),
729                    source_ref: mast_forest_builder
730                        .latest_source_ref_for_node_ref(proc.body_node_ref()),
731                    signature: signature.map(Arc::unwrap_or_clone),
732                    attributes,
733                })
734            },
735            SymbolItem::Constant(item) => {
736                // Evaluate constant to a concrete value for export
737                let value = self.linker.const_eval(gid, &item.value, &mut cache)?;
738
739                PendingPackageExport::Constant(ConstantExport { path: symbol_path, value })
740            },
741            SymbolItem::Type(item) => {
742                let ty = self.linker.resolve_type(item.span(), gid)?;
743                PendingPackageExport::Type(TypeExport { path: symbol_path, ty })
744            },
745        };
746
747        Ok(export)
748    }
749
750    fn export_import(
751        &mut self,
752        module: ModuleIndex,
753        module_kind: ModuleKind,
754        symbol_path: Arc<Path>,
755        import: &Import,
756        mast_forest_builder: &mut MastForestBuilder,
757    ) -> Result<PendingPackageExport, Report> {
758        if let Some(resolved) = import.resolved() {
759            return self.export_symbol(resolved, module_kind, symbol_path, mast_forest_builder);
760        }
761
762        let target = import.target_path();
763        let context = SymbolResolutionContext {
764            span: target.span(),
765            module,
766            kind: Some(InvokeKind::ProcRef),
767        };
768        match self.linker.resolve_path(&context, target.inner())? {
769            SymbolResolution::Exact { gid, .. } => {
770                self.export_symbol(gid, module_kind, symbol_path, mast_forest_builder)
771            },
772            SymbolResolution::Module { .. }
773            | SymbolResolution::MastRoot(_)
774            | SymbolResolution::Local(_)
775            | SymbolResolution::External(_) => {
776                Err(self.unresolved_import_report("export", &symbol_path, import))
777            },
778        }
779    }
780
781    /// Compiles the provided module into an executable package.
782    ///
783    /// The resulting program can be executed on Miden VM.
784    ///
785    /// # Errors
786    ///
787    /// Returns an error if parsing or compilation of the specified program fails, or if the source
788    /// doesn't have an entrypoint.
789    pub fn assemble_program(
790        self,
791        name: impl Into<PackageId>,
792        source: impl Parse,
793    ) -> Result<Box<Package>, Report> {
794        let program = source.parse(self.warnings_as_errors, self.source_manager.clone())?;
795        if !program.is_executable() {
796            return Err(Report::msg(
797                "unable to assemble program: source is not an executable module",
798            ));
799        }
800
801        self.assemble_executable_modules(name.into(), program, [])?.into_artifact()
802    }
803
804    pub(crate) fn assemble_library_modules(
805        mut self,
806        name: PackageId,
807        root: Box<ast::Module>,
808        support: impl IntoIterator<Item = Box<ast::Module>>,
809        kind: TargetType,
810    ) -> Result<AssemblyProduct, Report> {
811        let module_indices = match kind {
812            TargetType::Kernel => self.linker.link_kernel(root, support)?,
813            _ => self.linker.link([root], support)?,
814        };
815        self.verify_exported_signature_type_visibility(&module_indices)?;
816        self.assemble_library_product(name, &module_indices, kind)
817    }
818
819    fn verify_exported_signature_type_visibility(
820        &self,
821        module_indices: &[ModuleIndex],
822    ) -> Result<(), Report> {
823        let resolver = SymbolResolver::new(&self.linker);
824        for module_index in module_indices.iter().copied() {
825            let module = &self.linker[module_index];
826            for symbol in module.symbols() {
827                if !symbol.visibility().is_public() {
828                    continue;
829                }
830
831                self.verify_exported_item(&resolver, module_index, symbol, None)?;
832            }
833
834            for import in module.imports() {
835                if !import.visibility().is_public()
836                    || !matches!(import.kind(), ast::ImportKind::Item)
837                {
838                    continue;
839                }
840
841                let Some(gid) = import.resolved() else {
842                    continue;
843                };
844
845                self.verify_exported_item(
846                    &resolver,
847                    gid.module,
848                    &self.linker[gid],
849                    Some(import.span()),
850                )?;
851            }
852        }
853
854        Ok(())
855    }
856
857    fn verify_exported_item(
858        &self,
859        resolver: &SymbolResolver<'_>,
860        module_index: ModuleIndex,
861        symbol: &crate::linker::Symbol,
862        export_span: Option<SourceSpan>,
863    ) -> Result<(), Report> {
864        match symbol.item() {
865            SymbolItem::Procedure(proc) => {
866                let proc = proc.borrow();
867                self.verify_exported_signature(resolver, module_index, proc.signature())
868            },
869            SymbolItem::Type(type_decl) => {
870                if !symbol.visibility().is_public() {
871                    return Err(Report::new(SemanticAnalysisError::PrivateTypeInExportedType {
872                        span: export_span.unwrap_or_else(|| type_decl.name().span()),
873                        defined: type_decl.name().span(),
874                    }));
875                }
876
877                let mut visiting_types = BTreeSet::default();
878                self.verify_exported_type_decl(
879                    resolver,
880                    module_index,
881                    type_decl,
882                    &mut visiting_types,
883                    ExportedTypeUse::TypeDeclaration,
884                )
885            },
886            SymbolItem::Constant(_)
887            | SymbolItem::Compiled(
888                ItemInfo::Procedure(_) | ItemInfo::Constant(_) | ItemInfo::Type(_),
889            ) => Ok(()),
890        }
891    }
892
893    fn verify_exported_signature(
894        &self,
895        resolver: &SymbolResolver<'_>,
896        current_module: ModuleIndex,
897        signature: Option<&ast::FunctionType>,
898    ) -> Result<(), Report> {
899        let Some(signature) = signature else {
900            return Ok(());
901        };
902
903        for ty in signature.args.iter().chain(signature.results.iter()) {
904            let mut visiting_types = BTreeSet::default();
905            self.verify_exported_type_expr(
906                resolver,
907                current_module,
908                ty,
909                &mut visiting_types,
910                ExportedTypeUse::ProcedureSignature,
911            )?;
912        }
913
914        Ok(())
915    }
916
917    fn verify_exported_type_decl(
918        &self,
919        resolver: &SymbolResolver<'_>,
920        current_module: ModuleIndex,
921        type_decl: &ast::TypeDecl,
922        visiting_types: &mut BTreeSet<GlobalItemIndex>,
923        usage: ExportedTypeUse,
924    ) -> Result<(), Report> {
925        match type_decl {
926            ast::TypeDecl::Alias(alias) => {
927                self.verify_exported_type_expr(
928                    resolver,
929                    current_module,
930                    &alias.ty,
931                    visiting_types,
932                    usage,
933                )?;
934            },
935            ast::TypeDecl::Enum(ty) => {
936                for variant in ty.variants() {
937                    if let Some(payload_ty) = variant.value_ty.as_ref() {
938                        self.verify_exported_type_expr(
939                            resolver,
940                            current_module,
941                            payload_ty,
942                            visiting_types,
943                            usage,
944                        )?;
945                    }
946                }
947            },
948        }
949
950        Ok(())
951    }
952
953    fn verify_exported_type_expr(
954        &self,
955        resolver: &SymbolResolver<'_>,
956        current_module: ModuleIndex,
957        ty: &ast::TypeExpr,
958        visiting_types: &mut BTreeSet<GlobalItemIndex>,
959        usage: ExportedTypeUse,
960    ) -> Result<(), Report> {
961        match ty {
962            ast::TypeExpr::Primitive(_) => Ok(()),
963            ast::TypeExpr::Ptr(ty) => self.verify_exported_type_expr(
964                resolver,
965                current_module,
966                &ty.pointee,
967                visiting_types,
968                usage,
969            ),
970            ast::TypeExpr::Array(ty) => self.verify_exported_type_expr(
971                resolver,
972                current_module,
973                &ty.elem,
974                visiting_types,
975                usage,
976            ),
977            ast::TypeExpr::Struct(ty) => {
978                for field in ty.fields.iter() {
979                    self.verify_exported_type_expr(
980                        resolver,
981                        current_module,
982                        &field.ty,
983                        visiting_types,
984                        usage,
985                    )?;
986                }
987
988                Ok(())
989            },
990            ast::TypeExpr::Ref(path) => {
991                let context = SymbolResolutionContext {
992                    span: path.span(),
993                    module: current_module,
994                    kind: None,
995                };
996                let resolution =
997                    resolver.resolve_path(&context, path.as_deref()).map_err(Report::from)?;
998
999                let gid = match resolution {
1000                    SymbolResolution::Exact { gid, .. } => gid,
1001                    SymbolResolution::Local(item) => current_module + item.into_inner(),
1002                    SymbolResolution::External(_)
1003                    | SymbolResolution::MastRoot(_)
1004                    | SymbolResolution::Module { .. } => return Ok(()),
1005                };
1006
1007                let symbol = &self.linker[gid];
1008                let SymbolItem::Type(type_decl) = symbol.item() else {
1009                    return Ok(());
1010                };
1011
1012                if !symbol.visibility().is_public() {
1013                    return Err(Report::new(
1014                        usage.private_type_error(path.span(), type_decl.name().span()),
1015                    ));
1016                }
1017
1018                if !visiting_types.insert(gid) {
1019                    return Ok(());
1020                }
1021
1022                self.verify_exported_type_decl(
1023                    resolver,
1024                    gid.module,
1025                    type_decl,
1026                    visiting_types,
1027                    usage,
1028                )?;
1029
1030                visiting_types.remove(&gid);
1031                Ok(())
1032            },
1033        }
1034    }
1035
1036    pub(crate) fn assemble_executable_modules(
1037        mut self,
1038        name: PackageId,
1039        program: Box<ast::Module>,
1040        support_modules: impl IntoIterator<Item = Box<ast::Module>>,
1041    ) -> Result<AssemblyProduct, Report> {
1042        // Recompute graph with executable module, and start compiling
1043        let namespace = Arc::<Path>::from(program.path());
1044        let module_index = self.linker.link([program], support_modules)?[0];
1045
1046        // Find the executable entrypoint Note: it is safe to use `unwrap_ast()` here, since this is
1047        // the module we just added, which is in AST representation.
1048        let entrypoint = self.linker[module_index]
1049            .symbols()
1050            .position(|symbol| symbol.name().as_str() == Ident::MAIN)
1051            .map(|index| module_index + ItemIndex::new(index))
1052            .ok_or(SemanticAnalysisError::MissingEntrypoint)?;
1053
1054        // Compile the linked module graph rooted at the entrypoint
1055        let staticlibs = self.static_libraries_for_builder()?;
1056        let mut mast_forest_builder = MastForestBuilder::new_with_static_libraries(staticlibs)?;
1057
1058        if let Some(advice_map) = self.linker[module_index].advice_map() {
1059            mast_forest_builder.merge_advice_map(advice_map)?;
1060        }
1061
1062        self.compile_subgraph(SubgraphRoot::with_entrypoint(entrypoint), &mut mast_forest_builder)?;
1063        let entry_node_ref = mast_forest_builder
1064            .get_procedure(entrypoint)
1065            .expect("compilation succeeded but root not found in cache")
1066            .body_node_ref();
1067
1068        let (mast_forest, node_id_by_ref, source_graph, _) =
1069            mast_forest_builder.build()?.into_parts_with_source_graph();
1070        let entry_node_id = *node_id_by_ref.get(&entry_node_ref).ok_or_else(|| {
1071            Report::msg(format!("entrypoint ref {entry_node_ref} was not finalized"))
1072        })?;
1073
1074        self.finish_program_product(
1075            name,
1076            namespace,
1077            mast_forest,
1078            source_graph,
1079            entry_node_id,
1080            self.linker.kernel_package(),
1081        )
1082    }
1083
1084    fn finish_library_product(
1085        &self,
1086        name: PackageId,
1087        mast_forest: miden_core::mast::MastForest,
1088        source_graph: SourceDebugGraph,
1089        exports: BTreeMap<Arc<Path>, PackageExport>,
1090        modules: Vec<PackageModule>,
1091        kind: TargetType,
1092    ) -> Result<AssemblyProduct, Report> {
1093        let mast = Arc::new(mast_forest);
1094        let package = Box::new(
1095            Package::create_with_modules(
1096                name,
1097                miden_mast_package::Version::new(0, 0, 0),
1098                kind,
1099                mast,
1100                exports.into_values(),
1101                modules,
1102                None,
1103            )
1104            .map_err(Report::msg)?,
1105        );
1106        let debug_info = self.emit_debug_info.then(|| {
1107            #[cfg_attr(not(feature = "std"), expect(unused_mut))]
1108            let mut debug_info = self.debug_info.clone();
1109            #[cfg(feature = "std")]
1110            if let Some(trimmer) = self.source_path_trimmer() {
1111                debug_info.trim_paths(&trimmer);
1112            }
1113            debug_info
1114        });
1115
1116        let source_graph =
1117            self.emit_debug_info.then(|| self.apply_source_debug_options(source_graph));
1118
1119        Ok(AssemblyProduct::new(package, None, debug_info, source_graph))
1120    }
1121
1122    fn static_libraries_for_builder(&self) -> Result<Vec<StaticLibrary<'_>>, Report> {
1123        self.linker
1124            .static_libraries()
1125            .map(|lib| {
1126                let debug_info = match lib.package.debug_info() {
1127                    Ok(debug_info) => debug_info,
1128                    Err(PackageDebugInfoError::UntrustedSections) => None,
1129                    Err(err) => {
1130                        return Err(Report::msg(format!(
1131                            "failed to decode debug info for statically linked package '{}': {err}",
1132                            lib.package.name
1133                        )));
1134                    },
1135                };
1136                Ok(StaticLibrary::new(lib.mast().as_ref(), debug_info)
1137                    .with_source_library_commitment(lib.commitment())
1138                    .with_alternate_source_library_commitment(
1139                        lib.package.interface_digest().into_diagnostic()?,
1140                    ))
1141            })
1142            .collect()
1143    }
1144
1145    fn finish_program_product(
1146        &self,
1147        name: PackageId,
1148        namespace: Arc<Path>,
1149        mast_forest: miden_core::mast::MastForest,
1150        source_graph: SourceDebugGraph,
1151        entrypoint: MastNodeId,
1152        kernel: Option<Arc<Package>>,
1153    ) -> Result<AssemblyProduct, Report> {
1154        let mast = Arc::new(mast_forest);
1155        let entry: Arc<Path> = namespace.join(ast::ProcedureName::MAIN_PROC_NAME).into();
1156        let entry_digest = mast[entrypoint].digest();
1157        let entry_source_node = source_graph
1158            .unique_root_for_exec_node(entrypoint)
1159            .map(|source_id| DebugSourceNodeId::from(u32::from(source_id)));
1160        let package = Box::new(
1161            Package::create(
1162                name,
1163                miden_mast_package::Version::new(0, 0, 0),
1164                TargetType::Executable,
1165                mast,
1166                vec![PackageExport::Procedure(
1167                    ProcedureExport::new(entry, Some(entrypoint), entry_digest, None)
1168                        .with_source_node(entry_source_node),
1169                )],
1170                None,
1171            )
1172            .map_err(Report::msg)?,
1173        );
1174        let debug_info = self.emit_debug_info.then(|| {
1175            #[cfg_attr(not(feature = "std"), expect(unused_mut))]
1176            let mut debug_info = self.debug_info.clone();
1177            #[cfg(feature = "std")]
1178            if let Some(trimmer) = self.source_path_trimmer() {
1179                debug_info.trim_paths(&trimmer);
1180            }
1181            debug_info
1182        });
1183
1184        let source_graph =
1185            self.emit_debug_info.then(|| self.apply_source_debug_options(source_graph));
1186
1187        Ok(AssemblyProduct::new(package, kernel, debug_info, source_graph))
1188    }
1189
1190    fn apply_source_debug_options(&self, source_graph: SourceDebugGraph) -> SourceDebugGraph {
1191        if self.trim_paths {
1192            #[cfg(feature = "std")]
1193            if let Some(trimmer) = self.source_path_trimmer() {
1194                return source_graph.with_rewritten_source_locations(
1195                    |location| trimmer.trim_location(location),
1196                    |location| trimmer.trim_file_line_col(location),
1197                );
1198            }
1199        }
1200
1201        source_graph
1202    }
1203
1204    #[cfg(feature = "std")]
1205    fn source_path_trimmer(&self) -> Option<debuginfo::SourcePathTrimmer> {
1206        if !self.trim_paths {
1207            return None;
1208        }
1209
1210        std::env::current_dir().ok().map(debuginfo::SourcePathTrimmer::new)
1211    }
1212
1213    /// Compile the uncompiled procedure in the linked module graph which are members of the
1214    /// subgraph rooted at `root`, placing them in the MAST forest builder once compiled.
1215    ///
1216    /// Returns an error if any of the provided Miden Assembly is invalid.
1217    fn compile_subgraph(
1218        &mut self,
1219        root: SubgraphRoot,
1220        mast_forest_builder: &mut MastForestBuilder,
1221    ) -> Result<(), Report> {
1222        let mut worklist: Vec<GlobalItemIndex> = self
1223            .linker
1224            .topological_sort_from_root(root.proc_id)
1225            .map_err(|cycle| {
1226                let iter = cycle.into_node_ids();
1227                let mut nodes = Vec::with_capacity(iter.len());
1228                for node in iter {
1229                    let module = self.linker[node.module].path();
1230                    let proc = self.linker[node].name();
1231                    nodes.push(format!("{}", module.join(proc)));
1232                }
1233                LinkerError::Cycle { nodes: nodes.into() }
1234            })?
1235            .into_iter()
1236            .filter(|&gid| matches!(self.linker[gid].item(), SymbolItem::Procedure(_)))
1237            .collect();
1238
1239        assert!(!worklist.is_empty());
1240
1241        self.process_graph_worklist(&mut worklist, &root, mast_forest_builder)
1242    }
1243
1244    /// Compiles all procedures in the `worklist`.
1245    fn process_graph_worklist(
1246        &mut self,
1247        worklist: &mut Vec<GlobalItemIndex>,
1248        root: &SubgraphRoot,
1249        mast_forest_builder: &mut MastForestBuilder,
1250    ) -> Result<(), Report> {
1251        // Process the topological ordering in reverse order (bottom-up), so that
1252        // each procedure is compiled with all of its dependencies fully compiled
1253        while let Some(procedure_gid) = worklist.pop() {
1254            // If we have already compiled this procedure, do not recompile
1255            if let Some(proc) = mast_forest_builder.get_procedure(procedure_gid) {
1256                self.linker.register_procedure_root(procedure_gid, proc.mast_root());
1257                continue;
1258            }
1259            // Fetch procedure metadata from the graph
1260            let (module_kind, module_path) = {
1261                let module = &self.linker[procedure_gid.module];
1262                (module.kind(), module.path().clone())
1263            };
1264            match self.linker[procedure_gid].item() {
1265                SymbolItem::Procedure(proc) => {
1266                    let proc = proc.borrow();
1267                    let num_locals = proc.num_locals();
1268                    let path = Arc::<Path>::from(module_path.join(proc.name().as_str()));
1269                    let signature = self.linker.resolve_signature(procedure_gid)?;
1270                    let is_program_entrypoint =
1271                        root.is_program_entrypoint && root.proc_id == procedure_gid;
1272
1273                    let pctx = ProcedureContext::new(
1274                        procedure_gid,
1275                        is_program_entrypoint,
1276                        path.clone(),
1277                        proc.visibility(),
1278                        signature.clone(),
1279                        module_kind.is_kernel(),
1280                        self.source_manager.clone(),
1281                    )
1282                    .with_span(proc.span())
1283                    .with_num_locals(num_locals)?;
1284
1285                    // Compile this procedure
1286                    let procedure = self.compile_procedure(pctx, mast_forest_builder)?;
1287                    // TODO: if a re-exported procedure with the same MAST root had been previously
1288                    // added to the builder, this will result in unreachable nodes added to the
1289                    // MAST forest. This is because while we won't insert a duplicate node for the
1290                    // procedure body node itself, all nodes that make up the procedure body would
1291                    // be added to the forest.
1292
1293                    // Record the debug info for this procedure
1294                    self.debug_info
1295                        .register_procedure_debug_info(&procedure, self.source_manager.as_ref())?;
1296
1297                    // Cache the compiled procedure
1298                    drop(proc);
1299                    self.linker.register_procedure_root(procedure_gid, procedure.mast_root());
1300                    mast_forest_builder.insert_procedure(procedure_gid, procedure)?;
1301                },
1302                SymbolItem::Compiled(_) | SymbolItem::Constant(_) | SymbolItem::Type(_) => {
1303                    // There is nothing to do for other items that might have edges in the graph
1304                },
1305            }
1306        }
1307
1308        Ok(())
1309    }
1310
1311    fn unresolved_import_report(
1312        &self,
1313        action: &'static str,
1314        symbol_path: &Path,
1315        import: &Import,
1316    ) -> Report {
1317        let target = import.target_path();
1318        let span = target.span();
1319
1320        RelatedLabel::error(format!(
1321            "unable to {action} import '{symbol_path}' targeting '{}'",
1322            target.inner()
1323        ))
1324        .with_labeled_span(span, "this import target does not resolve to a concrete item")
1325        .with_help("imports must resolve to a concrete item before they can be used")
1326        .with_source_file(self.source_manager.get(span.source_id()).ok())
1327        .into()
1328    }
1329
1330    /// Compiles a single Miden Assembly procedure to its MAST representation.
1331    fn compile_procedure(
1332        &self,
1333        mut proc_ctx: ProcedureContext,
1334        mast_forest_builder: &mut MastForestBuilder,
1335    ) -> Result<Procedure, Report> {
1336        // Make sure the current procedure context is available during codegen
1337        let gid = proc_ctx.id();
1338
1339        let num_locals = proc_ctx.num_locals();
1340
1341        let proc = match self.linker[gid].item() {
1342            SymbolItem::Procedure(proc) => proc.borrow(),
1343            _ => panic!("expected item to be a procedure AST"),
1344        };
1345        let body_wrapper = if proc_ctx.is_program_entrypoint() {
1346            assert!(num_locals == 0, "program entrypoint cannot have locals");
1347
1348            Some(BodyWrapper {
1349                prologue: fmp_initialization_sequence(),
1350                epilogue: Vec::new(),
1351            })
1352        } else if num_locals > 0 {
1353            Some(BodyWrapper {
1354                prologue: fmp_start_frame_sequence(num_locals),
1355                epilogue: fmp_end_frame_sequence(num_locals),
1356            })
1357        } else {
1358            None
1359        };
1360
1361        let proc_body_ref =
1362            self.compile_body(proc.iter(), &mut proc_ctx, body_wrapper, mast_forest_builder, 0)?;
1363
1364        let proc_mast_root = mast_forest_builder
1365            .mast_root_for_ref(proc_body_ref)
1366            .expect("no MAST node for compiled procedure");
1367        Ok(proc_ctx.into_procedure(proc_mast_root, proc_body_ref))
1368    }
1369
1370    /// Creates assembly operation metadata for control flow nodes.
1371    fn create_asm_op(
1372        &self,
1373        span: &SourceSpan,
1374        op_name: &str,
1375        proc_ctx: &ProcedureContext,
1376    ) -> AssemblyOp {
1377        let location = proc_ctx.source_manager().location(*span).ok();
1378        let context_name = proc_ctx.path().to_string();
1379        let num_cycles = 0;
1380        AssemblyOp::new(location, context_name, num_cycles, op_name.to_string())
1381    }
1382
1383    fn compile_body<'a, I>(
1384        &self,
1385        body: I,
1386        proc_ctx: &mut ProcedureContext,
1387        wrapper: Option<BodyWrapper>,
1388        mast_forest_builder: &mut MastForestBuilder,
1389        nesting_depth: usize,
1390    ) -> Result<MastNodeRef, Report>
1391    where
1392        I: Iterator<Item = &'a ast::Op>,
1393    {
1394        use ast::Op;
1395
1396        let mut body_node_refs: Vec<MastNodeRef> = Vec::new();
1397        let mut block_builder = BasicBlockBuilder::new(wrapper, mast_forest_builder);
1398
1399        for op in body {
1400            match op {
1401                Op::Inst(inst) => {
1402                    if let Some(node_ref) =
1403                        self.compile_instruction(inst, &mut block_builder, proc_ctx)?
1404                    {
1405                        if let Some(basic_block_id) = block_builder.make_basic_block()? {
1406                            body_node_refs.push(basic_block_id);
1407                        }
1408
1409                        body_node_refs.push(node_ref);
1410                    }
1411                },
1412
1413                Op::If { then_blk, else_blk, span } => {
1414                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1415                        body_node_refs.push(basic_block_id);
1416                    }
1417
1418                    let next_depth = nesting_depth + 1;
1419                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1420                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1421                            span: *span,
1422                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1423                            max_depth: MAX_CONTROL_FLOW_NESTING,
1424                        }));
1425                    }
1426
1427                    let then_blk = self.compile_body(
1428                        then_blk.iter(),
1429                        proc_ctx,
1430                        None,
1431                        block_builder.mast_forest_builder_mut(),
1432                        next_depth,
1433                    )?;
1434                    let else_blk = self.compile_body(
1435                        else_blk.iter(),
1436                        proc_ctx,
1437                        None,
1438                        block_builder.mast_forest_builder_mut(),
1439                        next_depth,
1440                    )?;
1441
1442                    let asm_op = self.create_asm_op(span, "if.true", proc_ctx);
1443                    let split_node_ref = block_builder
1444                        .mast_forest_builder_mut()
1445                        .ensure_split_node_ref([then_blk, else_blk], asm_op)?;
1446
1447                    body_node_refs.push(split_node_ref);
1448                },
1449
1450                Op::Repeat { count, body, span } => {
1451                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1452                        body_node_refs.push(basic_block_id);
1453                    }
1454
1455                    let next_depth = nesting_depth + 1;
1456                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1457                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1458                            span: *span,
1459                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1460                            max_depth: MAX_CONTROL_FLOW_NESTING,
1461                        }));
1462                    }
1463
1464                    let repeat_node_ref = self.compile_body(
1465                        body.iter(),
1466                        proc_ctx,
1467                        None,
1468                        block_builder.mast_forest_builder_mut(),
1469                        next_depth,
1470                    )?;
1471
1472                    let iteration_count = (*count).expect_value();
1473                    if iteration_count == 0 {
1474                        return Err(RelatedLabel::error("invalid repeat count")
1475                            .with_help("repeat count must be greater than 0")
1476                            .with_labeled_span(count.span(), "repeat count must be at least 1")
1477                            .with_source_file(
1478                                proc_ctx.source_manager().get(proc_ctx.span().source_id()).ok(),
1479                            )
1480                            .into());
1481                    }
1482                    if iteration_count > MAX_REPEAT_COUNT {
1483                        return Err(RelatedLabel::error("invalid repeat count")
1484                            .with_help(format!(
1485                                "repeat count must be less than or equal to {MAX_REPEAT_COUNT}",
1486                            ))
1487                            .with_labeled_span(
1488                                count.span(),
1489                                format!("repeat count exceeds {MAX_REPEAT_COUNT}"),
1490                            )
1491                            .with_source_file(
1492                                proc_ctx.source_manager().get(proc_ctx.span().source_id()).ok(),
1493                            )
1494                            .into());
1495                    }
1496
1497                    for _ in 0..iteration_count {
1498                        body_node_refs.push(repeat_node_ref);
1499                    }
1500                },
1501
1502                Op::While { body, span } => {
1503                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1504                        body_node_refs.push(basic_block_id);
1505                    }
1506
1507                    let next_depth = nesting_depth + 1;
1508                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1509                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1510                            span: *span,
1511                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1512                            max_depth: MAX_CONTROL_FLOW_NESTING,
1513                        }));
1514                    }
1515
1516                    // `while.true` desugars to `if.true { LOOP { body } } else { noop }`. The LOOP
1517                    // itself has do-while semantics: the body executes unconditionally for the
1518                    // first iteration, so the surrounding SPLIT performs the initial true-check.
1519                    //
1520                    // The `while.true` asm_op is attached to *both* the LOOP and the wrapping
1521                    // SPLIT: both nodes belong to a single source-level `while.true` construct, and
1522                    // diagnostics emitted from inside the body walk up the continuation stack to
1523                    // the nearest control-flow parent (the LOOP), so it must carry the source
1524                    // mapping too.
1525                    let asm_op = self.create_asm_op(span, "while.true", proc_ctx);
1526
1527                    let loop_body_node_ref = self.compile_body(
1528                        body.iter(),
1529                        proc_ctx,
1530                        None,
1531                        block_builder.mast_forest_builder_mut(),
1532                        next_depth,
1533                    )?;
1534                    let loop_node_ref = block_builder
1535                        .mast_forest_builder_mut()
1536                        .ensure_loop_node_ref(loop_body_node_ref, asm_op.clone())?;
1537                    let noop_block_ref = block_builder.mast_forest_builder_mut().ensure_block_ref(
1538                        vec![Operation::Noop],
1539                        vec![],
1540                        vec![],
1541                    )?;
1542
1543                    let split_node_ref = block_builder
1544                        .mast_forest_builder_mut()
1545                        .ensure_split_node_ref([loop_node_ref, noop_block_ref], asm_op)?;
1546
1547                    body_node_refs.push(split_node_ref);
1548                },
1549
1550                Op::DoWhile { body, condition, span } => {
1551                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1552                        body_node_refs.push(basic_block_id);
1553                    }
1554
1555                    let next_depth = nesting_depth + 1;
1556                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1557                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1558                            span: *span,
1559                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1560                            max_depth: MAX_CONTROL_FLOW_NESTING,
1561                        }));
1562                    }
1563
1564                    // A `do { body } while { cond } end` loop maps directly onto the LOOP node's
1565                    // native do-while semantics: the body executes unconditionally on the first
1566                    // pass, and iteration is decided at the tail. Unlike `while.true`, no SPLIT
1567                    // wrapper (head-entry check) is needed. The loop body is `body ++ cond`; the
1568                    // condition leaves the re-entry boolean on top of the stack, and the
1569                    // contiguous basic blocks are merged by the MAST forest builder.
1570                    let asm_op = self.create_asm_op(span, "do.while", proc_ctx);
1571
1572                    let loop_body_node_ref = self.compile_body(
1573                        body.iter().chain(condition.iter()),
1574                        proc_ctx,
1575                        None,
1576                        block_builder.mast_forest_builder_mut(),
1577                        next_depth,
1578                    )?;
1579                    let loop_node_ref = block_builder
1580                        .mast_forest_builder_mut()
1581                        .ensure_loop_node_ref(loop_body_node_ref, asm_op)?;
1582
1583                    body_node_refs.push(loop_node_ref);
1584                },
1585            }
1586        }
1587
1588        if let Some(basic_block_id) = block_builder.try_into_basic_block()? {
1589            body_node_refs.push(basic_block_id);
1590        }
1591
1592        let procedure_body_ref = if body_node_refs.is_empty() {
1593            mast_forest_builder.ensure_block_ref(vec![Operation::Noop], vec![], vec![])?
1594        } else {
1595            let asm_op = self.create_asm_op(&proc_ctx.span(), "begin", proc_ctx);
1596            mast_forest_builder.join_node_refs(body_node_refs, Some(asm_op))?
1597        };
1598
1599        Ok(procedure_body_ref)
1600    }
1601
1602    /// Resolves the specified target to the corresponding procedure root [`MastNodeRef`].
1603    ///
1604    /// If no [`MastNodeRef`] exists for that procedure root, we wrap the root in an
1605    /// [`crate::mast::ExternalNode`], and return the resulting [`MastNodeRef`].
1606    pub(super) fn resolve_target(
1607        &self,
1608        kind: InvokeKind,
1609        target: &InvocationTarget,
1610        caller_module: ModuleIndex,
1611        mast_forest_builder: &mut MastForestBuilder,
1612    ) -> Result<ResolvedProcedure, Report> {
1613        let caller = SymbolResolutionContext {
1614            span: target.span(),
1615            module: caller_module,
1616            kind: Some(kind),
1617        };
1618        let resolved = self.linker.resolve_invoke_target(&caller, target)?;
1619        match resolved {
1620            SymbolResolution::MastRoot(mast_root) => {
1621                let node = self.ensure_valid_procedure_mast_root(
1622                    kind,
1623                    target.span(),
1624                    mast_root.into_inner(),
1625                    None,
1626                    None,
1627                    None,
1628                    mast_forest_builder,
1629                )?;
1630                Ok(ResolvedProcedure { node, signature: None })
1631            },
1632            SymbolResolution::Exact { gid, .. } => {
1633                match mast_forest_builder.get_procedure(gid) {
1634                    Some(proc) => Ok(ResolvedProcedure {
1635                        node: proc.body_node_ref(),
1636                        signature: proc.signature(),
1637                    }),
1638                    // We didn't find the procedure in our current MAST forest. We still need to
1639                    // check if it exists in one of a library dependency.
1640                    None => match self.linker[gid].item() {
1641                        SymbolItem::Compiled(ItemInfo::Procedure(p)) => {
1642                            let node = self.ensure_valid_procedure_mast_root(
1643                                kind,
1644                                target.span(),
1645                                p.digest,
1646                                p.source_library_commitment(),
1647                                p.source_root_id(),
1648                                p.source_debug_root_id().map(DebugSourceNodeId::from),
1649                                mast_forest_builder,
1650                            )?;
1651                            Ok(ResolvedProcedure { node, signature: p.signature.clone() })
1652                        },
1653                        SymbolItem::Procedure(_) => panic!(
1654                            "AST procedure {gid:?} exists in the linker, but not in the MastForestBuilder"
1655                        ),
1656                        SymbolItem::Compiled(_) | SymbolItem::Type(_) | SymbolItem::Constant(_) => {
1657                            unreachable!("invoke resolver should reject non-procedure targets")
1658                        },
1659                    },
1660                }
1661            },
1662            SymbolResolution::Module { .. }
1663            | SymbolResolution::External(_)
1664            | SymbolResolution::Local(_) => unreachable!(),
1665        }
1666    }
1667
1668    /// Verifies the validity of the MAST root as a procedure root hash, and adds it to the forest.
1669    ///
1670    /// If the root is present in the vendored MAST, its subtree is copied. Otherwise an
1671    /// external node is added to the forest.
1672    fn ensure_valid_procedure_mast_root(
1673        &self,
1674        kind: InvokeKind,
1675        span: SourceSpan,
1676        mast_root: Word,
1677        source_library_commitment: Option<Word>,
1678        source_root_id: Option<MastNodeId>,
1679        source_debug_root_id: Option<DebugSourceNodeId>,
1680        mast_forest_builder: &mut MastForestBuilder,
1681    ) -> Result<MastNodeRef, Report> {
1682        // Get the procedure from the assembler
1683        let current_source_file = self.source_manager.get(span.source_id()).ok();
1684
1685        if matches!(kind, InvokeKind::SysCall) && self.linker.has_nonempty_kernel() {
1686            // NOTE: The assembler is expected to know the full set of all kernel
1687            // procedures at this point, so if the digest is not present in the kernel,
1688            // it is a definite error.
1689            if !self.linker.kernel().contains_proc(mast_root) {
1690                let callee = mast_forest_builder
1691                    .find_procedure_by_mast_root(&mast_root)
1692                    .map(|proc| proc.path().clone())
1693                    .unwrap_or_else(|| {
1694                        let digest_path = format!("{mast_root}");
1695                        Arc::<Path>::from(Path::new(&digest_path))
1696                    });
1697                return Err(Report::new(LinkerError::InvalidSysCallTarget {
1698                    span,
1699                    source_file: current_source_file,
1700                    callee,
1701                }));
1702            }
1703        }
1704
1705        if let (Some(source_library_commitment), Some(source_root_id)) =
1706            (source_library_commitment, source_root_id)
1707            && let Some(conflicting_root) = self.linker.conflicting_dynamic_procedure_export_root(
1708                source_library_commitment,
1709                mast_root,
1710                source_root_id,
1711            )
1712        {
1713            return Err(Report::new(LinkerError::AmbiguousDynamicProcedureRoot {
1714                span,
1715                source_file: current_source_file,
1716                mast_root,
1717                source_library_commitment,
1718                selected_root: source_root_id,
1719                conflicting_root,
1720            }));
1721        }
1722
1723        mast_forest_builder.ensure_external_link_with_source_ref(
1724            mast_root,
1725            source_library_commitment,
1726            source_root_id,
1727            source_debug_root_id,
1728        )
1729    }
1730}
1731
1732// HELPERS
1733// ================================================================================================
1734
1735/// Information about the root of a subgraph to be compiled.
1736///
1737/// `is_program_entrypoint` is true if the root procedure is the entrypoint of an executable
1738/// program.
1739struct SubgraphRoot {
1740    proc_id: GlobalItemIndex,
1741    is_program_entrypoint: bool,
1742}
1743
1744impl SubgraphRoot {
1745    fn with_entrypoint(proc_id: GlobalItemIndex) -> Self {
1746        Self { proc_id, is_program_entrypoint: true }
1747    }
1748
1749    fn not_as_entrypoint(proc_id: GlobalItemIndex) -> Self {
1750        Self { proc_id, is_program_entrypoint: false }
1751    }
1752}
1753
1754/// Contains a set of operations which need to be executed before and after a sequence of AST
1755/// nodes (i.e., code body).
1756pub(crate) struct BodyWrapper {
1757    pub prologue: Vec<Operation>,
1758    pub epilogue: Vec<Operation>,
1759}
1760
1761pub(super) struct ResolvedProcedure {
1762    pub node: MastNodeRef,
1763    pub signature: Option<Arc<FunctionType>>,
1764}
miden_assembly/assembler.rs

miden_assembly/
assembler.rs
