texrs 0.6.8

A TeX engine: Knuth's mouth and expander, lowered for a bytecode VM
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
//! Breaking a paragraph the way `tex.web` §813 does: by minimising the total
//! demerits of the WHOLE paragraph, with Liang hyphenation to widen the set of
//! places a line may end.
//!
//! First fit -- fill until the next word will not go on -- decides each line
//! without looking at the one after it, so one long word early in a paragraph
//! leaves a gap that every later line pays for. TeX considers every feasible
//! set of breakpoints at once, prices each line by how far its glue is from its
//! natural width (§108's `badness`), and picks the cheapest set (§859's
//! `demerits`). Hyphenation (§891) is the second pass: when no set of
//! breakpoints between words is good enough, words themselves may be split.
//!
//! WHY THIS CAN BE USED AT ALL. A breaker that prices a line over glue decides
//! that some lines should be SHRUNK, and an earlier attempt at this was
//! reverted because the renderer could only draw a run at its natural width, so
//! every shrunk line was drawn out past the measure. `pdf::Page::text_set` now
//! sets a run to a width with PDF's `Tw`, and `typeset::to_pdf` sets every full
//! line to the measure, so the answer this module returns is one the page can
//! honour. The DVI path breaks through here too, and sets each line to the
//! width `hpack` gives it.
//!
//! WHAT IS NOT TeX. `\tolerance`, `\pretolerance`, `\linepenalty`, the two
//! hyphen penalties and the three demerit weights are [`Params`], read from
//! the document per paragraph as §816 reads them -- the lowerer writes the
//! values in force at each paragraph end into the text
//! (`typeset::BREAK_PARAMS`) -- and one a document never assigns keeps
//! plain.tex's value, because texrs loads no format. The interword glue stretches
//! and shrinks by cmr10's own fractions of the space rather than by each
//! embedded face's `\fontdimen3` and `\fontdimen4`, which a PDF font file does
//! not state. And TeX's final pass drops the demerits of a break it has no
//! alternative to (§855 `artificial_demerits`), which it can do because it
//! knows its active list is about to empty; a dynamic program has no such
//! moment, so an overfull line is priced above every paragraph of merely
//! dreadful ones instead (`OVERFULL_DEMERITS`). The outcome is TeX's: an
//! overfull line only where there is no other, and an underfull one preferred
//! to it, which is why tex reports `Underfull \hbox` far more often than
//! `Overfull`.

use std::sync::OnceLock;

/// What may happen after one piece of a paragraph.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum After {
    /// An interword space of this width. Breaking here is free and the space
    /// is discarded.
    Glue(f64),
    /// A hyphenation point inside a word: breaking here sets a hyphen of this
    /// width at the end of the line and costs `\hyphenpenalty`.
    Discretionary(f64),
    /// A break after a hyphen the AUTHOR wrote. The hyphen is already in the
    /// text, so nothing is added; it costs `\exhyphenpenalty` (§869).
    Explicit,
    /// The pieces run together with no break between them and no space.
    Nothing,
}

/// One unbreakable chunk of a paragraph, already measured.
#[derive(Clone, Debug)]
pub struct Piece {
    /// The text as it will be set, markers and all.
    pub text: String,
    /// What that text measures in the face it is set in.
    pub width: f64,
    pub after: After,
}

/// The eight `tex.web` §236 parameters the breaker reads.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Params {
    /// `\pretolerance`: the first pass's badness limit; negative skips it.
    pub pretolerance: f64,
    /// `\tolerance`: the second pass's, which offers the hyphens.
    pub tolerance: f64,
    /// `\linepenalty`: what every line costs before its badness.
    pub line_penalty: f64,
    /// `\hyphenpenalty`, `\exhyphenpenalty`: what breaking a word costs.
    pub hyphen_penalty: f64,
    pub ex_hyphen_penalty: f64,
    /// `\adjdemerits`: charged when two consecutive lines are more than one
    /// fitness class apart -- a tight line under a very loose one.
    pub adj_demerits: f64,
    /// `\doublehyphendemerits`, `\finalhyphendemerits`: charged for two
    /// hyphens in a row, and for a hyphen on the second-to-last line.
    pub double_hyphen_demerits: f64,
    pub final_hyphen_demerits: f64,
}

