bbtree 0.1.7

//! Inline keys (D18) against std's `BTreeMap`: std byte-string keys with the
//! default strategy, looked up by every borrowed form; keys behind a long
//! shared prefix (D50), whose inline keys tie where the tree keeps none, and
//! keys that their inline keys hold whole; integers, and strings, whose nodes
//! keep 2 or 4 bytes of their inline keys and a hash tag of their own;
//! inline keys and hash tags that break their contract, which may give wrong
//! answers but never break memory safety; and an `InlineKey` that panics,
//! which leaves the map memory-safe (D48). The
//! fuzz targets run `Vec<u8>`, `u64` and `[u8; 16]` keys, and a newtype that
//! opts in, against std's map (`fuzz/src/map_differential.rs`).

#![forbid(unsafe_code)]

use core::borrow::Borrow;
use core::cell::Cell;
use core::cmp::Ordering;
use core::ops::Bound;
use core::panic::AssertUnwindSafe;
use std::boxed::Box;
use std::collections::BTreeMap;
use std::format;
use std::panic::catch_unwind;
use std::string::String;
use std::vec::Vec;

use super::differential::{MirroredMaps, Workload};
use super::prefix::shared_prefix_key;
use crate::inline_key::{InlineKey, InlineWidth, InlineWord, WithInlineKey};
use crate::tree::test_support::{DropLedger, FromNumber, HashTagCase, TestRng, Tracked};
use crate::unsync::map::BBTreeMap;

/// A built-in stored key can be borrowed through an unknown query type.
/// Its full ordering must remain available in every node.
#[test]
fn auto_strings_accept_an_unrecognized_borrowed_query() {
    trait TextQuery {
        fn text(&self) -> &str;
    }
    impl TextQuery for String {
        fn text(&self) -> &str {
            self
        }
    }
    impl PartialEq for dyn TextQuery {
        fn eq(&self, other: &Self) -> bool {
            self.text() == other.text()
        }
    }
    impl Eq for dyn TextQuery {}
    impl PartialOrd for dyn TextQuery {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }
    impl Ord for dyn TextQuery {
        fn cmp(&self, other: &Self) -> Ordering {
            self.text().cmp(other.text())
        }
    }
    impl Borrow<dyn TextQuery> for String {
        fn borrow(&self) -> &(dyn TextQuery + 'static) {
            self
        }
    }

    let prefix = "long\0shared/prefix/".repeat(4);
    let entries = (0..1024).map(|index| (format!("{prefix}{:04}", 2 * index), index));
    let mut ours: BBTreeMap<_, _> = entries.clone().collect();
    let mut theirs: BTreeMap<_, _> = entries.collect();
    for index in 0..2048 {
        let query = format!("{prefix}{index:04}");
        let borrowed: &dyn TextQuery = &query;
        assert_eq!(ours.get(borrowed), theirs.get(borrowed));
        assert_eq!(ours.get_mut(borrowed), theirs.get_mut(borrowed));
    }
    for query in [
        String::new(),
        String::from(&prefix[..31]),
        format!("{prefix}0000\0"),
    ] {
        let borrowed: &dyn TextQuery = &query;
        assert_eq!(ours.get(borrowed), theirs.get(borrowed));
        let bounds = (Bound::Included(borrowed), Bound::Unbounded);
        assert_eq!(
            ours.range::<dyn TextQuery, _>(bounds)
                .take(4)
                .collect::<Vec<_>>(),
            theirs
                .range::<dyn TextQuery, _>(bounds)
                .take(4)
                .collect::<Vec<_>>(),
        );
    }
    for index in (0..1024).step_by(3) {
        let query = format!("{prefix}{:04}", 2 * index);
        let borrowed: &dyn TextQuery = &query;
        assert_eq!(ours.remove(borrowed), theirs.remove(borrowed));
    }
    ours.check_invariants();
    assert!(ours.iter().eq(theirs.iter()));
}

