miden_processor/fast/

mod.rs

use alloc::{
    boxed::Box,
    collections::{BTreeMap, BTreeSet},
    sync::Arc,
    vec,
    vec::Vec,
};
use core::{cmp::min, ops::ControlFlow};

use miden_air::{Felt, trace::RowIndex};
use miden_core::{
    EMPTY_WORD, WORD_SIZE, Word, ZERO,
    deferred::{DeferredState, Digest, PrecompileWitness, TRUE_DIGEST},
    mast::{ExecutableMastForest, MastForest},
    program::{MIN_STACK_DEPTH, Program, StackInputs, StackOutputs},
    utils::range,
};
use miden_mast_package::{
    Package,
    debug_info::{DebugSourceNodeId, PackageDebugInfo},
};

use crate::{
    AdviceInputs, AdviceProvider, ContextId, ExecutionError, ExecutionOptions, LoadedMastForest,
    ProcessorState,
    advice::AdviceError,
    continuation_stack::{Continuation, ContinuationStack},
    errors::MapExecErrNoCtx,
    tracer::{OperationHelperRegisters, Tracer},
};

mod basic_block;
mod execution_api;
mod external;
mod memory;
mod operation;
mod step;

pub use basic_block::SystemEventError;
pub use memory::Memory;
pub use step::{BreakReason, ResumeContext};

#[cfg(test)]
mod tests;

// CONSTANTS
// ================================================================================================

/// The initial size of the stack buffer.
///
/// Note: This value is much larger than it needs to be for the majority of programs. However, some
/// existing programs need it, so we're forced to push it up (though this should be double-checked).
/// At this high a value, we're starting to see some performance degradation on benchmarks. For
/// example, the blake3 benchmark went from 285 MHz to 250 MHz (~10% degradation). Perhaps a better
/// solution would be to make this value much smaller (~1000), and then fallback to a `Vec` if the
/// stack overflows.
const INITIAL_STACK_BUFFER_SIZE: usize = 6850;

/// The initial position of the top of the stack in the stack buffer.
///
/// We place this value close to 0 because if a program hits the limit, it's much more likely to hit
/// the upper bound than the lower bound, since hitting the lower bound only occurs when you drop
/// 0's that were generated automatically to keep the stack depth at 16. In practice, if this
/// occurs, it is most likely a bug.
const INITIAL_STACK_TOP_IDX: usize = 250;

/// Default maximum operand stack depth preserving the previous fixed-buffer ceiling.
const DEFAULT_MAX_STACK_DEPTH: usize =
    INITIAL_STACK_BUFFER_SIZE - INITIAL_STACK_TOP_IDX - 1 + MIN_STACK_DEPTH;

const _: [(); 1] =
    [(); (ExecutionOptions::DEFAULT_MAX_STACK_DEPTH == DEFAULT_MAX_STACK_DEPTH) as usize];

/// The stack buffer index where the logical operand stack starts after reset/recenter.
const STACK_BUFFER_BASE_IDX: usize = INITIAL_STACK_TOP_IDX - MIN_STACK_DEPTH;

// FAST PROCESSOR
// ================================================================================================

/// A fast processor which doesn't generate any trace.
///
/// This processor is designed to be as fast as possible. Hence, it only keeps track of the current
/// state of the processor (i.e. the stack, current clock cycle, current memory context, and free
/// memory pointer).
///
/// # Stack Management
/// A few key points about how the stack was designed for maximum performance:
///
/// - The stack starts with a fixed buffer size defined by `INITIAL_STACK_BUFFER_SIZE`.
///     - This was observed to increase performance by at least 2x compared to using a `Vec` with
///       `push()` & `pop()`.
///     - We track the stack top and bottom using indices `stack_top_idx` and `stack_bot_idx`,
///       respectively.
/// - Since we are using a fixed-size buffer, we need to ensure that stack buffer accesses are not
///   out of bounds. Naively, we could check for this on every access. However, every operation
///   alters the stack depth by a predetermined amount, allowing us to precisely determine the
///   minimum number of operations required to reach a stack buffer boundary, whether at the top or
///   bottom.
///     - For example, if the stack top is 10 elements away from the top boundary, and the stack
///       bottom is 15 elements away from the bottom boundary, then we can safely execute 10
///       operations that modify the stack depth with no bounds check.
/// - When switching contexts (e.g., during a call or syscall), all elements past the first 16 are
///   stored in `stack_overflow_save_stack`, and the stack is truncated to 16 elements. They will be
///   restored when returning from the call or syscall.
///
/// # Clock Cycle Management
/// - The clock cycle (`clk`) is managed in the same way as in `Process`. That is, it is incremented
///   by 1 for every row that `Process` adds to the main trace.
///     - It is important to do so because the clock cycle is used to determine the context ID for
///       new execution contexts when using `call` or `dyncall`.
#[derive(Debug)]
pub struct FastProcessor {
    /// The stack is stored in reverse order, so that the last element is at the top of the stack.
    stack: Box<[Felt]>,
    /// The index of the top of the stack.
    stack_top_idx: usize,
    /// The index of the bottom of the stack.
    stack_bot_idx: usize,

