ubt 0.4.1

//! Go-ethereum compatibility tests using their test vectors.
//!
//! These tests ensure our SHA256-based hashing and stem layout are
//! deterministic and structurally compatible with go-ethereum's
//! bintrie. Root hashes may differ due to tree structure differences.

#[cfg(test)]
mod tests {
    use crate::{Sha256Hasher, Stem, TreeKey, UnifiedBinaryTree, B256};

    fn hex_to_b256(s: &str) -> B256 {
        let s = s.strip_prefix("0x").unwrap_or(s);
        let bytes = hex::decode(s).expect("valid hex");
        B256::from_slice(&bytes)
    }

    // Test vectors from go-ethereum trie/bintrie/trie_test.go
    const ZERO_KEY: B256 = B256::ZERO;

    fn one_key() -> B256 {
        hex_to_b256("0101010101010101010101010101010101010101010101010101010101010101")
    }

    fn two_key() -> B256 {
        hex_to_b256("0202020202020202020202020202020202020202020202020202020202020202")
    }

    /// TestSingleEntry from go-ethereum
    /// Expected root: aab1060e04cb4f5dc6f697ae93156a95714debbf77d54238766adc5709282b6f
    #[test]
    fn test_single_entry_sha256() {
        let mut tree: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();

        // Insert key=0x00...00, value=0x0101...01
        tree.insert_b256(ZERO_KEY, one_key());

        let root = tree.root_hash().unwrap();
        let expected =
            hex_to_b256("aab1060e04cb4f5dc6f697ae93156a95714debbf77d54238766adc5709282b6f");

        // Verify tree has the value
        assert_eq!(tree.get_by_b256(&ZERO_KEY), Some(one_key()));

        // Root must match go-ethereum exactly
        assert_eq!(root, expected, "single entry root must match go-ethereum");
    }

    /// TestTwoEntriesDiffFirstBit from go-ethereum
    /// Expected root: dfc69c94013a8b3c65395625a719a87534a7cfd38719251ad8c8ea7fe79f065e
    #[test]
    fn test_two_entries_diff_first_bit_sha256() {
        let mut tree: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();

        // Insert two entries differing in first bit
        tree.insert_b256(ZERO_KEY, one_key());

        let key2 = hex_to_b256("8000000000000000000000000000000000000000000000000000000000000000");
        tree.insert_b256(key2, two_key());

        let root = tree.root_hash().unwrap();
        let expected =
            hex_to_b256("dfc69c94013a8b3c65395625a719a87534a7cfd38719251ad8c8ea7fe79f065e");

        assert_eq!(tree.len(), 2);
        assert_eq!(root, expected, "two entries root must match go-ethereum");
        assert_eq!(tree.get_by_b256(&ZERO_KEY), Some(one_key()));
        assert_eq!(tree.get_by_b256(&key2), Some(two_key()));
    }

    /// Test stem node hashing matches go-ethereum
    #[test]
    fn test_stem_node_hash_single_value() {
        use crate::{Sha256Hasher, StemNode};

        let hasher = Sha256Hasher;
        let stem = Stem::new([0u8; 31]);
        let mut node = StemNode::new(stem);

        // Insert value at subindex 0
        node.set_value(0, one_key());

        let hash = node.hash(&hasher);
        println!("Stem node hash (single value at idx 0): {}", hash);

        // The hash should be:
        // 1. hash(value) for leaf
        // 2. Build 8-level tree
        // 3. hash(stem || 0x00 || subtree_root)

        // Verify it's non-zero and deterministic
        assert_ne!(hash, B256::ZERO);
        assert_eq!(hash, node.hash(&hasher));
    }

    /// Test colocated values (same stem, different subindex)
    #[test]
    fn test_colocated_values_sha256() {
        let mut tree: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();

        // Keys with same stem (first 31 bytes) but different subindex
        let key1 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000003");
        let key2 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000004");

        tree.insert_b256(key1, one_key());
        tree.insert_b256(key2, two_key());

        // Both should be in same stem
        let tk1 = TreeKey::from_bytes(key1);
        let tk2 = TreeKey::from_bytes(key2);
        assert_eq!(tk1.stem, tk2.stem);

        // Tree should have 2 values but only 1 stem
        assert_eq!(tree.len(), 2);

        let root = tree.root_hash().unwrap();
        println!("Colocated values root: {}", root);
        assert_ne!(root, B256::ZERO);
    }