/// A 27-byte head, then eight digits ([`shared_prefix_key`]): the tree keeps
/// the head, and the leading zeros of the digits, as its shared prefix
/// (D50), and its nodes take their windows past it.
impl FromNumber for Box<str> {
    fn from_number(number: usize) -> Self {
        shared_prefix_key(number).into_boxed_str()
    }
}

/// A newtype: not a std byte string, so it has inline keys only with
/// `WithInlineKey`.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct UserName(String);

impl InlineKey for UserName {
    fn inline_key_at(&self, offset: usize) -> InlineWord {
        self.0.inline_key_at(offset)
    }
}

impl FromNumber for UserName {
    fn from_number(number: usize) -> Self {
        Self(String::from_number(number))
    }
}

/// Half of the workloads' numbers below zero: the sign flip in the encoding
/// puts them first.
impl FromNumber for i64 {
    fn from_number(number: usize) -> Self {
        number as i64 - (1 << 12)
    }
}

/// Spread over the high half and into the low one: neighbours share the
/// high half, mostly, and differ in the low one, so windows cross the
/// halves.
impl FromNumber for u128 {
    fn from_number(number: usize) -> Self {
        (number as u128) << 56 | 0xabcd
    }
}

/// Half of the workloads' numbers below zero, as `i64`'s.
impl FromNumber for i128 {
    fn from_number(number: usize) -> Self {
        (number as i128 - (1 << 12)) << 40
    }
}

/// Ten digits, of whose inline keys the nodes keep `BYTES`, 2 or 4: past a
/// node's prefix, keys tie on them often, and the strings decide. All have
/// one length, so their hash tag is their last digit instead. Ties compare
/// as the strings' do, from where keys differ.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct NarrowName<const BYTES: usize>(String);

impl<const BYTES: usize> InlineKey for NarrowName<BYTES> {
    const WIDTH: InlineWidth = if BYTES == 2 {
        InlineWidth::Two
    } else {
        InlineWidth::Four
    };
    const HAS_HASH_TAG: bool = true;
    const HAS_CMP_FROM: bool = true;

    fn inline_key_at(&self, offset: usize) -> InlineWord {
        self.0.inline_key_at(offset)
    }

    fn hash_tag(&self) -> u8 {
        self.0.bytes().last().unwrap_or(0)
    }

    fn cmp_from(&self, other: &Self, equal_len: usize) -> Ordering {
        self.0.cmp_from(&other.0, equal_len)
    }
}

impl<const BYTES: usize> FromNumber for NarrowName<BYTES> {
    fn from_number(number: usize) -> Self {
        Self(String::from_number(number))
    }
}

/// A newtype that takes every hook of its string's impl: leaves keep 8
/// bytes of its inline keys and its hash tags, internal nodes 4 bytes, which
/// they read again from its keys as they move them (D43), ties compare from
/// where keys differ, and the check against what every key shares compares
/// 32 bytes at a time (D50), as for `Auto`'s strings.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct PathName(String);

impl InlineKey for PathName {
    const HAS_HASH_TAG: bool = true;
    const HAS_CMP_FROM: bool = true;

    fn inline_key_at(&self, offset: usize) -> InlineWord {
        self.0.inline_key_at(offset)
    }

    fn hash_tag(&self) -> u8 {
        self.0.hash_tag()
    }

    fn cmp_from(&self, other: &Self, equal_len: usize) -> Ordering {
        self.0.cmp_from(&other.0, equal_len)
    }

    fn cmp_prefix(&self, prefix: &[u8]) -> Ordering {
        self.0.cmp_prefix(prefix)
    }
}

/// Behind a long shared head ([`shared_prefix_key`]), as paths are.
impl FromNumber for PathName {
    fn from_number(number: usize) -> Self {
        Self(shared_prefix_key(number))
    }
}

