libdictenstein 0.1.0

//! Disk-backed implementation of PersistentARTrieChar.
//!
//! This module provides disk persistence for the character-level trie,
//! supporting:
//! - Memory-mapped file storage
//! - Write-ahead logging (WAL) for crash recovery
//! - Buffer management for efficient I/O
//!
//! # Architecture
//!
//! The disk layout uses the char ART nodes (CharNode4/16/48/CharBucket)
//! for efficient storage of Unicode character keys.
//!
//! # File Layout
//!
//! ```text
//! ┌─────────────────────────────────────────────────┐
//! │ File Header (64 bytes)                          │
//! │ - Magic: "ARTC" (ART Char)                      │
//! │ - Version: u8                                   │
//! │ - Root pointer: u64                             │
//! │ - Entry count: u64                              │
//! │ - Checkpoint LSN: u64                           │
//! └─────────────────────────────────────────────────┘
//! │ Root Node (variable)                            │
//! └─────────────────────────────────────────────────┘
//! │ Child Nodes...                                  │
//! └─────────────────────────────────────────────────┘
//! ```

#[allow(unused_imports)]
use crate::persistent_artrie::wal::WalConfig;
#[allow(unused_imports)]
use std::sync::atomic::Ordering as AtomicOrdering;
use std::sync::Arc;

// Most imports moved to the relevant sub-modules in Phase-6 splits.
// `Arc` stays here for the `LockfreeInsertResult::Inserted` enum variant
// defined below. `AtomicOrdering` and `WalConfig` look unused at the
// file level but are pulled in by the test module via `use super::*`.

/// Magic bytes for char trie file
pub const CHAR_TRIE_MAGIC: [u8; 4] = *b"ARTC";

/// File header size in bytes
pub const CHAR_FILE_HEADER_SIZE: usize = 64;

/// Header format version 1 (original, no checksum)
pub const CHAR_HEADER_VERSION_V1: u8 = 1;

/// Header format version 2 (with checksum for crash recovery)
pub const CHAR_HEADER_VERSION_V2: u8 = 2;

/// Default buffer pool size (number of pages)
pub const DEFAULT_CHAR_BUFFER_POOL_SIZE: usize = 256;

// `EnhancedRecoveryMode` was relocated to `super::recovery_stats`; re-exported
// here under its original path.
pub use super::recovery_stats::EnhancedRecoveryMode;

/// Result of a lock-free CAS insert attempt.
///
/// Used internally by `insert_cas()` to communicate the outcome
/// of a single CAS attempt.
///
/// G1: generic over the overlay value type `V` (default `()`), so the
/// `Inserted` node matches the trie's `lockfree_root: AtomicNodePtr<V>`. A
/// membership trie (`V=()`) is unchanged; a counter trie (`V=u64`) carries the
/// `u64`-valued leaf back to the caller.
pub(super) enum LockfreeInsertResult<V = ()> {
    /// Successfully inserted a new term, returning the target leaf node AND a
    /// **published-root version** field.
    ///
    /// **G5.3' / S4 (FIX 1) — the `u64` field is SUPERSEDED + DROPPED by every
    /// durable caller.** It carries the published root's `version()` (a per-lifetime,
    /// per-attempt counter), but the durable insert/remove/increment recovery
    /// generation is the durable global `commit_seq` (restart-seeded; see
    /// [`OverlayCasWalk::claim_generation`](crate::persistent_artrie_core::overlay::cas_walk::OverlayCasWalk::claim_generation)),
    /// which `reconcile_lww` orders replay by. The `root.version()` is RESET on
    /// restart, so ranking with it re-opens the A.2 cross-restart resurrection bug —
    /// hence the durable skeleton DROPS this field (the char `try_insert_path_attempt`
    /// hook discards it at the `InsertAttempt` boundary) and ranks the
    /// caller-claimed `commit_seq`. The non-durable `insert_cas` ignores it entirely
    /// (it has no replay key). Retained ONLY for the (now caller-DROPPED) signature +
    /// the leaf the non-durable two-phase `try_set_final` arbiter needs.
    Inserted(
        Arc<super::nodes::persistent_node::PersistentCharNode<V>>,
        u64,
    ),
    /// Term already exists in the trie, carrying the **observed-root version**
    /// (FIX-A / D2.8): `version()` of the EXACT root in which the walk observed the
    /// term already-final (`current_root` at `try_insert_lockfree_path` entry), NOT a
    /// second `lockfree_root.load()`. This op took no root CAS (no position in the
    /// CAS order), so its commit generation is the causally-bounded observed-present
    /// version — provably `<` any strictly-later same-key remove's published version
    /// (the root chain is monotone and `r_obs ≺ r_remove`), so the idempotent record
    /// sorts BEFORE a later remove on replay (no resurrection), in the SAME
    /// `root.version` domain as the real arms. Closes RT-1's second-load leapfrog.
    AlreadyExists(u64),
    /// CAS failed due to concurrent modification (should retry)
    Conflict,
    /// WRITE-PATH FAULT-IN (design §4): a buffer-manager I/O error occurred while
    /// faulting an `OnDisk` prefix node back into memory during the path-copy. The
    /// term is NOT acknowledged; the durable image is intact (fault-in writes
    /// nothing). `insert_cas_durable` surfaces this as `Err(e)`; `insert_cas`
    /// treats it as a bounded-retry/`false`. **Flip F0:** un-gated — fault-in is
    /// now a production path, so this variant is always constructible.
    IoError(crate::persistent_artrie::error::PersistentARTrieError),
}

// Manual `Debug` so `V` need not be `Debug` (the `DictionaryValue` bound omits
// it). `V: Clone` so the node's own manual `Debug` (on `impl<V: Clone>`) applies.
impl<V: Clone> std::fmt::Debug for LockfreeInsertResult<V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            LockfreeInsertResult::Inserted(node, gen) => f
                .debug_tuple("LockfreeInsertResult::Inserted")
                .field(node)
                .field(gen)
                .finish(),
            LockfreeInsertResult::AlreadyExists(gen) => f
                .debug_tuple("LockfreeInsertResult::AlreadyExists")
                .field(gen)
                .finish(),
            LockfreeInsertResult::Conflict => f.write_str("LockfreeInsertResult::Conflict"),
            LockfreeInsertResult::IoError(e) => f
                .debug_tuple("LockfreeInsertResult::IoError")
                .field(e)
                .finish(),
        }
    }
}

// `EnhancedRecoveryStats` was relocated to `super::recovery_stats`;
// re-exported here under its original path.
pub use super::recovery_stats::EnhancedRecoveryStats;

// `CharTrieFileHeader` (struct + impls + Default + the private
// `crc32_header` helper it uses) was relocated to `super::file_header`;
// re-exported here under its original path.
pub use super::file_header::CharTrieFileHeader;

// `PrefixTermWithArena` and `PrefixTermWithValueAndArena` were relocated to
// `super::prefix_term`; re-exported here under their original paths.
pub use super::prefix_term::{PrefixTermWithArena, PrefixTermWithValueAndArena};

/// Transaction state for document transactions.
///
/// Re-exported from `persistent_artrie` for API consistency.
pub use crate::persistent_artrie::TransactionState;

/// Durability policy for WAL synchronization.
///
/// Re-exported from `persistent_artrie` for API consistency.
pub use crate::persistent_artrie::DurabilityPolicy;

// `CharDocumentTransaction` was relocated to `super::transactions`;
// re-exported here under its original path.
pub use super::transactions::CharDocumentTransaction;

// Note: Debug implementation is in mod.rs on PersistentARTrieChar directly

// =============================================================================
// MmapDiskManager-specific constructors moved to super::mmap_ctor.
// IoUringDiskManager-specific constructors moved to super::io_uring_ctor.
// =============================================================================

// =============================================================================
// All instance methods moved to sibling sub-modules in Phase-6:
//
// - mutation_core: insert_impl_no_wal, insert_impl_no_wal_with_value,
//                  remove_impl_no_wal (the _no_wal core primitives)
// - mutation_api:  insert, insert_with_value, remove (WAL-logged wrappers)
// - query_api:     contains/try_contains, get/try_get, optimistic variants,
//                  epoch + retry observability
// - prefix_helpers: navigate_to_prefix, collect_terms_*
// - prefix_api:    iter_prefix*, remove_prefix*
// - disk_io:       load_root_from_disk + child resolution helpers
// - persist:       checkpoint, persist_to_disk, serialize_char_node_to_disk
// - serialize variants live in serialization_char (pre-existing)
// - merge_api:     merge_from + batched variants
// - parallel_merge: rayon-based parallel merge (feature-gated)
// - document_tx:   begin/tx_insert/commit/abort
// - batch_insert:  insert_batch + 9 variants
// - lockfree_cas:  install_overlay/insert_cas/contains_lockfree/...
// - atomic_ops:    increment, upsert, compare_and_swap, fetch_add, get_or_insert
// - observability: sync, current_lsn, group commit + memory monitor + cache stats
// - epoch_checkpointing: enable/disable epoch-based auto checkpoint
// - prefetch_api:  prefetch_stats, prefetch_disk_refs_bounded
// - wal_helpers:   append_to_wal, sync_wal, *durability_policy
// - mmap_ctor / io_uring_ctor: storage-backend-specific constructors
// =============================================================================

/// Root descriptor type constants
pub(super) const ROOT_TYPE_EMPTY: u8 = 0;
pub(super) const ROOT_TYPE_NODE: u8 = 1;

