retex_engine/

nodeproc.rs

//! LuaTeX's node processing before packaging and line breaking: the
//! hyphenation, ligaturing and kerning passes (LuaTeX manual §5.5–§5.6).
//!
//! Characters are appended to lists as glyph nodes without any font
//! processing. When an `\hbox` is packaged or a paragraph is broken into
//! lines, LuaTeX first inserts discretionaries (explicit hyphens become
//! "automatic" discretionaries; patterns insert "regular" ones), then
//! builds ligatures, then inserts font kerns. Each step can be replaced by
//! a Lua callback; without callbacks
//! the built-in TeX-style processing below applies, using the font's
//! lig/kern program.
//!
//! Observed behaviour reproduced here:
//!
//! * a single `\exhyphenchar` glyph immediately followed by another
//!   glyph becomes an automatic discretionary (subtype 2) whose pre-break
//!   and replacement texts are the hyphen, with `\exhyphenpenalty` as
//!   current at processing time. Of a run of two or more hyphens (`--`,
//!   `---`) only the last one becomes such a discretionary, and only when
//!   the run follows a glyph with a non-zero hyphenation code and is
//!   followed by a glyph, and at most once between two glues; a kern also
//!   prevents it until the next glue. So `a--b` becomes `a-{-||-}b`, while
//!   `16--19`, `1--a` and the second dash of `a--b--c` stay as they are
//!   (observed with luatex);
//! * ligatures form within the main list and within each list of a
//!   discretionary; a glyph next to a discretionary moves into it when it
//!   would form a ligature across it;
//! * kerns between a glyph and a discretionary go into the discretionary's
//!   lists (pre-break and replacement at the left, post-break and
//!   replacement at the right);
//! * boundary nodes are removed; glyphs lose their "character" subtype.

use crate::Engine;
use crate::fonts::LigOp;
use crate::nodes::{GlyphData, NodeData, NodeRef, glyph_sub, id, kern_sub};
use crate::primitives_gen::assign_int as ip;

/// What a list is processed for (the callback group).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Context {
    /// An `\hbox` (or local box) being packaged.
    Hbox,
    /// A paragraph before line breaking.
    Paragraph,
}

/// One of the node processing passes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NodePass {
    /// Hyphenation (`lang.hyphenate`).
    Hyphenate,
    /// Ligatures (`node.ligaturing`).
    Ligaturing,
    /// Font kerns (`node.kerning`).
    Kerning,
}

impl Engine {
    /// The hyphenation parameters of language `l`.
    pub fn lang_params(&self, l: u32) -> retex_hyph::Settings {
        self.language(l).map(|x| x.settings).unwrap_or_default()
    }

    /// A new glyph node in font `f` with the current language data
    /// (LuaTeX's `new_char`).
    pub fn new_char_node(&mut self, f: u32, c: u32) -> NodeRef {
        let lang = self.cur_lang() as u16;
        let left = self.eqtb.int(ip::LEFTHYPHENMIN).clamp(0, 63) as u8;
        let right = self.eqtb.int(ip::RIGHTHYPHENMIN).clamp(0, 63) as u8;
        let uchyph = self.eqtb.int(ip::UCHYPH) > 0;
        self.new_node(
            id::GLYPH,
            glyph_sub::CHARACTER,
            NodeData::Glyph(GlyphData {
                chr: c,
                font: f,
                lang,
                left,
                right,
                uchyph,
                ..GlyphData::default()
            }),
        )
    }

    /// Runs the hyphenation, ligaturing and kerning passes over the list
    /// starting at `first`; returns the new first node.
    pub fn node_process_list(&mut self, first: NodeRef, ctx: Context) -> NodeRef {
        if first.is_null() {
            return first;
        }
        self.fonts.sync_dense();
        let head = self.nodes.new_temp();
        self.nodes.link(head, first);
        let saved_par_temp = self.nodes.par_temp;
        if ctx == Context::Paragraph {
            self.nodes.par_temp = head;
        }
        // The hyphenate, ligaturing and kerning callbacks replace the
        // built-in passes (a registered false skips them).
        let host = self.lua.clone();
        let pass = |e: &mut Engine, cb: &str| match &host {
            Some(h) => {
                if e.figures.recording() && h.has_callback(cb) {
                    e.figure_callback(cb);
                }
                h.node_pass(e, cb, head)
            }
            None => false,
        };
        if !pass(self, "hyphenate") {
            self.hyphenate_list(head);
        }
        if !pass(self, "ligaturing") {
            self.ligature_list(head, true);
        }
        if !pass(self, "kerning") {
            self.kern_list(head);
        }
        self.nodes.par_temp = saved_par_temp;
        let first = self.nodes.next(head);
        if !first.is_null() {
            self.nodes.set_prev(first, NodeRef::NULL);
        }
        self.nodes.free(head);
        first
    }

