Struct MastForest 

pub struct MastForest { /* private fields */ }

Represents one or more procedures, represented as a collection of MastNodes.

A MastForest does not have an entrypoint, and hence is not executable. A crate::program::Program can be built from a MastForest to specify an entrypoint.

Implementations

impl MastForest

Constructors

pub fn new() -> MastForest

Creates a new empty MastForest.

impl MastForest

State mutators

pub fn make_root(&mut self, new_root_id: MastNodeId)

Marks the given MastNodeId as being the root of a procedure.

If the specified node is already marked as a root, this will have no effect.

Panics

• if new_root_id’s internal index is larger than the number of nodes in this forest (i.e. clearly doesn’t belong to this MAST forest).

pub fn remove_nodes( &mut self, nodes_to_remove: &BTreeSet<MastNodeId>, ) -> BTreeMap<MastNodeId, MastNodeId>

Removes all nodes in the provided set from the MAST forest. The nodes MUST be orphaned (i.e. have no parent). Otherwise, this parent’s reference is considered “dangling” after the removal (i.e. will point to an incorrect node after the removal), and this removal operation would result in an invalid MastForest.

It also returns the map from old node IDs to new node IDs. Any MastNodeId used in reference to the old MastForest should be remapped using this map.

pub fn clear_debug_info(&mut self)

Clears all DebugInfo from this forest: decorators, error codes, and procedure names.

let mut forest = MastForest::new();
forest.clear_debug_info();
assert!(forest.decorators().is_empty());

pub fn compact(self) -> (MastForest, MastForestRootMap)

Compacts the forest by merging duplicate nodes.

This operation performs node deduplication by merging the forest with itself. The method assumes that debug info has already been cleared if that is desired. This method consumes the forest and returns a new compacted forest.

The process works by:

1. Merging the forest with itself to deduplicate identical nodes
2. Updating internal node references and remappings
3. Returning the compacted forest and root map

Examples

use miden_core::mast::MastForest;

let mut forest = MastForest::new();
// Add nodes to the forest

// First clear debug info if needed
forest.clear_debug_info();

// Then compact the forest (consumes the original)
let (compacted_forest, root_map) = forest.compact();

// compacted_forest is now compacted with duplicate nodes merged

pub fn merge<'forest>( forests: impl IntoIterator<Item = &'forest MastForest>, ) -> Result<(MastForest, MastForestRootMap), MastForestError>

Merges all forests into a new MastForest.

Merging two forests means combining all their constituent parts, i.e. MastNodes, Decorators and roots. During this process, any duplicate or unreachable nodes are removed. Additionally, MastNodeIds of nodes as well as DecoratorIds of decorators may change and references to them are remapped to their new location.

For example, consider this representation of a forest’s nodes with all of these nodes being roots:

[Block(foo), Block(bar)]

If we merge another forest into it:

[Block(bar), Call(0)]

then we would expect this forest:

[Block(foo), Block(bar), Call(1)]

• The Call to the bar block was remapped to its new index (now 1, previously 0).
• The Block(bar) was deduplicated any only exists once in the merged forest.

The function also returns a vector of MastForestRootMaps, whose length equals the number of passed forests. The indices in the vector correspond to the ones in forests. The map of a given forest contains the new locations of its roots in the merged forest. To illustrate, the above example would return a vector of two maps:

vec![{0 -> 0, 1 -> 1}
     {0 -> 1, 1 -> 2}]

• The root locations of the original forest are unchanged.
• For the second forest, the bar block has moved from index 0 to index 1 in the merged forest, and the Call has moved from index 1 to 2.

If any forest being merged contains an External(qux) node and another forest contains a node whose digest is qux, then the external node will be replaced with the qux node, which is effectively deduplication. Decorators are ignored when it comes to merging External nodes. This means that an External node with decorators may be replaced by a node without decorators or vice versa.

impl MastForest

This impl block contains no items.

Helpers

impl MastForest

Public accessors

pub fn get_node_by_id(&self, node_id: MastNodeId) -> Option<&MastNode>

