retex_engine/
protrusion.rs

1//! Character protrusion (margin kerning): `\protrudechars`, `\lpcode`,
2//! `\rpcode`, margin kern nodes, `\leftmarginkern` and `\rightmarginkern`.
3//!
4//! A character at the start (end) of a line may stick out into the left
5//! (right) margin by `\lpcode` (`\rpcode`) thousandths of the font's quad.
6//! With `\protrudechars` > 0, the post-line-break pass puts a margin kern
7//! of minus that amount at the start (end) of each line; with
8//! `\protrudechars` > 1 the line breaker counts the protrusion when it
9//! measures candidate lines (LuaTeX manual, *protrusion*; Hàn Thế Thành's
10//! thesis, chapter 3).
11//!
12//! Which character counts as "at the edge" was established by black-box
13//! tests against LuaTeX 1.22. Searching from the line end inwards, these
14//! nodes are passed over (the list in the LuaTeX manual): glue without
15//! width, stretch and shrink, penalties, empty discretionaries, font kerns
16//! and kerns of width zero, rules of zero width, height and depth, math
17//! nodes without surround, direction and local paragraph nodes, empty
18//! zero-sized hlists, inserts, marks, adjusts, boundaries and whatsits. A
19//! non-empty hlist is searched recursively; at the left edge, when it has
20//! no character, only a character right after it continues. Anything else
21//! ends the search without a protruding character.
22//!
23//! The line breaker searches a little differently from the post-line-break
24//! pass:
25//!
26//! * at the start of a line it first skips what the post-line-break pass
27//!   will prune (glue, explicit kerns, penalties and math nodes after the
28//!   break), starting at the break node itself;
29//! * after a break at a discretionary, the post-break text counts only if
30//!   it starts with a character (nothing in it is skipped); an empty
31//!   post-break text continues the search at the discretionary node,
32//!   which only an empty discretionary lets through;
33//! * before a break at a discretionary, likewise the pre-break text counts
34//!   only if it ends with a character; an empty one continues before the
35//!   discretionary;
36//! * the last line of a paragraph gets no right protrusion in line
37//!   breaking, whatever `\parfillskip` is (the post-line-break pass still
38//!   adds its margin kern).
39
40use crate::Engine;
41use crate::nodes::{NodeData, NodeRef, id, kern_sub};
42
43/// Subtype of a left margin kern node.
44pub const LEFT_SIDE: u16 = 0;
45/// Subtype of a right margin kern node.
46pub const RIGHT_SIDE: u16 = 1;
47
48/// The result of searching for a protruding character.
49enum Found {
50    /// A glyph.
51    Char(NodeRef),
52    /// The search ended at a node that stops protrusion.
53    Blocked,
54    /// The list ended without a decision.
55    End,
56}
57
58/// Rounds `a / b` to the nearest integer, halves away from zero (`b` > 0).
59pub(crate) fn round_div(a: i64, b: i64) -> i64 {
60    if a >= 0 {
61        (2 * a + b) / (2 * b)
62    } else {
63        -((-2 * a + b) / (2 * b))
64    }
65}
66
67impl Engine {
68    /// The protrusion of glyph `p` into the left (`left`) or right margin,
69    /// in sp: the `\lpcode`/`\rpcode` of its character in thousandths of
70    /// the font's quad. The margin kern is minus this amount.
71    pub fn char_protrusion(&self, p: NodeRef, left: bool) -> i32 {
72        let Some(g) = self.nodes.glyph(p) else {
73            return 0;
74        };
75        let fi = self.font(g.font);
76        let code = fi.char_codes[usize::from(!left)]
77            .get(&g.chr)
78            .copied()
79            .unwrap_or(0);
80        if code == 0 {
81            return 0;
82        }
83        let quad = i64::from(self.quad(g.font));
84        round_div(i64::from(code) * quad, 1000) as i32
85    }
86
87    /// Whether node `p` is passed over when looking for a protruding
88    /// character.
89    fn protrusion_skippable(&self, p: NodeRef) -> bool {
90        match self.nodes.data(p) {
91            NodeData::Glue { spec, .. } => spec.width == 0 && spec.stretch == 0 && spec.shrink == 0,
92            NodeData::Penalty { .. } => true,
93            NodeData::Disc {
94                pre, post, replace, ..
95            } => pre.is_null() && post.is_null() && replace.is_null(),
96            NodeData::Kern { kern, .. } => *kern == 0 || self.nodes.subtype(p) == kern_sub::FONT,
97            NodeData::Rule {
98                width,
99                height,
100                depth,
101                ..
102            } => *width == 0 && *height == 0 && *depth == 0,
103            NodeData::Math { surround, glue } => {
104                *surround == 0 && glue.width == 0 && glue.stretch == 0 && glue.shrink == 0
105            }
106            NodeData::Dir { .. }
107            | NodeData::LocalPar { .. }
108            | NodeData::Ins { .. }
109            | NodeData::Mark { .. }
110            | NodeData::Adjust { .. }
111            | NodeData::Boundary { .. }
112            | NodeData::Whatsit(_) => true,
113            NodeData::Box(b) => {
114                self.nodes.id(p) == id::HLIST
115                    && b.head.is_null()
116                    && b.width == 0
117                    && b.height == 0
118                    && b.depth == 0
119            }
120            _ => false,
121        }
122    }
123
124    /// Whether `p` is pruned at the start of a line after a break.
125    fn pruned_after_break(&self, p: NodeRef) -> bool {
126        match self.nodes.id(p) {
127            id::GLUE | id::PENALTY | id::MATH => true,
128            id::KERN => matches!(self.nodes.subtype(p), kern_sub::USER | kern_sub::ITALIC),
129            _ => false,
130        }
131    }
132
133    /// Searches forwards from `p` for the character at the left edge.
134    fn protchar_left_from(&self, mut p: NodeRef) -> Found {
135        // Observed: after a non-empty hlist without a character, only a
136        // character directly after it continues the search (a kern,
137        // penalty, glue, whatsit or box there ends it: hyperref's anchor
138        // box before a theorem head).
139        let mut after_box = false;
140        while !p.is_null() {
141            match self.nodes.id(p) {
142                id::GLYPH => return Found::Char(p),
143                _ if after_box => return Found::Blocked,
144                id::HLIST if !self.nodes.list_ptr(p).is_null() => {
145                    match self.protchar_left_from(self.nodes.list_ptr(p)) {
146                        Found::End => after_box = true,
147                        f => return f,
148                    }
149                }
150                _ if self.protrusion_skippable(p) => {}
151                _ => return Found::Blocked,
152            }
153            p = self.nodes.next(p);
154        }
155        Found::End
156    }
157
158    /// Searches the list `head` for the character at its right edge.
159    fn protchar_right_in(&self, head: NodeRef) -> Found {
160        // Collect the list, then walk it backwards (inner lists are
161        // short and their back links are not maintained everywhere).
162        let mut v = Vec::new();
163        let mut p = head;
164        while !p.is_null() {
165            v.push(p);
166            p = self.nodes.next(p);
167        }
168        self.protchar_right_rev(v.into_iter().rev())
169    }
170
171    fn protchar_right_rev(&self, it: impl Iterator<Item = NodeRef>) -> Found {
172        for p in it {
173            match self.nodes.id(p) {
174                id::GLYPH => return Found::Char(p),
175                id::HLIST if !self.nodes.list_ptr(p).is_null() => {
176                    match self.protchar_right_in(self.nodes.list_ptr(p)) {
177                        Found::End => {}
178                        f => return f,
179                    }
180                }
181                _ if self.protrusion_skippable(p) => {}
182                _ => return Found::Blocked,
183            }
184        }
185        Found::End
186    }
187
188    /// Searches backwards from `p` (inclusive) in a list with valid back
189    /// links, stopping at `stop` (exclusive).
190    fn protchar_right_back(&self, p: NodeRef, stop: NodeRef) -> Found {
191        let mut q = p;
192        let it = std::iter::from_fn(move || {
193            if q.is_null() || q == stop {
194                return None;
195            }
196            let r = q;
197            q = self.nodes.prev(q);
198            Some(r)
199        });
200        self.protchar_right_rev(it)
201    }
202
203    fn found_left(&self, f: Found) -> i32 {
204        match f {
205            Found::Char(g) => self.char_protrusion(g, true),
206            _ => 0,
207        }
208    }
209
210    fn found_right(&self, f: Found) -> i32 {
211        match f {
212            Found::Char(g) => self.char_protrusion(g, false),
213            _ => 0,
214        }
215    }
216
217    /// Line breaking: the left protrusion of a line that starts after the
218    /// break at `brk` (`None` for the first line, whose first node is
219    /// `first`).
220    pub(crate) fn lb_left_protrusion(&self, brk: Option<NodeRef>, first: NodeRef) -> i32 {
221        let mut p = match brk {
222            None => return self.found_left(self.protchar_left_from(first)),
223            Some(b) if b.is_null() => return 0,
224            Some(b) => b,
225        };
226        if self.nodes.id(p) == id::DISC {
227            let (_, post, _) = self.nodes.disc_lists(p);
228            if !post.is_null() {
229                return if self.nodes.id(post) == id::GLYPH {
230                    self.char_protrusion(post, true)
231                } else {
232                    0
233                };
234            }
235        }
236        while !p.is_null() && self.pruned_after_break(p) {
237            p = self.nodes.next(p);
238        }
239        self.found_left(self.protchar_left_from(p))
240    }
241
242    /// Line breaking: the right protrusion of a line that ends with a
243    /// break at `cur_p` (null for the end of the paragraph). Back links of
244    /// the main list must be valid; `head` is the list head.
245    pub(crate) fn lb_right_protrusion(&self, cur_p: NodeRef, head: NodeRef) -> i32 {
246        if cur_p.is_null() {
247            // The final break: LuaTeX counts no right protrusion here (even
248            // with a zero \parfillskip).
249            return 0;
250        }
251        if self.nodes.id(cur_p) == id::DISC {
252            let (pre, _, _) = self.nodes.disc_lists(cur_p);
253            if !pre.is_null() {
254                let t = self.nodes.tail_of(pre);
255                return if self.nodes.id(t) == id::GLYPH {
256                    self.char_protrusion(t, false)
257                } else {
258                    0
259                };
260            }
261        }
262        let p = self.nodes.prev(cur_p);
263        self.found_right(self.protchar_right_back(p, head))
264    }
265
266    /// Makes the back links of the list after `head` consistent.
267    pub(crate) fn fix_back_links(&mut self, head: NodeRef) {
268        let mut prev = head;
269        let mut p = self.nodes.next(head);
270        while !p.is_null() {
271            self.nodes.set_prev(p, prev);
272            prev = p;
273            p = self.nodes.next(p);
274        }
275    }
276
277    fn new_margin_kern(&mut self, width: i32, side: u16) -> NodeRef {
278        self.new_node(
279            id::MARGIN_KERN,
280            side,
281            NodeData::MarginKern {
282                width,
283                glyph: NodeRef::NULL,
284            },
285        )
286    }
287
288    /// Post-line-break: the left margin kern for a line starting with
289    /// `line`, or null if there is no protrusion.
290    pub(crate) fn left_margin_kern(&mut self, line: NodeRef) -> NodeRef {
291        let w = self.found_left(self.protchar_left_from(line));
292        if w == 0 {
293            return NodeRef::NULL;
294        }
295        self.new_margin_kern(-w, LEFT_SIDE)
296    }
297
298    /// Post-line-break: inserts the right margin kern of the line that
299    /// starts after `pred` just before its node `q` (the break node, or
300    /// the last node of the paragraph).
301    pub(crate) fn insert_right_margin_kern(&mut self, pred: NodeRef, q: NodeRef) {
302        let mut v = Vec::new();
303        let mut p = self.nodes.next(pred);
304        while !p.is_null() && p != q {
305            v.push(p);
306            p = self.nodes.next(p);
307        }
308        if p != q || q.is_null() {
309            return;
310        }
311        let w = self.found_right(self.protchar_right_rev(v.iter().rev().copied()));
312        if w == 0 {
313            return;
314        }
315        let k = self.new_margin_kern(-w, RIGHT_SIDE);
316        let before = v.last().copied().unwrap_or(pred);
317        self.nodes.link(before, k);
318        self.nodes.link(k, q);
319    }
320
321    /// `\leftmarginkern n`, `\rightmarginkern n`: the width of the margin
322    /// kern at the start (end) of hbox `n`, passing over glue and
323    /// penalties; `None` if there is none (expands to `0pt`). A void box
324    /// or a vbox is a fatal error in LuaTeX.
325    pub fn margin_kern(&mut self, n: u32, left: bool) -> Option<i32> {
326        let b = self
327            .eqtb
328            .boxes
329            .get(n as usize)
330            .map_or(NodeRef::NULL, |b| b.val);
331        if b.is_null() || self.nodes.id(b) != id::HLIST {
332            self.luatex_fatal("marginkern", "a non-empty hbox expected");
333        }
334        let mut v = Vec::new();
335        let mut p = self.nodes.list_ptr(b);
336        while !p.is_null() {
337            v.push(p);
338            p = self.nodes.next(p);
339        }
340        if !left {
341            v.reverse();
342        }
343        let want = if left { LEFT_SIDE } else { RIGHT_SIDE };
344        for p in v {
345            match self.nodes.data(p) {
346                NodeData::MarginKern { width, .. } => {
347                    return (self.nodes.subtype(p) == want).then_some(*width);
348                }
349                NodeData::Glue { .. } | NodeData::Penalty { .. } => {}
350                _ => return None,
351            }
352        }
353        None
354    }
355
356    /// Removes the margin kerns from the top level of the list `p`
357    /// (unboxing an hbox drops them, as in LuaTeX); returns the new head.
358    pub fn strip_margin_kerns(&mut self, mut head: NodeRef) -> NodeRef {
359        while !head.is_null() && self.nodes.id(head) == id::MARGIN_KERN {
360            let n = self.nodes.next(head);
361            self.nodes.free(head);
362            head = n;
363        }
364        if head.is_null() {
365            return head;
366        }
367        self.nodes.set_prev(head, NodeRef::NULL);
368        let mut prev = head;
369        let mut p = self.nodes.next(head);
370        while !p.is_null() {
371            let n = self.nodes.next(p);
372            if self.nodes.id(p) == id::MARGIN_KERN {
373                self.nodes.free(p);
374                self.nodes.set_next(prev, n);
375                if !n.is_null() {
376                    self.nodes.set_prev(n, prev);
377                }
378            } else {
379                prev = p;
380            }
381            p = n;
382        }
383        head
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::round_div;
390
391    #[test]
392    fn rounding_halves_away_from_zero() {
393        assert_eq!(round_div(3_276_805, 10), 327_681);
394        assert_eq!(round_div(-3_276_805, 10), -327_681);
395        assert_eq!(round_div(1_966_083, 10), 196_608);
396        assert_eq!(round_div(7, 2), 4);
397        assert_eq!(round_div(-7, 2), -4);
398    }
399}
retex_engine/protrusion.rs

retex_engine/
protrusion.rs
