mathtex-editor-core 0.3.0

//! The document and clipboard format, an id free nested tree rebuilt into slotmap storage on load.

use std::collections::BTreeSet;
use std::fmt;

use serde::{de, Deserialize, Deserializer, Serialize};

use crate::model::{Deco, FracStyle, Kind, Mark, MatrixEnv, NodeId, SeqId, Symbol, Tree, Variant};

/// The current serialized document format version.
pub const DOCUMENT_VERSION: u32 = 1;

/// Deepest allowed slot nesting, sized so a document stays under serde_json's recursion limit of 128.
pub const MAX_DEPTH: usize = 20;

/// Largest host box token, since TeX reads the `N` of `\hostbox{N}` as an integer of at most 2^31 - 1.
pub const MAX_HOST_TOKEN: u32 = i32::MAX as u32;

/// Delimiter characters a `Delim` node may carry, `.` is the invisible delimiter.
pub(crate) const DELIMITERS: &[char] =
    &['(', ')', '[', ']', '{', '}', '|', '‖', '/', '.', '⌈', '⌉', '⌊', '⌋', '⟨', '⟩'];

/// A whole document, the unit of persistence and of the clipboard, see the README for its JSON shape.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(try_from = "RawDocument")]
pub struct Document {
    version: u32,
    root: Vec<NodeDoc>,
}

#[derive(Deserialize)]
struct RawDocument {
    #[serde(deserialize_with = "deserialize_version")]
    version: u32,
    root: Vec<NodeDoc>,
}

impl TryFrom<RawDocument> for Document {
    type Error = DocumentError;

    fn try_from(raw: RawDocument) -> Result<Self, Self::Error> {
        let doc = Document { version: raw.version, root: raw.root };
        doc.validate()?;
        Ok(doc)
    }
}

fn deserialize_version<'de, D>(deserializer: D) -> Result<u32, D::Error>
where
    D: Deserializer<'de>,
{
    let version = u32::deserialize(deserializer)?;
    if version == DOCUMENT_VERSION {
        Ok(version)
    } else {
        Err(de::Error::custom(format_args!(
            "unsupported document version {version}, expected {DOCUMENT_VERSION}"
        )))
    }
}

impl Default for Document {
    fn default() -> Self {
        Self::new(Vec::new())
    }
}

impl Document {
    /// Build a document holding `root` in the current format version.
    pub fn new(root: Vec<NodeDoc>) -> Self {
        Self { version: DOCUMENT_VERSION, root }
    }

    /// The serialized format version.
    pub fn version(&self) -> u32 {
        self.version
    }

    /// The nodes in the root sequence.
    pub fn root(&self) -> &[NodeDoc] {
        &self.root
    }

    /// Number of nodes in the root sequence.
    pub fn len(&self) -> usize {
        self.root.len()
    }

    /// Whether the root sequence is empty.
    pub fn is_empty(&self) -> bool {
        self.root.is_empty()
    }

    /// Consume the document and return its root sequence.
    pub fn into_root(self) -> Vec<NodeDoc> {
        self.root
    }

    /// Check every structural rule that deserialization enforces.
    pub fn validate(&self) -> Result<(), DocumentError> {
        validate_seq(&self.root, 0)
    }

    /// Call `f` on every node in document order, parents before their slots.
    pub fn visit(&self, mut f: impl FnMut(&NodeDoc)) {
        visit_nodes(&self.root, &mut f);
    }

    /// Fix everything [`Document::validate`] rejects and report each change, in document order.
    pub fn repair(&mut self) -> Vec<Repair> {
        let mut out = Vec::new();
        repair_seq(&mut self.root, 0, &mut out);
        out
    }

    /// Call `f` on every node in document order, [`Document::validate`] tells whether the result is still valid.
    pub fn visit_mut(&mut self, mut f: impl FnMut(&mut NodeDoc)) {
        visit_nodes_mut(&mut self.root, &mut f);
    }

    /// Every host box token in the document.
    pub fn host_tokens(&self) -> BTreeSet<u32> {
        let mut out = BTreeSet::new();
        self.visit(|n| {
            if let NodeDoc::HostBox { token } = n {
                out.insert(*token);
            }
        });
        out
    }