Returns the MastNode associated with the provided MastNodeId if valid, or else None.

This is the fallible version of indexing (e.g. mast_forest[node_id]).

pub fn find_procedure_root(&self, digest: Word) -> Option<MastNodeId>

Returns the MastNodeId of the procedure associated with a given digest, if any.

pub fn is_procedure_root(&self, node_id: MastNodeId) -> bool

Returns true if a node with the specified ID is a root of a procedure in this MAST forest.

pub fn procedure_digests(&self) -> impl Iterator<Item = Word>

Returns an iterator over the digests of all procedures in this MAST forest.

pub fn local_procedure_digests(&self) -> impl Iterator<Item = Word>

Returns an iterator over the digests of local procedures in this MAST forest.

A local procedure is defined as a procedure which is not a single external node.

pub fn procedure_roots(&self) -> &[MastNodeId]

Returns an iterator over the IDs of the procedures in this MAST forest.

pub fn num_procedures(&self) -> u32

Returns the number of procedures in this MAST forest.

pub fn compute_nodes_commitment<'a>( &self, node_ids: impl IntoIterator<Item = &'a MastNodeId>, ) -> Word

Returns the Word representing the content hash of a subset of MastNodeIds.

Panics

This function panics if any node_ids is not a node of this forest.

pub fn commitment(&self) -> Word

Returns the commitment to this MAST forest.

The commitment is computed as the sequential hash of all procedure roots in the forest. This value is cached after the first computation and reused for subsequent calls, unless the forest is mutated (in which case the cache is invalidated).

The commitment uniquely identifies the forest’s structure, as each root’s digest transitively includes all of its descendants. Therefore, a commitment to all roots is a commitment to the entire forest.

pub fn num_nodes(&self) -> u32

Returns the number of nodes in this MAST forest.

pub fn nodes(&self) -> &[MastNode]

Returns the underlying nodes in this MAST forest.

pub fn advice_map(&self) -> &AdviceMap

pub fn advice_map_mut(&mut self) -> &mut AdviceMap

pub fn write_stripped<W>(&self, target: &mut W)

where W: ByteWriter,

Serializes this MastForest without debug information.

This produces a smaller output by omitting decorators, error codes, and procedure names. The resulting bytes can be deserialized with the standard Deserializable impl, which auto-detects the format and creates an empty DebugInfo.

Use this for production builds where debug info is not needed.

Example

use miden_core::{mast::MastForest, serde::Serializable};

let forest = MastForest::new();

// Full serialization (with debug info)
let full_bytes = forest.to_bytes();

// Stripped serialization (without debug info)
let mut stripped_bytes = Vec::new();
forest.write_stripped(&mut stripped_bytes);

// Both can be deserialized the same way
// let restored = MastForest::read_from_bytes(&stripped_bytes).unwrap();

impl MastForest

Decorator methods

pub fn decorators(&self) -> &[Decorator]

Returns a list of all decorators contained in this MastForest.

pub fn decorator_by_id(&self, decorator_id: DecoratorId) -> Option<&Decorator>

Returns the Decorator associated with the provided DecoratorId if valid, or else None.

This is the fallible version of indexing (e.g. mast_forest[decorator_id]).

pub fn decorators_for_op<'a>( &'a self, node_id: MastNodeId, local_op_idx: usize, ) -> impl Iterator<Item = &'a Decorator> + 'a

Returns an iterator over decorator references for a specific operation within a node.

This is the preferred method for accessing decorators, as it provides direct references to the decorator objects.

pub fn before_enter_decorators(&self, node_id: MastNodeId) -> &[DecoratorId]

Returns the decorators to be executed before this node is executed.

pub fn after_exit_decorators(&self, node_id: MastNodeId) -> &[DecoratorId]

Returns the decorators to be executed after this node is executed.

pub fn add_decorator( &mut self, decorator: Decorator, ) -> Result<DecoratorId, MastForestError>

Adds a decorator to the forest, and returns the associated DecoratorId.

pub fn get_assembly_op( &self, node_id: MastNodeId, target_op_idx: Option<usize>, ) -> Option<&AssemblyOp>