    /// The current clock cycle.
    clk: RowIndex,

    /// The current context ID.
    ctx: ContextId,

    /// The hash of the function that called into the current context, or `[ZERO, ZERO, ZERO,
    /// ZERO]` if we are in the first context (i.e. when `system_call_state_stack` is empty).
    caller_hash: Word,

    /// The advice provider to be used during execution.
    advice: AdviceProvider,

    /// MAST forests loaded during this execution, indexed by their local procedure digests.
    loaded_mast_forests: BTreeMap<Word, LoadedMastForest>,

    /// Commitments of MAST forests whose advice maps have been merged into the advice provider.
    merged_mast_forests: BTreeSet<Word>,

    /// A map from (context_id, word_address) to the word stored starting at that memory location.
    memory: Memory,

    /// Stack of saved system state, used when starting a new execution context (from a `call`,
    /// `syscall` or `dyncall`) to keep track of the previous `(ctx, caller_hash)` upon return.
    /// Pushed in lockstep with `stack_overflow_save_stack`.
    system_call_state_stack: Vec<SystemCallState>,

    /// Stack of saved operand-stack overflows, used when starting a new execution context to keep
    /// the elements that lived past the top 16 of the previous context. Pushed in lockstep with
    /// `system_call_state_stack`.
    stack_overflow_save_stack: Vec<Vec<Felt>>,

    /// Running total of the number of field elements currently held across all suspended overflow
    /// segments in `stack_overflow_save_stack`. Maintained in lockstep with that stack so the
    /// aggregate operand-stack depth (active context plus all suspended overflow) can be bounded
    /// by `ExecutionOptions::max_stack_depth()` in O(1) without summing every saved segment on
    /// each push. See [`Self::ensure_stack_capacity_for_push`].
    saved_overflow_len: usize,

    /// Options for execution, including cycle limits, stack limits, advice map limits, and the
    /// size of core trace fragments during execution.
    options: ExecutionOptions,

    /// Eager deferred evaluation state retained only while execution is running.
    deferred_state: DeferredState,

    /// Package debug information configured through [`ProgramExecutor`](crate::ProgramExecutor).
    pub(crate) package_debug_info: Option<PackageDebugInfo>,

    /// Entrypoint source node configured through [`ProgramExecutor`](crate::ProgramExecutor).
    pub(crate) entrypoint_source_node: Option<DebugSourceNodeId>,
}

impl FastProcessor {
    /// Packages the processor state after successful execution into a public result type.
    #[inline(always)]
    fn into_execution_output(self, stack: StackOutputs) -> Result<ExecutionOutput, ExecutionError> {
        let precompile_witness = self
            .deferred_state
            .into_witness()
            .map_err(|_| ExecutionError::Internal("failed to export deferred execution witness"))?;
        Ok(ExecutionOutput {
            stack,
            advice: self.advice,
            memory: self.memory,
            precompile_witness,
        })
    }

    /// Converts the terminal result of a full execution run into [`ExecutionOutput`].
    #[inline(always)]
    fn execution_result_from_flow(
        flow: ControlFlow<BreakReason<Arc<MastForest>>, StackOutputs>,
        processor: Self,
    ) -> Result<ExecutionOutput, ExecutionError> {
        match flow {
            ControlFlow::Continue(stack_outputs) => processor.into_execution_output(stack_outputs),
            ControlFlow::Break(break_reason) => match break_reason {
                BreakReason::Err(err) => Err(err),
                BreakReason::Stopped(_) => {
                    unreachable!("Execution never stops prematurely with NeverStopper")
                },
            },
        }
    }

