miden_processor/

lib.rs

#![no_std]
// Trace tests intentionally use index-based `for i in a..b` over column slices; clippy's iterator
// suggestion is noisier than helpful there.
#![cfg_attr(test, allow(clippy::needless_range_loop))]

#[macro_use]
extern crate alloc;

#[cfg(feature = "std")]
extern crate std;

use alloc::vec::Vec;
use core::{
    fmt::{self, Display, LowerHex},
    ops::ControlFlow,
};

use miden_mast_package::debug_info::DebugSourceNodeId;

mod continuation_stack;
mod errors;
mod execution;
mod execution_options;
mod executor;
mod fast;
mod host;
mod processor;
mod tracer;

use miden_core::{
    deferred::{Digest, Node, PrecompileError},
    mast::ExecutableMastForest,
    serde::{Deserializable, Serializable},
};

use crate::{
    advice::{AdviceInputs, AdviceProvider},
    continuation_stack::ContinuationStack,
    errors::MapExecErr,
    processor::{Processor, SystemInterface},
    trace::RowIndex,
};

#[cfg(any(test, feature = "testing"))]
mod test_utils;
#[cfg(any(test, feature = "testing"))]
pub use test_utils::{ProcessorStateSnapshot, TestHost};

#[cfg(test)]
mod tests;

// RE-EXPORTS
// ================================================================================================

pub use continuation_stack::{Continuation, SourceInlineCallContext};
pub use errors::{
    AceError, ExecutionError, HostError, MemoryError, PackageSourceDebugContext,
    advice_error_with_package_source_context, event_error_with_package_source_context,
    procedure_not_found_with_package_source_context,
};
pub use execution_options::{ExecutionOptions, ExecutionOptionsError};
pub use executor::ProgramExecutor;
pub use fast::{
    BreakReason, DebugCallFrame, DebugCallFrameResolver, DebugFrameOrigin, ExecutionOutput,
    FastProcessor, ResumeContext,
};
pub use host::{
    BaseHost, FutureMaybeSend, Host, LoadedMastForest, MastForestStore, MemMastForestStore,
    SyncHost,
    debug::{StdoutWriter, format_value, write_interval, write_stack},
    default::{DefaultHost, HostLibrary},
};
pub use miden_core::{
    EMPTY_WORD, Felt, ONE, WORD_SIZE, Word, ZERO, crypto, field, mast,
    program::{
        ExecutionClaim, InputError, KernelDescriptor, MIN_STACK_DEPTH, Program, ProgramInfo,
        StackInputs, StackOutputs,
    },
    serde, utils,
};
pub use trace::{ExecutionWitness, PrecompileWitness, VmWitness};

pub mod advice {
    pub use miden_core::advice::{AdviceInputs, AdviceMap, AdviceStack};

    pub use super::host::{
        AdviceMutation,
        advice::{AdviceError, AdviceProvider},
    };
}

pub mod event {
    pub use miden_core::events::*;

    pub use crate::host::handlers::{
        EventError, EventHandler, EventHandlerRegistry, NoopEventHandler, TraceError, TraceHandler,
        TraceHandlerRegistry,
    };
}

pub mod operation {
    pub use miden_core::operations::*;

    pub use crate::errors::{BinaryValueErrorContext, OperationError};
}

pub mod trace;

// PROCESSOR STATE
// ===============================================================================================

/// A view into the current state of the processor.
///
/// This struct provides read access to the processor's state, including the stack, memory,
/// advice provider, and execution context information.
#[derive(Debug)]
pub struct ProcessorState<'a> {
    processor: &'a FastProcessor,
}

impl<'a> ProcessorState<'a> {
    /// Returns a reference to the advice provider.
    #[inline(always)]
    pub fn advice_provider(&self) -> &AdviceProvider {
        self.processor.advice_provider()
    }

    /// Returns the execution options.
    #[inline(always)]
    pub fn execution_options(&self) -> &ExecutionOptions {
        self.processor.execution_options()
    }

    /// Returns the current clock cycle of a process.
    #[inline(always)]
    pub fn clock(&self) -> RowIndex {
        self.processor.clock()
    }

    /// Returns the current execution context ID.
    #[inline(always)]
    pub fn ctx(&self) -> ContextId {
        self.processor.ctx()
    }

    /// Returns the value located at the specified position on the stack at the current clock cycle.
    ///
    /// This method can access elements beyond the top 16 positions by using the overflow table.
    #[inline(always)]
    pub fn get_stack_item(&self, pos: usize) -> Felt {
        self.processor.stack_get_safe(pos)
    }

    /// Returns a word starting at the specified element index on the stack.
    ///
    /// The word is formed by taking 4 consecutive elements starting from the specified index.
    /// For example, start_idx=0 creates a word from stack elements 0-3, start_idx=1 creates
    /// a word from elements 1-4, etc.
    ///
    /// Stack element N will be at position 0 of the word, N+1 at position 1, N+2 at position 2,
    /// and N+3 at position 3. `word[0]` corresponds to the top of the stack.
    ///
    /// This method can access elements beyond the top 16 positions by using the overflow table.
    /// Creating a word does not change the state of the stack.
    #[inline(always)]
    pub fn get_stack_word(&self, start_idx: usize) -> Word {
        self.processor.stack_get_word_safe(start_idx)
    }

