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).
//! * In base mode, the discretionaries of hyphenation and of explicit
//!   hyphens get no boundary kern before their pre-break text, nor
//!   explicit hyphens in their replacement (as with TFM fonts).
//!
//! `mode=harf` fonts (polyglossia's default) differ, as HarfBuzz reports
//! where breaking the shaped text is safe: a discretionary also takes the
//! glyphs on either side up to a boundary without a kern (`AV\-AV` puts
//! the whole word into it), its pre-break and post-break texts get no
//! kern with the glyphs outside, and discretionaries whose glyphs overlap
//! become one, with the first one's pre-break and the last one's
//! post-break text (`W\-\-o` gives `{W-|o|W[k]o}`).

use std::collections::{HashMap, 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 marks: HashMap<u32, bool> = HashMap::new();
    // The text direction: the paragraph's (its local_par node), changed
    // by direction nodes; right to left (TRT) shapes mode=harf text so.
    let mut base_rtl = false;
    let mut dirs: Vec<bool> = Vec::new();
    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 marks = *marks.entry(font).or_insert_with(|| {
                    let mut chars = Vec::new();
                    font_chars(e, head, font, &mut chars);
                    lf.shaper.has_marks(&lf.file, &lf.tex, &chars)
                });
                let rtl = dirs.last().copied().unwrap_or(base_rtl);
                let ctx = if lf.shaper.uses_context {
                    (
                        context(e, e.nodes.prev(first), font, false),
                        context(e, q, font, true),
                        marks,
                        rtl,
                    )
                } else {
                    (Vec::new(), Vec::new(), marks, rtl)
                };
                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, ctx.2, ctx.3))
                };
                if first == head {
                    head = new_first;
                }
                p = q;
            }
            NodeData::LocalPar { dir, .. } => {
                base_rtl = *dir == 1;
                p = e.nodes.next(p);
            }
            NodeData::Dir { dir, .. } => {
                if node.subtype == 0 {
                    dirs.push(*dir == 1);
                } else {
                    dirs.pop();
                }
                p = e.nodes.next(p);
            }
            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>,
    base: bool,
) -> 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;
                // Observed: in base mode, where TeX's own ligaturing and
                // kerning run, glyphs lose the character bit and ligatures
                // are marked as such (box displays show "(ligature …)").
                let mut subtype = if base {
                    PROTECTED
                } else {
                    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;
                    // In node mode luaotfload keeps the components but does
                    // not mark the glyph as a ligature (observed subtype
                    // 256), so box displays show no "(ligature …)".
                    subtype = if base {
                        PROTECTED | glyph_sub::LIGATURE
                    } else {
                        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`.
/// Links `new` between `prev` and `next` (either may be null), replacing
/// what was there. Returns the first node after `prev`.
fn splice(e: &mut Engine, prev: NodeRef, next: NodeRef, new: &[NodeRef]) -> NodeRef {
    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`]), and
/// whether the list holds a combining mark of the run's font (see
/// `Shaper::has_marks`).
/// The text before and after a run, whether its font's characters
/// include marks, and whether it is right to left.
type Context = (Vec<u32>, Vec<u32>, bool, bool);

/// Shapes `text`: with HarfBuzz for mode=harf fonts when the text needs it
/// (complex scripts, right to left) and for the joining scripts (Arabic)
/// in node mode, else with retex's own shaper.
fn shape_text(
    lf: &LoadedFont,
    before: &[u32],
    text: &[u32],
    after: &[u32],
    marks: bool,
    rtl: bool,
) -> Vec<retex_font::ShapedItem> {
    let harf = lf.request.mode == retex_font::Mode::Harf;
    let use_hb = if harf {
        rtl || retex_font::harf::needs_harfbuzz(text)
    } else {
        lf.request.mode == retex_font::Mode::Node && retex_font::harf::joining_script(text)
    };
    if use_hb && let Some(h) = lf.harf() {
        return h.shape(&lf.tex, text, rtl);
    }
    let mut items = lf
        .shaper
        .shape_marked(&lf.file, &lf.tex, before, text, after, marks);
    if rtl {
        mirror_mark_offsets(lf, &mut items);
    }
    items
}

/// Right-to-left text: a mark's horizontal offset counts from the left
/// edge of its base, towards the left (as LuaTeX applies it there), not
/// from the end of the base. retex's shaper gives `anchors − advances`
/// (the advances from the base to the mark); the offset is then
/// `−(anchors)`. Observed with node-mode Hebrew in DejaVu Sans.
fn mirror_mark_offsets(lf: &LoadedFont, items: &mut [retex_font::ShapedItem]) {
    use retex_font::ShapedItem;
    let mut since_base = 0i32;
    for it in items.iter_mut() {
        match it {
            ShapedItem::Glyph(g) if g.x_offset == 0 && g.y_offset == 0 => {
                since_base = g
                    .glyph
                    .map(|gid| lf.tex.glyph_metrics(gid).width)
                    .unwrap_or(0);
            }
            ShapedItem::Glyph(g) => {
                if g.x_offset != 0 {
                    g.x_offset = -(g.x_offset + since_base);
                }
                since_base += g
                    .glyph
                    .map(|gid| lf.tex.glyph_metrics(gid).width)
                    .unwrap_or(0);
            }
            ShapedItem::Kern(k) => since_base += *k,
        }
    }
}

