miden-processor 1.0.0-rc.0

//! Processor glue for deferred-DAG system events.
//!
//! These handlers keep the processor agnostic to precompile semantics: they read VM inputs,
//! update deferred state, and delegate validation/evaluation to the installed registry.

use alloc::vec::Vec;

use miden_core::{
    Felt, Word, ZERO,
    deferred::{
        DEFERRED_AND_FRAME, DEFERRED_CHUNKS_DOMAIN, DataChunk, DeferredError, Digest, EidosFrame,
        MAX_DEFERRED_WIRE_ELEMENTS, Node, NodeType, PrecompileError, TRUE_DIGEST,
    },
    serde::Serializable,
    utils::bytes_to_packed_u32_elements,
};

use super::SystemEventError;
use crate::{AdviceProvider, MemoryError, fast::FastProcessor};

// STACK LAYOUT — `DeferredRegister`
// ================================================================================================
// `[event_id, CV, PAYLOAD_LO, PAYLOAD_HI, ...]`; `CV` is the framed initial Eidos chaining word
// used by the VM to hash the same payload. The handler recovers the unique semantic frame from it.
// The eight payload felts form one compression block. The payload is one
// 8-felt data chunk, `lhs || rhs` child digests for a precompile-owned join, or one `lhs || rhs`
// pair for a pair-list node. The exact framework AND frame registers a non-logging conjunction.

/// Stack offset of the initial Eidos chaining word.
const DEFERRED_CV_OFFSET: usize = 1;
/// Stack offset of the payload's low half below the event id.
const DEFERRED_PAYLOAD_LO_OFFSET: usize = 5;
/// Stack offset of the payload's high half.
const DEFERRED_PAYLOAD_HI_OFFSET: usize = 9;

// STACK LAYOUT — `DeferredEvaluate*`
// ================================================================================================
// `[event_id, NODE_DIGEST, ...]` — the node must already be registered in `DeferredState`; the
// handlers evaluate it to a canonical digest and push the requested canonical node component(s)
// onto the advice stack. Payload chunks are arranged for `adv_pushw adv_pushw` ergonomics: the two
// pushes leave the chunk's LOW word on top of the operand stack, with HIGH beneath it. The full
// event emits the frame first in advice-pop order, so `adv_pushw adv_pushw adv_pushw` leaves
// `[PAYLOAD_LO, PAYLOAD_HI, FRAME, ...]` for a single 8-felt payload. All `DeferredEvaluate*`
// outputs are unbound host hints; proof-relevant callers must relate them with VM instructions to
// values established independently of that advice.

/// Stack offset of the registered node digest.
const DEFERRED_NODE_DIGEST_OFFSET: usize = 1;

// STACK LAYOUT — `DeferredRegisterData`
// ================================================================================================
// `[event_id, n_chunks, CV, ptr, ...]` — no stack-resident payload. `CV` is the framed initial
// Eidos chaining word and `n_chunks` is the number of 8-felt payload chunks to read from memory at
// `ptr`. Data and pair-list nodes use that explicit chunk count. Precompile-owned join nodes
// require `n_chunks == 1`.

/// Stack offset of the data node's initial Eidos chaining word.
const DATA_CV_OFFSET: usize = 2;
/// Stack offset of the memory pointer for the node payload.
const DATA_PTR_OFFSET: usize = 6;
/// Stack offset of the number of 8-felt payload chunks to read from memory.
const DATA_N_CHUNKS_OFFSET: usize = 1;

/// Number of field elements occupied by a deferred node frame.
const FRAME_NUM_ELEMENTS: usize = 4;
/// Number of field elements in one deferred payload block.
const PAYLOAD_BLOCK_NUM_ELEMENTS: usize = 8;

/// Returns the storage footprint of `frame || n` 8-felt payload blocks.
fn payload_node_num_elements(n_blocks: u32) -> usize {
    (n_blocks as usize)
        .checked_mul(PAYLOAD_BLOCK_NUM_ELEMENTS)
        .and_then(|payload_elements| payload_elements.checked_add(FRAME_NUM_ELEMENTS))
        .unwrap_or(usize::MAX)
}

