miden-processor 1.0.0-rc.0

//! Hasher-chiplet bus tests.
//!
//! For each of the main hasher scenarios (SPAN/END control block, RESPAN, SPLIT merge, COMPRESS,
//! LOGDEFERRED, MPVERIFY, MRUPDATE) the test registers the decoder-side `remove` requests and
//! the chiplet-side `add` responses it expects to see, then lets
//! [`InteractionLog::assert_contains`] confirm every one of them fires somewhere in the trace.
//!
//! Because request and response messages share a `bus_prefix` and the same payload shape,
//! an add at a controller row and a remove at the matching decoder row produce the same
//! encoded denominator with opposite multiplicities — which is what makes the bus balance.
//! The subset matcher verifies each claimed interaction lands; their pairing is an algebraic
//! consequence.
//!
//! Each test pairs the `assert_contains` call with explicit request/response-count guardrails
//! so a silent-pass bug (e.g. the subset matcher ignoring a whole category of expectations
//! because nothing was registered) is caught structurally, not just by shape.

use alloc::vec::Vec;

use miden_air::{
    logup::{HasherMsg, SiblingBit, SiblingMsg},
    trace::{
        MainTrace,
        chiplets::hasher::CONTROLLER_ROWS_PER_HASHER_OP_FELT,
        log_deferred::{
            HELPER_ADDR_IDX, HELPER_STATE_PREV_RANGE, STACK_STATE_NEW_RANGE, STACK_STMNT_RANGE,
        },
    },
};
use miden_core::{
    Felt, ONE, Word, ZERO,
    chiplets::eidos_compression,
    crypto::merkle::{MerkleStore, MerkleTree, NodeIndex},
    deferred::DEFERRED_AND_INIT_CV,
    mast::{BasicBlockNodeBuilder, MastForest, SplitNodeBuilder},
    operations::{Operation, opcodes},
    program::Program,
};
use miden_utils_testing::{stack, stack_inputs_from_ints};
use rstest::rstest;

use super::super::{
    build_trace_from_ops_with_inputs, build_trace_from_program,
    lookup_harness::{Expectations, InteractionLog},
};
use crate::{AdviceInputs, RowIndex, trace::utils::build_span_with_respan_ops};

// RESPONSE-SIDE DISPATCH
// ================================================================================================

/// Hasher controller response kinds emitted by one-row controller rows.
///
/// Shared across every test so each can `match` on the semantic kind instead of re-deriving
/// the selector combinations by hand.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum HasherResponseKind {
    LinearHashInit,
    Absorption,
    MpInput,
    MvOldInput,
    MuNewInput,
    ReturnHash,
}

/// Walk every hasher controller row and collect the response-side interactions that row emits.
fn hasher_response_rows(main: &MainTrace) -> Vec<(RowIndex, HasherResponseKind)> {
    let mut rows = Vec::new();
    for row in 0..main.chiplets_height() {
        let idx = RowIndex::from(row);
        if !is_hasher_controller_row(main, idx) {
            continue;
        }
        let Some(hs0) = as_bit(main.chiplet_selector_1(idx)) else {
            continue;
        };
        let Some(hs1) = as_bit(main.chiplet_selector_2(idx)) else {
            continue;
        };
        let Some(hs2) = as_bit(main.chiplet_selector_3(idx)) else {
            continue;
        };
        let Some(merkle_or_padding) = as_bit(main.chiplet_cols(idx).controller_merkle_or_padding())
        else {
            continue;
        };
        let Some(op_final) = as_bit(main.chiplet_cols(idx).controller_op_final()) else {
            continue;
        };

        if !merkle_or_padding {
            if hs0 {
                rows.push((idx, HasherResponseKind::LinearHashInit));
            } else {
                rows.push((idx, HasherResponseKind::Absorption));
            }
        } else if hs0 && as_bit(main.chiplet_merkle_is_start(idx)) == Some(true) {
            match (hs1, hs2) {
                (false, true) => rows.push((idx, HasherResponseKind::MpInput)),
                (true, false) => rows.push((idx, HasherResponseKind::MvOldInput)),
                (true, true) => rows.push((idx, HasherResponseKind::MuNewInput)),
                _ => {},
            }
        }

        if op_final {
            rows.push((idx, HasherResponseKind::ReturnHash));
        }
    }
    rows
}

