mathtex_editor_core/

matcher.rs

//! Matcher geometry and render support for mapping model spans to mathtex IR boxes in SVG point units.

use std::collections::HashMap;

use crate::command::Point;
use crate::export::SpanMap;
use crate::host::{HostObject, Metrics, Rect, RenderOutput};
use crate::menu::{Menu, MenuItem, MenuView};
use crate::model::{Cursor, Kind, NodeId, Selection, SeqId, Tree};

use mathtex_ir::{Fragment, LayoutNode, LayoutNodeKind, NodeId as IrId, Point as IrPoint};

/// Geometry for each model element, resolved from the IR in points.
#[derive(Debug, Clone, Default)]
pub struct BoxMap {
    /// Rectangles for model nodes.
    pub node: HashMap<NodeId, Rect>,
    /// Rectangles for model sequences.
    pub seq: HashMap<SeqId, Rect>,
}

/// Match the typeset IR to the model by source span, then compute caret and selection rects.
pub(crate) fn render(
    tree: &Tree,
    cursor: Cursor,
    sel: Option<Selection>,
    spans: &SpanMap,
    ir: Fragment,
    menu: Option<&Menu>,
) -> RenderOutput {
    let boxes = match_boxes(spans, &ir);
    let caret = caret_rect(&boxes, tree, cursor);
    let selection = sel
        .map(|s| selection_rects(&boxes, tree, s))
        .unwrap_or_default();
    // Empty slot phantom boxes become placeholder rects for the host to draw.
    let placeholders: Vec<Rect> = spans
        .seq
        .keys()
        .filter(|&&s| tree.is_empty(s))
        .filter_map(|s| boxes.seq.get(s).copied())
        .collect();
    let metrics = Metrics {
        width: pt(ir.surface.width),
        height: pt(ir.surface.height),
        baseline: pt(ir.surface.baseline),
    };
    // The dropdown anchors at the swappable or deletable node's own box.
    let menu = menu.map(|m| MenuView {
        anchor: boxes.node.get(&m.anchor).copied().unwrap_or(ZERO),
        items: m
            .visible()
            .iter()
            .map(|row| MenuItem { label: row.label() })
            .collect(),
        selected: m.selected,
        query: m.query.clone(),
    });
    // Host object atoms report their matched box so the host can overlay their content.
    let host_objects: Vec<HostObject> = spans
        .node
        .keys()
        .filter_map(|&n| match tree.kind(n) {
            Some(Kind::HostBox { token }) => boxes
                .node
                .get(&n)
                .map(|&rect| HostObject { token: *token, rect }),
            _ => None,
        })
        .collect();
    RenderOutput {
        ir,
        caret,
        selection,
        placeholders,
        metrics,
        menu,
        host_objects,
    }
}

