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;
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
39#[inline]
40pub 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]
50pub 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
59impl<I> Decompositions<I> {
60 #[inline]
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]
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]
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]
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
103impl<I: Iterator<Item = char>> Iterator for Decompositions<I> {
104 type Item = char;
105
106 #[inline]
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
148 fn size_hint(&self) -> (usize, Option<usize>) {
149 let (lower, _) = self.iter.size_hint();
150 (lower, None)
151 }
152}
153
154impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> {
155 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
156 for c: char in self.clone() {
157 f.write_char(c)?;
158 }
159 Ok(())
160 }
161}
162