// TESTS
// ================================================================================================

#[test]
fn span_end_hasher_bus() {
    let program = single_block_program(vec![Operation::Add, Operation::Mul]);

    let trace = build_trace_from_program(&program, &[]);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut request_count = 0usize;

    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();

        if op == opcodes::SPAN as u64 {
            let addr_next = main.addr(RowIndex::from(row + 1));
            let block = block_from_hasher_state(main, idx);
            exp.remove(row, &HasherMsg::basic_block_init(addr_next, &block, main.group_count(idx)));
            request_count += 1;
        } else if op == opcodes::END as u64 {
            let parent = main.addr(idx) + CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE;
            let block = block_from_hasher_state(main, idx);
            let digest: [Felt; 4] = [block[0], block[1], block[2], block[3]];
            exp.remove(row, &HasherMsg::return_hash(parent, digest));
            request_count += 1;
        }
    }

    let mut response_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        match kind {
            HasherResponseKind::LinearHashInit => {
                exp.add(usize::from(idx), &HasherMsg::linear_hash_init(addr, state));
                response_count += 1;
            },
            HasherResponseKind::ReturnHash => {
                let digest = return_digest_from_controller_row(main, idx);
                exp.add(usize::from(idx), &HasherMsg::return_hash(addr, digest));
                response_count += 1;
            },
            _ => {},
        }
    }

    assert_eq!(request_count, 2, "SPAN+END: expected 2 removes (SPAN + END)");
    assert_eq!(response_count, 2, "SPAN+END: expected 2 adds (init + return)");
    log.assert_contains(&exp);
}

#[test]
fn respan_hasher_bus() {
    let (ops, _iv) = build_span_with_respan_ops();
    let program = single_block_program(ops);

    let trace = build_trace_from_program(&program, &[]);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut respan_request_count = 0usize;

    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::RESPAN as u64 {
            continue;
        }
        let addr_next = main.addr(RowIndex::from(row + 1));
        let block = block_from_hasher_state(main, idx);
        exp.remove(row, &HasherMsg::absorption(addr_next, block));
        respan_request_count += 1;
    }

    let mut absorption_response_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        if kind != HasherResponseKind::Absorption {
            continue;
        }
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        let block: [Felt; 8] =
            [state[0], state[1], state[2], state[3], state[4], state[5], state[6], state[7]];
        exp.add(usize::from(idx), &HasherMsg::absorption(addr, block));
        absorption_response_count += 1;
    }

    assert!(respan_request_count > 0, "multi-batch span should emit at least one RESPAN");
    assert_eq!(
        respan_request_count, absorption_response_count,
        "each RESPAN request must be paired with an absorption response",
    );
    log.assert_contains(&exp);
}

#[test]
fn merge_hasher_bus() {
    let program = {
        let mut mast_forest = MastForest::new();
        let t_branch = BasicBlockNodeBuilder::new(vec![Operation::Add])
            .add_to_forest(&mut mast_forest)
            .unwrap();
        let f_branch = BasicBlockNodeBuilder::new(vec![Operation::Mul])
            .add_to_forest(&mut mast_forest)
            .unwrap();
        let split_id = SplitNodeBuilder::new([t_branch, f_branch])
            .add_to_forest(&mut mast_forest)
            .unwrap();
        mast_forest.make_root(split_id);
        Program::new(mast_forest.into(), split_id)
    };

    let trace = build_trace_from_program(&program, &[]);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut split_request_count = 0usize;

    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::SPLIT as u64 {
            continue;
        }
        let addr_next = main.addr(RowIndex::from(row + 1));
        let block = block_from_hasher_state(main, idx);
        exp.remove(row, &HasherMsg::control_block(addr_next, &block, opcodes::SPLIT));
        split_request_count += 1;
    }

    let mut split_response_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        if kind != HasherResponseKind::LinearHashInit {
            continue;
        }
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        // SPLIT's own hasher response carries the SPLIT opcode in its Eidos chaining word;
        // sibling SPAN hash-init rows use the generic Felt-sequence domain tag.
        let split_cv = eidos_compression::two_to_one_chaining_word(opcodes::SPLIT as u32);
        if state[8..12] == *split_cv {
            exp.add(usize::from(idx), &HasherMsg::linear_hash_init(addr, state));
            split_response_count += 1;
        }
    }

    assert_eq!(split_request_count, 1, "single SPLIT program should emit one SPLIT remove");
    assert_eq!(
        split_response_count, 1,
        "single SPLIT program should emit one SPLIT-domain hash-init response",
    );
    log.assert_contains(&exp);
}

