mathtex-editor-core 0.3.0

//! Seeded random documents and command sequences, checking every invariant after every step.

use std::collections::HashSet;

use crate::doc::check_latex;
use crate::model::{Cursor, Kind, NodeId, SeqId, Tree};
use crate::*;

/// xorshift64star, enough to spread cases without a dependency.
struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 >> 12;
        self.0 ^= self.0 << 25;
        self.0 ^= self.0 >> 27;
        self.0.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    fn below(&mut self, n: usize) -> usize {
        (self.next() % n as u64) as usize
    }

    fn pick<T: Clone>(&mut self, items: &[T]) -> T {
        items[self.below(items.len())].clone()
    }

    fn chance(&mut self, percent: usize) -> bool {
        self.below(100) < percent
    }
}

const ATOMS: &[&str] = &["x", "y", "2", "+", "=", "\\alpha", "\\ ", "\\%", "\\mathbb{R}", "\\text{é}"];
const DELIMS: &[(char, char)] = &[('(', ')'), ('[', ']'), ('{', '}'), ('|', '|'), ('⟨', '⟩')];
const VARIANTS: &[Variant] = &[Variant::Bold, Variant::Text, Variant::Blackboard, Variant::OperatorName];
const DECOS: &[Deco] = &[Deco::None, Deco::Brace, Deco::Arrow, Deco::Line];
const ENVS: &[MatrixEnv] = &[MatrixEnv::Pmatrix, MatrixEnv::Array, MatrixEnv::Cases];

fn sym(rng: &mut Rng) -> Symbol {
    Symbol { latex: rng.pick(ATOMS).to_string(), class: MathClass::Ord }
}

fn op(rng: &mut Rng) -> Symbol {
    Symbol { latex: rng.pick(&["\\sum", "\\int", "\\bigcup"]).to_string(), class: MathClass::Op }
}

fn random_seq(rng: &mut Rng, depth: usize, max: usize) -> Vec<NodeDoc> {
    (0..rng.below(max + 1)).map(|_| random_node(rng, depth)).collect()
}

/// A valid node, structural only in the top three levels so documents stay small.
fn random_node(rng: &mut Rng, depth: usize) -> NodeDoc {
    if depth >= 3 || rng.chance(55) {
        return if rng.chance(90) { NodeDoc::Atom(sym(rng)) } else { NodeDoc::HostBox { token: rng.below(5) as u32 } };
    }
    let d = depth + 1;
    let seq = |rng: &mut Rng| random_seq(rng, d, 3);
    match rng.below(10) {
        0 => NodeDoc::Frac { num: seq(rng), den: seq(rng), style: rng.pick(&[FracStyle::Bar, FracStyle::Atop, FracStyle::Binom]) },
        1 => {
            let sub = rng.chance(50).then(|| seq(rng));
            let sup = if sub.is_none() || rng.chance(50) { Some(seq(rng)) } else { None };
            NodeDoc::Script { base: seq(rng), sub, sup }
        }
        2 => NodeDoc::BigOp { op: op(rng), lower: seq(rng), upper: seq(rng) },
        3 => NodeDoc::Sqrt { index: seq(rng), radicand: seq(rng) },
        4 => {
            let (open, close) = rng.pick(DELIMS);
            NodeDoc::Delim { open, close, body: seq(rng) }
        }
        5 => NodeDoc::Accent { mark: Mark::Hat, base: seq(rng) },
        6 => NodeDoc::UnderOver {
            base: seq(rng),
            over: rng.chance(60).then(|| seq(rng)),
            under: rng.chance(60).then(|| seq(rng)),
            over_deco: rng.pick(DECOS),
            under_deco: rng.pick(DECOS),
        },
        7 => {
            let variant = rng.pick(VARIANTS);
            let content = if variant == Variant::Text {
                (0..rng.below(3)).map(|_| NodeDoc::Atom(sym(rng))).collect()
            } else {
                seq(rng)
            };
            NodeDoc::Styled { variant, content }
        }
        _ => {
            let (rows, cols) = (1 + rng.below(2), 1 + rng.below(3));
            NodeDoc::Matrix { env: rng.pick(ENVS), rows: (0..rows).map(|_| (0..cols).map(|_| seq(rng)).collect()).collect() }
        }
    }
}

