miden-processor 1.0.0-rc.0

use alloc::string::String;

use miden_assembly::package::Package;
use rstest::fixture;

use super::*;

#[rstest]
// ---- syscalls --------------------------------

// check stack is preserved after syscall
#[case(Some("pub proc foo add end"), "begin push.1 syscall.foo swap.8 drop end", vec![Felt::from_u32(16); 16])]
// check that `fn_hash` register is updated correctly
#[case(Some("pub proc foo caller end"), "begin syscall.foo end", vec![Felt::from_u32(16); 16])]
#[case(Some("pub proc foo caller end"), "proc bar syscall.foo end begin call.bar end", vec![Felt::from_u32(16); 16])]
// check that clk works correctly through syscalls
#[case(Some("pub proc foo clk add end"), "begin syscall.foo end", vec![Felt::from_u32(16); 16])]
// check that fmp register is updated correctly after syscall
#[case(Some("@locals(2) pub proc foo locaddr.0 locaddr.1 swap.8 drop swap.8 drop end"), "proc bar syscall.foo end begin call.bar end", vec![Felt::from_u32(16); 16])]
// check that memory context is updated correctly across a syscall (i.e. anything stored before the
// syscall is retrievable after, but not during)
#[case(Some("pub proc foo add end"), "proc bar push.100 mem_store.44 syscall.foo mem_load.44 swap.8 drop end begin call.bar end", vec![Felt::from_u32(16); 16])]
// check that syscalls share the same memory context
#[case(Some("pub proc foo push.100 mem_store.44 end pub proc baz mem_load.44 swap.8 drop end"),
    "proc bar
        syscall.foo syscall.baz
    end
    begin call.bar end",
    vec![Felt::from_u32(16); 16]
)]
// ---- calls ------------------------

// check stack is preserved after call
#[case(None, "proc foo add end begin push.1 call.foo swap.8 drop end", vec![Felt::from_u32(16); 16])]
// check that `clk` works correctly though calls
#[case(None, "
    proc foo clk add end
    begin push.1
    if.true call.foo else swap end
    clk swap.8 drop
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that fmp register is updated correctly after call
#[case(None,"
    @locals(2) proc foo locaddr.0 locaddr.1 swap.8 drop swap.8 drop end
    begin call.foo end",
    vec![Felt::from_u32(16); 16]
)]
// check that 2 functions creating different memory contexts don't interfere with each other
#[case(None,"
    proc foo push.100 mem_store.44 end
    proc bar mem_load.44 assertz end
    begin call.foo mem_load.44 assertz call.bar end",
    vec![Felt::from_u32(16); 16]
)]
// check that memory context is updated correctly across a call (i.e. anything stored before the
// call is retrievable after, but not during)
#[case(None,"
    proc foo mem_load.44 assertz end
    proc bar push.100 mem_store.44 call.foo mem_load.44 swap.8 drop end
    begin call.bar end",
    vec![Felt::from_u32(16); 16]
)]
// ---- dyncalls ------------------------

// check stack is preserved after dyncall
#[case(None, "
    proc foo add end
    begin
        procref.foo mem_storew_le.100 dropw push.100
        dyncall swap.8 drop
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that `clk` works correctly though dyncalls
#[case(None, "
    proc foo clk add end
    begin
        push.1
        if.true
            procref.foo mem_storew_le.100 dropw
            push.100 dyncall
            push.100 dyncall
        else
            swap
        end
        clk swap.8 drop
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that fmp register is updated correctly after dyncall
#[case(None,"
    @locals(2) proc foo locaddr.0 locaddr.1 swap.8 drop swap.8 drop end
    begin
        procref.foo mem_storew_le.100 dropw push.100
        dyncall
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that 2 functions creating different memory contexts don't interfere with each other
#[case(None,"
    proc foo push.100 mem_store.44 end
    proc bar mem_load.44 assertz end
    begin
        procref.foo mem_storew_le.100 dropw push.100 dyncall
        mem_load.44 assertz
        procref.bar mem_storew_le.104 dropw push.104 dyncall
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that memory context is updated correctly across a dyncall (i.e. anything stored before the
// call is retrievable after, but not during)
#[case(None,"
    proc foo mem_load.44 assertz end
    proc bar
        push.100 mem_store.44
        procref.foo mem_storew_le.104 dropw push.104 dyncall
        mem_load.44 swap.8 drop
    end
    begin
        procref.bar mem_storew_le.104 dropw push.104 dyncall
    end",
    vec![Felt::from_u32(16); 16]
)]
// ---- dyn ------------------------

