retex_engine/

protrusion.rs

//! Character protrusion (margin kerning): `\protrudechars`, `\lpcode`,
//! `\rpcode`, margin kern nodes, `\leftmarginkern` and `\rightmarginkern`.
//!
//! A character at the start (end) of a line may stick out into the left
//! (right) margin by `\lpcode` (`\rpcode`) thousandths of the font's quad.
//! With `\protrudechars` > 0, the post-line-break pass puts a margin kern
//! of minus that amount at the start (end) of each line; with
//! `\protrudechars` > 1 the line breaker counts the protrusion when it
//! measures candidate lines (LuaTeX manual, *protrusion*; Hàn Thế Thành's
//! thesis, chapter 3).
//!
//! Which character counts as "at the edge" was established by black-box
//! tests against LuaTeX 1.22. Searching from the line end inwards, these
//! nodes are passed over (the list in the LuaTeX manual): glue without
//! width, stretch and shrink, penalties, empty discretionaries, font kerns
//! and kerns of width zero, rules of zero width, height and depth, math
//! nodes without surround, direction and local paragraph nodes, empty
//! zero-sized hlists, inserts, marks, adjusts, boundaries and whatsits. A
//! non-empty hlist is searched recursively. Anything else ends the search
//! without a protruding character.
//!
//! The line breaker searches a little differently from the post-line-break
//! pass:
//!
//! * at the start of a line it first skips what the post-line-break pass
//!   will prune (glue, explicit kerns, penalties and math nodes after the
//!   break), starting at the break node itself;
//! * after a break at a discretionary, the post-break text counts only if
//!   it starts with a character (nothing in it is skipped); an empty
//!   post-break text continues the search at the discretionary node,
//!   which only an empty discretionary lets through;
//! * before a break at a discretionary, likewise the pre-break text counts
//!   only if it ends with a character; an empty one continues before the
//!   discretionary;
//! * the last line of a paragraph gets no right protrusion in line
//!   breaking, whatever `\parfillskip` is (the post-line-break pass still
//!   adds its margin kern).

use crate::Engine;
use crate::nodes::{NodeData, NodeRef, id, kern_sub};

/// Subtype of a left margin kern node.
pub const LEFT_SIDE: u16 = 0;
/// Subtype of a right margin kern node.
pub const RIGHT_SIDE: u16 = 1;

/// The result of searching for a protruding character.
enum Found {
    /// A glyph.
    Char(NodeRef),
    /// The search ended at a node that stops protrusion.
    Blocked,
    /// The list ended without a decision.
    End,
}

/// Rounds `a / b` to the nearest integer, halves away from zero (`b` > 0).
pub(crate) fn round_div(a: i64, b: i64) -> i64 {
    if a >= 0 {
        (2 * a + b) / (2 * b)
    } else {
        -((-2 * a + b) / (2 * b))
    }
}

impl Engine {
    /// The protrusion of glyph `p` into the left (`left`) or right margin,
    /// in sp: the `\lpcode`/`\rpcode` of its character in thousandths of
    /// the font's quad. The margin kern is minus this amount.
    pub fn char_protrusion(&self, p: NodeRef, left: bool) -> i32 {
        let Some(g) = self.nodes.glyph(p) else {
            return 0;
        };
        let fi = self.font(g.font);
        let code = fi.char_codes[usize::from(!left)]
            .get(&g.chr)
            .copied()
            .unwrap_or(0);
        if code == 0 {
            return 0;
        }
        let quad = i64::from(self.quad(g.font));
        round_div(i64::from(code) * quad, 1000) as i32
    }

    /// Whether node `p` is passed over when looking for a protruding
    /// character.
    fn protrusion_skippable(&self, p: NodeRef) -> bool {
        match self.nodes.data(p) {
            NodeData::Glue { spec, .. } => spec.width == 0 && spec.stretch == 0 && spec.shrink == 0,
            NodeData::Penalty { .. } => true,
            NodeData::Disc {
                pre, post, replace, ..
            } => pre.is_null() && post.is_null() && replace.is_null(),
            NodeData::Kern { kern, .. } => *kern == 0 || self.nodes.subtype(p) == kern_sub::FONT,
            NodeData::Rule {
                width,
                height,
                depth,
                ..
            } => *width == 0 && *height == 0 && *depth == 0,
            NodeData::Math { surround, glue } => {
                *surround == 0 && glue.width == 0 && glue.stretch == 0 && glue.shrink == 0
            }
            NodeData::Dir { .. }
            | NodeData::LocalPar { .. }
            | NodeData::Ins { .. }
            | NodeData::Mark { .. }
            | NodeData::Adjust { .. }
            | NodeData::Boundary { .. }
            | NodeData::Whatsit(_) => true,
            NodeData::Box(b) => {
                self.nodes.id(p) == id::HLIST
                    && b.head.is_null()
                    && b.width == 0
                    && b.height == 0
                    && b.depth == 0
            }
            _ => false,
        }
    }

