src/libcollections/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 string manipulation (`str` type)
  14 //!
  15 //! # Basic Usage
  16 //!
  17 //! Rust's string type is one of the core primitive types of the language. While
  18 //! represented by the name `str`, the name `str` is not actually a valid type in
  19 //! Rust. Each string must also be decorated with a pointer. `String` is used
  20 //! for an owned string, so there is only one commonly-used `str` type in Rust:
  21 //! `&str`.
  22 //!
  23 //! `&str` is the borrowed string type. This type of string can only be created
  24 //! from other strings, unless it is a static string (see below). As the word
  25 //! "borrowed" implies, this type of string is owned elsewhere, and this string
  26 //! cannot be moved out of.
  27 //!
  28 //! As an example, here's some code that uses a string.
  29 //!
  30 //! ```rust
  31 //! fn main() {
  32 //!     let borrowed_string = "This string is borrowed with the 'static lifetime";
  33 //! }
  34 //! ```
  35 //!
  36 //! From the example above, you can guess that Rust's string literals have the
  37 //! `'static` lifetime. This is akin to C's concept of a static string.
  38 //! More precisely, string literals are immutable views with a 'static lifetime
  39 //! (otherwise known as the lifetime of the entire program), and thus have the
  40 //! type `&'static str`.
  41 //!
  42 //! # Representation
  43 //!
  44 //! Rust's string type, `str`, is a sequence of Unicode scalar values encoded as a
  45 //! stream of UTF-8 bytes. All [strings](../../reference.html#literals) are
  46 //! guaranteed to be validly encoded UTF-8 sequences. Additionally, strings are
  47 //! not null-terminated and can thus contain null bytes.
  48 //!
  49 //! The actual representation of strings have direct mappings to slices: `&str`
  50 //! is the same as `&[u8]`.
  51
  52 #![doc(primitive = "str")]
  53
  54 pub use self::MaybeOwned::*;
  55 use self::RecompositionState::*;
  56 use self::DecompositionType::*;
  57 use core::borrow::{BorrowFrom, Cow, ToOwned};
  58 use core::default::Default;
  59 use core::fmt;
  60 use core::cmp;
  61 use core::iter::AdditiveIterator;
  62 use core::kinds::Sized;
  63 use core::prelude::{Char, Clone, Eq, Equiv};
  64 use core::prelude::{Iterator, IteratorExt, SlicePrelude, None, Option, Ord, Ordering};
  65 use core::prelude::{PartialEq, PartialOrd, Result, AsSlice, Some};
  66 use core::prelude::{range};
  67
  68 use hash;
  69 use ring_buf::RingBuf;
  70 use string::String;
  71 use unicode;
  72 use vec::Vec;
  73
  74 pub use core::str::{from_utf8, CharEq, Chars, CharOffsets};
  75 pub use core::str::{Bytes, CharSplits};
  76 pub use core::str::{CharSplitsN, AnyLines, MatchIndices, StrSplits};
  77 pub use core::str::{Utf16Encoder, Utf16CodeUnits};
  78 pub use core::str::{eq_slice, is_utf8, is_utf16, Utf16Items};
  79 pub use core::str::{Utf16Item, ScalarValue, LoneSurrogate, utf16_items};
  80 pub use core::str::{truncate_utf16_at_nul, utf8_char_width, CharRange};
  81 pub use core::str::{FromStr, from_str};
  82 pub use core::str::{Str, StrPrelude};
  83 pub use core::str::{from_utf8_unchecked, from_c_str};
  84 pub use unicode::str::{UnicodeStrPrelude, Words, Graphemes, GraphemeIndices};
  85
  86 // FIXME(conventions): ensure bit/char conventions are followed by str's API
  87
  88 /*
  89 Section: Creating a string
  90 */
  91
  92 /// Methods for vectors of strings.
  93 pub trait StrVector for Sized? {
  94     /// Concatenates a vector of strings.
  95     ///
  96     /// # Examples
  97     ///
  98     /// ```rust
  99     /// let first = "Restaurant at the End of the".to_string();
 100     /// let second = " Universe".to_string();
 101     /// let string_vec = vec![first, second];
 102     /// assert_eq!(string_vec.concat(), "Restaurant at the End of the Universe".to_string());
 103     /// ```
 104     fn concat(&self) -> String;
 105
 106     /// Concatenates a vector of strings, placing a given separator between each.
 107     ///
 108     /// # Examples
 109     ///
 110     /// ```rust
 111     /// let first = "Roast".to_string();
 112     /// let second = "Sirloin Steak".to_string();
 113     /// let string_vec = vec![first, second];
 114     /// assert_eq!(string_vec.connect(", "), "Roast, Sirloin Steak".to_string());
 115     /// ```
 116     fn connect(&self, sep: &str) -> String;
 117 }
 118
 119 impl<S: Str> StrVector for [S] {
 120     fn concat(&self) -> String {
 121         if self.is_empty() {
 122             return String::new();
 123         }
 124
 125         // `len` calculation may overflow but push_str will check boundaries
 126         let len = self.iter().map(|s| s.as_slice().len()).sum();
 127
 128         let mut result = String::with_capacity(len);
 129
 130         for s in self.iter() {
 131             result.push_str(s.as_slice())
 132         }
 133
 134         result
 135     }
 136
 137     fn connect(&self, sep: &str) -> String {
 138         if self.is_empty() {
 139             return String::new();
 140         }
 141
 142         // concat is faster
 143         if sep.is_empty() {
 144             return self.concat();
 145         }
 146
 147         // this is wrong without the guarantee that `self` is non-empty
 148         // `len` calculation may overflow but push_str but will check boundaries
 149         let len = sep.len() * (self.len() - 1)
 150             + self.iter().map(|s| s.as_slice().len()).sum();
 151         let mut result = String::with_capacity(len);
 152         let mut first = true;
 153
 154         for s in self.iter() {
 155             if first {
 156                 first = false;
 157             } else {
 158                 result.push_str(sep);
 159             }
 160             result.push_str(s.as_slice());
 161         }
 162         result
 163     }
 164 }
 165
 166 impl<S: Str, T: AsSlice<S>> StrVector for T {
 167     #[inline]
 168     fn concat(&self) -> String {
 169         self.as_slice().concat()
 170     }
 171
 172     #[inline]
 173     fn connect(&self, sep: &str) -> String {
 174         self.as_slice().connect(sep)
 175     }
 176 }
 177
 178 /*
 179 Section: Iterators
 180 */
 181
 182 // Helper functions used for Unicode normalization
 183 fn canonical_sort(comb: &mut [(char, u8)]) {
 184     let len = comb.len();
 185     for i in range(0, len) {
 186         let mut swapped = false;
 187         for j in range(1, len-i) {
 188             let class_a = comb[j-1].1;
 189             let class_b = comb[j].1;
 190             if class_a != 0 && class_b != 0 && class_a > class_b {
 191                 comb.swap(j-1, j);
 192                 swapped = true;
 193             }
 194         }
 195         if !swapped { break; }
 196     }
 197 }
 198
 199 #[deriving(Clone)]
 200 enum DecompositionType {
 201     Canonical,
 202     Compatible
 203 }
 204
 205 /// External iterator for a string's decomposition's characters.
 206 /// Use with the `std::iter` module.
 207 #[deriving(Clone)]
 208 pub struct Decompositions<'a> {
 209     kind: DecompositionType,
 210     iter: Chars<'a>,
 211     buffer: Vec<(char, u8)>,
 212     sorted: bool
 213 }
 214
 215 impl<'a> Iterator<char> for Decompositions<'a> {
 216     #[inline]
 217     fn next(&mut self) -> Option<char> {
 218         match self.buffer.head() {
 219             Some(&(c, 0)) => {
 220                 self.sorted = false;
 221                 self.buffer.remove(0);
 222                 return Some(c);
 223             }
 224             Some(&(c, _)) if self.sorted => {
 225                 self.buffer.remove(0);
 226                 return Some(c);
 227             }
 228             _ => self.sorted = false
 229         }
 230
 231         if !self.sorted {
 232             for ch in self.iter {
 233                 let buffer = &mut self.buffer;
 234                 let sorted = &mut self.sorted;
 235                 {
 236                     let callback = |d| {
 237                         let class =
 238                             unicode::char::canonical_combining_class(d);
 239                         if class == 0 && !*sorted {
 240                             canonical_sort(buffer.as_mut_slice());
 241                             *sorted = true;
 242                         }
 243                         buffer.push((d, class));
 244                     };
 245                     match self.kind {
 246                         Canonical => {
 247                             unicode::char::decompose_canonical(ch, callback)
 248                         }
 249                         Compatible => {
 250                             unicode::char::decompose_compatible(ch, callback)
 251                         }
 252                     }
 253                 }
 254                 if *sorted {
 255                     break
 256                 }
 257             }
 258         }
 259
 260         if !self.sorted {
 261             canonical_sort(self.buffer.as_mut_slice());
 262             self.sorted = true;
 263         }
 264
 265         match self.buffer.remove(0) {
 266             Some((c, 0)) => {
 267                 self.sorted = false;
 268                 Some(c)
 269             }
 270             Some((c, _)) => Some(c),
 271             None => None
 272         }
 273     }
 274
 275     fn size_hint(&self) -> (uint, Option<uint>) {
 276         let (lower, _) = self.iter.size_hint();
 277         (lower, None)
 278     }
 279 }
 280
 281 #[deriving(Clone)]
 282 enum RecompositionState {
 283     Composing,
 284     Purging,
 285     Finished
 286 }
 287
 288 /// External iterator for a string's recomposition's characters.
 289 /// Use with the `std::iter` module.
 290 #[deriving(Clone)]
 291 pub struct Recompositions<'a> {
 292     iter: Decompositions<'a>,
 293     state: RecompositionState,
 294     buffer: RingBuf<char>,
 295     composee: Option<char>,
 296     last_ccc: Option<u8>
 297 }
 298
 299 impl<'a> Iterator<char> for Recompositions<'a> {
 300     #[inline]
 301     fn next(&mut self) -> Option<char> {
 302         loop {
 303             match self.state {
 304                 Composing => {
 305                     for ch in self.iter {
 306                         let ch_class = unicode::char::canonical_combining_class(ch);
 307                         if self.composee.is_none() {
 308                             if ch_class != 0 {
 309                                 return Some(ch);
 310                             }
 311                             self.composee = Some(ch);
 312                             continue;
 313                         }
 314                         let k = self.composee.clone().unwrap();
 315
 316                         match self.last_ccc {
 317                             None => {
 318                                 match unicode::char::compose(k, ch) {
 319                                     Some(r) => {
 320                                         self.composee = Some(r);
 321                                         continue;
 322                                     }
 323                                     None => {
 324                                         if ch_class == 0 {
 325                                             self.composee = Some(ch);
 326                                             return Some(k);
 327                                         }
 328                                         self.buffer.push_back(ch);
 329                                         self.last_ccc = Some(ch_class);
 330                                     }
 331                                 }
 332                             }
 333                             Some(l_class) => {
 334                                 if l_class >= ch_class {
 335                                     // `ch` is blocked from `composee`
 336                                     if ch_class == 0 {
 337                                         self.composee = Some(ch);
 338                                         self.last_ccc = None;
 339                                         self.state = Purging;
 340                                         return Some(k);
 341                                     }
 342                                     self.buffer.push_back(ch);
 343                                     self.last_ccc = Some(ch_class);
 344                                     continue;
 345                                 }
 346                                 match unicode::char::compose(k, ch) {
 347                                     Some(r) => {
 348                                         self.composee = Some(r);
 349                                         continue;
 350                                     }
 351                                     None => {
 352                                         self.buffer.push_back(ch);
 353                                         self.last_ccc = Some(ch_class);
 354                                     }
 355                                 }
 356                             }
 357                         }
 358                     }
 359                     self.state = Finished;
 360                     if self.composee.is_some() {
 361                         return self.composee.take();
 362                     }
 363                 }
 364                 Purging => {
 365                     match self.buffer.pop_front() {
 366                         None => self.state = Composing,
 367                         s => return s
 368                     }
 369                 }
 370                 Finished => {
 371                     match self.buffer.pop_front() {
 372                         None => return self.composee.take(),
 373                         s => return s
 374                     }
 375                 }
 376             }
 377         }
 378     }
 379 }
 380
 381 /// Replaces all occurrences of one string with another.
 382 ///
 383 /// # Arguments
 384 ///
 385 /// * s - The string containing substrings to replace
 386 /// * from - The string to replace
 387 /// * to - The replacement string
 388 ///
 389 /// # Return value
 390 ///
 391 /// The original string with all occurrences of `from` replaced with `to`.
 392 ///
 393 /// # Examples
 394 ///
 395 /// ```rust
 396 /// use std::str;
 397 /// let string = "orange";
 398 /// let new_string = str::replace(string, "or", "str");
 399 /// assert_eq!(new_string.as_slice(), "strange");
 400 /// ```
 401 pub fn replace(s: &str, from: &str, to: &str) -> String {
 402     let mut result = String::new();
 403     let mut last_end = 0;
 404     for (start, end) in s.match_indices(from) {
 405         result.push_str(unsafe { s.slice_unchecked(last_end, start) });
 406         result.push_str(to);
 407         last_end = end;
 408     }
 409     result.push_str(unsafe { s.slice_unchecked(last_end, s.len()) });
 410     result
 411 }
 412
 413 /*
 414 Section: Misc
 415 */
 416
 417 // Return the initial codepoint accumulator for the first byte.
 418 // The first byte is special, only want bottom 5 bits for width 2, 4 bits
 419 // for width 3, and 3 bits for width 4
 420 macro_rules! utf8_first_byte(
 421     ($byte:expr, $width:expr) => (($byte & (0x7F >> $width)) as u32)
 422 )
 423
 424 // return the value of $ch updated with continuation byte $byte
 425 macro_rules! utf8_acc_cont_byte(
 426     ($ch:expr, $byte:expr) => (($ch << 6) | ($byte & 63u8) as u32)
 427 )
 428
 429 /*
 430 Section: MaybeOwned
 431 */
 432
 433 /// A string type that can hold either a `String` or a `&str`.
 434 /// This can be useful as an optimization when an allocation is sometimes
 435 /// needed but not always.
 436 #[deprecated = "use std::str::CowString"]
 437 pub enum MaybeOwned<'a> {
 438     /// A borrowed string.
 439     Slice(&'a str),
 440     /// An owned string.
 441     Owned(String)
 442 }
 443
 444 /// A specialization of `CowString` to be sendable.
 445 pub type SendStr = CowString<'static>;
 446
 447 #[deprecated = "use std::str::CowString"]
 448 impl<'a> MaybeOwned<'a> {
 449     /// Returns `true` if this `MaybeOwned` wraps an owned string.
 450     ///
 451     /// # Examples
 452     ///
 453     /// ``` ignore
 454     /// let string = String::from_str("orange");
 455     /// let maybe_owned_string = string.into_maybe_owned();
 456     /// assert_eq!(true, maybe_owned_string.is_owned());
 457     /// ```
 458     #[inline]
 459     pub fn is_owned(&self) -> bool {
 460         match *self {
 461             Slice(_) => false,
 462             Owned(_) => true
 463         }
 464     }
 465
 466     /// Returns `true` if this `MaybeOwned` wraps a borrowed string.
 467     ///
 468     /// # Examples
 469     ///
 470     /// ``` ignore
 471     /// let string = "orange";
 472     /// let maybe_owned_string = string.as_slice().into_maybe_owned();
 473     /// assert_eq!(true, maybe_owned_string.is_slice());
 474     /// ```
 475     #[inline]
 476     pub fn is_slice(&self) -> bool {
 477         match *self {
 478             Slice(_) => true,
 479             Owned(_) => false
 480         }
 481     }
 482
 483     /// Return the number of bytes in this string.
 484     #[inline]
 485     pub fn len(&self) -> uint { self.as_slice().len() }
 486
 487     /// Returns true if the string contains no bytes
 488     #[allow(deprecated)]
 489     #[inline]
 490     pub fn is_empty(&self) -> bool { self.len() == 0 }
 491 }
 492
 493 #[deprecated = "use std::borrow::IntoCow"]
 494 /// Trait for moving into a `MaybeOwned`.
 495 pub trait IntoMaybeOwned<'a> {
 496     /// Moves `self` into a `MaybeOwned`.
 497     fn into_maybe_owned(self) -> MaybeOwned<'a>;
 498 }
 499
 500 #[deprecated = "use std::borrow::IntoCow"]
 501 #[allow(deprecated)]
 502 impl<'a> IntoMaybeOwned<'a> for String {
 503     /// # Examples
 504     ///
 505     /// ``` ignore
 506     /// let owned_string = String::from_str("orange");
 507     /// let maybe_owned_string = owned_string.into_maybe_owned();
 508     /// assert_eq!(true, maybe_owned_string.is_owned());
 509     /// ```
 510     #[allow(deprecated)]
 511     #[inline]
 512     fn into_maybe_owned(self) -> MaybeOwned<'a> {
 513         Owned(self)
 514     }
 515 }
 516
 517 #[deprecated = "use std::borrow::IntoCow"]
 518 #[allow(deprecated)]
 519 impl<'a> IntoMaybeOwned<'a> for &'a str {
 520     /// # Examples
 521     ///
 522     /// ``` ignore
 523     /// let string = "orange";
 524     /// let maybe_owned_str = string.as_slice().into_maybe_owned();
 525     /// assert_eq!(false, maybe_owned_str.is_owned());
 526     /// ```
 527     #[allow(deprecated)]
 528     #[inline]
 529     fn into_maybe_owned(self) -> MaybeOwned<'a> { Slice(self) }
 530 }
 531
 532 #[allow(deprecated)]
 533 #[deprecated = "use std::borrow::IntoCow"]
 534 impl<'a> IntoMaybeOwned<'a> for MaybeOwned<'a> {
 535     /// # Examples
 536     ///
 537     /// ``` ignore
 538     /// let str = "orange";
 539     /// let maybe_owned_str = str.as_slice().into_maybe_owned();
 540     /// let maybe_maybe_owned_str = maybe_owned_str.into_maybe_owned();
 541     /// assert_eq!(false, maybe_maybe_owned_str.is_owned());
 542     /// ```
 543     #[inline]
 544     fn into_maybe_owned(self) -> MaybeOwned<'a> { self }
 545 }
 546
 547 #[deprecated = "use std::str::CowString"]
 548 impl<'a> PartialEq for MaybeOwned<'a> {
 549     #[inline]
 550     fn eq(&self, other: &MaybeOwned) -> bool {
 551         self.as_slice() == other.as_slice()
 552     }
 553 }
 554
 555 #[deprecated = "use std::str::CowString"]
 556 impl<'a> Eq for MaybeOwned<'a> {}
 557
 558 #[deprecated = "use std::str::CowString"]
 559 impl<'a> PartialOrd for MaybeOwned<'a> {
 560     #[inline]
 561     fn partial_cmp(&self, other: &MaybeOwned) -> Option<Ordering> {
 562         Some(self.cmp(other))
 563     }
 564 }
 565
 566 #[deprecated = "use std::str::CowString"]
 567 impl<'a> Ord for MaybeOwned<'a> {
 568     #[inline]
 569     fn cmp(&self, other: &MaybeOwned) -> Ordering {
 570         self.as_slice().cmp(other.as_slice())
 571     }
 572 }
 573
 574 #[allow(deprecated)]
 575 #[deprecated = "use std::str::CowString"]
 576 impl<'a, S: Str> Equiv<S> for MaybeOwned<'a> {
 577     #[inline]
 578     fn equiv(&self, other: &S) -> bool {
 579         self.as_slice() == other.as_slice()
 580     }
 581 }
 582
 583 #[deprecated = "use std::str::CowString"]
 584 impl<'a> Str for MaybeOwned<'a> {
 585     #[allow(deprecated)]
 586     #[inline]
 587     fn as_slice<'b>(&'b self) -> &'b str {
 588         match *self {
 589             Slice(s) => s,
 590             Owned(ref s) => s.as_slice()
 591         }
 592     }
 593 }
 594
 595 #[deprecated = "use std::str::CowString"]
 596 impl<'a> StrAllocating for MaybeOwned<'a> {
 597     #[allow(deprecated)]
 598     #[inline]
 599     fn into_string(self) -> String {
 600         match self {
 601             Slice(s) => String::from_str(s),
 602             Owned(s) => s
 603         }
 604     }
 605 }
 606
 607 #[deprecated = "use std::str::CowString"]
 608 impl<'a> Clone for MaybeOwned<'a> {
 609     #[allow(deprecated)]
 610     #[inline]
 611     fn clone(&self) -> MaybeOwned<'a> {
 612         match *self {
 613             Slice(s) => Slice(s),
 614             Owned(ref s) => Owned(String::from_str(s.as_slice()))
 615         }
 616     }
 617 }
 618
 619 #[deprecated = "use std::str::CowString"]
 620 impl<'a> Default for MaybeOwned<'a> {
 621     #[allow(deprecated)]
 622     #[inline]
 623     fn default() -> MaybeOwned<'a> { Slice("") }
 624 }
 625
 626 #[deprecated = "use std::str::CowString"]
 627 impl<'a, H: hash::Writer> hash::Hash<H> for MaybeOwned<'a> {
 628     #[inline]
 629     fn hash(&self, hasher: &mut H) {
 630         self.as_slice().hash(hasher)
 631     }
 632 }
 633
 634 #[deprecated = "use std::str::CowString"]
 635 impl<'a> fmt::Show for MaybeOwned<'a> {
 636     #[inline]
 637     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 638         match *self {
 639             Slice(ref s) => s.fmt(f),
 640             Owned(ref s) => s.fmt(f)
 641         }
 642     }
 643 }
 644
 645 #[unstable = "trait is unstable"]
 646 impl BorrowFrom<String> for str {
 647     fn borrow_from(owned: &String) -> &str { owned[] }
 648 }
 649
 650 #[unstable = "trait is unstable"]
 651 impl ToOwned<String> for str {
 652     fn to_owned(&self) -> String { self.into_string() }
 653 }
 654
 655 /// Unsafe string operations.
 656 pub mod raw {
 657     pub use core::str::raw::{from_utf8, c_str_to_static_slice, slice_bytes};
 658     pub use core::str::raw::{slice_unchecked};
 659 }
 660
 661 /*
 662 Section: CowString
 663 */
 664
 665 /// A clone-on-write string
 666 pub type CowString<'a> = Cow<'a, String, str>;
 667
 668 impl<'a> Str for CowString<'a> {
 669     #[inline]
 670     fn as_slice<'b>(&'b self) -> &'b str {
 671         (**self).as_slice()
 672     }
 673 }
 674
 675 /*
 676 Section: Trait implementations
 677 */
 678
 679 /// Any string that can be represented as a slice.
 680 pub trait StrAllocating: Str {
 681     /// Converts `self` into a `String`, not making a copy if possible.
 682     fn into_string(self) -> String;
 683
 684     /// Escapes each char in `s` with `char::escape_default`.
 685     fn escape_default(&self) -> String {
 686         let me = self.as_slice();
 687         let mut out = String::with_capacity(me.len());
 688         for c in me.chars() {
 689             for c in c.escape_default() {
 690                 out.push(c);
 691             }
 692         }
 693         out
 694     }
 695
 696     /// Escapes each char in `s` with `char::escape_unicode`.
 697     fn escape_unicode(&self) -> String {
 698         let me = self.as_slice();
 699         let mut out = String::with_capacity(me.len());
 700         for c in me.chars() {
 701             for c in c.escape_unicode() {
 702                 out.push(c);
 703             }
 704         }
 705         out
 706     }
 707
 708     /// Replaces all occurrences of one string with another.
 709     ///
 710     /// # Arguments
 711     ///
 712     /// * `from` - The string to replace
 713     /// * `to` - The replacement string
 714     ///
 715     /// # Return value
 716     ///
 717     /// The original string with all occurrences of `from` replaced with `to`.
 718     ///
 719     /// # Examples
 720     ///
 721     /// ```rust
 722     /// let s = "Do you know the muffin man,
 723     /// The muffin man, the muffin man, ...".to_string();
 724     ///
 725     /// assert_eq!(s.replace("muffin man", "little lamb"),
 726     ///            "Do you know the little lamb,
 727     /// The little lamb, the little lamb, ...".to_string());
 728     ///
 729     /// // not found, so no change.
 730     /// assert_eq!(s.replace("cookie monster", "little lamb"), s);
 731     /// ```
 732     fn replace(&self, from: &str, to: &str) -> String {
 733         replace(self.as_slice(), from, to)
 734     }
 735
 736     /// Given a string, makes a new string with repeated copies of it.
 737     fn repeat(&self, nn: uint) -> String {
 738         let me = self.as_slice();
 739         let mut ret = String::with_capacity(nn * me.len());
 740         for _ in range(0, nn) {
 741             ret.push_str(me);
 742         }
 743         ret
 744     }
 745
 746     /// Returns the Levenshtein Distance between two strings.
 747     fn lev_distance(&self, t: &str) -> uint {
 748         let me = self.as_slice();
 749         if me.is_empty() { return t.char_len(); }
 750         if t.is_empty() { return me.char_len(); }
 751
 752         let mut dcol = Vec::from_fn(t.len() + 1, |x| x);
 753         let mut t_last = 0;
 754
 755         for (i, sc) in me.chars().enumerate() {
 756
 757             let mut current = i;
 758             dcol[0] = current + 1;
 759
 760             for (j, tc) in t.chars().enumerate() {
 761
 762                 let next = dcol[j + 1];
 763
 764                 if sc == tc {
 765                     dcol[j + 1] = current;
 766                 } else {
 767                     dcol[j + 1] = cmp::min(current, next);
 768                     dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
 769                 }
 770
 771                 current = next;
 772                 t_last = j;
 773             }
 774         }
 775
 776         dcol[t_last + 1]
 777     }
 778
 779     /// Returns an iterator over the string in Unicode Normalization Form D
 780     /// (canonical decomposition).
 781     #[inline]
 782     fn nfd_chars<'a>(&'a self) -> Decompositions<'a> {
 783         Decompositions {
 784             iter: self.as_slice().chars(),
 785             buffer: Vec::new(),
 786             sorted: false,
 787             kind: Canonical
 788         }
 789     }
 790
 791     /// Returns an iterator over the string in Unicode Normalization Form KD
 792     /// (compatibility decomposition).
 793     #[inline]
 794     fn nfkd_chars<'a>(&'a self) -> Decompositions<'a> {
 795         Decompositions {
 796             iter: self.as_slice().chars(),
 797             buffer: Vec::new(),
 798             sorted: false,
 799             kind: Compatible
 800         }
 801     }
 802
 803     /// An Iterator over the string in Unicode Normalization Form C
 804     /// (canonical decomposition followed by canonical composition).
 805     #[inline]
 806     fn nfc_chars<'a>(&'a self) -> Recompositions<'a> {
 807         Recompositions {
 808             iter: self.nfd_chars(),
 809             state: Composing,
 810             buffer: RingBuf::new(),
 811             composee: None,
 812             last_ccc: None
 813         }
 814     }
 815
 816     /// An Iterator over the string in Unicode Normalization Form KC
 817     /// (compatibility decomposition followed by canonical composition).
 818     #[inline]
 819     fn nfkc_chars<'a>(&'a self) -> Recompositions<'a> {
 820         Recompositions {
 821             iter: self.nfkd_chars(),
 822             state: Composing,
 823             buffer: RingBuf::new(),
 824             composee: None,
 825             last_ccc: None
 826         }
 827     }
 828 }
 829
 830 impl<'a> StrAllocating for &'a str {
 831     #[inline]
 832     fn into_string(self) -> String {
 833         String::from_str(self)
 834     }
 835 }
 836
 837 #[cfg(test)]
 838 mod tests {
 839     use std::iter::AdditiveIterator;
 840     use std::iter::range;
 841     use std::default::Default;
 842     use std::char::Char;
 843     use std::clone::Clone;
 844     use std::cmp::{Ord, PartialOrd, Equiv};
 845     use std::cmp::Ordering::{Equal, Greater, Less};
 846     use std::option::Option;
 847     use std::option::Option::{Some, None};
 848     use std::ptr::RawPtr;
 849     use std::iter::{Iterator, IteratorExt, DoubleEndedIteratorExt};
 850
 851     use super::*;
 852     use std::slice::{AsSlice, SlicePrelude};
 853     use string::String;
 854     use vec::Vec;
 855     use slice::CloneSliceAllocPrelude;
 856
 857     use unicode::char::UnicodeChar;
 858
 859     #[test]
 860     fn test_eq_slice() {
 861         assert!((eq_slice("foobar".slice(0, 3), "foo")));
 862         assert!((eq_slice("barfoo".slice(3, 6), "foo")));
 863         assert!((!eq_slice("foo1", "foo2")));
 864     }
 865
 866     #[test]
 867     fn test_le() {
 868         assert!("" <= "");
 869         assert!("" <= "foo");
 870         assert!("foo" <= "foo");
 871         assert!("foo" != "bar");
 872     }
 873
 874     #[test]
 875     fn test_len() {
 876         assert_eq!("".len(), 0u);
 877         assert_eq!("hello world".len(), 11u);
 878         assert_eq!("\x63".len(), 1u);
 879         assert_eq!("\u{a2}".len(), 2u);
 880         assert_eq!("\u{3c0}".len(), 2u);
 881         assert_eq!("\u{2620}".len(), 3u);
 882         assert_eq!("\u{1d11e}".len(), 4u);
 883
 884         assert_eq!("".char_len(), 0u);
 885         assert_eq!("hello world".char_len(), 11u);
 886         assert_eq!("\x63".char_len(), 1u);
 887         assert_eq!("\u{a2}".char_len(), 1u);
 888         assert_eq!("\u{3c0}".char_len(), 1u);
 889         assert_eq!("\u{2620}".char_len(), 1u);
 890         assert_eq!("\u{1d11e}".char_len(), 1u);
 891         assert_eq!("ประเทศไทย中华Việt Nam".char_len(), 19u);
 892
 893         assert_eq!("ｈｅｌｌｏ".width(false), 10u);
 894         assert_eq!("ｈｅｌｌｏ".width(true), 10u);
 895         assert_eq!("\0\0\0\0\0".width(false), 0u);
 896         assert_eq!("\0\0\0\0\0".width(true), 0u);
 897         assert_eq!("".width(false), 0u);
 898         assert_eq!("".width(true), 0u);
 899         assert_eq!("\u{2081}\u{2082}\u{2083}\u{2084}".width(false), 4u);
 900         assert_eq!("\u{2081}\u{2082}\u{2083}\u{2084}".width(true), 8u);
 901     }
 902
 903     #[test]
 904     fn test_find() {
 905         assert_eq!("hello".find('l'), Some(2u));
 906         assert_eq!("hello".find(|&: c:char| c == 'o'), Some(4u));
 907         assert!("hello".find('x').is_none());
 908         assert!("hello".find(|&: c:char| c == 'x').is_none());
 909         assert_eq!("ประเทศไทย中华Việt Nam".find('华'), Some(30u));
 910         assert_eq!("ประเทศไทย中华Việt Nam".find(|&: c: char| c == '华'), Some(30u));
 911     }
 912
 913     #[test]
 914     fn test_rfind() {
 915         assert_eq!("hello".rfind('l'), Some(3u));
 916         assert_eq!("hello".rfind(|&: c:char| c == 'o'), Some(4u));
 917         assert!("hello".rfind('x').is_none());
 918         assert!("hello".rfind(|&: c:char| c == 'x').is_none());
 919         assert_eq!("ประเทศไทย中华Việt Nam".rfind('华'), Some(30u));
 920         assert_eq!("ประเทศไทย中华Việt Nam".rfind(|&: c: char| c == '华'), Some(30u));
 921     }
 922
 923     #[test]
 924     fn test_collect() {
 925         let empty = String::from_str("");
 926         let s: String = empty.chars().collect();
 927         assert_eq!(empty, s);
 928         let data = String::from_str("ประเทศไทย中");
 929         let s: String = data.chars().collect();
 930         assert_eq!(data, s);
 931     }
 932
 933     #[test]
 934     fn test_into_bytes() {
 935         let data = String::from_str("asdf");
 936         let buf = data.into_bytes();
 937         assert_eq!(b"asdf", buf);
 938     }
 939
 940     #[test]
 941     fn test_find_str() {
 942         // byte positions
 943         assert_eq!("".find_str(""), Some(0u));
 944         assert!("banana".find_str("apple pie").is_none());
 945
 946         let data = "abcabc";
 947         assert_eq!(data.slice(0u, 6u).find_str("ab"), Some(0u));
 948         assert_eq!(data.slice(2u, 6u).find_str("ab"), Some(3u - 2u));
 949         assert!(data.slice(2u, 4u).find_str("ab").is_none());
 950
 951         let string = "ประเทศไทย中华Việt Nam";
 952         let mut data = String::from_str(string);
 953         data.push_str(string);
 954         assert!(data.find_str("ไท华").is_none());
 955         assert_eq!(data.slice(0u, 43u).find_str(""), Some(0u));
 956         assert_eq!(data.slice(6u, 43u).find_str(""), Some(6u - 6u));
 957
 958         assert_eq!(data.slice(0u, 43u).find_str("ประ"), Some( 0u));
 959         assert_eq!(data.slice(0u, 43u).find_str("ทศไ"), Some(12u));
 960         assert_eq!(data.slice(0u, 43u).find_str("ย中"), Some(24u));
 961         assert_eq!(data.slice(0u, 43u).find_str("iệt"), Some(34u));
 962         assert_eq!(data.slice(0u, 43u).find_str("Nam"), Some(40u));
 963
 964         assert_eq!(data.slice(43u, 86u).find_str("ประ"), Some(43u - 43u));
 965         assert_eq!(data.slice(43u, 86u).find_str("ทศไ"), Some(55u - 43u));
 966         assert_eq!(data.slice(43u, 86u).find_str("ย中"), Some(67u - 43u));
 967         assert_eq!(data.slice(43u, 86u).find_str("iệt"), Some(77u - 43u));
 968         assert_eq!(data.slice(43u, 86u).find_str("Nam"), Some(83u - 43u));
 969     }
 970
 971     #[test]
 972     fn test_slice_chars() {
 973         fn t(a: &str, b: &str, start: uint) {
 974             assert_eq!(a.slice_chars(start, start + b.char_len()), b);
 975         }
 976         t("", "", 0);
 977         t("hello", "llo", 2);
 978         t("hello", "el", 1);
 979         t("αβλ", "β", 1);
 980         t("αβλ", "", 3);
 981         assert_eq!("ะเทศไท", "ประเทศไทย中华Việt Nam".slice_chars(2, 8));
 982     }
 983
 984     struct S {
 985         x: [String, .. 2]
 986     }
 987
 988     impl AsSlice<String> for S {
 989         fn as_slice<'a> (&'a self) -> &'a [String] {
 990             &self.x
 991         }
 992     }
 993
 994     fn s(x: &str) -> String { x.into_string() }
 995
 996     macro_rules! test_concat {
 997         ($expected: expr, $string: expr) => {
 998             {
 999                 let s = $string.concat();
1000                 assert_eq!($expected, s);
1001             }
1002         }
1003     }
1004
1005     #[test]
1006     fn test_concat_for_different_types() {
1007         test_concat!("ab", ["a", "b"]);
1008         test_concat!("ab", [s("a"), s("b")]);
1009         test_concat!("ab", vec!["a", "b"]);
1010         test_concat!("ab", vec!["a", "b"].as_slice());
1011         test_concat!("ab", vec![s("a"), s("b")]);
1012
1013         let mut v0 = ["a", "b"];
1014         let mut v1 = [s("a"), s("b")];
1015         unsafe {
1016             use std::c_vec::CVec;
1017
1018             test_concat!("ab", CVec::new(v0.as_mut_ptr(), v0.len()));
1019             test_concat!("ab", CVec::new(v1.as_mut_ptr(), v1.len()));
1020         }
1021
1022         test_concat!("ab", S { x: [s("a"), s("b")] });
1023     }
1024
1025     #[test]
1026     fn test_concat_for_different_lengths() {
1027         let empty: &[&str] = &[];
1028         test_concat!("", empty);
1029         test_concat!("a", ["a"]);
1030         test_concat!("ab", ["a", "b"]);
1031         test_concat!("abc", ["", "a", "bc"]);
1032     }
1033
1034     macro_rules! test_connect {
1035         ($expected: expr, $string: expr, $delim: expr) => {
1036             {
1037                 let s = $string.connect($delim);
1038                 assert_eq!($expected, s);
1039             }
1040         }
1041     }
1042
1043     #[test]
1044     fn test_connect_for_different_types() {
1045         test_connect!("a-b", ["a", "b"], "-");
1046         let hyphen = "-".into_string();
1047         test_connect!("a-b", [s("a"), s("b")], hyphen.as_slice());
1048         test_connect!("a-b", vec!["a", "b"], hyphen.as_slice());
1049         test_connect!("a-b", vec!["a", "b"].as_slice(), "-");
1050         test_connect!("a-b", vec![s("a"), s("b")], "-");
1051
1052         let mut v0 = ["a", "b"];
1053         let mut v1 = [s("a"), s("b")];
1054         unsafe {
1055             use std::c_vec::CVec;
1056
1057             test_connect!("a-b", CVec::new(v0.as_mut_ptr(), v0.len()), "-");
1058             test_connect!("a-b", CVec::new(v1.as_mut_ptr(), v1.len()), hyphen.as_slice());
1059         }
1060
1061         test_connect!("a-b", S { x: [s("a"), s("b")] }, "-");
1062     }
1063
1064     #[test]
1065     fn test_connect_for_different_lengths() {
1066         let empty: &[&str] = &[];
1067         test_connect!("", empty, "-");
1068         test_connect!("a", ["a"], "-");
1069         test_connect!("a-b", ["a", "b"], "-");
1070         test_connect!("-a-bc", ["", "a", "bc"], "-");
1071     }
1072
1073     #[test]
1074     fn test_repeat() {
1075         assert_eq!("x".repeat(4), String::from_str("xxxx"));
1076         assert_eq!("hi".repeat(4), String::from_str("hihihihi"));
1077         assert_eq!("ไท华".repeat(3), String::from_str("ไท华ไท华ไท华"));
1078         assert_eq!("".repeat(4), String::from_str(""));
1079         assert_eq!("hi".repeat(0), String::from_str(""));
1080     }
1081
1082     #[test]
1083     fn test_unsafe_slice() {
1084         assert_eq!("ab", unsafe {raw::slice_bytes("abc", 0, 2)});
1085         assert_eq!("bc", unsafe {raw::slice_bytes("abc", 1, 3)});
1086         assert_eq!("", unsafe {raw::slice_bytes("abc", 1, 1)});
1087         fn a_million_letter_a() -> String {
1088             let mut i = 0u;
1089             let mut rs = String::new();
1090             while i < 100000 {
1091                 rs.push_str("aaaaaaaaaa");
1092                 i += 1;
1093             }
1094             rs
1095         }
1096         fn half_a_million_letter_a() -> String {
1097             let mut i = 0u;
1098             let mut rs = String::new();
1099             while i < 100000 {
1100                 rs.push_str("aaaaa");
1101                 i += 1;
1102             }
1103             rs
1104         }
1105         let letters = a_million_letter_a();
1106         assert!(half_a_million_letter_a() ==
1107             unsafe {String::from_str(raw::slice_bytes(letters.as_slice(),
1108                                      0u,
1109                                      500000))});
1110     }
1111
1112     #[test]
1113     fn test_starts_with() {
1114         assert!(("".starts_with("")));
1115         assert!(("abc".starts_with("")));
1116         assert!(("abc".starts_with("a")));
1117         assert!((!"a".starts_with("abc")));
1118         assert!((!"".starts_with("abc")));
1119         assert!((!"ödd".starts_with("-")));
1120         assert!(("ödd".starts_with("öd")));
1121     }
1122
1123     #[test]
1124     fn test_ends_with() {
1125         assert!(("".ends_with("")));
1126         assert!(("abc".ends_with("")));
1127         assert!(("abc".ends_with("c")));
1128         assert!((!"a".ends_with("abc")));
1129         assert!((!"".ends_with("abc")));
1130         assert!((!"ddö".ends_with("-")));
1131         assert!(("ddö".ends_with("dö")));
1132     }
1133
1134     #[test]
1135     fn test_is_empty() {
1136         assert!("".is_empty());
1137         assert!(!"a".is_empty());
1138     }
1139
1140     #[test]
1141     fn test_replace() {
1142         let a = "a";
1143         assert_eq!("".replace(a, "b"), String::from_str(""));
1144         assert_eq!("a".replace(a, "b"), String::from_str("b"));
1145         assert_eq!("ab".replace(a, "b"), String::from_str("bb"));
1146         let test = "test";
1147         assert!(" test test ".replace(test, "toast") ==
1148             String::from_str(" toast toast "));
1149         assert_eq!(" test test ".replace(test, ""), String::from_str("   "));
1150     }
1151
1152     #[test]
1153     fn test_replace_2a() {
1154         let data = "ประเทศไทย中华";
1155         let repl = "دولة الكويت";
1156
1157         let a = "ประเ";
1158         let a2 = "دولة الكويتทศไทย中华";
1159         assert_eq!(data.replace(a, repl), a2);
1160     }
1161
1162     #[test]
1163     fn test_replace_2b() {
1164         let data = "ประเทศไทย中华";
1165         let repl = "دولة الكويت";
1166
1167         let b = "ะเ";
1168         let b2 = "ปรدولة الكويتทศไทย中华";
1169         assert_eq!(data.replace(b, repl), b2);
1170     }
1171
1172     #[test]
1173     fn test_replace_2c() {
1174         let data = "ประเทศไทย中华";
1175         let repl = "دولة الكويت";
1176
1177         let c = "中华";
1178         let c2 = "ประเทศไทยدولة الكويت";
1179         assert_eq!(data.replace(c, repl), c2);
1180     }
1181
1182     #[test]
1183     fn test_replace_2d() {
1184         let data = "ประเทศไทย中华";
1185         let repl = "دولة الكويت";
1186
1187         let d = "ไท华";
1188         assert_eq!(data.replace(d, repl), data);
1189     }
1190
1191     #[test]
1192     fn test_slice() {
1193         assert_eq!("ab", "abc".slice(0, 2));
1194         assert_eq!("bc", "abc".slice(1, 3));
1195         assert_eq!("", "abc".slice(1, 1));
1196         assert_eq!("\u{65e5}", "\u{65e5}\u{672c}".slice(0, 3));
1197
1198         let data = "ประเทศไทย中华";
1199         assert_eq!("ป", data.slice(0, 3));
1200         assert_eq!("ร", data.slice(3, 6));
1201         assert_eq!("", data.slice(3, 3));
1202         assert_eq!("华", data.slice(30, 33));
1203
1204         fn a_million_letter_x() -> String {
1205             let mut i = 0u;
1206             let mut rs = String::new();
1207             while i < 100000 {
1208                 rs.push_str("华华华华华华华华华华");
1209                 i += 1;
1210             }
1211             rs
1212         }
1213         fn half_a_million_letter_x() -> String {
1214             let mut i = 0u;
1215             let mut rs = String::new();
1216             while i < 100000 {
1217                 rs.push_str("华华华华华");
1218                 i += 1;
1219             }
1220             rs
1221         }
1222         let letters = a_million_letter_x();
1223         assert!(half_a_million_letter_x() ==
1224             String::from_str(letters.slice(0u, 3u * 500000u)));
1225     }
1226
1227     #[test]
1228     fn test_slice_2() {
1229         let ss = "中华Việt Nam";
1230
1231         assert_eq!("华", ss.slice(3u, 6u));
1232         assert_eq!("Việt Nam", ss.slice(6u, 16u));
1233
1234         assert_eq!("ab", "abc".slice(0u, 2u));
1235         assert_eq!("bc", "abc".slice(1u, 3u));
1236         assert_eq!("", "abc".slice(1u, 1u));
1237
1238         assert_eq!("中", ss.slice(0u, 3u));
1239         assert_eq!("华V", ss.slice(3u, 7u));
1240         assert_eq!("", ss.slice(3u, 3u));
1241         /*0: 中
1242           3: 华
1243           6: V
1244           7: i
1245           8: ệ
1246          11: t
1247          12:
1248          13: N
1249          14: a
1250          15: m */
1251     }
1252
1253     #[test]
1254     #[should_fail]
1255     fn test_slice_fail() {
1256         "中华Việt Nam".slice(0u, 2u);
1257     }
1258
1259     #[test]
1260     fn test_slice_from() {
1261         assert_eq!("abcd".slice_from(0), "abcd");
1262         assert_eq!("abcd".slice_from(2), "cd");
1263         assert_eq!("abcd".slice_from(4), "");
1264     }
1265     #[test]
1266     fn test_slice_to() {
1267         assert_eq!("abcd".slice_to(0), "");
1268         assert_eq!("abcd".slice_to(2), "ab");
1269         assert_eq!("abcd".slice_to(4), "abcd");
1270     }
1271
1272     #[test]
1273     fn test_trim_left_chars() {
1274         let v: &[char] = &[];
1275         assert_eq!(" *** foo *** ".trim_left_chars(v), " *** foo *** ");
1276         let chars: &[char] = &['*', ' '];
1277         assert_eq!(" *** foo *** ".trim_left_chars(chars), "foo *** ");
1278         assert_eq!(" ***  *** ".trim_left_chars(chars), "");
1279         assert_eq!("foo *** ".trim_left_chars(chars), "foo *** ");
1280
1281         assert_eq!("11foo1bar11".trim_left_chars('1'), "foo1bar11");
1282         let chars: &[char] = &['1', '2'];
1283         assert_eq!("12foo1bar12".trim_left_chars(chars), "foo1bar12");
1284         assert_eq!("123foo1bar123".trim_left_chars(|&: c: char| c.is_numeric()), "foo1bar123");
1285     }
1286
1287     #[test]
1288     fn test_trim_right_chars() {
1289         let v: &[char] = &[];
1290         assert_eq!(" *** foo *** ".trim_right_chars(v), " *** foo *** ");
1291         let chars: &[char] = &['*', ' '];
1292         assert_eq!(" *** foo *** ".trim_right_chars(chars), " *** foo");
1293         assert_eq!(" ***  *** ".trim_right_chars(chars), "");
1294         assert_eq!(" *** foo".trim_right_chars(chars), " *** foo");
1295
1296         assert_eq!("11foo1bar11".trim_right_chars('1'), "11foo1bar");
1297         let chars: &[char] = &['1', '2'];
1298         assert_eq!("12foo1bar12".trim_right_chars(chars), "12foo1bar");
1299         assert_eq!("123foo1bar123".trim_right_chars(|&: c: char| c.is_numeric()), "123foo1bar");
1300     }
1301
1302     #[test]
1303     fn test_trim_chars() {
1304         let v: &[char] = &[];
1305         assert_eq!(" *** foo *** ".trim_chars(v), " *** foo *** ");
1306         let chars: &[char] = &['*', ' '];
1307         assert_eq!(" *** foo *** ".trim_chars(chars), "foo");
1308         assert_eq!(" ***  *** ".trim_chars(chars), "");
1309         assert_eq!("foo".trim_chars(chars), "foo");
1310
1311         assert_eq!("11foo1bar11".trim_chars('1'), "foo1bar");
1312         let chars: &[char] = &['1', '2'];
1313         assert_eq!("12foo1bar12".trim_chars(chars), "foo1bar");
1314         assert_eq!("123foo1bar123".trim_chars(|&: c: char| c.is_numeric()), "foo1bar");
1315     }
1316
1317     #[test]
1318     fn test_trim_left() {
1319         assert_eq!("".trim_left(), "");
1320         assert_eq!("a".trim_left(), "a");
1321         assert_eq!("    ".trim_left(), "");
1322         assert_eq!("     blah".trim_left(), "blah");
1323         assert_eq!("   \u{3000}  wut".trim_left(), "wut");
1324         assert_eq!("hey ".trim_left(), "hey ");
1325     }
1326
1327     #[test]
1328     fn test_trim_right() {
1329         assert_eq!("".trim_right(), "");
1330         assert_eq!("a".trim_right(), "a");
1331         assert_eq!("    ".trim_right(), "");
1332         assert_eq!("blah     ".trim_right(), "blah");
1333         assert_eq!("wut   \u{3000}  ".trim_right(), "wut");
1334         assert_eq!(" hey".trim_right(), " hey");
1335     }
1336
1337     #[test]
1338     fn test_trim() {
1339         assert_eq!("".trim(), "");
1340         assert_eq!("a".trim(), "a");
1341         assert_eq!("    ".trim(), "");
1342         assert_eq!("    blah     ".trim(), "blah");
1343         assert_eq!("\nwut   \u{3000}  ".trim(), "wut");
1344         assert_eq!(" hey dude ".trim(), "hey dude");
1345     }
1346
1347     #[test]
1348     fn test_is_whitespace() {
1349         assert!("".is_whitespace());
1350         assert!(" ".is_whitespace());
1351         assert!("\u{2009}".is_whitespace()); // Thin space
1352         assert!("  \n\t   ".is_whitespace());
1353         assert!(!"   _   ".is_whitespace());
1354     }
1355
1356     #[test]
1357     fn test_slice_shift_char() {
1358         let data = "ประเทศไทย中";
1359         assert_eq!(data.slice_shift_char(), Some(('ป', "ระเทศไทย中")));
1360     }
1361
1362     #[test]
1363     fn test_slice_shift_char_2() {
1364         let empty = "";
1365         assert_eq!(empty.slice_shift_char(), None);
1366     }
1367
1368     #[test]
1369     fn test_is_utf8() {
1370         // deny overlong encodings
1371         assert!(!is_utf8(&[0xc0, 0x80]));
1372         assert!(!is_utf8(&[0xc0, 0xae]));
1373         assert!(!is_utf8(&[0xe0, 0x80, 0x80]));
1374         assert!(!is_utf8(&[0xe0, 0x80, 0xaf]));
1375         assert!(!is_utf8(&[0xe0, 0x81, 0x81]));
1376         assert!(!is_utf8(&[0xf0, 0x82, 0x82, 0xac]));
1377         assert!(!is_utf8(&[0xf4, 0x90, 0x80, 0x80]));
1378
1379         // deny surrogates
1380         assert!(!is_utf8(&[0xED, 0xA0, 0x80]));
1381         assert!(!is_utf8(&[0xED, 0xBF, 0xBF]));
1382
1383         assert!(is_utf8(&[0xC2, 0x80]));
1384         assert!(is_utf8(&[0xDF, 0xBF]));
1385         assert!(is_utf8(&[0xE0, 0xA0, 0x80]));
1386         assert!(is_utf8(&[0xED, 0x9F, 0xBF]));
1387         assert!(is_utf8(&[0xEE, 0x80, 0x80]));
1388         assert!(is_utf8(&[0xEF, 0xBF, 0xBF]));
1389         assert!(is_utf8(&[0xF0, 0x90, 0x80, 0x80]));
1390         assert!(is_utf8(&[0xF4, 0x8F, 0xBF, 0xBF]));
1391     }
1392
1393     #[test]
1394     fn test_is_utf16() {
1395         macro_rules! pos ( ($($e:expr),*) => { { $(assert!(is_utf16($e));)* } });
1396
1397         // non-surrogates
1398         pos!(&[0x0000],
1399              &[0x0001, 0x0002],
1400              &[0xD7FF],
1401              &[0xE000]);
1402
1403         // surrogate pairs (randomly generated with Python 3's
1404         // .encode('utf-16be'))
1405         pos!(&[0xdb54, 0xdf16, 0xd880, 0xdee0, 0xdb6a, 0xdd45],
1406              &[0xd91f, 0xdeb1, 0xdb31, 0xdd84, 0xd8e2, 0xde14],
1407              &[0xdb9f, 0xdc26, 0xdb6f, 0xde58, 0xd850, 0xdfae]);
1408
1409         // mixtures (also random)
1410         pos!(&[0xd921, 0xdcc2, 0x002d, 0x004d, 0xdb32, 0xdf65],
1411              &[0xdb45, 0xdd2d, 0x006a, 0xdacd, 0xddfe, 0x0006],
1412              &[0x0067, 0xd8ff, 0xddb7, 0x000f, 0xd900, 0xdc80]);
1413
1414         // negative tests
1415         macro_rules! neg ( ($($e:expr),*) => { { $(assert!(!is_utf16($e));)* } });
1416
1417         neg!(
1418             // surrogate + regular unit
1419             &[0xdb45, 0x0000],
1420             // surrogate + lead surrogate
1421             &[0xd900, 0xd900],
1422             // unterminated surrogate
1423             &[0xd8ff],
1424             // trail surrogate without a lead
1425             &[0xddb7]);
1426
1427         // random byte sequences that Python 3's .decode('utf-16be')
1428         // failed on
1429         neg!(&[0x5b3d, 0x0141, 0xde9e, 0x8fdc, 0xc6e7],
1430              &[0xdf5a, 0x82a5, 0x62b9, 0xb447, 0x92f3],
1431              &[0xda4e, 0x42bc, 0x4462, 0xee98, 0xc2ca],
1432              &[0xbe00, 0xb04a, 0x6ecb, 0xdd89, 0xe278],
1433              &[0x0465, 0xab56, 0xdbb6, 0xa893, 0x665e],
1434              &[0x6b7f, 0x0a19, 0x40f4, 0xa657, 0xdcc5],
1435              &[0x9b50, 0xda5e, 0x24ec, 0x03ad, 0x6dee],
1436              &[0x8d17, 0xcaa7, 0xf4ae, 0xdf6e, 0xbed7],
1437              &[0xdaee, 0x2584, 0x7d30, 0xa626, 0x121a],
1438              &[0xd956, 0x4b43, 0x7570, 0xccd6, 0x4f4a],
1439              &[0x9dcf, 0x1b49, 0x4ba5, 0xfce9, 0xdffe],
1440              &[0x6572, 0xce53, 0xb05a, 0xf6af, 0xdacf],
1441              &[0x1b90, 0x728c, 0x9906, 0xdb68, 0xf46e],
1442              &[0x1606, 0xbeca, 0xbe76, 0x860f, 0xdfa5],
1443              &[0x8b4f, 0xde7a, 0xd220, 0x9fac, 0x2b6f],
1444              &[0xb8fe, 0xebbe, 0xda32, 0x1a5f, 0x8b8b],
1445              &[0x934b, 0x8956, 0xc434, 0x1881, 0xddf7],
1446              &[0x5a95, 0x13fc, 0xf116, 0xd89b, 0x93f9],
1447              &[0xd640, 0x71f1, 0xdd7d, 0x77eb, 0x1cd8],
1448              &[0x348b, 0xaef0, 0xdb2c, 0xebf1, 0x1282],
1449              &[0x50d7, 0xd824, 0x5010, 0xb369, 0x22ea]);
1450     }
1451
1452     #[test]
1453     fn test_as_bytes() {
1454         // no null
1455         let v = [
1456             224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
1457             184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
1458             109
1459         ];
1460         let b: &[u8] = &[];
1461         assert_eq!("".as_bytes(), b);
1462         assert_eq!("abc".as_bytes(), b"abc");
1463         assert_eq!("ศไทย中华Việt Nam".as_bytes(), v);
1464     }
1465
1466     #[test]
1467     #[should_fail]
1468     fn test_as_bytes_fail() {
1469         // Don't double free. (I'm not sure if this exercises the
1470         // original problem code path anymore.)
1471         let s = String::from_str("");
1472         let _bytes = s.as_bytes();
1473         panic!();
1474     }
1475
1476     #[test]
1477     fn test_as_ptr() {
1478         let buf = "hello".as_ptr();
1479         unsafe {
1480             assert_eq!(*buf.offset(0), b'h');
1481             assert_eq!(*buf.offset(1), b'e');
1482             assert_eq!(*buf.offset(2), b'l');
1483             assert_eq!(*buf.offset(3), b'l');
1484             assert_eq!(*buf.offset(4), b'o');
1485         }
1486     }
1487
1488     #[test]
1489     fn test_subslice_offset() {
1490         let a = "kernelsprite";
1491         let b = a.slice(7, a.len());
1492         let c = a.slice(0, a.len() - 6);
1493         assert_eq!(a.subslice_offset(b), 7);
1494         assert_eq!(a.subslice_offset(c), 0);
1495
1496         let string = "a\nb\nc";
1497         let lines: Vec<&str> = string.lines().collect();
1498         assert_eq!(string.subslice_offset(lines[0]), 0);
1499         assert_eq!(string.subslice_offset(lines[1]), 2);
1500         assert_eq!(string.subslice_offset(lines[2]), 4);
1501     }
1502
1503     #[test]
1504     #[should_fail]
1505     fn test_subslice_offset_2() {
1506         let a = "alchemiter";
1507         let b = "cruxtruder";
1508         a.subslice_offset(b);
1509     }
1510
1511     #[test]
1512     fn vec_str_conversions() {
1513         let s1: String = String::from_str("All mimsy were the borogoves");
1514
1515         let v: Vec<u8> = s1.as_bytes().to_vec();
1516         let s2: String = String::from_str(from_utf8(v.as_slice()).unwrap());
1517         let mut i: uint = 0u;
1518         let n1: uint = s1.len();
1519         let n2: uint = v.len();
1520         assert_eq!(n1, n2);
1521         while i < n1 {
1522             let a: u8 = s1.as_bytes()[i];
1523             let b: u8 = s2.as_bytes()[i];
1524             debug!("{}", a);
1525             debug!("{}", b);
1526             assert_eq!(a, b);
1527             i += 1u;
1528         }
1529     }
1530
1531     #[test]
1532     fn test_contains() {
1533         assert!("abcde".contains("bcd"));
1534         assert!("abcde".contains("abcd"));
1535         assert!("abcde".contains("bcde"));
1536         assert!("abcde".contains(""));
1537         assert!("".contains(""));
1538         assert!(!"abcde".contains("def"));
1539         assert!(!"".contains("a"));
1540
1541         let data = "ประเทศไทย中华Việt Nam";
1542         assert!(data.contains("ประเ"));
1543         assert!(data.contains("ะเ"));
1544         assert!(data.contains("中华"));
1545         assert!(!data.contains("ไท华"));
1546     }
1547
1548     #[test]
1549     fn test_contains_char() {
1550         assert!("abc".contains_char('b'));
1551         assert!("a".contains_char('a'));
1552         assert!(!"abc".contains_char('d'));
1553         assert!(!"".contains_char('a'));
1554     }
1555
1556     #[test]
1557     fn test_truncate_utf16_at_nul() {
1558         let v = [];
1559         let b: &[u16] = &[];
1560         assert_eq!(truncate_utf16_at_nul(&v), b);
1561
1562         let v = [0, 2, 3];
1563         assert_eq!(truncate_utf16_at_nul(&v), b);
1564
1565         let v = [1, 0, 3];
1566         let b: &[u16] = &[1];
1567         assert_eq!(truncate_utf16_at_nul(&v), b);
1568
1569         let v = [1, 2, 0];
1570         let b: &[u16] = &[1, 2];
1571         assert_eq!(truncate_utf16_at_nul(&v), b);
1572
1573         let v = [1, 2, 3];
1574         let b: &[u16] = &[1, 2, 3];
1575         assert_eq!(truncate_utf16_at_nul(&v), b);
1576     }
1577
1578     #[test]
1579     fn test_char_at() {
1580         let s = "ศไทย中华Việt Nam";
1581         let v = vec!['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
1582         let mut pos = 0;
1583         for ch in v.iter() {
1584             assert!(s.char_at(pos) == *ch);
1585             pos += String::from_char(1, *ch).len();
1586         }
1587     }
1588
1589     #[test]
1590     fn test_char_at_reverse() {
1591         let s = "ศไทย中华Việt Nam";
1592         let v = vec!['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
1593         let mut pos = s.len();
1594         for ch in v.iter().rev() {
1595             assert!(s.char_at_reverse(pos) == *ch);
1596             pos -= String::from_char(1, *ch).len();
1597         }
1598     }
1599
1600     #[test]
1601     fn test_escape_unicode() {
1602         assert_eq!("abc".escape_unicode(), String::from_str("\\x61\\x62\\x63"));
1603         assert_eq!("a c".escape_unicode(), String::from_str("\\x61\\x20\\x63"));
1604         assert_eq!("\r\n\t".escape_unicode(), String::from_str("\\x0d\\x0a\\x09"));
1605         assert_eq!("'\"\\".escape_unicode(), String::from_str("\\x27\\x22\\x5c"));
1606         assert_eq!("\x00\x01\u{fe}\u{ff}".escape_unicode(),
1607                    String::from_str("\\x00\\x01\\u00fe\\u00ff"));
1608         assert_eq!("\u{100}\u{ffff}".escape_unicode(), String::from_str("\\u0100\\uffff"));
1609         assert_eq!("\u{10000}\u{10ffff}".escape_unicode(),
1610                    String::from_str("\\U00010000\\U0010ffff"));
1611         assert_eq!("ab\u{fb00}".escape_unicode(), String::from_str("\\x61\\x62\\ufb00"));
1612         assert_eq!("\u{1d4ea}\r".escape_unicode(), String::from_str("\\U0001d4ea\\x0d"));
1613     }
1614
1615     #[test]
1616     fn test_escape_default() {
1617         assert_eq!("abc".escape_default(), String::from_str("abc"));
1618         assert_eq!("a c".escape_default(), String::from_str("a c"));
1619         assert_eq!("\r\n\t".escape_default(), String::from_str("\\r\\n\\t"));
1620         assert_eq!("'\"\\".escape_default(), String::from_str("\\'\\\"\\\\"));
1621         assert_eq!("\u{100}\u{ffff}".escape_default(), String::from_str("\\u0100\\uffff"));
1622         assert_eq!("\u{10000}\u{10ffff}".escape_default(),
1623                    String::from_str("\\U00010000\\U0010ffff"));
1624         assert_eq!("ab\u{fb00}".escape_default(), String::from_str("ab\\ufb00"));
1625         assert_eq!("\u{1d4ea}\r".escape_default(), String::from_str("\\U0001d4ea\\r"));
1626     }
1627
1628     #[test]
1629     fn test_total_ord() {
1630         "1234".cmp("123") == Greater;
1631         "123".cmp("1234") == Less;
1632         "1234".cmp("1234") == Equal;
1633         "12345555".cmp("123456") == Less;
1634         "22".cmp("1234") == Greater;
1635     }
1636
1637     #[test]
1638     fn test_char_range_at() {
1639         let data = "b¢€𤭢𤭢€¢b";
1640         assert_eq!('b', data.char_range_at(0).ch);
1641         assert_eq!('¢', data.char_range_at(1).ch);
1642         assert_eq!('€', data.char_range_at(3).ch);
1643         assert_eq!('𤭢', data.char_range_at(6).ch);
1644         assert_eq!('𤭢', data.char_range_at(10).ch);
1645         assert_eq!('€', data.char_range_at(14).ch);
1646         assert_eq!('¢', data.char_range_at(17).ch);
1647         assert_eq!('b', data.char_range_at(19).ch);
1648     }
1649
1650     #[test]
1651     fn test_char_range_at_reverse_underflow() {
1652         assert_eq!("abc".char_range_at_reverse(0).next, 0);
1653     }
1654
1655     #[test]
1656     fn test_iterator() {
1657         let s = "ศไทย中华Việt Nam";
1658         let v = ['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
1659
1660         let mut pos = 0;
1661         let mut it = s.chars();
1662
1663         for c in it {
1664             assert_eq!(c, v[pos]);
1665             pos += 1;
1666         }
1667         assert_eq!(pos, v.len());
1668     }
1669
1670     #[test]
1671     fn test_rev_iterator() {
1672         let s = "ศไทย中华Việt Nam";
1673         let v = ['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ'];
1674
1675         let mut pos = 0;
1676         let mut it = s.chars().rev();
1677
1678         for c in it {
1679             assert_eq!(c, v[pos]);
1680             pos += 1;
1681         }
1682         assert_eq!(pos, v.len());
1683     }
1684
1685     #[test]
1686     fn test_chars_decoding() {
1687         let mut bytes = [0u8, ..4];
1688         for c in range(0u32, 0x110000).filter_map(|c| ::core::char::from_u32(c)) {
1689             let len = c.encode_utf8(&mut bytes).unwrap_or(0);
1690             let s = ::core::str::from_utf8(bytes[..len]).unwrap();
1691             if Some(c) != s.chars().next() {
1692                 panic!("character {:x}={} does not decode correctly", c as u32, c);
1693             }
1694         }
1695     }
1696
1697     #[test]
1698     fn test_chars_rev_decoding() {
1699         let mut bytes = [0u8, ..4];
1700         for c in range(0u32, 0x110000).filter_map(|c| ::core::char::from_u32(c)) {
1701             let len = c.encode_utf8(&mut bytes).unwrap_or(0);
1702             let s = ::core::str::from_utf8(bytes[..len]).unwrap();
1703             if Some(c) != s.chars().rev().next() {
1704                 panic!("character {:x}={} does not decode correctly", c as u32, c);
1705             }
1706         }
1707     }
1708
1709     #[test]
1710     fn test_iterator_clone() {
1711         let s = "ศไทย中华Việt Nam";
1712         let mut it = s.chars();
1713         it.next();
1714         assert!(it.zip(it.clone()).all(|(x,y)| x == y));
1715     }
1716
1717     #[test]
1718     fn test_bytesator() {
1719         let s = "ศไทย中华Việt Nam";
1720         let v = [
1721             224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
1722             184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
1723             109
1724         ];
1725         let mut pos = 0;
1726
1727         for b in s.bytes() {
1728             assert_eq!(b, v[pos]);
1729             pos += 1;
1730         }
1731     }
1732
1733     #[test]
1734     fn test_bytes_revator() {
1735         let s = "ศไทย中华Việt Nam";
1736         let v = [
1737             224, 184, 168, 224, 185, 132, 224, 184, 151, 224, 184, 162, 228,
1738             184, 173, 229, 141, 142, 86, 105, 225, 187, 135, 116, 32, 78, 97,
1739             109
1740         ];
1741         let mut pos = v.len();
1742
1743         for b in s.bytes().rev() {
1744             pos -= 1;
1745             assert_eq!(b, v[pos]);
1746         }
1747     }
1748
1749     #[test]
1750     fn test_char_indicesator() {
1751         let s = "ศไทย中华Việt Nam";
1752         let p = [0, 3, 6, 9, 12, 15, 18, 19, 20, 23, 24, 25, 26, 27];
1753         let v = ['ศ','ไ','ท','ย','中','华','V','i','ệ','t',' ','N','a','m'];
1754
1755         let mut pos = 0;
1756         let mut it = s.char_indices();
1757
1758         for c in it {
1759             assert_eq!(c, (p[pos], v[pos]));
1760             pos += 1;
1761         }
1762         assert_eq!(pos, v.len());
1763         assert_eq!(pos, p.len());
1764     }
1765
1766     #[test]
1767     fn test_char_indices_revator() {
1768         let s = "ศไทย中华Việt Nam";
1769         let p = [27, 26, 25, 24, 23, 20, 19, 18, 15, 12, 9, 6, 3, 0];
1770         let v = ['m', 'a', 'N', ' ', 't', 'ệ','i','V','华','中','ย','ท','ไ','ศ'];
1771
1772         let mut pos = 0;
1773         let mut it = s.char_indices().rev();
1774
1775         for c in it {
1776             assert_eq!(c, (p[pos], v[pos]));
1777             pos += 1;
1778         }
1779         assert_eq!(pos, v.len());
1780         assert_eq!(pos, p.len());
1781     }
1782
1783     #[test]
1784     fn test_splitn_char_iterator() {
1785         let data = "\nMäry häd ä little lämb\nLittle lämb\n";
1786
1787         let split: Vec<&str> = data.splitn(3, ' ').collect();
1788         assert_eq!(split, vec!["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
1789
1790         let split: Vec<&str> = data.splitn(3, |&: c: char| c == ' ').collect();
1791         assert_eq!(split, vec!["\nMäry", "häd", "ä", "little lämb\nLittle lämb\n"]);
1792
1793         // Unicode
1794         let split: Vec<&str> = data.splitn(3, 'ä').collect();
1795         assert_eq!(split, vec!["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
1796
1797         let split: Vec<&str> = data.splitn(3, |&: c: char| c == 'ä').collect();
1798         assert_eq!(split, vec!["\nM", "ry h", "d ", " little lämb\nLittle lämb\n"]);
1799     }
1800
1801     #[test]
1802     fn test_split_char_iterator_no_trailing() {
1803         let data = "\nMäry häd ä little lämb\nLittle lämb\n";
1804
1805         let split: Vec<&str> = data.split('\n').collect();
1806         assert_eq!(split, vec!["", "Märy häd ä little lämb", "Little lämb", ""]);
1807
1808         let split: Vec<&str> = data.split_terminator('\n').collect();
1809         assert_eq!(split, vec!["", "Märy häd ä little lämb", "Little lämb"]);
1810     }
1811
1812     #[test]
1813     fn test_words() {
1814         let data = "\n \tMäry   häd\tä  little lämb\nLittle lämb\n";
1815         let words: Vec<&str> = data.words().collect();
1816         assert_eq!(words, vec!["Märy", "häd", "ä", "little", "lämb", "Little", "lämb"])
1817     }
1818
1819     #[test]
1820     fn test_lev_distance() {
1821         use std::char::{ from_u32, MAX };
1822         // Test bytelength agnosticity
1823         for c in range(0u32, MAX as u32)
1824                  .filter_map(|i| from_u32(i))
1825                  .map(|i| String::from_char(1, i)) {
1826             assert_eq!(c[].lev_distance(c[]), 0);
1827         }
1828
1829         let a = "\nMäry häd ä little lämb\n\nLittle lämb\n";
1830         let b = "\nMary häd ä little lämb\n\nLittle lämb\n";
1831         let c = "Mary häd ä little lämb\n\nLittle lämb\n";
1832         assert_eq!(a.lev_distance(b), 1);
1833         assert_eq!(b.lev_distance(a), 1);
1834         assert_eq!(a.lev_distance(c), 2);
1835         assert_eq!(c.lev_distance(a), 2);
1836         assert_eq!(b.lev_distance(c), 1);
1837         assert_eq!(c.lev_distance(b), 1);
1838     }
1839
1840     #[test]
1841     fn test_nfd_chars() {
1842         macro_rules! t {
1843             ($input: expr, $expected: expr) => {
1844                 assert_eq!($input.nfd_chars().collect::<String>(), $expected);
1845             }
1846         }
1847         t!("abc", "abc");
1848         t!("\u{1e0b}\u{1c4}", "d\u{307}\u{1c4}");
1849         t!("\u{2026}", "\u{2026}");
1850         t!("\u{2126}", "\u{3a9}");
1851         t!("\u{1e0b}\u{323}", "d\u{323}\u{307}");
1852         t!("\u{1e0d}\u{307}", "d\u{323}\u{307}");
1853         t!("a\u{301}", "a\u{301}");
1854         t!("\u{301}a", "\u{301}a");
1855         t!("\u{d4db}", "\u{1111}\u{1171}\u{11b6}");
1856         t!("\u{ac1c}", "\u{1100}\u{1162}");
1857     }
1858
1859     #[test]
1860     fn test_nfkd_chars() {
1861         macro_rules! t {
1862             ($input: expr, $expected: expr) => {
1863                 assert_eq!($input.nfkd_chars().collect::<String>(), $expected);
1864             }
1865         }
1866         t!("abc", "abc");
1867         t!("\u{1e0b}\u{1c4}", "d\u{307}DZ\u{30c}");
1868         t!("\u{2026}", "...");
1869         t!("\u{2126}", "\u{3a9}");
1870         t!("\u{1e0b}\u{323}", "d\u{323}\u{307}");
1871         t!("\u{1e0d}\u{307}", "d\u{323}\u{307}");
1872         t!("a\u{301}", "a\u{301}");
1873         t!("\u{301}a", "\u{301}a");
1874         t!("\u{d4db}", "\u{1111}\u{1171}\u{11b6}");
1875         t!("\u{ac1c}", "\u{1100}\u{1162}");
1876     }
1877
1878     #[test]
1879     fn test_nfc_chars() {
1880         macro_rules! t {
1881             ($input: expr, $expected: expr) => {
1882                 assert_eq!($input.nfc_chars().collect::<String>(), $expected);
1883             }
1884         }
1885         t!("abc", "abc");
1886         t!("\u{1e0b}\u{1c4}", "\u{1e0b}\u{1c4}");
1887         t!("\u{2026}", "\u{2026}");
1888         t!("\u{2126}", "\u{3a9}");
1889         t!("\u{1e0b}\u{323}", "\u{1e0d}\u{307}");
1890         t!("\u{1e0d}\u{307}", "\u{1e0d}\u{307}");
1891         t!("a\u{301}", "\u{e1}");
1892         t!("\u{301}a", "\u{301}a");
1893         t!("\u{d4db}", "\u{d4db}");
1894         t!("\u{ac1c}", "\u{ac1c}");
1895         t!("a\u{300}\u{305}\u{315}\u{5ae}b", "\u{e0}\u{5ae}\u{305}\u{315}b");
1896     }
1897
1898     #[test]
1899     fn test_nfkc_chars() {
1900         macro_rules! t {
1901             ($input: expr, $expected: expr) => {
1902                 assert_eq!($input.nfkc_chars().collect::<String>(), $expected);
1903             }
1904         }
1905         t!("abc", "abc");
1906         t!("\u{1e0b}\u{1c4}", "\u{1e0b}D\u{17d}");
1907         t!("\u{2026}", "...");
1908         t!("\u{2126}", "\u{3a9}");
1909         t!("\u{1e0b}\u{323}", "\u{1e0d}\u{307}");
1910         t!("\u{1e0d}\u{307}", "\u{1e0d}\u{307}");
1911         t!("a\u{301}", "\u{e1}");
1912         t!("\u{301}a", "\u{301}a");
1913         t!("\u{d4db}", "\u{d4db}");
1914         t!("\u{ac1c}", "\u{ac1c}");
1915         t!("a\u{300}\u{305}\u{315}\u{5ae}b", "\u{e0}\u{5ae}\u{305}\u{315}b");
1916     }
1917
1918     #[test]
1919     fn test_lines() {
1920         let data = "\nMäry häd ä little lämb\n\nLittle lämb\n";
1921         let lines: Vec<&str> = data.lines().collect();
1922         assert_eq!(lines, vec!["", "Märy häd ä little lämb", "", "Little lämb"]);
1923
1924         let data = "\nMäry häd ä little lämb\n\nLittle lämb"; // no trailing \n
1925         let lines: Vec<&str> = data.lines().collect();
1926         assert_eq!(lines, vec!["", "Märy häd ä little lämb", "", "Little lämb"]);
1927     }
1928
1929     #[test]
1930     fn test_graphemes() {
1931         use std::iter::order;
1932         // official Unicode test data
1933         // from http://www.unicode.org/Public/UCD/latest/ucd/auxiliary/GraphemeBreakTest.txt
1934         let test_same: [(_, &[_]), .. 325] = [
1935             ("\u{20}\u{20}", &["\u{20}", "\u{20}"]),
1936             ("\u{20}\u{308}\u{20}", &["\u{20}\u{308}", "\u{20}"]),
1937             ("\u{20}\u{D}", &["\u{20}", "\u{D}"]),
1938             ("\u{20}\u{308}\u{D}", &["\u{20}\u{308}", "\u{D}"]),
1939             ("\u{20}\u{A}", &["\u{20}", "\u{A}"]),
1940             ("\u{20}\u{308}\u{A}", &["\u{20}\u{308}", "\u{A}"]),
1941             ("\u{20}\u{1}", &["\u{20}", "\u{1}"]),
1942             ("\u{20}\u{308}\u{1}", &["\u{20}\u{308}", "\u{1}"]),
1943             ("\u{20}\u{300}", &["\u{20}\u{300}"]),
1944             ("\u{20}\u{308}\u{300}", &["\u{20}\u{308}\u{300}"]),
1945             ("\u{20}\u{1100}", &["\u{20}", "\u{1100}"]),
1946             ("\u{20}\u{308}\u{1100}", &["\u{20}\u{308}", "\u{1100}"]),
1947             ("\u{20}\u{1160}", &["\u{20}", "\u{1160}"]),
1948             ("\u{20}\u{308}\u{1160}", &["\u{20}\u{308}", "\u{1160}"]),
1949             ("\u{20}\u{11A8}", &["\u{20}", "\u{11A8}"]),
1950             ("\u{20}\u{308}\u{11A8}", &["\u{20}\u{308}", "\u{11A8}"]),
1951             ("\u{20}\u{AC00}", &["\u{20}", "\u{AC00}"]),
1952             ("\u{20}\u{308}\u{AC00}", &["\u{20}\u{308}", "\u{AC00}"]),
1953             ("\u{20}\u{AC01}", &["\u{20}", "\u{AC01}"]),
1954             ("\u{20}\u{308}\u{AC01}", &["\u{20}\u{308}", "\u{AC01}"]),
1955             ("\u{20}\u{1F1E6}", &["\u{20}", "\u{1F1E6}"]),
1956             ("\u{20}\u{308}\u{1F1E6}", &["\u{20}\u{308}", "\u{1F1E6}"]),
1957             ("\u{20}\u{378}", &["\u{20}", "\u{378}"]),
1958             ("\u{20}\u{308}\u{378}", &["\u{20}\u{308}", "\u{378}"]),
1959             ("\u{D}\u{20}", &["\u{D}", "\u{20}"]),
1960             ("\u{D}\u{308}\u{20}", &["\u{D}", "\u{308}", "\u{20}"]),
1961             ("\u{D}\u{D}", &["\u{D}", "\u{D}"]),
1962             ("\u{D}\u{308}\u{D}", &["\u{D}", "\u{308}", "\u{D}"]),
1963             ("\u{D}\u{A}", &["\u{D}\u{A}"]),
1964             ("\u{D}\u{308}\u{A}", &["\u{D}", "\u{308}", "\u{A}"]),
1965             ("\u{D}\u{1}", &["\u{D}", "\u{1}"]),
1966             ("\u{D}\u{308}\u{1}", &["\u{D}", "\u{308}", "\u{1}"]),
1967             ("\u{D}\u{300}", &["\u{D}", "\u{300}"]),
1968             ("\u{D}\u{308}\u{300}", &["\u{D}", "\u{308}\u{300}"]),
1969             ("\u{D}\u{903}", &["\u{D}", "\u{903}"]),
1970             ("\u{D}\u{1100}", &["\u{D}", "\u{1100}"]),
1971             ("\u{D}\u{308}\u{1100}", &["\u{D}", "\u{308}", "\u{1100}"]),
1972             ("\u{D}\u{1160}", &["\u{D}", "\u{1160}"]),
1973             ("\u{D}\u{308}\u{1160}", &["\u{D}", "\u{308}", "\u{1160}"]),
1974             ("\u{D}\u{11A8}", &["\u{D}", "\u{11A8}"]),
1975             ("\u{D}\u{308}\u{11A8}", &["\u{D}", "\u{308}", "\u{11A8}"]),
1976             ("\u{D}\u{AC00}", &["\u{D}", "\u{AC00}"]),
1977             ("\u{D}\u{308}\u{AC00}", &["\u{D}", "\u{308}", "\u{AC00}"]),
1978             ("\u{D}\u{AC01}", &["\u{D}", "\u{AC01}"]),
1979             ("\u{D}\u{308}\u{AC01}", &["\u{D}", "\u{308}", "\u{AC01}"]),
1980             ("\u{D}\u{1F1E6}", &["\u{D}", "\u{1F1E6}"]),
1981             ("\u{D}\u{308}\u{1F1E6}", &["\u{D}", "\u{308}", "\u{1F1E6}"]),
1982             ("\u{D}\u{378}", &["\u{D}", "\u{378}"]),
1983             ("\u{D}\u{308}\u{378}", &["\u{D}", "\u{308}", "\u{378}"]),
1984             ("\u{A}\u{20}", &["\u{A}", "\u{20}"]),
1985             ("\u{A}\u{308}\u{20}", &["\u{A}", "\u{308}", "\u{20}"]),
1986             ("\u{A}\u{D}", &["\u{A}", "\u{D}"]),
1987             ("\u{A}\u{308}\u{D}", &["\u{A}", "\u{308}", "\u{D}"]),
1988             ("\u{A}\u{A}", &["\u{A}", "\u{A}"]),
1989             ("\u{A}\u{308}\u{A}", &["\u{A}", "\u{308}", "\u{A}"]),
1990             ("\u{A}\u{1}", &["\u{A}", "\u{1}"]),
1991             ("\u{A}\u{308}\u{1}", &["\u{A}", "\u{308}", "\u{1}"]),
1992             ("\u{A}\u{300}", &["\u{A}", "\u{300}"]),
1993             ("\u{A}\u{308}\u{300}", &["\u{A}", "\u{308}\u{300}"]),
1994             ("\u{A}\u{903}", &["\u{A}", "\u{903}"]),
1995             ("\u{A}\u{1100}", &["\u{A}", "\u{1100}"]),
1996             ("\u{A}\u{308}\u{1100}", &["\u{A}", "\u{308}", "\u{1100}"]),
1997             ("\u{A}\u{1160}", &["\u{A}", "\u{1160}"]),
1998             ("\u{A}\u{308}\u{1160}", &["\u{A}", "\u{308}", "\u{1160}"]),
1999             ("\u{A}\u{11A8}", &["\u{A}", "\u{11A8}"]),
2000             ("\u{A}\u{308}\u{11A8}", &["\u{A}", "\u{308}", "\u{11A8}"]),
2001             ("\u{A}\u{AC00}", &["\u{A}", "\u{AC00}"]),
2002             ("\u{A}\u{308}\u{AC00}", &["\u{A}", "\u{308}", "\u{AC00}"]),
2003             ("\u{A}\u{AC01}", &["\u{A}", "\u{AC01}"]),
2004             ("\u{A}\u{308}\u{AC01}", &["\u{A}", "\u{308}", "\u{AC01}"]),
2005             ("\u{A}\u{1F1E6}", &["\u{A}", "\u{1F1E6}"]),
2006             ("\u{A}\u{308}\u{1F1E6}", &["\u{A}", "\u{308}", "\u{1F1E6}"]),
2007             ("\u{A}\u{378}", &["\u{A}", "\u{378}"]),
2008             ("\u{A}\u{308}\u{378}", &["\u{A}", "\u{308}", "\u{378}"]),
2009             ("\u{1}\u{20}", &["\u{1}", "\u{20}"]),
2010             ("\u{1}\u{308}\u{20}", &["\u{1}", "\u{308}", "\u{20}"]),
2011             ("\u{1}\u{D}", &["\u{1}", "\u{D}"]),
2012             ("\u{1}\u{308}\u{D}", &["\u{1}", "\u{308}", "\u{D}"]),
2013             ("\u{1}\u{A}", &["\u{1}", "\u{A}"]),
2014             ("\u{1}\u{308}\u{A}", &["\u{1}", "\u{308}", "\u{A}"]),
2015             ("\u{1}\u{1}", &["\u{1}", "\u{1}"]),
2016             ("\u{1}\u{308}\u{1}", &["\u{1}", "\u{308}", "\u{1}"]),
2017             ("\u{1}\u{300}", &["\u{1}", "\u{300}"]),
2018             ("\u{1}\u{308}\u{300}", &["\u{1}", "\u{308}\u{300}"]),
2019             ("\u{1}\u{903}", &["\u{1}", "\u{903}"]),
2020             ("\u{1}\u{1100}", &["\u{1}", "\u{1100}"]),
2021             ("\u{1}\u{308}\u{1100}", &["\u{1}", "\u{308}", "\u{1100}"]),
2022             ("\u{1}\u{1160}", &["\u{1}", "\u{1160}"]),
2023             ("\u{1}\u{308}\u{1160}", &["\u{1}", "\u{308}", "\u{1160}"]),
2024             ("\u{1}\u{11A8}", &["\u{1}", "\u{11A8}"]),
2025             ("\u{1}\u{308}\u{11A8}", &["\u{1}", "\u{308}", "\u{11A8}"]),
2026             ("\u{1}\u{AC00}", &["\u{1}", "\u{AC00}"]),
2027             ("\u{1}\u{308}\u{AC00}", &["\u{1}", "\u{308}", "\u{AC00}"]),
2028             ("\u{1}\u{AC01}", &["\u{1}", "\u{AC01}"]),
2029             ("\u{1}\u{308}\u{AC01}", &["\u{1}", "\u{308}", "\u{AC01}"]),
2030             ("\u{1}\u{1F1E6}", &["\u{1}", "\u{1F1E6}"]),
2031             ("\u{1}\u{308}\u{1F1E6}", &["\u{1}", "\u{308}", "\u{1F1E6}"]),
2032             ("\u{1}\u{378}", &["\u{1}", "\u{378}"]),
2033             ("\u{1}\u{308}\u{378}", &["\u{1}", "\u{308}", "\u{378}"]),
2034             ("\u{300}\u{20}", &["\u{300}", "\u{20}"]),
2035             ("\u{300}\u{308}\u{20}", &["\u{300}\u{308}", "\u{20}"]),
2036             ("\u{300}\u{D}", &["\u{300}", "\u{D}"]),
2037             ("\u{300}\u{308}\u{D}", &["\u{300}\u{308}", "\u{D}"]),
2038             ("\u{300}\u{A}", &["\u{300}", "\u{A}"]),
2039             ("\u{300}\u{308}\u{A}", &["\u{300}\u{308}", "\u{A}"]),
2040             ("\u{300}\u{1}", &["\u{300}", "\u{1}"]),
2041             ("\u{300}\u{308}\u{1}", &["\u{300}\u{308}", "\u{1}"]),
2042             ("\u{300}\u{300}", &["\u{300}\u{300}"]),
2043             ("\u{300}\u{308}\u{300}", &["\u{300}\u{308}\u{300}"]),
2044             ("\u{300}\u{1100}", &["\u{300}", "\u{1100}"]),
2045             ("\u{300}\u{308}\u{1100}", &["\u{300}\u{308}", "\u{1100}"]),
2046             ("\u{300}\u{1160}", &["\u{300}", "\u{1160}"]),
2047             ("\u{300}\u{308}\u{1160}", &["\u{300}\u{308}", "\u{1160}"]),
2048             ("\u{300}\u{11A8}", &["\u{300}", "\u{11A8}"]),
2049             ("\u{300}\u{308}\u{11A8}", &["\u{300}\u{308}", "\u{11A8}"]),
2050             ("\u{300}\u{AC00}", &["\u{300}", "\u{AC00}"]),
2051             ("\u{300}\u{308}\u{AC00}", &["\u{300}\u{308}", "\u{AC00}"]),
2052             ("\u{300}\u{AC01}", &["\u{300}", "\u{AC01}"]),
2053             ("\u{300}\u{308}\u{AC01}", &["\u{300}\u{308}", "\u{AC01}"]),
2054             ("\u{300}\u{1F1E6}", &["\u{300}", "\u{1F1E6}"]),
2055             ("\u{300}\u{308}\u{1F1E6}", &["\u{300}\u{308}", "\u{1F1E6}"]),
2056             ("\u{300}\u{378}", &["\u{300}", "\u{378}"]),
2057             ("\u{300}\u{308}\u{378}", &["\u{300}\u{308}", "\u{378}"]),
2058             ("\u{903}\u{20}", &["\u{903}", "\u{20}"]),
2059             ("\u{903}\u{308}\u{20}", &["\u{903}\u{308}", "\u{20}"]),
2060             ("\u{903}\u{D}", &["\u{903}", "\u{D}"]),
2061             ("\u{903}\u{308}\u{D}", &["\u{903}\u{308}", "\u{D}"]),
2062             ("\u{903}\u{A}", &["\u{903}", "\u{A}"]),
2063             ("\u{903}\u{308}\u{A}", &["\u{903}\u{308}", "\u{A}"]),
2064             ("\u{903}\u{1}", &["\u{903}", "\u{1}"]),
2065             ("\u{903}\u{308}\u{1}", &["\u{903}\u{308}", "\u{1}"]),
2066             ("\u{903}\u{300}", &["\u{903}\u{300}"]),
2067             ("\u{903}\u{308}\u{300}", &["\u{903}\u{308}\u{300}"]),
2068             ("\u{903}\u{1100}", &["\u{903}", "\u{1100}"]),
2069             ("\u{903}\u{308}\u{1100}", &["\u{903}\u{308}", "\u{1100}"]),
2070             ("\u{903}\u{1160}", &["\u{903}", "\u{1160}"]),
2071             ("\u{903}\u{308}\u{1160}", &["\u{903}\u{308}", "\u{1160}"]),
2072             ("\u{903}\u{11A8}", &["\u{903}", "\u{11A8}"]),
2073             ("\u{903}\u{308}\u{11A8}", &["\u{903}\u{308}", "\u{11A8}"]),
2074             ("\u{903}\u{AC00}", &["\u{903}", "\u{AC00}"]),
2075             ("\u{903}\u{308}\u{AC00}", &["\u{903}\u{308}", "\u{AC00}"]),
2076             ("\u{903}\u{AC01}", &["\u{903}", "\u{AC01}"]),
2077             ("\u{903}\u{308}\u{AC01}", &["\u{903}\u{308}", "\u{AC01}"]),
2078             ("\u{903}\u{1F1E6}", &["\u{903}", "\u{1F1E6}"]),
2079             ("\u{903}\u{308}\u{1F1E6}", &["\u{903}\u{308}", "\u{1F1E6}"]),
2080             ("\u{903}\u{378}", &["\u{903}", "\u{378}"]),
2081             ("\u{903}\u{308}\u{378}", &["\u{903}\u{308}", "\u{378}"]),
2082             ("\u{1100}\u{20}", &["\u{1100}", "\u{20}"]),
2083             ("\u{1100}\u{308}\u{20}", &["\u{1100}\u{308}", "\u{20}"]),
2084             ("\u{1100}\u{D}", &["\u{1100}", "\u{D}"]),
2085             ("\u{1100}\u{308}\u{D}", &["\u{1100}\u{308}", "\u{D}"]),
2086             ("\u{1100}\u{A}", &["\u{1100}", "\u{A}"]),
2087             ("\u{1100}\u{308}\u{A}", &["\u{1100}\u{308}", "\u{A}"]),
2088             ("\u{1100}\u{1}", &["\u{1100}", "\u{1}"]),
2089             ("\u{1100}\u{308}\u{1}", &["\u{1100}\u{308}", "\u{1}"]),
2090             ("\u{1100}\u{300}", &["\u{1100}\u{300}"]),
2091             ("\u{1100}\u{308}\u{300}", &["\u{1100}\u{308}\u{300}"]),
2092             ("\u{1100}\u{1100}", &["\u{1100}\u{1100}"]),
2093             ("\u{1100}\u{308}\u{1100}", &["\u{1100}\u{308}", "\u{1100}"]),
2094             ("\u{1100}\u{1160}", &["\u{1100}\u{1160}"]),
2095             ("\u{1100}\u{308}\u{1160}", &["\u{1100}\u{308}", "\u{1160}"]),
2096             ("\u{1100}\u{11A8}", &["\u{1100}", "\u{11A8}"]),
2097             ("\u{1100}\u{308}\u{11A8}", &["\u{1100}\u{308}", "\u{11A8}"]),
2098             ("\u{1100}\u{AC00}", &["\u{1100}\u{AC00}"]),
2099             ("\u{1100}\u{308}\u{AC00}", &["\u{1100}\u{308}", "\u{AC00}"]),
2100             ("\u{1100}\u{AC01}", &["\u{1100}\u{AC01}"]),
2101             ("\u{1100}\u{308}\u{AC01}", &["\u{1100}\u{308}", "\u{AC01}"]),
2102             ("\u{1100}\u{1F1E6}", &["\u{1100}", "\u{1F1E6}"]),
2103             ("\u{1100}\u{308}\u{1F1E6}", &["\u{1100}\u{308}", "\u{1F1E6}"]),
2104             ("\u{1100}\u{378}", &["\u{1100}", "\u{378}"]),
2105             ("\u{1100}\u{308}\u{378}", &["\u{1100}\u{308}", "\u{378}"]),
2106             ("\u{1160}\u{20}", &["\u{1160}", "\u{20}"]),
2107             ("\u{1160}\u{308}\u{20}", &["\u{1160}\u{308}", "\u{20}"]),
2108             ("\u{1160}\u{D}", &["\u{1160}", "\u{D}"]),
2109             ("\u{1160}\u{308}\u{D}", &["\u{1160}\u{308}", "\u{D}"]),
2110             ("\u{1160}\u{A}", &["\u{1160}", "\u{A}"]),
2111             ("\u{1160}\u{308}\u{A}", &["\u{1160}\u{308}", "\u{A}"]),
2112             ("\u{1160}\u{1}", &["\u{1160}", "\u{1}"]),
2113             ("\u{1160}\u{308}\u{1}", &["\u{1160}\u{308}", "\u{1}"]),
2114             ("\u{1160}\u{300}", &["\u{1160}\u{300}"]),
2115             ("\u{1160}\u{308}\u{300}", &["\u{1160}\u{308}\u{300}"]),
2116             ("\u{1160}\u{1100}", &["\u{1160}", "\u{1100}"]),
2117             ("\u{1160}\u{308}\u{1100}", &["\u{1160}\u{308}", "\u{1100}"]),
2118             ("\u{1160}\u{1160}", &["\u{1160}\u{1160}"]),
2119             ("\u{1160}\u{308}\u{1160}", &["\u{1160}\u{308}", "\u{1160}"]),
2120             ("\u{1160}\u{11A8}", &["\u{1160}\u{11A8}"]),
2121             ("\u{1160}\u{308}\u{11A8}", &["\u{1160}\u{308}", "\u{11A8}"]),
2122             ("\u{1160}\u{AC00}", &["\u{1160}", "\u{AC00}"]),
2123             ("\u{1160}\u{308}\u{AC00}", &["\u{1160}\u{308}", "\u{AC00}"]),
2124             ("\u{1160}\u{AC01}", &["\u{1160}", "\u{AC01}"]),
2125             ("\u{1160}\u{308}\u{AC01}", &["\u{1160}\u{308}", "\u{AC01}"]),
2126             ("\u{1160}\u{1F1E6}", &["\u{1160}", "\u{1F1E6}"]),
2127             ("\u{1160}\u{308}\u{1F1E6}", &["\u{1160}\u{308}", "\u{1F1E6}"]),
2128             ("\u{1160}\u{378}", &["\u{1160}", "\u{378}"]),
2129             ("\u{1160}\u{308}\u{378}", &["\u{1160}\u{308}", "\u{378}"]),
2130             ("\u{11A8}\u{20}", &["\u{11A8}", "\u{20}"]),
2131             ("\u{11A8}\u{308}\u{20}", &["\u{11A8}\u{308}", "\u{20}"]),
2132             ("\u{11A8}\u{D}", &["\u{11A8}", "\u{D}"]),
2133             ("\u{11A8}\u{308}\u{D}", &["\u{11A8}\u{308}", "\u{D}"]),
2134             ("\u{11A8}\u{A}", &["\u{11A8}", "\u{A}"]),
2135             ("\u{11A8}\u{308}\u{A}", &["\u{11A8}\u{308}", "\u{A}"]),
2136             ("\u{11A8}\u{1}", &["\u{11A8}", "\u{1}"]),
2137             ("\u{11A8}\u{308}\u{1}", &["\u{11A8}\u{308}", "\u{1}"]),
2138             ("\u{11A8}\u{300}", &["\u{11A8}\u{300}"]),
2139             ("\u{11A8}\u{308}\u{300}", &["\u{11A8}\u{308}\u{300}"]),
2140             ("\u{11A8}\u{1100}", &["\u{11A8}", "\u{1100}"]),
2141             ("\u{11A8}\u{308}\u{1100}", &["\u{11A8}\u{308}", "\u{1100}"]),
2142             ("\u{11A8}\u{1160}", &["\u{11A8}", "\u{1160}"]),
2143             ("\u{11A8}\u{308}\u{1160}", &["\u{11A8}\u{308}", "\u{1160}"]),
2144             ("\u{11A8}\u{11A8}", &["\u{11A8}\u{11A8}"]),
2145             ("\u{11A8}\u{308}\u{11A8}", &["\u{11A8}\u{308}", "\u{11A8}"]),
2146             ("\u{11A8}\u{AC00}", &["\u{11A8}", "\u{AC00}"]),
2147             ("\u{11A8}\u{308}\u{AC00}", &["\u{11A8}\u{308}", "\u{AC00}"]),
2148             ("\u{11A8}\u{AC01}", &["\u{11A8}", "\u{AC01}"]),
2149             ("\u{11A8}\u{308}\u{AC01}", &["\u{11A8}\u{308}", "\u{AC01}"]),
2150             ("\u{11A8}\u{1F1E6}", &["\u{11A8}", "\u{1F1E6}"]),
2151             ("\u{11A8}\u{308}\u{1F1E6}", &["\u{11A8}\u{308}", "\u{1F1E6}"]),
2152             ("\u{11A8}\u{378}", &["\u{11A8}", "\u{378}"]),
2153             ("\u{11A8}\u{308}\u{378}", &["\u{11A8}\u{308}", "\u{378}"]),
2154             ("\u{AC00}\u{20}", &["\u{AC00}", "\u{20}"]),
2155             ("\u{AC00}\u{308}\u{20}", &["\u{AC00}\u{308}", "\u{20}"]),
2156             ("\u{AC00}\u{D}", &["\u{AC00}", "\u{D}"]),
2157             ("\u{AC00}\u{308}\u{D}", &["\u{AC00}\u{308}", "\u{D}"]),
2158             ("\u{AC00}\u{A}", &["\u{AC00}", "\u{A}"]),
2159             ("\u{AC00}\u{308}\u{A}", &["\u{AC00}\u{308}", "\u{A}"]),
2160             ("\u{AC00}\u{1}", &["\u{AC00}", "\u{1}"]),
2161             ("\u{AC00}\u{308}\u{1}", &["\u{AC00}\u{308}", "\u{1}"]),
2162             ("\u{AC00}\u{300}", &["\u{AC00}\u{300}"]),
2163             ("\u{AC00}\u{308}\u{300}", &["\u{AC00}\u{308}\u{300}"]),
2164             ("\u{AC00}\u{1100}", &["\u{AC00}", "\u{1100}"]),
2165             ("\u{AC00}\u{308}\u{1100}", &["\u{AC00}\u{308}", "\u{1100}"]),
2166             ("\u{AC00}\u{1160}", &["\u{AC00}\u{1160}"]),
2167             ("\u{AC00}\u{308}\u{1160}", &["\u{AC00}\u{308}", "\u{1160}"]),
2168             ("\u{AC00}\u{11A8}", &["\u{AC00}\u{11A8}"]),
2169             ("\u{AC00}\u{308}\u{11A8}", &["\u{AC00}\u{308}", "\u{11A8}"]),
2170             ("\u{AC00}\u{AC00}", &["\u{AC00}", "\u{AC00}"]),
2171             ("\u{AC00}\u{308}\u{AC00}", &["\u{AC00}\u{308}", "\u{AC00}"]),
2172             ("\u{AC00}\u{AC01}", &["\u{AC00}", "\u{AC01}"]),
2173             ("\u{AC00}\u{308}\u{AC01}", &["\u{AC00}\u{308}", "\u{AC01}"]),
2174             ("\u{AC00}\u{1F1E6}", &["\u{AC00}", "\u{1F1E6}"]),
2175             ("\u{AC00}\u{308}\u{1F1E6}", &["\u{AC00}\u{308}", "\u{1F1E6}"]),
2176             ("\u{AC00}\u{378}", &["\u{AC00}", "\u{378}"]),
2177             ("\u{AC00}\u{308}\u{378}", &["\u{AC00}\u{308}", "\u{378}"]),
2178             ("\u{AC01}\u{20}", &["\u{AC01}", "\u{20}"]),
2179             ("\u{AC01}\u{308}\u{20}", &["\u{AC01}\u{308}", "\u{20}"]),
2180             ("\u{AC01}\u{D}", &["\u{AC01}", "\u{D}"]),
2181             ("\u{AC01}\u{308}\u{D}", &["\u{AC01}\u{308}", "\u{D}"]),
2182             ("\u{AC01}\u{A}", &["\u{AC01}", "\u{A}"]),
2183             ("\u{AC01}\u{308}\u{A}", &["\u{AC01}\u{308}", "\u{A}"]),
2184             ("\u{AC01}\u{1}", &["\u{AC01}", "\u{1}"]),
2185             ("\u{AC01}\u{308}\u{1}", &["\u{AC01}\u{308}", "\u{1}"]),
2186             ("\u{AC01}\u{300}", &["\u{AC01}\u{300}"]),
2187             ("\u{AC01}\u{308}\u{300}", &["\u{AC01}\u{308}\u{300}"]),
2188             ("\u{AC01}\u{1100}", &["\u{AC01}", "\u{1100}"]),
2189             ("\u{AC01}\u{308}\u{1100}", &["\u{AC01}\u{308}", "\u{1100}"]),
2190             ("\u{AC01}\u{1160}", &["\u{AC01}", "\u{1160}"]),
2191             ("\u{AC01}\u{308}\u{1160}", &["\u{AC01}\u{308}", "\u{1160}"]),
2192             ("\u{AC01}\u{11A8}", &["\u{AC01}\u{11A8}"]),
2193             ("\u{AC01}\u{308}\u{11A8}", &["\u{AC01}\u{308}", "\u{11A8}"]),
2194             ("\u{AC01}\u{AC00}", &["\u{AC01}", "\u{AC00}"]),
2195             ("\u{AC01}\u{308}\u{AC00}", &["\u{AC01}\u{308}", "\u{AC00}"]),
2196             ("\u{AC01}\u{AC01}", &["\u{AC01}", "\u{AC01}"]),
2197             ("\u{AC01}\u{308}\u{AC01}", &["\u{AC01}\u{308}", "\u{AC01}"]),
2198             ("\u{AC01}\u{1F1E6}", &["\u{AC01}", "\u{1F1E6}"]),
2199             ("\u{AC01}\u{308}\u{1F1E6}", &["\u{AC01}\u{308}", "\u{1F1E6}"]),
2200             ("\u{AC01}\u{378}", &["\u{AC01}", "\u{378}"]),
2201             ("\u{AC01}\u{308}\u{378}", &["\u{AC01}\u{308}", "\u{378}"]),
2202             ("\u{1F1E6}\u{20}", &["\u{1F1E6}", "\u{20}"]),
2203             ("\u{1F1E6}\u{308}\u{20}", &["\u{1F1E6}\u{308}", "\u{20}"]),
2204             ("\u{1F1E6}\u{D}", &["\u{1F1E6}", "\u{D}"]),
2205             ("\u{1F1E6}\u{308}\u{D}", &["\u{1F1E6}\u{308}", "\u{D}"]),
2206             ("\u{1F1E6}\u{A}", &["\u{1F1E6}", "\u{A}"]),
2207             ("\u{1F1E6}\u{308}\u{A}", &["\u{1F1E6}\u{308}", "\u{A}"]),
2208             ("\u{1F1E6}\u{1}", &["\u{1F1E6}", "\u{1}"]),
2209             ("\u{1F1E6}\u{308}\u{1}", &["\u{1F1E6}\u{308}", "\u{1}"]),
2210             ("\u{1F1E6}\u{300}", &["\u{1F1E6}\u{300}"]),
2211             ("\u{1F1E6}\u{308}\u{300}", &["\u{1F1E6}\u{308}\u{300}"]),
2212             ("\u{1F1E6}\u{1100}", &["\u{1F1E6}", "\u{1100}"]),
2213             ("\u{1F1E6}\u{308}\u{1100}", &["\u{1F1E6}\u{308}", "\u{1100}"]),
2214             ("\u{1F1E6}\u{1160}", &["\u{1F1E6}", "\u{1160}"]),
2215             ("\u{1F1E6}\u{308}\u{1160}", &["\u{1F1E6}\u{308}", "\u{1160}"]),
2216             ("\u{1F1E6}\u{11A8}", &["\u{1F1E6}", "\u{11A8}"]),
2217             ("\u{1F1E6}\u{308}\u{11A8}", &["\u{1F1E6}\u{308}", "\u{11A8}"]),
2218             ("\u{1F1E6}\u{AC00}", &["\u{1F1E6}", "\u{AC00}"]),
2219             ("\u{1F1E6}\u{308}\u{AC00}", &["\u{1F1E6}\u{308}", "\u{AC00}"]),
2220             ("\u{1F1E6}\u{AC01}", &["\u{1F1E6}", "\u{AC01}"]),
2221             ("\u{1F1E6}\u{308}\u{AC01}", &["\u{1F1E6}\u{308}", "\u{AC01}"]),
2222             ("\u{1F1E6}\u{1F1E6}", &["\u{1F1E6}\u{1F1E6}"]),
2223             ("\u{1F1E6}\u{308}\u{1F1E6}", &["\u{1F1E6}\u{308}", "\u{1F1E6}"]),
2224             ("\u{1F1E6}\u{378}", &["\u{1F1E6}", "\u{378}"]),
2225             ("\u{1F1E6}\u{308}\u{378}", &["\u{1F1E6}\u{308}", "\u{378}"]),
2226             ("\u{378}\u{20}", &["\u{378}", "\u{20}"]),
2227             ("\u{378}\u{308}\u{20}", &["\u{378}\u{308}", "\u{20}"]),
2228             ("\u{378}\u{D}", &["\u{378}", "\u{D}"]),
2229             ("\u{378}\u{308}\u{D}", &["\u{378}\u{308}", "\u{D}"]),
2230             ("\u{378}\u{A}", &["\u{378}", "\u{A}"]),
2231             ("\u{378}\u{308}\u{A}", &["\u{378}\u{308}", "\u{A}"]),
2232             ("\u{378}\u{1}", &["\u{378}", "\u{1}"]),
2233             ("\u{378}\u{308}\u{1}", &["\u{378}\u{308}", "\u{1}"]),
2234             ("\u{378}\u{300}", &["\u{378}\u{300}"]),
2235             ("\u{378}\u{308}\u{300}", &["\u{378}\u{308}\u{300}"]),
2236             ("\u{378}\u{1100}", &["\u{378}", "\u{1100}"]),
2237             ("\u{378}\u{308}\u{1100}", &["\u{378}\u{308}", "\u{1100}"]),
2238             ("\u{378}\u{1160}", &["\u{378}", "\u{1160}"]),
2239             ("\u{378}\u{308}\u{1160}", &["\u{378}\u{308}", "\u{1160}"]),
2240             ("\u{378}\u{11A8}", &["\u{378}", "\u{11A8}"]),
2241             ("\u{378}\u{308}\u{11A8}", &["\u{378}\u{308}", "\u{11A8}"]),
2242             ("\u{378}\u{AC00}", &["\u{378}", "\u{AC00}"]),
2243             ("\u{378}\u{308}\u{AC00}", &["\u{378}\u{308}", "\u{AC00}"]),
2244             ("\u{378}\u{AC01}", &["\u{378}", "\u{AC01}"]),
2245             ("\u{378}\u{308}\u{AC01}", &["\u{378}\u{308}", "\u{AC01}"]),
2246             ("\u{378}\u{1F1E6}", &["\u{378}", "\u{1F1E6}"]),
2247             ("\u{378}\u{308}\u{1F1E6}", &["\u{378}\u{308}", "\u{1F1E6}"]),
2248             ("\u{378}\u{378}", &["\u{378}", "\u{378}"]),
2249             ("\u{378}\u{308}\u{378}", &["\u{378}\u{308}", "\u{378}"]),
2250             ("\u{61}\u{1F1E6}\u{62}", &["\u{61}", "\u{1F1E6}", "\u{62}"]),
2251             ("\u{1F1F7}\u{1F1FA}", &["\u{1F1F7}\u{1F1FA}"]),
2252             ("\u{1F1F7}\u{1F1FA}\u{1F1F8}", &["\u{1F1F7}\u{1F1FA}\u{1F1F8}"]),
2253             ("\u{1F1F7}\u{1F1FA}\u{1F1F8}\u{1F1EA}",
2254             &["\u{1F1F7}\u{1F1FA}\u{1F1F8}\u{1F1EA}"]),
2255             ("\u{1F1F7}\u{1F1FA}\u{200B}\u{1F1F8}\u{1F1EA}",
2256              &["\u{1F1F7}\u{1F1FA}", "\u{200B}", "\u{1F1F8}\u{1F1EA}"]),
2257             ("\u{1F1E6}\u{1F1E7}\u{1F1E8}", &["\u{1F1E6}\u{1F1E7}\u{1F1E8}"]),
2258             ("\u{1F1E6}\u{200D}\u{1F1E7}\u{1F1E8}", &["\u{1F1E6}\u{200D}",
2259              "\u{1F1E7}\u{1F1E8}"]),
2260             ("\u{1F1E6}\u{1F1E7}\u{200D}\u{1F1E8}",
2261              &["\u{1F1E6}\u{1F1E7}\u{200D}", "\u{1F1E8}"]),
2262             ("\u{20}\u{200D}\u{646}", &["\u{20}\u{200D}", "\u{646}"]),
2263             ("\u{646}\u{200D}\u{20}", &["\u{646}\u{200D}", "\u{20}"]),
2264         ];
2265
2266         let test_diff: [(_, &[_], &[_]), .. 23] = [
2267             ("\u{20}\u{903}", &["\u{20}\u{903}"], &["\u{20}", "\u{903}"]), ("\u{20}\u{308}\u{903}",
2268             &["\u{20}\u{308}\u{903}"], &["\u{20}\u{308}", "\u{903}"]), ("\u{D}\u{308}\u{903}",
2269             &["\u{D}", "\u{308}\u{903}"], &["\u{D}", "\u{308}", "\u{903}"]), ("\u{A}\u{308}\u{903}",
2270             &["\u{A}", "\u{308}\u{903}"], &["\u{A}", "\u{308}", "\u{903}"]), ("\u{1}\u{308}\u{903}",
2271             &["\u{1}", "\u{308}\u{903}"], &["\u{1}", "\u{308}", "\u{903}"]), ("\u{300}\u{903}",
2272             &["\u{300}\u{903}"], &["\u{300}", "\u{903}"]), ("\u{300}\u{308}\u{903}",
2273             &["\u{300}\u{308}\u{903}"], &["\u{300}\u{308}", "\u{903}"]), ("\u{903}\u{903}",
2274             &["\u{903}\u{903}"], &["\u{903}", "\u{903}"]), ("\u{903}\u{308}\u{903}",
2275             &["\u{903}\u{308}\u{903}"], &["\u{903}\u{308}", "\u{903}"]), ("\u{1100}\u{903}",
2276             &["\u{1100}\u{903}"], &["\u{1100}", "\u{903}"]), ("\u{1100}\u{308}\u{903}",
2277             &["\u{1100}\u{308}\u{903}"], &["\u{1100}\u{308}", "\u{903}"]), ("\u{1160}\u{903}",
2278             &["\u{1160}\u{903}"], &["\u{1160}", "\u{903}"]), ("\u{1160}\u{308}\u{903}",
2279             &["\u{1160}\u{308}\u{903}"], &["\u{1160}\u{308}", "\u{903}"]), ("\u{11A8}\u{903}",
2280             &["\u{11A8}\u{903}"], &["\u{11A8}", "\u{903}"]), ("\u{11A8}\u{308}\u{903}",
2281             &["\u{11A8}\u{308}\u{903}"], &["\u{11A8}\u{308}", "\u{903}"]), ("\u{AC00}\u{903}",
2282             &["\u{AC00}\u{903}"], &["\u{AC00}", "\u{903}"]), ("\u{AC00}\u{308}\u{903}",
2283             &["\u{AC00}\u{308}\u{903}"], &["\u{AC00}\u{308}", "\u{903}"]), ("\u{AC01}\u{903}",
2284             &["\u{AC01}\u{903}"], &["\u{AC01}", "\u{903}"]), ("\u{AC01}\u{308}\u{903}",
2285             &["\u{AC01}\u{308}\u{903}"], &["\u{AC01}\u{308}", "\u{903}"]), ("\u{1F1E6}\u{903}",
2286             &["\u{1F1E6}\u{903}"], &["\u{1F1E6}", "\u{903}"]), ("\u{1F1E6}\u{308}\u{903}",
2287             &["\u{1F1E6}\u{308}\u{903}"], &["\u{1F1E6}\u{308}", "\u{903}"]), ("\u{378}\u{903}",
2288             &["\u{378}\u{903}"], &["\u{378}", "\u{903}"]), ("\u{378}\u{308}\u{903}",
2289             &["\u{378}\u{308}\u{903}"], &["\u{378}\u{308}", "\u{903}"]),
2290         ];
2291
2292         for &(s, g) in test_same.iter() {
2293             // test forward iterator
2294             assert!(order::equals(s.graphemes(true), g.iter().map(|&x| x)));
2295             assert!(order::equals(s.graphemes(false), g.iter().map(|&x| x)));
2296
2297             // test reverse iterator
2298             assert!(order::equals(s.graphemes(true).rev(), g.iter().rev().map(|&x| x)));
2299             assert!(order::equals(s.graphemes(false).rev(), g.iter().rev().map(|&x| x)));
2300         }
2301
2302         for &(s, gt, gf) in test_diff.iter() {
2303             // test forward iterator
2304             assert!(order::equals(s.graphemes(true), gt.iter().map(|&x| x)));
2305             assert!(order::equals(s.graphemes(false), gf.iter().map(|&x| x)));
2306
2307             // test reverse iterator
2308             assert!(order::equals(s.graphemes(true).rev(), gt.iter().rev().map(|&x| x)));
2309             assert!(order::equals(s.graphemes(false).rev(), gf.iter().rev().map(|&x| x)));
2310         }
2311
2312         // test the indices iterators
2313         let s = "a̐éö̲\r\n";
2314         let gr_inds = s.grapheme_indices(true).collect::<Vec<(uint, &str)>>();
2315         let b: &[_] = &[(0u, "a̐"), (3, "é"), (6, "ö̲"), (11, "\r\n")];
2316         assert_eq!(gr_inds, b);
2317         let gr_inds = s.grapheme_indices(true).rev().collect::<Vec<(uint, &str)>>();
2318         let b: &[_] = &[(11, "\r\n"), (6, "ö̲"), (3, "é"), (0u, "a̐")];
2319         assert_eq!(gr_inds, b);
2320         let mut gr_inds_iter = s.grapheme_indices(true);
2321         {
2322             let gr_inds = gr_inds_iter.by_ref();
2323             let e1 = gr_inds.size_hint();
2324             assert_eq!(e1, (1, Some(13)));
2325             let c = gr_inds.count();
2326             assert_eq!(c, 4);
2327         }
2328         let e2 = gr_inds_iter.size_hint();
2329         assert_eq!(e2, (0, Some(0)));
2330
2331         // make sure the reverse iterator does the right thing with "\n" at beginning of string
2332         let s = "\n\r\n\r";
2333         let gr = s.graphemes(true).rev().collect::<Vec<&str>>();
2334         let b: &[_] = &["\r", "\r\n", "\n"];
2335         assert_eq!(gr, b);
2336     }
2337
2338     #[test]
2339     fn test_split_strator() {
2340         fn t(s: &str, sep: &str, u: &[&str]) {
2341             let v: Vec<&str> = s.split_str(sep).collect();
2342             assert_eq!(v, u);
2343         }
2344         t("--1233345--", "12345", &["--1233345--"]);
2345         t("abc::hello::there", "::", &["abc", "hello", "there"]);
2346         t("::hello::there", "::", &["", "hello", "there"]);
2347         t("hello::there::", "::", &["hello", "there", ""]);
2348         t("::hello::there::", "::", &["", "hello", "there", ""]);
2349         t("ประเทศไทย中华Việt Nam", "中华", &["ประเทศไทย", "Việt Nam"]);
2350         t("zzXXXzzYYYzz", "zz", &["", "XXX", "YYY", ""]);
2351         t("zzXXXzYYYz", "XXX", &["zz", "zYYYz"]);
2352         t(".XXX.YYY.", ".", &["", "XXX", "YYY", ""]);
2353         t("", ".", &[""]);
2354         t("zz", "zz", &["",""]);
2355         t("ok", "z", &["ok"]);
2356         t("zzz", "zz", &["","z"]);
2357         t("zzzzz", "zz", &["","","z"]);
2358     }
2359
2360     #[test]
2361     fn test_str_default() {
2362         use std::default::Default;
2363         fn t<S: Default + Str>() {
2364             let s: S = Default::default();
2365             assert_eq!(s.as_slice(), "");
2366         }
2367
2368         t::<&str>();
2369         t::<String>();
2370     }
2371
2372     #[test]
2373     fn test_str_container() {
2374         fn sum_len(v: &[&str]) -> uint {
2375             v.iter().map(|x| x.len()).sum()
2376         }
2377
2378         let s = String::from_str("01234");
2379         assert_eq!(5, sum_len(&["012", "", "34"]));
2380         assert_eq!(5, sum_len(&[String::from_str("01").as_slice(),
2381                                 String::from_str("2").as_slice(),
2382                                 String::from_str("34").as_slice(),
2383                                 String::from_str("").as_slice()]));
2384         assert_eq!(5, sum_len(&[s.as_slice()]));
2385     }
2386
2387     #[test]
2388     fn test_str_from_utf8() {
2389         let xs = b"hello";
2390         assert_eq!(from_utf8(xs), Some("hello"));
2391
2392         let xs = "ศไทย中华Việt Nam".as_bytes();
2393         assert_eq!(from_utf8(xs), Some("ศไทย中华Việt Nam"));
2394
2395         let xs = b"hello\xFF";
2396         assert_eq!(from_utf8(xs), None);
2397     }
2398
2399     #[test]
2400     fn test_maybe_owned_traits() {
2401         let s = Slice("abcde");
2402         assert_eq!(s.len(), 5);
2403         assert_eq!(s.as_slice(), "abcde");
2404         assert_eq!(String::from_str(s.as_slice()).as_slice(), "abcde");
2405         assert_eq!(format!("{}", s).as_slice(), "abcde");
2406         assert!(s.lt(&Owned(String::from_str("bcdef"))));
2407         assert_eq!(Slice(""), Default::default());
2408
2409         let o = Owned(String::from_str("abcde"));
2410         assert_eq!(o.len(), 5);
2411         assert_eq!(o.as_slice(), "abcde");
2412         assert_eq!(String::from_str(o.as_slice()).as_slice(), "abcde");
2413         assert_eq!(format!("{}", o).as_slice(), "abcde");
2414         assert!(o.lt(&Slice("bcdef")));
2415         assert_eq!(Owned(String::from_str("")), Default::default());
2416
2417         assert!(s.cmp(&o) == Equal);
2418         assert!(s.equiv(&o));
2419
2420         assert!(o.cmp(&s) == Equal);
2421         assert!(o.equiv(&s));
2422     }
2423
2424     #[test]
2425     fn test_maybe_owned_methods() {
2426         let s = Slice("abcde");
2427         assert!(s.is_slice());
2428         assert!(!s.is_owned());
2429
2430         let o = Owned(String::from_str("abcde"));
2431         assert!(!o.is_slice());
2432         assert!(o.is_owned());
2433     }
2434
2435     #[test]
2436     fn test_maybe_owned_clone() {
2437         assert_eq!(Owned(String::from_str("abcde")), Slice("abcde").clone());
2438         assert_eq!(Owned(String::from_str("abcde")), Owned(String::from_str("abcde")).clone());
2439         assert_eq!(Slice("abcde"), Slice("abcde").clone());
2440         assert_eq!(Slice("abcde"), Owned(String::from_str("abcde")).clone());
2441     }
2442
2443     #[test]
2444     fn test_maybe_owned_into_string() {
2445         assert_eq!(Slice("abcde").into_string(), String::from_str("abcde"));
2446         assert_eq!(Owned(String::from_str("abcde")).into_string(),
2447                    String::from_str("abcde"));
2448     }
2449
2450     #[test]
2451     fn test_into_maybe_owned() {
2452         assert_eq!("abcde".into_maybe_owned(), Slice("abcde"));
2453         assert_eq!((String::from_str("abcde")).into_maybe_owned(), Slice("abcde"));
2454         assert_eq!("abcde".into_maybe_owned(), Owned(String::from_str("abcde")));
2455         assert_eq!((String::from_str("abcde")).into_maybe_owned(),
2456                    Owned(String::from_str("abcde")));
2457     }
2458 }
2459
2460 #[cfg(test)]
2461 mod bench {
2462     use test::Bencher;
2463     use test::black_box;
2464     use super::*;
2465     use std::iter::{IteratorExt, DoubleEndedIteratorExt};
2466     use std::str::StrPrelude;
2467     use std::slice::SlicePrelude;
2468
2469     #[bench]
2470     fn char_iterator(b: &mut Bencher) {
2471         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2472
2473         b.iter(|| s.chars().count());
2474     }
2475
2476     #[bench]
2477     fn char_iterator_for(b: &mut Bencher) {
2478         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2479
2480         b.iter(|| {
2481             for ch in s.chars() { black_box(ch) }
2482         });
2483     }
2484
2485     #[bench]
2486     fn char_iterator_ascii(b: &mut Bencher) {
2487         let s = "Mary had a little lamb, Little lamb
2488         Mary had a little lamb, Little lamb
2489         Mary had a little lamb, Little lamb
2490         Mary had a little lamb, Little lamb
2491         Mary had a little lamb, Little lamb
2492         Mary had a little lamb, Little lamb";
2493
2494         b.iter(|| s.chars().count());
2495     }
2496
2497     #[bench]
2498     fn char_iterator_rev(b: &mut Bencher) {
2499         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2500
2501         b.iter(|| s.chars().rev().count());
2502     }
2503
2504     #[bench]
2505     fn char_iterator_rev_for(b: &mut Bencher) {
2506         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2507
2508         b.iter(|| {
2509             for ch in s.chars().rev() { black_box(ch) }
2510         });
2511     }
2512
2513     #[bench]
2514     fn char_indicesator(b: &mut Bencher) {
2515         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2516         let len = s.char_len();
2517
2518         b.iter(|| assert_eq!(s.char_indices().count(), len));
2519     }
2520
2521     #[bench]
2522     fn char_indicesator_rev(b: &mut Bencher) {
2523         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2524         let len = s.char_len();
2525
2526         b.iter(|| assert_eq!(s.char_indices().rev().count(), len));
2527     }
2528
2529     #[bench]
2530     fn split_unicode_ascii(b: &mut Bencher) {
2531         let s = "ประเทศไทย中华Việt Namประเทศไทย中华Việt Nam";
2532
2533         b.iter(|| assert_eq!(s.split('V').count(), 3));
2534     }
2535
2536     #[bench]
2537     fn split_unicode_not_ascii(b: &mut Bencher) {
2538         struct NotAscii(char);
2539         impl CharEq for NotAscii {
2540             fn matches(&mut self, c: char) -> bool {
2541                 let NotAscii(cc) = *self;
2542                 cc == c
2543             }
2544             fn only_ascii(&self) -> bool { false }
2545         }
2546         let s = "ประเทศไทย中华Việt Namประเทศไทย中华Việt Nam";
2547
2548         b.iter(|| assert_eq!(s.split(NotAscii('V')).count(), 3));
2549     }
2550
2551
2552     #[bench]
2553     fn split_ascii(b: &mut Bencher) {
2554         let s = "Mary had a little lamb, Little lamb, little-lamb.";
2555         let len = s.split(' ').count();
2556
2557         b.iter(|| assert_eq!(s.split(' ').count(), len));
2558     }
2559
2560     #[bench]
2561     fn split_not_ascii(b: &mut Bencher) {
2562         struct NotAscii(char);
2563         impl CharEq for NotAscii {
2564             #[inline]
2565             fn matches(&mut self, c: char) -> bool {
2566                 let NotAscii(cc) = *self;
2567                 cc == c
2568             }
2569             fn only_ascii(&self) -> bool { false }
2570         }
2571         let s = "Mary had a little lamb, Little lamb, little-lamb.";
2572         let len = s.split(' ').count();
2573
2574         b.iter(|| assert_eq!(s.split(NotAscii(' ')).count(), len));
2575     }
2576
2577     #[bench]
2578     fn split_extern_fn(b: &mut Bencher) {
2579         let s = "Mary had a little lamb, Little lamb, little-lamb.";
2580         let len = s.split(' ').count();
2581         fn pred(c: char) -> bool { c == ' ' }
2582
2583         b.iter(|| assert_eq!(s.split(pred).count(), len));
2584     }
2585
2586     #[bench]
2587     fn split_closure(b: &mut Bencher) {
2588         let s = "Mary had a little lamb, Little lamb, little-lamb.";
2589         let len = s.split(' ').count();
2590
2591         b.iter(|| assert_eq!(s.split(|&: c: char| c == ' ').count(), len));
2592     }
2593
2594     #[bench]
2595     fn split_slice(b: &mut Bencher) {
2596         let s = "Mary had a little lamb, Little lamb, little-lamb.";
2597         let len = s.split(' ').count();
2598
2599         let c: &[char] = &[' '];
2600         b.iter(|| assert_eq!(s.split(c).count(), len));
2601     }
2602
2603     #[bench]
2604     fn is_utf8_100_ascii(b: &mut Bencher) {
2605
2606         let s = b"Hello there, the quick brown fox jumped over the lazy dog! \
2607                   Lorem ipsum dolor sit amet, consectetur. ";
2608
2609         assert_eq!(100, s.len());
2610         b.iter(|| {
2611             is_utf8(s)
2612         });
2613     }
2614
2615     #[bench]
2616     fn is_utf8_100_multibyte(b: &mut Bencher) {
2617         let s = "𐌀𐌖𐌋𐌄𐌑𐌉ปรدولة الكويتทศไทย中华𐍅𐌿𐌻𐍆𐌹𐌻𐌰".as_bytes();
2618         assert_eq!(100, s.len());
2619         b.iter(|| {
2620             is_utf8(s)
2621         });
2622     }
2623
2624     #[bench]
2625     fn bench_connect(b: &mut Bencher) {
2626         let s = "ศไทย中华Việt Nam; Mary had a little lamb, Little lamb";
2627         let sep = "→";
2628         let v = [s, s, s, s, s, s, s, s, s, s];
2629         b.iter(|| {
2630             assert_eq!(v.connect(sep).len(), s.len() * 10 + sep.len() * 9);
2631         })
2632     }
2633
2634     #[bench]
2635     fn bench_contains_short_short(b: &mut Bencher) {
2636         let haystack = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
2637         let needle = "sit";
2638
2639         b.iter(|| {
2640             assert!(haystack.contains(needle));
2641         })
2642     }
2643
2644     #[bench]
2645     fn bench_contains_short_long(b: &mut Bencher) {
2646         let haystack = "\
2647 Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse quis lorem sit amet dolor \
2648 ultricies condimentum. Praesent iaculis purus elit, ac malesuada quam malesuada in. Duis sed orci \
2649 eros. Suspendisse sit amet magna mollis, mollis nunc luctus, imperdiet mi. Integer fringilla non \
2650 sem ut lacinia. Fusce varius tortor a risus porttitor hendrerit. Morbi mauris dui, ultricies nec \
2651 tempus vel, gravida nec quam.
2652
2653 In est dui, tincidunt sed tempus interdum, adipiscing laoreet ante. Etiam tempor, tellus quis \
2654 sagittis interdum, nulla purus mattis sem, quis auctor erat odio ac tellus. In nec nunc sit amet \
2655 diam volutpat molestie at sed ipsum. Vestibulum laoreet consequat vulputate. Integer accumsan \
2656 lorem ac dignissim placerat. Suspendisse convallis faucibus lorem. Aliquam erat volutpat. In vel \
2657 eleifend felis. Sed suscipit nulla lorem, sed mollis est sollicitudin et. Nam fermentum egestas \
2658 interdum. Curabitur ut nisi justo.
2659
2660 Sed sollicitudin ipsum tellus, ut condimentum leo eleifend nec. Cras ut velit ante. Phasellus nec \
2661 mollis odio. Mauris molestie erat in arcu mattis, at aliquet dolor vehicula. Quisque malesuada \
2662 lectus sit amet nisi pretium, a condimentum ipsum porta. Morbi at dapibus diam. Praesent egestas \
2663 est sed risus elementum, eu rutrum metus ultrices. Etiam fermentum consectetur magna, id rutrum \
2664 felis accumsan a. Aliquam ut pellentesque libero. Sed mi nulla, lobortis eu tortor id, suscipit \
2665 ultricies neque. Morbi iaculis sit amet risus at iaculis. Praesent eget ligula quis turpis \
2666 feugiat suscipit vel non arcu. Interdum et malesuada fames ac ante ipsum primis in faucibus. \
2667 Aliquam sit amet placerat lorem.
2668
2669 Cras a lacus vel ante posuere elementum. Nunc est leo, bibendum ut facilisis vel, bibendum at \
2670 mauris. Nullam adipiscing diam vel odio ornare, luctus adipiscing mi luctus. Nulla facilisi. \
2671 Mauris adipiscing bibendum neque, quis adipiscing lectus tempus et. Sed feugiat erat et nisl \
2672 lobortis pharetra. Donec vitae erat enim. Nullam sit amet felis et quam lacinia tincidunt. Aliquam \
2673 suscipit dapibus urna. Sed volutpat urna in magna pulvinar volutpat. Phasellus nec tellus ac diam \
2674 cursus accumsan.
2675
2676 Nam lectus enim, dapibus non nisi tempor, consectetur convallis massa. Maecenas eleifend dictum \
2677 feugiat. Etiam quis mauris vel risus luctus mattis a a nunc. Nullam orci quam, imperdiet id \
2678 vehicula in, porttitor ut nibh. Duis sagittis adipiscing nisl vitae congue. Donec mollis risus eu \
2679 leo suscipit, varius porttitor nulla porta. Pellentesque ut sem nec nisi euismod vehicula. Nulla \
2680 malesuada sollicitudin quam eu fermentum.";
2681         let needle = "english";
2682
2683         b.iter(|| {
2684             assert!(!haystack.contains(needle));
2685         })
2686     }
2687
2688     #[bench]
2689     fn bench_contains_bad_naive(b: &mut Bencher) {
2690         let haystack = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
2691         let needle = "aaaaaaaab";
2692
2693         b.iter(|| {
2694             assert!(!haystack.contains(needle));
2695         })
2696     }
2697
2698     #[bench]
2699     fn bench_contains_equal(b: &mut Bencher) {
2700         let haystack = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
2701         let needle = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
2702
2703         b.iter(|| {
2704             assert!(haystack.contains(needle));
2705         })
2706     }
2707 }