boxworks_knuthplass/
lib.rs

1//! # Knuth-Plass line breaking algorithm.
2
3use std::{collections::VecDeque, ops::AddAssign};
4
5use boxworks::ds::{self, KernKind};
6use common::{GlueOrder, Scaled};
7pub mod debug;
8
9pub struct LineBreaker<'a> {
10    pub params: &'a Params,
11    pub line_widths: &'a [Scaled],
12    pub line_indents: &'a [Scaled],
13    pub debug_logger: Option<&'a mut dyn debug::Logger>,
14    pub hyphenator: &'a dyn boxworks::Hyphenator,
15}
16
17#[derive(Debug)]
18pub struct Params {
19    pub adj_demerits: i32,
20    pub broken_penalty: i32,
21    pub double_hyphen_demerits: i32,
22    pub club_penalty: i32,
23    pub ex_hyphen_penalty: i32,
24    pub final_hyphen_demerits: i32,
25    // TODO: this is actually different for each invocation. Make it so!
26    pub final_widow_penalty: i32,
27    pub hyphen_penalty: i32,
28    pub inter_line_penalty: i32,
29    pub left_skip: common::Glue,
30    pub line_penalty: i32,
31    pub looseness: i32,
32    pub par_fill_skip: common::Glue,
33    pub pre_tolerance: i32,
34    pub right_skip: common::Glue,
35    pub tolerance: i32,
36}
37
38impl Default for Params {
39    fn default() -> Self {
40        Self::plain_tex_defaults()
41    }
42}
43
44impl Params {
45    pub fn plain_tex_defaults() -> Self {
46        Self {
47            adj_demerits: 10000,
48            broken_penalty: 100,
49            double_hyphen_demerits: 10000,
50            club_penalty: 150,
51            ex_hyphen_penalty: 50,
52            final_hyphen_demerits: 5000,
53            final_widow_penalty: 150,
54            hyphen_penalty: 50,
55            inter_line_penalty: 0,
56            left_skip: common::Glue::ZERO,
57            line_penalty: 10,
58            looseness: 0,
59            par_fill_skip: common::Glue {
60                width: Scaled::ZERO,
61                stretch: Scaled::ONE,
62                stretch_order: common::GlueOrder::Fil,
63                shrink: Scaled::ZERO,
64                shrink_order: Default::default(),
65            },
66            pre_tolerance: 100,
67            right_skip: common::Glue::ZERO,
68            tolerance: 200,
69        }
70    }
71
72    /// Output the parameters in TeX format.
73    pub fn tex(&self) -> String {
74        let Params {
75            adj_demerits,
76            broken_penalty,
77            double_hyphen_demerits,
78            club_penalty,
79            ex_hyphen_penalty,
80            final_hyphen_demerits,
81            final_widow_penalty: _,
82            hyphen_penalty,
83            inter_line_penalty,
84            left_skip,
85            line_penalty,
86            looseness,
87            par_fill_skip,
88            pre_tolerance,
89            right_skip,
90            tolerance,
91        } = self;
92        format!(
93            r"
94            \adjdemerits={adj_demerits}
95            \brokenpenalty={broken_penalty}
96            \clubpenalty={club_penalty}
97            \doublehyphendemerits={double_hyphen_demerits}
98            \exhyphenpenalty={ex_hyphen_penalty}
99            \finalhyphendemerits={final_hyphen_demerits}
100            \hyphenpenalty={hyphen_penalty}
101            \interlinepenalty={inter_line_penalty}
102            \leftskip={left_skip}
103            \linepenalty={line_penalty}
104            \looseness={looseness}
105            \parfillskip={par_fill_skip}
106            \pretolerance={pre_tolerance}
107            \rightskip={right_skip}
108            \tolerance={tolerance}
109        "
110        )
111    }
112}
113
114#[derive(Copy, Clone, Default, PartialEq, Eq, PartialOrd, Ord, Debug)]
115struct Scaled64(i64);
116
117impl std::ops::Add for Scaled64 {
118    type Output = Self;
119
120    fn add(self, rhs: Self) -> Self::Output {
121        Self(self.0 + rhs.0)
122    }
123}
124
125impl std::ops::Sub for Scaled64 {
126    type Output = Self;
127
128    fn sub(self, rhs: Self) -> Self::Output {
129        Self(self.0 - rhs.0)
130    }
131}
132
133impl std::ops::Neg for Scaled64 {
134    type Output = Self;
135
136    fn neg(self) -> Self::Output {
137        Self(-self.0)
138    }
139}
140
141impl AddAssign<Scaled> for Scaled64 {
142    fn add_assign(&mut self, rhs: Scaled) {
143        self.0 += rhs.0 as i64
144    }
145}
146
147impl std::ops::SubAssign<Scaled> for Scaled64 {
148    fn sub_assign(&mut self, rhs: Scaled) {
149        self.0 -= rhs.0 as i64
150    }
151}
152
153#[derive(Debug, Clone, Default, PartialEq, Eq)]
154struct Diffs {
155    width: Scaled64,
156    shrinkability: Scaled64,
157    stretchabilities: [Scaled64; 4],
158}
159
160impl Diffs {
161    fn update_from_glue(&mut self, glue: &common::Glue) {
162        self.width += glue.width;
163        // TODO: emit warning if the shrink order is not normal like in TeX.2021.825
164        self.shrinkability += glue.shrink;
165        self.stretchabilities[glue.stretch_order as usize] += glue.stretch;
166    }
167    fn infinitely_stretchable(&self) -> bool {
168        self.stretchabilities[GlueOrder::Fil as usize].0 != 0
169            || self.stretchabilities[GlueOrder::Fill as usize].0 != 0
170            || self.stretchabilities[GlueOrder::Filll as usize].0 != 0
171    }
172    fn finite_stretchability(&self) -> Scaled64 {
173        self.stretchabilities[GlueOrder::Normal as usize]
174    }
175}
176
177// TeX.2021.819
178#[derive(Clone, Debug, PartialEq, Eq)]
179struct ActiveNode {
180    // Deltas between this active node and the preceding element in
181    // the list of active nodes.
182    diffs: Diffs,
183    fitness_class: FitnessClass,
184    hyphenated: bool,
185    line_number: usize,
186    line_class: LineClass,
187    // Index of the passive node corresponding to this active node.
188    node_index: usize,
189    total_demerits: i32,
190}
191
192/// TeX.2021.817
193#[derive(Clone, Copy, Debug, PartialEq, Eq)]
194enum FitnessClass {
195    VeryLoose = 0,
196    Loose = 1,
197    Decent = 2,
198    Tight = 3,
199}
200
201struct PassiveNode {
202    // Index of the element in the horizontal list
203    elem: usize,
204    // Index of the passive node corresponding to the previous break
205    // in the optimal path to this node.
206    previous_node_index: usize,
207}
208
209#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
210enum LineClass {
211    Beginning,
212    Numbered(usize),
213    End,
214}
215
216impl<'a> boxworks::LineBreaker for LineBreaker<'a> {
217    fn break_line<F: boxworks::FontRepo>(
218        mut self,
219        font_repo: &F,
220        v_list: &mut Vec<ds::Vertical>,
221        h_list: &mut Vec<ds::Horizontal>,
222    ) {
223        // This function is analagous to TeX.2021.815.
224
225        // TeX.2021.816
226        if matches!(h_list.last(), Some(ds::Horizontal::Glue(_))) {
227            h_list.pop();
228        }
229        h_list.push(ds::Horizontal::Penalty(ds::Penalty::INFINITE));
230        h_list.push(ds::Horizontal::Glue(ds::Glue {
231            kind: ds::GlueKind::Normal,
232            value: self.params.par_fill_skip,
233        }));
234
235        let break_points = self.break_line_all_attempts(font_repo, self.hyphenator, v_list, h_list);
236        println!("{break_points:?}");
237        self.post_line_break(font_repo, v_list, h_list, &break_points);
238    }
239}
240
241impl<'a> LineBreaker<'a> {
242    fn post_line_break<F: boxworks::FontRepo>(
243        &self,
244        font_repo: &F,
245        v_list: &mut Vec<ds::Vertical>,
246        h_list: &[ds::Horizontal],
247        break_points: &[usize],
248    ) {
249        let mut start_of_line = 0_usize;
250        let mut disc_post_break_nodes: Option<Vec<ds::DiscretionaryElem>> = None;
251        for (line_index, break_point) in break_points.iter().enumerate() {
252            let mut inner_list: Vec<ds::Horizontal> = vec![];
253
254            // TeX.2021.887
255            if !self.params.left_skip.is_zero() {
256                inner_list.push(
257                    ds::Glue {
258                        value: self.params.left_skip,
259                        kind: ds::GlueKind::Normal,
260                    }
261                    .into(),
262                );
263            }
264
265            // TeX.2021.884
266            if let Some(disc_nodes) = disc_post_break_nodes.take() {
267                for disc_node in disc_nodes {
268                    inner_list.push(disc_node.into());
269                }
270            }
271
272            inner_list.extend_from_slice(&h_list[start_of_line..*break_point]);
273            start_of_line = *break_point + 1;
274
275            // TeX.2021.881
276            // This is the check that `q != null` in Knuth's TeX.
277            // This logic does not run for the final breakpoint.
278            if let Some(break_point_node) = h_list.get(*break_point).cloned() {
279                use ds::Horizontal::*;
280                match break_point_node {
281                    Discretionary(discretionary) => {
282                        // TeX.2021.882
283                        // The empty discretionary survives in the list, funnily enough.
284                        inner_list.push(Discretionary(Default::default()));
285                        for pre_break_node in discretionary.pre_break {
286                            inner_list.push(pre_break_node.into());
287                        }
288                        disc_post_break_nodes = Some(discretionary.post_break);
289                        start_of_line += discretionary.replace_count as usize;
290                    }
291                    Math(math) => {
292                        // TODO: set the width of Math to zero
293                        inner_list.push(math.into());
294                    }
295                    Glue(_) => {
296                        // Do nothing. In TeX there is an "optimization" in which the glue is
297                        // modified to be \rightskip, but we don't do this. Instead it is inserted
298                        // below.
299                    }
300                    Kern(mut kern) => {
301                        kern.width = Scaled::ZERO;
302                        inner_list.push(kern.into());
303                    }
304                    Penalty(penalty) => {
305                        // Do nothing.
306                        inner_list.push(penalty.into());
307                    }
308                    _ => {
309                        unreachable!("node cannot appear as a breakpoint: {break_point_node:?}");
310                    }
311                }
312            }
313
314            // TeX.2021.886
315            // Unlike \leftskip, there is no check if the glue here is zero.
316            inner_list.push(
317                ds::Glue {
318                    value: self.params.right_skip,
319                    kind: ds::GlueKind::Normal,
320                }
321                .into(),
322            );
323
324            // TeX.2021.889
325            let width = self
326                .line_widths
327                .get(line_index)
328                .unwrap_or(self.line_widths.last().expect("non-empty line widths"));
329            let indent = self
330                .line_indents
331                .get(line_index)
332                .copied()
333                .unwrap_or(self.line_indents.last().copied().unwrap_or(Scaled::ZERO));
334            let h_box = {
335                let mut b = ds::HBox::pack(font_repo, inner_list, ds::PackWidth::Exact(*width));
336                b.shift_amount = indent;
337                b
338            };
339
340            // TeX.2021.888 and TeX.2021.679
341            if !v_list.is_empty() {
342                // TODO: make \baselineskip configurable
343                // TODO: implement `\lineskiplimit` `\lineskip`.
344                let mut baseline_skip = common::Glue {
345                    width: common::Scaled::ONE * 12,
346                    ..Default::default()
347                };
348                baseline_skip.width -= h_box.height;
349                let mut j = v_list.len() - 1;
350                // TODO: this is probably way too wrong. And shouldn't be managed
351                // here: probably the v list should carry last_depth, like Knuth
352                // does.
353                let last_depth = loop {
354                    let elem = &v_list[j];
355                    use ds::Vertical::*;
356                    match elem {
357                        HBox(hbox) => break hbox.depth,
358                        VBox(vbox) => break vbox.depth,
359                        _ => {}
360                    };
361                    j = match j.checked_sub(1) {
362                        None => break common::Scaled::ZERO,
363                        Some(j) => j,
364                    };
365                };
366                baseline_skip.width -= last_depth;
367                v_list.push(
368                    ds::Glue {
369                        value: baseline_skip,
370                        kind: Default::default(),
371                    }
372                    .into(),
373                );
374            }
375            v_list.push(h_box.into());
376
377            // TeX.2021.890
378            // If this is not the last line, we consider penalties.
379            if line_index + 1 != break_points.len() {
380                let mut p = self.params.inter_line_penalty;
381                if line_index == 0 {
382                    p += self.params.club_penalty;
383                }
384                if line_index + 2 == break_points.len() {
385                    p += self.params.final_widow_penalty;
386                }
387                if disc_post_break_nodes.is_some() {
388                    p += self.params.broken_penalty;
389                }
390                if p != 0 {
391                    v_list.push(ds::Penalty(p).into());
392                }
393            }
394        }
395    }
396    pub fn break_line_all_attempts<F: boxworks::FontRepo>(
397        &mut self,
398        font_repo: &F,
399        hyphenator: &dyn boxworks::Hyphenator,
400        _v_list: &mut Vec<ds::Vertical>,
401        h_list: &mut Vec<ds::Horizontal>,
402    ) -> Vec<usize> {
403        // We manually unroll the "loop" in TeX.2021.863.
404        if let Some(debug_logger) = self.debug_logger.as_deref_mut() {
405            debug_logger.log_attempt(1);
406        }
407        if let Some(v) =
408            self.break_line_single_attempt(h_list, font_repo, self.params.pre_tolerance)
409        {
410            return v;
411        }
412        if let Some(debug_logger) = self.debug_logger.as_deref_mut() {
413            debug_logger.log_attempt(2);
414        }
415        hyphenator.hyphenate(h_list);
416        if let Some(v) = self.break_line_single_attempt(h_list, font_repo, self.params.tolerance) {
417            return v;
418        }
419        panic!("need emergency attempt");
420    }
421
422    pub fn break_line_single_attempt<F: boxworks::FontRepo>(
423        &mut self,
424        list: &[ds::Horizontal],
425        font_repo: &F,
426        tolerance: i32,
427    ) -> Option<Vec<usize>> {
428        let mut auto_breaking = true;
429        let mut passive_nodes = vec![PassiveNode {
430            elem: 0,
431            previous_node_index: 0,
432        }];
433
434        let mut active_nodes = VecDeque::<ActiveNode>::from([
435            // TeX.2021.864
436            ActiveNode {
437                diffs: {
438                    // TeX.2021.827
439                    let mut d: Diffs = Default::default();
440                    d.update_from_glue(&self.params.left_skip);
441                    d.update_from_glue(&self.params.right_skip);
442                    d
443                },
444                fitness_class: FitnessClass::Decent,
445                hyphenated: false,
446                line_number: 0,
447                line_class: LineClass::Beginning,
448                node_index: 0,
449                total_demerits: 0,
450            },
451        ]);
452        let mut diffs: Diffs = Default::default();
453        // This is the loop in TeX.2021.863
454        for i in 0..=list.len() {
455            let elem = list.get(i);
456            use ds::Horizontal::*;
457            let mut disc_width = Scaled::ZERO;
458            // This switch is TeX.2021.866. In TeX, Knuth invokes `try_break` inline
459            // at the relevant parts of the switch. We instead return the two arguments
460            // to `try_break` from the match, and the rest of this function implements
461            // the `try_break`. Switch cases for which `try_break` should not be invoked
462            // contain a continue statement.
463            let (mut penalty, hyphenated) = match elem {
464                None => {
465                    // This corresponds to the try_break call in TeX.202.873.
466                    // I'm guessing the last break is considered hyphenated so as to penalize
467                    // the second-to-last line being hyphenated. A hyphen doesn't look nice
468                    // in the bottom right of the paragraph.
469                    (EJECT_PENALTY, true)
470                }
471                Some(elem) => match elem {
472                    Char(ds::Char { char, font }) | Ligature(ds::Ligature { char, font, .. }) => {
473                        // TeX.2021.867 has an optimization in which subsequent chars are read
474                        // here. I'm not convinced it's worth it.
475                        diffs.width += font_repo.width(*char, *font).unwrap_or(Scaled::ZERO);
476                        continue;
477                    }
478                    HBox(ds::HBox { width, .. })
479                    | VBox(ds::VBox { width, .. })
480                    | Rule(ds::Rule { width, .. }) => {
481                        diffs.width += *width;
482                        continue;
483                    }
484                    Mark(_) | Insertion(_) | Adjust(_) => {
485                        // do nothing
486                        continue;
487                    }
488                    Discretionary(discretionary) => {
489                        // TeX.2021.869
490                        disc_width = discretionary
491                            .pre_break
492                            .iter()
493                            .map(|e| e.width(font_repo))
494                            .sum();
495                        (
496                            if discretionary.pre_break.is_empty() {
497                                self.params.ex_hyphen_penalty
498                            } else {
499                                self.params.hyphen_penalty
500                            },
501                            true,
502                        )
503                        // Knuth includes the following optimization, which we omit.
504                        // The discretionary node specifies that the following r
505                        // elements of the horizontal list should be removed if
506                        // a break occurs here. These elements must be one of the 6
507                        // types allowed in discretionary lists. None of these elements
508                        // can themselves be breakpoints. Thus, Knuth skips ahead
509                        // by r elements in the horizontal list just updating the widths.
510                        // It's unclear if this optimization is worth implementing...
511                    }
512                    Whatsit(_whatsit) => todo!(),
513                    Math(math) => {
514                        auto_breaking = *math == ds::Math::After;
515                        if auto_breaking && matches!(list.get(i + 1), Some(Glue(_))) {
516                            // List of allowable line breaks in TeXBook chapter 14 p96:
517                            // (c) at a math-off that is immediately followed by glue.
518                            (0, false)
519                        } else {
520                            continue;
521                        }
522                    }
523                    Glue(glue) => {
524                        // TeX.2021.868
525                        if auto_breaking && i > 0 && list[i - 1].precedes_break() {
526                            // List of allowable line breaks in TeXBook chapter 14 p96:
527                            // (a) at glue, provided that this glue is immediately preceded by
528                            // a non-discardable item, and that it is not part of a math formula
529                            // (i.e., not between math-on and math-off). A break "at glue" occurs
530                            // at the left edge of the glue space.
531                            (0, false)
532                        } else {
533                            diffs.update_from_glue(&glue.value);
534                            continue;
535                        }
536                    }
537                    Kern(kern) => {
538                        if kern.kind == KernKind::Explicit
539                            && auto_breaking
540                            && matches!(list.get(i + 1), Some(Glue(_)))
541                        {
542                            // List of allowable line breaks in TeXBook chapter 14 p96:
543                            // (b) at a kern, provided that this kern is immediately followed by glue,
544                            // and that it is not part of a math formula.
545                            (0, false)
546                        } else {
547                            diffs.width += kern.width;
548                            continue;
549                        }
550                    }
551                    Penalty(penalty) => {
552                        // List of allowable line breaks in TeXBook chapter 14 p96:
553                        // (d) at a penalty (which might have been inserted automatically in a formula).
554                        (penalty.0, false)
555                    }
556                },
557            };
558
559            // TeX.2021.831
560            if penalty >= INFINITE_PENALTY {
561                // TODO: For discretionaty nodes we need to adjust the width here?
562                continue;
563            }
564            if penalty <= EJECT_PENALTY {
565                penalty = EJECT_PENALTY
566            }
567
568            let mut n = active_nodes.len();
569            while n > 0 {
570                let (line_class, mut m) = get_next_line_class(&active_nodes, n);
571                n -= m;
572
573                // TODO: destroy this. Instead just use the line number to calculate the class.
574
575                // The line width is calculated in TeX.2021.850. However in this implementation
576                // of Knuth-Plass, the line width calculator is passed as a parameter.
577                let (next_line_class, line_width) = match line_class {
578                    // todo: if len(self.line_widths) = 1 then we should return End
579                    LineClass::Beginning => {
580                        if self.line_widths.len() == 1 {
581                            (LineClass::End, *self.line_widths.first().unwrap())
582                        } else {
583                            (LineClass::Numbered(0), *self.line_widths.first().unwrap())
584                        }
585                    }
586                    LineClass::Numbered(i) => match self.line_widths.get(i + 1) {
587                        Some(line_width) => {
588                            // if index i+1 is the last element, meaning it has i+2 elements
589                            if self.line_widths.len() == i + 2 {
590                                (LineClass::End, *line_width)
591                            } else {
592                                (LineClass::Numbered(i + 1), *line_width)
593                            }
594                        }
595                        None => (LineClass::End, *self.line_widths.last().unwrap()),
596                    },
597                    LineClass::End => (LineClass::End, *self.line_widths.last().unwrap()),
598                };
599
600                // TeX.2021.833
601                #[derive(Clone, Copy, Debug)]
602                struct Candidate {
603                    total_demerits: i32,
604                    previous_node_index: usize,
605                    line_number: usize,
606                }
607                // TeX.2021.834
608                let mut candidates = [Candidate {
609                    total_demerits: i32::MAX,
610                    previous_node_index: 0,
611                    line_number: 0,
612                }; 4];
613                let mut minimum_demerits = i32::MAX;
614
615                while m > 0 {
616                    m -= 1;
617                    let active_node = active_nodes.pop_front().expect("active nodes to consider");
618                    let ideal_line_width = Scaled64(line_width.0 as i64);
619                    let actual_line_width_no_stretching =
620                        diffs.width - active_node.diffs.width + Scaled64(disc_width.0 as i64);
621                    let line_diffs = Diffs {
622                        width: ideal_line_width - actual_line_width_no_stretching,
623                        shrinkability: diffs.shrinkability - active_node.diffs.shrinkability,
624                        stretchabilities: [
625                            diffs.stretchabilities[0] - active_node.diffs.stretchabilities[0],
626                            diffs.stretchabilities[1] - active_node.diffs.stretchabilities[1],
627                            diffs.stretchabilities[2] - active_node.diffs.stretchabilities[2],
628                            diffs.stretchabilities[3] - active_node.diffs.stretchabilities[3],
629                        ],
630                    };
631
632                    // TeX.2021.851
633                    let shortfall = line_diffs.width;
634                    let (badness, fitness_class) = if shortfall.0 > 0 {
635                        // Stretching the line
636                        // TeX.2021.852
637                        if line_diffs.infinitely_stretchable() {
638                            (0, FitnessClass::Decent)
639                        } else {
640                            let b = badness(shortfall, line_diffs.finite_stretchability());
641                            (
642                                b,
643                                if b <= 12 {
644                                    FitnessClass::Decent
645                                } else if b <= 99 {
646                                    FitnessClass::Loose
647                                } else {
648                                    FitnessClass::VeryLoose
649                                },
650                            )
651                        }
652                    } else {
653                        // Shrinking the line
654                        // TeX.2021.853
655                        if -shortfall > line_diffs.shrinkability {
656                            (INFINITE_BADNESS + 1, FitnessClass::Decent)
657                        } else {
658                            let b = badness(-shortfall, line_diffs.shrinkability);
659                            (
660                                b,
661                                if b <= 12 {
662                                    FitnessClass::Decent
663                                } else {
664                                    FitnessClass::Tight
665                                },
666                            )
667                        }
668                    };
669
670                    // The conidition of the if statement is in TeX.2021.851
671                    let deactivate = if badness > INFINITE_BADNESS || penalty == EJECT_PENALTY {
672                        // TeX.2021.854
673                        // TODO: finish TeX.2021.854 when we implement the final pass.
674                        true
675                    } else {
676                        false
677                    };
678
679                    // Allowable break.
680                    // Add a candidate
681                    if badness <= tolerance {
682                        // TeX.2021.855
683                        let demerits = self.demerits(
684                            badness,
685                            penalty,
686                            active_node.fitness_class,
687                            fitness_class,
688                            active_node.hyphenated && hyphenated,
689                            active_node.hyphenated && elem.is_none(),
690                        );
691                        let total_demerits = demerits + active_node.total_demerits;
692                        // The logging here is implemented in TeX.2021.856
693                        if let Some(debug_logger) = self.debug_logger.as_deref_mut() {
694                            debug_logger.log_feasible_breakpoint(
695                                list,
696                                debug::FeasibleBreakpoint {
697                                    elem_index: i,
698                                    badness,
699                                    penalty,
700                                    demerits,
701                                    previous_node_index: active_node.node_index,
702                                },
703                            );
704                        }
705                        let candidate = &mut candidates[fitness_class as usize];
706                        if total_demerits <= candidate.total_demerits {
707                            // TeX.2021.856
708                            *candidate = Candidate {
709                                total_demerits,
710                                previous_node_index: active_node.node_index,
711                                line_number: active_node.line_number + 1,
712                            };
713                        }
714                        if total_demerits <= minimum_demerits {
715                            minimum_demerits = total_demerits;
716                        }
717                    }
718                    if !deactivate {
719                        active_nodes.push_back(active_node);
720                    }
721                }
722
723                // TeX.2021.835
724                // TODO: if this is the last active node we must also calculated candidates
725                if minimum_demerits < AWFUL_BAD {
726                    // TeX.2021.836
727                    if self.params.adj_demerits.abs() >= AWFUL_BAD - minimum_demerits {
728                        minimum_demerits = AWFUL_BAD - 1;
729                    } else {
730                        minimum_demerits += self.params.adj_demerits.abs();
731                    }
732                    let mut diffs = diffs.clone();
733                    if let Some(elem) = elem {
734                        // TeX.2021.837
735                        match elem {
736                            Discretionary(discretionary) => {
737                                // TeX.2021.840
738                                // TODO: also need to factor in the post_break adjustment.
739                                let mut j = i + 1;
740                                while j < i + 1 + discretionary.replace_count as usize {
741                                    diffs.width += match &list[j] {
742                                        Char(ds::Char { char, font })
743                                        | Ligature(ds::Ligature { char, font, .. }) => {
744                                            font_repo.width(*char, *font).unwrap_or(Scaled::ZERO)
745                                        }
746                                        HBox(ds::HBox { width, .. })
747                                        | VBox(ds::VBox { width, .. })
748                                        | Rule(ds::Rule { width, .. })
749                                        | Kern(ds::Kern { width, .. }) => *width,
750                                        _ => {
751                                            eprintln!(
752                                                "invalid node {:?} in discretionary replacement list",
753                                                &list[j]
754                                            );
755                                            Scaled::ZERO
756                                        }
757                                    };
758                                    j += 1;
759                                }
760                            }
761                            Math(_math) => {
762                                // TODO when math node is fixed in boxworks crate.
763                            }
764                            Glue(glue) => {
765                                diffs.update_from_glue(&glue.value);
766                            }
767                            Kern(kern) => {
768                                if kern.kind == ds::KernKind::Explicit {
769                                    diffs.width -= kern.width;
770                                }
771                            }
772                            _ => {}
773                        }
774                    }
775                    for fitness_class in [
776                        FitnessClass::VeryLoose,
777                        FitnessClass::Loose,
778                        FitnessClass::Decent,
779                        FitnessClass::Tight,
780                    ] {
781                        let candidate = candidates[fitness_class as usize];
782                        if candidate.total_demerits > minimum_demerits {
783                            continue;
784                        }
785                        // TeX.2021.845
786                        let active_node = ActiveNode {
787                            diffs: diffs.clone(),
788                            fitness_class,
789                            hyphenated,
790                            line_number: candidate.line_number,
791                            line_class: next_line_class,
792                            node_index: passive_nodes.len(),
793                            total_demerits: candidate.total_demerits,
794                        };
795
796                        // Logging here is TeX.2021.846
797                        if let Some(debug_logger) = self.debug_logger.as_deref_mut() {
798                            debug_logger.log_new_active_node(debug::NewActiveNode {
799                                node_index: active_node.node_index,
800                                line_number: active_node.line_number,
801                                fitness_class: active_node.fitness_class as u8,
802                                hyphenated: active_node.hyphenated,
803                                total_demerits: active_node.total_demerits,
804                                previous_node_index: candidate.previous_node_index,
805                            });
806                        }
807                        active_nodes.push_back(active_node);
808                        passive_nodes.push(PassiveNode {
809                            elem: i,
810                            previous_node_index: candidate.previous_node_index,
811                        });
812                    }
813                }
814            }
815
816            // At the end we update the widths.
817            let Some(elem) = elem else { break };
818            match elem {
819                Char(_) | HBox(_) | VBox(_) | Rule(_) | Mark(_) | Insertion(_) | Adjust(_)
820                | Ligature(_) => {
821                    // Unreachable because we've already handled these nodes in
822                    // the earlier switch and skipped the rest of the loop.
823                }
824                Discretionary(_) => {
825                    // diffs.width += -disc_width;
826                }
827                Whatsit(_whatsit) => todo!(),
828                Math(_) => {
829                    // Math nodes have no width.
830                }
831                Glue(glue) => {
832                    diffs.update_from_glue(&glue.value);
833                }
834                Kern(kern) => {
835                    diffs.width += kern.width;
836                }
837                Penalty(_) => {
838                    // Penalty nodes have no width.
839                }
840            }
841        }
842
843        // TeX.2021.874
844        // The following line exits early if there are no active nodes and thus no solution.
845        let mut best = active_nodes.front()?;
846        for active_node in &active_nodes {
847            if active_node.total_demerits < best.total_demerits {
848                best = active_node;
849            }
850        }
851        let mut v = vec![];
852        let mut index = best.node_index;
853        while index > 0 {
854            let passive_node = &passive_nodes[index];
855            v.push(passive_node.elem);
856            index = passive_node.previous_node_index;
857        }
858        v.reverse();
859        Some(v)
860    }
861
862    /// TeX.2021.859
863    fn demerits(
864        &self,
865        badness: i32,
866        penalty: i32,
867        previous_fitness_class: FitnessClass,
868        this_fitness_class: FitnessClass,
869        consecutive_hyphens: bool,
870        end_after_hyphen: bool,
871    ) -> i32 {
872        let mut d = self.params.line_penalty + badness;
873        if d.abs() >= 10_000 {
874            d = 10_000;
875        }
876        d = d * d;
877        if penalty > 0 {
878            d += penalty * penalty;
879        } else if penalty > EJECT_PENALTY {
880            d -= penalty * penalty;
881        }
882        if end_after_hyphen {
883            d += self.params.final_hyphen_demerits;
884        } else if consecutive_hyphens {
885            d += self.params.double_hyphen_demerits;
886        }
887        if (previous_fitness_class as isize - this_fitness_class as isize).abs() > 1 {
888            d += self.params.adj_demerits;
889        }
890        d
891    }
892}
893
894// TeX.2021.833
895const AWFUL_BAD: i32 = 0o7_777_777_777;
896const INFINITE_BADNESS: i32 = 10000;
897const INFINITE_PENALTY: i32 = 10000;
898const EJECT_PENALTY: i32 = -10000;
899
900/// TeX.2021.108
901fn badness(shortfall: Scaled64, stretchability: Scaled64) -> i32 {
902    let t = shortfall.0;
903    let s = stretchability.0;
904    if t == 0 {
905        return 0;
906    }
907    if s <= 0 {
908        return INFINITE_BADNESS;
909    }
910    let r = if t <= 7_230_584 {
911        (t * 297) / s
912    } else if s >= 1_663_497 {
913        t / (s / 297)
914    } else {
915        t
916    };
917    if r > 1290 {
918        INFINITE_BADNESS
919    } else {
920        ((r * r * r + 0o400_000) / 0o1_000_000)
921            .try_into()
922            .unwrap_or(INFINITE_BADNESS)
923    }
924}
925
926fn get_next_line_class(active_nodes: &VecDeque<ActiveNode>, max: usize) -> (LineClass, usize) {
927    let line_class = active_nodes
928        .front()
929        .expect("still active nodes to be considered")
930        .line_class;
931    let mut m = 0;
932    for (i, node) in active_nodes.iter().enumerate() {
933        if i >= max {
934            break;
935        }
936        if node.line_class != line_class {
937            break;
938        }
939        m += 1;
940    }
941    (line_class, m)
942}
943
944#[cfg(test)]
945mod tests {
946    use super::*;
947    use boxworks::TextPreprocessor;
948    use boxworks_text as bwt;
949    use pretty_assertions::assert_eq;
950    use std::{cell::RefCell, rc::Rc};
951
952    const WOLF_HALL_5IN_TYPESET: &'static str = "
953        He thinks, if you were born in Putney, you saw the river every day, and imagined it 
954        widening out to the sea. Even if you had never seen the ocean you had a picture of 
955        it in your head from what you had been told by foreign people who sometimes came 
956        upriver. You knew that one day you would go out into a world of marble pavements 
957        and peacocks, of hillsides buzzing with heat, the fragrance of crushed herbs rising 
958        around you as you walked. You planned for what your journeys would bring you: 
959        the touch of warm terracotta, the night sky of another climate, alien flowers, the 
960        stone eyed gaze of other peoples saints. But if you were born in Aslockton, in flat 
961        fields under a wide sky, you might just be able to imagine Cambridge: no farther.
962    ";
963    const WOLF_HALL_5IN_LOG: &'static str = include_str!("../testdata/wolf_hall_5in_log.txt");
964    const WOLF_HALL_5IN_WANT: &'static str = include_str!("../testdata/wolf_hall_5in_want.txt");
965    const WOLF_HALL_3IN_WANT: &'static str = include_str!("../testdata/wolf_hall_3in_want.txt");
966    const WOLF_HALL_3IN_LOG: &'static str = include_str!("../testdata/wolf_hall_3in_log.txt");
967    const TFM_CMR10: &'static [u8] = include_bytes!("../../tfm/corpus/computer-modern/cmr10.tfm");
968
969    #[test]
970    fn wolf_hall_5in() {
971        run_test(
972            TFM_CMR10,
973            WOLF_HALL_5IN_TYPESET,
974            Some(WOLF_HALL_5IN_WANT),
975            Some(WOLF_HALL_5IN_LOG),
976            "5in",
977        );
978    }
979
980    #[test]
981    fn wolf_hall_3in() {
982        run_test(
983            TFM_CMR10,
984            WOLF_HALL_5IN_TYPESET,
985            Some(WOLF_HALL_3IN_WANT),
986            Some(WOLF_HALL_3IN_LOG),
987            "3in",
988        );
989    }
990
991    fn run_test(
992        tfm_bytes: &[u8],
993        input: &str,
994        want: Option<&str>,
995        want_log: Option<&str>,
996        width: &str,
997    ) {
998        let mut tfm_file = tfm::File::deserialize(tfm_bytes).0.unwrap();
999        let lig_kern_program =
1000            tfm::ligkern::CompiledProgram::compile_from_tfm_file(&mut tfm_file).0;
1001        let mut tp: bwt::TextPreprocessorImpl = Default::default();
1002        tp.register_font(0, &tfm_file, lig_kern_program);
1003        tp.activate_font(0);
1004        let mut list = vec![];
1005        for word in input.split_ascii_whitespace() {
1006            tp.add_word(word.trim_matches(' '), &mut list);
1007            tp.add_space(&mut list);
1008        }
1009
1010        let mut font_repo: bwt::TfmFontRepo = Default::default();
1011        font_repo.register_font(0, tfm_file);
1012        let width = common::Scaled::parse_from_string(width).unwrap();
1013        let params = Params::plain_tex_defaults();
1014
1015        let log: Rc<RefCell<String>> = Default::default();
1016        let mut logger = debug::TexLogger::new(log.clone());
1017
1018        let hyphenator = boxworks_hyphenate::Hyphenator::plain_tex_en_us();
1019
1020        let line_breaker = super::LineBreaker {
1021            params: &params,
1022            line_widths: &[width],
1023            line_indents: &[],
1024            debug_logger: Some(&mut logger),
1025            hyphenator: &hyphenator,
1026        };
1027        let mut v_list = vec![];
1028        use boxworks::LineBreaker;
1029        line_breaker.break_line(&font_repo, &mut v_list, &mut list);
1030
1031        let log = log.take();
1032        if let Some(want_log) = want_log {
1033            assert_eq!(normalize(want_log), normalize(&log));
1034        }
1035
1036        let v_box = ds::VBox {
1037            list: v_list,
1038            ..Default::default()
1039        };
1040        if let Some(want) = want {
1041            boxworks_testing::assert_box_eq!(want, v_box);
1042        }
1043    }
1044
1045    fn normalize(s: &str) -> String {
1046        let v: Vec<&str> = s
1047            .split('\n')
1048            .map(|l| l.trim())
1049            .map(|l| l.strip_prefix(r"\customFont ").unwrap_or(l))
1050            .filter(|l| !l.is_empty())
1051            .collect();
1052        v.join("\n")
1053    }
1054}
boxworks_knuthplass/lib.rs

boxworks_knuthplass/
lib.rs
