utf8_iter/handler.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//! UTF-8 decoding with pluggable handler for the four byte sequence
18//! lengths and error.
19//!
20//! The handler implementation is expected not to mutate any state.
21//! Its primary purpose is to allow read-only data structure lookups
22//! to be fused into the decoder when the data structure layout benefits
23//! from knowing more UTF-8 structure detail than `char` provides.
24
25use core::iter::FusedIterator;
26
27use utf_types::utf8::Ascii;
28use utf_types::utf8::FourByteSequence;
29use utf_types::utf8::PreparedThreeBytes;
30use utf_types::utf8::PreparedTwoBytes;
31use utf_types::utf8::ThreeByteSequence;
32use utf_types::utf8::TwoByteSequence;
33
34const SEQUENCE_FOR_REPLACEMENT_CHARACTER: ThreeByteSequence = const {
35 if let Ok(sequence) = ThreeByteSequence::try_new(0xEF, 0xBF, 0xBD) {
36 sequence
37 } else {
38 panic!()
39 }
40};
41
42/// Mapping from the four kinds of byte sequences or error
43/// to output.
44pub trait Utf8Handler {
45 /// The per-scalar-value output type. (In the common case,
46 /// this is `char`.)
47 type Output;
48
49 /// Map a single-byte UTF-8 sequence to `Output`.
50 ///
51 /// When `Output` is `char`, `ascii.to_char()`
52 /// is the appropriate implementation.
53 ///
54 /// The implementation is expected to be marked
55 /// `#[inline(always)]`.
56 fn single_byte(&self, ascii: Ascii) -> Self::Output;
57
58 /// Map a two-byte UTF-8 sequence to `Output`.
59 ///
60 /// When `Output` is `char`, `sequence.to_char()`
61 /// is the appropriate implementation.
62 ///
63 /// The implementation is expected to be marked
64 /// `#[inline(always)]`.
65 fn two_byte(&self, sequence: TwoByteSequence) -> Self::Output;
66
67 /// Map a three-byte UTF-8 sequence to `Output`.
68 ///
69 /// When `Output` is `char`, `sequence.to_char()`
70 /// is the appropriate implementation.
71 ///
72 /// The implementation is expected to be marked
73 /// `#[inline(always)]`.
74 fn three_byte(&self, sequence: ThreeByteSequence) -> Self::Output;
75
76 /// Map a four-byte UTF-8 sequence to `Output`.
77 ///
78 /// When `Output` is `char`, `sequence.to_char()`
79 /// is the appropriate implementation.
80 ///
81 /// The implementation is expected to be marked
82 /// `#[inline(always)]`.
83 fn four_byte(&self, sequence: FourByteSequence) -> Self::Output;
84
85 /// Map a single UTF-8 error to `Output`.
86 ///
87 /// What constitutes a single error is defined by the
88 /// WHATWG Encoding Standard.
89 ///
90 /// When `Output` is `char`,
91 /// `char::REPLACEMENT_CHARACTER`
92 /// is the appropriate implementation. The provided
93 /// implementation delegates to `three_byte` by
94 /// passing the three bytes that represent the
95 /// REPLACEMENT CHARACTER.
96 ///
97 /// The implementation of this method is expected to
98 /// be declared `#[inline(always)]`.
99 #[inline(always)]
100 fn error(&self) -> Self::Output {
101 self.three_byte(SEQUENCE_FOR_REPLACEMENT_CHARACTER)
102 }
103}
104
105/// Iterator by `char` over `&[u8]` that contains
106/// potentially-invalid UTF-8 with a handler for the four
107/// kinds of byte sequences (or error). See the crate documentation.
108#[derive(Debug)]
109pub struct Utf8CharsWithHandler<'a, H>
110where
111 H: Utf8Handler,
112{
113 remaining: &'a [u8],
114 handler: H,
115}
116
117impl<'a, H> Utf8CharsWithHandler<'a, H>
118where
119 H: Utf8Handler,
120{
121 #[inline(always)]
122 /// Creates the iterator from a byte slice and handler.
123 pub fn new(bytes: &'a [u8], handler: H) -> Self {
124 Utf8CharsWithHandler::<'a, H> {
125 remaining: bytes,
126 handler,
127 }
128 }
129
130 /// Views the current remaining data in the iterator as a subslice
131 /// of the original slice.
132 #[inline(always)]
133 pub fn as_slice(&self) -> &'a [u8] {
134 self.remaining
135 }
136
137 /// Obtains a reference to the handler.
138 #[inline(always)]
139 pub fn handler(&self) -> &H {
140 &self.handler
141 }
142
143 #[cold]
144 fn error(&self) -> H::Output {
145 self.handler.error()
146 }
147
148 // TODO: Add a method or per-sequence-length methods analogous to
149 // `CharsWithHandler::next_with_minimum_lead`. These would need
150 // to validate the sequences but not compute the `char` or invoke
151 // the handler for the characters that are skipped over.
152
153 #[cold]
154 #[inline(never)]
155 fn next_fallback(&mut self) -> Option<H::Output> {
156 let (&first, after_one) = self.remaining.split_first()?;
157 if let Ok(ascii) = Ascii::try_new(first) {
158 self.remaining = after_one;
159 return Some(self.handler.single_byte(ascii));
160 }
161 if let Some((&second, after_two)) = after_one.split_first() {
162 if let Ok(two_byte) = TwoByteSequence::try_new(first, second) {
163 self.remaining = after_two;
164 return Some(self.handler.two_byte(two_byte));
165 }
166 let prepared_two = PreparedTwoBytes::new(first, second);
167 if let Some((&third, after_three)) = after_two.split_first() {
168 let prepared_three = PreparedThreeBytes::new_with_prepared(prepared_two, third);
169 if let Ok(three_byte) = ThreeByteSequence::try_new_with_prepared(prepared_three) {
170 self.remaining = after_three;
171 return Some(self.handler.three_byte(three_byte));
172 }
173 // We have already determined that we don't have a single-byte,
174 // two-byte, or three-byte sequence.
175 // We cannot have a well-formed four-byte sequence, because if
176 // we had one, `next` would have consumed it. Consume three bytes
177 // if we have a three-byte prefix of a four-byte sequence.
178 // Otherwise, fall through to consuming one byte.
179 if prepared_three.prefix_of_four_byte() {
180 self.remaining = after_three;
181 return Some(self.error());
182 }
183 }
184 // We have already determined
185 // that `first` is not ASCII and that `prepared_two` is not
186 // a two-byte UTF-8 sequence. If it is a prefix of a three-byte
187 // sequence or of a four-byte sequence, consume both bytes.
188 // Otherwise, fall through to consuming one byte.
189 if prepared_two.sequence_prefix() {
190 self.remaining = after_two;
191 return Some(self.error());
192 }
193 }
194 self.remaining = after_one;
195 Some(self.error())
196 }
197
198 #[cold]
199 #[inline(never)]
200 fn next_back_fallback(&mut self) -> Option<H::Output> {
201 let (&last, before_one) = self.remaining.split_last()?;
202 if let Ok(ascii) = Ascii::try_new(last) {
203 self.remaining = before_one;
204 return Some(self.handler.single_byte(ascii));
205 }
206 if let Some((&second_last, before_two)) = before_one.split_last() {
207 if let Ok(two_byte) = TwoByteSequence::try_new(second_last, last) {
208 self.remaining = before_two;
209 return Some(self.handler.two_byte(two_byte));
210 }
211 let prepared_two = PreparedTwoBytes::new(second_last, last);
212 if let Some((&third_last, before_three)) = before_two.split_last() {
213 let prepared_three = PreparedThreeBytes::new(third_last, second_last, last);
214 if let Ok(three_byte) = ThreeByteSequence::try_new_with_prepared(prepared_three) {
215 self.remaining = before_three;
216 return Some(self.handler.three_byte(three_byte));
217 }
218 // Consume three bytes if we have a three-byte prefix of a four-byte sequence.
219 if prepared_three.prefix_of_four_byte() {
220 self.remaining = before_three;
221 return Some(self.error());
222 }
223 }
224 // We've established that the two last bytes don't form a two-byte
225 // UTF-8 sequence, but they could form a two-byte prefix of a
226 // three-byte or four-byte sequence, in which case we need to consume
227 // two bytes instead of falling through to consuming just one byte.
228 // We have not established whether `second_last` is ASCII!
229 if prepared_two.sequence_prefix() {
230 self.remaining = before_two;
231 return Some(self.error());
232 }
233 }
234 self.remaining = before_one;
235 Some(self.error())
236 }
237}
238
239impl<'a, H> Iterator for Utf8CharsWithHandler<'a, H>
240where
241 H: Utf8Handler,
242{
243 type Item = H::Output;
244
245 #[inline(always)]
246 fn next(&mut self) -> Option<Self::Item> {
247 if self.remaining.len() >= 4 {
248 // UNWRAP: Length checked at the start of the method.
249 let (&first, after_one) = self.remaining.split_first().unwrap();
250 if let Ok(ascii) = Ascii::try_new(first) {
251 self.remaining = after_one;
252 return Some(self.handler.single_byte(ascii));
253 }
254 // UNWRAP: Length checked at the start of the method.
255 let (&second, after_two) = after_one.split_first().unwrap();
256 if let Ok(two_byte) = TwoByteSequence::try_new(first, second) {
257 self.remaining = after_two;
258 return Some(self.handler.two_byte(two_byte));
259 }
260 // UNWRAP: Length checked at the start of the method.
261 let (&third, after_three) = after_two.split_first().unwrap();
262 let prepared_three = PreparedThreeBytes::new(first, second, third);
263 if let Ok(three_byte) = ThreeByteSequence::try_new_with_prepared(prepared_three) {
264 self.remaining = after_three;
265 return Some(self.handler.three_byte(three_byte));
266 }
267 // UNWRAP: Length checked at the start of the method.
268 let (&fourth, after_four) = after_three.split_first().unwrap();
269 if let Ok(four_byte) = FourByteSequence::try_new_with_prepared(prepared_three, fourth) {
270 self.remaining = after_four;
271 return Some(self.handler.four_byte(four_byte));
272 }
273 }
274 self.next_fallback()
275 }
276
277 // TODO: Optimize `count` without a circular dependency
278
279 #[inline(always)]
280 fn size_hint(&self) -> (usize, Option<usize>) {
281 let len = self.remaining.len();
282 (len.div_ceil(4), Some(len))
283 }
284
285 #[inline(always)]
286 fn last(mut self) -> Option<Self::Item> {
287 // No need to go through the entire string.
288 self.next_back()
289 }
290}
291
292impl<'a, H> DoubleEndedIterator for Utf8CharsWithHandler<'a, H>
293where
294 H: Utf8Handler,
295{
296 #[inline(always)]
297 fn next_back(&mut self) -> Option<H::Output> {
298 if self.remaining.len() >= 4 {
299 // UNWRAP: Length checked at the start of the method.
300 let (&last, before_one) = self.remaining.split_last().unwrap();
301 if let Ok(ascii) = Ascii::try_new(last) {
302 self.remaining = before_one;
303 return Some(self.handler.single_byte(ascii));
304 }
305 // UNWRAP: Length checked at the start of the method.
306 let (&second_last, before_two) = before_one.split_last().unwrap();
307 if let Ok(two_byte) = TwoByteSequence::try_new(second_last, last) {
308 self.remaining = before_two;
309 return Some(self.handler.two_byte(two_byte));
310 }
311 // UNWRAP: Length checked at the start of the method.
312 let (&third_last, before_three) = before_two.split_last().unwrap();
313 if let Ok(three_byte) = ThreeByteSequence::try_new(third_last, second_last, last) {
314 self.remaining = before_three;
315 return Some(self.handler.three_byte(three_byte));
316 }
317 // UNWRAP: Length checked at the start of the method.
318 let (&fourth_last, before_four) = before_three.split_last().unwrap();
319 if let Ok(four_byte) =
320 FourByteSequence::try_new(fourth_last, third_last, second_last, last)
321 {
322 self.remaining = before_four;
323 return Some(self.handler.four_byte(four_byte));
324 }
325 }
326 self.next_back_fallback()
327 }
328}
329
330impl<H> FusedIterator for Utf8CharsWithHandler<'_, H> where H: Utf8Handler {}
331
332impl<'a, H> Clone for Utf8CharsWithHandler<'a, H>
333where
334 H: Utf8Handler + Clone,
335{
336 fn clone(&self) -> Self {
337 Self {
338 remaining: self.remaining,
339 handler: self.handler.clone(),
340 }
341 }
342}
343
344// No manually-written tests for forward-iteration, because the code passed multiple
345// days of fuzzing comparing with known-good behavior.