#[test]
fn compress_hasher_bus() {
    let program = single_block_program(vec![Operation::Compress]);
    let stack = vec![8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 8];
    let trace = build_trace_from_program(&program, &stack);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut request_count = 0usize;
    let mut compress_helper0: Option<Felt> = None;
    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::COMPRESS as u64 {
            continue;
        }

        let helper0 = main.helper_register(0, idx);
        compress_helper0 = Some(helper0);
        let next = RowIndex::from(row + 1);
        let stk_state: [Felt; 12] = core::array::from_fn(|i| main.stack_element(i, idx));
        let cv_next: [Felt; 4] = core::array::from_fn(|i| main.stack_element(8 + i, next));
        exp.remove(row, &HasherMsg::linear_hash_init(helper0, stk_state));
        exp.remove(
            row,
            &HasherMsg::return_hash(helper0 + CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE, cv_next),
        );
        request_count += 2;
    }
    let compress_helper0 = compress_helper0.expect("program should contain a COMPRESS row");
    let compress_return_addr = compress_helper0 + CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE;

    let mut hash_init_count = 0usize;
    let mut return_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        match kind {
            HasherResponseKind::LinearHashInit => {
                exp.add(usize::from(idx), &HasherMsg::linear_hash_init(addr, state));
                // Only the COMPRESS-paired hash-init response matches `compress_helper0`; the outer
                // SPAN/END controller rows live on their own `addr` track.
                if addr == compress_helper0 {
                    hash_init_count += 1;
                }
            },
            HasherResponseKind::ReturnHash => {
                let digest = return_digest_from_controller_row(main, idx);
                exp.add(usize::from(idx), &HasherMsg::return_hash(addr, digest));
                if addr == compress_return_addr {
                    return_count += 1;
                }
            },
            _ => {},
        }
    }

    assert_eq!(request_count, 2, "COMPRESS: expected 2 removes (init + return)");
    assert_eq!(hash_init_count, 1, "COMPRESS: expected 1 COMPRESS-paired hash-init response");
    assert_eq!(return_count, 1, "COMPRESS: expected 1 COMPRESS-paired return");
    log.assert_contains(&exp);
}