/// Map each model element to the union of IR boxes whose source span is contained in its export range.
pub fn match_boxes(spans: &SpanMap, fragment: &Fragment) -> BoxMap {
    let abs = absolute_origins(fragment);
    // Parent links let empty range fallback walk through redundant wrappers.
    let mut parent: HashMap<IrId, IrId> = HashMap::new();
    for n in &fragment.nodes {
        for c in children_of(n) {
            parent.insert(c, n.id);
        }
    }
    // Index leaves, fallback containers, and box metrics by source span.
    let mut box_metrics: Vec<(usize, usize, f64, f64)> = Vec::new();
    for n in &fragment.nodes {
        let LayoutNodeKind::Box(bx) = &n.kind else { continue };
        let Some(s) = n.primary_source else { continue };
        let (a, b) = (s.span.start as usize, s.span.end as usize);
        box_metrics.push((a, b, pt(bx.metrics.height), pt(bx.metrics.depth)));
    }
    // Exact span plus nearest size finds the glyph run's own box instead of a containing box.
    let own_box_split = |a: usize, b: usize, glyph_total: f64| -> Option<(f64, f64)> {
        box_metrics
            .iter()
            .filter(|(ba, bb, _, _)| *ba == a && *bb == b)
            .min_by(|(_, _, h1, d1), (_, _, h2, d2)| {
                let e1 = (h1 + d1 - glyph_total).abs();
                let e2 = (h2 + d2 - glyph_total).abs();
                e1.total_cmp(&e2)
            })
            .map(|(_, _, h, d)| (*h, *d))
    };
    let mut leaves: Vec<(usize, usize, Rect)> = Vec::new();
    let mut containers: Vec<(IrId, usize, usize, Rect)> = Vec::new();
    for n in &fragment.nodes {
        let Some(s) = n.primary_source else { continue };
        let (a, b) = (s.span.start as usize, s.span.end as usize);
        if a >= b {
            continue;
        }
        // A zero area `Rule` draws nothing, so it carries no visible geometry.
        if let LayoutNodeKind::Rule(r) = &n.kind {
            if r.size.width.0 == 0 || r.size.height.0 == 0 {
                continue;
            }
        }
        // Spacing carries the last atom's span in the IR, so glue and kern never define geometry.
        if matches!(n.kind, LayoutNodeKind::Glue(_) | LayoutNodeKind::Kern(_)) {
            continue;
        }
        let mut rect = rect_of(fragment, &abs, n.id);
        if matches!(
            n.kind,
            LayoutNodeKind::GlyphRun(_) | LayoutNodeKind::Rule(_) | LayoutNodeKind::Drawing(_)
        ) {
            // Recompute glyph vertical bounds from its own height and depth split.
            if let LayoutNodeKind::GlyphRun(_) = &n.kind {
                let glyph_total = pt(n.bounds.size.height);
                if let (Some((h, d)), Some(o)) = (own_box_split(a, b, glyph_total), abs.get(&n.id))
                {
                    rect.y = pt(o.y) - h;
                    rect.height = h + d;
                }
            }
            leaves.push((a, b, rect));
        } else {
            // A `Box`'s own metrics give the above and below baseline split.
            if let LayoutNodeKind::Box(bx) = &n.kind {
                if let Some(o) = abs.get(&n.id) {
                    rect.y = pt(o.y) - pt(bx.metrics.height);
                    rect.height = pt(bx.metrics.height) + pt(bx.metrics.depth);
                    // Childless boxes such as host boxes have empty bounds but a real advance width.
                    rect.width = rect.width.max(pt(bx.metrics.width));
                }
            }
            containers.push((n.id, a, b, rect));
        }
    }
    // A container has no ink of its own if no leaf span is contained within it.
    let is_leafless =
        |ca: usize, cb: usize| !leaves.iter().any(|(la, lb, _)| *la >= ca && *lb <= cb);
    let union_in = |range: &std::ops::Range<usize>| -> Option<Rect> {
        let leaf_rects: Vec<Rect> = leaves
            .iter()
            .filter(|(a, b, _)| *a >= range.start && *b <= range.end)
            .map(|(_, _, r)| *r)
            .collect();
        // Prefer deepest leafless containers so wrapper padding doesn't detach the caret.
        let leafless: Vec<(IrId, Rect)> = containers
            .iter()
            .filter(|(_, a, b, _)| *a >= range.start && *b <= range.end)
            .filter(|(_, a, b, _)| is_leafless(*a, *b))
            .map(|(id, _, _, r)| (*id, *r))
            .collect();
        let mut has_leafless_descendant: std::collections::HashSet<IrId> =
            std::collections::HashSet::new();
        for (id, _) in &leafless {
            let mut cur = *id;
            while let Some(&p) = parent.get(&cur) {
                if leafless.iter().any(|(cid, _)| *cid == p) {
                    has_leafless_descendant.insert(p);
                }
                cur = p;
            }
        }
        let leafless_deepest: Vec<Rect> = leafless
            .iter()
            .filter(|(id, _)| !has_leafless_descendant.contains(id))
            .map(|(_, r)| *r)
            .collect();
        union(&[leaf_rects, leafless_deepest].concat())
    };
    let mut map = BoxMap::default();
    for (&node, range) in &spans.node {
        if let Some(r) = union_in(range) {
            map.node.insert(node, r);
        }
    }
    for (&seq, range) in &spans.seq {
        if let Some(r) = union_in(range) {
            map.seq.insert(seq, r);
        }
    }
    map
}

/// Absolute origin of every node, accumulating parent relative `origin` down the box tree.
fn absolute_origins(fragment: &Fragment) -> HashMap<IrId, IrPoint> {
    let mut map = HashMap::new();
    if let Some(root) = select_root(fragment) {
        // mathtex-svg seeds the y axis with the surface baseline to match SVG viewBox coordinates.
        let base = IrPoint {
            x: mathtex_ir::Length(0),
            y: fragment.surface.baseline,
        };
        walk_origins(fragment, root, base, &mut map);
    }
    // Nodes not reached from the root keep their own origin as a fallback.
    for n in &fragment.nodes {
        map.entry(n.id).or_insert(n.origin);
    }
    map
}

