mathtex-editor-core 0.3.0

//! Edit operations built from primitives that keep slotmap entries, parent links, and `edits` in sync.

use std::ops::Range;

use crate::command::Side;
use crate::doc::{check_latex, Document, DELIMITERS, MAX_DEPTH, MAX_HOST_TOKEN};
use crate::model::{
    Cursor, Deco, FracStyle, Kind, Mark, MatrixEnv, Node, NodeId, ScriptSlot, Seq, SeqId, SeqRange, Symbol, Tree,
    UnderOverSpec, Variant,
};
use crate::nav;

/// Describes a structure to create with empty slots.
pub(crate) enum NewNode {
    Frac(FracStyle),
    Script(ScriptSlot),
    BigOp(Symbol),
    Sqrt,
    Delim { open: char, close: char },
    Accent(Mark),
    UnderOver(UnderOverSpec),
    Styled(Variant),
    Matrix { env: MatrixEnv, rows: usize, cols: usize },
}

impl Tree {
    pub(crate) fn alloc_seq(&mut self, parent: Option<NodeId>) -> SeqId {
        self.seqs.insert(Seq { parent, items: Vec::new() })
    }

    fn build_kind(&mut self, spec: NewNode) -> Kind {
        match spec {
            NewNode::Frac(style) => Kind::Frac { num: self.alloc_seq(None), den: self.alloc_seq(None), style },
            NewNode::Script(slot) => {
                let base = self.alloc_seq(None);
                let (sub, sup) = match slot {
                    ScriptSlot::Sub => (Some(self.alloc_seq(None)), None),
                    ScriptSlot::Sup => (None, Some(self.alloc_seq(None))),
                };
                Kind::Script { base, sub, sup }
            }
            NewNode::BigOp(op) => Kind::BigOp { op, lower: self.alloc_seq(None), upper: self.alloc_seq(None) },
            // Both slots always exist, an empty degree is just a placeholder.
            NewNode::Sqrt => Kind::Sqrt { index: self.alloc_seq(None), radicand: self.alloc_seq(None) },
            NewNode::Delim { open, close } => Kind::Delim { open, close, body: self.alloc_seq(None) },
            NewNode::Accent(mark) => Kind::Accent { mark, base: self.alloc_seq(None) },
            NewNode::UnderOver(spec) => Kind::UnderOver {
                base: self.alloc_seq(None),
                over: spec.over.then(|| self.alloc_seq(None)),
                under: spec.under.then(|| self.alloc_seq(None)),
                over_deco: spec.over_deco,
                under_deco: spec.under_deco,
            },
            NewNode::Styled(variant) => Kind::Styled { variant, content: self.alloc_seq(None) },
            NewNode::Matrix { env, rows, cols } => {
                let grid = (0..rows).map(|_| (0..cols).map(|_| self.alloc_seq(None)).collect()).collect();
                Kind::Matrix { env, rows: grid }
            }
        }
    }

    /// Splices a node carrying `kind` into `seq` and points its slot seqs at it.
    pub(crate) fn place(&mut self, seq: SeqId, index: usize, kind: Kind) -> NodeId {
        let node = self.nodes.insert(Node { parent: seq, kind });
        for s in self.child_seqs(node) {
            if let Some(sq) = self.seqs.get_mut(s) {
                sq.parent = Some(node);
            }
        }
        if let Some(sq) = self.seqs.get_mut(seq) {
            let i = index.min(sq.items.len());
            sq.items.insert(i, node);
        }
        self.touch();
        node
    }

    pub(crate) fn insert_new(&mut self, seq: SeqId, index: usize, spec: NewNode) -> NodeId {
        let kind = self.build_kind(spec);
        self.place(seq, index, kind)
    }

    /// Unlinks `seq[range]` while keeping the subtrees alive.
    fn take_range(&mut self, seq: SeqId, range: Range<usize>) -> Vec<NodeId> {
        let Some(sq) = self.seqs.get_mut(seq) else {
            return Vec::new();
        };
        let range = range.start.min(sq.items.len())..range.end.min(sq.items.len());
        let taken: Vec<NodeId> = sq.items.drain(range).collect();
        if !taken.is_empty() {
            self.touch();
        }
        taken
    }

    /// Recursively frees a node, its slot seqs, and their contents.
    pub(crate) fn drop_node(&mut self, node: NodeId) {
        if let Some((parent, idx)) = self.index_in_parent(node) {
            self.take_range(parent, idx..idx + 1);
        }
        self.free_node(node);
    }

    fn free_node(&mut self, node: NodeId) {
        for s in self.child_seqs(node) {
            self.free_seq(s);
        }
        self.nodes.remove(node);
    }