    /// Rewrite every host box token, for example after minting fresh tokens on paste.
    pub fn map_host_tokens(&mut self, mut f: impl FnMut(u32) -> u32) {
        self.visit_mut(|n| {
            if let NodeDoc::HostBox { token } = n {
                *token = f(*token);
            }
        });
    }

    /// Clean LaTeX with empty placeholders dropped, host boxes stay `\hostbox{N}`.
    pub fn to_tex(&self) -> String {
        self.to_tex_with(|_| None)
    }

    /// Clean LaTeX where `host_box` supplies each host box's content, `None` keeps `\hostbox{N}`.
    pub fn to_tex_with(&self, mut host_box: impl FnMut(u32) -> Option<String>) -> String {
        let tree = Tree::from_doc(self);
        crate::export::clean_tex(&tree, Some(&mut host_box))
    }

    /// Extra slot levels the nodes add below the sequence they are pasted into.
    pub(crate) fn height(&self) -> usize {
        seq_height(&self.root)
    }
}

/// A rule broken by a document.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DocumentError {
    /// An atom or big operator symbol whose LaTeX is unsafe to splice into the output.
    InvalidSymbol {
        /// The offending LaTeX.
        latex: String,
        /// What is wrong with it.
        reason: &'static str,
    },
    /// A matrix without any row or column.
    EmptyMatrix,
    /// A matrix whose rows differ in length.
    RaggedMatrix,
    /// A script with neither a subscript nor a superscript.
    EmptyScript,
    /// Slots nest deeper than [`MAX_DEPTH`].
    TooDeep,
    /// A delimiter outside the supported set.
    UnsupportedDelimiter(char),
    /// A host box token above [`MAX_HOST_TOKEN`].
    HostTokenTooLarge(u32),
}

impl fmt::Display for DocumentError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            DocumentError::InvalidSymbol { latex, reason } => write!(f, "symbol {latex:?} {reason}"),
            DocumentError::EmptyMatrix => write!(f, "matrix has no cells"),
            DocumentError::RaggedMatrix => write!(f, "matrix rows differ in length"),
            DocumentError::EmptyScript => write!(f, "script has neither subscript nor superscript"),
            DocumentError::TooDeep => write!(f, "slots nest deeper than {MAX_DEPTH}"),
            DocumentError::UnsupportedDelimiter(c) => write!(f, "unsupported delimiter {c:?}"),
            DocumentError::HostTokenTooLarge(t) => write!(f, "host box token {t} is above {MAX_HOST_TOKEN}"),
        }
    }
}

impl std::error::Error for DocumentError {}

/// One change [`Document::repair`] made.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Repair {
    /// Dropped an atom or big operator whose symbol LaTeX is unsafe.
    DroppedSymbol {
        /// The dropped LaTeX.
        latex: String,
    },
    /// Dropped a structure whose slots would nest deeper than [`MAX_DEPTH`].
    DroppedTooDeep,
    /// Dropped a host box whose token is above [`MAX_HOST_TOKEN`].
    DroppedHostBox {
        /// The dropped token.
        token: u32,
    },
    /// Gave a script with neither a subscript nor a superscript an empty superscript.
    AddedSuperscript,
    /// Replaced an unsupported delimiter with the invisible `.`.
    ReplacedDelimiter {
        /// The unsupported delimiter.
        found: char,
    },
    /// Padded ragged matrix rows with empty cells, or gave a matrix without cells one empty cell.
    PaddedMatrix,
}

impl fmt::Display for Repair {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Repair::DroppedSymbol { latex } => write!(f, "dropped symbol {latex:?}"),
            Repair::DroppedTooDeep => write!(f, "dropped a structure nested deeper than {MAX_DEPTH}"),
            Repair::DroppedHostBox { token } => write!(f, "dropped host box token {token}"),
            Repair::AddedSuperscript => write!(f, "gave a script without scripts an empty superscript"),
            Repair::ReplacedDelimiter { found } => write!(f, "replaced unsupported delimiter {found:?}"),
            Repair::PaddedMatrix => write!(f, "padded a matrix to a rectangle"),
        }
    }
}

fn repair_seq(nodes: &mut Vec<NodeDoc>, depth: usize, out: &mut Vec<Repair>) {
    nodes.retain_mut(|n| repair_node(n, depth, out));
}