    /// Runs one built-in pass (`node.ligaturing`, `node.kerning`,
    /// `lang.hyphenate`) over the list `head`, which may start with a
    /// temporary node (as in the callbacks); returns the new head and the
    /// tail.
    pub fn lua_node_pass(&mut self, pass: NodePass, head: NodeRef) -> (NodeRef, NodeRef) {
        if head.is_null() {
            return (head, head);
        }
        self.fonts.sync_dense();
        let temp = self.nodes.id(head) == id::TEMP;
        let h = if temp {
            head
        } else {
            let t = self.nodes.new_temp();
            self.nodes.link(t, head);
            t
        };
        match pass {
            NodePass::Hyphenate => self.hyphenate_list(h),
            NodePass::Ligaturing => self.ligature_list(h, true),
            NodePass::Kerning => self.kern_list(h),
        }
        let first = if temp {
            head
        } else {
            let f = self.nodes.next(h);
            if !f.is_null() {
                self.nodes.set_prev(f, NodeRef::NULL);
            }
            self.nodes.free(h);
            f
        };
        let tail = self.nodes.tail_of(first);
        (first, tail)
    }

    // ----- hyphenation ---------------------------------------------------

    /// The built-in `hyphenate` step: explicit hyphens become automatic
    /// discretionaries; patterns (through the [`crate::typeset::Hyphenator`])
    /// insert regular ones.
    fn hyphenate_list(&mut self, head: NodeRef) {
        let ex = self.eqtb.int(ip::EXHYPHENCHAR);
        let pen = self.eqtb.int(ip::EXHYPHENPENALTY);
        if ex > 0 {
            let ex = ex as u32;
            let is_hyphen = |e: &Engine, n: NodeRef| e.nodes.glyph(n).is_some_and(|g| g.chr == ex);
            // Whether a run of several hyphens may still become a
            // discretionary before the next glue.
            let mut armed = true;
            let mut prev = head;
            let mut p = self.nodes.next(head);
            while !p.is_null() {
                // Observed: hyphens in a formula stay as they are (a URL
                // set as math, with apacite's `\mathbin{}\mathchar"2D`).
                if self.nodes.id(p) == id::MATH && self.nodes.subtype(p) == 0 {
                    let mut q = self.nodes.next(p);
                    while !(q.is_null()
                        || (self.nodes.id(q) == id::MATH && self.nodes.subtype(q) == 1))
                    {
                        q = self.nodes.next(q);
                    }
                    if q.is_null() {
                        break;
                    }
                    prev = q;
                    p = self.nodes.next(q);
                    continue;
                }
                if !is_hyphen(self, p) {
                    match self.nodes.id(p) {
                        id::GLUE => armed = true,
                        id::KERN => armed = false,
                        _ => {}
                    }
                    prev = p;
                    p = self.nodes.next(p);
                    continue;
                }
                // Find the run of hyphens.
                let mut last = p;
                let mut len = 1;
                let mut q = self.nodes.next(p);
                while !q.is_null() && is_hyphen(self, q) {
                    last = q;
                    len += 1;
                    q = self.nodes.next(q);
                }
                let followed = !q.is_null() && self.nodes.is_glyph(q);
                let convert =
                    followed && (len == 1 || (armed && prev != head && self.has_hj_code(prev)));
                if !convert {
                    prev = last;
                    p = q;
                    continue;
                }
                if len > 1 {
                    armed = false;
                }
                // Replace the last hyphen by an automatic discretionary.
                let before = if len == 1 {
                    prev
                } else {
                    self.nodes.prev(last)
                };
                self.nodes.set_next(last, NodeRef::NULL);
                let d = self.nodes.new_disc(2, pen);
                if let Some(a) = self.nodes.attr(last).cloned() {
                    self.nodes.set_attr(d, Some(a));
                }
                let pre = self.nodes.copy_list(last);
                self.nodes.set_prev(last, NodeRef::NULL);
                self.nodes.set_disc_lists(d, (pre, NodeRef::NULL, last));
                self.nodes.link(before, d);
                self.nodes.link(d, q);
                prev = d;
                p = q;
            }
        }
        if !self.languages.is_empty() {
            self.pattern_hyphenate(head);
        }
    }

