retex_lua/

otfnodes.rs

//! luaotfload's node processor: OpenType shaping applied to node lists.
//!
//! A *run* is a sequence of unprocessed glyphs of one OpenType font,
//! possibly interrupted by discretionaries whose lists hold only such
//! glyphs. Runs are shaped with [`retex_font::Shaper`] and the glyph nodes
//! are replaced by the result (glyphs, ligatures with their components,
//! font kerns). Shaped glyphs are marked as processed (subtype bit 256),
//! as LuaTeX's `node.protect_glyphs` does.
//!
//! Discretionaries take part in shaping as luaotfload does. Observed with
//! `luatex` (Latin Modern and Linux Libertine, see the regression tests):
//!
//! * The unbroken text (each discretionary replaced by its replacement
//!   list) is shaped as a whole. Its glyphs that come entirely from text
//!   before a discretionary stay in front of it, those entirely from text
//!   after it stay behind it; everything in between (kerns across the
//!   break point, ligatures that span it) becomes the replacement list. So
//!   a kern between `n` and `t` gives `n{-||[k]}t`, and `of\-fice` gives
//!   `o{f-|fi|ffi}ce`.
//! * The pre-break list is the characters the replacement took from the
//!   left followed by the pre-break text, shaped on their own; the
//!   post-break list likewise. The glyph outside next to them only adds a
//!   kern at the boundary: in bold Libertine (no `ffl` ligature)
//!   `af\-fluent` gives `a{f-|f[k]|ff[k]}luent`, without an `fl` ligature
//!   in the post-break list.
//! * When two discretionaries follow each other directly, nothing is
//!   shaped across them (`W\-\-o` gets no kern).

use std::collections::HashSet;
use std::sync::Arc;

use retex_engine::Engine;
use retex_engine::nodes::{GlyphData, NodeData, NodeRef, glyph_sub, id, kern_sub};
use retex_font::{LoadedFont, ShapedItem};

use crate::luaotfload::loaded_font;

/// Protection bit LuaTeX sets in the subtype of processed glyphs.
const PROTECTED: u16 = 256;

/// The unprocessed glyph `p` in font `font`, if it is one.
fn is_raw_glyph(e: &Engine, p: NodeRef, font: u32) -> bool {
    let n = e.nodes.get(p);
    matches!(&n.data, NodeData::Glyph(g) if g.font == font && n.subtype < PROTECTED)
}

/// The nodes of the list starting at `head`, if all are unprocessed glyphs
/// of `font`.
fn glyph_list(e: &Engine, head: NodeRef, font: u32) -> Option<Vec<NodeRef>> {
    let mut v = Vec::new();
    let mut p = head;
    while !p.is_null() {
        if !is_raw_glyph(e, p, font) {
            return None;
        }
        v.push(p);
        p = e.nodes.next(p);
    }
    Some(v)
}

fn disc_lists(e: &Engine, d: NodeRef) -> [NodeRef; 3] {
    match &e.nodes.get(d).data {
        NodeData::Disc {
            pre, post, replace, ..
        } => [*pre, *post, *replace],
        _ => [NodeRef::NULL; 3],
    }
}

fn set_disc_lists(e: &mut Engine, d: NodeRef, lists: [NodeRef; 3]) {
    if let NodeData::Disc {
        pre, post, replace, ..
    } = &mut e.nodes.get_mut(d).data
    {
        [*pre, *post, *replace] = lists;
    }
}

/// How many characters of context [`context`] collects on each side.
const CONTEXT_LEN: usize = 8;

/// The text around a run that contextual lookups can see: from `p`
/// onwards (or backwards), glue counts as a space and glyphs of `font` as
/// their characters; anything else ends it. Observed with luaotfload (Inter's
/// `calt`: `A) v` keeps the default `)`, `A)\kern0pt v`, `A)~v` and
/// `A)\penalty0 v` get the capital form).
fn context(e: &Engine, mut p: NodeRef, font: u32, forward: bool) -> Vec<u32> {
    let mut out = Vec::new();
    while !p.is_null() && out.len() < CONTEXT_LEN {
        match &e.nodes.get(p).data {
            NodeData::Glue { .. } => out.push(0x20),
            NodeData::Glyph(g) if g.font == font => out.push(g.chr),
            _ => break,
        }
        p = if forward {
            e.nodes.next(p)
        } else {
            e.nodes.prev(p)
        };
    }
    if !forward {
        out.reverse();
    }
    out
}

