src/libcore/str/mod.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 //! String manipulation
  12 //!
  13 //! For more details, see std::str
  14
  15 #![stable(feature = "rust1", since = "1.0.0")]
  16
  17 use self::pattern::Pattern;
  18 use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher};
  19
  20 use char;
  21 use fmt;
  22 use iter::{Map, Cloned, FusedIterator};
  23 use mem;
  24 use slice;
  25
  26 pub mod pattern;
  27
  28 /// A trait to abstract the idea of creating a new instance of a type from a
  29 /// string.
  30 ///
  31 /// `FromStr`'s [`from_str()`] method is often used implicitly, through
  32 /// [`str`]'s [`parse()`] method. See [`parse()`]'s documentation for examples.
  33 ///
  34 /// [`from_str()`]: #tymethod.from_str
  35 /// [`str`]: ../../std/primitive.str.html
  36 /// [`parse()`]: ../../std/primitive.str.html#method.parse
  37 #[stable(feature = "rust1", since = "1.0.0")]
  38 pub trait FromStr: Sized {
  39     /// The associated error which can be returned from parsing.
  40     #[stable(feature = "rust1", since = "1.0.0")]
  41     type Err;
  42
  43     /// Parses a string `s` to return a value of this type.
  44     ///
  45     /// If parsing succeeds, return the value inside `Ok`, otherwise
  46     /// when the string is ill-formatted return an error specific to the
  47     /// inside `Err`. The error type is specific to implementation of the trait.
  48     ///
  49     /// # Examples
  50     ///
  51     /// Basic usage with [`i32`][ithirtytwo], a type that implements `FromStr`:
  52     ///
  53     /// [ithirtytwo]: ../../std/primitive.i32.html
  54     ///
  55     /// ```
  56     /// use std::str::FromStr;
  57     ///
  58     /// let s = "5";
  59     /// let x = i32::from_str(s).unwrap();
  60     ///
  61     /// assert_eq!(5, x);
  62     /// ```
  63     #[stable(feature = "rust1", since = "1.0.0")]
  64     fn from_str(s: &str) -> Result<Self, Self::Err>;
  65 }
  66
  67 #[stable(feature = "rust1", since = "1.0.0")]
  68 impl FromStr for bool {
  69     type Err = ParseBoolError;
  70
  71     /// Parse a `bool` from a string.
  72     ///
  73     /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
  74     /// actually be parseable.
  75     ///
  76     /// # Examples
  77     ///
  78     /// ```
  79     /// use std::str::FromStr;
  80     ///
  81     /// assert_eq!(FromStr::from_str("true"), Ok(true));
  82     /// assert_eq!(FromStr::from_str("false"), Ok(false));
  83     /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
  84     /// ```
  85     ///
  86     /// Note, in many cases, the `.parse()` method on `str` is more proper.
  87     ///
  88     /// ```
  89     /// assert_eq!("true".parse(), Ok(true));
  90     /// assert_eq!("false".parse(), Ok(false));
  91     /// assert!("not even a boolean".parse::<bool>().is_err());
  92     /// ```
  93     #[inline]
  94     fn from_str(s: &str) -> Result<bool, ParseBoolError> {
  95         match s {
  96             "true"  => Ok(true),
  97             "false" => Ok(false),
  98             _       => Err(ParseBoolError { _priv: () }),
  99         }
 100     }
 101 }
 102
 103 /// An error returned when parsing a `bool` from a string fails.
 104 #[derive(Debug, Clone, PartialEq, Eq)]
 105 #[stable(feature = "rust1", since = "1.0.0")]
 106 pub struct ParseBoolError { _priv: () }
 107
 108 #[stable(feature = "rust1", since = "1.0.0")]
 109 impl fmt::Display for ParseBoolError {
 110     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 111         "provided string was not `true` or `false`".fmt(f)
 112     }
 113 }
 114
 115 /*
 116 Section: Creating a string
 117 */
 118
 119 /// Errors which can occur when attempting to interpret a sequence of `u8`
 120 /// as a string.
 121 ///
 122 /// As such, the `from_utf8` family of functions and methods for both `String`s
 123 /// and `&str`s make use of this error, for example.
 124 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
 125 #[stable(feature = "rust1", since = "1.0.0")]
 126 pub struct Utf8Error {
 127     valid_up_to: usize,
 128 }
 129
 130 impl Utf8Error {
 131     /// Returns the index in the given string up to which valid UTF-8 was
 132     /// verified.
 133     ///
 134     /// It is the maximum index such that `from_utf8(input[..index])`
 135     /// would return `Some(_)`.
 136     ///
 137     /// # Examples
 138     ///
 139     /// Basic usage:
 140     ///
 141     /// ```
 142     /// use std::str;
 143     ///
 144     /// // some invalid bytes, in a vector
 145     /// let sparkle_heart = vec![0, 159, 146, 150];
 146     ///
 147     /// // std::str::from_utf8 returns a Utf8Error
 148     /// let error = str::from_utf8(&sparkle_heart).unwrap_err();
 149     ///
 150     /// // the second byte is invalid here
 151     /// assert_eq!(1, error.valid_up_to());
 152     /// ```
 153     #[stable(feature = "utf8_error", since = "1.5.0")]
 154     pub fn valid_up_to(&self) -> usize { self.valid_up_to }
 155 }
 156
 157 /// Converts a slice of bytes to a string slice.
 158 ///
 159 /// A string slice (`&str`) is made of bytes (`u8`), and a byte slice (`&[u8]`)
 160 /// is made of bytes, so this function converts between the two. Not all byte
 161 /// slices are valid string slices, however: `&str` requires that it is valid
 162 /// UTF-8. `from_utf8()` checks to ensure that the bytes are valid UTF-8, and
 163 /// then does the conversion.
 164 ///
 165 /// If you are sure that the byte slice is valid UTF-8, and you don't want to
 166 /// incur the overhead of the validity check, there is an unsafe version of
 167 /// this function, [`from_utf8_unchecked()`][fromutf8u], which has the same
 168 /// behavior but skips the check.
 169 ///
 170 /// [fromutf8u]: fn.from_utf8_unchecked.html
 171 ///
 172 /// If you need a `String` instead of a `&str`, consider
 173 /// [`String::from_utf8()`][string].
 174 ///
 175 /// [string]: ../../std/string/struct.String.html#method.from_utf8
 176 ///
 177 /// Because you can stack-allocate a `[u8; N]`, and you can take a `&[u8]` of
 178 /// it, this function is one way to have a stack-allocated string. There is
 179 /// an example of this in the examples section below.
 180 ///
 181 /// # Errors
 182 ///
 183 /// Returns `Err` if the slice is not UTF-8 with a description as to why the
 184 /// provided slice is not UTF-8.
 185 ///
 186 /// # Examples
 187 ///
 188 /// Basic usage:
 189 ///
 190 /// ```
 191 /// use std::str;
 192 ///
 193 /// // some bytes, in a vector
 194 /// let sparkle_heart = vec![240, 159, 146, 150];
 195 ///
 196 /// // We know these bytes are valid, so just use `unwrap()`.
 197 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 198 ///
 199 /// assert_eq!("💖", sparkle_heart);
 200 /// ```
 201 ///
 202 /// Incorrect bytes:
 203 ///
 204 /// ```
 205 /// use std::str;
 206 ///
 207 /// // some invalid bytes, in a vector
 208 /// let sparkle_heart = vec![0, 159, 146, 150];
 209 ///
 210 /// assert!(str::from_utf8(&sparkle_heart).is_err());
 211 /// ```
 212 ///
 213 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 214 /// errors that can be returned.
 215 ///
 216 /// [error]: struct.Utf8Error.html
 217 ///
 218 /// A "stack allocated string":
 219 ///
 220 /// ```
 221 /// use std::str;
 222 ///
 223 /// // some bytes, in a stack-allocated array
 224 /// let sparkle_heart = [240, 159, 146, 150];
 225 ///
 226 /// // We know these bytes are valid, so just use `unwrap()`.
 227 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 228 ///
 229 /// assert_eq!("💖", sparkle_heart);
 230 /// ```
 231 #[stable(feature = "rust1", since = "1.0.0")]
 232 pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
 233     run_utf8_validation(v)?;
 234     Ok(unsafe { from_utf8_unchecked(v) })
 235 }
 236
 237 /// Forms a str from a pointer and a length.
 238 ///
 239 /// The `len` argument is the number of bytes in the string.
 240 ///
 241 /// # Safety
 242 ///
 243 /// This function is unsafe as there is no guarantee that the given pointer is
 244 /// valid for `len` bytes, nor whether the lifetime inferred is a suitable
 245 /// lifetime for the returned str.
 246 ///
 247 /// The data must be valid UTF-8
 248 ///
 249 /// `p` must be non-null, even for zero-length str.
 250 ///
 251 /// # Caveat
 252 ///
 253 /// The lifetime for the returned str is inferred from its usage. To
 254 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
 255 /// source lifetime is safe in the context, such as by providing a helper
 256 /// function taking the lifetime of a host value for the str, or by explicit
 257 /// annotation.
 258 /// Performs the same functionality as `from_raw_parts`, except that a mutable
 259 /// str is returned.
 260 ///
 261 unsafe fn from_raw_parts_mut<'a>(p: *mut u8, len: usize) -> &'a mut str {
 262     mem::transmute::<&mut [u8], &mut str>(slice::from_raw_parts_mut(p, len))
 263 }
 264
 265 /// Converts a slice of bytes to a string slice without checking
 266 /// that the string contains valid UTF-8.
 267 ///
 268 /// See the safe version, [`from_utf8()`][fromutf8], for more information.
 269 ///
 270 /// [fromutf8]: fn.from_utf8.html
 271 ///
 272 /// # Safety
 273 ///
 274 /// This function is unsafe because it does not check that the bytes passed to
 275 /// it are valid UTF-8. If this constraint is violated, undefined behavior
 276 /// results, as the rest of Rust assumes that `&str`s are valid UTF-8.
 277 ///
 278 /// # Examples
 279 ///
 280 /// Basic usage:
 281 ///
 282 /// ```
 283 /// use std::str;
 284 ///
 285 /// // some bytes, in a vector
 286 /// let sparkle_heart = vec![240, 159, 146, 150];
 287 ///
 288 /// let sparkle_heart = unsafe {
 289 ///     str::from_utf8_unchecked(&sparkle_heart)
 290 /// };
 291 ///
 292 /// assert_eq!("💖", sparkle_heart);
 293 /// ```
 294 #[inline(always)]
 295 #[stable(feature = "rust1", since = "1.0.0")]
 296 pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
 297     mem::transmute(v)
 298 }
 299
 300 #[stable(feature = "rust1", since = "1.0.0")]
 301 impl fmt::Display for Utf8Error {
 302     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 303         write!(f, "invalid utf-8: invalid byte near index {}", self.valid_up_to)
 304     }
 305 }
 306
 307 /*
 308 Section: Iterators
 309 */
 310
 311 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
 312 ///
 313 /// Created with the method [`chars()`].
 314 ///
 315 /// [`chars()`]: ../../std/primitive.str.html#method.chars
 316 #[derive(Clone, Debug)]
 317 #[stable(feature = "rust1", since = "1.0.0")]
 318 pub struct Chars<'a> {
 319     iter: slice::Iter<'a, u8>
 320 }
 321
 322 /// Return the initial codepoint accumulator for the first byte.
 323 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
 324 /// for width 3, and 3 bits for width 4.
 325 #[inline]
 326 fn utf8_first_byte(byte: u8, width: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
 327
 328 /// Return the value of `ch` updated with continuation byte `byte`.
 329 #[inline]
 330 fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
 331
 332 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
 333 /// bits `10`).
 334 #[inline]
 335 fn utf8_is_cont_byte(byte: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
 336
 337 #[inline]
 338 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 339     match opt {
 340         Some(&byte) => byte,
 341         None => 0,
 342     }
 343 }
 344
 345 /// Reads the next code point out of a byte iterator (assuming a
 346 /// UTF-8-like encoding).
 347 #[unstable(feature = "str_internals", issue = "0")]
 348 #[inline]
 349 pub fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
 350     // Decode UTF-8
 351     let x = match bytes.next() {
 352         None => return None,
 353         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 354         Some(&next_byte) => next_byte,
 355     };
 356
 357     // Multibyte case follows
 358     // Decode from a byte combination out of: [[[x y] z] w]
 359     // NOTE: Performance is sensitive to the exact formulation here
 360     let init = utf8_first_byte(x, 2);
 361     let y = unwrap_or_0(bytes.next());
 362     let mut ch = utf8_acc_cont_byte(init, y);
 363     if x >= 0xE0 {
 364         // [[x y z] w] case
 365         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 366         let z = unwrap_or_0(bytes.next());
 367         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
 368         ch = init << 12 | y_z;
 369         if x >= 0xF0 {
 370             // [x y z w] case
 371             // use only the lower 3 bits of `init`
 372             let w = unwrap_or_0(bytes.next());
 373             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
 374         }
 375     }
 376
 377     Some(ch)
 378 }
 379
 380 /// Reads the last code point out of a byte iterator (assuming a
 381 /// UTF-8-like encoding).
 382 #[inline]
 383 fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
 384     where I: DoubleEndedIterator<Item = &'a u8>,
 385 {
 386     // Decode UTF-8
 387     let w = match bytes.next_back() {
 388         None => return None,
 389         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 390         Some(&back_byte) => back_byte,
 391     };
 392
 393     // Multibyte case follows
 394     // Decode from a byte combination out of: [x [y [z w]]]
 395     let mut ch;
 396     let z = unwrap_or_0(bytes.next_back());
 397     ch = utf8_first_byte(z, 2);
 398     if utf8_is_cont_byte(z) {
 399         let y = unwrap_or_0(bytes.next_back());
 400         ch = utf8_first_byte(y, 3);
 401         if utf8_is_cont_byte(y) {
 402             let x = unwrap_or_0(bytes.next_back());
 403             ch = utf8_first_byte(x, 4);
 404             ch = utf8_acc_cont_byte(ch, y);
 405         }
 406         ch = utf8_acc_cont_byte(ch, z);
 407     }
 408     ch = utf8_acc_cont_byte(ch, w);
 409
 410     Some(ch)
 411 }
 412
 413 #[stable(feature = "rust1", since = "1.0.0")]
 414 impl<'a> Iterator for Chars<'a> {
 415     type Item = char;
 416
 417     #[inline]
 418     fn next(&mut self) -> Option<char> {
 419         next_code_point(&mut self.iter).map(|ch| {
 420             // str invariant says `ch` is a valid Unicode Scalar Value
 421             unsafe {
 422                 char::from_u32_unchecked(ch)
 423             }
 424         })
 425     }
 426
 427     #[inline]
 428     fn size_hint(&self) -> (usize, Option<usize>) {
 429         let len = self.iter.len();
 430         // `(len + 3)` can't overflow, because we know that the `slice::Iter`
 431         // belongs to a slice in memory which has a maximum length of
 432         // `isize::MAX` (that's well below `usize::MAX`).
 433         ((len + 3) / 4, Some(len))
 434     }
 435 }
 436
 437 #[stable(feature = "rust1", since = "1.0.0")]
 438 impl<'a> DoubleEndedIterator for Chars<'a> {
 439     #[inline]
 440     fn next_back(&mut self) -> Option<char> {
 441         next_code_point_reverse(&mut self.iter).map(|ch| {
 442             // str invariant says `ch` is a valid Unicode Scalar Value
 443             unsafe {
 444                 char::from_u32_unchecked(ch)
 445             }
 446         })
 447     }
 448 }
 449
 450 #[unstable(feature = "fused", issue = "35602")]
 451 impl<'a> FusedIterator for Chars<'a> {}
 452
 453 impl<'a> Chars<'a> {
 454     /// View the underlying data as a subslice of the original data.
 455     ///
 456     /// This has the same lifetime as the original slice, and so the
 457     /// iterator can continue to be used while this exists.
 458     ///
 459     /// # Examples
 460     ///
 461     /// ```
 462     /// let mut chars = "abc".chars();
 463     ///
 464     /// assert_eq!(chars.as_str(), "abc");
 465     /// chars.next();
 466     /// assert_eq!(chars.as_str(), "bc");
 467     /// chars.next();
 468     /// chars.next();
 469     /// assert_eq!(chars.as_str(), "");
 470     /// ```
 471     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 472     #[inline]
 473     pub fn as_str(&self) -> &'a str {
 474         unsafe { from_utf8_unchecked(self.iter.as_slice()) }
 475     }
 476 }
 477
 478 /// Iterator for a string's characters and their byte offsets.
 479 #[derive(Clone, Debug)]
 480 #[stable(feature = "rust1", since = "1.0.0")]
 481 pub struct CharIndices<'a> {
 482     front_offset: usize,
 483     iter: Chars<'a>,
 484 }
 485
 486 #[stable(feature = "rust1", since = "1.0.0")]
 487 impl<'a> Iterator for CharIndices<'a> {
 488     type Item = (usize, char);
 489
 490     #[inline]
 491     fn next(&mut self) -> Option<(usize, char)> {
 492         let pre_len = self.iter.iter.len();
 493         match self.iter.next() {
 494             None => None,
 495             Some(ch) => {
 496                 let index = self.front_offset;
 497                 let len = self.iter.iter.len();
 498                 self.front_offset += pre_len - len;
 499                 Some((index, ch))
 500             }
 501         }
 502     }
 503
 504     #[inline]
 505     fn size_hint(&self) -> (usize, Option<usize>) {
 506         self.iter.size_hint()
 507     }
 508 }
 509
 510 #[stable(feature = "rust1", since = "1.0.0")]
 511 impl<'a> DoubleEndedIterator for CharIndices<'a> {
 512     #[inline]
 513     fn next_back(&mut self) -> Option<(usize, char)> {
 514         match self.iter.next_back() {
 515             None => None,
 516             Some(ch) => {
 517                 let index = self.front_offset + self.iter.iter.len();
 518                 Some((index, ch))
 519             }
 520         }
 521     }
 522 }
 523
 524 #[unstable(feature = "fused", issue = "35602")]
 525 impl<'a> FusedIterator for CharIndices<'a> {}
 526
 527 impl<'a> CharIndices<'a> {
 528     /// View the underlying data as a subslice of the original data.
 529     ///
 530     /// This has the same lifetime as the original slice, and so the
 531     /// iterator can continue to be used while this exists.
 532     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 533     #[inline]
 534     pub fn as_str(&self) -> &'a str {
 535         self.iter.as_str()
 536     }
 537 }
 538
 539 /// External iterator for a string's bytes.
 540 /// Use with the `std::iter` module.
 541 ///
 542 /// Created with the method [`bytes()`].
 543 ///
 544 /// [`bytes()`]: ../../std/primitive.str.html#method.bytes
 545 #[stable(feature = "rust1", since = "1.0.0")]
 546 #[derive(Clone, Debug)]
 547 pub struct Bytes<'a>(Cloned<slice::Iter<'a, u8>>);
 548
 549 #[stable(feature = "rust1", since = "1.0.0")]
 550 impl<'a> Iterator for Bytes<'a> {
 551     type Item = u8;
 552
 553     #[inline]
 554     fn next(&mut self) -> Option<u8> {
 555         self.0.next()
 556     }
 557
 558     #[inline]
 559     fn size_hint(&self) -> (usize, Option<usize>) {
 560         self.0.size_hint()
 561     }
 562
 563     #[inline]
 564     fn count(self) -> usize {
 565         self.0.count()
 566     }
 567
 568     #[inline]
 569     fn last(self) -> Option<Self::Item> {
 570         self.0.last()
 571     }
 572
 573     #[inline]
 574     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 575         self.0.nth(n)
 576     }
 577 }
 578
 579 #[stable(feature = "rust1", since = "1.0.0")]
 580 impl<'a> DoubleEndedIterator for Bytes<'a> {
 581     #[inline]
 582     fn next_back(&mut self) -> Option<u8> {
 583         self.0.next_back()
 584     }
 585 }
 586
 587 #[stable(feature = "rust1", since = "1.0.0")]
 588 impl<'a> ExactSizeIterator for Bytes<'a> {
 589     #[inline]
 590     fn len(&self) -> usize {
 591         self.0.len()
 592     }
 593 }
 594
 595 #[unstable(feature = "fused", issue = "35602")]
 596 impl<'a> FusedIterator for Bytes<'a> {}
 597
 598 /// This macro generates a Clone impl for string pattern API
 599 /// wrapper types of the form X<'a, P>
 600 macro_rules! derive_pattern_clone {
 601     (clone $t:ident with |$s:ident| $e:expr) => {
 602         impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
 603             where P::Searcher: Clone
 604         {
 605             fn clone(&self) -> Self {
 606                 let $s = self;
 607                 $e
 608             }
 609         }
 610     }
 611 }
 612
 613 /// This macro generates two public iterator structs
 614 /// wrapping a private internal one that makes use of the `Pattern` API.
 615 ///
 616 /// For all patterns `P: Pattern<'a>` the following items will be
 617 /// generated (generics omitted):
 618 ///
 619 /// struct $forward_iterator($internal_iterator);
 620 /// struct $reverse_iterator($internal_iterator);
 621 ///
 622 /// impl Iterator for $forward_iterator
 623 /// { /* internal ends up calling Searcher::next_match() */ }
 624 ///
 625 /// impl DoubleEndedIterator for $forward_iterator
 626 ///       where P::Searcher: DoubleEndedSearcher
 627 /// { /* internal ends up calling Searcher::next_match_back() */ }
 628 ///
 629 /// impl Iterator for $reverse_iterator
 630 ///       where P::Searcher: ReverseSearcher
 631 /// { /* internal ends up calling Searcher::next_match_back() */ }
 632 ///
 633 /// impl DoubleEndedIterator for $reverse_iterator
 634 ///       where P::Searcher: DoubleEndedSearcher
 635 /// { /* internal ends up calling Searcher::next_match() */ }
 636 ///
 637 /// The internal one is defined outside the macro, and has almost the same
 638 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
 639 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
 640 ///
 641 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
 642 /// `Pattern` might not return the same elements, so actually implementing
 643 /// `DoubleEndedIterator` for it would be incorrect.
 644 /// (See the docs in `str::pattern` for more details)
 645 ///
 646 /// However, the internal struct still represents a single ended iterator from
 647 /// either end, and depending on pattern is also a valid double ended iterator,
 648 /// so the two wrapper structs implement `Iterator`
 649 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
 650 /// to the complex impls seen above.
 651 macro_rules! generate_pattern_iterators {
 652     {
 653         // Forward iterator
 654         forward:
 655             $(#[$forward_iterator_attribute:meta])*
 656             struct $forward_iterator:ident;
 657
 658         // Reverse iterator
 659         reverse:
 660             $(#[$reverse_iterator_attribute:meta])*
 661             struct $reverse_iterator:ident;
 662
 663         // Stability of all generated items
 664         stability:
 665             $(#[$common_stability_attribute:meta])*
 666
 667         // Internal almost-iterator that is being delegated to
 668         internal:
 669             $internal_iterator:ident yielding ($iterty:ty);
 670
 671         // Kind of delgation - either single ended or double ended
 672         delegate $($t:tt)*
 673     } => {
 674         $(#[$forward_iterator_attribute])*
 675         $(#[$common_stability_attribute])*
 676         pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 677
 678         $(#[$common_stability_attribute])*
 679         impl<'a, P: Pattern<'a>> fmt::Debug for $forward_iterator<'a, P>
 680             where P::Searcher: fmt::Debug
 681         {
 682             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 683                 f.debug_tuple(stringify!($forward_iterator))
 684                     .field(&self.0)
 685                     .finish()
 686             }
 687         }
 688
 689         $(#[$common_stability_attribute])*
 690         impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
 691             type Item = $iterty;
 692
 693             #[inline]
 694             fn next(&mut self) -> Option<$iterty> {
 695                 self.0.next()
 696             }
 697         }
 698
 699         $(#[$common_stability_attribute])*
 700         impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
 701             where P::Searcher: Clone
 702         {
 703             fn clone(&self) -> Self {
 704                 $forward_iterator(self.0.clone())
 705             }
 706         }
 707
 708         $(#[$reverse_iterator_attribute])*
 709         $(#[$common_stability_attribute])*
 710         pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 711
 712         $(#[$common_stability_attribute])*
 713         impl<'a, P: Pattern<'a>> fmt::Debug for $reverse_iterator<'a, P>
 714             where P::Searcher: fmt::Debug
 715         {
 716             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 717                 f.debug_tuple(stringify!($reverse_iterator))
 718                     .field(&self.0)
 719                     .finish()
 720             }
 721         }
 722
 723         $(#[$common_stability_attribute])*
 724         impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
 725             where P::Searcher: ReverseSearcher<'a>
 726         {
 727             type Item = $iterty;
 728
 729             #[inline]
 730             fn next(&mut self) -> Option<$iterty> {
 731                 self.0.next_back()
 732             }
 733         }
 734
 735         $(#[$common_stability_attribute])*
 736         impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
 737             where P::Searcher: Clone
 738         {
 739             fn clone(&self) -> Self {
 740                 $reverse_iterator(self.0.clone())
 741             }
 742         }
 743
 744         #[unstable(feature = "fused", issue = "35602")]
 745         impl<'a, P: Pattern<'a>> FusedIterator for $forward_iterator<'a, P> {}
 746
 747         #[unstable(feature = "fused", issue = "35602")]
 748         impl<'a, P: Pattern<'a>> FusedIterator for $reverse_iterator<'a, P>
 749             where P::Searcher: ReverseSearcher<'a> {}
 750
 751         generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
 752                                                 $forward_iterator,
 753                                                 $reverse_iterator, $iterty);
 754     };
 755     {
 756         double ended; with $(#[$common_stability_attribute:meta])*,
 757                            $forward_iterator:ident,
 758                            $reverse_iterator:ident, $iterty:ty
 759     } => {
 760         $(#[$common_stability_attribute])*
 761         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
 762             where P::Searcher: DoubleEndedSearcher<'a>
 763         {
 764             #[inline]
 765             fn next_back(&mut self) -> Option<$iterty> {
 766                 self.0.next_back()
 767             }
 768         }
 769
 770         $(#[$common_stability_attribute])*
 771         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
 772             where P::Searcher: DoubleEndedSearcher<'a>
 773         {
 774             #[inline]
 775             fn next_back(&mut self) -> Option<$iterty> {
 776                 self.0.next()
 777             }
 778         }
 779     };
 780     {
 781         single ended; with $(#[$common_stability_attribute:meta])*,
 782                            $forward_iterator:ident,
 783                            $reverse_iterator:ident, $iterty:ty
 784     } => {}
 785 }
 786
 787 derive_pattern_clone!{
 788     clone SplitInternal
 789     with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
 790 }
 791
 792 struct SplitInternal<'a, P: Pattern<'a>> {
 793     start: usize,
 794     end: usize,
 795     matcher: P::Searcher,
 796     allow_trailing_empty: bool,
 797     finished: bool,
 798 }
 799
 800 impl<'a, P: Pattern<'a>> fmt::Debug for SplitInternal<'a, P> where P::Searcher: fmt::Debug {
 801     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 802         f.debug_struct("SplitInternal")
 803             .field("start", &self.start)
 804             .field("end", &self.end)
 805             .field("matcher", &self.matcher)
 806             .field("allow_trailing_empty", &self.allow_trailing_empty)
 807             .field("finished", &self.finished)
 808             .finish()
 809     }
 810 }
 811
 812 impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
 813     #[inline]
 814     fn get_end(&mut self) -> Option<&'a str> {
 815         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
 816             self.finished = true;
 817             unsafe {
 818                 let string = self.matcher.haystack().slice_unchecked(self.start, self.end);
 819                 Some(string)
 820             }
 821         } else {
 822             None
 823         }
 824     }
 825
 826     #[inline]
 827     fn next(&mut self) -> Option<&'a str> {
 828         if self.finished { return None }
 829
 830         let haystack = self.matcher.haystack();
 831         match self.matcher.next_match() {
 832             Some((a, b)) => unsafe {
 833                 let elt = haystack.slice_unchecked(self.start, a);
 834                 self.start = b;
 835                 Some(elt)
 836             },
 837             None => self.get_end(),
 838         }
 839     }
 840
 841     #[inline]
 842     fn next_back(&mut self) -> Option<&'a str>
 843         where P::Searcher: ReverseSearcher<'a>
 844     {
 845         if self.finished { return None }
 846
 847         if !self.allow_trailing_empty {
 848             self.allow_trailing_empty = true;
 849             match self.next_back() {
 850                 Some(elt) if !elt.is_empty() => return Some(elt),
 851                 _ => if self.finished { return None }
 852             }
 853         }
 854
 855         let haystack = self.matcher.haystack();
 856         match self.matcher.next_match_back() {
 857             Some((a, b)) => unsafe {
 858                 let elt = haystack.slice_unchecked(b, self.end);
 859                 self.end = a;
 860                 Some(elt)
 861             },
 862             None => unsafe {
 863                 self.finished = true;
 864                 Some(haystack.slice_unchecked(self.start, self.end))
 865             },
 866         }
 867     }
 868 }
 869
 870 generate_pattern_iterators! {
 871     forward:
 872         /// Created with the method [`split()`].
 873         ///
 874         /// [`split()`]: ../../std/primitive.str.html#method.split
 875         struct Split;
 876     reverse:
 877         /// Created with the method [`rsplit()`].
 878         ///
 879         /// [`rsplit()`]: ../../std/primitive.str.html#method.rsplit
 880         struct RSplit;
 881     stability:
 882         #[stable(feature = "rust1", since = "1.0.0")]
 883     internal:
 884         SplitInternal yielding (&'a str);
 885     delegate double ended;
 886 }
 887
 888 generate_pattern_iterators! {
 889     forward:
 890         /// Created with the method [`split_terminator()`].
 891         ///
 892         /// [`split_terminator()`]: ../../std/primitive.str.html#method.split_terminator
 893         struct SplitTerminator;
 894     reverse:
 895         /// Created with the method [`rsplit_terminator()`].
 896         ///
 897         /// [`rsplit_terminator()`]: ../../std/primitive.str.html#method.rsplit_terminator
 898         struct RSplitTerminator;
 899     stability:
 900         #[stable(feature = "rust1", since = "1.0.0")]
 901     internal:
 902         SplitInternal yielding (&'a str);
 903     delegate double ended;
 904 }
 905
 906 derive_pattern_clone!{
 907     clone SplitNInternal
 908     with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
 909 }
 910
 911 struct SplitNInternal<'a, P: Pattern<'a>> {
 912     iter: SplitInternal<'a, P>,
 913     /// The number of splits remaining
 914     count: usize,
 915 }
 916
 917 impl<'a, P: Pattern<'a>> fmt::Debug for SplitNInternal<'a, P> where P::Searcher: fmt::Debug {
 918     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 919         f.debug_struct("SplitNInternal")
 920             .field("iter", &self.iter)
 921             .field("count", &self.count)
 922             .finish()
 923     }
 924 }
 925
 926 impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
 927     #[inline]
 928     fn next(&mut self) -> Option<&'a str> {
 929         match self.count {
 930             0 => None,
 931             1 => { self.count = 0; self.iter.get_end() }
 932             _ => { self.count -= 1; self.iter.next() }
 933         }
 934     }
 935
 936     #[inline]
 937     fn next_back(&mut self) -> Option<&'a str>
 938         where P::Searcher: ReverseSearcher<'a>
 939     {
 940         match self.count {
 941             0 => None,
 942             1 => { self.count = 0; self.iter.get_end() }
 943             _ => { self.count -= 1; self.iter.next_back() }
 944         }
 945     }
 946 }
 947
 948 generate_pattern_iterators! {
 949     forward:
 950         /// Created with the method [`splitn()`].
 951         ///
 952         /// [`splitn()`]: ../../std/primitive.str.html#method.splitn
 953         struct SplitN;
 954     reverse:
 955         /// Created with the method [`rsplitn()`].
 956         ///
 957         /// [`rsplitn()`]: ../../std/primitive.str.html#method.rsplitn
 958         struct RSplitN;
 959     stability:
 960         #[stable(feature = "rust1", since = "1.0.0")]
 961     internal:
 962         SplitNInternal yielding (&'a str);
 963     delegate single ended;
 964 }
 965
 966 derive_pattern_clone!{
 967     clone MatchIndicesInternal
 968     with |s| MatchIndicesInternal(s.0.clone())
 969 }
 970
 971 struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
 972
 973 impl<'a, P: Pattern<'a>> fmt::Debug for MatchIndicesInternal<'a, P> where P::Searcher: fmt::Debug {
 974     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 975         f.debug_tuple("MatchIndicesInternal")
 976             .field(&self.0)
 977             .finish()
 978     }
 979 }
 980
 981 impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
 982     #[inline]
 983     fn next(&mut self) -> Option<(usize, &'a str)> {
 984         self.0.next_match().map(|(start, end)| unsafe {
 985             (start, self.0.haystack().slice_unchecked(start, end))
 986         })
 987     }
 988
 989     #[inline]
 990     fn next_back(&mut self) -> Option<(usize, &'a str)>
 991         where P::Searcher: ReverseSearcher<'a>
 992     {
 993         self.0.next_match_back().map(|(start, end)| unsafe {
 994             (start, self.0.haystack().slice_unchecked(start, end))
 995         })
 996     }
 997 }
 998
 999 generate_pattern_iterators! {
1000     forward:
1001         /// Created with the method [`match_indices()`].
1002         ///
1003         /// [`match_indices()`]: ../../std/primitive.str.html#method.match_indices
1004         struct MatchIndices;
1005     reverse:
1006         /// Created with the method [`rmatch_indices()`].
1007         ///
1008         /// [`rmatch_indices()`]: ../../std/primitive.str.html#method.rmatch_indices
1009         struct RMatchIndices;
1010     stability:
1011         #[stable(feature = "str_match_indices", since = "1.5.0")]
1012     internal:
1013         MatchIndicesInternal yielding ((usize, &'a str));
1014     delegate double ended;
1015 }
1016
1017 derive_pattern_clone!{
1018     clone MatchesInternal
1019     with |s| MatchesInternal(s.0.clone())
1020 }
1021
1022 struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
1023
1024 impl<'a, P: Pattern<'a>> fmt::Debug for MatchesInternal<'a, P> where P::Searcher: fmt::Debug {
1025     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1026         f.debug_tuple("MatchesInternal")
1027             .field(&self.0)
1028             .finish()
1029     }
1030 }
1031
1032 impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
1033     #[inline]
1034     fn next(&mut self) -> Option<&'a str> {
1035         self.0.next_match().map(|(a, b)| unsafe {
1036             // Indices are known to be on utf8 boundaries
1037             self.0.haystack().slice_unchecked(a, b)
1038         })
1039     }
1040
1041     #[inline]
1042     fn next_back(&mut self) -> Option<&'a str>
1043         where P::Searcher: ReverseSearcher<'a>
1044     {
1045         self.0.next_match_back().map(|(a, b)| unsafe {
1046             // Indices are known to be on utf8 boundaries
1047             self.0.haystack().slice_unchecked(a, b)
1048         })
1049     }
1050 }
1051
1052 generate_pattern_iterators! {
1053     forward:
1054         /// Created with the method [`matches()`].
1055         ///
1056         /// [`matches()`]: ../../std/primitive.str.html#method.matches
1057         struct Matches;
1058     reverse:
1059         /// Created with the method [`rmatches()`].
1060         ///
1061         /// [`rmatches()`]: ../../std/primitive.str.html#method.rmatches
1062         struct RMatches;
1063     stability:
1064         #[stable(feature = "str_matches", since = "1.2.0")]
1065     internal:
1066         MatchesInternal yielding (&'a str);
1067     delegate double ended;
1068 }
1069
1070 /// Created with the method [`lines()`].
1071 ///
1072 /// [`lines()`]: ../../std/primitive.str.html#method.lines
1073 #[stable(feature = "rust1", since = "1.0.0")]
1074 #[derive(Clone, Debug)]
1075 pub struct Lines<'a>(Map<SplitTerminator<'a, char>, LinesAnyMap>);
1076
1077 #[stable(feature = "rust1", since = "1.0.0")]
1078 impl<'a> Iterator for Lines<'a> {
1079     type Item = &'a str;
1080
1081     #[inline]
1082     fn next(&mut self) -> Option<&'a str> {
1083         self.0.next()
1084     }
1085
1086     #[inline]
1087     fn size_hint(&self) -> (usize, Option<usize>) {
1088         self.0.size_hint()
1089     }
1090 }
1091
1092 #[stable(feature = "rust1", since = "1.0.0")]
1093 impl<'a> DoubleEndedIterator for Lines<'a> {
1094     #[inline]
1095     fn next_back(&mut self) -> Option<&'a str> {
1096         self.0.next_back()
1097     }
1098 }
1099
1100 #[unstable(feature = "fused", issue = "35602")]
1101 impl<'a> FusedIterator for Lines<'a> {}
1102
1103 /// Created with the method [`lines_any()`].
1104 ///
1105 /// [`lines_any()`]: ../../std/primitive.str.html#method.lines_any
1106 #[stable(feature = "rust1", since = "1.0.0")]
1107 #[rustc_deprecated(since = "1.4.0", reason = "use lines()/Lines instead now")]
1108 #[derive(Clone, Debug)]
1109 #[allow(deprecated)]
1110 pub struct LinesAny<'a>(Lines<'a>);
1111
1112 /// A nameable, cloneable fn type
1113 #[derive(Clone)]
1114 struct LinesAnyMap;
1115
1116 impl<'a> Fn<(&'a str,)> for LinesAnyMap {
1117     #[inline]
1118     extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
1119         let l = line.len();
1120         if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
1121         else { line }
1122     }
1123 }
1124
1125 impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
1126     #[inline]
1127     extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
1128         Fn::call(&*self, (line,))
1129     }
1130 }
1131
1132 impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
1133     type Output = &'a str;
1134
1135     #[inline]
1136     extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
1137         Fn::call(&self, (line,))
1138     }
1139 }
1140
1141 #[stable(feature = "rust1", since = "1.0.0")]
1142 #[allow(deprecated)]
1143 impl<'a> Iterator for LinesAny<'a> {
1144     type Item = &'a str;
1145
1146     #[inline]
1147     fn next(&mut self) -> Option<&'a str> {
1148         self.0.next()
1149     }
1150
1151     #[inline]
1152     fn size_hint(&self) -> (usize, Option<usize>) {
1153         self.0.size_hint()
1154     }
1155 }
1156
1157 #[stable(feature = "rust1", since = "1.0.0")]
1158 #[allow(deprecated)]
1159 impl<'a> DoubleEndedIterator for LinesAny<'a> {
1160     #[inline]
1161     fn next_back(&mut self) -> Option<&'a str> {
1162         self.0.next_back()
1163     }
1164 }
1165
1166 #[unstable(feature = "fused", issue = "35602")]
1167 #[allow(deprecated)]
1168 impl<'a> FusedIterator for LinesAny<'a> {}
1169
1170 /*
1171 Section: Comparing strings
1172 */
1173
1174 /// Bytewise slice equality
1175 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
1176 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
1177 #[lang = "str_eq"]
1178 #[inline]
1179 fn eq_slice(a: &str, b: &str) -> bool {
1180     a.as_bytes() == b.as_bytes()
1181 }
1182
1183 /*
1184 Section: UTF-8 validation
1185 */
1186
1187 // use truncation to fit u64 into usize
1188 const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;
1189
1190 /// Return `true` if any byte in the word `x` is nonascii (>= 128).
1191 #[inline]
1192 fn contains_nonascii(x: usize) -> bool {
1193     (x & NONASCII_MASK) != 0
1194 }
1195
1196 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
1197 /// returning `true` in that case, or, if it is invalid, `false` with
1198 /// `iter` reset such that it is pointing at the first byte in the
1199 /// invalid sequence.
1200 #[inline(always)]
1201 fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
1202     let mut offset = 0;
1203     let len = v.len();
1204     while offset < len {
1205         let old_offset = offset;
1206         macro_rules! err { () => {{
1207             return Err(Utf8Error {
1208                 valid_up_to: old_offset
1209             })
1210         }}}
1211
1212         macro_rules! next { () => {{
1213             offset += 1;
1214             // we needed data, but there was none: error!
1215             if offset >= len {
1216                 err!()
1217             }
1218             v[offset]
1219         }}}
1220
1221         let first = v[offset];
1222         if first >= 128 {
1223             let w = UTF8_CHAR_WIDTH[first as usize];
1224             let second = next!();
1225             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
1226             //        first  C2 80        last DF BF
1227             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
1228             //        first  E0 A0 80     last EF BF BF
1229             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
1230             //               ED A0 80 to       ED BF BF
1231             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1232             //        first  F0 90 80 80  last F4 8F BF BF
1233             //
1234             // Use the UTF-8 syntax from the RFC
1235             //
1236             // https://tools.ietf.org/html/rfc3629
1237             // UTF8-1      = %x00-7F
1238             // UTF8-2      = %xC2-DF UTF8-tail
1239             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1240             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1241             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1242             //               %xF4 %x80-8F 2( UTF8-tail )
1243             match w {
1244                 2 => if second & !CONT_MASK != TAG_CONT_U8 {err!()},
1245                 3 => {
1246                     match (first, second, next!() & !CONT_MASK) {
1247                         (0xE0         , 0xA0 ... 0xBF, TAG_CONT_U8) |
1248                         (0xE1 ... 0xEC, 0x80 ... 0xBF, TAG_CONT_U8) |
1249                         (0xED         , 0x80 ... 0x9F, TAG_CONT_U8) |
1250                         (0xEE ... 0xEF, 0x80 ... 0xBF, TAG_CONT_U8) => {}
1251                         _ => err!()
1252                     }
1253                 }
1254                 4 => {
1255                     match (first, second, next!() & !CONT_MASK, next!() & !CONT_MASK) {
1256                         (0xF0         , 0x90 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
1257                         (0xF1 ... 0xF3, 0x80 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
1258                         (0xF4         , 0x80 ... 0x8F, TAG_CONT_U8, TAG_CONT_U8) => {}
1259                         _ => err!()
1260                     }
1261                 }
1262                 _ => err!()
1263             }
1264             offset += 1;
1265         } else {
1266             // Ascii case, try to skip forward quickly.
1267             // When the pointer is aligned, read 2 words of data per iteration
1268             // until we find a word containing a non-ascii byte.
1269             let usize_bytes = mem::size_of::<usize>();
1270             let bytes_per_iteration = 2 * usize_bytes;
1271             let ptr = v.as_ptr();
1272             let align = (ptr as usize + offset) & (usize_bytes - 1);
1273             if align == 0 {
1274                 if len >= bytes_per_iteration {
1275                     while offset <= len - bytes_per_iteration {
1276                         unsafe {
1277                             let u = *(ptr.offset(offset as isize) as *const usize);
1278                             let v = *(ptr.offset((offset + usize_bytes) as isize) as *const usize);
1279
1280                             // break if there is a nonascii byte
1281                             let zu = contains_nonascii(u);
1282                             let zv = contains_nonascii(v);
1283                             if zu || zv {
1284                                 break;
1285                             }
1286                         }
1287                         offset += bytes_per_iteration;
1288                     }
1289                 }
1290                 // step from the point where the wordwise loop stopped
1291                 while offset < len && v[offset] < 128 {
1292                     offset += 1;
1293                 }
1294             } else {
1295                 offset += 1;
1296             }
1297         }
1298     }
1299
1300     Ok(())
1301 }
1302
1303 // https://tools.ietf.org/html/rfc3629
1304 static UTF8_CHAR_WIDTH: [u8; 256] = [
1305 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1306 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1307 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1308 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1309 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1310 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1311 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1312 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1313 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1314 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1315 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1316 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1317 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1318 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1319 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1320 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1321 ];
1322
1323 /// Mask of the value bits of a continuation byte
1324 const CONT_MASK: u8 = 0b0011_1111;
1325 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
1326 const TAG_CONT_U8: u8 = 0b1000_0000;
1327
1328 /*
1329 Section: Trait implementations
1330 */
1331
1332 mod traits {
1333     use cmp::Ordering;
1334     use ops;
1335     use str::eq_slice;
1336
1337     #[stable(feature = "rust1", since = "1.0.0")]
1338     impl Ord for str {
1339         #[inline]
1340         fn cmp(&self, other: &str) -> Ordering {
1341             self.as_bytes().cmp(other.as_bytes())
1342         }
1343     }
1344
1345     #[stable(feature = "rust1", since = "1.0.0")]
1346     impl PartialEq for str {
1347         #[inline]
1348         fn eq(&self, other: &str) -> bool {
1349             eq_slice(self, other)
1350         }
1351         #[inline]
1352         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1353     }
1354
1355     #[stable(feature = "rust1", since = "1.0.0")]
1356     impl Eq for str {}
1357
1358     #[stable(feature = "rust1", since = "1.0.0")]
1359     impl PartialOrd for str {
1360         #[inline]
1361         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1362             Some(self.cmp(other))
1363         }
1364     }
1365
1366     /// Implements substring slicing with syntax `&self[begin .. end]`.
1367     ///
1368     /// Returns a slice of the given string from the byte range
1369     /// [`begin`..`end`).
1370     ///
1371     /// This operation is `O(1)`.
1372     ///
1373     /// # Panics
1374     ///
1375     /// Panics if `begin` or `end` does not point to the starting
1376     /// byte offset of a character (as defined by `is_char_boundary`).
1377     /// Requires that `begin <= end` and `end <= len` where `len` is the
1378     /// length of the string.
1379     ///
1380     /// # Examples
1381     ///
1382     /// ```
1383     /// let s = "Löwe 老虎 Léopard";
1384     /// assert_eq!(&s[0 .. 1], "L");
1385     ///
1386     /// assert_eq!(&s[1 .. 9], "öwe 老");
1387     ///
1388     /// // these will panic:
1389     /// // byte 2 lies within `ö`:
1390     /// // &s[2 ..3];
1391     ///
1392     /// // byte 8 lies within `老`
1393     /// // &s[1 .. 8];
1394     ///
1395     /// // byte 100 is outside the string
1396     /// // &s[3 .. 100];
1397     /// ```
1398     #[stable(feature = "rust1", since = "1.0.0")]
1399     impl ops::Index<ops::Range<usize>> for str {
1400         type Output = str;
1401         #[inline]
1402         fn index(&self, index: ops::Range<usize>) -> &str {
1403             // is_char_boundary checks that the index is in [0, .len()]
1404             if index.start <= index.end &&
1405                self.is_char_boundary(index.start) &&
1406                self.is_char_boundary(index.end) {
1407                 unsafe { self.slice_unchecked(index.start, index.end) }
1408             } else {
1409                 super::slice_error_fail(self, index.start, index.end)
1410             }
1411         }
1412     }
1413
1414     /// Implements mutable substring slicing with syntax
1415     /// `&mut self[begin .. end]`.
1416     ///
1417     /// Returns a mutable slice of the given string from the byte range
1418     /// [`begin`..`end`).
1419     ///
1420     /// This operation is `O(1)`.
1421     ///
1422     /// # Panics
1423     ///
1424     /// Panics if `begin` or `end` does not point to the starting
1425     /// byte offset of a character (as defined by `is_char_boundary`).
1426     /// Requires that `begin <= end` and `end <= len` where `len` is the
1427     /// length of the string.
1428     #[stable(feature = "derefmut_for_string", since = "1.2.0")]
1429     impl ops::IndexMut<ops::Range<usize>> for str {
1430         #[inline]
1431         fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
1432             // is_char_boundary checks that the index is in [0, .len()]
1433             if index.start <= index.end &&
1434                self.is_char_boundary(index.start) &&
1435                self.is_char_boundary(index.end) {
1436                 unsafe { self.slice_mut_unchecked(index.start, index.end) }
1437             } else {
1438                 super::slice_error_fail(self, index.start, index.end)
1439             }
1440         }
1441     }
1442
1443     /// Implements substring slicing with syntax `&self[.. end]`.
1444     ///
1445     /// Returns a slice of the string from the beginning to byte offset
1446     /// `end`.
1447     ///
1448     /// Equivalent to `&self[0 .. end]`.
1449     #[stable(feature = "rust1", since = "1.0.0")]
1450     impl ops::Index<ops::RangeTo<usize>> for str {
1451         type Output = str;
1452
1453         #[inline]
1454         fn index(&self, index: ops::RangeTo<usize>) -> &str {
1455             // is_char_boundary checks that the index is in [0, .len()]
1456             if self.is_char_boundary(index.end) {
1457                 unsafe { self.slice_unchecked(0, index.end) }
1458             } else {
1459                 super::slice_error_fail(self, 0, index.end)
1460             }
1461         }
1462     }
1463
1464     /// Implements mutable substring slicing with syntax `&mut self[.. end]`.
1465     ///
1466     /// Returns a mutable slice of the string from the beginning to byte offset
1467     /// `end`.
1468     ///
1469     /// Equivalent to `&mut self[0 .. end]`.
1470     #[stable(feature = "derefmut_for_string", since = "1.2.0")]
1471     impl ops::IndexMut<ops::RangeTo<usize>> for str {
1472         #[inline]
1473         fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
1474             // is_char_boundary checks that the index is in [0, .len()]
1475             if self.is_char_boundary(index.end) {
1476                 unsafe { self.slice_mut_unchecked(0, index.end) }
1477             } else {
1478                 super::slice_error_fail(self, 0, index.end)
1479             }
1480         }
1481     }
1482
1483     /// Implements substring slicing with syntax `&self[begin ..]`.
1484     ///
1485     /// Returns a slice of the string from byte offset `begin`
1486     /// to the end of the string.
1487     ///
1488     /// Equivalent to `&self[begin .. len]`.
1489     #[stable(feature = "rust1", since = "1.0.0")]
1490     impl ops::Index<ops::RangeFrom<usize>> for str {
1491         type Output = str;
1492
1493         #[inline]
1494         fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1495             // is_char_boundary checks that the index is in [0, .len()]
1496             if self.is_char_boundary(index.start) {
1497                 unsafe { self.slice_unchecked(index.start, self.len()) }
1498             } else {
1499                 super::slice_error_fail(self, index.start, self.len())
1500             }
1501         }
1502     }
1503
1504     /// Implements mutable substring slicing with syntax `&mut self[begin ..]`.
1505     ///
1506     /// Returns a mutable slice of the string from byte offset `begin`
1507     /// to the end of the string.
1508     ///
1509     /// Equivalent to `&mut self[begin .. len]`.
1510     #[stable(feature = "derefmut_for_string", since = "1.2.0")]
1511     impl ops::IndexMut<ops::RangeFrom<usize>> for str {
1512         #[inline]
1513         fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
1514             // is_char_boundary checks that the index is in [0, .len()]
1515             if self.is_char_boundary(index.start) {
1516                 let len = self.len();
1517                 unsafe { self.slice_mut_unchecked(index.start, len) }
1518             } else {
1519                 super::slice_error_fail(self, index.start, self.len())
1520             }
1521         }
1522     }
1523
1524     /// Implements substring slicing with syntax `&self[..]`.
1525     ///
1526     /// Returns a slice of the whole string. This operation can
1527     /// never panic.
1528     ///
1529     /// Equivalent to `&self[0 .. len]`.
1530     #[stable(feature = "rust1", since = "1.0.0")]
1531     impl ops::Index<ops::RangeFull> for str {
1532         type Output = str;
1533
1534         #[inline]
1535         fn index(&self, _index: ops::RangeFull) -> &str {
1536             self
1537         }
1538     }
1539
1540     /// Implements mutable substring slicing with syntax `&mut self[..]`.
1541     ///
1542     /// Returns a mutable slice of the whole string. This operation can
1543     /// never panic.
1544     ///
1545     /// Equivalent to `&mut self[0 .. len]`.
1546     #[stable(feature = "derefmut_for_string", since = "1.2.0")]
1547     impl ops::IndexMut<ops::RangeFull> for str {
1548         #[inline]
1549         fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
1550             self
1551         }
1552     }
1553
1554     #[unstable(feature = "inclusive_range",
1555                reason = "recently added, follows RFC",
1556                issue = "28237")]
1557     impl ops::Index<ops::RangeInclusive<usize>> for str {
1558         type Output = str;
1559
1560         #[inline]
1561         fn index(&self, index: ops::RangeInclusive<usize>) -> &str {
1562             match index {
1563                 ops::RangeInclusive::Empty { .. } => "",
1564                 ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() =>
1565                     panic!("attempted to index slice up to maximum usize"),
1566                 ops::RangeInclusive::NonEmpty { start, end } =>
1567                     self.index(start .. end+1)
1568             }
1569         }
1570     }
1571     #[unstable(feature = "inclusive_range",
1572                reason = "recently added, follows RFC",
1573                issue = "28237")]
1574     impl ops::Index<ops::RangeToInclusive<usize>> for str {
1575         type Output = str;
1576
1577         #[inline]
1578         fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
1579             self.index(0...index.end)
1580         }
1581     }
1582
1583     #[unstable(feature = "inclusive_range",
1584                reason = "recently added, follows RFC",
1585                issue = "28237")]
1586     impl ops::IndexMut<ops::RangeInclusive<usize>> for str {
1587         #[inline]
1588         fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
1589             match index {
1590                 ops::RangeInclusive::Empty { .. } => &mut self[0..0], // `&mut ""` doesn't work
1591                 ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() =>
1592                     panic!("attempted to index str up to maximum usize"),
1593                     ops::RangeInclusive::NonEmpty { start, end } =>
1594                         self.index_mut(start .. end+1)
1595             }
1596         }
1597     }
1598     #[unstable(feature = "inclusive_range",
1599                reason = "recently added, follows RFC",
1600                issue = "28237")]
1601     impl ops::IndexMut<ops::RangeToInclusive<usize>> for str {
1602         #[inline]
1603         fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
1604             self.index_mut(0...index.end)
1605         }
1606     }
1607 }
1608
1609 /// Methods for string slices
1610 #[allow(missing_docs)]
1611 #[doc(hidden)]
1612 #[unstable(feature = "core_str_ext",
1613            reason = "stable interface provided by `impl str` in later crates",
1614            issue = "32110")]
1615 pub trait StrExt {
1616     // NB there are no docs here are they're all located on the StrExt trait in
1617     // libcollections, not here.
1618
1619     #[stable(feature = "core", since = "1.6.0")]
1620     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
1621     #[stable(feature = "core", since = "1.6.0")]
1622     fn chars(&self) -> Chars;
1623     #[stable(feature = "core", since = "1.6.0")]
1624     fn bytes(&self) -> Bytes;
1625     #[stable(feature = "core", since = "1.6.0")]
1626     fn char_indices(&self) -> CharIndices;
1627     #[stable(feature = "core", since = "1.6.0")]
1628     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P>;
1629     #[stable(feature = "core", since = "1.6.0")]
1630     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
1631         where P::Searcher: ReverseSearcher<'a>;
1632     #[stable(feature = "core", since = "1.6.0")]
1633     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P>;
1634     #[stable(feature = "core", since = "1.6.0")]
1635     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
1636         where P::Searcher: ReverseSearcher<'a>;
1637     #[stable(feature = "core", since = "1.6.0")]
1638     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P>;
1639     #[stable(feature = "core", since = "1.6.0")]
1640     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
1641         where P::Searcher: ReverseSearcher<'a>;
1642     #[stable(feature = "core", since = "1.6.0")]
1643     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P>;
1644     #[stable(feature = "core", since = "1.6.0")]
1645     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
1646         where P::Searcher: ReverseSearcher<'a>;
1647     #[stable(feature = "core", since = "1.6.0")]
1648     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P>;
1649     #[stable(feature = "core", since = "1.6.0")]
1650     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
1651         where P::Searcher: ReverseSearcher<'a>;
1652     #[stable(feature = "core", since = "1.6.0")]
1653     fn lines(&self) -> Lines;
1654     #[stable(feature = "core", since = "1.6.0")]
1655     #[rustc_deprecated(since = "1.6.0", reason = "use lines() instead now")]
1656     #[allow(deprecated)]
1657     fn lines_any(&self) -> LinesAny;
1658     #[stable(feature = "core", since = "1.6.0")]
1659     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str;
1660     #[stable(feature = "core", since = "1.6.0")]
1661     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str;
1662     #[stable(feature = "core", since = "1.6.0")]
1663     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
1664     #[stable(feature = "core", since = "1.6.0")]
1665     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
1666         where P::Searcher: ReverseSearcher<'a>;
1667     #[stable(feature = "core", since = "1.6.0")]
1668     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
1669         where P::Searcher: DoubleEndedSearcher<'a>;
1670     #[stable(feature = "core", since = "1.6.0")]
1671     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str;
1672     #[stable(feature = "core", since = "1.6.0")]
1673     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
1674         where P::Searcher: ReverseSearcher<'a>;
1675     #[stable(feature = "is_char_boundary", since = "1.9.0")]
1676     fn is_char_boundary(&self, index: usize) -> bool;
1677     #[stable(feature = "core", since = "1.6.0")]
1678     fn as_bytes(&self) -> &[u8];
1679     #[stable(feature = "core", since = "1.6.0")]
1680     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
1681     #[stable(feature = "core", since = "1.6.0")]
1682     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
1683         where P::Searcher: ReverseSearcher<'a>;
1684     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
1685     #[stable(feature = "core", since = "1.6.0")]
1686     fn split_at(&self, mid: usize) -> (&str, &str);
1687     #[stable(feature = "core", since = "1.6.0")]
1688     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str);
1689     #[stable(feature = "core", since = "1.6.0")]
1690     fn as_ptr(&self) -> *const u8;
1691     #[stable(feature = "core", since = "1.6.0")]
1692     fn len(&self) -> usize;
1693     #[stable(feature = "core", since = "1.6.0")]
1694     fn is_empty(&self) -> bool;
1695     #[stable(feature = "core", since = "1.6.0")]
1696     fn parse<T: FromStr>(&self) -> Result<T, T::Err>;
1697 }
1698
1699 // truncate `&str` to length at most equal to `max`
1700 // return `true` if it were truncated, and the new str.
1701 fn truncate_to_char_boundary(s: &str, mut max: usize) -> (bool, &str) {
1702     if max >= s.len() {
1703         (false, s)
1704     } else {
1705         while !s.is_char_boundary(max) {
1706             max -= 1;
1707         }
1708         (true, &s[..max])
1709     }
1710 }
1711
1712 #[inline(never)]
1713 #[cold]
1714 fn slice_error_fail(s: &str, begin: usize, end: usize) -> ! {
1715     const MAX_DISPLAY_LENGTH: usize = 256;
1716     let (truncated, s) = truncate_to_char_boundary(s, MAX_DISPLAY_LENGTH);
1717     let ellipsis = if truncated { "[...]" } else { "" };
1718
1719     assert!(begin <= end, "begin <= end ({} <= {}) when slicing `{}`{}",
1720             begin, end, s, ellipsis);
1721     panic!("index {} and/or {} in `{}`{} do not lie on character boundary",
1722           begin, end, s, ellipsis);
1723 }
1724
1725 #[stable(feature = "core", since = "1.6.0")]
1726 impl StrExt for str {
1727     #[inline]
1728     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
1729         pat.is_contained_in(self)
1730     }
1731
1732     #[inline]
1733     fn chars(&self) -> Chars {
1734         Chars{iter: self.as_bytes().iter()}
1735     }
1736
1737     #[inline]
1738     fn bytes(&self) -> Bytes {
1739         Bytes(self.as_bytes().iter().cloned())
1740     }
1741
1742     #[inline]
1743     fn char_indices(&self) -> CharIndices {
1744         CharIndices { front_offset: 0, iter: self.chars() }
1745     }
1746
1747     #[inline]
1748     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
1749         Split(SplitInternal {
1750             start: 0,
1751             end: self.len(),
1752             matcher: pat.into_searcher(self),
1753             allow_trailing_empty: true,
1754             finished: false,
1755         })
1756     }
1757
1758     #[inline]
1759     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
1760         where P::Searcher: ReverseSearcher<'a>
1761     {
1762         RSplit(self.split(pat).0)
1763     }
1764
1765     #[inline]
1766     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
1767         SplitN(SplitNInternal {
1768             iter: self.split(pat).0,
1769             count: count,
1770         })
1771     }
1772
1773     #[inline]
1774     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
1775         where P::Searcher: ReverseSearcher<'a>
1776     {
1777         RSplitN(self.splitn(count, pat).0)
1778     }
1779
1780     #[inline]
1781     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
1782         SplitTerminator(SplitInternal {
1783             allow_trailing_empty: false,
1784             ..self.split(pat).0
1785         })
1786     }
1787
1788     #[inline]
1789     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
1790         where P::Searcher: ReverseSearcher<'a>
1791     {
1792         RSplitTerminator(self.split_terminator(pat).0)
1793     }
1794
1795     #[inline]
1796     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
1797         Matches(MatchesInternal(pat.into_searcher(self)))
1798     }
1799
1800     #[inline]
1801     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
1802         where P::Searcher: ReverseSearcher<'a>
1803     {
1804         RMatches(self.matches(pat).0)
1805     }
1806
1807     #[inline]
1808     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
1809         MatchIndices(MatchIndicesInternal(pat.into_searcher(self)))
1810     }
1811
1812     #[inline]
1813     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
1814         where P::Searcher: ReverseSearcher<'a>
1815     {
1816         RMatchIndices(self.match_indices(pat).0)
1817     }
1818     #[inline]
1819     fn lines(&self) -> Lines {
1820         Lines(self.split_terminator('\n').map(LinesAnyMap))
1821     }
1822
1823     #[inline]
1824     #[allow(deprecated)]
1825     fn lines_any(&self) -> LinesAny {
1826         LinesAny(self.lines())
1827     }
1828
1829     #[inline]
1830     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str {
1831         let ptr = self.as_ptr().offset(begin as isize);
1832         let len = end - begin;
1833         from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1834     }
1835
1836     #[inline]
1837     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str {
1838         let ptr = self.as_ptr().offset(begin as isize);
1839         let len = end - begin;
1840         mem::transmute(slice::from_raw_parts_mut(ptr as *mut u8, len))
1841     }
1842
1843     #[inline]
1844     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
1845         pat.is_prefix_of(self)
1846     }
1847
1848     #[inline]
1849     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
1850         where P::Searcher: ReverseSearcher<'a>
1851     {
1852         pat.is_suffix_of(self)
1853     }
1854
1855     #[inline]
1856     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
1857         where P::Searcher: DoubleEndedSearcher<'a>
1858     {
1859         let mut i = 0;
1860         let mut j = 0;
1861         let mut matcher = pat.into_searcher(self);
1862         if let Some((a, b)) = matcher.next_reject() {
1863             i = a;
1864             j = b; // Remember earliest known match, correct it below if
1865                    // last match is different
1866         }
1867         if let Some((_, b)) = matcher.next_reject_back() {
1868             j = b;
1869         }
1870         unsafe {
1871             // Searcher is known to return valid indices
1872             self.slice_unchecked(i, j)
1873         }
1874     }
1875
1876     #[inline]
1877     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str {
1878         let mut i = self.len();
1879         let mut matcher = pat.into_searcher(self);
1880         if let Some((a, _)) = matcher.next_reject() {
1881             i = a;
1882         }
1883         unsafe {
1884             // Searcher is known to return valid indices
1885             self.slice_unchecked(i, self.len())
1886         }
1887     }
1888
1889     #[inline]
1890     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
1891         where P::Searcher: ReverseSearcher<'a>
1892     {
1893         let mut j = 0;
1894         let mut matcher = pat.into_searcher(self);
1895         if let Some((_, b)) = matcher.next_reject_back() {
1896             j = b;
1897         }
1898         unsafe {
1899             // Searcher is known to return valid indices
1900             self.slice_unchecked(0, j)
1901         }
1902     }
1903
1904     #[inline]
1905     fn is_char_boundary(&self, index: usize) -> bool {
1906         // 0 and len are always ok.
1907         // Test for 0 explicitly so that it can optimize out the check
1908         // easily and skip reading string data for that case.
1909         if index == 0 || index == self.len() { return true; }
1910         match self.as_bytes().get(index) {
1911             None => false,
1912             // This is bit magic equivalent to: b < 128 || b >= 192
1913             Some(&b) => (b as i8) >= -0x40,
1914         }
1915     }
1916
1917     #[inline]
1918     fn as_bytes(&self) -> &[u8] {
1919         unsafe { mem::transmute(self) }
1920     }
1921
1922     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
1923         pat.into_searcher(self).next_match().map(|(i, _)| i)
1924     }
1925
1926     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
1927         where P::Searcher: ReverseSearcher<'a>
1928     {
1929         pat.into_searcher(self).next_match_back().map(|(i, _)| i)
1930     }
1931
1932     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
1933         self.find(pat)
1934     }
1935
1936     #[inline]
1937     fn split_at(&self, mid: usize) -> (&str, &str) {
1938         // is_char_boundary checks that the index is in [0, .len()]
1939         if self.is_char_boundary(mid) {
1940             unsafe {
1941                 (self.slice_unchecked(0, mid),
1942                  self.slice_unchecked(mid, self.len()))
1943             }
1944         } else {
1945             slice_error_fail(self, 0, mid)
1946         }
1947     }
1948
1949     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str) {
1950         // is_char_boundary checks that the index is in [0, .len()]
1951         if self.is_char_boundary(mid) {
1952             let len = self.len();
1953             let ptr = self.as_ptr() as *mut u8;
1954             unsafe {
1955                 (from_raw_parts_mut(ptr, mid),
1956                  from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
1957             }
1958         } else {
1959             slice_error_fail(self, 0, mid)
1960         }
1961     }
1962
1963     #[inline]
1964     fn as_ptr(&self) -> *const u8 {
1965         self as *const str as *const u8
1966     }
1967
1968     #[inline]
1969     fn len(&self) -> usize {
1970         self.as_bytes().len()
1971     }
1972
1973     #[inline]
1974     fn is_empty(&self) -> bool { self.len() == 0 }
1975
1976     #[inline]
1977     fn parse<T: FromStr>(&self) -> Result<T, T::Err> { FromStr::from_str(self) }
1978 }
1979
1980 #[stable(feature = "rust1", since = "1.0.0")]
1981 impl AsRef<[u8]> for str {
1982     #[inline]
1983     fn as_ref(&self) -> &[u8] {
1984         self.as_bytes()
1985     }
1986 }
1987
1988 #[stable(feature = "rust1", since = "1.0.0")]
1989 impl<'a> Default for &'a str {
1990     /// Creates an empty str
1991     fn default() -> &'a str { "" }
1992 }