iddqd 0.5.0

//! A "table" of b-tree-based indexes.
//!
//! Similar to [`super::hash_table::MapHashTable`], b-tree based tables store
//! integers (that are indexes corresponding to items), but use an external
//! comparator.
//!
//! # The no-duplicate invariant
//!
//! No two entries in a [`MapBTreeTable`] hold the same [`ItemIndex`].
//!
//! Unsafe code relies on this invariant without checking it at the point of
//! use. `IdOrdMap`'s `IterMut` walks the tree and calls `ItemSlotsPtr::get_mut`
//! once per entry. That call checks that the slot is in bounds and occupied,
//! but it does not check that it has not seen the same index before. If the
//! tree held an index twice, `IterMut` would hand out two `&mut T` to the same
//! slot.
//!
//! Only two operations can add or change an index in the tree, and each one
//! maintains the invariant:
//!
//! * [`MapBTreeTable::prepare_insert`] inserts an index that is vacant in the
//!   item set, so it cannot already be in the tree. Even if a user `Ord` lies,
//!   [`insert_cmp`] never returns `Equal` for two different indexes, so
//!   `BTreeMap::entry` cannot land on an existing entry.
//! * [`MapBTreeTable::remap_indexes`] rewrites every index through an
//!   injective map, and it checks every index before it writes any, so a
//!   panic cannot leave the tree half rewritten.
//!
//! The invariant also relies on the supporting fact that the tree only holds
//! indexes of occupied slots. `IdOrdMap` maintains that by:
//!
//! * Removing an entry from the tree before it frees the slot.
//! * Clearing the tree before it drops the items.
//!
//! A stale index would let a later insert reuse the slot and produce a
//! duplicate.

use super::{ItemIndex, item_set::IndexRemap, map_hash::MapHash};
use crate::internal::{
    TableValidationError, ValidateCompact, table_validation_fail,
};
use alloc::{
    collections::{BTreeMap, btree_map},
    vec::Vec,
};
use core::{
    cell::Cell,
    cmp::Ordering,
    hash::{BuildHasher, Hash},
    marker::PhantomData,
};
use equivalent::Comparable;

thread_local! {
    /// Stores an external comparator function to provide dynamic scoping.
    ///
    /// std's BTreeMap doesn't allow passing an external comparator, so we make
    /// do with this function that's passed in through dynamic scoping.
    ///
    /// This works by:
    ///
    /// * We store an `Index` in the BTreeMap which knows how to call this
    ///   dynamic comparator.
    /// * When we need to compare two `Index` values, we create a CmpDropGuard.
    ///   This struct is responsible for managing the lifetime of the
    ///   comparator.
    /// * When the CmpDropGuard is dropped (including due to a panic), we reset
    ///   the comparator to None.
    ///
    /// Comparators take `&Index` rather than `Index` by value because `Index`
    /// wraps `IndexCell` (an `AtomicU32` newtype) for in-place mutation in
    /// `remap_indexes`, and `AtomicU32` isn't `Copy`.
    ///
    /// This is not great! (For one, thread-locals and no-std don't really mix.)
    /// Some alternatives:
    ///
    /// * Using `Borrow` as described in
    ///   https://github.com/sunshowers-code/borrow-complex-key-example. While
    ///   hacky, this actually works for the find operation. But the insert
    ///   operation currently requires a concrete `Index`.
    ///
    ///   If and when https://github.com/rust-lang/rust/issues/133549 lands,
    ///   this should become a viable option. Worth looking out for!
    ///
    /// * Using a third-party BTreeMap implementation that allows passing in
    ///   external comparators. As of 2025-05, there appear to be two options:
    ///
    ///   1. copse (https://docs.rs/copse), which doesn't seem like a good fit
    ///      here.
    ///   2. btree_monstrousity (https://crates.io/crates/btree_monstrousity),
    ///      which has an API perfect for this but is, uhh, not really
    ///      production-ready.
    ///
    ///   Third-party implementations also run the risk of being relatively
    ///   untested.
    ///
    /// * Using some other kind of sorted set. We've picked B-trees here as the
    ///   default choice to balance cache locality, but other options are worth
    ///   benchmarking. We do need to provide a comparator, though, so radix
    ///   trees and such are out of the question.
    static CMP: Cell<Option<&'static IndexCmp<'static>>>
        = const { Cell::new(None) };
}

