armdb 0.12.0

use std::marker::PhantomData;
use std::ops::Bound;
#[cfg(test)]
use std::sync::atomic::AtomicBool;
use std::sync::atomic::{AtomicU64, Ordering};

use crate::codec::Codec;
use crate::error::{DbError, DbResult};
use crate::hook::TypedWriteHook;
use crate::lsm::config::{LsmConfig, PersistPolicy};
use crate::lsm::iter::{LsmIter, LsmKeyIter, TryLsmIter, TryLsmKeyIter};
use crate::lsm::map_fjall;
use crate::map_index::dir_from;
use crate::sync::{self, Mutex};
use crate::{CollectionMeta, Dir, Key, NoHook};

/// A fjall-backed, codec-typed, ordered collection. Mirrors `VarTypedTree`.
///
/// Key-only iteration via [`crate::scope::Scope::keys`] uses [`fjall::Guard::key`]
/// so value bytes are not loaded on key-value-separated keyspaces; inline values
/// may still be read.
// Fields `db`, `reversed`, and `persist` are used by later tasks (iteration, flush, Db wiring).
#[allow(dead_code)]
pub struct LsmTree<K, T, C, H = NoHook>
where
    K: Key + Ord,
    T: CollectionMeta<SelfId = K> + Send + Sync,
    C: Codec<T> + Clone,
    H: TypedWriteHook<K, T>,
{
    db: fjall::Database,
    ks: fjall::Keyspace,
    codec: C,
    hook: H,
    config: LsmConfig,
    reversed: bool,
    persist: PersistPolicy,
    stripes: Vec<Mutex<()>>,
    count: AtomicU64,
    #[cfg(test)]
    force_next_key_guard_error: AtomicBool,
    _marker: PhantomData<fn() -> (K, T)>,
}