// check stack is preserved after dynexec
#[case(None, "
    proc foo add end
    begin
        procref.foo mem_storew_le.100 dropw push.100
        dynexec swap.8 drop
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that `clk` works correctly though dynexecs
#[case(None, "
    proc foo clk add end
    begin
        push.1
        if.true
            procref.foo mem_storew_le.100 dropw
            push.100 dynexec
            push.100 dynexec
        else
            swap
        end
        clk swap.8 drop
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that fmp register is updated correctly after dynexec
#[case(None,"
    @locals(2) proc foo locaddr.0 locaddr.1 swap.8 drop swap.8 drop end
    begin
        procref.foo mem_storew_le.100 dropw push.100
        dynexec
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that dynexec doesn't create a new memory context
#[case(None,"
    proc foo push.100 mem_store.44 end
    proc bar mem_load.44 sub.100 assertz end
    begin
        procref.foo mem_storew_le.104 dropw push.104 dynexec
        mem_load.44 sub.100 assertz
        procref.bar mem_storew_le.108 dropw push.108 dynexec
    end",
    vec![Felt::from_u32(16); 16]
)]
// ---- loop --------------------------------

// check that the loop is never entered if the condition is false (and that clk is properly updated)
// Stack: [ZERO, 1, 2, 3] with ZERO at top (for while.true condition)
#[case(None, "begin while.true push.1 assertz end clk swap.8 drop end", vec![ZERO, Felt::from_u32(1), Felt::from_u32(2), Felt::from_u32(3)])]
// check that the loop is entered if the condition is true, and that the stack and clock are managed
// properly
// Stack: [ONE, ONE, ONE, ONE, ZERO, 42] with first ONE at top (for while.true condition)
#[case(None,
    "begin
        while.true
            clk swap.15 drop
        end
        clk swap.8 drop
    end",
    vec![ONE, ONE, ONE, ONE, ZERO, Felt::from_u32(42)]
)]
// ---- horner ops --------------------------------
#[case(None,
    "begin
        push.0.0.3.4 mem_storew_le.40 dropw
        horner_eval_base
    end",
    vec![Felt::from_u32(16), Felt::from_u32(15), Felt::from_u32(14), Felt::from_u32(13), Felt::from_u32(12), Felt::from_u32(11), Felt::from_u32(10),
        Felt::from_u32(9), Felt::from_u32(8), Felt::from_u32(7), Felt::from_u32(6), Felt::from_u32(5), Felt::from_u32(4),
        Felt::from_u32(40), Felt::from_u32(4), Felt::from_u32(100)]
)]
#[case(None,
    "begin
        push.0.0.3.4 mem_storew_le.40 dropw
        horner_eval_ext
        end",
    vec![Felt::from_u32(16), Felt::from_u32(15), Felt::from_u32(14), Felt::from_u32(13), Felt::from_u32(12), Felt::from_u32(11), Felt::from_u32(10),
        Felt::from_u32(9), Felt::from_u32(8), Felt::from_u32(7), Felt::from_u32(6), Felt::from_u32(5), Felt::from_u32(4),
        Felt::from_u32(40), Felt::from_u32(4), Felt::from_u32(100)]
)]
// ---- log deferred ops --------------------------------
// Drift marker only: this snapshot guards the `log_deferred` deferred-root output against
// silent changes. The semantic folding rule is asserted in `test_log_deferred_correctness`.
// TRUE_DIGEST is the zero word at the top of the stack.
#[case(None, "begin log_deferred end",
    vec![ZERO; 8],
)]
// ---- u32 ops --------------------------------
// check that u32 6/3 works as expected
#[case(None,"
    begin
        u32divmod
    end",
    vec![Felt::from_u32(6), Felt::from_u32(3)]
)]
// check that overflowing add properly sets the overflow bit
#[case(None,"
    begin
        u32overflowing_add sub.1 assertz
    end",
    vec![Felt::from_u32(u32::MAX), ONE]
)]
fn test_masm_consistency(
    testname: String,
    #[case] kernel_source: Option<&'static str>,
    #[case] program_source: &'static str,
    #[case] stack_inputs: Vec<Felt>,
) {
    let (program, kernel_lib) = {
        let source_manager = Arc::new(DefaultSourceManager::default());

        match kernel_source {
            Some(kernel_source) => {
                let kernel = parse_kernel_source(source_manager.clone(), kernel_source);
                let kernel_lib = Assembler::new(source_manager.clone())
                    .assemble_kernel("kernel", kernel, None)
                    .map(Arc::<Package>::from)
                    .unwrap();
                let program = Assembler::with_kernel(source_manager, kernel_lib.clone())
                    .unwrap()
                    .assemble_program("program", program_source)
                    .unwrap()
                    .unwrap_program();

                (program, Some(kernel_lib))
            },
            None => {
                let program = Assembler::new(source_manager)
                    .assemble_program("program", program_source)
                    .unwrap()
                    .unwrap_program();
                (program, None)
            },
        }
    };

    let mut host = DefaultHost::default();
    if let Some(kernel_lib) = &kernel_lib {
        host.load_library(kernel_lib.mast_forest()).unwrap();
    }

    // fast processor
    let processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
    let fast_stack_outputs = processor.execute_sync(&program, &mut host).unwrap().stack;

    // fast processor by step
    let stepped_stack_outputs = {
        let processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
        processor.execute_by_step_sync(&program, &mut host).unwrap()
    };

    assert_eq!(fast_stack_outputs, stepped_stack_outputs);
    insta::assert_debug_snapshot!(testname, fast_stack_outputs);
}