/// External comparator type used via `CMP`'s dynamic scoping.
type IndexCmp<'a> = dyn Fn(&Index, &Index) -> Ordering + 'a;

/// A B-tree-based table with an external comparator.
#[derive(Clone, Debug, Default)]
pub(crate) struct MapBTreeTable {
    items: BTreeMap<Index, ()>,
    // We use foldhash directly here because we allow compiling with std but
    // without the default-hasher. std turns on foldhash but not the default
    // hasher.
    hash_state: foldhash::fast::FixedState,
}

impl MapBTreeTable {
    pub(crate) const fn new() -> Self {
        Self {
            items: BTreeMap::new(),
            // FixedState::with_seed XORs the passed in seed with a fixed
            // high-entropy value.
            hash_state: foldhash::fast::FixedState::with_seed(0),
        }
    }

    #[doc(hidden)]
    pub(crate) fn len(&self) -> usize {
        self.items.len()
    }

    #[doc(hidden)]
    pub(crate) fn validate(
        &self,
        expected_len: usize,
        compactness: ValidateCompact,
    ) -> Result<(), TableValidationError> {
        if self.len() != expected_len {
            table_validation_fail!(
                "expected length {expected_len}, was {}",
                self.len(),
            );
        }

        match compactness {
            ValidateCompact::Compact => {
                // All items between 0 (inclusive) and self.len() (exclusive)
                // are present, and there are no duplicates. Also, the sentinel
                // value should not be stored.
                let mut indexes: Vec<ItemIndex> =
                    Vec::with_capacity(expected_len);
                for index in self.items.keys() {
                    let v = index.value();
                    if v == Index::SENTINEL_VALUE {
                        table_validation_fail!(
                            "sentinel value should not be stored in map",
                        );
                    }
                    indexes.push(v);
                }
                indexes.sort_unstable();
                for (i, index) in indexes.iter().enumerate() {
                    if index.as_u32() as usize != i {
                        table_validation_fail!(
                            "value at index {i} should be {i}, was {index}",
                        );
                    }
                }
            }
            ValidateCompact::NonCompact => {
                // There should be no duplicates, and the sentinel value
                // should not be stored.
                //
                // A sort and dedup is equivalent to a `BTreeSet`, but is much
                // faster under the Soteria model checker.
                let mut values: Vec<ItemIndex> =
                    self.items.keys().map(|ix| ix.value()).collect();
                let total = values.len();
                values.sort_unstable();
                values.dedup();
                if values.len() != total {
                    table_validation_fail!(
                        "expected {} values with no duplicates, but only found \
                         {} values (unique values: {:?})",
                        total,
                        values.len(),
                        values,
                    );
                }
                if values.contains(&Index::SENTINEL_VALUE) {
                    table_validation_fail!(
                        "sentinel value should not be stored in map",
                    );
                }
            }
        }

        Ok(())
    }

    #[inline]
    pub(crate) fn first(&self) -> Option<ItemIndex> {
        self.items.first_key_value().map(|(ix, ())| ix.value())
    }

    #[inline]
    pub(crate) fn last(&self) -> Option<ItemIndex> {
        self.items.last_key_value().map(|(ix, ())| ix.value())
    }

    pub(crate) fn find_index<K, Q, F>(
        &self,
        key: &Q,
        lookup: F,
    ) -> Option<ItemIndex>
    where
        K: Ord,
        Q: ?Sized + Comparable<K>,
        F: Fn(ItemIndex) -> K,
    {
        let f = find_cmp(key, lookup);

        let guard = CmpDropGuard::new(&f);

        let ret = match self.items.get_key_value(&Index::sentinel()) {
            Some((ix, ())) if ix.value() == Index::SENTINEL_VALUE => {
                panic!("internal map shouldn't store sentinel value")
            }
            Some((ix, ())) => Some(ix.value()),
            None => {
                // The key is not in the table.
                None
            }
        };

        // drop(guard) isn't necessary, but we make it explicit
        drop(guard);
        ret
    }