    fn free_seq(&mut self, seq: SeqId) {
        let items = self.seqs.get(seq).map(|s| s.items.clone()).unwrap_or_default();
        for n in items {
            self.free_node(n);
        }
        self.seqs.remove(seq);
        self.touch();
    }

    /// Moves nodes from `src[range]` into `dst` at `at`, the caller ensures the seqs differ.
    pub(crate) fn move_range(&mut self, src: SeqId, range: Range<usize>, dst: SeqId, at: usize) {
        let moved = self.take_range(src, range);
        for &n in &moved {
            if let Some(nd) = self.nodes.get_mut(n) {
                nd.parent = dst;
            }
        }
        if let Some(d) = self.seqs.get_mut(dst) {
            let at = at.min(d.items.len());
            d.items.splice(at..at, moved);
        }
    }

    /// Deletes a run within one seq in a single pass and returns the gap it leaves.
    pub(crate) fn delete_range(&mut self, sel: SeqRange) -> Cursor {
        for n in self.take_range(sel.seq, sel.lo()..sel.hi()) {
            self.free_node(n);
        }
        Cursor { seq: sel.seq, index: sel.lo().min(self.len(sel.seq)) }
    }

    /// Whether a structure `height` slot levels tall may be inserted into `seq`.
    pub(crate) fn fits(&self, seq: SeqId, height: usize) -> bool {
        self.seq_depth(seq) + height <= MAX_DEPTH
    }

    fn range_height(&self, sel: SeqRange) -> usize {
        let items = self.items(sel.seq);
        let hi = sel.hi().min(items.len());
        items[sel.lo().min(hi)..hi].iter().map(|&n| self.node_height(n)).max().unwrap_or(0)
    }

    /// Deletes an optional selection and returns the gap where insertion continues.
    fn clear(&mut self, at: Cursor, sel: Option<SeqRange>) -> Cursor {
        match sel {
            Some(s) => self.delete_range(s),
            None => at,
        }
    }
}

impl Tree {
    /// Evicts a nonempty Script base to the left so the next insertion replaces it.
    fn make_room_in_script_base(&mut self, at: Cursor) -> Cursor {
        if self.is_empty(at.seq) {
            return at;
        }
        let Some(script) = self.script_base_node(at.seq) else {
            return at;
        };
        let Some((pseq, pidx)) = self.index_in_parent(script) else {
            return at;
        };
        let n = self.len(at.seq);
        self.move_range(at.seq, 0..n, pseq, pidx);
        Cursor { seq: at.seq, index: 0 }
    }

    /// Inserts an atom, replacing `sel`, and returns the gap after it.
    pub(crate) fn insert_atom(&mut self, at: Cursor, sel: Option<SeqRange>, sym: Symbol) -> Option<Cursor> {
        check_latex(&sym.latex).ok()?;
        self.insert_leaf(at, sel, Kind::Atom(sym))
    }

    /// Inserts an opaque host object, replacing `sel`, and returns the gap after it.
    pub(crate) fn insert_host_box(&mut self, at: Cursor, sel: Option<SeqRange>, token: u32) -> Option<Cursor> {
        if token > MAX_HOST_TOKEN {
            return None;
        }
        self.insert_leaf(at, sel, Kind::HostBox { token })
    }

    fn insert_leaf(&mut self, at: Cursor, sel: Option<SeqRange>, kind: Kind) -> Option<Cursor> {
        let at = self.clear(at, sel);
        let at = self.make_room_in_script_base(at);
        self.place(at.seq, at.index, kind);
        Some(Cursor { seq: at.seq, index: at.index + 1 })
    }

    /// Inserts a structure and wraps `sel` into the slot at `wrap_slot` of `child_seqs`.
    fn insert_struct(
        &mut self,
        at: Cursor,
        sel: Option<SeqRange>,
        spec: NewNode,
        wrap_slot: usize,
    ) -> Option<(NodeId, bool)> {
        if self.is_text_slot(at.seq) {
            return None;
        }
        match sel {
            None => {
                if !self.fits(at.seq, 1) {
                    return None;
                }
                let at = self.make_room_in_script_base(at);
                Some((self.insert_new(at.seq, at.index, spec), false))
            }
            Some(s) => {
                if !self.fits(s.seq, 1 + self.range_height(s)) {
                    return None;
                }
                let (lo, hi) = (s.lo(), s.hi().min(self.len(s.seq)));
                let node = self.insert_new(s.seq, lo, spec);
                let slot = self.child_seqs(node)[wrap_slot];
                self.move_range(s.seq, lo + 1..hi + 1, slot, 0);
                Some((node, true))
            }
        }
    }

    /// The gap in slot `slot` of `node`, at its end when content was wrapped into it.
    fn slot_gap(&self, node: NodeId, slot: usize, wrapped: bool) -> Cursor {
        let seq = self.child_seqs(node)[slot];
        Cursor { seq, index: if wrapped { self.len(seq) } else { 0 } }
    }