/// Stack-resident registration of an operand-stack deferred node.
///
/// The frame decodes to one [`DataChunk`] (8 field elements), a precompile-owned join payload
/// containing two 4-felt child digests, a framework AND, or a one-pair pair-list payload containing
/// `lhs || rhs`. TRUE nodes are not accepted. Frames that semantically require more than
/// one data chunk or pair still form a one-chunk or one-pair node here; precompile-specific
/// payload validation rejects the length mismatch before registration.
/// Registration is delegated to [`miden_core::deferred::DeferredState::register`], so
/// semantic failures, including false predicates, surface immediately. The stack arguments are
/// part of the VM execution trace, but the event does not constrain the host-side registration.
/// This event does not return the node digest; any proof-relevant caller must compute it with VM
/// instructions from the exact same initial chaining word and payload.
pub(super) fn handle_deferred_register(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let lo = processor.stack_get_word(DEFERRED_PAYLOAD_LO_OFFSET);
    let hi = processor.stack_get_word(DEFERRED_PAYLOAD_HI_OFFSET);
    let frame = decode_frame_from_cv(processor.stack_get_word(DEFERRED_CV_OFFSET))?;
    let block: DataChunk = [lo[0], lo[1], lo[2], lo[3], hi[0], hi[1], hi[2], hi[3]];

    // Decode the frame before shaping the payload so the host commits the structurally correct
    // node.
    let node = match processor.deferred_state().decode(frame)? {
        NodeType::Data if frame.domain().as_felt() == DEFERRED_CHUNKS_DOMAIN => {
            let node = Node::chunks(Vec::from([block])).map_err(PrecompileError::from)?;
            if node.frame() != Some(frame) {
                return Err(PrecompileError::InvalidNode.into());
            }
            node
        },
        NodeType::Data => Node::value(frame, block).map_err(PrecompileError::from)?,
        NodeType::Join => {
            let lhs = Digest::new([block[0], block[1], block[2], block[3]]);
            let rhs = Digest::new([block[4], block[5], block[6], block[7]]);
            if frame == DEFERRED_AND_FRAME {
                Node::and(lhs, rhs)
            } else {
                Node::join(frame, lhs, rhs).map_err(PrecompileError::from)?
            }
        },
        NodeType::PairList => {
            let lhs = Digest::new([block[0], block[1], block[2], block[3]]);
            let rhs = Digest::new([block[4], block[5], block[6], block[7]]);
            Node::try_pair_list(frame, vec![(lhs, rhs)]).map_err(PrecompileError::from)?
        },
        NodeType::True => return Err(PrecompileError::InvalidNode.into()),
    };
    processor.deferred_state_mut().register(node)?;
    Ok(())
}

/// Handles deferred-node evaluation and returns the canonical frame and payload as advice.
///
/// The digest must already be registered in
/// [`miden_core::deferred::DeferredState`]. The handler evaluates it with
/// [`miden_core::deferred::DeferredState::evaluate_digest`] and pushes the canonical node's frame
/// and payload. The frame is first in advice-pop order, followed by the payload in the same word
/// ordering used by [`handle_deferred_evaluate_payload`]. TRUE emits one zero word.
pub(super) fn handle_deferred_evaluate(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let canonical_node = evaluate_canonical_node(processor)?;
    push_evaluated_payload(&mut processor.advice, &canonical_node)?;
    push_evaluated_frame(&mut processor.advice, &canonical_node)?;
    Ok(())
}

/// Handles deferred-node evaluation and returns only the canonical frame as advice.
pub(super) fn handle_deferred_evaluate_frame(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let canonical_node = evaluate_canonical_node(processor)?;
    push_evaluated_frame(&mut processor.advice, &canonical_node)?;
    Ok(())
}

/// Handles deferred-node evaluation and returns only the canonical payload as advice.
///
/// This preserves the original payload-only behavior for payload-only consumers. Data payloads emit
/// two advice words per 8-felt chunk. Because both the advice stack and operand stack
/// are LIFO, each chunk is placed on advice as HIGH then LOW (and chunks are processed in reverse
/// before front-pushing) so `adv_pushw adv_pushw` leaves `[LOW, HIGH, ...]` on the operand stack
/// for that chunk. Join payloads use the same convention for their two words, leaving
/// `[lhs, rhs, ...]` after two `adv_pushw`s. TRUE emits no advice.
pub(super) fn handle_deferred_evaluate_payload(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let canonical_node = evaluate_canonical_node(processor)?;
    push_evaluated_payload(&mut processor.advice, &canonical_node)?;
    Ok(())
}

