retex_engine/

expansion.rs

//! Font expansion (hz): `\adjustspacing`, `\expandglyphsinfont`,
//! `\efcode` and the `expansion_factor` of glyph and kern nodes.
//!
//! A font made expandable with `\expandglyphsinfont f stretch shrink step`
//! (limits and step in thousandths of the glyph widths) can be widened or
//! narrowed horizontally to justify a line, so that less glue stretching
//! or shrinking is needed. LuaTeX keeps no expanded font copies: each glyph
//! node carries its own `expansion_factor` (in millionths of the width), and
//! the backend draws it scaled horizontally (LuaTeX manual, *font
//! expansion*; Hàn Thế Thành's thesis, chapter 4).
//!
//! The arithmetic below was established by black-box tests against LuaTeX
//! 1.22 (fonts with chosen widths and kerns, lines swept across rounding
//! boundaries one sp at a time):
//!
//! * `\expandglyphsinfont` limits the stretch to 1000 and the shrink to
//!   500, and rounds both down to multiples of the step.
//! * A glyph of width *w* with `\efcode` *e* (default 1000) can stretch
//!   by round(*s*·*e*/1000), where *s* = round(*w*·(1000 + stretch)/1000)
//!   − *w* is the stretch of the glyph at the font's limit; it can shrink
//!   by round(*s*′·*e*/1000), *s*′ = *w* − round(*w*·(1000 − shrink)/1000).
//!   Rounding the expanded width rather than the difference matters for
//!   halves: 400425 sp at 50% stretches by 200213 sp but shrinks by
//!   200212 sp. A negative `\efcode` counts as 0 here; one above 1000
//!   counts in full.
//! * A font kern between two glyphs of an expandable font contributes the
//!   same amounts computed from the kern *k* and the integer mean *ē* of
//!   the two `\efcode`s (truncated, not limited to 0…1000): −45875 sp at
//!   2% stretches by −918 sp and shrinks by −917 sp. Since kerns are
//!   usually negative, they reduce both the stretchability and the
//!   shrinkability of the line.
//! * With `\adjustspacing` ≥ 2 the line breaker adds these amounts to the
//!   line's stretch and shrink: the shortfall is first taken up by font
//!   expansion and only the remainder by glue (badness 0 when expansion
//!   suffices). With 3, kerns do not take part.
//! * When a line of a paragraph is packaged (any `\adjustspacing` > 0), the
//!   ratio *r* = round(1000·shortfall/total font stretch or shrink), at most
//!   1000 in magnitude, sets each glyph's factor in thousandths to
//!   round(round(*r*·limit·*e*/10⁶)/step)·step (negative when shrinking,
//!   with the glyph's own `\efcode`, at most the limit in magnitude), and
//!   each expandable kern's `expansion_factor` (an amount in sp) to its
//!   full stretch amount when the line stretches, or its full shrink amount
//!   when it shrinks, whatever the ratio. The glue then takes up the rest.
//!   If *r* is 0 (the shortfall is within half a thousandth of the font
//!   stretch or shrink), nothing is expanded and the line keeps its
//!   natural glue, with badness 0 and no warning. A line with infinitely
//!   stretchable glue is not expanded when it stretches (it is when it
//!   shrinks). Explicit `\hbox`es are never expanded.
//! * An expanded glyph is round(*w*·(10⁶ + factor)/10⁶) wide; a kern is
//!   wider by its `expansion_factor`. `\showbox` shows neither.

use crate::Engine;
use crate::nodes::{NodeData, NodeRef, id, kern_sub};
use crate::primitives_gen::assign_int as ip;
use crate::protrusion::round_div;

/// The expansion parameters of a font (`\expandglyphsinfont`).
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct FontExpansion {
    /// Maximal stretch, in thousandths.
    pub stretch: i32,
    /// Maximal shrink, in thousandths.
    pub shrink: i32,
    /// Step, in thousandths.
    pub step: i32,
}

impl FontExpansion {
    /// The expansion parameters given to `\expandglyphsinfont`, if they
    /// make the font expandable. The stretch limit is at most 1000, the
    /// shrink limit at most 500, and both are rounded down to multiples
    /// of the step.
    pub fn new(stretch: i32, shrink: i32, step: i32) -> Option<FontExpansion> {
        let step = step.clamp(0, 1000);
        if step == 0 {
            return None;
        }
        let limit = |l: i32, max: i32| l.clamp(0, max) / step * step;
        let e = FontExpansion {
            stretch: limit(stretch, 1000),
            shrink: limit(shrink, 500),
            step,
        };
        (e.stretch > 0 || e.shrink > 0).then_some(e)
    }