fn chr(e: &Engine, p: NodeRef) -> u32 {
    match &e.nodes.get(p).data {
        NodeData::Glyph(g) => g.chr,
        _ => 0,
    }
}

/// A run: glyph segments separated by discretionaries
/// (`segs.len() == discs.len() + 1`).
struct DiscRun {
    segs: Vec<Vec<NodeRef>>,
    discs: Vec<NodeRef>,
    /// Pre, post and replacement glyphs of each discretionary.
    lists: Vec<[Vec<NodeRef>; 3]>,
}

/// Shapes all runs of unprocessed glyphs in the list starting at `head`
/// (luaotfload's node mode). Returns the (possibly new) head of the list.
pub fn process_list(e: &mut Engine, head: NodeRef) -> NodeRef {
    let mut head = head;
    let mut p = head;
    while !p.is_null() {
        let node = e.nodes.get(p);
        match &node.data {
            NodeData::Glyph(g) if node.subtype < PROTECTED => {
                let font = g.font;
                let Some(lf) = loaded_font(e, font) else {
                    p = e.nodes.next(p);
                    continue;
                };
                let mut run = DiscRun {
                    segs: vec![vec![p]],
                    discs: Vec::new(),
                    lists: Vec::new(),
                };
                let mut q = e.nodes.next(p);
                while !q.is_null() {
                    if is_raw_glyph(e, q, font) {
                        run.segs.last_mut().expect("segment").push(q);
                    } else if e.nodes.id(q) == id::DISC {
                        let [pre, post, rep] = disc_lists(e, q);
                        let (Some(a), Some(b), Some(c)) = (
                            glyph_list(e, pre, font),
                            glyph_list(e, post, font),
                            glyph_list(e, rep, font),
                        ) else {
                            break;
                        };
                        run.discs.push(q);
                        run.lists.push([a, b, c]);
                        run.segs.push(Vec::new());
                    } else {
                        break;
                    }
                    q = e.nodes.next(q);
                }
                let first = p;
                let ctx = if lf.shaper.uses_context {
                    (
                        context(e, e.nodes.prev(first), font, false),
                        context(e, q, font, true),
                    )
                } else {
                    (Vec::new(), Vec::new())
                };
                let new_first = if run.discs.is_empty() {
                    shape_plain(e, &lf, &run.segs[0], &ctx)
                } else {
                    shape_disc_run(e, &lf, &run, &ctx)
                        .unwrap_or_else(|| shape_separately(e, &lf, &run))
                };
                if first == head {
                    head = new_first;
                }
                p = q;
            }
            NodeData::Disc { .. } => {
                let lists = disc_lists(e, p);
                let new = lists.map(|l| if l.is_null() { l } else { process_list(e, l) });
                set_disc_lists(e, p, new);
                p = e.nodes.next(p);
            }
            _ => p = e.nodes.next(p),
        }
    }
    head
}