/// Repair one node in a sequence at `depth` and its slots, `false` drops it.
fn repair_node(n: &mut NodeDoc, depth: usize, out: &mut Vec<Repair>) -> bool {
    if n.is_structural() && depth + 1 > MAX_DEPTH {
        out.push(Repair::DroppedTooDeep);
        return false;
    }
    match n {
        NodeDoc::Atom(s) | NodeDoc::BigOp { op: s, .. } if check_latex(&s.latex).is_err() => {
            out.push(Repair::DroppedSymbol { latex: s.latex.clone() });
            return false;
        }
        NodeDoc::HostBox { token } if *token > MAX_HOST_TOKEN => {
            out.push(Repair::DroppedHostBox { token: *token });
            return false;
        }
        NodeDoc::Script { sub: None, sup: sup @ None, .. } => {
            *sup = Some(Vec::new());
            out.push(Repair::AddedSuperscript);
        }
        NodeDoc::Delim { open, close, .. } => {
            for c in [open, close] {
                if !DELIMITERS.contains(&*c) {
                    out.push(Repair::ReplacedDelimiter { found: *c });
                    *c = '.';
                }
            }
        }
        NodeDoc::Matrix { rows, .. } => {
            let cols = rows.iter().map(Vec::len).max().unwrap_or(0).max(1);
            if rows.is_empty() || rows.iter().any(|r| r.len() != cols) {
                rows.resize_with(rows.len().max(1), Vec::new);
                for row in rows.iter_mut() {
                    row.resize_with(cols, Vec::new);
                }
                out.push(Repair::PaddedMatrix);
            }
        }
        _ => {}
    }
    for slot in n.slots_mut() {
        repair_seq(slot, depth + 1, out);
    }
    true
}

/// Reject LaTeX that could escape its atom: stray braces, comment or math shift characters, controls.
pub(crate) fn check_latex(latex: &str) -> Result<(), &'static str> {
    if latex.is_empty() {
        return Err("is empty");
    }
    let mut depth = 0usize;
    let mut chars = latex.chars();
    while let Some(c) = chars.next() {
        if c.is_control() {
            return Err("contains a control character");
        }
        match c {
            '\\' => match chars.next() {
                None => return Err("ends in a lone backslash"),
                Some(n) if n.is_control() => return Err("contains a control character"),
                Some(_) => {}
            },
            '{' => depth += 1,
            '}' => depth = depth.checked_sub(1).ok_or("has unbalanced braces")?,
            '%' | '$' | '#' | '&' => return Err("contains an unescaped % $ # or &"),
            _ => {}
        }
    }
    if depth == 0 { Ok(()) } else { Err("has unbalanced braces") }
}

fn check_symbol(s: &Symbol) -> Result<(), DocumentError> {
    check_latex(&s.latex).map_err(|reason| DocumentError::InvalidSymbol { latex: s.latex.clone(), reason })
}

fn validate_seq(nodes: &[NodeDoc], depth: usize) -> Result<(), DocumentError> {
    for n in nodes {
        match n {
            NodeDoc::Atom(s) => check_symbol(s)?,
            NodeDoc::BigOp { op, .. } => check_symbol(op)?,
            NodeDoc::HostBox { token } if *token > MAX_HOST_TOKEN => {
                return Err(DocumentError::HostTokenTooLarge(*token));
            }
            NodeDoc::Script { sub: None, sup: None, .. } => return Err(DocumentError::EmptyScript),
            NodeDoc::Delim { open, close, .. } => {
                for c in [*open, *close] {
                    if !DELIMITERS.contains(&c) {
                        return Err(DocumentError::UnsupportedDelimiter(c));
                    }
                }
            }
            NodeDoc::Matrix { rows, .. } => {
                let cols = rows.first().map_or(0, Vec::len);
                if cols == 0 {
                    return Err(DocumentError::EmptyMatrix);
                }
                if rows.iter().any(|r| r.len() != cols) {
                    return Err(DocumentError::RaggedMatrix);
                }
            }
            _ => {}
        }
        let slots = n.slots();
        if !slots.is_empty() && depth + 1 > MAX_DEPTH {
            return Err(DocumentError::TooDeep);
        }
        for s in slots {
            validate_seq(s, depth + 1)?;
        }
    }
    Ok(())
}

