vendor/unicode-normalization/src/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.
  10 use smallvec::SmallVec;
  11 use std::fmt::{self, Write};
  12 use std::iter::Fuse;
  13 use std::ops::Range;
  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: SmallVec<[(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: SmallVec::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: SmallVec::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         }
  67
  68         self.buffer.push((class, ch));
  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
 102 impl<I: Iterator<Item=char>> Iterator for Decompositions<I> {
 103     type Item = char;
 104
 105     #[inline]
 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
 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> {
 153     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 }