    /// Whether `p` is a glyph whose character has a non-zero hyphenation
    /// code in its language.
    fn has_hj_code(&self, p: NodeRef) -> bool {
        let Some(g) = self.nodes.glyph(p) else {
            return false;
        };
        let lang = u32::from(g.lang);
        let c = g.chr;
        let code = match self.language(lang) {
            Some(l) if l.has_hj_codes() => l.hj_code(c),
            _ => self.eqtb.lc.get(c).max(0) as u32,
        };
        code != 0
    }

    /// Inserts pattern discretionaries into the words of the list
    /// (LuaTeX's hyphenation pass, using `retex-hyph`).
    ///
    /// Observed: a word is hyphenated only if what precedes it lets a word
    /// start and what follows it lets a word end. The list start and glue
    /// let words start; once the list has had a glyph, kerns, penalties,
    /// discretionaries, marks and `\vadjust`s stop that until the next
    /// glue; other glyphs, boxes, rules, whatsits, formulas (with all
    /// they hold) and direction nodes leave it as it is. A word followed by a discretionary, a math
    /// node or a mark is not hyphenated; nor is any word of a run of glyphs
    /// (with the automatic discretionaries of explicit hyphens) that ends
    /// at a math node, a mark or another discretionary, even one followed
    /// by punctuation or by other words of the run (`AUROC($x$)`,
    /// `word,word-word\mark{}`). With `\automatichyphenmode` > 0 automatic
    /// discretionaries (from explicit hyphens) count as letting words
    /// start and end. Otherwise the automatic discretionary of a single
    /// explicit hyphen lets words start again, but not the word attached
    /// to it (`ab-online/on-line`); after `--` none does.
    fn pattern_hyphenate(&mut self, head: NodeRef) {
        let hpen = self.eqtb.int(ip::HYPHENPENALTY);
        let auto_ok = self.eqtb.int(ip::AUTOMATICHYPHENMODE) != 0;
        let mut run: Vec<NodeRef> = Vec::new();
        let mut word: Vec<NodeRef> = Vec::new();
        let mut codes: Vec<u32> = Vec::new();
        let mut pos: Vec<usize> = Vec::new();
        let mut can_start = true;
        let mut seen_glyph = false;
        // The run starts right after the automatic discretionary of a
        // single explicit hyphen: its first word is not hyphenated.
        let mut skip_first = false;
        // Whether the current unit (runs joined by automatic
        // discretionaries) ends where its words cannot be hyphenated.
        let mut unit_kill: Option<bool> = None;
        let mut p = self.nodes.next(head);
        while !p.is_null() {
            if self.nodes.is_glyph(p) && self.nodes.subtype(p) & glyph_sub::CHARACTER != 0 {
                // A run of character glyphs.
                run.clear();
                let mut q = p;
                while !q.is_null()
                    && self.nodes.is_glyph(q)
                    && self.nodes.subtype(q) & glyph_sub::CHARACTER != 0
                {
                    run.push(q);
                    q = self.nodes.next(q);
                }
                let end_ok = q.is_null()
                    || match self.nodes.id(q) {
                        id::DISC => auto_ok && self.nodes.subtype(q) == 2,
                        id::MATH | id::MARK => false,
                        _ => true,
                    };
                let kill = *unit_kill.get_or_insert_with(|| self.unit_ends_badly(q));
                let bounds = (can_start && !kill, end_ok, skip_first);
                self.hyphenate_run(&run, hpen, bounds, &mut word, &mut codes, &mut pos);
                seen_glyph = true;
                skip_first = false;
                p = q;
                continue;
            }
            if !(self.nodes.id(p) == id::DISC && self.nodes.subtype(p) == 2) {
                unit_kill = None;
            }
            // Observed: a formula's contents leave the state as it is
            // (`$T-$dependencies` is hyphenated after the kern and the
            // glyphs of the formula).
            if self.nodes.id(p) == id::MATH && self.nodes.subtype(p) == 0 {
                let mut q = self.nodes.next(p);
                while !(q.is_null() || (self.nodes.id(q) == id::MATH && self.nodes.subtype(q) == 1))
                {
                    q = self.nodes.next(q);
                }
                p = if q.is_null() { q } else { self.nodes.next(q) };
                continue;
            }
            match self.nodes.id(p) {
                id::GLUE => can_start = true,
                id::KERN | id::PENALTY | id::MARK | id::ADJUST => can_start &= !seen_glyph,
                id::DISC if auto_ok && self.nodes.subtype(p) == 2 => can_start = true,
                id::DISC if self.nodes.subtype(p) == 2 && self.single_hyphen_disc(p) => {
                    can_start = true;
                    skip_first = true;
                }
                id::DISC => can_start &= !seen_glyph,
                _ => {}
            }
            p = self.nodes.next(p);
        }
    }

