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

miden_assembly/
assembler.rs