/// A newtype with every hook matches std through inserts that split, and
/// removals that merge and move entries between nodes: the moves read
/// internal windows again from its keys.
#[test]
fn keys_with_every_hook_match_std() {
    let workload = Workload::new(10_000, 1 << 13);
    workload.run::<PathName, u64, WithInlineKey>(82);
    workload.run::<PathName, String, WithInlineKey>(83);
}

/// Keys behind a long shared head, which the tree keeps as its shared prefix
/// (D50). Then one key outside the head leaves the tree no shared prefix:
/// along its borders, where nodes take their windows from the keys' first
/// byte, every inline key ties, the search over them finds one run, the whole
/// node, and the full keys decide.
#[test]
fn keys_sharing_long_prefixes_match_std() {
    let rng = TestRng::new(66);
    let mut maps = MirroredMaps::<Box<str>, u64>::new();
    // Enough keys to put the leaves 2 below the root on 32-bit targets too,
    // whose internal nodes hold more edges.
    maps.run_random_operations(&rng, 8000, 1 << 13);
    maps.insert(Box::from("z"), 0);
    let keys: Vec<Box<str>> = maps.keys().cloned().collect();
    assert!(maps.ours().leaf_depth() >= 2);
    for step in maps.ours().inspect().trace(&*keys[0]) {
        assert_eq!(
            step.tied(),
            Some(0..step.node().len()),
            "the left border ties"
        );
    }
    for key in keys {
        maps.get_borrowed(&*key);
        maps.get_borrowed(&key[..key.len() - 1]);
    }
}

/// A random string of up to 14 bytes over a few characters, a NUL among
/// them: many are 8 bytes or fewer, which their inline keys hold whole, and
/// many share an inline key with another one of another length.
fn short_string(rng: &TestRng) -> String {
    let len = rng.below(8);
    (0..len)
        .map(|_| ['\0', 'a', 'b', 'é'][rng.below(4)])
        .collect()
}

/// Short keys, by `String`, `str` and `&str`: equal keys are told by their
/// length where the inline keys hold them whole, and only there.
#[test]
fn short_keys_match_std() {
    let rng = TestRng::new(68);
    let steps = if cfg!(miri) { 400 } else { 50_000 };
    let mut ours: BBTreeMap<String, u64> = BBTreeMap::new();
    let mut theirs: BTreeMap<String, u64> = BTreeMap::new();
    for step in 0..steps as u64 {
        let key = short_string(&rng);
        match rng.below(5) {
            0 | 1 => assert_eq!(ours.insert(key.clone(), step), theirs.insert(key, step)),
            2 => {
                assert_eq!(ours.get(key.as_str()), theirs.get(key.as_str()));
                assert_eq!(ours.get_key_value(&key), theirs.get_key_value(&key));
            }
            3 => assert_eq!(ours.remove(key.as_str()), theirs.remove(key.as_str())),
            _ => assert_eq!(ours.get_mut(key.as_str()), theirs.get_mut(key.as_str())),
        }
    }
    ours.check_invariants();
    assert_eq!(ours.len(), theirs.len());
    for (key, value) in &theirs {
        assert_eq!(ours.get(key.as_str()), Some(value));
    }

    // `&str` keys, borrowed from the strings above, by `&str` and by `str`.
    let mut borrowed: BBTreeMap<&str, u64> = BBTreeMap::new();
    for (key, value) in &theirs {
        borrowed.insert(key.as_str(), *value);
    }
    borrowed.check_invariants();
    for _ in 0..steps {
        let key = short_string(&rng);
        assert_eq!(borrowed.get(key.as_str()), theirs.get(key.as_str()));
        assert_eq!(borrowed.get(&key.as_str()), theirs.get(key.as_str()));
    }
}

/// Integers opt in, and their nodes keep 2 bytes of their inline keys:
/// signed, and 16 bytes wide, the last with zero-sized values, as in a set.
/// `u64` keys are fuzzed (`map_integers`).
#[test]
fn integer_keys_match_std() {
    let workload = Workload::new(10_000, 1 << 13);
    workload.run::<i64, u64, WithInlineKey>(77);
    workload.run::<u128, u64, WithInlineKey>(78);
    workload.run::<i128, (), WithInlineKey>(79);
}