    /// Whether automatic discretionary `d` comes from a single explicit
    /// hyphen: after a glyph other than the hyphen character.
    fn single_hyphen_disc(&self, d: NodeRef) -> bool {
        let ex = self.eqtb.int(ip::EXHYPHENCHAR);
        let prev = self.nodes.prev(d);
        !prev.is_null()
            && self
                .nodes
                .glyph(prev)
                .is_some_and(|g| ex <= 0 || g.chr != ex as u32)
    }

    /// Whether the unit of glyph runs and automatic discretionaries that
    /// goes on at `q` (the node after a run) ends at a math node, a mark or
    /// a discretionary other than an automatic one.
    fn unit_ends_badly(&self, mut q: NodeRef) -> bool {
        loop {
            if q.is_null() {
                return false;
            }
            match self.nodes.id(q) {
                id::DISC if self.nodes.subtype(q) == 2 => {}
                id::DISC | id::MATH | id::MARK => return true,
                _ if self.nodes.is_glyph(q)
                    && self.nodes.subtype(q) & glyph_sub::CHARACTER != 0 => {}
                _ => return false,
            }
            q = self.nodes.next(q);
        }
    }

    /// Hyphenates the words in a run of character glyphs; `bounds` tells
    /// whether words may start in the run and end at its end.
    fn hyphenate_run(
        &mut self,
        run: &[NodeRef],
        hpen: i32,
        bounds: (bool, bool, bool),
        word: &mut Vec<NodeRef>,
        codes: &mut Vec<u32>,
        pos: &mut Vec<usize>,
    ) {
        if !bounds.0 {
            return;
        }
        let mut i = 0;
        while i < run.len() {
            // A word: glyphs of one language with non-zero hj codes.
            let Some(g0) = self.nodes.glyph(run[i]).cloned() else {
                i += 1;
                continue;
            };
            let lang = u32::from(g0.lang);
            word.clear();
            codes.clear();
            // Observed: a word next to or with an explicit hyphen that did
            // not become a discretionary (`--word` after a space, `word--`;
            // LaTeX gives the hyphen an hj code) is not hyphenated.
            let ex = self.eqtb.int(ip::EXHYPHENCHAR);
            let mut with_hyphen = false;
            while i < run.len() {
                let Some(g) = self.nodes.glyph(run[i]) else {
                    break;
                };
                if u32::from(g.lang) != lang {
                    break;
                }
                let c = g.chr;
                let code = match self.language(lang) {
                    Some(l) if l.has_hj_codes() => l.hj_code(c),
                    _ => self.eqtb.lc.get(c).max(0) as u32,
                };
                if code == 0 {
                    if word.is_empty() {
                        with_hyphen = ex > 0 && c == ex as u32;
                        i += 1;
                        continue;
                    }
                    with_hyphen |= ex > 0 && c == ex as u32;
                    break;
                }
                with_hyphen |= ex > 0 && c == ex as u32;
                word.push(run[i]);
                codes.push(code);
                i += 1;
            }
            if word.len() < 2 || with_hyphen || (bounds.2 && word.first() == run.first()) {
                continue;
            }
            if !bounds.1 && word.last() == run.last() {
                continue;
            }
            let Some(first) = self.nodes.glyph(word[0]).cloned() else {
                continue;
            };
            if first.font == 0 || self.font(first.font).hyphen_char < 0 {
                continue;
            }
            if !first.uchyph && codes[0] != first.chr {
                continue;
            }
            let Some(language) = self.language(lang) else {
                continue;
            };
            pos.clear();
            let _ =
                language.hyphenate_into(codes, u32::from(first.left), u32::from(first.right), pos);
            if pos.is_empty() {
                continue;
            }
            let settings = language.settings;
            pos.sort_unstable();
            pos.dedup();
            for &k in pos.iter().rev() {
                if k == 0 || k >= word.len() {
                    continue;
                }
                let left = word[k - 1];
                let right = word[k];
                let f = self.nodes.glyph(left).map_or(0, |g| g.font);
                let d = self.nodes.new_disc(3, hpen);
                if let Some(a) = self.nodes.attr(left).cloned() {
                    self.nodes.set_attr(d, Some(a));
                }
                let mk = |e: &mut Engine, c: i32| {
                    if c > 0 {
                        let mut g = e.nodes.glyph(left).cloned().unwrap_or_default();
                        g.chr = c as u32;
                        g.font = f;
                        g.components = NodeRef::NULL;
                        // Observed: with the attributes of the glyph
                        // before the break, like the discretionary.
                        let a = e.nodes.attr(left).cloned();
                        let n = e
                            .nodes
                            .alloc(id::GLYPH, glyph_sub::CHARACTER, NodeData::Glyph(g));
                        e.nodes.set_attr(n, a);
                        n
                    } else {
                        NodeRef::NULL
                    }
                };
                let pre = mk(self, settings.pre_hyphen_char);
                let post = mk(self, settings.post_hyphen_char);
                self.nodes.set_disc_lists(d, (pre, post, NodeRef::NULL));
                self.nodes.link(left, d);
                self.nodes.link(d, right);
            }
        }
    }