/// The characters of font `font` in the list `head`, discretionaries
/// included.
fn font_chars(e: &Engine, head: NodeRef, font: u32, out: &mut Vec<u32>) {
    let mut p = head;
    while !p.is_null() {
        match &e.nodes.get(p).data {
            NodeData::Glyph(g) if g.font == font => out.push(chr(e, p)),
            NodeData::Disc { .. } => {
                for l in disc_lists(e, p) {
                    font_chars(e, l, font, out);
                }
            }
            _ => {}
        }
        p = e.nodes.next(p);
    }
}

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 = shape_text(lf, &ctx.0, &chars, &ctx.1, ctx.2, ctx.3);
    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");
    let base = lf.request.mode == retex_font::Mode::Base;
    if unchanged {
        for &n in run {
            let node = e.nodes.get_mut(n);
            if base {
                node.subtype &= !glyph_sub::CHARACTER;
            }
            node.subtype |= PROTECTED;
        }
        return first;
    }
    let mut reused = HashSet::new();
    let (prev, next) = (e.nodes.get(first).prev, e.nodes.next(last));
    let new = build(e, &items, run, &mut reused, base);
    let new_first = splice(e, prev, next, &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();
    let base = lf.request.mode == retex_font::Mode::Base;
    let harf = lf.request.mode == retex_font::request::Mode::Harf;
    // The run's neighbours, before its glyphs move into new lists.
    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 (prev, next) = (e.nodes.get(first).prev, e.nodes.next(last));
    if !harf && 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();
    if lf.shaper.changes_text(&lf.tex, &uchars, ctx.2) {
        return None;
    }
    let shape = |src: &[NodeRef]| {
        let chars: Vec<u32> = src.iter().map(|&n| chr(e, n)).collect();
        shape_text(lf, &[], &chars, &[], ctx.2, ctx.3)
    };
    let u = shape_text(lf, &ctx.0, &uchars, &ctx.1, ctx.2, ctx.3);
    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,
        /// Where the replacement list starts (after `lo` for an explicit
        /// hyphen, whose kern with the glyph before it goes).
        rep_lo: usize,
        /// The discretionary, and those merged into it (harf mode).
        disc: NodeRef,
        merged: Vec<NodeRef>,
    }
    let glyph_id = |it: &ShapedItem| match it {
        ShapedItem::Glyph(g) => g.glyph,
        ShapedItem::Kern(_) => None,
    };
    // The items of `u` each discretionary takes: (lo, hi, a, b).
    let mut regions: Vec<(usize, usize, usize, usize)> = Vec::with_capacity(k);
    for (&a, lists) in starts.iter().zip(&run.lists) {
        let b = a + lists[2].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 mut hi = n - s;
        if harf {
            // Out to boundaries where breaking is safe: no kern there.
            while lo > 0 && (is_kern(lo - 1) || (lo < n && is_kern(lo))) {
                lo -= 1;
            }
            while hi < n && (is_kern(hi) || (hi > 0 && is_kern(hi - 1))) {
                hi += 1;
            }
        }
        if hi < lo {
            return None;
        }
        regions.push((lo, hi, a, b));
    }
    // Groups of discretionaries that become one: overlapping ones in harf
    // mode (elsewhere an overlap is not handled).
    let mut groups: Vec<(usize, usize)> = Vec::new();
    for i in 0..k {
        match groups.last_mut() {
            Some(g) if regions[i].0 < regions[g.1].1 => {
                if !harf {
                    return None;
                }
                g.1 = i;
            }
            _ => groups.push((i, i)),
        }
    }
    let mut pieces: Vec<Piece> = Vec::with_capacity(groups.len());
    for &(first, last) in &groups {
        let lo = (first..=last).map(|i| regions[i].0).min().unwrap_or(0);
        let hi = (first..=last).map(|i| regions[i].1).max().unwrap_or(0);
        let (a, b) = (regions[first].2, regions[last].3);
        let (pre, post) = (&run.lists[first][0], &run.lists[last][1]);
        // 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; in node
        // mode the glyphs outside 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);
        // Observed in base mode, where TeX's own kerning runs, as with TFM
        // fonts: the discretionaries of explicit hyphens (subtype 2) and
        // of hyphenation (3) get no kern with the glyph before them in
        // their pre-break text, nor (explicit hyphens) in their
        // replacement. luaotfload's node mode kerns them.
        let sub = e.nodes.get(run.discs[first]).subtype;
        let left_kerns = !(base && matches!(sub, 2 | 3));
        let mut rep_lo = lo;
        if base && sub == 2 {
            while rep_lo < hi && is_kern(rep_lo) {
                rep_lo += 1;
            }
        }
        if !harf {
            if left_kerns
                && 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,
            rep_lo,
            disc: run.discs[first],
            merged: run.discs[first + 1..=last].to_vec(),
        });
    }
    // Build the new list.
    let mut out: Vec<NodeRef> = Vec::new();
    let mut pos = 0usize;
    let mut reused = HashSet::new();
    for pc in &pieces {
        out.extend(build(e, &u[pos..pc.lo], &usrc, &mut reused, base));
        let pre = build(e, &pc.pre.0, &pc.pre.1, &mut reused, base);
        let post = build(e, &pc.post.0, &pc.post.1, &mut reused, base);
        let rep = build(e, &u[pc.rep_lo..pc.hi], &usrc, &mut reused, base);
        let d = pc.disc;
        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, base));
    // Splice, then free the old glyphs.
    let new_first = splice(e, prev, next, &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);
        }
    }
    // Discretionaries merged into another one (their glyphs are freed).
    for &d in pieces.iter().flat_map(|pc| &pc.merged) {
        set_disc_lists(e, d, [NodeRef::NULL; 3]);
        e.nodes.get_mut(d).next = NodeRef::NULL;
        e.nodes.flush_list(d);
    }
    Some(new_first)
}

/// Shapes the segments and discretionary lists of `run` independently.
fn shape_separately(
    e: &mut Engine,
    lf: &Arc<LoadedFont>,
    run: &DiscRun,
    marks: bool,
    rtl: bool,
) -> 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(), marks, rtl));
            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
}