mathtex-editor-core 0.3.0

//! The editor: document, caret, selection, and menu state, changed only by explicit calls.

use std::fmt;
use std::sync::atomic::{AtomicU64, Ordering};

use mathtex_ir::Fragment;
use serde::{Deserialize, Serialize};

use crate::command::{Command, Dir, Edge, ExitDir, HostBoxEntry, HostBoxPolicy, Outcome, Side};
use crate::doc::{Document, DocumentError};
use crate::export::{self, Source};
use crate::geometry::{Point, RenderOutput, StaleSource};
use crate::menu::{Menu, MenuView, RowEffect};
use crate::model::{Cursor, Kind, NodeId, SeqId, SeqRange, Symbol, Tree};
use crate::path::{CaretPath, PathError, Selection};
use crate::{matcher, nav, selection};

/// Distinguishes editors so a [`Source`] only renders against the editor that exported it.
static NEXT_EDITOR: AtomicU64 = AtomicU64::new(1);

/// Everything needed to put an editor back into a previous state, the host keeps its own undo stack.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Snapshot {
    /// The document.
    pub document: Document,
    /// The caret.
    pub cursor: CaretPath,
    /// The selection, whose focus wins over `cursor` when present.
    pub selection: Option<Selection>,
}

/// Why [`Editor::restore`] refused a snapshot.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum RestoreError {
    /// The snapshot's document breaks a rule of [`Document::validate`].
    Document(DocumentError),
    /// A caret of the snapshot does not resolve in its document.
    Path(PathError),
}

impl From<PathError> for RestoreError {
    fn from(e: PathError) -> Self {
        RestoreError::Path(e)
    }
}

impl fmt::Display for RestoreError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            RestoreError::Document(e) => write!(f, "invalid snapshot document: {e}"),
            RestoreError::Path(e) => write!(f, "invalid snapshot caret: {e}"),
        }
    }
}

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

/// Facts a keymap needs to interpret the next key.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash)]
pub struct InputContext {
    /// The caret is inside `\text{}`, where keys insert literal text.
    pub in_text_slot: bool,
    /// The swap or delete menu is open and takes typed characters as its filter.
    pub menu_open: bool,
    /// The close character of the innermost delimiters whose end the caret sits at.
    pub closing_delimiter: Option<char>,
    /// Counts `exec`, `restore`, and caret setter calls, so a keymap sees whether anything ran between keys.
    pub serial: u64,
}

/// A headless structural math editor that never typesets, keeps no history, and has no callbacks.
pub struct Editor {
    tree: Tree,
    cursor: Cursor,
    /// Selection anchor gap in `cursor.seq`, the caret is the focus.
    anchor: Option<usize>,
    menu: Option<Menu>,
    revision: u64,
    serial: u64,
    id: u64,
    policy: HostBoxPolicy,
}

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

impl Editor {
    /// An empty editor.
    pub fn new() -> Self {
        Self::with_tree(Tree::new())
    }

    /// An editor holding `doc`, which must pass [`Document::validate`], see [`Document::repair`].
    pub fn from_document(doc: &Document) -> Result<Self, DocumentError> {
        doc.validate()?;
        Ok(Self::with_tree(Tree::from_doc(doc)))
    }

    fn with_tree(tree: Tree) -> Self {
        let cursor = Cursor { seq: tree.root(), index: 0 };
        Self {
            tree,
            cursor,
            anchor: None,
            menu: None,
            revision: 0,
            serial: 0,
            id: NEXT_EDITOR.fetch_add(1, Ordering::Relaxed),
            policy: HostBoxPolicy::Skip,
        }
    }

    /// The whole document.
    pub fn document(&self) -> Document {
        self.tree.to_doc()
    }

    /// Advances on every content change and on [`Editor::restore`], never on motion.
    pub fn revision(&self) -> u64 {
        self.revision
    }

    /// The caret, which is the selection focus while a selection is active.
    pub fn cursor(&self) -> CaretPath {
        self.tree.path_of(self.cursor)
    }

