ubt 0.4.0

//! Compatibility tests with go-ethereum bintrie implementation.
//!
//! These tests reuse go-ethereum's trie/bintrie test vectors to ensure our
//! stem layout and lookup behavior are compatible. Because we use BLAKE3
//! instead of go-ethereum's hash, root hashes will differ.

#[cfg(test)]
mod tests {
    use crate::{Blake3Hasher, 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")
    }

    fn three_key() -> B256 {
        hex_to_b256("0303030303030303030303030303030303030303030303030303030303030303")
    }

    fn four_key() -> B256 {
        hex_to_b256("0404040404040404040404040404040404040404040404040404040404040404")
    }

    fn ff_key() -> B256 {
        hex_to_b256("ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff")
    }

    /// TestSingleEntry: Insert one entry and verify root hash
    /// go-ethereum expected: aab1060e04cb4f5dc6f697ae93156a95714debbf77d54238766adc5709282b6f
    #[test]
    fn test_single_entry() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        tree.insert_b256(ZERO_KEY, one_key());

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

        // Note: This test will fail if hash function differs from go-ethereum
        // go-ethereum uses a specific hash function; we use BLAKE3
        // The structure should be the same, but hashes will differ
        println!("Single entry root (BLAKE3): {}", root);
        println!("go-ethereum expected (their hash): {}", expected);

