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