encode_unicode/decoding_iterators.rs
1/* Copyright 2018-2020 Torbjørn Birch Moltu
2 *
3 * Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4 * http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5 * http://opensource.org/licenses/MIT>, at your option. This file may not be
6 * copied, modified, or distributed except according to those terms.
7 */
8
9//! Iterators that turn multiple `u8`s or `u16`s into `Utf*Char`s, but can fail.
10//!
11//! To be predictable, all errors consume one element each.
12//!
13//! The iterator adaptors produce neither offset nor element length to work
14//! well with other adaptors,
15//! while the slice iterators yield both to make more advanced use cases easy.
16
17use crate::errors::{Utf16FirstUnitError, Utf16PairError, Utf8Error};
18use crate::errors::Utf16SliceError::*;
19use crate::errors::Utf16PairError::*;
20use crate::errors::Utf8ErrorKind::*;
21use crate::utf8_char::Utf8Char;
22use crate::utf16_char::Utf16Char;
23use crate::traits::U16UtfExt;
24extern crate core;
25use core::borrow::Borrow;
26use core::fmt::{self, Debug};
27use core::iter::Chain;
28use core::option;
29
30
31/// Decodes UTF-8 characters from a byte iterator into `Utf8Char`s.
32///
33/// See [`IterExt::to_utf8chars()`](../trait.IterExt.html#tymethod.to_utf8chars)
34/// for examples and error handling.
35#[derive(Clone, Default)]
36pub struct Utf8CharMerger<B:Borrow<u8>, I:Iterator<Item=B>> {
37 iter: I,
38 /// number of bytes that were read before an error was detected
39 after_err_leftover: u8,
40 /// stack because it simplifies popping.
41 after_err_stack: [u8; 3],
42}
43impl<B:Borrow<u8>, I:Iterator<Item=B>, T:IntoIterator<IntoIter=I,Item=B>>
44From<T> for Utf8CharMerger<B, I> {
45 fn from(t: T) -> Self {
46 Utf8CharMerger {
47 iter: t.into_iter(),
48 after_err_leftover: 0,
49 after_err_stack: [0; 3],
50 }
51 }
52}
53impl<B:Borrow<u8>, I:Iterator<Item=B>> Utf8CharMerger<B,I> {
54 /// Extract the inner iterator.
55 ///
56 /// If the last item produced by `.next()` was an `Err`,
57 /// up to three following bytes might be missing.
58 /// The exact number of missing bytes for each error type should not be relied on.
59 ///
60 /// # Examples
61 ///
62 /// Three bytes swallowed:
63 /// ```
64 /// # use encode_unicode::IterExt;
65 /// let mut merger = b"\xf4\xa1\xb2FS".iter().to_utf8chars();
66 /// assert!(merger.next().unwrap().is_err());
67 /// let mut inner: std::slice::Iter<u8> = merger.into_inner();
68 /// assert_eq!(inner.next(), Some(&b'S')); // b'\xa1', b'\xb2' and b'F' disappeared
69 /// ```
70 ///
71 /// All bytes present:
72 /// ```
73 /// # use encode_unicode::IterExt;
74 /// let mut merger = b"\xb0FS".iter().to_utf8chars();
75 /// assert!(merger.next().unwrap().is_err());
76 /// assert_eq!(merger.into_inner().next(), Some(&b'F'));
77 /// ```
78 ///
79 /// Two bytes missing:
80 /// ```
81 /// # use encode_unicode::IterExt;
82 /// let mut merger = b"\xe0\x80\x80FS".iter().to_utf8chars();
83 /// assert!(merger.next().unwrap().is_err());
84 /// assert_eq!(merger.into_inner().next(), Some(&b'F'));
85 /// ```
86 pub fn into_inner(self) -> I {
87 self.iter
88 }
89
90 fn save(&mut self, bytes: &[u8;4], len: usize) {
91 // forget bytes[0] and push the others onto self.after_err_stack (in reverse).
92 for &after_err in bytes[1..len].iter().rev() {
93 self.after_err_stack[self.after_err_leftover as usize] = after_err;
94 self.after_err_leftover += 1;
95 }
96 }
97 /// Reads len-1 bytes into bytes[1..]
98 fn extra(&mut self, bytes: &mut[u8;4], len: usize) -> Result<(),Utf8Error> {
99 // This is the only function that pushes onto after_err_stack,
100 // and it checks that all bytes are continuation bytes before fetching the next one.
101 // Therefore only the last byte retrieved can be a non-continuation byte.
102 // That last byte is also the last to be retrieved from after_err.
103 //
104 // Before this function is called, there has been retrieved at least one byte.
105 // If that byte was a continuation byte, next() produces an error
106 // and won't call this function.
107 // Therefore, we know that after_err is empty at this point.
108 // This means that we can use self.iter directly, and knows where to start pushing
109 debug_assert_eq!(self.after_err_leftover, 0, "first: {:#02x}, stack: {:?}", bytes[0], self.after_err_stack);
110 for i in 1..len {
111 if let Some(extra) = self.iter.next() {
112 let extra = *extra.borrow();
113 bytes[i] = extra;
114 if extra & 0b1100_0000 != 0b1000_0000 {
115 // not a continuation byte
116 self.save(bytes, i+1);
117 return Err(Utf8Error{ kind: InterruptedSequence })
118 }
119 } else {
120 self.save(bytes, i);
121 return Err(Utf8Error{ kind: TooFewBytes });
122 }
123 }
124 Ok(())
125 }
126}
127impl<B:Borrow<u8>, I:Iterator<Item=B>> Iterator for Utf8CharMerger<B,I> {
128 type Item = Result<Utf8Char,Utf8Error>;
129 fn next(&mut self) -> Option<Self::Item> {
130 let first: u8;
131 if self.after_err_leftover != 0 {
132 self.after_err_leftover -= 1;
133 first = self.after_err_stack[self.after_err_leftover as usize];
134 } else if let Some(next) = self.iter.next() {
135 first = *next.borrow();
136 } else {
137 return None;
138 }
139
140 unsafe {
141 let mut bytes = [first, 0, 0, 0];
142 let ok = match first {
143 0b0000_0000..=0b0111_1111 => {/*1 and */Ok(())},
144 0b1100_0010..=0b1101_1111 => {//2 and not overlong
145 self.extra(&mut bytes, 2) // no extra validation required
146 },
147 0b1110_0000..=0b1110_1111 => {//3
148 if let Err(e) = self.extra(&mut bytes, 3) {
149 Err(e)
150 } else if bytes[0] == 0b1110_0000 && bytes[1] <= 0b10_011111 {
151 self.save(&bytes, 3);
152 Err(Utf8Error{ kind: OverlongEncoding })
153 } else if bytes[0] == 0b1110_1101 && bytes[1] & 0b11_100000 == 0b10_100000 {
154 self.save(&bytes, 3);
155 Err(Utf8Error{ kind: Utf16ReservedCodepoint })
156 } else {
157 Ok(())
158 }
159 },
160 0b1111_0000..=0b1111_0100 => {//4
161 if let Err(e) = self.extra(&mut bytes, 4) {
162 Err(e)
163 } else if bytes[0] == 0b11110_000 && bytes[1] <= 0b10_001111 {
164 self.save(&bytes, 4);
165 Err(Utf8Error{ kind: OverlongEncoding })
166 } else if bytes[0] == 0b11110_100 && bytes[1] > 0b10_001111 {
167 self.save(&bytes, 4);
168 Err(Utf8Error{ kind: TooHighCodepoint })
169 } else {
170 Ok(())
171 }
172 },
173 0b1000_0000..=0b1011_1111 => {// continuation byte
174 Err(Utf8Error{ kind: UnexpectedContinuationByte })
175 },
176 0b1100_0000..=0b1100_0001 => {// 2 and overlong
177 Err(Utf8Error{ kind: NonUtf8Byte })
178 },
179 0b1111_0101..=0b1111_0111 => {// 4 and too high codepoint
180 Err(Utf8Error{ kind: NonUtf8Byte })
181 },
182 0b1111_1000..=0b1111_1111 => {
183 Err(Utf8Error{ kind: NonUtf8Byte })
184 },
185 };
186 Some(ok.map(|()| Utf8Char::from_array_unchecked(bytes) ))
187 }
188 }
189 fn size_hint(&self) -> (usize,Option<usize>) {
190 let (iter_min, iter_max) = self.iter.size_hint();
191 // cannot be exact, so KISS
192 let min = iter_min / 4; // don't bother rounding up or accounting for after_err
193 // handle edge case of max > usize::MAX-3 just in case.
194 // Using wrapping_add() wouldn't violate any API contract as the trait isn't unsafe.
195 let max = iter_max.and_then(|max| {
196 max.checked_add(self.after_err_leftover as usize)
197 });
198 (min, max)
199 }
200}
201impl<B:Borrow<u8>, I:Iterator<Item=B>+Debug> Debug for Utf8CharMerger<B,I> {
202 fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result {
203 let mut in_order = [0u8; 3];
204 for i in 0..self.after_err_leftover as usize {
205 in_order[i] = self.after_err_stack[self.after_err_leftover as usize - i - 1];
206 }
207 fmtr.debug_struct("Utf8CharMerger")
208 .field("buffered", &&in_order[..self.after_err_leftover as usize])
209 .field("inner", &self.iter)
210 .finish()
211 }
212}
213
214
215/// An [`Utf8CharMerger`](struct.Utf8CharMerger.html) that also produces
216/// offsets and lengths, but can only iterate over slices.
217///
218/// See [`SliceExt::utf8char_indices()`](../trait.SliceExt.html#tymethod.utf8char_indices)
219/// for examples and error handling.
220#[derive(Clone, Default)]
221pub struct Utf8CharDecoder<'a> {
222 slice: &'a[u8],
223 index: usize,
224}
225impl<'a> From<&'a[u8]> for Utf8CharDecoder<'a> {
226 fn from(s: &[u8]) -> Utf8CharDecoder {
227 Utf8CharDecoder { slice: s, index: 0 }
228 }
229}
230impl<'a> Utf8CharDecoder<'a> {
231 /// Extract the remainder of the source slice.
232 ///
233 /// # Examples
234 ///
235 /// Unlike `Utf8CharMerger::into_inner()`, bytes directly after an error
236 /// are never swallowed:
237 /// ```
238 /// # use encode_unicode::SliceExt;
239 /// let mut iter = b"\xf4\xa1\xb2FS".utf8char_indices();
240 /// assert!(iter.next().unwrap().1.is_err());
241 /// assert_eq!(iter.as_slice(), b"\xa1\xb2FS");
242 /// ```
243 pub fn as_slice(&self) -> &'a[u8] {
244 &self.slice[self.index..]
245 }
246}
247impl<'a> Iterator for Utf8CharDecoder<'a> {
248 type Item = (usize, Result<Utf8Char,Utf8Error>, usize);
249 fn next(&mut self) -> Option<Self::Item> {
250 let start = self.index;
251 match Utf8Char::from_slice_start(&self.slice[self.index..]) {
252 Ok((u8c, len)) => {
253 self.index += len;
254 Some((start, Ok(u8c), len))
255 },
256 Err(_) if self.slice.len() <= self.index => None,
257 Err(e) => {
258 self.index += 1;
259 Some((start, Err(e), 1))
260 }
261 }
262 }
263 #[inline]
264 fn size_hint(&self) -> (usize,Option<usize>) {
265 let bytes = self.slice.len() - self.index;
266 // Cannot be exact, so KISS and don't bother rounding up.
267 // The slice is unlikely be full of 4-byte codepoints, so buffers
268 // allocated with the lower bound will have to be grown anyway.
269 (bytes/4, Some(bytes))
270 }
271}
272impl<'a> DoubleEndedIterator for Utf8CharDecoder<'a> {
273 fn next_back(&mut self) -> Option<Self::Item> {
274 if self.index < self.slice.len() {
275 let extras = self.slice.iter()
276 .rev()
277 .take_while(|&b| b & 0b1100_0000 == 0b1000_0000 )
278 .count();
279 let starts = self.slice.len() - (extras+1);
280 match Utf8Char::from_slice_start(&self.slice[starts..]) {
281 Ok((u8c,len)) if len == 1+extras => {
282 self.slice = &self.slice[..starts];
283 Some((starts, Ok(u8c), len))
284 },
285 // This enures errors for every byte in both directions,
286 // but means overlong and codepoint errors will be turned into
287 // tooshort errors.
288 Err(e) if extras == 0 => {
289 self.slice = &self.slice[..self.slice.len()-1];
290 Some((self.slice.len()-1, Err(e), 1))
291 },
292 _ => {
293 self.slice = &self.slice[..self.slice.len()-1];
294 Some((self.slice.len()-1, Err(Utf8Error{ kind: UnexpectedContinuationByte }), 1))
295 },
296 }
297 } else {
298 None
299 }
300 }
301}
302impl<'a> Debug for Utf8CharDecoder<'a> {
303 fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result {
304 write!(fmtr, "Utf8CharDecoder {{ bytes[{}..]: {:?} }}", self.index, self.as_slice())
305 }
306}
307
308
309
310/// Decodes UTF-16 characters from a `u16` iterator into `Utf16Char`s.
311///
312/// See [`IterExt::to_utf16chars()`](../trait.IterExt.html#tymethod.to_utf16chars)
313/// for examples and error handling.
314#[derive(Clone, Default)]
315pub struct Utf16CharMerger<B:Borrow<u16>, I:Iterator<Item=B>> {
316 iter: I,
317 /// Used when a trailing surrogate was expected, the u16 can be any value.
318 prev: Option<B>,
319}
320impl<B:Borrow<u16>, I:Iterator<Item=B>, T:IntoIterator<IntoIter=I,Item=B>>
321From<T> for Utf16CharMerger<B,I> {
322 fn from(t: T) -> Self {
323 Utf16CharMerger { iter: t.into_iter(), prev: None }
324 }
325}
326impl<B:Borrow<u16>, I:Iterator<Item=B>> Utf16CharMerger<B,I> {
327 /// Extract the inner iterator.
328 ///
329 /// If the last item produced was an `Err`, the first unit might be missing.
330 ///
331 /// # Examples
332 ///
333 /// Unit right after an error missing
334 /// ```
335 /// # use encode_unicode::IterExt;
336 /// # use encode_unicode::error::Utf16PairError;
337 /// let mut merger = [0xd901, 'F' as u16, 'S' as u16].iter().to_utf16chars();
338 /// assert_eq!(merger.next(), Some(Err(Utf16PairError::UnmatchedLeadingSurrogate)));
339 /// let mut inner: std::slice::Iter<u16> = merger.into_inner();
340 /// assert_eq!(inner.next(), Some('S' as u16).as_ref()); // 'F' was consumed by Utf16CharMerger
341 /// ```
342 ///
343 /// Error that doesn't swallow any units
344 /// ```
345 /// # use encode_unicode::IterExt;
346 /// # use encode_unicode::error::Utf16PairError;
347 /// let mut merger = [0xde00, 'F' as u16, 'S' as u16].iter().to_utf16chars();
348 /// assert_eq!(merger.next(), Some(Err(Utf16PairError::UnexpectedTrailingSurrogate)));
349 /// let mut inner: std::slice::Iter<u16> = merger.into_inner();
350 /// assert_eq!(inner.next(), Some('F' as u16).as_ref()); // not consumed
351 /// ```
352 pub fn into_inner(self) -> I {
353 self.iter
354 }
355 /// Returns an iterator over the remaining units.
356 /// Unlike `into_inner()` this will never drop any units.
357 ///
358 /// The exact type of the returned iterator should not be depended on.
359 ///
360 /// # Examples
361 ///
362 /// ```
363 /// # use encode_unicode::IterExt;
364 /// # use encode_unicode::error::Utf16PairError;
365 /// let slice = [0xd901, 'F' as u16, 'S' as u16];
366 /// let mut merger = slice.iter().to_utf16chars();
367 /// assert_eq!(merger.next(), Some(Err(Utf16PairError::UnmatchedLeadingSurrogate)));
368 /// let mut remaining = merger.into_remaining_units();
369 /// assert_eq!(remaining.next(), Some('F' as u16).as_ref());
370 /// ```
371 pub fn into_remaining_units(self) -> Chain<option::IntoIter<B>,I> {
372 self.prev.into_iter().chain(self.iter)
373 }
374}
375impl<B:Borrow<u16>, I:Iterator<Item=B>> Iterator for Utf16CharMerger<B,I> {
376 type Item = Result<Utf16Char,Utf16PairError>;
377 fn next(&mut self) -> Option<Self::Item> {
378 let first = self.prev.take().or_else(|| self.iter.next() );
379 first.map(|first| unsafe {
380 match first.borrow().utf16_needs_extra_unit() {
381 Ok(false) => Ok(Utf16Char::from_array_unchecked([*first.borrow(), 0])),
382 Ok(true) => match self.iter.next() {
383 Some(second) => match second.borrow().utf16_needs_extra_unit() {
384 Err(Utf16FirstUnitError) => Ok(Utf16Char::from_tuple_unchecked((
385 *first.borrow(),
386 Some(*second.borrow())
387 ))),
388 Ok(_) => {
389 self.prev = Some(second);
390 Err(Utf16PairError::UnmatchedLeadingSurrogate)
391 }
392 },
393 None => Err(Utf16PairError::Incomplete)
394 },
395 Err(Utf16FirstUnitError) => Err(Utf16PairError::UnexpectedTrailingSurrogate),
396 }
397 })
398 }
399 fn size_hint(&self) -> (usize,Option<usize>) {
400 let (iter_min, iter_max) = self.iter.size_hint();
401 // cannot be exact, so KISS
402 let min = iter_min / 2; // don't bother rounding up or accounting for self.prev
403 let max = match (iter_max, &self.prev) {
404 (Some(max), &Some(_)) => max.checked_add(1),
405 (max, _) => max,
406 };
407 (min, max)
408 }
409}
410impl<B:Borrow<u16>, I:Iterator<Item=B>+Debug> Debug for Utf16CharMerger<B,I> {
411 fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result {
412 fmtr.debug_struct("Utf16CharMerger")
413 .field("buffered", &self.prev.as_ref().map(|b| *b.borrow() ))
414 .field("inner", &self.iter)
415 .finish()
416 }
417}
418
419
420/// An [`Utf16CharMerger`](struct.Utf16CharMerger.html) that also produces
421/// offsets and lengths, but can only iterate over slices.
422///
423/// See [`SliceExt::utf16char_indices()`](../trait.SliceExt.html#tymethod.utf16char_indices)
424/// for examples and error handling.
425#[derive(Clone, Default)]
426pub struct Utf16CharDecoder<'a> {
427 slice: &'a[u16],
428 index: usize,
429}
430impl<'a> From<&'a[u16]> for Utf16CharDecoder<'a> {
431 fn from(s: &'a[u16]) -> Self {
432 Utf16CharDecoder{ slice: s, index: 0 }
433 }
434}
435impl<'a> Utf16CharDecoder<'a> {
436 /// Extract the remainder of the source slice.
437 ///
438 /// # Examples
439 ///
440 /// Unlike `Utf16CharMerger::into_inner()`, the unit after an error is never swallowed:
441 /// ```
442 /// # use encode_unicode::SliceExt;
443 /// # use encode_unicode::error::Utf16PairError;
444 /// let mut iter = [0xd901, 'F' as u16, 'S' as u16].utf16char_indices();
445 /// assert_eq!(iter.next(), Some((0, Err(Utf16PairError::UnmatchedLeadingSurrogate), 1)));
446 /// assert_eq!(iter.as_slice(), &['F' as u16, 'S' as u16]);
447 /// ```
448 pub fn as_slice(&self) -> &[u16] {
449 &self.slice[self.index..]
450 }
451}
452impl<'a> Iterator for Utf16CharDecoder<'a> {
453 type Item = (usize,Result<Utf16Char,Utf16PairError>,usize);
454 #[inline]
455 fn next(&mut self) -> Option<Self::Item> {
456 let start = self.index;
457 match Utf16Char::from_slice_start(self.as_slice()) {
458 Ok((u16c,len)) => {
459 self.index += len;
460 Some((start, Ok(u16c), len))
461 },
462 Err(EmptySlice) => None,
463 Err(FirstIsTrailingSurrogate) => {
464 self.index += 1;
465 Some((start, Err(UnexpectedTrailingSurrogate), 1))
466 },
467 Err(SecondIsNotTrailingSurrogate) => {
468 self.index += 1;
469 Some((start, Err(UnmatchedLeadingSurrogate), 1))
470 },
471 Err(MissingSecond) => {
472 self.index = self.slice.len();
473 Some((start, Err(Incomplete), 1))
474 }
475 }
476 }
477 #[inline]
478 fn size_hint(&self) -> (usize,Option<usize>) {
479 let units = self.slice.len() - self.index;
480 // Cannot be exact, so KISS and don't bother rounding up.
481 // The slice is unlikely be full of surrogate pairs, so buffers
482 // allocated with the lower bound will have to be grown anyway.
483 (units/2, Some(units))
484 }
485}
486impl<'a> Debug for Utf16CharDecoder<'a> {
487 fn fmt(&self, fmtr: &mut fmt::Formatter) -> fmt::Result {
488 write!(fmtr, "Utf16CharDecoder {{ units[{}..]: {:?} }}", self.index, self.as_slice())
489 }
490}