    /// Place the caret, collapsing the selection and closing the menu.
    pub fn set_cursor(&mut self, at: &CaretPath) -> Result<(), PathError> {
        let c = self.tree.resolve(at)?;
        self.cursor = c;
        self.anchor = None;
        self.menu = None;
        self.serial += 1;
        self.normalize();
        Ok(())
    }

    /// The active selection, `None` when the caret is collapsed.
    pub fn selection(&self) -> Option<Selection> {
        let s = self.sel()?;
        let steps = self.tree.seq_steps(s.seq);
        Some(Selection {
            anchor: CaretPath { steps: steps.clone(), index: s.anchor },
            focus: CaretPath { steps, index: s.focus },
        })
    }

    /// Select between two carets in the same sequence and close the menu.
    pub fn set_selection(&mut self, anchor: &CaretPath, focus: &CaretPath) -> Result<(), PathError> {
        let a = self.tree.resolve(anchor)?;
        let f = self.tree.resolve(focus)?;
        if a.seq != f.seq {
            return Err(PathError::SplitSelection);
        }
        self.cursor = f;
        self.anchor = Some(a.index);
        self.menu = None;
        self.serial += 1;
        self.normalize();
        Ok(())
    }

    /// Whether the caret is before everything in the formula.
    pub fn at_start(&self) -> bool {
        self.cursor == Cursor { seq: self.tree.root(), index: 0 }
    }

    /// Whether the caret is after everything in the formula.
    pub fn at_end(&self) -> bool {
        let root = self.tree.root();
        self.cursor == Cursor { seq: root, index: self.tree.len(root) }
    }

    /// Whether the caret is at the start of its slot.
    pub fn at_slot_start(&self) -> bool {
        self.cursor.index == 0
    }

    /// Whether the caret is at the end of its slot.
    pub fn at_slot_end(&self) -> bool {
        self.cursor.index == self.tree.len(self.cursor.seq)
    }

    /// Whether the caret is inside `\text{}`.
    pub fn in_text_slot(&self) -> bool {
        self.tree.is_text_slot(self.cursor.seq)
    }

    /// The open swap or delete menu.
    pub fn menu(&self) -> Option<MenuView> {
        self.menu.as_ref().map(Menu::view)
    }

    /// Rows and columns of the matrix whose cell holds the caret.
    pub fn matrix_shape(&self) -> Option<(usize, usize)> {
        self.tree.matrix_shape_at(self.cursor)
    }

    /// Everything a keymap needs to know about the caret in one call.
    pub fn input_context(&self) -> InputContext {
        InputContext {
            in_text_slot: self.in_text_slot(),
            menu_open: self.menu.is_some(),
            closing_delimiter: self.innermost_delim().and_then(|(_, close, body)| self.at_end_of(body).then_some(close)),
            serial: self.serial,
        }
    }

    /// Choose whether horizontal motion steps over host boxes or stops and reports them.
    pub fn set_host_box_policy(&mut self, policy: HostBoxPolicy) {
        self.policy = policy;
    }

    /// Put the caret at an edge of the formula, clearing selection and menu.
    pub fn place_at(&mut self, edge: Edge) {
        let root = self.tree.root();
        let index = match edge {
            Edge::Start => 0,
            Edge::End => self.tree.len(root),
        };
        self.cursor = Cursor { seq: root, index };
        self.anchor = None;
        self.menu = None;
        self.serial += 1;
    }

    /// LaTeX for typesetting, with `\phantom{x}` boxes in empty slots so they can be drawn.
    pub fn source(&self) -> Source {
        export::source(&self.tree, self.id, self.revision, true)
    }

    /// Clean LaTeX with spans, so hosts can map a caret to a byte offset in what users see.
    pub fn display_source(&self) -> Source {
        export::source(&self.tree, self.id, self.revision, false)
    }

