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 fast;
mod host;
mod processor;
mod tracer;

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

use crate::{
    advice::{AdviceInputs, AdviceProvider},
    continuation_stack::ContinuationStack,
    errors::{MapExecErr, MapExecErrNoCtx},
    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;
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 fast::{BreakReason, 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::{
        InputError, KernelDescriptor, MIN_STACK_DEPTH, Program, ProgramInfo, StackInputs,
        StackOutputs,
    },
    serde, utils,
};
pub use trace::{TraceBuildInputs, TraceGenerationContext};

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

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

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;

// EXECUTORS
// ================================================================================================

/// Executes the provided program against the provided inputs and returns the resulting execution
/// output.
///
/// The `host` parameter is used to provide the external environment to the program being executed,
/// such as access to the advice provider and libraries that the program depends on.
///
/// # Errors
/// Returns an error if program execution fails for any reason.
#[tracing::instrument("execute_program", skip_all)]
pub async fn execute(
    program: &Program,
    stack_inputs: StackInputs,
    advice_inputs: AdviceInputs,
    host: &mut impl Host,
    options: ExecutionOptions,
) -> Result<ExecutionOutput, ExecutionError> {
    let processor = FastProcessor::new_with_options(stack_inputs, advice_inputs, options)
        .map_exec_err_no_ctx()?;
    processor.execute(program, host).await
}

/// Synchronous wrapper for the async `execute()` function.
///
/// This method is only available on non-wasm32 targets. On wasm32, use the async `execute()`
/// method directly since wasm32 runs in the browser's event loop.
///
/// # Panics
/// Panics if called from within an existing Tokio runtime. Use the async `execute()` method
/// instead in async contexts.
#[cfg(not(target_family = "wasm"))]
#[tracing::instrument("execute_program_sync", skip_all)]
pub fn execute_sync(
    program: &Program,
    stack_inputs: StackInputs,
    advice_inputs: AdviceInputs,
    host: &mut impl SyncHost,
    options: ExecutionOptions,
) -> Result<ExecutionOutput, ExecutionError> {
    let processor = FastProcessor::new_with_options(stack_inputs, advice_inputs, options)
        .map_exec_err_no_ctx()?;
    processor.execute_sync(program, host)
}

// 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)]
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)
    }
}

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))),
    }
}