minerva 0.2.0

//! Contract-form tests for the counted fragment arena.

use super::*;
use proptest::prelude::*;

/// A literal identity for the fixtures below (test machinery).
fn d(station: u32, counter: u64) -> Dot {
    Dot::from_parts(station, counter).expect("a test dot has a nonzero counter")
}

/// The splice's contract form: the same range moved through a plain
/// slot vector, agreement checked on every read the thread serves.
fn assert_agrees_with_slot_model(thread: &OrderThread, model: &[(Dot, bool)]) {
    thread.check_invariants();
    assert_eq!(thread.slot_len(), model.len(), "slot totals agree");
    let visible: Vec<Dot> = model
        .iter()
        .filter(|&&(_, seen)| seen)
        .map(|&(dot, _)| dot)
        .collect();
    assert_eq!(thread.visible_len(), visible.len(), "visible totals agree");
    for (k, &dot) in visible.iter().enumerate() {
        assert_eq!(thread.order_at(k), Some(dot), "selection agrees");
    }
    assert_eq!(thread.order_at(visible.len()), None, "out of range refuses");
    let mut visible_before = 0usize;
    for (slot, &(dot, seen)) in model.iter().enumerate() {
        assert_eq!(
            thread.position_of(dot),
            Some((slot, visible_before)),
            "positions agree"
        );
        if seen {
            visible_before += 1;
        }
    }
}

proptest! {
    /// The region splice's one law (the shell discipline applied to
    /// the fragment-grade re-placement, S204): over any run layout
    /// and any sequence of range moves, extract-then-insert agrees
    /// with the plain slot-vector model on every read, with the
    /// structural invariants held after every move.
    #[test]
    fn prop_splice_range_agrees_with_the_slot_model(
        runs in prop::collection::vec((0..3u8, 1..40u8, any::<bool>()), 1..8),
        moves in prop::collection::vec(
            (any::<u16>(), any::<u16>(), any::<u16>()),
            1..10,
        ),
    ) {
        // Materialize runs into unique dots: a rolling next index per
        // station, so same-station spans chain into fragments and
        // foreign spans break them.
        let mut next: BTreeMap<u32, u64> = BTreeMap::new();
        let mut model: Vec<(Dot, bool)> = Vec::new();
        for (station, len, seen) in runs {
            let station = u32::from(station);
            for _ in 0..len {
                let index = next.entry(station).or_insert(1);
                model.push((d(station, *index), seen));
                *index += 1;
            }
        }
        let mut thread = OrderThread::from_slots(model.iter().copied());
        assert_agrees_with_slot_model(&thread, &model);
        for (a, b, c) in moves {
            let n = model.len();
            let from = usize::from(a) % n;
            let len = 1 + usize::from(b) % (n - from);
            let to = usize::from(c) % (n - len + 1);
            let lifted = thread.extract_range(from, len);
            prop_assert_eq!(thread.slot_len(), n - len);
            let cut: Vec<(Dot, bool)> = model.drain(from..from + len).collect();
            thread.insert_fragments(to, lifted);
            for (k, entry) in cut.into_iter().enumerate() {
                model.insert(to + k, entry);
            }
            assert_agrees_with_slot_model(&thread, &model);
        }
    }
}

proptest! {
    /// The bulk run insert is the per-slot insert, exactly: over any
    /// base document and any sequence of chain-run insertions at
    /// arbitrary positions (fresh station-disjoint dots, mixed
    /// visibility, leaf-splitting lengths), `insert_run` agrees with
    /// the plain slot-vector model on every read, invariants held
    /// after every insertion.
    #[test]
    fn prop_insert_run_agrees_with_the_slot_model(
        runs in prop::collection::vec((0..2u8, 1..30u8, any::<bool>()), 0..4),
        inserts in prop::collection::vec(
            (any::<u16>(), 1..200u16, any::<bool>()),
            1..6,
        ),
    ) {
        let mut next: BTreeMap<u32, u64> = BTreeMap::new();
        let mut model: Vec<(Dot, bool)> = Vec::new();
        for (station, len, seen) in runs {
            let station = u32::from(station);
            for _ in 0..len {
                let index = next.entry(station).or_insert(1);
                model.push((d(station, *index), seen));
                *index += 1;
            }
        }
        let mut thread = OrderThread::from_slots(model.iter().copied());
        // Bulk runs mint fresh dots on a station of their own per
        // insertion, disjoint from the base and from each other.
        for (round, (position_salt, len, visible)) in inserts.into_iter().enumerate() {
            let station = 10 + u32::try_from(round).expect("test scale");
            let position = usize::from(position_salt) % (model.len() + 1);
            let len = u32::from(len);
            thread.insert_run(position, station, NonZeroU64::MIN, len, visible);
            for k in 0..u64::from(len) {
                model.insert(
                    position + usize::try_from(k).expect("test scale"),
                    (d(station, 1 + k), visible),
                );
            }
            thread.check_invariants();
            assert_agrees_with_slot_model(&thread, &model);
        }
    }
}