Returns the AssemblyOp associated with a node.

For basic block nodes with a target_op_idx, returns the AssemblyOp for that operation. For other nodes or when no target_op_idx is provided, returns the first AssemblyOp.

impl MastForest

Validation methods

pub fn validate(&self) -> Result<(), MastForestError>

Validates that all BasicBlockNodes in this forest satisfy the core invariants:

1. Power-of-two number of groups in each batch
2. No operation group ends with an operation requiring an immediate value
3. The last operation group in a batch cannot contain operations requiring immediate values
4. OpBatch structural consistency (num_groups <= BATCH_SIZE, group size <= GROUP_SIZE, indptr integrity, bounds checking)

This addresses the gap created by PR 2094, where padding NOOPs are now inserted at assembly time rather than dynamically during execution, and adds comprehensive structural validation to prevent deserialization-time panics.

impl MastForest

Error message methods

pub fn resolve_error_message(&self, code: Goldilocks) -> Option<Arc<str>>

Given an error code as a Felt, resolves it to its corresponding error message.

pub fn register_error(&mut self, msg: Arc<str>) -> Goldilocks

Registers an error message in the MAST Forest and returns the corresponding error code as a Felt.

impl MastForest

Procedure name methods

pub fn procedure_name(&self, digest: &Word) -> Option<&str>

Returns the procedure name for the given MAST root digest, if present.

pub fn procedure_names(&self) -> impl Iterator<Item = (Word, &Arc<str>)>

Returns an iterator over all (digest, name) pairs of procedure names.

pub fn insert_procedure_name(&mut self, digest: Word, name: Arc<str>)

Inserts a procedure name for the given MAST root digest.

pub fn debug_info(&self) -> &DebugInfo

Returns a reference to the debug info for this forest.

pub fn debug_info_mut(&mut self) -> &mut DebugInfo

Returns a mutable reference to the debug info.

This is intended for use by the assembler to register AssemblyOps and other debug information during compilation.

Trait Implementations

impl Clone for MastForest

fn clone(&self) -> MastForest

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MastForest

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Default for MastForest

fn default() -> MastForest

Returns the “default value” for a type.

impl Deserializable for MastForest

fn read_from<R>(source: &mut R) -> Result<MastForest, DeserializationError>

where R: ByteReader,

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn min_serialized_size() -> usize

Returns the minimum serialized size for one instance of this type.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

fn read_from_bytes_with_budget( bytes: &[u8], budget: usize, ) -> Result<Self, DeserializationError>

Deserializes Self from bytes with a byte budget limit.

impl<'de> Deserialize<'de> for MastForest

Available on crate feature serde only.

fn deserialize<D>( deserializer: D, ) -> Result<MastForest, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Index<DecoratorId> for MastForest

type Output = Decorator

The returned type after indexing.

fn index( &self, decorator_id: DecoratorId, ) -> &<MastForest as Index<DecoratorId>>::Output

Performs the indexing (container[index]) operation.

impl Index<MastNodeId> for MastForest

type Output = MastNode

The returned type after indexing.

fn index( &self, node_id: MastNodeId, ) -> &<MastForest as Index<MastNodeId>>::Output

Performs the indexing (container[index]) operation.

impl IndexMut<DecoratorId> for MastForest

fn index_mut( &mut self, decorator_id: DecoratorId, ) -> &mut <MastForest as Index<DecoratorId>>::Output

Performs the mutable indexing (container[index]) operation.

impl IndexMut<MastNodeId> for MastForest

fn index_mut( &mut self, node_id: MastNodeId, ) -> &mut <MastForest as Index<MastNodeId>>::Output

Performs the mutable indexing (container[index]) operation.

impl PartialEq for MastForest

Equality implementations

fn eq(&self, other: &MastForest) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serializable for MastForest

fn write_into<W>(&self, target: &mut W)

where W: ByteWriter,

Serializes self into bytes and writes these bytes into the target.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

impl Serialize for MastForest

Available on crate feature serde only.

fn serialize<S>( &self, serializer: S, ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for MastForest