    /// Inserts a fraction, wrapping `sel` into the numerator and continuing in the denominator.
    pub(crate) fn insert_fraction(&mut self, at: Cursor, style: FracStyle, sel: Option<SeqRange>) -> Option<Cursor> {
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::Frac(style), 0)?;
        Some(self.slot_gap(node, usize::from(wrapped), false))
    }

    /// Inserts a radical, wrapping `sel` into the radicand.
    pub(crate) fn insert_sqrt(&mut self, at: Cursor, sel: Option<SeqRange>) -> Option<Cursor> {
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::Sqrt, 1)?;
        Some(self.slot_gap(node, 1, wrapped))
    }

    /// Inserts delimiters from the supported set, wrapping `sel` into the body.
    pub(crate) fn insert_delimiters(
        &mut self,
        at: Cursor,
        open: char,
        close: char,
        sel: Option<SeqRange>,
    ) -> Option<Cursor> {
        if !DELIMITERS.contains(&open) || !DELIMITERS.contains(&close) {
            return None;
        }
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::Delim { open, close }, 0)?;
        Some(self.slot_gap(node, 0, wrapped))
    }

    /// Inserts an accent, wrapping `sel` into its base.
    pub(crate) fn insert_accent(&mut self, at: Cursor, mark: Mark, sel: Option<SeqRange>) -> Option<Cursor> {
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::Accent(mark), 0)?;
        Some(self.slot_gap(node, 0, wrapped))
    }

    /// Inserts a styled run, a text run only wraps a selection made of atoms.
    pub(crate) fn insert_styled(&mut self, at: Cursor, variant: Variant, sel: Option<SeqRange>) -> Option<Cursor> {
        if variant == Variant::Text && sel.is_some_and(|s| self.range_height(s) > 0) {
            return None;
        }
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::Styled(variant), 0)?;
        Some(self.slot_gap(node, 0, wrapped))
    }

    /// Inserts an under or over construct, wrapping `sel` into its base.
    pub(crate) fn insert_under_over(&mut self, at: Cursor, spec: UnderOverSpec, sel: Option<SeqRange>) -> Option<Cursor> {
        let base_slot = usize::from(spec.over);
        let (node, wrapped) = self.insert_struct(at, sel, NewNode::UnderOver(spec), base_slot)?;
        Some(self.slot_gap(node, base_slot, wrapped))
    }

    /// Inserts a matrix of at least one cell, replacing `sel`, and returns the first cell.
    pub(crate) fn insert_matrix(
        &mut self,
        at: Cursor,
        sel: Option<SeqRange>,
        env: MatrixEnv,
        rows: usize,
        cols: usize,
    ) -> Option<Cursor> {
        if self.is_text_slot(at.seq) || !self.fits(at.seq, 1) {
            return None;
        }
        let at = self.clear(at, sel);
        let at = self.make_room_in_script_base(at);
        let spec = NewNode::Matrix { env, rows: rows.max(1), cols: cols.max(1) };
        let node = self.insert_new(at.seq, at.index, spec);
        Some(self.slot_gap(node, 0, false))
    }

    /// Inserts a big operator with empty limits, replacing `sel`, and returns the gap after it.
    pub(crate) fn insert_big_op(&mut self, at: Cursor, sel: Option<SeqRange>, op: Symbol) -> Option<Cursor> {
        check_latex(&op.latex).ok()?;
        if self.is_text_slot(at.seq) || !self.fits(at.seq, 1) {
            return None;
        }
        let at = self.clear(at, sel);
        let at = self.make_room_in_script_base(at);
        self.insert_new(at.seq, at.index, NewNode::BigOp(op));
        Some(Cursor { seq: at.seq, index: at.index + 1 })
    }

    /// Splices a document at the caret, in a script base only the last node stays in the base.
    pub(crate) fn insert_doc(&mut self, at: Cursor, sel: Option<SeqRange>, doc: &Document) -> Option<Cursor> {
        if doc.is_empty() || !self.fits(at.seq, doc.height()) {
            return None;
        }
        if self.is_text_slot(at.seq) && doc.root().iter().any(|d| d.is_structural()) {
            return None;
        }
        let depth = self.seq_depth(at.seq);
        let at = self.clear(at, sel);
        let at = self.make_room_in_script_base(at);
        let nodes = doc.root();
        let (last, rest) = nodes.split_last()?;
        if let Some(script) = self.script_base_node(at.seq) {
            let (pseq, pidx) = self.index_in_parent(script)?;
            let mut i = pidx;
            for d in rest {
                if self.build_node(pseq, i, d, depth - 1).is_some() {
                    i += 1;
                }
            }
            let placed = self.build_node(at.seq, 0, last, depth).is_some();
            return Some(Cursor { seq: at.seq, index: usize::from(placed) });
        }
        let mut i = at.index;
        for d in nodes {
            if self.build_node(at.seq, i, d, depth).is_some() {
                i += 1;
            }
        }
        Some(Cursor { seq: at.seq, index: i })
    }

    /// Returns the BigOp limit targeted by `_` or `^` when the caret is right after the operator.
    pub(crate) fn bigop_limit_target(&self, at: Cursor, which: ScriptSlot) -> Option<Cursor> {
        let prev = *self.items(at.seq).get(at.index.checked_sub(1)?)?;
        let Some(Kind::BigOp { lower, upper, .. }) = self.kind(prev) else {
            return None;
        };
        let target = match which {
            ScriptSlot::Sub => *lower,
            ScriptSlot::Sup => *upper,
        };
        Some(Cursor { seq: target, index: self.len(target) })
    }

    /// Attaches or moves into a subscript or superscript, wrapping `sel` as the base when given.
    pub(crate) fn attach_script(&mut self, at: Cursor, which: ScriptSlot, sel: Option<SeqRange>) -> Option<Cursor> {
        if self.is_text_slot(at.seq) {
            return None;
        }
        // Inside a base the owning Script takes the script, never a nested one.
        if let Some(script) = self.script_base_node(at.seq) {
            let slot = self.script_slot(script, which);
            return Some(Cursor { seq: slot, index: self.len(slot) });
        }
        if let Some(s) = sel {
            let (node, _) = self.insert_struct(at, Some(s), NewNode::Script(which), 0)?;
            let slot = self.script_slot(node, which);
            return Some(Cursor { seq: slot, index: 0 });
        }
        if at.index > 0 {
            let prev = self.items(at.seq)[at.index - 1];
            if matches!(self.kind(prev), Some(Kind::Script { .. })) {
                let slot = self.script_slot(prev, which);
                return Some(Cursor { seq: slot, index: self.len(slot) });
            }
            // The preceding node becomes the base of a new Script.
            if !self.fits(at.seq, 1 + self.node_height(prev)) {
                return None;
            }
            let script = self.insert_new(at.seq, at.index, NewNode::Script(which));
            let base = self.child_seqs(script)[0];
            self.move_range(at.seq, at.index - 1..at.index, base, 0);
            let slot = self.script_slot(script, which);
            return Some(Cursor { seq: slot, index: 0 });
        }
        if !self.fits(at.seq, 1) {
            return None;
        }
        let script = self.insert_new(at.seq, at.index, NewNode::Script(which));
        let slot = self.script_slot(script, which);
        Some(Cursor { seq: slot, index: 0 })
    }

    /// Returns the existing or newly created subscript or superscript seq of a Script node.
    fn script_slot(&mut self, node: NodeId, which: ScriptSlot) -> SeqId {
        let existing = match self.kind(node) {
            Some(Kind::Script { sub, sup, .. }) => match which {
                ScriptSlot::Sub => *sub,
                ScriptSlot::Sup => *sup,
            },
            _ => None,
        };
        if let Some(s) = existing {
            return s;
        }
        let s = self.alloc_seq(Some(node));
        if let Some(Node { kind: Kind::Script { sub, sup, .. }, .. }) = self.nodes.get_mut(node) {
            match which {
                ScriptSlot::Sub => *sub = Some(s),
                ScriptSlot::Sup => *sup = Some(s),
            }
        }
        self.touch();
        s
    }

    /// Deletes backward, escalating empty slots and otherwise moving left when no leaf is removed.
    pub(crate) fn delete_backward(&mut self, at: Cursor) -> Cursor {
        if at.index > 0 {
            let prev = self.items(at.seq)[at.index - 1];
            if self.child_seqs(prev).is_empty() {
                self.drop_node(prev);
                return Cursor { seq: at.seq, index: at.index - 1 };
            }
            return nav::move_left(self, at).unwrap_or(at);
        }
        if self.is_empty(at.seq) {
            if let Some(parent) = self.seq_parent(at.seq) {
                return self.escalate_delete(parent, at.seq, at);
            }
            return at;
        }
        nav::move_left(self, at).unwrap_or(at)
    }

    /// Deletes forward as the mirror of [`Tree::delete_backward`].
    pub(crate) fn delete_forward(&mut self, at: Cursor) -> Cursor {
        if at.index < self.len(at.seq) {
            let next = self.items(at.seq)[at.index];
            if self.child_seqs(next).is_empty() {
                self.drop_node(next);
                return at;
            }
            return nav::move_right(self, at).unwrap_or(at);
        }
        if self.is_empty(at.seq) {
            if let Some(parent) = self.seq_parent(at.seq) {
                return self.escalate_delete(parent, at.seq, at);
            }
            return at;
        }
        nav::move_right(self, at).unwrap_or(at)
    }

    fn drop_and_step_out(&mut self, parent: NodeId, at_parent: Cursor) -> Cursor {
        self.drop_node(parent);
        at_parent
    }

    /// Promotes `from` into `into`, drops `parent`, and returns the gap after the promoted run.
    fn promote_and_drop(&mut self, parent: NodeId, from: SeqId, into: SeqId, at: usize) -> Cursor {
        let n = self.len(from);
        self.move_range(from, 0..n, into, at);
        self.drop_node(parent);
        Cursor { seq: into, index: at + n }
    }

    /// Handles deletion from an empty Script base by pulling in the left sibling or dissolving.
    fn delete_empty_script_base(&mut self, parent: NodeId, base: SeqId, at_parent: Cursor) -> Cursor {
        let (pseq, pidx) = (at_parent.seq, at_parent.index);
        if pidx > 0 {
            let prev = self.items(pseq)[pidx - 1];
            if self.fits(base, self.node_height(prev)) {
                self.move_range(pseq, pidx - 1..pidx, base, 0);
                return Cursor { seq: base, index: self.len(base) };
            }
        }
        let mut offset = 0;
        for s in self.child_seqs(parent) {
            let n = self.len(s);
            self.move_range(s, 0..n, pseq, pidx + offset);
            offset += n;
        }
        self.drop_and_step_out(parent, at_parent)
    }

    /// Removes an empty optional slot, then promotes the base when no optional slot remains.
    fn drop_optional_slot(&mut self, parent: NodeId, slot: SeqId, at_parent: Cursor) -> Cursor {
        let remaining = match self.nodes.get_mut(parent).map(|n| &mut n.kind) {
            Some(Kind::Script { sub: a, sup: b, .. } | Kind::UnderOver { over: a, under: b, .. }) => {
                if *a == Some(slot) {
                    *a = None;
                } else if *b == Some(slot) {
                    *b = None;
                }
                a.is_some() || b.is_some()
            }
            _ => return at_parent,
        };
        self.free_seq(slot);
        let base = self.child_seqs(parent).into_iter().find(|&s| self.slot_of(parent, s) == Some(crate::path::Slot::Base));
        let Some(base) = base else {
            return at_parent;
        };
        if remaining {
            Cursor { seq: base, index: self.len(base) }
        } else {
            self.promote_and_drop(parent, base, at_parent.seq, at_parent.index)
        }
    }

    /// Handles deletion at the start of an empty slot.
    fn escalate_delete(&mut self, parent: NodeId, slot: SeqId, fallback: Cursor) -> Cursor {
        let Some((pseq, pidx)) = self.index_in_parent(parent) else {
            return fallback;
        };
        let Some(kind) = self.kind(parent).cloned() else {
            return fallback;
        };
        let at_parent = Cursor { seq: pseq, index: pidx };
        let end_of = |t: &Tree, s: SeqId| Cursor { seq: s, index: t.len(s) };
        match kind {
            // An empty Frac slot drops the frac or promotes the other slot's content.
            Kind::Frac { num, den, .. } => {
                let other = if slot == num { den } else { num };
                if self.is_empty(other) {
                    self.drop_and_step_out(parent, at_parent)
                } else {
                    self.promote_and_drop(parent, other, pseq, pidx)
                }
            }
            // An empty radicand steps into a filled degree, an empty degree steps out left.
            Kind::Sqrt { index, radicand } => {
                let other = if slot == radicand { index } else { radicand };
                if self.is_empty(other) {
                    self.drop_and_step_out(parent, at_parent)
                } else if slot == radicand {
                    end_of(self, index)
                } else {
                    at_parent
                }
            }
            Kind::Delim { .. } | Kind::Accent { .. } | Kind::Styled { .. } => {
                self.drop_and_step_out(parent, at_parent)
            }
            Kind::Script { base, .. } => {
                if slot == base {
                    self.delete_empty_script_base(parent, base, at_parent)
                } else {
                    self.drop_optional_slot(parent, slot, at_parent)
                }
            }
            // An empty limit drops the operator or steps into the filled other limit.
            Kind::BigOp { lower, upper, .. } => {
                let other = if slot == lower { upper } else { lower };
                if self.is_empty(other) {
                    self.drop_and_step_out(parent, at_parent)
                } else {
                    end_of(self, other)
                }
            }
            // An empty base steps into a filled label and only drops the construct when all are empty.
            Kind::UnderOver { base, over, under, .. } => {
                if slot != base {
                    return self.drop_optional_slot(parent, slot, at_parent);
                }
                match [over, under].into_iter().flatten().find(|&s| !self.is_empty(s)) {
                    Some(label) => end_of(self, label),
                    None => self.drop_and_step_out(parent, at_parent),
                }
            }
            // Empty cells are valid, so the matrix goes only when every cell is empty.
            Kind::Matrix { rows, .. } => {
                if rows.iter().flatten().all(|&c| self.is_empty(c)) {
                    self.drop_and_step_out(parent, at_parent)
                } else {
                    nav::move_left(self, Cursor { seq: slot, index: 0 }).unwrap_or(fallback)
                }
            }
            Kind::Atom(_) | Kind::HostBox { .. } => fallback,
        }
    }

    /// The matrix node, row, and column of the cell that directly holds the caret.
    fn matrix_of(&self, at: Cursor) -> Option<(NodeId, usize, usize)> {
        let m = self.seq_parent(at.seq)?;
        match self.slot_of(m, at.seq)? {
            crate::path::Slot::Cell { row, col } => Some((m, row, col)),
            _ => None,
        }
    }

    fn matrix_rows(&self, m: NodeId) -> &[Vec<SeqId>] {
        match self.kind(m) {
            Some(Kind::Matrix { rows, .. }) => rows,
            _ => &[],
        }
    }

    fn matrix_rows_mut(&mut self, m: NodeId) -> Option<&mut Vec<Vec<SeqId>>> {
        match self.nodes.get_mut(m).map(|n| &mut n.kind) {
            Some(Kind::Matrix { rows, .. }) => Some(rows),
            _ => None,
        }
    }

    /// Rows and columns of the matrix whose cell holds the caret.
    pub(crate) fn matrix_shape_at(&self, at: Cursor) -> Option<(usize, usize)> {
        let (m, _, _) = self.matrix_of(at)?;
        let rows = self.matrix_rows(m);
        Some((rows.len(), rows.first().map_or(0, Vec::len)))
    }

    /// The first cell of `row` near `col`, else the gap before the matrix, never a freed seq.
    fn cell_or_before(&self, m: NodeId, row: usize, col: usize) -> Option<Cursor> {
        let rows = self.matrix_rows(m);
        let row = rows.get(row.min(rows.len().saturating_sub(1)))?;
        match row.get(col.min(row.len().saturating_sub(1))) {
            Some(&seq) => Some(Cursor { seq, index: 0 }),
            None => self.index_in_parent(m).map(|(seq, index)| Cursor { seq, index }),
        }
    }

    /// Inserts a matrix row before or after the caret's row.
    pub(crate) fn matrix_insert_row(&mut self, at: Cursor, side: Side) -> Option<Cursor> {
        let (m, r, c) = self.matrix_of(at)?;
        let cols = self.matrix_rows(m).first().map_or(0, Vec::len).max(1);
        let new_row: Vec<SeqId> = (0..cols).map(|_| self.alloc_seq(Some(m))).collect();
        let idx = match side {
            Side::Before => r,
            Side::After => r + 1,
        };
        let rows = self.matrix_rows_mut(m)?;
        rows.insert(idx.min(rows.len()), new_row);
        self.touch();
        self.cell_or_before(m, idx, c)
    }

    /// Deletes the caret's matrix row when another row remains.
    pub(crate) fn matrix_delete_row(&mut self, at: Cursor) -> Option<Cursor> {
        let (m, r, c) = self.matrix_of(at)?;
        if self.matrix_rows(m).len() <= 1 {
            return None;
        }
        let removed = self.matrix_rows_mut(m)?.remove(r);
        for cell in removed {
            self.free_seq(cell);
        }
        self.cell_or_before(m, r, c)
    }

    /// Inserts a matrix column before or after the caret's column.
    pub(crate) fn matrix_insert_col(&mut self, at: Cursor, side: Side) -> Option<Cursor> {
        let (m, r, c) = self.matrix_of(at)?;
        let nrows = self.matrix_rows(m).len();
        let cells: Vec<SeqId> = (0..nrows).map(|_| self.alloc_seq(Some(m))).collect();
        let idx = match side {
            Side::Before => c,
            Side::After => c + 1,
        };
        for (row, cell) in self.matrix_rows_mut(m)?.iter_mut().zip(cells) {
            let i = idx.min(row.len());
            row.insert(i, cell);
        }
        self.touch();
        self.cell_or_before(m, r, idx)
    }

    /// Deletes the caret's matrix column when another column remains.
    pub(crate) fn matrix_delete_col(&mut self, at: Cursor) -> Option<Cursor> {
        let (m, r, c) = self.matrix_of(at)?;
        if self.matrix_rows(m).first().map_or(0, Vec::len) <= 1 {
            return None;
        }
        let mut removed = Vec::new();
        for row in self.matrix_rows_mut(m)?.iter_mut() {
            if c < row.len() {
                removed.push(row.remove(c));
            }
        }
        for cell in removed {
            self.free_seq(cell);
        }
        self.cell_or_before(m, r, c)
    }

    /// Swap menu alternatives for `node`, excluding its current value, `None` when not swappable.
    pub(crate) fn swap_variants(&self, node: NodeId) -> Option<Vec<SwapVariant>> {
        let alts = |labels: &[(&str, SwapKind)], keep: &dyn Fn(&SwapKind) -> bool| -> Vec<SwapVariant> {
            labels
                .iter()
                .filter(|(_, k)| keep(k))
                .map(|(label, kind)| SwapVariant { label: (*label).to_string(), kind: *kind })
                .collect()
        };
        match self.kind(node)? {
            Kind::Atom(_) | Kind::HostBox { .. } | Kind::Frac { .. } | Kind::Script { .. } | Kind::Sqrt { .. } => None,
            Kind::Delim { open, close, .. } => {
                let (open, close) = (*open, *close);
                Some(alts(DELIM_ALTS, &|k| *k != SwapKind::Delim { open, close }))
            }
            Kind::BigOp { op, .. } => {
                let current = op.latex.clone();
                Some(alts(BIGOP_ALTS, &|k| !matches!(k, SwapKind::BigOp { latex } if *latex == current)))
            }
            Kind::Accent { mark, .. } => {
                let mark = *mark;
                Some(alts(ACCENT_ALTS, &|k| *k != SwapKind::Accent(mark)))
            }
            // Only decorations of present slots vary, prefixed with the slot when both exist.
            Kind::UnderOver { over, under, over_deco, under_deco, .. } => {
                let both = over.is_some() && under.is_some();
                let mut out = Vec::new();
                for (present, current, is_over) in [(over.is_some(), *over_deco, true), (under.is_some(), *under_deco, false)] {
                    if !present {
                        continue;
                    }
                    for &(deco, label) in DECO_ALTS {
                        if deco == current {
                            continue;
                        }
                        let (o, u) = if is_over { (deco, *under_deco) } else { (*over_deco, deco) };
                        let label = match (both, is_over) {
                            (false, _) => label.to_string(),
                            (true, true) => format!("over: {label}"),
                            (true, false) => format!("under: {label}"),
                        };
                        out.push(SwapVariant { label, kind: SwapKind::UnderOverDeco { over: o, under: u } });
                    }
                }
                Some(out)
            }
            // `\text{}` is a carve out where the caret enters instead of swapping.
            Kind::Styled { variant: Variant::Text, .. } => None,
            Kind::Styled { variant, .. } => {
                let v = *variant;
                Some(alts(STYLED_ALTS, &|k| *k != SwapKind::Styled(v)))
            }
            Kind::Matrix { env, .. } => {
                let e = *env;
                Some(alts(MATRIX_ENV_ALTS, &|k| *k != SwapKind::Matrix(e)))
            }
        }
    }

    /// Applies a chosen alternative by changing only the named tag fields.
    pub(crate) fn apply_swap(&mut self, node: NodeId, variant: &SwapKind) {
        let Some(n) = self.nodes.get_mut(node) else {
            return;
        };
        let applied = match (&mut n.kind, variant) {
            (Kind::Delim { open, close, .. }, SwapKind::Delim { open: o, close: c }) => {
                (*open, *close) = (*o, *c);
                true
            }
            (Kind::BigOp { op, .. }, SwapKind::BigOp { latex }) => {
                op.latex = (*latex).to_string();
                true
            }
            (Kind::Accent { mark, .. }, SwapKind::Accent(m)) => {
                *mark = *m;
                true
            }
            (Kind::UnderOver { over_deco, under_deco, .. }, SwapKind::UnderOverDeco { over, under }) => {
                (*over_deco, *under_deco) = (*over, *under);
                true
            }
            (Kind::Styled { variant: v, .. }, SwapKind::Styled(nv)) => {
                *v = *nv;
                true
            }
            (Kind::Matrix { env, .. }, SwapKind::Matrix(e)) => {
                *env = *e;
                true
            }
            _ => false,
        };
        if applied {
            self.touch();
        }
    }
}