    /// Whether `p` is pruned at the start of a line after a break.
    fn pruned_after_break(&self, p: NodeRef) -> bool {
        match self.nodes.id(p) {
            id::GLUE | id::PENALTY | id::MATH => true,
            id::KERN => matches!(self.nodes.subtype(p), kern_sub::USER | kern_sub::ITALIC),
            _ => false,
        }
    }

    /// Searches forwards from `p` for the character at the left edge.
    fn protchar_left_from(&self, mut p: NodeRef) -> Found {
        while !p.is_null() {
            match self.nodes.id(p) {
                id::GLYPH => return Found::Char(p),
                id::HLIST if !self.nodes.list_ptr(p).is_null() => {
                    match self.protchar_left_from(self.nodes.list_ptr(p)) {
                        Found::End => {}
                        f => return f,
                    }
                }
                _ if self.protrusion_skippable(p) => {}
                _ => return Found::Blocked,
            }
            p = self.nodes.next(p);
        }
        Found::End
    }

    /// Searches the list `head` for the character at its right edge.
    fn protchar_right_in(&self, head: NodeRef) -> Found {
        // Collect the list, then walk it backwards (inner lists are
        // short and their back links are not maintained everywhere).
        let mut v = Vec::new();
        let mut p = head;
        while !p.is_null() {
            v.push(p);
            p = self.nodes.next(p);
        }
        self.protchar_right_rev(v.into_iter().rev())
    }

    fn protchar_right_rev(&self, it: impl Iterator<Item = NodeRef>) -> Found {
        for p in it {
            match self.nodes.id(p) {
                id::GLYPH => return Found::Char(p),
                id::HLIST if !self.nodes.list_ptr(p).is_null() => {
                    match self.protchar_right_in(self.nodes.list_ptr(p)) {
                        Found::End => {}
                        f => return f,
                    }
                }
                _ if self.protrusion_skippable(p) => {}
                _ => return Found::Blocked,
            }
        }
        Found::End
    }

    /// Searches backwards from `p` (inclusive) in a list with valid back
    /// links, stopping at `stop` (exclusive).
    fn protchar_right_back(&self, p: NodeRef, stop: NodeRef) -> Found {
        let mut q = p;
        let it = std::iter::from_fn(move || {
            if q.is_null() || q == stop {
                return None;
            }
            let r = q;
            q = self.nodes.prev(q);
            Some(r)
        });
        self.protchar_right_rev(it)
    }

    fn found_left(&self, f: Found) -> i32 {
        match f {
            Found::Char(g) => self.char_protrusion(g, true),
            _ => 0,
        }
    }

    fn found_right(&self, f: Found) -> i32 {
        match f {
            Found::Char(g) => self.char_protrusion(g, false),
            _ => 0,
        }
    }

    /// Line breaking: the left protrusion of a line that starts after the
    /// break at `brk` (`None` for the first line, whose first node is
    /// `first`).
    pub(crate) fn lb_left_protrusion(&self, brk: Option<NodeRef>, first: NodeRef) -> i32 {
        let mut p = match brk {
            None => return self.found_left(self.protchar_left_from(first)),
            Some(b) if b.is_null() => return 0,
            Some(b) => b,
        };
        if self.nodes.id(p) == id::DISC {
            let (_, post, _) = self.nodes.disc_lists(p);
            if !post.is_null() {
                return if self.nodes.id(post) == id::GLYPH {
                    self.char_protrusion(post, true)
                } else {
                    0
                };
            }
        }
        while !p.is_null() && self.pruned_after_break(p) {
            p = self.nodes.next(p);
        }
        self.found_left(self.protchar_left_from(p))
    }

    /// Line breaking: the right protrusion of a line that ends with a
    /// break at `cur_p` (null for the end of the paragraph). Back links of
    /// the main list must be valid; `head` is the list head.
    pub(crate) fn lb_right_protrusion(&self, cur_p: NodeRef, head: NodeRef) -> i32 {
        if cur_p.is_null() {
            // The final break: LuaTeX counts no right protrusion here (even
            // with a zero \parfillskip).
            return 0;
        }
        if self.nodes.id(cur_p) == id::DISC {
            let (pre, _, _) = self.nodes.disc_lists(cur_p);
            if !pre.is_null() {
                let t = self.nodes.tail_of(pre);
                return if self.nodes.id(t) == id::GLYPH {
                    self.char_protrusion(t, false)
                } else {
                    0
                };
            }
        }
        let p = self.nodes.prev(cur_p);
        self.found_right(self.protchar_right_back(p, head))
    }

