1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10 use core::fmt::{self, Write};
11 use core::iter::Fuse;
12 use core::ops::Range;
13 use tinyvec::TinyVec;
14 
15 #[derive(Clone)]
16 enum DecompositionType {
17     Canonical,
18     Compatible,
19 }
20 
21 /// External iterator for a string decomposition's characters.
22 #[derive(Clone)]
23 pub struct Decompositions<I> {
24     kind: DecompositionType,
25     iter: Fuse<I>,
26 
27     // This buffer stores pairs of (canonical combining class, character),
28     // pushed onto the end in text order.
29     //
30     // It's divided into up to three sections:
31     // 1) A prefix that is free space;
32     // 2) "Ready" characters which are sorted and ready to emit on demand;
33     // 3) A "pending" block which stills needs more characters for us to be able
34     //    to sort in canonical order and is not safe to emit.
35     buffer: TinyVec<[(u8, char); 4]>,
36     ready: Range<usize>,
37 }
38 
39 #[inline]
new_canonical<I: Iterator<Item = char>>(iter: I) -> Decompositions<I>40 pub fn new_canonical<I: Iterator<Item = char>>(iter: I) -> Decompositions<I> {
41     Decompositions {
42         kind: self::DecompositionType::Canonical,
43         iter: iter.fuse(),
44         buffer: TinyVec::new(),
45         ready: 0..0,
46     }
47 }
48 
49 #[inline]
new_compatible<I: Iterator<Item = char>>(iter: I) -> Decompositions<I>50 pub fn new_compatible<I: Iterator<Item = char>>(iter: I) -> Decompositions<I> {
51     Decompositions {
52         kind: self::DecompositionType::Compatible,
53         iter: iter.fuse(),
54         buffer: TinyVec::new(),
55         ready: 0..0,
56     }
57 }
58 
59 impl<I> Decompositions<I> {
60     #[inline]
push_back(&mut self, ch: char)61     fn push_back(&mut self, ch: char) {
62         let class = super::char::canonical_combining_class(ch);
63 
64         if class == 0 {
65             self.sort_pending();
66             self.buffer.push((class, ch));
67             self.ready.end = self.buffer.len();
68         } else {
69             self.buffer.push((class, ch));
70         }
71     }
72 
73     #[inline]
sort_pending(&mut self)74     fn sort_pending(&mut self) {
75         // NB: `sort_by_key` is stable, so it will preserve the original text's
76         // order within a combining class.
77         self.buffer[self.ready.end..].sort_by_key(|k| k.0);
78     }
79 
80     #[inline]
reset_buffer(&mut self)81     fn reset_buffer(&mut self) {
82         // Equivalent to `self.buffer.drain(0..self.ready.end)`
83         // but faster than drain() if the buffer is a SmallVec or TinyVec
84         let pending = self.buffer.len() - self.ready.end;
85         for i in 0..pending {
86             self.buffer[i] = self.buffer[i + self.ready.end];
87         }
88         self.buffer.truncate(pending);
89         self.ready = 0..0;
90     }
91 
92     #[inline]
increment_next_ready(&mut self)93     fn increment_next_ready(&mut self) {
94         let next = self.ready.start + 1;
95         if next == self.ready.end {
96             self.reset_buffer();
97         } else {
98             self.ready.start = next;
99         }
100     }
101 }
102 
103 impl<I: Iterator<Item = char>> Iterator for Decompositions<I> {
104     type Item = char;
105 
106     #[inline]
next(&mut self) -> Option<char>107     fn next(&mut self) -> Option<char> {
108         while self.ready.end == 0 {
109             match (self.iter.next(), &self.kind) {
110                 (Some(ch), &DecompositionType::Canonical) => {
111                     super::char::decompose_canonical(ch, |d| self.push_back(d));
112                 }
113                 (Some(ch), &DecompositionType::Compatible) => {
114                     super::char::decompose_compatible(ch, |d| self.push_back(d));
115                 }
116                 (None, _) => {
117                     if self.buffer.is_empty() {
118                         return None;
119                     } else {
120                         self.sort_pending();
121                         self.ready.end = self.buffer.len();
122 
123                         // This implementation means that we can call `next`
124                         // on an exhausted iterator; the last outer `next` call
125                         // will result in an inner `next` call. To make this
126                         // safe, we use `fuse`.
127                         break;
128                     }
129                 }
130             }
131         }
132 
133         // We can assume here that, if `self.ready.end` is greater than zero,
134         // it's also greater than `self.ready.start`. That's because we only
135         // increment `self.ready.start` inside `increment_next_ready`, and
136         // whenever it reaches equality with `self.ready.end`, we reset both
137         // to zero, maintaining the invariant that:
138         //      self.ready.start < self.ready.end || self.ready.end == self.ready.start == 0
139         //
140         // This less-than-obviously-safe implementation is chosen for performance,
141         // minimizing the number & complexity of branches in `next` in the common
142         // case of buffering then unbuffering a single character with each call.
143         let (_, ch) = self.buffer[self.ready.start];
144         self.increment_next_ready();
145         Some(ch)
146     }
147 
size_hint(&self) -> (usize, Option<usize>)148     fn size_hint(&self) -> (usize, Option<usize>) {
149         let (lower, _) = self.iter.size_hint();
150         (lower, None)
151     }
152 }
153 
154 impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result155     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
156         for c in self.clone() {
157             f.write_char(c)?;
158         }
159         Ok(())
160     }
161 }
162