#[test]
fn logdeferred_hasher_bus() {
    let program = single_block_program(vec![Operation::LogDeferred]);
    let stack_inputs = stack![0, 0, 0, 0, 0, 0, 0, 0];
    let trace = build_trace_from_program(&program, &stack_inputs);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut request_count = 0usize;
    let mut logdeferred_addr: Option<Felt> = None;
    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::LOGDEFERRED as u64 {
            continue;
        }

        let next = RowIndex::from(row + 1);
        let log_addr = main.helper_register(HELPER_ADDR_IDX, idx);
        logdeferred_addr = Some(log_addr);

        let cv = DEFERRED_AND_INIT_CV;

        // Input: [STATE_PREV, STMNT, CV] — 4 helpers + 4 stack lanes + AND init CV.
        let input_state: [Felt; 12] = core::array::from_fn(|i| {
            if i < 4 {
                main.helper_register(HELPER_STATE_PREV_RANGE.start + i, idx)
            } else if i < 8 {
                main.stack_element(STACK_STMNT_RANGE.start + (i - 4), idx)
            } else {
                cv[i - 8]
            }
        });

        let state_new: [Felt; 4] =
            core::array::from_fn(|i| main.stack_element(STACK_STATE_NEW_RANGE.start + i, next));

        exp.remove(row, &HasherMsg::linear_hash_init(log_addr, input_state));
        exp.remove(
            row,
            &HasherMsg::return_hash(log_addr + CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE, state_new),
        );
        request_count += 2;
    }
    let log_addr = logdeferred_addr.expect("program should contain a LOGDEFERRED row");
    let log_return_addr = log_addr + CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE;

    let mut hash_init_count = 0usize;
    let mut return_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        match kind {
            HasherResponseKind::LinearHashInit => {
                exp.add(usize::from(idx), &HasherMsg::linear_hash_init(addr, state));
                if addr == log_addr {
                    hash_init_count += 1;
                }
            },
            HasherResponseKind::ReturnHash => {
                let digest = return_digest_from_controller_row(main, idx);
                exp.add(usize::from(idx), &HasherMsg::return_hash(addr, digest));
                if addr == log_return_addr {
                    return_count += 1;
                }
            },
            _ => {},
        }
    }

    assert_eq!(request_count, 2, "LOGDEFERRED: expected 2 removes (init + return)");
    assert_eq!(
        hash_init_count, 1,
        "LOGDEFERRED: expected 1 LOGDEFERRED-paired hash-init response"
    );
    assert_eq!(return_count, 1, "LOGDEFERRED: expected 1 LOGDEFERRED-paired return");
    log.assert_contains(&exp);
}

#[test]
fn mpverify_hasher_bus() {
    let index = 5usize;
    let leaves = init_leaves(&[1, 2, 3, 4, 5, 6, 7, 8]);
    let tree = MerkleTree::new(&leaves).unwrap();

    let mut runtime_stack = Vec::new();
    runtime_stack.extend_from_slice(&word_to_ints(leaves[index]));
    runtime_stack.push(tree.depth() as u64);
    runtime_stack.push(index as u64);
    runtime_stack.extend_from_slice(&word_to_ints(tree.root()));
    let stack_inputs = stack_inputs_from_ints(runtime_stack);
    let store = MerkleStore::from(&tree);
    let advice_inputs = AdviceInputs::default().with_merkle_store(store);

    let trace = build_trace_from_ops_with_inputs(
        vec![Operation::MpVerify(ZERO)],
        stack_inputs,
        advice_inputs,
    );
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut request_count = 0usize;

    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::MPVERIFY as u64 {
            continue;
        }
        let helper0 = main.helper_register(0, idx);
        let direction_bit = main.helper_register(1, idx);
        let mp_depth = main.stack_element(4, idx);
        let mp_index = main.stack_element(5, idx);
        let leaf_word: [Felt; 4] = core::array::from_fn(|i| main.stack_element(i, idx));
        let old_root: [Felt; 4] = core::array::from_fn(|i| main.stack_element(6 + i, idx));

        let return_addr = helper0 + mp_depth * CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE;
        exp.remove(
            row,
            &HasherMsg::merkle_verify_init(helper0, mp_index, direction_bit, leaf_word),
        );
        exp.remove(row, &HasherMsg::return_hash(return_addr, old_root));
        request_count += 2;
    }

    let mut mp_input_count = 0usize;
    let mut return_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        let block_lo: [Felt; 4] = [state[0], state[1], state[2], state[3]];
        let block_hi: [Felt; 4] = [state[4], state[5], state[6], state[7]];
        match kind {
            HasherResponseKind::MpInput => {
                let node_index = main.chiplet_node_index(idx);
                // Match the emitter's own `bit = node_index - 2·node_index_next` formula.
                let bit = merkle_direction_bit(main, idx);
                let word: [Felt; 4] = if bit == ZERO { block_lo } else { block_hi };
                exp.add(
                    usize::from(idx),
                    &HasherMsg::merkle_verify_init(addr, node_index, bit, word),
                );
                mp_input_count += 1;
            },
            HasherResponseKind::ReturnHash => {
                exp.add(
                    usize::from(idx),
                    &HasherMsg::return_hash(addr, return_digest_from_controller_row(main, idx)),
                );
                return_count += 1;
            },
            _ => {},
        }
    }

    assert_eq!(request_count, 2, "MPVERIFY: expected 2 removes (init + return)");
    assert_eq!(mp_input_count, 1, "MPVERIFY: expected 1 mp_verify_input add");
    assert_eq!(return_count, 2, "MPVERIFY: expected exactly 2 return-hash adds");
    log.assert_contains(&exp);
}