/// Builds nodes for shaped `items`; `src[i]` is the original glyph node of
/// input character `i`, whose data and attributes the new glyph inherits.
///
/// A glyph that comes from a single source glyph reuses that node (once;
/// `reused` collects them), as luaotfload changes glyph nodes in place: the
/// node keeps its identity, so Lua properties set before shaping survive
/// (tagpdf marks discretionary hyphens in `pre_shaping_filter` and rewrites
/// them in `post_shaping_filter`).
fn build(
    e: &mut Engine,
    items: &[ShapedItem],
    src: &[NodeRef],
    reused: &mut HashSet<NodeRef>,
) -> Vec<NodeRef> {
    let mut out = Vec::with_capacity(items.len());
    let Some(&last_src) = src.last() else {
        return out;
    };
    let source = |k: usize| src.get(k).copied().unwrap_or(last_src);
    for it in items {
        match it {
            ShapedItem::Glyph(g) => {
                let s = source(g.cluster);
                let mut data = match &e.nodes.get(s).data {
                    NodeData::Glyph(d) => d.clone(),
                    _ => GlyphData::default(),
                };
                let attr = e.nodes.get(s).attr.clone();
                data.chr = g.code;
                data.xoffset = g.x_offset;
                data.yoffset = g.y_offset;
                data.components = NodeRef::NULL;
                let mut subtype = glyph_sub::CHARACTER | PROTECTED;
                if !g.components.is_empty() {
                    let mut ch = NodeRef::NULL;
                    let mut tail = NodeRef::NULL;
                    for (k, &c) in g.components.iter().enumerate() {
                        let n = e.nodes.copy_node(source(g.cluster + k));
                        if let NodeData::Glyph(gd) = &mut e.nodes.get_mut(n).data {
                            gd.chr = c;
                        }
                        if ch.is_null() {
                            ch = n;
                        } else {
                            e.nodes.link(tail, n);
                        }
                        tail = n;
                    }
                    data.components = ch;
                    // luaotfload keeps the components but does not mark
                    // the glyph as a ligature (observed subtype 256), so
                    // box displays show no "(ligature …)".
                    subtype = PROTECTED;
                }
                let n = if data.components.is_null() && reused.insert(s) {
                    let node = e.nodes.get_mut(s);
                    node.subtype = subtype;
                    node.data = NodeData::Glyph(data);
                    s
                } else {
                    let n = e.nodes.alloc(id::GLYPH, subtype, NodeData::Glyph(data));
                    e.nodes.get_mut(n).attr = attr;
                    n
                };
                out.push(n);
            }
            ShapedItem::Kern(k) => {
                let attr = e.nodes.get(last_src).attr.clone();
                let n = e.nodes.new_kern(*k, kern_sub::FONT);
                // luaotfload copies its kerns: they get the current line.
                e.nodes.sync_as_copied(n);
                e.nodes.get_mut(n).attr = attr;
                out.push(n);
            }
        }
    }
    // Kerns take the attributes of the glyph before them.
    for i in 1..out.len() {
        if e.nodes.id(out[i]) == id::KERN {
            let a = e.nodes.get(out[i - 1]).attr.clone();
            e.nodes.get_mut(out[i]).attr = a;
        }
    }
    out
}

/// Links `nodes` into a list and returns its head.
fn link_all(e: &mut Engine, nodes: &[NodeRef]) -> NodeRef {
    for w in nodes.windows(2) {
        e.nodes.link(w[0], w[1]);
    }
    if let Some(&f) = nodes.first() {
        e.nodes.get_mut(f).prev = NodeRef::NULL;
    }
    if let Some(&l) = nodes.last() {
        e.nodes.get_mut(l).next = NodeRef::NULL;
    }
    nodes.first().copied().unwrap_or(NodeRef::NULL)
}

/// Frees glyph nodes (each a single node in some list), except those
/// reused by [`build`].
fn free_glyphs(e: &mut Engine, nodes: &[NodeRef], reused: &HashSet<NodeRef>) {
    for &n in nodes {
        if !reused.contains(&n) {
            e.nodes.get_mut(n).next = NodeRef::NULL;
            e.nodes.flush_list(n);
        }
    }
}

/// Replaces the nodes from `first` to `last` (inclusive) of a list by
/// `new`; returns the node now in the place of `first`.
fn splice(e: &mut Engine, first: NodeRef, last: NodeRef, new: &[NodeRef]) -> NodeRef {
    let prev = e.nodes.get(first).prev;
    let next = e.nodes.next(last);
    let mut cur = prev;
    for &n in new {
        if cur.is_null() {
            e.nodes.get_mut(n).prev = NodeRef::NULL;
        } else {
            e.nodes.link(cur, n);
        }
        cur = n;
    }
    if cur.is_null() {
        return next;
    }
    e.nodes.link(cur, next);
    if !next.is_null() {
        e.nodes.get_mut(next).prev = cur;
    }
    new.first().copied().unwrap_or(next)
}

/// Shapes a run of glyphs without discretionaries.
/// Context characters before and after a run (see [`context`]).
type Context = (Vec<u32>, Vec<u32>);

