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