    fn check(&self, source: &Source) -> Result<(), StaleSource> {
        if source.revision == self.revision && source.spans.owner == self.id {
            Ok(())
        } else {
            Err(StaleSource { source: source.revision, editor: self.revision })
        }
    }

    /// Geometry for the caret, selection, placeholders, menu, and host boxes over `fragment`.
    pub fn render(&self, source: &Source, fragment: &Fragment) -> Result<RenderOutput, StaleSource> {
        self.check(source)?;
        let menu = self.menu.as_ref().map(|m| m.anchor);
        Ok(matcher::render(&self.tree, self.cursor, self.sel(), &source.spans, fragment, menu))
    }

    /// The caret nearest `at`, `None` when the fragment has no geometry to hit.
    pub fn hit_test(&self, source: &Source, fragment: &Fragment, at: Point) -> Result<Option<CaretPath>, StaleSource> {
        self.check(source)?;
        let hit = matcher::hit_test(&self.tree, &source.spans, fragment, at);
        Ok(hit.map(|c| self.tree.path_of(nav::normalize(&self.tree, c))))
    }

    /// The current state for a host undo stack.
    pub fn snapshot(&self) -> Snapshot {
        Snapshot { document: self.document(), cursor: self.cursor(), selection: self.selection() }
    }

    /// Return to a snapshot, closing the menu and advancing the revision, unchanged on error.
    pub fn restore(&mut self, s: &Snapshot) -> Result<(), RestoreError> {
        s.document.validate().map_err(RestoreError::Document)?;
        let tree = Tree::from_doc(&s.document);
        let (cursor, anchor) = match &s.selection {
            Some(sel) => {
                let a = tree.resolve(&sel.anchor)?;
                let f = tree.resolve(&sel.focus)?;
                if a.seq != f.seq {
                    return Err(PathError::SplitSelection.into());
                }
                (f, Some(a.index))
            }
            None => (tree.resolve(&s.cursor)?, None),
        };
        self.tree = tree;
        self.cursor = cursor;
        self.anchor = anchor;
        self.menu = None;
        self.revision += 1;
        self.serial += 1;
        self.normalize();
        Ok(())
    }

    /// The selected nodes as a standalone document for the clipboard.
    pub fn selection_document(&self) -> Option<Document> {
        let s = self.sel()?;
        let items = self.tree.items(s.seq);
        let hi = s.hi().min(items.len());
        Some(Document::new(items[s.lo()..hi].iter().filter_map(|&n| self.tree.node_to_doc(n)).collect()))
    }

    /// The selection as clean LaTeX for external clipboards.
    pub fn selection_tex(&self) -> Option<String> {
        self.sel().map(|s| export::range_tex(&self.tree, s))
    }

    /// Run one command and report what it did.
    pub fn exec(&mut self, cmd: Command) -> Outcome {
        let edits = self.tree.edits;
        let before = self.position();
        let mut out = Outcome::default();
        self.serial += 1;
        self.run(cmd, &mut out);
        out.changed = self.tree.edits != edits;
        if out.changed {
            self.revision += 1;
        }
        out.moved = self.position() != before;
        out.revision = self.revision;
        out
    }

    fn position(&self) -> (CaretPath, Option<usize>) {
        (self.cursor(), self.sel().map(|s| s.anchor))
    }

    fn sel(&self) -> Option<SeqRange> {
        let a = self.anchor.filter(|&a| a != self.cursor.index)?;
        Some(SeqRange { seq: self.cursor.seq, anchor: a, focus: self.cursor.index })
    }

    fn set(&mut self, c: Cursor) {
        self.cursor = c;
        self.anchor = None;
    }

    /// Apply an edit result, a refused edit leaves caret and selection alone.
    fn edit(&mut self, result: Option<Cursor>) {
        if let Some(c) = result {
            self.set(c);
        }
    }

    fn run(&mut self, cmd: Command, out: &mut Outcome) {
        if self.menu.is_some() {
            if self.run_menu(&cmd) {
                self.normalize();
                return;
            }
            // Any other command closes the menu and then runs normally.
            self.menu = None;
        }
        self.dispatch(cmd, out);
        self.normalize();
    }