    /// Makes the back links of the list after `head` consistent.
    pub(crate) fn fix_back_links(&mut self, head: NodeRef) {
        let mut prev = head;
        let mut p = self.nodes.next(head);
        while !p.is_null() {
            self.nodes.set_prev(p, prev);
            prev = p;
            p = self.nodes.next(p);
        }
    }

    fn new_margin_kern(&mut self, width: i32, side: u16) -> NodeRef {
        self.new_node(
            id::MARGIN_KERN,
            side,
            NodeData::MarginKern {
                width,
                glyph: NodeRef::NULL,
            },
        )
    }

    /// Post-line-break: the left margin kern for a line starting with
    /// `line`, or null if there is no protrusion.
    pub(crate) fn left_margin_kern(&mut self, line: NodeRef) -> NodeRef {
        let w = self.found_left(self.protchar_left_from(line));
        if w == 0 {
            return NodeRef::NULL;
        }
        self.new_margin_kern(-w, LEFT_SIDE)
    }

    /// Post-line-break: inserts the right margin kern of the line that
    /// starts after `pred` just before its node `q` (the break node, or
    /// the last node of the paragraph).
    pub(crate) fn insert_right_margin_kern(&mut self, pred: NodeRef, q: NodeRef) {
        let mut v = Vec::new();
        let mut p = self.nodes.next(pred);
        while !p.is_null() && p != q {
            v.push(p);
            p = self.nodes.next(p);
        }
        if p != q || q.is_null() {
            return;
        }
        let w = self.found_right(self.protchar_right_rev(v.iter().rev().copied()));
        if w == 0 {
            return;
        }
        let k = self.new_margin_kern(-w, RIGHT_SIDE);
        let before = v.last().copied().unwrap_or(pred);
        self.nodes.link(before, k);
        self.nodes.link(k, q);
    }

    /// `\leftmarginkern n`, `\rightmarginkern n`: the width of the margin
    /// kern at the start (end) of hbox `n`, passing over glue and
    /// penalties; `None` if there is none (expands to `0pt`). A void box
    /// or a vbox is a fatal error in LuaTeX.
    pub fn margin_kern(&mut self, n: u32, left: bool) -> Option<i32> {
        let b = self
            .eqtb
            .boxes
            .get(n as usize)
            .map_or(NodeRef::NULL, |b| b.val);
        if b.is_null() || self.nodes.id(b) != id::HLIST {
            self.luatex_fatal("marginkern", "a non-empty hbox expected");
        }
        let mut v = Vec::new();
        let mut p = self.nodes.list_ptr(b);
        while !p.is_null() {
            v.push(p);
            p = self.nodes.next(p);
        }
        if !left {
            v.reverse();
        }
        let want = if left { LEFT_SIDE } else { RIGHT_SIDE };
        for p in v {
            match self.nodes.data(p) {
                NodeData::MarginKern { width, .. } => {
                    return (self.nodes.subtype(p) == want).then_some(*width);
                }
                NodeData::Glue { .. } | NodeData::Penalty { .. } => {}
                _ => return None,
            }
        }
        None
    }

    /// Removes the margin kerns from the top level of the list `p`
    /// (unboxing an hbox drops them, as in LuaTeX); returns the new head.
    pub fn strip_margin_kerns(&mut self, mut head: NodeRef) -> NodeRef {
        while !head.is_null() && self.nodes.id(head) == id::MARGIN_KERN {
            let n = self.nodes.next(head);
            self.nodes.free(head);
            head = n;
        }
        if head.is_null() {
            return head;
        }
        self.nodes.set_prev(head, NodeRef::NULL);
        let mut prev = head;
        let mut p = self.nodes.next(head);
        while !p.is_null() {
            let n = self.nodes.next(p);
            if self.nodes.id(p) == id::MARGIN_KERN {
                self.nodes.free(p);
                self.nodes.set_next(prev, n);
                if !n.is_null() {
                    self.nodes.set_prev(n, prev);
                }
            } else {
                prev = p;
            }
            p = n;
        }
        head
    }
}

#[cfg(test)]
mod tests {
    use super::round_div;

    #[test]
    fn rounding_halves_away_from_zero() {
        assert_eq!(round_div(3_276_805, 10), 327_681);
        assert_eq!(round_div(-3_276_805, 10), -327_681);
        assert_eq!(round_div(1_966_083, 10), 196_608);
        assert_eq!(round_div(7, 2), 4);
        assert_eq!(round_div(-7, 2), -4);
    }
}