    pub(crate) fn prepare_insert<K, Q, F>(
        &mut self,
        index: ItemIndex,
        key: &Q,
        lookup: F,
    ) -> PreparedBTreeInsert<'_>
    where
        K: Ord,
        Q: ?Sized + Comparable<K>,
        F: Fn(ItemIndex) -> K,
    {
        let f = insert_cmp(index, key, lookup);
        let guard = CmpDropGuard::new(&f);

        let entry = match self.items.entry(Index::new(index)) {
            btree_map::Entry::Vacant(entry) => entry,
            btree_map::Entry::Occupied(_) => {
                panic!("internal map already contains index {index}")
            }
        };

        // drop(guard) isn't necessary, but we make it explicit
        drop(guard);

        PreparedBTreeInsert { entry }
    }

    pub(crate) fn prepare_remove<K, F>(
        &mut self,
        index: ItemIndex,
        key: &K,
        lookup: F,
    ) -> PreparedBTreeRemove<'_>
    where
        F: Fn(ItemIndex) -> K,
        K: Ord,
    {
        let f = insert_cmp(index, key, lookup);
        let guard = CmpDropGuard::new(&f);
        let entry = self.items.entry(Index::new(index));

        // drop(guard) isn't necessary, but we make it explicit
        drop(guard);

        match entry {
            btree_map::Entry::Vacant(_) => {
                // The comparator-based search missed an entry that
                // `remove_by_index` has just confirmed lives in the item set.
                // The most likely cause is a hash-blind key mutation that
                // `RefMut` could not detect: the tree's structural order is
                // now wrong, so a binary search walks past the physical
                // entry.
                //
                // This is a signal to the caller to fall back to the linear
                // `remove_exact` fallback when it commits the change.
                PreparedBTreeRemove { inner: PreparedBTreeRemoveInner::Missing }
            }
            btree_map::Entry::Occupied(entry) => PreparedBTreeRemove {
                inner: PreparedBTreeRemoveInner::Occupied(entry),
            },
        }
    }

    pub(crate) fn remove_exact(&mut self, index: ItemIndex) {
        // If an item key was changed without detection, the B-tree order can be
        // wrong. A comparator-based search may then miss the physical entry for
        // this index. Fall back to a linear exact-index cleanup before the
        // item slot can be reused.
        //
        // (BTreeMap::retain does not re-sort the tree or recompute positions,
        // so a comparator guard isn't necessary.)
        self.items.retain(|stored_index, ()| stored_index.value() != index);
    }

    pub(crate) fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(ItemIndex) -> bool,
    {
        // We don't need to set up a comparator in the environment because
        // `retain` doesn't do any comparisons as part of its operation.
        self.items.retain(|index, ()| f(index.value()));
    }