    fn dispatch(&mut self, cmd: Command, out: &mut Outcome) {
        let at = self.cursor;
        let sel = self.sel();
        match cmd {
            Command::Move(dir @ (Dir::Left | Dir::Right)) => {
                let right = dir == Dir::Right;
                if self.policy == HostBoxPolicy::Enter {
                    if let Some(token) = self.host_box_neighbor(right) {
                        let side = if right { Side::Before } else { Side::After };
                        out.entered_host_box = Some(HostBoxEntry { token, side });
                        return;
                    }
                }
                let next = if right { nav::move_right(&self.tree, at) } else { nav::move_left(&self.tree, at) };
                match next {
                    Some(c) => self.set(c),
                    None => self.boundary(if right { ExitDir::Right } else { ExitDir::Left }, out),
                }
            }
            Command::Move(dir) => {
                let up = dir == Dir::Up;
                match nav::vertical(&self.tree, at, up) {
                    Some(c) => self.set(c),
                    None => self.boundary(if up { ExitDir::Up } else { ExitDir::Down }, out),
                }
            }
            Command::MoveLineStart => self.set(Cursor { seq: at.seq, index: 0 }),
            Command::MoveLineEnd => self.set(Cursor { seq: at.seq, index: self.tree.len(at.seq) }),
            Command::Tab => match self.next_fill_target(true) {
                Some(c) => self.set(c),
                None => out.exit = Some(ExitDir::Right),
            },
            Command::ShiftTab => match self.next_fill_target(false) {
                Some(c) => self.set(c),
                None => out.exit = Some(ExitDir::Left),
            },
            Command::MoveTo(path) => {
                if let Ok(c) = self.tree.resolve(&path) {
                    self.set(c);
                }
            }
            Command::ExtendTo(path) => {
                if let Ok(target) = self.tree.resolve(&path) {
                    let anchor = Cursor { seq: at.seq, index: self.anchor.unwrap_or(at.index) };
                    self.select(selection::extend_to(&self.tree, anchor, target));
                }
            }
            Command::Extend(dir @ (Dir::Left | Dir::Right)) => {
                let s = sel.unwrap_or(SeqRange { seq: at.seq, anchor: at.index, focus: at.index });
                self.select(selection::extend(&self.tree, s, dir == Dir::Right));
            }
            Command::Extend(_) => {}
            Command::SelectAll => self.select(selection::select_all(&self.tree)),
            Command::Collapse | Command::Confirm => self.anchor = None,
            Command::MenuSelect(_) => {}
            Command::InsertAtom(sym) => {
                let r = self.tree.insert_atom(at, sel, sym);
                self.edit(r);
            }
            Command::InsertHostBox(token) => {
                let r = self.tree.insert_host_box(at, sel, token);
                self.edit(r);
            }
            Command::InsertText(text) => self.insert_text(&text),
            Command::InsertFraction(style) => {
                let r = self.tree.insert_fraction(at, style, sel);
                self.edit(r);
            }
            Command::InsertScript(slot) => {
                // `_` and `^` right after a big operator move into its limits.
                if let (None, Some(c)) = (sel, self.tree.bigop_limit_target(at, slot)) {
                    self.set(c);
                } else {
                    let r = self.tree.attach_script(at, slot, sel);
                    self.edit(r);
                }
            }
            Command::InsertBigOp(op) => {
                let r = self.tree.insert_big_op(at, sel, op);
                self.edit(r);
            }
            Command::InsertSqrt => {
                let r = self.tree.insert_sqrt(at, sel);
                self.edit(r);
            }
            Command::InsertDelimiters { open, close } => {
                let r = self.tree.insert_delimiters(at, open, close, sel);
                self.edit(r);
            }
            Command::InsertAccent(mark) => {
                let r = self.tree.insert_accent(at, mark, sel);
                self.edit(r);
            }
            Command::InsertUnderOver(spec) => {
                let r = self.tree.insert_under_over(at, spec, sel);
                self.edit(r);
            }
            Command::InsertStyled(variant) => {
                let r = self.tree.insert_styled(at, variant, sel);
                self.edit(r);
            }
            Command::InsertMatrix { env, rows, cols } => {
                let r = self.tree.insert_matrix(at, sel, env, rows, cols);
                self.edit(r);
            }
            Command::InsertDocument(doc) => {
                if doc.validate().is_err() {
                    return;
                }
                let r = self.tree.insert_doc(at, sel, &doc);
                self.edit(r);
            }
            Command::DeleteBackward | Command::DeleteForward => {
                let back = cmd == Command::DeleteBackward;
                let neighbor = if back {
                    nav::adjacent_structure_backward(&self.tree, at)
                } else {
                    nav::adjacent_structure_forward(&self.tree, at)
                };
                if let Some(s) = sel {
                    let c = self.tree.delete_range(s);
                    self.set(c);
                } else if let Some(node) = neighbor {
                    self.select_or_open_menu(node);
                } else if at.seq == self.tree.root() && self.tree.is_empty(at.seq) {
                    out.close = true;
                } else {
                    let c = if back { self.tree.delete_backward(at) } else { self.tree.delete_forward(at) };
                    self.set(c);
                }
            }
            Command::MatrixInsertRow(side) => {
                let r = self.tree.matrix_insert_row(at, side);
                self.edit(r);
            }
            Command::MatrixDeleteRow => {
                let r = self.tree.matrix_delete_row(at);
                self.edit(r);
            }
            Command::MatrixInsertCol(side) => {
                let r = self.tree.matrix_insert_col(at, side);
                self.edit(r);
            }
            Command::MatrixDeleteCol => {
                let r = self.tree.matrix_delete_col(at);
                self.edit(r);
            }
            Command::ReplaceTyped { typed, with } => {
                if sel.is_none() && self.typed_matches(&typed) {
                    let n = typed.chars().count();
                    let c = self.tree.delete_range(SeqRange { seq: at.seq, anchor: at.index - n, focus: at.index });
                    self.set(c);
                    self.normalize();
                    for cmd in with {
                        self.run(cmd, out);
                    }
                }
            }
            Command::CloseDelimiter(close) => {
                if sel.is_none() {
                    if let Some(after) = self.closing_target(close) {
                        self.set(after);
                        return;
                    }
                }
                if let Some(sym) = Symbol::from_char(close) {
                    let r = self.tree.insert_atom(at, sel, sym);
                    self.edit(r);
                }
            }
        }
    }