    /// Converts a testing-only execution result into stack outputs.
    #[cfg(any(test, feature = "testing"))]
    #[inline(always)]
    fn stack_result_from_flow(
        flow: ControlFlow<BreakReason<Arc<MastForest>>, StackOutputs>,
    ) -> Result<StackOutputs, ExecutionError> {
        match flow {
            ControlFlow::Continue(stack_outputs) => Ok(stack_outputs),
            ControlFlow::Break(break_reason) => match break_reason {
                BreakReason::Err(err) => Err(err),
                BreakReason::Stopped(_) => {
                    unreachable!("Execution never stops prematurely with NeverStopper")
                },
            },
        }
    }

    // CONSTRUCTORS
    // ----------------------------------------------------------------------------------------------

    /// Creates a new `FastProcessor` instance with the given stack inputs.
    ///
    /// By default, advice inputs are empty and execution options use their defaults.
    ///
    /// # Example
    /// ```ignore
    /// use miden_processor::FastProcessor;
    ///
    /// let processor = FastProcessor::new(stack_inputs)
    ///     .with_advice(advice_inputs)
    ///     .expect("advice inputs should fit advice map limits");
    /// ```
    ///
    /// When using non-default advice map limits, prefer [`Self::new_with_options`] so the advice
    /// inputs are validated against the intended execution options.
    pub fn new(stack_inputs: StackInputs) -> Self {
        Self::new_with_options(stack_inputs, AdviceInputs::default(), ExecutionOptions::default())
            .expect("default processor initialization should fit default execution limits")
    }

    /// Sets the advice inputs for the processor.
    ///
    /// Advice inputs are loaded into the live advice provider immediately and are validated against
    /// the processor's current [`ExecutionOptions`]. If the advice map needs non-default limits,
    /// construct the processor with [`Self::new_with_options`] or call [`Self::with_options`]
    /// before calling this method.
    pub fn with_advice(mut self, advice_inputs: AdviceInputs) -> Result<Self, AdviceError> {
        self.advice = AdviceProvider::new(advice_inputs, &self.options)?;
        Ok(self)
    }

    /// Sets the execution options for the processor.
    ///
    /// Existing advice inputs are revalidated against the new options before they are applied. To
    /// load advice inputs that require non-default advice map limits, call this before
    /// [`Self::with_advice`] or use [`Self::new_with_options`]. The installed precompile registry
    /// and any accumulated deferred state are preserved.
    pub fn with_options(mut self, options: ExecutionOptions) -> Result<Self, AdviceError> {
        self.advice.set_options(&options)?;
        self.memory.set_max_elements(options.max_memory_elements());
        self.options = options;
        Ok(self)
    }

    /// Constructor for creating a `FastProcessor` with all options specified at once.
    ///
    /// For a more fluent API, consider using `FastProcessor::new()` with builder methods.
    pub fn new_with_options(
        stack_inputs: StackInputs,
        advice_inputs: AdviceInputs,
        options: ExecutionOptions,
    ) -> Result<Self, AdviceError> {
        let stack_top_idx = INITIAL_STACK_TOP_IDX;
        let stack = {
            // Note: we use `Vec::into_boxed_slice()` here, since `Box::new([T; N])` first allocates
            // the array on the stack, and then moves it to the heap. This might cause a
            // stack overflow on some systems.
            let mut stack = vec![ZERO; INITIAL_STACK_BUFFER_SIZE].into_boxed_slice();

            // Copy inputs in reverse order so first element ends up at top of stack
            for (i, &input) in stack_inputs.iter().enumerate() {
                stack[stack_top_idx - 1 - i] = input;
            }
            stack
        };

        Ok(Self {
            advice: AdviceProvider::new(advice_inputs, &options)?,
            loaded_mast_forests: BTreeMap::new(),
            merged_mast_forests: BTreeSet::new(),
            stack,
            stack_top_idx,
            stack_bot_idx: stack_top_idx - MIN_STACK_DEPTH,
            clk: 0_u32.into(),
            ctx: 0_u32.into(),
            caller_hash: EMPTY_WORD,
            memory: Memory::new(options.max_memory_elements()),
            system_call_state_stack: Vec::new(),
            stack_overflow_save_stack: Vec::new(),
            saved_overflow_len: 0,
            deferred_state: DeferredState::new(Arc::new(miden_precompiles::registry()))
                .map_err(AdviceError::DeferredStateInitializationFailed)?,
            package_debug_info: None,
            entrypoint_source_node: None,
            options,
        })
    }