/// An array's exact-key lookup may confirm its one candidate, the key whose
/// inline key is the query's, by equality alone (D38). Borrowed slices still
/// tell apart the key's prefixes, which pad to its inline key with zeros, and
/// a difference anywhere in the array counts.
#[test]
fn fixed_array_exact_key_lookups_match_std() {
    struct ArrayQueries;

    impl ArrayQueries {
        fn check<const N: usize>() {
            let mut ours = BBTreeMap::new();
            let mut theirs = BTreeMap::new();
            for number in 0..1024_u16 {
                let mut key = [0; N];
                key[..2].copy_from_slice(&number.to_be_bytes());
                ours.insert(key, number);
                theirs.insert(key, number);
            }
            ours.check_invariants();
            for (&key, &value) in &theirs {
                assert_eq!(ours.get(&key), Some(&value));
                assert_eq!(
                    ours.get_mut(key.as_slice()).map(|value| *value),
                    Some(value)
                );
                let mut query = key.to_vec();
                query.push(0);
                for len in 0..=query.len() {
                    let borrowed = &query[..len];
                    assert_eq!(ours.get(borrowed), theirs.get(borrowed));
                }
                for byte in 0..N {
                    let mut different = key;
                    different[byte] ^= 0x80;
                    assert_eq!(ours.get(&different), theirs.get(&different));
                }
            }
        }
    }

    ArrayQueries::check::<16>();
    ArrayQueries::check::<20>();
    ArrayQueries::check::<32>();
}

/// Strings whose nodes keep 2 or 4 bytes of their inline keys: runs of
/// tied inline keys are long, their hash tags narrow them, and the full keys
/// decide within what is left. The leaves keep the hash tags on 64-bit
/// targets.
#[test]
fn narrow_inline_keys_match_std() {
    let two_bytes_keep_tags = HashTagCase::leaves_keep_tags::<NarrowName<2>, String, WithInlineKey>;
    let four_bytes_keep_tags = HashTagCase::leaves_keep_tags::<NarrowName<4>, u64, WithInlineKey>;
    if cfg!(target_pointer_width = "64") {
        assert!(two_bytes_keep_tags() && four_bytes_keep_tags());
    }
    let workload = Workload::new(10_000, 1 << 13);
    workload.run::<NarrowName<2>, String, WithInlineKey>(80);
    workload.run::<NarrowName<4>, u64, WithInlineKey>(81);
}

/// A key's own hash tags narrow an exact-key lookup's candidates, as a std
/// string's lengths do: ten keys of one length tie on their 2-byte inline
/// keys in the one leaf, and only one has the query's last digit. An
/// outside key leaves the tree no shared prefix (D50).
#[test]
#[cfg_attr(not(target_pointer_width = "64"), ignore = "assumes 64-bit pointers")]
fn a_keys_own_hash_tags_narrow_its_candidates() {
    let name = |text: &str| NarrowName::<2>(String::from(text));
    let mut map = BBTreeMap::with_strategy(WithInlineKey);
    for digit in 0..10 {
        map.insert(name(&format!("k0-{digit}")), String::new());
    }
    map.insert(name("z"), String::new());
    assert_eq!(map.leaf_depth(), 0);
    let trace = map.inspect().trace(&name("k0-5"));
    let leaf = trace.last().expect("the lookup reads a leaf");
    let tied = leaf.tied().expect("the leaf has inline keys");
    assert_eq!(tied.len(), 10);
    let tags = tied.map(|index| leaf.node().hash_tag(index));
    assert_eq!(tags.filter(|&tag| tag == Some(b'5')).count(), 1);
    for digit in 0..10 {
        assert!(map.contains_key(&name(&format!("k0-{digit}"))));
    }
    assert!(!map.contains_key(&name("k0-x")));
    assert!(!map.contains_key(&name("k0-55")));
}