    /// Consume commands the open menu understands, `false` lets the command close it and run.
    fn run_menu(&mut self, cmd: &Command) -> bool {
        let Some(menu) = self.menu.as_mut() else {
            return false;
        };
        match cmd {
            Command::InsertAtom(sym) if sym.latex.chars().count() == 1 => {
                menu.query.push_str(&sym.latex);
                menu.selected = 0;
            }
            Command::InsertText(text) => {
                menu.query.push_str(text);
                menu.selected = 0;
            }
            // With an empty filter both deletes remove the structure, otherwise they edit the filter.
            Command::DeleteBackward | Command::DeleteForward => {
                if menu.query.pop().is_none() {
                    self.commit_menu_row(0);
                } else {
                    menu.selected = 0;
                }
            }
            Command::Move(Dir::Up) => menu.selected = menu.selected.saturating_sub(1),
            Command::Move(Dir::Down) => {
                let max = menu.visible().len().saturating_sub(1);
                menu.selected = (menu.selected + 1).min(max);
            }
            Command::Confirm => {
                let selected = menu.selected;
                self.commit_menu_row(selected);
            }
            Command::MenuSelect(i) => self.commit_menu_row(*i),
            Command::Collapse => self.menu = None,
            _ => return false,
        }
        true
    }

    /// Commit a visible menu row by deleting or swapping the anchored structure.
    fn commit_menu_row(&mut self, visible_idx: usize) {
        let Some(menu) = self.menu.take() else {
            return;
        };
        match menu.visible().get(visible_idx) {
            Some(RowEffect::Delete) => {
                if let Some((seq, idx)) = self.tree.index_in_parent(menu.anchor) {
                    let c = self.tree.delete_range(SeqRange { seq, anchor: idx, focus: idx + 1 });
                    self.set(c);
                }
            }
            Some(RowEffect::Swap(kind)) => self.tree.apply_swap(menu.anchor, kind),
            None => {}
        }
    }

