Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/hyphen/mod.rs

11.1 KiB, 1 run

created by r1870400018:65177, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// SPDX-License-Identifier: MIT OR Apache-2.0
2// Original work copyright (c) the hypher authors, Laurenz Mädje (hypher 0.1.6).
3// Modified for Hematite: ported to its error handling, returning split offsets.
4//! Liang hyphenation for 35 languages, over pattern automata compiled from the TeX patterns.
5//!
6//! A port of `hypher` 0.1.6 (Laurenz Mädje, MIT or Apache-2.0), the crate Typst hyphenates with, and of
7//! its compiled automata (`tries/*.bin`), so a word breaks where Typst breaks it. The patterns behind
8//! the automata come from the TeX `hyph-utf8` collection under their own permissive licences (LPPL,
9//! MPL, MIT, BSD-3); `tries/NOTICE.txt` names the sources. The module is compiled only with the
10//! `hyphenation` feature, since the automata add about 1.1 MiB.
11
12/// A language hyphenation has patterns for.
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub enum Lang {
15 Afrikaans,
16 Albanian,
17 Belarusian,
18 Bulgarian,
19 Catalan,
20 Croatian,
21 Czech,
22 Danish,
23 Dutch,
24 English,
25 Estonian,
26 Finnish,
27 French,
28 Georgian,
29 German,
30 Greek,
31 Hungarian,
32 Icelandic,
33 Italian,
34 Kurmanji,
35 Latin,
36 Lithuanian,
37 Mongolian,
38 Norwegian,
39 Polish,
40 Portuguese,
41 Russian,
42 Serbian,
43 Slovak,
44 Slovenian,
45 Spanish,
46 Swedish,
47 Turkish,
48 Turkmen,
49 Ukrainian,
50}
51
52impl Lang {
53
54 /// The language an ISO 639-1 code names, where there are patterns for it.
55 pub fn from_iso(code: &str) -> Option<Self> {
56 match code {
57 "af" => Some(Self::Afrikaans),
58 "sq" => Some(Self::Albanian),
59 "be" => Some(Self::Belarusian),
60 "bg" => Some(Self::Bulgarian),
61 "ca" => Some(Self::Catalan),
62 "hr" => Some(Self::Croatian),
63 "cs" => Some(Self::Czech),
64 "da" => Some(Self::Danish),
65 "nl" => Some(Self::Dutch),
66 "en" => Some(Self::English),
67 "et" => Some(Self::Estonian),
68 "fi" => Some(Self::Finnish),
69 "fr" => Some(Self::French),
70 "ka" => Some(Self::Georgian),
71 "de" => Some(Self::German),
72 "el" => Some(Self::Greek),
73 "hu" => Some(Self::Hungarian),
74 "is" => Some(Self::Icelandic),
75 "it" => Some(Self::Italian),
76 "ku" => Some(Self::Kurmanji),
77 "la" => Some(Self::Latin),
78 "lt" => Some(Self::Lithuanian),
79 "mn" => Some(Self::Mongolian),
80 "no" | "nb" | "nn" => Some(Self::Norwegian),
81 "pl" => Some(Self::Polish),
82 "pt" => Some(Self::Portuguese),
83 "ru" => Some(Self::Russian),
84 "sr" => Some(Self::Serbian),
85 "sk" => Some(Self::Slovak),
86 "sl" => Some(Self::Slovenian),
87 "es" => Some(Self::Spanish),
88 "sv" => Some(Self::Swedish),
89 "tr" => Some(Self::Turkish),
90 "tk" => Some(Self::Turkmen),
91 "uk" => Some(Self::Ukrainian),
92 _ => None,
93 }
94 }
95
96 /// The fewest characters the patterns leave before the first break and after the last.
97 pub fn bounds(self) -> (usize, usize) {
98 match self {
99 Self::Afrikaans => (1, 2),
100 Self::Albanian => (2, 2),
101 Self::Belarusian => (2, 2),
102 Self::Bulgarian => (2, 2),
103 Self::Catalan => (2, 2),
104 Self::Croatian => (2, 2),
105 Self::Czech => (2, 2),
106 Self::Danish => (2, 2),
107 Self::Dutch => (2, 2),
108 Self::English => (2, 3),
109 Self::Estonian => (2, 3),
110 Self::Finnish => (2, 2),
111 Self::French => (2, 2),
112 Self::Georgian => (1, 2),
113 Self::German => (2, 2),
114 Self::Greek => (1, 1),
115 Self::Hungarian => (2, 2),
116 Self::Icelandic => (2, 2),
117 Self::Italian => (2, 2),
118 Self::Kurmanji => (2, 2),
119 Self::Latin => (2, 2),
120 Self::Lithuanian => (2, 2),
121 Self::Mongolian => (2, 2),
122 Self::Norwegian => (2, 2),
123 Self::Polish => (2, 2),
124 Self::Portuguese => (2, 3),
125 Self::Russian => (2, 2),
126 Self::Serbian => (2, 2),
127 Self::Slovak => (2, 3),
128 Self::Slovenian => (2, 2),
129 Self::Spanish => (2, 2),
130 Self::Swedish => (2, 2),
131 Self::Turkish => (2, 2),
132 Self::Turkmen => (2, 2),
133 Self::Ukrainian => (2, 2),
134 }
135 }
136
137 fn data(self) -> &'static [u8] {
138 match self {
139 Self::Afrikaans => include_bytes!("tries/af.bin"),
140 Self::Albanian => include_bytes!("tries/sq.bin"),
141 Self::Belarusian => include_bytes!("tries/be.bin"),
142 Self::Bulgarian => include_bytes!("tries/bg.bin"),
143 Self::Catalan => include_bytes!("tries/ca.bin"),
144 Self::Croatian => include_bytes!("tries/hr.bin"),
145 Self::Czech => include_bytes!("tries/cs.bin"),
146 Self::Danish => include_bytes!("tries/da.bin"),
147 Self::Dutch => include_bytes!("tries/nl.bin"),
148 Self::English => include_bytes!("tries/en.bin"),
149 Self::Estonian => include_bytes!("tries/et.bin"),
150 Self::Finnish => include_bytes!("tries/fi.bin"),
151 Self::French => include_bytes!("tries/fr.bin"),
152 Self::Georgian => include_bytes!("tries/ka.bin"),
153 Self::German => include_bytes!("tries/de.bin"),
154 Self::Greek => include_bytes!("tries/el.bin"),
155 Self::Hungarian => include_bytes!("tries/hu.bin"),
156 Self::Icelandic => include_bytes!("tries/is.bin"),
157 Self::Italian => include_bytes!("tries/it.bin"),
158 Self::Kurmanji => include_bytes!("tries/ku.bin"),
159 Self::Latin => include_bytes!("tries/la.bin"),
160 Self::Lithuanian => include_bytes!("tries/lt.bin"),
161 Self::Mongolian => include_bytes!("tries/mn.bin"),
162 Self::Norwegian => include_bytes!("tries/no.bin"),
163 Self::Polish => include_bytes!("tries/pl.bin"),
164 Self::Portuguese => include_bytes!("tries/pt.bin"),
165 Self::Russian => include_bytes!("tries/ru.bin"),
166 Self::Serbian => include_bytes!("tries/sr.bin"),
167 Self::Slovak => include_bytes!("tries/sk.bin"),
168 Self::Slovenian => include_bytes!("tries/sl.bin"),
169 Self::Spanish => include_bytes!("tries/es.bin"),
170 Self::Swedish => include_bytes!("tries/sv.bin"),
171 Self::Turkish => include_bytes!("tries/tr.bin"),
172 Self::Turkmen => include_bytes!("tries/tk.bin"),
173 Self::Ukrainian => include_bytes!("tries/uk.bin"),
174 }
175 }
176}
177
178/// The byte offsets inside `word` at which it may be hyphenated in `lang`, in order, the language's own
179/// minimum run of characters kept either side.
180pub fn hyphenate(word: &str, lang: Lang) -> Vec<usize> {
181 let (l, r) = lang.bounds();
182 hyphenate_bounded(word, lang, l, r)
183}
184
185/// As [`hyphenate`], with `left_min` and `right_min` characters kept either side.
186pub fn hyphenate_bounded(word: &str, lang: Lang, left_min: usize, right_min: usize) -> Vec<usize> {
187 let data = lang.data();
188 let root = match State::root(data) {
189 Some(s) => s,
190 None => return Vec::new(),
191 };
192 let dotted = lowercase_and_dot(word);
193 let (min_idx, max_idx) = byte_bounds(word, left_min, right_min);
194 let mut levels = vec![0u8; word.len().saturating_sub(1)];
195 for start in 0..dotted.len() {
196 if !is_char_boundary(dotted[start]) {
197 continue;
198 }
199 let mut state = root;
200 for &b in &dotted[start..] {
201 match state.transition(b) {
202 Some(next) => {
203 state = next;
204 for (offset, level) in state.levels() {
205 let split = start + offset;
206 if split >= min_idx && split <= max_idx {
207 if let Some(slot) = split.checked_sub(2).and_then(|i| levels.get_mut(i)) {
208 *slot = (*slot).max(level);
209 }
210 }
211 }
212 }
213 None => break,
214 }
215 }
216 }
217 levels.iter().enumerate().filter(|(_, l)| *l % 2 == 1).map(|(i, _)| i + 1).collect()
218}
219
220/// The word lower-cased where that keeps each character's length, between two dots.
221fn lowercase_and_dot(word: &str) -> Vec<u8> {
222 let mut out = Vec::with_capacity(word.len() + 2);
223 out.push(b'.');
224 let mut buf = [0u8; 4];
225 for c in word.chars() {
226 let mut lower = c.to_lowercase();
227 let c = match (lower.next(), lower.next()) {
228 (Some(l), None) if l.len_utf8() == c.len_utf8() => l,
229 _ => c,
230 };
231 out.extend_from_slice(c.encode_utf8(&mut buf).as_bytes());
232 }
233 out.push(b'.');
234 out
235}
236
237/// The dotted-word offsets between which a break may fall.
238fn byte_bounds(word: &str, left_min: usize, right_min: usize) -> (usize, usize) {
239 let left_min = left_min.max(1);
240 let right_min = right_min.max(1);
241 let min_idx = 1 + word.chars().take(left_min).map(char::len_utf8).sum::<usize>();
242 let right: usize = word.chars().rev().take(right_min).map(char::len_utf8).sum();
243 let max_idx = (1 + word.len()).saturating_sub(right);
244 (min_idx, max_idx)
245}
246
247fn is_char_boundary(b: u8) -> bool {
248 (b as i8) >= -0x40
249}
250
251/// A state of the automaton: its levels, and its transitions by byte to targets `stride` bytes wide.
252#[derive(Clone, Copy)]
253struct State<'a> {
254 data: &'a [u8],
255 addr: usize,
256 stride: usize,
257 levels: &'a [u8],
258 trans: &'a [u8],
259 targets: &'a [u8],
260}
261
262impl<'a> State<'a> {
263
264 fn root(data: &'a [u8]) -> Option<Self> {
265 let b = data.get(..4)?;
266 let addr = u32::from_be_bytes([b[0], b[1], b[2], b[3]]) as usize;
267 Self::at(data, addr)
268 }
269
270 fn at(data: &'a [u8], addr: usize) -> Option<Self> {
271 let node = data.get(addr..)?;
272 let head = *node.first()?;
273 let mut pos = 1;
274 let has_levels = head >> 7 != 0;
275 let stride = usize::from((head >> 5) & 3);
276 let mut count = usize::from(head & 31);
277 if count == 31 {
278 count = usize::from(*node.get(pos)?);
279 pos += 1;
280 }
281 let mut levels: &[u8] = &[];
282 if has_levels {
283 let hi = usize::from(*node.get(pos)?) << 4;
284 let second = *node.get(pos + 1)?;
285 let offset = hi | (usize::from(second) >> 4);
286 let len = usize::from(second & 15);
287 levels = data.get(offset..offset + len)?;
288 pos += 2;
289 }
290 let trans = node.get(pos..pos + count)?;
291 pos += count;
292 let targets = node.get(pos..pos + stride * count)?;
293 Some(Self { data, addr, stride, levels, trans, targets })
294 }
295
296 fn transition(self, b: u8) -> Option<Self> {
297 let idx = self.trans.iter().position(|&x| x == b)?;
298 let off = self.stride * idx;
299 let delta = from_be_bytes(self.targets.get(off..off + self.stride)?)?;
300 let next = (self.addr as isize + delta) as usize;
301 Self::at(self.data, next)
302 }
303
304 fn levels(self) -> impl Iterator<Item = (usize, u8)> + 'a {
305 let mut offset = 0;
306 self.levels.iter().map(move |&packed| {
307 offset += usize::from(packed / 10);
308 (offset, packed % 10)
309 })
310 }
311}
312
313/// A signed big-endian offset of one, two or three bytes (three biased by 2^23).
314fn from_be_bytes(buf: &[u8]) -> Option<isize> {
315 match buf {
316 [a] => Some(i8::from_be_bytes([*a]) as isize),
317 [a, b] => Some(i16::from_be_bytes([*a, *b]) as isize),
318 [a, b, c] => {
319 let u = (usize::from(*a) << 16) | (usize::from(*b) << 8) | usize::from(*c);
320 Some(u as isize - (1 << 23))
321 }
322 _ => None,
323 }
324}
325
326#[cfg(test)]
327mod tests {
328 use super::*;
329
330 fn joined(word: &str, lang: Lang) -> String {
331 let mut out = String::new();
332 let mut last = 0;
333 for at in hyphenate(word, lang) {
334 out.push_str(&word[last..at]);
335 out.push('-');
336 last = at;
337 }
338 out.push_str(&word[last..]);
339 out
340 }
341
342 #[test]
343 fn test_english_breaks_as_hypher_does_00() {
344 for w in ["wel-come", "walk-ing", "cap-tiVe", "pur-sue", "wHaT-eVeR", "bro-ken", "ex-ten-sive",
345 "Prob-a-bil-ity", "rec-og-nize", "hello", "hi", ""] {
346 assert_eq!(joined(&w.replace('-', ""), Lang::English), w);
347 }
348 }
349
350 #[test]
351 fn test_german_breaks_as_hypher_does_01() {
352 for w in ["Baum", "ge-hen", "Ap-fel", "To-ma-te", "Ein-ga-be-auf-for-de-rung", "Fort-pflan-zungs-lem-ma",
353 "stra-te-gie-er-hal-ten-den", "hübsch", "häss-lich", "über-zeu-gen-der"] {
354 assert_eq!(joined(&w.replace('-', ""), Lang::German), w);
355 }
356 }
357
358 #[test]
359 fn test_other_scripts_02() {
360 assert_eq!(joined("διαμερίσματα", Lang::Greek), "δια-με-ρί-σμα-τα");
361 assert_eq!(joined("კარტოფილი", Lang::Georgian), "კარ-ტო-ფი-ლი");
362 assert_eq!(joined("wykształciuchy", Lang::Polish), "wy-kształ-ciu-chy");
363 assert_eq!(joined("brněnský", Lang::Czech), "br-něn-ský");
364 }
365}