retex_engine/
pack.rs

1//! Packaging: `hpack` and `vpackage` (*TeX: The Program* §644–§679).
2//!
3//! The over/underfull box messages follow TeX82; LuaTeX's box display adds
4//! the box direction (see [`crate::showbox`]).
5
6use crate::Engine;
7use crate::build::PackSpec;
8use crate::nodes::{BoxData, NodeData, NodeRef, glue_sub, id};
9use crate::primitives_gen::{assign_dimen as dp, assign_int as ip};
10
11/// Totals of stretch and shrink by glue order (`total_stretch`,
12/// `total_shrink`).
13#[derive(Default, Clone, Copy)]
14struct Totals {
15    stretch: [i32; 5],
16    shrink: [i32; 5],
17}
18
19impl Totals {
20    #[inline]
21    fn add(&mut self, g: &crate::glue::Glue) {
22        let so = (g.stretch_order as usize).min(4);
23        let ho = (g.shrink_order as usize).min(4);
24        self.stretch[so] = self.stretch[so].wrapping_add(g.stretch);
25        self.shrink[ho] = self.shrink[ho].wrapping_add(g.shrink);
26    }
27
28    fn stretch_order(&self) -> u8 {
29        (1..5).rev().find(|&o| self.stretch[o] != 0).unwrap_or(0) as u8
30    }
31
32    fn shrink_order(&self) -> u8 {
33        (1..5).rev().find(|&o| self.shrink[o] != 0).unwrap_or(0) as u8
34    }
35}
36
37impl Engine {
38    /// With `\tracinglostchars` 4 or more (LaTeX's setting), reports glyph
39    /// `p` if its font lacks its character, as LuaTeX does each time it
40    /// measures the glyph (when packing a box and in each line-breaking
41    /// pass): `Missing character: There is no ペ (U+30DA) in font cmr10!`
42    /// on its own line, whatever `\tracingonline` (observed).
43    #[inline]
44    pub fn check_lost_char(&mut self, p: NodeRef) {
45        if self.eqtb.int(ip::TRACINGLOSTCHARS) < 4 {
46            return;
47        }
48        let NodeData::Glyph(g) = self.nodes.data(p) else {
49            return;
50        };
51        let (f, c) = (g.font, g.chr);
52        if self.fonts.char_metrics(f, c).is_some() {
53            return;
54        }
55        self.printer.print_nl("Missing character: There is no ");
56        self.printer.print_char(c);
57        self.printer.print_str(&format!(" (U+{c:04X}) in font "));
58        let name = self.font(f).name.clone();
59        self.printer.print_bytes(&name);
60        self.printer.print_char('!' as u32);
61        self.printer.print_nl("");
62    }
63
64    /// The dimensions (width, height, depth) of a glyph node.
65    #[inline]
66    pub fn glyph_dimensions(&self, p: NodeRef) -> (i32, i32, i32) {
67        match self.nodes.data(p) {
68            NodeData::Glyph(g) => match self.fonts.char_metrics(g.font, g.chr) {
69                Some(m) => (
70                    crate::expansion::expanded_width(m.width, g.expansion_factor),
71                    m.height + g.yoffset,
72                    m.depth - g.yoffset,
73                ),
74                None => (0, 0, 0),
75            },
76            _ => (0, 0, 0),
77        }
78    }
79
80    /// Gives box `r` the direction in [`Engine::pack_dir`], if any.
81    fn take_pack_dir(&mut self, r: NodeRef) {
82        let dir = std::mem::replace(&mut self.pack_dir, -1);
83        if dir >= 0
84            && let Some(b) = self.nodes.box_data_mut(r)
85        {
86            b.dir = dir;
87        }
88    }
89
90    /// Packs the hlist `p` into an hbox (`hpack`).
91    pub fn hpack(&mut self, p: NodeRef, spec: PackSpec) -> NodeRef {
92        self.fonts.sync_dense();
93        self.last_badness = 0;
94        let r = self.new_null_box_node(true);
95        self.take_pack_dir(r);
96        let (mut h, mut d, mut x) = (0i32, 0i32, 0i32);
97        let mut tot = Totals::default();
98        // `q` trails behind `p`; a temporary head holds the list so that
99        // nodes can be moved to the adjustment lists.
100        let head = self.nodes.new_temp();
101        self.nodes.link(head, p);
102        let mut q = head;
103        let mut p = p;
104        while !p.is_null() {
105            let next = self.nodes.next(p);
106            match self.nodes.data(p) {
107                NodeData::Glyph(_) => {
108                    self.check_lost_char(p);
109                    let (w, gh, gd) = self.glyph_dimensions(p);
110                    x += w;
111                    if gh > h {
112                        h = gh;
113                    }
114                    if gd > d {
115                        d = gd;
116                    }
117                }
118                NodeData::Box(b) => {
119                    x += b.width;
120                    let s = b.shift;
121                    if b.height - s > h {
122                        h = b.height - s;
123                    }
124                    if b.depth + s > d {
125                        d = b.depth + s;
126                    }
127                }
128                NodeData::Unset { b, .. } => {
129                    x += b.width;
130                    if b.height > h {
131                        h = b.height;
132                    }
133                    if b.depth > d {
134                        d = b.depth;
135                    }
136                }
137                NodeData::Rule {
138                    width,
139                    height,
140                    depth,
141                    ..
142                } => {
143                    x += *width;
144                    if *height > h {
145                        h = *height;
146                    }
147                    if *depth > d {
148                        d = *depth;
149                    }
150                }
151                NodeData::Ins { .. } | NodeData::Mark { .. } | NodeData::Adjust { .. } => {
152                    if let Some(at) = self.ts.adjust_tail {
153                        // Transfer node p to the adjustment list.
154                        self.nodes.set_next(q, next);
155                        if !next.is_null() {
156                            self.nodes.set_prev(next, q);
157                        }
158                        let is_pre = self.nodes.id(p) == id::ADJUST && self.nodes.subtype(p) == 1;
159                        if self.nodes.id(p) == id::ADJUST {
160                            let l = self.nodes.list_ptr(p);
161                            self.nodes.set_list_ptr(p, NodeRef::NULL);
162                            self.nodes.free(p);
163                            if !l.is_null() {
164                                let target = if is_pre {
165                                    self.ts.pre_adjust_tail.unwrap_or(at)
166                                } else {
167                                    at
168                                };
169                                self.nodes.link(target, l);
170                                let t = self.nodes.tail_of(l);
171                                if is_pre && self.ts.pre_adjust_tail.is_some() {
172                                    self.ts.pre_adjust_tail = Some(t);
173                                } else {
174                                    self.ts.adjust_tail = Some(t);
175                                }
176                            }
177                        } else {
178                            self.nodes.link(at, p);
179                            self.nodes.set_next(p, NodeRef::NULL);
180                            self.ts.adjust_tail = Some(p);
181                        }
182                        p = next;
183                        continue;
184                    }
185                }
186                NodeData::Glue { spec, leader } => {
187                    x += spec.width;
188                    tot.add(spec);
189                    let (leader, sub) = (*leader, self.nodes.subtype(p));
190                    if sub >= glue_sub::A_LEADERS && !leader.is_null() {
191                        let (lh, ld) = (self.node_height(leader), self.node_depth(leader));
192                        if lh > h {
193                            h = lh;
194                        }
195                        if ld > d {
196                            d = ld;
197                        }
198                    }
199                }
200                NodeData::Kern {
201                    kern,
202                    expansion_factor,
203                } => x += *kern + *expansion_factor,
204                NodeData::MarginKern { width, .. } => x += *width,
205                NodeData::Math { surround, glue } => {
206                    if glue.width != 0 || glue.stretch != 0 || glue.shrink != 0 {
207                        x += glue.width;
208                        let g = *glue;
209                        tot.add(&g);
210                    } else {
211                        x += *surround;
212                    }
213                }
214                NodeData::Disc { replace, .. } => {
215                    // The replacement text is typeset when there is no break.
216                    let mut s = *replace;
217                    while !s.is_null() {
218                        self.check_lost_char(s);
219                        let (w, sh, sd) = self.simple_dimensions(s);
220                        x += w;
221                        if sh > h {
222                            h = sh;
223                        }
224                        if sd > d {
225                            d = sd;
226                        }
227                        s = self.nodes.next(s);
228                    }
229                }
230                _ => {}
231            }
232            q = p;
233            p = next;
234        }
235        if let Some(at) = self.ts.adjust_tail {
236            self.nodes.set_next(at, NodeRef::NULL);
237        }
238        if let Some(at) = self.ts.pre_adjust_tail {
239            self.nodes.set_next(at, NodeRef::NULL);
240        }
241        let first = self.nodes.next(head);
242        self.nodes.free(head);
243        if !first.is_null() {
244            self.nodes.set_prev(first, NodeRef::NULL);
245        }
246        let w = match spec {
247            PackSpec::Exactly(w) => w,
248            PackSpec::Additional(w) => x + w,
249        };
250        {
251            let b = self.box_mut(r);
252            b.head = first;
253            b.height = h;
254            b.depth = d;
255            b.width = w;
256        }
257        self.ts.last_totals = (tot.stretch, tot.shrink);
258        let x = w - x;
259        let report: Option<()> = if x == 0 {
260            None
261        } else if x > 0 {
262            let o = tot.stretch_order();
263            let ts = tot.stretch[o as usize];
264            {
265                let b = self.box_mut(r);
266                b.glue_order = o;
267                b.glue_sign = 1;
268                if ts != 0 {
269                    b.glue_set = crate::nodes::glue_ratio(x, ts);
270                } else {
271                    b.glue_sign = 0;
272                    b.glue_set = 0.0;
273                }
274            }
275            if o == 0 && !first.is_null() {
276                self.last_badness = retex_arith::badness(x, tot.stretch[0]);
277                if self.last_badness > self.eqtb.int(ip::HBADNESS) {
278                    self.printer.print_ln();
279                    if self.last_badness > 100 {
280                        self.diag_capture_start();
281                        self.printer.print_nl("Underfull");
282                    } else {
283                        self.printer.print_nl("Loose");
284                    }
285                    self.printer.print_str(" \\hbox (badness ");
286                    self.printer.print_int(i64::from(self.last_badness));
287                    Some(())
288                } else {
289                    None
290                }
291            } else {
292                None
293            }
294        } else {
295            let o = tot.shrink_order();
296            let ts = tot.shrink[o as usize];
297            {
298                let b = self.box_mut(r);
299                b.glue_order = o;
300                b.glue_sign = 2;
301                if ts != 0 {
302                    b.glue_set = crate::nodes::glue_ratio(-x, ts);
303                } else {
304                    b.glue_sign = 0;
305                    b.glue_set = 0.0;
306                }
307            }
308            if ts < -x && o == 0 && !first.is_null() {
309                self.last_badness = 1_000_000;
310                self.box_mut(r).glue_set = 1.0;
311                let excess = -x - tot.shrink[0];
312                let hfuzz = self.eqtb.dimen(dp::HFUZZ);
313                if excess > hfuzz || self.eqtb.int(ip::HBADNESS) < 100 {
314                    let ofr = self.eqtb.dimen(dp::OVERFULLRULE);
315                    if ofr > 0 && excess > hfuzz {
316                        let rule = self.nodes.new_rule(ofr, NULL_RULE, NULL_RULE);
317                        if first.is_null() {
318                            self.box_mut(r).head = rule;
319                        } else {
320                            let t = self.nodes.tail_of(first);
321                            self.nodes.link(t, rule);
322                        }
323                    }
324                    self.printer.print_ln();
325                    self.diag_capture_start();
326                    self.printer.print_nl("Overfull \\hbox (");
327                    self.printer.print_scaled(excess);
328                    self.printer.print_str("pt too wide");
329                    Some(())
330                } else {
331                    None
332                }
333            } else if o == 0 && !first.is_null() {
334                self.last_badness = retex_arith::badness(-x, tot.shrink[0]);
335                if self.last_badness > self.eqtb.int(ip::HBADNESS) {
336                    self.printer.print_ln();
337                    self.diag_capture_start();
338                    self.printer.print_nl("Tight \\hbox (badness ");
339                    self.printer.print_int(i64::from(self.last_badness));
340                    Some(())
341                } else {
342                    None
343                }
344            } else {
345                None
346            }
347        };
348        if report.is_some() {
349            self.finish_hbox_diagnostic(r);
350        }
351        r
352    }
353
354    /// The natural width, height and depth of the hlist from `p` up to
355    /// `stop` (exclusive), as `hpack` measures it (LuaTeX's
356    /// `node.dimensions`).
357    pub fn natural_dimensions(&self, mut p: NodeRef, stop: NodeRef) -> (i32, i32, i32) {
358        let (mut w, mut h, mut d) = (0i32, 0i32, 0i32);
359        while !p.is_null() && p != stop {
360            let (pw, ph, pd) = match self.nodes.data(p) {
361                NodeData::Glyph(_) => self.glyph_dimensions(p),
362                NodeData::Box(b) => (b.width, b.height - b.shift, b.depth + b.shift),
363                NodeData::Rule {
364                    width,
365                    height,
366                    depth,
367                    ..
368                } => (*width, *height, *depth),
369                NodeData::Disc { replace, .. } => {
370                    let r = *replace;
371                    self.natural_dimensions(r, NodeRef::NULL)
372                }
373                _ => (self.nodes.width(p), 0, 0),
374            };
375            w += pw;
376            h = h.max(ph);
377            d = d.max(pd);
378            p = self.nodes.next(p);
379        }
380        (w, h, d)
381    }
382
383    /// Width, height and depth of a node in a discretionary text.
384    fn simple_dimensions(&self, p: NodeRef) -> (i32, i32, i32) {
385        match self.nodes.data(p) {
386            NodeData::Glyph(_) => self.glyph_dimensions(p),
387            NodeData::Box(b) => (b.width, b.height - b.shift, b.depth + b.shift),
388            NodeData::Rule {
389                width,
390                height,
391                depth,
392                ..
393            } => (*width, *height, *depth),
394            NodeData::Kern {
395                kern,
396                expansion_factor,
397            } => (*kern + *expansion_factor, 0, 0),
398            _ => (0, 0, 0),
399        }
400    }
401
402    fn box_mut(&mut self, r: NodeRef) -> &mut BoxData {
403        match self.nodes.data_mut(r) {
404            NodeData::Box(b) => b,
405            _ => unreachable!("box_mut on a non-box node"),
406        }
407    }
408
409    /// Prints the location and the box for an over/underfull hbox message.
410    fn finish_hbox_diagnostic(&mut self, r: NodeRef) {
411        if self.ts.output_active {
412            self.printer
413                .print_str(") has occurred while \\output is active");
414        } else {
415            let pbl = self.ts.pack_begin_line;
416            if pbl != 0 {
417                if pbl > 0 {
418                    self.printer.print_str(") in paragraph at lines ");
419                } else {
420                    self.printer.print_str(") in alignment at lines ");
421                }
422                self.printer.print_int(i64::from(pbl.abs()));
423                self.printer.print_str("--");
424            } else {
425                self.printer.print_str(") detected at line ");
426            }
427            self.printer.print_int(i64::from(self.input.line()));
428        }
429        let at = (self.ts.pack_begin_line != 0).then(|| self.ts.pack_begin_line.unsigned_abs());
430        self.diag_capture_warning(at);
431        if self.diagnostics.is_some() {
432            let facts = self.hbox_facts(r);
433            if let Some(d) = self.diagnostics.as_mut().and_then(|l| l.last_mut()) {
434                d.facts = facts;
435            }
436        }
437        self.printer.print_ln();
438        self.ts.font_in_short_display = 0;
439        let l = self.nodes.list_ptr(r);
440        self.short_display(l);
441        self.printer.print_ln();
442        self.begin_diagnostic();
443        self.show_box(r);
444        self.end_diagnostic(true);
445    }
446
447    /// Packs a vlist with unlimited depth (`vpack`).
448    pub fn vpack(&mut self, p: NodeRef, spec: PackSpec) -> NodeRef {
449        self.vpackage(p, spec, retex_arith::MAX_DIMEN)
450    }
451
452    /// Packs the vlist `p` into a vbox with maximum depth `l`
453    /// (`vpackage`).
454    pub fn vpackage(&mut self, p: NodeRef, spec: PackSpec, l: i32) -> NodeRef {
455        self.last_badness = 0;
456        let r = self.new_null_box_node(false);
457        self.take_pack_dir(r);
458        let (mut w, mut d, mut x) = (0i32, 0i32, 0i32);
459        let mut tot = Totals::default();
460        let mut q = p;
461        while !q.is_null() {
462            match self.nodes.data(q) {
463                NodeData::Box(b) => {
464                    x += d + b.height;
465                    d = b.depth;
466                    if b.width + b.shift > w {
467                        w = b.width + b.shift;
468                    }
469                }
470                NodeData::Unset { b, .. } => {
471                    x += d + b.height;
472                    d = b.depth;
473                    if b.width > w {
474                        w = b.width;
475                    }
476                }
477                NodeData::Rule {
478                    width,
479                    height,
480                    depth,
481                    ..
482                } => {
483                    x += d + *height;
484                    d = *depth;
485                    if *width > w {
486                        w = *width;
487                    }
488                }
489                NodeData::Glue { spec, leader } => {
490                    x += d;
491                    d = 0;
492                    x += spec.width;
493                    tot.add(spec);
494                    let leader = *leader;
495                    if self.nodes.subtype(q) >= glue_sub::A_LEADERS && !leader.is_null() {
496                        let lw = self.nodes.width(leader);
497                        if lw > w {
498                            w = lw;
499                        }
500                    }
501                }
502                NodeData::Kern { kern, .. } => {
503                    x += d + *kern;
504                    d = 0;
505                }
506                _ => {}
507            }
508            q = self.nodes.next(q);
509        }
510        {
511            let b = self.box_mut(r);
512            b.width = w;
513            b.head = p;
514        }
515        if d > l {
516            x += d - l;
517            self.box_mut(r).depth = l;
518        } else {
519            self.box_mut(r).depth = d;
520        }
521        let h = match spec {
522            PackSpec::Exactly(h) => h,
523            PackSpec::Additional(h) => x + h,
524        };
525        self.box_mut(r).height = h;
526        self.ts.last_totals = (tot.stretch, tot.shrink);
527        let x = h - x;
528        let report = if x == 0 {
529            false
530        } else if x > 0 {
531            let o = tot.stretch_order();
532            let ts = tot.stretch[o as usize];
533            {
534                let b = self.box_mut(r);
535                b.glue_order = o;
536                b.glue_sign = 1;
537                if ts != 0 {
538                    b.glue_set = crate::nodes::glue_ratio(x, ts);
539                } else {
540                    b.glue_sign = 0;
541                    b.glue_set = 0.0;
542                }
543            }
544            if o == 0 && !p.is_null() {
545                self.last_badness = retex_arith::badness(x, tot.stretch[0]);
546                if self.last_badness > self.eqtb.int(ip::VBADNESS) {
547                    self.printer.print_ln();
548                    if self.last_badness > 100 {
549                        self.diag_capture_start();
550                        self.printer.print_nl("Underfull");
551                    } else {
552                        self.printer.print_nl("Loose");
553                    }
554                    self.printer.print_str(" \\vbox (badness ");
555                    self.printer.print_int(i64::from(self.last_badness));
556                    true
557                } else {
558                    false
559                }
560            } else {
561                false
562            }
563        } else {
564            let o = tot.shrink_order();
565            let ts = tot.shrink[o as usize];
566            {
567                let b = self.box_mut(r);
568                b.glue_order = o;
569                b.glue_sign = 2;
570                if ts != 0 {
571                    b.glue_set = crate::nodes::glue_ratio(-x, ts);
572                } else {
573                    b.glue_sign = 0;
574                    b.glue_set = 0.0;
575                }
576            }
577            if ts < -x && o == 0 && !p.is_null() {
578                self.last_badness = 1_000_000;
579                self.box_mut(r).glue_set = 1.0;
580                let excess = -x - tot.shrink[0];
581                if excess > self.eqtb.dimen(dp::VFUZZ) || self.eqtb.int(ip::VBADNESS) < 100 {
582                    self.printer.print_ln();
583                    self.diag_capture_start();
584                    self.printer.print_nl("Overfull \\vbox (");
585                    self.printer.print_scaled(excess);
586                    self.printer.print_str("pt too high");
587                    true
588                } else {
589                    false
590                }
591            } else if o == 0 && !p.is_null() {
592                self.last_badness = retex_arith::badness(-x, tot.shrink[0]);
593                if self.last_badness > self.eqtb.int(ip::VBADNESS) {
594                    self.printer.print_ln();
595                    self.diag_capture_start();
596                    self.printer.print_nl("Tight \\vbox (badness ");
597                    self.printer.print_int(i64::from(self.last_badness));
598                    true
599                } else {
600                    false
601                }
602            } else {
603                false
604            }
605        };
606        if report {
607            if self.ts.output_active {
608                self.printer
609                    .print_str(") has occurred while \\output is active");
610            } else {
611                let pbl = self.ts.pack_begin_line;
612                if pbl != 0 {
613                    self.printer.print_str(") in alignment at lines ");
614                    self.printer.print_int(i64::from(pbl.abs()));
615                    self.printer.print_str("--");
616                } else {
617                    self.printer.print_str(") detected at line ");
618                }
619                self.printer.print_int(i64::from(self.input.line()));
620            }
621            let at = (self.ts.pack_begin_line != 0).then(|| self.ts.pack_begin_line.unsigned_abs());
622            self.diag_capture_warning(at);
623            // An underfull page: explain why (see `pagenote`).
624            if self.ts.output_active
625                && self.last_badness > 100
626                && self.last_badness < 1_000_000
627                && let Some((message, notes, help)) = self.underfull_page_note(self.last_badness)
628                && let Some(d) = self.diagnostics.as_mut().and_then(|l| l.last_mut())
629                && d.message.starts_with("Underfull \\vbox")
630            {
631                d.message = message;
632                d.notes = notes;
633                d.help = help;
634            }
635            if !self.ts.output_active {
636                self.printer.print_ln();
637            }
638            self.begin_diagnostic();
639            self.show_box(r);
640            self.end_diagnostic(true);
641        }
642        r
643    }
644}
645
646/// The running dimension of rules (`null_flag`).
647const NULL_RULE: i32 = crate::typeset::NULL_FLAG;
retex_engine/pack.rs

retex_engine/
pack.rs
