diff options
Diffstat (limited to 'vendor/bstr/src/unicode/grapheme.rs')
| -rw-r--r-- | vendor/bstr/src/unicode/grapheme.rs | 390 |
1 files changed, 390 insertions, 0 deletions
diff --git a/vendor/bstr/src/unicode/grapheme.rs b/vendor/bstr/src/unicode/grapheme.rs new file mode 100644 index 0000000..8a701be --- /dev/null +++ b/vendor/bstr/src/unicode/grapheme.rs @@ -0,0 +1,390 @@ +use regex_automata::{dfa::Automaton, Anchored, Input}; + +use crate::{ + ext_slice::ByteSlice, + unicode::fsm::{ + grapheme_break_fwd::GRAPHEME_BREAK_FWD, + grapheme_break_rev::GRAPHEME_BREAK_REV, + regional_indicator_rev::REGIONAL_INDICATOR_REV, + }, + utf8, +}; + +/// An iterator over grapheme clusters in a byte string. +/// +/// This iterator is typically constructed by +/// [`ByteSlice::graphemes`](trait.ByteSlice.html#method.graphemes). +/// +/// Unicode defines a grapheme cluster as an *approximation* to a single user +/// visible character. A grapheme cluster, or just "grapheme," is made up of +/// one or more codepoints. For end user oriented tasks, one should generally +/// prefer using graphemes instead of [`Chars`](struct.Chars.html), which +/// always yields one codepoint at a time. +/// +/// Since graphemes are made up of one or more codepoints, this iterator yields +/// `&str` elements. When invalid UTF-8 is encountered, replacement codepoints +/// are [substituted](index.html#handling-of-invalid-utf-8). +/// +/// This iterator can be used in reverse. When reversed, exactly the same +/// set of grapheme clusters are yielded, but in reverse order. +/// +/// This iterator only yields *extended* grapheme clusters, in accordance with +/// [UAX #29](https://www.unicode.org/reports/tr29/tr29-33.html#Grapheme_Cluster_Boundaries). +#[derive(Clone, Debug)] +pub struct Graphemes<'a> { + bs: &'a [u8], +} + +impl<'a> Graphemes<'a> { + pub(crate) fn new(bs: &'a [u8]) -> Graphemes<'a> { + Graphemes { bs } + } + + /// View the underlying data as a subslice of the original data. + /// + /// The slice returned has the same lifetime as the original slice, and so + /// the iterator can continue to be used while this exists. + /// + /// # Examples + /// + /// ``` + /// use bstr::ByteSlice; + /// + /// let mut it = b"abc".graphemes(); + /// + /// assert_eq!(b"abc", it.as_bytes()); + /// it.next(); + /// assert_eq!(b"bc", it.as_bytes()); + /// it.next(); + /// it.next(); + /// assert_eq!(b"", it.as_bytes()); + /// ``` + #[inline] + pub fn as_bytes(&self) -> &'a [u8] { + self.bs + } +} + +impl<'a> Iterator for Graphemes<'a> { + type Item = &'a str; + + #[inline] + fn next(&mut self) -> Option<&'a str> { + let (grapheme, size) = decode_grapheme(self.bs); + if size == 0 { + return None; + } + self.bs = &self.bs[size..]; + Some(grapheme) + } +} + +impl<'a> DoubleEndedIterator for Graphemes<'a> { + #[inline] + fn next_back(&mut self) -> Option<&'a str> { + let (grapheme, size) = decode_last_grapheme(self.bs); + if size == 0 { + return None; + } + self.bs = &self.bs[..self.bs.len() - size]; + Some(grapheme) + } +} + +/// An iterator over grapheme clusters in a byte string and their byte index +/// positions. +/// +/// This iterator is typically constructed by +/// [`ByteSlice::grapheme_indices`](trait.ByteSlice.html#method.grapheme_indices). +/// +/// Unicode defines a grapheme cluster as an *approximation* to a single user +/// visible character. A grapheme cluster, or just "grapheme," is made up of +/// one or more codepoints. For end user oriented tasks, one should generally +/// prefer using graphemes instead of [`Chars`](struct.Chars.html), which +/// always yields one codepoint at a time. +/// +/// Since graphemes are made up of one or more codepoints, this iterator +/// yields `&str` elements (along with their start and end byte offsets). +/// When invalid UTF-8 is encountered, replacement codepoints are +/// [substituted](index.html#handling-of-invalid-utf-8). Because of this, the +/// indices yielded by this iterator may not correspond to the length of the +/// grapheme cluster yielded with those indices. For example, when this +/// iterator encounters `\xFF` in the byte string, then it will yield a pair +/// of indices ranging over a single byte, but will provide an `&str` +/// equivalent to `"\u{FFFD}"`, which is three bytes in length. However, when +/// given only valid UTF-8, then all indices are in exact correspondence with +/// their paired grapheme cluster. +/// +/// This iterator can be used in reverse. When reversed, exactly the same +/// set of grapheme clusters are yielded, but in reverse order. +/// +/// This iterator only yields *extended* grapheme clusters, in accordance with +/// [UAX #29](https://www.unicode.org/reports/tr29/tr29-33.html#Grapheme_Cluster_Boundaries). +#[derive(Clone, Debug)] +pub struct GraphemeIndices<'a> { + bs: &'a [u8], + forward_index: usize, + reverse_index: usize, +} + +impl<'a> GraphemeIndices<'a> { + pub(crate) fn new(bs: &'a [u8]) -> GraphemeIndices<'a> { + GraphemeIndices { bs, forward_index: 0, reverse_index: bs.len() } + } + + /// View the underlying data as a subslice of the original data. + /// + /// The slice returned has the same lifetime as the original slice, and so + /// the iterator can continue to be used while this exists. + /// + /// # Examples + /// + /// ``` + /// use bstr::ByteSlice; + /// + /// let mut it = b"abc".grapheme_indices(); + /// + /// assert_eq!(b"abc", it.as_bytes()); + /// it.next(); + /// assert_eq!(b"bc", it.as_bytes()); + /// it.next(); + /// it.next(); + /// assert_eq!(b"", it.as_bytes()); + /// ``` + #[inline] + pub fn as_bytes(&self) -> &'a [u8] { + self.bs + } +} + +impl<'a> Iterator for GraphemeIndices<'a> { + type Item = (usize, usize, &'a str); + + #[inline] + fn next(&mut self) -> Option<(usize, usize, &'a str)> { + let index = self.forward_index; + let (grapheme, size) = decode_grapheme(self.bs); + if size == 0 { + return None; + } + self.bs = &self.bs[size..]; + self.forward_index += size; + Some((index, index + size, grapheme)) + } +} + +impl<'a> DoubleEndedIterator for GraphemeIndices<'a> { + #[inline] + fn next_back(&mut self) -> Option<(usize, usize, &'a str)> { + let (grapheme, size) = decode_last_grapheme(self.bs); + if size == 0 { + return None; + } + self.bs = &self.bs[..self.bs.len() - size]; + self.reverse_index -= size; + Some((self.reverse_index, self.reverse_index + size, grapheme)) + } +} + +/// Decode a grapheme from the given byte string. +/// +/// This returns the resulting grapheme (which may be a Unicode replacement +/// codepoint if invalid UTF-8 was found), along with the number of bytes +/// decoded in the byte string. The number of bytes decoded may not be the +/// same as the length of grapheme in the case where invalid UTF-8 is found. +pub fn decode_grapheme(bs: &[u8]) -> (&str, usize) { + if bs.is_empty() { + ("", 0) + } else if bs.len() >= 2 + && bs[0].is_ascii() + && bs[1].is_ascii() + && !bs[0].is_ascii_whitespace() + { + // FIXME: It is somewhat sad that we have to special case this, but it + // leads to a significant speed up in predominantly ASCII text. The + // issue here is that the DFA has a bit of overhead, and running it for + // every byte in mostly ASCII text results in a bit slowdown. We should + // re-litigate this once regex-automata 0.3 is out, but it might be + // hard to avoid the special case. A DFA is always going to at least + // require some memory access. + + // Safe because all ASCII bytes are valid UTF-8. + let grapheme = unsafe { bs[..1].to_str_unchecked() }; + (grapheme, 1) + } else if let Some(hm) = { + let input = Input::new(bs).anchored(Anchored::Yes); + GRAPHEME_BREAK_FWD.try_search_fwd(&input).unwrap() + } { + // Safe because a match can only occur for valid UTF-8. + let grapheme = unsafe { bs[..hm.offset()].to_str_unchecked() }; + (grapheme, grapheme.len()) + } else { + const INVALID: &'static str = "\u{FFFD}"; + // No match on non-empty bytes implies we found invalid UTF-8. + let (_, size) = utf8::decode_lossy(bs); + (INVALID, size) + } +} + +fn decode_last_grapheme(bs: &[u8]) -> (&str, usize) { + if bs.is_empty() { + ("", 0) + } else if let Some(hm) = { + let input = Input::new(bs).anchored(Anchored::Yes); + GRAPHEME_BREAK_REV.try_search_rev(&input).unwrap() + } { + let start = adjust_rev_for_regional_indicator(bs, hm.offset()); + // Safe because a match can only occur for valid UTF-8. + let grapheme = unsafe { bs[start..].to_str_unchecked() }; + (grapheme, grapheme.len()) + } else { + const INVALID: &'static str = "\u{FFFD}"; + // No match on non-empty bytes implies we found invalid UTF-8. + let (_, size) = utf8::decode_last_lossy(bs); + (INVALID, size) + } +} + +/// Return the correct offset for the next grapheme decoded at the end of the +/// given byte string, where `i` is the initial guess. In particular, +/// `&bs[i..]` represents the candidate grapheme. +/// +/// `i` is returned by this function in all cases except when `&bs[i..]` is +/// a pair of regional indicator codepoints. In that case, if an odd number of +/// additional regional indicator codepoints precedes `i`, then `i` is +/// adjusted such that it points to only a single regional indicator. +/// +/// This "fixing" is necessary to handle the requirement that a break cannot +/// occur between regional indicators where it would cause an odd number of +/// regional indicators to exist before the break from the *start* of the +/// string. A reverse regex cannot detect this case easily without look-around. +fn adjust_rev_for_regional_indicator(mut bs: &[u8], i: usize) -> usize { + // All regional indicators use a 4 byte encoding, and we only care about + // the case where we found a pair of regional indicators. + if bs.len() - i != 8 { + return i; + } + // Count all contiguous occurrences of regional indicators. If there's an + // even number of them, then we can accept the pair we found. Otherwise, + // we can only take one of them. + // + // FIXME: This is quadratic in the worst case, e.g., a string of just + // regional indicator codepoints. A fix probably requires refactoring this + // code a bit such that we don't rescan regional indicators. + let mut count = 0; + while let Some(hm) = { + let input = Input::new(bs).anchored(Anchored::Yes); + REGIONAL_INDICATOR_REV.try_search_rev(&input).unwrap() + } { + bs = &bs[..hm.offset()]; + count += 1; + } + if count % 2 == 0 { + i + } else { + i + 4 + } +} + +#[cfg(all(test, feature = "std"))] +mod tests { + #[cfg(not(miri))] + use ucd_parse::GraphemeClusterBreakTest; + + use crate::{ext_slice::ByteSlice, tests::LOSSY_TESTS}; + + use super::*; + + #[test] + #[cfg(not(miri))] + fn forward_ucd() { + for (i, test) in ucdtests().into_iter().enumerate() { + let given = test.grapheme_clusters.concat(); + let got: Vec<String> = Graphemes::new(given.as_bytes()) + .map(|cluster| cluster.to_string()) + .collect(); + assert_eq!( + test.grapheme_clusters, + got, + "\ngrapheme forward break test {} failed:\n\ + given: {:?}\n\ + expected: {:?}\n\ + got: {:?}\n", + i, + uniescape(&given), + uniescape_vec(&test.grapheme_clusters), + uniescape_vec(&got), + ); + } + } + + #[test] + #[cfg(not(miri))] + fn reverse_ucd() { + for (i, test) in ucdtests().into_iter().enumerate() { + let given = test.grapheme_clusters.concat(); + let mut got: Vec<String> = Graphemes::new(given.as_bytes()) + .rev() + .map(|cluster| cluster.to_string()) + .collect(); + got.reverse(); + assert_eq!( + test.grapheme_clusters, + got, + "\n\ngrapheme reverse break test {} failed:\n\ + given: {:?}\n\ + expected: {:?}\n\ + got: {:?}\n", + i, + uniescape(&given), + uniescape_vec(&test.grapheme_clusters), + uniescape_vec(&got), + ); + } + } + + #[test] + fn forward_lossy() { + for &(expected, input) in LOSSY_TESTS { + let got = Graphemes::new(input.as_bytes()).collect::<String>(); + assert_eq!(expected, got); + } + } + + #[test] + fn reverse_lossy() { + for &(expected, input) in LOSSY_TESTS { + let expected: String = expected.chars().rev().collect(); + let got = + Graphemes::new(input.as_bytes()).rev().collect::<String>(); + assert_eq!(expected, got); + } + } + + #[cfg(not(miri))] + fn uniescape(s: &str) -> String { + s.chars().flat_map(|c| c.escape_unicode()).collect::<String>() + } + + #[cfg(not(miri))] + fn uniescape_vec(strs: &[String]) -> Vec<String> { + strs.iter().map(|s| uniescape(s)).collect() + } + + /// Return all of the UCD for grapheme breaks. + #[cfg(not(miri))] + fn ucdtests() -> Vec<GraphemeClusterBreakTest> { + const TESTDATA: &'static str = + include_str!("data/GraphemeBreakTest.txt"); + + let mut tests = vec![]; + for mut line in TESTDATA.lines() { + line = line.trim(); + if line.starts_with("#") || line.contains("surrogate") { + continue; + } + tests.push(line.parse().unwrap()); + } + tests + } +} |