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, TrustedLen};
  23 use iter_private::TrustedRandomAccess;
  24 use slice::{self, SliceIndex};
  25 use mem;
  26
  27 pub mod pattern;
  28
  29 /// A trait to abstract the idea of creating a new instance of a type from a
  30 /// string.
  31 ///
  32 /// `FromStr`'s [`from_str`] method is often used implicitly, through
  33 /// [`str`]'s [`parse`] method. See [`parse`]'s documentation for examples.
  34 ///
  35 /// [`from_str`]: #tymethod.from_str
  36 /// [`str`]: ../../std/primitive.str.html
  37 /// [`parse`]: ../../std/primitive.str.html#method.parse
  38 ///
  39 /// # Examples
  40 ///
  41 /// Basic implementation of `FromStr` on an example `Point` type:
  42 ///
  43 /// ```
  44 /// use std::str::FromStr;
  45 /// use std::num::ParseIntError;
  46 ///
  47 /// #[derive(Debug, PartialEq)]
  48 /// struct Point {
  49 ///     x: i32,
  50 ///     y: i32
  51 /// }
  52 ///
  53 /// impl FromStr for Point {
  54 ///     type Err = ParseIntError;
  55 ///
  56 ///     fn from_str(s: &str) -> Result<Self, Self::Err> {
  57 ///         let coords: Vec<&str> = s.trim_matches(|p| p == '(' || p == ')' )
  58 ///                                  .split(",")
  59 ///                                  .collect();
  60 ///
  61 ///         let x_fromstr = coords[0].parse::<i32>()?;
  62 ///         let y_fromstr = coords[1].parse::<i32>()?;
  63 ///
  64 ///         Ok(Point { x: x_fromstr, y: y_fromstr })
  65 ///     }
  66 /// }
  67 ///
  68 /// let p = Point::from_str("(1,2)");
  69 /// assert_eq!(p.unwrap(), Point{ x: 1, y: 2} )
  70 /// ```
  71 #[stable(feature = "rust1", since = "1.0.0")]
  72 pub trait FromStr: Sized {
  73     /// The associated error which can be returned from parsing.
  74     #[stable(feature = "rust1", since = "1.0.0")]
  75     type Err;
  76
  77     /// Parses a string `s` to return a value of this type.
  78     ///
  79     /// If parsing succeeds, return the value inside [`Ok`], otherwise
  80     /// when the string is ill-formatted return an error specific to the
  81     /// inside [`Err`]. The error type is specific to implementation of the trait.
  82     ///
  83     /// [`Ok`]: ../../std/result/enum.Result.html#variant.Ok
  84     /// [`Err`]: ../../std/result/enum.Result.html#variant.Err
  85     ///
  86     /// # Examples
  87     ///
  88     /// Basic usage with [`i32`][ithirtytwo], a type that implements `FromStr`:
  89     ///
  90     /// [ithirtytwo]: ../../std/primitive.i32.html
  91     ///
  92     /// ```
  93     /// use std::str::FromStr;
  94     ///
  95     /// let s = "5";
  96     /// let x = i32::from_str(s).unwrap();
  97     ///
  98     /// assert_eq!(5, x);
  99     /// ```
 100     #[stable(feature = "rust1", since = "1.0.0")]
 101     fn from_str(s: &str) -> Result<Self, Self::Err>;
 102 }
 103
 104 #[stable(feature = "rust1", since = "1.0.0")]
 105 impl FromStr for bool {
 106     type Err = ParseBoolError;
 107
 108     /// Parse a `bool` from a string.
 109     ///
 110     /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
 111     /// actually be parseable.
 112     ///
 113     /// # Examples
 114     ///
 115     /// ```
 116     /// use std::str::FromStr;
 117     ///
 118     /// assert_eq!(FromStr::from_str("true"), Ok(true));
 119     /// assert_eq!(FromStr::from_str("false"), Ok(false));
 120     /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
 121     /// ```
 122     ///
 123     /// Note, in many cases, the `.parse()` method on `str` is more proper.
 124     ///
 125     /// ```
 126     /// assert_eq!("true".parse(), Ok(true));
 127     /// assert_eq!("false".parse(), Ok(false));
 128     /// assert!("not even a boolean".parse::<bool>().is_err());
 129     /// ```
 130     #[inline]
 131     fn from_str(s: &str) -> Result<bool, ParseBoolError> {
 132         match s {
 133             "true"  => Ok(true),
 134             "false" => Ok(false),
 135             _       => Err(ParseBoolError { _priv: () }),
 136         }
 137     }
 138 }
 139
 140 /// An error returned when parsing a `bool` using [`from_str`] fails
 141 ///
 142 /// [`from_str`]: ../../std/primitive.bool.html#method.from_str
 143 #[derive(Debug, Clone, PartialEq, Eq)]
 144 #[stable(feature = "rust1", since = "1.0.0")]
 145 pub struct ParseBoolError { _priv: () }
 146
 147 #[stable(feature = "rust1", since = "1.0.0")]
 148 impl fmt::Display for ParseBoolError {
 149     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 150         "provided string was not `true` or `false`".fmt(f)
 151     }
 152 }
 153
 154 /*
 155 Section: Creating a string
 156 */
 157
 158 /// Errors which can occur when attempting to interpret a sequence of [`u8`]
 159 /// as a string.
 160 ///
 161 /// [`u8`]: ../../std/primitive.u8.html
 162 ///
 163 /// As such, the `from_utf8` family of functions and methods for both [`String`]s
 164 /// and [`&str`]s make use of this error, for example.
 165 ///
 166 /// [`String`]: ../../std/string/struct.String.html#method.from_utf8
 167 /// [`&str`]: ../../std/str/fn.from_utf8.html
 168 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
 169 #[stable(feature = "rust1", since = "1.0.0")]
 170 pub struct Utf8Error {
 171     valid_up_to: usize,
 172     error_len: Option<u8>,
 173 }
 174
 175 impl Utf8Error {
 176     /// Returns the index in the given string up to which valid UTF-8 was
 177     /// verified.
 178     ///
 179     /// It is the maximum index such that `from_utf8(&input[..index])`
 180     /// would return `Ok(_)`.
 181     ///
 182     /// # Examples
 183     ///
 184     /// Basic usage:
 185     ///
 186     /// ```
 187     /// use std::str;
 188     ///
 189     /// // some invalid bytes, in a vector
 190     /// let sparkle_heart = vec![0, 159, 146, 150];
 191     ///
 192     /// // std::str::from_utf8 returns a Utf8Error
 193     /// let error = str::from_utf8(&sparkle_heart).unwrap_err();
 194     ///
 195     /// // the second byte is invalid here
 196     /// assert_eq!(1, error.valid_up_to());
 197     /// ```
 198     #[stable(feature = "utf8_error", since = "1.5.0")]
 199     pub fn valid_up_to(&self) -> usize { self.valid_up_to }
 200
 201     /// Provide more information about the failure:
 202     ///
 203     /// * `None`: the end of the input was reached unexpectedly.
 204     ///   `self.valid_up_to()` is 1 to 3 bytes from the end of the input.
 205     ///   If a byte stream (such as a file or a network socket) is being decoded incrementally,
 206     ///   this could be a valid `char` whose UTF-8 byte sequence is spanning multiple chunks.
 207     ///
 208     /// * `Some(len)`: an unexpected byte was encountered.
 209     ///   The length provided is that of the invalid byte sequence
 210     ///   that starts at the index given by `valid_up_to()`.
 211     ///   Decoding should resume after that sequence
 212     ///   (after inserting a U+FFFD REPLACEMENT CHARACTER) in case of lossy decoding.
 213     #[stable(feature = "utf8_error_error_len", since = "1.20.0")]
 214     pub fn error_len(&self) -> Option<usize> {
 215         self.error_len.map(|len| len as usize)
 216     }
 217 }
 218
 219 /// Converts a slice of bytes to a string slice.
 220 ///
 221 /// A string slice ([`&str`]) is made of bytes ([`u8`]), and a byte slice
 222 /// ([`&[u8]`][byteslice]) is made of bytes, so this function converts between
 223 /// the two. Not all byte slices are valid string slices, however: [`&str`] requires
 224 /// that it is valid UTF-8. `from_utf8()` checks to ensure that the bytes are valid
 225 /// UTF-8, and then does the conversion.
 226 ///
 227 /// [`&str`]: ../../std/primitive.str.html
 228 /// [`u8`]: ../../std/primitive.u8.html
 229 /// [byteslice]: ../../std/primitive.slice.html
 230 ///
 231 /// If you are sure that the byte slice is valid UTF-8, and you don't want to
 232 /// incur the overhead of the validity check, there is an unsafe version of
 233 /// this function, [`from_utf8_unchecked`][fromutf8u], which has the same
 234 /// behavior but skips the check.
 235 ///
 236 /// [fromutf8u]: fn.from_utf8_unchecked.html
 237 ///
 238 /// If you need a `String` instead of a `&str`, consider
 239 /// [`String::from_utf8`][string].
 240 ///
 241 /// [string]: ../../std/string/struct.String.html#method.from_utf8
 242 ///
 243 /// Because you can stack-allocate a `[u8; N]`, and you can take a
 244 /// [`&[u8]`][byteslice] of it, this function is one way to have a
 245 /// stack-allocated string. There is an example of this in the
 246 /// examples section below.
 247 ///
 248 /// [byteslice]: ../../std/primitive.slice.html
 249 ///
 250 /// # Errors
 251 ///
 252 /// Returns `Err` if the slice is not UTF-8 with a description as to why the
 253 /// provided slice is not UTF-8.
 254 ///
 255 /// # Examples
 256 ///
 257 /// Basic usage:
 258 ///
 259 /// ```
 260 /// use std::str;
 261 ///
 262 /// // some bytes, in a vector
 263 /// let sparkle_heart = vec![240, 159, 146, 150];
 264 ///
 265 /// // We know these bytes are valid, so just use `unwrap()`.
 266 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 267 ///
 268 /// assert_eq!("💖", sparkle_heart);
 269 /// ```
 270 ///
 271 /// Incorrect bytes:
 272 ///
 273 /// ```
 274 /// use std::str;
 275 ///
 276 /// // some invalid bytes, in a vector
 277 /// let sparkle_heart = vec![0, 159, 146, 150];
 278 ///
 279 /// assert!(str::from_utf8(&sparkle_heart).is_err());
 280 /// ```
 281 ///
 282 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 283 /// errors that can be returned.
 284 ///
 285 /// [error]: struct.Utf8Error.html
 286 ///
 287 /// A "stack allocated string":
 288 ///
 289 /// ```
 290 /// use std::str;
 291 ///
 292 /// // some bytes, in a stack-allocated array
 293 /// let sparkle_heart = [240, 159, 146, 150];
 294 ///
 295 /// // We know these bytes are valid, so just use `unwrap()`.
 296 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 297 ///
 298 /// assert_eq!("💖", sparkle_heart);
 299 /// ```
 300 #[stable(feature = "rust1", since = "1.0.0")]
 301 pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
 302     run_utf8_validation(v)?;
 303     Ok(unsafe { from_utf8_unchecked(v) })
 304 }
 305
 306 /// Converts a mutable slice of bytes to a mutable string slice.
 307 ///
 308 /// # Examples
 309 ///
 310 /// Basic usage:
 311 ///
 312 /// ```
 313 /// use std::str;
 314 ///
 315 /// // "Hello, Rust!" as a mutable vector
 316 /// let mut hellorust = vec![72, 101, 108, 108, 111, 44, 32, 82, 117, 115, 116, 33];
 317 ///
 318 /// // As we know these bytes are valid, we can use `unwrap()`
 319 /// let outstr = str::from_utf8_mut(&mut hellorust).unwrap();
 320 ///
 321 /// assert_eq!("Hello, Rust!", outstr);
 322 /// ```
 323 ///
 324 /// Incorrect bytes:
 325 ///
 326 /// ```
 327 /// use std::str;
 328 ///
 329 /// // Some invalid bytes in a mutable vector
 330 /// let mut invalid = vec![128, 223];
 331 ///
 332 /// assert!(str::from_utf8_mut(&mut invalid).is_err());
 333 /// ```
 334 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 335 /// errors that can be returned.
 336 ///
 337 /// [error]: struct.Utf8Error.html
 338 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 339 pub fn from_utf8_mut(v: &mut [u8]) -> Result<&mut str, Utf8Error> {
 340     run_utf8_validation(v)?;
 341     Ok(unsafe { from_utf8_unchecked_mut(v) })
 342 }
 343
 344 /// Forms a str from a pointer and a length.
 345 ///
 346 /// The `len` argument is the number of bytes in the string.
 347 ///
 348 /// # Safety
 349 ///
 350 /// This function is unsafe as there is no guarantee that the given pointer is
 351 /// valid for `len` bytes, nor whether the lifetime inferred is a suitable
 352 /// lifetime for the returned str.
 353 ///
 354 /// The data must be valid UTF-8
 355 ///
 356 /// `p` must be non-null, even for zero-length strs, because non-zero bits
 357 /// are required to distinguish between a zero-length str within `Some()`
 358 /// from `None`. `p` can be a bogus non-dereferencable pointer, such as `0x1`,
 359 /// for zero-length strs, though.
 360 ///
 361 /// # Caveat
 362 ///
 363 /// The lifetime for the returned str is inferred from its usage. To
 364 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
 365 /// source lifetime is safe in the context, such as by providing a helper
 366 /// function taking the lifetime of a host value for the str, or by explicit
 367 /// annotation.
 368 /// Performs the same functionality as `from_raw_parts`, except that a mutable
 369 /// str is returned.
 370 ///
 371 unsafe fn from_raw_parts_mut<'a>(p: *mut u8, len: usize) -> &'a mut str {
 372     from_utf8_unchecked_mut(slice::from_raw_parts_mut(p, len))
 373 }
 374
 375 /// Converts a slice of bytes to a string slice without checking
 376 /// that the string contains valid UTF-8.
 377 ///
 378 /// See the safe version, [`from_utf8`][fromutf8], for more information.
 379 ///
 380 /// [fromutf8]: fn.from_utf8.html
 381 ///
 382 /// # Safety
 383 ///
 384 /// This function is unsafe because it does not check that the bytes passed to
 385 /// it are valid UTF-8. If this constraint is violated, undefined behavior
 386 /// results, as the rest of Rust assumes that [`&str`]s are valid UTF-8.
 387 ///
 388 /// [`&str`]: ../../std/primitive.str.html
 389 ///
 390 /// # Examples
 391 ///
 392 /// Basic usage:
 393 ///
 394 /// ```
 395 /// use std::str;
 396 ///
 397 /// // some bytes, in a vector
 398 /// let sparkle_heart = vec![240, 159, 146, 150];
 399 ///
 400 /// let sparkle_heart = unsafe {
 401 ///     str::from_utf8_unchecked(&sparkle_heart)
 402 /// };
 403 ///
 404 /// assert_eq!("💖", sparkle_heart);
 405 /// ```
 406 #[inline]
 407 #[stable(feature = "rust1", since = "1.0.0")]
 408 pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
 409     &*(v as *const [u8] as *const str)
 410 }
 411
 412 /// Converts a slice of bytes to a string slice without checking
 413 /// that the string contains valid UTF-8; mutable version.
 414 ///
 415 /// See the immutable version, [`from_utf8_unchecked()`][fromutf8], for more information.
 416 ///
 417 /// [fromutf8]: fn.from_utf8_unchecked.html
 418 ///
 419 /// # Examples
 420 ///
 421 /// Basic usage:
 422 ///
 423 /// ```
 424 /// use std::str;
 425 ///
 426 /// let mut heart = vec![240, 159, 146, 150];
 427 /// let heart = unsafe { str::from_utf8_unchecked_mut(&mut heart) };
 428 ///
 429 /// assert_eq!("💖", heart);
 430 /// ```
 431 #[inline]
 432 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 433 pub unsafe fn from_utf8_unchecked_mut(v: &mut [u8]) -> &mut str {
 434     &mut *(v as *mut [u8] as *mut str)
 435 }
 436
 437 #[stable(feature = "rust1", since = "1.0.0")]
 438 impl fmt::Display for Utf8Error {
 439     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 440         if let Some(error_len) = self.error_len {
 441             write!(f, "invalid utf-8 sequence of {} bytes from index {}",
 442                    error_len, self.valid_up_to)
 443         } else {
 444             write!(f, "incomplete utf-8 byte sequence from index {}", self.valid_up_to)
 445         }
 446     }
 447 }
 448
 449 /*
 450 Section: Iterators
 451 */
 452
 453 /// An iterator over the [`char`]s of a string slice.
 454 ///
 455 /// [`char`]: ../../std/primitive.char.html
 456 ///
 457 /// This struct is created by the [`chars`] method on [`str`].
 458 /// See its documentation for more.
 459 ///
 460 /// [`chars`]: ../../std/primitive.str.html#method.chars
 461 /// [`str`]: ../../std/primitive.str.html
 462 #[derive(Clone, Debug)]
 463 #[stable(feature = "rust1", since = "1.0.0")]
 464 pub struct Chars<'a> {
 465     iter: slice::Iter<'a, u8>
 466 }
 467
 468 /// Returns the initial codepoint accumulator for the first byte.
 469 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
 470 /// for width 3, and 3 bits for width 4.
 471 #[inline]
 472 fn utf8_first_byte(byte: u8, width: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
 473
 474 /// Returns the value of `ch` updated with continuation byte `byte`.
 475 #[inline]
 476 fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
 477
 478 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
 479 /// bits `10`).
 480 #[inline]
 481 fn utf8_is_cont_byte(byte: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
 482
 483 #[inline]
 484 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 485     match opt {
 486         Some(&byte) => byte,
 487         None => 0,
 488     }
 489 }
 490
 491 /// Reads the next code point out of a byte iterator (assuming a
 492 /// UTF-8-like encoding).
 493 #[unstable(feature = "str_internals", issue = "0")]
 494 #[inline]
 495 pub fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
 496     // Decode UTF-8
 497     let x = match bytes.next() {
 498         None => return None,
 499         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 500         Some(&next_byte) => next_byte,
 501     };
 502
 503     // Multibyte case follows
 504     // Decode from a byte combination out of: [[[x y] z] w]
 505     // NOTE: Performance is sensitive to the exact formulation here
 506     let init = utf8_first_byte(x, 2);
 507     let y = unwrap_or_0(bytes.next());
 508     let mut ch = utf8_acc_cont_byte(init, y);
 509     if x >= 0xE0 {
 510         // [[x y z] w] case
 511         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 512         let z = unwrap_or_0(bytes.next());
 513         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
 514         ch = init << 12 | y_z;
 515         if x >= 0xF0 {
 516             // [x y z w] case
 517             // use only the lower 3 bits of `init`
 518             let w = unwrap_or_0(bytes.next());
 519             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
 520         }
 521     }
 522
 523     Some(ch)
 524 }
 525
 526 /// Reads the last code point out of a byte iterator (assuming a
 527 /// UTF-8-like encoding).
 528 #[inline]
 529 fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
 530     where I: DoubleEndedIterator<Item = &'a u8>,
 531 {
 532     // Decode UTF-8
 533     let w = match bytes.next_back() {
 534         None => return None,
 535         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 536         Some(&back_byte) => back_byte,
 537     };
 538
 539     // Multibyte case follows
 540     // Decode from a byte combination out of: [x [y [z w]]]
 541     let mut ch;
 542     let z = unwrap_or_0(bytes.next_back());
 543     ch = utf8_first_byte(z, 2);
 544     if utf8_is_cont_byte(z) {
 545         let y = unwrap_or_0(bytes.next_back());
 546         ch = utf8_first_byte(y, 3);
 547         if utf8_is_cont_byte(y) {
 548             let x = unwrap_or_0(bytes.next_back());
 549             ch = utf8_first_byte(x, 4);
 550             ch = utf8_acc_cont_byte(ch, y);
 551         }
 552         ch = utf8_acc_cont_byte(ch, z);
 553     }
 554     ch = utf8_acc_cont_byte(ch, w);
 555
 556     Some(ch)
 557 }
 558
 559 #[stable(feature = "rust1", since = "1.0.0")]
 560 impl<'a> Iterator for Chars<'a> {
 561     type Item = char;
 562
 563     #[inline]
 564     fn next(&mut self) -> Option<char> {
 565         next_code_point(&mut self.iter).map(|ch| {
 566             // str invariant says `ch` is a valid Unicode Scalar Value
 567             unsafe {
 568                 char::from_u32_unchecked(ch)
 569             }
 570         })
 571     }
 572
 573     #[inline]
 574     fn count(self) -> usize {
 575         // length in `char` is equal to the number of non-continuation bytes
 576         let bytes_len = self.iter.len();
 577         let mut cont_bytes = 0;
 578         for &byte in self.iter {
 579             cont_bytes += utf8_is_cont_byte(byte) as usize;
 580         }
 581         bytes_len - cont_bytes
 582     }
 583
 584     #[inline]
 585     fn size_hint(&self) -> (usize, Option<usize>) {
 586         let len = self.iter.len();
 587         // `(len + 3)` can't overflow, because we know that the `slice::Iter`
 588         // belongs to a slice in memory which has a maximum length of
 589         // `isize::MAX` (that's well below `usize::MAX`).
 590         ((len + 3) / 4, Some(len))
 591     }
 592
 593     #[inline]
 594     fn last(mut self) -> Option<char> {
 595         // No need to go through the entire string.
 596         self.next_back()
 597     }
 598 }
 599
 600 #[stable(feature = "rust1", since = "1.0.0")]
 601 impl<'a> DoubleEndedIterator for Chars<'a> {
 602     #[inline]
 603     fn next_back(&mut self) -> Option<char> {
 604         next_code_point_reverse(&mut self.iter).map(|ch| {
 605             // str invariant says `ch` is a valid Unicode Scalar Value
 606             unsafe {
 607                 char::from_u32_unchecked(ch)
 608             }
 609         })
 610     }
 611 }
 612
 613 #[unstable(feature = "fused", issue = "35602")]
 614 impl<'a> FusedIterator for Chars<'a> {}
 615
 616 impl<'a> Chars<'a> {
 617     /// View the underlying data as a subslice of the original data.
 618     ///
 619     /// This has the same lifetime as the original slice, and so the
 620     /// iterator can continue to be used while this exists.
 621     ///
 622     /// # Examples
 623     ///
 624     /// ```
 625     /// let mut chars = "abc".chars();
 626     ///
 627     /// assert_eq!(chars.as_str(), "abc");
 628     /// chars.next();
 629     /// assert_eq!(chars.as_str(), "bc");
 630     /// chars.next();
 631     /// chars.next();
 632     /// assert_eq!(chars.as_str(), "");
 633     /// ```
 634     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 635     #[inline]
 636     pub fn as_str(&self) -> &'a str {
 637         unsafe { from_utf8_unchecked(self.iter.as_slice()) }
 638     }
 639 }
 640
 641 /// An iterator over the [`char`]s of a string slice, and their positions.
 642 ///
 643 /// [`char`]: ../../std/primitive.char.html
 644 ///
 645 /// This struct is created by the [`char_indices`] method on [`str`].
 646 /// See its documentation for more.
 647 ///
 648 /// [`char_indices`]: ../../std/primitive.str.html#method.char_indices
 649 /// [`str`]: ../../std/primitive.str.html
 650 #[derive(Clone, Debug)]
 651 #[stable(feature = "rust1", since = "1.0.0")]
 652 pub struct CharIndices<'a> {
 653     front_offset: usize,
 654     iter: Chars<'a>,
 655 }
 656
 657 #[stable(feature = "rust1", since = "1.0.0")]
 658 impl<'a> Iterator for CharIndices<'a> {
 659     type Item = (usize, char);
 660
 661     #[inline]
 662     fn next(&mut self) -> Option<(usize, char)> {
 663         let pre_len = self.iter.iter.len();
 664         match self.iter.next() {
 665             None => None,
 666             Some(ch) => {
 667                 let index = self.front_offset;
 668                 let len = self.iter.iter.len();
 669                 self.front_offset += pre_len - len;
 670                 Some((index, ch))
 671             }
 672         }
 673     }
 674
 675     #[inline]
 676     fn count(self) -> usize {
 677         self.iter.count()
 678     }
 679
 680     #[inline]
 681     fn size_hint(&self) -> (usize, Option<usize>) {
 682         self.iter.size_hint()
 683     }
 684
 685     #[inline]
 686     fn last(mut self) -> Option<(usize, char)> {
 687         // No need to go through the entire string.
 688         self.next_back()
 689     }
 690 }
 691
 692 #[stable(feature = "rust1", since = "1.0.0")]
 693 impl<'a> DoubleEndedIterator for CharIndices<'a> {
 694     #[inline]
 695     fn next_back(&mut self) -> Option<(usize, char)> {
 696         match self.iter.next_back() {
 697             None => None,
 698             Some(ch) => {
 699                 let index = self.front_offset + self.iter.iter.len();
 700                 Some((index, ch))
 701             }
 702         }
 703     }
 704 }
 705
 706 #[unstable(feature = "fused", issue = "35602")]
 707 impl<'a> FusedIterator for CharIndices<'a> {}
 708
 709 impl<'a> CharIndices<'a> {
 710     /// View the underlying data as a subslice of the original data.
 711     ///
 712     /// This has the same lifetime as the original slice, and so the
 713     /// iterator can continue to be used while this exists.
 714     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 715     #[inline]
 716     pub fn as_str(&self) -> &'a str {
 717         self.iter.as_str()
 718     }
 719 }
 720
 721 /// An iterator over the bytes of a string slice.
 722 ///
 723 /// This struct is created by the [`bytes`] method on [`str`].
 724 /// See its documentation for more.
 725 ///
 726 /// [`bytes`]: ../../std/primitive.str.html#method.bytes
 727 /// [`str`]: ../../std/primitive.str.html
 728 #[stable(feature = "rust1", since = "1.0.0")]
 729 #[derive(Clone, Debug)]
 730 pub struct Bytes<'a>(Cloned<slice::Iter<'a, u8>>);
 731
 732 #[stable(feature = "rust1", since = "1.0.0")]
 733 impl<'a> Iterator for Bytes<'a> {
 734     type Item = u8;
 735
 736     #[inline]
 737     fn next(&mut self) -> Option<u8> {
 738         self.0.next()
 739     }
 740
 741     #[inline]
 742     fn size_hint(&self) -> (usize, Option<usize>) {
 743         self.0.size_hint()
 744     }
 745
 746     #[inline]
 747     fn count(self) -> usize {
 748         self.0.count()
 749     }
 750
 751     #[inline]
 752     fn last(self) -> Option<Self::Item> {
 753         self.0.last()
 754     }
 755
 756     #[inline]
 757     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 758         self.0.nth(n)
 759     }
 760
 761     #[inline]
 762     fn all<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 763         self.0.all(f)
 764     }
 765
 766     #[inline]
 767     fn any<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 768         self.0.any(f)
 769     }
 770
 771     #[inline]
 772     fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where
 773         P: FnMut(&Self::Item) -> bool
 774     {
 775         self.0.find(predicate)
 776     }
 777
 778     #[inline]
 779     fn position<P>(&mut self, predicate: P) -> Option<usize> where
 780         P: FnMut(Self::Item) -> bool
 781     {
 782         self.0.position(predicate)
 783     }
 784
 785     #[inline]
 786     fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
 787         P: FnMut(Self::Item) -> bool
 788     {
 789         self.0.rposition(predicate)
 790     }
 791 }
 792
 793 #[stable(feature = "rust1", since = "1.0.0")]
 794 impl<'a> DoubleEndedIterator for Bytes<'a> {
 795     #[inline]
 796     fn next_back(&mut self) -> Option<u8> {
 797         self.0.next_back()
 798     }
 799
 800     #[inline]
 801     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where
 802         P: FnMut(&Self::Item) -> bool
 803     {
 804         self.0.rfind(predicate)
 805     }
 806 }
 807
 808 #[stable(feature = "rust1", since = "1.0.0")]
 809 impl<'a> ExactSizeIterator for Bytes<'a> {
 810     #[inline]
 811     fn len(&self) -> usize {
 812         self.0.len()
 813     }
 814
 815     #[inline]
 816     fn is_empty(&self) -> bool {
 817         self.0.is_empty()
 818     }
 819 }
 820
 821 #[unstable(feature = "fused", issue = "35602")]
 822 impl<'a> FusedIterator for Bytes<'a> {}
 823
 824 #[unstable(feature = "trusted_len", issue = "37572")]
 825 unsafe impl<'a> TrustedLen for Bytes<'a> {}
 826
 827 #[doc(hidden)]
 828 unsafe impl<'a> TrustedRandomAccess for Bytes<'a> {
 829     unsafe fn get_unchecked(&mut self, i: usize) -> u8 {
 830         self.0.get_unchecked(i)
 831     }
 832     fn may_have_side_effect() -> bool { false }
 833 }
 834
 835 /// This macro generates a Clone impl for string pattern API
 836 /// wrapper types of the form X<'a, P>
 837 macro_rules! derive_pattern_clone {
 838     (clone $t:ident with |$s:ident| $e:expr) => {
 839         impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
 840             where P::Searcher: Clone
 841         {
 842             fn clone(&self) -> Self {
 843                 let $s = self;
 844                 $e
 845             }
 846         }
 847     }
 848 }
 849
 850 /// This macro generates two public iterator structs
 851 /// wrapping a private internal one that makes use of the `Pattern` API.
 852 ///
 853 /// For all patterns `P: Pattern<'a>` the following items will be
 854 /// generated (generics omitted):
 855 ///
 856 /// struct $forward_iterator($internal_iterator);
 857 /// struct $reverse_iterator($internal_iterator);
 858 ///
 859 /// impl Iterator for $forward_iterator
 860 /// { /* internal ends up calling Searcher::next_match() */ }
 861 ///
 862 /// impl DoubleEndedIterator for $forward_iterator
 863 ///       where P::Searcher: DoubleEndedSearcher
 864 /// { /* internal ends up calling Searcher::next_match_back() */ }
 865 ///
 866 /// impl Iterator for $reverse_iterator
 867 ///       where P::Searcher: ReverseSearcher
 868 /// { /* internal ends up calling Searcher::next_match_back() */ }
 869 ///
 870 /// impl DoubleEndedIterator for $reverse_iterator
 871 ///       where P::Searcher: DoubleEndedSearcher
 872 /// { /* internal ends up calling Searcher::next_match() */ }
 873 ///
 874 /// The internal one is defined outside the macro, and has almost the same
 875 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
 876 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
 877 ///
 878 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
 879 /// `Pattern` might not return the same elements, so actually implementing
 880 /// `DoubleEndedIterator` for it would be incorrect.
 881 /// (See the docs in `str::pattern` for more details)
 882 ///
 883 /// However, the internal struct still represents a single ended iterator from
 884 /// either end, and depending on pattern is also a valid double ended iterator,
 885 /// so the two wrapper structs implement `Iterator`
 886 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
 887 /// to the complex impls seen above.
 888 macro_rules! generate_pattern_iterators {
 889     {
 890         // Forward iterator
 891         forward:
 892             $(#[$forward_iterator_attribute:meta])*
 893             struct $forward_iterator:ident;
 894
 895         // Reverse iterator
 896         reverse:
 897             $(#[$reverse_iterator_attribute:meta])*
 898             struct $reverse_iterator:ident;
 899
 900         // Stability of all generated items
 901         stability:
 902             $(#[$common_stability_attribute:meta])*
 903
 904         // Internal almost-iterator that is being delegated to
 905         internal:
 906             $internal_iterator:ident yielding ($iterty:ty);
 907
 908         // Kind of delegation - either single ended or double ended
 909         delegate $($t:tt)*
 910     } => {
 911         $(#[$forward_iterator_attribute])*
 912         $(#[$common_stability_attribute])*
 913         pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 914
 915         $(#[$common_stability_attribute])*
 916         impl<'a, P: Pattern<'a>> fmt::Debug for $forward_iterator<'a, P>
 917             where P::Searcher: fmt::Debug
 918         {
 919             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 920                 f.debug_tuple(stringify!($forward_iterator))
 921                     .field(&self.0)
 922                     .finish()
 923             }
 924         }
 925
 926         $(#[$common_stability_attribute])*
 927         impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
 928             type Item = $iterty;
 929
 930             #[inline]
 931             fn next(&mut self) -> Option<$iterty> {
 932                 self.0.next()
 933             }
 934         }
 935
 936         $(#[$common_stability_attribute])*
 937         impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
 938             where P::Searcher: Clone
 939         {
 940             fn clone(&self) -> Self {
 941                 $forward_iterator(self.0.clone())
 942             }
 943         }
 944
 945         $(#[$reverse_iterator_attribute])*
 946         $(#[$common_stability_attribute])*
 947         pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 948
 949         $(#[$common_stability_attribute])*
 950         impl<'a, P: Pattern<'a>> fmt::Debug for $reverse_iterator<'a, P>
 951             where P::Searcher: fmt::Debug
 952         {
 953             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 954                 f.debug_tuple(stringify!($reverse_iterator))
 955                     .field(&self.0)
 956                     .finish()
 957             }
 958         }
 959
 960         $(#[$common_stability_attribute])*
 961         impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
 962             where P::Searcher: ReverseSearcher<'a>
 963         {
 964             type Item = $iterty;
 965
 966             #[inline]
 967             fn next(&mut self) -> Option<$iterty> {
 968                 self.0.next_back()
 969             }
 970         }
 971
 972         $(#[$common_stability_attribute])*
 973         impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
 974             where P::Searcher: Clone
 975         {
 976             fn clone(&self) -> Self {
 977                 $reverse_iterator(self.0.clone())
 978             }
 979         }
 980
 981         #[unstable(feature = "fused", issue = "35602")]
 982         impl<'a, P: Pattern<'a>> FusedIterator for $forward_iterator<'a, P> {}
 983
 984         #[unstable(feature = "fused", issue = "35602")]
 985         impl<'a, P: Pattern<'a>> FusedIterator for $reverse_iterator<'a, P>
 986             where P::Searcher: ReverseSearcher<'a> {}
 987
 988         generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
 989                                                 $forward_iterator,
 990                                                 $reverse_iterator, $iterty);
 991     };
 992     {
 993         double ended; with $(#[$common_stability_attribute:meta])*,
 994                            $forward_iterator:ident,
 995                            $reverse_iterator:ident, $iterty:ty
 996     } => {
 997         $(#[$common_stability_attribute])*
 998         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
 999             where P::Searcher: DoubleEndedSearcher<'a>
1000         {
1001             #[inline]
1002             fn next_back(&mut self) -> Option<$iterty> {
1003                 self.0.next_back()
1004             }
1005         }
1006
1007         $(#[$common_stability_attribute])*
1008         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
1009             where P::Searcher: DoubleEndedSearcher<'a>
1010         {
1011             #[inline]
1012             fn next_back(&mut self) -> Option<$iterty> {
1013                 self.0.next()
1014             }
1015         }
1016     };
1017     {
1018         single ended; with $(#[$common_stability_attribute:meta])*,
1019                            $forward_iterator:ident,
1020                            $reverse_iterator:ident, $iterty:ty
1021     } => {}
1022 }
1023
1024 derive_pattern_clone!{
1025     clone SplitInternal
1026     with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
1027 }
1028
1029 struct SplitInternal<'a, P: Pattern<'a>> {
1030     start: usize,
1031     end: usize,
1032     matcher: P::Searcher,
1033     allow_trailing_empty: bool,
1034     finished: bool,
1035 }
1036
1037 impl<'a, P: Pattern<'a>> fmt::Debug for SplitInternal<'a, P> where P::Searcher: fmt::Debug {
1038     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1039         f.debug_struct("SplitInternal")
1040             .field("start", &self.start)
1041             .field("end", &self.end)
1042             .field("matcher", &self.matcher)
1043             .field("allow_trailing_empty", &self.allow_trailing_empty)
1044             .field("finished", &self.finished)
1045             .finish()
1046     }
1047 }
1048
1049 impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
1050     #[inline]
1051     fn get_end(&mut self) -> Option<&'a str> {
1052         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
1053             self.finished = true;
1054             unsafe {
1055                 let string = self.matcher.haystack().slice_unchecked(self.start, self.end);
1056                 Some(string)
1057             }
1058         } else {
1059             None
1060         }
1061     }
1062
1063     #[inline]
1064     fn next(&mut self) -> Option<&'a str> {
1065         if self.finished { return None }
1066
1067         let haystack = self.matcher.haystack();
1068         match self.matcher.next_match() {
1069             Some((a, b)) => unsafe {
1070                 let elt = haystack.slice_unchecked(self.start, a);
1071                 self.start = b;
1072                 Some(elt)
1073             },
1074             None => self.get_end(),
1075         }
1076     }
1077
1078     #[inline]
1079     fn next_back(&mut self) -> Option<&'a str>
1080         where P::Searcher: ReverseSearcher<'a>
1081     {
1082         if self.finished { return None }
1083
1084         if !self.allow_trailing_empty {
1085             self.allow_trailing_empty = true;
1086             match self.next_back() {
1087                 Some(elt) if !elt.is_empty() => return Some(elt),
1088                 _ => if self.finished { return None }
1089             }
1090         }
1091
1092         let haystack = self.matcher.haystack();
1093         match self.matcher.next_match_back() {
1094             Some((a, b)) => unsafe {
1095                 let elt = haystack.slice_unchecked(b, self.end);
1096                 self.end = a;
1097                 Some(elt)
1098             },
1099             None => unsafe {
1100                 self.finished = true;
1101                 Some(haystack.slice_unchecked(self.start, self.end))
1102             },
1103         }
1104     }
1105 }
1106
1107 generate_pattern_iterators! {
1108     forward:
1109         /// Created with the method [`split`].
1110         ///
1111         /// [`split`]: ../../std/primitive.str.html#method.split
1112         struct Split;
1113     reverse:
1114         /// Created with the method [`rsplit`].
1115         ///
1116         /// [`rsplit`]: ../../std/primitive.str.html#method.rsplit
1117         struct RSplit;
1118     stability:
1119         #[stable(feature = "rust1", since = "1.0.0")]
1120     internal:
1121         SplitInternal yielding (&'a str);
1122     delegate double ended;
1123 }
1124
1125 generate_pattern_iterators! {
1126     forward:
1127         /// Created with the method [`split_terminator`].
1128         ///
1129         /// [`split_terminator`]: ../../std/primitive.str.html#method.split_terminator
1130         struct SplitTerminator;
1131     reverse:
1132         /// Created with the method [`rsplit_terminator`].
1133         ///
1134         /// [`rsplit_terminator`]: ../../std/primitive.str.html#method.rsplit_terminator
1135         struct RSplitTerminator;
1136     stability:
1137         #[stable(feature = "rust1", since = "1.0.0")]
1138     internal:
1139         SplitInternal yielding (&'a str);
1140     delegate double ended;
1141 }
1142
1143 derive_pattern_clone!{
1144     clone SplitNInternal
1145     with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
1146 }
1147
1148 struct SplitNInternal<'a, P: Pattern<'a>> {
1149     iter: SplitInternal<'a, P>,
1150     /// The number of splits remaining
1151     count: usize,
1152 }
1153
1154 impl<'a, P: Pattern<'a>> fmt::Debug for SplitNInternal<'a, P> where P::Searcher: fmt::Debug {
1155     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1156         f.debug_struct("SplitNInternal")
1157             .field("iter", &self.iter)
1158             .field("count", &self.count)
1159             .finish()
1160     }
1161 }
1162
1163 impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
1164     #[inline]
1165     fn next(&mut self) -> Option<&'a str> {
1166         match self.count {
1167             0 => None,
1168             1 => { self.count = 0; self.iter.get_end() }
1169             _ => { self.count -= 1; self.iter.next() }
1170         }
1171     }
1172
1173     #[inline]
1174     fn next_back(&mut self) -> Option<&'a str>
1175         where P::Searcher: ReverseSearcher<'a>
1176     {
1177         match self.count {
1178             0 => None,
1179             1 => { self.count = 0; self.iter.get_end() }
1180             _ => { self.count -= 1; self.iter.next_back() }
1181         }
1182     }
1183 }
1184
1185 generate_pattern_iterators! {
1186     forward:
1187         /// Created with the method [`splitn`].
1188         ///
1189         /// [`splitn`]: ../../std/primitive.str.html#method.splitn
1190         struct SplitN;
1191     reverse:
1192         /// Created with the method [`rsplitn`].
1193         ///
1194         /// [`rsplitn`]: ../../std/primitive.str.html#method.rsplitn
1195         struct RSplitN;
1196     stability:
1197         #[stable(feature = "rust1", since = "1.0.0")]
1198     internal:
1199         SplitNInternal yielding (&'a str);
1200     delegate single ended;
1201 }
1202
1203 derive_pattern_clone!{
1204     clone MatchIndicesInternal
1205     with |s| MatchIndicesInternal(s.0.clone())
1206 }
1207
1208 struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
1209
1210 impl<'a, P: Pattern<'a>> fmt::Debug for MatchIndicesInternal<'a, P> where P::Searcher: fmt::Debug {
1211     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1212         f.debug_tuple("MatchIndicesInternal")
1213             .field(&self.0)
1214             .finish()
1215     }
1216 }
1217
1218 impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
1219     #[inline]
1220     fn next(&mut self) -> Option<(usize, &'a str)> {
1221         self.0.next_match().map(|(start, end)| unsafe {
1222             (start, self.0.haystack().slice_unchecked(start, end))
1223         })
1224     }
1225
1226     #[inline]
1227     fn next_back(&mut self) -> Option<(usize, &'a str)>
1228         where P::Searcher: ReverseSearcher<'a>
1229     {
1230         self.0.next_match_back().map(|(start, end)| unsafe {
1231             (start, self.0.haystack().slice_unchecked(start, end))
1232         })
1233     }
1234 }
1235
1236 generate_pattern_iterators! {
1237     forward:
1238         /// Created with the method [`match_indices`].
1239         ///
1240         /// [`match_indices`]: ../../std/primitive.str.html#method.match_indices
1241         struct MatchIndices;
1242     reverse:
1243         /// Created with the method [`rmatch_indices`].
1244         ///
1245         /// [`rmatch_indices`]: ../../std/primitive.str.html#method.rmatch_indices
1246         struct RMatchIndices;
1247     stability:
1248         #[stable(feature = "str_match_indices", since = "1.5.0")]
1249     internal:
1250         MatchIndicesInternal yielding ((usize, &'a str));
1251     delegate double ended;
1252 }
1253
1254 derive_pattern_clone!{
1255     clone MatchesInternal
1256     with |s| MatchesInternal(s.0.clone())
1257 }
1258
1259 struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
1260
1261 impl<'a, P: Pattern<'a>> fmt::Debug for MatchesInternal<'a, P> where P::Searcher: fmt::Debug {
1262     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1263         f.debug_tuple("MatchesInternal")
1264             .field(&self.0)
1265             .finish()
1266     }
1267 }
1268
1269 impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
1270     #[inline]
1271     fn next(&mut self) -> Option<&'a str> {
1272         self.0.next_match().map(|(a, b)| unsafe {
1273             // Indices are known to be on utf8 boundaries
1274             self.0.haystack().slice_unchecked(a, b)
1275         })
1276     }
1277
1278     #[inline]
1279     fn next_back(&mut self) -> Option<&'a str>
1280         where P::Searcher: ReverseSearcher<'a>
1281     {
1282         self.0.next_match_back().map(|(a, b)| unsafe {
1283             // Indices are known to be on utf8 boundaries
1284             self.0.haystack().slice_unchecked(a, b)
1285         })
1286     }
1287 }
1288
1289 generate_pattern_iterators! {
1290     forward:
1291         /// Created with the method [`matches`].
1292         ///
1293         /// [`matches`]: ../../std/primitive.str.html#method.matches
1294         struct Matches;
1295     reverse:
1296         /// Created with the method [`rmatches`].
1297         ///
1298         /// [`rmatches`]: ../../std/primitive.str.html#method.rmatches
1299         struct RMatches;
1300     stability:
1301         #[stable(feature = "str_matches", since = "1.2.0")]
1302     internal:
1303         MatchesInternal yielding (&'a str);
1304     delegate double ended;
1305 }
1306
1307 /// An iterator over the lines of a string, as string slices.
1308 ///
1309 /// This struct is created with the [`lines`] method on [`str`].
1310 /// See its documentation for more.
1311 ///
1312 /// [`lines`]: ../../std/primitive.str.html#method.lines
1313 /// [`str`]: ../../std/primitive.str.html
1314 #[stable(feature = "rust1", since = "1.0.0")]
1315 #[derive(Clone, Debug)]
1316 pub struct Lines<'a>(Map<SplitTerminator<'a, char>, LinesAnyMap>);
1317
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 impl<'a> Iterator for Lines<'a> {
1320     type Item = &'a str;
1321
1322     #[inline]
1323     fn next(&mut self) -> Option<&'a str> {
1324         self.0.next()
1325     }
1326
1327     #[inline]
1328     fn size_hint(&self) -> (usize, Option<usize>) {
1329         self.0.size_hint()
1330     }
1331 }
1332
1333 #[stable(feature = "rust1", since = "1.0.0")]
1334 impl<'a> DoubleEndedIterator for Lines<'a> {
1335     #[inline]
1336     fn next_back(&mut self) -> Option<&'a str> {
1337         self.0.next_back()
1338     }
1339 }
1340
1341 #[unstable(feature = "fused", issue = "35602")]
1342 impl<'a> FusedIterator for Lines<'a> {}
1343
1344 /// Created with the method [`lines_any`].
1345 ///
1346 /// [`lines_any`]: ../../std/primitive.str.html#method.lines_any
1347 #[stable(feature = "rust1", since = "1.0.0")]
1348 #[rustc_deprecated(since = "1.4.0", reason = "use lines()/Lines instead now")]
1349 #[derive(Clone, Debug)]
1350 #[allow(deprecated)]
1351 pub struct LinesAny<'a>(Lines<'a>);
1352
1353 /// A nameable, cloneable fn type
1354 #[derive(Clone)]
1355 struct LinesAnyMap;
1356
1357 impl<'a> Fn<(&'a str,)> for LinesAnyMap {
1358     #[inline]
1359     extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
1360         let l = line.len();
1361         if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
1362         else { line }
1363     }
1364 }
1365
1366 impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
1367     #[inline]
1368     extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
1369         Fn::call(&*self, (line,))
1370     }
1371 }
1372
1373 impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
1374     type Output = &'a str;
1375
1376     #[inline]
1377     extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
1378         Fn::call(&self, (line,))
1379     }
1380 }
1381
1382 #[stable(feature = "rust1", since = "1.0.0")]
1383 #[allow(deprecated)]
1384 impl<'a> Iterator for LinesAny<'a> {
1385     type Item = &'a str;
1386
1387     #[inline]
1388     fn next(&mut self) -> Option<&'a str> {
1389         self.0.next()
1390     }
1391
1392     #[inline]
1393     fn size_hint(&self) -> (usize, Option<usize>) {
1394         self.0.size_hint()
1395     }
1396 }
1397
1398 #[stable(feature = "rust1", since = "1.0.0")]
1399 #[allow(deprecated)]
1400 impl<'a> DoubleEndedIterator for LinesAny<'a> {
1401     #[inline]
1402     fn next_back(&mut self) -> Option<&'a str> {
1403         self.0.next_back()
1404     }
1405 }
1406
1407 #[unstable(feature = "fused", issue = "35602")]
1408 #[allow(deprecated)]
1409 impl<'a> FusedIterator for LinesAny<'a> {}
1410
1411 /*
1412 Section: UTF-8 validation
1413 */
1414
1415 // use truncation to fit u64 into usize
1416 const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;
1417
1418 /// Returns `true` if any byte in the word `x` is nonascii (>= 128).
1419 #[inline]
1420 fn contains_nonascii(x: usize) -> bool {
1421     (x & NONASCII_MASK) != 0
1422 }
1423
1424 /// Walks through `iter` checking that it's a valid UTF-8 sequence,
1425 /// returning `true` in that case, or, if it is invalid, `false` with
1426 /// `iter` reset such that it is pointing at the first byte in the
1427 /// invalid sequence.
1428 #[inline]
1429 fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
1430     let mut index = 0;
1431     let len = v.len();
1432
1433     let usize_bytes = mem::size_of::<usize>();
1434     let ascii_block_size = 2 * usize_bytes;
1435     let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
1436
1437     while index < len {
1438         let old_offset = index;
1439         macro_rules! err {
1440             ($error_len: expr) => {
1441                 return Err(Utf8Error {
1442                     valid_up_to: old_offset,
1443                     error_len: $error_len,
1444                 })
1445             }
1446         }
1447
1448         macro_rules! next { () => {{
1449             index += 1;
1450             // we needed data, but there was none: error!
1451             if index >= len {
1452                 err!(None)
1453             }
1454             v[index]
1455         }}}
1456
1457         let first = v[index];
1458         if first >= 128 {
1459             let w = UTF8_CHAR_WIDTH[first as usize];
1460             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
1461             //        first  C2 80        last DF BF
1462             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
1463             //        first  E0 A0 80     last EF BF BF
1464             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
1465             //               ED A0 80 to       ED BF BF
1466             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1467             //        first  F0 90 80 80  last F4 8F BF BF
1468             //
1469             // Use the UTF-8 syntax from the RFC
1470             //
1471             // https://tools.ietf.org/html/rfc3629
1472             // UTF8-1      = %x00-7F
1473             // UTF8-2      = %xC2-DF UTF8-tail
1474             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1475             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1476             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1477             //               %xF4 %x80-8F 2( UTF8-tail )
1478             match w {
1479                 2 => if next!() & !CONT_MASK != TAG_CONT_U8 {
1480                     err!(Some(1))
1481                 },
1482                 3 => {
1483                     match (first, next!()) {
1484                         (0xE0         , 0xA0 ... 0xBF) |
1485                         (0xE1 ... 0xEC, 0x80 ... 0xBF) |
1486                         (0xED         , 0x80 ... 0x9F) |
1487                         (0xEE ... 0xEF, 0x80 ... 0xBF) => {}
1488                         _ => err!(Some(1))
1489                     }
1490                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1491                         err!(Some(2))
1492                     }
1493                 }
1494                 4 => {
1495                     match (first, next!()) {
1496                         (0xF0         , 0x90 ... 0xBF) |
1497                         (0xF1 ... 0xF3, 0x80 ... 0xBF) |
1498                         (0xF4         , 0x80 ... 0x8F) => {}
1499                         _ => err!(Some(1))
1500                     }
1501                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1502                         err!(Some(2))
1503                     }
1504                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1505                         err!(Some(3))
1506                     }
1507                 }
1508                 _ => err!(Some(1))
1509             }
1510             index += 1;
1511         } else {
1512             // Ascii case, try to skip forward quickly.
1513             // When the pointer is aligned, read 2 words of data per iteration
1514             // until we find a word containing a non-ascii byte.
1515             let ptr = v.as_ptr();
1516             let align = unsafe {
1517                 // the offset is safe, because `index` is guaranteed inbounds
1518                 ptr.offset(index as isize).align_offset(usize_bytes)
1519             };
1520             if align == 0 {
1521                 while index < blocks_end {
1522                     unsafe {
1523                         let block = ptr.offset(index as isize) as *const usize;
1524                         // break if there is a nonascii byte
1525                         let zu = contains_nonascii(*block);
1526                         let zv = contains_nonascii(*block.offset(1));
1527                         if zu | zv {
1528                             break;
1529                         }
1530                     }
1531                     index += ascii_block_size;
1532                 }
1533                 // step from the point where the wordwise loop stopped
1534                 while index < len && v[index] < 128 {
1535                     index += 1;
1536                 }
1537             } else {
1538                 index += 1;
1539             }
1540         }
1541     }
1542
1543     Ok(())
1544 }
1545
1546 // https://tools.ietf.org/html/rfc3629
1547 static UTF8_CHAR_WIDTH: [u8; 256] = [
1548 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1549 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1550 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1551 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1552 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1553 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1554 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1555 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1556 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1557 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1558 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1559 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1560 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1561 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1562 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1563 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1564 ];
1565
1566 /// Given a first byte, determines how many bytes are in this UTF-8 character.
1567 #[unstable(feature = "str_internals", issue = "0")]
1568 #[inline]
1569 pub fn utf8_char_width(b: u8) -> usize {
1570     return UTF8_CHAR_WIDTH[b as usize] as usize;
1571 }
1572
1573 /// Mask of the value bits of a continuation byte.
1574 const CONT_MASK: u8 = 0b0011_1111;
1575 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte.
1576 const TAG_CONT_U8: u8 = 0b1000_0000;
1577
1578 /*
1579 Section: Trait implementations
1580 */
1581
1582 mod traits {
1583     use cmp::Ordering;
1584     use ops;
1585     use slice::{self, SliceIndex};
1586
1587     /// Implements ordering of strings.
1588     ///
1589     /// Strings are ordered  lexicographically by their byte values.  This orders Unicode code
1590     /// points based on their positions in the code charts.  This is not necessarily the same as
1591     /// "alphabetical" order, which varies by language and locale.  Sorting strings according to
1592     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1593     /// the `str` type.
1594     #[stable(feature = "rust1", since = "1.0.0")]
1595     impl Ord for str {
1596         #[inline]
1597         fn cmp(&self, other: &str) -> Ordering {
1598             self.as_bytes().cmp(other.as_bytes())
1599         }
1600     }
1601
1602     #[stable(feature = "rust1", since = "1.0.0")]
1603     impl PartialEq for str {
1604         #[inline]
1605         fn eq(&self, other: &str) -> bool {
1606             self.as_bytes() == other.as_bytes()
1607         }
1608         #[inline]
1609         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1610     }
1611
1612     #[stable(feature = "rust1", since = "1.0.0")]
1613     impl Eq for str {}
1614
1615     /// Implements comparison operations on strings.
1616     ///
1617     /// Strings are compared lexicographically by their byte values.  This compares Unicode code
1618     /// points based on their positions in the code charts.  This is not necessarily the same as
1619     /// "alphabetical" order, which varies by language and locale.  Comparing strings according to
1620     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1621     /// the `str` type.
1622     #[stable(feature = "rust1", since = "1.0.0")]
1623     impl PartialOrd for str {
1624         #[inline]
1625         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1626             Some(self.cmp(other))
1627         }
1628     }
1629
1630     /// Implements substring slicing with syntax `&self[begin .. end]`.
1631     ///
1632     /// Returns a slice of the given string from the byte range
1633     /// [`begin`..`end`).
1634     ///
1635     /// This operation is `O(1)`.
1636     ///
1637     /// # Panics
1638     ///
1639     /// Panics if `begin` or `end` does not point to the starting
1640     /// byte offset of a character (as defined by `is_char_boundary`).
1641     /// Requires that `begin <= end` and `end <= len` where `len` is the
1642     /// length of the string.
1643     ///
1644     /// # Examples
1645     ///
1646     /// ```
1647     /// let s = "Löwe 老虎 Léopard";
1648     /// assert_eq!(&s[0 .. 1], "L");
1649     ///
1650     /// assert_eq!(&s[1 .. 9], "öwe 老");
1651     ///
1652     /// // these will panic:
1653     /// // byte 2 lies within `ö`:
1654     /// // &s[2 ..3];
1655     ///
1656     /// // byte 8 lies within `老`
1657     /// // &s[1 .. 8];
1658     ///
1659     /// // byte 100 is outside the string
1660     /// // &s[3 .. 100];
1661     /// ```
1662     #[stable(feature = "rust1", since = "1.0.0")]
1663     impl ops::Index<ops::Range<usize>> for str {
1664         type Output = str;
1665         #[inline]
1666         fn index(&self, index: ops::Range<usize>) -> &str {
1667             index.index(self)
1668         }
1669     }
1670
1671     /// Implements mutable substring slicing with syntax
1672     /// `&mut self[begin .. end]`.
1673     ///
1674     /// Returns a mutable slice of the given string from the byte range
1675     /// [`begin`..`end`).
1676     ///
1677     /// This operation is `O(1)`.
1678     ///
1679     /// # Panics
1680     ///
1681     /// Panics if `begin` or `end` does not point to the starting
1682     /// byte offset of a character (as defined by `is_char_boundary`).
1683     /// Requires that `begin <= end` and `end <= len` where `len` is the
1684     /// length of the string.
1685     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1686     impl ops::IndexMut<ops::Range<usize>> for str {
1687         #[inline]
1688         fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
1689             index.index_mut(self)
1690         }
1691     }
1692
1693     /// Implements substring slicing with syntax `&self[.. end]`.
1694     ///
1695     /// Returns a slice of the string from the beginning to byte offset
1696     /// `end`.
1697     ///
1698     /// Equivalent to `&self[0 .. end]`.
1699     #[stable(feature = "rust1", since = "1.0.0")]
1700     impl ops::Index<ops::RangeTo<usize>> for str {
1701         type Output = str;
1702
1703         #[inline]
1704         fn index(&self, index: ops::RangeTo<usize>) -> &str {
1705             index.index(self)
1706         }
1707     }
1708
1709     /// Implements mutable substring slicing with syntax `&mut self[.. end]`.
1710     ///
1711     /// Returns a mutable slice of the string from the beginning to byte offset
1712     /// `end`.
1713     ///
1714     /// Equivalent to `&mut self[0 .. end]`.
1715     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1716     impl ops::IndexMut<ops::RangeTo<usize>> for str {
1717         #[inline]
1718         fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
1719             index.index_mut(self)
1720         }
1721     }
1722
1723     /// Implements substring slicing with syntax `&self[begin ..]`.
1724     ///
1725     /// Returns a slice of the string from byte offset `begin`
1726     /// to the end of the string.
1727     ///
1728     /// Equivalent to `&self[begin .. len]`.
1729     #[stable(feature = "rust1", since = "1.0.0")]
1730     impl ops::Index<ops::RangeFrom<usize>> for str {
1731         type Output = str;
1732
1733         #[inline]
1734         fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1735             index.index(self)
1736         }
1737     }
1738
1739     /// Implements mutable substring slicing with syntax `&mut self[begin ..]`.
1740     ///
1741     /// Returns a mutable slice of the string from byte offset `begin`
1742     /// to the end of the string.
1743     ///
1744     /// Equivalent to `&mut self[begin .. len]`.
1745     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1746     impl ops::IndexMut<ops::RangeFrom<usize>> for str {
1747         #[inline]
1748         fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
1749             index.index_mut(self)
1750         }
1751     }
1752
1753     /// Implements substring slicing with syntax `&self[..]`.
1754     ///
1755     /// Returns a slice of the whole string. This operation can
1756     /// never panic.
1757     ///
1758     /// Equivalent to `&self[0 .. len]`.
1759     #[stable(feature = "rust1", since = "1.0.0")]
1760     impl ops::Index<ops::RangeFull> for str {
1761         type Output = str;
1762
1763         #[inline]
1764         fn index(&self, _index: ops::RangeFull) -> &str {
1765             self
1766         }
1767     }
1768
1769     /// Implements mutable substring slicing with syntax `&mut self[..]`.
1770     ///
1771     /// Returns a mutable slice of the whole string. This operation can
1772     /// never panic.
1773     ///
1774     /// Equivalent to `&mut self[0 .. len]`.
1775     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1776     impl ops::IndexMut<ops::RangeFull> for str {
1777         #[inline]
1778         fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
1779             self
1780         }
1781     }
1782
1783     #[unstable(feature = "inclusive_range",
1784                reason = "recently added, follows RFC",
1785                issue = "28237")]
1786     impl ops::Index<ops::RangeInclusive<usize>> for str {
1787         type Output = str;
1788
1789         #[inline]
1790         fn index(&self, index: ops::RangeInclusive<usize>) -> &str {
1791             index.index(self)
1792         }
1793     }
1794
1795     #[unstable(feature = "inclusive_range",
1796                reason = "recently added, follows RFC",
1797                issue = "28237")]
1798     impl ops::Index<ops::RangeToInclusive<usize>> for str {
1799         type Output = str;
1800
1801         #[inline]
1802         fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
1803             index.index(self)
1804         }
1805     }
1806
1807     #[unstable(feature = "inclusive_range",
1808                reason = "recently added, follows RFC",
1809                issue = "28237")]
1810     impl ops::IndexMut<ops::RangeInclusive<usize>> for str {
1811         #[inline]
1812         fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
1813             index.index_mut(self)
1814         }
1815     }
1816     #[unstable(feature = "inclusive_range",
1817                reason = "recently added, follows RFC",
1818                issue = "28237")]
1819     impl ops::IndexMut<ops::RangeToInclusive<usize>> for str {
1820         #[inline]
1821         fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
1822             index.index_mut(self)
1823         }
1824     }
1825
1826     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1827     impl SliceIndex<str> for ops::RangeFull {
1828         type Output = str;
1829         #[inline]
1830         fn get(self, slice: &str) -> Option<&Self::Output> {
1831             Some(slice)
1832         }
1833         #[inline]
1834         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1835             Some(slice)
1836         }
1837         #[inline]
1838         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1839             slice
1840         }
1841         #[inline]
1842         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1843             slice
1844         }
1845         #[inline]
1846         fn index(self, slice: &str) -> &Self::Output {
1847             slice
1848         }
1849         #[inline]
1850         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1851             slice
1852         }
1853     }
1854
1855     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1856     impl SliceIndex<str> for ops::Range<usize> {
1857         type Output = str;
1858         #[inline]
1859         fn get(self, slice: &str) -> Option<&Self::Output> {
1860             if self.start <= self.end &&
1861                slice.is_char_boundary(self.start) &&
1862                slice.is_char_boundary(self.end) {
1863                 Some(unsafe { self.get_unchecked(slice) })
1864             } else {
1865                 None
1866             }
1867         }
1868         #[inline]
1869         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1870             if self.start <= self.end &&
1871                slice.is_char_boundary(self.start) &&
1872                slice.is_char_boundary(self.end) {
1873                 Some(unsafe { self.get_unchecked_mut(slice) })
1874             } else {
1875                 None
1876             }
1877         }
1878         #[inline]
1879         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1880             let ptr = slice.as_ptr().offset(self.start as isize);
1881             let len = self.end - self.start;
1882             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1883         }
1884         #[inline]
1885         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1886             let ptr = slice.as_ptr().offset(self.start as isize);
1887             let len = self.end - self.start;
1888             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1889         }
1890         #[inline]
1891         fn index(self, slice: &str) -> &Self::Output {
1892             let (start, end) = (self.start, self.end);
1893             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1894         }
1895         #[inline]
1896         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1897             // is_char_boundary checks that the index is in [0, .len()]
1898             // canot reuse `get` as above, because of NLL trouble
1899             if self.start <= self.end &&
1900                slice.is_char_boundary(self.start) &&
1901                slice.is_char_boundary(self.end) {
1902                 unsafe { self.get_unchecked_mut(slice) }
1903             } else {
1904                 super::slice_error_fail(slice, self.start, self.end)
1905             }
1906         }
1907     }
1908
1909     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1910     impl SliceIndex<str> for ops::RangeTo<usize> {
1911         type Output = str;
1912         #[inline]
1913         fn get(self, slice: &str) -> Option<&Self::Output> {
1914             if slice.is_char_boundary(self.end) {
1915                 Some(unsafe { self.get_unchecked(slice) })
1916             } else {
1917                 None
1918             }
1919         }
1920         #[inline]
1921         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1922             if slice.is_char_boundary(self.end) {
1923                 Some(unsafe { self.get_unchecked_mut(slice) })
1924             } else {
1925                 None
1926             }
1927         }
1928         #[inline]
1929         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1930             let ptr = slice.as_ptr();
1931             super::from_utf8_unchecked(slice::from_raw_parts(ptr, self.end))
1932         }
1933         #[inline]
1934         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1935             let ptr = slice.as_ptr();
1936             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, self.end))
1937         }
1938         #[inline]
1939         fn index(self, slice: &str) -> &Self::Output {
1940             let end = self.end;
1941             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, 0, end))
1942         }
1943         #[inline]
1944         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1945             // is_char_boundary checks that the index is in [0, .len()]
1946             if slice.is_char_boundary(self.end) {
1947                 unsafe { self.get_unchecked_mut(slice) }
1948             } else {
1949                 super::slice_error_fail(slice, 0, self.end)
1950             }
1951         }
1952     }
1953
1954     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1955     impl SliceIndex<str> for ops::RangeFrom<usize> {
1956         type Output = str;
1957         #[inline]
1958         fn get(self, slice: &str) -> Option<&Self::Output> {
1959             if slice.is_char_boundary(self.start) {
1960                 Some(unsafe { self.get_unchecked(slice) })
1961             } else {
1962                 None
1963             }
1964         }
1965         #[inline]
1966         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1967             if slice.is_char_boundary(self.start) {
1968                 Some(unsafe { self.get_unchecked_mut(slice) })
1969             } else {
1970                 None
1971             }
1972         }
1973         #[inline]
1974         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1975             let ptr = slice.as_ptr().offset(self.start as isize);
1976             let len = slice.len() - self.start;
1977             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1978         }
1979         #[inline]
1980         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1981             let ptr = slice.as_ptr().offset(self.start as isize);
1982             let len = slice.len() - self.start;
1983             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1984         }
1985         #[inline]
1986         fn index(self, slice: &str) -> &Self::Output {
1987             let (start, end) = (self.start, slice.len());
1988             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1989         }
1990         #[inline]
1991         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1992             // is_char_boundary checks that the index is in [0, .len()]
1993             if slice.is_char_boundary(self.start) {
1994                 unsafe { self.get_unchecked_mut(slice) }
1995             } else {
1996                 super::slice_error_fail(slice, self.start, slice.len())
1997             }
1998         }
1999     }
2000
2001     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2002     impl SliceIndex<str> for ops::RangeInclusive<usize> {
2003         type Output = str;
2004         #[inline]
2005         fn get(self, slice: &str) -> Option<&Self::Output> {
2006             if let Some(end) = self.end.checked_add(1) {
2007                 (self.start..end).get(slice)
2008             } else {
2009                 None
2010             }
2011         }
2012         #[inline]
2013         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2014             if let Some(end) = self.end.checked_add(1) {
2015                 (self.start..end).get_mut(slice)
2016             } else {
2017                 None
2018             }
2019         }
2020         #[inline]
2021         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2022             (self.start..self.end+1).get_unchecked(slice)
2023         }
2024         #[inline]
2025         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2026             (self.start..self.end+1).get_unchecked_mut(slice)
2027         }
2028         #[inline]
2029         fn index(self, slice: &str) -> &Self::Output {
2030             assert!(self.end != usize::max_value(),
2031                 "attempted to index str up to maximum usize");
2032             (self.start..self.end+1).index(slice)
2033         }
2034         #[inline]
2035         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2036             assert!(self.end != usize::max_value(),
2037                 "attempted to index str up to maximum usize");
2038             (self.start..self.end+1).index_mut(slice)
2039         }
2040     }
2041
2042
2043
2044     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2045     impl SliceIndex<str> for ops::RangeToInclusive<usize> {
2046         type Output = str;
2047         #[inline]
2048         fn get(self, slice: &str) -> Option<&Self::Output> {
2049             if self.end < usize::max_value() && slice.is_char_boundary(self.end + 1) {
2050                 Some(unsafe { self.get_unchecked(slice) })
2051             } else {
2052                 None
2053             }
2054         }
2055         #[inline]
2056         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2057             if self.end < usize::max_value() && slice.is_char_boundary(self.end + 1) {
2058                 Some(unsafe { self.get_unchecked_mut(slice) })
2059             } else {
2060                 None
2061             }
2062         }
2063         #[inline]
2064         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2065             let ptr = slice.as_ptr();
2066             super::from_utf8_unchecked(slice::from_raw_parts(ptr, self.end + 1))
2067         }
2068         #[inline]
2069         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2070             let ptr = slice.as_ptr();
2071             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, self.end + 1))
2072         }
2073         #[inline]
2074         fn index(self, slice: &str) -> &Self::Output {
2075             assert!(self.end != usize::max_value(),
2076                 "attempted to index str up to maximum usize");
2077             let end = self.end + 1;
2078             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, 0, end))
2079         }
2080         #[inline]
2081         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2082             assert!(self.end != usize::max_value(),
2083                 "attempted to index str up to maximum usize");
2084             if slice.is_char_boundary(self.end) {
2085                 unsafe { self.get_unchecked_mut(slice) }
2086             } else {
2087                 super::slice_error_fail(slice, 0, self.end + 1)
2088             }
2089         }
2090     }
2091
2092 }
2093
2094
2095 /// Methods for string slices
2096 #[allow(missing_docs)]
2097 #[doc(hidden)]
2098 #[unstable(feature = "core_str_ext",
2099            reason = "stable interface provided by `impl str` in later crates",
2100            issue = "32110")]
2101 pub trait StrExt {
2102     // NB there are no docs here are they're all located on the StrExt trait in
2103     // liballoc, not here.
2104
2105     #[stable(feature = "core", since = "1.6.0")]
2106     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
2107     #[stable(feature = "core", since = "1.6.0")]
2108     fn chars(&self) -> Chars;
2109     #[stable(feature = "core", since = "1.6.0")]
2110     fn bytes(&self) -> Bytes;
2111     #[stable(feature = "core", since = "1.6.0")]
2112     fn char_indices(&self) -> CharIndices;
2113     #[stable(feature = "core", since = "1.6.0")]
2114     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P>;
2115     #[stable(feature = "core", since = "1.6.0")]
2116     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
2117         where P::Searcher: ReverseSearcher<'a>;
2118     #[stable(feature = "core", since = "1.6.0")]
2119     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P>;
2120     #[stable(feature = "core", since = "1.6.0")]
2121     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
2122         where P::Searcher: ReverseSearcher<'a>;
2123     #[stable(feature = "core", since = "1.6.0")]
2124     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P>;
2125     #[stable(feature = "core", since = "1.6.0")]
2126     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
2127         where P::Searcher: ReverseSearcher<'a>;
2128     #[stable(feature = "core", since = "1.6.0")]
2129     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P>;
2130     #[stable(feature = "core", since = "1.6.0")]
2131     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
2132         where P::Searcher: ReverseSearcher<'a>;
2133     #[stable(feature = "core", since = "1.6.0")]
2134     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P>;
2135     #[stable(feature = "core", since = "1.6.0")]
2136     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
2137         where P::Searcher: ReverseSearcher<'a>;
2138     #[stable(feature = "core", since = "1.6.0")]
2139     fn lines(&self) -> Lines;
2140     #[stable(feature = "core", since = "1.6.0")]
2141     #[rustc_deprecated(since = "1.6.0", reason = "use lines() instead now")]
2142     #[allow(deprecated)]
2143     fn lines_any(&self) -> LinesAny;
2144     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2145     fn get<I: SliceIndex<str>>(&self, i: I) -> Option<&I::Output>;
2146     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2147     fn get_mut<I: SliceIndex<str>>(&mut self, i: I) -> Option<&mut I::Output>;
2148     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2149     unsafe fn get_unchecked<I: SliceIndex<str>>(&self, i: I) -> &I::Output;
2150     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2151     unsafe fn get_unchecked_mut<I: SliceIndex<str>>(&mut self, i: I) -> &mut I::Output;
2152     #[stable(feature = "core", since = "1.6.0")]
2153     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str;
2154     #[stable(feature = "core", since = "1.6.0")]
2155     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str;
2156     #[stable(feature = "core", since = "1.6.0")]
2157     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
2158     #[stable(feature = "core", since = "1.6.0")]
2159     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
2160         where P::Searcher: ReverseSearcher<'a>;
2161     #[stable(feature = "core", since = "1.6.0")]
2162     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2163         where P::Searcher: DoubleEndedSearcher<'a>;
2164     #[stable(feature = "core", since = "1.6.0")]
2165     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str;
2166     #[stable(feature = "core", since = "1.6.0")]
2167     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2168         where P::Searcher: ReverseSearcher<'a>;
2169     #[stable(feature = "is_char_boundary", since = "1.9.0")]
2170     fn is_char_boundary(&self, index: usize) -> bool;
2171     #[stable(feature = "core", since = "1.6.0")]
2172     fn as_bytes(&self) -> &[u8];
2173     #[stable(feature = "str_mut_extras", since = "1.20.0")]
2174     unsafe fn as_bytes_mut(&mut self) -> &mut [u8];
2175     #[stable(feature = "core", since = "1.6.0")]
2176     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
2177     #[stable(feature = "core", since = "1.6.0")]
2178     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
2179         where P::Searcher: ReverseSearcher<'a>;
2180     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
2181     #[stable(feature = "core", since = "1.6.0")]
2182     fn split_at(&self, mid: usize) -> (&str, &str);
2183     #[stable(feature = "core", since = "1.6.0")]
2184     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str);
2185     #[stable(feature = "core", since = "1.6.0")]
2186     fn as_ptr(&self) -> *const u8;
2187     #[stable(feature = "core", since = "1.6.0")]
2188     fn len(&self) -> usize;
2189     #[stable(feature = "core", since = "1.6.0")]
2190     fn is_empty(&self) -> bool;
2191     #[stable(feature = "core", since = "1.6.0")]
2192     fn parse<T: FromStr>(&self) -> Result<T, T::Err>;
2193 }
2194
2195 // truncate `&str` to length at most equal to `max`
2196 // return `true` if it were truncated, and the new str.
2197 fn truncate_to_char_boundary(s: &str, mut max: usize) -> (bool, &str) {
2198     if max >= s.len() {
2199         (false, s)
2200     } else {
2201         while !s.is_char_boundary(max) {
2202             max -= 1;
2203         }
2204         (true, &s[..max])
2205     }
2206 }
2207
2208 #[inline(never)]
2209 #[cold]
2210 fn slice_error_fail(s: &str, begin: usize, end: usize) -> ! {
2211     const MAX_DISPLAY_LENGTH: usize = 256;
2212     let (truncated, s_trunc) = truncate_to_char_boundary(s, MAX_DISPLAY_LENGTH);
2213     let ellipsis = if truncated { "[...]" } else { "" };
2214
2215     // 1. out of bounds
2216     if begin > s.len() || end > s.len() {
2217         let oob_index = if begin > s.len() { begin } else { end };
2218         panic!("byte index {} is out of bounds of `{}`{}", oob_index, s_trunc, ellipsis);
2219     }
2220
2221     // 2. begin <= end
2222     assert!(begin <= end, "begin <= end ({} <= {}) when slicing `{}`{}",
2223             begin, end, s_trunc, ellipsis);
2224
2225     // 3. character boundary
2226     let index = if !s.is_char_boundary(begin) { begin } else { end };
2227     // find the character
2228     let mut char_start = index;
2229     while !s.is_char_boundary(char_start) {
2230         char_start -= 1;
2231     }
2232     // `char_start` must be less than len and a char boundary
2233     let ch = s[char_start..].chars().next().unwrap();
2234     let char_range = char_start .. char_start + ch.len_utf8();
2235     panic!("byte index {} is not a char boundary; it is inside {:?} (bytes {:?}) of `{}`{}",
2236            index, ch, char_range, s_trunc, ellipsis);
2237 }
2238
2239 #[stable(feature = "core", since = "1.6.0")]
2240 impl StrExt for str {
2241     #[inline]
2242     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2243         pat.is_contained_in(self)
2244     }
2245
2246     #[inline]
2247     fn chars(&self) -> Chars {
2248         Chars{iter: self.as_bytes().iter()}
2249     }
2250
2251     #[inline]
2252     fn bytes(&self) -> Bytes {
2253         Bytes(self.as_bytes().iter().cloned())
2254     }
2255
2256     #[inline]
2257     fn char_indices(&self) -> CharIndices {
2258         CharIndices { front_offset: 0, iter: self.chars() }
2259     }
2260
2261     #[inline]
2262     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
2263         Split(SplitInternal {
2264             start: 0,
2265             end: self.len(),
2266             matcher: pat.into_searcher(self),
2267             allow_trailing_empty: true,
2268             finished: false,
2269         })
2270     }
2271
2272     #[inline]
2273     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
2274         where P::Searcher: ReverseSearcher<'a>
2275     {
2276         RSplit(self.split(pat).0)
2277     }
2278
2279     #[inline]
2280     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
2281         SplitN(SplitNInternal {
2282             iter: self.split(pat).0,
2283             count,
2284         })
2285     }
2286
2287     #[inline]
2288     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
2289         where P::Searcher: ReverseSearcher<'a>
2290     {
2291         RSplitN(self.splitn(count, pat).0)
2292     }
2293
2294     #[inline]
2295     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
2296         SplitTerminator(SplitInternal {
2297             allow_trailing_empty: false,
2298             ..self.split(pat).0
2299         })
2300     }
2301
2302     #[inline]
2303     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
2304         where P::Searcher: ReverseSearcher<'a>
2305     {
2306         RSplitTerminator(self.split_terminator(pat).0)
2307     }
2308
2309     #[inline]
2310     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
2311         Matches(MatchesInternal(pat.into_searcher(self)))
2312     }
2313
2314     #[inline]
2315     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
2316         where P::Searcher: ReverseSearcher<'a>
2317     {
2318         RMatches(self.matches(pat).0)
2319     }
2320
2321     #[inline]
2322     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
2323         MatchIndices(MatchIndicesInternal(pat.into_searcher(self)))
2324     }
2325
2326     #[inline]
2327     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
2328         where P::Searcher: ReverseSearcher<'a>
2329     {
2330         RMatchIndices(self.match_indices(pat).0)
2331     }
2332     #[inline]
2333     fn lines(&self) -> Lines {
2334         Lines(self.split_terminator('\n').map(LinesAnyMap))
2335     }
2336
2337     #[inline]
2338     #[allow(deprecated)]
2339     fn lines_any(&self) -> LinesAny {
2340         LinesAny(self.lines())
2341     }
2342
2343     #[inline]
2344     fn get<I: SliceIndex<str>>(&self, i: I) -> Option<&I::Output> {
2345         i.get(self)
2346     }
2347
2348     #[inline]
2349     fn get_mut<I: SliceIndex<str>>(&mut self, i: I) -> Option<&mut I::Output> {
2350         i.get_mut(self)
2351     }
2352
2353     #[inline]
2354     unsafe fn get_unchecked<I: SliceIndex<str>>(&self, i: I) -> &I::Output {
2355         i.get_unchecked(self)
2356     }
2357
2358     #[inline]
2359     unsafe fn get_unchecked_mut<I: SliceIndex<str>>(&mut self, i: I) -> &mut I::Output {
2360         i.get_unchecked_mut(self)
2361     }
2362
2363     #[inline]
2364     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str {
2365         (begin..end).get_unchecked(self)
2366     }
2367
2368     #[inline]
2369     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str {
2370         (begin..end).get_unchecked_mut(self)
2371     }
2372
2373     #[inline]
2374     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2375         pat.is_prefix_of(self)
2376     }
2377
2378     #[inline]
2379     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
2380         where P::Searcher: ReverseSearcher<'a>
2381     {
2382         pat.is_suffix_of(self)
2383     }
2384
2385     #[inline]
2386     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2387         where P::Searcher: DoubleEndedSearcher<'a>
2388     {
2389         let mut i = 0;
2390         let mut j = 0;
2391         let mut matcher = pat.into_searcher(self);
2392         if let Some((a, b)) = matcher.next_reject() {
2393             i = a;
2394             j = b; // Remember earliest known match, correct it below if
2395                    // last match is different
2396         }
2397         if let Some((_, b)) = matcher.next_reject_back() {
2398             j = b;
2399         }
2400         unsafe {
2401             // Searcher is known to return valid indices
2402             self.slice_unchecked(i, j)
2403         }
2404     }
2405
2406     #[inline]
2407     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str {
2408         let mut i = self.len();
2409         let mut matcher = pat.into_searcher(self);
2410         if let Some((a, _)) = matcher.next_reject() {
2411             i = a;
2412         }
2413         unsafe {
2414             // Searcher is known to return valid indices
2415             self.slice_unchecked(i, self.len())
2416         }
2417     }
2418
2419     #[inline]
2420     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2421         where P::Searcher: ReverseSearcher<'a>
2422     {
2423         let mut j = 0;
2424         let mut matcher = pat.into_searcher(self);
2425         if let Some((_, b)) = matcher.next_reject_back() {
2426             j = b;
2427         }
2428         unsafe {
2429             // Searcher is known to return valid indices
2430             self.slice_unchecked(0, j)
2431         }
2432     }
2433
2434     #[inline]
2435     fn is_char_boundary(&self, index: usize) -> bool {
2436         // 0 and len are always ok.
2437         // Test for 0 explicitly so that it can optimize out the check
2438         // easily and skip reading string data for that case.
2439         if index == 0 || index == self.len() { return true; }
2440         match self.as_bytes().get(index) {
2441             None => false,
2442             // This is bit magic equivalent to: b < 128 || b >= 192
2443             Some(&b) => (b as i8) >= -0x40,
2444         }
2445     }
2446
2447     #[inline]
2448     fn as_bytes(&self) -> &[u8] {
2449         unsafe { &*(self as *const str as *const [u8]) }
2450     }
2451
2452     #[inline]
2453     unsafe fn as_bytes_mut(&mut self) -> &mut [u8] {
2454         &mut *(self as *mut str as *mut [u8])
2455     }
2456
2457     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
2458         pat.into_searcher(self).next_match().map(|(i, _)| i)
2459     }
2460
2461     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
2462         where P::Searcher: ReverseSearcher<'a>
2463     {
2464         pat.into_searcher(self).next_match_back().map(|(i, _)| i)
2465     }
2466
2467     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
2468         self.find(pat)
2469     }
2470
2471     #[inline]
2472     fn split_at(&self, mid: usize) -> (&str, &str) {
2473         // is_char_boundary checks that the index is in [0, .len()]
2474         if self.is_char_boundary(mid) {
2475             unsafe {
2476                 (self.slice_unchecked(0, mid),
2477                  self.slice_unchecked(mid, self.len()))
2478             }
2479         } else {
2480             slice_error_fail(self, 0, mid)
2481         }
2482     }
2483
2484     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str) {
2485         // is_char_boundary checks that the index is in [0, .len()]
2486         if self.is_char_boundary(mid) {
2487             let len = self.len();
2488             let ptr = self.as_ptr() as *mut u8;
2489             unsafe {
2490                 (from_raw_parts_mut(ptr, mid),
2491                  from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
2492             }
2493         } else {
2494             slice_error_fail(self, 0, mid)
2495         }
2496     }
2497
2498     #[inline]
2499     fn as_ptr(&self) -> *const u8 {
2500         self as *const str as *const u8
2501     }
2502
2503     #[inline]
2504     fn len(&self) -> usize {
2505         self.as_bytes().len()
2506     }
2507
2508     #[inline]
2509     fn is_empty(&self) -> bool { self.len() == 0 }
2510
2511     #[inline]
2512     fn parse<T: FromStr>(&self) -> Result<T, T::Err> { FromStr::from_str(self) }
2513 }
2514
2515 #[stable(feature = "rust1", since = "1.0.0")]
2516 impl AsRef<[u8]> for str {
2517     #[inline]
2518     fn as_ref(&self) -> &[u8] {
2519         self.as_bytes()
2520     }
2521 }
2522
2523 #[stable(feature = "rust1", since = "1.0.0")]
2524 impl<'a> Default for &'a str {
2525     /// Creates an empty str
2526     fn default() -> &'a str { "" }
2527 }