    // ----- ligaturing ----------------------------------------------------

    /// Whether `p` is a glyph of font `f` (any subtype except ghosts).
    #[inline]
    fn glyph_of_font(&self, p: NodeRef, f: u32) -> Option<u32> {
        if p.is_null() {
            return None;
        }
        match self.nodes.data(p) {
            NodeData::Glyph(g) if g.font == f && self.nodes.subtype(p) & glyph_sub::GHOST == 0 => {
                Some(g.chr)
            }
            _ => None,
        }
    }

    /// The ligature step for (`l`, `r`) in font `f`, if it is a ligature.
    /// A font with `\ignoreligaturesinfont` has none (its kerns stay).
    #[inline]
    fn lig_step(&self, f: u32, l: u32, r: u32) -> Option<(u8, u32)> {
        if self.font(f).ignore_ligatures != 0 {
            return None;
        }
        match self.lig_kern_step(f, l, r) {
            Some(LigOp::Lig { op, chr }) => Some((op, chr)),
            _ => None,
        }
    }

    /// The components of a glyph for a new ligature: the glyph itself, or
    /// its components if it is already a ligature.
    fn take_components(&mut self, p: NodeRef) -> NodeRef {
        let is_lig = self.nodes.subtype(p) & glyph_sub::LIGATURE != 0;
        if is_lig {
            let c = self
                .nodes
                .glyph_mut(p)
                .map(|g| std::mem::take(&mut g.components));
            let c = c.unwrap_or(NodeRef::NULL);
            self.nodes.free(p);
            if c.is_null() {
                return NodeRef::NULL;
            }
            c
        } else {
            self.nodes.set_next(p, NodeRef::NULL);
            self.nodes.set_prev(p, NodeRef::NULL);
            let s = self.nodes.subtype(p) & !glyph_sub::CHARACTER;
            self.nodes.set_subtype(p, s);
            p
        }
    }

    /// Makes a ligature glyph like `model` with character `c` and the given
    /// components.
    fn new_ligature(&mut self, model: NodeRef, c: u32, comps: NodeRef) -> NodeRef {
        let mut g = self.nodes.glyph(model).cloned().unwrap_or_default();
        g.chr = c;
        g.components = comps;
        let a = self.nodes.attr(model).cloned();
        let n = self
            .nodes
            .alloc(id::GLYPH, glyph_sub::LIGATURE, NodeData::Glyph(g));
        self.nodes.set_attr(n, a);
        n
    }

    /// Concatenates two node lists.
    fn concat(&mut self, a: NodeRef, b: NodeRef) -> NodeRef {
        if a.is_null() {
            return b;
        }
        if !b.is_null() {
            let t = self.nodes.tail_of(a);
            self.nodes.link(t, b);
        }
        a
    }

    /// Replaces `old` (whose predecessor is `prev`) by `new` in a list.
    fn replace_node(&mut self, prev: NodeRef, old_next: NodeRef, new: NodeRef) {
        self.nodes.link(prev, new);
        self.nodes.link(new, old_next);
        if old_next.is_null() {
            self.nodes.set_next(new, NodeRef::NULL);
        }
    }

