weirflow 0.1.0

//! Dense `u32` domain indexing for hot Weir host paths.

const DENSE_WORD_BITS: u64 = 32;
const U32_BYTES: u64 = std::mem::size_of::<u32>() as u64;
const PPM_SCALE: u128 = 1_000_000;

/// Sparse/dense execution family selected from domain shape and observed
/// frontier density.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(crate) enum SparseDenseDomainMode {
    /// No active bits were observed.
    Empty,
    /// Active and changed frontier density are low enough for sparse ids.
    Sparse,
    /// Density is mixed enough that a sparse/dense hybrid should own dispatch.
    Hybrid,
    /// Dense bitsets should own dispatch.
    Dense,
}

/// Operator-visible reason for a sparse/dense domain decision.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub(crate) enum SparseDenseDomainReason {
    /// There is no dispatch domain.
    EmptyDomain,
    /// The dispatch domain exists but no active bits were observed.
    EmptyActiveSet,
    /// Small domains should stay dense to avoid scheduler and conversion churn.
    SmallDomainDense,
    /// Active and delta density are both low.
    LowDensitySparse,
    /// Dense bitset storage did not fit the configured byte budget.
    DenseBudgetExceeded,
    /// Dense bitset byte accounting exceeded the host index width.
    DenseFootprintOverflow,
    /// Active density or most recent active density is high.
    HighDensityDense,
    /// Average graph degree is high enough that dense traversal should win.
    HighDegreeDense,
    /// Density and degree are both mixed.
    MixedDensityHybrid,
}

/// Tunable policy for converting shape and frontier observations into a
/// sparse/dense domain decision.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct SparseDenseDomainPolicy {
    /// Domains at or below this size choose dense after the empty checks.
    pub small_dense_domain_bits: u64,
    /// Mean active density at or below this value can choose sparse.
    pub sparse_active_density_ppm: u64,
    /// Mean delta density at or below this value can choose sparse.
    pub sparse_delta_density_ppm: u64,
    /// Mean active density at or above this value chooses dense.
    pub dense_active_density_ppm: u64,
    /// Most recent active density at or above this value chooses dense.
    pub dense_last_active_density_ppm: u64,
    /// Sparse is only selected at or below this average graph degree.
    pub sparse_max_average_degree_ppm: u64,
    /// Dense is selected at or above this average graph degree.
    pub dense_min_average_degree_ppm: u64,
    /// Optional dense bitset budget. Exceeding it forces sparse mode.
    pub dense_byte_budget: Option<usize>,
}

impl SparseDenseDomainPolicy {
    /// Policy for raw frontier-density telemetry. This preserves telemetry's
    /// density-only recommendation semantics.
    pub(crate) const fn frontier_density() -> Self {
        Self {
            small_dense_domain_bits: 0,
            sparse_active_density_ppm: 62_500,
            sparse_delta_density_ppm: 31_250,
            dense_active_density_ppm: 500_000,
            dense_last_active_density_ppm: 750_000,
            sparse_max_average_degree_ppm: u64::MAX,
            dense_min_average_degree_ppm: u64::MAX,
            dense_byte_budget: None,
        }
    }

    /// Policy for fixed-point execution planning. This adds scheduler-churn and
    /// graph-degree cutoffs around the same frontier-density thresholds.
    pub(crate) const fn fixed_point_execution() -> Self {
        Self {
            small_dense_domain_bits: 1024,
            sparse_max_average_degree_ppm: 2_000_000,
            dense_min_average_degree_ppm: 16_000_000,
            ..Self::frontier_density()
        }
    }
}

/// Raw facts used by the sparse/dense domain planner.
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub(crate) struct SparseDenseDomainObservation {
    /// Number of bits in the dispatch domain.
    pub domain_bits: u64,
    /// Number of decoded frontier samples, including the seed frontier.
    pub samples: u64,
    /// Number of decoded frontier transitions.
    pub iterations: u64,
    /// Sum of active frontier bits across all samples.
    pub active_bits_total: u64,
    /// Sum of changed frontier bits across decoded transitions.
    pub delta_bits_total: u64,
    /// Active bits in the most recently decoded sample.
    pub last_active_bits: u64,
    /// Maximum active bits observed in one decoded sample.
    pub peak_active_bits: u64,
    /// Average outgoing graph degree in parts per million.
    pub average_degree_ppm: u64,
}

