haematite 0.7.0

//! Tree chunking policy — the explicit, threaded successor to the deleted
//! `active_detector()` thread-local (CHUNKING-POLICY.md §4.1).
//!
//! Every mutation carries a [`TreePolicy`] by value. There is no default and no
//! ambient source: a caller that fails to supply one is a COMPILE error, which
//! is the whole point of deleting the thread-local — policy can only reach the
//! chunker from exactly one place (the stamp read at open, or an explicit
//! public-API argument), never a silent fallback.
//!
//! Two variants:
//!
//! - [`TreePolicy::V1`] wraps the legacy count-target [`BoundaryDetector`] and
//!   reproduces today's roots BYTE-FOR-BYTE. Its leaf and internal grouping is
//!   the pre-v2 `boundary_after`-only split, and it retains the collapse-all
//!   spine fallback for the all-boundary degenerate case (that fallback lives in
//!   `spine::build_spine`; v1 keeps it, v2 never reaches it).
//! - [`TreePolicy::V2`] is the byte-weighted rule (§2.1/§2.2): leaves weighted by
//!   entry size with deterministic oversized isolation, internal levels grouped
//!   by the min-2 rule.
//!
//! The v1 and v2 paths draw their per-key sample from the SAME primitive
//! ([`super::boundary::key_sample`]); only the threshold arithmetic differs.

use super::boundary::{BoundaryDetector, DEFAULT_TARGET_SIZE, key_sample};

/// Fixed serialized overhead of one leaf entry: two `u64` length prefixes
/// (`node.rs` `leaf_serialised_len`, `2 * U64_SIZE`). The v2 leaf weight is
/// `LEAF_ENTRY_OVERHEAD + |key| + |value|`.
const LEAF_ENTRY_OVERHEAD: u64 = 16;

/// Fixed serialized overhead of one internal child: a `u64` separator-length
/// prefix plus the 32-byte child hash (`node.rs` `internal_serialised_len`,
/// `U64_SIZE + HASH_SIZE`). The v2 internal weight is
/// `INTERNAL_ENTRY_OVERHEAD + |separator|`.
const INTERNAL_ENTRY_OVERHEAD: u64 = 8 + 32;

/// The chunking policy threaded through every mutation. `Copy` so it flows
/// through the recursion without ceremony.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TreePolicy {
    /// Legacy count-targeted chunking (on-disk format 1). Reproduces today's
    /// roots exactly; keeps the collapse-all spine fallback.
    V1(BoundaryDetector),
    /// Byte-aware chunking (on-disk format 2). `leaf_target_bytes` and
    /// `internal_target_bytes` are the stamped, validated-nonzero deployment
    /// contract (`config.rs` refuses a zero stamp with a typed error).
    V2 {
        leaf_target_bytes: u64,
        internal_target_bytes: u64,
    },
}

impl TreePolicy {
    /// The production v1 policy: the default count target the shipped detector
    /// used. This is the byte-for-byte-compatible constant §4.1 names.
    pub const V1_DEFAULT: Self = Self::V1(BoundaryDetector::new(DEFAULT_TARGET_SIZE));

    /// A v1 policy with an explicit count target — used by tests to force
    /// genuinely multi-leaf trees at small key counts (replacing the deleted
    /// `set_test_target_size` seam).
    #[must_use]
    pub const fn v1_with_target(target_size: usize) -> Self {
        Self::V1(BoundaryDetector::new(target_size))
    }

    /// A v2 policy with explicit byte targets. Production constructs this from
    /// the stamped config (validated nonzero at read); tests pass small targets
    /// directly.
    #[must_use]
    pub const fn v2(leaf_target_bytes: u64, internal_target_bytes: u64) -> Self {
        Self::V2 {
            leaf_target_bytes,
            internal_target_bytes,
        }
    }

    /// True for the byte-aware policy. Drives the min-2 internal grouping and
    /// the both-edges sparse-window rule, neither of which applies to v1.
    #[must_use]
    pub const fn is_v2(&self) -> bool {
        matches!(self, Self::V2 { .. })
    }

    /// A chunk closes AFTER this leaf entry.
    ///
    /// v1: the count-target modulo rule on the key alone (value length ignored,
    /// exactly today). v2: the byte-weighted rule `sample * target <
    /// entry_size << 64`, where `entry_size = 16 + |key| + |value|`. An entry at
    /// or above target closes always (P capped at 1).
    #[must_use]
    pub fn leaf_boundary_after(&self, key: &[u8], value_len: usize) -> bool {
        match self {
            Self::V1(detector) => detector.is_boundary(key),
            Self::V2 {
                leaf_target_bytes, ..
            } => byte_boundary_after(
                key,
                leaf_entry_size(key.len(), value_len),
                *leaf_target_bytes,
            ),
        }
    }