impl Default for Params {
    /// plain.tex's values, which latex.ltx sets identically.
    fn default() -> Self {
        Self {
            pretolerance: 100.0,
            tolerance: 200.0,
            line_penalty: 10.0,
            hyphen_penalty: 50.0,
            ex_hyphen_penalty: 50.0,
            adj_demerits: 10000.0,
            double_hyphen_demerits: 10000.0,
            final_hyphen_demerits: 5000.0,
        }
    }
}

impl Params {
    /// The parameters as they stand in the engine, and plain.tex's for any the
    /// document never assigned: texrs loads no format, and
    /// INITEX's own values (`\tolerance=10000`, `\pretolerance=0`,
    /// `\linepenalty=0`) are not what a document is set with.
    pub fn from_intpars(p: &crate::intpar::IntPars) -> Self {
        let d = Self::default();
        let read = |name: &str, fallback: f64| {
            crate::intpar::index(name)
                .and_then(|i| p.assigned(i))
                .map_or(fallback, |v| v as f64)
        };
        Self {
            pretolerance: read("pretolerance", d.pretolerance),
            tolerance: read("tolerance", d.tolerance),
            line_penalty: read("linepenalty", d.line_penalty),
            hyphen_penalty: read("hyphenpenalty", d.hyphen_penalty),
            ex_hyphen_penalty: read("exhyphenpenalty", d.ex_hyphen_penalty),
            adj_demerits: read("adjdemerits", d.adj_demerits),
            double_hyphen_demerits: read("doublehyphendemerits", d.double_hyphen_demerits),
            final_hyphen_demerits: read("finalhyphendemerits", d.final_hyphen_demerits),
        }
    }
}
/// `inf_bad` (§108): the badness of a line that cannot be set at all.
const INF_BAD: f64 = 10000.0;
/// What an OVERFULL line costs, which is more than any paragraph of merely bad
/// ones: §859 caps a line's demerits at 1e8 and no paragraph runs to ten
/// thousand lines, so this floor cannot be reached by adding ordinary lines up.
const OVERFULL_DEMERITS: f64 = 1e12;
/// `inf_penalty` (§157): a penalty this large forbids its break.
const INF_PENALTY: f64 = 10000.0;
/// `eject_penalty` (§157): the forced break at the end of the paragraph.
const EJECT_PENALTY: f64 = -10000.0;
/// cmr10's interword glue is `3.33333pt plus 1.66666pt minus 1.11111pt`
/// (`\fontdimen2..4`), so it stretches by half the space and shrinks by a
/// third of it. A PDF font file states no such thing, so these fractions stand
/// in for every face.
const STRETCH_FRACTION: f64 = 0.5;
const SHRINK_FRACTION: f64 = 1.0 / 3.0;
/// Widths are in points and come out of a font's own table; a line that lands
/// on the measure to within this is on it.
const EPS: f64 = 1e-6;

/// TeX's four fitness classes (§817), in its own numbering.
const VERY_LOOSE: usize = 0;
const LOOSE: usize = 1;
const DECENT: usize = 2;
const TIGHT: usize = 3;

/// §108: how bad it is to stretch or shrink `t` points of glue that has `s`
/// points to give.
///
/// This was `100*(t/s)^3` rounded, which is what §108 SAYS badness is and not
/// what §108 DOES: "all implementations of TeX should use precisely this
/// method", and the method is integer arithmetic on scaled points whose
/// constant is $297^3/2^{18} = 99.94$ rather than 100, with everything above
/// 8189 jumping straight to `inf_bad`. The gap is a couple of parts in ten
/// thousand and it lands exactly where badness is read -- §817's fitness
/// classes are decided by `badness<=12` and `badness>99`. So the port in
/// `crate::pack` is called here, with the widths converted to the scaled
/// points TeX holds them in.
fn badness(t: f64, s: f64) -> f64 {
    if t <= 0.0 {
        return 0.0;
    }
    if s <= 0.0 {
        return INF_BAD;
    }
    let sp = |x: f64| (x * crate::dimen::UNITY as f64).round() as i64;
    crate::pack::badness(sp(t), sp(s)) as f64
}