/// A key with a consistent `Ord` and an `InlineKey` that breaks its
/// contract in one of the ways of [`Lie`], in its inline keys, its hash tags
/// and its comparison from where keys differ. Its internal nodes keep 4
/// bytes, and read lying windows again as they move keys.
struct LyingKey<'r> {
    number: u32,
    lie: Lie,
    rng: &'r TestRng,
}

#[derive(Clone, Copy)]
enum Lie {
    /// The same inline key and hash tag for every key, and ties compared
    /// by `Ord`: consistent after all, as ties decide nothing, so answers
    /// stay right.
    Constant,
    /// Inline keys, and ties, ordered against the keys.
    Reversed,
    /// A random inline key, hash tag and order of ties on every call.
    Random,
}

impl PartialEq for LyingKey<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.number == other.number
    }
}

impl Eq for LyingKey<'_> {}

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 {
        self.number.cmp(&other.number)
    }
}

impl InlineKey for LyingKey<'_> {
    const HAS_HASH_TAG: bool = true;
    const HAS_CMP_FROM: bool = true;

    fn inline_key_at(&self, _offset: usize) -> InlineWord {
        match self.lie {
            Lie::Constant => 7,
            Lie::Reversed => InlineWord::from(u32::MAX - self.number),
            Lie::Random => self.rng.below(4) as InlineWord,
        }
    }

    fn hash_tag(&self) -> u8 {
        match self.lie {
            Lie::Constant => 7,
            Lie::Reversed => self.number as u8,
            Lie::Random => self.rng.below(4) as u8,
        }
    }

    fn cmp_from(&self, other: &Self, _equal_len: usize) -> Ordering {
        match self.lie {
            Lie::Constant => self.cmp(other),
            Lie::Reversed => other.cmp(self),
            Lie::Random => [Ordering::Less, Ordering::Equal, Ordering::Greater][self.rng.below(3)],
        }
    }
}

/// Inserts, looks up, removes and ranges over keys whose inline keys lie,
/// checking only what any map must do whatever its answers: every value
/// inserted is dropped once, and the map never holds more entries than were
/// inserted. Inline keys that tie everywhere ([`Lie::Constant`]) must also
/// leave a well-formed tree. Returns whether every answer matched std's.
fn run_with_lying_keys(lie: Lie, seed: u64) -> bool {
    let rng = TestRng::new(seed);
    let ledger = DropLedger::new();
    let (steps, key_space) = if cfg!(miri) {
        (180, 120)
    } else {
        (20_000, 4000)
    };
    let key = |number: usize| LyingKey {
        number: number as u32,
        lie,
        rng: &rng,
    };
    let mut ours: BBTreeMap<LyingKey<'_>, Tracked<'_>, WithInlineKey> =
        BBTreeMap::with_strategy(WithInlineKey);
    let mut theirs: BTreeMap<u32, ()> = BTreeMap::new();
    let mut all_right = true;
    let mut inserts = 0;
    for _ in 0..steps {
        let number = rng.below(key_space);
        match rng.below(5) {
            0 | 1 => {
                inserts += 1;
                let replaced = ours.insert(key(number), ledger.track()).is_some();
                all_right &= replaced == theirs.insert(number as u32, ()).is_some();
            }
            2 => {
                let found = ours.get(&key(number)).is_some();
                all_right &= found == theirs.contains_key(&(number as u32));
            }
            3 => {
                let removed = ours.remove(&key(number)).is_some();
                all_right &= removed == theirs.remove(&(number as u32)).is_some();
            }
            _ if rng.below(8) == 0 => {
                let popped = ours.pop_first().map(|(key, _)| key.number);
                all_right &= popped == theirs.pop_first().map(|(number, ())| number);
            }
            _ if rng.below(8) == 0 => {
                // The bounds are in order, but inline keys that lie may find
                // the start after the end, which panics as an ill-defined
                // `Ord` does.
                let high = number + rng.below(64);
                let ranged = catch_unwind(AssertUnwindSafe(|| {
                    let range = ours.range(key(number)..key(high));
                    range.map(|(key, _)| key.number).collect::<Vec<u32>>()
                }));
                let expected = theirs.range(number as u32..high as u32);
                let expected: Vec<u32> = expected.map(|(&number, ())| number).collect();
                all_right &= ranged.is_ok_and(|numbers| numbers == expected);
            }
            _ => {
                if let Some(value) = ours.get_mut(&key(number)) {
                    *value = ledger.track();
                }
            }
        }
        assert!(ours.len() <= inserts);
        // Lying inline keys may leave the keys unordered: check what holds
        // anyway, each node's prefix length against its parent's, which
        // calls no `InlineKey`.
        ours.check_prefix_lens();
    }
    assert!(ours.len() <= inserts);
    if matches!(lie, Lie::Constant) {
        ours.check_invariants();
    }
    drop(ours);
    ledger.assert_all_dropped_once();
    all_right
}