/// Tests that emitted errors are consistent between the fast and slow processors.
#[rstest]
// check that error is returned if condition is not a boolean
#[case(None, "begin while.true swap end end", vec![Felt::from_u32(2); 16])]
#[case(None, "begin while.true push.100 end end", vec![ONE; 16])]
// check that dynamically calling a hash that doesn't exist fails
#[case(None,"
    begin
        dyncall
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that dynamically calling a hash that doesn't exist fails
#[case(None,"
    begin
        dynexec
    end",
    vec![Felt::from_u32(16); 16]
)]
// check that u32 division by 0 results in an error
#[case(None,"
    begin
        u32divmod
    end",
    vec![ZERO; 16]
)]
// check that adding any value to a u32::MAX results in an error
#[case(None,"
    begin
        u32overflowing_add
    end",
    vec![Felt::from_u32(u32::MAX) + ONE, ZERO]
)]
fn test_masm_errors_consistency(
    testname: String,
    #[case] kernel_source: Option<&'static str>,
    #[case] program_source: &'static str,
    #[case] stack_inputs: Vec<Felt>,
) {
    let (program, kernel_lib) = {
        let source_manager = Arc::new(DefaultSourceManager::default());

        match kernel_source {
            Some(kernel_source) => {
                let kernel = parse_kernel_source(source_manager.clone(), kernel_source);
                let kernel_lib = Assembler::new(source_manager.clone())
                    .assemble_kernel("kernel", kernel, None)
                    .map(Arc::<Package>::from)
                    .unwrap();
                let program = Assembler::with_kernel(source_manager, kernel_lib.clone())
                    .unwrap()
                    .assemble_program("program", program_source)
                    .unwrap()
                    .unwrap_program();

                (program, Some(kernel_lib))
            },
            None => {
                let program = Assembler::new(source_manager)
                    .assemble_program("program", program_source)
                    .unwrap()
                    .unwrap_program();
                (program, None)
            },
        }
    };

    let mut host = DefaultHost::default();
    if let Some(kernel_lib) = &kernel_lib {
        host.load_library(kernel_lib.mast_forest()).unwrap();
    }

    // fast processor
    let processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
    let fast_err = processor.execute_sync(&program, &mut host).unwrap_err();

    // fast processor by step
    let fast_stepped_err = {
        let processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
        processor.execute_by_step_sync(&program, &mut host).unwrap_err()
    };

    assert_eq!(fast_err.to_string(), fast_stepped_err.to_string());
    insta::assert_debug_snapshot!(testname, fast_err);
}