fn walk_origins(fragment: &Fragment, id: IrId, parent_abs: IrPoint, map: &mut HashMap<IrId, IrPoint>) {
    let Some(node) = fragment.node(id) else { return };
    let abs = IrPoint {
        x: mathtex_ir::Length(parent_abs.x.0.saturating_add(node.origin.x.0)),
        y: mathtex_ir::Length(parent_abs.y.0.saturating_add(node.origin.y.0)),
    };
    map.insert(id, abs);
    for child in children_of(node) {
        walk_origins(fragment, child, abs, map);
    }
}

fn children_of(node: &LayoutNode) -> Vec<IrId> {
    match &node.kind {
        LayoutNodeKind::Box(b) => b.children.clone(),
        LayoutNodeKind::List(l) => l.children.clone(),
        LayoutNodeKind::Group { children } => children.clone(),
        _ => Vec::new(),
    }
}

/// The root box is the `Box` that no node lists as a child, matching mathtex-svg.
fn select_root(fragment: &Fragment) -> Option<IrId> {
    let mut is_child = std::collections::HashSet::new();
    for n in &fragment.nodes {
        for c in children_of(n) {
            is_child.insert(c);
        }
    }
    fragment.nodes.iter().find_map(|n| match n.kind {
        LayoutNodeKind::Box(_) if !is_child.contains(&n.id) => Some(n.id),
        _ => None,
    })
}

fn rect_of(fragment: &Fragment, abs: &HashMap<IrId, IrPoint>, id: IrId) -> Rect {
    let Some(n) = fragment.node(id) else {
        return ZERO;
    };
    let o = abs.get(&id).copied().unwrap_or(n.origin);
    // `o.y` is the node baseline in SVG coordinates, while bounds are TeX style baseline relative.
    Rect {
        x: pt(mathtex_ir::Length(o.x.0.saturating_add(n.bounds.origin.x.0))),
        y: pt(mathtex_ir::Length(
            o.y.0
                .saturating_sub(n.bounds.origin.y.0)
                .saturating_sub(n.bounds.size.height.0),
        )),
        width: pt(n.bounds.size.width),
        height: pt(n.bounds.size.height),
    }
}

/// Caret rect for a cursor, using the left neighbor or next item when at sequence start.
pub fn caret_rect(boxes: &BoxMap, tree: &Tree, cursor: Cursor) -> Rect {
    // Empty slot uses the phantom slot box.
    if tree.is_empty(cursor.seq) {
        return boxes
            .seq
            .get(&cursor.seq)
            .map(|v| caret_at(v.x, v))
            .unwrap_or(ZERO);
    }
    let items = tree.items(cursor.seq);
    // Use the previous item at its right edge, else the next item at its left edge.
    let placement = if cursor.index > 0 {
        Some((items[cursor.index - 1], true))
    } else if cursor.index < items.len() {
        Some((items[cursor.index], false))
    } else {
        None
    };
    if let Some((node, right_edge)) = placement {
        if let Some(v) = boxes.node.get(&node) {
            return caret_at(if right_edge { v.x + v.width } else { v.x }, v);
        }
    }
    boxes
        .seq
        .get(&cursor.seq)
        .map(|v| caret_at(v.x, v))
        .unwrap_or(ZERO)
}

/// A zero width caret at `x`, spanning the vertical extent of `v`.
fn caret_at(x: f64, v: &Rect) -> Rect {
    Rect {
        x,
        y: v.y,
        width: 0.0,
        height: v.height,
    }
}

/// Highlight rects for a single seq selection run using the union of the run's node boxes.
pub fn selection_rects(boxes: &BoxMap, tree: &Tree, sel: Selection) -> Vec<Rect> {
    let lo = sel.anchor.min(sel.focus);
    let hi = sel.anchor.max(sel.focus).min(tree.len(sel.seq));
    let rects: Vec<Rect> = tree.items(sel.seq)[lo..hi]
        .iter()
        .filter_map(|n| boxes.node.get(n).copied())
        .collect();
    union(&rects).into_iter().collect()
}

/// Reverse hit test from a point to the model cursor position.
pub fn hit_test(fragment: &Fragment, spans: &SpanMap, tree: &Tree, point: Point) -> Cursor {
    hit_test_boxes(&match_boxes(spans, fragment), spans, tree, point)
}

/// Target resolved from a hit test point.
#[derive(Clone, Copy)]
enum Target {
    Node(NodeId),
    EmptySeq(SeqId),
}