/// Inline keys that tie everywhere: right answers, and a well-formed tree.
/// The leaves keep the keys' hash tags on 64-bit targets.
#[test]
fn inline_keys_that_tie_everywhere_give_right_answers() {
    let keep_tags = HashTagCase::leaves_keep_tags::<LyingKey<'_>, Tracked<'_>, WithInlineKey>;
    assert_eq!(keep_tags(), cfg!(target_pointer_width = "64"));
    assert!(run_with_lying_keys(Lie::Constant, 72));
}

/// Wrong answers, as the contract allows, but never out of bounds: Miri
/// checks every access in CI.
#[test]
#[cfg_attr(panic = "abort", ignore = "needs unwinding")]
fn wrong_inline_keys_stay_memory_safe() {
    let _ = run_with_lying_keys(Lie::Reversed, 73);
    let _ = run_with_lying_keys(Lie::Random, 74);
}

/// A name whose `InlineKey` panics once its shared budget of calls is spent,
/// and then not again until given a new budget: a second panic while the
/// first unwinds would abort.
struct PanickingName<'b> {
    name: UserName,
    budget: &'b Cell<usize>,
}

impl PartialEq for PanickingName<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.name == other.name
    }
}

impl Eq for PanickingName<'_> {}

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

impl Ord for PanickingName<'_> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.name.cmp(&other.name)
    }
}

impl InlineKey for PanickingName<'_> {
    fn inline_key_at(&self, offset: usize) -> InlineWord {
        match self.budget.get().checked_sub(1) {
            Some(left) => self.budget.set(left),
            None => {
                self.budget.set(usize::MAX);
                panic!("inline key panic");
            }
        }
        self.name.inline_key_at(offset)
    }
}

/// An `InlineKey` that panics in the middle of inserts and removals, which
/// split, merge and refit nodes, leaves a map that is still memory-safe to
/// search, change and drop (D48): the map calls it only before a change, or
/// after the entry is in or out and counted, so its length still counts its
/// entries, which its walks rely on. A refit it stops may leave a node's
/// inline keys off its prefix, which only makes searches wrong.
#[test]
#[cfg_attr(panic = "abort", ignore = "needs unwinding")]
fn a_panicking_inline_key_leaves_a_sound_map() {
    let rng = TestRng::new(96);
    let budget = Cell::new(usize::MAX);
    let (steps, key_space) = if cfg!(miri) {
        (300, 300)
    } else {
        (20_000, 6000)
    };
    let key = |number: usize| PanickingName {
        name: UserName::from_number(number),
        budget: &budget,
    };
    let mut map: BBTreeMap<PanickingName<'_>, usize, WithInlineKey> =
        BBTreeMap::with_strategy(WithInlineKey);
    let mut panics = 0;
    for step in 0..steps {
        let number = rng.below(key_space);
        let insert = rng.below(3) != 0;
        budget.set(rng.below(40));
        let changed = catch_unwind(AssertUnwindSafe(|| {
            if insert {
                map.insert(key(number), step);
            } else {
                map.remove(&key(number));
            }
        }));
        budget.set(usize::MAX);
        if changed.is_err() {
            panics += 1;
            map.get(&key(number));
        }
    }
    assert!(panics > 0);
    assert_eq!(map.len(), map.iter().count());
    assert_eq!(map.len(), map.iter().rev().count());
}

