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)] |
| 14 | pub 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 | |
| 52 | impl 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. |
| 180 | pub 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. |
| 186 | pub 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. |
| 221 | fn 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. |
| 238 | fn 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 | |
| 247 | fn 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)] |
| 253 | struct 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 | |
| 262 | impl<'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). |
| 314 | fn 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)] |
| 327 | mod 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 | } |