/// §817: which of the four classes a line of this badness falls in.
fn fitness(bad: f64, stretching: bool) -> usize {
    if bad <= 12.0 {
        return DECENT;
    }
    match stretching {
        false => TIGHT,
        true if bad > 99.0 => VERY_LOOSE,
        true => LOOSE,
    }
}

/// What one candidate line comes to: its badness, whether it is being
/// stretched, and whether it can be set at all.
///
/// `fil` is the last line of the paragraph, which TeX ends with
/// `\parfillskip = 0pt plus 1fil` -- infinitely stretchable, so a short last
/// line is never a bad one.
fn assess(natural: f64, stretch: f64, shrink: f64, measure: f64, fil: bool) -> (f64, bool, bool) {
    let short = measure - natural;
    if short > EPS {
        return match fil {
            true => (0.0, true, true),
            false => (badness(short, stretch), true, true),
        };
    }
    if short < -EPS {
        // Past the measure by more than the glue can give back is an overfull
        // line: TeX's adjustment ratio below -1, which is not a break at all.
        if -short > shrink + EPS {
            return (INF_BAD, false, false);
        }
        return (badness(-short, shrink), false, true);
    }
    (0.0, true, true)
}

/// Where to end each line of `pieces`, as the number of pieces consumed.
///
/// The answer always covers the whole paragraph: the last entry is
/// `pieces.len()`. An empty paragraph gets an empty answer.
///
/// TeX's three passes (§863): break with no hyphens at `\pretolerance` (a
/// negative one skips the pass); if no set of breakpoints is that good, offer
/// the hyphens at `\tolerance`; and if that fails too, take the least bad set
/// there is, overfull lines included.
pub fn break_paragraph(pieces: &[Piece], measure: f64, params: &Params) -> Vec<usize> {
    if pieces.is_empty() {
        return Vec::new();
    }
    let first = match params.pretolerance >= 0.0 {
        true => total_fit(pieces, measure, params.pretolerance, false, false, params),
        false => None,
    };
    first
        .or_else(|| total_fit(pieces, measure, params.tolerance, true, false, params))
        .or_else(|| total_fit(pieces, measure, INF_BAD, true, true, params))
        .unwrap_or_else(|| vec![pieces.len()])
}