fn seq_height(nodes: &[NodeDoc]) -> usize {
    nodes
        .iter()
        .flat_map(|n| n.slots().into_iter().map(|s| 1 + seq_height(s)))
        .max()
        .unwrap_or(0)
}

fn visit_nodes(nodes: &[NodeDoc], f: &mut dyn FnMut(&NodeDoc)) {
    for n in nodes {
        f(n);
        for s in n.slots() {
            visit_nodes(s, f);
        }
    }
}

fn visit_nodes_mut(nodes: &mut [NodeDoc], f: &mut dyn FnMut(&mut NodeDoc)) {
    for n in nodes {
        f(n);
        for s in n.slots_mut() {
            visit_nodes_mut(s, f);
        }
    }
}

/// The serialized form of one node.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
#[serde(tag = "type", content = "data", rename_all = "snake_case")]
pub enum NodeDoc {
    /// A single leaf token.
    Atom(Symbol),
    /// A fraction.
    Frac {
        /// Numerator nodes.
        num: Vec<NodeDoc>,
        /// Denominator nodes.
        den: Vec<NodeDoc>,
        /// Visual style.
        style: FracStyle,
    },
    /// Subscript and superscript on a base, at least one of the two is present.
    Script {
        /// Base nodes.
        base: Vec<NodeDoc>,
        /// Subscript nodes when present.
        sub: Option<Vec<NodeDoc>>,
        /// Superscript nodes when present.
        sup: Option<Vec<NodeDoc>>,
    },
    /// A big operator with limits.
    BigOp {
        /// The operator symbol.
        op: Symbol,
        /// Lower limit nodes.
        lower: Vec<NodeDoc>,
        /// Upper limit nodes.
        upper: Vec<NodeDoc>,
    },
    /// A radical.
    Sqrt {
        /// Degree nodes, empty for a square root.
        index: Vec<NodeDoc>,
        /// Radicand nodes.
        radicand: Vec<NodeDoc>,
    },
    /// Stretchy delimiters around a body.
    Delim {
        /// Opening delimiter character.
        open: char,
        /// Closing delimiter character.
        close: char,
        /// Body nodes.
        body: Vec<NodeDoc>,
    },
    /// An accent over a base.
    Accent {
        /// The accent mark.
        mark: Mark,
        /// Base nodes.
        base: Vec<NodeDoc>,
    },
    /// A base with optional labels above and below.
    UnderOver {
        /// Base nodes.
        base: Vec<NodeDoc>,
        /// Label above when present.
        over: Option<Vec<NodeDoc>>,
        /// Label below when present.
        under: Option<Vec<NodeDoc>>,
        /// Decoration between the base and the label above.
        over_deco: Deco,
        /// Decoration between the base and the label below.
        under_deco: Deco,
    },
    /// Content in a font variant or in text mode.
    Styled {
        /// The variant.
        variant: Variant,
        /// Content nodes.
        content: Vec<NodeDoc>,
    },
    /// An opaque host owned object.
    HostBox {
        /// The host minted token.
        token: u32,
    },
    /// A rectangular grid of cells.
    Matrix {
        /// The environment.
        env: MatrixEnv,
        /// Cells by row, each cell a node list.
        rows: Vec<Vec<Vec<NodeDoc>>>,
    },
}

impl NodeDoc {
    fn slots(&self) -> Vec<&Vec<NodeDoc>> {
        match self {
            NodeDoc::Atom(_) | NodeDoc::HostBox { .. } => Vec::new(),
            NodeDoc::Frac { num, den, .. } => vec![num, den],
            NodeDoc::Script { base, sub, sup } => {
                let mut v = vec![base];
                v.extend(sub.iter());
                v.extend(sup.iter());
                v
            }
            NodeDoc::BigOp { lower, upper, .. } => vec![lower, upper],
            NodeDoc::Sqrt { index, radicand } => vec![index, radicand],
            NodeDoc::Delim { body, .. } => vec![body],
            NodeDoc::Accent { base, .. } => vec![base],
            NodeDoc::UnderOver { base, over, under, .. } => {
                let mut v = vec![base];
                v.extend(over.iter());
                v.extend(under.iter());
                v
            }
            NodeDoc::Styled { content, .. } => vec![content],
            NodeDoc::Matrix { rows, .. } => rows.iter().flatten().collect(),
        }
    }