    /// The stretch and shrink of a glyph or font kern of width `w` with
    /// `\efcode` `e`: the difference between `w` expanded to the font's
    /// limit and `w`, scaled by `e`/1000.
    fn amounts(self, w: i32, e: i64) -> FontStretch {
        let full = |limit: i32| i64::from(expanded_width(w, limit * 1000)) - i64::from(w);
        FontStretch {
            stretch: round_div(full(self.stretch) * e, 1000) as i32,
            shrink: round_div(-full(-self.shrink) * e, 1000) as i32,
        }
    }
}

/// Width `w` expanded by `ef` millionths.
#[inline]
pub fn expanded_width(w: i32, ef: i32) -> i32 {
    if ef == 0 {
        w
    } else {
        round_div(i64::from(w) * (1_000_000 + i64::from(ef)), 1_000_000) as i32
    }
}

/// Stretch and shrink totals of font expansion in a list.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct FontStretch {
    /// Total stretch (sp).
    pub stretch: i32,
    /// Total shrink (sp).
    pub shrink: i32,
}

impl Engine {
    /// The expansion parameters of font `f`, if it is expandable.
    #[inline]
    pub fn font_expansion(&self, f: u32) -> Option<FontExpansion> {
        self.font(f).expansion
    }

    /// `\efcode` of character `c` in font `f` (1000 by default).
    pub fn ef_code(&self, f: u32, c: u32) -> i32 {
        self.font(f).char_codes[2].get(&c).copied().unwrap_or(1000)
    }

    /// `\expandglyphsinfont f stretch shrink step`.
    pub fn set_font_expansion(&mut self, f: u32, stretch: i32, shrink: i32, step: i32) {
        let e = FontExpansion::new(stretch, shrink, step);
        if let Some(fi) = self.fonts.fonts.get_mut(f as usize) {
            fi.expansion = e;
        }
    }

    /// The stretch and shrink of glyph node `p` through font expansion.
    pub(crate) fn glyph_font_stretch(&self, p: NodeRef) -> FontStretch {
        let Some(g) = self.nodes.glyph(p) else {
            return FontStretch::default();
        };
        let Some(x) = self.font_expansion(g.font) else {
            return FontStretch::default();
        };
        // A negative \efcode gives no stretch or shrink (but still a factor).
        let e = i64::from(self.ef_code(g.font, g.chr).max(0));
        let w = self.font_char_dimen(g.font, g.chr, 0);
        x.amounts(w, e)
    }

    /// The stretch and shrink of kern `k` between nodes `prev` and `next`
    /// through font expansion (font kerns between two glyphs of an
    /// expandable font).
    pub(crate) fn kern_font_stretch(
        &self,
        prev: NodeRef,
        k: NodeRef,
        next: NodeRef,
    ) -> FontStretch {
        if prev.is_null() || next.is_null() || self.nodes.subtype(k) != kern_sub::FONT {
            return FontStretch::default();
        }
        let (Some(a), Some(b)) = (self.nodes.glyph(prev), self.nodes.glyph(next)) else {
            return FontStretch::default();
        };
        let Some(x) = self.font_expansion(a.font) else {
            return FontStretch::default();
        };
        let NodeData::Kern { kern, .. } = self.nodes.data(k) else {
            return FontStretch::default();
        };
        let mean = i64::from((self.ef_code(a.font, a.chr) + self.ef_code(b.font, b.chr)) / 2);
        x.amounts(*kern, mean)
    }

    /// Font stretch and shrink of the list `p` (a discretionary text):
    /// glyphs, and kerns too if `kerns`.
    pub(crate) fn list_font_stretch(&self, mut p: NodeRef, kerns: bool) -> FontStretch {
        let mut t = FontStretch::default();
        let mut prev = NodeRef::NULL;
        while !p.is_null() {
            let s = match self.nodes.id(p) {
                id::GLYPH => self.glyph_font_stretch(p),
                id::KERN if kerns => self.kern_font_stretch(prev, p, self.nodes.next(p)),
                _ => FontStretch::default(),
            };
            t.stretch += s.stretch;
            t.shrink += s.shrink;
            prev = p;
            p = self.nodes.next(p);
        }
        t
    }