    /// Rewrites every stored index via `remap`.
    ///
    /// Called after [`ItemSet::compact`] compacts the backing items buffer.
    /// Each stored `Index` needs to be rewritten to point at the item's new
    /// position.
    ///
    /// We do not rebuild the tree. [`IndexRemap`] preserves relative
    /// order, so the tree's iteration order — which is the user's
    /// `Ord` over items — matches before and after the rewrite. Only
    /// the stored index values change; node structure, pointers, and
    /// the user-visible total order are all preserved. The walk is
    /// O(N) with no comparator calls and no allocations.
    ///
    /// In-place mutation through `&Index` is provided by [`IndexCell`],
    /// which uses an `AtomicU32` for `&self`-based stores.
    ///
    /// [`ItemSet::compact`]: super::item_set::ItemSet::compact
    pub(crate) fn remap_indexes(&mut self, remap: &IndexRemap) {
        // Walk the B-tree twice: once to check every index, then once to
        // rewrite them.
        //
        // Why? `remap.remap` panics if compaction vacated the index. That can't
        // happen while the B-tree is structurally sound and only holds valid
        // indexes. But suppose it did, and we checked and rewrote in a single
        // walk. What would happen then?
        //
        // * The walk would rewrite some indexes, then panic on the bad one.
        // * The tree would be left half-rewritten.
        // * An index that was rewritten could now equal one that wasn't, so
        //   the tree would hold the same index twice, breaking the
        //   no-duplicate-index invariant.
        //
        // With two walks, the first one panics before anything is rewritten,
        // and the tree is unchanged.
        for idx in self.items.keys() {
            remap.remap(idx.value());
        }
        for idx in self.items.keys() {
            // SAFETY: We hold `&mut self`. `remap` is injective on the indexes
            // stored here (compaction assigns each occupied slot a distinct
            // new position), so distinct entries stay distinct. The check
            // pass above already established that no stored index maps to
            // `SENTINEL`.
            unsafe { idx.set_value(remap.remap(idx.value())) };
        }
    }

    /// Clears the B-tree table, removing all items.
    #[inline]
    pub(crate) fn clear(&mut self) {
        self.items.clear();
    }

    pub(crate) fn iter(&self) -> Iter<'_> {
        Iter::new(self.items.keys())
    }

    pub(crate) fn into_iter(self) -> IntoIter {
        IntoIter::new(self.items.into_iter())
    }

    pub(crate) fn state(&self) -> &foldhash::fast::FixedState {
        &self.hash_state
    }

    pub(crate) fn compute_hash<K: Hash>(&self, key: K) -> MapHash {
        MapHash { hash: self.hash_state.hash_one(key) }
    }
}

#[derive(Clone, Debug)]
pub(crate) struct Iter<'a> {
    inner: btree_map::Keys<'a, Index, ()>,
}

impl<'a> Iter<'a> {
    fn new(inner: btree_map::Keys<'a, Index, ()>) -> Self {
        Self { inner }
    }

    pub(crate) fn len(&self) -> usize {
        self.inner.len()
    }
}

impl<'a> Iterator for Iter<'a> {
    type Item = ItemIndex;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|index| index.value())
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

#[derive(Debug)]
pub(crate) struct IntoIter {
    inner: btree_map::IntoIter<Index, ()>,
}

impl IntoIter {
    fn new(inner: btree_map::IntoIter<Index, ()>) -> Self {
        Self { inner }
    }

    pub(crate) fn len(&self) -> usize {
        self.inner.len()
    }
}

impl Iterator for IntoIter {
    type Item = ItemIndex;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(index, ())| index.value())
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

pub(crate) struct PreparedBTreeInsert<'a> {
    entry: btree_map::VacantEntry<'a, Index, ()>,
}

impl PreparedBTreeInsert<'_> {
    pub(crate) fn insert(self) {
        self.entry.insert(());
    }
}

pub(crate) struct PreparedBTreeRemove<'a> {
    inner: PreparedBTreeRemoveInner<'a>,
}

enum PreparedBTreeRemoveInner<'a> {
    Occupied(btree_map::OccupiedEntry<'a, Index, ()>),
    Missing,
}

impl PreparedBTreeRemove<'_> {
    pub(crate) fn remove(self) -> bool {
        match self.inner {
            PreparedBTreeRemoveInner::Occupied(entry) => {
                entry.remove_entry();
                true
            }
            PreparedBTreeRemoveInner::Missing => false,
        }
    }
}