#[test]
fn mrupdate_hasher_bus() {
    let index = 5usize;
    let leaves = init_leaves(&[1, 2, 3, 4, 5, 6, 7, 8]);
    let tree = MerkleTree::new(&leaves).unwrap();
    let new_leaf_value = leaves[0];

    let mut runtime_stack = Vec::new();
    runtime_stack.extend_from_slice(&word_to_ints(leaves[index]));
    runtime_stack.push(tree.depth() as u64);
    runtime_stack.push(index as u64);
    runtime_stack.extend_from_slice(&word_to_ints(tree.root()));
    runtime_stack.extend_from_slice(&word_to_ints(new_leaf_value));
    let stack_inputs = stack_inputs_from_ints(runtime_stack);
    let store = MerkleStore::from(&tree);
    let advice_inputs = AdviceInputs::default().with_merkle_store(store);

    let trace =
        build_trace_from_ops_with_inputs(vec![Operation::MrUpdate], stack_inputs, advice_inputs);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    let mut exp = Expectations::new(&log);
    let mut request_count = 0usize;

    for row in 0..main.core_height() {
        let idx = RowIndex::from(row);
        let op = main.get_op_code(idx).as_canonical_u64();
        if op != opcodes::MRUPDATE as u64 {
            continue;
        }
        let helper0 = main.helper_register(0, idx);
        let direction_bit = main.helper_register(1, idx);
        let next = RowIndex::from(row + 1);
        let mr_depth = main.stack_element(4, idx);
        let mr_index = main.stack_element(5, idx);
        let old_leaf: [Felt; 4] = core::array::from_fn(|i| main.stack_element(i, idx));
        let old_root: [Felt; 4] = core::array::from_fn(|i| main.stack_element(6 + i, idx));
        let new_leaf: [Felt; 4] = core::array::from_fn(|i| main.stack_element(10 + i, idx));
        let new_root: [Felt; 4] = core::array::from_fn(|i| main.stack_element(i, next));

        let old_return = helper0 + mr_depth * CONTROLLER_ROWS_PER_HASHER_OP_FELT - ONE;
        let new_init = helper0 + mr_depth * CONTROLLER_ROWS_PER_HASHER_OP_FELT;
        let new_return = helper0
            + mr_depth * (CONTROLLER_ROWS_PER_HASHER_OP_FELT + CONTROLLER_ROWS_PER_HASHER_OP_FELT)
            - ONE;

        exp.remove(row, &HasherMsg::merkle_old_init(helper0, mr_index, direction_bit, old_leaf));
        exp.remove(row, &HasherMsg::return_hash(old_return, old_root));
        exp.remove(row, &HasherMsg::merkle_new_init(new_init, mr_index, direction_bit, new_leaf));
        exp.remove(row, &HasherMsg::return_hash(new_return, new_root));
        request_count += 4;
    }

    let mut mv_count = 0usize;
    let mut mu_count = 0usize;
    let mut return_count = 0usize;
    for (idx, kind) in hasher_response_rows(main) {
        let addr = main.chiplet_clk(idx);
        let state = main.chiplet_hasher_state(idx);
        let block_lo: [Felt; 4] = [state[0], state[1], state[2], state[3]];
        let block_hi: [Felt; 4] = [state[4], state[5], state[6], state[7]];
        let node_index = main.chiplet_node_index(idx);
        let bit = merkle_direction_bit(main, idx);
        let word: [Felt; 4] = if bit == ZERO { block_lo } else { block_hi };

        match kind {
            HasherResponseKind::MvOldInput => {
                exp.add(usize::from(idx), &HasherMsg::merkle_old_init(addr, node_index, bit, word));
                mv_count += 1;
            },
            HasherResponseKind::MuNewInput => {
                exp.add(usize::from(idx), &HasherMsg::merkle_new_init(addr, node_index, bit, word));
                mu_count += 1;
            },
            HasherResponseKind::ReturnHash => {
                exp.add(
                    usize::from(idx),
                    &HasherMsg::return_hash(addr, return_digest_from_controller_row(main, idx)),
                );
                return_count += 1;
            },
            _ => {},
        }
    }

    assert_eq!(
        request_count, 4,
        "MRUPDATE: expected 4 removes (old_init + old_return + new_init + new_return)",
    );
    assert_eq!(mv_count, 1, "MRUPDATE: expected 1 mr_update_old_input add");
    assert_eq!(mu_count, 1, "MRUPDATE: expected 1 mr_update_new_input add");
    assert_eq!(return_count, 3, "MRUPDATE: expected exactly 3 return-hash adds");
    log.assert_contains(&exp);
}

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