/// One pass of §813's algorithm.
///
/// `hyphens` says whether a discretionary counts as a breakpoint this pass;
/// `overfull` whether a line past the measure may be taken when nothing else
/// fits. `None` means no set of breakpoints met `threshold`.
fn total_fit(
    pieces: &[Piece],
    measure: f64,
    threshold: f64,
    hyphens: bool,
    overfull: bool,
    params: &Params,
) -> Option<Vec<usize>> {
    let n = pieces.len();
    // Prefix sums, so the width of a candidate line is a subtraction rather
    // than a walk: a paragraph of 200 words offers thousands of candidates and
    // each would otherwise re-add the words it holds.
    let mut wide = vec![0.0; n + 1];
    let mut gap = vec![0.0; n + 1];
    let mut give = vec![0.0; n + 1];
    let mut take = vec![0.0; n + 1];
    for (k, piece) in pieces.iter().enumerate() {
        wide[k + 1] = wide[k] + piece.width;
        let space = match piece.after {
            After::Glue(space) => space,
            _ => 0.0,
        };
        gap[k + 1] = gap[k] + space;
        give[k + 1] = give[k] + space * STRETCH_FRACTION;
        take[k + 1] = take[k] + space * SHRINK_FRACTION;
    }
    // §831: a penalty of 10000 or more is no breakpoint at all, so
    // `\hyphenpenalty=10000` forbids hyphenation rather than pricing it.
    let allowed = |penalty: f64| penalty < INF_PENALTY;
    let breakable = |k: usize| match pieces[k].after {
        After::Glue(_) => true,
        After::Discretionary(_) => hyphens && allowed(params.hyphen_penalty),
        After::Explicit => allowed(params.ex_hyphen_penalty),
        After::Nothing => false,
    };

    // best[b][f]: the least demerits of setting pieces 0..b as whole lines,
    // where the line ending at b is of fitness class f. Four classes because
    // the NEXT line's demerits depend on this one's class (§859's
    // `adj_demerits`), so they cannot be collapsed to one number per break.
    let mut best = vec![[f64::INFINITY; 4]; n + 1];
    let mut from = vec![[(0usize, 0usize); 4]; n + 1];
    // §864: the paragraph starts as though the line before it were decent.
    best[0][DECENT] = 0.0;

    for p in 0..n {
        if best[p].iter().all(|d| !d.is_finite()) {
            continue;
        }
        // A break at p is one the previous line ended on; whether it was a
        // hyphen decides `\doublehyphendemerits` below.
        let after_hyphen = p > 0
            && matches!(
                pieces[p - 1].after,
                After::Discretionary(_) | After::Explicit
            );
        for b in p + 1..=n {
            let dash = match pieces[b - 1].after {
                After::Discretionary(dash) => dash,
                _ => 0.0,
            };
            let natural = (wide[b] - wide[p]) + (gap[b - 1] - gap[p]) + dash;
            let stretch = give[b - 1] - give[p];
            let shrink = take[b - 1] - take[p];
            let last = b == n;
            let (bad, stretching, fits) = assess(natural, stretch, shrink, measure, last);
            // The end of the paragraph is a breakpoint whatever is written
            // there; anywhere else the piece has to offer one.
            if last || breakable(b - 1) {
                let take_it = match fits {
                    true => bad <= threshold,
                    // An overfull line is only ever taken in the final pass,
                    // and then at `OVERFULL_DEMERITS` below.
                    false => overfull,
                };
                if take_it {
                    let here = fitness(bad, stretching);
                    // §869: what the breakpoint itself costs.
                    let penalty = match last {
                        true => EJECT_PENALTY,
                        false => match pieces[b - 1].after {
                            After::Discretionary(_) => params.hyphen_penalty,
                            After::Explicit => params.ex_hyphen_penalty,
                            _ => 0.0,
                        },
                    };
                    // §859: the demerits of this line.
                    let mut cost = params.line_penalty + bad;
                    cost = match cost.abs() >= INF_BAD {
                        true => 1e8,
                        false => cost * cost,
                    };
                    // An overfull line is not a break TeX would make at all
                    // (§851 deactivates one), so it has to cost more than any
                    // number of merely dreadful lines -- 1e8 apiece and a
                    // paragraph is a few hundred of them at most. Charging it
                    // the same 1e8 they get is how one 1,100pt line came out
                    // preferred to two ordinary ones, and the four words above
                    // it were drawn a foot into the margin. Past that floor the
                    // overflow itself is priced, so the least bad overfull line
                    // is the one taken.
                    if !fits {
                        let excess = natural - shrink - measure;
                        cost = OVERFULL_DEMERITS + excess * excess;
                    }
                    if penalty > 0.0 {
                        cost += penalty * penalty;
                    } else if penalty > EJECT_PENALTY {
                        cost -= penalty * penalty;
                    }
                    // §873 asks for the final break as a HYPHENATED one, which
                    // is what makes `\finalhyphendemerits` reachable: a hyphen
                    // on the second-to-last line is the one TeX charges for.
                    let hyphen_here = last
                        || matches!(
                            pieces[b - 1].after,
                            After::Discretionary(_) | After::Explicit
                        );
                    if hyphen_here && after_hyphen {
                        cost += match last {
                            true => params.final_hyphen_demerits,
                            false => params.double_hyphen_demerits,
                        };
                    }
                    for before in 0..4 {
                        if !best[p][before].is_finite() {
                            continue;
                        }
                        let mut total = best[p][before] + cost;
                        if here.abs_diff(before) > 1 {
                            total += params.adj_demerits;
                        }
                        if total < best[b][here] {
                            best[b][here] = total;
                            from[b][here] = (p, before);
                        }
                    }
                }
            }
            // Past this point every longer line is longer still, so there is
            // nothing left to consider from p.
            if !fits {
                break;
            }
        }
    }

    let end = (0..4).filter(|f| best[n][*f].is_finite()).min_by(|a, b| {
        best[n][*a]
            .partial_cmp(&best[n][*b])
            .unwrap_or(std::cmp::Ordering::Equal)
    })?;
    let mut breaks = Vec::new();
    let (mut at, mut class) = (n, end);
    while at > 0 {
        breaks.push(at);
        let (p, before) = from[at][class];
        at = p;
        class = before;
    }
    breaks.reverse();
    Some(breaks)
}