    /// Expands the glyphs of a line of a paragraph (the hlist `list`) so
    /// that it gets closer to width `width`, before it is packaged. Returns
    /// true if the line is to be left at its natural size (its glue not
    /// set), which LuaTeX does when the expansion ratio rounds to 0.
    pub(crate) fn expand_line(&mut self, list: NodeRef, width: i32) -> bool {
        let kerns = self.eqtb.int(ip::ADJUSTSPACING) != 3;
        // Natural width with unexpanded glyphs and kerns, and the font
        // stretch and shrink.
        let mut nat: i64 = 0;
        let mut fs = FontStretch::default();
        let mut any = false;
        let mut infinite_stretch = false;
        let mut prev = NodeRef::NULL;
        let mut p = list;
        while !p.is_null() {
            let next = self.nodes.next(p);
            match self.nodes.id(p) {
                id::GLYPH => {
                    let (f, c) = match self.nodes.data_mut(p) {
                        NodeData::Glyph(g) => {
                            g.expansion_factor = 0;
                            (g.font, g.chr)
                        }
                        _ => unreachable!("glyph node without glyph data"),
                    };
                    nat += i64::from(self.font_char_dimen(f, c, 0));
                    if self.font_expansion(f).is_some() {
                        any = true;
                        let s = self.glyph_font_stretch(p);
                        fs.stretch += s.stretch;
                        fs.shrink += s.shrink;
                    }
                }
                id::KERN => {
                    if let NodeData::Kern {
                        kern,
                        expansion_factor,
                    } = self.nodes.data_mut(p)
                    {
                        *expansion_factor = 0;
                        nat += i64::from(*kern);
                    }
                    if kerns {
                        let s = self.kern_font_stretch(prev, p, next);
                        fs.stretch += s.stretch;
                        fs.shrink += s.shrink;
                    }
                }
                id::DISC => {
                    // The replacement text of an unbroken discretionary
                    // is typeset; its glyphs (not its kerns) expand too.
                    let (_, _, r) = self.nodes.disc_lists(p);
                    let mut q = r;
                    while !q.is_null() {
                        if let NodeData::Glyph(g) = self.nodes.data_mut(q) {
                            g.expansion_factor = 0;
                            let f = g.font;
                            if self.font_expansion(f).is_some() {
                                any = true;
                                let s = self.glyph_font_stretch(q);
                                fs.stretch += s.stretch;
                                fs.shrink += s.shrink;
                            }
                        }
                        q = self.nodes.next(q);
                    }
                    nat += i64::from(self.list_natural_width(r));
                }
                _ => {
                    if let NodeData::Glue { spec, .. } = self.nodes.data(p)
                        && spec.stretch_order > 0
                        && spec.stretch != 0
                    {
                        infinite_stretch = true;
                    }
                    nat += i64::from(self.node_natural_width(p));
                }
            }
            prev = p;
            p = next;
        }
        if !any {
            return false;
        }
        let x = i64::from(width) - nat;
        if x > 0 && infinite_stretch {
            // Infinitely stretchable glue takes it all (the last line of a
            // paragraph): no expansion.
            return false;
        }
        let (ratio, total) = if x > 0 {
            (1, fs.stretch)
        } else if x < 0 {
            (-1, fs.shrink)
        } else {
            return false;
        };
        if total <= 0 {
            return false;
        }
        let r = (round_div(x.abs() * 1000, i64::from(total))).min(1000) * ratio;
        if r == 0 {
            return true;
        }
        let mut prev = NodeRef::NULL;
        let mut p = list;
        while !p.is_null() {
            let next = self.nodes.next(p);
            match self.nodes.id(p) {
                id::GLYPH => self.set_glyph_expansion(p, r, x > 0),
                id::DISC => {
                    let (_, _, rl) = self.nodes.disc_lists(p);
                    let mut q = rl;
                    while !q.is_null() {
                        if self.nodes.id(q) == id::GLYPH {
                            self.set_glyph_expansion(q, r, x > 0);
                        }
                        q = self.nodes.next(q);
                    }
                }
                id::KERN if kerns => {
                    let s = self.kern_font_stretch(prev, p, next);
                    let amount = if x > 0 { s.stretch } else { s.shrink };
                    if let NodeData::Kern {
                        expansion_factor, ..
                    } = self.nodes.data_mut(p)
                    {
                        *expansion_factor = amount;
                    }
                }
                _ => {}
            }
            prev = p;
            p = next;
        }
        false
    }

