use std::sync::OnceLock;
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum After {
Glue(f64),
Discretionary(f64),
Explicit,
Nothing,
}
#[derive(Clone, Debug)]
pub struct Piece {
pub text: String,
pub width: f64,
pub after: After,
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Params {
pub pretolerance: f64,
pub tolerance: f64,
pub line_penalty: f64,
pub hyphen_penalty: f64,
pub ex_hyphen_penalty: f64,
pub adj_demerits: f64,
pub double_hyphen_demerits: f64,
pub final_hyphen_demerits: f64,
}
impl Default for Params {
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 {
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),
}
}
}
const INF_BAD: f64 = 10000.0;
const OVERFULL_DEMERITS: f64 = 1e12;
const INF_PENALTY: f64 = 10000.0;
const EJECT_PENALTY: f64 = -10000.0;
const STRETCH_FRACTION: f64 = 0.5;
const SHRINK_FRACTION: f64 = 1.0 / 3.0;
const EPS: f64 = 1e-6;
const VERY_LOOSE: usize = 0;
const LOOSE: usize = 1;
const DECENT: usize = 2;
const TIGHT: usize = 3;
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
}
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,
}
}
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 {
if -short > shrink + EPS {
return (INF_BAD, false, false);
}
return (badness(-short, shrink), false, true);
}
(0.0, true, true)
}
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()])
}
fn total_fit(
pieces: &[Piece],
measure: f64,
threshold: f64,
hyphens: bool,
overfull: bool,
params: &Params,
) -> Option<Vec<usize>> {
let n = pieces.len();
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;
}
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,
};
let mut best = vec![[f64::INFINITY; 4]; n + 1];
let mut from = vec![[(0usize, 0usize); 4]; n + 1];
best[0][DECENT] = 0.0;
for p in 0..n {
if best[p].iter().all(|d| !d.is_finite()) {
continue;
}
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);
if last || breakable(b - 1) {
let take_it = match fits {
true => bad <= threshold,
false => overfull,
};
if take_it {
let here = fitness(bad, stretching);
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,
},
};
let mut cost = params.line_penalty + bad;
cost = match cost.abs() >= INF_BAD {
true => 1e8,
false => cost * cost,
};
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;
}
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);
}
}
}
}
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)
}
#[derive(Default)]
pub struct Hyphenator {
letters: Letters,
patterns: Trie<Vec<u8>>,
exceptions: Trie<Vec<usize>>,
}
#[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;
column[usize::from(byte)] = u8::try_from(count).unwrap_or(u8::MAX);
}
}
Self { column, count }
}
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),
}
}
}
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],
}
}
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);
}
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),
}
}
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)
}
}
const LEFT_MIN: usize = 2;
const RIGHT_MIN: usize = 3;
impl Hyphenator {
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,
};
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
}
pub fn is_empty(&self) -> bool {
self.patterns.is_empty() && self.exceptions.is_empty()
}
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();
}
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();
}
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);
}
}
}
}
}
(LEFT_MIN..=len.saturating_sub(RIGHT_MIN))
.filter(|at| level[at + 1] % 2 == 1)
.collect()
}
}
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
}
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)
}
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(),
})
}
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::*;
#[test]
fn liang_breaks_the_words_tex_breaks() {
let words = hyphenator();
if words.is_empty() {
return; }
let showhyphens = [
"hy-phen-ation",
"com-puter",
"al-go-rithm",
"as-so-ciate", "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}");
}
assert!(words.points("into").is_empty(), "into");
}
#[test]
fn no_patterns_means_no_hyphens() {
let none = Hyphenator::default();
assert!(none.is_empty());
assert!(none.points("hyphenation").is_empty());
}
#[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;
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");
}
#[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]
);
}
}