notescraft/crates/collab/tests/props.rs

//! Randomised properties of the OT core and a three-client simulation, with a
//! tiny deterministic generator (no extra dependency).

use notescraft_collab::{Client, ClientState, Room, Submit, TextOp, transform};

/// The tiny LCG used by the sync property tests.
struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1_442_695_040_888_963_407);
        self.0 >> 33
    }

    fn below(&mut self, n: usize) -> usize {
        usize::try_from(self.next()).unwrap_or(0) % n.max(1)
    }
}

/// Characters the random texts draw from; several are multibyte on purpose.
const ALPHABET: [&str; 8] = ["a", "é", "日", "🌍", "b", "x", "ß", "字"];

fn random_text(rng: &mut Rng, max: usize) -> String {
    let count = 1 + rng.below(max);
    (0..count).map(|_| ALPHABET[rng.below(ALPHABET.len())]).collect()
}

/// At most this many parts in a random op, so generator loops provably end.
const MAX_PARTS: usize = 12;

fn random_op(rng: &mut Rng, len: usize) -> TextOp {
    let mut op = TextOp::new();
    let mut remaining = len;
    for _ in 0..MAX_PARTS {
        if remaining == 0 {
            break;
        }
        match rng.below(3) {
            0 => {
                let part = remaining.min(1 + rng.below(4));
                op = op.retain(part);
                remaining -= part;
            }
            1 => {
                let added = random_text(rng, 4);
                op = op.insert(&added);
            }
            _ => {
                let dropped = remaining.min(1 + rng.below(4));
                op = op.delete(dropped);
                remaining -= dropped;
            }
        }
        if remaining == 0 {
            break;
        }
    }
    if remaining > 0 {
        op = op.retain(remaining);
    }
    if rng.below(4) == 0 {
        op = op.insert(&random_text(rng, 4));
    }
    op
}

#[test]
fn compose_matches_sequential_apply() {
    let mut rng = Rng(7);
    for step in 0..500 {
        let base = random_text(&mut rng, 40);
        let a = random_op(&mut rng, base.chars().count());
        let mid = a.apply(&base).unwrap();
        let b = random_op(&mut rng, mid.chars().count());
        let combined = a.compose(&b).unwrap();
        let sequential = b.apply(&mid).unwrap();
        assert_eq!(
            combined.apply(&base).unwrap_or_else(|e| panic!(
                "step {step}: {e:?};\n  base={base:?};\n  a={:?};\n  b={:?};\n  combined={:?}",
                a.components(),
                b.components(),
                combined.components()
            )),
            sequential,
            "step {step}: compose(a, b) must equal b after a"
        );
    }
}

#[test]
fn invert_undoes_apply() {
    let mut rng = Rng(11);
    for step in 0..500 {
        let original = random_text(&mut rng, 40);
        let op = random_op(&mut rng, original.chars().count());
        let applied = op.apply(&original).unwrap();
        let undo = op.invert(&original).unwrap();
        assert_eq!(undo.base_len(), op.target_len(), "step {step}: inverted lengths");
        assert_eq!(undo.apply(&applied).unwrap(), original, "step {step}: undo");
    }
}

#[test]
fn transform_converges_tp1() {
    let mut rng = Rng(13);
    for step in 0..2000 {
        let base = random_text(&mut rng, 40);
        let a = random_op(&mut rng, base.chars().count());
        let b = random_op(&mut rng, base.chars().count());
        let (target_a, target_b) = transform(&a, &b).unwrap();
        let via_b = target_a.apply(&b.apply(&base).unwrap()).unwrap();
        let via_a = target_b.apply(&a.apply(&base).unwrap()).unwrap();
        assert_eq!(via_b, via_a, "step {step}: convergence");
    }
}

/// Longest queue delay, in rounds.
const MAX_DELAY: usize = 4;
/// Rounds where a client may type; the queues drain fully afterwards.
const TYPING_ROUNDS: usize = 60;

/// A message on a client's line: an accepted op or an ack, in order.
#[derive(Debug)]
enum PeerMsg {
    /// An accepted op (already transformed by the room) to apply.
    Op(TextOp),
    /// The room confirms this client's outstanding op.
    Ack,
}

use std::collections::VecDeque;

/// Three clients, one room, per-peer ordered lines and random delays.
struct Sim {
    rng: Rng,
    room: Room,
    clients: Vec<(Client, String)>,
    lines: Vec<VecDeque<PeerMsg>>,
    line_delay: Vec<u64>,
    room_in: VecDeque<(usize, Submit)>,
    room_delay: u64,
}