fn find_cmp<'a, K, Q, F>(
    key: &'a Q,
    lookup: F,
) -> impl Fn(&Index, &Index) -> Ordering + 'a
where
    Q: ?Sized + Comparable<K>,
    F: 'a + Fn(ItemIndex) -> K,
    K: Ord,
{
    move |a: &Index, b: &Index| {
        let (a, b) = (a.value(), b.value());
        if a == b {
            // Two entries with the same index are equal, whatever the user's
            // `Ord` says. This keeps the no-duplicate invariant in the module
            // docs: a lookup for an index that is already in the tree lands
            // on that entry, not beside it.
            return Ordering::Equal;
        }
        match (a, b) {
            (Index::SENTINEL_VALUE, v) => key.compare(&lookup(v)),
            (v, Index::SENTINEL_VALUE) => key.compare(&lookup(v)).reverse(),
            // The tiebreaker (then_with) in this arm preserves bijection when a
            // pathological user `Ord` returns `Equal` for distinct keys: if the
            // comparison returns equal, then the indexes are the same.
            (a, b) => lookup(a).cmp(&lookup(b)).then_with(|| a.cmp(&b)),
        }
    }
}

fn insert_cmp<'a, K, Q, F>(
    index: ItemIndex,
    key: &'a Q,
    lookup: F,
) -> impl Fn(&Index, &Index) -> Ordering + 'a
where
    Q: ?Sized + Comparable<K>,
    F: 'a + Fn(ItemIndex) -> K,
    K: Ord,
{
    move |a: &Index, b: &Index| {
        let (a, b) = (a.value(), b.value());
        if a == b {
            // Two entries with the same index are equal, whatever the user's
            // `Ord` says. Together with the tiebreakers below, this means the
            // comparator returns `Equal` only for the same index, which is
            // what `prepare_insert` and `prepare_remove` need to keep the
            // no-duplicate invariant in the module docs.
            return Ordering::Equal;
        }
        match (a, b) {
            // The sentinel value should not be invoked at all, because it's not
            // passed in during insert and not stored in the table.
            (Index::SENTINEL_VALUE, _) | (_, Index::SENTINEL_VALUE) => {
                panic!("sentinel value should not be invoked in insert path")
            }
            // The tiebreakers (then_with) in the arms below preserve bijection
            // when the user `Ord` returns `Equal` for distinct keys: if the
            // comparison returns equal, then the indexes are the same. Without
            // this, `BTreeMap::entry` could land on the wrong physical index
            // during `prepare_remove`.
            (a, b) if a == index => {
                key.compare(&lookup(b)).then_with(|| a.cmp(&b))
            }
            (a, b) if b == index => {
                key.compare(&lookup(a)).reverse().then_with(|| a.cmp(&b))
            }
            (a, b) => lookup(a).cmp(&lookup(b)).then_with(|| a.cmp(&b)),
        }
    }
}

struct CmpDropGuard<'a> {
    _marker: PhantomData<&'a ()>,
}

impl<'a> CmpDropGuard<'a> {
    fn new(f: &'a IndexCmp<'a>) -> Self {
        let ret = Self { _marker: PhantomData };

        // SAFETY: We store the transmuted reference in the `CMP` thread-local,
        // so we must show that nothing reads it after `f` is gone. Here's a
        // proof sketch:
        //
        // * The guard borrows `f` for `'a`, so `f` outlives the guard. Every
        //   caller declares `f` before the guard, so the guard drops
        //   first, including during unwinding.
        // * The guard's `Drop` sets `CMP` back to `None`.
        // * The only readers are `Index::cmp` and `Index::eq`. Each one copies
        //   the reference out of the `Cell`, calls it once, and discards it.
        //   Neither stores it.
        // * In a contrived scenario, a user `Ord` may itself reenter this (or
        //   some other) map and create a nested guard. The nested guard
        //   would overwrite `CMP` with its own live `f`, and its
        //   `Drop` would `CMP` to `None. The outer operation's next comparison
        //   would then panic with "cmp should be set" rather than calling
        //   through a dangling reference. Not great but also not UB, and
        //   not really worth paying the cost to maintain a stack of IndexCmp
        //   functions for.
        //
        // The transmute itself only changes lifetimes -- we assume here (as we
        // do elsewhere) that this doesn't change the layout of a type.
        let as_static = unsafe {
            std::mem::transmute::<&'a IndexCmp<'a>, &'static IndexCmp<'static>>(
                f,
            )
        };
        CMP.set(Some(as_static));

        ret
    }
}