/// An `InlineKey` that panics while `retain` or `extract_if` removes entries,
/// or while `append` builds a tree of the entries it keeps, loses at most the
/// entries it was moving: the map counts only those it holds, every value is
/// dropped once, none leaked, and the tree's borders keep its shared prefix
/// (D50), so that a key past the last goes in last. The panic lands on every
/// call in turn: computing an entry's inline key, fitting the prefix of a node
/// a new leaf closes or a removal changed, and fitting the border when the
/// merge finishes.
#[test]
#[cfg_attr(panic = "abort", ignore = "needs unwinding")]
fn a_panicking_inline_key_in_a_bulk_change_leaves_a_valid_map() {
    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
    enum BulkChange {
        Retain,
        ExtractIfAll,
        ExtractIfRange,
        /// Appends the upper half to the lower: the merge takes all of the
        /// lower half first, and a panic leaves nothing of it to take after.
        Append,
    }
    let budget = Cell::new(usize::MAX);
    let ledger = DropLedger::new();
    let count = if cfg!(miri) { 30 } else { 120 };
    let key = |number: usize| PanickingName {
        name: UserName::from_number(number),
        budget: &budget,
    };
    // Runs `change` on fresh maps, the `left`-th call of `InlineKey`
    // panicking; returns the calls left.
    let run = |change: BulkChange, left: usize| {
        let mut map: BBTreeMap<PanickingName<'_>, Tracked<'_>, WithInlineKey> =
            BBTreeMap::with_strategy(WithInlineKey);
        let mut other = BBTreeMap::with_strategy(WithInlineKey);
        for number in 0..count {
            let target = if change == BulkChange::Append && number >= count / 2 {
                &mut other
            } else {
                &mut map
            };
            target.insert(key(number), ledger.track());
        }
        let mut position = 0;
        let mut every_third = |_: &PanickingName<'_>, _: &mut Tracked<'_>| {
            position += 1;
            position % 3 == 0
        };
        budget.set(left);
        let _ = catch_unwind(AssertUnwindSafe(|| match change {
            BulkChange::Retain => map.retain(|key, value| !every_third(key, value)),
            BulkChange::ExtractIfAll => {
                map.extract_if(.., &mut every_third)
                    .take(count / 10)
                    .for_each(drop);
            }
            BulkChange::ExtractIfRange => {
                map.extract_if(key(count / 4)..key(3 * count / 4), &mut every_third)
                    .take(count / 10)
                    .for_each(drop);
            }
            BulkChange::Append => map.append(&mut other),
        }));
        let calls_left = budget.replace(usize::MAX);
        assert_eq!(map.len(), map.iter().count(), "{change:?}, budget {left}");
        assert_eq!(
            map.len(),
            map.iter().rev().count(),
            "{change:?}, budget {left}"
        );
        map.check_prefix_lens();
        map.insert(key(count), ledger.track());
        assert!(
            map.keys().is_sorted(),
            "{change:?}, budget {left}: a key past the last went in elsewhere"
        );
        calls_left
    };
    for change in [
        BulkChange::Retain,
        BulkChange::ExtractIfAll,
        BulkChange::ExtractIfRange,
        BulkChange::Append,
    ] {
        let calls = usize::MAX - run(change, usize::MAX);
        let step = if cfg!(miri) { calls / 8 + 1 } else { 1 };
        for left in (0..calls).step_by(step) {
            run(change, left);
            ledger.assert_all_dropped_once();
        }
    }
}