fn single_block_program(ops: Vec<Operation>) -> Program {
    let mut mast_forest = MastForest::new();
    let id = BasicBlockNodeBuilder::new(ops).add_to_forest(&mut mast_forest).unwrap();
    mast_forest.make_root(id);
    Program::new(mast_forest.into(), id)
}

fn block_from_hasher_state(main: &MainTrace, row: RowIndex) -> [Felt; 8] {
    let first = main.decoder_hasher_state_first_half(row);
    let second = main.decoder_hasher_state_second_half(row);
    [
        first[0], first[1], first[2], first[3], second[0], second[1], second[2], second[3],
    ]
}

fn return_digest_from_controller_row(main: &MainTrace, row: RowIndex) -> [Felt; 4] {
    let ctrl = main.chiplet_cols(row).controller();
    if main.chiplet_cols(row).controller_merkle_or_padding() == ONE {
        ctrl.merkle_digest()
    } else {
        ctrl.hash_cv()
    }
}

fn is_hasher_controller_row(main: &MainTrace, row: RowIndex) -> bool {
    main.is_hash_row(row)
}

/// Returns `Some(false)` for ZERO, `Some(true)` for ONE, and `None` for any other value.
///
/// Used to guard selector-bit reads: a malformed value (e.g. 2) yields `None` so the row is
/// skipped rather than silently misclassified.
fn as_bit(val: Felt) -> Option<bool> {
    if val == ZERO {
        Some(false)
    } else if val == ONE {
        Some(true)
    } else {
        None
    }
}

/// Recompute the Merkle direction bit the emitter uses: `bit = node_index - 2·node_index_next`.
fn merkle_direction_bit(main: &MainTrace, row: RowIndex) -> Felt {
    main.chiplet_node_index(row) - main.chiplet_node_index_next(row).double()
}

// SIBLING TABLE (MRUPDATE add/remove pairing)
// ================================================================================================
//
// MRUPDATE verifies the old root on the MV leg and recomputes the new root on the MU leg.
// Each level adds one sibling-table entry on MV and removes the matching entry on MU.
// Entries match by `(level, mrupdate_id, node_index, sibling_word)`, with direction-dependent
// sibling lanes.
//
// The matcher checks emitted messages independently of their lookup-column placement.