    /// Sets the expansion factor of glyph `p` for the ratio `r`
    /// (thousandths of the full stretch or shrink).
    fn set_glyph_expansion(&mut self, p: NodeRef, r: i64, stretching: bool) {
        let Some((f, c)) = self.nodes.glyph(p).map(|g| (g.font, g.chr)) else {
            return;
        };
        let Some(e) = self.font_expansion(f) else {
            return;
        };
        let limit = i64::from(if stretching { e.stretch } else { e.shrink });
        let code = i64::from(self.ef_code(f, c));
        let step = i64::from(e.step);
        // The factor in thousandths, then rounded to a multiple of the step.
        let n = round_div(round_div(r * limit * code, 1_000_000), step) * step;
        if let NodeData::Glyph(g) = self.nodes.data_mut(p) {
            g.expansion_factor = (n.clamp(-limit, limit) * 1000) as i32;
        }
    }

    /// The natural width of a node as `hpack` counts it (not glyphs and
    /// kerns, which [`Engine::expand_line`] handles).
    fn node_natural_width(&self, p: NodeRef) -> i32 {
        match self.nodes.data(p) {
            NodeData::Glue { spec, .. } => spec.width,
            NodeData::Box(b) => b.width,
            NodeData::Unset { b, .. } => b.width,
            NodeData::Rule { width, .. } => *width,
            NodeData::MarginKern { width, .. } => *width,
            NodeData::Math { surround, glue } => {
                if glue.width != 0 || glue.stretch != 0 || glue.shrink != 0 {
                    glue.width
                } else {
                    *surround
                }
            }
            _ => 0,
        }
    }

    fn list_natural_width(&self, mut p: NodeRef) -> i32 {
        let mut w = 0;
        while !p.is_null() {
            w += match self.nodes.data(p) {
                NodeData::Glyph(_) => self.glyph_dimensions(p).0,
                NodeData::Kern {
                    kern,
                    expansion_factor,
                } => kern + expansion_factor,
                _ => self.node_natural_width(p),
            };
            p = self.nodes.next(p);
        }
        w
    }
}

#[cfg(test)]
mod tests {
    use super::{FontExpansion, FontStretch, expanded_width};

    #[test]
    fn limits() {
        let e = |a, b, c| FontExpansion::new(a, b, c).map(|e| (e.stretch, e.shrink, e.step));
        assert_eq!(e(20, 20, 1), Some((20, 20, 1)));
        assert_eq!(e(1500, 600, 7), Some((994, 497, 7)));
        assert_eq!(e(20, 20, 3), Some((18, 18, 3)));
        assert_eq!(e(20, 0, 20), Some((20, 0, 20)));
        assert_eq!(e(20, 20, 0), None);
        assert_eq!(e(0, 0, 1), None);
    }

    #[test]
    fn amounts() {
        let x = |a, b| FontExpansion::new(a, b, 1).unwrap();
        let st = |stretch, shrink| FontStretch { stretch, shrink };
        // Halves: the expanded widths are rounded, not the differences.
        assert_eq!(x(500, 500).amounts(400_425, 1000), st(200_213, 200_212));
        assert_eq!(x(20, 20).amounts(-45_875, 1000), st(-918, -917));
        assert_eq!(x(20, 20).amounts(45_875, 1000), st(918, 917));
        // The \efcode scales the rounded amounts.
        assert_eq!(x(20, 20).amounts(400_425, 999), st(8001, 8000));
        assert_eq!(x(20, 20).amounts(-45_875, 749), st(-688, -687));
        assert_eq!(x(20, 20).amounts(345_886, 1000), st(6918, 6918));
    }

    #[test]
    fn expanded_widths() {
        assert_eq!(expanded_width(491_521, 20_000), 501_351);
        assert_eq!(expanded_width(491_521, -20_000), 481_691);
        assert_eq!(expanded_width(327_681, 0), 327_681);
    }
}