// Note: Default implementation is in mod.rs on PersistentARTrieChar directly
// Note: SharedCharARTrie is now a type alias in mod.rs: `pub type SharedCharARTrie<V> = Arc<RwLock<PersistentARTrieChar<V>>>;`
// Note: SharedCharTrie is a deprecated alias for SharedCharARTrie

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::super::PersistentARTrieChar;

    use super::*;
    use crate::ARTrie;
    // F4: the `.read()/.write()` compat shim on the collapsed handle.
    use crate::persistent_artrie_core::shared_access::SharedTrieAccess;

    #[test]
    fn test_file_header_roundtrip() {
        let mut header = CharTrieFileHeader {
            magic: CHAR_TRIE_MAGIC,
            version: CHAR_HEADER_VERSION_V2,
            _reserved: [0; 3],
            root_ptr: 12345,
            entry_count: 67890,
            checkpoint_lsn: 111,
            header_checksum: 0,
            _padding: [0; 28],
        };
        header.finalize_checksum();

        let bytes = header.to_bytes();
        let restored = CharTrieFileHeader::from_bytes(&bytes);

        assert_eq!(restored.magic, CHAR_TRIE_MAGIC);
        assert_eq!(restored.version, CHAR_HEADER_VERSION_V2);
        assert_eq!(restored.root_ptr, 12345);
        assert_eq!(restored.entry_count, 67890);
        assert_eq!(restored.checkpoint_lsn, 111);
        assert!(restored.verify_checksum());
    }

    #[test]
    fn test_file_header_v1_roundtrip() {
        // V1 headers have no checksum
        let header = CharTrieFileHeader {
            magic: CHAR_TRIE_MAGIC,
            version: CHAR_HEADER_VERSION_V1,
            _reserved: [0; 3],
            root_ptr: 12345,
            entry_count: 67890,
            checkpoint_lsn: 111,
            header_checksum: 0,
            _padding: [0; 28],
        };

        let bytes = header.to_bytes();
        let restored = CharTrieFileHeader::from_bytes(&bytes);

        assert_eq!(restored.magic, CHAR_TRIE_MAGIC);
        assert_eq!(restored.version, CHAR_HEADER_VERSION_V1);
        assert_eq!(restored.root_ptr, 12345);
        assert!(!restored.has_checksum());
        assert!(restored.verify_checksum()); // V1 always valid
    }

    #[test]
    fn test_file_header_checksum() {
        let mut header = CharTrieFileHeader::new();
        header.root_ptr = 12345;
        header.entry_count = 67890;

        // Before finalize, checksum is 0
        assert_eq!(header.header_checksum, 0);
        assert!(!header.verify_checksum()); // Checksum doesn't match

        // After finalize, checksum is valid
        header.finalize_checksum();
        assert_ne!(header.header_checksum, 0);
        assert!(header.verify_checksum());

        // Modify a field and checksum becomes invalid
        header.root_ptr = 99999;
        assert!(!header.verify_checksum());

        // Finalize again to fix
        header.finalize_checksum();
        assert!(header.verify_checksum());
    }

    #[test]
    fn test_file_header_validation() {
        let mut header = CharTrieFileHeader::new();
        header.finalize_checksum();
        assert!(header.validate().is_ok());

        // Invalid magic
        header.magic = *b"XXXX";
        assert!(header.validate().is_err());

        // Restore magic, corrupt checksum
        header.magic = CHAR_TRIE_MAGIC;
        header.header_checksum = 0xDEADBEEF;
        assert!(header.validate().is_err());
    }

    #[test]
    fn test_file_header_from_bytes_verified() {
        let mut header = CharTrieFileHeader::new();
        header.root_ptr = 12345;
        header.finalize_checksum();

        let bytes = header.to_bytes();

        // Valid bytes should succeed
        let restored = CharTrieFileHeader::from_bytes_verified(&bytes);
        assert!(restored.is_ok());

        // Corrupt bytes should fail
        let mut corrupted = bytes;
        corrupted[8] = 0xFF; // Corrupt root_ptr
        let result = CharTrieFileHeader::from_bytes_verified(&corrupted);
        assert!(result.is_err());
    }

    #[test]
    fn test_file_header_upgrade_to_v2() {
        let mut header = CharTrieFileHeader::new_v1();
        assert!(!header.has_checksum());

        header.root_ptr = 12345;
        header.upgrade_to_v2();

        assert!(header.has_checksum());
        assert!(header.verify_checksum());
        assert_eq!(header.version, CHAR_HEADER_VERSION_V2);
    }

    #[test]
    fn test_inner_new() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();
        assert_eq!(inner.len.load(AtomicOrdering::Acquire), 0);
        assert!(!inner.dirty.load(AtomicOrdering::Acquire));
        // L3.3: the owned root field is gone; a fresh trie is empty via the overlay.
        assert_eq!(inner.len(), 0, "fresh trie is empty (overlay-backed)");
    }

    #[test]
    fn test_create_and_open() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test.trie");

        // Create a new trie
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("hello").expect("insert");
            inner.insert("world").expect("insert");
            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            // WAL replay should have reconstructed the state
            assert_eq!(inner.len(), 2);
        }
    }

    #[test]
    fn test_insert_and_contains() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // Insert some terms
        assert!(inner.insert("hello").expect("ins"));
        assert!(inner.insert("world").expect("ins"));
        assert!(inner.insert("hello world").expect("ins"));

        // Verify contains
        assert!(inner.contains("hello"));
        assert!(inner.contains("world"));
        assert!(inner.contains("hello world"));
        assert!(!inner.contains("hell"));
        assert!(!inner.contains("hello worl"));

        assert_eq!(inner.len(), 3);
    }

    #[test]
    fn test_insert_duplicate() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // First insert should succeed
        assert!(inner.insert("hello").expect("ins"));

        // Duplicate insert should fail
        assert!(!inner.insert("hello").expect("ins"));

        // Length should still be 1
        assert_eq!(inner.len(), 1);
    }

    #[test]
    fn test_remove() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // Insert some terms
        inner.insert("hello").expect("ins");
        inner.insert("world").expect("ins");
        assert_eq!(inner.len(), 2);

        // Remove one
        assert!(inner.remove("hello").expect("rm"));
        assert_eq!(inner.len(), 1);
        assert!(!inner.contains("hello"));
        assert!(inner.contains("world"));

        // Remove again should fail
        assert!(!inner.remove("hello").expect("rm"));

        // Remove the other
        assert!(inner.remove("world").expect("rm"));
        assert_eq!(inner.len(), 0);
    }

    #[test]
    fn test_unicode_support() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // Test various Unicode characters
        let terms = vec![
            "こんにちは", // Japanese
            "你好",       // Chinese
            "안녕하세요", // Korean
            "مرحبا",      // Arabic
            "שלום",       // Hebrew
            "🎉🎊🎋",     // Emoji
            "café",       // Latin with diacritics
            "naïve",      // Latin with diacritics
        ];

        for term in &terms {
            assert!(inner.insert(term).expect("ins"), "should insert: {}", term);
        }

        assert_eq!(inner.len(), terms.len());

        // Verify all are present
        for term in &terms {
            assert!(inner.contains(term), "should contain: {}", term);
        }

        // Verify partial terms are not present
        assert!(!inner.contains("こん"));
        assert!(!inner.contains("你"));
        assert!(!inner.contains("🎉"));
    }

    #[test]
    fn test_prefix_sharing() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // Terms that share prefixes
        inner.insert("a").expect("ins");
        inner.insert("ab").expect("ins");
        inner.insert("abc").expect("ins");
        inner.insert("abd").expect("ins");
        inner.insert("abcd").expect("ins");

        assert_eq!(inner.len(), 5);

        // All should be present
        assert!(inner.contains("a"));
        assert!(inner.contains("ab"));
        assert!(inner.contains("abc"));
        assert!(inner.contains("abd"));
        assert!(inner.contains("abcd"));

        // Partial paths should not be final
        assert!(!inner.contains("abce"));
    }

    #[test]
    fn test_empty_string() {
        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::new();

        // Empty string is valid
        assert!(inner.insert("").expect("ins"));
        assert!(inner.contains(""));
        assert_eq!(inner.len(), 1);

        // Add another term
        inner.insert("hello").expect("ins");
        assert_eq!(inner.len(), 2);
        assert!(inner.contains(""));
        assert!(inner.contains("hello"));
    }

    #[test]
    fn test_get_value() {
        let inner: PersistentARTrieChar<i32> = PersistentARTrieChar::new();

        inner.insert_with_value("one", 1).expect("ins");
        inner.insert_with_value("two", 2).expect("ins");
        inner.insert_with_value("three", 3).expect("ins");

        assert_eq!(inner.get("one"), Some(1));
        assert_eq!(inner.get("two"), Some(2));
        assert_eq!(inner.get("three"), Some(3));
        assert_eq!(inner.get("four"), None);
    }

    #[test]
    fn test_value_update() {
        let inner: PersistentARTrieChar<i32> = PersistentARTrieChar::new();

        // First insert
        assert!(inner.insert_with_value("key", 100).expect("ins"));
        assert_eq!(inner.get("key"), Some(100));

        // Update (insert returns false but value is updated)
        assert!(!inner.insert_with_value("key", 200).expect("ins"));
        assert_eq!(inner.get("key"), Some(200));

        // Length unchanged
        assert_eq!(inner.len(), 1);
    }

    #[test]
    fn test_wal_recovery_with_values() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_values.trie");

        // Create and insert with values
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("alpha").expect("insert");
            inner.insert("beta").expect("insert");
            inner.insert("gamma").expect("insert");
            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 3);
            assert!(inner.contains("alpha"));
            assert!(inner.contains("beta"));
            assert!(inner.contains("gamma"));
            assert!(!inner.contains("delta"));
        }
    }

    #[test]
    fn test_wal_recovery_mixed_operations() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_mixed.trie");

        // Create with mixed insert/remove
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("a").expect("insert");
            inner.insert("b").expect("insert");
            inner.insert("c").expect("insert");
            inner.remove("b").expect("remove");
            inner.insert("d").expect("insert");
            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 3);
            assert!(inner.contains("a"));
            assert!(!inner.contains("b"));
            assert!(inner.contains("c"));
            assert!(inner.contains("d"));
        }
    }

    #[test]
    fn test_checkpoint_and_disk_loading() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_checkpoint.trie");

        // Create, insert terms, and checkpoint
        let root_ptr_after_checkpoint;
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("apple").expect("insert");
            inner.insert("banana").expect("insert");
            inner.insert("cherry").expect("insert");
            assert_eq!(inner.len(), 3, "len after inserts");

            inner.checkpoint().expect("checkpoint");

            // Read root_ptr from disk to verify it was written
            let buffer_manager = inner.buffer_manager.as_ref().expect("buffer manager");
            let bm = buffer_manager.read();
            root_ptr_after_checkpoint = bm.disk_manager().root_ptr().expect("root_ptr");
        }

        // Verify root_ptr was written
        assert_ne!(
            root_ptr_after_checkpoint, 0,
            "root_ptr should be non-zero after checkpoint"
        );

        // Reopen and verify data was loaded from disk
        {
            // First check what root_ptr is stored in the file
            let dm = crate::persistent_artrie::disk_manager::DiskManager::open(&path)
                .expect("open disk manager");
            let stored_root_ptr = dm.root_ptr().expect("read root_ptr");

            // Also check entry count
            let stored_entry_count = dm.entry_count().expect("read entry_count");

            assert_ne!(
                stored_root_ptr, 0,
                "root_ptr on disk should be non-zero (was: {}, entry_count: {})",
                stored_root_ptr, stored_entry_count
            );

            drop(dm);

            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");

            assert_eq!(
                inner.len(),
                3,
                "len after reopen (root_ptr was {}, entry_count was {})",
                stored_root_ptr,
                stored_entry_count
            );
            assert!(inner.contains("apple"));
            assert!(inner.contains("banana"));
            assert!(inner.contains("cherry"));
            assert!(!inner.contains("date"));
        }
    }

    #[test]
    fn test_checkpoint_with_unicode() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_unicode_checkpoint.trie");

        // Create with Unicode terms and checkpoint
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("こんにちは").expect("insert");
            inner.insert("你好").expect("insert");
            inner.insert("🎉").expect("insert");
            inner.insert("café").expect("insert");
            inner.checkpoint().expect("checkpoint");
        }

        // Reopen and verify Unicode data
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 4);
            assert!(inner.contains("こんにちは"));
            assert!(inner.contains("你好"));
            assert!(inner.contains("🎉"));
            assert!(inner.contains("café"));
        }
    }

    #[test]
    fn test_checkpoint_then_more_inserts() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_post_checkpoint.trie");

        // Create, checkpoint, then add more
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("first").expect("insert");
            inner.insert("second").expect("insert");
            inner.checkpoint().expect("checkpoint");

            // Add more after checkpoint
            inner.insert("third").expect("insert");
            inner.insert("fourth").expect("insert");
            inner.sync().expect("sync");
        }

        // Reopen - should have all 4 (disk + WAL replay)
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 4);
            assert!(inner.contains("first"));
            assert!(inner.contains("second"));
            assert!(inner.contains("third"));
            assert!(inner.contains("fourth"));
        }
    }

    #[test]
    fn test_checkpoint_empty_trie() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_empty_checkpoint.trie");

        // Create empty trie and checkpoint
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.checkpoint().expect("checkpoint");
        }

        // Reopen empty trie
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 0);
            assert!(!inner.contains("anything"));
        }
    }

    #[test]
    fn test_multiple_checkpoints() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_multi_checkpoint.trie");

        // Create with multiple checkpoint cycles
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");

            inner.insert("one").expect("insert");
            inner.checkpoint().expect("checkpoint 1");

            inner.insert("two").expect("insert");
            inner.checkpoint().expect("checkpoint 2");

            inner.insert("three").expect("insert");
            inner.checkpoint().expect("checkpoint 3");
        }

        // Reopen and verify all data
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 3);
            assert!(inner.contains("one"));
            assert!(inner.contains("two"));
            assert!(inner.contains("three"));
        }
    }

    #[test]
    fn test_deep_trie_checkpoint() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_deep_checkpoint.trie");

        // Create with deeply nested terms
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            inner.insert("a").expect("insert");
            inner.insert("ab").expect("insert");
            inner.insert("abc").expect("insert");
            inner.insert("abcd").expect("insert");
            inner.insert("abcde").expect("insert");
            inner.insert("abcdef").expect("insert");
            inner.insert("abcdefg").expect("insert");
            inner.insert("abcdefgh").expect("insert");
            inner.checkpoint().expect("checkpoint");
        }

        // Reopen and verify all levels
        {
            let inner: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");
            assert_eq!(inner.len(), 8);
            assert!(inner.contains("a"));
            assert!(inner.contains("ab"));
            assert!(inner.contains("abc"));
            assert!(inner.contains("abcd"));
            assert!(inner.contains("abcde"));
            assert!(inner.contains("abcdef"));
            assert!(inner.contains("abcdefg"));
            assert!(inner.contains("abcdefgh"));
            assert!(!inner.contains("abcdefghi"));
        }
    }

    // ==================== Phase C6: Atomic Operations with WAL ====================

    #[test]
    fn test_increment_with_wal() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_increment.trie");

        // Create and increment
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            // First increment creates value
            let result = inner.increment("counter", 10).expect("increment");
            assert_eq!(result, 10);

            // Second increment adds to existing
            let result = inner.increment("counter", 5).expect("increment");
            assert_eq!(result, 15);

            // Negative increment
            let result = inner.increment("counter", -3).expect("increment");
            assert_eq!(result, 12);

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("counter"));
        }
    }

    #[test]
    fn test_upsert_with_wal() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_upsert.trie");

        // Create and upsert
        {
            let inner: PersistentARTrieChar<String> =
                PersistentARTrieChar::create(&path).expect("create");

            // First upsert inserts
            let inserted = inner.upsert("key", "value1".to_string()).expect("upsert");
            assert!(inserted);
            assert!(inner.contains("key"));

            // Second upsert updates
            let inserted = inner.upsert("key", "value2".to_string()).expect("upsert");
            assert!(!inserted);
            assert!(inner.contains("key"));

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<String> =
                PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("key"));
            assert_eq!(inner.len(), 1);
        }
    }

    #[test]
    fn test_compare_and_swap_with_wal() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_cas.trie");

        // Create and CAS
        {
            let mut inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            // CAS on non-existent key (expected None) should succeed
            let success = inner.compare_and_swap("key", None, 100).expect("cas");
            assert!(success);
            assert!(inner.contains("key"));

            // CAS with wrong expected value should fail
            let success = inner.compare_and_swap("key", Some(50), 200).expect("cas");
            assert!(!success);

            // CAS with correct expected value should succeed
            let success = inner.compare_and_swap("key", Some(100), 200).expect("cas");
            assert!(success);

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<i32> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("key"));
        }
    }

    #[test]
    fn test_fetch_add_with_wal() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_fetch_add.trie");

        // Create and fetch_add
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            // First fetch_add on non-existent key returns 0
            let old = inner.fetch_add("counter", 10).expect("fetch_add");
            assert_eq!(old, 0);

            // Second fetch_add returns previous value
            let old = inner.fetch_add("counter", 5).expect("fetch_add");
            assert_eq!(old, 10);

            // Third fetch_add
            let old = inner.fetch_add("counter", -3).expect("fetch_add");
            assert_eq!(old, 15);

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("counter"));
        }
    }

    #[test]
    fn test_get_or_insert_with_wal() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_get_or_insert.trie");

        // Create and get_or_insert
        {
            let inner: PersistentARTrieChar<String> =
                PersistentARTrieChar::create(&path).expect("create");

            // First get_or_insert inserts
            let value = inner
                .get_or_insert("key", "default".to_string())
                .expect("get_or_insert");
            assert_eq!(value, "default");
            assert!(inner.contains("key"));

            // Second get_or_insert returns existing (does not insert)
            let value = inner
                .get_or_insert("key", "other".to_string())
                .expect("get_or_insert");
            assert_eq!(value, "default"); // Still the original

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<String> =
                PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("key"));
            assert_eq!(inner.len(), 1);
        }
    }

    #[test]
    fn test_atomic_ops_recovery() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_atomic_recovery.trie");

        // Create with various atomic operations
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            // Use increment
            inner.increment("counter1", 100).expect("increment");
            inner.increment("counter1", 50).expect("increment");

            // Use fetch_add
            inner.fetch_add("counter2", 200).expect("fetch_add");
            inner.fetch_add("counter2", 25).expect("fetch_add");

            inner.sync().expect("sync");
        }

        // Reopen and verify recovery
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("counter1"));
            assert!(inner.contains("counter2"));
            assert_eq!(inner.len(), 2);
        }
    }

    #[test]
    fn test_atomic_ops_with_checkpoint() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_atomic_checkpoint.trie");

        // Create, checkpoint, then more atomic ops
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            inner.increment("before_cp", 100).expect("increment");
            inner.checkpoint().expect("checkpoint");

            inner.increment("after_cp", 200).expect("increment");
            inner.sync().expect("sync");
        }

        // Reopen - should have both (disk + WAL replay)
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("before_cp"));
            assert!(inner.contains("after_cp"));
            assert_eq!(inner.len(), 2);
        }
    }

    #[test]
    fn test_unicode_atomic_ops() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_unicode_atomic.trie");

        // Create with Unicode keys
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            inner.increment("カウンター", 10).expect("increment");
            inner.increment("计数器", 20).expect("increment");
            inner.increment("🔢", 30).expect("increment");

            inner.sync().expect("sync");
        }

        // Reopen and verify
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");
            assert!(inner.contains("カウンター"));
            assert!(inner.contains("计数器"));
            assert!(inner.contains("🔢"));
            assert_eq!(inner.len(), 3);
        }
    }

    // ==================== Phase C7: Concurrency Tests ====================

    #[test]
    fn test_optimistic_contains() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_optimistic_contains.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        inner.insert("hello").expect("insert");
        inner.insert("world").expect("insert");

        // Test optimistic reads
        let result = inner.contains_optimistic("hello", 10);
        assert_eq!(result, Some(true));

        let result = inner.contains_optimistic("world", 10);
        assert_eq!(result, Some(true));

        let result = inner.contains_optimistic("missing", 10);
        assert_eq!(result, Some(false));
    }

    #[test]
    fn test_optimistic_get() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_optimistic_get.trie");

        let mut inner: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path).expect("create");

        inner.increment("counter", 100).expect("increment");

        // Test optimistic get
        let result = inner.get_optimistic("counter", 10);
        assert!(result.is_some());
        let value = result.unwrap();
        assert_eq!(value, Some(100));

        let result = inner.get_optimistic("missing", 10);
        assert!(result.is_some());
        assert_eq!(result.unwrap(), None);
    }

    #[test]
    fn test_epoch_management() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Initial state
        assert_eq!(inner.current_epoch(), 0);
        assert_eq!(inner.active_readers(), 0);

        // Enter epoch
        {
            let _guard = inner.enter_epoch();
            assert_eq!(inner.active_readers(), 1);

            // Can have multiple readers
            {
                let _guard2 = inner.enter_epoch();
                assert_eq!(inner.active_readers(), 2);
            }

            // One reader left
            assert_eq!(inner.active_readers(), 1);
        }

        // No readers left
        assert_eq!(inner.active_readers(), 0);

        // Advance epoch
        let old = inner.advance_epoch();
        assert_eq!(old, 0);
        assert_eq!(inner.current_epoch(), 1);
    }

    #[test]
    fn test_retry_stats() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_stats.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        inner.insert("test").expect("insert");

        // Perform some optimistic reads
        for _ in 0..10 {
            let _ = inner.contains_optimistic("test", 5);
        }

        let stats = inner.retry_stats_snapshot();
        assert!(stats.successful >= 10); // At least 10 successful reads
                                         // Retry count should be low (no concurrent writers)
        assert_eq!(stats.retries, 0);
    }

    #[test]
    fn test_concurrent_readers() {
        use std::sync::Arc;
        use std::thread;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_concurrent.trie");

        // Create and populate
        {
            let inner: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");

            for i in 0..100 {
                inner.insert(&format!("term{}", i)).expect("insert");
            }
            inner.sync().expect("sync");
        }

        // Reopen and spawn multiple reader threads
        let inner = Arc::new(PersistentARTrieChar::<()>::open(&path).expect("open"));

        let handles: Vec<_> = (0..4)
            .map(|t| {
                let inner = inner.clone();
                thread::spawn(move || {
                    let mut found = 0;
                    for i in 0..100 {
                        let _guard = inner.enter_epoch();
                        if let Some(true) = inner.contains_optimistic(&format!("term{}", i), 10) {
                            found += 1;
                        }
                    }
                    (t, found)
                })
            })
            .collect();

        for handle in handles {
            let (thread_id, found) = handle.join().expect("thread join");
            assert_eq!(found, 100, "Thread {} should find all 100 terms", thread_id);
        }
    }

    #[test]
    fn test_try_contains_optimistic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_try_contains.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        inner.insert("apple").expect("insert");

        // Single optimistic read should succeed
        let result = inner.try_contains_optimistic("apple");
        assert_eq!(result, Some(true));

        let result = inner.try_contains_optimistic("banana");
        assert_eq!(result, Some(false));
    }

    #[test]
    fn test_unicode_optimistic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_unicode_optimistic.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        inner.insert("日本語").expect("insert");
        inner.insert("中文").expect("insert");
        inner.insert("🎉🎊🎋").expect("insert");

        // Test optimistic reads with Unicode
        assert_eq!(inner.contains_optimistic("日本語", 10), Some(true));
        assert_eq!(inner.contains_optimistic("中文", 10), Some(true));
        assert_eq!(inner.contains_optimistic("🎉🎊🎋", 10), Some(true));
        assert_eq!(inner.contains_optimistic("한글", 10), Some(false));
    }

    // ========================================================================
    // Document Transaction Tests
    // ========================================================================

    #[test]
    fn test_document_transaction_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_basic.trie");

        let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::create(&path).expect("create");

        // Start a transaction
        let mut tx = inner.begin_document("doc_001").expect("begin");
        assert!(tx.is_active());
        assert!(tx.is_empty());

        // Buffer some terms
        inner.tx_insert(&mut tx, "hello", Some(1));
        inner.tx_insert(&mut tx, "world", Some(2));
        inner.tx_insert(&mut tx, "foo", None);

        assert_eq!(tx.len(), 3);
        assert!(!tx.is_empty());

        // Terms should NOT be in trie yet
        assert!(!inner.contains("hello"));
        assert!(!inner.contains("world"));
        assert!(!inner.contains("foo"));

        // Commit the transaction
        let count = inner.commit_document(tx).expect("commit");
        assert_eq!(count, 3);

        // Now terms should be in trie
        assert!(inner.contains("hello"));
        assert!(inner.contains("world"));
        assert!(inner.contains("foo"));
        assert_eq!(inner.len(), 3);
    }

    #[test]
    fn test_document_transaction_abort() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_abort.trie");

        let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::create(&path).expect("create");

        // Insert a baseline term
        inner.insert("existing").expect("insert");

        // Start a transaction
        let mut tx = inner.begin_document("doc_002").expect("begin");
        inner.tx_insert(&mut tx, "new_term_1", Some(1));
        inner.tx_insert(&mut tx, "new_term_2", Some(2));

        // Abort the transaction
        inner.abort_document(tx).expect("abort");

        // New terms should NOT be in trie
        assert!(!inner.contains("new_term_1"));
        assert!(!inner.contains("new_term_2"));

        // Existing term should still be there
        assert!(inner.contains("existing"));
        assert_eq!(inner.len(), 1);
    }

    #[test]
    fn test_document_transaction_unicode() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_unicode.trie");

        let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::create(&path).expect("create");

        let mut tx = inner.begin_document("unicode_doc").expect("begin");

        // Test with Unicode strings
        inner.tx_insert(&mut tx, "日本語", Some(1));
        inner.tx_insert(&mut tx, "中文", Some(2));
        inner.tx_insert(&mut tx, "🎉🎊🎋", Some(3));

        // Test with char slice
        inner.tx_insert_chars(&mut tx, &['한', '글'], Some(4));
        inner.tx_insert_chars(&mut tx, &['π', '∑', '∫'], Some(5));

        let count = inner.commit_document(tx).expect("commit");
        assert_eq!(count, 5);

        // Verify all terms
        assert!(inner.contains("日本語"));
        assert!(inner.contains("中文"));
        assert!(inner.contains("🎉🎊🎋"));
        assert!(inner.contains("한글"));
        assert!(inner.contains("π∑∫"));
    }

    #[test]
    fn test_document_transaction_empty() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_empty.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Create and commit an empty transaction
        let tx = inner.begin_document("empty_doc").expect("begin");
        let count = inner.commit_document(tx).expect("commit");

        assert_eq!(count, 0);
        assert_eq!(inner.len(), 0);
    }

    #[test]
    fn test_document_transaction_recovery() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_recovery.trie");

        // Create and commit a transaction
        {
            let inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            let mut tx = inner.begin_document("recovery_doc").expect("begin");
            inner.tx_insert(&mut tx, "term1", Some(100));
            inner.tx_insert(&mut tx, "term2", Some(200));
            inner.tx_insert(&mut tx, "term3", Some(300));

            inner.commit_document(tx).expect("commit");
            inner.sync().expect("sync");
        }

        // Reopen and verify recovery
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");

            assert!(inner.contains("term1"));
            assert!(inner.contains("term2"));
            assert!(inner.contains("term3"));
            assert_eq!(inner.len(), 3);
        }
    }

    // Note: test_document_transaction_insert_after_commit is not needed because
    // Rust's ownership system already prevents reuse after commit_document() consumes tx.
    // The compiler prevents this error at compile time.

    #[test]
    fn test_document_transaction_commit_twice_error() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_commit_twice.trie");

        let inner: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // First transaction succeeds
        let mut tx = inner.begin_document("test").expect("begin");
        inner.tx_insert(&mut tx, "term", None);
        inner.commit_document(tx).expect("commit");

        // Second transaction also succeeds
        let tx2 = inner.begin_document("test2").expect("begin");
        inner.commit_document(tx2).expect("commit empty");
    }

    #[test]
    fn test_document_transaction_multiple_sequential() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_sequential.trie");

        let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::create(&path).expect("create");

        // First document
        let mut tx1 = inner.begin_document("doc1").expect("begin");
        inner.tx_insert(&mut tx1, "apple", Some(1));
        inner.tx_insert(&mut tx1, "apricot", Some(2));
        inner.commit_document(tx1).expect("commit");

        // Second document (aborted)
        let mut tx2 = inner.begin_document("doc2").expect("begin");
        inner.tx_insert(&mut tx2, "banana", Some(3));
        inner.abort_document(tx2).expect("abort");

        // Third document
        let mut tx3 = inner.begin_document("doc3").expect("begin");
        inner.tx_insert(&mut tx3, "cherry", Some(4));
        inner.tx_insert(&mut tx3, "coconut", Some(5));
        inner.commit_document(tx3).expect("commit");

        // Verify final state
        assert!(inner.contains("apple"));
        assert!(inner.contains("apricot"));
        assert!(!inner.contains("banana")); // Aborted
        assert!(inner.contains("cherry"));
        assert!(inner.contains("coconut"));
        assert_eq!(inner.len(), 4);
    }

    #[test]
    fn test_document_transaction_tx_insert_bytes() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_bytes.trie");

        let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::create(&path).expect("create");

        let mut tx = inner.begin_document("bytes_doc").expect("begin");

        // Test with raw bytes
        inner.tx_insert_bytes(&mut tx, b"hello", Some(1));
        inner.tx_insert_bytes(&mut tx, b"world", Some(2));
        inner.tx_insert_bytes(&mut tx, "日本語".as_bytes(), Some(3));

        let count = inner.commit_document(tx).expect("commit");
        assert_eq!(count, 3);

        assert!(inner.contains("hello"));
        assert!(inner.contains("world"));
        assert!(inner.contains("日本語"));
    }

    #[test]
    fn test_document_transaction_tx_increment() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_increment.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        // Insert some initial values
        inner.increment("term_a", 100).expect("initial increment");
        inner.increment("term_b", 50).expect("initial increment");

        // Create a transaction with increments
        let mut tx = inner.begin_document("increment_doc").expect("begin");

        // Buffer some increments
        inner.tx_increment(&mut tx, "term_a", 25); // Should add to existing 100
        inner.tx_increment(&mut tx, "term_b", 10); // Should add to existing 50
        inner.tx_increment(&mut tx, "term_c", 75); // New term
        inner.tx_increment(&mut tx, "term_a", 5); // Multiple increments to same term

        assert_eq!(tx.increment_count(), 4);
        assert_eq!(tx.set_count(), 0);
        assert_eq!(tx.len(), 4);

        // Values should NOT be updated yet
        assert_eq!(inner.get("term_a"), Some(100u64));
        assert_eq!(inner.get("term_b"), Some(50u64));
        assert!(inner.get("term_c").is_none());

        // Commit the transaction
        let count = inner.commit_document(tx).expect("commit");
        assert_eq!(count, 4);

        // Values should be updated now (increments aggregated)
        // term_a: 100 + 25 + 5 = 130
        assert_eq!(inner.get("term_a"), Some(130u64));
        // term_b: 50 + 10 = 60
        assert_eq!(inner.get("term_b"), Some(60u64));
        // term_c: 0 + 75 = 75
        assert_eq!(inner.get("term_c"), Some(75u64));
    }

    #[test]
    fn test_document_transaction_mixed_insert_and_increment() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_mixed.trie");

        let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::create(&path).expect("create");

        // Create a transaction with both inserts and increments
        let mut tx = inner.begin_document("mixed_doc").expect("begin");

        // Buffer inserts
        inner.tx_insert(&mut tx, "set_term", Some(100));

        // Buffer increments
        inner.tx_increment(&mut tx, "inc_term", 50);

        assert_eq!(tx.set_count(), 1);
        assert_eq!(tx.increment_count(), 1);
        assert_eq!(tx.len(), 2);

        // Commit
        let count = inner.commit_document(tx).expect("commit");
        assert_eq!(count, 2);

        // Verify results
        assert_eq!(inner.get("set_term"), Some(100u64));
        assert_eq!(inner.get("inc_term"), Some(50u64));
    }

    #[test]
    fn test_document_transaction_increment_recovery() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_doc_tx_inc_recovery.trie");

        // Phase 1: Create trie, add increments, close
        {
            let mut inner: PersistentARTrieChar<u64> =
                PersistentARTrieChar::create(&path).expect("create");

            inner.increment("existing", 100).expect("initial");

            let mut tx = inner.begin_document("recovery_doc").expect("begin");
            inner.tx_increment(&mut tx, "existing", 50);
            inner.tx_increment(&mut tx, "new_term", 75);
            inner.commit_document(tx).expect("commit");

            // Values should be correct before close
            assert_eq!(inner.get("existing"), Some(150u64));
            assert_eq!(inner.get("new_term"), Some(75u64));
        }

        // Phase 2: Reopen and verify recovery
        {
            let inner: PersistentARTrieChar<u64> = PersistentARTrieChar::open(&path).expect("open");

            // Values should survive recovery
            assert_eq!(inner.get("existing"), Some(150u64));
            assert_eq!(inner.get("new_term"), Some(75u64));
        }
    }

    // ========================================================================
    // Batch Insert Tests
    // ========================================================================

    #[test]
    fn test_insert_batch_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_basic.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries = vec![
            ("hello".to_string(), Some(1u64)),
            ("world".to_string(), Some(2u64)),
            ("foo".to_string(), None),
            ("bar".to_string(), Some(4u64)),
        ];

        let count = inner.insert_batch(&entries);
        assert_eq!(count, 4);
        assert_eq!(inner.len(), 4);

        assert!(inner.contains("hello"));
        assert!(inner.contains("world"));
        assert!(inner.contains("foo"));
        assert!(inner.contains("bar"));
    }

    #[test]
    fn test_insert_batch_unicode() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_unicode.trie");

        let mut inner: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries = vec![
            ("日本語".to_string(), Some(1)),
            ("中文".to_string(), Some(2)),
            ("한글".to_string(), Some(3)),
            ("🎉🎊🎋".to_string(), Some(4)),
        ];

        let count = inner.insert_batch(&entries);
        assert_eq!(count, 4);

        assert!(inner.contains("日本語"));
        assert!(inner.contains("中文"));
        assert!(inner.contains("한글"));
        assert!(inner.contains("🎉🎊🎋"));
    }

    #[test]
    fn test_insert_batch_chars() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_chars.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries: Vec<(&[char], Option<u64>)> = vec![
            (&['h', 'e', 'l', 'l', 'o'][..], Some(1)),
            (&['日', '本', '語'][..], Some(2)),
            (&['π', '∑', '∫'][..], None),
        ];

        let count = inner.insert_batch_chars(&entries);
        assert_eq!(count, 3);

        assert!(inner.contains("hello"));
        assert!(inner.contains("日本語"));
        assert!(inner.contains("π∑∫"));
    }

    #[test]
    fn test_insert_batch_sorted() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_sorted.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        // Entries in unsorted order
        let entries = vec![
            ("zebra".to_string(), Some(1u64)),
            ("apple".to_string(), Some(2u64)),
            ("mango".to_string(), Some(3u64)),
            ("apricot".to_string(), Some(4u64)),
        ];

        let count = inner.insert_batch_sorted(entries);
        assert_eq!(count, 4);

        assert!(inner.contains("apple"));
        assert!(inner.contains("apricot"));
        assert!(inner.contains("mango"));
        assert!(inner.contains("zebra"));
    }

    #[test]
    fn test_insert_batch_chars_sorted() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_chars_sorted.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries: Vec<(Vec<char>, Option<u64>)> = vec![
            (vec!['z', 'e', 'b', 'r', 'a'], Some(1)),
            (vec!['a', 'p', 'p', 'l', 'e'], Some(2)),
            (vec!['m', 'a', 'n', 'g', 'o'], Some(3)),
        ];

        let count = inner.insert_batch_chars_sorted(entries);
        assert_eq!(count, 3);

        assert!(inner.contains("apple"));
        assert!(inner.contains("mango"));
        assert!(inner.contains("zebra"));
    }

    #[test]
    fn test_insert_batch_bytes() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_bytes.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries: Vec<(&[u8], Option<u64>)> = vec![
            (b"hello" as &[u8], Some(1)),
            (b"world" as &[u8], Some(2)),
            ("日本語".as_bytes(), Some(3)),
        ];

        let count = inner.insert_batch_bytes(&entries);
        assert_eq!(count, 3);

        assert!(inner.contains("hello"));
        assert!(inner.contains("world"));
        assert!(inner.contains("日本語"));
    }

    #[test]
    fn test_insert_batch_bytes_sorted() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_bytes_sorted.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries: Vec<(Vec<u8>, Option<u64>)> = vec![
            (b"zebra".to_vec(), Some(1)),
            (b"apple".to_vec(), Some(2)),
            (b"mango".to_vec(), Some(3)),
        ];

        let count = inner.insert_batch_bytes_sorted(entries);
        assert_eq!(count, 3);

        assert!(inner.contains("apple"));
        assert!(inner.contains("mango"));
        assert!(inner.contains("zebra"));
    }

    #[test]
    fn test_insert_batch_empty() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_empty.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        let entries: Vec<(String, Option<u64>)> = vec![];

        let count = inner.insert_batch(&entries);
        assert_eq!(count, 0);
        assert_eq!(inner.len(), 0);
    }

    #[test]
    fn test_insert_batch_duplicates() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_duplicates.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        // Insert initial batch
        let entries1 = vec![
            ("apple".to_string(), Some(1u64)),
            ("banana".to_string(), Some(2u64)),
        ];
        let count1 = inner.insert_batch(&entries1);
        assert_eq!(count1, 2);

        // Insert with some duplicates
        let entries2 = vec![
            ("apple".to_string(), Some(10u64)),  // Duplicate - will update
            ("cherry".to_string(), Some(3u64)),  // New
            ("banana".to_string(), Some(20u64)), // Duplicate - will update
        ];
        let count2 = inner.insert_batch(&entries2);
        assert_eq!(count2, 1); // Only cherry is new

        assert_eq!(inner.len(), 3); // apple, banana, cherry
    }

    #[test]
    fn test_insert_batch_recovery() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_recovery.trie");

        // Create and batch insert
        {
            let mut inner: PersistentARTrieChar<i64> =
                PersistentARTrieChar::create(&path).expect("create");

            let entries = vec![
                ("term1".to_string(), Some(100i64)),
                ("term2".to_string(), Some(200i64)),
                ("term3".to_string(), Some(300i64)),
            ];
            inner.insert_batch(&entries);
            inner.sync().expect("sync");
        }

        // Reopen and verify recovery
        {
            let inner: PersistentARTrieChar<i64> = PersistentARTrieChar::open(&path).expect("open");

            assert!(inner.contains("term1"));
            assert!(inner.contains("term2"));
            assert!(inner.contains("term3"));
            assert_eq!(inner.len(), 3);
        }
    }

    #[test]
    fn test_insert_batch_large() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_batch_large.trie");

        let mut inner: PersistentARTrieChar<u64> =
            PersistentARTrieChar::create(&path).expect("create");

        // Create a large batch
        let entries: Vec<(String, Option<u64>)> = (0..1000)
            .map(|i| (format!("term_{:05}", i), Some(i as u64)))
            .collect();

        let count = inner.insert_batch(&entries);
        assert_eq!(count, 1000);
        assert_eq!(inner.len(), 1000);

        // Verify a few random entries
        assert!(inner.contains("term_00000"));
        assert!(inner.contains("term_00500"));
        assert!(inner.contains("term_00999"));
    }

    // ========================================================================
    // Batch/Parallel Merge Tests
    // ========================================================================

    #[test]
    fn test_merge_from_batched_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_batched_src.trie");
        let path2 = dir.path().join("test_merge_batched_dst.trie");

        // Create source trie
        let mut src: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path1).expect("create");
        src.increment("apple", 10).expect("increment");
        src.increment("banana", 20).expect("increment");
        src.increment("cherry", 30).expect("increment");

        // Create destination trie with overlapping terms
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");
        dst.increment("apple", 5).expect("increment");
        dst.increment("date", 40).expect("increment");

        // Merge with summing function
        let count = dst
            .merge_from_batched(&src, |a, b| a + b, 2)
            .expect("merge");
        assert_eq!(count, 3);

        // Verify results
        assert!(dst.contains("apple")); // Merged: 5 + 10 = 15
        assert!(dst.contains("banana")); // From src: 20
        assert!(dst.contains("cherry")); // From src: 30
        assert!(dst.contains("date")); // Original: 40
        assert_eq!(dst.len(), 4);
    }

    #[test]
    fn test_merge_from_batched_unicode() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_batched_unicode_src.trie");
        let path2 = dir.path().join("test_merge_batched_unicode_dst.trie");

        // Create source with Unicode terms
        let mut src: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path1).expect("create");
        src.increment("日本語", 1).expect("increment");
        src.increment("中文", 2).expect("increment");
        src.increment("한글", 3).expect("increment");

        // Create destination
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");
        dst.increment("日本語", 100).expect("increment");

        // Merge with summing function
        let count = dst
            .merge_from_batched(&src, |a, b| a + b, 10)
            .expect("merge");
        assert_eq!(count, 3);

        // Verify Unicode terms
        assert!(dst.contains("日本語"));
        assert!(dst.contains("中文"));
        assert!(dst.contains("한글"));
    }

    #[test]
    fn test_merge_from_batched_empty() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_batched_empty_src.trie");
        let path2 = dir.path().join("test_merge_batched_empty_dst.trie");

        // Create empty source
        let src: PersistentARTrieChar<i64> = PersistentARTrieChar::create(&path1).expect("create");

        // Create destination with some terms
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");
        dst.increment("existing", 100).expect("increment");

        // Merge from empty source
        let count = dst
            .merge_from_batched(&src, |a, b| a + b, 100)
            .expect("merge");
        assert_eq!(count, 0);
        assert_eq!(dst.len(), 1);
    }

    #[cfg(feature = "parallel-merge")]
    #[test]
    fn test_merge_from_parallel_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_parallel_src.trie");
        let path2 = dir.path().join("test_merge_parallel_dst.trie");

        // Create source with many terms
        let mut src: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path1).expect("create");
        for i in 0..100 {
            src.increment(&format!("term_{:03}", i), i as i64)
                .expect("increment");
        }

        // Create destination with some overlapping terms
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");
        for i in 0..50 {
            dst.increment(&format!("term_{:03}", i), 1000)
                .expect("increment");
        }

        // Parallel merge with summing function
        let count = dst.merge_from_parallel(&src, |a, b| a + b).expect("merge");
        assert_eq!(count, 100);

        // Verify all terms exist
        assert_eq!(dst.len(), 100);
        for i in 0..100 {
            assert!(dst.contains(&format!("term_{:03}", i)));
        }
    }

    #[cfg(feature = "parallel-merge")]
    #[test]
    fn test_merge_from_batched_parallel_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_batched_parallel_src.trie");
        let path2 = dir.path().join("test_merge_batched_parallel_dst.trie");

        // Create source
        let mut src: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path1).expect("create");
        for i in 0..50 {
            src.increment(&format!("key_{:02}", i), i as i64)
                .expect("increment");
        }

        // Create destination
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");
        dst.increment("key_00", 1000).expect("increment");

        // Batched parallel merge
        let count = dst
            .merge_from_batched_parallel(&src, |a, b| a + b, 10)
            .expect("merge");
        assert_eq!(count, 50);
        assert_eq!(dst.len(), 50);
    }

    #[cfg(feature = "parallel-merge")]
    #[test]
    fn test_merge_from_parallel_unicode() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path1 = dir.path().join("test_merge_parallel_unicode_src.trie");
        let path2 = dir.path().join("test_merge_parallel_unicode_dst.trie");

        // Create source with Unicode terms from different character ranges
        let mut src: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path1).expect("create");
        src.increment("日本語_001", 1).expect("increment");
        src.increment("日本語_002", 2).expect("increment");
        src.increment("中文_001", 3).expect("increment");
        src.increment("한글_001", 4).expect("increment");
        src.increment("🎉_emoji", 5).expect("increment");
        src.increment("ascii_test", 6).expect("increment");

        // Create empty destination
        let mut dst: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path2).expect("create");

        // Parallel merge
        let count = dst.merge_from_parallel(&src, |a, b| a + b).expect("merge");
        assert_eq!(count, 6);

        // Verify all Unicode terms
        assert!(dst.contains("日本語_001"));
        assert!(dst.contains("日本語_002"));
        assert!(dst.contains("中文_001"));
        assert!(dst.contains("한글_001"));
        assert!(dst.contains("🎉_emoji"));
        assert!(dst.contains("ascii_test"));
    }

    // ==================== Phase 4: Group Commit Tests ====================

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_enable_disable() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit.trie");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create");

        // Initially disabled
        assert!(!trie.is_group_commit_enabled());
        assert!(trie.group_commit_stats().is_none());

        // Enable group commit
        trie.enable_group_commit(GroupCommitConfig::default())
            .expect("enable group commit");
        assert!(trie.is_group_commit_enabled());
        assert!(trie.group_commit_stats().is_some());

        // Double enable should fail
        let result = trie.enable_group_commit(GroupCommitConfig::default());
        assert!(result.is_err());

        // Disable group commit
        trie.disable_group_commit().expect("disable group commit");
        assert!(!trie.is_group_commit_enabled());
        assert!(trie.group_commit_stats().is_none());

        // Double disable should be ok (idempotent)
        trie.disable_group_commit().expect("disable again");
    }

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_with_inserts() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit_inserts.trie");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create");

        // Enable group commit with low latency config for testing
        let config = GroupCommitConfig {
            max_batch_size: 10,
            max_batch_delay_us: 1_000, // 1ms
            dedicated_commit_thread: true,
            adaptive_batching: false,
            ..Default::default()
        };
        trie.enable_group_commit(config)
            .expect("enable group commit");

        // Perform inserts
        trie.insert("hello").expect("insert");
        trie.insert("world").expect("insert");
        trie.insert("foo").expect("insert");
        trie.insert("bar").expect("insert");
        trie.insert("baz").expect("insert");

        // Verify inserts
        assert!(trie.contains("hello"));
        assert!(trie.contains("world"));
        assert!(trie.contains("foo"));
        assert!(trie.contains("bar"));
        assert!(trie.contains("baz"));
        assert_eq!(trie.len(), 5);

        // Check stats - should have committed
        let stats = trie.group_commit_stats().expect("stats");
        assert!(stats.records_committed > 0, "should have committed records");

        // Disable and verify still works
        trie.disable_group_commit().expect("disable");
        trie.insert("after_disable").expect("insert");
        assert!(trie.contains("after_disable"));
    }

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_with_unicode() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit_unicode.trie");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create");

        trie.enable_group_commit(GroupCommitConfig::low_latency())
            .expect("enable group commit");

        // Insert Unicode terms
        trie.insert("こんにちは").expect("insert");
        trie.insert("你好").expect("insert");
        trie.insert("안녕하세요").expect("insert");
        trie.insert("🎉🎊🎋").expect("insert");

        // Verify
        assert!(trie.contains("こんにちは"));
        assert!(trie.contains("你好"));
        assert!(trie.contains("안녕하세요"));
        assert!(trie.contains("🎉🎊🎋"));
    }

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_high_throughput_config() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit_throughput.trie");

        let mut trie: PersistentARTrieChar<i64> =
            PersistentARTrieChar::create(&path).expect("create");

        // Use high throughput config
        trie.enable_group_commit(GroupCommitConfig::high_throughput())
            .expect("enable group commit");

        // Perform many inserts to test batching
        for i in 0..100 {
            trie.increment(&format!("counter_{}", i), 1)
                .expect("increment");
        }

        // Verify all inserted
        assert_eq!(trie.len(), 100);
        for i in 0..100 {
            assert!(trie.contains(&format!("counter_{}", i)));
        }

        // Check batching efficiency (should have batched multiple writes per fsync)
        let stats = trie.group_commit_stats().expect("stats");
        let efficiency = stats.batching_efficiency();
        println!(
            "High throughput batching efficiency: {:.2} records/fsync",
            efficiency
        );
        // With high throughput config, we expect some batching
        assert!(
            stats.records_committed >= 100,
            "should have committed at least 100 records"
        );
    }

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_recovery() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit_recovery.trie");

        // Create and insert with group commit
        {
            let mut trie: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");

            trie.enable_group_commit(GroupCommitConfig::default())
                .expect("enable group commit");

            trie.insert("persisted_1").expect("insert");
            trie.insert("persisted_2").expect("insert");
            trie.insert("persisted_3").expect("insert");

            // Sync to ensure all writes are flushed
            trie.sync().expect("sync");
        }

        // Reopen without group commit and verify recovery
        {
            let trie: PersistentARTrieChar<()> = PersistentARTrieChar::open(&path).expect("open");

            // Data should be recovered from WAL
            assert!(trie.contains("persisted_1"));
            assert!(trie.contains("persisted_2"));
            assert!(trie.contains("persisted_3"));
            assert_eq!(trie.len(), 3);
        }
    }

    #[cfg(feature = "group-commit")]
    #[test]
    fn test_group_commit_stats_tracking() {
        use crate::persistent_artrie::group_commit::GroupCommitConfig;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_group_commit_stats.trie");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create");

        trie.enable_group_commit(GroupCommitConfig::default())
            .expect("enable group commit");

        // Get initial stats
        let initial_stats = trie.group_commit_stats().expect("stats");
        let initial_committed = initial_stats.records_committed;

        // Perform operations
        trie.insert("term1").expect("insert");
        trie.insert("term2").expect("insert");
        trie.remove("term1").expect("remove");

        // Wait briefly for async commits
        std::thread::sleep(std::time::Duration::from_millis(50));

        // Stats should have increased
        let final_stats = trie.group_commit_stats().expect("stats");
        assert!(
            final_stats.records_committed > initial_committed,
            "records_committed should have increased: {} -> {}",
            initial_committed,
            final_stats.records_committed
        );
    }

    // ==================== Performance Infrastructure Tests ====================

    #[test]
    fn test_cache_stats_basic() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_cache_stats.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Initially no accesses
        let (hits, misses) = trie.cache_counts();
        assert_eq!(hits, 0);
        assert_eq!(misses, 0);
        assert_eq!(trie.cache_total_accesses(), 0);
        assert_eq!(trie.cache_hit_rate(), 1.0); // No accesses = 100% hit rate

        // Record some hits
        trie.record_cache_hit();
        trie.record_cache_hit();
        trie.record_cache_hit();

        // Record some misses
        trie.record_cache_miss();

        // Check counts
        let (hits, misses) = trie.cache_counts();
        assert_eq!(hits, 3);
        assert_eq!(misses, 1);
        assert_eq!(trie.cache_total_accesses(), 4);

        // Hit rate should be 75%
        let hit_rate = trie.cache_hit_rate();
        assert!(
            (hit_rate - 0.75).abs() < 0.001,
            "Hit rate should be 0.75, got {}",
            hit_rate
        );
    }

    #[test]
    fn test_cache_stats_and_reset() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_cache_reset.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Record some activity
        trie.record_cache_hit();
        trie.record_cache_hit();
        trie.record_cache_miss();

        // Get and reset
        let (hit_rate, hits, misses) = trie.cache_stats_and_reset();
        assert_eq!(hits, 2);
        assert_eq!(misses, 1);
        assert!(
            (hit_rate - 0.666).abs() < 0.01,
            "Hit rate should be ~0.666, got {}",
            hit_rate
        );

        // After reset, counts should be zero
        let (hits, misses) = trie.cache_counts();
        assert_eq!(hits, 0);
        assert_eq!(misses, 0);
    }

    #[test]
    fn test_memory_monitor_enable_disable() {
        use crate::persistent_artrie::memory_monitor::MemoryPressureConfig;
        use std::sync::atomic::{AtomicUsize, Ordering};
        use std::sync::Arc;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_memory_monitor.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Initially no monitor
        assert!(!trie.has_memory_monitor());
        assert!(trie.memory_stats().is_none());
        assert!(trie.memory_pressure_level().is_none());

        // Use a counter to track callback invocations
        let callback_count = Arc::new(AtomicUsize::new(0));
        let count_clone = Arc::clone(&callback_count);

        // Enable with callback
        let result =
            trie.enable_memory_monitor(MemoryPressureConfig::default(), move |_level, _stats| {
                count_clone.fetch_add(1, Ordering::Relaxed);
            });
        assert!(result.is_ok(), "enable_memory_monitor should succeed");

        // Now monitor is enabled
        assert!(trie.has_memory_monitor());

        // Stats should be available
        let stats = trie.memory_stats();
        assert!(stats.is_some(), "memory_stats should return Some");

        // Pressure level should be available
        let level = trie.memory_pressure_level();
        assert!(level.is_some(), "memory_pressure_level should return Some");

        // Disable
        trie.disable_memory_monitor();
        assert!(!trie.has_memory_monitor());
        assert!(trie.memory_stats().is_none());
    }

    #[test]
    fn test_memory_monitor_default() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_memory_default.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Enable with default config (no-op callback)
        let result = trie.enable_memory_monitor_default();
        assert!(
            result.is_ok(),
            "enable_memory_monitor_default should succeed"
        );
        assert!(trie.has_memory_monitor());

        // Stats should still be queryable
        let stats = trie.memory_stats().expect("stats should be available");
        assert!(stats.mem_total > 0, "System should have some memory");

        trie.disable_memory_monitor();
    }

    // ==================== Epoch Checkpointing Tests ====================

    #[test]
    fn test_epoch_checkpointing_enable_disable() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch_checkpointing.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Initially no checkpoint manager
        assert!(!trie.has_epoch_checkpointing());
        assert!(trie.current_epoch_id().is_none());
        assert!(trie.epoch_stats().is_none());

        // Enable with default config
        let result = trie.enable_epoch_checkpointing_default();
        assert!(
            result.is_ok(),
            "enable_epoch_checkpointing_default should succeed"
        );
        assert!(trie.has_epoch_checkpointing());

        // Now we should have epoch info
        let epoch_id = trie.current_epoch_id();
        assert!(epoch_id.is_some(), "current_epoch_id should be Some");

        let stats = trie.epoch_stats();
        assert!(stats.is_some(), "epoch_stats should be Some");

        // Disable
        trie.disable_epoch_checkpointing();
        assert!(!trie.has_epoch_checkpointing());
        assert!(trie.current_epoch_id().is_none());
    }

    #[test]
    fn test_epoch_checkpointing_record_operations() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch_record_ops.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Enable checkpoint manager
        trie.enable_epoch_checkpointing_default().expect("enable");

        // Get initial epoch
        let initial_epoch = trie.current_epoch_id().expect("epoch_id");

        // Record some operations
        for _ in 0..10 {
            let epoch = trie.record_epoch_operation(100);
            assert!(epoch.is_some());
        }

        // Epoch should still be the same (not enough ops to advance)
        let current_epoch = trie.current_epoch_id().expect("epoch_id");
        assert_eq!(
            initial_epoch, current_epoch,
            "Epoch should not have advanced yet"
        );

        // Current epoch metadata should show operations
        let metadata = trie.epoch_metadata().expect("metadata");
        let current_epoch_meta = metadata
            .iter()
            .find(|m| m.id == current_epoch)
            .expect("current epoch");
        assert_eq!(
            current_epoch_meta.operation_count, 10,
            "Should have recorded 10 operations"
        );
        assert_eq!(
            current_epoch_meta.wal_size_bytes, 1000,
            "Should have recorded 1000 WAL bytes"
        );
    }

    #[test]
    fn test_epoch_checkpointing_high_throughput_config() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch_high_throughput.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Enable with high-throughput config
        let result = trie.enable_epoch_checkpointing_high_throughput();
        assert!(
            result.is_ok(),
            "enable_epoch_checkpointing_high_throughput should succeed"
        );
        assert!(trie.has_epoch_checkpointing());

        // Config should reflect high-throughput settings
        let config = trie.epoch_config().expect("config");
        assert!(
            config.max_ops_per_epoch > 10_000,
            "High-throughput should have high ops limit"
        );
    }

    #[test]
    fn test_epoch_checkpointing_low_latency_config() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch_low_latency.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        // Enable with low-latency config
        let result = trie.enable_epoch_checkpointing_low_latency();
        assert!(
            result.is_ok(),
            "enable_epoch_checkpointing_low_latency should succeed"
        );
        assert!(trie.has_epoch_checkpointing());

        // Config should reflect low-latency settings
        let config = trie.epoch_config().expect("config");
        // Low latency has shorter epochs
        assert!(
            config.epoch_duration.as_millis() < 1000,
            "Low-latency should have short epoch duration"
        );
    }

    #[test]
    fn test_epoch_metadata() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("test_epoch_metadata.trie");

        let trie: PersistentARTrieChar<()> = PersistentARTrieChar::create(&path).expect("create");

        trie.enable_epoch_checkpointing_default().expect("enable");

        // Should have metadata for at least the current epoch
        let metadata = trie.epoch_metadata().expect("metadata");
        assert!(
            !metadata.is_empty(),
            "Should have at least one epoch's metadata"
        );

        // First epoch should be active
        let first = &metadata[0];
        assert_eq!(first.id, trie.current_epoch_id().expect("epoch_id"));
    }

    // === Enhanced Recovery Tests ===

    #[test]
    fn test_enhanced_recovery_mode_is_normal() {
        assert!(EnhancedRecoveryMode::Normal.is_normal());
        assert!(EnhancedRecoveryMode::CreatedNew.is_normal());
        assert!(!EnhancedRecoveryMode::RebuiltFromWal.is_normal());
        assert!(!EnhancedRecoveryMode::RebuiltFromArchives.is_normal());
    }

    #[test]
    fn test_enhanced_recovery_mode_required_rebuild() {
        assert!(!EnhancedRecoveryMode::Normal.required_rebuild());
        assert!(!EnhancedRecoveryMode::CreatedNew.required_rebuild());
        assert!(EnhancedRecoveryMode::RebuiltFromWal.required_rebuild());
        assert!(EnhancedRecoveryMode::RebuiltFromArchives.required_rebuild());
    }

    #[test]
    fn test_enhanced_recovery_stats_normal() {
        let stats = EnhancedRecoveryStats::normal();
        assert!(stats.mode.is_normal());
        assert_eq!(stats.records_replayed, 0);
        assert_eq!(stats.epochs_recovered, 0);
    }

    #[test]
    fn test_enhanced_recovery_stats_created_new() {
        let stats = EnhancedRecoveryStats::created_new();
        assert_eq!(stats.mode, EnhancedRecoveryMode::CreatedNew);
        assert!(stats.mode.is_normal());
    }

    #[test]
    fn test_open_with_full_recovery_creates_new() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("new_full_recovery.trie");

        let (trie, stats): (PersistentARTrieChar<i64>, _) =
            PersistentARTrieChar::open_with_full_recovery(
                &path,
                None, // No epoch config
                WalConfig::default(),
            )
            .expect("open_with_full_recovery");

        assert_eq!(stats.mode, EnhancedRecoveryMode::CreatedNew);
        assert_eq!(stats.records_replayed, 0);
        assert_eq!(trie.len(), 0); // Trie should be empty
    }

    #[test]
    fn test_open_with_full_recovery_normal_open() {
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let path = dir.path().join("existing_full_recovery.trie");

        // Create and populate trie first
        {
            let trie: PersistentARTrieChar<()> =
                PersistentARTrieChar::create(&path).expect("create");
            trie.insert("hello").expect("ins");
            trie.checkpoint().expect("checkpoint");
        }

        // Open with full recovery
        let (trie, stats): (PersistentARTrieChar<()>, _) =
            PersistentARTrieChar::open_with_full_recovery(&path, None, WalConfig::default())
                .expect("open_with_full_recovery");

        assert_eq!(stats.mode, EnhancedRecoveryMode::Normal);
        assert!(trie.contains("hello")); // contains returns bool directly
    }

    #[test]
    fn test_incremental_recovery_empty_wal() {
        use crate::persistent_artrie::recovery::IncrementalRecovery;
        use crate::persistent_artrie::wal::WalWriter;
        use tempfile::tempdir;

        let dir = tempdir().expect("create temp dir");
        let wal_path = dir.path().join("empty.wal");

        // Create empty WAL
        {
            let _wal = WalWriter::create(&wal_path).expect("create wal");
        }

        // Create incremental recovery
        let mut recovery: IncrementalRecovery =
            PersistentARTrieChar::<()>::incremental_recovery(&wal_path).expect("recovery");

        // Should return None for empty WAL
        let batch = recovery.next_batch(10).expect("next_batch");
        assert!(batch.is_none(), "Empty WAL should return no batches");
    }

    // ========================================================================
    // LSN API Tests
    // ========================================================================

    mod lsn_api_tests {
        use super::*;
        use tempfile::tempdir;

        #[test]
        fn test_current_lsn_starts_at_one_for_persistent() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            // Persistent tries start at LSN 1 (0 is reserved for "no LSN")
            assert_eq!(inner.current_lsn(), 1);
        }

        #[test]
        fn test_current_lsn_starts_at_one_for_in_memory() {
            // In-memory tries still start at LSN 1 for consistency
            let inner: PersistentARTrieChar<i32> = PersistentARTrieChar::new();
            assert_eq!(inner.current_lsn(), 1);
        }

        #[test]
        fn test_current_lsn_increases_after_insert() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            let before = inner.current_lsn();
            inner.upsert("key1", 42).expect("upsert");
            let after = inner.current_lsn();

            assert!(
                after > before,
                "LSN should increase after insert: before={}, after={}",
                before,
                after
            );
        }

        #[test]
        fn test_current_lsn_increases_after_remove() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            inner.upsert("key1", 42).expect("upsert");
            let before = inner.current_lsn();
            inner.remove("key1").expect("remove");
            let after = inner.current_lsn();

            assert!(
                after > before,
                "LSN should increase after remove: before={}, after={}",
                before,
                after
            );
        }

        #[test]
        fn test_synced_lsn_none_for_in_memory() {
            // In-memory tries have no WAL, so synced_lsn should be None
            let inner: PersistentARTrieChar<i32> = PersistentARTrieChar::new();
            assert!(
                inner.synced_lsn().is_none(),
                "In-memory trie should have no synced LSN"
            );
        }

        #[test]
        fn test_synced_lsn_after_sync() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            // Insert some data
            inner.upsert("key1", 42).expect("upsert");
            inner.upsert("key2", 43).expect("upsert");

            // The default Immediate durability policy syncs each acknowledged
            // mutation, so the WAL should already cover the last insert.
            let synced_before = inner
                .synced_lsn()
                .expect("persistent trie should have synced_lsn");
            assert_eq!(
                synced_before,
                inner.current_lsn().saturating_sub(1),
                "Immediate durability should sync through the last acknowledged write"
            );

            // Sync to disk
            inner.sync().expect("sync should succeed");

            // Explicit sync must not move the durable LSN backwards.
            let synced_after = inner
                .synced_lsn()
                .expect("persistent trie should have synced_lsn");
            assert!(
                synced_after >= synced_before,
                "synced_lsn should not go backwards after sync: before={}, after={}",
                synced_before,
                synced_after
            );
        }

        #[test]
        fn test_synced_lsn_invariant() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            // Insert and sync
            inner.upsert("key1", 42).expect("upsert");
            inner.sync().expect("sync should succeed");

            // Insert more data without syncing
            inner.upsert("key2", 43).expect("upsert");

            let current = inner.current_lsn();
            let synced = inner
                .synced_lsn()
                .expect("persistent trie should have synced_lsn");

            // Invariant: synced_lsn <= current_lsn - 1
            // (current_lsn is the NEXT lsn to be assigned, so the last written is current - 1)
            assert!(
                synced < current,
                "synced_lsn ({}) should be less than current_lsn ({})",
                synced,
                current
            );
        }

        #[test]
        fn test_lsn_monotonically_increasing() {
            let dir = tempdir().expect("create temp dir");
            let path = dir.path().join("lsn_test.trie");

            let inner: PersistentARTrieChar<i32> =
                PersistentARTrieChar::create(&path).expect("create");

            let mut prev_lsn = inner.current_lsn();

            // Perform multiple operations and verify LSN increases
            for i in 0..10 {
                inner.upsert(&format!("key{}", i), i).expect("upsert");
                let curr_lsn = inner.current_lsn();
                assert!(
                    curr_lsn > prev_lsn,
                    "LSN should increase monotonically: prev={}, curr={}",
                    prev_lsn,
                    curr_lsn
                );
                prev_lsn = curr_lsn;
            }
        }
    }

    #[test]
    fn test_shared_char_trie_current_lsn() {
        use crate::artrie_trait::ARTrie;
        let dir = tempfile::TempDir::new().expect("temp dir");
        let path = dir.path().join("test_shared_lsn.artc");
        let trie =
            std::sync::Arc::new(PersistentARTrieChar::<()>::create(&path).expect("create trie"));
        let lsn0 = trie.current_lsn();
        trie.write().insert("hello");
        let lsn1 = trie.current_lsn();
        assert!(lsn1 > lsn0, "current_lsn must advance after insert");
    }

    #[test]
    fn test_shared_char_trie_synced_lsn() {
        use crate::artrie_trait::ARTrie;
        let dir = tempfile::TempDir::new().expect("temp dir");
        let path = dir.path().join("test_shared_synced.artc");
        let trie =
            std::sync::Arc::new(PersistentARTrieChar::<()>::create(&path).expect("create trie"));
        let synced_before = trie.synced_lsn();
        trie.write().insert("hello");
        let current_after_insert = trie.current_lsn();
        // After an insert that hasn't been synced, current_lsn advances ahead of
        // synced_lsn (or synced is still None for an unsynced fresh trie).
        assert!(
            synced_before.map_or(true, |s| s < current_after_insert),
            "synced_lsn must lag current_lsn until sync() runs"
        );
        trie.sync().expect("sync");
        // After sync(), synced_lsn must be reported as Some(_): the trie has
        // flushed the WAL at least once, so the on-disk state has a well-defined
        // LSN. The exact value relative to current_lsn depends on sync
        // semantics — the WAL writer's synced_lsn is the last LSN that fsync
        // confirmed durable, which may lag current_lsn by one record (the
        // checkpoint marker that sync itself emits).
        assert!(
            trie.synced_lsn().is_some(),
            "synced_lsn must be Some(_) after sync()"
        );
    }

    #[test]
    fn test_shared_char_trie_upsert() {
        use crate::artrie_trait::ARTrie;
        let dir = tempfile::TempDir::new().expect("temp dir");
        let path = dir.path().join("test_shared_upsert.artc");
        let trie =
            std::sync::Arc::new(PersistentARTrieChar::<i64>::create(&path).expect("create trie"));
        assert!(
            trie.upsert("k", 1).expect("upsert"),
            "first upsert reports insert"
        );
        assert!(
            !trie.upsert("k", 2).expect("upsert"),
            "second upsert reports update"
        );
        // F2-migrate: Bucket A — `get()` returns None under the overlay (a fresh `i64`
        // trie create-flips); read the updated value via `get_value`.
        assert_eq!(trie.read().get_value("k"), Some(2), "value updated");
    }

    /// **F3 / NF-3 regression gate.** Two threads call `checkpoint()` concurrently on
    /// a shared overlay-routed trie (u64 auto-flips to the overlay), whose overlay-arm
    /// checkpoint holds only `self.read()`. Without the `checkpoint_lock` the two
    /// checkpoints can interleave their block-0 descriptor / arena writes → a torn
    /// on-disk image → terms lost/corrupt on reopen (the NF-3 data loss, formally
    /// modeled in `ConcurrentCheckpointSerialization.tla`). With the lock they
    /// serialize, so EVERY committed term survives the concurrent checkpoints + reopen.
    /// Real-disk scratch (`ln/`), not tmpfs — this exercises real checkpoint I/O.
    #[test]
    fn nf3_concurrent_checkpoints_lose_no_terms_on_reopen() {
        use crate::artrie_trait::ARTrie;
        std::fs::create_dir_all("ln").ok();
        let dir = tempfile::Builder::new()
            .prefix("nf3-concurrent-ckpt")
            .tempdir_in("ln")
            .expect("real-disk scratch under ln");
        let path = dir.path().join("t.artc");
        let n = 200usize;
        {
            let trie =
                std::sync::Arc::new(PersistentARTrieChar::<u64>::create(&path).expect("create"));
            assert!(
                trie.read().route_overlay(),
                "u64 trie auto-flips to the overlay (the overlay-arm checkpoint is the NF-3 race site)"
            );
            for i in 0..n {
                trie.insert_with_value(&format!("term{i:04}"), i as u64);
            }
            // Two threads checkpoint concurrently; checkpoint_lock must serialize them.
            let handles: Vec<_> = (0..2)
                .map(|_| {
                    let t = std::sync::Arc::clone(&trie);
                    std::thread::spawn(move || {
                        for _ in 0..15 {
                            t.checkpoint().expect("concurrent checkpoint");
                        }
                    })
                })
                .collect();
            for h in handles {
                h.join().expect("join");
            }
        }
        let reopened = PersistentARTrieChar::<u64>::open(&path).expect("reopen");
        for i in 0..n {
            assert_eq!(
                reopened.get_value(&format!("term{i:04}")),
                Some(i as u64),
                "term{i} lost/corrupt after two concurrent checkpoints + reopen (NF-3 — \
                 checkpoint_lock must serialize the descriptor writes)"
            );
        }
    }

    #[test]
    fn test_shared_char_trie_sync_persists() {
        use crate::artrie_trait::ARTrie;
        let dir = tempfile::TempDir::new().expect("temp dir");
        let path = dir.path().join("test_shared_sync.artc");
        let trie =
            std::sync::Arc::new(PersistentARTrieChar::<()>::create(&path).expect("create trie"));
        trie.write().insert("persistent");
        trie.sync().expect("sync");
        drop(trie);
        let reopened = PersistentARTrieChar::<()>::open(&path).expect("reopen");
        assert!(reopened.contains("persistent"));
    }

    // ==================== Lock-Free CAS Tests ====================

    #[test]
    fn test_insert_cas_basic() {
        let dir = tempfile::TempDir::new().expect("create temp dir");
        let path = dir.path().join("test_insert_cas.artc");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create trie");
        trie.install_overlay();

        // First insert should succeed
        assert!(trie.insert_cas("hello"));
        assert!(trie.insert_cas("world"));

        // Duplicate insert should return false
        assert!(!trie.insert_cas("hello"));
        assert!(!trie.insert_cas("world"));

        // Different terms should succeed
        assert!(trie.insert_cas("rust"));
        assert!(trie.insert_cas("cargo"));
    }

    #[test]
    fn test_insert_cas_empty_term_publishes_root() {
        let dir = tempfile::TempDir::new().expect("create temp dir");
        let path = dir.path().join("test_insert_cas_empty.artc");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create trie");
        trie.install_overlay();

        // Empty-string support (P3): "" is a first-class key on the overlay ROOT. The
        // first insert publishes the root final (returns true → newly inserted); it is
        // then a member and a second insert is a no-op (returns false). (Was: the old
        // behavior rejected "" with `!insert_cas("")`.)
        assert!(
            trie.insert_cas(""),
            "first insert_cas(\"\") publishes the root final"
        );
        assert!(trie.contains_lockfree(""), "\"\" is a member after insert");
        assert!(
            !trie.insert_cas(""),
            "second insert_cas(\"\") is a no-op (already present)"
        );
    }

    #[test]
    fn test_insert_cas_unicode() {
        let dir = tempfile::TempDir::new().expect("create temp dir");
        let path = dir.path().join("test_insert_cas_unicode.artc");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create trie");
        trie.install_overlay();

        // Unicode terms
        assert!(trie.insert_cas("日本語"));
        assert!(trie.insert_cas("中文"));
        assert!(trie.insert_cas("한국어"));
        assert!(trie.insert_cas("🦀"));

        // Duplicates
        assert!(!trie.insert_cas("日本語"));
        assert!(!trie.insert_cas("🦀"));
    }

    #[test]
    fn test_insert_cas_concurrent() {
        use std::sync::Arc;
        use std::thread;

        let dir = tempfile::TempDir::new().expect("create temp dir");
        let path = dir.path().join("test_insert_cas_concurrent.artc");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create trie");
        trie.install_overlay();

        let trie = Arc::new(trie);
        let num_threads = 4;
        let terms_per_thread = 25;

        // Test that concurrent access is safe (no panics/data races)
        let handles: Vec<_> = (0..num_threads)
            .map(|t| {
                let trie = Arc::clone(&trie);
                thread::spawn(move || {
                    let mut inserted = 0;
                    for i in 0..terms_per_thread {
                        let term = format!("term_{}_{}", t, i);
                        if trie.insert_cas(&term) {
                            inserted += 1;
                        }
                    }
                    inserted
                })
            })
            .collect();

        let total_inserted: usize = handles
            .into_iter()
            .map(|h| h.join().expect("thread join"))
            .sum();

        // Note: The current simplified implementation uses root-level CAS,
        // which has high contention. The important thing is that:
        // 1. No panics or data races occurred
        // 2. At least one term was inserted
        assert!(total_inserted >= 1, "At least one term should be inserted");

        let retries = trie.cas_retry_count();
        println!(
            "Inserted: {}/{}, CAS retries: {}",
            total_inserted,
            num_threads * terms_per_thread,
            retries
        );

        // The lock-free infrastructure is working - concurrent access is safe
        // Full per-level CAS traversal will be implemented in later phases
    }

    #[test]
    fn test_contains_lockfree() {
        let dir = tempfile::TempDir::new().expect("create temp dir");
        let path = dir.path().join("test_contains_lockfree.artc");

        let mut trie: PersistentARTrieChar<()> =
            PersistentARTrieChar::create(&path).expect("create trie");
        trie.install_overlay();

        // Insert some terms
        trie.insert_cas("apple");
        trie.insert_cas("banana");

        // Check contains
        assert!(trie.contains_lockfree("apple"));
        assert!(trie.contains_lockfree("banana"));
        assert!(!trie.contains_lockfree("cherry"));
    }
}