    /// Returns stack state at the current clock cycle. This includes the top 16 items of the
    /// stack + overflow entries.
    #[inline(always)]
    pub fn get_stack_state(&self) -> Vec<Felt> {
        self.processor.stack().iter().rev().copied().collect()
    }

    /// Returns the element located at the specified context/address, or None if the address hasn't
    /// been accessed previously.
    #[inline(always)]
    pub fn get_mem_value(&self, ctx: ContextId, addr: u32) -> Option<Felt> {
        self.processor.memory().read_element_impl(ctx, addr)
    }

    /// Returns the batch of elements starting at the specified context/address.
    ///
    /// # Errors
    /// - If the address is not word aligned.
    #[inline(always)]
    pub fn get_mem_word(&self, ctx: ContextId, addr: u32) -> Result<Option<Word>, MemoryError> {
        self.processor.memory().read_word_impl(ctx, addr)
    }

    /// Reads (start_addr, end_addr) tuple from the specified elements of the operand stack (
    /// without modifying the state of the stack), and verifies that memory range is valid.
    ///
    /// The range is half-open `[start, end)`; both `start` and `end` must be `<= u32::MAX`.
    pub fn get_mem_addr_range(
        &self,
        start_idx: usize,
        end_idx: usize,
    ) -> Result<core::ops::Range<u32>, MemoryError> {
        let start_addr = self.get_stack_item(start_idx).as_canonical_u64();
        let end_addr = self.get_stack_item(end_idx).as_canonical_u64();

        if start_addr > u32::MAX as u64 {
            return Err(MemoryError::AddressOutOfBounds { addr: start_addr });
        }
        if end_addr > u32::MAX as u64 {
            return Err(MemoryError::AddressOutOfBounds { addr: end_addr });
        }

        if start_addr > end_addr {
            return Err(MemoryError::InvalidMemoryRange { start_addr, end_addr });
        }

        Ok(start_addr as u32..end_addr as u32)
    }

    /// Returns the entire memory state for the specified execution context at the current clock
    /// cycle.
    ///
    /// The state is returned as a vector of (address, value) tuples, and includes addresses which
    /// have been accessed at least once.
    #[inline(always)]
    pub fn get_mem_state(&self, ctx: ContextId) -> Vec<(MemoryAddress, Felt)> {
        self.processor.memory().get_memory_state(ctx)
    }

    /// Returns the already-memoized canonical deferred digest for `digest`, if present.
    ///
    /// This is a read-only lookup: it does not evaluate `digest`, register helper nodes, or mutate
    /// deferred state.
    #[inline(always)]
    pub fn get_canonical_deferred_digest(&self, digest: Digest) -> Option<Digest> {
        self.processor.deferred_state().get_canonical_digest(digest)
    }

    /// Returns the already-memoized canonical deferred node for `digest`, if present.
    ///
    /// This is a read-only lookup and returns only canonical results that were already memoized in
    /// deferred state; it never evaluates or mutates deferred state.
    #[inline(always)]
    pub fn get_canonical_deferred_node(&self, digest: Digest) -> Option<(Digest, &Node)> {
        self.processor.deferred_state().get_canonical_node(digest)
    }

    /// Returns the already-memoized canonical deferred node for `digest`.
    ///
    /// This is a read-only lookup and never evaluates or mutates deferred state.
    ///
    /// # Errors
    /// Returns [`PrecompileError::MissingNode`] if no memoized canonical node is available.
    #[inline(always)]
    pub fn require_canonical_deferred_node(
        &self,
        digest: Digest,
    ) -> Result<(Digest, &Node), PrecompileError> {
        self.processor.deferred_state().require_canonical_node(digest)
    }
}

// STOPPER
// ===============================================================================================

/// A trait for types that determine whether execution should be stopped after each clock cycle.
///
/// This allows for flexible control over the execution process, enabling features such as stepping
/// through execution (see [`crate::FastProcessor::step`]) or limiting execution to a certain number
/// of clock cycles (used in parallel trace generation to fill the trace for a predetermined trace
/// fragment).
pub trait Stopper {
    type Processor;

    /// The forest representation used by the executor this stopper is paired with.
    ///
    /// For live execution this is `Arc<MastForest>`; for replay it is `Arc<SparseMastForest>`.
    type Forest: ExecutableMastForest + Clone;