#[test]
fn a_bulk_run_lands_as_whole_fragments_and_coalesces_its_seam() {
    // A 200-slot run into a chain tail: the first 64 extend nothing
    // (foreign station), so the run lands as four fragments; pasting
    // the SAME station's next run at its own tail coalesces into the
    // existing fragment run exactly as per-slot typing would.
    let mut thread = OrderThread::new();
    for index in 1..=64u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    assert_eq!(thread.fragments(), 1);
    thread.insert_run(64, 1, NonZeroU64::new(65).unwrap(), 200, true);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 264);
    assert_eq!(
        thread.fragments(),
        5,
        "the run lands as whole fragments, the seam fragment full"
    );
    for index in 1..=264u64 {
        let k = usize::try_from(index).unwrap() - 1;
        assert_eq!(
            thread.position_of(d(1, index)).map(|(slot, _)| slot),
            Some(k)
        );
    }
    // An invisible run carries a zero mask.
    thread.insert_run(264, 2, NonZeroU64::MIN, 100, false);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 364);
    assert_eq!(thread.visible_len(), 264);
}

#[test]
fn a_range_splice_moves_fragments_wholesale() {
    // A 200-slot chain is four fragments under the cap; moving a
    // 100-slot interior range must carry fragments whole, splitting
    // only at the seams, never re-fragmenting the interior.
    let mut thread = OrderThread::new();
    for index in 1..=200u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    assert_eq!(thread.fragments(), 4);
    let lifted = thread.extract_range(50, 100);
    assert_eq!(thread.slot_len(), 100);
    thread.insert_fragments(0, lifted);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 200);
    assert_eq!(thread.order_at(0), Some(d(1, 51)));
    assert_eq!(thread.order_at(99), Some(d(1, 150)));
    assert_eq!(thread.order_at(100), Some(d(1, 1)));
    assert_eq!(thread.order_at(150), Some(d(1, 151)));
    assert!(
        thread.fragments() <= 7,
        "the splice fragments only at the seams"
    );
}

#[test]
fn a_returned_splice_coalesces_back() {
    // Moving a range out and straight back restores the original
    // fragment count: the seam coalescing that keeps move-and-undo
    // churn (the collation's unwind mechanics) from fragmenting the
    // thread permanently. Visibility masks ride the move intact.
    let mut thread = OrderThread::new();
    for index in 1..=128u64 {
        thread.insert_slot(
            usize::try_from(index).unwrap() - 1,
            d(1, index),
            index % 3 != 0,
        );
    }
    let baseline = thread.fragments();
    let visible = thread.visible_len();
    let lifted = thread.extract_range(32, 64);
    thread.insert_fragments(32, lifted);
    thread.check_invariants();
    assert_eq!(thread.fragments(), baseline, "the seams re-coalesce");
    assert_eq!(thread.visible_len(), visible, "the masks rode the move");
    for index in 1..=128u64 {
        let k = usize::try_from(index).unwrap() - 1;
        assert_eq!(
            thread.position_of(d(1, index)).map(|(slot, _)| slot),
            Some(k)
        );
    }
}

#[test]
fn an_extraction_heals_the_junction_it_opens() {
    // Removing a foreign range from a chain interior re-joins the
    // chain's two halves into one fragment: the source-junction
    // coalesce, the seam the insert-side repairs cannot reach.
    let mut thread = OrderThread::new();
    for index in 1..=40u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    thread.insert_slot(20, d(2, 1), true);
    assert_eq!(thread.fragments(), 3);
    let lifted = thread.extract_range(20, 1);
    thread.check_invariants();
    assert_eq!(thread.fragments(), 1, "the junction healed");
    thread.insert_fragments(40, lifted);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 41);
    assert_eq!(thread.order_at(40), Some(d(2, 1)));
}