/// One swap menu alternative for a swappable structure.
#[derive(Debug, Clone, PartialEq)]
pub(crate) struct SwapVariant {
    pub(crate) label: String,
    pub(crate) kind: SwapKind,
}

/// The tag fields a swap writes.
#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) enum SwapKind {
    Delim { open: char, close: char },
    BigOp { latex: &'static str },
    Accent(Mark),
    UnderOverDeco { over: Deco, under: Deco },
    Styled(Variant),
    Matrix(MatrixEnv),
}

const DELIM_ALTS: &[(&str, SwapKind)] = &[
    ("( ) parentheses", SwapKind::Delim { open: '(', close: ')' }),
    ("[ ] brackets", SwapKind::Delim { open: '[', close: ']' }),
    ("{ } braces", SwapKind::Delim { open: '{', close: '}' }),
    ("| | bars", SwapKind::Delim { open: '|', close: '|' }),
    ("⌈ ⌉ ceiling", SwapKind::Delim { open: '⌈', close: '⌉' }),
    ("⌊ ⌋ floor", SwapKind::Delim { open: '⌊', close: '⌋' }),
    ("⟨ ⟩ angle", SwapKind::Delim { open: '⟨', close: '⟩' }),
];

const BIGOP_ALTS: &[(&str, SwapKind)] = &[
    ("∑ sum", SwapKind::BigOp { latex: "\\sum" }),
    ("∏ product", SwapKind::BigOp { latex: "\\prod" }),
    ("∐ coproduct", SwapKind::BigOp { latex: "\\coprod" }),
    ("∫ integral", SwapKind::BigOp { latex: "\\int" }),
    ("∬ double integral", SwapKind::BigOp { latex: "\\iint" }),
    ("∭ triple integral", SwapKind::BigOp { latex: "\\iiint" }),
    ("∮ contour integral", SwapKind::BigOp { latex: "\\oint" }),
    ("⋃ union", SwapKind::BigOp { latex: "\\bigcup" }),
    ("⋂ intersection", SwapKind::BigOp { latex: "\\bigcap" }),
    ("⊔ disjoint union", SwapKind::BigOp { latex: "\\bigsqcup" }),
    ("⊎ uplus", SwapKind::BigOp { latex: "\\biguplus" }),
    ("⊕ oplus", SwapKind::BigOp { latex: "\\bigoplus" }),
    ("⊗ otimes", SwapKind::BigOp { latex: "\\bigotimes" }),
    ("⊙ odot", SwapKind::BigOp { latex: "\\bigodot" }),
    ("⋁ vee", SwapKind::BigOp { latex: "\\bigvee" }),
    ("⋀ wedge", SwapKind::BigOp { latex: "\\bigwedge" }),
];

