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] 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] 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] 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 103 impl<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 154 impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> { 155 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