    /// Regression test for #70: one-sided subtrees must hash_64 against zero,
    /// not short-circuit by returning the non-empty child's hash directly.
    /// Two stems that both start with bit 0 produce a one-sided tree at depth 0.
    /// Expected root from go-ethereum: eb3937998684b2dbf1f87c9b48ff3dd0282ca3073d3f87611e06586b88297c91
    #[test]
    fn test_one_sided_subtree_hashes_against_zero() {
        let mut tree: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();

        // Both keys start with bit 0 → both go left at depth 0, right subtree is empty
        let key1 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000001");
        let key2 = hex_to_b256("0100000000000000000000000000000000000000000000000000000000000001");

        tree.insert_b256(
            key1,
            hex_to_b256("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"),
        );
        tree.insert_b256(
            key2,
            hex_to_b256("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"),
        );

        let root = tree.root_hash().unwrap();
        let expected =
            hex_to_b256("eb3937998684b2dbf1f87c9b48ff3dd0282ca3073d3f87611e06586b88297c91");
        assert_eq!(
            root, expected,
            "one-sided subtree root must match go-ethereum (issue #70)"
        );
    }

    /// Same test via StreamingTreeBuilder for #70 coverage.
    #[test]
    fn test_one_sided_subtree_streaming() {
        use crate::{StreamingTreeBuilder, TreeKey};

        let builder = StreamingTreeBuilder::<Sha256Hasher>::new();

        let key1 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000001");
        let key2 = hex_to_b256("0100000000000000000000000000000000000000000000000000000000000001");
        let val1 = hex_to_b256("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
        let val2 = hex_to_b256("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb");

        let entries = vec![
            (TreeKey::from_bytes(key1), val1),
            (TreeKey::from_bytes(key2), val2),
        ];
        let root = builder.build_root_hash(entries).unwrap();
        let expected =
            hex_to_b256("eb3937998684b2dbf1f87c9b48ff3dd0282ca3073d3f87611e06586b88297c91");
        assert_eq!(
            root, expected,
            "streaming one-sided subtree root must match go-ethereum (issue #70)"
        );
    }

    /// Test hash determinism with SHA256
    #[test]
    fn test_hash_determinism_sha256() {
        let mut tree1: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();
        let mut tree2: UnifiedBinaryTree<Sha256Hasher> = UnifiedBinaryTree::new();

        let key1 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000001");
        let key2 = hex_to_b256("8000000000000000000000000000000000000000000000000000000000000001");

        // Insert in different order
        tree1.insert_b256(key1, one_key());
        tree1.insert_b256(key2, two_key());

        tree2.insert_b256(key2, two_key());
        tree2.insert_b256(key1, one_key());

        assert_eq!(tree1.root_hash().unwrap(), tree2.root_hash().unwrap());
    }

    /// Test internal node hash
    #[test]
    fn test_internal_node_hash_sha256() {
        use crate::{Hasher, InternalNode, Node, Sha256Hasher, StemNode};

        let hasher = Sha256Hasher;

        // Create two stem nodes
        let mut stem1 = StemNode::new(Stem::new([0u8; 31]));
        stem1.set_value(0, one_key());

        let mut bytes2 = [0u8; 31];
        bytes2[0] = 0x80; // Different first bit
        let mut stem2 = StemNode::new(Stem::new(bytes2));
        stem2.set_value(0, two_key());

        // Create internal node
        let internal = InternalNode::new(Node::Stem(stem1.clone()), Node::Stem(stem2.clone()));

        let left_hash = stem1.hash(&hasher);
        let right_hash = stem2.hash(&hasher);
        let internal_hash = internal.hash(&hasher);

        // Internal hash should be hash(left || right)
        let expected = hasher.hash_64(&left_hash, &right_hash);
        assert_eq!(internal_hash, expected);

        println!("Left stem hash:  {}", left_hash);
        println!("Right stem hash: {}", right_hash);
        println!("Internal hash:   {}", internal_hash);
    }
}