/// Tests that `log_deferred` folds a statement word into the rolling deferred root.
#[test]
fn test_log_deferred_correctness() {
    use miden_core::deferred::TRUE_DIGEST;

    // The opcode replaces STMNT at stack[0..4] with STATE_NEW.
    // `log_deferred` only accepts a registered statement that evaluates to TRUE. The framework
    // TRUE node is implicitly registered by every processor, so it is the minimal valid fixture
    // for testing the constrained root transition directly.
    let mut stack_inputs =
        [0, 0, 0, 0, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20].map(Felt::new_unchecked);
    stack_inputs[0..4].copy_from_slice(TRUE_DIGEST.as_elements());
    let stmnt = TRUE_DIGEST;
    let state_prev = Word::empty();
    let expected_state_new = deferred_and_digest(state_prev, stmnt);

    let program_source = "begin log_deferred end";
    let program = {
        let source_manager = Arc::new(DefaultSourceManager::default());
        Assembler::new(source_manager)
            .assemble_program("program", program_source)
            .unwrap()
            .unwrap_program()
    };

    let mut host = DefaultHost::default();
    let processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
    let execution_output = processor.execute_sync(&program, &mut host).unwrap();

    let actual_state_new = execution_output.stack.get_word(0).unwrap();

    assert_eq!(expected_state_new, actual_state_new, "STATE_NEW mismatch");
    for (offset, expected) in stack_inputs[4..].iter().enumerate() {
        assert_eq!(
            execution_output.stack.get_element(offset + 4),
            Some(*expected),
            "stack tail changed at position {}",
            offset + 4
        );
    }
}

/// Exporting an unlogged assertion preserves its original root and the execution's deferred root.
#[test]
fn export_deferred_witness_opens_an_unlogged_shared_graph() {
    use miden_core::{
        advice::AdviceStack,
        deferred::{Node, PrecompileRegistry, PrecompileWitness, TRUE_DIGEST},
        utils::packed_u32_elements_to_bytes,
    };

    let mut processor = FastProcessor::new(StackInputs::default());
    let state = processor.deferred_state_mut();
    let shared = state.register(Node::and(TRUE_DIGEST, TRUE_DIGEST)).unwrap();
    let branch = state.register(Node::and(shared, shared)).unwrap();
    let selected = state.register(Node::and(branch, branch)).unwrap();
    let unrelated = state.register(Node::and(shared, TRUE_DIGEST)).unwrap();
    let logged_root = state.log_statement(unrelated).unwrap();
    let byte_len = state
        .witness_for(selected, &miden_precompiles::default_verification_precompile_limits())
        .unwrap()
        .to_bytes()
        .len();
    assert!(!byte_len.is_multiple_of(4), "exercise final-limb padding");

    let mut stack_inputs = [Felt::from_u32(7); 16];
    stack_inputs[..4].copy_from_slice(selected.as_elements());
    for (offset, value) in stack_inputs.iter().copied().enumerate() {
        processor.stack_write(offset, value);
    }
    let advice_stack = vec![Felt::from_u32(17), Felt::from_u32(19)];
    processor = processor
        .with_advice(AdviceInputs::default().with_stack(AdviceStack::from(advice_stack.clone())))
        .unwrap();
    let program = Assembler::new(Arc::new(DefaultSourceManager::default()))
        .assemble_program(
            "program",
            r#"begin
                # Insert one zero felt under the selected root before exporting its witness.
                push.0.1 movdn.5 movdn.4 adv.insert_mem
                movup.4 drop movup.4 drop
                adv.export_deferred_witness
                emit.event("sys::adv::export_deferred_witness")
            end"#,
        )
        .unwrap()
        .unwrap_program();
    let output = processor.execute_sync(&program, &mut DefaultHost::default()).unwrap();

    assert_eq!(output.precompile_root(), logged_root);
    for (offset, expected) in stack_inputs.into_iter().enumerate() {
        assert_eq!(output.stack.get_element(offset), Some(expected));
    }
    assert_eq!(output.advice.stack(), advice_stack);
    assert_eq!(output.advice.map().len(), 1);
    let value = output.advice.get_mapped_values(&selected).unwrap();
    assert_eq!(value[0].as_canonical_u64() as usize, byte_len);
    assert_eq!(value.len(), 1 + byte_len.div_ceil(4));
    let bytes = packed_u32_elements_to_bytes(&value[1..]);
    assert!(bytes[byte_len..].iter().all(|byte| *byte == 0));
    let witness = PrecompileWitness::read_from_bytes(&bytes[..byte_len]).unwrap();
    let prepared = witness
        .prepare(
            Arc::new(PrecompileRegistry::new()),
            &miden_precompiles::default_verification_precompile_limits(),
        )
        .unwrap();
    assert_eq!(prepared.root(), selected);
    let mut digests = vec![TRUE_DIGEST];
    digests.extend(prepared.into_nodes().map(|node| node.digest()));
    assert_eq!(digests, [TRUE_DIGEST, shared, branch, selected]);
}