/// Liang's hyphenation patterns, as `hyphen.tex` states them.
///
/// The patterns are Knuth's own, read from the TeX installation rather than
/// copied: they are the ones the reference PDFs beside the corpus were set
/// with, and a copy here would be a second thing to keep in step. A machine
/// with no TeX installation gets an EMPTY set and no hyphenation, which is
/// what texrs did before this and is still a correct paragraph.
///
/// Both the patterns and the exceptions are held in a letter trie, the
/// structure `tex.web` keeps them in (§920-§923): looking a word up walks the
/// trie once from each of its positions, following one letter at a time, so a
/// lookup costs one array index per letter rather than one hash of every
/// substring it might match.
#[derive(Default)]
pub struct Hyphenator {
    /// Every byte a pattern or exception spells with, numbered from one; 0 is
    /// a byte none of them uses, which no lookup can follow.
    letters: Letters,
    /// A pattern's letters to the level between each of them: `.ach4` is
    /// `".ach"` and `[0, 0, 0, 0, 4]`.
    patterns: Trie<Vec<u8>>,
    /// `\hyphenation{as-so-ciate}`: where a named word breaks, whatever the
    /// patterns say.
    exceptions: Trie<Vec<usize>>,
}

/// The bytes a trie's keys are spelled in, each to its column.
#[derive(Default)]
struct Letters {
    column: Vec<u8>,
    count: usize,
}

impl Letters {
    fn new(keys: &[&[u8]]) -> Self {
        let mut column = vec![0u8; 256];
        let mut count = 0;
        for &byte in keys.iter().flat_map(|key| key.iter()) {
            if column[usize::from(byte)] == 0 {
                count += 1;
                // Hyphenation keys are letters and the full stop: far fewer
                // than 255, which a column number has room for.
                column[usize::from(byte)] = u8::try_from(count).unwrap_or(u8::MAX);
            }
        }
        Self { column, count }
    }

    /// The column `byte` is followed in, or `None` when no key spells with it.
    fn of(&self, byte: u8) -> Option<usize> {
        match self.column.get(usize::from(byte)).copied().unwrap_or(0) {
            0 => None,
            c => Some(usize::from(c) - 1),
        }
    }
}

/// Keys spelled in [`Letters`], each to the value stored where it ends.
///
/// Node 0 is the root. `next[node * width + column]` is the node one letter
/// on, and 0 there means no key continues that way (the root is no node's
/// child, so 0 is free to mean "none").
struct Trie<V> {
    width: usize,
    next: Vec<u32>,
    value: Vec<Option<V>>,
}

impl<V> Default for Trie<V> {
    fn default() -> Self {
        Self {
            width: 0,
            next: Vec::new(),
            value: Vec::new(),
        }
    }
}

impl<V> Trie<V> {
    fn new(width: usize) -> Self {
        Self {
            width,
            next: vec![0; width],
            value: vec![None],
        }
    }