/// Checks that a depth-3 MRUPDATE emits three sibling-table adds and three matching removals.
#[rstest]
#[case(5_u64)]
#[case(4_u64)]
fn mrupdate_emits_sibling_add_and_remove_per_level(#[case] index: u64) {
    let (tree, _) = build_merkle_tree();
    let old_node = tree.get_node(NodeIndex::new(3, index).unwrap()).unwrap();
    let new_node = init_leaf(11);

    let mut init_stack = Vec::new();
    init_stack.extend_from_slice(&word_to_ints(old_node));
    init_stack.extend_from_slice(&[3, index]);
    init_stack.extend_from_slice(&word_to_ints(tree.root()));
    init_stack.extend_from_slice(&word_to_ints(new_node));
    let stack_inputs = stack_inputs_from_ints(init_stack);
    let store = MerkleStore::from(&tree);
    let advice_inputs = AdviceInputs::default().with_merkle_store(store);

    let ops = vec![Operation::MrUpdate];
    let trace = build_trace_from_ops_with_inputs(ops, stack_inputs, advice_inputs);
    let log = InteractionLog::new(&trace);
    let main = trace.main_trace();

    // The sibling-table gates are defined by `emit_siblings` in
    // `air/src/constraints/lookup/operations/merkle.rs`.
    let mut mv_rows: Vec<RowIndex> = Vec::new();
    let mut mu_rows: Vec<RowIndex> = Vec::new();
    for row in 0..main.chiplets_height() {
        let idx = RowIndex::from(row);
        if main.chiplet_selector_0(idx) != ONE {
            continue;
        }
        let hs0 = main.chiplet_selector_1(idx);
        let hs1 = main.chiplet_selector_2(idx);
        let hs2 = main.chiplet_selector_3(idx);
        if hs0 == ONE && hs1 == ONE && hs2 == ZERO {
            mv_rows.push(idx);
        } else if hs0 == ONE && hs1 == ONE && hs2 == ONE {
            mu_rows.push(idx);
        }
    }
    assert_eq!(mv_rows.len(), 3, "depth-3 MRUPDATE should emit 3 MV sibling adds");
    assert_eq!(mu_rows.len(), 3, "depth-3 MRUPDATE should emit 3 MU sibling removes");

    let mut exp = Expectations::new(&log);
    for &row in &mv_rows {
        push_sibling(&mut exp, row, main, SiblingSide::Add);
    }
    for &row in &mu_rows {
        push_sibling(&mut exp, row, main, SiblingSide::Remove);
    }

    log.assert_contains(&exp);
}

enum SiblingSide {
    Add,
    Remove,
}

fn push_sibling(exp: &mut Expectations<'_>, row: RowIndex, main: &MainTrace, side: SiblingSide) {
    let mrupdate_id = main.chiplet_mrupdate_id(row);
    let node_index = main.chiplet_node_index(row);
    let state = main.chiplet_hasher_state(row);
    let block_lo: [Felt; 4] = [state[0], state[1], state[2], state[3]];
    let block_hi: [Felt; 4] = [state[4], state[5], state[6], state[7]];

    // Direction bit drives which block half the sibling lives in.
    let bit = main.chiplet_merkle_direction_bit(row);
    let row_usize = usize::from(row);
    let (bit_tag, h) = if bit == ZERO {
        (SiblingBit::Zero, block_hi)
    } else {
        (SiblingBit::One, block_lo)
    };
    let level = main.chiplet_merkle_level(row);
    let msg = SiblingMsg {
        bit: bit_tag,
        level,
        mrupdate_id,
        node_index,
        h,
    };
    match side {
        SiblingSide::Add => exp.add(row_usize, &msg),
        SiblingSide::Remove => exp.remove(row_usize, &msg),
    };
}

fn build_merkle_tree() -> (MerkleTree, Vec<Word>) {
    let leaves = init_leaves(&[1, 2, 3, 4, 5, 6, 7, 8]);
    (MerkleTree::new(leaves.clone()).unwrap(), leaves)
}

// MERKLE TEST HELPERS
// ================================================================================================

fn init_leaves(values: &[u64]) -> Vec<Word> {
    values.iter().map(|&v| init_leaf(v)).collect()
}

fn init_leaf(value: u64) -> Word {
    [Felt::new_unchecked(value), ZERO, ZERO, ZERO].into()
}

fn word_to_ints(word: Word) -> [u64; 4] {
    [
        word[0].as_canonical_u64(),
        word[1].as_canonical_u64(),
        word[2].as_canonical_u64(),
        word[3].as_canonical_u64(),
    ]
}