    /// Returns the resume context to be used with the first call to `step_sync()`.
    ///
    /// This function asserts that `package` is of executable type - callers should ensure that it
    /// is before calling.
    pub fn get_initial_resume_context_for_package(
        &mut self,
        package: Arc<Package>,
    ) -> Result<ResumeContext, ExecutionError> {
        let program = package.unwrap_program();
        let package_debug_info = package.debug_info()?.map(Arc::new);
        let current_forest = program.mast_forest().clone();
        self.advice.extend_map(current_forest.advice_map()).map_exec_err_no_ctx()?;

        let entrypoint_source_node_id = package.entrypoint_source_node();
        let continuation_stack = if let Some(debug_info) = package_debug_info.as_deref() {
            Self::source_aware_continuation_stack(&program, debug_info, entrypoint_source_node_id)?
        } else {
            ContinuationStack::new(&program)
        };

        Ok(ResumeContext {
            current_forest,
            continuation_stack,
            kernel: program.kernel().clone(),
            package_debug_info,
            inline_call_contexts: Vec::new(),
        })
    }

    /// Returns the resume context to be used with the first call to `step_sync()`.
    pub fn get_initial_resume_context(
        &mut self,
        program: &Program,
    ) -> Result<ResumeContext, ExecutionError> {
        self.advice
            .extend_map(program.mast_forest().advice_map())
            .map_exec_err_no_ctx()?;

        Ok(ResumeContext {
            current_forest: program.mast_forest().clone(),
            continuation_stack: ContinuationStack::new(program),
            kernel: program.kernel().clone(),
            package_debug_info: None,
            inline_call_contexts: Vec::new(),
        })
    }

    // ACCESSORS
    // -------------------------------------------------------------------------------------------

    /// Returns the deferred witness accumulated during execution.
    #[inline(always)]
    pub fn deferred_state(&self) -> &DeferredState {
        &self.deferred_state
    }

    #[inline(always)]
    pub(super) fn deferred_state_mut(&mut self) -> &mut DeferredState {
        &mut self.deferred_state
    }

    /// Returns the size of the stack.
    #[inline(always)]
    fn stack_size(&self) -> usize {
        self.stack_top_idx - self.stack_bot_idx
    }

    /// Returns the stack, such that the top of the stack is at the last index of the returned
    /// slice.
    pub fn stack(&self) -> &[Felt] {
        &self.stack[self.stack_bot_idx..self.stack_top_idx]
    }

    /// Returns the top 16 elements of the stack.
    pub fn stack_top(&self) -> &[Felt] {
        &self.stack[self.stack_top_idx - MIN_STACK_DEPTH..self.stack_top_idx]
    }

    /// Returns a mutable reference to the top 16 elements of the stack.
    pub fn stack_top_mut(&mut self) -> &mut [Felt] {
        &mut self.stack[self.stack_top_idx - MIN_STACK_DEPTH..self.stack_top_idx]
    }

    /// Returns the element on the stack at index `idx`.
    ///
    /// This method is only meant to be used to access the stack top by operation handlers, and
    /// system event handlers.
    ///
    /// # Preconditions
    /// - `idx` must be less than or equal to 15.
    #[inline(always)]
    pub fn stack_get(&self, idx: usize) -> Felt {
        self.stack[self.stack_top_idx - idx - 1]
    }

    /// Same as [`Self::stack_get()`], but returns [`ZERO`] if `idx` falls below index 0 in the
    /// stack buffer.
    ///
    /// Use this instead of `stack_get()` when `idx` may exceed 15.
    #[inline(always)]
    pub fn stack_get_safe(&self, idx: usize) -> Felt {
        if idx < self.stack_top_idx {
            self.stack[self.stack_top_idx - idx - 1]
        } else {
            ZERO
        }
    }

    /// Mutable variant of `stack_get()`.
    ///
    /// This method is only meant to be used to access the stack top by operation handlers, and
    /// system event handlers.
    ///
    /// # Preconditions
    /// - `idx` must be less than or equal to 15.
    #[inline(always)]
    pub fn stack_get_mut(&mut self, idx: usize) -> &mut Felt {
        &mut self.stack[self.stack_top_idx - idx - 1]
    }