/// Sparse/dense decision plus byte and density evidence.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) struct SparseDenseDomainPlan {
    /// Selected sparse/dense family.
    pub mode: SparseDenseDomainMode,
    /// Why the family was selected.
    pub reason: SparseDenseDomainReason,
    /// Domain bits covered by this decision.
    pub domain_bits: u64,
    /// Mean active density in parts per million.
    pub active_density_ppm: u64,
    /// Mean delta density in parts per million.
    pub delta_density_ppm: u64,
    /// Most recent active density in parts per million.
    pub last_active_density_ppm: u64,
    /// Dense bitset words needed to cover the domain.
    pub dense_words: Option<u64>,
    /// Dense bitset bytes needed to cover the domain.
    pub dense_bytes: Option<usize>,
    /// Sparse frontier bytes needed for the peak observed active set.
    pub sparse_bytes: Option<usize>,
    /// Optional dense budget applied by the policy.
    pub dense_byte_budget: Option<usize>,
    /// Average outgoing graph degree in parts per million.
    pub average_degree_ppm: u64,
}

/// Build a single sparse/dense domain decision from domain shape, frontier
/// observations, and policy.
#[must_use]
pub(crate) fn plan_sparse_dense_domain(
    policy: SparseDenseDomainPolicy,
    observation: SparseDenseDomainObservation,
) -> SparseDenseDomainPlan {
    let active_density_ppm = density_ppm(
        observation.active_bits_total,
        u128::from(observation.domain_bits) * u128::from(observation.samples),
    );
    let delta_density_ppm = density_ppm(
        observation.delta_bits_total,
        u128::from(observation.domain_bits) * u128::from(observation.iterations),
    );
    let last_active_density_ppm = density_ppm(
        observation.last_active_bits,
        u128::from(observation.domain_bits),
    );
    let dense_words = observation.domain_bits.checked_add(DENSE_WORD_BITS - 1).map(|bits| {
        if bits == 0 {
            0
        } else {
            bits / DENSE_WORD_BITS
        }
    });
    let dense_bytes_u64 = dense_words.and_then(|words| words.checked_mul(U32_BYTES));
    let dense_bytes = dense_bytes_u64.and_then(|bytes| usize::try_from(bytes).ok());
    let sparse_bytes = observation
        .peak_active_bits
        .checked_mul(U32_BYTES)
        .and_then(|bytes| usize::try_from(bytes).ok());

    let (mode, reason) = choose_sparse_dense_mode(
        policy,
        observation,
        active_density_ppm,
        delta_density_ppm,
        last_active_density_ppm,
        dense_bytes,
    );

    SparseDenseDomainPlan {
        mode,
        reason,
        domain_bits: observation.domain_bits,
        active_density_ppm,
        delta_density_ppm,
        last_active_density_ppm,
        dense_words,
        dense_bytes,
        sparse_bytes,
        dense_byte_budget: policy.dense_byte_budget,
        average_degree_ppm: observation.average_degree_ppm,
    }
}