    /// Builds ligatures in the list after `head`. `main` is true for the
    /// main list (boundary nodes are removed there).
    fn ligature_list(&mut self, head: NodeRef, main: bool) {
        let mut prev = head;
        let mut p = self.nodes.next(head);
        while !p.is_null() {
            match self.nodes.id(p) {
                id::BOUNDARY if main => {
                    let n = self.nodes.next(p);
                    self.nodes.set_next(prev, n);
                    if !n.is_null() {
                        self.nodes.set_prev(n, prev);
                    }
                    self.nodes.free(p);
                    p = n;
                }
                id::GLYPH => {
                    let (last_prev, last) = self.ligature_run(prev, p);
                    // `last` is the final glyph of the run; it may be
                    // followed by a discretionary.
                    let n = self.nodes.next(last);
                    if main
                        && (n.is_null()
                            || !matches!(self.nodes.id(n), id::GLYPH | id::DISC | id::BOUNDARY))
                    {
                        self.right_boundary_kern(last);
                    }
                    if !n.is_null() && self.nodes.id(n) == id::DISC {
                        let (np, nd) = self.lig_disc(last_prev, last, n);
                        prev = np;
                        p = nd;
                    } else {
                        prev = last;
                        p = n;
                    }
                }
                id::DISC => {
                    self.lig_disc_lists(p);
                    prev = p;
                    p = self.nodes.next(p);
                }
                _ => {
                    prev = p;
                    p = self.nodes.next(p);
                }
            }
        }
    }

    /// Appends the font kern between glyph `p` and its font's right
    /// boundary character, if there is one. Observed: LuaTeX applies it
    /// in the main list when the next node is not a glyph, a
    /// discretionary or a boundary node (`\noboundary`, `\boundary`, ...),
    /// even after a font kern (an unboxed list gets a second one).
    fn right_boundary_kern(&mut self, p: NodeRef) {
        let Some((f, l)) = self.nodes.glyph(p).map(|g| (g.font, g.chr)) else {
            return;
        };
        let Some(b) = self.font(f).right_boundary else {
            return;
        };
        if let Some(k) = self.kern_between(f, l, b) {
            let kn = self.font_kern(k, p);
            let n = self.nodes.next(p);
            self.nodes.link(p, kn);
            self.nodes.link(kn, n);
        }
    }

    /// Ligatures the three lists of a discretionary independently.
    fn lig_disc_lists(&mut self, d: NodeRef) {
        let (pre, post, rep) = self.nodes.disc_lists(d);
        let pre = self.ligature_sublist(pre);
        let post = self.ligature_sublist(post);
        let rep = self.ligature_sublist(rep);
        self.nodes.set_disc_lists(d, (pre, post, rep));
    }

    /// Ligatures a detached list; returns its new head.
    fn ligature_sublist(&mut self, l: NodeRef) -> NodeRef {
        if l.is_null() {
            return l;
        }
        let h = self.nodes.new_temp();
        self.nodes.link(h, l);
        self.ligature_list(h, false);
        let r = self.nodes.next(h);
        if !r.is_null() {
            self.nodes.set_prev(r, NodeRef::NULL);
        }
        self.nodes.free(h);
        r
    }

    /// Handles a discretionary `d` that follows the glyph `last` (whose
    /// predecessor is found through `prev` links): moves neighbouring
    /// glyphs into it when ligatures cross it, then ligatures its lists.
    /// Returns (prev, next) for continuing the scan after `d`.
    fn lig_disc(&mut self, before: NodeRef, last: NodeRef, d: NodeRef) -> (NodeRef, NodeRef) {
        let f = self.nodes.glyph(last).map_or(0, |g| g.font);
        if self.font(f).lig_kern.is_empty() {
            self.lig_disc_lists(d);
            return (d, self.nodes.next(d));
        }
        let lc = self.nodes.glyph(last).map_or(0, |g| g.chr);
        let (pre, post, rep) = self.nodes.disc_lists(d);
        let after = self.nodes.next(d);
        let crosses =
            |e: &Engine, l: NodeRef| e.glyph_of_font(l, f).and_then(|c| e.lig_step(f, lc, c));
        let left = crosses(self, pre).is_some()
            || (!rep.is_null() && crosses(self, rep).is_some())
            || (rep.is_null() && crosses(self, after).is_some());
        let (mut pre, mut post, mut rep) = (pre, post, rep);
        if left {
            // Move `last` into the discretionary.
            self.nodes.link(before, d);
            self.nodes.set_next(last, NodeRef::NULL);
            self.nodes.set_prev(last, NodeRef::NULL);
            let copy = self.nodes.copy_node(last);
            pre = self.concat(copy, pre);
            rep = self.concat(last, rep);
        }
        // Move following glyphs into the discretionary while a ligature
        // crosses the right edge.
        loop {
            let n = self.nodes.next(d);
            let Some(nc) = self.glyph_of_font(n, f) else {
                break;
            };
            let ends = |e: &Engine, l: NodeRef| {
                if l.is_null() {
                    return false;
                }
                let t = e.nodes.tail_of(l);
                e.glyph_of_font(t, f)
                    .is_some_and(|c| e.lig_step(f, c, nc).is_some())
            };
            if !(ends(self, post) || ends(self, rep)) {
                break;
            }
            let nn = self.nodes.next(n);
            self.nodes.link(d, nn);
            if nn.is_null() {
                self.nodes.set_next(d, NodeRef::NULL);
            }
            self.nodes.set_next(n, NodeRef::NULL);
            self.nodes.set_prev(n, NodeRef::NULL);
            let copy = self.nodes.copy_node(n);
            post = self.concat(post, copy);
            rep = self.concat(rep, n);
        }
        self.nodes.set_disc_lists(d, (pre, post, rep));
        self.lig_disc_lists(d);
        (d, self.nodes.next(d))
    }

