miden_assembly/
assembler.rs

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

miden_assembly/
assembler.rs
