fast_grapheme_segmenter/lib.rs
1//! Fast, lightweight, forward-only segmentation into Unicode extended grapheme clusters,
2//! as defined by [UAX #29](https://www.unicode.org/reports/tr29/).
3//!
4//! This crate does one thing: iterate extended grapheme clusters from the
5//! start of a string towards the end, as fast as the rules allow.
6//!
7//! - Unicode 17.0, follow up-to-date standard.
8//! - Extended grapheme clusters only. GB9a, GB9b and GB9c always apply.
9//! - `no_std`, no `unsafe`, zero dependencies.
10//! - Only ~19 KB of generated tables
11//!
12//! It is a Rust port of the [unicode-segmenter](https://github.com/cometkim/unicode-segmenter),
13//! the JavaScript library this algorithm was originally developed for,
14//! replicating the [`Intl.Segmenter`](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Intl/Segmenter) behavior.
15//!
16//! And it's highly optmized for simple foward segmentation and counting grapheme clusters in a given text.
17//!
18//! # Examples
19//!
20//! ```
21//! use fast_grapheme_segmenter::graphemes;
22//!
23//! let text = "a๐ฐ๐ทb";
24//! let clusters: Vec<&str> = graphemes(text).collect();
25//! assert_eq!(clusters, ["a", "๐ฐ๐ท", "b"]);
26//! ```
27//!
28//! Byte offsets of each cluster:
29//!
30//! ```
31//! use fast_grapheme_segmenter::grapheme_indices;
32//!
33//! let text = "a๐ฐ๐ทb";
34//! let offsets: Vec<usize> = grapheme_indices(text).map(|(i, _)| i).collect();
35//! assert_eq!(offsets, [0, 1, 9]);
36//! ```
37//!
38//! Or just the offsets, without slicing the clusters out:
39//!
40//! ```
41//! use fast_grapheme_segmenter::grapheme_boundaries;
42//!
43//! let offsets: Vec<usize> = grapheme_boundaries("a๐ฐ๐ทb").collect();
44//! assert_eq!(offsets, [0, 1, 9]);
45//! ```
46//!
47//! Counting clusters, e.g. for a display-width-aware `strlen`:
48//!
49//! ```
50//! use fast_grapheme_segmenter::count_graphemes;
51//!
52//! assert_eq!(count_graphemes("๐ณ๏ธโ๐๐ฉโ๐ฉโ๐งโ๐ฆ"), 2);
53//! ```
54
55#![cfg_attr(not(test), no_std)]
56#![warn(missing_docs)]
57#![forbid(unsafe_code)]
58
59mod tables;
60
61use core::cmp;
62use core::str::CharIndices;
63use tables::GraphemeCat;
64
65/// The Unicode version whose data this crate's tables encode.
66pub const UNICODE_VERSION: (u8, u8, u8) = tables::UNICODE_VERSION;
67
68// Bits of the packed rule state, which summarises everything the boundary
69// rules can ask about the text preceding the cursor.
70//
71// It is a pure function of the codepoints consumed so far, so it carries
72// across cluster boundaries and needs no reset.
73//
74// The bits a rule can ask about are laid out so that each `PAIR_MASK` entry
75// selects exactly one of them, which turns every rule into a single
76// `state & mask == 0` test.
77
78/// Always set, so that a mask of `ALWAYS` means "never a boundary".
79const ALWAYS: u8 = 1 << 0;
80/// An odd run of `Regional_Indicator` immediately precedes (GB12, GB13).
81const RIS_ODD: u8 = 1 << 1;
82/// The last codepoint is a ZWJ that was preceded by `Extended_Pictographic Extend*` (GB11).
83const EMOJI_ZWJ: u8 = 1 << 2;
84/// The `InCB=Consonant` run in progress contains an `InCB=Linker` (GB9c).
85const INCB_LINKED: u8 = 1 << 3;
86/// `Extended_Pictographic Extend*` immediately precedes; feeds `EMOJI_ZWJ` on a ZWJ.
87const EXTPIC_RUN: u8 = 1 << 4;
88/// `InCB=Consonant [InCB=Extend InCB=Linker]*` precedes.
89const INCB_RUN: u8 = 1 << 5;
90
91/// Bits that survive consuming an `Extend`: the pictographic run that GB11
92/// allows `Extend*` to span.
93const EXTEND_KEEP: u8 = ALWAYS | EXTPIC_RUN;
94
95/// The state bit that decides the boundary verdict for a pair of categories.
96///
97/// A mask of `0` is an unconditional boundary (GB999 and friends)
98/// and can never match, while `ALWAYS` is unconditionally not a boundary.
99const fn pair_mask(before: GraphemeCat, after: GraphemeCat) -> u8 {
100 use GraphemeCat::*;
101 match (before, after) {
102 (GC_CR, GC_LF) => ALWAYS, // GB3
103 (GC_Control | GC_CR | GC_LF, _) => 0, // GB4
104 (_, GC_Control | GC_CR | GC_LF) => 0, // GB5
105 (GC_L, GC_L | GC_V | GC_LV | GC_LVT) => ALWAYS, // GB6
106 (GC_LV | GC_V, GC_V | GC_T) => ALWAYS, // GB7
107 (GC_LVT | GC_T, GC_T) => ALWAYS, // GB8
108 (_, GC_Extend | GC_ZWJ) => ALWAYS, // GB9
109 (_, GC_SpacingMark) => ALWAYS, // GB9a
110 (GC_Prepend, _) => ALWAYS, // GB9b
111 (_, GC_InCB_Consonant) => INCB_LINKED, // GB9c
112 (GC_ZWJ, GC_Extended_Pictographic) => EMOJI_ZWJ, // GB11
113 (GC_Regional_Indicator, GC_Regional_Indicator) => RIS_ODD, // GB12, GB13
114 (_, _) => 0, // GB999
115 }
116}
117
118/// Every pairwise rule evaluated at compile time,
119/// indexed by `(before as usize) << 4 | after as usize`.
120///
121/// There is a boundary between two codepoints exactly
122/// when the packed state and the pair's mask share no bit.
123const PAIR_MASK: [u8; 256] = {
124 let mut table = [0u8; 256];
125 let mut before = 0;
126 while before < 16 {
127 let mut after = 0;
128 while after < 16 {
129 table[before << 4 | after] = pair_mask(tables::CATS[before], tables::CATS[after]);
130 after += 1;
131 }
132 before += 1;
133 }
134 table
135};
136
137// The state machine works on raw category bytes, which is what the tables
138// hand back and what indexes `PAIR_MASK`, so the driver never widens them to the enum.
139
140const CAT_ANY: u8 = GraphemeCat::GC_Any as u8;
141const CAT_EXTEND: u8 = GraphemeCat::GC_Extend as u8;
142const CAT_PICTOGRAPHIC: u8 = GraphemeCat::GC_Extended_Pictographic as u8;
143const CAT_REGIONAL: u8 = GraphemeCat::GC_Regional_Indicator as u8;
144const CAT_ZWJ: u8 = GraphemeCat::GC_ZWJ as u8;
145const CAT_CONSONANT: u8 = GraphemeCat::GC_InCB_Consonant as u8;
146
147/// State transition on consuming an `Extend` that continues an `InCB=Consonant` run.
148///
149/// Split out of [`next_state`] because it is the only transition that has to
150/// look at the codepoint rather than just its category.
151#[inline]
152fn extend_in_incb_run(state: u8, ch: char) -> u8 {
153 if ch == '\u{200c}' {
154 // ZWNJ is `InCB=None`, so it ends the conjunct sequence.
155 state & EXTEND_KEEP
156 } else if state & INCB_LINKED != 0 || tables::is_incb_linker(ch) {
157 state & EXTEND_KEEP | INCB_LINKED | INCB_RUN
158 } else {
159 // `InCB=Extend`: the run continues but is still unlinked.
160 state & EXTEND_KEEP | INCB_RUN
161 }
162}
163
164/// The packed state after consuming `ch`, whose category is `cat`.
165#[inline(always)]
166fn next_state(state: u8, cat: u8, ch: char) -> u8 {
167 match cat {
168 CAT_EXTEND if state & INCB_RUN != 0 => extend_in_incb_run(state, ch),
169 CAT_EXTEND => state & EXTEND_KEEP,
170 CAT_PICTOGRAPHIC => ALWAYS | EXTPIC_RUN,
171 // Flip the parity of the run of regional indicators.
172 CAT_REGIONAL => (state & RIS_ODD) ^ (ALWAYS | RIS_ODD),
173 // A ZWJ arms GB11 if a pictographic run precedes it, and is itself `InCB=Extend`,
174 // so any conjunct sequence in progress carries on.
175 CAT_ZWJ => (state & EXTPIC_RUN) >> 2 | state & (ALWAYS | INCB_LINKED | INCB_RUN),
176 CAT_CONSONANT => ALWAYS | INCB_RUN,
177 // Nothing to remember: only the always-set bit remains.
178 _ => ALWAYS,
179 }
180}
181
182/// External iterator for a string's extended grapheme clusters.
183///
184/// Created with [`graphemes`] or [`GraphemeSegmentation::graphemes`].
185#[derive(Clone, Debug)]
186pub struct Graphemes<'a> {
187 driver: Driver<'a>,
188}
189
190impl<'a> Graphemes<'a> {
191 /// Create an iterator over the extended grapheme clusters of `s`.
192 #[must_use]
193 #[inline]
194 pub fn new(s: &'a str) -> Graphemes<'a> {
195 Graphemes {
196 driver: Driver::new(s),
197 }
198 }
199
200 /// The remaining, not yet segmented part of the original string.
201 #[must_use]
202 #[inline]
203 pub fn as_str(&self) -> &'a str {
204 &self.driver.string[self.driver.offset..]
205 }
206}
207
208impl<'a> Iterator for Graphemes<'a> {
209 type Item = &'a str;
210
211 #[inline]
212 fn size_hint(&self) -> (usize, Option<usize>) {
213 let remaining = self.driver.string.len() - self.driver.offset;
214 (cmp::min(remaining, 1), Some(remaining))
215 }
216
217 #[inline]
218 fn next(&mut self) -> Option<&'a str> {
219 let start = self.driver.offset;
220 if start == self.driver.string.len() {
221 return None;
222 }
223 let end = self.driver.next_boundary();
224 Some(&self.driver.string[start..end])
225 }
226
227 /// Counts by delegating to [`count_graphemes`], skipping the slicing
228 /// that feeding each cluster through [`Iterator::next`] would do.
229 ///
230 /// Restarting the count at the current offset is sound: a cluster head
231 /// re-establishes every packed state bit it depends on.
232 ///
233 /// The only rule that can carry context across a boundary pair is one whose head
234 /// category sets those bits itself, or the boundary went through a state-resetting Control.
235 ///
236 /// The randomized test below checks it.
237 #[inline]
238 fn count(self) -> usize {
239 count_graphemes(&self.driver.string[self.driver.offset..])
240 }
241}
242
243/// External iterator for a string's extended grapheme clusters and their byte offsets.
244///
245/// Created with [`grapheme_indices`] or [`GraphemeSegmentation::grapheme_indices`].
246#[derive(Clone, Debug)]
247pub struct GraphemeIndices<'a> {
248 start_offset: usize,
249 iter: Graphemes<'a>,
250}
251
252impl<'a> GraphemeIndices<'a> {
253 /// Create an iterator over the extended grapheme clusters of `s` with their byte offsets.
254 #[must_use]
255 #[inline]
256 pub fn new(s: &'a str) -> GraphemeIndices<'a> {
257 GraphemeIndices {
258 start_offset: 0,
259 iter: Graphemes::new(s),
260 }
261 }
262
263 /// The remaining, not yet segmented part of the original string.
264 #[must_use]
265 #[inline]
266 pub fn as_str(&self) -> &'a str {
267 self.iter.as_str()
268 }
269}
270
271impl<'a> Iterator for GraphemeIndices<'a> {
272 type Item = (usize, &'a str);
273
274 #[inline]
275 fn size_hint(&self) -> (usize, Option<usize>) {
276 self.iter.size_hint()
277 }
278
279 #[inline]
280 fn next(&mut self) -> Option<(usize, &'a str)> {
281 let pre_offset = self.start_offset;
282 let cluster = self.iter.next()?;
283 self.start_offset += cluster.len();
284 Some((pre_offset, cluster))
285 }
286
287 #[inline]
288 fn count(self) -> usize {
289 self.iter.count()
290 }
291}
292
293/// External iterator over the byte offsets at which a string's extended grapheme clusters start.
294///
295/// The same segmentation as [`graphemes`] without slicing the clusters out,
296/// which is what cursor motion and column arithmetic usually wants.
297///
298/// Created with [`grapheme_boundaries`] or [`GraphemeSegmentation::grapheme_boundaries`].
299#[derive(Clone, Debug)]
300pub struct GraphemeBoundaries<'a> {
301 driver: Driver<'a>,
302}
303
304impl<'a> GraphemeBoundaries<'a> {
305 /// Create an iterator over the byte offsets at which the extended grapheme clusters of `s` start.
306 #[must_use]
307 #[inline]
308 pub fn new(s: &'a str) -> GraphemeBoundaries<'a> {
309 GraphemeBoundaries {
310 driver: Driver::new(s),
311 }
312 }
313
314 /// The remaining, not yet segmented part of the original string.
315 #[must_use]
316 #[inline]
317 pub fn as_str(&self) -> &'a str {
318 &self.driver.string[self.driver.offset..]
319 }
320}
321
322impl<'a> Iterator for GraphemeBoundaries<'a> {
323 type Item = usize;
324
325 #[inline]
326 fn size_hint(&self) -> (usize, Option<usize>) {
327 let remaining = self.driver.string.len() - self.driver.offset;
328 (cmp::min(remaining, 1), Some(remaining))
329 }
330
331 #[inline]
332 fn next(&mut self) -> Option<usize> {
333 let start = self.driver.offset;
334 if start == self.driver.string.len() {
335 return None;
336 }
337 self.driver.next_boundary();
338 Some(start)
339 }
340
341 /// Counts by delegating to [`count_graphemes`],
342 /// skipping the boundary walk that feeding each offset through [`Iterator::next`] would do.
343 #[inline]
344 fn count(self) -> usize {
345 count_graphemes(&self.driver.string[self.driver.offset..])
346 }
347}
348
349/// Extension methods for segmenting a `str` into extended grapheme clusters.
350pub trait GraphemeSegmentation {
351 /// Iterate over the extended grapheme clusters.
352 ///
353 /// ```
354 /// use fast_grapheme_segmenter::GraphemeSegmentation;
355 ///
356 /// let mut clusters = "a\u{301}b".graphemes();
357 /// assert_eq!(clusters.next(), Some("a\u{301}"));
358 /// assert_eq!(clusters.next(), Some("b"));
359 /// assert_eq!(clusters.next(), None);
360 /// ```
361 fn graphemes(&self) -> Graphemes<'_>;
362
363 /// Iterate over the extended grapheme clusters with their byte offsets.
364 fn grapheme_indices(&self) -> GraphemeIndices<'_>;
365
366 /// Iterate over the byte offsets at which the extended grapheme clusters start,
367 /// without slicing the clusters out.
368 fn grapheme_boundaries(&self) -> GraphemeBoundaries<'_>;
369
370 /// Count the extended grapheme clusters.
371 fn count_graphemes(&self) -> usize;
372}
373
374impl GraphemeSegmentation for str {
375 #[inline]
376 fn graphemes(&self) -> Graphemes<'_> {
377 Graphemes::new(self)
378 }
379
380 #[inline]
381 fn grapheme_indices(&self) -> GraphemeIndices<'_> {
382 GraphemeIndices::new(self)
383 }
384
385 #[inline]
386 fn grapheme_boundaries(&self) -> GraphemeBoundaries<'_> {
387 GraphemeBoundaries::new(self)
388 }
389
390 #[inline]
391 fn count_graphemes(&self) -> usize {
392 count_graphemes(self)
393 }
394}
395
396/// Iterate over the extended grapheme clusters of a string.
397///
398/// ```
399/// use fast_grapheme_segmenter::graphemes;
400///
401/// assert_eq!(graphemes("๐ณ๏ธโ๐!").collect::<Vec<_>>(), ["๐ณ๏ธโ๐", "!"]);
402/// ```
403#[must_use]
404#[inline]
405pub fn graphemes(s: &str) -> Graphemes<'_> {
406 Graphemes::new(s)
407}
408
409/// Iterate over the extended grapheme clusters of a string with their byte offsets.
410///
411/// ```
412/// use fast_grapheme_segmenter::grapheme_indices;
413///
414/// let clusters = grapheme_indices("a๐ณ๏ธโ๐").collect::<Vec<_>>();
415/// assert_eq!(clusters, [(0, "a"), (1, "๐ณ๏ธโ๐")]);
416/// ```
417#[must_use]
418#[inline]
419pub fn grapheme_indices(s: &str) -> GraphemeIndices<'_> {
420 GraphemeIndices::new(s)
421}
422
423/// Iterate over the byte offsets at which the extended grapheme clusters of a string start,
424/// without slicing the clusters out.
425///
426/// ```
427/// use fast_grapheme_segmenter::grapheme_boundaries;
428///
429/// let offsets: Vec<usize> = grapheme_boundaries("a๐ฐ๐ทb").collect();
430/// assert_eq!(offsets, [0, 1, 9]);
431/// ```
432#[must_use]
433#[inline]
434pub fn grapheme_boundaries(s: &str) -> GraphemeBoundaries<'_> {
435 GraphemeBoundaries::new(s)
436}
437
438/// Decode the codepoint starting at UTF-16 code unit `i`.
439///
440/// Unpaired surrogates decode as U+FFFD, the replacement character, whose category is `Any`;
441/// The same policy icu4x applies to ill-formed input.
442///
443/// The caller guarantees `i < s.len()`;
444/// the return is the codepoint and the number of code units it occupies.
445#[inline]
446fn decode_utf16_at(s: &[u16], i: usize) -> (char, usize) {
447 match s[i] {
448 hi @ 0xD800..=0xDBFF => match s.get(i + 1) {
449 Some(0xDC00..=0xDFFF) => {
450 // Safe by construction: a high surrogate plus a low one.
451 let cp = 0x10000 + ((hi as u32 - 0xD800) << 10) + (s[i + 1] as u32 - 0xDC00);
452 (char::from_u32(cp).unwrap_or('\u{FFFD}'), 2)
453 }
454 _ => ('\u{FFFD}', 1),
455 },
456 0xDC00..=0xDFFF => ('\u{FFFD}', 1),
457 u => (char::from_u32(u as u32).unwrap_or('\u{FFFD}'), 1),
458 }
459}
460
461/// Count the extended grapheme clusters of a potentially ill-formed UTF-16 slice,
462/// as JavaScript and the `wasm32` targets store their strings.
463///
464/// Lone surrogates count as one cluster each, by way of U+FFFD.
465/// Offsets in the sibling functions are UTF-16 code units, not bytes.
466///
467/// ```
468/// use fast_grapheme_segmenter::count_graphemes_utf16;
469///
470/// // "๐ฐ๐ทa" - the flag is two surrogate pairs, then one BMP codepoint.
471/// let units: Vec<u16> = "๐ฐ๐ทa".encode_utf16().collect();
472/// assert_eq!(count_graphemes_utf16(&units), 2);
473/// ```
474#[must_use]
475pub fn count_graphemes_utf16(s: &[u16]) -> usize {
476 if s.is_empty() {
477 return 0;
478 }
479 let (first, mut i) = decode_utf16_at(s, 0);
480 let mut count = 1;
481 let mut cat_before = tables::grapheme_category_raw(first);
482 let mut state = next_state(ALWAYS, cat_before, first);
483
484 while i < s.len() {
485 let (ch, units) = decode_utf16_at(s, i);
486 let cat_after = tables::grapheme_category_raw(ch);
487 if state & PAIR_MASK[(cat_before as usize) << 4 | cat_after as usize] == 0 {
488 count += 1;
489 }
490 state = next_state(state, cat_after, ch);
491 cat_before = cat_after;
492 i += units;
493 }
494 count
495}
496
497/// External iterator over the UTF-16 code unit offsets at which the extended grapheme clusters of a slice start.
498///
499/// Created with [`grapheme_boundaries_utf16`].
500#[derive(Clone, Debug)]
501pub struct GraphemeBoundariesUtf16<'a> {
502 units: &'a [u16],
503 /// Code unit offset of the cluster whose start the next `next` yields.
504 pos: usize,
505 /// Code units consumed so far: always just past the head of the cluster
506 /// at `pos`, or `pos` itself before the first call.
507 scan: usize,
508 cat_before: u8,
509 state: u8,
510}
511
512impl<'a> Iterator for GraphemeBoundariesUtf16<'a> {
513 type Item = usize;
514
515 #[inline]
516 fn size_hint(&self) -> (usize, Option<usize>) {
517 let remaining = self.units.len() - self.pos;
518 (cmp::min(remaining, 1), Some(remaining))
519 }
520
521 fn next(&mut self) -> Option<usize> {
522 let len = self.units.len();
523 let start = self.pos;
524 if start == len {
525 return None;
526 }
527 if self.scan == start {
528 // Consume the cluster head; nothing can break before it.
529 let (ch, units) = decode_utf16_at(self.units, start);
530 self.cat_before = tables::grapheme_category_raw(ch);
531 self.state = next_state(ALWAYS, self.cat_before, ch);
532 self.scan = start + units;
533 }
534 while self.scan < len {
535 let (ch, units) = decode_utf16_at(self.units, self.scan);
536 let cat = tables::grapheme_category_raw(ch);
537 let boundary =
538 self.state & PAIR_MASK[(self.cat_before as usize) << 4 | cat as usize] == 0;
539 self.state = next_state(self.state, cat, ch);
540 self.cat_before = cat;
541 let char_at = self.scan;
542 self.scan += units;
543 if boundary {
544 self.pos = char_at;
545 return Some(start);
546 }
547 }
548 // The end of the slice is always a boundary.
549 self.pos = len;
550 Some(start)
551 }
552}
553
554/// Iterate over the UTF-16 code unit offsets at which the extended grapheme clusters of a slice start,
555/// without decoding the clusters out.
556///
557/// ```
558/// use fast_grapheme_segmenter::grapheme_boundaries_utf16;
559///
560/// let units: Vec<u16> = "a๐ฐ๐ทb".encode_utf16().collect();
561/// let offsets: Vec<usize> = grapheme_boundaries_utf16(&units).collect();
562/// assert_eq!(offsets, [0, 1, 5]);
563/// ```
564#[must_use]
565#[inline]
566pub fn grapheme_boundaries_utf16(s: &[u16]) -> GraphemeBoundariesUtf16<'_> {
567 GraphemeBoundariesUtf16 {
568 units: s,
569 pos: 0,
570 scan: 0,
571 cat_before: CAT_ANY,
572 state: ALWAYS,
573 }
574}
575
576/// Whether `b` is a printable ASCII byte.
577///
578/// Printable ASCII is a category-`Any` island:
579/// no ASCII codepoint is Extend, ZWJ, SpacingMark, Prepend, Regional_Indicator or InCB=Consonant,
580/// so the only rule that could suppress a boundary between two of them is GB3 (CR ร LF), and neither CR nor LF is printable.
581/// Every adjacent pair is a GB999 boundary, and each byte leaves the packed state at `(Any, ALWAYS)`,
582/// which is exactly what the per-codepoint loop would leave behind.
583#[inline]
584fn is_printable_ascii(b: u8) -> bool {
585 b.wrapping_sub(0x20) < 0x5F // 0x20..=0x7E
586}
587
588/// Whether every byte of `w` is printable ASCII.
589///
590/// The standard SWAR zero-byte test, applied to a mask whose byte vanishes
591/// for anything below 0x20 and to the XOR with 0x7F whose byte vanishes for DEL;
592/// bytes with the high bit set are caught by the mask itself.
593#[inline]
594fn all_printable_ascii(w: u64) -> bool {
595 const ONES: u64 = 0x0101_0101_0101_0101;
596 const MSB: u64 = 0x8080_8080_8080_8080;
597 let low = w & 0xE0E0_E0E0_E0E0_E0E0;
598 let del = w ^ 0x7F7F_7F7F_7F7F_7F7F;
599 let bad = (low.wrapping_sub(ONES) & !low) | (del.wrapping_sub(ONES) & !del) | w;
600 bad & MSB == 0
601}
602
603/// End of the maximal printable-ASCII run starting at `from`.
604///
605/// Swallows eight bytes at a time while a whole word is printable,
606/// then walks the remainder byte by byte.
607#[inline]
608fn printable_run_end(bytes: &[u8], from: usize) -> usize {
609 let mut j = from;
610 while j + 8 <= bytes.len() {
611 let word = u64::from_le_bytes(bytes[j..j + 8].try_into().unwrap());
612 if !all_printable_ascii(word) {
613 break;
614 }
615 j += 8;
616 }
617 while j < bytes.len() && is_printable_ascii(bytes[j]) {
618 j += 1;
619 }
620 j
621}
622
623/// A per-byte printable-ASCII mask for a word:
624/// 0x80 set in each byte that is in 0x20..=0x7E.
625#[inline]
626fn printable_msb_mask(w: u64) -> u64 {
627 const ONES: u64 = 0x0101_0101_0101_0101;
628 const MSB: u64 = 0x8080_8080_8080_8080;
629 let low = w & 0xE0E0_E0E0_E0E0_E0E0;
630 let del = w ^ 0x7F7F_7F7F_7F7F_7F7F;
631 let bad =
632 (low.wrapping_sub(ONES) & !low & MSB) | (del.wrapping_sub(ONES) & !del & MSB) | (w & MSB);
633 !bad & MSB
634}
635
636/// Find the next run of printable-ASCII bytes of length two or more.
637///
638/// Returns `(start, end)` of the run, or `(len, len)` when none follows.
639///
640/// Keeping the run discovery out of the per-codepoint loop is what lets
641/// text without such runs count exactly as it did before the bulk path:
642/// the char loop stays untouched, and this word-at-a-time scan costs a
643/// couple of instructions per eight bytes.
644///
645/// It is kept out of line for the same reason: it runs once per run, and letting its machinery bloat
646/// the counting function measurably degrades the char loop's codegen.
647#[inline(never)]
648fn next_run(bytes: &[u8], from: usize) -> (usize, usize) {
649 let len = bytes.len();
650 let mut j = from;
651 while j + 8 <= len {
652 let p = printable_msb_mask(u64::from_le_bytes(bytes[j..j + 8].try_into().unwrap()));
653 // A byte and its successor both printable inside the word, or the
654 // word's last byte pairing up with the byte that follows it.
655 let pair = p & p >> 8;
656 if pair != 0 {
657 let start = j + (pair.trailing_zeros() >> 3) as usize;
658 return (start, printable_run_end(bytes, start));
659 }
660 if p >> 56 != 0 && j + 8 < len && is_printable_ascii(bytes[j + 8]) {
661 return (j + 7, printable_run_end(bytes, j + 7));
662 }
663 j += 8;
664 }
665 let mut i = j;
666 while i + 1 < len {
667 if is_printable_ascii(bytes[i]) && is_printable_ascii(bytes[i + 1]) {
668 return (i, printable_run_end(bytes, i));
669 }
670 i += 1;
671 }
672 (len, len)
673}
674
675/// The per-codepoint counting loop over `seg`, carrying the rule state.
676///
677/// Kept out of line so that both counting paths get the same tight loop:
678/// the bulk path only ever calls it on run-free gaps, and letting either
679/// path's surroundings influence its codegen is measurable on the other.
680#[inline(never)]
681fn count_gap(seg: &str, count: &mut usize, cat_before: &mut u8, state: &mut u8) {
682 for (_, ch) in seg.char_indices() {
683 let cat_after = tables::grapheme_category_raw(ch);
684 if *state & PAIR_MASK[(*cat_before as usize) << 4 | cat_after as usize] == 0 {
685 *count += 1;
686 }
687 *state = next_state(*state, cat_after, ch);
688 *cat_before = cat_after;
689 }
690}
691
692/// Whether the head of the string is printable-ASCII-heavy enough that the
693/// run-bulk counting path will pay for itself.
694///
695/// Both counting paths are correct for any input; this only picks one,
696/// so a misleading sample can cost speed, never correctness.
697///
698/// Scanning the gaps between runs word-by-word is cheap, but not free,
699/// and text that is mostly non-ASCII has no runs worth swallowing.
700fn ascii_heavy(bytes: &[u8]) -> bool {
701 let sample = bytes.len().min(64);
702 let mut printable = 0;
703 let mut j = 0;
704 while j + 8 <= sample {
705 let w = u64::from_le_bytes(bytes[j..j + 8].try_into().unwrap());
706 printable += printable_msb_mask(w).count_ones();
707 j += 8;
708 }
709 while j < sample {
710 printable += is_printable_ascii(bytes[j]) as u32;
711 j += 1;
712 }
713 printable >= sample as u32 / 2
714}
715
716/// Count the extended grapheme clusters of a string.
717///
718/// A dedicated loop that never slices the clusters it counts, unlike [`Graphemes::count`].
719///
720/// ```
721/// use fast_grapheme_segmenter::count_graphemes;
722///
723/// assert_eq!(count_graphemes("๐ฐ๐ท๊ฐ๋๋ค"), 4); // one flag, three syllables
724/// ```
725#[must_use]
726pub fn count_graphemes(s: &str) -> usize {
727 let bytes = s.as_bytes();
728 // The first codepoint starts the first cluster (GB1);
729 // nothing can break before it, so it is consumed outright.
730 let first = match s.chars().next() {
731 Some(ch) => ch,
732 None => return 0,
733 };
734 let mut count = 1;
735 let mut cat_before = tables::grapheme_category_raw(first);
736 let mut state = next_state(ALWAYS, cat_before, first);
737 let mut pos = first.len_utf8();
738
739 if !ascii_heavy(bytes) {
740 count_gap(&s[pos..], &mut count, &mut cat_before, &mut state);
741 return count;
742 }
743 while pos < bytes.len() {
744 let (start, end) = next_run(bytes, pos);
745 count_gap(&s[pos..start], &mut count, &mut cat_before, &mut state);
746 if start == end {
747 break;
748 }
749 // The run counts wholesale: every byte is its own cluster,
750 // except the first when the pair test against what precedes it suppresses the boundary (GB9b, a Prepend).
751 if state & PAIR_MASK[(cat_before as usize) << 4 | CAT_ANY as usize] == 0 {
752 count += end - start;
753 } else {
754 count += end - start - 1;
755 }
756 pos = end;
757 cat_before = CAT_ANY;
758 state = ALWAYS;
759 }
760 count
761}
762
763/// Forward-only driver over a contiguous string.
764///
765/// Every rule context GB9c, GB11 and GB12/GB13 needs is carried in the packed state byte.
766#[derive(Clone, Debug)]
767struct Driver<'a> {
768 iter: CharIndices<'a>,
769 /// The string being scanned.
770 string: &'a str,
771 /// Byte offset of the start of the cluster being scanned.
772 offset: usize,
773 /// Category of the last consumed codepoint.
774 cat_before: u8,
775 /// Packed rule state for everything consumed so far.
776 state: u8,
777 /// Whether the one-byte shortcut below is armed.
778 /// Arms itself when the state machine lands on the head of a printable-ASCII pair, disarms when the run ends,
779 /// so construction stays O(1): callers that build an iterator to extract a single cluster never pay a probe scan.
780 bulk: bool,
781}
782
783impl<'a> Driver<'a> {
784 fn new(s: &'a str) -> Driver<'a> {
785 let mut driver = Driver {
786 iter: s.char_indices(),
787 string: s,
788 offset: 0,
789 cat_before: CAT_ANY,
790 state: ALWAYS,
791 bulk: false,
792 };
793 // Consume the first codepoint; nothing can break before it.
794 if let Some((_, ch)) = driver.iter.next() {
795 driver.cat_before = tables::grapheme_category_raw(ch);
796 driver.state = next_state(ALWAYS, driver.cat_before, ch);
797 }
798 driver
799 }
800
801 /// Advance to the next boundary and return its offset.
802 #[inline]
803 fn next_boundary(&mut self) -> usize {
804 // A printable ASCII byte is always followed by
805 // a boundary when the next byte is printable ASCII too (GB999),
806 // and the byte consumed leaves (Any, ALWAYS): the cluster starting at `offset` is a single byte,
807 // and the state machine only ever sees the edges of such a run.
808 // `iter` sits right behind the char at `offset`, which the shortcut just proved to be one byte.
809 //
810 // Arming is local, the boundary return below tests the head of the next cluster,
811 // so on text that mixes scripts the branch follows the actual runs instead of a construction-time sample,
812 // and mispredicts only at run edges.
813 if self.bulk
814 && self.offset + 1 < self.string.len()
815 && is_printable_ascii(self.string.as_bytes()[self.offset])
816 && is_printable_ascii(self.string.as_bytes()[self.offset + 1])
817 {
818 self.iter.next();
819 self.offset += 1;
820 self.cat_before = CAT_ANY;
821 self.state = ALWAYS;
822 return self.offset;
823 }
824 loop {
825 let (i, ch) = match self.iter.next() {
826 Some(next) => next,
827 None => {
828 // The end of the string is always a boundary (GB2).
829 self.offset = self.string.len();
830 return self.offset;
831 }
832 };
833 let cat_after = tables::grapheme_category_raw(ch);
834 let boundary =
835 self.state & PAIR_MASK[(self.cat_before as usize) << 4 | cat_after as usize] == 0;
836 self.state = next_state(self.state, cat_after, ch);
837 self.cat_before = cat_after;
838 if boundary {
839 self.offset = i;
840 // Arm the shortcut when the next cluster's head starts a printable-ASCII pair, disarm when it doesn't.
841 // The head is `ch`, already decoded: its printability is a register test,
842 // so arming costs one guarded byte load per state-machine boundary instead of a sample scan at construction.
843 self.bulk = (ch as u32).wrapping_sub(0x20) < 0x5f
844 && i + 1 < self.string.len()
845 && is_printable_ascii(self.string.as_bytes()[i + 1]);
846 return i;
847 }
848 }
849 }
850}
851
852#[cfg(test)]
853mod tests {
854 use super::*;
855
856 fn split(s: &str) -> Vec<&str> {
857 graphemes(s).collect()
858 }
859
860 #[test]
861 fn empty_and_ascii() {
862 assert_eq!(split(""), Vec::<&str>::new());
863 assert_eq!(split("abcd"), vec!["a", "b", "c", "d"]);
864 assert_eq!(count_graphemes(""), 0);
865 assert_eq!(count_graphemes("abcd"), 4);
866 }
867
868 #[test]
869 fn printable_ascii_runs() {
870 // Every adjacent printable-ASCII pair is a boundary (GB999)...
871 assert_eq!(count_graphemes("abcdefgh"), 8);
872 assert_eq!(count_graphemes("hello world"), 11);
873 // ...while controls, CR/LF, TAB and DEL fall through to the rules.
874 assert_eq!(split("ab\ncd"), vec!["a", "b", "\n", "c", "d"]);
875 assert_eq!(split("a\r\nb"), vec!["a", "\r\n", "b"]);
876 assert_eq!(split("a\tb"), vec!["a", "\t", "b"]);
877 assert_eq!(split("a\u{7f}b"), vec!["a", "\u{7f}", "b"]);
878 assert_eq!(split("a\u{1f}b"), vec!["a", "\u{1f}", "b"]);
879 // A combining mark still glues onto the run's last byte (GB9).
880 assert_eq!(split("tee\u{301}!"), vec!["t", "e", "e\u{301}", "!"]);
881 // A prepend swallows the printable byte that follows it (GB9b),
882 // and the bulk path resumes only at the next boundary.
883 assert_eq!(split("\u{600}ab"), vec!["\u{600}a", "b"]);
884 // Run lengths around the 8-byte word scan and its scalar tail.
885 for n in [6, 7, 8, 9, 15, 16, 17, 31] {
886 let run: String = "x".repeat(n);
887 assert_eq!(count_graphemes(&run), n);
888 assert_eq!(count_graphemes(&format!("y{run}")), n + 1);
889 assert_eq!(count_graphemes(&format!("{run}\u{301}")), n);
890 assert_eq!(count_graphemes(&format!("{run}\n{run}")), 2 * n + 1);
891 assert_eq!(split(&run).len(), n);
892 }
893 // The word scan must not read past the run's end.
894 let edge = "1234567\u{e9}890"; // 7 printable, 2-byte รฉ, 3 printable
895 assert_eq!(split(edge).len(), 11);
896 }
897
898 #[test]
899 fn crlf() {
900 assert_eq!(split("\r\n\r"), vec!["\r\n", "\r"]);
901 assert_eq!(split("\n\r\n\r"), vec!["\n", "\r\n", "\r"]);
902 }
903
904 #[test]
905 fn regional_indicators() {
906 // Pairs of flags, then an unpaired one.
907 assert_eq!(
908 split("\u{1f1f0}\u{1f1f7}\u{1f1e6}\u{1f1f7}"),
909 vec!["\u{1f1f0}\u{1f1f7}", "\u{1f1e6}\u{1f1f7}"]
910 );
911 assert_eq!(count_graphemes("\u{1f1f0}\u{1f1f7}\u{1f1e6}"), 2);
912 }
913
914 #[test]
915 fn emoji() {
916 // Family with skin tones joined by ZWJ: one cluster (GB9, GB11).
917 assert_eq!(
918 count_graphemes("\u{1f468}\u{200d}\u{1f467}\u{200d}\u{1f466}"),
919 1
920 );
921 assert_eq!(count_graphemes("\u{1F938}\u{1F3FE}\u{1F3FE}"), 1);
922 // Rainbow flag and family, both held together by ZWJ + Extend.
923 assert_eq!(
924 count_graphemes(
925 "\u{1f3f3}\u{fe0f}\u{200d}\u{1f308}\u{1f469}\u{200d}\u{1f469}\u{200d}\u{1f467}\u{200d}\u{1f466}"
926 ),
927 2
928 );
929 }
930
931 #[test]
932 fn jamo() {
933 // Precomposed syllables and decomposed jamo segment alike.
934 assert_eq!(
935 count_graphemes("\u{1100}\u{1161}\u{11a8}\u{1102}\u{1161}"),
936 2
937 );
938 assert_eq!(count_graphemes("แแ
งแแ
ฐ"), 2);
939 }
940
941 #[test]
942 fn incb_conjuncts() {
943 // GB9c: consonant, virama (linker), consonant stay joined...
944 let conjunct = "\u{915}\u{94d}\u{915}";
945 assert_eq!(split(conjunct), vec![conjunct]);
946 // ...and so does a trailing InCB=Extend between the two.
947 let linked = "\u{915}\u{93c}\u{94d}\u{915}";
948 assert_eq!(split(linked), vec![linked]);
949 // A lone virama still attaches to the preceding cluster (GB9).
950 assert_eq!(split("\u{915}\u{94d}"), vec!["\u{915}\u{94d}"]);
951 // ZWNJ is InCB=None, so it ends the conjunct run and splits the consonants
952 // while joining the cluster it follows (GB9).
953 assert_eq!(
954 split("\u{915}\u{200c}\u{915}"),
955 vec!["\u{915}\u{200c}", "\u{915}"]
956 );
957 }
958
959 #[test]
960 fn prepend() {
961 // Multiple prepends stack onto the following cluster (GB9b).
962 assert_eq!(
963 split("\u{20}\u{600}\u{600}\u{20}"),
964 vec!["\u{20}", "\u{600}\u{600}\u{20}"]
965 );
966 assert_eq!(
967 split("\u{600}\u{20}\u{20}"),
968 vec!["\u{600}\u{20}", "\u{20}"]
969 );
970 }
971
972 #[test]
973 fn indices_and_as_str() {
974 let s = "a\u{301}\r\nb";
975 let v: Vec<_> = grapheme_indices(s).collect();
976 assert_eq!(v, [(0, "a\u{301}"), (3, "\r\n"), (5, "b")]);
977
978 let offsets: Vec<usize> = grapheme_boundaries(s).collect();
979 assert_eq!(offsets, [0, 3, 5]);
980 assert_eq!(
981 grapheme_boundaries("").collect::<Vec<usize>>(),
982 Vec::<usize>::new()
983 );
984
985 let mut iter = graphemes("ab");
986 assert_eq!(iter.next(), Some("a"));
987 assert_eq!(iter.as_str(), "b");
988 assert_eq!(iter.next(), Some("b"));
989 assert_eq!(iter.as_str(), "");
990 assert_eq!(iter.next(), None);
991
992 let mut bounds = grapheme_boundaries("a\u{301}b");
993 assert_eq!(bounds.next(), Some(0));
994 // The remaining, not yet yielded part starts at the next cluster.
995 assert_eq!(bounds.as_str(), "b");
996 assert_eq!(bounds.next(), Some(3));
997 assert_eq!(bounds.next(), None);
998 }
999
1000 /// `Iterator::count` restarts the count at the current offset,
1001 /// which is only sound because a cluster head re-establishes every packed state bit its rules depend on.
1002 /// This hammers that claim over random strings.
1003 #[test]
1004 fn count_after_partial_consumption() {
1005 const RANGES: &[(u32, u32)] = &[
1006 (0x0, 0x7F),
1007 (0x300, 0x370),
1008 (0x600, 0x605),
1009 (0x903, 0x94d),
1010 (0x1100, 0x11FF),
1011 (0xAC00, 0xAC1C),
1012 (0x200B, 0x200D),
1013 (0x3297, 0x3299),
1014 (0xFE00, 0xFE0F),
1015 (0x1F1E6, 0x1F1FF),
1016 (0x1F3FB, 0x1F3FF),
1017 (0x1F400, 0x1F680),
1018 (0xE0020, 0xE007F),
1019 ];
1020
1021 let mut seed = 0x9E3779B97F4A7C15u64;
1022 let mut next = move || {
1023 seed ^= seed << 13;
1024 seed ^= seed >> 7;
1025 seed ^= seed << 17;
1026 seed
1027 };
1028
1029 for _ in 0..4_000 {
1030 let len = (next() % 20) as usize;
1031 let mut s = String::new();
1032 for _ in 0..len {
1033 let (lo, hi) = RANGES[(next() % RANGES.len() as u64) as usize];
1034 let cp = lo as u64 + next() % (hi as u64 - lo as u64 + 1);
1035 s.push(char::from_u32(cp as u32).unwrap());
1036 }
1037 let total = count_graphemes(&s);
1038 assert_eq!(graphemes(&s).count(), total, "full count on {:?}", s);
1039 assert_eq!(
1040 grapheme_boundaries(&s).count(),
1041 total,
1042 "full boundary count on {:?}",
1043 s
1044 );
1045 for k in 0..=total {
1046 let mut clusters = graphemes(&s);
1047 for _ in 0..k {
1048 assert!(clusters.next().is_some(), "under-count on {:?}", s);
1049 }
1050 assert_eq!(
1051 clusters.count(),
1052 total - k,
1053 "after {} clusters of {:?}",
1054 k,
1055 s
1056 );
1057
1058 let mut offsets = grapheme_boundaries(&s);
1059 for _ in 0..k {
1060 assert!(offsets.next().is_some(), "under-boundaries on {:?}", s);
1061 }
1062 assert_eq!(
1063 offsets.count(),
1064 total - k,
1065 "after {} boundaries of {:?}",
1066 k,
1067 s
1068 );
1069 }
1070 }
1071 }
1072
1073 #[test]
1074 fn size_hint() {
1075 let mut iter = graphemes("a\u{301}bc");
1076 assert_eq!(iter.size_hint(), (1, Some(5)));
1077 iter.next();
1078 assert_eq!(iter.size_hint(), (1, Some(2)));
1079 }
1080
1081 #[test]
1082 fn demonic() {
1083 // Zalgo text is one cluster per base character.
1084 assert_eq!(
1085 count_graphemes("Z\u{335}\u{36e}\u{34b}A\u{35c}\u{331}\u{334}L\u{328}\u{332}"),
1086 3
1087 );
1088 }
1089}