impl<K, T, C, H> LsmTree<K, T, C, H>
where
    K: Key + Ord,
    T: CollectionMeta<SelfId = K> + Send + Sync,
    C: Codec<T> + Clone,
    H: TypedWriteHook<K, T>,
{
    /// Open the collection's keyspace inside a shared `fjall::Database`.
    /// The keyspace is named `T::NAME`. Seeds the live counter from
    /// `keyspace.len()` (one-time O(n)).
    pub fn open(db: fjall::Database, config: LsmConfig, codec: C, hook: H) -> DbResult<Self> {
        Self::open_with_initial_count(db, config, codec, hook, None)
    }

    /// Open with an optional persisted entry count, avoiding the O(N) `ks.len()` scan.
    ///
    /// When `initial_count` is `Some(c)` the counter is seeded from the
    /// persisted value (exact after a clean close, approximate after an unclean
    /// shutdown — re-converges on the next clean close). When `None` the count
    /// is computed via `ks.len()` (one-time O(N) scan).
    pub(crate) fn open_with_initial_count(
        db: fjall::Database,
        config: LsmConfig,
        codec: C,
        hook: H,
        initial_count: Option<u64>,
    ) -> DbResult<Self> {
        if H::WATCHES {
            return Err(DbError::WatchUnsupported);
        }
        let memtable = config.memtable_size;
        let ks = map_fjall(db.keyspace(T::NAME, move || {
            fjall::KeyspaceCreateOptions::default().max_memtable_size(memtable)
        }))?;
        let count = match initial_count {
            // A seeded count is trusted, but it is cheap to catch the two states
            // that are *provably* wrong, and both are reachable: the saturating
            // `count_dec` floor biases the counter upward, and a crash after
            // durable writes but before the clean marker lands leaves a stale
            // seed. `is_empty()` is a boundary lookup (unlike the O(N) `len()`),
            // so this costs nothing on a collection sized beyond RAM.
            Some(c) => {
                let empty = map_fjall(ks.is_empty())?;
                if empty && c != 0 {
                    tracing::warn!(
                        collection = T::NAME,
                        seeded = c,
                        "persisted LSM count is non-zero over an empty keyspace — re-seeding to 0"
                    );
                    0
                } else if !empty && c == 0 {
                    // Zero over a non-empty keyspace is the sticky end state of
                    // the underflow floor: every later delete is suppressed and
                    // `close()` re-persists the 0. Pay the O(N) rescan once.
                    let actual = map_fjall(ks.len())? as u64;
                    tracing::warn!(
                        collection = T::NAME,
                        recovered = actual,
                        "persisted LSM count is 0 over a non-empty keyspace — rescanned"
                    );
                    actual
                } else {
                    c
                }
            }
            None => map_fjall(ks.len())? as u64,
        };
        let stripes = (0..config.lock_stripes.max(1))
            .map(|_| Mutex::new(()))
            .collect();
        Ok(Self {
            db,
            ks,
            codec,
            hook,
            reversed: config.reversed,
            persist: config.persist_or_default(),
            config,
            stripes,
            count: AtomicU64::new(count),
            #[cfg(test)]
            force_next_key_guard_error: AtomicBool::new(false),
            _marker: PhantomData,
        })
    }

    /// Open the collection's keyspace and override the persist policy.
    ///
    /// Used by `Db::open_lsm_tree` to propagate the shared `LsmDbConfig::persist`
    /// to each collection. `initial_count` is forwarded to
    /// [`open_with_initial_count`](Self::open_with_initial_count) to skip the
    /// O(N) `ks.len()` scan when a persisted count is available.
    pub(crate) fn open_with_persist(
        db: fjall::Database,
        config: LsmConfig,
        persist: PersistPolicy,
        codec: C,
        hook: H,
        initial_count: Option<u64>,
    ) -> DbResult<Self> {
        let mut t = Self::open_with_initial_count(db, config, codec, hook, initial_count)?;
        t.persist = persist;
        Ok(t)
    }

    // Used by later tasks (iteration, Db wiring, flush).
    #[allow(dead_code)]
    #[inline]
    pub(crate) fn keyspace(&self) -> &fjall::Keyspace {
        &self.ks
    }

    // Used by later tasks (iteration, Db wiring, flush).
    #[allow(dead_code)]
    #[inline]
    pub(crate) fn codec(&self) -> &C {
        &self.codec
    }

    // Used by Task 7 (flush integration with LsmDbConfig).
    #[allow(dead_code)]
    #[inline]
    pub(crate) fn persist_handle(&self) -> (&fjall::Database, PersistPolicy) {
        (&self.db, self.persist)
    }

    /// The per-collection config this tree was opened with.
    ///
    /// Note: the **effective** persist policy may differ from `config.persist` when
    /// the tree was opened via `Db::open_lsm_tree` — in that case the shared
    /// `LsmDbConfig::persist` overrides the per-collection value via
    /// `open_with_persist`. Use `persist_handle()` to read the live policy.
    #[inline]
    pub fn config(&self) -> &LsmConfig {
        &self.config
    }

    /// Stripe index a key routes to (for RMW/`atomic` locking).
    #[inline]
    pub fn shard_for(&self, key: &K) -> usize {
        (xxhash_rust::xxh3::xxh3_64(key.as_bytes()) as usize) % self.stripes.len()
    }

    #[inline]
    pub(crate) fn stripe_for(&self, key: &K) -> &Mutex<()> {
        &self.stripes[self.shard_for(key)]
    }

    /// Saturating decrement of the live-entry counter. The persisted seed is
    /// only approximate after an unclean shutdown, so it can under-count the
    /// true live rows; a plain `fetch_sub(1)` would then wrap to `~u64::MAX`,
    /// making `len()` report a full tree on an empty one. The CAS loop floors
    /// at 0 instead.
    fn count_dec(&self) {
        loop {
            let cur = self.count.load(Ordering::Relaxed);
            if cur == 0 {
                // Every suppressed decrement leaves a permanent +1 bias that a
                // clean `close()` then persists as an exact seed. Log it, or the
                // drift is silent forever (see the count self-heal follow-up).
                tracing::warn!(
                    collection = T::NAME,
                    "lsm count underflow suppressed — the seeded count under-counts live rows"
                );
                return;
            }
            if self
                .count
                .compare_exchange_weak(cur, cur - 1, Ordering::Relaxed, Ordering::Relaxed)
                .is_ok()
            {
                return;
            }
        }
    }

    #[inline]
    pub(crate) fn get_raw(&self, key: &K) -> DbResult<Option<fjall::Slice>> {
        map_fjall(self.ks.get(key.as_bytes()))
    }

    /// Return the decoded value for `key`, or `None` if missing or the value fails to decode.
    ///
    /// A fjall **I/O error also yields `None`** — this method cannot distinguish
    /// "absent" from "unreadable". Use [`try_get`](Self::try_get) on any path
    /// where that difference matters (it does wherever a false "absent" leads to
    /// an overwrite).
    pub fn get(&self, key: &K) -> Option<T> {
        let raw = self.ks.get(key.as_bytes()).ok()??;
        self.codec.decode_from(raw.as_ref()).ok()
    }

    /// Return `true` if `key` exists in the keyspace (ignores decode errors).
    ///
    /// A fjall I/O error is reported as `false` — use [`try_contains`](Self::try_contains)
    /// on any path where "absent" and "unreadable" must not be conflated.
    pub fn contains(&self, key: &K) -> bool {
        self.ks.contains_key(key.as_bytes()).unwrap_or(false)
    }

    /// Strict existence check: a fjall I/O error propagates instead of reading
    /// as "absent". Required wherever a false negative destroys data — e.g. an
    /// insert-if-absent that would overwrite the live row it failed to see.
    pub fn try_contains(&self, key: &K) -> DbResult<bool> {
        map_fjall(self.ks.contains_key(key.as_bytes()))
    }

    // ── Lock-free write primitives ──────────────────────────────────────────
    // Caller MUST hold the relevant stripe lock before calling these.
    // Used by the public `put`/`insert`/`delete` (which acquire the lock) and
    // by `LsmShard` (which reuses the already-held lock from `atomic`).

    pub(crate) fn put_locked(&self, key: &K, value: &T) -> DbResult<()> {
        self.put_locked_inner::<true>(key, value)
    }

    /// `HOOKS = false` skips `on_write` — used by `migrate`, whose rewrites are
    /// bookkeeping, not application writes. Firing the hook there would make a
    /// secondary index observe a full rewrite of the collection on every
    /// migration (and would diverge from the other families, which all migrate
    /// hook-free via `put_locked_inner::<false>`).
    pub(crate) fn put_locked_inner<const HOOKS: bool>(&self, key: &K, value: &T) -> DbResult<()> {
        let fire = HOOKS && H::NEEDS_WRITE;
        let mut buf = Vec::new();
        self.codec.encode_to(value, &mut buf)?;
        let prev = self.get_raw(key)?;
        // Decode the previous value BEFORE mutating. Propagating a decode
        // failure rather than collapsing it to `None` keeps an overwrite
        // distinguishable from an insert, so a secondary-index hook can remove
        // the stale entry — but the decode must fail *before* the write lands,
        // otherwise `Err` would mean "value already replaced, hook skipped",
        // leaving derived state more inconsistent than the bug being fixed.
        // Same ordering as `update`/`fetch_update`/`cas`: `Err` ⇒ no side effect.
        let old_t = if fire {
            prev.as_ref()
                .map(|b| self.codec.decode_from(b.as_ref()))
                .transpose()?
        } else {
            None
        };
        map_fjall(self.ks.insert(key.as_bytes(), buf.as_slice()))?;
        if prev.is_none() {
            self.count.fetch_add(1, Ordering::Relaxed);
        }
        if fire {
            self.hook.on_write(key, old_t.as_ref(), Some(value));
        }
        Ok(())
    }

    pub(crate) fn insert_locked(&self, key: &K, value: &T) -> DbResult<()> {
        if map_fjall(self.ks.contains_key(key.as_bytes()))? {
            return Err(DbError::KeyExists);
        }
        let mut buf = Vec::new();
        self.codec.encode_to(value, &mut buf)?;
        map_fjall(self.ks.insert(key.as_bytes(), buf.as_slice()))?;
        self.count.fetch_add(1, Ordering::Relaxed);
        if H::NEEDS_WRITE {
            self.hook.on_write(key, None, Some(value));
        }
        Ok(())
    }

    pub(crate) fn delete_locked(&self, key: &K) -> DbResult<bool> {
        self.delete_locked_inner::<true>(key)
    }

    /// `HOOKS = false` skips `on_write` — see [`put_locked_inner`](Self::put_locked_inner).
    pub(crate) fn delete_locked_inner<const HOOKS: bool>(&self, key: &K) -> DbResult<bool> {
        let fire = HOOKS && H::NEEDS_WRITE;
        let Some(prev) = self.get_raw(key)? else {
            return Ok(false);
        };
        // Decode BEFORE removing the row: the hook needs the real old value to
        // clean up derived state, so a corrupt previous row is an error rather
        // than a silent `old=None` — and that error must leave the row in place,
        // or the primary row would vanish while its index entries survive.
        let old_t = if fire {
            Some(self.codec.decode_from(prev.as_ref())?)
        } else {
            None
        };
        map_fjall(self.ks.remove(key.as_bytes()))?;
        self.count_dec();
        if fire {
            self.hook.on_write(key, old_t.as_ref(), None);
        }
        Ok(true)
    }

    // ── Public write ops (acquire lock, then delegate to lock-free helpers) ──

    /// Insert or overwrite `key` with `value`. Fires the write hook with the previous value.
    pub fn put(&self, key: &K, value: &T) -> DbResult<()> {
        let _g = sync::lock(self.stripe_for(key));
        self.put_locked(key, value)
    }

    /// Insert `key` only if it does not yet exist. Returns `DbError::KeyExists` otherwise.
    pub fn insert(&self, key: &K, value: &T) -> DbResult<()> {
        let _g = sync::lock(self.stripe_for(key));
        self.insert_locked(key, value)
    }

    /// Delete `key`. Returns `true` if the key existed, `false` if it was already absent.
    pub fn delete(&self, key: &K) -> DbResult<bool> {
        let _g = sync::lock(self.stripe_for(key));
        self.delete_locked(key)
    }

    /// Run a closure under the stripe lock for `shard_key`.
    ///
    /// All writes inside the closure are serialized against other writers that
    /// hash to the *same* stripe. Mutating a key that hashes to a *different*
    /// stripe is rejected with `DbError::ShardMismatch` — identical to
    /// `VarTypedTree::atomic`'s shard-scoped guarantee.
    ///
    /// **Concurrency contract**: `atomic` holds only the `shard_key`'s stripe
    /// lock, and the mutation methods on `LsmShard` (`put`/`insert`/`delete`)
    /// enforce that every key hashes to that same stripe; a foreign-stripe key
    /// returns `DbError::ShardMismatch` rather than racing concurrent writers
    /// on the other stripe. Stripe assignment hashes the *whole* key
    /// (`xxh3_64(key) % lock_stripes`, see [`shard_for`](Self::shard_for)) — there
    /// is no prefix-based routing. To co-locate keys mutated together in one
    /// `atomic` block, either set `lock_stripes: 1` (single stripe, so no
    /// `ShardMismatch` is possible) or ensure the keys share a stripe by
    /// construction.
    ///
    /// **Hook timing diverges from the Bitcask/FixedStore families**: mutations
    /// inside this closure fire `on_write` *synchronously, under the held stripe
    /// lock*, instead of buffering and replaying after release. A hook that
    /// re-enters this collection will deadlock. Tracked in libfunc/armour#119.
    pub fn atomic<R>(
        &self,
        shard_key: &K,
        f: impl FnOnce(&mut crate::lsm::shard::LsmShard<'_, K, T, C, H>) -> DbResult<R>,
    ) -> DbResult<R> {
        let _atomic_depth = crate::AtomicDepthGuard::try_enter()?;
        let stripe = self.shard_for(shard_key);
        let _g = sync::lock(&self.stripes[stripe]);
        let mut shard = crate::lsm::shard::LsmShard { tree: self, stripe };
        f(&mut shard)
    }

    /// Return the decoded value for `key`, or `DbError::KeyNotFound` if missing.
    pub fn get_or_err(&self, key: &K) -> DbResult<T> {
        let raw = self.get_raw(key)?.ok_or(DbError::KeyNotFound)?;
        self.codec.decode_from(raw.as_ref())
    }

    /// Return `Ok(Some(v))` if `key` exists, `Ok(None)` if absent, or an error on I/O or decode failure.
    pub fn try_get(&self, key: &K) -> DbResult<Option<T>> {
        match self.get_raw(key)? {
            Some(raw) => Ok(Some(self.codec.decode_from(raw.as_ref())?)),
            None => Ok(None),
        }
    }

    /// Return the raw encoded byte length for `key`, or `None` if absent.
    ///
    /// As with [`get`](Self::get), a fjall I/O error also yields `None`.
    pub fn entry_len(&self, key: &K) -> Option<u32> {
        let raw = self.ks.get(key.as_bytes()).ok()??;
        Some(raw.as_ref().len() as u32)
    }

    /// Read-modify-write: apply `f` to the current value and write the result. Returns the new value, or `None` if `key` is absent.
    pub fn update(&self, key: &K, f: impl FnOnce(&T) -> T) -> DbResult<Option<T>> {
        let _g = sync::lock(self.stripe_for(key));
        let Some(raw) = self.get_raw(key)? else {
            return Ok(None);
        };
        let old = self.codec.decode_from(raw.as_ref())?;
        let new = f(&old);
        let mut buf = Vec::new();
        self.codec.encode_to(&new, &mut buf)?;
        map_fjall(self.ks.insert(key.as_bytes(), buf.as_slice()))?;
        if H::NEEDS_WRITE {
            self.hook.on_write(key, Some(&old), Some(&new));
        }
        Ok(Some(new))
    }

    /// Read-modify-write: apply `f` to the current value, write the result, and return the **old** value. Returns `None` if `key` is absent.
    pub fn fetch_update(&self, key: &K, f: impl FnOnce(&T) -> T) -> DbResult<Option<T>> {
        let _g = sync::lock(self.stripe_for(key));
        let Some(raw) = self.get_raw(key)? else {
            return Ok(None);
        };
        let old = self.codec.decode_from(raw.as_ref())?;
        let new = f(&old);
        let mut buf = Vec::new();
        self.codec.encode_to(&new, &mut buf)?;
        map_fjall(self.ks.insert(key.as_bytes(), buf.as_slice()))?;
        if H::NEEDS_WRITE {
            self.hook.on_write(key, Some(&old), Some(&new));
        }
        Ok(Some(old))
    }

    /// Decide-and-write: insert, update, keep, or delete based on the closure's
    /// [`Upsert`](crate::Upsert) decision. The closure must be short — the stripe
    /// lock is held across it, so it must not panic and must not call back into
    /// this collection (the stripe lock is not reentrant).
    pub fn upsert<U: crate::IntoUpsert<T>>(
        &self,
        key: &K,
        f: impl FnOnce(Option<&T>) -> U,
    ) -> crate::DbResult<U::Out> {
        self.atomic(key, |s| crate::upsert::upsert_via_held(s, key, f))
    }

    /// Compare-and-swap: write `new_value` only if the stored value equals `expected`. Returns `DbError::CasMismatch` on mismatch or if the key is absent.
    pub fn cas(&self, key: &K, expected: &T, new_value: &T) -> DbResult<()>
    where
        T: PartialEq,
    {
        let _g = sync::lock(self.stripe_for(key));
        let raw = self.get_raw(key)?.ok_or(DbError::CasMismatch)?;
        let cur = self.codec.decode_from(raw.as_ref())?;
        if &cur != expected {
            return Err(DbError::CasMismatch);
        }
        let mut buf = Vec::new();
        self.codec.encode_to(new_value, &mut buf)?;
        map_fjall(self.ks.insert(key.as_bytes(), buf.as_slice()))?;
        if H::NEEDS_WRITE {
            self.hook.on_write(key, Some(&cur), Some(new_value));
        }
        Ok(())
    }

    /// Delete `key` only if the stored value equals `expected`. Returns `DbError::CasMismatch` on mismatch or if the key is absent.
    pub fn compare_delete(&self, key: &K, expected: &T) -> DbResult<()>
    where
        T: PartialEq,
    {
        let _g = sync::lock(self.stripe_for(key));
        let raw = self.get_raw(key)?.ok_or(DbError::CasMismatch)?;
        let cur = self.codec.decode_from(raw.as_ref())?;
        if &cur != expected {
            return Err(DbError::CasMismatch);
        }
        map_fjall(self.ks.remove(key.as_bytes()))?;
        self.count_dec();
        if H::NEEDS_WRITE {
            self.hook.on_write(key, Some(&cur), None);
        }
        Ok(())
    }

    /// Iterate all entries. Honors the `reversed` flag (default: descending key order).
    pub fn iter(&self) -> LsmIter<'_, K, T, C> {
        LsmIter::new(self.ks.iter(), self.reversed, &self.codec)
    }

    /// Iterate the half-open key range `[start, end)`. Honors the `reversed` flag.
    pub fn range(&self, start: &K, end: &K) -> LsmIter<'_, K, T, C> {
        let lo = start.as_bytes().to_vec();
        let hi = end.as_bytes().to_vec();
        LsmIter::new(self.ks.range(lo..hi), self.reversed, &self.codec)
    }

    /// Iterate a user-specified `Bound` range. Honors the `reversed` flag.
    pub fn range_bounds(&self, start: Bound<&K>, end: Bound<&K>) -> LsmIter<'_, K, T, C> {
        let map = |b: Bound<&K>| match b {
            Bound::Included(k) => Bound::Included(k.as_bytes().to_vec()),
            Bound::Excluded(k) => Bound::Excluded(k.as_bytes().to_vec()),
            Bound::Unbounded => Bound::Unbounded,
        };
        LsmIter::new(
            self.ks.range((map(start), map(end))),
            self.reversed,
            &self.codec,
        )
    }

    /// Range iterator with explicit direction override (ignores the tree's `reversed` flag).
    pub(crate) fn range_bounds_dir(
        &self,
        start: Bound<&K>,
        end: Bound<&K>,
        dir: Dir,
    ) -> LsmIter<'_, K, T, C> {
        let reversed = matches!(dir, Dir::Desc);
        let map = |b: Bound<&K>| match b {
            Bound::Included(k) => Bound::Included(k.as_bytes().to_vec()),
            Bound::Excluded(k) => Bound::Excluded(k.as_bytes().to_vec()),
            Bound::Unbounded => Bound::Unbounded,
        };
        LsmIter::new(self.ks.range((map(start), map(end))), reversed, &self.codec)
    }

    /// Key-only range iterator with explicit direction override.
    pub(crate) fn keys_range_bounds_dir(
        &self,
        start: Bound<&K>,
        end: Bound<&K>,
        dir: Dir,
    ) -> LsmKeyIter<K> {
        let reversed = matches!(dir, Dir::Desc);
        let map = |b: Bound<&K>| match b {
            Bound::Included(k) => Bound::Included(k.as_bytes().to_vec()),
            Bound::Excluded(k) => Bound::Excluded(k.as_bytes().to_vec()),
            Bound::Unbounded => Bound::Unbounded,
        };
        LsmKeyIter::new(self.ks.range((map(start), map(end))), reversed)
    }

    /// Strict key-only range iterator with an explicit direction override.
    pub(crate) fn try_keys_range_bounds_dir(
        &self,
        start: Bound<&K>,
        end: Bound<&K>,
        dir: Dir,
    ) -> TryLsmKeyIter<K> {
        let reversed = matches!(dir, Dir::Desc);
        let map = |b: Bound<&K>| match b {
            Bound::Included(k) => Bound::Included(k.as_bytes().to_vec()),
            Bound::Excluded(k) => Bound::Excluded(k.as_bytes().to_vec()),
            Bound::Unbounded => Bound::Unbounded,
        };
        let inner = self.ks.range((map(start), map(end)));
        #[cfg(test)]
        if self
            .force_next_key_guard_error
            .swap(false, Ordering::Relaxed)
        {
            return TryLsmKeyIter::new_with_forced_guard_error(inner, reversed);
        }
        TryLsmKeyIter::new(inner, reversed)
    }

    /// Field-granular prefix / range / page builder over this tree's key space.
    pub fn scope<const N: usize>(
        &self,
        key: &K,
    ) -> crate::scope::Scope<'_, crate::scope::TreeScan<&Self>, N> {
        crate::scope::tree_scope::<_, _, N>(self, key, dir_from(self.config().reversed))
    }

    /// Strict range iterator: surfaces storage/decode errors instead of skipping.
    pub(crate) fn try_range_bounds(
        &self,
        start: Bound<&K>,
        end: Bound<&K>,
    ) -> TryLsmIter<'_, K, T, C> {
        self.try_range_bounds_dir(start, end, dir_from(self.reversed))
    }

    /// Strict row range iterator with an explicit direction override.
    pub(crate) fn try_range_bounds_dir(
        &self,
        start: Bound<&K>,
        end: Bound<&K>,
        dir: Dir,
    ) -> TryLsmIter<'_, K, T, C> {
        let map = |b: Bound<&K>| match b {
            Bound::Included(k) => Bound::Included(k.as_bytes().to_vec()),
            Bound::Excluded(k) => Bound::Excluded(k.as_bytes().to_vec()),
            Bound::Unbounded => Bound::Unbounded,
        };
        TryLsmIter::new(
            self.ks.range((map(start), map(end))),
            matches!(dir, Dir::Desc),
            &self.codec,
        )
    }

    #[cfg(test)]
    pub(crate) fn force_next_key_guard_error_for_test(&self) {
        self.force_next_key_guard_error
            .store(true, Ordering::Relaxed);
    }

    /// Iterate all entries whose raw key begins with `prefix`. Honors the `reversed` flag.
    pub fn prefix_iter(&self, prefix: &[u8]) -> LsmIter<'_, K, T, C> {
        LsmIter::new(self.ks.prefix(prefix), self.reversed, &self.codec)
    }

    /// With `reversed=true` (default): the entry with the largest key.
    ///
    /// Lenient like [`Self::iter`]: a corrupt boundary row is skipped (logged)
    /// and the next valid entry is returned. Use [`Self::try_first`] to surface
    /// a decode error instead.
    pub fn first(&self) -> Option<(K, T)> {
        self.iter().next()
    }

    /// With `reversed=true` (default): the entry with the smallest key.
    ///
    /// Lenient like [`Self::iter`]: a corrupt boundary row is skipped (logged)
    /// and the next valid entry is returned. Use [`Self::try_last`] to surface
    /// a decode error instead.
    pub fn last(&self) -> Option<(K, T)> {
        self.iter().next_back()
    }

    /// Strict variant of `first`: a value decode error is returned, not skipped.
    pub fn try_first(&self) -> DbResult<Option<(K, T)>> {
        let g = if self.reversed {
            self.ks.last_key_value()
        } else {
            self.ks.first_key_value()
        };
        match g {
            Some(g) => {
                let (uk, uv) = crate::lsm::map_fjall(g.into_inner())?;
                Ok(Some((
                    K::from_bytes(uk.as_ref()),
                    self.codec.decode_from(uv.as_ref())?,
                )))
            }
            None => Ok(None),
        }
    }

    /// Strict variant of `last`.
    pub fn try_last(&self) -> DbResult<Option<(K, T)>> {
        let g = if self.reversed {
            self.ks.first_key_value()
        } else {
            self.ks.last_key_value()
        };
        match g {
            Some(g) => {
                let (uk, uv) = crate::lsm::map_fjall(g.into_inner())?;
                Ok(Some((
                    K::from_bytes(uk.as_ref()),
                    self.codec.decode_from(uv.as_ref())?,
                )))
            }
            None => Ok(None),
        }
    }

    /// Replay `on_init` for every live entry. Called by `Db` when no migration ran.
    pub(crate) fn replay_init(&self) {
        if H::NEEDS_INIT {
            for (k, v) in self.iter() {
                self.hook.on_init(&k, &v);
            }
        }
    }

    /// Alias of `flush` for VarTypedTree API parity.
    pub fn flush_buffers(&self) -> DbResult<()> {
        self.flush()
    }

    /// Alias of `periodic_flush` for VarTypedTree API parity.
    pub fn sync_hints(&self) -> DbResult<()> {
        self.periodic_flush()
    }

    /// Return the live entry count (approximate under concurrent mutation; exact after a clean open).
    ///
    /// The counter is maintained incrementally and seeded from `db.info` on a
    /// clean open, so it can drift — see [`recount`](Self::recount).
    pub fn len(&self) -> usize {
        self.count.load(Ordering::Relaxed) as usize
    }

    /// Return `true` if there are no live entries.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Re-derive the live-entry counter from the keyspace and return the new value.
    ///
    /// **O(N)** — a full key scan. The incremental counter is only re-checked
    /// against storage on open (and only for the two provably-wrong states), so
    /// a drift introduced mid-session persists until the next open. This is the
    /// operator escape hatch: call it when `len()` is suspect, or on a schedule
    /// if the collection tolerates the scan.
    ///
    /// Concurrent writers may mutate during the scan, so the result is a
    /// point-in-time estimate on a live collection — quiesce writes for an exact
    /// value. The count is persisted by the next `Db::close`/`clean_shutdown`.
    pub fn recount(&self) -> DbResult<u64> {
        let actual = map_fjall(self.ks.len())? as u64;
        let prev = self.count.swap(actual, Ordering::Relaxed);
        if prev != actual {
            tracing::info!(
                collection = T::NAME,
                previous = prev,
                recounted = actual,
                "LSM live-entry counter re-derived from the keyspace"
            );
        }
        Ok(actual)
    }

    /// Durable flush (fsync data + metadata). Called by `Db::close`; an immediate
    /// process exit afterwards will not lose committed writes.
    pub fn flush(&self) -> DbResult<()> {
        map_fjall(self.db.persist(fjall::PersistMode::SyncAll))
    }

    /// Full clean shutdown: a `SyncAll` persist (fsync of data + metadata).
    ///
    /// LSM has no separate hint files — `SyncAll` is both the "write hints" and
    /// "flush + fsync" step in one, so this is the maximally-durable counterpart
    /// of the Bitcask `clean_shutdown` (sync_hints + flush). Called by
    /// [`Db::clean_shutdown`](crate::armour::Db::clean_shutdown).
    pub fn clean_shutdown(&self) -> DbResult<()> {
        self.flush()
    }

    /// Lightweight periodic durability bound — uses the configured `PersistPolicy`.
    pub fn periodic_flush(&self) -> DbResult<()> {
        map_fjall(self.db.persist(self.persist.to_fjall()))
    }

    /// Trigger an LSM major compaction. LSM reclaim is not a single byte/row
    /// count, so this returns 0 (the `Collection` contract is a usize, unused here).
    pub fn compact(&self) -> DbResult<usize> {
        map_fjall(self.ks.major_compact())?;
        Ok(0)
    }

    /// Prime the OS/block cache with a full scan. Best-effort; no-op on error.
    pub fn warmup(&self) -> DbResult<()> {
        for _ in self.iter() {}
        Ok(())
    }

    /// Apply a migration across all rows. Returns the number of rows changed
    /// (updated or deleted). Mutations are serialized per stripe.
    ///
    /// Unlike the lenient [`iter`](Self::iter), this scans the raw keyspace and
    /// **propagates** a value decode error as `Err` rather than skipping the row.
    /// A migration must not report success while corrupt rows remain untouched
    /// on disk — the caller ([`run_migration`](crate::armour::Db) path) aborts
    /// and leaves the schema version un-bumped so the next open retries.
    ///
    /// fjall iterators are snapshot-isolated so mutating the keyspace during
    /// iteration is safe — no `collect()` needed.
    ///
    /// **Failure is not clean.** Rows are rewritten in place as the scan walks,
    /// so an `Err` mid-scan leaves the collection *partially* migrated with the
    /// version un-bumped; the next open re-runs the whole step, which is why
    /// migration callbacks must be idempotent (the standing `run_migration`
    /// contract). A single undecodable row therefore blocks
    /// [`Db::open_lsm_tree`](crate::armour::Db::open_lsm_tree) on **every**
    /// subsequent start until the row is repaired out-of-band — deliberate:
    /// silently carrying corrupt rows through a version bump is worse.
    ///
    /// Rows are visited in ascending key order regardless of the `reversed` flag.
    ///
    /// Rewrites are **hook-free** (`on_write` does not fire) — a migration is
    /// bookkeeping, not an application write. `on_init` fires for every live row
    /// so a `NEEDS_INIT` hook still sees the post-migration state.
    pub fn migrate(&self, f: impl Fn(&K, &T) -> crate::MigrateAction<T>) -> DbResult<usize> {
        self.migrate_inner(f, true)
    }

    /// `fire_init = false` suppresses `on_init` during the walk; `Db::open_lsm_tree`
    /// uses it because it calls [`replay_init`](Self::replay_init) unconditionally
    /// afterwards, which guarantees exactly one `on_init` per live key with the
    /// final value whether or not a migration ran (F1, PR #88 — the same wiring
    /// every other collection family uses).
    pub(crate) fn migrate_inner(
        &self,
        f: impl Fn(&K, &T) -> crate::MigrateAction<T>,
        fire_init: bool,
    ) -> DbResult<usize> {
        let init = fire_init && H::NEEDS_INIT;
        let mut changed = 0usize;
        for g in self.ks.iter() {
            let (uk, uv) = map_fjall(g.into_inner())?;
            // Guard the `unsafe { ptr::read }` inside `Key::from_bytes`, which is
            // only `debug_assert`-checked: a short key from an out-of-band write
            // would be an OOB read in release builds.
            if uk.len() != size_of::<K>() {
                return Err(DbError::CorruptedEntry { offset: 0 });
            }
            let key = K::from_bytes(uk.as_ref());
            let val = self.codec.decode_from(uv.as_ref())?;
            match f(&key, &val) {
                crate::MigrateAction::Keep => {
                    if init {
                        self.hook.on_init(&key, &val);
                    }
                }
                crate::MigrateAction::Update(new) => {
                    {
                        let _g = sync::lock(self.stripe_for(&key));
                        self.put_locked_inner::<false>(&key, &new)?;
                    }
                    if init {
                        // Init on the *new* value — a hook rebuilding an index
                        // must see the post-migration state.
                        self.hook.on_init(&key, &new);
                    }
                    changed += 1;
                }
                crate::MigrateAction::Delete => {
                    let _g = sync::lock(self.stripe_for(&key));
                    if self.delete_locked_inner::<false>(&key)? {
                        changed += 1;
                    }
                }
            }
        }
        Ok(changed)
    }
}

