Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/unicode/linebreak.rs

15.6 KiB, 1 run

created by r1870400018:13900, 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//! Line breaking, following UAX #14.
2//!
3//! The algorithm answers one question: where in this text may a renderer end a line, and where
4//! must it? It does not decide where a line actually ends, because that depends on the width of
5//! the glyphs and of the column, which are no business of a text library. A layout engine walks the
6//! opportunities this module yields, measures the run up to each one, and breaks at the last that
7//! fits.
8//!
9//! The rules are those of the default, untailored algorithm, which is what the Unicode Consortium's
10//! `LineBreakTest.txt` tests: class AI, SG and XX resolve to AL, class CJ resolves to NS, and class
11//! SA resolves to CM if the character is a nonspacing or spacing mark and to AL otherwise.
12//!
13//! ```
14//! use oxedyne_fe2o3_text::unicode::linebreak::{
15//! self,
16//! Break,
17//! };
18//!
19//! let s = "one two\nthree";
20//! let opps = linebreak::line_breaks(s);
21//!
22//! // After the space, after the newline, and at the end of the text.
23//! assert_eq!(opps[0].offset, 4);
24//! assert_eq!(opps[0].kind, Break::Optional);
25//! assert_eq!(opps[1].offset, 8);
26//! assert_eq!(opps[1].kind, Break::Mandatory);
27//! ```
28
29use crate::unicode::{
30 lookup::{
31 self,
32 Partitioned,
33 },
34 prop::LineBreakClass as L,
35 tables::lb::{
36 LB_FLAG_STARTS,
37 LB_FLAG_VALS,
38 },
39};
40
41/// Bit marking a character of East Asian width F, W or H.
42const FLAG_EAST_ASIAN: u8 = 1 << 0;
43/// Bit marking an initial quotation mark, general category Pi.
44const FLAG_PI: u8 = 1 << 1;
45/// Bit marking a final quotation mark, general category Pf.
46const FLAG_PF: u8 = 1 << 2;
47/// Bit marking an unassigned code point that is Extended_Pictographic.
48const FLAG_EXT_PICT_UNASSIGNED: u8 = 1 << 3;
49/// Bit marking general category Mn or Mc, which decides how class SA resolves.
50const FLAG_MARK: u8 = 1 << 4;
51
52/// The dotted circle, which the Brahmic rules LB28a treat as an aksara.
53const DOTTED_CIRCLE: char = '\u{25CC}';
54
55/// Whether a break at an offset is allowed or required.
56#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
57pub enum Break {
58 /// The line may end here.
59 Optional,
60 /// The line must end here, because the text says so or because it has run out.
61 Mandatory,
62}
63
64/// A place at which a line may or must end, as a byte offset into the string.
65#[derive(Clone, Copy, Debug, PartialEq, Eq)]
66pub struct Opportunity {
67 /// The byte offset of the first character of the next line.
68 pub offset: usize,
69 /// Whether the break is allowed or required.
70 pub kind: Break,
71}
72
73/// Returns every place a line may or must end in `s`, in order, ending with the length of the
74/// string. The end of the text is always a mandatory break, since a line cannot run past it.
75pub fn line_breaks(s: &str) -> Vec<Opportunity> {
76
77 let mut out = Vec::new();
78 if s.is_empty() {
79 return out;
80 }
81
82 let chs = scan(s);
83 let cls = clusters(&chs);
84
85 for i in 1..chs.len() {
86 match rule(&chs, &cls, i) {
87 Some(kind) => out.push(Opportunity { offset: chs[i].byte, kind }),
88 None => (),
89 }
90 }
91
92 out.push(Opportunity { offset: s.len(), kind: Break::Mandatory });
93 out
94}
95
96/// Returns the byte offsets at which `s` may or must break, without saying which is which.
97pub fn break_offsets(s: &str) -> Vec<usize> {
98 line_breaks(s).into_iter().map(|o| o.offset).collect()
99}
100
101/// A character, with the line breaking class it resolves to.
102struct Ch {
103 /// The byte offset of the character in the string.
104 byte: usize,
105 /// The resolved line breaking class.
106 cls: L,
107 /// The line breaking flags.
108 flags: u8,
109 /// Whether the character is the dotted circle.
110 dot: bool,
111}
112
113/// A run of a character and the combining marks that rule LB9 folds into it. The rules from LB11
114/// onwards read clusters, not characters.
115struct Cl {
116 /// The index of the character the cluster begins with.
117 first: usize,
118 /// The class of that character, with a lone combining mark resolved to AL by rule LB10.
119 cls: L,
120 /// The flags of that character.
121 flags: u8,
122 /// Whether that character is the dotted circle.
123 dot: bool,
124}
125
126/// Reads a string into the per character state the rules work over, resolving the classes that the
127/// default algorithm does not use.
128fn scan(s: &str) -> Vec<Ch> {
129
130 let mut chs = Vec::with_capacity(s.len());
131 for (byte, c) in s.char_indices() {
132 let flags = lookup::flags(&LB_FLAG_STARTS, &LB_FLAG_VALS, c);
133 let cls = match L::of(c) {
134 L::AI | L::SG | L::XX => L::AL,
135 L::CJ => L::NS,
136 L::SA => if flags & FLAG_MARK != 0 { L::CM } else { L::AL },
137 other => other,
138 };
139 chs.push(Ch {
140 byte,
141 cls,
142 flags,
143 dot: c == DOTTED_CIRCLE,
144 });
145 }
146 chs
147}
148
149/// Whether the character at `i` is a combining mark that rule LB9 folds into the character before
150/// it.
151fn folds(chs: &[Ch], i: usize) -> bool {
152 let (a, b) = match (chs.get(i.wrapping_sub(1)), chs.get(i)) {
153 (Some(a), Some(b)) => (a, b),
154 _ => return false,
155 };
156 if !matches!(b.cls, L::CM | L::ZWJ) {
157 return false;
158 }
159 !matches!(a.cls, L::BK | L::CR | L::LF | L::NL | L::SP | L::ZW)
160}
161
162/// Groups the characters into the clusters that rule LB9 leaves behind.
163fn clusters(chs: &[Ch]) -> Vec<Cl> {
164 let mut out = Vec::with_capacity(chs.len());
165 for (i, ch) in chs.iter().enumerate() {
166 if i > 0 && folds(chs, i) {
167 continue;
168 }
169 // LB10. A combining mark that folds into nothing stands for an alphabetic character.
170 let cls = match ch.cls {
171 L::CM | L::ZWJ => L::AL,
172 other => other,
173 };
174 out.push(Cl {
175 first: i,
176 cls,
177 flags: ch.flags,
178 dot: ch.dot,
179 });
180 }
181 out
182}
183
184/// Returns the index of the cluster the character at `i` belongs to, given that `i` begins one.
185fn cluster_at(cls: &[Cl], i: usize) -> Option<usize> {
186 match cls.binary_search_by(|c| c.first.cmp(&i)) {
187 Ok(q) => Some(q),
188 Err(_) => None,
189 }
190}
191
192/// The class of cluster `q`, or `None` past either end of the text.
193fn cl(cls: &[Cl], q: Option<usize>) -> Option<L> {
194 q.and_then(|q| cls.get(q)).map(|c| c.cls)
195}
196
197/// Whether cluster `q` is East Asian. A cluster past the end of the text is not.
198fn ea(cls: &[Cl], q: Option<usize>) -> bool {
199 match q.and_then(|q| cls.get(q)) {
200 Some(c) => c.flags & FLAG_EAST_ASIAN != 0,
201 None => false,
202 }
203}
204
205/// Whether cluster `q` carries a flag.
206fn has(cls: &[Cl], q: Option<usize>, flag: u8) -> bool {
207 match q.and_then(|q| cls.get(q)) {
208 Some(c) => c.flags & flag != 0,
209 None => false,
210 }
211}
212
213/// Whether cluster `q` is an aksara or the dotted circle, which rules LB28a group together.
214fn aksara(cls: &[Cl], q: Option<usize>) -> bool {
215 match q.and_then(|q| cls.get(q)) {
216 Some(c) => matches!(c.cls, L::AK | L::AS) || c.dot,
217 None => false,
218 }
219}
220
221/// Steps back over the clusters of the classes in `over`, returning the first cluster that is not
222/// one of them.
223fn skip_back(cls: &[Cl], from: usize, over: &[L]) -> Option<usize> {
224 let mut q = Some(from);
225 while let Some(i) = q {
226 match cls.get(i) {
227 Some(c) if over.contains(&c.cls) => q = i.checked_sub(1),
228 _ => break,
229 }
230 }
231 q
232}
233
234/// Whether the clusters running back from `q` are a number followed by any number of symbols and
235/// separators, the `NU (SY | IS)*` of rule LB25.
236fn numeric_run(cls: &[Cl], q: usize) -> bool {
237 match skip_back(cls, q, &[L::SY, L::IS]) {
238 Some(i) => cl(cls, Some(i)) == Some(L::NU),
239 None => false,
240 }
241}
242
243/// Returns the number of regional indicator clusters running back from `q`, inclusive.
244fn regional_run(cls: &[Cl], q: usize) -> usize {
245 let mut n = 0;
246 let mut i = Some(q);
247 while let Some(j) = i {
248 match cls.get(j) {
249 Some(c) if c.cls == L::RI => {
250 n += 1;
251 i = j.checked_sub(1);
252 },
253 _ => break,
254 }
255 }
256 n
257}
258
259/// Whether a line may or must end before the character at `i`, by the rules of UAX #14, taken in
260/// order. `None` means it may not.
261fn rule(chs: &[Ch], cls: &[Cl], i: usize) -> Option<Break> {
262
263 let (a, b) = match (chs.get(i - 1), chs.get(i)) {
264 (Some(a), Some(b)) => (a, b),
265 _ => return Some(Break::Mandatory),
266 };
267
268 // LB4, LB5. A mandatory break follows a hard line break, and a carriage return keeps its line
269 // feed.
270 if a.cls == L::BK {
271 return Some(Break::Mandatory);
272 }
273 if a.cls == L::CR && b.cls == L::LF {
274 return None;
275 }
276 if matches!(a.cls, L::CR | L::LF | L::NL) {
277 return Some(Break::Mandatory);
278 }
279
280 // LB6, LB7. Nothing breaks before a hard line break, a space or a zero width space.
281 if matches!(b.cls, L::BK | L::CR | L::LF | L::NL) {
282 return None;
283 }
284 if matches!(b.cls, L::SP | L::ZW) {
285 return None;
286 }
287
288 // LB8. A zero width space breaks after, even across the spaces that follow it.
289 let mut j = i - 1;
290 while j > 0 && chs[j].cls == L::SP {
291 j -= 1;
292 }
293 if chs[j].cls == L::ZW {
294 return Some(Break::Optional);
295 }
296
297 // LB8a. A zero width joiner holds on to what follows it.
298 if a.cls == L::ZWJ {
299 return None;
300 }
301
302 // LB9. A combining mark is part of the character it follows.
303 if folds(chs, i) {
304 return None;
305 }
306
307 // The remaining rules read clusters. `q` is the cluster beginning at `i`, `p` the one before
308 // it, `o` the one before that, and `r` and `t` the ones after `q`.
309 let q = match cluster_at(cls, i) {
310 Some(q) => q,
311 None => return None,
312 };
313 let p = match q.checked_sub(1) {
314 Some(p) => p,
315 None => return None,
316 };
317 let o = p.checked_sub(1);
318 let r = Some(q + 1);
319 let t = Some(q + 2);
320
321 let (ca, cb) = (cl(cls, Some(p)), cl(cls, Some(q)));
322 let (co, cr) = (cl(cls, o), cl(cls, r));
323 let ct = cl(cls, t);
324
325 let is = |c: Option<L>, set: &[L]| -> bool {
326 match c {
327 Some(c) => set.contains(&c),
328 None => false,
329 }
330 };
331
332 // LB11. A word joiner binds on both sides.
333 if cb == Some(L::WJ) || ca == Some(L::WJ) {
334 return None;
335 }
336
337 // LB12, LB12a. Non-breaking glue binds on both sides, except after a space or a hyphen.
338 if ca == Some(L::GL) {
339 return None;
340 }
341 if !is(ca, &[L::SP, L::BA, L::HY, L::HH]) && cb == Some(L::GL) {
342 return None;
343 }
344
345 // LB13. Nothing breaks before a closing bracket or the punctuation that clings to a word.
346 if is(cb, &[L::EX, L::CL, L::CP, L::SY]) {
347 return None;
348 }
349
350 // LB14. An opening bracket holds on to what follows it, across any spaces.
351 if cl(cls, skip_back(cls, p, &[L::SP])) == Some(L::OP) {
352 return None;
353 }
354
355 // LB15a, LB15b. An opening quotation mark holds on to what follows it, and a closing one to
356 // what precedes it.
357 if let Some(k) = skip_back(cls, p, &[L::SP]) {
358 if cl(cls, Some(k)) == Some(L::QU) && has(cls, Some(k), FLAG_PI) {
359 let before = k.checked_sub(1);
360 if before.is_none()
361 || is(cl(cls, before), &[L::BK, L::CR, L::LF, L::NL, L::OP, L::QU, L::GL, L::SP,
362 L::ZW])
363 {
364 return None;
365 }
366 }
367 }
368 if cb == Some(L::QU) && has(cls, Some(q), FLAG_PF) {
369 if cr.is_none()
370 || is(cr, &[L::SP, L::GL, L::WJ, L::CL, L::QU, L::CP, L::EX, L::IS, L::SY, L::BK,
371 L::CR, L::LF, L::NL, L::ZW])
372 {
373 return None;
374 }
375 }
376
377 // LB15c, LB15d. A separator that begins a number breaks after a space, but otherwise binds.
378 if ca == Some(L::SP) && cb == Some(L::IS) && cr == Some(L::NU) {
379 return Some(Break::Optional);
380 }
381 if cb == Some(L::IS) {
382 return None;
383 }
384
385 // LB16, LB17. A nonstarter clings to the bracket before it, and an em dash to an em dash.
386 if cb == Some(L::NS) && is(cl(cls, skip_back(cls, p, &[L::SP])), &[L::CL, L::CP]) {
387 return None;
388 }
389 if cb == Some(L::B2) && cl(cls, skip_back(cls, p, &[L::SP])) == Some(L::B2) {
390 return None;
391 }
392
393 // LB18. A space breaks after.
394 if ca == Some(L::SP) {
395 return Some(Break::Optional);
396 }
397
398 // LB19, LB19a. Quotation marks bind, except where an East Asian character makes the side
399 // unambiguous.
400 if cb == Some(L::QU) && !has(cls, Some(q), FLAG_PI) {
401 return None;
402 }
403 if ca == Some(L::QU) && !has(cls, Some(p), FLAG_PF) {
404 return None;
405 }
406 if !ea(cls, Some(p)) && cb == Some(L::QU) {
407 return None;
408 }
409 if cb == Some(L::QU) && (cr.is_none() || !ea(cls, r)) {
410 return None;
411 }
412 if ca == Some(L::QU) && !ea(cls, Some(q)) {
413 return None;
414 }
415 if ca == Some(L::QU) && (o.is_none() || !ea(cls, o)) {
416 return None;
417 }
418
419 // LB20. A contingent break breaks on both sides.
420 if cb == Some(L::CB) || ca == Some(L::CB) {
421 return Some(Break::Optional);
422 }
423
424 // LB20a. A hyphen that begins a word holds on to it.
425 if is(ca, &[L::HY, L::HH]) && is(cb, &[L::AL, L::HL])
426 && (o.is_none()
427 || is(cl(cls, o), &[L::BK, L::CR, L::LF, L::NL, L::SP, L::ZW, L::CB, L::GL]))
428 {
429 return None;
430 }
431
432 // LB21, LB21a, LB21b. A break clings to the character before a hyphen, and to a Hebrew letter.
433 if is(cb, &[L::BA, L::HH, L::HY, L::NS]) || ca == Some(L::BB) {
434 return None;
435 }
436 if is(ca, &[L::HY, L::HH]) && co == Some(L::HL) && cb != Some(L::HL) {
437 return None;
438 }
439 if ca == Some(L::SY) && cb == Some(L::HL) {
440 return None;
441 }
442
443 // LB22. Nothing breaks before an inseparable character, such as an ellipsis.
444 if cb == Some(L::IN) {
445 return None;
446 }
447
448 // LB23, LB23a. Letters and numbers bind to each other, as do numeric prefixes and ideographs.
449 if is(ca, &[L::AL, L::HL]) && cb == Some(L::NU) {
450 return None;
451 }
452 if ca == Some(L::NU) && is(cb, &[L::AL, L::HL]) {
453 return None;
454 }
455 if ca == Some(L::PR) && is(cb, &[L::ID, L::EB, L::EM]) {
456 return None;
457 }
458 if is(ca, &[L::ID, L::EB, L::EM]) && cb == Some(L::PO) {
459 return None;
460 }
461
462 // LB24. A numeric prefix or postfix binds to a letter.
463 if is(ca, &[L::PR, L::PO]) && is(cb, &[L::AL, L::HL]) {
464 return None;
465 }
466 if is(ca, &[L::AL, L::HL]) && is(cb, &[L::PR, L::PO]) {
467 return None;
468 }
469
470 // LB25. A number does not break apart, and holds on to the currency and percent signs around
471 // it.
472 if is(ca, &[L::CL, L::CP]) && is(cb, &[L::PO, L::PR]) {
473 if let Some(k) = p.checked_sub(1) {
474 if numeric_run(cls, k) {
475 return None;
476 }
477 }
478 }
479 if is(cb, &[L::PO, L::PR]) && numeric_run(cls, p) {
480 return None;
481 }
482 if is(ca, &[L::PO, L::PR]) && cb == Some(L::OP) && cr == Some(L::NU) {
483 return None;
484 }
485 if is(ca, &[L::PO, L::PR]) && cb == Some(L::OP) && cr == Some(L::IS) && ct == Some(L::NU) {
486 return None;
487 }
488 if is(ca, &[L::PO, L::PR, L::HY, L::IS]) && cb == Some(L::NU) {
489 return None;
490 }
491 if cb == Some(L::NU) && numeric_run(cls, p) {
492 return None;
493 }
494
495 // LB26, LB27. A Hangul syllable does not break apart, and binds to the numeric affixes.
496 if ca == Some(L::JL) && is(cb, &[L::JL, L::JV, L::H2, L::H3]) {
497 return None;
498 }
499 if is(ca, &[L::JV, L::H2]) && is(cb, &[L::JV, L::JT]) {
500 return None;
501 }
502 if is(ca, &[L::JT, L::H3]) && cb == Some(L::JT) {
503 return None;
504 }
505 if is(ca, &[L::JL, L::JV, L::JT, L::H2, L::H3]) && cb == Some(L::PO) {
506 return None;
507 }
508 if ca == Some(L::PR) && is(cb, &[L::JL, L::JV, L::JT, L::H2, L::H3]) {
509 return None;
510 }
511
512 // LB28. Letters bind to letters.
513 if is(ca, &[L::AL, L::HL]) && is(cb, &[L::AL, L::HL]) {
514 return None;
515 }
516
517 // LB28a. A Brahmic orthographic syllable does not break apart.
518 if ca == Some(L::AP) && aksara(cls, Some(q)) {
519 return None;
520 }
521 if aksara(cls, Some(p)) && is(cb, &[L::VF, L::VI]) {
522 return None;
523 }
524 if ca == Some(L::VI) && aksara(cls, o) && (cb == Some(L::AK) || has_dot(cls, Some(q))) {
525 return None;
526 }
527 if aksara(cls, Some(p)) && aksara(cls, Some(q)) && cr == Some(L::VF) {
528 return None;
529 }
530
531 // LB29. A numeric separator binds to the letter after it.
532 if ca == Some(L::IS) && is(cb, &[L::AL, L::HL]) {
533 return None;
534 }
535
536 // LB30. A letter or number binds to the narrow bracket beside it.
537 if is(ca, &[L::AL, L::HL, L::NU]) && cb == Some(L::OP) && !ea(cls, Some(q)) {
538 return None;
539 }
540 if ca == Some(L::CP) && !ea(cls, Some(p)) && is(cb, &[L::AL, L::HL, L::NU]) {
541 return None;
542 }
543
544 // LB30a. Regional indicators pair up into flags, so a break falls between pairs.
545 if ca == Some(L::RI) && cb == Some(L::RI) {
546 if regional_run(cls, p) % 2 == 1 {
547 return None;
548 }
549 return Some(Break::Optional);
550 }
551
552 // LB30b. An emoji keeps its modifier.
553 if ca == Some(L::EB) && cb == Some(L::EM) {
554 return None;
555 }
556 if has(cls, Some(p), FLAG_EXT_PICT_UNASSIGNED) && cb == Some(L::EM) {
557 return None;
558 }
559
560 // LB31.
561 Some(Break::Optional)
562}
563
564/// Whether cluster `q` is the dotted circle.
565fn has_dot(cls: &[Cl], q: Option<usize>) -> bool {
566 match q.and_then(|q| cls.get(q)) {
567 Some(c) => c.dot,
568 None => false,
569 }
570}