/// Evaluates the digest on the operand stack and returns the registered canonical node.
fn evaluate_canonical_node(processor: &mut FastProcessor) -> Result<Node, SystemEventError> {
    let digest: Digest = processor.stack_get_word(DEFERRED_NODE_DIGEST_OFFSET);
    let canonical_digest = processor.deferred_state_mut().evaluate_digest(digest)?;
    processor
        .deferred_state()
        .get_node(&canonical_digest)
        .cloned()
        .ok_or(PrecompileError::MissingNode.into())
}

/// Computes the original graph of a registered true assertion and replaces its advice-map value.
pub(super) fn handle_deferred_export_witness(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let digest = processor.stack_get_word(DEFERRED_NODE_DIGEST_OFFSET);
    if processor.deferred_state_mut().evaluate_digest(digest)? != TRUE_DIGEST {
        return Err(PrecompileError::AssertionFailed.into());
    }
    let witness = processor
        .deferred_state()
        .witness_for(digest, processor.execution_options().verification_precompile_limits())?;
    let bytes = witness.to_bytes();

    let mut values = bytes_to_packed_u32_elements(&bytes);
    // The deferred graph's element ceiling bounds its byte length well below the field modulus.
    values.insert(0, Felt::new_unchecked(bytes.len() as u64));
    processor.advice.replace_into_map(digest, values)?;
    Ok(())
}

/// Pushes `node`'s canonical frame onto the advice stack.
fn push_evaluated_frame(advice: &mut AdviceProvider, node: &Node) -> Result<(), SystemEventError> {
    let frame = node.frame().map(EidosFrame::as_word).unwrap_or_default();
    advice.push_stack_word(&frame)?;
    Ok(())
}

/// Pushes `node`'s canonical payload onto the advice stack in `adv_pushw`-ergonomic order.
fn push_evaluated_payload(
    advice: &mut AdviceProvider,
    node: &Node,
) -> Result<(), SystemEventError> {
    // `AdviceProvider::push_stack_word` front-pushes, while `adv_pushw` pushes each consumed word
    // onto the operand stack. Push payload blocks from the back, preserving LOW/HIGH order within
    // each block, so repeated `adv_pushw`s leave later blocks above earlier blocks.
    for chunk in node.payload().as_chunks().iter().rev() {
        let [lo0, lo1, lo2, lo3, hi0, hi1, hi2, hi3] = *chunk;
        advice.push_stack_word(&Word::new([lo0, lo1, lo2, lo3]))?;
        advice.push_stack_word(&Word::new([hi0, hi1, hi2, hi3]))?;
    }
    Ok(())
}