/// Hit test over an already matched [`BoxMap`] for fallback testing without a real IR `Fragment`.
fn hit_test_boxes(boxes: &BoxMap, spans: &SpanMap, tree: &Tree, point: Point) -> Cursor {
    let mut best: Option<(Target, Rect, usize)> = None;
    for (&node, &rect) in &boxes.node {
        if contains(&rect, point) {
            let span = spans.node.get(&node).map_or(usize::MAX, |r| r.end - r.start);
            if best.as_ref().is_none_or(|(_, _, s)| span < *s) {
                best = Some((Target::Node(node), rect, span));
            }
        }
    }
    // Empty seqs have no node, so their phantom placeholder box is the only direct hit target.
    for (&seq, &rect) in &boxes.seq {
        if tree.is_empty(seq) && contains(&rect, point) {
            let span = spans.seq.get(&seq).map_or(usize::MAX, |r| r.end - r.start);
            if best.as_ref().is_none_or(|(_, _, s)| span < *s) {
                best = Some((Target::EmptySeq(seq), rect, span));
            }
        }
    }
    // Misses during drag resolve to the nearest box instead of jumping to document start.
    let chosen = best
        .map(|(t, r, _)| (t, r))
        .or_else(|| nearest_target(boxes, tree, point));
    if let Some((target, rect)) = chosen {
        if let Some(c) = resolve_target(tree, target, rect, point) {
            return c;
        }
    }
    Cursor {
        seq: tree.root(),
        index: 0,
    }
}

fn resolve_target(tree: &Tree, target: Target, rect: Rect, point: Point) -> Option<Cursor> {
    match target {
        Target::Node(node) => {
            let (seq, idx) = tree.index_in_parent(node)?;
            let mid = rect.x + rect.width / 2.0;
            let index = if point.x > mid { idx + 1 } else { idx };
            Some(Cursor { seq, index })
        }
        // An empty seq has exactly one position at its own start.
        Target::EmptySeq(seq) => Some(Cursor { seq, index: 0 }),
    }
}

/// The node or empty seq box nearest `point`, by squared distance to the rect's nearest edge.
fn nearest_target(boxes: &BoxMap, tree: &Tree, point: Point) -> Option<(Target, Rect)> {
    let nodes = boxes
        .node
        .iter()
        .map(|(&n, &r)| (Target::Node(n), r, rect_dist2(&r, point)));
    let empty_seqs = boxes
        .seq
        .iter()
        .filter(|&(&s, _)| tree.is_empty(s))
        .map(|(&s, &r)| (Target::EmptySeq(s), r, rect_dist2(&r, point)));
    nodes
        .chain(empty_seqs)
        .min_by(|(_, _, a), (_, _, b)| a.total_cmp(b))
        .map(|(t, r, _)| (t, r))
}

/// Squared distance from `p` to the nearest point on `r`, or 0 if `p` is inside.
fn rect_dist2(r: &Rect, p: Point) -> f64 {
    let cx = p.x.clamp(r.x, r.x + r.width);
    let cy = p.y.clamp(r.y, r.y + r.height);
    let (dx, dy) = (p.x - cx, p.y - cy);
    dx * dx + dy * dy
}

const ZERO: Rect = Rect {
    x: 0.0,
    y: 0.0,
    width: 0.0,
    height: 0.0,
};

fn contains(r: &Rect, p: Point) -> bool {
    p.x >= r.x && p.x <= r.x + r.width && p.y >= r.y && p.y <= r.y + r.height
}
fn union(rects: &[Rect]) -> Option<Rect> {
    let first = rects.first()?;
    let (mut x0, mut y0) = (first.x, first.y);
    let (mut x1, mut y1) = (first.x + first.width, first.y + first.height);
    for r in &rects[1..] {
        x0 = x0.min(r.x);
        y0 = y0.min(r.y);
        x1 = x1.max(r.x + r.width);
        y1 = y1.max(r.y + r.height);
    }
    Some(Rect {
        x: x0,
        y: y0,
        width: x1 - x0,
        height: y1 - y0,
    })
}