impl<K, T, C, H> crate::armour::Collection for LsmTree<K, T, C, H>
where
    K: Key + Ord + 'static,
    T: CollectionMeta<SelfId = K> + Send + Sync + 'static,
    C: Codec<T> + Clone + 'static,
    H: TypedWriteHook<K, T> + 'static,
{
    fn name(&self) -> &str {
        T::NAME
    }

    fn len(&self) -> usize {
        LsmTree::len(self)
    }

    fn compact(&self) -> DbResult<usize> {
        LsmTree::compact(self)
    }

    fn flush(&self) -> DbResult<()> {
        LsmTree::flush(self)
    }

    fn periodic_flush(&self) -> DbResult<()> {
        LsmTree::periodic_flush(self)
    }

    fn durable_flush(&self) -> DbResult<()> {
        LsmTree::flush(self)
    }

    fn clean_shutdown(&self) -> DbResult<()> {
        LsmTree::clean_shutdown(self)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{NoHook, RapiraCodec, WatchHook};
    use armour_core::{Fuid, GetRefs, GetType};
    use rapira::Rapira;

    armour_core::const_hasher_or!(doc_id, "DOC", "dev-key-doc", brand = "DOC");
    type DocId = Fuid<doc_id::Hasher>;

    #[derive(Clone, Debug, PartialEq, GetType, GetRefs, Rapira)]
    struct Doc {
        name: String,
    }
    impl crate::CollectionMeta for Doc {
        type SelfId = DocId;
        const NAME: &'static str = "docs";
    }

    fn k(n: u64) -> DocId {
        // deterministic key from raw bytes (big-endian → order-preserving)
        DocId::from_be_bytes(n.to_be_bytes())
    }

    fn temp_tree() -> (tempfile::TempDir, LsmTree<DocId, Doc, RapiraCodec, NoHook>) {
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let tree = LsmTree::open(db, LsmConfig::default(), RapiraCodec, NoHook).unwrap();
        (dir, tree)
    }

    /// Open with an explicit seeded count, bypassing `LsmTree::open`'s `None`.
    fn reopen_seeded(
        dir: &tempfile::TempDir,
        seed: Option<u64>,
    ) -> LsmTree<DocId, Doc, RapiraCodec, NoHook> {
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        LsmTree::open_with_initial_count(db, LsmConfig::default(), RapiraCodec, NoHook, seed)
            .unwrap()
    }

    #[test]
    fn lsm_watch_hook_is_refused_from_direct_and_managed_open() {
        let direct_dir = tempfile::tempdir().unwrap();
        let direct_db = fjall::Database::builder(direct_dir.path()).open().unwrap();
        let direct = LsmTree::<DocId, Doc, RapiraCodec, WatchHook<Doc, NoHook, true>>::open(
            direct_db,
            LsmConfig::default(),
            RapiraCodec,
            WatchHook::with_old(NoHook),
        );
        assert!(matches!(direct, Err(DbError::WatchUnsupported)));

        let managed_dir = tempfile::tempdir().unwrap();
        let managed_db = crate::armour::Db::open_test(managed_dir.path()).unwrap();
        let managed = managed_db.open_lsm_tree::<Doc, RapiraCodec, _>(
            None,
            LsmConfig::default(),
            WatchHook::with_old(NoHook),
            &[],
        );
        assert!(matches!(managed, Err(DbError::WatchUnsupported)));
        assert!(
            !managed_db.has_lsm_database_for_test(),
            "rejected watch must not open or record the managed fjall database"
        );
    }

    #[test]
    fn lsm_seeded_count_self_heals_the_two_provably_wrong_states() {
        // Sticky-drift end state: the saturating floor parks the counter at 0
        // while rows remain, `close()` persists that 0, and every clean reopen
        // re-trusts it. Opening must notice and rescan.
        let dir = tempfile::tempdir().unwrap();
        {
            let t = reopen_seeded(&dir, None);
            t.put(&k(1), &Doc { name: "a".into() }).unwrap();
            t.put(&k(2), &Doc { name: "b".into() }).unwrap();
            t.flush().unwrap();
        }
        let t = reopen_seeded(&dir, Some(0));
        assert_eq!(t.len(), 2, "count 0 over a non-empty keyspace must rescan");
        drop(t);

        // Mirror image: a stale non-zero seed over an emptied keyspace.
        let dir2 = tempfile::tempdir().unwrap();
        {
            let t = reopen_seeded(&dir2, None);
            t.flush().unwrap();
        }
        let t = reopen_seeded(&dir2, Some(7));
        assert_eq!(
            t.len(),
            0,
            "non-zero count over an empty keyspace must reset"
        );
    }

    #[test]
    fn lsm_recount_rederives_a_drifted_counter() {
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        t.put(&k(2), &Doc { name: "b".into() }).unwrap();
        // Simulate mid-session drift: the counter is incremental, so nothing
        // reconciles it against storage until the next open.
        t.count.store(99, Ordering::Relaxed);
        assert_eq!(t.len(), 99);
        assert_eq!(t.recount().unwrap(), 2);
        assert_eq!(t.len(), 2, "recount must publish the re-derived value");
    }

    fn names(it: impl Iterator<Item = (DocId, Doc)>) -> Vec<String> {
        it.map(|(_, d)| d.name).collect()
    }

    #[test]
    fn lsm_iter_reversed_default_is_desc() {
        let (_d, t) = temp_tree();
        for i in 1..=3u64 {
            t.put(
                &k(i),
                &Doc {
                    name: i.to_string(),
                },
            )
            .unwrap();
        }
        // reversed=true (default) ⇒ DESC by byte order of the big-endian key
        assert_eq!(names(t.iter()), vec!["3", "2", "1"]);
        assert_eq!(t.first().map(|(_, d)| d.name), Some("3".into()));
        assert_eq!(t.last().map(|(_, d)| d.name), Some("1".into()));
    }

    #[test]
    fn lsm_keys_use_guard_key() {
        let (_d, t_rev) = temp_tree();
        for i in 1..=3u64 {
            t_rev
                .put(
                    &k(i),
                    &Doc {
                        name: i.to_string(),
                    },
                )
                .unwrap();
        }
        // reversed=true (default) + Dir::Desc — same signal, key-only path
        let keys: Vec<_> = t_rev
            .keys_range_bounds_dir(Bound::Unbounded, Bound::Unbounded, Dir::Desc)
            .collect();
        assert_eq!(keys, vec![k(3), k(2), k(1)]);

        // Crossed: storage reversed=true, explicit Dir::Asc
        let keys_asc: Vec<_> = t_rev
            .keys_range_bounds_dir(Bound::Unbounded, Bound::Unbounded, Dir::Asc)
            .collect();
        assert_eq!(keys_asc, vec![k(1), k(2), k(3)]);

        // range_bounds_dir must override storage order too
        let names_asc: Vec<_> = t_rev
            .range_bounds_dir(Bound::Unbounded, Bound::Unbounded, Dir::Asc)
            .map(|(_, d)| d.name)
            .collect();
        assert_eq!(names_asc, vec!["1", "2", "3"]);

        // Crossed: storage reversed=false, explicit Dir::Desc
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let cfg = LsmConfig {
            reversed: false,
            ..LsmConfig::default()
        };
        let t_fwd: LsmTree<DocId, Doc, RapiraCodec, NoHook> =
            LsmTree::open(db, cfg, RapiraCodec, NoHook).unwrap();
        for i in 1..=3u64 {
            t_fwd
                .put(
                    &k(i),
                    &Doc {
                        name: i.to_string(),
                    },
                )
                .unwrap();
        }
        let keys_desc: Vec<_> = t_fwd
            .keys_range_bounds_dir(Bound::Unbounded, Bound::Unbounded, Dir::Desc)
            .collect();
        assert_eq!(keys_desc, vec![k(3), k(2), k(1)]);
    }

    #[test]
    fn lsm_iter_ascending_when_not_reversed() {
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let cfg = LsmConfig {
            reversed: false,
            ..LsmConfig::default()
        };
        let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> =
            LsmTree::open(db, cfg, RapiraCodec, NoHook).unwrap();
        for i in 1..=3u64 {
            t.put(
                &k(i),
                &Doc {
                    name: i.to_string(),
                },
            )
            .unwrap();
        }
        assert_eq!(names(t.iter()), vec!["1", "2", "3"]);
        assert_eq!(t.first().map(|(_, d)| d.name), Some("1".into()));
    }

    #[test]
    fn lsm_reversed_tunable_across_reopen() {
        let dir = tempfile::tempdir().unwrap();
        {
            let db = fjall::Database::builder(dir.path()).open().unwrap();
            let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> =
                LsmTree::open(db, LsmConfig::default(), RapiraCodec, NoHook).unwrap();
            for i in 1..=3u64 {
                t.put(
                    &k(i),
                    &Doc {
                        name: i.to_string(),
                    },
                )
                .unwrap();
            }
            // fjall persists on Database drop — no explicit flush needed
        }
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let cfg = LsmConfig {
            reversed: false,
            ..LsmConfig::default()
        };
        let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> =
            LsmTree::open(db, cfg, RapiraCodec, NoHook).unwrap();
        assert_eq!(names(t.iter()), vec!["1", "2", "3"]); // same data, ASC now
        assert_eq!(t.len(), 3); // counter re-seeded on reopen
    }

    #[test]
    fn lsm_put_get_roundtrip() {
        let (_d, t) = temp_tree();
        let doc = Doc { name: "a".into() };
        t.put(&k(1), &doc).unwrap();
        assert_eq!(t.get(&k(1)), Some(doc));
        assert!(t.get(&k(2)).is_none());
        assert!(t.contains(&k(1)));
    }

    #[test]
    fn lsm_insert_rejects_existing() {
        let (_d, t) = temp_tree();
        t.insert(&k(1), &Doc { name: "a".into() }).unwrap();
        assert!(matches!(
            t.insert(&k(1), &Doc { name: "b".into() }),
            Err(DbError::KeyExists)
        ));
    }

    #[test]
    fn lsm_delete_reports_existence_and_count() {
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        t.put(&k(2), &Doc { name: "b".into() }).unwrap();
        assert_eq!(t.len(), 2);
        assert!(t.delete(&k(1)).unwrap());
        assert!(!t.delete(&k(1)).unwrap()); // already gone
        assert_eq!(t.len(), 1);
        // overwrite must NOT change count
        t.put(&k(2), &Doc { name: "b2".into() }).unwrap();
        assert_eq!(t.len(), 1);
    }

    #[test]
    fn lsm_update_returns_new_value_and_fires_hook() {
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        let new = t
            .update(&k(1), |d| Doc {
                name: format!("{}!", d.name),
            })
            .unwrap();
        assert_eq!(new, Some(Doc { name: "a!".into() }));
        assert_eq!(t.get(&k(1)), Some(Doc { name: "a!".into() }));
        assert_eq!(t.update(&k(99), |d| d.clone()).unwrap(), None);
    }

    #[test]
    fn lsm_cas_and_compare_delete() {
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        assert!(matches!(
            t.cas(
                &k(1),
                &Doc {
                    name: "WRONG".into()
                },
                &Doc { name: "b".into() }
            ),
            Err(DbError::CasMismatch)
        ));
        t.cas(&k(1), &Doc { name: "a".into() }, &Doc { name: "b".into() })
            .unwrap();
        assert_eq!(t.get(&k(1)), Some(Doc { name: "b".into() }));
        assert!(matches!(
            t.compare_delete(&k(1), &Doc { name: "a".into() }),
            Err(DbError::CasMismatch)
        ));
        t.compare_delete(&k(1), &Doc { name: "b".into() }).unwrap();
        assert!(!t.contains(&k(1)));
        assert_eq!(t.len(), 0);
    }

    #[test]
    fn lsm_entry_len_and_typed_reads() {
        let (_d, t) = temp_tree();
        assert!(matches!(t.get_or_err(&k(1)), Err(DbError::KeyNotFound)));
        assert_eq!(t.try_get(&k(1)).unwrap(), None);
        t.put(&k(1), &Doc { name: "abc".into() }).unwrap();
        assert!(t.entry_len(&k(1)).unwrap() > 0);
        assert_eq!(t.get_or_err(&k(1)).unwrap(), Doc { name: "abc".into() });
    }

    #[test]
    fn lsm_hook_fires_with_old_and_new() {
        use std::sync::Arc;
        use std::sync::atomic::{AtomicUsize, Ordering};
        #[derive(Clone)]
        struct CountHook(Arc<AtomicUsize>);
        impl crate::hook::TypedWriteHook<DocId, Doc> for CountHook {
            fn on_write(&self, _k: &DocId, _old: Option<&Doc>, _new: Option<&Doc>) {
                self.0.fetch_add(1, Ordering::Relaxed);
            }
        }
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let n = Arc::new(AtomicUsize::new(0));
        let t: LsmTree<DocId, Doc, RapiraCodec, CountHook> =
            LsmTree::open(db, LsmConfig::default(), RapiraCodec, CountHook(n.clone())).unwrap();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        t.delete(&k(1)).unwrap();
        assert_eq!(n.load(Ordering::Relaxed), 2);
    }

    #[test]
    fn lsm_migrate_rewrites_and_deletes() {
        use crate::MigrateAction;
        let (_d, t) = temp_tree();
        for i in 1..=4u64 {
            t.put(
                &k(i),
                &Doc {
                    name: i.to_string(),
                },
            )
            .unwrap();
        }
        let changed = t
            .migrate(|_id, d| {
                if d.name == "2" {
                    MigrateAction::Delete
                } else {
                    MigrateAction::Update(Doc {
                        name: format!("v_{}", d.name),
                    })
                }
            })
            .unwrap();
        assert_eq!(changed, 4); // 3 updates + 1 delete
        assert_eq!(t.get(&k(1)), Some(Doc { name: "v_1".into() }));
        assert!(t.get(&k(2)).is_none());
        assert_eq!(t.len(), 3);
    }

    #[test]
    fn lsm_collection_trait_object() {
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        let c: &dyn crate::armour::Collection = &t;
        assert_eq!(c.name(), "docs");
        assert_eq!(c.len(), 1);
        c.flush().unwrap();
        c.periodic_flush().unwrap();
        assert_eq!(c.compact().unwrap(), 0); // LSM reclaim has no single count
    }

    #[test]
    fn lsm_atomic_runs_multiple_writes_under_one_lock() {
        // Use lock_stripes=1 so k(1) and k(2) are guaranteed on the same stripe.
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> = LsmTree::open(
            db,
            LsmConfig {
                lock_stripes: 1,
                ..LsmConfig::default()
            },
            RapiraCodec,
            NoHook,
        )
        .unwrap();

        t.put(&k(1), &Doc { name: "a".into() }).unwrap();
        let out = t
            .atomic(&k(1), |sh| {
                let cur = sh.get(&k(1)).unwrap();
                sh.put(
                    &k(1),
                    &Doc {
                        name: format!("{}-x", cur.name),
                    },
                )?;
                sh.insert(&k(2), &Doc { name: "two".into() })?;
                Ok(cur.name)
            })
            .unwrap();
        assert_eq!(out, "a");
        assert_eq!(t.get(&k(1)), Some(Doc { name: "a-x".into() }));
        assert_eq!(t.get(&k(2)), Some(Doc { name: "two".into() }));
        assert_eq!(t.len(), 2);
    }

    #[test]
    fn lsm_atomic_rejects_foreign_stripe() {
        // Open with 4 stripes; find two keys that land on different stripes,
        // then assert that writing the foreign key inside atomic returns ShardMismatch.
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> = LsmTree::open(
            db,
            LsmConfig {
                lock_stripes: 4,
                ..LsmConfig::default()
            },
            RapiraCodec,
            NoHook,
        )
        .unwrap();

        // Find two keys on different stripes.
        let a = k(0);
        let a_stripe = t.shard_for(&a);
        let b = (1u64..=1000)
            .map(k)
            .find(|key| t.shard_for(key) != a_stripe)
            .expect("should find a key on a different stripe within first 1000");

        assert!(matches!(
            t.atomic(&a, |sh| sh.put(
                &b,
                &Doc {
                    name: "foreign".into()
                }
            )),
            Err(DbError::ShardMismatch)
        ));
    }

    #[test]
    fn lsm_count_saturating_no_underflow() {
        // Simulate a persisted seed that under-counts the live rows: open with
        // count=0 and inject a row straight into the keyspace. Deleting that row
        // must saturate at 0, not wrap the AtomicU64 to ~u64::MAX.
        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let t: LsmTree<DocId, Doc, RapiraCodec, NoHook> = LsmTree::open_with_initial_count(
            db,
            LsmConfig::default(),
            RapiraCodec,
            NoHook,
            Some(0),
        )
        .unwrap();
        t.keyspace().insert(k(1).as_bytes(), b"raw").unwrap();
        t.delete(&k(1)).unwrap();
        assert_eq!(t.len(), 0, "count must saturate at 0, not underflow");
        assert!(t.is_empty());
    }

    #[test]
    fn lsm_migrate_errors_on_undecodable_row() {
        use crate::MigrateAction;
        let (_d, t) = temp_tree();
        t.put(&k(1), &Doc { name: "one".into() }).unwrap();
        // Inject a value that cannot decode as `Doc`.
        t.keyspace().insert(k(2).as_bytes(), b"not-a-doc").unwrap();
        // A migration that rewrites every row must surface the corrupt row as
        // an error, not skip it silently and report success (which would let
        // `run_migration` commit a version bump with unmigrated rows on disk).
        let err = t
            .migrate(|_id, _d| MigrateAction::Update(Doc { name: "v".into() }))
            .unwrap_err();
        assert!(matches!(err, DbError::CorruptedEntry { .. }), "{err:?}");
    }

    #[test]
    fn lsm_put_delete_propagate_decode_error_for_corrupt_prev() {
        use std::sync::Arc;
        use std::sync::atomic::{AtomicUsize, Ordering};
        #[derive(Clone)]
        struct CountHook(Arc<AtomicUsize>);
        impl crate::hook::TypedWriteHook<DocId, Doc> for CountHook {
            fn on_write(&self, _k: &DocId, _old: Option<&Doc>, _new: Option<&Doc>) {
                self.0.fetch_add(1, Ordering::Relaxed);
            }
        }
        fn corrupt_tree() -> (
            tempfile::TempDir,
            LsmTree<DocId, Doc, RapiraCodec, CountHook>,
            Arc<AtomicUsize>,
        ) {
            let dir = tempfile::tempdir().unwrap();
            let db = fjall::Database::builder(dir.path()).open().unwrap();
            let hits = Arc::new(AtomicUsize::new(0));
            let t: LsmTree<DocId, Doc, RapiraCodec, CountHook> = LsmTree::open(
                db,
                LsmConfig::default(),
                RapiraCodec,
                CountHook(Arc::clone(&hits)),
            )
            .unwrap();
            t.keyspace().insert(k(1).as_bytes(), b"not-a-doc").unwrap();
            (dir, t, hits)
        }
        // put: corrupt previous value must surface as Err, not collapse to
        // old=None and fire the hook as if this were an insert.
        let (_d, t, hits) = corrupt_tree();
        let err = t.put(&k(1), &Doc { name: "x".into() }).unwrap_err();
        assert!(matches!(err, DbError::CorruptedEntry { .. }), "{err:?}");
        // The failed write must leave NO side effect: the decode happens before
        // the keyspace mutation, so the corrupt row is still there untouched and
        // the hook never fired. Otherwise `Err` would mean "already written but
        // derived state not updated" — a worse index orphan than the bug fixed.
        assert_eq!(
            t.keyspace().get(k(1).as_bytes()).unwrap().as_deref(),
            Some(&b"not-a-doc"[..]),
            "failed put must not have overwritten the stored value"
        );
        assert_eq!(
            hits.load(Ordering::Relaxed),
            0,
            "hook must not fire for a failed put"
        );
        // delete: same — the hook must receive the real old value, so a corrupt
        // previous value is an error rather than a silent old=None cleanup miss.
        let (_d, t, hits) = corrupt_tree();
        let err = t.delete(&k(1)).unwrap_err();
        assert!(matches!(err, DbError::CorruptedEntry { .. }), "{err:?}");
        assert!(
            t.contains(&k(1)),
            "failed delete must not have removed the row"
        );
        assert_eq!(
            hits.load(Ordering::Relaxed),
            0,
            "hook must not fire for a failed delete"
        );
    }

    #[test]
    fn strict_lsm_range_bounds_surfaces_decode_error_without_skipping() {
        use crate::error::{DbError, DbResult};
        use std::ops::Bound;

        let (_d, tree) = temp_tree();
        tree.put(&k(1), &Doc { name: "one".into() }).unwrap();
        tree.put(
            &k(3),
            &Doc {
                name: "three".into(),
            },
        )
        .unwrap();
        tree.keyspace()
            .insert(k(2).as_bytes(), b"not-a-doc")
            .unwrap();

        let result = tree
            .try_range_bounds(Bound::Unbounded, Bound::Unbounded)
            .collect::<DbResult<Vec<_>>>();
        assert!(matches!(result, Err(DbError::CorruptedEntry { .. })));
        assert_eq!(
            tree.iter().count(),
            2,
            "lenient LSM iteration remains unchanged"
        );
    }

    #[test]
    fn strict_lsm_range_rejects_short_key_before_from_bytes() {
        use crate::error::DbError;
        use std::ops::Bound;

        let dir = tempfile::tempdir().unwrap();
        let db = fjall::Database::builder(dir.path()).open().unwrap();
        let tree: LsmTree<DocId, Doc, RapiraCodec, NoHook> = LsmTree::open(
            db,
            LsmConfig {
                reversed: false,
                ..LsmConfig::default()
            },
            RapiraCodec,
            NoHook,
        )
        .unwrap();
        tree.put(&k(1), &Doc { name: "one".into() }).unwrap();
        tree.keyspace().insert(b"short", b"not-a-doc").unwrap();

        let mut iter = tree.try_range_bounds(Bound::Unbounded, Bound::Unbounded);
        match iter.next() {
            Some(Ok((key, d))) => {
                assert_eq!(key, k(1));
                assert_eq!(d, Doc { name: "one".into() });
            }
            other => panic!("expected Ok((k(1), doc)), got {other:?}"),
        }
        assert!(matches!(
            iter.next(),
            Some(Err(DbError::CorruptedEntry { .. }))
        ));
        assert!(iter.next().is_none());
    }

    #[test]
    fn lsm_try_first_last_and_aliases() {
        // Empty tree: try_first returns Ok(None).
        let (_d, t) = temp_tree();
        assert_eq!(t.try_first().unwrap(), None);
        assert_eq!(t.try_last().unwrap(), None);

        // Insert two rows with big-endian keys so ordering is deterministic.
        // reversed=true (default) => first() == largest key, last() == smallest key.
        t.put(&k(1), &Doc { name: "one".into() }).unwrap();
        t.put(&k(2), &Doc { name: "two".into() }).unwrap();

        // try_first / try_last must agree with first / last.
        assert_eq!(t.try_first().unwrap(), t.first());
        assert_eq!(t.try_last().unwrap(), t.last());

        // Under reversed=true: first == k(2)/"two", last == k(1)/"one".
        assert_eq!(
            t.try_first().unwrap(),
            Some((k(2), Doc { name: "two".into() }))
        );
        assert_eq!(
            t.try_last().unwrap(),
            Some((k(1), Doc { name: "one".into() }))
        );

        // flush_buffers and sync_hints are callable and succeed.
        t.flush_buffers().unwrap();
        t.sync_hints().unwrap();
    }
}