#[test]
fn a_whole_document_splice_rebuilds() {
    // Extracting every slot drains the tree to empty; the insertion
    // rebuilds it bottom-up from the carried fragments, multi-level
    // (alternating stations force one fragment per slot).
    let mut thread = OrderThread::new();
    for (position, index) in (1..=300u64).enumerate() {
        thread.insert_slot(
            position,
            d(u32::try_from(index % 2).unwrap() + 1, index),
            index % 5 != 0,
        );
    }
    let lifted = thread.extract_range(0, 300);
    assert_eq!(thread.slot_len(), 0);
    thread.insert_fragments(0, lifted);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 300);
    for (k, index) in (1..=300u64).enumerate() {
        let dot = d(u32::try_from(index % 2).unwrap() + 1, index);
        assert_eq!(thread.position_of(dot).map(|(slot, _)| slot), Some(k));
    }
}

#[test]
fn a_splice_seam_at_the_dot_ceiling_refuses_overflow() {
    // The seam-coalescing probe rides checked arithmetic: a left
    // fragment ending at the dot ceiling has no successor, so the
    // seam stays split instead of overflowing (the S200/S201
    // discipline at the new probe).
    let mut thread = OrderThread::new();
    thread.insert_slot(0, d(1, u64::MAX), true);
    thread.insert_slot(1, d(2, 7), true);
    thread.insert_slot(2, d(1, 1), true);
    let lifted = thread.extract_range(1, 1);
    thread.check_invariants();
    assert_eq!(thread.order_at(0), Some(d(1, u64::MAX)));
    assert_eq!(thread.order_at(1), Some(d(1, 1)));
    thread.insert_fragments(2, lifted);
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 3);
    assert_eq!(thread.order_at(2), Some(d(2, 7)));
}

#[test]
fn nth_set_bit_selects_across_the_word() {
    let mask: u64 = 0b1011_0101;
    let expected = [0u32, 2, 4, 5, 7];
    for (k, &bit) in expected.iter().enumerate() {
        assert_eq!(nth_set_bit(mask, u32::try_from(k).unwrap()), bit);
    }
    assert_eq!(nth_set_bit(1u64 << 63, 0), 63);
}

#[test]
fn a_typed_run_coalesces_into_one_fragment() {
    let mut thread = OrderThread::new();
    for index in 1..=10u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    thread.check_invariants();
    assert_eq!(thread.fragments(), 1);
    assert_eq!(thread.slot_len(), 10);
    assert_eq!(thread.visible_len(), 10);
    for index in 1..=10u64 {
        let k = usize::try_from(index).unwrap() - 1;
        assert_eq!(thread.order_at(k), Some(d(1, index)));
        assert_eq!(thread.position_of(d(1, index)), Some((k, k)));
    }
    assert_eq!(thread.order_at(10), None);
}

#[test]
fn an_interior_insert_splits_the_fragment() {
    let mut thread = OrderThread::new();
    for index in 1..=6u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    // A foreign element lands between dots 3 and 4 in walk order.
    thread.insert_slot(3, d(2, 1), true);
    thread.check_invariants();
    assert_eq!(thread.fragments(), 3);
    assert_eq!(thread.order_at(3), Some(d(2, 1)));
    assert_eq!(thread.order_at(4), Some(d(1, 4)));
    assert_eq!(thread.position_of(d(1, 6)), Some((6, 6)));
}

#[test]
fn visibility_flips_move_the_aggregates_not_the_slots() {
    let mut thread = OrderThread::new();
    for index in 1..=8u64 {
        thread.insert_slot(usize::try_from(index).unwrap() - 1, d(1, index), true);
    }
    assert!(thread.set_visible(d(1, 3), false));
    assert!(thread.set_visible(d(1, 7), false));
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 8);
    assert_eq!(thread.visible_len(), 6);
    // Visible rank 2 skips the tombstone at dot 3.
    assert_eq!(thread.order_at(2), Some(d(1, 4)));
    // The tombstone still holds its slot: three slots and two visible
    // elements precede it.
    assert_eq!(thread.position_of(d(1, 3)), Some((2, 2)));
    assert_eq!(thread.position_of(d(1, 4)), Some((3, 2)));
    assert!(!thread.set_visible(d(9, 9), true), "unheld dots refuse");
}