/// Tests that successive `log_deferred` calls fold registered DAG roots in execution order.
#[test]
fn successive_log_deferred_calls_build_an_ordered_and_chain() {
    use miden_core::deferred::{DEFERRED_AND_FRAME, Node, TRUE_DIGEST};

    let first_node = Node::and(TRUE_DIGEST, TRUE_DIGEST);
    let first_statement = first_node.digest();
    let second_node = Node::and(first_statement, TRUE_DIGEST);
    let second_statement = second_node.digest();

    let mut stack_inputs = [ZERO; 16];
    stack_inputs[0..4].copy_from_slice(first_statement.as_elements());
    stack_inputs[4..8].copy_from_slice(second_statement.as_elements());
    for (offset, value) in stack_inputs[8..].iter_mut().enumerate() {
        *value = Felt::new_unchecked(offset as u64 + 9);
    }

    let source_manager = Arc::new(DefaultSourceManager::default());
    let program = Assembler::new(source_manager)
        .assemble_program("program", "begin log_deferred dropw log_deferred end")
        .unwrap()
        .unwrap_program();

    let mut processor = FastProcessor::new(StackInputs::new(&stack_inputs).unwrap());
    processor.deferred_state_mut().register(first_node).unwrap();
    processor.deferred_state_mut().register(second_node).unwrap();

    let first_root = deferred_and_digest(TRUE_DIGEST, first_statement);
    let expected_root = deferred_and_digest(first_root, second_statement);
    let reversed_root =
        deferred_and_digest(deferred_and_digest(TRUE_DIGEST, second_statement), first_statement);
    assert_ne!(expected_root, reversed_root);

    let execution_output = processor.execute_sync(&program, &mut DefaultHost::default()).unwrap();

    assert_eq!(execution_output.stack.get_word(0), Some(expected_root));
    assert_eq!(execution_output.precompile_root(), expected_root);
    let prepared = execution_output
        .precompile_witness
        .expect("log_deferred leaves a precompile witness")
        .prepare(
            Arc::new(miden_precompiles::registry()),
            &miden_precompiles::default_verification_precompile_limits(),
        )
        .expect("execution-produced witness must prepare");
    assert_eq!(prepared.root(), expected_root);
    let nodes = prepared.into_nodes().collect::<Vec<_>>();
    // Check both prepared AND steps bind the expected child commitments.
    for (digest, expected_children) in [
        (first_root, (TRUE_DIGEST, first_statement)),
        (expected_root, (first_root, second_statement)),
    ] {
        let prepared = nodes
            .iter()
            .find(|prepared| prepared.digest() == digest)
            .expect("AND node is in the witness");
        let node = prepared.node();
        assert_eq!(node.frame(), Some(DEFERRED_AND_FRAME));
        assert_eq!(node.payload().as_join().unwrap(), expected_children);
    }
    for (offset, expected) in stack_inputs[8..].iter().enumerate() {
        assert_eq!(
            execution_output.stack.get_element(offset + 4),
            Some(*expected),
            "stack tail changed at position {}",
            offset + 4,
        );
    }
}

fn deferred_and_digest(lhs: Word, rhs: Word) -> Word {
    use miden_core::{crypto::hash::Eidos, deferred::DEFERRED_AND_INIT_CV};

    let mut block = [ZERO; 8];
    block[0..4].copy_from_slice(lhs.as_slice());
    block[4..8].copy_from_slice(rhs.as_slice());
    Eidos::compress(DEFERRED_AND_INIT_CV, block)
}

// Workaround to make insta and rstest work together.
// See: https://github.com/la10736/rstest/issues/183#issuecomment-1564088329
#[fixture]
fn testname() -> String {
    // Replace `::` with `__` to make snapshot file names Windows-compatible.
    // Windows does not allow `:` in file names.
    std::thread::current().name().unwrap().replace("::", "__")
}