    /// Store `value` at `key`, replacing what a key spelled the same stored.
    fn insert(&mut self, letters: &Letters, key: &[u8], value: V) {
        let mut node = 0usize;
        for &byte in key {
            let Some(column) = letters.of(byte) else {
                return;
            };
            let slot = node * self.width + column;
            node = match self.next[slot] {
                0 => {
                    let fresh = self.value.len();
                    self.next[slot] = u32::try_from(fresh).unwrap_or(u32::MAX);
                    self.next.extend(std::iter::repeat_n(0, self.width));
                    self.value.push(None);
                    fresh
                }
                to => to as usize,
            };
        }
        self.value[node] = Some(value);
    }

    /// The node one letter on from `node`, if any key continues that way.
    fn step(&self, letters: &Letters, node: usize, byte: u8) -> Option<usize> {
        let column = letters.of(byte)?;
        match self.next.get(node * self.width + column).copied() {
            None | Some(0) => None,
            Some(to) => Some(to as usize),
        }
    }

    /// What is stored at `key` exactly.
    fn get(&self, letters: &Letters, key: &[u8]) -> Option<&V> {
        if self.value.is_empty() {
            return None;
        }
        let mut node = 0usize;
        for &byte in key {
            node = self.step(letters, node, byte)?;
        }
        self.value[node].as_ref()
    }

    fn is_empty(&self) -> bool {
        self.value.iter().all(Option::is_none)
    }
}

/// `\lefthyphenmin` and `\righthyphenmin`, at the values LaTeX sets for
/// English: no break with fewer than two letters before it or three after.
const LEFT_MIN: usize = 2;
const RIGHT_MIN: usize = 3;

impl Hyphenator {
    /// The patterns from a `hyphen.tex`, and nothing if it cannot be read.
    pub fn from_source(src: &str) -> Self {
        let patterns: Vec<(Vec<u8>, Vec<u8>)> = block(src, "\\patterns{")
            .iter()
            .map(|pattern| split_pattern(pattern))
            .filter(|(key, _)| !key.is_empty())
            .collect();
        let exceptions: Vec<(Vec<u8>, Vec<usize>)> = block(src, "\\hyphenation{")
            .iter()
            .map(|word| {
                let letters: Vec<u8> = word
                    .bytes()
                    .filter(|b| *b != b'-')
                    .map(|b| b.to_ascii_lowercase())
                    .collect();
                let mut at = Vec::new();
                let mut seen = 0usize;
                for byte in word.bytes() {
                    match byte {
                        b'-' => at.push(seen),
                        _ => seen += 1,
                    }
                }
                (letters, at)
            })
            .collect();
        let keys: Vec<&[u8]> = patterns
            .iter()
            .map(|(key, _)| key.as_slice())
            .chain(exceptions.iter().map(|(key, _)| key.as_slice()))
            .collect();
        let letters = Letters::new(&keys);
        let mut me = Self {
            patterns: Trie::new(letters.count),
            exceptions: Trie::new(letters.count),
            letters,
        };
        // In source order, so a pattern or exception stated twice keeps the
        // later statement, as inserting into a map did.
        for (key, levels) in patterns {
            me.patterns.insert(&me.letters, &key, levels);
        }
        for (key, at) in exceptions {
            me.exceptions.insert(&me.letters, &key, at);
        }
        me
    }

    /// Whether anything was loaded at all.
    pub fn is_empty(&self) -> bool {
        self.patterns.is_empty() && self.exceptions.is_empty()
    }