impl Sim {
    fn new(seed: u64, peers: usize) -> Self {
        Self {
            rng: Rng(seed),
            room: Room::new("start\n".into()),
            clients: (0..peers).map(|_| (Client::new(0), "start\n".to_owned())).collect(),
            lines: (0..peers).map(|_| VecDeque::new()).collect(),
            line_delay: vec![0; peers],
            room_in: VecDeque::new(),
            room_delay: 0,
        }
    }

    /// Each client may type a unique marker at a random place; the edit applies locally first.
    fn type_round(&mut self, round: usize, markers: &mut Vec<String>) {
        for (index, (client, text)) in self.clients.iter_mut().enumerate() {
            if self.rng.below(2) == 0 {
                continue;
            }
            let marker = format!("<c{index}r{round}>");
            markers.push(marker.clone());
            let len = text.chars().count();
            let at = self.rng.below(len + 1);
            let edit = TextOp::new().retain(at).insert(&marker).retain(len.saturating_sub(at));
            *text = edit.apply(text).unwrap();
            if let Some(submit) = client.local_edit(edit).unwrap() {
                self.room_in.push_back((index, submit));
            }
        }
    }

    /// The room takes the front submit (after its random delay) and fans the result out.
    fn room_tick(&mut self) {
        if self.room_delay > 0 {
            self.room_delay -= 1;
            return;
        }
        let Some((sender, submit)) = self.room_in.pop_front() else { return };
        let applied = self.room.submit(submit.base_rev, submit.op).unwrap_or_else(|error| panic!("room rejected submit: {error:?}"));
        for (peer, line) in self.lines.iter_mut().enumerate() {
            line.push_back(if peer == sender { PeerMsg::Ack } else { PeerMsg::Op(applied.op.clone()) });
        }
        self.room_delay = self.rng.below(MAX_DELAY) as u64;
    }

    /// Each peer's line delivers its front message unless delayed (`skip` adds random stalls while typing).
    fn peer_tick(&mut self, skip: bool) {
        for (peer, (client, text)) in self.clients.iter_mut().enumerate() {
            if let Some(delay) = self.line_delay.get_mut(peer).filter(|d| **d > 0) {
                *delay -= 1;
                continue;
            }
            if skip && self.rng.below(3) == 0 {
                continue;
            }
            let Some(message) = self.lines.get_mut(peer).and_then(VecDeque::pop_front) else { continue };
            match message {
                PeerMsg::Op(op) => {
                    let applied = client.remote_op(op).unwrap();
                    *text = applied.apply(text).unwrap();
                }
                PeerMsg::Ack => {
                    if let Some(submit) = client.server_ack().unwrap() {
                        self.room_in.push_back((peer, submit));
                    }
                }
            }
            if let Some(delay) = self.line_delay.get_mut(peer) {
                *delay = self.rng.below(MAX_DELAY) as u64;
            }
        }
    }

    fn quiet(&self) -> bool {
        self.room_in.is_empty() && self.lines.iter().all(VecDeque::is_empty)
    }
}

#[test]
fn three_clients_converge() {
    let mut sim = Sim::new(2026, 3);
    let mut markers: Vec<String> = Vec::new();
    for round in 0..TYPING_ROUNDS {
        sim.type_round(round, &mut markers);
        sim.room_tick();
        sim.peer_tick(true);
    }
    // Drain: keep ticking until every line and the room queue are empty.
    for _ in 0..2000 {
        if sim.quiet() {
            break;
        }
        sim.room_tick();
        sim.peer_tick(false);
    }
    assert!(sim.quiet(), "queues drained");
    // Quiescence: every client synchronized, at the room revision, equal text.
    for (client, text) in &sim.clients {
        assert!(matches!(client.state(), ClientState::Synchronized), "queues drained fully");
        assert_eq!(client.rev, sim.room.rev(), "revision caught up");
        assert_eq!(text, sim.room.text(), "documents equal the room text");
    }
    // No insert lost: typing adds only marker strings (later inserts may land inside an earlier
    // marker and split it, which is legal), so the final text is "start\n" plus every marker's characters.
    let final_text = sim.room.text();
    assert_eq!(
        final_text.chars().count(),
        "start\n".chars().count() + markers.iter().map(|m| m.chars().count()).sum::<usize>(),
        "typing added nothing but markers"
    );
    assert_eq!(final_text.chars().filter(|c| *c == '<').count(), markers.len(), "one opener per marker");
    assert_eq!(final_text.chars().filter(|c| *c == '>').count(), markers.len(), "one closer per marker");
}