const ACCENT_ALTS: &[(&str, SwapKind)] = &[
    ("hat", SwapKind::Accent(Mark::Hat)),
    ("vec", SwapKind::Accent(Mark::Vec)),
    ("bar", SwapKind::Accent(Mark::Bar)),
    ("tilde", SwapKind::Accent(Mark::Tilde)),
    ("dot", SwapKind::Accent(Mark::Dot)),
    ("double dot", SwapKind::Accent(Mark::Ddot)),
    ("wide hat", SwapKind::Accent(Mark::Widehat)),
    ("wide tilde", SwapKind::Accent(Mark::Widetilde)),
    ("overline", SwapKind::Accent(Mark::Overline)),
    ("underline", SwapKind::Accent(Mark::Underline)),
    ("check", SwapKind::Accent(Mark::Check)),
    ("breve", SwapKind::Accent(Mark::Breve)),
];

const DECO_ALTS: &[(Deco, &str)] = &[(Deco::None, "plain"), (Deco::Brace, "brace"), (Deco::Arrow, "arrow"), (Deco::Line, "line")];

const STYLED_ALTS: &[(&str, SwapKind)] = &[
    ("normal", SwapKind::Styled(Variant::Normal)),
    ("bold", SwapKind::Styled(Variant::Bold)),
    ("blackboard", SwapKind::Styled(Variant::Blackboard)),
    ("calligraphic", SwapKind::Styled(Variant::Calligraphic)),
    ("fraktur", SwapKind::Styled(Variant::Fraktur)),
    ("roman", SwapKind::Styled(Variant::Roman)),
    ("sans serif", SwapKind::Styled(Variant::SansSerif)),
    ("typewriter", SwapKind::Styled(Variant::Typewriter)),
    ("operator name", SwapKind::Styled(Variant::OperatorName)),
];

const MATRIX_ENV_ALTS: &[(&str, SwapKind)] = &[
    ("matrix", SwapKind::Matrix(MatrixEnv::Matrix)),
    ("( matrix )", SwapKind::Matrix(MatrixEnv::Pmatrix)),
    ("[ matrix ]", SwapKind::Matrix(MatrixEnv::Bmatrix)),
    ("| matrix |", SwapKind::Matrix(MatrixEnv::Vmatrix)),
    ("cases", SwapKind::Matrix(MatrixEnv::Cases)),
    ("aligned", SwapKind::Matrix(MatrixEnv::Aligned)),
    ("array", SwapKind::Matrix(MatrixEnv::Array)),
];