    /// Where `word` may be broken, as the number of letters left on the line.
    ///
    /// Only a plain ASCII word is offered: a word carrying a typesetting
    /// marker, an accent or a digit is left whole rather than broken somewhere
    /// the patterns were never stated for.
    pub fn points(&self, word: &str) -> Vec<usize> {
        let len = word.len();
        if len < LEFT_MIN + RIGHT_MIN || !word.bytes().all(|b| b.is_ascii_alphabetic()) {
            return Vec::new();
        }
        // The word between two full stops, lower-cased: the exceptions are
        // keyed on the letters alone, the patterns on the whole of it.
        let mut edged = Vec::with_capacity(len + 2);
        edged.push(b'.');
        edged.extend(word.bytes().map(|b| b.to_ascii_lowercase()));
        edged.push(b'.');
        let inside = |at: &usize| *at >= LEFT_MIN && len - *at >= RIGHT_MIN;
        if let Some(known) = self.exceptions.get(&self.letters, &edged[1..=len]) {
            return known.iter().copied().filter(inside).collect();
        }
        // Liang: every substring that is a pattern applies its levels, and
        // the highest level wins at each position. An odd level is a break.
        // The substrings starting at `i` are exactly the trie nodes walking
        // `edged[i..]` passes through, so one walk per start finds them all.
        let mut level = vec![0u8; edged.len() + 1];
        if !self.patterns.value.is_empty() {
            for i in 0..edged.len() {
                let mut node = 0usize;
                for &byte in &edged[i..] {
                    let Some(to) = self.patterns.step(&self.letters, node, byte) else {
                        break;
                    };
                    node = to;
                    if let Some(values) = &self.patterns.value[node] {
                        for (k, value) in values.iter().enumerate() {
                            level[i + k] = level[i + k].max(*value);
                        }
                    }
                }
            }
        }
        // `level[i]` is the gap before `edged[i]`, and `edged` is the word with
        // a full stop welded to each end, so the gap after the word's `at`th
        // letter is `level[at + 1]`.
        (LEFT_MIN..=len.saturating_sub(RIGHT_MIN))
            .filter(|at| level[at + 1] % 2 == 1)
            .collect()
    }
}

/// The words inside one `\patterns{...}` or `\hyphenation{...}` group.
///
/// The group closes on a `}` alone on its line, which is how `hyphen.tex`
/// writes both of them, and `%` starts a comment as it does anywhere in TeX.
fn block(src: &str, opens: &str) -> Vec<String> {
    let Some(at) = src.find(opens) else {
        return Vec::new();
    };
    let mut out = Vec::new();
    for line in src[at + opens.len()..].lines() {
        let line = match line.find('%') {
            Some(comment) => &line[..comment],
            None => line,
        };
        if line.trim() == "}" {
            break;
        }
        out.extend(line.split_whitespace().map(str::to_string));
    }
    out
}

/// A pattern into the letters it matches and the level between each of them.
fn split_pattern(pattern: &str) -> (Vec<u8>, Vec<u8>) {
    let mut key = Vec::new();
    let mut levels = vec![0u8];
    for byte in pattern.bytes() {
        match byte.is_ascii_digit() {
            true => *levels.last_mut().unwrap_or(&mut 0) = byte - b'0',
            false => {
                key.push(byte);
                levels.push(0);
            }
        }
    }
    (key, levels)
}

/// The patterns this process breaks words with, read once.
pub fn hyphenator() -> &'static Hyphenator {
    static PATTERNS: OnceLock<Hyphenator> = OnceLock::new();
    PATTERNS.get_or_init(|| match patterns_source() {
        Some(src) => Hyphenator::from_source(&src),
        None => Hyphenator::default(),
    })
}

