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 }
67
68 self.buffer.push((class, ch));
69 }
70
71 #[inline]
sort_pending(&mut self)72 fn sort_pending(&mut self) {
73 // NB: `sort_by_key` is stable, so it will preserve the original text's
74 // order within a combining class.
75 self.buffer[self.ready.end..].sort_by_key(|k| k.0);
76 self.ready.end = self.buffer.len();
77 }
78
79 #[inline]
reset_buffer(&mut self)80 fn reset_buffer(&mut self) {
81 // Equivalent to `self.buffer.drain(0..self.ready.end)`
82 // but faster than drain() if the buffer is a SmallVec or TinyVec
83 let pending = self.buffer.len() - self.ready.end;
84 for i in 0..pending {
85 self.buffer[i] = self.buffer[i + self.ready.end];
86 }
87 self.buffer.truncate(pending);
88 self.ready = 0..0;
89 }
90
91 #[inline]
increment_next_ready(&mut self)92 fn increment_next_ready(&mut self) {
93 let next = self.ready.start + 1;
94 if next == self.ready.end {
95 self.reset_buffer();
96 } else {
97 self.ready.start = next;
98 }
99 }
100 }
101
102 impl<I: Iterator<Item = char>> Iterator for Decompositions<I> {
103 type Item = char;
104
105 #[inline]
next(&mut self) -> Option<char>106 fn next(&mut self) -> Option<char> {
107 while self.ready.end == 0 {
108 match (self.iter.next(), &self.kind) {
109 (Some(ch), &DecompositionType::Canonical) => {
110 super::char::decompose_canonical(ch, |d| self.push_back(d));
111 }
112 (Some(ch), &DecompositionType::Compatible) => {
113 super::char::decompose_compatible(ch, |d| self.push_back(d));
114 }
115 (None, _) => {
116 if self.buffer.is_empty() {
117 return None;
118 } else {
119 self.sort_pending();
120
121 // This implementation means that we can call `next`
122 // on an exhausted iterator; the last outer `next` call
123 // will result in an inner `next` call. To make this
124 // safe, we use `fuse`.
125 break;
126 }
127 }
128 }
129 }
130
131 // We can assume here that, if `self.ready.end` is greater than zero,
132 // it's also greater than `self.ready.start`. That's because we only
133 // increment `self.ready.start` inside `increment_next_ready`, and
134 // whenever it reaches equality with `self.ready.end`, we reset both
135 // to zero, maintaining the invariant that:
136 // self.ready.start < self.ready.end || self.ready.end == self.ready.start == 0
137 //
138 // This less-than-obviously-safe implementation is chosen for performance,
139 // minimizing the number & complexity of branches in `next` in the common
140 // case of buffering then unbuffering a single character with each call.
141 let (_, ch) = self.buffer[self.ready.start];
142 self.increment_next_ready();
143 Some(ch)
144 }
145
size_hint(&self) -> (usize, Option<usize>)146 fn size_hint(&self) -> (usize, Option<usize>) {
147 let (lower, _) = self.iter.size_hint();
148 (lower, None)
149 }
150 }
151
152 impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result153 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
154 for c in self.clone() {
155 f.write_char(c)?;
156 }
157 Ok(())
158 }
159 }
160