impl Drop for CmpDropGuard<'_> {
    fn drop(&mut self) {
        CMP.set(None);
    }
}

/// An [`ItemIndex`] (= `u32`) with interior mutability, layout-identical
/// to `u32`.
///
/// Backed by `AtomicU32`. We use `Relaxed` ordering everywhere because
/// the only caller of `set` holds `&mut MapBTreeTable`, which excludes
/// every other reference — so there is never a race between a reader
/// and a writer. `Relaxed` loads compile to a plain `mov` on x86-64
/// and similar instructions on other architectures, so this gives us
/// interior mutability at the cost of a normal load.
///
/// Going through `AtomicU32` rather than `Cell<u32>` keeps us
/// naturally `Sync` without an `unsafe impl Sync` — `AtomicU32` is
/// designed to be accessed from multiple threads.
#[repr(transparent)]
#[derive(Debug, Default)]
struct IndexCell(core::sync::atomic::AtomicU32);

impl Clone for IndexCell {
    fn clone(&self) -> Self {
        Self(core::sync::atomic::AtomicU32::new(self.get().as_u32()))
    }
}

impl IndexCell {
    #[inline]
    const fn new(value: ItemIndex) -> Self {
        Self(core::sync::atomic::AtomicU32::new(value.as_u32()))
    }

    #[inline]
    fn get(&self) -> ItemIndex {
        ItemIndex::new(self.0.load(core::sync::atomic::Ordering::Relaxed))
    }

    /// Overwrite the stored value. The atomic store makes this safe to call
    /// through `&self` (though see the doc comment on `Index::set_value`
    /// below).
    #[inline]
    fn set(&self, value: ItemIndex) {
        debug_assert_ne!(
            value,
            ItemIndex::SENTINEL,
            "IndexCell::set: sentinel must never be stored in the table",
        );
        self.0.store(value.as_u32(), core::sync::atomic::Ordering::Relaxed);
    }
}

#[derive(Clone, Debug)]
struct Index(IndexCell);

impl Index {
    const SENTINEL_VALUE: ItemIndex = ItemIndex::SENTINEL;

    /// Returns a fresh sentinel `Index`.
    ///
    /// A function rather than an associated `const` because `IndexCell`
    /// wraps an `AtomicU32` (interior mutability), and a `const Self`
    /// would trigger `clippy::declare_interior_mutable_const` at every
    /// borrow site.
    #[inline]
    const fn sentinel() -> Self {
        Self(IndexCell::new(Self::SENTINEL_VALUE))
    }

    #[inline]
    fn new(value: ItemIndex) -> Self {
        if value == Self::SENTINEL_VALUE {
            panic!("btree map overflow, index with value {value:?} was added")
        }
        Self(IndexCell::new(value))
    }

    #[inline]
    fn value(&self) -> ItemIndex {
        self.0.get()
    }

    /// Overwrite the stored index value in place.
    ///
    /// This is unsafe because it rewrites a B-tree key and can break
    /// the no-duplicate invariant in the module docs.
    ///
    /// # Safety
    ///
    /// The caller must hold `&mut` on the enclosing [`MapBTreeTable`], and
    /// must ensure that after every `set_value` call in the same operation
    /// completes, no two entries in the table hold the same index and no
    /// entry holds [`ItemIndex::SENTINEL`].
    #[inline]
    unsafe fn set_value(&self, value: ItemIndex) {
        self.0.set(value)
    }
}

impl PartialEq for Index {
    fn eq(&self, other: &Self) -> bool {
        // For non-sentinel indexes, two values are the same iff their indexes
        // are the same. This is ensured by the fact that our key types
        // implement Eq (as part of implementing Ord).
        let (a, b) = (self.value(), other.value());
        if a != Self::SENTINEL_VALUE && b != Self::SENTINEL_VALUE {
            return a == b;
        }

        // If any of the two indexes is the sentinel, we're required to perform
        // a lookup.
        CMP.with(|cmp| {
            let cmp = cmp.get().expect("cmp should be set");
            cmp(self, other) == Ordering::Equal
        })
    }
}

