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