    /// Returns the word on the stack starting at index `start_idx` in "stack order".
    ///
    /// For `start_idx=0` the top element of the stack will be at position 0 in the word.
    ///
    /// For example, if the stack looks like this:
    ///
    /// top                                                       bottom
    /// v                                                           v
    /// a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p
    ///
    /// Then
    /// - `stack_get_word(0)` returns `[a, b, c, d]`,
    /// - `stack_get_word(1)` returns `[b, c, d, e]`,
    /// - etc.
    ///
    /// This method is only meant to be used to access the stack top by operation handlers, and
    /// system event handlers.
    ///
    /// # Preconditions
    /// - `start_idx` must be less than or equal to 12.
    #[inline(always)]
    pub fn stack_get_word(&self, start_idx: usize) -> Word {
        // Ensure we have enough elements to form a complete word
        debug_assert!(
            start_idx + WORD_SIZE <= self.stack_depth() as usize,
            "Not enough elements on stack to read word starting at index {start_idx}"
        );

        let word_start_idx = self.stack_top_idx - start_idx - WORD_SIZE;
        let mut result: [Felt; WORD_SIZE] =
            self.stack[range(word_start_idx, WORD_SIZE)].try_into().unwrap();
        // Reverse so top of stack (idx 0) goes to word[0]
        result.reverse();
        result.into()
    }

    /// Same as [`Self::stack_get_word()`], but returns [`ZERO`] for any element that falls below
    /// index 0 in the stack buffer.
    ///
    /// Use this instead of `stack_get_word()` when `start_idx + WORD_SIZE` may exceed
    /// `stack_top_idx`.
    #[inline(always)]
    pub fn stack_get_word_safe(&self, start_idx: usize) -> Word {
        let buf_end = self.stack_top_idx.saturating_sub(start_idx);
        let buf_start = self.stack_top_idx.saturating_sub(start_idx.saturating_add(WORD_SIZE));
        let num_elements_to_read_from_buf = buf_end - buf_start;

        let mut result = [ZERO; WORD_SIZE];
        if num_elements_to_read_from_buf == WORD_SIZE {
            result.copy_from_slice(&self.stack[range(buf_start, WORD_SIZE)]);
        } else if num_elements_to_read_from_buf > 0 {
            let offset = WORD_SIZE - num_elements_to_read_from_buf;
            result[offset..]
                .copy_from_slice(&self.stack[range(buf_start, num_elements_to_read_from_buf)]);
        }
        result.reverse();

        result.into()
    }

    /// Returns the number of elements on the stack in the current context.
    #[inline(always)]
    pub fn stack_depth(&self) -> u32 {
        (self.stack_top_idx - self.stack_bot_idx) as u32
    }

    /// Returns a reference to the processor's memory.
    pub fn memory(&self) -> &Memory {
        &self.memory
    }

    /// Consumes the processor and returns the advice provider and memory.
    pub fn into_parts(self) -> (AdviceProvider, Memory) {
        (self.advice, self.memory)
    }

    /// Returns a reference to the execution options.
    pub fn execution_options(&self) -> &ExecutionOptions {
        &self.options
    }