    /// Open the swap or delete menu for swappable structures, else select the node.
    fn select_or_open_menu(&mut self, node: NodeId) {
        match self.tree.swap_variants(node) {
            Some(variants) => self.menu = Some(Menu::for_node(node, variants)),
            None => {
                if let Some((seq, idx)) = self.tree.index_in_parent(node) {
                    self.select(SeqRange { seq, anchor: idx, focus: idx + 1 });
                }
            }
        }
    }

    fn select(&mut self, s: SeqRange) {
        self.cursor = Cursor { seq: s.seq, index: s.focus };
        self.anchor = Some(s.anchor);
    }

    fn insert_text(&mut self, text: &str) {
        let text_slot = self.tree.is_text_slot(self.cursor.seq);
        let mut sel = self.sel();
        let mut at = self.cursor;
        let mut any = false;
        for ch in text.chars() {
            if ch == ' ' && !text_slot {
                continue;
            }
            let Some(sym) = Symbol::from_char(ch) else { continue };
            if let Some(c) = self.tree.insert_atom(at, sel.take(), sym) {
                at = c;
                any = true;
            }
        }
        if any {
            self.set(at);
        }
    }

    /// Collapse an active selection at a boundary, or report the exit for a plain caret.
    fn boundary(&mut self, dir: ExitDir, out: &mut Outcome) {
        if self.sel().is_some() {
            self.anchor = None;
        } else {
            out.exit = Some(dir);
        }
    }

    /// The token of the host box the caret would cross next.
    fn host_box_neighbor(&self, right: bool) -> Option<u32> {
        let items = self.tree.items(self.cursor.seq);
        let node = if right { items.get(self.cursor.index) } else { items.get(self.cursor.index.checked_sub(1)?) };
        match self.tree.kind(*node?) {
            Some(Kind::HostBox { token }) => Some(*token),
            _ => None,
        }
    }

    /// Whether the atoms directly left of the caret spell `typed`.
    fn typed_matches(&self, typed: &str) -> bool {
        let items = self.tree.items(self.cursor.seq);
        let n = typed.chars().count();
        let Some(start) = self.cursor.index.checked_sub(n) else {
            return false;
        };
        typed.chars().zip(&items[start..self.cursor.index]).all(|(ch, &node)| {
            matches!((self.tree.kind(node), Symbol::from_char(ch)), (Some(Kind::Atom(s)), Some(e)) if s.latex == e.latex)
        })
    }

    /// The innermost delimiters around the caret as `(node, close, body)`.
    fn innermost_delim(&self) -> Option<(NodeId, char, SeqId)> {
        let mut seq = self.cursor.seq;
        loop {
            let node = self.tree.seq_parent(seq)?;
            if let Some(Kind::Delim { close, body, .. }) = self.tree.kind(node) {
                return Some((node, *close, *body));
            }
            seq = self.tree.before_parent(seq)?.seq;
        }
    }

    /// Whether moving right from the caret would only climb out until the end of `body`.
    fn at_end_of(&self, body: SeqId) -> bool {
        let mut cur = self.cursor;
        loop {
            if cur.index != self.tree.len(cur.seq) {
                return false;
            }
            if cur.seq == body {
                return true;
            }
            let Some(node) = self.tree.seq_parent(cur.seq) else {
                return false;
            };
            if self.tree.child_seqs(node).last() != Some(&cur.seq) {
                return false;
            }
            let Some((seq, idx)) = self.tree.index_in_parent(node) else {
                return false;
            };
            cur = Cursor { seq, index: idx + 1 };
        }
    }