fn choose_sparse_dense_mode(
    policy: SparseDenseDomainPolicy,
    observation: SparseDenseDomainObservation,
    active_density_ppm: u64,
    delta_density_ppm: u64,
    last_active_density_ppm: u64,
    dense_bytes: Option<usize>,
) -> (SparseDenseDomainMode, SparseDenseDomainReason) {
    if observation.domain_bits == 0 {
        return (
            SparseDenseDomainMode::Empty,
            SparseDenseDomainReason::EmptyDomain,
        );
    }
    if observation.peak_active_bits == 0
        && observation.active_bits_total == 0
        && observation.last_active_bits == 0
    {
        return (
            SparseDenseDomainMode::Empty,
            SparseDenseDomainReason::EmptyActiveSet,
        );
    }
    if dense_bytes.is_none() {
        return (
            SparseDenseDomainMode::Sparse,
            SparseDenseDomainReason::DenseFootprintOverflow,
        );
    }
    if let (Some(budget), Some(bytes)) = (policy.dense_byte_budget, dense_bytes) {
        if bytes > budget {
            return (
                SparseDenseDomainMode::Sparse,
                SparseDenseDomainReason::DenseBudgetExceeded,
            );
        }
    }
    if observation.domain_bits <= policy.small_dense_domain_bits {
        return (
            SparseDenseDomainMode::Dense,
            SparseDenseDomainReason::SmallDomainDense,
        );
    }
    if active_density_ppm >= policy.dense_active_density_ppm
        || last_active_density_ppm >= policy.dense_last_active_density_ppm
    {
        return (
            SparseDenseDomainMode::Dense,
            SparseDenseDomainReason::HighDensityDense,
        );
    }
    if observation.average_degree_ppm >= policy.dense_min_average_degree_ppm {
        return (
            SparseDenseDomainMode::Dense,
            SparseDenseDomainReason::HighDegreeDense,
        );
    }
    if active_density_ppm <= policy.sparse_active_density_ppm
        && delta_density_ppm <= policy.sparse_delta_density_ppm
        && observation.average_degree_ppm <= policy.sparse_max_average_degree_ppm
    {
        return (
            SparseDenseDomainMode::Sparse,
            SparseDenseDomainReason::LowDensitySparse,
        );
    }
    (
        SparseDenseDomainMode::Hybrid,
        SparseDenseDomainReason::MixedDensityHybrid,
    )
}

#[derive(Clone, Debug)]
pub(crate) struct DenseU32Slots<T> {
    domain: u32,
    slots: Vec<T>,
}

impl<T: Copy + Default> DenseU32Slots<T> {
    pub(crate) fn new(domain: u32, field: &'static str) -> Result<Self, String> {
        let len = usize::try_from(domain).map_err(|_| {
            format!(
                "Weir dense domain {domain} cannot fit usize for {field}. Fix: shard the graph before host SSA or cache indexing."
            )
        })?;
        let mut slots = Vec::new();
        crate::staging_reserve::reserve_vec(&mut slots, len, field)?;
        slots.resize(len, T::default());
        Ok(Self { domain, slots })
    }

    #[inline]
    pub(crate) fn get(&self, key: u32) -> Option<&T> {
        self.slots.get(key as usize)
    }

    #[inline]
    pub(crate) fn insert(&mut self, key: u32, value: T) -> Result<(), String> {
        let slot = self.slots.get_mut(key as usize).ok_or_else(|| {
            format!(
                "Weir dense slot key {key} is outside domain {}. Fix: only index ids present in the CFG or graph layout.",
                self.domain
            )
        })?;
        *slot = value;
        Ok(())
    }

    #[inline]
    #[must_use]
    #[allow(dead_code)]
    pub(crate) fn len(&self) -> usize {
        self.slots.len()
    }

    #[inline]
    #[must_use]
    #[allow(dead_code)]
    pub(crate) fn is_empty(&self) -> bool {
        self.slots.is_empty()
    }

    #[inline]
    #[must_use]
    #[allow(dead_code)]
    pub(crate) fn first(&self) -> Option<&T> {
        self.slots.first()
    }

    #[inline]
    #[must_use]
    #[allow(dead_code)]
    pub(crate) fn last(&self) -> Option<&T> {
        self.slots.last()
    }
}

pub(crate) fn dense_domain_for_keys<I>(keys: I) -> Result<u32, String>
where
    I: IntoIterator<Item = u32>,
{
    let mut max_key = 0u32;
    let mut any = false;
    for key in keys {
        any = true;
        max_key = max_key.max(key);
    }
    if !any {
        return Ok(0);
    }
    max_key.checked_add(1).ok_or_else(|| {
        "Weir dense domain overflowed u32 while covering block ids. Fix: shard the CFG before SSA host indexing.".to_string()
    })
}