    /// Builds ligatures in the run of glyphs starting at `p` (with
    /// predecessor `prev`); returns the last glyph of the processed run
    /// and its predecessor.
    fn ligature_run(&mut self, prev: NodeRef, p: NodeRef) -> (NodeRef, NodeRef) {
        let f = self.nodes.glyph(p).map_or(0, |g| g.font);
        if self.font(f).lig_kern.is_empty() {
            // No ligatures in this font: skip the run.
            let (mut qp, mut q) = (prev, p);
            loop {
                let n = self.nodes.next(q);
                if self.glyph_of_font(n, f).is_none() {
                    return (qp, q);
                }
                qp = q;
                q = n;
            }
        }
        let mut cur_prev = prev;
        let mut cur = p;
        let mut guard = 0u32;
        loop {
            let nxt = self.nodes.next(cur);
            let (Some(l), Some(r)) = (self.glyph_of_font(cur, f), self.glyph_of_font(nxt, f))
            else {
                return (cur_prev, cur);
            };
            guard += 1;
            if guard > 100_000 {
                // An infinite ligature loop in a broken font.
                return (cur_prev, cur);
            }
            let Some((op, c)) = self.lig_step(f, l, r) else {
                cur_prev = cur;
                cur = nxt;
                continue;
            };
            let after = self.nodes.next(nxt);
            match op {
                0 => {
                    // =: — both characters replaced.
                    let a = self.take_components(cur);
                    let b = self.take_components(nxt);
                    let comps = self.concat(a, b);
                    let model = if comps.is_null() { cur } else { comps };
                    let lig = self.new_ligature(model, c, comps);
                    self.replace_node(cur_prev, after, lig);
                    cur = lig;
                }
                1 | 5 => {
                    // =:| and =:|> — the left character is replaced.
                    let a = self.take_components(cur);
                    let model = if a.is_null() { nxt } else { a };
                    let lig = self.new_ligature(model, c, a);
                    self.replace_node(cur_prev, nxt, lig);
                    if op == 5 {
                        cur_prev = lig;
                        cur = nxt;
                    } else {
                        cur = lig;
                    }
                }
                2 | 6 => {
                    // |=: and |=:> — the right character is replaced.
                    let b = self.take_components(nxt);
                    let model = if b.is_null() { cur } else { b };
                    let lig = self.new_ligature(model, c, b);
                    self.replace_node(cur, after, lig);
                    if op == 6 {
                        cur_prev = cur;
                        cur = lig;
                    }
                }
                _ => {
                    // |=:|, |=:|>, |=:|>> — a character is inserted.
                    let lig = self.new_ligature(cur, c, NodeRef::NULL);
                    self.nodes.set_subtype(lig, 0);
                    self.replace_node(cur, nxt, lig);
                    match op {
                        7 => {
                            cur_prev = cur;
                            cur = lig;
                        }
                        11 => {
                            cur_prev = lig;
                            cur = nxt;
                        }
                        _ => {}
                    }
                }
            }
        }
    }

    // ----- kerning -------------------------------------------------------

    /// The font kern between (`l`, `r`) in font `f`.
    #[inline]
    fn kern_between(&self, f: u32, l: u32, r: u32) -> Option<i32> {
        match self.lig_kern_step(f, l, r) {
            Some(LigOp::Kern(k)) => Some(k),
            _ => None,
        }
    }

    /// A font kern node with the attributes of `model`.
    fn font_kern(&mut self, k: i32, model: NodeRef) -> NodeRef {
        let n = self.nodes.new_kern(k, kern_sub::FONT);
        let a = self.nodes.attr(model).cloned();
        self.nodes.set_attr(n, a);
        n
    }