    fn slots_mut(&mut self) -> Vec<&mut Vec<NodeDoc>> {
        match self {
            NodeDoc::Atom(_) | NodeDoc::HostBox { .. } => Vec::new(),
            NodeDoc::Frac { num, den, .. } => vec![num, den],
            NodeDoc::Script { base, sub, sup } => {
                let mut v = vec![base];
                v.extend(sub.iter_mut());
                v.extend(sup.iter_mut());
                v
            }
            NodeDoc::BigOp { lower, upper, .. } => vec![lower, upper],
            NodeDoc::Sqrt { index, radicand } => vec![index, radicand],
            NodeDoc::Delim { body, .. } => vec![body],
            NodeDoc::Accent { base, .. } => vec![base],
            NodeDoc::UnderOver { base, over, under, .. } => {
                let mut v = vec![base];
                v.extend(over.iter_mut());
                v.extend(under.iter_mut());
                v
            }
            NodeDoc::Styled { content, .. } => vec![content],
            NodeDoc::Matrix { rows, .. } => rows.iter_mut().flatten().collect(),
        }
    }

    /// Whether the node owns slots, as opposed to atoms and host boxes.
    pub(crate) fn is_structural(&self) -> bool {
        !matches!(self, NodeDoc::Atom(_) | NodeDoc::HostBox { .. })
    }
}

impl Tree {
    /// The id free document form of the live tree.
    pub(crate) fn to_doc(&self) -> Document {
        Document::new(self.seq_to_doc(self.root()))
    }

    pub(crate) fn seq_to_doc(&self, seq: SeqId) -> Vec<NodeDoc> {
        self.items(seq).iter().filter_map(|&n| self.node_to_doc(n)).collect()
    }

    pub(crate) fn node_to_doc(&self, node: NodeId) -> Option<NodeDoc> {
        let s = |seq: SeqId| self.seq_to_doc(seq);
        let o = |seq: Option<SeqId>| seq.map(|q| self.seq_to_doc(q));
        Some(match self.kind(node)? {
            Kind::Atom(sym) => NodeDoc::Atom(sym.clone()),
            Kind::HostBox { token } => NodeDoc::HostBox { token: *token },
            Kind::Frac { num, den, style } => NodeDoc::Frac { num: s(*num), den: s(*den), style: *style },
            Kind::Script { base, sub, sup } => NodeDoc::Script { base: s(*base), sub: o(*sub), sup: o(*sup) },
            Kind::BigOp { op, lower, upper } => {
                NodeDoc::BigOp { op: op.clone(), lower: s(*lower), upper: s(*upper) }
            }
            Kind::Sqrt { index, radicand } => NodeDoc::Sqrt { index: s(*index), radicand: s(*radicand) },
            Kind::Delim { open, close, body } => NodeDoc::Delim { open: *open, close: *close, body: s(*body) },
            Kind::Accent { mark, base } => NodeDoc::Accent { mark: *mark, base: s(*base) },
            Kind::UnderOver { base, over, under, over_deco, under_deco } => NodeDoc::UnderOver {
                base: s(*base),
                over: o(*over),
                under: o(*under),
                over_deco: *over_deco,
                under_deco: *under_deco,
            },
            Kind::Styled { variant, content } => NodeDoc::Styled { variant: *variant, content: s(*content) },
            Kind::Matrix { env, rows } => NodeDoc::Matrix {
                env: *env,
                rows: rows.iter().map(|row| row.iter().map(|&c| s(c)).collect()).collect(),
            },
        })
    }

    /// Rebuild a tree with fresh ids, dropping whatever cannot be built safely, callers validate first.
    pub(crate) fn from_doc(doc: &Document) -> Self {
        let mut t = Tree::new();
        let root = t.root();
        for d in doc.root() {
            let at = t.len(root);
            t.build_node(root, at, d, 0);
        }
        t
    }

