Oregami
Repositories/oxedyne/fe2o3

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

17.2 KiB, 5 runs

created by r1870400018:13908, 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//! Grapheme cluster and word segmentation, following UAX #29.
2//!
3//! An extended grapheme cluster is what a reader calls a character, and so it is what a cursor
4//! should step over and what a selection should snap to. A word boundary is coarser, and is what a
5//! double click should select.
6//!
7//! Both functions return byte offsets into the string, including zero and its length, so that
8//! `s[b[i]..b[i + 1]]` is always a valid slice.
9//!
10//! ```
11//! use oxedyne_fe2o3_text::unicode::segment;
12//!
13//! // A base and its mark are one cluster, and a flag is one cluster.
14//! let s = "e\u{0301}\u{1F1E6}\u{1F1FA}";
15//! assert_eq!(segment::graphemes(s), vec!["e\u{0301}", "\u{1F1E6}\u{1F1FA}"]);
16//! ```
17
18use crate::unicode::{
19 lookup::{
20 self,
21 Partitioned,
22 },
23 prop::{
24 ConjunctBreak,
25 GraphemeClass as G,
26 WordClass as W,
27 },
28 tables::seg::{
29 SEG_FLAG_STARTS,
30 SEG_FLAG_VALS,
31 },
32};
33
34/// Bit in the segmentation flags marking Extended_Pictographic.
35const FLAG_EXT_PICT: u8 = 1 << 0;
36/// Shift of the two bit Indic_Conjunct_Break field in the segmentation flags.
37const INCB_SHIFT: u8 = 1;
38
39/// Whether `c` has the Extended_Pictographic property, which is to say whether it is an emoji or
40/// could become one.
41pub fn is_extended_pictographic(c: char) -> bool {
42 flags(c) & FLAG_EXT_PICT != 0
43}
44
45/// Returns the Indic_Conjunct_Break property of `c`.
46pub fn conjunct_break(c: char) -> ConjunctBreak {
47 match (flags(c) >> INCB_SHIFT) & 0b11 {
48 1 => ConjunctBreak::Consonant,
49 2 => ConjunctBreak::Extend,
50 3 => ConjunctBreak::Linker,
51 _ => ConjunctBreak::None,
52 }
53}
54
55/// Returns the segmentation flags of `c`.
56fn flags(c: char) -> u8 {
57 lookup::flags(&SEG_FLAG_STARTS, &SEG_FLAG_VALS, c)
58}
59
60/// A character with everything the segmentation rules ask of it.
61struct Ch {
62 /// The byte offset of the character in the string.
63 byte: usize,
64 /// The Grapheme_Cluster_Break class.
65 gcb: G,
66 /// The Word_Break class.
67 wb: W,
68 /// The Indic_Conjunct_Break class.
69 incb: ConjunctBreak,
70 /// Whether the character is Extended_Pictographic.
71 pict: bool,
72}
73
74/// Reads a string into the per character state the rules work over.
75fn scan(s: &str) -> Vec<Ch> {
76 let mut chs = Vec::with_capacity(s.len());
77 for (byte, c) in s.char_indices() {
78 chs.push(Ch {
79 byte,
80 gcb: G::of(c),
81 wb: W::of(c),
82 incb: conjunct_break(c),
83 pict: is_extended_pictographic(c),
84 });
85 }
86 chs
87}
88
89// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
90// │ Grapheme clusters │
91// └───────────────────────────────────────────────────────────────────────────────────────────┘
92
93/// Returns the byte offsets of the extended grapheme cluster boundaries of `s`, beginning with
94/// zero and ending with its length.
95pub fn grapheme_boundaries(s: &str) -> Vec<usize> {
96
97 let mut out = vec![0];
98 if s.is_empty() {
99 return out;
100 }
101 let chs = scan(s);
102
103 for i in 1..chs.len() {
104 if grapheme_break(&chs, i) {
105 out.push(chs[i].byte);
106 }
107 }
108 out.push(s.len());
109 out
110}
111
112/// Returns the extended grapheme clusters of `s`.
113pub fn graphemes(s: &str) -> Vec<&str> {
114 let bounds = grapheme_boundaries(s);
115 let mut out = Vec::with_capacity(bounds.len().saturating_sub(1));
116 for w in bounds.windows(2) {
117 if let (Some(a), Some(b)) = (w.first(), w.get(1)) {
118 if let Some(part) = s.get(*a..*b) {
119 out.push(part);
120 }
121 }
122 }
123 out
124}
125
126/// Returns the byte offset of the grapheme cluster boundary at or after `from`, which is the
127/// string length once there is nothing left. This is where a cursor moving right should land.
128pub fn next_grapheme(s: &str, from: usize) -> usize {
129 for b in grapheme_boundaries(s) {
130 if b > from {
131 return b;
132 }
133 }
134 s.len()
135}
136
137/// Returns the byte offset of the grapheme cluster boundary before `from`, which is zero once
138/// there is nothing left. This is where a cursor moving left should land.
139pub fn prev_grapheme(s: &str, from: usize) -> usize {
140 let mut prev = 0;
141 for b in grapheme_boundaries(s) {
142 if b >= from {
143 break;
144 }
145 prev = b;
146 }
147 prev
148}
149
150/// Whether `at` is a grapheme cluster boundary, which is where a cursor is allowed to be. A cursor
151/// anywhere else sits inside a character, which is a corruption rather than a position.
152pub fn is_grapheme_boundary(s: &str, at: usize) -> bool {
153 if at == 0 || at == s.len() {
154 return true;
155 }
156 grapheme_boundaries(s).contains(&at)
157}
158
159/// Returns the byte offset of the grapheme cluster boundary at or after `from` that is nearest to
160/// it, snapping a cursor onto the character grid it must sit on.
161pub fn snap_grapheme(s: &str, at: usize) -> usize {
162 let at = at.min(s.len());
163 let mut best = 0;
164 for b in grapheme_boundaries(s) {
165 if b == at {
166 return at;
167 }
168 // The boundaries come in order, so the last one below `at` and the first one above it are
169 // the only two candidates, and the nearer of those two wins.
170 if b < at {
171 best = b;
172 } else {
173 return if at - best <= b - at { best } else { b };
174 }
175 }
176 best
177}
178
179/// Returns the byte offset of the word boundary after `from`, which is the string length once there
180/// is nothing left. This is where a cursor moving a word to the right should land.
181///
182/// A word boundary is UAX #29's, so an apostrophe does not break `don't` and a full stop does not
183/// break `3.14`.
184pub fn next_word(s: &str, from: usize) -> usize {
185 for b in word_boundaries(s) {
186 if b > from {
187 return b;
188 }
189 }
190 s.len()
191}
192
193/// Returns the byte offset of the word boundary before `from`, which is zero once there is nothing
194/// left. This is where a cursor moving a word to the left should land.
195pub fn prev_word(s: &str, from: usize) -> usize {
196 let mut prev = 0;
197 for b in word_boundaries(s) {
198 if b >= from {
199 break;
200 }
201 prev = b;
202 }
203 prev
204}
205
206/// Whether there is a grapheme cluster boundary before the character at `i`, by the rules of
207/// UAX #29, taken in order.
208fn grapheme_break(chs: &[Ch], i: usize) -> bool {
209
210 let (a, b) = match (chs.get(i - 1), chs.get(i)) {
211 (Some(a), Some(b)) => (a, b),
212 _ => return true,
213 };
214
215 // GB3, GB4, GB5. A CR and its LF stay together; nothing else joins a control.
216 if a.gcb == G::CR && b.gcb == G::LF {
217 return false;
218 }
219 if matches!(a.gcb, G::Control | G::CR | G::LF) {
220 return true;
221 }
222 if matches!(b.gcb, G::Control | G::CR | G::LF) {
223 return true;
224 }
225
226 // GB6, GB7, GB8. A Hangul syllable holds together.
227 if a.gcb == G::L && matches!(b.gcb, G::L | G::V | G::LV | G::LVT) {
228 return false;
229 }
230 if matches!(a.gcb, G::LV | G::V) && matches!(b.gcb, G::V | G::T) {
231 return false;
232 }
233 if matches!(a.gcb, G::LVT | G::T) && b.gcb == G::T {
234 return false;
235 }
236
237 // GB9, GB9a, GB9b.
238 if matches!(b.gcb, G::Extend | G::ZWJ) {
239 return false;
240 }
241 if b.gcb == G::SpacingMark {
242 return false;
243 }
244 if a.gcb == G::Prepend {
245 return false;
246 }
247
248 // GB9c. An Indic conjunct, that is a consonant joined to a consonant by a virama, is one
249 // cluster.
250 if b.incb == ConjunctBreak::Consonant && conjunct_before(chs, i) {
251 return false;
252 }
253
254 // GB11. An emoji joined to an emoji by a zero width joiner is one cluster.
255 if a.gcb == G::ZWJ && b.pict && pictographic_before(chs, i - 1) {
256 return false;
257 }
258
259 // GB12, GB13. Regional indicators pair up into flags, so a break falls between pairs.
260 if a.gcb == G::RegionalIndicator && b.gcb == G::RegionalIndicator {
261 return regional_run(chs, i - 1) % 2 == 0;
262 }
263
264 // GB999.
265 true
266}
267
268/// Whether the characters before `i` are a linking consonant, then extenders including at least
269/// one linker, as grapheme rule GB9c requires.
270fn conjunct_before(chs: &[Ch], i: usize) -> bool {
271 let mut j = i;
272 let mut linked = false;
273 while j > 0 {
274 match chs.get(j - 1) {
275 Some(ch) => match ch.incb {
276 ConjunctBreak::Linker => {
277 linked = true;
278 j -= 1;
279 },
280 ConjunctBreak::Extend => j -= 1,
281 ConjunctBreak::Consonant => return linked,
282 ConjunctBreak::None => return false,
283 },
284 None => return false,
285 }
286 }
287 false
288}
289
290/// Whether the character at `i` is a zero width joiner preceded by an Extended_Pictographic
291/// character and any number of extenders, as grapheme rule GB11 requires.
292fn pictographic_before(chs: &[Ch], i: usize) -> bool {
293 let mut j = i;
294 while j > 0 {
295 match chs.get(j - 1) {
296 Some(ch) if ch.gcb == G::Extend => j -= 1,
297 Some(ch) => return ch.pict,
298 None => return false,
299 }
300 }
301 false
302}
303
304/// Returns the number of regional indicators running back from `i`, inclusive.
305fn regional_run(chs: &[Ch], i: usize) -> usize {
306 let mut n = 0;
307 let mut j = i + 1;
308 while j > 0 {
309 match chs.get(j - 1) {
310 Some(ch) if ch.gcb == G::RegionalIndicator => {
311 n += 1;
312 j -= 1;
313 },
314 _ => break,
315 }
316 }
317 n
318}
319
320// ┌───────────────────────────────────────────────────────────────────────────────────────────┐
321// │ Words │
322// └───────────────────────────────────────────────────────────────────────────────────────────┘
323
324/// Returns the byte offsets of the word boundaries of `s`, beginning with zero and ending with its
325/// length. The spans between them include the spaces and punctuation as well as the words.
326pub fn word_boundaries(s: &str) -> Vec<usize> {
327
328 let mut out = vec![0];
329 if s.is_empty() {
330 return out;
331 }
332 let chs = scan(s);
333
334 // Rule WB4 folds extenders into the character they follow, so the later rules see a sequence of
335 // clusters rather than of characters. `base[i]` is the index of the character that begins the
336 // cluster holding character `i`, and `next[i]` the index of the cluster after it.
337 let (base, next) = word_clusters(&chs);
338
339 for i in 1..chs.len() {
340 if word_break(&chs, &base, &next, i) {
341 out.push(chs[i].byte);
342 }
343 }
344 out.push(s.len());
345 out
346}
347
348/// Returns the words and the spans between them, in order.
349pub fn words(s: &str) -> Vec<&str> {
350 let bounds = word_boundaries(s);
351 let mut out = Vec::with_capacity(bounds.len().saturating_sub(1));
352 for w in bounds.windows(2) {
353 if let (Some(a), Some(b)) = (w.first(), w.get(1)) {
354 if let Some(part) = s.get(*a..*b) {
355 out.push(part);
356 }
357 }
358 }
359 out
360}
361
362/// Whether the character at `i` extends the one before it, under word rule WB4.
363fn extends(chs: &[Ch], i: usize) -> bool {
364 let (a, b) = match (chs.get(i.wrapping_sub(1)), chs.get(i)) {
365 (Some(a), Some(b)) => (a, b),
366 _ => return false,
367 };
368 if !matches!(b.wb, W::Extend | W::Format | W::ZWJ) {
369 return false;
370 }
371 !matches!(a.wb, W::CR | W::LF | W::Newline)
372}
373
374/// Groups the characters into the clusters that word rule WB4 leaves behind, returning the first
375/// character of the cluster holding each character, and the first character of the cluster after
376/// it.
377fn word_clusters(chs: &[Ch]) -> (Vec<usize>, Vec<usize>) {
378
379 let n = chs.len();
380 let mut base = vec![0usize; n];
381 let mut next = vec![n; n];
382
383 let mut start = 0;
384 for i in 0..n {
385 if i > 0 && !extends(chs, i) {
386 start = i;
387 }
388 base[i] = start;
389 }
390 for i in 0..n {
391 let mut j = base[i] + 1;
392 while j < n && base[j] != j {
393 j += 1;
394 }
395 next[i] = j;
396 }
397
398 (base, next)
399}
400
401/// The Word_Break class of the cluster beginning at `i`, or `None` past the end of the text.
402fn wcls(chs: &[Ch], i: usize) -> Option<W> {
403 chs.get(i).map(|ch| ch.wb)
404}
405
406/// Whether `w` is a letter that takes part in words, the AHLetter of UAX #29.
407fn is_ah(w: Option<W>) -> bool {
408 matches!(w, Some(W::ALetter) | Some(W::HebrewLetter))
409}
410
411/// Whether `w` may appear inside a word or a number, the MidNumLetQ of UAX #29.
412fn is_midnumlet(w: Option<W>) -> bool {
413 matches!(w, Some(W::MidNumLet) | Some(W::SingleQuote))
414}
415
416/// Whether there is a word boundary before the character at `i`, by the rules of UAX #29, taken in
417/// order.
418fn word_break(chs: &[Ch], base: &[usize], next: &[usize], i: usize) -> bool {
419
420 let (a, b) = match (chs.get(i - 1), chs.get(i)) {
421 (Some(a), Some(b)) => (a, b),
422 _ => return true,
423 };
424
425 // WB3, WB3a, WB3b. A CR and its LF stay together; nothing else joins a newline.
426 if a.wb == W::CR && b.wb == W::LF {
427 return false;
428 }
429 if matches!(a.wb, W::Newline | W::CR | W::LF) {
430 return true;
431 }
432 if matches!(b.wb, W::Newline | W::CR | W::LF) {
433 return true;
434 }
435
436 // WB3c. A zero width joiner holds an emoji to what follows it.
437 if a.wb == W::ZWJ && b.pict {
438 return false;
439 }
440
441 // WB3d. Spaces that segment words stay with each other.
442 if a.wb == W::WSegSpace && b.wb == W::WSegSpace {
443 return false;
444 }
445
446 // WB4. An extender or format character joins the cluster before it.
447 if extends(chs, i) {
448 return false;
449 }
450
451 // The remaining rules read clusters rather than characters: `p` begins the cluster before the
452 // boundary, `q` begins the one after, `o` the one before `p`, and `r` the one after `q`.
453 let q = i;
454 let p = base[i - 1];
455 let o = if p == 0 { None } else { Some(base[p - 1]) };
456 let r = lookup::get(next, q, chs.len());
457
458 let ca = wcls(chs, p);
459 let cb = wcls(chs, q);
460 let co = o.and_then(|o| wcls(chs, o));
461 let cr = wcls(chs, r);
462
463 // WB5, WB6, WB7. Letters hold together, across at most one character that lives inside a word.
464 if is_ah(ca) && is_ah(cb) {
465 return false;
466 }
467 if is_ah(ca) && (cb == Some(W::MidLetter) || is_midnumlet(cb)) && is_ah(cr) {
468 return false;
469 }
470 if is_ah(co) && (ca == Some(W::MidLetter) || is_midnumlet(ca)) && is_ah(cb) {
471 return false;
472 }
473
474 // WB7a, WB7b, WB7c. Hebrew keeps its quotation marks.
475 if ca == Some(W::HebrewLetter) && cb == Some(W::SingleQuote) {
476 return false;
477 }
478 if ca == Some(W::HebrewLetter) && cb == Some(W::DoubleQuote)
479 && cr == Some(W::HebrewLetter)
480 {
481 return false;
482 }
483 if co == Some(W::HebrewLetter) && ca == Some(W::DoubleQuote)
484 && cb == Some(W::HebrewLetter)
485 {
486 return false;
487 }
488
489 // WB8, WB9, WB10, WB11, WB12. Numbers hold together, and hold on to the letters beside them.
490 if ca == Some(W::Numeric) && cb == Some(W::Numeric) {
491 return false;
492 }
493 if is_ah(ca) && cb == Some(W::Numeric) {
494 return false;
495 }
496 if ca == Some(W::Numeric) && is_ah(cb) {
497 return false;
498 }
499 if co == Some(W::Numeric) && (ca == Some(W::MidNum) || is_midnumlet(ca))
500 && cb == Some(W::Numeric)
501 {
502 return false;
503 }
504 if ca == Some(W::Numeric) && (cb == Some(W::MidNum) || is_midnumlet(cb))
505 && cr == Some(W::Numeric)
506 {
507 return false;
508 }
509
510 // WB13, WB13a, WB13b. Katakana holds together, and an underscore or the like joins what it
511 // sits between.
512 if ca == Some(W::Katakana) && cb == Some(W::Katakana) {
513 return false;
514 }
515 if (is_ah(ca) || matches!(ca, Some(W::Numeric) | Some(W::Katakana) | Some(W::ExtendNumLet)))
516 && cb == Some(W::ExtendNumLet)
517 {
518 return false;
519 }
520 if ca == Some(W::ExtendNumLet)
521 && (is_ah(cb) || matches!(cb, Some(W::Numeric) | Some(W::Katakana)))
522 {
523 return false;
524 }
525
526 // WB15, WB16. Regional indicators pair up into flags.
527 if ca == Some(W::RegionalIndicator) && cb == Some(W::RegionalIndicator) {
528 return word_regional_run(chs, base, p) % 2 == 0;
529 }
530
531 // WB999.
532 true
533}
534
535/// Returns the number of regional indicator clusters running back from the one beginning at `p`,
536/// inclusive.
537fn word_regional_run(chs: &[Ch], base: &[usize], p: usize) -> usize {
538 let mut n = 0;
539 let mut j = Some(p);
540 while let Some(k) = j {
541 match chs.get(k) {
542 Some(ch) if ch.wb == W::RegionalIndicator => {
543 n += 1;
544 j = if k == 0 { None } else { Some(lookup::get(base, k - 1, 0)) };
545 },
546 _ => break,
547 }
548 }
549 n
550}
551
552#[cfg(test)]
553mod tests {
554 use super::*;
555 use oxedyne_fe2o3_core::prelude::*;
556
557 /// A cursor moves by character, and a character is a grapheme cluster: the acute and the letter
558 /// it sits on are one press of an arrow key, not two.
559 #[test]
560 fn test_a_cursor_steps_over_a_combining_mark_00() -> Outcome<()> {
561 let s = "e\u{301}f"; // e + combining acute, then f.
562 assert_eq!(next_grapheme(s, 0), 3);
563 assert_eq!(prev_grapheme(s, 3), 0);
564 Ok(())
565 }
566
567 /// Word movement lands on UAX #29's boundaries, so an apostrophe does not split a word.
568 #[test]
569 fn test_word_movement_keeps_a_contraction_whole_01() -> Outcome<()> {
570 let s = "don't stop";
571 // The word runs to its end rather than breaking at the apostrophe.
572 assert_eq!(next_word(s, 0), 5);
573 assert_eq!(prev_word(s, 10), 6);
574 Ok(())
575 }
576
577 /// A cursor offset that fell inside a character is snapped back onto the character grid.
578 #[test]
579 fn test_an_offset_inside_a_character_snaps_to_a_boundary_02() -> Outcome<()> {
580 let s = "e\u{301}f";
581 assert!(!is_grapheme_boundary(s, 1)); // Inside the cluster.
582 assert!(is_grapheme_boundary(s, 0));
583 assert!(is_grapheme_boundary(s, 3));
584 assert_eq!(snap_grapheme(s, 1), 0); // Nearer the start of the cluster.
585 assert_eq!(snap_grapheme(s, 2), 3); // Nearer its end.
586 Ok(())
587 }
588
589 /// The ends of the string are boundaries, and movement stops at them rather than running off.
590 #[test]
591 fn test_movement_stops_at_the_ends_03() -> Outcome<()> {
592 let s = "ab";
593 assert_eq!(next_grapheme(s, 2), 2);
594 assert_eq!(prev_grapheme(s, 0), 0);
595 assert_eq!(next_word(s, 2), 2);
596 assert_eq!(prev_word(s, 0), 0);
597 Ok(())
598 }
599}