    /// Determines whether execution should be stopped at the end of each clock cycle.
    ///
    /// This method is guaranteed to be called at the end of each clock cycle, *after* the processor
    /// state has been updated to reflect the effects of the operations executed during that cycle
    /// (*including* the processor clock). Hence, a processor clock of `N` indicates that clock
    /// cycle `N - 1` has just completed.
    ///
    /// The `continuation_after_stop` is provided in cases where simply resuming execution from the
    /// top of the continuation stack is not sufficient to continue execution correctly. For
    /// example, when stopping execution in the middle of a basic block, we need to provide a
    /// `ResumeBasicBlock` continuation to ensure that execution resumes at the correct operation
    /// within the basic block (i.e. the operation right after the one that was last executed before
    /// being stopped). No continuation is provided in case of error, since it is expected that
    /// execution will not be resumed.
    fn should_stop(
        &self,
        processor: &Self::Processor,
        continuation_stack: &ContinuationStack<Self::Forest>,
        continuation_after_stop: impl FnOnce() -> Option<(
            Continuation<Self::Forest>,
            Option<DebugSourceNodeId>,
        )>,
    ) -> ControlFlow<BreakReason<Self::Forest>>;
}

// EXECUTION CONTEXT
// ================================================================================================

/// Represents the ID of an execution context
#[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
#[cfg_attr(
    all(feature = "arbitrary", test),
    miden_test_serialization_macros::serialization_test
)]
pub struct ContextId(u32);

impl ContextId {
    /// Returns the root context ID
    pub fn root() -> Self {
        Self(0)
    }

    /// Returns true if the context ID represents the root context
    pub fn is_root(&self) -> bool {
        self.0 == 0
    }
}

impl From<RowIndex> for ContextId {
    fn from(value: RowIndex) -> Self {
        Self(value.as_u32())
    }
}

impl From<u32> for ContextId {
    fn from(value: u32) -> Self {
        Self(value)
    }
}

impl From<ContextId> for u32 {
    fn from(context_id: ContextId) -> Self {
        context_id.0
    }
}

impl From<ContextId> for u64 {
    fn from(context_id: ContextId) -> Self {
        context_id.0.into()
    }
}

impl From<ContextId> for Felt {
    fn from(context_id: ContextId) -> Self {
        Felt::from_u32(context_id.0)
    }
}

#[cfg(any(test, feature = "arbitrary"))]
mod context_id_arbitrary {
    use proptest::prelude::*;

    use super::ContextId;

    impl Arbitrary for ContextId {
        type Parameters = ();
        type Strategy = BoxedStrategy<Self>;

        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
            // Plain u32 newtype; edge-biased to the 0 and u32::MAX bounds.
            prop_oneof![Just(0u32), Just(u32::MAX), any::<u32>()].prop_map(Self).boxed()
        }
    }
}

impl Serializable for ContextId {
    fn write_into<W: serde::ByteWriter>(&self, target: &mut W) {
        Serializable::write_into(&self.0, target);
    }
}

impl Deserializable for ContextId {
    fn read_from<R: serde::ByteReader>(
        source: &mut R,
    ) -> Result<Self, serde::DeserializationError> {
        Ok(Self(<u32 as Deserializable>::read_from(source)?))
    }

    fn min_serialized_size() -> usize {
        <u32 as Deserializable>::min_serialized_size()
    }
}

impl Display for ContextId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

// MEMORY ADDRESS
// ================================================================================================

#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
pub struct MemoryAddress(u32);

impl From<u32> for MemoryAddress {
    fn from(addr: u32) -> Self {
        MemoryAddress(addr)
    }
}

impl From<MemoryAddress> for u32 {
    fn from(value: MemoryAddress) -> Self {
        value.0
    }
}

impl Display for MemoryAddress {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        Display::fmt(&self.0, f)
    }
}

impl LowerHex for MemoryAddress {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        LowerHex::fmt(&self.0, f)
    }
}

impl core::ops::Add<MemoryAddress> for MemoryAddress {
    type Output = Self;

    fn add(self, rhs: MemoryAddress) -> Self::Output {
        MemoryAddress(self.0 + rhs.0)
    }
}

impl core::ops::Add<u32> for MemoryAddress {
    type Output = Self;

    fn add(self, rhs: u32) -> Self::Output {
        MemoryAddress(self.0 + rhs)
    }
}

// HELPERS
// ===============================================================================================

/// Lifts an [`Option<T>`] into a [`ControlFlow`] suitable for the execution loop, mapping `None`
/// to a break carrying an [`ExecutionError::Internal`] with `err_msg`.
///
/// Intended for use with `?` at sites where a `None` represents a violated internal invariant —
/// most commonly a missing node returned by
/// [`ExecutableMastForest::get_node_by_id`](miden_core::mast::ExecutableMastForest::get_node_by_id).
/// For functions returning `ControlFlow<InternalBreakReason<F>>`, chain
/// `.map_break(InternalBreakReason::from)` before `?`.
#[track_caller]
fn option_map_break_reason<F, T>(
    opt: Option<T>,
    err_msg: &'static str,
) -> ControlFlow<BreakReason<F>, T> {
    match opt {
        Some(value) => ControlFlow::Continue(value),
        None => ControlFlow::Break(BreakReason::Err(ExecutionError::Internal(err_msg))),
    }
}