/// `hyphen.tex`, asked for the way every TeX program asks for a file.
fn patterns_source() -> Option<String> {
    let path = crate::kpse::locate("hyphen.tex")?;
    std::fs::read_to_string(path).ok()
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Every word breaks where TeX's own `\showhyphens` breaks it.
    ///
    /// The right-hand column is verbatim out of a `pdflatex` run of
    /// `\showhyphens{...}` over these words -- not out of Liang's paper and
    /// not out of this implementation -- so what the test says is "the same as
    /// TeX" rather than "the same as it was yesterday".
    #[test]
    fn liang_breaks_the_words_tex_breaks() {
        let words = hyphenator();
        if words.is_empty() {
            return; // no TeX installation: hyphenation degrades to none
        }
        let showhyphens = [
            "hy-phen-ation",
            "com-puter",
            "al-go-rithm",
            "as-so-ciate", // one of \hyphenation{}'s own exceptions
            "type-set-ting",
            "para-graph",
            "rep-re-sen-ta-tion",
            "im-ple-men-ta-tion",
            "un-der-stand-ing",
            "dif-fer-ence",
            "pro-fes-sional",
            "in-ter-na-tional",
            "de-vel-op-ment",
            "con-sid-er-a-tion",
        ];
        for dashed in showhyphens {
            let word: String = dashed.chars().filter(|c| *c != '-').collect();
            let mut wanted = Vec::new();
            let mut at = 0;
            for c in dashed.chars() {
                match c {
                    '-' => wanted.push(at),
                    _ => at += 1,
                }
            }
            assert_eq!(words.points(&word), wanted, "{dashed}");
        }
        // \lefthyphenmin and \righthyphenmin: neither of these breaks at all.
        assert!(words.points("into").is_empty(), "into");
    }

    /// A machine with no TeX installation gets no patterns, and no patterns
    /// means every word is one piece rather than a panic or a wrong break.
    #[test]
    fn no_patterns_means_no_hyphens() {
        let none = Hyphenator::default();
        assert!(none.is_empty());
        assert!(none.points("hyphenation").is_empty());
    }

    /// The breaker takes the set of breakpoints that costs the whole paragraph
    /// least, and that is not the set a left-to-right fill reaches.
    ///
    /// Seventeen boxes on a 400pt measure with 20pt glue, and every line of
    /// BOTH answers is inside `\tolerance`, so this is a difference of quality
    /// and not one answer failing:
    ///
    ///   first fit  391 / 369 / 385 / 86   badness 1 / 110 / 3 / 0
    ///   total fit  391 / 417 / 390 / 33   badness 1 /  26 / 1 / 0
    ///
    /// First fit stops line two one box early because the next box will not go
    /// on at its natural width, and pays 110 badness for the gap. Total fit
    /// takes that box and shrinks the line onto the measure instead -- 14,790
    /// demerits against 1,638 for the whole paragraph. Shrinking is exactly
    /// what the renderer could not do before `Page::text_set`.
    #[test]
    fn total_fit_is_not_first_fit() {
        let boxes = [
            63.0, 32.0, 52.0, 63.0, 101.0, 81.0, 44.0, 89.0, 95.0, 28.0, 30.0, 40.0, 56.0, 101.0,
            30.0, 33.0, 33.0,
        ];
        let pieces: Vec<Piece> = boxes
            .iter()
            .enumerate()
            .map(|(at, width)| Piece {
                text: format!("w{at}"),
                width: *width,
                after: match at + 1 == boxes.len() {
                    true => After::Nothing,
                    false => After::Glue(20.0),
                },
            })
            .collect();
        let measure = 400.0;

        // First fit, spelled out here so the comparison is not a claim about
        // some other function's behaviour.
        let mut greedy = Vec::new();
        let (mut width, mut count) = (0.0f64, 0usize);
        for (at, piece) in pieces.iter().enumerate() {
            let need = match count {
                0 => piece.width,
                _ => width + 20.0 + piece.width,
            };
            if count > 0 && need > measure {
                greedy.push(at);
                width = piece.width;
                count = 1;
                continue;
            }
            width = need;
            count += 1;
        }
        greedy.push(pieces.len());
        assert_eq!(greedy, vec![5, 9, 15, 17], "first fit stops at the measure");

        let total = break_paragraph(&pieces, measure, &Params::default());
        assert_eq!(total, vec![5, 10, 16, 17], "total fit takes one box more");
        assert_ne!(total, greedy, "the two answers differ, which is the point");
    }

    /// A paragraph always comes out whole, even when no line can be set: a
    /// word wider than the measure still reaches the page.
    #[test]
    fn an_unbreakable_paragraph_is_still_broken() {
        let pieces = vec![
            Piece {
                text: "enormous".into(),
                width: 900.0,
                after: After::Glue(4.0),
            },
            Piece {
                text: "word".into(),
                width: 900.0,
                after: After::Nothing,
            },
        ];
        assert_eq!(
            break_paragraph(&pieces, 100.0, &Params::default()),
            vec![1, 2]
        );
    }
}