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