/// Scaled points convert to points matching the SVG `viewBox` units.
fn pt(len: mathtex_ir::Length) -> f64 {
    len.0 as f64 / 65536.0
}

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

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

    /// Misses in gaps or vertical drag wobble must resolve to the nearest box, not document start.
    #[test]
    fn hit_test_falls_back_to_nearest_box_on_a_miss() {
        let mut t = Tree::new();
        let root = t.root();
        t.insert_atom(Cursor { seq: root, index: 0 }, atom("a"));
        t.insert_atom(Cursor { seq: root, index: 1 }, atom("b"));
        let a = t.items(root)[0];
        let b = t.items(root)[1];

        let mut boxes = BoxMap::default();
        boxes.node.insert(a, Rect { x: 0.0, y: 0.0, width: 1.0, height: 1.0 });
        boxes.node.insert(b, Rect { x: 5.0, y: 0.0, width: 1.0, height: 1.0 });
        let spans = SpanMap::default();

        // In the gap, closer to `a`: lands just after it.
        let c = hit_test_boxes(&boxes, &spans, &t, Point { x: 1.5, y: 0.5 });
        assert_eq!(c, Cursor { seq: root, index: 1 });

        // In the gap, closer to `b`: lands just before it.
        let c = hit_test_boxes(&boxes, &spans, &t, Point { x: 4.0, y: 0.5 });
        assert_eq!(c, Cursor { seq: root, index: 1 });

        // Vertically off `a` during a drag still resolves near `a`, not the document start.
        let c = hit_test_boxes(&boxes, &spans, &t, Point { x: 0.8, y: -5.0 });
        assert_eq!(c, Cursor { seq: root, index: 1 });
    }

    #[test]
    fn hit_test_on_a_truly_empty_box_map_defaults_to_document_start() {
        let t = Tree::new();
        let root = t.root();
        let c = hit_test_boxes(&BoxMap::default(), &SpanMap::default(), &t, Point { x: 3.0, y: 3.0 });
        assert_eq!(c, Cursor { seq: root, index: 0 });
    }

    /// Empty matrix cells must resolve through their own `boxes.seq` phantom placeholders.
    #[test]
    fn hit_test_lands_inside_empty_matrix_cells() {
        let mut t = Tree::new();
        let root = t.root();
        let c = t.insert_matrix(Cursor { seq: root, index: 0 }, crate::model::MatrixEnv::Pmatrix, 2, 2);
        let matrix = t.items(root)[0];
        let cells = t.child_seqs(matrix); // Row major: [r0c0, r0c1, r1c0, r1c1]
        assert_eq!(cells.len(), 4);
        assert_eq!(c.seq, cells[0]); // insert_matrix lands in the first cell

        let mut boxes = BoxMap::default();
        boxes.node.insert(matrix, Rect { x: 0.0, y: 0.0, width: 10.0, height: 10.0 });
        boxes.seq.insert(cells[0], Rect { x: 1.0, y: 1.0, width: 3.0, height: 3.0 }); // Top left
        boxes.seq.insert(cells[1], Rect { x: 6.0, y: 1.0, width: 3.0, height: 3.0 }); // Top right
        boxes.seq.insert(cells[2], Rect { x: 1.0, y: 6.0, width: 3.0, height: 3.0 }); // Bottom left
        boxes.seq.insert(cells[3], Rect { x: 6.0, y: 6.0, width: 3.0, height: 3.0 }); // Bottom right

        // Realistic spans let each cell win the most specific tie break over the matrix box.
        let mut spans = SpanMap::default();
        spans.node.insert(matrix, 0..40);
        for (i, &cell) in cells.iter().enumerate() {
            spans.seq.insert(cell, i * 11..i * 11 + 11);
        }

        let hit = |x: f64, y: f64| hit_test_boxes(&boxes, &spans, &t, Point { x, y });
        assert_eq!(hit(2.5, 2.5), Cursor { seq: cells[0], index: 0 });
        assert_eq!(hit(7.5, 2.5), Cursor { seq: cells[1], index: 0 });
        assert_eq!(hit(2.5, 7.5), Cursor { seq: cells[2], index: 0 });
        assert_eq!(hit(7.5, 7.5), Cursor { seq: cells[3], index: 0 });
    }

    /// A non empty seq must resolve through its child node, not through `boxes.seq`.
    #[test]
    fn hit_test_prefers_node_over_a_non_empty_seqs_own_box() {
        let mut t = Tree::new();
        let root = t.root();
        t.insert_atom(Cursor { seq: root, index: 0 }, atom("a"));
        let a = t.items(root)[0];

        let mut boxes = BoxMap::default();
        boxes.node.insert(a, Rect { x: 0.0, y: 0.0, width: 2.0, height: 2.0 });
        boxes.seq.insert(root, Rect { x: 0.0, y: 0.0, width: 2.0, height: 2.0 });
        let spans = SpanMap::default();

        // root is not empty because it holds "a", so this must resolve via the node.
        let c = hit_test_boxes(&boxes, &spans, &t, Point { x: 0.5, y: 0.5 });
        assert_eq!(c, Cursor { seq: root, index: 0 });
    }
}