unicode_normalization_alignments/
decompose.rs

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 smallvec::SmallVec;
11use std::fmt::{self, Write};
12use std::iter::Fuse;
13use std::ops::Range;
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: SmallVec<[(u8, char, isize); 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: SmallVec::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: SmallVec::new(),
55        ready: 0..0,
56    }
57}
58
59impl<I> Decompositions<I> {
60    #[inline]
61    fn push_back(&mut self, ch: char, first: bool) {
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, if first { 0 } else { 1 }));
69    }
70
71    #[inline]
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]
80    fn reset_buffer(&mut self) {
81        // Equivalent to `self.buffer.drain(0..self.ready.end)` (if SmallVec
82        // supported this API)
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]
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
102impl<I: Iterator<Item = char>> Iterator for Decompositions<I> {
103    type Item = (char, isize);
104
105    #[inline]
106    fn next(&mut self) -> Option<(char, isize)> {
107        while self.ready.end == 0 {
108            match (self.iter.next(), &self.kind) {
109                (Some(ch), &DecompositionType::Canonical) => {
110                    let mut first = true;
111                    super::char::decompose_canonical(ch, |d| {
112                        self.push_back(d, first);
113                        first = false;
114                    });
115                }
116                (Some(ch), &DecompositionType::Compatible) => {
117                    let mut first = true;
118                    super::char::decompose_compatible(ch, |d| {
119                        self.push_back(d, first);
120                        first = false;
121                    });
122                }
123                (None, _) => {
124                    if self.buffer.is_empty() {
125                        return None;
126                    } else {
127                        self.sort_pending();
128
129                        // This implementation means that we can call `next`
130                        // on an exhausted iterator; the last outer `next` call
131                        // will result in an inner `next` call. To make this
132                        // safe, we use `fuse`.
133                        break;
134                    }
135                }
136            }
137        }
138
139        // We can assume here that, if `self.ready.end` is greater than zero,
140        // it's also greater than `self.ready.start`. That's because we only
141        // increment `self.ready.start` inside `increment_next_ready`, and
142        // whenever it reaches equality with `self.ready.end`, we reset both
143        // to zero, maintaining the invariant that:
144        //      self.ready.start < self.ready.end || self.ready.end == self.ready.start == 0
145        //
146        // This less-than-obviously-safe implementation is chosen for performance,
147        // minimizing the number & complexity of branches in `next` in the common
148        // case of buffering then unbuffering a single character with each call.
149        let (_, ch, size) = self.buffer[self.ready.start];
150        self.increment_next_ready();
151        Some((ch, size))
152    }
153
154    fn size_hint(&self) -> (usize, Option<usize>) {
155        let (lower, _) = self.iter.size_hint();
156        (lower, None)
157    }
158}
159
160impl<I: Iterator<Item = char> + Clone> fmt::Display for Decompositions<I> {
161    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
162        for c in self.clone() {
163            f.write_char(c.0)?;
164        }
165        Ok(())
166    }
167}
unicode_normalization_alignments/decompose.rs

unicode_normalization_alignments/
decompose.rs