    /// Build `d` into `seq` at `index`, where `depth` is the depth of `seq`, `None` when dropped.
    pub(crate) fn build_node(&mut self, seq: SeqId, index: usize, d: &NodeDoc, depth: usize) -> Option<NodeId> {
        let inner = depth + 1;
        if d.is_structural() && inner > MAX_DEPTH {
            return None;
        }
        let kind = match d {
            NodeDoc::Atom(sym) => {
                check_latex(&sym.latex).ok()?;
                Kind::Atom(sym.clone())
            }
            NodeDoc::HostBox { token } if *token > MAX_HOST_TOKEN => return None,
            NodeDoc::HostBox { token } => Kind::HostBox { token: *token },
            NodeDoc::Frac { num, den, style } => Kind::Frac {
                num: self.build_seq(num, inner),
                den: self.build_seq(den, inner),
                style: *style,
            },
            NodeDoc::Script { base, sub, sup } => {
                let base = self.build_seq(base, inner);
                let sub = sub.as_ref().map(|s| self.build_seq(s, inner));
                let mut sup = sup.as_ref().map(|s| self.build_seq(s, inner));
                if sub.is_none() && sup.is_none() {
                    sup = Some(self.alloc_seq(None));
                }
                Kind::Script { base, sub, sup }
            }
            NodeDoc::BigOp { op, lower, upper } => {
                check_latex(&op.latex).ok()?;
                Kind::BigOp { op: op.clone(), lower: self.build_seq(lower, inner), upper: self.build_seq(upper, inner) }
            }
            NodeDoc::Sqrt { index, radicand } => Kind::Sqrt {
                index: self.build_seq(index, inner),
                radicand: self.build_seq(radicand, inner),
            },
            NodeDoc::Delim { open, close, body } => {
                let fix = |c: char| if DELIMITERS.contains(&c) { c } else { '.' };
                Kind::Delim { open: fix(*open), close: fix(*close), body: self.build_seq(body, inner) }
            }
            NodeDoc::Accent { mark, base } => Kind::Accent { mark: *mark, base: self.build_seq(base, inner) },
            NodeDoc::UnderOver { base, over, under, over_deco, under_deco } => Kind::UnderOver {
                base: self.build_seq(base, inner),
                over: over.as_ref().map(|s| self.build_seq(s, inner)),
                under: under.as_ref().map(|s| self.build_seq(s, inner)),
                over_deco: *over_deco,
                under_deco: *under_deco,
            },
            NodeDoc::Styled { variant, content } => {
                Kind::Styled { variant: *variant, content: self.build_seq(content, inner) }
            }
            NodeDoc::Matrix { env, rows } => {
                // Ragged rows are padded and an empty grid becomes a single empty cell.
                let cols = rows.iter().map(Vec::len).max().unwrap_or(0).max(1);
                let nrows = rows.len().max(1);
                let mut grid = Vec::with_capacity(nrows);
                for r in 0..nrows {
                    let mut row = Vec::with_capacity(cols);
                    for c in 0..cols {
                        let cell = rows.get(r).and_then(|row| row.get(c)).map_or(&[][..], Vec::as_slice);
                        row.push(self.build_seq(cell, inner));
                    }
                    grid.push(row);
                }
                Kind::Matrix { env: *env, rows: grid }
            }
        };
        Some(self.place(seq, index, kind))
    }

