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.
10use core::fmt::{self, Write};
11use core::iter::{Fuse, FusedIterator};
12use core::ops::Range;
13use tinyvec::TinyVec;
14
15#[derive(Clone)]
16enum DecompositionType {
17 Canonical,
18 Compatible,
19}
20
21/// External iterator for a string decomposition's characters.
22#[derive(Clone)]
23pub 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
39impl<I: Iterator<Item = char>> Decompositions<I> {
40 /// Create a new decomposition iterator for canonical decompositions (NFD)
41 ///
42 /// Note that this iterator can also be obtained by directly calling [`.nfd()`](crate::UnicodeNormalization::nfd)
43 /// on the iterator.
44 #[inline]
45 pub fn new_canonical(iter: I) -> Decompositions<I> {
46 Decompositions {
47 kind: self::DecompositionType::Canonical,
48 iter: iter.fuse(),
49 buffer: TinyVec::new(),
50 ready: 0..0,
51 }
52 }
53
54 /// Create a new decomposition iterator for compatability decompositions (NFkD)
55 ///
56 /// Note that this iterator can also be obtained by directly calling [`.nfd()`](crate::UnicodeNormalization::nfd)
57 /// on the iterator.
58 #[inline]
59 pub fn new_compatible(iter: I) -> Decompositions<I> {
60 Decompositions {
61 kind: self::DecompositionType::Compatible,
62 iter: iter.fuse(),
63 buffer: TinyVec::new(),
64 ready: 0..0,
65 }
66 }
67}
68
69impl<I> Decompositions<I> {
70 #[inline]
71 fn push_back(&mut self, ch: char) {
72 let class = super::char::canonical_combining_class(ch);
73
74 if class == 0 {
75 self.sort_pending();
76 self.buffer.push((class, ch));
77 self.ready.end = self.buffer.len();
78 } else {
79 self.buffer.push((class, ch));
80 }
81 }
82
83 #[inline]
84 fn sort_pending(&mut self) {
85 // NB: `sort_by_key` is stable, so it will preserve the original text's
86 // order within a combining class.
87 self.buffer[self.ready.end..].sort_by_key(|k| k.0);
88 }
89
90 #[inline]
91 fn reset_buffer(&mut self) {
92 // Equivalent to `self.buffer.drain(0..self.ready.end)`
93 // but faster than drain() if the buffer is a SmallVec or TinyVec
94 let pending = self.buffer.len() - self.ready.end;
95 for i in 0..pending {
96 self.buffer[i] = self.buffer[i + self.ready.end];
97 }
98 self.buffer.truncate(pending);
99 self.ready = 0..0;
100 }
101
102 #[inline]
103 fn increment_next_ready(&mut self) {
104 let next = self.ready.start + 1;
105 if next == self.ready.end {
106 self.reset_buffer();
107 } else {
108 self.ready.start = next;
109 }
110 }
111}
112
113impl<I: Iterator<Item = char>> Iterator for Decompositions<I> {
114 type Item = char;
115
116 #[inline]
117 fn next(&mut self) -> Option<char> {
118 while self.ready.end == 0 {
119 match (self.iter.next(), &self.kind) {
120 (Some(ch), &DecompositionType::Canonical) => {
121 super::char::decompose_canonical(ch, |d| self.push_back(d));
122 }
123 (Some(ch), &DecompositionType::Compatible) => {
124 super::char::decompose_compatible(ch, |d| self.push_back(d));
125 }
126 (None, _) => {
127 if self.buffer.is_empty() {
128 return None;
129 } else {
130 self.sort_pending();
131 self.ready.end = self.buffer.len();
132
133 // This implementation means that we can call `next`
134 // on an exhausted iterator; the last outer `next` call
135 // will result in an inner `next` call. To make this
136 // safe, we use `fuse`.
137 break;
138 }
139 }
140 }
141 }
142
143 // We can assume here that, if `self.ready.end` is greater than zero,
144 // it's also greater than `self.ready.start`. That's because we only
145 // increment `self.ready.start` inside `increment_next_ready`, and
146 // whenever it reaches equality with `self.ready.end`, we reset both
147 // to zero, maintaining the invariant that:
148 // self.ready.start < self.ready.end || self.ready.end == self.ready.start == 0
149 //
150 // This less-than-obviously-safe implementation is chosen for performance,
151 // minimizing the number & complexity of branches in `next` in the common
152 // case of buffering then unbuffering a single character with each call.
153 let (_, ch) = self.buffer[self.ready.start];
154 self.increment_next_ready();
155 Some(ch)
156 }
157
158 fn size_hint(&self) -> (usize, Option<usize>) {
159 let (lower, _) = self.iter.size_hint();
160 (lower, None)
161 }
162}
163
164impl<I: Iterator<Item = char> + FusedIterator> FusedIterator for Decompositions<I> {}
165
166impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> {
167 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
168 for c: char in self.clone() {
169 f.write_char(c)?;
170 }
171 Ok(())
172 }
173}
174