/// A chain of delimiters just under the depth cap, so inserts hit the limit.
fn deep_doc(depth: usize) -> Document {
    let mut nodes = vec![NodeDoc::Atom(Symbol { latex: "x".into(), class: MathClass::Ord })];
    for _ in 0..depth {
        nodes = vec![NodeDoc::Delim { open: '(', close: ')', body: nodes }];
    }
    Document::new(nodes)
}

fn all_seqs(tree: &Tree) -> Vec<SeqId> {
    let mut out = vec![tree.root()];
    let mut i = 0;
    while i < out.len() {
        for &n in tree.items(out[i]) {
            out.extend(tree.child_seqs(n));
        }
        i += 1;
    }
    out
}

fn random_path(rng: &mut Rng, ed: &Editor) -> CaretPath {
    let seqs = all_seqs(ed.tree());
    let seq = rng.pick(&seqs);
    let len = ed.tree().len(seq);
    // Occasionally past the end, which must be refused rather than trusted.
    let index = if rng.chance(5) { len + 1 } else { rng.below(len + 1) };
    ed.tree().path_of(Cursor { seq, index })
}

fn random_command(rng: &mut Rng, ed: &Editor) -> Command {
    let dir = rng.pick(&[Dir::Left, Dir::Right, Dir::Up, Dir::Down]);
    match rng.below(40) {
        0..=5 => Command::Move(dir),
        6 => rng.pick(&[Command::MoveLineStart, Command::MoveLineEnd, Command::Tab, Command::ShiftTab]),
        7 | 8 => Command::Extend(dir),
        9 => {
            let row = rng.below(4);
            rng.pick(&[Command::SelectAll, Command::Collapse, Command::Confirm, Command::MenuSelect(row)])
        }
        10 | 11 => Command::MoveTo(random_path(rng, ed)),
        12 => Command::ExtendTo(random_path(rng, ed)),
        13..=16 => Command::InsertAtom(sym(rng)),
        17 => Command::InsertText(rng.pick(&["ab", "a b", "%^'", "\t~"]).to_string()),
        18 => Command::InsertHostBox(rng.below(5) as u32),
        19 => Command::InsertFraction(rng.pick(&[FracStyle::Bar, FracStyle::Atop])),
        20 | 21 => Command::InsertScript(rng.pick(&[ScriptSlot::Sub, ScriptSlot::Sup])),
        22 => Command::InsertBigOp(op(rng)),
        23 => Command::InsertSqrt,
        24 => {
            let (open, close) = rng.pick(DELIMS);
            Command::InsertDelimiters { open, close }
        }
        25 => Command::InsertAccent(Mark::Vec),
        26 => Command::InsertUnderOver(UnderOverSpec {
            over: rng.chance(60),
            under: rng.chance(60),
            over_deco: rng.pick(DECOS),
            under_deco: rng.pick(DECOS),
        }),
        27 => Command::InsertStyled(rng.pick(VARIANTS)),
        28 => Command::InsertMatrix { env: rng.pick(ENVS), rows: rng.below(3), cols: rng.below(3) },
        29 => Command::InsertDocument(Document::new(random_seq(rng, 0, 2))),
        30..=33 => Command::DeleteBackward,
        34 | 35 => Command::DeleteForward,
        36 => rng.pick(&[
            Command::MatrixInsertRow(Side::After),
            Command::MatrixInsertCol(Side::Before),
            Command::MatrixDeleteRow,
            Command::MatrixDeleteCol,
        ]),
        37 => Command::ReplaceTyped {
            typed: rng.pick(&["x", "xy", "%"]).to_string(),
            with: vec![Command::InsertFraction(FracStyle::Bar), Command::InsertAtom(sym(rng))],
        },
        38 => Command::CloseDelimiter(rng.pick(&[')', ']', '|'])),
        _ => Command::InsertText("y".into()),
    }
}