    /// Returns a narrowed interface for reading and updating the processor state.
    #[inline(always)]
    pub fn state(&self) -> ProcessorState<'_> {
        ProcessorState { processor: self }
    }

    // MUTATORS
    // -------------------------------------------------------------------------------------------

    /// Writes an element to the stack at the given index.
    #[inline(always)]
    pub fn stack_write(&mut self, idx: usize, element: Felt) {
        self.stack[self.stack_top_idx - idx - 1] = element
    }

    /// Writes a word to the stack starting at the given index.
    ///
    /// `word[0]` goes to stack position start_idx (top), `word[1]` to start_idx+1, etc.
    #[inline(always)]
    pub fn stack_write_word(&mut self, start_idx: usize, word: &Word) {
        debug_assert!(start_idx <= MIN_STACK_DEPTH - WORD_SIZE);

        let word_start_idx = self.stack_top_idx - start_idx - 4;
        let mut source: [Felt; WORD_SIZE] = (*word).into();
        // Reverse so word[0] ends up at the top of stack (highest internal index)
        source.reverse();
        self.stack[range(word_start_idx, WORD_SIZE)].copy_from_slice(&source)
    }

    /// Swaps the elements at the given indices on the stack.
    #[inline(always)]
    pub fn stack_swap(&mut self, idx1: usize, idx2: usize) {
        let a = self.stack_get(idx1);
        let b = self.stack_get(idx2);
        self.stack_write(idx1, b);
        self.stack_write(idx2, a);
    }

    /// Increments the stack top pointer by 1.
    ///
    /// The bottom of the stack is never affected by this operation.
    #[inline(always)]
    fn increment_stack_size(&mut self) {
        self.stack_top_idx += 1;
    }

    /// Ensures the internal stack storage can accommodate one additional logical stack element.
    ///
    /// The operand stack depth limit is the semantic resource bound; the buffer is only an
    /// implementation detail. We therefore check the logical depth before allocating so a program
    /// cannot force memory growth beyond `ExecutionOptions::max_stack_depth()`. When storage does
    /// need to grow, it grows geometrically and remains heap-allocated as a boxed slice. A
    /// `SmallVec` would put a useful inline buffer inside `FastProcessor`, and preallocating the
    /// full limit would penalize ordinary programs. This policy is performance-sensitive and should
    /// be benchmarked against the fixed-buffer baseline.
    ///
    /// The depth that is checked is the *aggregate* operand-stack depth: the active context's depth
    /// plus every element held in suspended overflow segments (`saved_overflow_len`). A `call`,
    /// `dyncall`, or `syscall` context switch hides the caller's overflow in
    /// `stack_overflow_save_stack` rather than freeing it, so checking only the active context
    /// would let a program nest context switches to accumulate `O(call_depth *
    /// max_stack_depth)` hidden operand-stack memory while every live frame stayed within the
    /// limit. Because a context switch merely moves elements between the active stack and the
    /// saved overflow (it never creates elements), the aggregate is conserved across switches
    /// and only grows on a push, so enforcing the bound here is sufficient to cap total
    /// operand-stack memory.
    #[inline(always)]
    fn ensure_stack_capacity_for_push(&mut self) -> Result<(), ExecutionError> {
        let depth = self.stack_size() + self.saved_overflow_len + 1;
        let max = self.options.max_stack_depth();
        if depth > max {
            return Err(ExecutionError::StackDepthLimitExceeded { depth, max });
        }

        if self.stack_top_idx >= self.stack.len() - 1 {
            self.grow_stack_buffer(self.stack_top_idx + 2);
        }

        Ok(())
    }

    fn ensure_stack_capacity_for_top_idx(&mut self, top_idx: usize) {
        if top_idx >= self.stack.len() {
            self.grow_stack_buffer(top_idx + 1);
        }
    }

    fn grow_stack_buffer(&mut self, requested_min_len: usize) {
        // The maximum allocation is tied to the logical operand stack depth, not to the current
        // buffer position. Using `stack_bot_idx` here would make the allocation ceiling drift when
        // the live stack has moved away from the initial base.
        let max_len = STACK_BUFFER_BASE_IDX
            .saturating_add(self.options.max_stack_depth())
            .saturating_add(1);
        let live_len = self.stack_size();

        // Growth also recenters the live stack at the normal base. This keeps future push/drop
        // behavior close to the fixed-buffer layout and avoids carrying unused prefix cells into
        // the new allocation. The extra slot is for the next checked push that triggered growth.
        let recentered_min_len = STACK_BUFFER_BASE_IDX.saturating_add(live_len).saturating_add(2);
        debug_assert!(recentered_min_len <= max_len);

        // Allocation growth is based on the stack's post-recentered live range, not the previous
        // buffer length. The `requested_min_len` may be beyond the allocation cap when a shallow
        // context is still positioned near the end of the old buffer; recentering the live stack is
        // what makes that valid. The VM-visible requirements are that the live stack is restored at
        // `STACK_BUFFER_BASE_IDX`, the post-recentered push slot is available, and allocation stays
        // capped by the configured stack depth. The allocation size can differ from the previous
        // doubling policy: normal push growth may allocate a couple of extra cells because of the
        // spare push slot, while restoring a deep caller from a shallow callee may allocate only
        // the requested restored range instead of doubling the old buffer. That smaller
        // restore allocation is intentional, but it means future pushes can grow again
        // sooner and should stay covered by benchmarks.
        let new_len = recentered_min_len.saturating_mul(2).max(requested_min_len).min(max_len);
        debug_assert!(new_len <= max_len);

        let mut new_stack = vec![ZERO; new_len].into_boxed_slice();
        let new_stack_bot_idx = STACK_BUFFER_BASE_IDX;
        let new_stack_top_idx = new_stack_bot_idx + live_len;

        // Only the active stack range carries VM state. Prefix/suffix cells are scratch storage and
        // stay zeroed, which keeps growth proportional to the live depth instead of the old buffer
        // length.
        new_stack[new_stack_bot_idx..new_stack_top_idx]
            .copy_from_slice(&self.stack[self.stack_bot_idx..self.stack_top_idx]);

        self.stack = new_stack;
        self.stack_bot_idx = new_stack_bot_idx;
        self.stack_top_idx = new_stack_top_idx;
    }

    /// Decrements the stack top pointer by 1.
    ///
    /// The bottom of the stack is only decremented in cases where the stack depth would become less
    /// than 16.
    #[inline(always)]
    fn decrement_stack_size(&mut self) {
        if self.stack_top_idx == MIN_STACK_DEPTH {
            // We no longer have any room in the stack buffer to decrement the stack size (which
            // would cause the `stack_bot_idx` to go below 0). We therefore reset the stack to its
            // original position.
            self.reset_stack_in_buffer(INITIAL_STACK_TOP_IDX);
        }

        self.stack_top_idx -= 1;
        self.stack_bot_idx = min(self.stack_bot_idx, self.stack_top_idx - MIN_STACK_DEPTH);
    }

    /// Resets the stack in the buffer to a new position, preserving the top 16 elements of the
    /// stack.
    ///
    /// # Preconditions
    /// - The stack is expected to have exactly 16 elements.
    #[inline(always)]
    fn reset_stack_in_buffer(&mut self, new_stack_top_idx: usize) {
        debug_assert_eq!(self.stack_depth(), MIN_STACK_DEPTH as u32);

        let new_stack_bot_idx = new_stack_top_idx - MIN_STACK_DEPTH;

        // Copy stack to its new position
        self.stack
            .copy_within(self.stack_bot_idx..self.stack_top_idx, new_stack_bot_idx);

        // Zero out stack below the new new_stack_bot_idx, since this is where overflow values
        // come from, and are guaranteed to be ZERO. We don't need to zero out above
        // `stack_top_idx`, since values there are never read before being written.
        self.stack[0..new_stack_bot_idx].fill(ZERO);

        // Update indices.
        self.stack_bot_idx = new_stack_bot_idx;
        self.stack_top_idx = new_stack_top_idx;
    }
}

