Skip to main content

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}