fn density_ppm(numerator: u64, denominator: u128) -> u64 {
    if denominator == 0 {
        return 0;
    }
    let scaled = u128::from(numerator) * PPM_SCALE;
    let value = scaled / denominator;
    if value > u128::from(u64::MAX) {
        u64::MAX
    } else {
        value as u64
    }
}

#[cfg(test)]
mod tests {
    use super::{
        dense_domain_for_keys, plan_sparse_dense_domain, DenseU32Slots,
        SparseDenseDomainMode, SparseDenseDomainObservation, SparseDenseDomainPolicy,
        SparseDenseDomainReason,
    };

    fn observation(
        domain_bits: u64,
        active_bits_total: u64,
        delta_bits_total: u64,
        samples: u64,
        iterations: u64,
        peak_active_bits: u64,
        average_degree_ppm: u64,
    ) -> SparseDenseDomainObservation {
        SparseDenseDomainObservation {
            domain_bits,
            samples,
            iterations,
            active_bits_total,
            delta_bits_total,
            last_active_bits: peak_active_bits,
            peak_active_bits,
            average_degree_ppm,
        }
    }

    #[test]
    fn sparse_dense_plan_reports_empty_domain() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(0, 0, 0, 0, 0, 0, 0),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Empty);
        assert_eq!(plan.reason, SparseDenseDomainReason::EmptyDomain);
        assert_eq!(plan.dense_words, Some(0));
        assert_eq!(plan.dense_bytes, Some(0));
    }

    #[test]
    fn sparse_dense_plan_reports_empty_active_set() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(4096, 0, 0, 2, 1, 0, 1_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Empty);
        assert_eq!(plan.reason, SparseDenseDomainReason::EmptyActiveSet);
    }

    #[test]
    fn sparse_dense_plan_selects_sparse_for_low_density_delta() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(4096, 8, 4, 2, 1, 4, 1_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Sparse);
        assert_eq!(plan.reason, SparseDenseDomainReason::LowDensitySparse);
        assert_eq!(plan.active_density_ppm, 976);
        assert_eq!(plan.delta_density_ppm, 976);
        assert_eq!(plan.last_active_density_ppm, 976);
    }

    #[test]
    fn sparse_dense_plan_keeps_small_domains_dense() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(128, 2, 1, 2, 1, 1, 1_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Dense);
        assert_eq!(plan.reason, SparseDenseDomainReason::SmallDomainDense);
    }

    #[test]
    fn sparse_dense_plan_selects_hybrid_for_mixed_density() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(4096, 1024, 256, 2, 1, 512, 4_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Hybrid);
        assert_eq!(plan.reason, SparseDenseDomainReason::MixedDensityHybrid);
    }

    #[test]
    fn sparse_dense_plan_selects_dense_for_high_density() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(4096, 4096, 16, 2, 1, 3072, 1_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Dense);
        assert_eq!(plan.reason, SparseDenseDomainReason::HighDensityDense);
    }

    #[test]
    fn sparse_dense_plan_selects_dense_for_high_degree() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(4096, 8, 4, 2, 1, 4, 16_000_000),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Dense);
        assert_eq!(plan.reason, SparseDenseDomainReason::HighDegreeDense);
    }

    #[test]
    fn sparse_dense_plan_honors_dense_byte_budget() {
        let mut policy = SparseDenseDomainPolicy::fixed_point_execution();
        policy.dense_byte_budget = Some(511);

        let plan = plan_sparse_dense_domain(policy, observation(4096, 4096, 16, 2, 1, 3072, 0));

        assert_eq!(plan.mode, SparseDenseDomainMode::Sparse);
        assert_eq!(plan.reason, SparseDenseDomainReason::DenseBudgetExceeded);
        assert_eq!(plan.dense_bytes, Some(512));
        assert_eq!(plan.dense_byte_budget, Some(511));
    }

    #[test]
    fn sparse_dense_plan_reports_checked_dense_byte_overflow() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::fixed_point_execution(),
            observation(u64::MAX, u64::MAX, 0, 1, 1, u64::MAX, 0),
        );

        assert_eq!(plan.mode, SparseDenseDomainMode::Sparse);
        assert_eq!(plan.reason, SparseDenseDomainReason::DenseFootprintOverflow);
        assert_eq!(plan.dense_words, None);
        assert_eq!(plan.dense_bytes, None);
        assert_eq!(plan.sparse_bytes, None);
    }

    #[test]
    fn sparse_dense_plan_reports_exact_dense_and_sparse_bytes() {
        let plan = plan_sparse_dense_domain(
            SparseDenseDomainPolicy::frontier_density(),
            observation(100, 50, 5, 2, 1, 7, 0),
        );

        assert_eq!(plan.domain_bits, 100);
        assert_eq!(plan.active_density_ppm, 250_000);
        assert_eq!(plan.delta_density_ppm, 50_000);
        assert_eq!(plan.last_active_density_ppm, 70_000);
        assert_eq!(plan.dense_words, Some(4));
        assert_eq!(plan.dense_bytes, Some(16));
        assert_eq!(plan.sparse_bytes, Some(28));
        assert_eq!(plan.average_degree_ppm, 0);
    }

    // ------------------------------------------------------------------
    // 1. insert OOB error.
    // ------------------------------------------------------------------

    #[test]
    fn insert_oob_at_domain_boundary() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(4, "test").unwrap();
        assert!(slots.insert(3, 99).is_ok());
        let err = slots
            .insert(4, 100)
            .expect_err("must error at domain boundary");
        assert!(err.contains("is outside domain"));
    }

    #[test]
    fn insert_oob_beyond_domain() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(2, "test").unwrap();
        let err = slots.insert(100, 1).expect_err("must error beyond domain");
        assert!(err.contains("is outside domain"));
    }

    #[test]
    fn insert_at_zero_boundary() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(1, "test").unwrap();
        assert!(slots.insert(0, 42).is_ok());
        assert_eq!(slots.get(0), Some(&42));
    }

    #[test]
    fn insert_oob_on_empty_domain() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(0, "test").unwrap();
        let err = slots.insert(0, 1).expect_err("must error on empty domain");
        assert!(err.contains("is outside domain"));
    }

    #[test]
    fn insert_overwrite_existing_value() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(3, "test").unwrap();
        slots.insert(1, 10).unwrap();
        slots.insert(1, 20).unwrap();
        assert_eq!(slots.get(1), Some(&20));
    }

    // ------------------------------------------------------------------
    // 2. new overflow.
    // ------------------------------------------------------------------

    #[test]
    fn new_with_u32_max_does_not_panic() {
        // u32::MAX may succeed or fail depending on host memory; either is valid
        // as long as the function does not panic and reports correctly.
        let result = DenseU32Slots::<u8>::new(u32::MAX, "test_overflow");
        match result {
            Ok(slots) => assert_eq!(slots.len(), u32::MAX as usize),
            Err(err) => assert!(
                err.contains("could not reserve") || err.contains("cannot fit"),
                "unexpected error: {err}"
            ),
        }
    }

    #[test]
    fn new_with_zero_domain_succeeds() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        assert_eq!(slots.len(), 0);
        assert!(slots.is_empty());
    }

    #[test]
    fn new_with_small_domain_succeeds() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(5, "test").unwrap();
        assert_eq!(slots.len(), 5);
        assert!(!slots.is_empty());
    }

    // ------------------------------------------------------------------
    // 3. dense_domain_for_keys with empty iterators.
    // ------------------------------------------------------------------

    #[test]
    fn dense_domain_for_keys_empty_returns_zero() {
        let domain = dense_domain_for_keys::<std::iter::Empty<u32>>(std::iter::empty()).unwrap();
        assert_eq!(domain, 0);
    }

    #[test]
    fn dense_domain_for_keys_empty_vec_returns_zero() {
        let domain = dense_domain_for_keys::<Vec<u32>>(vec![]).unwrap();
        assert_eq!(domain, 0);
    }

    #[test]
    fn dense_domain_for_keys_single_key() {
        let domain = dense_domain_for_keys([5]).unwrap();
        assert_eq!(domain, 6);
    }

    #[test]
    fn dense_domain_for_keys_multiple_keys() {
        let domain = dense_domain_for_keys([0, 3, 7, 2]).unwrap();
        assert_eq!(domain, 8);
    }

    #[test]
    fn dense_domain_for_keys_max_u32_overflows() {
        let result = dense_domain_for_keys([u32::MAX]);
        assert!(result.is_err(), "u32::MAX key must overflow domain");
    }

    #[test]
    fn dense_domain_for_keys_zero_key() {
        let domain = dense_domain_for_keys([0]).unwrap();
        assert_eq!(domain, 1);
    }

    #[test]
    fn dense_domain_for_keys_duplicate_keys() {
        let domain = dense_domain_for_keys([3, 3, 3, 3]).unwrap();
        assert_eq!(domain, 4);
    }

    #[test]
    fn dense_domain_for_keys_mixed_with_max() {
        let result = dense_domain_for_keys([0, 1, u32::MAX]);
        assert!(result.is_err());
    }

    // ------------------------------------------------------------------
    // 4. Domain indexing roundtrip.
    // ------------------------------------------------------------------

    #[test]
    fn roundtrip_insert_get() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(8, "test").unwrap();
        slots.insert(3, 12345).unwrap();
        assert_eq!(slots.get(3), Some(&12345));
    }

    #[test]
    fn roundtrip_multiple_inserts() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(8, "test").unwrap();
        for i in 0..8 {
            slots.insert(i, i as u64 * 10).unwrap();
        }
        for i in 0..8 {
            assert_eq!(slots.get(i), Some(&(i as u64 * 10)));
        }
    }

    #[test]
    fn get_oob_returns_none() {
        let slots: DenseU32Slots<u64> = DenseU32Slots::new(4, "test").unwrap();
        assert_eq!(slots.get(4), None);
        assert_eq!(slots.get(100), None);
    }

    #[test]
    fn get_on_empty_domain_returns_none() {
        let slots: DenseU32Slots<u64> = DenseU32Slots::new(0, "test").unwrap();
        assert_eq!(slots.get(0), None);
    }

    #[test]
    fn unset_slots_return_default_value() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(4, "test").unwrap();
        for i in 0..4 {
            assert_eq!(slots.get(i), Some(&0));
        }
    }

    #[test]
    fn roundtrip_with_bool_type() {
        let mut slots: DenseU32Slots<bool> = DenseU32Slots::new(4, "test").unwrap();
        slots.insert(1, true).unwrap();
        slots.insert(2, true).unwrap();
        assert_eq!(slots.get(0), Some(&false));
        assert_eq!(slots.get(1), Some(&true));
        assert_eq!(slots.get(2), Some(&true));
        assert_eq!(slots.get(3), Some(&false));
    }

    // ------------------------------------------------------------------
    // 5. DenseU32Slots boundary queries.
    // ------------------------------------------------------------------

    #[test]
    fn len_matches_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(7, "test").unwrap();
        assert_eq!(slots.len(), 7);
    }

    #[test]
    fn len_zero_for_empty_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        assert_eq!(slots.len(), 0);
    }

    #[test]
    fn is_empty_true_for_zero_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        assert!(slots.is_empty());
    }

    #[test]
    fn is_empty_false_for_nonzero_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(1, "test").unwrap();
        assert!(!slots.is_empty());
    }

    #[test]
    fn first_returns_default_on_uninitialized() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(3, "test").unwrap();
        assert_eq!(slots.first(), Some(&0));
    }

    #[test]
    fn first_returns_none_on_empty_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        assert_eq!(slots.first(), None);
    }

    #[test]
    fn last_returns_default_on_uninitialized() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(3, "test").unwrap();
        assert_eq!(slots.last(), Some(&0));
    }

    #[test]
    fn last_returns_none_on_empty_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        assert_eq!(slots.last(), None);
    }

    #[test]
    fn first_and_last_after_inserts() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(3, "test").unwrap();
        slots.insert(0, 10).unwrap();
        slots.insert(2, 30).unwrap();
        assert_eq!(slots.first(), Some(&10));
        assert_eq!(slots.last(), Some(&30));
        assert_eq!(slots.get(1), Some(&0));
    }

    #[test]
    fn clone_preserves_values() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(4, "test").unwrap();
        slots.insert(0, 1).unwrap();
        slots.insert(2, 3).unwrap();
        let cloned = slots.clone();
        assert_eq!(cloned.get(0), Some(&1));
        assert_eq!(cloned.get(1), Some(&0));
        assert_eq!(cloned.get(2), Some(&3));
        assert_eq!(cloned.get(3), Some(&0));
        assert_eq!(cloned.len(), 4);
    }

    #[test]
    fn debug_format_includes_struct_name() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(2, "test").unwrap();
        let debug = format!("{:?}", slots);
        assert!(debug.contains("DenseU32Slots"));
    }

    #[test]
    fn insert_at_last_valid_index() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(5, "test").unwrap();
        assert!(slots.insert(4, 99).is_ok());
        assert_eq!(slots.get(4), Some(&99));
    }

    #[test]
    fn get_at_domain_boundary_returns_none() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(3, "test").unwrap();
        assert_eq!(slots.get(3), None);
    }

    #[test]
    fn get_at_u32_max_returns_none() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(3, "test").unwrap();
        assert_eq!(slots.get(u32::MAX), None);
    }

    #[test]
    fn dense_domain_for_keys_large_values() {
        let domain = dense_domain_for_keys([100_000, 50_000, 99_999]).unwrap();
        assert_eq!(domain, 100_001);
    }

    #[test]
    fn dense_domain_for_keys_ascending_sequence() {
        let domain = dense_domain_for_keys([0, 1, 2, 3, 4]).unwrap();
        assert_eq!(domain, 5);
    }

    #[test]
    fn dense_domain_for_keys_descending_sequence() {
        let domain = dense_domain_for_keys([4, 3, 2, 1, 0]).unwrap();
        assert_eq!(domain, 5);
    }

    #[test]
    fn dense_domain_for_keys_sparse() {
        let domain = dense_domain_for_keys([0, 100, 200]).unwrap();
        assert_eq!(domain, 201);
    }

    #[test]
    fn dense_domain_for_keys_single_zero() {
        let domain = dense_domain_for_keys([0]).unwrap();
        assert_eq!(domain, 1);
    }

    #[test]
    fn len_matches_after_insert_no_resize() {
        let mut slots: DenseU32Slots<u32> = DenseU32Slots::new(4, "test").unwrap();
        slots.insert(0, 1).unwrap();
        slots.insert(3, 4).unwrap();
        assert_eq!(slots.len(), 4);
    }

    #[test]
    fn first_after_explicit_inserts() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(4, "test").unwrap();
        slots.insert(0, 42).unwrap();
        assert_eq!(slots.first(), Some(&42));
    }

    #[test]
    fn last_after_explicit_inserts() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(4, "test").unwrap();
        slots.insert(3, 99).unwrap();
        assert_eq!(slots.last(), Some(&99));
    }

    #[test]
    fn single_element_domain_roundtrip() {
        let mut slots: DenseU32Slots<u64> = DenseU32Slots::new(1, "test").unwrap();
        slots.insert(0, 123).unwrap();
        assert_eq!(slots.get(0), Some(&123));
        assert_eq!(slots.first(), Some(&123));
        assert_eq!(slots.last(), Some(&123));
        assert_eq!(slots.len(), 1);
        assert!(!slots.is_empty());
    }

    #[test]
    fn new_with_large_but_reasonable_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(1_000_000, "test").unwrap();
        assert_eq!(slots.len(), 1_000_000);
        assert_eq!(slots.get(999_999), Some(&0));
    }

    #[test]
    fn clone_of_empty_domain() {
        let slots: DenseU32Slots<u32> = DenseU32Slots::new(0, "test").unwrap();
        let cloned = slots.clone();
        assert!(cloned.is_empty());
        assert_eq!(cloned.len(), 0);
    }
}