        // Verify tree structure is correct (single stem node)
        assert_eq!(tree.len(), 1);
        assert_eq!(tree.get_by_b256(&ZERO_KEY), Some(one_key()));
    }

    /// TestTwoEntriesDiffFirstBit: Two entries differing in first bit
    /// go-ethereum expected: dfc69c94013a8b3c65395625a719a87534a7cfd38719251ad8c8ea7fe79f065e
    #[test]
    fn test_two_entries_diff_first_bit() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        // First entry: key = 0x00...00
        tree.insert_b256(ZERO_KEY, one_key());

        // Second entry: key = 0x80...00 (differs in first bit)
        let key2 = hex_to_b256("8000000000000000000000000000000000000000000000000000000000000000");
        tree.insert_b256(key2, two_key());

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

        println!("Two entries (diff first bit) root (BLAKE3): {}", root);
        println!("go-ethereum expected: {}", expected);

        assert_eq!(tree.len(), 2);
        assert_eq!(tree.get_by_b256(&ZERO_KEY), Some(one_key()));
        assert_eq!(tree.get_by_b256(&key2), Some(two_key()));
    }

    /// TestOneStemColocatedValues: Multiple values in same stem (same first 31 bytes)
    #[test]
    fn test_one_stem_colocated_values() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        // All these keys share the same stem (first 31 bytes = 0x00...00)
        // but differ in subindex (last byte)
        let key1 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000003");
        let key2 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000004");
        let key3 = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000009");
        let key4 = hex_to_b256("00000000000000000000000000000000000000000000000000000000000000FF");

        tree.insert_b256(key1, one_key());
        tree.insert_b256(key2, two_key());
        tree.insert_b256(key3, three_key());
        tree.insert_b256(key4, four_key());

        // All 4 values should be in the same stem
        let tk1 = TreeKey::from_bytes(key1);
        let tk2 = TreeKey::from_bytes(key2);
        let tk3 = TreeKey::from_bytes(key3);
        let tk4 = TreeKey::from_bytes(key4);

        assert_eq!(tk1.stem, tk2.stem);
        assert_eq!(tk2.stem, tk3.stem);
        assert_eq!(tk3.stem, tk4.stem);

        // Subindexes should be different
        assert_eq!(tk1.subindex, 0x03);
        assert_eq!(tk2.subindex, 0x04);
        assert_eq!(tk3.subindex, 0x09);
        assert_eq!(tk4.subindex, 0xFF);

        assert_eq!(tree.len(), 4);
    }

    /// TestTwoStemColocatedValues: Values colocated in two different stems
    #[test]
    fn test_two_stem_colocated_values() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        // Stem 1: 0x00...00
        let key1a = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000003");
        let key1b = hex_to_b256("0000000000000000000000000000000000000000000000000000000000000004");

        // Stem 2: 0x80...00 (differs in first bit)
        let key2a = hex_to_b256("8000000000000000000000000000000000000000000000000000000000000003");
        let key2b = hex_to_b256("8000000000000000000000000000000000000000000000000000000000000004");

        tree.insert_b256(key1a, one_key());
        tree.insert_b256(key1b, two_key());
        tree.insert_b256(key2a, one_key());
        tree.insert_b256(key2b, two_key());

        // Verify stem grouping
        let tk1a = TreeKey::from_bytes(key1a);
        let tk1b = TreeKey::from_bytes(key1b);
        let tk2a = TreeKey::from_bytes(key2a);
        let tk2b = TreeKey::from_bytes(key2b);

        assert_eq!(tk1a.stem, tk1b.stem); // Same stem
        assert_eq!(tk2a.stem, tk2b.stem); // Same stem
        assert_ne!(tk1a.stem, tk2a.stem); // Different stems

        assert_eq!(tree.len(), 4);
    }

    /// TestTwoKeysMatchFirst42Bits: Keys that share 42-bit prefix
    #[test]
    fn test_two_keys_match_first_42_bits() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        let key1 = hex_to_b256("0000000000C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0C0");
        let key2 = hex_to_b256("0000000000E00000000000000000000000000000000000000000000000000000");

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

        // These should be in different stems (differ after 42 bits)
        let tk1 = TreeKey::from_bytes(key1);
        let tk2 = TreeKey::from_bytes(key2);
        assert_ne!(tk1.stem, tk2.stem);

        assert_eq!(tree.len(), 2);
    }

    /// TestInsertDuplicateKey: Inserting same key twice updates value
    #[test]
    fn test_insert_duplicate_key() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

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

        // Value should be updated
        assert_eq!(tree.get_by_b256(&one_key()), Some(two_key()));
        assert_eq!(tree.len(), 1);
    }

    /// TestLargeNumberOfEntries: 256 entries with different first bytes
    #[test]
    fn test_large_number_of_entries() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        for i in 0..256u16 {
            let mut key = [0u8; 32];
            key[0] = i as u8;
            tree.insert_b256(B256::from(key), ff_key());
        }

        assert_eq!(tree.len(), 256);

        // Verify all entries retrievable
        for i in 0..256u16 {
            let mut key = [0u8; 32];
            key[0] = i as u8;
            assert_eq!(tree.get_by_b256(&B256::from(key)), Some(ff_key()));
        }
    }

    /// TestMerkleizeMultipleEntries: Multiple entries with known root hash
    /// go-ethereum expected: 9317155862f7a3867660ddd0966ff799a3d16aa4df1e70a7516eaa4a675191b5
    ///
    /// Note: go-ethereum uses value = i (little-endian u64), where i=0 gives zero value.
    /// Our implementation treats zero values as "empty" (optimizes them away).
    /// This test uses i+1 to avoid zero values while testing the same tree structure.
    #[test]
    fn test_merkleize_multiple_entries() {
        let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();

        let keys = [
            ZERO_KEY,
            hex_to_b256("8000000000000000000000000000000000000000000000000000000000000000"),
            hex_to_b256("0100000000000000000000000000000000000000000000000000000000000000"),
            hex_to_b256("8100000000000000000000000000000000000000000000000000000000000000"),
        ];

        // Use i+1 to avoid zero values (our impl treats zeros as empty)
        for (i, key) in keys.iter().enumerate() {
            let mut v = [0u8; 32];
            v[..8].copy_from_slice(&((i + 1) as u64).to_le_bytes());
            tree.insert_b256(*key, B256::from(v));
        }

        let root = tree.root_hash().unwrap();

        println!("Multiple entries root (BLAKE3): {}", root);
        println!("Note: go-ethereum uses different hash function, roots will differ");

        // Verify all entries are retrievable
        for (i, key) in keys.iter().enumerate() {
            let mut expected_v = [0u8; 32];
            expected_v[..8].copy_from_slice(&((i + 1) as u64).to_le_bytes());
            assert_eq!(
                tree.get_by_b256(key),
                Some(B256::from(expected_v)),
                "Failed to retrieve entry {} with key {}",
                i,
                key
            );
        }

        assert_eq!(tree.len(), 4);
    }

    /// Test that root hash is deterministic regardless of insertion order
    #[test]
    fn test_insertion_order_independence() {
        let keys = [
            ZERO_KEY,
            hex_to_b256("8000000000000000000000000000000000000000000000000000000000000000"),
            hex_to_b256("0100000000000000000000000000000000000000000000000000000000000000"),
            hex_to_b256("8100000000000000000000000000000000000000000000000000000000000000"),
        ];

        // Insert in forward order
        let mut tree1: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();
        for (i, key) in keys.iter().enumerate() {
            let mut v = [0u8; 32];
            v[..8].copy_from_slice(&(i as u64).to_le_bytes());
            tree1.insert_b256(*key, B256::from(v));
        }

        // Insert in reverse order
        let mut tree2: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();
        for (i, key) in keys.iter().enumerate().rev() {
            let mut v = [0u8; 32];
            v[..8].copy_from_slice(&(i as u64).to_le_bytes());
            tree2.insert_b256(*key, B256::from(v));
        }

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