/// Handles memory-backed registration of a deferred node.
///
/// The frame is the source of truth for the framework payload shape, while the operand-stack
/// `n_chunks` value is the source of truth for the memory range. Data nodes read exactly
/// `n_chunks` [`DataChunk`] values (8 field elements each). Pair-list nodes interpret chunks as
/// `lhs || rhs` pairs. Precompile-owned join nodes require `n_chunks == 1` and interpret the one
/// chunk as `lhs || rhs`. Framework-owned AND and TRUE nodes are not accepted. After checking word
/// alignment, address bounds, and a hard allocation-size precheck, registration and semantic
/// evaluation are delegated to [`miden_core::deferred::DeferredState::register`], so registration
/// failures surface during this event.
///
/// The stack-supplied CV, pointer, and chunk count are visible in the VM execution trace, but the
/// direct host memory reads below do not add AIR memory constraints. Thus, the event alone does not
/// tie the registered chunks to VM memory. Any proof-relevant caller must compute the node digest
/// with VM instructions from the same CV and ordered chunk sequence; the shared `register_mem`
/// MASM wrapper does so by hashing the exact same range.
pub(super) fn handle_deferred_register_data(
    processor: &mut FastProcessor,
) -> Result<(), SystemEventError> {
    let frame = decode_frame_from_cv(processor.stack_get_word(DATA_CV_OFFSET))?;
    let ptr = processor.stack_get(DATA_PTR_OFFSET).as_canonical_u64();
    let n_chunks_felt = processor.stack_get(DATA_N_CHUNKS_OFFSET).as_canonical_u64();
    let n = u32::try_from(n_chunks_felt).map_err(|_| PrecompileError::InvalidNode)?;
    if n == 0 {
        return Err(PrecompileError::InvalidNode.into());
    }

    // Decode the frame before any memory reads. The precompile is the source of truth for payload
    // shape, and payload lengths are checked during registration before evaluation.
    let node_type = processor.deferred_state().decode(frame)?;
    match node_type {
        NodeType::Data | NodeType::PairList => {},
        NodeType::Join if n == 1 => {},
        NodeType::Join | NodeType::True => {
            return Err(PrecompileError::InvalidNode.into());
        },
    }

    // Reject a payload exceeding the hard allocation ceiling before reading guest memory. The
    // configurable execution-work policy is enforced by `DeferredState::register` after the node
    // and its declared work have been decoded.
    let num_elements = payload_node_num_elements(n);
    if num_elements > MAX_DEFERRED_WIRE_ELEMENTS {
        return Err(PrecompileError::from(DeferredError::DeferredStateTooLarge {
            num_elements,
            max: MAX_DEFERRED_WIRE_ELEMENTS,
        })
        .into());
    }

    // Bounds + alignment validation.
    if ptr > u32::MAX as u64 {
        return Err(MemoryError::AddressOutOfBounds { addr: ptr }.into());
    }
    if !ptr.is_multiple_of(4) {
        return Err(
            MemoryError::UnalignedWordAccess { addr: ptr as u32, ctx: processor.ctx }.into()
        );
    }
    let total = 8u64 * n as u64;
    let end = ptr
        .checked_add(total)
        .ok_or(MemoryError::AddressOutOfBounds { addr: u64::MAX })?;
    if end > u32::MAX as u64 {
        return Err(MemoryError::AddressOutOfBounds { addr: end }.into());
    }
    // Read `n` eight-Felt payload blocks from memory.
    let ctx = processor.ctx;
    let mut chunks: Vec<DataChunk> = Vec::with_capacity(n as usize);
    for k in 0..n {
        let base = ptr as u32 + k * 8;
        let mut chunk = [ZERO; 8];
        for (i, felt) in chunk.iter_mut().enumerate() {
            *felt = processor.memory().read_element_impl(ctx, base + i as u32).unwrap_or(ZERO);
        }
        chunks.push(chunk);
    }

    let node = match node_type {
        NodeType::Data if frame.domain().as_felt() == DEFERRED_CHUNKS_DOMAIN => {
            let node = Node::chunks(chunks).map_err(PrecompileError::from)?;
            if node.frame() != Some(frame) {
                return Err(PrecompileError::InvalidNode.into());
            }
            node
        },
        NodeType::Data => Node::try_data(frame, chunks).map_err(PrecompileError::from)?,
        NodeType::Join => {
            let block = chunks.into_iter().next().ok_or(PrecompileError::InvalidNode)?;
            let lhs = Digest::new([block[0], block[1], block[2], block[3]]);
            let rhs = Digest::new([block[4], block[5], block[6], block[7]]);
            Node::join(frame, lhs, rhs).map_err(PrecompileError::from)?
        },
        NodeType::PairList => {
            Node::try_pair_list_chunks(frame, chunks).map_err(PrecompileError::from)?
        },
        NodeType::True => unreachable!("TRUE was rejected before memory reads"),
    };
    processor.deferred_state_mut().register(node)?;
    Ok(())
}

fn decode_frame_from_cv(cv: Word) -> Result<EidosFrame, SystemEventError> {
    EidosFrame::from_initial_chaining_word(cv).ok_or_else(|| PrecompileError::InvalidNode.into())
}

