miden_assembly/
assembler.rs

1#[cfg(feature = "std")]
2pub(super) mod debuginfo;
3pub(crate) mod error;
4mod product;
5
6use alloc::{
7    boxed::Box,
8    collections::{BTreeMap, BTreeSet},
9    string::ToString,
10    sync::Arc,
11    vec::Vec,
12};
13
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::KernelDescriptor,
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, PackageDebugInfo},
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::{MastForestBuilder, MastNodeRef, SourceNodeRef, StaticLibrary},
49};
50
51/// Maximum allowed nesting of control-flow blocks during compilation.
52///
53/// This limit is intended to prevent stack overflows from maliciously deep block nesting while
54/// remaining far above typical program structure depth.
55pub(crate) const MAX_CONTROL_FLOW_NESTING: usize = 256;
56
57/// Maximum number of locals a single procedure may allocate.
58///
59/// When emitting the frame-pointer sequence, the local count is rounded up to the nearest multiple
60/// of word size. To keep that rounding from overflowing the u16 frame counter, the
61/// maximum must itself be a multiple of word size. This mirrors the limit the assembly parser
62/// enforces on the @locals(..) attribute.
63pub(crate) const MAX_PROC_LOCALS: u16 = (u16::MAX / WORD_SIZE as u16) * WORD_SIZE as u16;
64
65#[derive(Debug)]
66enum PendingPackageExport {
67    Procedure(PendingProcedureExport),
68    Constant(ConstantExport),
69    Type(TypeExport),
70}
71
72#[derive(Debug)]
73struct PendingProcedureExport {
74    node_ref: MastNodeRef,
75    source_ref: Option<SourceNodeRef>,
76    digest: Word,
77    path: Arc<Path>,
78    signature: Option<FunctionType>,
79    attributes: AttributeSet,
80}
81
82impl PendingPackageExport {
83    fn into_package_export(
84        self,
85        node_id_by_ref: &BTreeMap<MastNodeRef, MastNodeId>,
86        source_id_by_ref: &BTreeMap<SourceNodeRef, DebugSourceNodeId>,
87    ) -> Result<PackageExport, Report> {
88        match self {
89            Self::Procedure(export) => export.into_package_export(node_id_by_ref, source_id_by_ref),
90            Self::Constant(export) => Ok(PackageExport::Constant(export)),
91            Self::Type(export) => Ok(PackageExport::Type(export)),
92        }
93    }
94}
95
96impl PendingProcedureExport {
97    fn into_package_export(
98        self,
99        node_id_by_ref: &BTreeMap<MastNodeRef, MastNodeId>,
100        source_id_by_ref: &BTreeMap<SourceNodeRef, DebugSourceNodeId>,
101    ) -> Result<PackageExport, Report> {
102        let node = node_id_by_ref.get(&self.node_ref).copied().ok_or_else(|| {
103            Report::msg(format!("procedure export ref {} was not finalized", self.node_ref))
104        })?;
105        let source_node = self
106            .source_ref
107            .and_then(|source_ref| source_id_by_ref.get(&source_ref).copied())
108            .map(|source_id| DebugSourceNodeId::from(u32::from(source_id)));
109        Ok(PackageExport::Procedure(ProcedureExport {
110            digest: self.digest,
111            path: self.path,
112            node: Some(node),
113            source_node,
114            signature: self.signature,
115            attributes: self.attributes,
116        }))
117    }
118}
119
120// ASSEMBLER
121// ================================================================================================
122
123/// The [Assembler] produces a _Merkelized Abstract Syntax Tree (MAST)_ from Miden Assembly sources,
124/// as a [`Package`] artifact. In general, packages come in three primary varieties:
125///
126/// * A kernel library (i.e. [`TargetType::Kernel`])
127/// * A program (see [`TargetType::Executable`])
128/// * A library (all other target types)
129///
130/// Assembled artifacts can additionally reference or include code from previously assembled
131/// libraries.
132///
133/// # Usage
134///
135/// Depending on your needs, there are multiple ways of using the assembler, starting with the
136/// type of artifact you want to produce:
137///
138/// * If you wish to produce an executable program, you will call [`Self::assemble_program`] with
139///   the source module which contains the program entrypoint.
140/// * If you wish to produce a library for use in other executables, you will call
141///   [`Self::assemble_library`] with the source module(s) whose exports form the public API of the
142///   library.
143/// * If you wish to produce a kernel library, you will call [`Self::assemble_kernel`] with the
144///   source module(s) whose exports form the public API of the kernel.
145///
146/// In the case where you are assembling a library or program, you also need to determine if you
147/// need to specify a kernel. You will need to do so if any of your code needs to call into the
148/// kernel directly.
149///
150/// * If a kernel is needed, you should construct an `Assembler` using [`Assembler::with_kernel`]
151/// * Otherwise, you should construct an `Assembler` using [`Assembler::new`]
152///
153/// <div class="warning">
154/// Programs compiled with an empty kernel cannot use the `syscall` instruction.
155/// </div>
156///
157/// Lastly, you need to provide inputs to the assembler which it will use at link time to resolve
158/// references to procedures which are externally-defined (i.e. not defined in any of the modules
159/// provided to the `assemble_*` function you called). There are a few different ways to do this:
160///
161/// * If you have source code, or a [`ast::Module`], see [`Self::compile_and_statically_link`]
162/// * If you need to reference procedures from a previously assembled package, but do not want to
163///   include the MAST of those procedures in the assembled artifact, you want to _dynamically link_
164///   that library, see [`Linkage::Dynamic`] for more.
165/// * If you want to incorporate referenced procedures from a previously assembled package into the
166///   assembled artifact, you want to _statically link_ that library, see [`Linkage::Static`] for
167///   more.
168#[derive(Clone)]
169pub struct Assembler {
170    /// The source manager to use for compilation and source location information
171    source_manager: Arc<dyn SourceManager>,
172    /// The linker instance used internally to link assembler inputs
173    linker: Box<Linker>,
174    /// Whether to treat warning diagnostics as errors
175    warnings_as_errors: bool,
176    /// Whether to preserve debug information in the assembled artifact.
177    pub(super) emit_debug_info: bool,
178    /// Whether to trim source file paths in debug information.
179    pub(super) trim_paths: bool,
180}
181
182impl Default for Assembler {
183    fn default() -> Self {
184        let source_manager = Arc::new(DefaultSourceManager::default());
185        let linker = Box::new(Linker::new(source_manager.clone()));
186        Self {
187            source_manager,
188            linker,
189            warnings_as_errors: false,
190            emit_debug_info: true,
191            trim_paths: false,
192        }
193    }
194}
195
196// ------------------------------------------------------------------------------------------------
197/// Constructors
198impl Assembler {
199    /// Start building an [Assembler]
200    pub fn new(source_manager: Arc<dyn SourceManager>) -> Self {
201        let linker = Box::new(Linker::new(source_manager.clone()));
202        Self {
203            source_manager,
204            linker,
205            warnings_as_errors: false,
206            emit_debug_info: true,
207            trim_paths: false,
208        }
209    }
210
211    /// Start building an [`Assembler`] with a kernel defined by the provided kernel package.
212    pub fn with_kernel(
213        source_manager: Arc<dyn SourceManager>,
214        kernel: Arc<Package>,
215    ) -> Result<Self, Report> {
216        let linker = Box::new(Linker::with_kernel(source_manager.clone(), kernel)?);
217        Ok(Self {
218            source_manager,
219            linker,
220            ..Default::default()
221        })
222    }
223
224    /// Sets the default behavior of this assembler with regard to warning diagnostics.
225    ///
226    /// When true, any warning diagnostics that are emitted will be promoted to errors.
227    pub fn with_warnings_as_errors(mut self, yes: bool) -> Self {
228        self.warnings_as_errors = yes;
229        self
230    }
231
232    /// Configure this assembler based on configuration in `profile`
233    pub fn with_profile(mut self, profile: &miden_project::Profile) -> Self {
234        self.emit_debug_info = profile.should_emit_debug_info();
235        self.trim_paths = profile.should_trim_paths();
236        self
237    }
238}
239
240// ------------------------------------------------------------------------------------------------
241/// Dependency Management
242impl Assembler {
243    /// Ensures `module` is compiled, and then statically links it into the final artifact.
244    ///
245    /// The given module must be a library module, or an error will be returned.
246    #[inline]
247    pub fn compile_and_statically_link(&mut self, module: impl Parse) -> Result<&mut Self, Report> {
248        self.compile_and_statically_link_all([module])
249    }
250
251    /// Ensures every module in `modules` is compiled, and then statically links them into the final
252    /// artifact.
253    ///
254    /// All of the given modules must be library modules, or an error will be returned.
255    pub fn compile_and_statically_link_all(
256        &mut self,
257        modules: impl IntoIterator<Item = impl Parse>,
258    ) -> Result<&mut Self, Report> {
259        let modules = modules
260            .into_iter()
261            .map(|module| module.parse(self.warnings_as_errors, self.source_manager.clone()))
262            .collect::<Result<Vec<_>, Report>>()?;
263
264        self.linker.link_modules(modules)?;
265
266        Ok(self)
267    }
268
269    /// Compiles and statically links all Miden Assembly modules reachable from the provided root
270    /// module. The namespace of the resulting modules will be derived from an explicit namespace
271    /// declaration in the root module, or from `namespace` if provided - if both are present, they
272    /// must agree.
273    ///
274    /// The module structure is determined by `mod` declarations reachable from the root module,
275    /// i.e. if the root module contains the line `mod foo`, then a submodule `foo` in the namespace
276    /// of the root module will be located and parsed.
277    ///
278    /// If provided `namespace` can be any valid Miden Assembly path, e.g. `std` is a valid path, as
279    /// is `std::math::u64` - there is no requirement that the namespace be a single identifier.
280    /// This allows defining multiple projects relative to a common root namespace without conflict.
281    ///
282    /// For example, let's say I call this function like so:
283    ///
284    /// ```rust
285    /// use miden_assembly::{Assembler, Path};
286    ///
287    /// let mut assembler = Assembler::default();
288    /// assembler.compile_and_statically_link_from_root("~/masm/core/lib.masm", None);
289    /// ```
290    ///
291    /// And `lib.masm` contains:
292    ///
293    /// ```text,ignore
294    /// namespace miden::core
295    ///
296    /// pub mod sys;
297    /// pub mod math;
298    /// ```
299    ///
300    /// Then either of the following directory layouts would be parsed successfully, with the
301    /// namespacing shown:
302    ///
303    /// Layout 1: Submodules are defined at the same level as the parent, named after their module
304    /// name:
305    ///
306    /// - ~/masm/core/lib.masm        -> Parsed as "miden::core"
307    /// - ~/masm/core/sys.masm        -> Parsed as "miden::core::sys"
308    /// - ~/masm/core/math.masm       -> Parsed as "miden::core::math"
309    /// - ~/masm/core/math/README.md  -> Ignored
310    ///
311    /// Layout 2: Submodules are defined in sub-directories named after their module name:
312    ///
313    /// - ~/masm/core/lib.masm        -> Parsed as "miden::core"
314    /// - ~/masm/core/sys/mod.masm    -> Parsed as "miden::core::sys"
315    /// - ~/masm/core/math/mod.masm   -> Parsed as "miden::core::math"
316    /// - ~/masm/core/math/README.md  -> Ignored
317    #[cfg(feature = "std")]
318    pub fn compile_and_statically_link_from_root(
319        &mut self,
320        root: impl AsRef<std::path::Path>,
321        namespace: Option<&Path>,
322    ) -> Result<(), Report> {
323        use miden_assembly_syntax::parser;
324
325        let (root, modules) = parser::read_modules_from_root(
326            root,
327            namespace.map(Into::into),
328            None,
329            self.source_manager.clone(),
330            self.warnings_as_errors,
331        )?;
332        self.linker.link_modules(core::iter::once(root).chain(modules))?;
333        Ok(())
334    }
335
336    /// Link against `package` with the specified linkage mode during assembly.
337    pub fn with_package(mut self, package: Arc<Package>, linkage: Linkage) -> Result<Self, Report> {
338        self.link_package(package, linkage)?;
339        Ok(self)
340    }
341
342    /// Link against `package` with the specified linkage mode during assembly.
343    pub fn link_package(&mut self, package: Arc<Package>, linkage: Linkage) -> Result<(), Report> {
344        match package.kind {
345            TargetType::Kernel => {
346                if !self.kernel().is_empty() {
347                    return Err(Report::msg(format!(
348                        "duplicate kernels present in the dependency graph: '{}@{}' conflicts with another kernel we've already linked",
349                        package.name, package.version
350                    )));
351                }
352
353                self.linker.link_with_kernel(package)?;
354                Ok(())
355            },
356            TargetType::Executable => {
357                Err(Report::msg("cannot add executable packages to an assembler"))
358            },
359            _ => {
360                self.linker
361                    .link_library(LinkLibrary::from_package(package).with_linkage(linkage))?;
362                Ok(())
363            },
364        }
365    }
366}
367
368// ------------------------------------------------------------------------------------------------
369/// Public Accessors
370impl Assembler {
371    /// Returns true if this assembler promotes warning diagnostics as errors by default.
372    pub fn warnings_as_errors(&self) -> bool {
373        self.warnings_as_errors
374    }
375
376    /// Returns a reference to the kernel for this assembler.
377    ///
378    /// If the assembler was instantiated without a kernel, the internal kernel will be empty.
379    pub fn kernel(&self) -> &KernelDescriptor {
380        self.linker.kernel()
381    }
382
383    #[cfg(any(feature = "std", all(test, feature = "std")))]
384    pub(crate) fn source_manager(&self) -> Arc<dyn SourceManager> {
385        self.source_manager.clone()
386    }
387
388    #[cfg(any(test, feature = "testing"))]
389    #[doc(hidden)]
390    pub fn linker(&self) -> &Linker {
391        &self.linker
392    }
393}
394
395// ------------------------------------------------------------------------------------------------
396/// Compilation/Assembly
397impl Assembler {
398    /// Assembles a root module, and its supporting submodules into a library [`Package`].
399    ///
400    /// # Errors
401    ///
402    /// Returns an error if parsing or compilation of the specified modules fails.
403    pub fn assemble_library(
404        self,
405        name: impl Into<PackageId>,
406        root: impl Parse,
407        support: impl IntoIterator<Item = impl Parse>,
408    ) -> Result<Box<Package>, Report> {
409        let root = root.parse(self.warnings_as_errors, self.source_manager.clone())?;
410        let support = support
411            .into_iter()
412            .map(|module| module.parse(self.warnings_as_errors, self.source_manager.clone()))
413            .collect::<Result<Vec<_>, Report>>()?;
414
415        let emit_debug_info = self.emit_debug_info;
416        self.assemble_library_modules(name.into(), root, support, TargetType::Library)?
417            .into_artifact(emit_debug_info)
418    }
419
420    /// Assemble a library [`Package`] from the set of modules reachable from `root`.
421    ///
422    /// See [Assembler::compile_and_statically_link_from_root] for details on how modules are
423    /// discovered and linked from `root`.
424    #[cfg(feature = "std")]
425    pub fn assemble_library_from_root(
426        self,
427        root: impl AsRef<std::path::Path>,
428        namespace: Option<&Path>,
429    ) -> Result<Box<Package>, Report> {
430        use miden_assembly_syntax::parser;
431
432        let root = root.as_ref().to_path_buf();
433        let namespace = namespace.map(Into::into);
434        let (root, support) = parser::read_modules_from_root(
435            &root,
436            namespace,
437            Some(ModuleKind::Library),
438            self.source_manager.clone(),
439            self.warnings_as_errors,
440        )?;
441
442        // Derive the package name from the namespace of the root module
443        let name = root.path().to_relative().as_str().replace("::", "-");
444
445        let emit_debug_info = self.emit_debug_info;
446        self.assemble_library_modules(name.into(), root, support, TargetType::Library)?
447            .into_artifact(emit_debug_info)
448    }
449
450    /// Assembles the provided module into a kernel package.
451    ///
452    /// # Errors
453    ///
454    /// Returns an error if parsing or compilation of the specified modules fails.
455    pub fn assemble_kernel(
456        self,
457        name: impl Into<PackageId>,
458        root: Box<ast::Module>,
459        support: impl IntoIterator<Item = Box<ast::Module>>,
460    ) -> Result<Box<Package>, Report> {
461        let emit_debug_info = self.emit_debug_info;
462        self.assemble_library_modules(name.into(), root, support, TargetType::Kernel)?
463            .into_artifact(emit_debug_info)
464    }
465
466    /// Assemble a kernel [`Package`] from a standard Miden Assembly kernel project layout.
467    ///
468    /// The kernel library will export procedures defined by the module at `sys_module_path`.
469    ///
470    /// If the optional `lib_dir` is provided, all modules under this directory will be available
471    /// from the kernel module under the `$kernel` namespace. For example, if `lib_dir` is set to
472    /// "~/masm/lib", the files will be accessible in the kernel module as follows:
473    ///
474    /// - ~/masm/lib/foo.masm        -> Can be imported as "$kernel::foo"
475    /// - ~/masm/lib/bar/baz.masm    -> Can be imported as "$kernel::bar::baz"
476    ///
477    /// Note: this is a temporary structure which will likely change once
478    /// <https://github.com/0xMiden/miden-vm/issues/1436> is implemented.
479    #[cfg(feature = "std")]
480    pub fn assemble_kernel_from_root(
481        self,
482        name: impl Into<PackageId>,
483        sys_module_path: impl AsRef<std::path::Path>,
484    ) -> Result<Box<Package>, Report> {
485        let sys_module_path = sys_module_path.as_ref();
486        let namespace = Some(Path::KERNEL.into());
487        let (root, support) = miden_assembly_syntax::parser::read_modules_from_root(
488            sys_module_path,
489            namespace,
490            Some(ModuleKind::Kernel),
491            self.source_manager.clone(),
492            self.warnings_as_errors,
493        )?;
494
495        let emit_debug_info = self.emit_debug_info;
496        self.assemble_library_modules(name.into(), root, support, TargetType::Kernel)?
497            .into_artifact(emit_debug_info)
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, debug_info, source_id_by_ref) =
583            mast_forest_builder.build()?.into_parts_with_debug_info();
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, debug_info, 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                            Some(&self.linker[gid.module].path().join(&item.name)),
667                            item.digest,
668                            item.source_library_commitment(),
669                            item.source_root_id(),
670                            item.source_debug_root_id().map(DebugSourceNodeId::from),
671                            mast_forest_builder,
672                        )?;
673                        ResolvedProcedure { node, signature: item.signature.clone() }
674                    },
675                };
676                let digest = item.digest;
677                let ResolvedProcedure { node, signature } = resolved;
678                let attributes = item.attributes.clone();
679                let pctx = ProcedureContext::new(
680                    gid,
681                    /* is_program_entrypoint= */ false,
682                    symbol_path.clone(),
683                    Visibility::Public,
684                    signature.clone(),
685                    module_kind.is_kernel(),
686                    self.source_manager.clone(),
687                );
688
689                let procedure = pctx.into_procedure(digest, node);
690                self.linker.register_procedure_root(gid, digest);
691                mast_forest_builder.insert_procedure(gid, procedure, &self.source_manager)?;
692                PendingPackageExport::Procedure(PendingProcedureExport {
693                    digest,
694                    path: symbol_path,
695                    node_ref: node,
696                    source_ref: mast_forest_builder.latest_source_ref_for_node_ref(node),
697                    signature: signature.map(|sig| (*sig).clone()),
698                    attributes,
699                })
700            },
701            SymbolItem::Compiled(ItemInfo::Constant(item)) => {
702                PendingPackageExport::Constant(ConstantExport {
703                    path: symbol_path,
704                    value: item.value.clone(),
705                })
706            },
707            SymbolItem::Compiled(ItemInfo::Type(item)) => {
708                PendingPackageExport::Type(TypeExport { path: symbol_path, ty: item.ty.clone() })
709            },
710            SymbolItem::Procedure(_) => {
711                self.compile_subgraph(SubgraphRoot::not_as_entrypoint(gid), mast_forest_builder)?;
712                let proc = mast_forest_builder
713                    .get_procedure(gid)
714                    .expect("compilation succeeded but root not found in cache");
715                let digest = proc.mast_root();
716                let signature = self.linker.resolve_signature(gid)?;
717                let attributes = self.linker.resolve_attributes(gid);
718                PendingPackageExport::Procedure(PendingProcedureExport {
719                    digest,
720                    path: symbol_path,
721                    node_ref: proc.body_node_ref(),
722                    source_ref: mast_forest_builder
723                        .latest_source_ref_for_node_ref(proc.body_node_ref()),
724                    signature: signature.map(Arc::unwrap_or_clone),
725                    attributes,
726                })
727            },
728            SymbolItem::Constant(item) => {
729                // Evaluate constant to a concrete value for export
730                let value = self.linker.const_eval(gid, &item.value, &mut cache)?;
731
732                PendingPackageExport::Constant(ConstantExport { path: symbol_path, value })
733            },
734            SymbolItem::Type(item) => {
735                let ty = self.linker.resolve_type(item.span(), gid)?;
736                PendingPackageExport::Type(TypeExport { path: symbol_path, ty })
737            },
738        };
739
740        Ok(export)
741    }
742
743    fn export_import(
744        &mut self,
745        module: ModuleIndex,
746        module_kind: ModuleKind,
747        symbol_path: Arc<Path>,
748        import: &Import,
749        mast_forest_builder: &mut MastForestBuilder,
750    ) -> Result<PendingPackageExport, Report> {
751        if let Some(resolved) = import.resolved() {
752            return self.export_symbol(resolved, module_kind, symbol_path, mast_forest_builder);
753        }
754
755        let target = import.target_path();
756        let context = SymbolResolutionContext {
757            span: target.span(),
758            module,
759            kind: Some(InvokeKind::ProcRef),
760        };
761        match self.linker.resolve_path(&context, target.inner())? {
762            SymbolResolution::Exact { gid, .. } => {
763                self.export_symbol(gid, module_kind, symbol_path, mast_forest_builder)
764            },
765            SymbolResolution::Module { .. }
766            | SymbolResolution::MastRoot(_)
767            | SymbolResolution::Local(_)
768            | SymbolResolution::External(_) => {
769                Err(self.unresolved_import_report("export", &symbol_path, import))
770            },
771        }
772    }
773
774    /// Compiles the provided module into an executable package.
775    ///
776    /// The resulting program can be executed on Miden VM.
777    ///
778    /// # Errors
779    ///
780    /// Returns an error if parsing or compilation of the specified program fails, or if the source
781    /// doesn't have an entrypoint.
782    pub fn assemble_program(
783        self,
784        name: impl Into<PackageId>,
785        source: impl Parse,
786    ) -> Result<Box<Package>, Report> {
787        let program = source.parse(self.warnings_as_errors, self.source_manager.clone())?;
788        if !program.is_executable() {
789            return Err(Report::msg(
790                "unable to assemble program: source is not an executable module",
791            ));
792        }
793
794        let emit_debug_info = self.emit_debug_info;
795        self.assemble_executable_modules(name.into(), program, [])?
796            .into_artifact(emit_debug_info)
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        let entry_source_ref = mast_forest_builder.latest_source_ref_for_node_ref(entry_node_ref);
1063
1064        let (mast_forest, node_id_by_ref, debug_info, source_id_by_ref) =
1065            mast_forest_builder.build()?.into_parts_with_debug_info();
1066        let entry_node_id = *node_id_by_ref.get(&entry_node_ref).ok_or_else(|| {
1067            Report::msg(format!("entrypoint ref {entry_node_ref} was not finalized"))
1068        })?;
1069        let entry_source_id =
1070            entry_source_ref.and_then(|source_ref| source_id_by_ref.get(&source_ref).copied());
1071
1072        let kernel_package = self.linker.kernel_package();
1073        self.finish_program_product(
1074            name,
1075            namespace,
1076            mast_forest,
1077            debug_info,
1078            entry_node_id,
1079            entry_source_id,
1080            kernel_package,
1081        )
1082    }
1083
1084    fn finish_library_product(
1085        self,
1086        name: PackageId,
1087        mast_forest: miden_core::mast::MastForest,
1088        #[cfg_attr(not(feature = "std"), allow(unused_mut))] mut debug_info: Box<PackageDebugInfo>,
1089        exports: BTreeMap<Arc<Path>, PackageExport>,
1090        modules: Vec<PackageModule>,
1091        kind: TargetType,
1092    ) -> Result<AssemblyProduct, Report> {
1093        let mast = Arc::new(mast_forest);
1094        let package = Box::new(
1095            Package::create_with_modules(
1096                name,
1097                miden_mast_package::Version::new(0, 0, 0),
1098                kind,
1099                mast,
1100                exports.into_values(),
1101                modules,
1102                None,
1103            )
1104            .map_err(Report::msg)?,
1105        );
1106
1107        #[cfg(feature = "std")]
1108        if self.emit_debug_info
1109            && let Some(trimmer) = self.source_path_trimmer()
1110        {
1111            debuginfo::trim_paths(&mut debug_info, &trimmer);
1112        }
1113
1114        Ok(AssemblyProduct::new(package, None, debug_info))
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                StaticLibrary::from_link_library(lib, debug_info).into_diagnostic()
1132            })
1133            .collect()
1134    }
1135
1136    fn finish_program_product(
1137        self,
1138        name: PackageId,
1139        namespace: Arc<Path>,
1140        mast_forest: miden_core::mast::MastForest,
1141        #[cfg_attr(not(feature = "std"), allow(unused_mut))] mut debug_info: Box<PackageDebugInfo>,
1142        entrypoint: MastNodeId,
1143        entrypoint_source_id: Option<DebugSourceNodeId>,
1144        kernel: Option<Arc<Package>>,
1145    ) -> Result<AssemblyProduct, Report> {
1146        let mast = Arc::new(mast_forest);
1147        let entry: Arc<Path> = namespace.join(ast::ProcedureName::MAIN_PROC_NAME).into();
1148        let entry_digest = mast[entrypoint].digest();
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(entrypoint_source_id),
1158                )],
1159                None,
1160            )
1161            .map_err(Report::msg)?,
1162        );
1163
1164        #[cfg(feature = "std")]
1165        if let Some(trimmer) = self.source_path_trimmer() {
1166            debuginfo::trim_paths(&mut debug_info, &trimmer);
1167        }
1168
1169        Ok(AssemblyProduct::new(package, kernel, debug_info))
1170    }
1171
1172    #[cfg(feature = "std")]
1173    fn source_path_trimmer(&self) -> Option<debuginfo::SourcePathTrimmer> {
1174        if !self.trim_paths {
1175            return None;
1176        }
1177
1178        std::env::current_dir().ok().map(debuginfo::SourcePathTrimmer::new)
1179    }
1180
1181    /// Compile the uncompiled procedure in the linked module graph which are members of the
1182    /// subgraph rooted at `root`, placing them in the MAST forest builder once compiled.
1183    ///
1184    /// Returns an error if any of the provided Miden Assembly is invalid.
1185    fn compile_subgraph(
1186        &mut self,
1187        root: SubgraphRoot,
1188        mast_forest_builder: &mut MastForestBuilder,
1189    ) -> Result<(), Report> {
1190        let mut worklist: Vec<GlobalItemIndex> = self
1191            .linker
1192            .topological_sort_from_root(root.proc_id)
1193            .map_err(|cycle| {
1194                let iter = cycle.into_node_ids();
1195                let mut nodes = Vec::with_capacity(iter.len());
1196                for node in iter {
1197                    let module = self.linker[node.module].path();
1198                    let proc = self.linker[node].name();
1199                    nodes.push(format!("{}", module.join(proc)));
1200                }
1201                LinkerError::Cycle { nodes: nodes.into() }
1202            })?
1203            .into_iter()
1204            .filter(|&gid| matches!(self.linker[gid].item(), SymbolItem::Procedure(_)))
1205            .collect();
1206
1207        assert!(!worklist.is_empty());
1208
1209        self.process_graph_worklist(&mut worklist, &root, mast_forest_builder)
1210    }
1211
1212    /// Compiles all procedures in the `worklist`.
1213    fn process_graph_worklist(
1214        &mut self,
1215        worklist: &mut Vec<GlobalItemIndex>,
1216        root: &SubgraphRoot,
1217        mast_forest_builder: &mut MastForestBuilder,
1218    ) -> Result<(), Report> {
1219        // Process the topological ordering in reverse order (bottom-up), so that
1220        // each procedure is compiled with all of its dependencies fully compiled
1221        while let Some(procedure_gid) = worklist.pop() {
1222            // If we have already compiled this procedure, do not recompile
1223            if let Some(proc) = mast_forest_builder.get_procedure(procedure_gid) {
1224                self.linker.register_procedure_root(procedure_gid, proc.mast_root());
1225                continue;
1226            }
1227            // Fetch procedure metadata from the graph
1228            let (module_kind, module_path) = {
1229                let module = &self.linker[procedure_gid.module];
1230                (module.kind(), module.path().clone())
1231            };
1232            match self.linker[procedure_gid].item() {
1233                SymbolItem::Procedure(proc) => {
1234                    let proc = proc.borrow();
1235                    let num_locals = proc.num_locals();
1236                    let path = Arc::<Path>::from(module_path.join(proc.name().as_str()));
1237                    let signature = self.linker.resolve_signature(procedure_gid)?;
1238                    let is_program_entrypoint =
1239                        root.is_program_entrypoint && root.proc_id == procedure_gid;
1240
1241                    let pctx = ProcedureContext::new(
1242                        procedure_gid,
1243                        is_program_entrypoint,
1244                        path.clone(),
1245                        proc.visibility(),
1246                        signature.clone(),
1247                        module_kind.is_kernel(),
1248                        self.source_manager.clone(),
1249                    )
1250                    .with_span(proc.span())
1251                    .with_num_locals(num_locals)?;
1252
1253                    // Compile this procedure
1254                    let procedure = self.compile_procedure(pctx, mast_forest_builder)?;
1255                    // TODO: if a re-exported procedure with the same MAST root had been previously
1256                    // added to the builder, this will result in unreachable nodes added to the
1257                    // MAST forest. This is because while we won't insert a duplicate node for the
1258                    // procedure body node itself, all nodes that make up the procedure body would
1259                    // be added to the forest.
1260
1261                    // Cache the compiled procedure
1262                    drop(proc);
1263                    self.linker.register_procedure_root(procedure_gid, procedure.mast_root());
1264                    mast_forest_builder.insert_procedure(
1265                        procedure_gid,
1266                        procedure,
1267                        self.source_manager.as_ref(),
1268                    )?;
1269                },
1270                SymbolItem::Compiled(_) | SymbolItem::Constant(_) | SymbolItem::Type(_) => {
1271                    // There is nothing to do for other items that might have edges in the graph
1272                },
1273            }
1274        }
1275
1276        Ok(())
1277    }
1278
1279    fn unresolved_import_report(
1280        &self,
1281        action: &'static str,
1282        symbol_path: &Path,
1283        import: &Import,
1284    ) -> Report {
1285        let target = import.target_path();
1286        let span = target.span();
1287
1288        RelatedLabel::error(format!(
1289            "unable to {action} import '{symbol_path}' targeting '{}'",
1290            target.inner()
1291        ))
1292        .with_labeled_span(span, "this import target does not resolve to a concrete item")
1293        .with_help("imports must resolve to a concrete item before they can be used")
1294        .with_source_file(self.source_manager.get(span.source_id()).ok())
1295        .into()
1296    }
1297
1298    /// Compiles a single Miden Assembly procedure to its MAST representation.
1299    fn compile_procedure(
1300        &self,
1301        mut proc_ctx: ProcedureContext,
1302        mast_forest_builder: &mut MastForestBuilder,
1303    ) -> Result<Procedure, Report> {
1304        // Make sure the current procedure context is available during codegen
1305        let gid = proc_ctx.id();
1306
1307        let num_locals = proc_ctx.num_locals();
1308
1309        let proc = match self.linker[gid].item() {
1310            SymbolItem::Procedure(proc) => proc.borrow(),
1311            _ => panic!("expected item to be a procedure AST"),
1312        };
1313        let body_wrapper = if proc_ctx.is_program_entrypoint() {
1314            // The primary check now lives at the AST mutation site (`Procedure::set_num_locals`).
1315            // This backstop still catches entrypoints constructed with locals directly via
1316            // `Procedure::new`, which bypasses that setter.
1317            assert!(num_locals == 0, "program entrypoint cannot have locals");
1318
1319            Some(BodyWrapper {
1320                prologue: fmp_initialization_sequence(),
1321                epilogue: Vec::new(),
1322            })
1323        } else if num_locals > 0 {
1324            Some(BodyWrapper {
1325                prologue: fmp_start_frame_sequence(num_locals),
1326                epilogue: fmp_end_frame_sequence(num_locals),
1327            })
1328        } else {
1329            None
1330        };
1331
1332        let proc_body_ref =
1333            self.compile_body(proc.iter(), &mut proc_ctx, body_wrapper, mast_forest_builder, 0)?;
1334
1335        let proc_mast_root = mast_forest_builder
1336            .mast_root_for_ref(proc_body_ref)
1337            .expect("no MAST node for compiled procedure");
1338        Ok(proc_ctx.into_procedure(proc_mast_root, proc_body_ref))
1339    }
1340
1341    /// Creates assembly operation metadata for control flow nodes.
1342    fn create_asm_op(
1343        &self,
1344        span: &SourceSpan,
1345        op_name: &str,
1346        proc_ctx: &ProcedureContext,
1347    ) -> AssemblyOp {
1348        let location = proc_ctx.source_manager().location(*span).ok();
1349        let context_name = proc_ctx.path().to_string();
1350        let num_cycles = 0;
1351        AssemblyOp::new(location, context_name, num_cycles, op_name.to_string())
1352    }
1353
1354    fn compile_body<'a, I>(
1355        &self,
1356        body: I,
1357        proc_ctx: &mut ProcedureContext,
1358        wrapper: Option<BodyWrapper>,
1359        mast_forest_builder: &mut MastForestBuilder,
1360        nesting_depth: usize,
1361    ) -> Result<MastNodeRef, Report>
1362    where
1363        I: Iterator<Item = &'a ast::Op>,
1364    {
1365        use ast::Op;
1366
1367        let mut body_node_refs: Vec<MastNodeRef> = Vec::new();
1368        let mut block_builder = BasicBlockBuilder::new(wrapper, mast_forest_builder);
1369
1370        for op in body {
1371            match op {
1372                Op::Inst(inst) => {
1373                    if let Some(node_ref) =
1374                        self.compile_instruction(inst, &mut block_builder, proc_ctx)?
1375                    {
1376                        if let Some(basic_block_id) = block_builder.make_basic_block()? {
1377                            body_node_refs.push(basic_block_id);
1378                        }
1379
1380                        body_node_refs.push(node_ref);
1381                    }
1382                },
1383
1384                Op::If { then_blk, else_blk, span } => {
1385                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1386                        body_node_refs.push(basic_block_id);
1387                    }
1388
1389                    let next_depth = nesting_depth + 1;
1390                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1391                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1392                            span: *span,
1393                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1394                            max_depth: MAX_CONTROL_FLOW_NESTING,
1395                        }));
1396                    }
1397
1398                    let then_blk = self.compile_body(
1399                        then_blk.iter(),
1400                        proc_ctx,
1401                        None,
1402                        block_builder.mast_forest_builder_mut(),
1403                        next_depth,
1404                    )?;
1405                    let else_blk = self.compile_body(
1406                        else_blk.iter(),
1407                        proc_ctx,
1408                        None,
1409                        block_builder.mast_forest_builder_mut(),
1410                        next_depth,
1411                    )?;
1412
1413                    let asm_op = self.create_asm_op(span, "if.true", proc_ctx);
1414                    let split_node_ref = block_builder
1415                        .mast_forest_builder_mut()
1416                        .ensure_split_node_ref([then_blk, else_blk], asm_op)?;
1417
1418                    body_node_refs.push(split_node_ref);
1419                },
1420
1421                Op::Repeat { count, body, span } => {
1422                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1423                        body_node_refs.push(basic_block_id);
1424                    }
1425
1426                    let next_depth = nesting_depth + 1;
1427                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1428                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1429                            span: *span,
1430                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1431                            max_depth: MAX_CONTROL_FLOW_NESTING,
1432                        }));
1433                    }
1434
1435                    let repeat_node_ref = self.compile_body(
1436                        body.iter(),
1437                        proc_ctx,
1438                        None,
1439                        block_builder.mast_forest_builder_mut(),
1440                        next_depth,
1441                    )?;
1442
1443                    let iteration_count = (*count).expect_value();
1444                    if iteration_count == 0 {
1445                        return Err(RelatedLabel::error("invalid repeat count")
1446                            .with_help("repeat count must be greater than 0")
1447                            .with_labeled_span(count.span(), "repeat count must be at least 1")
1448                            .with_source_file(
1449                                proc_ctx.source_manager().get(proc_ctx.span().source_id()).ok(),
1450                            )
1451                            .into());
1452                    }
1453                    if iteration_count > MAX_REPEAT_COUNT {
1454                        return Err(RelatedLabel::error("invalid repeat count")
1455                            .with_help(format!(
1456                                "repeat count must be less than or equal to {MAX_REPEAT_COUNT}",
1457                            ))
1458                            .with_labeled_span(
1459                                count.span(),
1460                                format!("repeat count exceeds {MAX_REPEAT_COUNT}"),
1461                            )
1462                            .with_source_file(
1463                                proc_ctx.source_manager().get(proc_ctx.span().source_id()).ok(),
1464                            )
1465                            .into());
1466                    }
1467
1468                    for _ in 0..iteration_count {
1469                        body_node_refs.push(repeat_node_ref);
1470                    }
1471                },
1472
1473                Op::While { body, span } => {
1474                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1475                        body_node_refs.push(basic_block_id);
1476                    }
1477
1478                    let next_depth = nesting_depth + 1;
1479                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1480                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1481                            span: *span,
1482                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1483                            max_depth: MAX_CONTROL_FLOW_NESTING,
1484                        }));
1485                    }
1486
1487                    // `while.true` desugars to `if.true { LOOP { body } } else { noop }`. The LOOP
1488                    // itself has do-while semantics: the body executes unconditionally for the
1489                    // first iteration, so the surrounding SPLIT performs the initial true-check.
1490                    //
1491                    // The `while.true` asm_op is attached to *both* the LOOP and the wrapping
1492                    // SPLIT: both nodes belong to a single source-level `while.true` construct, and
1493                    // diagnostics emitted from inside the body walk up the continuation stack to
1494                    // the nearest control-flow parent (the LOOP), so it must carry the source
1495                    // mapping too.
1496                    let asm_op = self.create_asm_op(span, "while.true", proc_ctx);
1497
1498                    let loop_body_node_ref = self.compile_body(
1499                        body.iter(),
1500                        proc_ctx,
1501                        None,
1502                        block_builder.mast_forest_builder_mut(),
1503                        next_depth,
1504                    )?;
1505                    let loop_node_ref = block_builder
1506                        .mast_forest_builder_mut()
1507                        .ensure_loop_node_ref(loop_body_node_ref, asm_op.clone())?;
1508                    let noop_block_ref = block_builder.mast_forest_builder_mut().ensure_block_ref(
1509                        vec![Operation::Noop],
1510                        vec![],
1511                        vec![],
1512                        vec![],
1513                        vec![],
1514                    )?;
1515
1516                    let split_node_ref = block_builder
1517                        .mast_forest_builder_mut()
1518                        .ensure_split_node_ref([loop_node_ref, noop_block_ref], asm_op)?;
1519
1520                    body_node_refs.push(split_node_ref);
1521                },
1522
1523                Op::DoWhile { body, condition, span } => {
1524                    if let Some(basic_block_id) = block_builder.make_basic_block()? {
1525                        body_node_refs.push(basic_block_id);
1526                    }
1527
1528                    let next_depth = nesting_depth + 1;
1529                    if next_depth > MAX_CONTROL_FLOW_NESTING {
1530                        return Err(Report::new(AssemblerError::ControlFlowNestingDepthExceeded {
1531                            span: *span,
1532                            source_file: proc_ctx.source_manager().get(span.source_id()).ok(),
1533                            max_depth: MAX_CONTROL_FLOW_NESTING,
1534                        }));
1535                    }
1536
1537                    // A `do { body } while { cond } end` loop maps directly onto the LOOP node's
1538                    // native do-while semantics: the body executes unconditionally on the first
1539                    // pass, and iteration is decided at the tail. Unlike `while.true`, no SPLIT
1540                    // wrapper (head-entry check) is needed. The loop body is `body ++ cond`; the
1541                    // condition leaves the re-entry boolean on top of the stack, and the
1542                    // contiguous basic blocks are merged by the MAST forest builder.
1543                    let asm_op = self.create_asm_op(span, "do.while", proc_ctx);
1544
1545                    let loop_body_node_ref = self.compile_body(
1546                        body.iter().chain(condition.iter()),
1547                        proc_ctx,
1548                        None,
1549                        block_builder.mast_forest_builder_mut(),
1550                        next_depth,
1551                    )?;
1552                    let loop_node_ref = block_builder
1553                        .mast_forest_builder_mut()
1554                        .ensure_loop_node_ref(loop_body_node_ref, asm_op)?;
1555
1556                    body_node_refs.push(loop_node_ref);
1557                },
1558            }
1559        }
1560
1561        if let Some(basic_block_id) = block_builder.try_into_basic_block()? {
1562            body_node_refs.push(basic_block_id);
1563        }
1564
1565        let procedure_body_ref = if body_node_refs.is_empty() {
1566            mast_forest_builder.ensure_block_ref(
1567                vec![Operation::Noop],
1568                vec![],
1569                vec![],
1570                vec![],
1571                vec![],
1572            )?
1573        } else {
1574            let asm_op = self.create_asm_op(&proc_ctx.span(), "begin", proc_ctx);
1575            mast_forest_builder.join_node_refs(body_node_refs, Some(asm_op))?
1576        };
1577
1578        Ok(procedure_body_ref)
1579    }
1580
1581    /// Resolves the specified target to the corresponding procedure root [`MastNodeRef`].
1582    ///
1583    /// If no [`MastNodeRef`] exists for that procedure root, we wrap the root in an
1584    /// [`crate::mast::ExternalNode`], and return the resulting [`MastNodeRef`].
1585    pub(super) fn resolve_target(
1586        &self,
1587        kind: InvokeKind,
1588        target: &InvocationTarget,
1589        caller_module: ModuleIndex,
1590        mast_forest_builder: &mut MastForestBuilder,
1591    ) -> Result<ResolvedProcedure, Report> {
1592        let caller = SymbolResolutionContext {
1593            span: target.span(),
1594            module: caller_module,
1595            kind: Some(kind),
1596        };
1597        let resolved = self.linker.resolve_invoke_target(&caller, target)?;
1598        match resolved {
1599            SymbolResolution::MastRoot(mast_root) => {
1600                let path = match target {
1601                    InvocationTarget::Path(path) => Some(path.inner().as_ref()),
1602                    InvocationTarget::MastRoot(_) | InvocationTarget::Symbol(_) => None,
1603                };
1604                let node = self.ensure_valid_procedure_mast_root(
1605                    kind,
1606                    target.span(),
1607                    path,
1608                    mast_root.into_inner(),
1609                    None,
1610                    None,
1611                    None,
1612                    mast_forest_builder,
1613                )?;
1614                Ok(ResolvedProcedure { node, signature: None })
1615            },
1616            SymbolResolution::Exact { gid, .. } => {
1617                match mast_forest_builder.get_procedure(gid) {
1618                    Some(proc) => Ok(ResolvedProcedure {
1619                        node: proc.body_node_ref(),
1620                        signature: proc.signature(),
1621                    }),
1622                    // We didn't find the procedure in our current MAST forest. We still need to
1623                    // check if it exists in one of a library dependency.
1624                    None => match self.linker[gid].item() {
1625                        SymbolItem::Compiled(ItemInfo::Procedure(p)) => {
1626                            let node = self.ensure_valid_procedure_mast_root(
1627                                kind,
1628                                target.span(),
1629                                Some(&self.linker[gid.module].path().join(&p.name)),
1630                                p.digest,
1631                                p.source_library_commitment(),
1632                                p.source_root_id(),
1633                                p.source_debug_root_id().map(DebugSourceNodeId::from),
1634                                mast_forest_builder,
1635                            )?;
1636                            Ok(ResolvedProcedure { node, signature: p.signature.clone() })
1637                        },
1638                        SymbolItem::Procedure(_) => panic!(
1639                            "AST procedure {gid:?} exists in the linker, but not in the MastForestBuilder"
1640                        ),
1641                        SymbolItem::Compiled(_) | SymbolItem::Type(_) | SymbolItem::Constant(_) => {
1642                            unreachable!("invoke resolver should reject non-procedure targets")
1643                        },
1644                    },
1645                }
1646            },
1647            SymbolResolution::Module { .. }
1648            | SymbolResolution::External(_)
1649            | SymbolResolution::Local(_) => unreachable!(),
1650        }
1651    }
1652
1653    /// Verifies the validity of the MAST root as a procedure root hash, and adds it to the forest.
1654    ///
1655    /// If the root is present in the vendored MAST, its subtree is copied. Otherwise an
1656    /// external node is added to the forest.
1657    fn ensure_valid_procedure_mast_root(
1658        &self,
1659        kind: InvokeKind,
1660        span: SourceSpan,
1661        path: Option<&Path>,
1662        mast_root: Word,
1663        source_library_commitment: Option<Word>,
1664        source_root_id: Option<MastNodeId>,
1665        source_debug_root_id: Option<DebugSourceNodeId>,
1666        mast_forest_builder: &mut MastForestBuilder,
1667    ) -> Result<MastNodeRef, Report> {
1668        // Get the procedure from the assembler
1669        let current_source_file = self.source_manager.get(span.source_id()).ok();
1670
1671        if matches!(kind, InvokeKind::SysCall) && self.linker.has_nonempty_kernel() {
1672            // NOTE: The assembler is expected to know the full set of all kernel
1673            // procedures at this point, so if the digest is not present in the kernel,
1674            // it is a definite error.
1675            if !self.linker.kernel().contains_proc(mast_root) {
1676                let callee = path
1677                    .map(|p| p.to_path_buf().into_boxed_path().into())
1678                    .or_else(|| {
1679                        mast_forest_builder
1680                            .find_procedure_by_mast_root(&mast_root)
1681                            .map(|proc| proc.path().clone())
1682                    })
1683                    .unwrap_or_else(|| {
1684                        let digest_path = format!("{mast_root}");
1685                        Arc::<Path>::from(Path::new(&digest_path))
1686                    });
1687                return Err(Report::new(LinkerError::InvalidSysCallTarget {
1688                    span,
1689                    source_file: current_source_file,
1690                    callee,
1691                }));
1692            }
1693        }
1694
1695        mast_forest_builder.ensure_external_link_with_source_ref(
1696            mast_root,
1697            source_library_commitment,
1698            source_root_id,
1699            source_debug_root_id,
1700        )
1701    }
1702}
1703
1704// HELPERS
1705// ================================================================================================
1706
1707/// Information about the root of a subgraph to be compiled.
1708///
1709/// `is_program_entrypoint` is true if the root procedure is the entrypoint of an executable
1710/// program.
1711struct SubgraphRoot {
1712    proc_id: GlobalItemIndex,
1713    is_program_entrypoint: bool,
1714}
1715
1716impl SubgraphRoot {
1717    fn with_entrypoint(proc_id: GlobalItemIndex) -> Self {
1718        Self { proc_id, is_program_entrypoint: true }
1719    }
1720
1721    fn not_as_entrypoint(proc_id: GlobalItemIndex) -> Self {
1722        Self { proc_id, is_program_entrypoint: false }
1723    }
1724}
1725
1726/// Contains a set of operations which need to be executed before and after a sequence of AST
1727/// nodes (i.e., code body).
1728pub(crate) struct BodyWrapper {
1729    pub prologue: Vec<Operation>,
1730    pub epilogue: Vec<Operation>,
1731}
1732
1733pub(super) struct ResolvedProcedure {
1734    pub node: MastNodeRef,
1735    pub signature: Option<Arc<FunctionType>>,
1736}
miden_assembly/assembler.rs

miden_assembly/
assembler.rs