/// Every seq and node is reachable exactly once, links agree both ways, and nothing leaks.
fn check_tree(tree: &Tree) {
    let mut seen_seqs = HashSet::new();
    let mut seen_nodes: HashSet<NodeId> = HashSet::new();
    let mut stack = vec![(tree.root(), None, 0usize)];
    while let Some((seq, owner, depth)) = stack.pop() {
        assert!(depth <= MAX_DEPTH, "depth {depth}");
        assert!(seen_seqs.insert(seq), "seq reached twice");
        let s = tree.seqs.get(seq).expect("reachable seq is live");
        assert_eq!(s.parent, owner, "seq parent link");
        for &n in &s.items {
            assert!(seen_nodes.insert(n), "node reached twice");
            let node = tree.nodes.get(n).expect("reachable node is live");
            assert_eq!(node.parent, seq, "node parent link");
            match &node.kind {
                Kind::Atom(sym) => assert_eq!(check_latex(&sym.latex), Ok(()), "{sym:?}"),
                Kind::BigOp { op, .. } => assert_eq!(check_latex(&op.latex), Ok(()), "{op:?}"),
                Kind::Script { sub, sup, .. } => assert!(sub.is_some() || sup.is_some(), "scriptless Script"),
                Kind::Matrix { rows, .. } => {
                    let cols = rows.first().map_or(0, Vec::len);
                    assert!(cols > 0 && rows.iter().all(|r| r.len() == cols), "matrix shape");
                }
                _ => {}
            }
            for c in tree.child_seqs(n) {
                stack.push((c, Some(n), depth + 1));
            }
        }
    }
    assert_eq!(seen_seqs.len(), tree.seqs.len(), "leaked seqs");
    assert_eq!(seen_nodes.len(), tree.nodes.len(), "leaked nodes");
}

fn check_editor(ed: &Editor) {
    let tree = ed.tree();
    check_tree(tree);
    let c = ed.raw_cursor();
    assert!(tree.seqs.contains_key(c.seq), "cursor seq is live");
    assert!(c.index <= tree.len(c.seq), "cursor in range");
    assert!(!crate::nav::is_illegal(tree, c), "cursor on an illegal gap");
    if let Some(a) = ed.raw_anchor() {
        assert!(a <= tree.len(c.seq), "anchor in range");
    }
    if let Some(m) = ed.menu_anchor() {
        assert!(tree.nodes.contains_key(m), "menu anchor is live");
    }
    assert_eq!(ed.caret_round_trips(), Ok(()));
    let doc = ed.document();
    assert_eq!(doc.validate(), Ok(()));
    let json = serde_json::to_string(&doc).unwrap();
    assert_eq!(serde_json::from_str::<Document>(&json).unwrap(), doc);
    assert_eq!(Tree::from_doc(&doc).to_doc(), doc);
    let src = ed.source();
    assert!(src.caret_offset(&ed.cursor()).is_some(), "caret has a source offset");
    let _ = ed.display_source();
    let _ = doc.to_tex();
    let _ = ed.selection_tex();
    let _ = ed.selection_document();
    let _ = ed.input_context();
    let _ = ed.render(&src, &mathtex_ir::Fragment::default()).unwrap();
    let snap = ed.snapshot();
    let mut other = Editor::new();
    other.restore(&snap).unwrap();
    assert_eq!(other.snapshot(), snap, "snapshot round trip");
}

impl Editor {
    /// The public view of the caret resolves back to the same position.
    fn caret_round_trips(&self) -> Result<(), PathError> {
        let resolved = self.tree().resolve(&self.cursor())?;
        assert_eq!(resolved, self.raw_cursor());
        Ok(())
    }
}

#[test]
fn random_edits_keep_every_invariant() {
    for seed in 1..=200u64 {
        let mut rng = Rng(seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1);
        let doc = if seed % 20 == 0 { deep_doc(MAX_DEPTH - 1) } else { Document::new(random_seq(&mut rng, 0, 4)) };
        assert_eq!(doc.validate(), Ok(()), "seed {seed} generated an invalid document");
        let mut ed = Editor::from_document(&doc).unwrap();
        assert_eq!(ed.document(), doc, "seed {seed} load");
        check_editor(&ed);
        for step in 0..60 {
            let cmd = random_command(&mut rng, &ed);
            let before = ed.document();
            let revision = ed.revision();
            let had_selection = ed.selection().is_some();
            let out = ed.exec(cmd.clone());
            let after = ed.document();
            let ctx = format!("seed {seed} step {step} {cmd:?}");
            // Replacing a selection or a typed run with equal content is still an edit.
            let may_rewrite_equal = had_selection || matches!(cmd, Command::ReplaceTyped { .. });
            assert!(out.changed || before == after, "{ctx}: unreported change");
            assert!(!out.changed || before != after || may_rewrite_equal, "{ctx}: spurious change");
            assert_eq!(out.revision, revision + u64::from(out.changed), "{ctx}: revision");
            check_editor(&ed);
        }
    }
}