    fn build_seq(&mut self, docs: &[NodeDoc], depth: usize) -> SeqId {
        let seq = self.alloc_seq(None);
        for d in docs {
            let at = self.len(seq);
            self.build_node(seq, at, d, depth);
        }
        seq
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::model::MathClass;

    fn atom(c: &str) -> NodeDoc {
        NodeDoc::Atom(Symbol { latex: c.into(), class: MathClass::Ord })
    }

    fn every_kind() -> Document {
        let op = Symbol { latex: "\\sum".into(), class: MathClass::Op };
        Document::new(vec![
            NodeDoc::Script { base: vec![atom("a")], sub: None, sup: Some(vec![atom("2")]) },
            NodeDoc::Frac { num: vec![atom("x")], den: vec![], style: FracStyle::Bar },
            NodeDoc::Sqrt { index: vec![], radicand: vec![atom("y")] },
            NodeDoc::BigOp { op, lower: vec![], upper: vec![atom("n")] },
            NodeDoc::Delim { open: '(', close: ')', body: vec![atom("z")] },
            NodeDoc::Accent { mark: Mark::Hat, base: vec![atom("b")] },
            NodeDoc::Styled { variant: Variant::Bold, content: vec![atom("c")] },
            NodeDoc::UnderOver {
                base: vec![atom("d")],
                over: Some(vec![]),
                under: None,
                over_deco: Deco::Brace,
                under_deco: Deco::None,
            },
            NodeDoc::Matrix { env: MatrixEnv::Pmatrix, rows: vec![vec![vec![atom("e")], vec![]], vec![vec![], vec![]]] },
            NodeDoc::HostBox { token: 7 },
        ])
    }

    #[test]
    fn every_kind_round_trips_through_json_and_the_tree() {
        let d1 = every_kind();
        let json = serde_json::to_string(&d1).unwrap();
        let decoded: Document = serde_json::from_str(&json).unwrap();
        assert_eq!(decoded, d1);
        assert_eq!(Tree::from_doc(&decoded).to_doc(), d1);
    }

    #[test]
    fn serde_field_order_is_canonical() {
        let pos = |s: &str, key: &str| s.find(&format!("\"{key}\"")).unwrap_or_else(|| panic!("missing {key} in {s}"));
        let s = serde_json::to_string(&every_kind().root()[3]).unwrap();
        assert!(pos(&s, "op") < pos(&s, "lower") && pos(&s, "lower") < pos(&s, "upper"), "{s}");
        let doc = every_kind();
        let uo = &doc.root()[7];
        let s = serde_json::to_string(uo).unwrap();
        let order = ["base", "over", "under", "over_deco", "under_deco"];
        assert!(order.windows(2).all(|w| pos(&s, w[0]) < pos(&s, w[1])), "{s}");
        // `Some` holding empty data and `None` survive distinctly.
        let back: NodeDoc = serde_json::from_str(&s).unwrap();
        assert_eq!(&back, uo);
    }

    #[test]
    fn document_json_has_a_stable_shape() {
        let doc = Document::new(vec![atom("x"), NodeDoc::HostBox { token: 17 }]);
        let json = serde_json::to_string(&doc).unwrap();
        assert_eq!(
            json,
            r#"{"version":1,"root":[{"type":"atom","data":{"latex":"x","class":"ord"}},{"type":"host_box","data":{"token":17}}]}"#
        );
    }

    #[test]
    fn unknown_document_version_is_rejected() {
        let error = serde_json::from_str::<Document>(r#"{"version":2,"root":[]}"#).unwrap_err().to_string();
        assert!(error.contains("unsupported document version 2"), "{error}");
    }

    fn reject(json: &str) -> String {
        serde_json::from_str::<Document>(json).unwrap_err().to_string()
    }

    #[test]
    fn deserialization_rejects_ragged_empty_and_scriptless_structures() {
        let ragged = r#"{"version":1,"root":[{"type":"matrix","data":{"env":"matrix","rows":[[[],[]],[[]]]}}]}"#;
        assert!(reject(ragged).contains("differ in length"));
        let empty = r#"{"version":1,"root":[{"type":"matrix","data":{"env":"matrix","rows":[]}}]}"#;
        assert!(reject(empty).contains("no cells"));
        let script = r#"{"version":1,"root":[{"type":"script","data":{"base":[],"sub":null,"sup":null}}]}"#;
        assert!(reject(script).contains("neither"));
        let delim = r#"{"version":1,"root":[{"type":"delim","data":{"open":"x","close":")","body":[]}}]}"#;
        assert!(reject(delim).contains("delimiter"));
    }

    #[test]
    fn deserialization_rejects_unsafe_atom_latex() {
        for bad in ["", "{", "}{", "%", "a$b", "#", "&", "\\", "\u{7}", "x\ny"] {
            let doc = Document::new(vec![atom(bad)]);
            assert!(doc.validate().is_err(), "{bad:?} should be rejected");
        }
        for good in ["x", "\\%", "\\{", "\\mathbb{R}", "\\text{\\textasciicircum}", "\\ "] {
            assert_eq!(Document::new(vec![atom(good)]).validate(), Ok(()), "{good:?}");
        }
    }

    fn nested(depth: usize) -> Document {
        let mut nodes = vec![atom("x")];
        for _ in 0..depth {
            nodes = vec![NodeDoc::Delim { open: '(', close: ')', body: nodes }];
        }
        Document::new(nodes)
    }

    #[test]
    fn nesting_is_capped_and_the_cap_survives_json() {
        let deepest = nested(MAX_DEPTH);
        assert_eq!(deepest.validate(), Ok(()));
        assert_eq!(nested(MAX_DEPTH + 1).validate(), Err(DocumentError::TooDeep));
        // A matrix costs the most JSON levels per slot, so a full depth matrix chain must still parse.
        let mut nodes = vec![atom("x")];
        for _ in 0..MAX_DEPTH {
            nodes = vec![NodeDoc::Matrix { env: MatrixEnv::Matrix, rows: vec![vec![nodes]] }];
        }
        let json = serde_json::to_string(&Document::new(nodes)).unwrap();
        let back: Document = serde_json::from_str(&json).unwrap();
        assert_eq!(back.height(), MAX_DEPTH);
    }

    #[test]
    fn repair_fixes_every_rule_and_reports_each_change() {
        let mut doc = Document::new(vec![
            NodeDoc::Matrix { env: MatrixEnv::Matrix, rows: vec![vec![vec![atom("a")], vec![]], vec![]] },
            NodeDoc::Matrix { env: MatrixEnv::Matrix, rows: vec![] },
            NodeDoc::Script { base: vec![atom("b")], sub: None, sup: None },
            NodeDoc::Delim { open: 'x', close: ')', body: vec![] },
            atom("%"),
            NodeDoc::HostBox { token: MAX_HOST_TOKEN + 1 },
            NodeDoc::HostBox { token: MAX_HOST_TOKEN },
        ]);
        let repairs = doc.repair();
        assert_eq!(
            repairs,
            [
                Repair::PaddedMatrix,
                Repair::PaddedMatrix,
                Repair::AddedSuperscript,
                Repair::ReplacedDelimiter { found: 'x' },
                Repair::DroppedSymbol { latex: "%".into() },
                Repair::DroppedHostBox { token: MAX_HOST_TOKEN + 1 },
            ]
        );
        assert_eq!(doc.validate(), Ok(()));
        assert_eq!(doc.len(), 5);
        assert_eq!(doc.repair(), []);
        let mut deep = nested(MAX_DEPTH + 3);
        assert_eq!(deep.repair(), [Repair::DroppedTooDeep]);
        assert_eq!(deep.validate(), Ok(()));
        assert_eq!(deep.height(), MAX_DEPTH);
    }

    #[test]
    fn host_tokens_above_the_tex_integer_range_are_rejected() {
        let doc = Document::new(vec![NodeDoc::HostBox { token: 1 << 31 }]);
        assert_eq!(doc.validate(), Err(DocumentError::HostTokenTooLarge(1 << 31)));
        let json = r#"{"version":1,"root":[{"type":"host_box","data":{"token":2147483648}}]}"#;
        assert!(serde_json::from_str::<Document>(json).unwrap_err().to_string().contains("2147483648"));
        assert_eq!(Document::new(vec![NodeDoc::HostBox { token: MAX_HOST_TOKEN }]).validate(), Ok(()));
    }

    #[test]
    fn host_tokens_reach_nested_slots_and_can_be_remapped() {
        let mut doc = Document::new(vec![
            NodeDoc::HostBox { token: 3 },
            NodeDoc::Frac { num: vec![NodeDoc::HostBox { token: 7 }], den: vec![], style: FracStyle::Bar },
            NodeDoc::Matrix { env: MatrixEnv::Pmatrix, rows: vec![vec![vec![NodeDoc::HostBox { token: 9 }]]] },
        ]);
        assert_eq!(doc.host_tokens().into_iter().collect::<Vec<_>>(), vec![3, 7, 9]);
        doc.map_host_tokens(|t| t + 100);
        assert_eq!(doc.host_tokens().into_iter().collect::<Vec<_>>(), vec![103, 107, 109]);
        let mut count = 0;
        doc.visit(|_| count += 1);
        assert_eq!(count, 5);
    }

    #[test]
    fn to_tex_substitutes_host_box_content() {
        let doc = Document::new(vec![atom("a"), NodeDoc::HostBox { token: 4 }, NodeDoc::HostBox { token: 5 }]);
        assert_eq!(doc.to_tex(), "a\\hostbox{4}\\hostbox{5}");
        let tex = doc.to_tex_with(|t| (t == 4).then(|| "\\square".to_string()));
        assert_eq!(tex, "a\\square\\hostbox{5}");
    }
}