#[cfg(test)]
mod tests {
    use miden_core::{
        deferred::{EidosFrame, deferred_chunks_frame},
        program::{StackInputs, domain::DomainTag},
    };
    use miden_precompiles::Keccak256Precompile;

    use super::*;

    #[test]
    fn export_witness_rejects_invalid_roots_even_with_existing_entries() {
        let mut processor = FastProcessor::new(StackInputs::default());
        let value = processor
            .deferred_state_mut()
            .register(Node::chunks(vec![[ZERO; 8]]).unwrap())
            .unwrap();
        for (digest, expected) in [
            (Word::new([Felt::from_u32(99); 4]), PrecompileError::MissingNode),
            (TRUE_DIGEST, PrecompileError::InvalidNode),
            (value, PrecompileError::AssertionFailed),
        ] {
            processor.stack_write_word(1, &digest);
            for existing_entry in [false, true] {
                if existing_entry {
                    processor.advice.insert_into_map(digest, vec![Felt::ONE]).unwrap();
                }
                let advice = processor.advice.clone();
                let stack = processor.stack().to_vec();
                let SystemEventError::Deferred(error) =
                    handle_deferred_export_witness(&mut processor).unwrap_err()
                else {
                    panic!("expected a deferred error");
                };
                assert_eq!(
                    core::mem::discriminant(error.root()),
                    core::mem::discriminant(&expected)
                );
                assert_eq!(processor.advice, advice);
                assert_eq!(processor.stack(), stack);
                assert_eq!(processor.deferred_state().root(), TRUE_DIGEST);
            }
        }
    }

    #[test]
    fn export_witness_preserves_existing_advice_on_budget_failure() {
        use miden_core::{WORD_SIZE, crypto::merkle::MerkleStore};

        use crate::{ExecutionOptions, advice::AdviceError};

        let mut processor = FastProcessor::new(StackInputs::default());
        let digest = processor
            .deferred_state_mut()
            .register(Node::and(TRUE_DIGEST, TRUE_DIGEST))
            .unwrap();
        processor.stack_write_word(1, &digest);
        processor.advice.insert_into_map(digest, vec![Felt::ONE]).unwrap();
        let budget =
            (MerkleStore::default().num_internal_nodes() * 3 * WORD_SIZE + WORD_SIZE + 1) * 8;
        processor = processor
            .with_options(ExecutionOptions::default().with_max_advice_size_bytes(budget))
            .unwrap();
        let advice = processor.advice.clone();
        assert!(matches!(
            handle_deferred_export_witness(&mut processor),
            Err(SystemEventError::Advice(AdviceError::SizeBudgetExceeded { .. }))
        ));
        assert_eq!(processor.advice, advice);
    }

    #[test]
    fn register_accepts_only_exact_framework_and_frame() {
        let malformed_and = EidosFrame::new(DEFERRED_AND_FRAME.domain(), [1, 0, 0]);

        for (name, frame, exact) in [
            ("exact AND frame", DEFERRED_AND_FRAME, true),
            ("parameterized AND-domain frame", malformed_and, false),
        ] {
            let mut stack = vec![ZERO];
            stack.extend(frame.initial_chaining_word());
            stack.extend([ZERO; 8]);
            let mut processor =
                FastProcessor::new(StackInputs::new(&stack).expect("valid test stack"));

            if exact {
                handle_deferred_register(&mut processor).expect("exact AND must register");
                let digest = Node::and(TRUE_DIGEST, TRUE_DIGEST).digest();
                assert!(processor.deferred_state().get_node(&digest).is_some());
                assert_eq!(processor.deferred_state().root(), TRUE_DIGEST);
                continue;
            }
            let error = match handle_deferred_register(&mut processor) {
                Ok(()) => panic!("{name} should be rejected"),
                Err(error) => error,
            };
            let SystemEventError::Deferred(error) = error else {
                panic!("{name} returned the wrong error class: {error}");
            };
            assert!(
                matches!(error.root(), PrecompileError::InvalidNode),
                "{name} returned {error}",
            );
        }
    }