    /// Inserts font kerns into the list after `head` and clears the
    /// character subtype of glyphs.
    fn kern_list(&mut self, head: NodeRef) {
        let mut p = self.nodes.next(head);
        while !p.is_null() {
            match self.nodes.id(p) {
                id::GLYPH => {
                    let s = self.nodes.subtype(p) & !glyph_sub::CHARACTER;
                    self.nodes.set_subtype(p, s);
                    let n = self.nodes.next(p);
                    if n.is_null() {
                        break;
                    }
                    let (f, l) = match self.nodes.glyph(p) {
                        Some(g) => (g.font, g.chr),
                        None => break,
                    };
                    if self.nodes.id(n) == id::GLYPH {
                        if let Some(r) = self.glyph_of_font(n, f)
                            && let Some(k) = self.kern_between(f, l, r)
                        {
                            let kn = self.font_kern(k, p);
                            self.nodes.link(p, kn);
                            self.nodes.link(kn, n);
                        }
                        p = n;
                    } else if self.nodes.id(n) == id::DISC {
                        self.kern_disc(p, n);
                        p = self.nodes.next(n);
                    } else {
                        p = n;
                    }
                }
                id::DISC => {
                    self.kern_disc(NodeRef::NULL, p);
                    p = self.nodes.next(p);
                }
                _ => p = self.nodes.next(p),
            }
        }
    }

    /// Kerns a discretionary with its neighbours (`before` may be null)
    /// and kerns its lists.
    fn kern_disc(&mut self, before: NodeRef, d: NodeRef) {
        let (mut pre, mut post, mut rep) = self.nodes.disc_lists(d);
        pre = self.kern_sublist(pre);
        post = self.kern_sublist(post);
        let rep_was_empty = rep.is_null();
        rep = self.kern_sublist(rep);
        let after = self.nodes.next(d);
        let bg = if before.is_null() {
            None
        } else {
            self.nodes.glyph(before).map(|g| (g.font, g.chr))
        };
        let ag = if after.is_null() || self.nodes.id(after) != id::GLYPH {
            None
        } else {
            self.nodes.glyph(after).map(|g| (g.font, g.chr))
        };
        // Observed: the discretionaries of an explicit hyphen (subtype 2)
        // and of hyphenation (3) are not kerned with the character before
        // them in their pre-break text, nor (an explicit hyphen's) in
        // their replacement; those of `\-` and `\discretionary` are.
        let sub = self.nodes.subtype(d);
        let left_kerns = !matches!(sub, 2 | 3);
        if let Some((f, l)) = bg {
            if left_kerns
                && let Some(r) = self.glyph_of_font(pre, f)
                && let Some(k) = self.kern_between(f, l, r)
            {
                let kn = self.font_kern(k, before);
                self.nodes.link(kn, pre);
                pre = kn;
            }
            if sub == 2 {
                // No kern in the replacement.
            } else if !rep_was_empty {
                if let Some(r) = self.glyph_of_font(rep, f)
                    && let Some(k) = self.kern_between(f, l, r)
                {
                    let kn = self.font_kern(k, before);
                    self.nodes.link(kn, rep);
                    rep = kn;
                }
            } else if let Some((af, ac)) = ag
                && af == f
                && let Some(k) = self.kern_between(f, l, ac)
            {
                rep = self.font_kern(k, before);
            }
        }
        if let Some((f, r)) = ag {
            if !post.is_null() {
                let t = self.nodes.tail_of(post);
                if let Some(l) = self.glyph_of_font(t, f)
                    && let Some(k) = self.kern_between(f, l, r)
                {
                    let kn = self.font_kern(k, after);
                    self.nodes.link(t, kn);
                }
            }
            if !rep_was_empty {
                let t = self.nodes.tail_of(rep);
                if let Some(l) = self.glyph_of_font(t, f)
                    && let Some(k) = self.kern_between(f, l, r)
                {
                    let kn = self.font_kern(k, after);
                    self.nodes.link(t, kn);
                }
            }
        }
        self.nodes.set_disc_lists(d, (pre, post, rep));
    }

    /// Kerns a detached list; returns its new head.
    fn kern_sublist(&mut self, l: NodeRef) -> NodeRef {
        if l.is_null() {
            return l;
        }
        let h = self.nodes.new_temp();
        self.nodes.link(h, l);
        self.kern_list(h);
        let r = self.nodes.next(h);
        if !r.is_null() {
            self.nodes.set_prev(r, NodeRef::NULL);
        }
        self.nodes.free(h);
        r
    }
}