src/libunicode/u_str.rs

   1 // Copyright 2012-2014 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 //
  11 // ignore-lexer-test FIXME #15679
  12
  13 //! Unicode-intensive string manipulations.
  14 //!
  15 //! This module provides functionality to `str` that requires the Unicode methods provided by the
  16 //! unicode parts of the CharExt trait.
  17
  18 use self::GraphemeState::*;
  19 use core::prelude::*;
  20
  21 use core::char;
  22 use core::cmp;
  23 use core::iter::{Filter, AdditiveIterator};
  24 use core::mem;
  25 use core::slice;
  26 use core::str::Split;
  27
  28 use tables::grapheme::GraphemeCat;
  29
  30 /// An iterator over the words of a string, separated by a sequence of whitespace
  31 #[stable(feature = "rust1", since = "1.0.0")]
  32 pub struct Words<'a> {
  33     inner: Filter<Split<'a, fn(char) -> bool>, fn(&&str) -> bool>,
  34 }
  35
  36 /// Methods for Unicode string slices
  37 #[allow(missing_docs)] // docs in libcollections
  38 pub trait UnicodeStr {
  39     fn graphemes<'a>(&'a self, is_extended: bool) -> Graphemes<'a>;
  40     fn grapheme_indices<'a>(&'a self, is_extended: bool) -> GraphemeIndices<'a>;
  41     fn words<'a>(&'a self) -> Words<'a>;
  42     fn is_whitespace(&self) -> bool;
  43     fn is_alphanumeric(&self) -> bool;
  44     fn width(&self, is_cjk: bool) -> usize;
  45     fn trim<'a>(&'a self) -> &'a str;
  46     fn trim_left<'a>(&'a self) -> &'a str;
  47     fn trim_right<'a>(&'a self) -> &'a str;
  48 }
  49
  50 impl UnicodeStr for str {
  51     #[inline]
  52     fn graphemes(&self, is_extended: bool) -> Graphemes {
  53         Graphemes { string: self, extended: is_extended, cat: None, catb: None }
  54     }
  55
  56     #[inline]
  57     fn grapheme_indices(&self, is_extended: bool) -> GraphemeIndices {
  58         GraphemeIndices { start_offset: self.as_ptr() as usize, iter: self.graphemes(is_extended) }
  59     }
  60
  61     #[inline]
  62     fn words(&self) -> Words {
  63         fn is_not_empty(s: &&str) -> bool { !s.is_empty() }
  64         let is_not_empty: fn(&&str) -> bool = is_not_empty; // coerce to fn pointer
  65
  66         fn is_whitespace(c: char) -> bool { c.is_whitespace() }
  67         let is_whitespace: fn(char) -> bool = is_whitespace; // coerce to fn pointer
  68
  69         Words { inner: self.split(is_whitespace).filter(is_not_empty) }
  70     }
  71
  72     #[inline]
  73     fn is_whitespace(&self) -> bool { self.chars().all(|c| c.is_whitespace()) }
  74
  75     #[inline]
  76     fn is_alphanumeric(&self) -> bool { self.chars().all(|c| c.is_alphanumeric()) }
  77
  78     #[inline]
  79     fn width(&self, is_cjk: bool) -> usize {
  80         self.chars().map(|c| c.width(is_cjk).unwrap_or(0)).sum()
  81     }
  82
  83     #[inline]
  84     fn trim(&self) -> &str {
  85         self.trim_matches(|c: char| c.is_whitespace())
  86     }
  87
  88     #[inline]
  89     fn trim_left(&self) -> &str {
  90         self.trim_left_matches(|c: char| c.is_whitespace())
  91     }
  92
  93     #[inline]
  94     fn trim_right(&self) -> &str {
  95         self.trim_right_matches(|c: char| c.is_whitespace())
  96     }
  97 }
  98
  99 /// External iterator for grapheme clusters and byte offsets.
 100 #[derive(Clone)]
 101 pub struct GraphemeIndices<'a> {
 102     start_offset: usize,
 103     iter: Graphemes<'a>,
 104 }
 105
 106 impl<'a> Iterator for GraphemeIndices<'a> {
 107     type Item = (usize, &'a str);
 108
 109     #[inline]
 110     fn next(&mut self) -> Option<(usize, &'a str)> {
 111         self.iter.next().map(|s| (s.as_ptr() as usize - self.start_offset, s))
 112     }
 113
 114     #[inline]
 115     fn size_hint(&self) -> (usize, Option<usize>) {
 116         self.iter.size_hint()
 117     }
 118 }
 119
 120 impl<'a> DoubleEndedIterator for GraphemeIndices<'a> {
 121     #[inline]
 122     fn next_back(&mut self) -> Option<(usize, &'a str)> {
 123         self.iter.next_back().map(|s| (s.as_ptr() as usize - self.start_offset, s))
 124     }
 125 }
 126
 127 /// External iterator for a string's
 128 /// [grapheme clusters](http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundaries).
 129 #[derive(Clone)]
 130 pub struct Graphemes<'a> {
 131     string: &'a str,
 132     extended: bool,
 133     cat: Option<GraphemeCat>,
 134     catb: Option<GraphemeCat>,
 135 }
 136
 137 // state machine for cluster boundary rules
 138 #[derive(PartialEq,Eq)]
 139 enum GraphemeState {
 140     Start,
 141     FindExtend,
 142     HangulL,
 143     HangulLV,
 144     HangulLVT,
 145     Regional,
 146 }
 147
 148 impl<'a> Iterator for Graphemes<'a> {
 149     type Item = &'a str;
 150
 151     #[inline]
 152     fn size_hint(&self) -> (usize, Option<usize>) {
 153         let slen = self.string.len();
 154         (cmp::min(slen, 1), Some(slen))
 155     }
 156
 157     #[inline]
 158     fn next(&mut self) -> Option<&'a str> {
 159         use tables::grapheme as gr;
 160         if self.string.len() == 0 {
 161             return None;
 162         }
 163
 164         let mut take_curr = true;
 165         let mut idx = 0;
 166         let mut state = Start;
 167         let mut cat = gr::GC_Any;
 168         for (curr, ch) in self.string.char_indices() {
 169             idx = curr;
 170
 171             // retrieve cached category, if any
 172             // We do this because most of the time we would end up
 173             // looking up each character twice.
 174             cat = match self.cat {
 175                 None => gr::grapheme_category(ch),
 176                 _ => self.cat.take().unwrap()
 177             };
 178
 179             if match cat {
 180                 gr::GC_Extend => true,
 181                 gr::GC_SpacingMark if self.extended => true,
 182                 _ => false
 183             } {
 184                     state = FindExtend;     // rule GB9/GB9a
 185                     continue;
 186             }
 187
 188             state = match state {
 189                 Start if '\r' == ch => {
 190                     let slen = self.string.len();
 191                     let nidx = idx + 1;
 192                     if nidx != slen && self.string.char_at(nidx) == '\n' {
 193                         idx = nidx;             // rule GB3
 194                     }
 195                     break;                      // rule GB4
 196                 }
 197                 Start => match cat {
 198                     gr::GC_Control => break,
 199                     gr::GC_L => HangulL,
 200                     gr::GC_LV | gr::GC_V => HangulLV,
 201                     gr::GC_LVT | gr::GC_T => HangulLVT,
 202                     gr::GC_RegionalIndicator => Regional,
 203                     _ => FindExtend
 204                 },
 205                 FindExtend => {         // found non-extending when looking for extending
 206                     take_curr = false;
 207                     break;
 208                 },
 209                 HangulL => match cat {      // rule GB6: L x (L|V|LV|LVT)
 210                     gr::GC_L => continue,
 211                     gr::GC_LV | gr::GC_V => HangulLV,
 212                     gr::GC_LVT => HangulLVT,
 213                     _ => {
 214                         take_curr = false;
 215                         break;
 216                     }
 217                 },
 218                 HangulLV => match cat {     // rule GB7: (LV|V) x (V|T)
 219                     gr::GC_V => continue,
 220                     gr::GC_T => HangulLVT,
 221                     _ => {
 222                         take_curr = false;
 223                         break;
 224                     }
 225                 },
 226                 HangulLVT => match cat {    // rule GB8: (LVT|T) x T
 227                     gr::GC_T => continue,
 228                     _ => {
 229                         take_curr = false;
 230                         break;
 231                     }
 232                 },
 233                 Regional => match cat {     // rule GB8a
 234                     gr::GC_RegionalIndicator => continue,
 235                     _ => {
 236                         take_curr = false;
 237                         break;
 238                     }
 239                 }
 240             }
 241         }
 242
 243         self.cat = if take_curr {
 244             idx = idx + self.string.char_at(idx).len_utf8();
 245             None
 246         } else {
 247             Some(cat)
 248         };
 249
 250         let retstr = &self.string[..idx];
 251         self.string = &self.string[idx..];
 252         Some(retstr)
 253     }
 254 }
 255
 256 impl<'a> DoubleEndedIterator for Graphemes<'a> {
 257     #[inline]
 258     fn next_back(&mut self) -> Option<&'a str> {
 259         use tables::grapheme as gr;
 260         if self.string.len() == 0 {
 261             return None;
 262         }
 263
 264         let mut take_curr = true;
 265         let mut idx = self.string.len();
 266         let mut previdx = idx;
 267         let mut state = Start;
 268         let mut cat = gr::GC_Any;
 269         for (curr, ch) in self.string.char_indices().rev() {
 270             previdx = idx;
 271             idx = curr;
 272
 273             // cached category, if any
 274             cat = match self.catb {
 275                 None => gr::grapheme_category(ch),
 276                 _ => self.catb.take().unwrap()
 277             };
 278
 279             // a matching state machine that runs *backwards* across an input string
 280             // note that this has some implications for the Hangul matching, since
 281             // we now need to know what the rightward letter is:
 282             //
 283             // Right to left, we have:
 284             //      L x L
 285             //      V x (L|V|LV)
 286             //      T x (V|T|LV|LVT)
 287             // HangulL means the letter to the right is L
 288             // HangulLV means the letter to the right is V
 289             // HangulLVT means the letter to the right is T
 290             state = match state {
 291                 Start if '\n' == ch => {
 292                     if idx > 0 && '\r' == self.string.char_at_reverse(idx) {
 293                         idx -= 1;       // rule GB3
 294                     }
 295                     break;              // rule GB4
 296                 },
 297                 Start | FindExtend => match cat {
 298                     gr::GC_Extend => FindExtend,
 299                     gr::GC_SpacingMark if self.extended => FindExtend,
 300                     gr::GC_L | gr::GC_LV | gr::GC_LVT => HangulL,
 301                     gr::GC_V => HangulLV,
 302                     gr::GC_T => HangulLVT,
 303                     gr::GC_RegionalIndicator => Regional,
 304                     gr::GC_Control => {
 305                         take_curr = Start == state;
 306                         break;
 307                     },
 308                     _ => break
 309                 },
 310                 HangulL => match cat {      // char to right is an L
 311                     gr::GC_L => continue,               // L x L is the only legal match
 312                     _ => {
 313                         take_curr = false;
 314                         break;
 315                     }
 316                 },
 317                 HangulLV => match cat {     // char to right is a V
 318                     gr::GC_V => continue,               // V x V, right char is still V
 319                     gr::GC_L | gr::GC_LV => HangulL,    // (L|V) x V, right char is now L
 320                     _ => {
 321                         take_curr = false;
 322                         break;
 323                     }
 324                 },
 325                 HangulLVT => match cat {    // char to right is a T
 326                     gr::GC_T => continue,               // T x T, right char is still T
 327                     gr::GC_V => HangulLV,               // V x T, right char is now V
 328                     gr::GC_LV | gr::GC_LVT => HangulL,  // (LV|LVT) x T, right char is now L
 329                     _ => {
 330                         take_curr = false;
 331                         break;
 332                     }
 333                 },
 334                 Regional => match cat {     // rule GB8a
 335                     gr::GC_RegionalIndicator => continue,
 336                     _ => {
 337                         take_curr = false;
 338                         break;
 339                     }
 340                 }
 341             }
 342         }
 343
 344         self.catb = if take_curr {
 345             None
 346         } else  {
 347             idx = previdx;
 348             Some(cat)
 349         };
 350
 351         let retstr = &self.string[idx..];
 352         self.string = &self.string[..idx];
 353         Some(retstr)
 354     }
 355 }
 356
 357 // https://tools.ietf.org/html/rfc3629
 358 static UTF8_CHAR_WIDTH: [u8; 256] = [
 359 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 360 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
 361 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 362 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
 363 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 364 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
 365 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
 366 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
 367 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 368 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
 369 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
 370 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
 371 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
 372 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
 373 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
 374 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
 375 ];
 376
 377 /// Given a first byte, determine how many bytes are in this UTF-8 character
 378 #[inline]
 379 pub fn utf8_char_width(b: u8) -> usize {
 380     return UTF8_CHAR_WIDTH[b as usize] as usize;
 381 }
 382
 383 /// Determines if a vector of `u16` contains valid UTF-16
 384 pub fn is_utf16(v: &[u16]) -> bool {
 385     let mut it = v.iter();
 386     macro_rules! next { ($ret:expr) => {
 387             match it.next() { Some(u) => *u, None => return $ret }
 388         }
 389     }
 390     loop {
 391         let u = next!(true);
 392
 393         match char::from_u32(u as u32) {
 394             Some(_) => {}
 395             None => {
 396                 let u2 = next!(false);
 397                 if u < 0xD7FF || u > 0xDBFF ||
 398                     u2 < 0xDC00 || u2 > 0xDFFF { return false; }
 399             }
 400         }
 401     }
 402 }
 403
 404 /// An iterator that decodes UTF-16 encoded codepoints from a vector
 405 /// of `u16`s.
 406 #[derive(Clone)]
 407 pub struct Utf16Items<'a> {
 408     iter: slice::Iter<'a, u16>
 409 }
 410 /// The possibilities for values decoded from a `u16` stream.
 411 #[derive(Copy, PartialEq, Eq, Clone, Debug)]
 412 pub enum Utf16Item {
 413     /// A valid codepoint.
 414     ScalarValue(char),
 415     /// An invalid surrogate without its pair.
 416     LoneSurrogate(u16)
 417 }
 418
 419 impl Utf16Item {
 420     /// Convert `self` to a `char`, taking `LoneSurrogate`s to the
 421     /// replacement character (U+FFFD).
 422     #[inline]
 423     pub fn to_char_lossy(&self) -> char {
 424         match *self {
 425             Utf16Item::ScalarValue(c) => c,
 426             Utf16Item::LoneSurrogate(_) => '\u{FFFD}'
 427         }
 428     }
 429 }
 430
 431 impl<'a> Iterator for Utf16Items<'a> {
 432     type Item = Utf16Item;
 433
 434     fn next(&mut self) -> Option<Utf16Item> {
 435         let u = match self.iter.next() {
 436             Some(u) => *u,
 437             None => return None
 438         };
 439
 440         if u < 0xD800 || 0xDFFF < u {
 441             // not a surrogate
 442             Some(Utf16Item::ScalarValue(unsafe {mem::transmute(u as u32)}))
 443         } else if u >= 0xDC00 {
 444             // a trailing surrogate
 445             Some(Utf16Item::LoneSurrogate(u))
 446         } else {
 447             // preserve state for rewinding.
 448             let old = self.iter.clone();
 449
 450             let u2 = match self.iter.next() {
 451                 Some(u2) => *u2,
 452                 // eof
 453                 None => return Some(Utf16Item::LoneSurrogate(u))
 454             };
 455             if u2 < 0xDC00 || u2 > 0xDFFF {
 456                 // not a trailing surrogate so we're not a valid
 457                 // surrogate pair, so rewind to redecode u2 next time.
 458                 self.iter = old.clone();
 459                 return Some(Utf16Item::LoneSurrogate(u))
 460             }
 461
 462             // all ok, so lets decode it.
 463             let c = (((u - 0xD800) as u32) << 10 | (u2 - 0xDC00) as u32) + 0x1_0000;
 464             Some(Utf16Item::ScalarValue(unsafe {mem::transmute(c)}))
 465         }
 466     }
 467
 468     #[inline]
 469     fn size_hint(&self) -> (usize, Option<usize>) {
 470         let (low, high) = self.iter.size_hint();
 471         // we could be entirely valid surrogates (2 elements per
 472         // char), or entirely non-surrogates (1 element per char)
 473         (low / 2, high)
 474     }
 475 }
 476
 477 /// Create an iterator over the UTF-16 encoded codepoints in `v`,
 478 /// returning invalid surrogates as `LoneSurrogate`s.
 479 ///
 480 /// # Examples
 481 ///
 482 /// ```
 483 /// # #![feature(unicode)]
 484 /// extern crate unicode;
 485 ///
 486 /// use unicode::str::Utf16Item::{ScalarValue, LoneSurrogate};
 487 ///
 488 /// fn main() {
 489 ///     // 𝄞mus<invalid>ic<invalid>
 490 ///     let v = [0xD834, 0xDD1E, 0x006d, 0x0075,
 491 ///              0x0073, 0xDD1E, 0x0069, 0x0063,
 492 ///              0xD834];
 493 ///
 494 ///     assert_eq!(unicode::str::utf16_items(&v).collect::<Vec<_>>(),
 495 ///                vec![ScalarValue('𝄞'),
 496 ///                     ScalarValue('m'), ScalarValue('u'), ScalarValue('s'),
 497 ///                     LoneSurrogate(0xDD1E),
 498 ///                     ScalarValue('i'), ScalarValue('c'),
 499 ///                     LoneSurrogate(0xD834)]);
 500 /// }
 501 /// ```
 502 pub fn utf16_items<'a>(v: &'a [u16]) -> Utf16Items<'a> {
 503     Utf16Items { iter : v.iter() }
 504 }
 505
 506 /// Iterator adaptor for encoding `char`s to UTF-16.
 507 #[derive(Clone)]
 508 pub struct Utf16Encoder<I> {
 509     chars: I,
 510     extra: u16
 511 }
 512
 513 impl<I> Utf16Encoder<I> {
 514     /// Create an UTF-16 encoder from any `char` iterator.
 515     pub fn new(chars: I) -> Utf16Encoder<I> where I: Iterator<Item=char> {
 516         Utf16Encoder { chars: chars, extra: 0 }
 517     }
 518 }
 519
 520 impl<I> Iterator for Utf16Encoder<I> where I: Iterator<Item=char> {
 521     type Item = u16;
 522
 523     #[inline]
 524     fn next(&mut self) -> Option<u16> {
 525         if self.extra != 0 {
 526             let tmp = self.extra;
 527             self.extra = 0;
 528             return Some(tmp);
 529         }
 530
 531         let mut buf = [0; 2];
 532         self.chars.next().map(|ch| {
 533             let n = CharExt::encode_utf16(ch, &mut buf).unwrap_or(0);
 534             if n == 2 { self.extra = buf[1]; }
 535             buf[0]
 536         })
 537     }
 538
 539     #[inline]
 540     fn size_hint(&self) -> (usize, Option<usize>) {
 541         let (low, high) = self.chars.size_hint();
 542         // every char gets either one u16 or two u16,
 543         // so this iterator is between 1 or 2 times as
 544         // long as the underlying iterator.
 545         (low, high.and_then(|n| n.checked_mul(2)))
 546     }
 547 }
 548
 549 impl<'a> Iterator for Words<'a> {
 550     type Item = &'a str;
 551
 552     fn next(&mut self) -> Option<&'a str> { self.inner.next() }
 553 }
 554 impl<'a> DoubleEndedIterator for Words<'a> {
 555     fn next_back(&mut self) -> Option<&'a str> { self.inner.next_back() }
 556 }