    #[test]
    fn register_and_validates_children_without_advancing_logged_root() {
        let mut processor = FastProcessor::new(StackInputs::default());
        let logged_root = processor.deferred_state_mut().log_statement(TRUE_DIGEST).unwrap();
        let value = processor
            .deferred_state_mut()
            .register(Node::chunks(vec![[ZERO; 8]]).unwrap())
            .unwrap();
        processor.stack_write_word(1, &DEFERRED_AND_FRAME.initial_chaining_word());
        processor.stack_write_word(9, &TRUE_DIGEST);

        for (child, expected) in [
            (Word::new([Felt::from_u32(99); 4]), PrecompileError::MissingNode),
            (value, PrecompileError::AssertionFailed),
        ] {
            processor.stack_write_word(5, &child);
            let SystemEventError::Deferred(error) =
                handle_deferred_register(&mut processor).unwrap_err()
            else {
                panic!("expected invalid AND child");
            };
            assert_eq!(core::mem::discriminant(error.root()), core::mem::discriminant(&expected));
            assert_eq!(processor.deferred_state().root(), logged_root);
        }

        processor.stack_write_word(5, &logged_root);
        handle_deferred_register(&mut processor).unwrap();
        let selected_root = Node::and(logged_root, TRUE_DIGEST).digest();
        assert_ne!(selected_root, logged_root);
        assert!(processor.deferred_state().get_node(&selected_root).is_some());
        assert_eq!(processor.deferred_state().root(), logged_root);
    }

    #[test]
    fn register_data_rejects_framework_and_frames() {
        let malformed_and = EidosFrame::new(DEFERRED_AND_FRAME.domain(), [1, 0, 0]);

        for (name, frame, exact) in [
            ("exact AND frame", DEFERRED_AND_FRAME, true),
            ("parameterized AND-domain frame", malformed_and, false),
        ] {
            let mut stack = vec![ZERO, Felt::ONE];
            stack.extend(frame.initial_chaining_word());
            stack.push(ZERO);
            let mut processor =
                FastProcessor::new(StackInputs::new(&stack).expect("valid test stack"));

            let error = match handle_deferred_register_data(&mut processor) {
                Ok(()) => panic!("{name} should be rejected"),
                Err(error) => error,
            };
            let SystemEventError::Deferred(error) = error else {
                panic!("{name} returned the wrong error class: {error}");
            };
            if exact {
                assert!(
                    matches!(error.root(), PrecompileError::Other(DeferredError::InvalidFrame)),
                    "{name} returned {error}",
                );
            } else {
                assert!(
                    matches!(error.root(), PrecompileError::InvalidNode),
                    "{name} returned {error}",
                );
            }
        }
    }

    #[test]
    fn register_data_rejects_invalid_or_inconsistent_frames() {
        let mut malformed_cv = deferred_chunks_frame(1).initial_chaining_word().into_elements();
        malformed_cv[0] += Felt::new_unchecked(1 << 32);

        let unregistered_domain =
            DomainTag::from_u32(0x10ff_fe01).expect("test tag uses an allocated namespace");
        let unregistered_frame = EidosFrame::new(unregistered_domain, [0; 3]);

        let cases = [
            ("malformed fixed CV lane", 1, Word::new(malformed_cv)),
            ("unregistered domain", 1, unregistered_frame.initial_chaining_word()),
            (
                "CHUNKS frame/count mismatch",
                2,
                deferred_chunks_frame(1).initial_chaining_word(),
            ),
            (
                "fixed one-block domain with two blocks",
                2,
                Keccak256Precompile::assert_frame(0).initial_chaining_word(),
            ),
        ];

        for (name, n_chunks, cv) in cases {
            let mut stack = vec![ZERO, Felt::from_u32(n_chunks)];
            stack.extend(cv);
            stack.push(ZERO);
            let mut processor =
                FastProcessor::new(StackInputs::new(&stack).expect("valid test stack"));

            let error = match handle_deferred_register_data(&mut processor) {
                Ok(()) => panic!("{name} should be rejected"),
                Err(error) => error,
            };
            let SystemEventError::Deferred(error) = error else {
                panic!("{name} returned the wrong error class: {error}");
            };
            assert!(
                matches!(error.root(), PrecompileError::InvalidNode),
                "{name} returned {error}",
            );
        }
    }
}