impl Eq for Index {}

impl Ord for Index {
    #[inline]
    fn cmp(&self, other: &Self) -> Ordering {
        // Ord should only be called if we're doing lookups within the table,
        // which should have set the thread local.
        CMP.with(|cmp| {
            let cmp = cmp.get().expect("cmp should be set");
            cmp(self, other)
        })
    }
}

impl PartialOrd for Index {
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[cfg(all(test, feature = "std"))]
mod tests {
    use super::*;
    use crate::support::{alloc::Global, item_set::ItemSet};
    use core::cell::Cell;

    thread_local! {
        /// When set, `PanickingKey::cmp` panics on invocation. Scoped by
        /// individual tests.
        static PANIC_TRIGGER: Cell<bool> = const { Cell::new(false) };

        /// When set, `LyingKey::cmp` returns this ordering rather than
        /// comparing honestly. Scoped by individual tests.
        static LIE_ORD: Cell<Option<Ordering>> = const { Cell::new(None) };
    }

    /// A key type whose `Ord` impl can be made to panic on demand.
    #[derive(Clone, Debug, PartialEq, Eq)]
    struct PanickingKey(u32);

    impl PartialOrd for PanickingKey {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    impl Ord for PanickingKey {
        fn cmp(&self, other: &Self) -> Ordering {
            if PANIC_TRIGGER.with(|c| c.get()) {
                panic!("simulated Ord panic");
            }
            self.0.cmp(&other.0)
        }
    }

    /// A key type whose `Ord` impl can be told to return a fixed ordering on
    /// every call, to simulate adversarial user comparators.
    #[derive(Clone, Debug, PartialEq, Eq)]
    struct LyingKey(u32);

    impl PartialOrd for LyingKey {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    impl Ord for LyingKey {
        fn cmp(&self, other: &Self) -> Ordering {
            LIE_ORD.with(Cell::get).unwrap_or_else(|| self.0.cmp(&other.0))
        }
    }

    /// `remap_indexes` must not invoke the user-supplied `Ord` impl. We arm
    /// `PANIC_TRIGGER` for the duration of the call and verify the rebuild
    /// succeeds — any stray user-Ord invocation would panic the test.
    #[test]
    fn remap_indexes_does_not_call_user_ord() {
        // Build an IndexRemap with holes. This yields holes = [1, 3].
        let mut set: ItemSet<PanickingKey, Global> = ItemSet::new();
        for i in 0..5u32 {
            set.assert_can_grow().insert(PanickingKey(i * 10));
        }
        set.remove(ItemIndex::new(1));
        set.remove(ItemIndex::new(3));
        let remap = set.compact();
        set.shrink_capacity_to_fit();
        assert!(!remap.is_identity(), "remap should carry two holes");

        // A MapBTreeTable populated to match the pre-compaction live indexes
        // 0, 2, 4 — these are the indexes the outer map would have stored
        // before shrink. Setup uses the user `Ord`, so the trigger is off.
        let mut table = MapBTreeTable::new();
        let pre_lookup = |ix: ItemIndex| -> PanickingKey {
            match ix.as_u32() {
                0 => PanickingKey(0),
                2 => PanickingKey(20),
                4 => PanickingKey(40),
                _ => panic!("unexpected index in pre-compaction lookup: {ix}"),
            }
        };
        for ix in [0u32, 2, 4] {
            let ix = ItemIndex::new(ix);
            let key = pre_lookup(ix);
            table.prepare_insert(ix, &key, pre_lookup).insert();
        }
        assert_eq!(table.len(), 3);
        assert_eq!(
            table
                .items
                .keys()
                .map(|i| i.value().as_u32())
                .collect::<alloc::vec::Vec<_>>(),
            [0u32, 2, 4],
        );

        // Arm the trigger: any call into `PanickingKey::cmp` during the
        // rebuild below will panic this test.
        PANIC_TRIGGER.with(|c| c.set(true));
        table.remap_indexes(&remap);
        PANIC_TRIGGER.with(|c| c.set(false));

        // Remap 0 -> 0, 2 -> 1, 4 -> 2, and key order is preserved, so the
        // final contents must be [0, 1, 2].
        assert_eq!(
            table
                .items
                .keys()
                .map(|i| i.value().as_u32())
                .collect::<alloc::vec::Vec<_>>(),
            [0u32, 1, 2],
        );
    }

