mozjs_utf8_iter/
lib.rs

1// Copyright Mozilla Foundation
2//
3// Licensed under the Apache License (Version 2.0), or the MIT license,
4// (the "Licenses") at your option. You may not use this file except in
5// compliance with one of the Licenses. You may obtain copies of the
6// Licenses at:
7//
8//    https://www.apache.org/licenses/LICENSE-2.0
9//    https://opensource.org/licenses/MIT
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the Licenses is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the Licenses for the specific language governing permissions and
15// limitations under the Licenses.
16
17#![no_std]
18
19//! Provides iteration by `char` over `&[u8]` containing potentially-invalid
20//! UTF-8 such that errors are handled according to the [WHATWG Encoding
21//! Standard](https://encoding.spec.whatwg.org/#utf-8-decoder) (i.e. the same
22//! way as in `String::from_utf8_lossy`).
23//!
24//! The trait `Utf8CharsEx` provides the convenience method `chars()` on
25//! byte slices themselves instead of having to use the more verbose
26//! `Utf8Chars::new(slice)`.
27//!
28//! ```rust
29//! use utf8_iter::Utf8CharsEx;
30//! let data = b"\xFF\xC2\xE2\xE2\x98\xF0\xF0\x9F\xF0\x9F\x92\xE2\x98\x83";
31//! let from_iter: String = data.chars().collect();
32//! let from_std = String::from_utf8_lossy(data);
33//! assert_eq!(from_iter, from_std);
34//! ```
35
36#[cfg(feature = "icu_collections")]
37mod cptrie;
38#[cfg(feature = "icu_collections")]
39mod cptrie_indices;
40mod indices;
41mod report;
42
43#[cfg(feature = "icu_collections")]
44pub use crate::cptrie::Utf8CharsWithTrie;
45#[cfg(feature = "icu_collections")]
46pub use crate::cptrie::Utf8CharsWithTrieDefaultForAscii;
47#[cfg(feature = "icu_collections")]
48pub use crate::cptrie::Utf8CharsWithTrieDefaultForAsciiEx;
49#[cfg(feature = "icu_collections")]
50pub use crate::cptrie::Utf8CharsWithTrieEx;
51#[cfg(feature = "icu_collections")]
52pub use crate::cptrie_indices::Utf8CharIndicesWithTrie;
53#[cfg(feature = "icu_collections")]
54pub use crate::cptrie_indices::Utf8CharIndicesWithTrieDefaultForAscii;
55pub use crate::indices::Utf8CharIndices;
56pub use crate::report::ErrorReportingUtf8Chars;
57pub use crate::report::Utf8CharsError;
58use core::iter::FusedIterator;
59
60#[repr(align(64))] // Align to cache lines
61struct Utf8Data {
62    pub table: [u8; 384],
63}
64
65// This is generated code copied and pasted from utf_8.rs of encoding_rs.
66// Please don't edit by hand but instead regenerate as instructed in that
67// file.
68
69pub(crate) static UTF8_DATA: Utf8Data = Utf8Data {
70    table: [
71        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
72        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
73        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
74        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
75        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
76        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
77        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
78        252, 252, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 148, 148, 148,
79        148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 164, 164, 164, 164, 164,
80        164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164, 164,
81        164, 164, 164, 164, 164, 164, 164, 164, 164, 252, 252, 252, 252, 252, 252, 252, 252, 252,
82        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
83        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
84        252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252, 252,
85        252, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
86        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
87        4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
88        8, 8, 8, 8, 8, 8, 8, 16, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 32, 8, 8, 64, 8, 8, 8, 128, 4,
89        4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
90    ],
91};
92
93// End manually copypasted generated code.
94
95#[inline(always)]
96pub(crate) fn in_inclusive_range8(i: u8, start: u8, end: u8) -> bool {
97    i.wrapping_sub(start) <= (end - start)
98}
99
100/// Iterator by `char` over `&[u8]` that contains
101/// potentially-invalid UTF-8. See the crate documentation.
102#[derive(Debug, Clone)]
103pub struct Utf8Chars<'a> {
104    remaining: &'a [u8],
105}
106
107impl<'a> Utf8Chars<'a> {
108    #[inline(always)]
109    /// Creates the iterator from a byte slice.
110    pub fn new(bytes: &'a [u8]) -> Self {
111        Utf8Chars::<'a> { remaining: bytes }
112    }
113
114    /// Views the current remaining data in the iterator as a subslice
115    /// of the original slice.
116    #[inline(always)]
117    pub fn as_slice(&self) -> &'a [u8] {
118        self.remaining
119    }
120
121    #[inline(never)]
122    fn next_fallback(&mut self) -> Option<char> {
123        if self.remaining.is_empty() {
124            return None;
125        }
126        let first = self.remaining[0];
127        if first < 0x80 {
128            self.remaining = &self.remaining[1..];
129            return Some(char::from(first));
130        }
131        if !in_inclusive_range8(first, 0xC2, 0xF4) || self.remaining.len() == 1 {
132            self.remaining = &self.remaining[1..];
133            return Some('\u{FFFD}');
134        }
135        let second = self.remaining[1];
136        let (lower_bound, upper_bound) = match first {
137            0xE0 => (0xA0, 0xBF),
138            0xED => (0x80, 0x9F),
139            0xF0 => (0x90, 0xBF),
140            0xF4 => (0x80, 0x8F),
141            _ => (0x80, 0xBF),
142        };
143        if !in_inclusive_range8(second, lower_bound, upper_bound) {
144            self.remaining = &self.remaining[1..];
145            return Some('\u{FFFD}');
146        }
147        if first < 0xE0 {
148            self.remaining = &self.remaining[2..];
149            let point = ((u32::from(first) & 0x1F) << 6) | (u32::from(second) & 0x3F);
150            return Some(unsafe { char::from_u32_unchecked(point) });
151        }
152        if self.remaining.len() == 2 {
153            self.remaining = &self.remaining[2..];
154            return Some('\u{FFFD}');
155        }
156        let third = self.remaining[2];
157        if !in_inclusive_range8(third, 0x80, 0xBF) {
158            self.remaining = &self.remaining[2..];
159            return Some('\u{FFFD}');
160        }
161        if first < 0xF0 {
162            self.remaining = &self.remaining[3..];
163            let point = ((u32::from(first) & 0xF) << 12)
164                | ((u32::from(second) & 0x3F) << 6)
165                | (u32::from(third) & 0x3F);
166            return Some(unsafe { char::from_u32_unchecked(point) });
167        }
168        // At this point, we have a valid 3-byte prefix of a
169        // four-byte sequence that has to be incomplete, because
170        // otherwise `next()` would have succeeded.
171        self.remaining = &self.remaining[3..];
172        Some('\u{FFFD}')
173    }
174}
175
176impl<'a> Iterator for Utf8Chars<'a> {
177    type Item = char;
178
179    #[inline]
180    fn next(&mut self) -> Option<char> {
181        // Not delegating directly to `ErrorReportingUtf8Chars` to avoid
182        // an extra branch in the common case based on a cursory inspection
183        // of generated code in a similar case. Be sure to inspect the
184        // generated code as inlined into an actual usage site carefully
185        // if attempting to consolidate the source code here.
186
187        // This loop is only broken out of as goto forward
188        #[allow(clippy::never_loop)]
189        loop {
190            if self.remaining.len() < 4 {
191                break;
192            }
193            let first = self.remaining[0];
194            if first < 0x80 {
195                self.remaining = &self.remaining[1..];
196                return Some(char::from(first));
197            }
198            let second = self.remaining[1];
199            if in_inclusive_range8(first, 0xC2, 0xDF) {
200                if !in_inclusive_range8(second, 0x80, 0xBF) {
201                    break;
202                }
203                let point = ((u32::from(first) & 0x1F) << 6) | (u32::from(second) & 0x3F);
204                self.remaining = &self.remaining[2..];
205                return Some(unsafe { char::from_u32_unchecked(point) });
206            }
207            // This table-based formulation was benchmark-based in encoding_rs,
208            // but it hasn't been re-benchmarked in this iterator context.
209            let third = self.remaining[2];
210            if first < 0xF0 {
211                if ((UTF8_DATA.table[usize::from(second)]
212                    & UTF8_DATA.table[usize::from(first) + 0x80])
213                    | (third >> 6))
214                    != 2
215                {
216                    break;
217                }
218                let point = ((u32::from(first) & 0xF) << 12)
219                    | ((u32::from(second) & 0x3F) << 6)
220                    | (u32::from(third) & 0x3F);
221                self.remaining = &self.remaining[3..];
222                return Some(unsafe { char::from_u32_unchecked(point) });
223            }
224            let fourth = self.remaining[3];
225            if (u16::from(
226                UTF8_DATA.table[usize::from(second)] & UTF8_DATA.table[usize::from(first) + 0x80],
227            ) | u16::from(third >> 6)
228                | (u16::from(fourth & 0xC0) << 2))
229                != 0x202
230            {
231                break;
232            }
233            let point = ((u32::from(first) & 0x7) << 18)
234                | ((u32::from(second) & 0x3F) << 12)
235                | ((u32::from(third) & 0x3F) << 6)
236                | (u32::from(fourth) & 0x3F);
237            self.remaining = &self.remaining[4..];
238            return Some(unsafe { char::from_u32_unchecked(point) });
239        }
240        self.next_fallback()
241    }
242}
243
244impl<'a> DoubleEndedIterator for Utf8Chars<'a> {
245    #[inline]
246    fn next_back(&mut self) -> Option<char> {
247        if self.remaining.is_empty() {
248            return None;
249        }
250        let mut attempt = 1;
251        for b in self.remaining.iter().rev() {
252            if b & 0xC0 != 0x80 {
253                let (head, tail) = self.remaining.split_at(self.remaining.len() - attempt);
254                let mut inner = Utf8Chars::new(tail);
255                let candidate = inner.next();
256                if inner.as_slice().is_empty() {
257                    self.remaining = head;
258                    return candidate;
259                }
260                break;
261            }
262            if attempt == 4 {
263                break;
264            }
265            attempt += 1;
266        }
267
268        self.remaining = &self.remaining[..self.remaining.len() - 1];
269        Some('\u{FFFD}')
270    }
271}
272
273impl FusedIterator for Utf8Chars<'_> {}
274
275/// Convenience trait that adds `chars()` and `char_indices()` methods
276/// similar to the ones on string slices to byte slices.
277pub trait Utf8CharsEx {
278    fn chars(&self) -> Utf8Chars<'_>;
279    fn char_indices(&self) -> Utf8CharIndices<'_>;
280}
281
282impl Utf8CharsEx for [u8] {
283    /// Convenience method for creating an UTF-8 iterator
284    /// for the slice.
285    #[inline]
286    fn chars(&self) -> Utf8Chars<'_> {
287        Utf8Chars::new(self)
288    }
289    /// Convenience method for creating a byte index and
290    /// UTF-8 iterator for the slice.
291    #[inline]
292    fn char_indices(&self) -> Utf8CharIndices<'_> {
293        Utf8CharIndices::new(self)
294    }
295}
296
297// No manually-written tests for forward-iteration, because the code passed multiple
298// days of fuzzing comparing with known-good behavior.
mozjs_utf8_iter/lib.rs

mozjs_utf8_iter/
lib.rs