#[test]
fn removal_splits_rebases_and_frees() {
    let mut thread = OrderThread::new();
    for index in 1..=5u64 {
        thread.insert_slot(
            usize::try_from(index).unwrap() - 1,
            d(1, index),
            index % 2 == 1,
        );
    }
    // Interior removal splits.
    assert!(thread.remove_slot(d(1, 3)));
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 4);
    assert_eq!(thread.fragments(), 2);
    // Head removal rebases.
    assert!(thread.remove_slot(d(1, 1)));
    thread.check_invariants();
    assert_eq!(thread.position_of(d(1, 2)), Some((0, 0)));
    // Tail removal truncates; the rest drain to empty.
    assert!(thread.remove_slot(d(1, 5)));
    assert!(thread.remove_slot(d(1, 4)));
    assert!(thread.remove_slot(d(1, 2)));
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 0);
    assert_eq!(thread.order_at(0), None);
    assert!(!thread.remove_slot(d(1, 2)), "a drained slot refuses");
}

#[test]
fn deep_documents_split_leaves_and_grow_levels() {
    let mut thread = OrderThread::new();
    // Alternate stations so nothing coalesces: every slot is its own
    // fragment, forcing leaf and internal splits.
    for (position, index) in (1..=200u64).enumerate() {
        thread.insert_slot(
            position,
            d(u32::try_from(index % 3).unwrap() + 1, index),
            true,
        );
    }
    thread.check_invariants();
    assert_eq!(thread.slot_len(), 200);
    assert_eq!(thread.fragments(), 200);
    for k in 0..200usize {
        let dot = thread.order_at(k).expect("every rank resolves");
        assert_eq!(thread.position_of(dot), Some((k, k)));
    }
}

/// The S200 gate review's finding, pinned at the structure: a fragment
/// based at the dot ceiling has no successor, so the tail-extend probe
/// must refuse by checked arithmetic rather than overflow, on both the
/// incremental and the bulk build.
#[test]
fn a_ceiling_fragment_refuses_extension_without_overflow() {
    let mut thread = OrderThread::new();
    thread.insert_slot(0, d(1, u64::MAX), true);
    // The next slot after the ceiling fragment probes extension; the
    // checked compare refuses and the slot lands as its own fragment.
    thread.insert_slot(1, d(1, 1), true);
    thread.check_invariants();
    assert_eq!(thread.fragments(), 2);
    assert_eq!(thread.order_at(0), Some(d(1, u64::MAX)));
    assert_eq!(thread.order_at(1), Some(d(1, 1)));

    let bulk = OrderThread::from_slots([(d(1, u64::MAX), true), (d(1, 1), true)]);
    bulk.check_invariants();
    assert_eq!(bulk.fragments(), 2);
    assert_eq!(bulk.order_at(0), Some(d(1, u64::MAX)));
    assert_eq!(bulk.order_at(1), Some(d(1, 1)));
}

#[test]
fn from_slots_agrees_with_incremental_builds() {
    let slots: Vec<(Dot, bool)> = (1..=100u64)
        .map(|index| {
            (
                d(1u32 + u32::try_from(index / 40).unwrap(), index),
                index % 3 != 0,
            )
        })
        .collect();
    let bulk = OrderThread::from_slots(slots.iter().copied());
    bulk.check_invariants();
    let mut incremental = OrderThread::new();
    for (position, &(dot, visible)) in slots.iter().enumerate() {
        incremental.insert_slot(position, dot, visible);
    }
    incremental.check_invariants();
    assert_eq!(bulk.slot_len(), incremental.slot_len());
    assert_eq!(bulk.visible_len(), incremental.visible_len());
    for k in 0..bulk.visible_len() {
        assert_eq!(bulk.order_at(k), incremental.order_at(k));
    }
    for &(dot, _) in &slots {
        assert_eq!(bulk.position_of(dot), incremental.position_of(dot));
    }
}