fn shape_plain(e: &mut Engine, lf: &Arc<LoadedFont>, run: &[NodeRef], ctx: &Context) -> NodeRef {
    let chars: Vec<u32> = run.iter().map(|&n| chr(e, n)).collect();
    let items = lf
        .shaper
        .shape_in_context(&lf.file, &lf.tex, &ctx.0, &chars, &ctx.1);
    let unchanged = items.len() == run.len()
        && items.iter().zip(&chars).all(|(it, &c)| {
            matches!(it, ShapedItem::Glyph(g) if g.code == c && g.components.is_empty()
                && g.x_offset == 0 && g.y_offset == 0)
        });
    let first = run[0];
    let last = *run.last().expect("non-empty run");
    if unchanged {
        for &n in run {
            e.nodes.get_mut(n).subtype |= PROTECTED;
        }
        return first;
    }
    let mut reused = HashSet::new();
    let new = build(e, &items, run, &mut reused);
    let new_first = splice(e, first, last, &new);
    free_glyphs(e, run, &reused);
    new_first
}

fn n_chars(it: &ShapedItem) -> usize {
    match it {
        ShapedItem::Glyph(g) => g.components.len().max(1),
        ShapedItem::Kern(_) => 0,
    }
}

/// Shapes a run with discretionaries as described in the module
/// documentation. Returns `None` (leaving the nodes untouched) when the
/// run cannot be handled that way.
fn shape_disc_run(
    e: &mut Engine,
    lf: &Arc<LoadedFont>,
    run: &DiscRun,
    ctx: &Context,
) -> Option<NodeRef> {
    let k = run.discs.len();
    if run.segs[1..k].iter().any(Vec::is_empty) {
        return None;
    }
    // The unbroken text and the start of each replacement in it.
    let mut usrc: Vec<NodeRef> = Vec::new();
    let mut starts = Vec::with_capacity(k);
    for i in 0..k {
        usrc.extend(&run.segs[i]);
        starts.push(usrc.len());
        usrc.extend(&run.lists[i][2]);
    }
    usrc.extend(&run.segs[k]);
    let uchars: Vec<u32> = usrc.iter().map(|&n| chr(e, n)).collect();
    let has = |c: u32| lf.tex.has_char(c);
    if retex_font::normalize::normalize(&uchars, has) != uchars {
        return None;
    }
    let shape = |src: &[NodeRef]| {
        let chars: Vec<u32> = src.iter().map(|&n| chr(e, n)).collect();
        lf.shaper.shape(&lf.file, &lf.tex, &chars)
    };
    let u = lf
        .shaper
        .shape_in_context(&lf.file, &lf.tex, &ctx.0, &uchars, &ctx.1);
    let n = u.len();
    let is_kern = |i: usize| matches!(u[i], ShapedItem::Kern(_));
    struct Piece {
        pre: (Vec<ShapedItem>, Vec<NodeRef>),
        post: (Vec<ShapedItem>, Vec<NodeRef>),
        lo: usize,
        hi: usize,
    }
    let mut pieces: Vec<Piece> = Vec::with_capacity(k);
    let mut prev_hi = 0usize;
    let glyph_id = |it: &ShapedItem| match it {
        ShapedItem::Glyph(g) => g.glyph,
        ShapedItem::Kern(_) => None,
    };
    for (&a, lists) in starts.iter().zip(&run.lists) {
        let [pre, post, rep] = lists;
        let b = a + rep.len();
        // The items of `u` entirely before the replacement stay in front
        // of the discretionary; those entirely after it, behind.
        let mut lo = 0;
        while lo < n
            && match &u[lo] {
                ShapedItem::Glyph(g) => g.cluster + n_chars(&u[lo]) <= a,
                ShapedItem::Kern(_) => true,
            }
        {
            lo += 1;
        }
        while lo > 0 && is_kern(lo - 1) {
            lo -= 1;
        }
        let mut s = 0;
        while s < n
            && match &u[n - 1 - s] {
                ShapedItem::Glyph(g) => g.cluster >= b,
                ShapedItem::Kern(_) => true,
            }
        {
            s += 1;
        }
        while s > 0 && is_kern(n - s) {
            s -= 1;
        }
        let hi = n - s;
        if lo < prev_hi || hi < lo {
            return None;
        }
        // The characters the replacement took from either side.
        let ca = u[..lo]
            .iter()
            .filter_map(|it| match it {
                ShapedItem::Glyph(g) => Some(g.cluster + n_chars(it)),
                ShapedItem::Kern(_) => None,
            })
            .max()
            .unwrap_or(0)
            .min(a);
        let cb = u[hi..]
            .iter()
            .filter_map(|it| match it {
                ShapedItem::Glyph(g) => Some(g.cluster),
                ShapedItem::Kern(_) => None,
            })
            .min()
            .unwrap_or(usrc.len())
            .max(b);
        // Pre-break and post-break texts are shaped on their own; the
        // glyphs outside only add a kern at the boundary.
        let mut psrc = usrc[ca..a].to_vec();
        psrc.extend(pre);
        let mut qsrc = post.clone();
        qsrc.extend(&usrc[b..cb]);
        let mut pre_items = shape(&psrc);
        let mut post_items = shape(&qsrc);
        if let (Some(l), Some(r)) = (
            lo.checked_sub(1).and_then(|i| glyph_id(&u[i])),
            pre_items.first().and_then(glyph_id),
        ) {
            let k = lf.shaper.pair_kern(&lf.file, &lf.tex, l, r);
            if k != 0 {
                pre_items.insert(0, ShapedItem::Kern(k));
            }
        }
        if let (Some(l), Some(r)) = (
            post_items.last().and_then(glyph_id),
            u.get(hi).and_then(glyph_id),
        ) {
            let k = lf.shaper.pair_kern(&lf.file, &lf.tex, l, r);
            if k != 0 {
                post_items.push(ShapedItem::Kern(k));
            }
        }
        pieces.push(Piece {
            pre: (pre_items, psrc),
            post: (post_items, qsrc),
            lo,
            hi,
        });
        prev_hi = hi;
    }
    // Build the new list.
    let mut out: Vec<NodeRef> = Vec::new();
    let mut pos = 0usize;
    let mut reused = HashSet::new();
    for (i, pc) in pieces.iter().enumerate() {
        out.extend(build(e, &u[pos..pc.lo], &usrc, &mut reused));
        let pre = build(e, &pc.pre.0, &pc.pre.1, &mut reused);
        let post = build(e, &pc.post.0, &pc.post.1, &mut reused);
        let rep = build(e, &u[pc.lo..pc.hi], &usrc, &mut reused);
        let d = run.discs[i];
        let lists = [link_all(e, &pre), link_all(e, &post), link_all(e, &rep)];
        set_disc_lists(e, d, lists);
        out.push(d);
        pos = pc.hi;
    }
    out.extend(build(e, &u[pos..], &usrc, &mut reused));
    // Free the old glyphs, then splice.
    let first = run.segs[0][0];
    let last = run
        .segs
        .last()
        .and_then(|s| s.last().copied())
        .unwrap_or(*run.discs.last().expect("a discretionary"));
    let new_first = splice(e, first, last, &out);
    for seg in &run.segs {
        free_glyphs(e, seg, &reused);
    }
    for l in &run.lists {
        for part in l {
            free_glyphs(e, part, &reused);
        }
    }
    Some(new_first)
}

/// Shapes the segments and discretionary lists of `run` independently.
fn shape_separately(e: &mut Engine, lf: &Arc<LoadedFont>, run: &DiscRun) -> NodeRef {
    let mut first = NodeRef::NULL;
    for (i, seg) in run.segs.iter().enumerate() {
        if !seg.is_empty() {
            let f = shape_plain(e, lf, seg, &(Vec::new(), Vec::new()));
            if i == 0 {
                first = f;
            }
        }
        if let Some(&d) = run.discs.get(i) {
            let lists = disc_lists(e, d);
            let new = lists.map(|l| if l.is_null() { l } else { process_list(e, l) });
            set_disc_lists(e, d, new);
        }
    }
    first
}