    /// A chunk closes BEFORE this leaf entry — the v2 oversized-isolation edge
    /// (`entry_size >= leaf_target_bytes`). Always `false` under v1 (no
    /// `boundary_before` exists there), so v1 leaf grouping reduces exactly to
    /// the `boundary_after`-only split.
    #[must_use]
    pub fn leaf_boundary_before(&self, key_len: usize, value_len: usize) -> bool {
        match self {
            Self::V1(_) => false,
            Self::V2 {
                leaf_target_bytes, ..
            } => {
                *leaf_target_bytes > 0 && leaf_entry_size(key_len, value_len) >= *leaf_target_bytes
            }
        }
    }

    /// A group closes AFTER this internal child's separator.
    ///
    /// v1: the count-target modulo rule on the separator. v2: the byte-weighted
    /// rule against `internal_target_bytes`, weight `8 + |separator| + 32`. The
    /// min-2 gate (a group closes only once it holds >= 2 entries) is applied by
    /// the grouping loop, not here.
    #[must_use]
    pub fn internal_boundary_after(&self, separator: &[u8]) -> bool {
        match self {
            Self::V1(detector) => detector.is_boundary(separator),
            Self::V2 {
                internal_target_bytes,
                ..
            } => byte_boundary_after(
                separator,
                internal_entry_size(separator.len()),
                *internal_target_bytes,
            ),
        }
    }
}

/// The byte-weighted boundary predicate, exact in `u128`:
/// `(sample as u128) * target < (entry_size as u128) << 64`.
///
/// Accepts `sample/2^64 < entry_size/target`, i.e. `P = min(entry_size/target,
/// 1)` to within `2^-64` — the cap makes the at-or-above-target case fire
/// always rather than overflowing the sample space. A zero target (never
/// produced in production — the config read refuses it) yields `0 < x`, i.e. a
/// boundary after every entry: degenerate but terminating.
fn byte_boundary_after(key: &[u8], entry_size: u64, target: u64) -> bool {
    let sample = u128::from(key_sample(key));
    sample * u128::from(target) < (u128::from(entry_size) << 64)
}

/// `16 + |key| + |value|`, saturating in `u64` — the v2 leaf weight matching
/// `node.rs` `leaf_serialised_len`'s per-entry contribution exactly.
fn leaf_entry_size(key_len: usize, value_len: usize) -> u64 {
    LEAF_ENTRY_OVERHEAD
        .saturating_add(len_as_u64(key_len))
        .saturating_add(len_as_u64(value_len))
}

/// `8 + |separator| + 32`, saturating in `u64` — the v2 internal weight
/// matching `node.rs` `internal_serialised_len`'s per-child contribution.
fn internal_entry_size(separator_len: usize) -> u64 {
    INTERNAL_ENTRY_OVERHEAD.saturating_add(len_as_u64(separator_len))
}

/// Checked `usize -> u64` length conversion; a length that cannot fit a `u64`
/// (impossible on 64-bit targets, guarded for completeness) saturates to
/// `u64::MAX`, which only ever makes an entry MORE oversized — never fewer
/// boundaries.
fn len_as_u64(len: usize) -> u64 {
    u64::try_from(len).unwrap_or(u64::MAX)
}

#[cfg(test)]
mod tests {
    use super::{TreePolicy, leaf_entry_size};

    #[test]
    fn v1_default_ignores_value_length() {
        let policy = TreePolicy::V1_DEFAULT;
        // Same key, different value lengths — v1 samples the key only, so the
        // boundary decision must not move.
        let short = policy.leaf_boundary_after(b"some-key", 1);
        let long = policy.leaf_boundary_after(b"some-key", 1_000_000);
        assert_eq!(short, long);
        assert!(!policy.leaf_boundary_before(8, 1_000_000));
    }

    #[test]
    fn v2_oversized_entry_is_always_a_singleton() {
        let policy = TreePolicy::v2(64, 48);
        // entry_size = 16 + 8 + 64 = 88 >= 64 target: boundary both sides.
        assert!(policy.leaf_boundary_before(8, 64));
        assert!(policy.leaf_boundary_after(b"a-key-88", 64));
    }

    #[test]
    fn v2_threshold_equality_always_boundaries() {
        // entry_size exactly == target ⇒ sample * target < target << 64 ⇒
        // sample < 2^64, always true.
        let target = leaf_entry_size(4, 0); // 16 + 4 = 20
        let policy = TreePolicy::v2(target, 48);
        assert!(policy.leaf_boundary_after(b"abcd", 0));
        assert!(policy.leaf_boundary_before(4, 0));
    }

    #[test]
    fn v2_sub_target_entry_is_probabilistic() {
        let policy = TreePolicy::v2(64 * 1024, 48 * 1024);
        // A tiny entry against a 64 KiB target is a boundary only for a vanishing
        // sample fraction; not oversized either way.
        assert!(!policy.leaf_boundary_before(3, 3));
    }
}