    /// The gap after the innermost enclosing delimiters closed by `close` whose end the caret is at.
    fn closing_target(&self, close: char) -> Option<Cursor> {
        let mut seq = self.cursor.seq;
        loop {
            let node = self.tree.seq_parent(seq)?;
            if let Some(Kind::Delim { close: c, body, .. }) = self.tree.kind(node) {
                if *c == close && self.at_end_of(*body) {
                    let (pseq, idx) = self.tree.index_in_parent(node)?;
                    return Some(Cursor { seq: pseq, index: idx + 1 });
                }
            }
            seq = self.tree.before_parent(seq)?.seq;
        }
    }

    fn next_fill_target(&self, forward: bool) -> Option<Cursor> {
        let at = self.cursor;
        let tree = &self.tree;
        let empty_start = |s: SeqId| tree.is_empty(s).then_some(Cursor { seq: s, index: 0 });
        if forward {
            // Big operator limits fill in reading order, lower then upper.
            if let Some(Kind::BigOp { lower, upper, .. }) = tree.seq_parent(at.seq).and_then(|p| tree.kind(p)) {
                if at.seq == *lower {
                    if let Some(c) = empty_start(*upper) {
                        return Some(c);
                    }
                }
            }
            let prev = at.index.checked_sub(1).and_then(|i| tree.items(at.seq).get(i));
            if let Some(Kind::BigOp { lower, upper, .. }) = prev.and_then(|&p| tree.kind(p)) {
                if let Some(c) = empty_start(*lower).or_else(|| empty_start(*upper)) {
                    return Some(c);
                }
            }
            // From a radicand, visit an empty degree before continuing.
            if let Some(Kind::Sqrt { index, radicand }) = tree.seq_parent(at.seq).and_then(|p| tree.kind(p)) {
                if at.seq == *radicand {
                    if let Some(c) = empty_start(*index) {
                        return Some(c);
                    }
                }
            }
        }
        nav::next_empty_slot(tree, at, forward).map(|seq| Cursor { seq, index: 0 })
    }

    /// Restore every caret invariant, run after each command and state setter.
    fn normalize(&mut self) {
        let root = self.tree.root();
        if !self.tree.seqs.contains_key(self.cursor.seq) {
            self.cursor = Cursor { seq: root, index: self.tree.len(root) };
            self.anchor = None;
        }
        let len = self.tree.len(self.cursor.seq);
        self.cursor.index = self.cursor.index.min(len);
        self.anchor = self.anchor.map(|a| a.min(len));
        loop {
            match self.anchor {
                Some(a) if a != self.cursor.index => {
                    // A focus on an illegal gap grows the selection to cover the whole Script.
                    if !nav::is_illegal(&self.tree, self.cursor) {
                        break;
                    }
                    let Some(p) = self.tree.before_parent(self.cursor.seq) else { break };
                    self.anchor = Some(p.index + 1);
                    self.cursor = p;
                }
                _ => {
                    self.anchor = None;
                    self.cursor = nav::normalize(&self.tree, self.cursor);
                    break;
                }
            }
        }
        if self.menu.as_ref().is_some_and(|m| !self.tree.nodes.contains_key(m.anchor)) {
            self.menu = None;
        }
    }

    #[cfg(test)]
    pub(crate) fn tree(&self) -> &Tree {
        &self.tree
    }

    #[cfg(test)]
    pub(crate) fn raw_cursor(&self) -> Cursor {
        self.cursor
    }

    #[cfg(test)]
    pub(crate) fn raw_anchor(&self) -> Option<usize> {
        self.anchor
    }

    #[cfg(test)]
    pub(crate) fn menu_anchor(&self) -> Option<NodeId> {
        self.menu.as_ref().map(|m| m.anchor)
    }
}