    /// If `remap_indexes` encounters an index that compaction vacated, it must
    /// panic before rewriting anything.
    #[test]
    fn remap_indexes_panics_before_rewriting_on_vacated_index() {
        let mut table = MapBTreeTable::new();
        let lookup = |ix: ItemIndex| -> u32 { ix.as_u32() };
        for ix in [0u32, 2, 4] {
            let ix = ItemIndex::new(ix);
            table.prepare_insert(ix, &lookup(ix), lookup).insert();
        }

        // 0 -> 0, 2 -> 1, and 4 is (wrongly) marked vacated.
        let remap = IndexRemap::Permuted(alloc::vec![
            ItemIndex::new(0),
            ItemIndex::SENTINEL,
            ItemIndex::new(1),
            ItemIndex::SENTINEL,
            ItemIndex::SENTINEL,
        ]);

        let result =
            std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
                table.remap_indexes(&remap)
            }));
        assert!(result.is_err(), "remap of a vacated index should panic");

        assert_eq!(
            table
                .items
                .keys()
                .map(|i| i.value().as_u32())
                .collect::<alloc::vec::Vec<_>>(),
            [0u32, 2, 4],
            "tree must be unchanged after the panic",
        );
    }

    /// Under a pathological user comparator that returns `Equal` for distinct
    /// keys, `prepare_insert` at a fresh index must not declare a spurious
    /// `Occupied` match.
    ///
    /// * Without the index tiebreaker in `insert_cmp`, `BTreeMap::entry` would
    ///   land on the first stored Index it visited and `prepare_insert` would
    ///   panic with "internal map already contains index".
    /// * With the tiebreaker, every comparison effectively becomes
    ///   `fresh_index.cmp(&stored)`, which is always non-equal for a fresh index,
    ///   so the descent reaches Vacant and the insert proceeds.
    ///
    /// This is a unit test rather than an integration test in pathological.rs
    /// because the path is somewhat hard to reach via the public API.
    /// `insert_unique` runs `find_index` first, which would return
    /// `Err(DuplicateItem)` before `prepare_insert` is ever called. We could in
    /// principle set things up to start lying after `find_index` but before
    /// `prepare_insert` (or extend our PBTs to generate random sequences of
    /// lying implementations), but this is more convenient.
    #[test]
    fn prepare_insert_under_lying_equal_does_not_spuriously_panic() {
        let mut table = MapBTreeTable::new();
        let lookup = |ix: ItemIndex| -> LyingKey { LyingKey(ix.as_u32() * 10) };

        // Populate four entries under honest ordering. Four is enough that
        // BTreeMap's root holds more than one key, so the descent below
        // actually invokes the comparator.
        for i in 0..4u32 {
            let ix = ItemIndex::new(i);
            let key = lookup(ix);
            table.prepare_insert(ix, &key, lookup).insert();
        }
        assert_eq!(table.len(), 4);

        // Arm the lie and prepare an insert at a fresh index. Under the
        // un-tiebroken comparator this panics inside `prepare_insert`.
        LIE_ORD.with(|c| c.set(Some(Ordering::Equal)));
        let fresh_ix = ItemIndex::new(100);
        let fresh_key = LyingKey(999);
        let prepared = table.prepare_insert(fresh_ix, &fresh_key, lookup);
        LIE_ORD.with(|c| c.set(None));

        prepared.insert();
        assert_eq!(table.len(), 5);
    }
}