// EXECUTION OUTPUT
// ===============================================================================================

/// The output of a program execution, containing the state of the stack, advice provider, memory,
/// and optional portable precompile witness at the end of execution.
#[derive(Debug)]
pub struct ExecutionOutput {
    pub stack: StackOutputs,
    pub advice: AdviceProvider,
    pub memory: Memory,
    pub precompile_witness: Option<PrecompileWitness>,
}

impl ExecutionOutput {
    /// Returns the carried deferred root, or TRUE when no witness is present.
    ///
    /// This does not validate the witness's precompile computations.
    pub fn precompile_root(&self) -> Digest {
        self.precompile_witness
            .as_ref()
            .map_or(TRUE_DIGEST, PrecompileWitness::root_unchecked)
    }
}

// SYSTEM CALL STATE
// ===============================================================================================

/// The system-state half of a saved execution context.
///
/// Used to keep track of the `(ctx, caller_hash)` pair that needs to be restored upon return from a
/// `call`, `syscall` or `dyncall`.
#[derive(Debug)]
pub(super) struct SystemCallState {
    pub ctx: ContextId,
    pub caller_hash: Word,
}

// NOOP TRACER
// ================================================================================================

/// A [Tracer] that does nothing.
pub struct NoopTracer;

impl Tracer for NoopTracer {
    type Processor = FastProcessor;
    type Forest = Arc<MastForest>;

    #[inline(always)]
    fn start_clock_cycle(
        &mut self,
        _processor: &FastProcessor,
        _continuation: Continuation<Arc<MastForest>>,
        _continuation_stack: &ContinuationStack<Arc<MastForest>>,
        _current_forest: &Arc<MastForest>,
    ) {
        // do nothing
    }

    #[inline(always)]
    fn finalize_clock_cycle(
        &mut self,
        _processor: &FastProcessor,
        _op_helper_registers: OperationHelperRegisters,
        _current_forest: &Arc<MastForest>,
    ) -> Result<(), ExecutionError> {
        // do nothing
        Ok(())
    }
}