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

miden_assembly/
assembler.rs
