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, Filter};
  23 use iter_private::TrustedRandomAccess;
  24 use slice::{self, SliceIndex, Split as SliceSplit};
  25 use mem;
  26
  27 pub mod pattern;
  28
  29 #[unstable(feature = "str_internals", issue = "0")]
  30 #[allow(missing_docs)]
  31 pub mod lossy;
  32
  33 /// A trait to abstract the idea of creating a new instance of a type from a
  34 /// string.
  35 ///
  36 /// `FromStr`'s [`from_str`] method is often used implicitly, through
  37 /// [`str`]'s [`parse`] method. See [`parse`]'s documentation for examples.
  38 ///
  39 /// [`from_str`]: #tymethod.from_str
  40 /// [`str`]: ../../std/primitive.str.html
  41 /// [`parse`]: ../../std/primitive.str.html#method.parse
  42 ///
  43 /// # Examples
  44 ///
  45 /// Basic implementation of `FromStr` on an example `Point` type:
  46 ///
  47 /// ```
  48 /// use std::str::FromStr;
  49 /// use std::num::ParseIntError;
  50 ///
  51 /// #[derive(Debug, PartialEq)]
  52 /// struct Point {
  53 ///     x: i32,
  54 ///     y: i32
  55 /// }
  56 ///
  57 /// impl FromStr for Point {
  58 ///     type Err = ParseIntError;
  59 ///
  60 ///     fn from_str(s: &str) -> Result<Self, Self::Err> {
  61 ///         let coords: Vec<&str> = s.trim_matches(|p| p == '(' || p == ')' )
  62 ///                                  .split(',')
  63 ///                                  .collect();
  64 ///
  65 ///         let x_fromstr = coords[0].parse::<i32>()?;
  66 ///         let y_fromstr = coords[1].parse::<i32>()?;
  67 ///
  68 ///         Ok(Point { x: x_fromstr, y: y_fromstr })
  69 ///     }
  70 /// }
  71 ///
  72 /// let p = Point::from_str("(1,2)");
  73 /// assert_eq!(p.unwrap(), Point{ x: 1, y: 2} )
  74 /// ```
  75 #[stable(feature = "rust1", since = "1.0.0")]
  76 pub trait FromStr: Sized {
  77     /// The associated error which can be returned from parsing.
  78     #[stable(feature = "rust1", since = "1.0.0")]
  79     type Err;
  80
  81     /// Parses a string `s` to return a value of this type.
  82     ///
  83     /// If parsing succeeds, return the value inside [`Ok`], otherwise
  84     /// when the string is ill-formatted return an error specific to the
  85     /// inside [`Err`]. The error type is specific to implementation of the trait.
  86     ///
  87     /// [`Ok`]: ../../std/result/enum.Result.html#variant.Ok
  88     /// [`Err`]: ../../std/result/enum.Result.html#variant.Err
  89     ///
  90     /// # Examples
  91     ///
  92     /// Basic usage with [`i32`][ithirtytwo], a type that implements `FromStr`:
  93     ///
  94     /// [ithirtytwo]: ../../std/primitive.i32.html
  95     ///
  96     /// ```
  97     /// use std::str::FromStr;
  98     ///
  99     /// let s = "5";
 100     /// let x = i32::from_str(s).unwrap();
 101     ///
 102     /// assert_eq!(5, x);
 103     /// ```
 104     #[stable(feature = "rust1", since = "1.0.0")]
 105     fn from_str(s: &str) -> Result<Self, Self::Err>;
 106 }
 107
 108 #[stable(feature = "rust1", since = "1.0.0")]
 109 impl FromStr for bool {
 110     type Err = ParseBoolError;
 111
 112     /// Parse a `bool` from a string.
 113     ///
 114     /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
 115     /// actually be parseable.
 116     ///
 117     /// # Examples
 118     ///
 119     /// ```
 120     /// use std::str::FromStr;
 121     ///
 122     /// assert_eq!(FromStr::from_str("true"), Ok(true));
 123     /// assert_eq!(FromStr::from_str("false"), Ok(false));
 124     /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
 125     /// ```
 126     ///
 127     /// Note, in many cases, the `.parse()` method on `str` is more proper.
 128     ///
 129     /// ```
 130     /// assert_eq!("true".parse(), Ok(true));
 131     /// assert_eq!("false".parse(), Ok(false));
 132     /// assert!("not even a boolean".parse::<bool>().is_err());
 133     /// ```
 134     #[inline]
 135     fn from_str(s: &str) -> Result<bool, ParseBoolError> {
 136         match s {
 137             "true"  => Ok(true),
 138             "false" => Ok(false),
 139             _       => Err(ParseBoolError { _priv: () }),
 140         }
 141     }
 142 }
 143
 144 /// An error returned when parsing a `bool` using [`from_str`] fails
 145 ///
 146 /// [`from_str`]: ../../std/primitive.bool.html#method.from_str
 147 #[derive(Debug, Clone, PartialEq, Eq)]
 148 #[stable(feature = "rust1", since = "1.0.0")]
 149 pub struct ParseBoolError { _priv: () }
 150
 151 #[stable(feature = "rust1", since = "1.0.0")]
 152 impl fmt::Display for ParseBoolError {
 153     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 154         "provided string was not `true` or `false`".fmt(f)
 155     }
 156 }
 157
 158 /*
 159 Section: Creating a string
 160 */
 161
 162 /// Errors which can occur when attempting to interpret a sequence of [`u8`]
 163 /// as a string.
 164 ///
 165 /// [`u8`]: ../../std/primitive.u8.html
 166 ///
 167 /// As such, the `from_utf8` family of functions and methods for both [`String`]s
 168 /// and [`&str`]s make use of this error, for example.
 169 ///
 170 /// [`String`]: ../../std/string/struct.String.html#method.from_utf8
 171 /// [`&str`]: ../../std/str/fn.from_utf8.html
 172 ///
 173 /// # Examples
 174 ///
 175 /// This error type’s methods can be used to create functionality
 176 /// similar to `String::from_utf8_lossy` without allocating heap memory:
 177 ///
 178 /// ```
 179 /// fn from_utf8_lossy<F>(mut input: &[u8], mut push: F) where F: FnMut(&str) {
 180 ///     loop {
 181 ///         match ::std::str::from_utf8(input) {
 182 ///             Ok(valid) => {
 183 ///                 push(valid);
 184 ///                 break
 185 ///             }
 186 ///             Err(error) => {
 187 ///                 let (valid, after_valid) = input.split_at(error.valid_up_to());
 188 ///                 unsafe {
 189 ///                     push(::std::str::from_utf8_unchecked(valid))
 190 ///                 }
 191 ///                 push("\u{FFFD}");
 192 ///
 193 ///                 if let Some(invalid_sequence_length) = error.error_len() {
 194 ///                     input = &after_valid[invalid_sequence_length..]
 195 ///                 } else {
 196 ///                     break
 197 ///                 }
 198 ///             }
 199 ///         }
 200 ///     }
 201 /// }
 202 /// ```
 203 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
 204 #[stable(feature = "rust1", since = "1.0.0")]
 205 pub struct Utf8Error {
 206     valid_up_to: usize,
 207     error_len: Option<u8>,
 208 }
 209
 210 impl Utf8Error {
 211     /// Returns the index in the given string up to which valid UTF-8 was
 212     /// verified.
 213     ///
 214     /// It is the maximum index such that `from_utf8(&input[..index])`
 215     /// would return `Ok(_)`.
 216     ///
 217     /// # Examples
 218     ///
 219     /// Basic usage:
 220     ///
 221     /// ```
 222     /// use std::str;
 223     ///
 224     /// // some invalid bytes, in a vector
 225     /// let sparkle_heart = vec![0, 159, 146, 150];
 226     ///
 227     /// // std::str::from_utf8 returns a Utf8Error
 228     /// let error = str::from_utf8(&sparkle_heart).unwrap_err();
 229     ///
 230     /// // the second byte is invalid here
 231     /// assert_eq!(1, error.valid_up_to());
 232     /// ```
 233     #[stable(feature = "utf8_error", since = "1.5.0")]
 234     pub fn valid_up_to(&self) -> usize { self.valid_up_to }
 235
 236     /// Provide more information about the failure:
 237     ///
 238     /// * `None`: the end of the input was reached unexpectedly.
 239     ///   `self.valid_up_to()` is 1 to 3 bytes from the end of the input.
 240     ///   If a byte stream (such as a file or a network socket) is being decoded incrementally,
 241     ///   this could be a valid `char` whose UTF-8 byte sequence is spanning multiple chunks.
 242     ///
 243     /// * `Some(len)`: an unexpected byte was encountered.
 244     ///   The length provided is that of the invalid byte sequence
 245     ///   that starts at the index given by `valid_up_to()`.
 246     ///   Decoding should resume after that sequence
 247     ///   (after inserting a [`U+FFFD REPLACEMENT CHARACTER`][U+FFFD]) in case of
 248     ///   lossy decoding.
 249     ///
 250     /// [U+FFFD]: ../../std/char/constant.REPLACEMENT_CHARACTER.html
 251     #[stable(feature = "utf8_error_error_len", since = "1.20.0")]
 252     pub fn error_len(&self) -> Option<usize> {
 253         self.error_len.map(|len| len as usize)
 254     }
 255 }
 256
 257 /// Converts a slice of bytes to a string slice.
 258 ///
 259 /// A string slice ([`&str`]) is made of bytes ([`u8`]), and a byte slice
 260 /// ([`&[u8]`][byteslice]) is made of bytes, so this function converts between
 261 /// the two. Not all byte slices are valid string slices, however: [`&str`] requires
 262 /// that it is valid UTF-8. `from_utf8()` checks to ensure that the bytes are valid
 263 /// UTF-8, and then does the conversion.
 264 ///
 265 /// [`&str`]: ../../std/primitive.str.html
 266 /// [`u8`]: ../../std/primitive.u8.html
 267 /// [byteslice]: ../../std/primitive.slice.html
 268 ///
 269 /// If you are sure that the byte slice is valid UTF-8, and you don't want to
 270 /// incur the overhead of the validity check, there is an unsafe version of
 271 /// this function, [`from_utf8_unchecked`][fromutf8u], which has the same
 272 /// behavior but skips the check.
 273 ///
 274 /// [fromutf8u]: fn.from_utf8_unchecked.html
 275 ///
 276 /// If you need a `String` instead of a `&str`, consider
 277 /// [`String::from_utf8`][string].
 278 ///
 279 /// [string]: ../../std/string/struct.String.html#method.from_utf8
 280 ///
 281 /// Because you can stack-allocate a `[u8; N]`, and you can take a
 282 /// [`&[u8]`][byteslice] of it, this function is one way to have a
 283 /// stack-allocated string. There is an example of this in the
 284 /// examples section below.
 285 ///
 286 /// [byteslice]: ../../std/primitive.slice.html
 287 ///
 288 /// # Errors
 289 ///
 290 /// Returns `Err` if the slice is not UTF-8 with a description as to why the
 291 /// provided slice is not UTF-8.
 292 ///
 293 /// # Examples
 294 ///
 295 /// Basic usage:
 296 ///
 297 /// ```
 298 /// use std::str;
 299 ///
 300 /// // some bytes, in a vector
 301 /// let sparkle_heart = vec![240, 159, 146, 150];
 302 ///
 303 /// // We know these bytes are valid, so just use `unwrap()`.
 304 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 305 ///
 306 /// assert_eq!("💖", sparkle_heart);
 307 /// ```
 308 ///
 309 /// Incorrect bytes:
 310 ///
 311 /// ```
 312 /// use std::str;
 313 ///
 314 /// // some invalid bytes, in a vector
 315 /// let sparkle_heart = vec![0, 159, 146, 150];
 316 ///
 317 /// assert!(str::from_utf8(&sparkle_heart).is_err());
 318 /// ```
 319 ///
 320 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 321 /// errors that can be returned.
 322 ///
 323 /// [error]: struct.Utf8Error.html
 324 ///
 325 /// A "stack allocated string":
 326 ///
 327 /// ```
 328 /// use std::str;
 329 ///
 330 /// // some bytes, in a stack-allocated array
 331 /// let sparkle_heart = [240, 159, 146, 150];
 332 ///
 333 /// // We know these bytes are valid, so just use `unwrap()`.
 334 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 335 ///
 336 /// assert_eq!("💖", sparkle_heart);
 337 /// ```
 338 #[stable(feature = "rust1", since = "1.0.0")]
 339 pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
 340     run_utf8_validation(v)?;
 341     Ok(unsafe { from_utf8_unchecked(v) })
 342 }
 343
 344 /// Converts a mutable slice of bytes to a mutable string slice.
 345 ///
 346 /// # Examples
 347 ///
 348 /// Basic usage:
 349 ///
 350 /// ```
 351 /// use std::str;
 352 ///
 353 /// // "Hello, Rust!" as a mutable vector
 354 /// let mut hellorust = vec![72, 101, 108, 108, 111, 44, 32, 82, 117, 115, 116, 33];
 355 ///
 356 /// // As we know these bytes are valid, we can use `unwrap()`
 357 /// let outstr = str::from_utf8_mut(&mut hellorust).unwrap();
 358 ///
 359 /// assert_eq!("Hello, Rust!", outstr);
 360 /// ```
 361 ///
 362 /// Incorrect bytes:
 363 ///
 364 /// ```
 365 /// use std::str;
 366 ///
 367 /// // Some invalid bytes in a mutable vector
 368 /// let mut invalid = vec![128, 223];
 369 ///
 370 /// assert!(str::from_utf8_mut(&mut invalid).is_err());
 371 /// ```
 372 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 373 /// errors that can be returned.
 374 ///
 375 /// [error]: struct.Utf8Error.html
 376 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 377 pub fn from_utf8_mut(v: &mut [u8]) -> Result<&mut str, Utf8Error> {
 378     run_utf8_validation(v)?;
 379     Ok(unsafe { from_utf8_unchecked_mut(v) })
 380 }
 381
 382 /// Converts a slice of bytes to a string slice without checking
 383 /// that the string contains valid UTF-8.
 384 ///
 385 /// See the safe version, [`from_utf8`][fromutf8], for more information.
 386 ///
 387 /// [fromutf8]: fn.from_utf8.html
 388 ///
 389 /// # Safety
 390 ///
 391 /// This function is unsafe because it does not check that the bytes passed to
 392 /// it are valid UTF-8. If this constraint is violated, undefined behavior
 393 /// results, as the rest of Rust assumes that [`&str`]s are valid UTF-8.
 394 ///
 395 /// [`&str`]: ../../std/primitive.str.html
 396 ///
 397 /// # Examples
 398 ///
 399 /// Basic usage:
 400 ///
 401 /// ```
 402 /// use std::str;
 403 ///
 404 /// // some bytes, in a vector
 405 /// let sparkle_heart = vec![240, 159, 146, 150];
 406 ///
 407 /// let sparkle_heart = unsafe {
 408 ///     str::from_utf8_unchecked(&sparkle_heart)
 409 /// };
 410 ///
 411 /// assert_eq!("💖", sparkle_heart);
 412 /// ```
 413 #[inline]
 414 #[stable(feature = "rust1", since = "1.0.0")]
 415 pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
 416     &*(v as *const [u8] as *const str)
 417 }
 418
 419 /// Converts a slice of bytes to a string slice without checking
 420 /// that the string contains valid UTF-8; mutable version.
 421 ///
 422 /// See the immutable version, [`from_utf8_unchecked()`][fromutf8], for more information.
 423 ///
 424 /// [fromutf8]: fn.from_utf8_unchecked.html
 425 ///
 426 /// # Examples
 427 ///
 428 /// Basic usage:
 429 ///
 430 /// ```
 431 /// use std::str;
 432 ///
 433 /// let mut heart = vec![240, 159, 146, 150];
 434 /// let heart = unsafe { str::from_utf8_unchecked_mut(&mut heart) };
 435 ///
 436 /// assert_eq!("💖", heart);
 437 /// ```
 438 #[inline]
 439 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 440 pub unsafe fn from_utf8_unchecked_mut(v: &mut [u8]) -> &mut str {
 441     &mut *(v as *mut [u8] as *mut str)
 442 }
 443
 444 #[stable(feature = "rust1", since = "1.0.0")]
 445 impl fmt::Display for Utf8Error {
 446     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 447         if let Some(error_len) = self.error_len {
 448             write!(f, "invalid utf-8 sequence of {} bytes from index {}",
 449                    error_len, self.valid_up_to)
 450         } else {
 451             write!(f, "incomplete utf-8 byte sequence from index {}", self.valid_up_to)
 452         }
 453     }
 454 }
 455
 456 /*
 457 Section: Iterators
 458 */
 459
 460 /// An iterator over the [`char`]s of a string slice.
 461 ///
 462 /// [`char`]: ../../std/primitive.char.html
 463 ///
 464 /// This struct is created by the [`chars`] method on [`str`].
 465 /// See its documentation for more.
 466 ///
 467 /// [`chars`]: ../../std/primitive.str.html#method.chars
 468 /// [`str`]: ../../std/primitive.str.html
 469 #[derive(Clone, Debug)]
 470 #[stable(feature = "rust1", since = "1.0.0")]
 471 pub struct Chars<'a> {
 472     iter: slice::Iter<'a, u8>
 473 }
 474
 475 /// Returns the initial codepoint accumulator for the first byte.
 476 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
 477 /// for width 3, and 3 bits for width 4.
 478 #[inline]
 479 fn utf8_first_byte(byte: u8, width: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
 480
 481 /// Returns the value of `ch` updated with continuation byte `byte`.
 482 #[inline]
 483 fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
 484
 485 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
 486 /// bits `10`).
 487 #[inline]
 488 fn utf8_is_cont_byte(byte: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
 489
 490 #[inline]
 491 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 492     match opt {
 493         Some(&byte) => byte,
 494         None => 0,
 495     }
 496 }
 497
 498 /// Reads the next code point out of a byte iterator (assuming a
 499 /// UTF-8-like encoding).
 500 #[unstable(feature = "str_internals", issue = "0")]
 501 #[inline]
 502 pub fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
 503     // Decode UTF-8
 504     let x = *bytes.next()?;
 505     if x < 128 {
 506         return Some(x as u32)
 507     }
 508
 509     // Multibyte case follows
 510     // Decode from a byte combination out of: [[[x y] z] w]
 511     // NOTE: Performance is sensitive to the exact formulation here
 512     let init = utf8_first_byte(x, 2);
 513     let y = unwrap_or_0(bytes.next());
 514     let mut ch = utf8_acc_cont_byte(init, y);
 515     if x >= 0xE0 {
 516         // [[x y z] w] case
 517         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 518         let z = unwrap_or_0(bytes.next());
 519         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
 520         ch = init << 12 | y_z;
 521         if x >= 0xF0 {
 522             // [x y z w] case
 523             // use only the lower 3 bits of `init`
 524             let w = unwrap_or_0(bytes.next());
 525             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
 526         }
 527     }
 528
 529     Some(ch)
 530 }
 531
 532 /// Reads the last code point out of a byte iterator (assuming a
 533 /// UTF-8-like encoding).
 534 #[inline]
 535 fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
 536     where I: DoubleEndedIterator<Item = &'a u8>,
 537 {
 538     // Decode UTF-8
 539     let w = match bytes.next_back() {
 540         None => return None,
 541         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 542         Some(&back_byte) => back_byte,
 543     };
 544
 545     // Multibyte case follows
 546     // Decode from a byte combination out of: [x [y [z w]]]
 547     let mut ch;
 548     let z = unwrap_or_0(bytes.next_back());
 549     ch = utf8_first_byte(z, 2);
 550     if utf8_is_cont_byte(z) {
 551         let y = unwrap_or_0(bytes.next_back());
 552         ch = utf8_first_byte(y, 3);
 553         if utf8_is_cont_byte(y) {
 554             let x = unwrap_or_0(bytes.next_back());
 555             ch = utf8_first_byte(x, 4);
 556             ch = utf8_acc_cont_byte(ch, y);
 557         }
 558         ch = utf8_acc_cont_byte(ch, z);
 559     }
 560     ch = utf8_acc_cont_byte(ch, w);
 561
 562     Some(ch)
 563 }
 564
 565 #[stable(feature = "rust1", since = "1.0.0")]
 566 impl<'a> Iterator for Chars<'a> {
 567     type Item = char;
 568
 569     #[inline]
 570     fn next(&mut self) -> Option<char> {
 571         next_code_point(&mut self.iter).map(|ch| {
 572             // str invariant says `ch` is a valid Unicode Scalar Value
 573             unsafe {
 574                 char::from_u32_unchecked(ch)
 575             }
 576         })
 577     }
 578
 579     #[inline]
 580     fn count(self) -> usize {
 581         // length in `char` is equal to the number of non-continuation bytes
 582         let bytes_len = self.iter.len();
 583         let mut cont_bytes = 0;
 584         for &byte in self.iter {
 585             cont_bytes += utf8_is_cont_byte(byte) as usize;
 586         }
 587         bytes_len - cont_bytes
 588     }
 589
 590     #[inline]
 591     fn size_hint(&self) -> (usize, Option<usize>) {
 592         let len = self.iter.len();
 593         // `(len + 3)` can't overflow, because we know that the `slice::Iter`
 594         // belongs to a slice in memory which has a maximum length of
 595         // `isize::MAX` (that's well below `usize::MAX`).
 596         ((len + 3) / 4, Some(len))
 597     }
 598
 599     #[inline]
 600     fn last(mut self) -> Option<char> {
 601         // No need to go through the entire string.
 602         self.next_back()
 603     }
 604 }
 605
 606 #[stable(feature = "rust1", since = "1.0.0")]
 607 impl<'a> DoubleEndedIterator for Chars<'a> {
 608     #[inline]
 609     fn next_back(&mut self) -> Option<char> {
 610         next_code_point_reverse(&mut self.iter).map(|ch| {
 611             // str invariant says `ch` is a valid Unicode Scalar Value
 612             unsafe {
 613                 char::from_u32_unchecked(ch)
 614             }
 615         })
 616     }
 617 }
 618
 619 #[stable(feature = "fused", since = "1.26.0")]
 620 impl FusedIterator for Chars<'_> {}
 621
 622 impl<'a> Chars<'a> {
 623     /// View the underlying data as a subslice of the original data.
 624     ///
 625     /// This has the same lifetime as the original slice, and so the
 626     /// iterator can continue to be used while this exists.
 627     ///
 628     /// # Examples
 629     ///
 630     /// ```
 631     /// let mut chars = "abc".chars();
 632     ///
 633     /// assert_eq!(chars.as_str(), "abc");
 634     /// chars.next();
 635     /// assert_eq!(chars.as_str(), "bc");
 636     /// chars.next();
 637     /// chars.next();
 638     /// assert_eq!(chars.as_str(), "");
 639     /// ```
 640     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 641     #[inline]
 642     pub fn as_str(&self) -> &'a str {
 643         unsafe { from_utf8_unchecked(self.iter.as_slice()) }
 644     }
 645 }
 646
 647 /// An iterator over the [`char`]s of a string slice, and their positions.
 648 ///
 649 /// [`char`]: ../../std/primitive.char.html
 650 ///
 651 /// This struct is created by the [`char_indices`] method on [`str`].
 652 /// See its documentation for more.
 653 ///
 654 /// [`char_indices`]: ../../std/primitive.str.html#method.char_indices
 655 /// [`str`]: ../../std/primitive.str.html
 656 #[derive(Clone, Debug)]
 657 #[stable(feature = "rust1", since = "1.0.0")]
 658 pub struct CharIndices<'a> {
 659     front_offset: usize,
 660     iter: Chars<'a>,
 661 }
 662
 663 #[stable(feature = "rust1", since = "1.0.0")]
 664 impl<'a> Iterator for CharIndices<'a> {
 665     type Item = (usize, char);
 666
 667     #[inline]
 668     fn next(&mut self) -> Option<(usize, char)> {
 669         let pre_len = self.iter.iter.len();
 670         match self.iter.next() {
 671             None => None,
 672             Some(ch) => {
 673                 let index = self.front_offset;
 674                 let len = self.iter.iter.len();
 675                 self.front_offset += pre_len - len;
 676                 Some((index, ch))
 677             }
 678         }
 679     }
 680
 681     #[inline]
 682     fn count(self) -> usize {
 683         self.iter.count()
 684     }
 685
 686     #[inline]
 687     fn size_hint(&self) -> (usize, Option<usize>) {
 688         self.iter.size_hint()
 689     }
 690
 691     #[inline]
 692     fn last(mut self) -> Option<(usize, char)> {
 693         // No need to go through the entire string.
 694         self.next_back()
 695     }
 696 }
 697
 698 #[stable(feature = "rust1", since = "1.0.0")]
 699 impl<'a> DoubleEndedIterator for CharIndices<'a> {
 700     #[inline]
 701     fn next_back(&mut self) -> Option<(usize, char)> {
 702         self.iter.next_back().map(|ch| {
 703             let index = self.front_offset + self.iter.iter.len();
 704             (index, ch)
 705         })
 706     }
 707 }
 708
 709 #[stable(feature = "fused", since = "1.26.0")]
 710 impl FusedIterator for CharIndices<'_> {}
 711
 712 impl<'a> CharIndices<'a> {
 713     /// View the underlying data as a subslice of the original data.
 714     ///
 715     /// This has the same lifetime as the original slice, and so the
 716     /// iterator can continue to be used while this exists.
 717     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 718     #[inline]
 719     pub fn as_str(&self) -> &'a str {
 720         self.iter.as_str()
 721     }
 722 }
 723
 724 /// An iterator over the bytes of a string slice.
 725 ///
 726 /// This struct is created by the [`bytes`] method on [`str`].
 727 /// See its documentation for more.
 728 ///
 729 /// [`bytes`]: ../../std/primitive.str.html#method.bytes
 730 /// [`str`]: ../../std/primitive.str.html
 731 #[stable(feature = "rust1", since = "1.0.0")]
 732 #[derive(Clone, Debug)]
 733 pub struct Bytes<'a>(Cloned<slice::Iter<'a, u8>>);
 734
 735 #[stable(feature = "rust1", since = "1.0.0")]
 736 impl Iterator for Bytes<'_> {
 737     type Item = u8;
 738
 739     #[inline]
 740     fn next(&mut self) -> Option<u8> {
 741         self.0.next()
 742     }
 743
 744     #[inline]
 745     fn size_hint(&self) -> (usize, Option<usize>) {
 746         self.0.size_hint()
 747     }
 748
 749     #[inline]
 750     fn count(self) -> usize {
 751         self.0.count()
 752     }
 753
 754     #[inline]
 755     fn last(self) -> Option<Self::Item> {
 756         self.0.last()
 757     }
 758
 759     #[inline]
 760     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 761         self.0.nth(n)
 762     }
 763
 764     #[inline]
 765     fn all<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 766         self.0.all(f)
 767     }
 768
 769     #[inline]
 770     fn any<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 771         self.0.any(f)
 772     }
 773
 774     #[inline]
 775     fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where
 776         P: FnMut(&Self::Item) -> bool
 777     {
 778         self.0.find(predicate)
 779     }
 780
 781     #[inline]
 782     fn position<P>(&mut self, predicate: P) -> Option<usize> where
 783         P: FnMut(Self::Item) -> bool
 784     {
 785         self.0.position(predicate)
 786     }
 787
 788     #[inline]
 789     fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
 790         P: FnMut(Self::Item) -> bool
 791     {
 792         self.0.rposition(predicate)
 793     }
 794 }
 795
 796 #[stable(feature = "rust1", since = "1.0.0")]
 797 impl DoubleEndedIterator for Bytes<'_> {
 798     #[inline]
 799     fn next_back(&mut self) -> Option<u8> {
 800         self.0.next_back()
 801     }
 802
 803     #[inline]
 804     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where
 805         P: FnMut(&Self::Item) -> bool
 806     {
 807         self.0.rfind(predicate)
 808     }
 809 }
 810
 811 #[stable(feature = "rust1", since = "1.0.0")]
 812 impl ExactSizeIterator for Bytes<'_> {
 813     #[inline]
 814     fn len(&self) -> usize {
 815         self.0.len()
 816     }
 817
 818     #[inline]
 819     fn is_empty(&self) -> bool {
 820         self.0.is_empty()
 821     }
 822 }
 823
 824 #[stable(feature = "fused", since = "1.26.0")]
 825 impl FusedIterator for Bytes<'_> {}
 826
 827 #[unstable(feature = "trusted_len", issue = "37572")]
 828 unsafe impl TrustedLen for Bytes<'_> {}
 829
 830 #[doc(hidden)]
 831 unsafe impl<'a> TrustedRandomAccess for Bytes<'a> {
 832     unsafe fn get_unchecked(&mut self, i: usize) -> u8 {
 833         self.0.get_unchecked(i)
 834     }
 835     fn may_have_side_effect() -> bool { false }
 836 }
 837
 838 /// This macro generates a Clone impl for string pattern API
 839 /// wrapper types of the form X<'a, P>
 840 macro_rules! derive_pattern_clone {
 841     (clone $t:ident with |$s:ident| $e:expr) => {
 842         impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
 843             where P::Searcher: Clone
 844         {
 845             fn clone(&self) -> Self {
 846                 let $s = self;
 847                 $e
 848             }
 849         }
 850     }
 851 }
 852
 853 /// This macro generates two public iterator structs
 854 /// wrapping a private internal one that makes use of the `Pattern` API.
 855 ///
 856 /// For all patterns `P: Pattern<'a>` the following items will be
 857 /// generated (generics omitted):
 858 ///
 859 /// struct $forward_iterator($internal_iterator);
 860 /// struct $reverse_iterator($internal_iterator);
 861 ///
 862 /// impl Iterator for $forward_iterator
 863 /// { /* internal ends up calling Searcher::next_match() */ }
 864 ///
 865 /// impl DoubleEndedIterator for $forward_iterator
 866 ///       where P::Searcher: DoubleEndedSearcher
 867 /// { /* internal ends up calling Searcher::next_match_back() */ }
 868 ///
 869 /// impl Iterator for $reverse_iterator
 870 ///       where P::Searcher: ReverseSearcher
 871 /// { /* internal ends up calling Searcher::next_match_back() */ }
 872 ///
 873 /// impl DoubleEndedIterator for $reverse_iterator
 874 ///       where P::Searcher: DoubleEndedSearcher
 875 /// { /* internal ends up calling Searcher::next_match() */ }
 876 ///
 877 /// The internal one is defined outside the macro, and has almost the same
 878 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
 879 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
 880 ///
 881 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
 882 /// `Pattern` might not return the same elements, so actually implementing
 883 /// `DoubleEndedIterator` for it would be incorrect.
 884 /// (See the docs in `str::pattern` for more details)
 885 ///
 886 /// However, the internal struct still represents a single ended iterator from
 887 /// either end, and depending on pattern is also a valid double ended iterator,
 888 /// so the two wrapper structs implement `Iterator`
 889 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
 890 /// to the complex impls seen above.
 891 macro_rules! generate_pattern_iterators {
 892     {
 893         // Forward iterator
 894         forward:
 895             $(#[$forward_iterator_attribute:meta])*
 896             struct $forward_iterator:ident;
 897
 898         // Reverse iterator
 899         reverse:
 900             $(#[$reverse_iterator_attribute:meta])*
 901             struct $reverse_iterator:ident;
 902
 903         // Stability of all generated items
 904         stability:
 905             $(#[$common_stability_attribute:meta])*
 906
 907         // Internal almost-iterator that is being delegated to
 908         internal:
 909             $internal_iterator:ident yielding ($iterty:ty);
 910
 911         // Kind of delegation - either single ended or double ended
 912         delegate $($t:tt)*
 913     } => {
 914         $(#[$forward_iterator_attribute])*
 915         $(#[$common_stability_attribute])*
 916         pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 917
 918         $(#[$common_stability_attribute])*
 919         impl<'a, P: Pattern<'a>> fmt::Debug for $forward_iterator<'a, P>
 920             where P::Searcher: fmt::Debug
 921         {
 922             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 923                 f.debug_tuple(stringify!($forward_iterator))
 924                     .field(&self.0)
 925                     .finish()
 926             }
 927         }
 928
 929         $(#[$common_stability_attribute])*
 930         impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
 931             type Item = $iterty;
 932
 933             #[inline]
 934             fn next(&mut self) -> Option<$iterty> {
 935                 self.0.next()
 936             }
 937         }
 938
 939         $(#[$common_stability_attribute])*
 940         impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
 941             where P::Searcher: Clone
 942         {
 943             fn clone(&self) -> Self {
 944                 $forward_iterator(self.0.clone())
 945             }
 946         }
 947
 948         $(#[$reverse_iterator_attribute])*
 949         $(#[$common_stability_attribute])*
 950         pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 951
 952         $(#[$common_stability_attribute])*
 953         impl<'a, P: Pattern<'a>> fmt::Debug for $reverse_iterator<'a, P>
 954             where P::Searcher: fmt::Debug
 955         {
 956             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 957                 f.debug_tuple(stringify!($reverse_iterator))
 958                     .field(&self.0)
 959                     .finish()
 960             }
 961         }
 962
 963         $(#[$common_stability_attribute])*
 964         impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
 965             where P::Searcher: ReverseSearcher<'a>
 966         {
 967             type Item = $iterty;
 968
 969             #[inline]
 970             fn next(&mut self) -> Option<$iterty> {
 971                 self.0.next_back()
 972             }
 973         }
 974
 975         $(#[$common_stability_attribute])*
 976         impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
 977             where P::Searcher: Clone
 978         {
 979             fn clone(&self) -> Self {
 980                 $reverse_iterator(self.0.clone())
 981             }
 982         }
 983
 984         #[stable(feature = "fused", since = "1.26.0")]
 985         impl<'a, P: Pattern<'a>> FusedIterator for $forward_iterator<'a, P> {}
 986
 987         #[stable(feature = "fused", since = "1.26.0")]
 988         impl<'a, P: Pattern<'a>> FusedIterator for $reverse_iterator<'a, P>
 989             where P::Searcher: ReverseSearcher<'a> {}
 990
 991         generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
 992                                                 $forward_iterator,
 993                                                 $reverse_iterator, $iterty);
 994     };
 995     {
 996         double ended; with $(#[$common_stability_attribute:meta])*,
 997                            $forward_iterator:ident,
 998                            $reverse_iterator:ident, $iterty:ty
 999     } => {
1000         $(#[$common_stability_attribute])*
1001         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
1002             where P::Searcher: DoubleEndedSearcher<'a>
1003         {
1004             #[inline]
1005             fn next_back(&mut self) -> Option<$iterty> {
1006                 self.0.next_back()
1007             }
1008         }
1009
1010         $(#[$common_stability_attribute])*
1011         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
1012             where P::Searcher: DoubleEndedSearcher<'a>
1013         {
1014             #[inline]
1015             fn next_back(&mut self) -> Option<$iterty> {
1016                 self.0.next()
1017             }
1018         }
1019     };
1020     {
1021         single ended; with $(#[$common_stability_attribute:meta])*,
1022                            $forward_iterator:ident,
1023                            $reverse_iterator:ident, $iterty:ty
1024     } => {}
1025 }
1026
1027 derive_pattern_clone!{
1028     clone SplitInternal
1029     with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
1030 }
1031
1032 struct SplitInternal<'a, P: Pattern<'a>> {
1033     start: usize,
1034     end: usize,
1035     matcher: P::Searcher,
1036     allow_trailing_empty: bool,
1037     finished: bool,
1038 }
1039
1040 impl<'a, P: Pattern<'a>> fmt::Debug for SplitInternal<'a, P> where P::Searcher: fmt::Debug {
1041     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1042         f.debug_struct("SplitInternal")
1043             .field("start", &self.start)
1044             .field("end", &self.end)
1045             .field("matcher", &self.matcher)
1046             .field("allow_trailing_empty", &self.allow_trailing_empty)
1047             .field("finished", &self.finished)
1048             .finish()
1049     }
1050 }
1051
1052 impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
1053     #[inline]
1054     fn get_end(&mut self) -> Option<&'a str> {
1055         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
1056             self.finished = true;
1057             unsafe {
1058                 let string = self.matcher.haystack().get_unchecked(self.start..self.end);
1059                 Some(string)
1060             }
1061         } else {
1062             None
1063         }
1064     }
1065
1066     #[inline]
1067     fn next(&mut self) -> Option<&'a str> {
1068         if self.finished { return None }
1069
1070         let haystack = self.matcher.haystack();
1071         match self.matcher.next_match() {
1072             Some((a, b)) => unsafe {
1073                 let elt = haystack.get_unchecked(self.start..a);
1074                 self.start = b;
1075                 Some(elt)
1076             },
1077             None => self.get_end(),
1078         }
1079     }
1080
1081     #[inline]
1082     fn next_back(&mut self) -> Option<&'a str>
1083         where P::Searcher: ReverseSearcher<'a>
1084     {
1085         if self.finished { return None }
1086
1087         if !self.allow_trailing_empty {
1088             self.allow_trailing_empty = true;
1089             match self.next_back() {
1090                 Some(elt) if !elt.is_empty() => return Some(elt),
1091                 _ => if self.finished { return None }
1092             }
1093         }
1094
1095         let haystack = self.matcher.haystack();
1096         match self.matcher.next_match_back() {
1097             Some((a, b)) => unsafe {
1098                 let elt = haystack.get_unchecked(b..self.end);
1099                 self.end = a;
1100                 Some(elt)
1101             },
1102             None => unsafe {
1103                 self.finished = true;
1104                 Some(haystack.get_unchecked(self.start..self.end))
1105             },
1106         }
1107     }
1108 }
1109
1110 generate_pattern_iterators! {
1111     forward:
1112         /// Created with the method [`split`].
1113         ///
1114         /// [`split`]: ../../std/primitive.str.html#method.split
1115         struct Split;
1116     reverse:
1117         /// Created with the method [`rsplit`].
1118         ///
1119         /// [`rsplit`]: ../../std/primitive.str.html#method.rsplit
1120         struct RSplit;
1121     stability:
1122         #[stable(feature = "rust1", since = "1.0.0")]
1123     internal:
1124         SplitInternal yielding (&'a str);
1125     delegate double ended;
1126 }
1127
1128 generate_pattern_iterators! {
1129     forward:
1130         /// Created with the method [`split_terminator`].
1131         ///
1132         /// [`split_terminator`]: ../../std/primitive.str.html#method.split_terminator
1133         struct SplitTerminator;
1134     reverse:
1135         /// Created with the method [`rsplit_terminator`].
1136         ///
1137         /// [`rsplit_terminator`]: ../../std/primitive.str.html#method.rsplit_terminator
1138         struct RSplitTerminator;
1139     stability:
1140         #[stable(feature = "rust1", since = "1.0.0")]
1141     internal:
1142         SplitInternal yielding (&'a str);
1143     delegate double ended;
1144 }
1145
1146 derive_pattern_clone!{
1147     clone SplitNInternal
1148     with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
1149 }
1150
1151 struct SplitNInternal<'a, P: Pattern<'a>> {
1152     iter: SplitInternal<'a, P>,
1153     /// The number of splits remaining
1154     count: usize,
1155 }
1156
1157 impl<'a, P: Pattern<'a>> fmt::Debug for SplitNInternal<'a, P> where P::Searcher: fmt::Debug {
1158     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1159         f.debug_struct("SplitNInternal")
1160             .field("iter", &self.iter)
1161             .field("count", &self.count)
1162             .finish()
1163     }
1164 }
1165
1166 impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
1167     #[inline]
1168     fn next(&mut self) -> Option<&'a str> {
1169         match self.count {
1170             0 => None,
1171             1 => { self.count = 0; self.iter.get_end() }
1172             _ => { self.count -= 1; self.iter.next() }
1173         }
1174     }
1175
1176     #[inline]
1177     fn next_back(&mut self) -> Option<&'a str>
1178         where P::Searcher: ReverseSearcher<'a>
1179     {
1180         match self.count {
1181             0 => None,
1182             1 => { self.count = 0; self.iter.get_end() }
1183             _ => { self.count -= 1; self.iter.next_back() }
1184         }
1185     }
1186 }
1187
1188 generate_pattern_iterators! {
1189     forward:
1190         /// Created with the method [`splitn`].
1191         ///
1192         /// [`splitn`]: ../../std/primitive.str.html#method.splitn
1193         struct SplitN;
1194     reverse:
1195         /// Created with the method [`rsplitn`].
1196         ///
1197         /// [`rsplitn`]: ../../std/primitive.str.html#method.rsplitn
1198         struct RSplitN;
1199     stability:
1200         #[stable(feature = "rust1", since = "1.0.0")]
1201     internal:
1202         SplitNInternal yielding (&'a str);
1203     delegate single ended;
1204 }
1205
1206 derive_pattern_clone!{
1207     clone MatchIndicesInternal
1208     with |s| MatchIndicesInternal(s.0.clone())
1209 }
1210
1211 struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
1212
1213 impl<'a, P: Pattern<'a>> fmt::Debug for MatchIndicesInternal<'a, P> where P::Searcher: fmt::Debug {
1214     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1215         f.debug_tuple("MatchIndicesInternal")
1216             .field(&self.0)
1217             .finish()
1218     }
1219 }
1220
1221 impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
1222     #[inline]
1223     fn next(&mut self) -> Option<(usize, &'a str)> {
1224         self.0.next_match().map(|(start, end)| unsafe {
1225             (start, self.0.haystack().get_unchecked(start..end))
1226         })
1227     }
1228
1229     #[inline]
1230     fn next_back(&mut self) -> Option<(usize, &'a str)>
1231         where P::Searcher: ReverseSearcher<'a>
1232     {
1233         self.0.next_match_back().map(|(start, end)| unsafe {
1234             (start, self.0.haystack().get_unchecked(start..end))
1235         })
1236     }
1237 }
1238
1239 generate_pattern_iterators! {
1240     forward:
1241         /// Created with the method [`match_indices`].
1242         ///
1243         /// [`match_indices`]: ../../std/primitive.str.html#method.match_indices
1244         struct MatchIndices;
1245     reverse:
1246         /// Created with the method [`rmatch_indices`].
1247         ///
1248         /// [`rmatch_indices`]: ../../std/primitive.str.html#method.rmatch_indices
1249         struct RMatchIndices;
1250     stability:
1251         #[stable(feature = "str_match_indices", since = "1.5.0")]
1252     internal:
1253         MatchIndicesInternal yielding ((usize, &'a str));
1254     delegate double ended;
1255 }
1256
1257 derive_pattern_clone!{
1258     clone MatchesInternal
1259     with |s| MatchesInternal(s.0.clone())
1260 }
1261
1262 struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
1263
1264 impl<'a, P: Pattern<'a>> fmt::Debug for MatchesInternal<'a, P> where P::Searcher: fmt::Debug {
1265     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1266         f.debug_tuple("MatchesInternal")
1267             .field(&self.0)
1268             .finish()
1269     }
1270 }
1271
1272 impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
1273     #[inline]
1274     fn next(&mut self) -> Option<&'a str> {
1275         self.0.next_match().map(|(a, b)| unsafe {
1276             // Indices are known to be on utf8 boundaries
1277             self.0.haystack().get_unchecked(a..b)
1278         })
1279     }
1280
1281     #[inline]
1282     fn next_back(&mut self) -> Option<&'a str>
1283         where P::Searcher: ReverseSearcher<'a>
1284     {
1285         self.0.next_match_back().map(|(a, b)| unsafe {
1286             // Indices are known to be on utf8 boundaries
1287             self.0.haystack().get_unchecked(a..b)
1288         })
1289     }
1290 }
1291
1292 generate_pattern_iterators! {
1293     forward:
1294         /// Created with the method [`matches`].
1295         ///
1296         /// [`matches`]: ../../std/primitive.str.html#method.matches
1297         struct Matches;
1298     reverse:
1299         /// Created with the method [`rmatches`].
1300         ///
1301         /// [`rmatches`]: ../../std/primitive.str.html#method.rmatches
1302         struct RMatches;
1303     stability:
1304         #[stable(feature = "str_matches", since = "1.2.0")]
1305     internal:
1306         MatchesInternal yielding (&'a str);
1307     delegate double ended;
1308 }
1309
1310 /// An iterator over the lines of a string, as string slices.
1311 ///
1312 /// This struct is created with the [`lines`] method on [`str`].
1313 /// See its documentation for more.
1314 ///
1315 /// [`lines`]: ../../std/primitive.str.html#method.lines
1316 /// [`str`]: ../../std/primitive.str.html
1317 #[stable(feature = "rust1", since = "1.0.0")]
1318 #[derive(Clone, Debug)]
1319 pub struct Lines<'a>(Map<SplitTerminator<'a, char>, LinesAnyMap>);
1320
1321 #[stable(feature = "rust1", since = "1.0.0")]
1322 impl<'a> Iterator for Lines<'a> {
1323     type Item = &'a str;
1324
1325     #[inline]
1326     fn next(&mut self) -> Option<&'a str> {
1327         self.0.next()
1328     }
1329
1330     #[inline]
1331     fn size_hint(&self) -> (usize, Option<usize>) {
1332         self.0.size_hint()
1333     }
1334 }
1335
1336 #[stable(feature = "rust1", since = "1.0.0")]
1337 impl<'a> DoubleEndedIterator for Lines<'a> {
1338     #[inline]
1339     fn next_back(&mut self) -> Option<&'a str> {
1340         self.0.next_back()
1341     }
1342 }
1343
1344 #[stable(feature = "fused", since = "1.26.0")]
1345 impl FusedIterator for Lines<'_> {}
1346
1347 /// Created with the method [`lines_any`].
1348 ///
1349 /// [`lines_any`]: ../../std/primitive.str.html#method.lines_any
1350 #[stable(feature = "rust1", since = "1.0.0")]
1351 #[rustc_deprecated(since = "1.4.0", reason = "use lines()/Lines instead now")]
1352 #[derive(Clone, Debug)]
1353 #[allow(deprecated)]
1354 pub struct LinesAny<'a>(Lines<'a>);
1355
1356 /// A nameable, cloneable fn type
1357 #[derive(Clone)]
1358 struct LinesAnyMap;
1359
1360 impl<'a> Fn<(&'a str,)> for LinesAnyMap {
1361     #[inline]
1362     extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
1363         let l = line.len();
1364         if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
1365         else { line }
1366     }
1367 }
1368
1369 impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
1370     #[inline]
1371     extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
1372         Fn::call(&*self, (line,))
1373     }
1374 }
1375
1376 impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
1377     type Output = &'a str;
1378
1379     #[inline]
1380     extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
1381         Fn::call(&self, (line,))
1382     }
1383 }
1384
1385 #[stable(feature = "rust1", since = "1.0.0")]
1386 #[allow(deprecated)]
1387 impl<'a> Iterator for LinesAny<'a> {
1388     type Item = &'a str;
1389
1390     #[inline]
1391     fn next(&mut self) -> Option<&'a str> {
1392         self.0.next()
1393     }
1394
1395     #[inline]
1396     fn size_hint(&self) -> (usize, Option<usize>) {
1397         self.0.size_hint()
1398     }
1399 }
1400
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 #[allow(deprecated)]
1403 impl<'a> DoubleEndedIterator for LinesAny<'a> {
1404     #[inline]
1405     fn next_back(&mut self) -> Option<&'a str> {
1406         self.0.next_back()
1407     }
1408 }
1409
1410 #[stable(feature = "fused", since = "1.26.0")]
1411 #[allow(deprecated)]
1412 impl FusedIterator for LinesAny<'_> {}
1413
1414 /*
1415 Section: UTF-8 validation
1416 */
1417
1418 // use truncation to fit u64 into usize
1419 const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;
1420
1421 /// Returns `true` if any byte in the word `x` is nonascii (>= 128).
1422 #[inline]
1423 fn contains_nonascii(x: usize) -> bool {
1424     (x & NONASCII_MASK) != 0
1425 }
1426
1427 /// Walks through `v` checking that it's a valid UTF-8 sequence,
1428 /// returning `Ok(())` in that case, or, if it is invalid, `Err(err)`.
1429 #[inline]
1430 fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
1431     let mut index = 0;
1432     let len = v.len();
1433
1434     let usize_bytes = mem::size_of::<usize>();
1435     let ascii_block_size = 2 * usize_bytes;
1436     let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
1437
1438     while index < len {
1439         let old_offset = index;
1440         macro_rules! err {
1441             ($error_len: expr) => {
1442                 return Err(Utf8Error {
1443                     valid_up_to: old_offset,
1444                     error_len: $error_len,
1445                 })
1446             }
1447         }
1448
1449         macro_rules! next { () => {{
1450             index += 1;
1451             // we needed data, but there was none: error!
1452             if index >= len {
1453                 err!(None)
1454             }
1455             v[index]
1456         }}}
1457
1458         let first = v[index];
1459         if first >= 128 {
1460             let w = UTF8_CHAR_WIDTH[first as usize];
1461             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
1462             //        first  C2 80        last DF BF
1463             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
1464             //        first  E0 A0 80     last EF BF BF
1465             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
1466             //               ED A0 80 to       ED BF BF
1467             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1468             //        first  F0 90 80 80  last F4 8F BF BF
1469             //
1470             // Use the UTF-8 syntax from the RFC
1471             //
1472             // https://tools.ietf.org/html/rfc3629
1473             // UTF8-1      = %x00-7F
1474             // UTF8-2      = %xC2-DF UTF8-tail
1475             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1476             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1477             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1478             //               %xF4 %x80-8F 2( UTF8-tail )
1479             match w {
1480                 2 => if next!() & !CONT_MASK != TAG_CONT_U8 {
1481                     err!(Some(1))
1482                 },
1483                 3 => {
1484                     match (first, next!()) {
1485                         (0xE0         , 0xA0 ..= 0xBF) |
1486                         (0xE1 ..= 0xEC, 0x80 ..= 0xBF) |
1487                         (0xED         , 0x80 ..= 0x9F) |
1488                         (0xEE ..= 0xEF, 0x80 ..= 0xBF) => {}
1489                         _ => err!(Some(1))
1490                     }
1491                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1492                         err!(Some(2))
1493                     }
1494                 }
1495                 4 => {
1496                     match (first, next!()) {
1497                         (0xF0         , 0x90 ..= 0xBF) |
1498                         (0xF1 ..= 0xF3, 0x80 ..= 0xBF) |
1499                         (0xF4         , 0x80 ..= 0x8F) => {}
1500                         _ => err!(Some(1))
1501                     }
1502                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1503                         err!(Some(2))
1504                     }
1505                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1506                         err!(Some(3))
1507                     }
1508                 }
1509                 _ => err!(Some(1))
1510             }
1511             index += 1;
1512         } else {
1513             // Ascii case, try to skip forward quickly.
1514             // When the pointer is aligned, read 2 words of data per iteration
1515             // until we find a word containing a non-ascii byte.
1516             let ptr = v.as_ptr();
1517             let align = unsafe {
1518                 // the offset is safe, because `index` is guaranteed inbounds
1519                 ptr.add(index).align_offset(usize_bytes)
1520             };
1521             if align == 0 {
1522                 while index < blocks_end {
1523                     unsafe {
1524                         let block = ptr.add(index) as *const usize;
1525                         // break if there is a nonascii byte
1526                         let zu = contains_nonascii(*block);
1527                         let zv = contains_nonascii(*block.offset(1));
1528                         if zu | zv {
1529                             break;
1530                         }
1531                     }
1532                     index += ascii_block_size;
1533                 }
1534                 // step from the point where the wordwise loop stopped
1535                 while index < len && v[index] < 128 {
1536                     index += 1;
1537                 }
1538             } else {
1539                 index += 1;
1540             }
1541         }
1542     }
1543
1544     Ok(())
1545 }
1546
1547 // https://tools.ietf.org/html/rfc3629
1548 static UTF8_CHAR_WIDTH: [u8; 256] = [
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, // 0x1F
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, // 0x3F
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, // 0x5F
1555 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1556 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
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, // 0x9F
1559 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1560 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1561 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1562 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1563 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1564 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1565 ];
1566
1567 /// Given a first byte, determines how many bytes are in this UTF-8 character.
1568 #[unstable(feature = "str_internals", issue = "0")]
1569 #[inline]
1570 pub fn utf8_char_width(b: u8) -> usize {
1571     UTF8_CHAR_WIDTH[b as usize] as usize
1572 }
1573
1574 /// Mask of the value bits of a continuation byte.
1575 const CONT_MASK: u8 = 0b0011_1111;
1576 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte.
1577 const TAG_CONT_U8: u8 = 0b1000_0000;
1578
1579 /*
1580 Section: Trait implementations
1581 */
1582
1583 mod traits {
1584     use cmp::Ordering;
1585     use ops;
1586     use slice::{self, SliceIndex};
1587
1588     /// Implements ordering of strings.
1589     ///
1590     /// Strings are ordered  lexicographically by their byte values.  This orders Unicode code
1591     /// points based on their positions in the code charts.  This is not necessarily the same as
1592     /// "alphabetical" order, which varies by language and locale.  Sorting strings according to
1593     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1594     /// the `str` type.
1595     #[stable(feature = "rust1", since = "1.0.0")]
1596     impl Ord for str {
1597         #[inline]
1598         fn cmp(&self, other: &str) -> Ordering {
1599             self.as_bytes().cmp(other.as_bytes())
1600         }
1601     }
1602
1603     #[stable(feature = "rust1", since = "1.0.0")]
1604     impl PartialEq for str {
1605         #[inline]
1606         fn eq(&self, other: &str) -> bool {
1607             self.as_bytes() == other.as_bytes()
1608         }
1609         #[inline]
1610         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1611     }
1612
1613     #[stable(feature = "rust1", since = "1.0.0")]
1614     impl Eq for str {}
1615
1616     /// Implements comparison operations on strings.
1617     ///
1618     /// Strings are compared lexicographically by their byte values.  This compares Unicode code
1619     /// points based on their positions in the code charts.  This is not necessarily the same as
1620     /// "alphabetical" order, which varies by language and locale.  Comparing strings according to
1621     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1622     /// the `str` type.
1623     #[stable(feature = "rust1", since = "1.0.0")]
1624     impl PartialOrd for str {
1625         #[inline]
1626         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1627             Some(self.cmp(other))
1628         }
1629     }
1630
1631     /// Implements substring slicing with syntax `&self[begin .. end]`.
1632     ///
1633     /// Returns a slice of the given string from the byte range
1634     /// [`begin`..`end`).
1635     ///
1636     /// This operation is `O(1)`.
1637     ///
1638     /// # Panics
1639     ///
1640     /// Panics if `begin` or `end` does not point to the starting
1641     /// byte offset of a character (as defined by `is_char_boundary`).
1642     /// Requires that `begin <= end` and `end <= len` where `len` is the
1643     /// length of the string.
1644     ///
1645     /// # Examples
1646     ///
1647     /// ```
1648     /// let s = "Löwe 老虎 Léopard";
1649     /// assert_eq!(&s[0 .. 1], "L");
1650     ///
1651     /// assert_eq!(&s[1 .. 9], "öwe 老");
1652     ///
1653     /// // these will panic:
1654     /// // byte 2 lies within `ö`:
1655     /// // &s[2 ..3];
1656     ///
1657     /// // byte 8 lies within `老`
1658     /// // &s[1 .. 8];
1659     ///
1660     /// // byte 100 is outside the string
1661     /// // &s[3 .. 100];
1662     /// ```
1663     #[stable(feature = "rust1", since = "1.0.0")]
1664     impl ops::Index<ops::Range<usize>> for str {
1665         type Output = str;
1666         #[inline]
1667         fn index(&self, index: ops::Range<usize>) -> &str {
1668             index.index(self)
1669         }
1670     }
1671
1672     /// Implements mutable substring slicing with syntax
1673     /// `&mut self[begin .. end]`.
1674     ///
1675     /// Returns a mutable slice of the given string from the byte range
1676     /// [`begin`..`end`).
1677     ///
1678     /// This operation is `O(1)`.
1679     ///
1680     /// # Panics
1681     ///
1682     /// Panics if `begin` or `end` does not point to the starting
1683     /// byte offset of a character (as defined by `is_char_boundary`).
1684     /// Requires that `begin <= end` and `end <= len` where `len` is the
1685     /// length of the string.
1686     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1687     impl ops::IndexMut<ops::Range<usize>> for str {
1688         #[inline]
1689         fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
1690             index.index_mut(self)
1691         }
1692     }
1693
1694     /// Implements substring slicing with syntax `&self[.. end]`.
1695     ///
1696     /// Returns a slice of the string from the beginning to byte offset
1697     /// `end`.
1698     ///
1699     /// Equivalent to `&self[0 .. end]`.
1700     #[stable(feature = "rust1", since = "1.0.0")]
1701     impl ops::Index<ops::RangeTo<usize>> for str {
1702         type Output = str;
1703
1704         #[inline]
1705         fn index(&self, index: ops::RangeTo<usize>) -> &str {
1706             index.index(self)
1707         }
1708     }
1709
1710     /// Implements mutable substring slicing with syntax `&mut self[.. end]`.
1711     ///
1712     /// Returns a mutable slice of the string from the beginning to byte offset
1713     /// `end`.
1714     ///
1715     /// Equivalent to `&mut self[0 .. end]`.
1716     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1717     impl ops::IndexMut<ops::RangeTo<usize>> for str {
1718         #[inline]
1719         fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
1720             index.index_mut(self)
1721         }
1722     }
1723
1724     /// Implements substring slicing with syntax `&self[begin ..]`.
1725     ///
1726     /// Returns a slice of the string from byte offset `begin`
1727     /// to the end of the string.
1728     ///
1729     /// Equivalent to `&self[begin .. len]`.
1730     #[stable(feature = "rust1", since = "1.0.0")]
1731     impl ops::Index<ops::RangeFrom<usize>> for str {
1732         type Output = str;
1733
1734         #[inline]
1735         fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1736             index.index(self)
1737         }
1738     }
1739
1740     /// Implements mutable substring slicing with syntax `&mut self[begin ..]`.
1741     ///
1742     /// Returns a mutable slice of the string from byte offset `begin`
1743     /// to the end of the string.
1744     ///
1745     /// Equivalent to `&mut self[begin .. len]`.
1746     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1747     impl ops::IndexMut<ops::RangeFrom<usize>> for str {
1748         #[inline]
1749         fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
1750             index.index_mut(self)
1751         }
1752     }
1753
1754     /// Implements substring slicing with syntax `&self[..]`.
1755     ///
1756     /// Returns a slice of the whole string. This operation can
1757     /// never panic.
1758     ///
1759     /// Equivalent to `&self[0 .. len]`.
1760     #[stable(feature = "rust1", since = "1.0.0")]
1761     impl ops::Index<ops::RangeFull> for str {
1762         type Output = str;
1763
1764         #[inline]
1765         fn index(&self, _index: ops::RangeFull) -> &str {
1766             self
1767         }
1768     }
1769
1770     /// Implements mutable substring slicing with syntax `&mut self[..]`.
1771     ///
1772     /// Returns a mutable slice of the whole string. This operation can
1773     /// never panic.
1774     ///
1775     /// Equivalent to `&mut self[0 .. len]`.
1776     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1777     impl ops::IndexMut<ops::RangeFull> for str {
1778         #[inline]
1779         fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
1780             self
1781         }
1782     }
1783
1784     #[stable(feature = "inclusive_range", since = "1.26.0")]
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     #[stable(feature = "inclusive_range", since = "1.26.0")]
1795     impl ops::Index<ops::RangeToInclusive<usize>> for str {
1796         type Output = str;
1797
1798         #[inline]
1799         fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
1800             index.index(self)
1801         }
1802     }
1803
1804     #[stable(feature = "inclusive_range", since = "1.26.0")]
1805     impl ops::IndexMut<ops::RangeInclusive<usize>> for str {
1806         #[inline]
1807         fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
1808             index.index_mut(self)
1809         }
1810     }
1811     #[stable(feature = "inclusive_range", since = "1.26.0")]
1812     impl ops::IndexMut<ops::RangeToInclusive<usize>> for str {
1813         #[inline]
1814         fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
1815             index.index_mut(self)
1816         }
1817     }
1818
1819     #[inline(never)]
1820     #[cold]
1821     fn str_index_overflow_fail() -> ! {
1822         panic!("attempted to index str up to maximum usize");
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().add(self.start);
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().add(self.start);
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             // cannot 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().add(self.start);
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().add(self.start);
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     #[stable(feature = "inclusive_range", since = "1.26.0")]
2001     impl SliceIndex<str> for ops::RangeInclusive<usize> {
2002         type Output = str;
2003         #[inline]
2004         fn get(self, slice: &str) -> Option<&Self::Output> {
2005             if *self.end() == usize::max_value() { None }
2006             else { (*self.start()..self.end()+1).get(slice) }
2007         }
2008         #[inline]
2009         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2010             if *self.end() == usize::max_value() { None }
2011             else { (*self.start()..self.end()+1).get_mut(slice) }
2012         }
2013         #[inline]
2014         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2015             (*self.start()..self.end()+1).get_unchecked(slice)
2016         }
2017         #[inline]
2018         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2019             (*self.start()..self.end()+1).get_unchecked_mut(slice)
2020         }
2021         #[inline]
2022         fn index(self, slice: &str) -> &Self::Output {
2023             if *self.end() == usize::max_value() { str_index_overflow_fail(); }
2024             (*self.start()..self.end()+1).index(slice)
2025         }
2026         #[inline]
2027         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2028             if *self.end() == usize::max_value() { str_index_overflow_fail(); }
2029             (*self.start()..self.end()+1).index_mut(slice)
2030         }
2031     }
2032
2033
2034
2035     #[stable(feature = "inclusive_range", since = "1.26.0")]
2036     impl SliceIndex<str> for ops::RangeToInclusive<usize> {
2037         type Output = str;
2038         #[inline]
2039         fn get(self, slice: &str) -> Option<&Self::Output> {
2040             if self.end == usize::max_value() { None }
2041             else { (..self.end+1).get(slice) }
2042         }
2043         #[inline]
2044         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2045             if self.end == usize::max_value() { None }
2046             else { (..self.end+1).get_mut(slice) }
2047         }
2048         #[inline]
2049         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2050             (..self.end+1).get_unchecked(slice)
2051         }
2052         #[inline]
2053         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2054             (..self.end+1).get_unchecked_mut(slice)
2055         }
2056         #[inline]
2057         fn index(self, slice: &str) -> &Self::Output {
2058             if self.end == usize::max_value() { str_index_overflow_fail(); }
2059             (..self.end+1).index(slice)
2060         }
2061         #[inline]
2062         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2063             if self.end == usize::max_value() { str_index_overflow_fail(); }
2064             (..self.end+1).index_mut(slice)
2065         }
2066     }
2067 }
2068
2069 // truncate `&str` to length at most equal to `max`
2070 // return `true` if it were truncated, and the new str.
2071 fn truncate_to_char_boundary(s: &str, mut max: usize) -> (bool, &str) {
2072     if max >= s.len() {
2073         (false, s)
2074     } else {
2075         while !s.is_char_boundary(max) {
2076             max -= 1;
2077         }
2078         (true, &s[..max])
2079     }
2080 }
2081
2082 #[inline(never)]
2083 #[cold]
2084 fn slice_error_fail(s: &str, begin: usize, end: usize) -> ! {
2085     const MAX_DISPLAY_LENGTH: usize = 256;
2086     let (truncated, s_trunc) = truncate_to_char_boundary(s, MAX_DISPLAY_LENGTH);
2087     let ellipsis = if truncated { "[...]" } else { "" };
2088
2089     // 1. out of bounds
2090     if begin > s.len() || end > s.len() {
2091         let oob_index = if begin > s.len() { begin } else { end };
2092         panic!("byte index {} is out of bounds of `{}`{}", oob_index, s_trunc, ellipsis);
2093     }
2094
2095     // 2. begin <= end
2096     assert!(begin <= end, "begin <= end ({} <= {}) when slicing `{}`{}",
2097             begin, end, s_trunc, ellipsis);
2098
2099     // 3. character boundary
2100     let index = if !s.is_char_boundary(begin) { begin } else { end };
2101     // find the character
2102     let mut char_start = index;
2103     while !s.is_char_boundary(char_start) {
2104         char_start -= 1;
2105     }
2106     // `char_start` must be less than len and a char boundary
2107     let ch = s[char_start..].chars().next().unwrap();
2108     let char_range = char_start .. char_start + ch.len_utf8();
2109     panic!("byte index {} is not a char boundary; it is inside {:?} (bytes {:?}) of `{}`{}",
2110            index, ch, char_range, s_trunc, ellipsis);
2111 }
2112
2113 #[lang = "str"]
2114 #[cfg(not(test))]
2115 impl str {
2116     /// Returns the length of `self`.
2117     ///
2118     /// This length is in bytes, not [`char`]s or graphemes. In other words,
2119     /// it may not be what a human considers the length of the string.
2120     ///
2121     /// # Examples
2122     ///
2123     /// Basic usage:
2124     ///
2125     /// ```
2126     /// let len = "foo".len();
2127     /// assert_eq!(3, len);
2128     ///
2129     /// let len = "ƒoo".len(); // fancy f!
2130     /// assert_eq!(4, len);
2131     /// ```
2132     #[stable(feature = "rust1", since = "1.0.0")]
2133     #[inline]
2134     #[rustc_const_unstable(feature = "const_str_len")]
2135     pub const fn len(&self) -> usize {
2136         self.as_bytes().len()
2137     }
2138
2139     /// Returns `true` if `self` has a length of zero bytes.
2140     ///
2141     /// # Examples
2142     ///
2143     /// Basic usage:
2144     ///
2145     /// ```
2146     /// let s = "";
2147     /// assert!(s.is_empty());
2148     ///
2149     /// let s = "not empty";
2150     /// assert!(!s.is_empty());
2151     /// ```
2152     #[inline]
2153     #[stable(feature = "rust1", since = "1.0.0")]
2154     #[rustc_const_unstable(feature = "const_str_len")]
2155     pub const fn is_empty(&self) -> bool {
2156         self.len() == 0
2157     }
2158
2159     /// Checks that `index`-th byte lies at the start and/or end of a
2160     /// UTF-8 code point sequence.
2161     ///
2162     /// The start and end of the string (when `index == self.len()`) are
2163     /// considered to be
2164     /// boundaries.
2165     ///
2166     /// Returns `false` if `index` is greater than `self.len()`.
2167     ///
2168     /// # Examples
2169     ///
2170     /// ```
2171     /// let s = "Löwe 老虎 Léopard";
2172     /// assert!(s.is_char_boundary(0));
2173     /// // start of `老`
2174     /// assert!(s.is_char_boundary(6));
2175     /// assert!(s.is_char_boundary(s.len()));
2176     ///
2177     /// // second byte of `ö`
2178     /// assert!(!s.is_char_boundary(2));
2179     ///
2180     /// // third byte of `老`
2181     /// assert!(!s.is_char_boundary(8));
2182     /// ```
2183     #[stable(feature = "is_char_boundary", since = "1.9.0")]
2184     #[inline]
2185     pub fn is_char_boundary(&self, index: usize) -> bool {
2186         // 0 and len are always ok.
2187         // Test for 0 explicitly so that it can optimize out the check
2188         // easily and skip reading string data for that case.
2189         if index == 0 || index == self.len() { return true; }
2190         match self.as_bytes().get(index) {
2191             None => false,
2192             // This is bit magic equivalent to: b < 128 || b >= 192
2193             Some(&b) => (b as i8) >= -0x40,
2194         }
2195     }
2196
2197     /// Converts a string slice to a byte slice. To convert the byte slice back
2198     /// into a string slice, use the [`str::from_utf8`] function.
2199     ///
2200     /// [`str::from_utf8`]: ./str/fn.from_utf8.html
2201     ///
2202     /// # Examples
2203     ///
2204     /// Basic usage:
2205     ///
2206     /// ```
2207     /// let bytes = "bors".as_bytes();
2208     /// assert_eq!(b"bors", bytes);
2209     /// ```
2210     #[stable(feature = "rust1", since = "1.0.0")]
2211     #[inline(always)]
2212     #[rustc_const_unstable(feature="const_str_as_bytes")]
2213     pub const fn as_bytes(&self) -> &[u8] {
2214         union Slices<'a> {
2215             str: &'a str,
2216             slice: &'a [u8],
2217         }
2218         unsafe { Slices { str: self }.slice }
2219     }
2220
2221     /// Converts a mutable string slice to a mutable byte slice. To convert the
2222     /// mutable byte slice back into a mutable string slice, use the
2223     /// [`str::from_utf8_mut`] function.
2224     ///
2225     /// [`str::from_utf8_mut`]: ./str/fn.from_utf8_mut.html
2226     ///
2227     /// # Examples
2228     ///
2229     /// Basic usage:
2230     ///
2231     /// ```
2232     /// let mut s = String::from("Hello");
2233     /// let bytes = unsafe { s.as_bytes_mut() };
2234     ///
2235     /// assert_eq!(b"Hello", bytes);
2236     /// ```
2237     ///
2238     /// Mutability:
2239     ///
2240     /// ```
2241     /// let mut s = String::from("🗻∈🌏");
2242     ///
2243     /// unsafe {
2244     ///     let bytes = s.as_bytes_mut();
2245     ///
2246     ///     bytes[0] = 0xF0;
2247     ///     bytes[1] = 0x9F;
2248     ///     bytes[2] = 0x8D;
2249     ///     bytes[3] = 0x94;
2250     /// }
2251     ///
2252     /// assert_eq!("🍔∈🌏", s);
2253     /// ```
2254     #[stable(feature = "str_mut_extras", since = "1.20.0")]
2255     #[inline(always)]
2256     pub unsafe fn as_bytes_mut(&mut self) -> &mut [u8] {
2257         &mut *(self as *mut str as *mut [u8])
2258     }
2259
2260     /// Converts a string slice to a raw pointer.
2261     ///
2262     /// As string slices are a slice of bytes, the raw pointer points to a
2263     /// [`u8`]. This pointer will be pointing to the first byte of the string
2264     /// slice.
2265     ///
2266     /// [`u8`]: primitive.u8.html
2267     ///
2268     /// # Examples
2269     ///
2270     /// Basic usage:
2271     ///
2272     /// ```
2273     /// let s = "Hello";
2274     /// let ptr = s.as_ptr();
2275     /// ```
2276     #[stable(feature = "rust1", since = "1.0.0")]
2277     #[inline]
2278     pub const fn as_ptr(&self) -> *const u8 {
2279         self as *const str as *const u8
2280     }
2281
2282     /// Returns a subslice of `str`.
2283     ///
2284     /// This is the non-panicking alternative to indexing the `str`. Returns
2285     /// [`None`] whenever equivalent indexing operation would panic.
2286     ///
2287     /// [`None`]: option/enum.Option.html#variant.None
2288     ///
2289     /// # Examples
2290     ///
2291     /// ```
2292     /// let v = String::from("🗻∈🌏");
2293     ///
2294     /// assert_eq!(Some("🗻"), v.get(0..4));
2295     ///
2296     /// // indices not on UTF-8 sequence boundaries
2297     /// assert!(v.get(1..).is_none());
2298     /// assert!(v.get(..8).is_none());
2299     ///
2300     /// // out of bounds
2301     /// assert!(v.get(..42).is_none());
2302     /// ```
2303     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2304     #[inline]
2305     pub fn get<I: SliceIndex<str>>(&self, i: I) -> Option<&I::Output> {
2306         i.get(self)
2307     }
2308
2309     /// Returns a mutable subslice of `str`.
2310     ///
2311     /// This is the non-panicking alternative to indexing the `str`. Returns
2312     /// [`None`] whenever equivalent indexing operation would panic.
2313     ///
2314     /// [`None`]: option/enum.Option.html#variant.None
2315     ///
2316     /// # Examples
2317     ///
2318     /// ```
2319     /// let mut v = String::from("hello");
2320     /// // correct length
2321     /// assert!(v.get_mut(0..5).is_some());
2322     /// // out of bounds
2323     /// assert!(v.get_mut(..42).is_none());
2324     /// assert_eq!(Some("he"), v.get_mut(0..2).map(|v| &*v));
2325     ///
2326     /// assert_eq!("hello", v);
2327     /// {
2328     ///     let s = v.get_mut(0..2);
2329     ///     let s = s.map(|s| {
2330     ///         s.make_ascii_uppercase();
2331     ///         &*s
2332     ///     });
2333     ///     assert_eq!(Some("HE"), s);
2334     /// }
2335     /// assert_eq!("HEllo", v);
2336     /// ```
2337     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2338     #[inline]
2339     pub fn get_mut<I: SliceIndex<str>>(&mut self, i: I) -> Option<&mut I::Output> {
2340         i.get_mut(self)
2341     }
2342
2343     /// Returns a unchecked subslice of `str`.
2344     ///
2345     /// This is the unchecked alternative to indexing the `str`.
2346     ///
2347     /// # Safety
2348     ///
2349     /// Callers of this function are responsible that these preconditions are
2350     /// satisfied:
2351     ///
2352     /// * The starting index must come before the ending index;
2353     /// * Indexes must be within bounds of the original slice;
2354     /// * Indexes must lie on UTF-8 sequence boundaries.
2355     ///
2356     /// Failing that, the returned string slice may reference invalid memory or
2357     /// violate the invariants communicated by the `str` type.
2358     ///
2359     /// # Examples
2360     ///
2361     /// ```
2362     /// let v = "🗻∈🌏";
2363     /// unsafe {
2364     ///     assert_eq!("🗻", v.get_unchecked(0..4));
2365     ///     assert_eq!("∈", v.get_unchecked(4..7));
2366     ///     assert_eq!("🌏", v.get_unchecked(7..11));
2367     /// }
2368     /// ```
2369     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2370     #[inline]
2371     pub unsafe fn get_unchecked<I: SliceIndex<str>>(&self, i: I) -> &I::Output {
2372         i.get_unchecked(self)
2373     }
2374
2375     /// Returns a mutable, unchecked subslice of `str`.
2376     ///
2377     /// This is the unchecked alternative to indexing the `str`.
2378     ///
2379     /// # Safety
2380     ///
2381     /// Callers of this function are responsible that these preconditions are
2382     /// satisfied:
2383     ///
2384     /// * The starting index must come before the ending index;
2385     /// * Indexes must be within bounds of the original slice;
2386     /// * Indexes must lie on UTF-8 sequence boundaries.
2387     ///
2388     /// Failing that, the returned string slice may reference invalid memory or
2389     /// violate the invariants communicated by the `str` type.
2390     ///
2391     /// # Examples
2392     ///
2393     /// ```
2394     /// let mut v = String::from("🗻∈🌏");
2395     /// unsafe {
2396     ///     assert_eq!("🗻", v.get_unchecked_mut(0..4));
2397     ///     assert_eq!("∈", v.get_unchecked_mut(4..7));
2398     ///     assert_eq!("🌏", v.get_unchecked_mut(7..11));
2399     /// }
2400     /// ```
2401     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2402     #[inline]
2403     pub unsafe fn get_unchecked_mut<I: SliceIndex<str>>(&mut self, i: I) -> &mut I::Output {
2404         i.get_unchecked_mut(self)
2405     }
2406
2407     /// Creates a string slice from another string slice, bypassing safety
2408     /// checks.
2409     ///
2410     /// This is generally not recommended, use with caution! For a safe
2411     /// alternative see [`str`] and [`Index`].
2412     ///
2413     /// [`str`]: primitive.str.html
2414     /// [`Index`]: ops/trait.Index.html
2415     ///
2416     /// This new slice goes from `begin` to `end`, including `begin` but
2417     /// excluding `end`.
2418     ///
2419     /// To get a mutable string slice instead, see the
2420     /// [`slice_mut_unchecked`] method.
2421     ///
2422     /// [`slice_mut_unchecked`]: #method.slice_mut_unchecked
2423     ///
2424     /// # Safety
2425     ///
2426     /// Callers of this function are responsible that three preconditions are
2427     /// satisfied:
2428     ///
2429     /// * `begin` must come before `end`.
2430     /// * `begin` and `end` must be byte positions within the string slice.
2431     /// * `begin` and `end` must lie on UTF-8 sequence boundaries.
2432     ///
2433     /// # Examples
2434     ///
2435     /// Basic usage:
2436     ///
2437     /// ```
2438     /// let s = "Löwe 老虎 Léopard";
2439     ///
2440     /// unsafe {
2441     ///     assert_eq!("Löwe 老虎 Léopard", s.slice_unchecked(0, 21));
2442     /// }
2443     ///
2444     /// let s = "Hello, world!";
2445     ///
2446     /// unsafe {
2447     ///     assert_eq!("world", s.slice_unchecked(7, 12));
2448     /// }
2449     /// ```
2450     #[stable(feature = "rust1", since = "1.0.0")]
2451     #[rustc_deprecated(since = "1.29.0", reason = "use `get_unchecked(begin..end)` instead")]
2452     #[inline]
2453     pub unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str {
2454         (begin..end).get_unchecked(self)
2455     }
2456
2457     /// Creates a string slice from another string slice, bypassing safety
2458     /// checks.
2459     /// This is generally not recommended, use with caution! For a safe
2460     /// alternative see [`str`] and [`IndexMut`].
2461     ///
2462     /// [`str`]: primitive.str.html
2463     /// [`IndexMut`]: ops/trait.IndexMut.html
2464     ///
2465     /// This new slice goes from `begin` to `end`, including `begin` but
2466     /// excluding `end`.
2467     ///
2468     /// To get an immutable string slice instead, see the
2469     /// [`slice_unchecked`] method.
2470     ///
2471     /// [`slice_unchecked`]: #method.slice_unchecked
2472     ///
2473     /// # Safety
2474     ///
2475     /// Callers of this function are responsible that three preconditions are
2476     /// satisfied:
2477     ///
2478     /// * `begin` must come before `end`.
2479     /// * `begin` and `end` must be byte positions within the string slice.
2480     /// * `begin` and `end` must lie on UTF-8 sequence boundaries.
2481     #[stable(feature = "str_slice_mut", since = "1.5.0")]
2482     #[rustc_deprecated(since = "1.29.0", reason = "use `get_unchecked_mut(begin..end)` instead")]
2483     #[inline]
2484     pub unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str {
2485         (begin..end).get_unchecked_mut(self)
2486     }
2487
2488     /// Divide one string slice into two at an index.
2489     ///
2490     /// The argument, `mid`, should be a byte offset from the start of the
2491     /// string. It must also be on the boundary of a UTF-8 code point.
2492     ///
2493     /// The two slices returned go from the start of the string slice to `mid`,
2494     /// and from `mid` to the end of the string slice.
2495     ///
2496     /// To get mutable string slices instead, see the [`split_at_mut`]
2497     /// method.
2498     ///
2499     /// [`split_at_mut`]: #method.split_at_mut
2500     ///
2501     /// # Panics
2502     ///
2503     /// Panics if `mid` is not on a UTF-8 code point boundary, or if it is
2504     /// beyond the last code point of the string slice.
2505     ///
2506     /// # Examples
2507     ///
2508     /// Basic usage:
2509     ///
2510     /// ```
2511     /// let s = "Per Martin-Löf";
2512     ///
2513     /// let (first, last) = s.split_at(3);
2514     ///
2515     /// assert_eq!("Per", first);
2516     /// assert_eq!(" Martin-Löf", last);
2517     /// ```
2518     #[inline]
2519     #[stable(feature = "str_split_at", since = "1.4.0")]
2520     pub fn split_at(&self, mid: usize) -> (&str, &str) {
2521         // is_char_boundary checks that the index is in [0, .len()]
2522         if self.is_char_boundary(mid) {
2523             unsafe {
2524                 (self.get_unchecked(0..mid),
2525                  self.get_unchecked(mid..self.len()))
2526             }
2527         } else {
2528             slice_error_fail(self, 0, mid)
2529         }
2530     }
2531
2532     /// Divide one mutable string slice into two at an index.
2533     ///
2534     /// The argument, `mid`, should be a byte offset from the start of the
2535     /// string. It must also be on the boundary of a UTF-8 code point.
2536     ///
2537     /// The two slices returned go from the start of the string slice to `mid`,
2538     /// and from `mid` to the end of the string slice.
2539     ///
2540     /// To get immutable string slices instead, see the [`split_at`] method.
2541     ///
2542     /// [`split_at`]: #method.split_at
2543     ///
2544     /// # Panics
2545     ///
2546     /// Panics if `mid` is not on a UTF-8 code point boundary, or if it is
2547     /// beyond the last code point of the string slice.
2548     ///
2549     /// # Examples
2550     ///
2551     /// Basic usage:
2552     ///
2553     /// ```
2554     /// let mut s = "Per Martin-Löf".to_string();
2555     /// {
2556     ///     let (first, last) = s.split_at_mut(3);
2557     ///     first.make_ascii_uppercase();
2558     ///     assert_eq!("PER", first);
2559     ///     assert_eq!(" Martin-Löf", last);
2560     /// }
2561     /// assert_eq!("PER Martin-Löf", s);
2562     /// ```
2563     #[inline]
2564     #[stable(feature = "str_split_at", since = "1.4.0")]
2565     pub fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str) {
2566         // is_char_boundary checks that the index is in [0, .len()]
2567         if self.is_char_boundary(mid) {
2568             let len = self.len();
2569             let ptr = self.as_ptr() as *mut u8;
2570             unsafe {
2571                 (from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr, mid)),
2572                  from_utf8_unchecked_mut(slice::from_raw_parts_mut(
2573                     ptr.add(mid),
2574                     len - mid
2575                  )))
2576             }
2577         } else {
2578             slice_error_fail(self, 0, mid)
2579         }
2580     }
2581
2582     /// Returns an iterator over the [`char`]s of a string slice.
2583     ///
2584     /// As a string slice consists of valid UTF-8, we can iterate through a
2585     /// string slice by [`char`]. This method returns such an iterator.
2586     ///
2587     /// It's important to remember that [`char`] represents a Unicode Scalar
2588     /// Value, and may not match your idea of what a 'character' is. Iteration
2589     /// over grapheme clusters may be what you actually want.
2590     ///
2591     /// # Examples
2592     ///
2593     /// Basic usage:
2594     ///
2595     /// ```
2596     /// let word = "goodbye";
2597     ///
2598     /// let count = word.chars().count();
2599     /// assert_eq!(7, count);
2600     ///
2601     /// let mut chars = word.chars();
2602     ///
2603     /// assert_eq!(Some('g'), chars.next());
2604     /// assert_eq!(Some('o'), chars.next());
2605     /// assert_eq!(Some('o'), chars.next());
2606     /// assert_eq!(Some('d'), chars.next());
2607     /// assert_eq!(Some('b'), chars.next());
2608     /// assert_eq!(Some('y'), chars.next());
2609     /// assert_eq!(Some('e'), chars.next());
2610     ///
2611     /// assert_eq!(None, chars.next());
2612     /// ```
2613     ///
2614     /// Remember, [`char`]s may not match your human intuition about characters:
2615     ///
2616     /// ```
2617     /// let y = "y̆";
2618     ///
2619     /// let mut chars = y.chars();
2620     ///
2621     /// assert_eq!(Some('y'), chars.next()); // not 'y̆'
2622     /// assert_eq!(Some('\u{0306}'), chars.next());
2623     ///
2624     /// assert_eq!(None, chars.next());
2625     /// ```
2626     #[stable(feature = "rust1", since = "1.0.0")]
2627     #[inline]
2628     pub fn chars(&self) -> Chars {
2629         Chars{iter: self.as_bytes().iter()}
2630     }
2631
2632     /// Returns an iterator over the [`char`]s of a string slice, and their
2633     /// positions.
2634     ///
2635     /// As a string slice consists of valid UTF-8, we can iterate through a
2636     /// string slice by [`char`]. This method returns an iterator of both
2637     /// these [`char`]s, as well as their byte positions.
2638     ///
2639     /// The iterator yields tuples. The position is first, the [`char`] is
2640     /// second.
2641     ///
2642     /// # Examples
2643     ///
2644     /// Basic usage:
2645     ///
2646     /// ```
2647     /// let word = "goodbye";
2648     ///
2649     /// let count = word.char_indices().count();
2650     /// assert_eq!(7, count);
2651     ///
2652     /// let mut char_indices = word.char_indices();
2653     ///
2654     /// assert_eq!(Some((0, 'g')), char_indices.next());
2655     /// assert_eq!(Some((1, 'o')), char_indices.next());
2656     /// assert_eq!(Some((2, 'o')), char_indices.next());
2657     /// assert_eq!(Some((3, 'd')), char_indices.next());
2658     /// assert_eq!(Some((4, 'b')), char_indices.next());
2659     /// assert_eq!(Some((5, 'y')), char_indices.next());
2660     /// assert_eq!(Some((6, 'e')), char_indices.next());
2661     ///
2662     /// assert_eq!(None, char_indices.next());
2663     /// ```
2664     ///
2665     /// Remember, [`char`]s may not match your human intuition about characters:
2666     ///
2667     /// ```
2668     /// let yes = "y̆es";
2669     ///
2670     /// let mut char_indices = yes.char_indices();
2671     ///
2672     /// assert_eq!(Some((0, 'y')), char_indices.next()); // not (0, 'y̆')
2673     /// assert_eq!(Some((1, '\u{0306}')), char_indices.next());
2674     ///
2675     /// // note the 3 here - the last character took up two bytes
2676     /// assert_eq!(Some((3, 'e')), char_indices.next());
2677     /// assert_eq!(Some((4, 's')), char_indices.next());
2678     ///
2679     /// assert_eq!(None, char_indices.next());
2680     /// ```
2681     #[stable(feature = "rust1", since = "1.0.0")]
2682     #[inline]
2683     pub fn char_indices(&self) -> CharIndices {
2684         CharIndices { front_offset: 0, iter: self.chars() }
2685     }
2686
2687     /// An iterator over the bytes of a string slice.
2688     ///
2689     /// As a string slice consists of a sequence of bytes, we can iterate
2690     /// through a string slice by byte. This method returns such an iterator.
2691     ///
2692     /// # Examples
2693     ///
2694     /// Basic usage:
2695     ///
2696     /// ```
2697     /// let mut bytes = "bors".bytes();
2698     ///
2699     /// assert_eq!(Some(b'b'), bytes.next());
2700     /// assert_eq!(Some(b'o'), bytes.next());
2701     /// assert_eq!(Some(b'r'), bytes.next());
2702     /// assert_eq!(Some(b's'), bytes.next());
2703     ///
2704     /// assert_eq!(None, bytes.next());
2705     /// ```
2706     #[stable(feature = "rust1", since = "1.0.0")]
2707     #[inline]
2708     pub fn bytes(&self) -> Bytes {
2709         Bytes(self.as_bytes().iter().cloned())
2710     }
2711
2712     /// Split a string slice by whitespace.
2713     ///
2714     /// The iterator returned will return string slices that are sub-slices of
2715     /// the original string slice, separated by any amount of whitespace.
2716     ///
2717     /// 'Whitespace' is defined according to the terms of the Unicode Derived
2718     /// Core Property `White_Space`. If you only want to split on ASCII whitespace
2719     /// instead, use [`split_ascii_whitespace`].
2720     ///
2721     /// [`split_ascii_whitespace`]: #method.split_ascii_whitespace
2722     ///
2723     /// # Examples
2724     ///
2725     /// Basic usage:
2726     ///
2727     /// ```
2728     /// let mut iter = "A few words".split_whitespace();
2729     ///
2730     /// assert_eq!(Some("A"), iter.next());
2731     /// assert_eq!(Some("few"), iter.next());
2732     /// assert_eq!(Some("words"), iter.next());
2733     ///
2734     /// assert_eq!(None, iter.next());
2735     /// ```
2736     ///
2737     /// All kinds of whitespace are considered:
2738     ///
2739     /// ```
2740     /// let mut iter = " Mary   had\ta\u{2009}little  \n\t lamb".split_whitespace();
2741     /// assert_eq!(Some("Mary"), iter.next());
2742     /// assert_eq!(Some("had"), iter.next());
2743     /// assert_eq!(Some("a"), iter.next());
2744     /// assert_eq!(Some("little"), iter.next());
2745     /// assert_eq!(Some("lamb"), iter.next());
2746     ///
2747     /// assert_eq!(None, iter.next());
2748     /// ```
2749     #[stable(feature = "split_whitespace", since = "1.1.0")]
2750     #[inline]
2751     pub fn split_whitespace(&self) -> SplitWhitespace {
2752         SplitWhitespace { inner: self.split(IsWhitespace).filter(IsNotEmpty) }
2753     }
2754
2755     /// Split a string slice by ASCII whitespace.
2756     ///
2757     /// The iterator returned will return string slices that are sub-slices of
2758     /// the original string slice, separated by any amount of ASCII whitespace.
2759     ///
2760     /// To split by Unicode `Whitespace` instead, use [`split_whitespace`].
2761     ///
2762     /// [`split_whitespace`]: #method.split_whitespace
2763     ///
2764     /// # Examples
2765     ///
2766     /// Basic usage:
2767     ///
2768     /// ```
2769     /// #![feature(split_ascii_whitespace)]
2770     /// let mut iter = "A few words".split_ascii_whitespace();
2771     ///
2772     /// assert_eq!(Some("A"), iter.next());
2773     /// assert_eq!(Some("few"), iter.next());
2774     /// assert_eq!(Some("words"), iter.next());
2775     ///
2776     /// assert_eq!(None, iter.next());
2777     /// ```
2778     ///
2779     /// All kinds of ASCII whitespace are considered:
2780     ///
2781     /// ```
2782     /// let mut iter = " Mary   had\ta little  \n\t lamb".split_whitespace();
2783     /// assert_eq!(Some("Mary"), iter.next());
2784     /// assert_eq!(Some("had"), iter.next());
2785     /// assert_eq!(Some("a"), iter.next());
2786     /// assert_eq!(Some("little"), iter.next());
2787     /// assert_eq!(Some("lamb"), iter.next());
2788     ///
2789     /// assert_eq!(None, iter.next());
2790     /// ```
2791     #[unstable(feature = "split_ascii_whitespace", issue = "48656")]
2792     #[inline]
2793     pub fn split_ascii_whitespace(&self) -> SplitAsciiWhitespace {
2794         let inner = self
2795             .as_bytes()
2796             .split(IsAsciiWhitespace)
2797             .filter(IsNotEmpty)
2798             .map(UnsafeBytesToStr);
2799         SplitAsciiWhitespace { inner }
2800     }
2801
2802     /// An iterator over the lines of a string, as string slices.
2803     ///
2804     /// Lines are ended with either a newline (`\n`) or a carriage return with
2805     /// a line feed (`\r\n`).
2806     ///
2807     /// The final line ending is optional.
2808     ///
2809     /// # Examples
2810     ///
2811     /// Basic usage:
2812     ///
2813     /// ```
2814     /// let text = "foo\r\nbar\n\nbaz\n";
2815     /// let mut lines = text.lines();
2816     ///
2817     /// assert_eq!(Some("foo"), lines.next());
2818     /// assert_eq!(Some("bar"), lines.next());
2819     /// assert_eq!(Some(""), lines.next());
2820     /// assert_eq!(Some("baz"), lines.next());
2821     ///
2822     /// assert_eq!(None, lines.next());
2823     /// ```
2824     ///
2825     /// The final line ending isn't required:
2826     ///
2827     /// ```
2828     /// let text = "foo\nbar\n\r\nbaz";
2829     /// let mut lines = text.lines();
2830     ///
2831     /// assert_eq!(Some("foo"), lines.next());
2832     /// assert_eq!(Some("bar"), lines.next());
2833     /// assert_eq!(Some(""), lines.next());
2834     /// assert_eq!(Some("baz"), lines.next());
2835     ///
2836     /// assert_eq!(None, lines.next());
2837     /// ```
2838     #[stable(feature = "rust1", since = "1.0.0")]
2839     #[inline]
2840     pub fn lines(&self) -> Lines {
2841         Lines(self.split_terminator('\n').map(LinesAnyMap))
2842     }
2843
2844     /// An iterator over the lines of a string.
2845     #[stable(feature = "rust1", since = "1.0.0")]
2846     #[rustc_deprecated(since = "1.4.0", reason = "use lines() instead now")]
2847     #[inline]
2848     #[allow(deprecated)]
2849     pub fn lines_any(&self) -> LinesAny {
2850         LinesAny(self.lines())
2851     }
2852
2853     /// Returns an iterator of `u16` over the string encoded as UTF-16.
2854     ///
2855     /// # Examples
2856     ///
2857     /// Basic usage:
2858     ///
2859     /// ```
2860     /// let text = "Zażółć gęślą jaźń";
2861     ///
2862     /// let utf8_len = text.len();
2863     /// let utf16_len = text.encode_utf16().count();
2864     ///
2865     /// assert!(utf16_len <= utf8_len);
2866     /// ```
2867     #[stable(feature = "encode_utf16", since = "1.8.0")]
2868     pub fn encode_utf16(&self) -> EncodeUtf16 {
2869         EncodeUtf16 { chars: self.chars(), extra: 0 }
2870     }
2871
2872     /// Returns `true` if the given pattern matches a sub-slice of
2873     /// this string slice.
2874     ///
2875     /// Returns `false` if it does not.
2876     ///
2877     /// # Examples
2878     ///
2879     /// Basic usage:
2880     ///
2881     /// ```
2882     /// let bananas = "bananas";
2883     ///
2884     /// assert!(bananas.contains("nana"));
2885     /// assert!(!bananas.contains("apples"));
2886     /// ```
2887     #[stable(feature = "rust1", since = "1.0.0")]
2888     #[inline]
2889     pub fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2890         pat.is_contained_in(self)
2891     }
2892
2893     /// Returns `true` if the given pattern matches a prefix of this
2894     /// string slice.
2895     ///
2896     /// Returns `false` if it does not.
2897     ///
2898     /// # Examples
2899     ///
2900     /// Basic usage:
2901     ///
2902     /// ```
2903     /// let bananas = "bananas";
2904     ///
2905     /// assert!(bananas.starts_with("bana"));
2906     /// assert!(!bananas.starts_with("nana"));
2907     /// ```
2908     #[stable(feature = "rust1", since = "1.0.0")]
2909     pub fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2910         pat.is_prefix_of(self)
2911     }
2912
2913     /// Returns `true` if the given pattern matches a suffix of this
2914     /// string slice.
2915     ///
2916     /// Returns `false` if it does not.
2917     ///
2918     /// # Examples
2919     ///
2920     /// Basic usage:
2921     ///
2922     /// ```
2923     /// let bananas = "bananas";
2924     ///
2925     /// assert!(bananas.ends_with("anas"));
2926     /// assert!(!bananas.ends_with("nana"));
2927     /// ```
2928     #[stable(feature = "rust1", since = "1.0.0")]
2929     pub fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
2930         where P::Searcher: ReverseSearcher<'a>
2931     {
2932         pat.is_suffix_of(self)
2933     }
2934
2935     /// Returns the byte index of the first character of this string slice that
2936     /// matches the pattern.
2937     ///
2938     /// Returns [`None`] if the pattern doesn't match.
2939     ///
2940     /// The pattern can be a `&str`, [`char`], or a closure that determines if
2941     /// a character matches.
2942     ///
2943     /// [`None`]: option/enum.Option.html#variant.None
2944     ///
2945     /// # Examples
2946     ///
2947     /// Simple patterns:
2948     ///
2949     /// ```
2950     /// let s = "Löwe 老虎 Léopard";
2951     ///
2952     /// assert_eq!(s.find('L'), Some(0));
2953     /// assert_eq!(s.find('é'), Some(14));
2954     /// assert_eq!(s.find("Léopard"), Some(13));
2955     /// ```
2956     ///
2957     /// More complex patterns using point-free style and closures:
2958     ///
2959     /// ```
2960     /// let s = "Löwe 老虎 Léopard";
2961     ///
2962     /// assert_eq!(s.find(char::is_whitespace), Some(5));
2963     /// assert_eq!(s.find(char::is_lowercase), Some(1));
2964     /// assert_eq!(s.find(|c: char| c.is_whitespace() || c.is_lowercase()), Some(1));
2965     /// assert_eq!(s.find(|c: char| (c < 'o') && (c > 'a')), Some(4));
2966     /// ```
2967     ///
2968     /// Not finding the pattern:
2969     ///
2970     /// ```
2971     /// let s = "Löwe 老虎 Léopard";
2972     /// let x: &[_] = &['1', '2'];
2973     ///
2974     /// assert_eq!(s.find(x), None);
2975     /// ```
2976     #[stable(feature = "rust1", since = "1.0.0")]
2977     #[inline]
2978     pub fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
2979         pat.into_searcher(self).next_match().map(|(i, _)| i)
2980     }
2981
2982     /// Returns the byte index of the last character of this string slice that
2983     /// matches the pattern.
2984     ///
2985     /// Returns [`None`] if the pattern doesn't match.
2986     ///
2987     /// The pattern can be a `&str`, [`char`], or a closure that determines if
2988     /// a character matches.
2989     ///
2990     /// [`None`]: option/enum.Option.html#variant.None
2991     ///
2992     /// # Examples
2993     ///
2994     /// Simple patterns:
2995     ///
2996     /// ```
2997     /// let s = "Löwe 老虎 Léopard";
2998     ///
2999     /// assert_eq!(s.rfind('L'), Some(13));
3000     /// assert_eq!(s.rfind('é'), Some(14));
3001     /// ```
3002     ///
3003     /// More complex patterns with closures:
3004     ///
3005     /// ```
3006     /// let s = "Löwe 老虎 Léopard";
3007     ///
3008     /// assert_eq!(s.rfind(char::is_whitespace), Some(12));
3009     /// assert_eq!(s.rfind(char::is_lowercase), Some(20));
3010     /// ```
3011     ///
3012     /// Not finding the pattern:
3013     ///
3014     /// ```
3015     /// let s = "Löwe 老虎 Léopard";
3016     /// let x: &[_] = &['1', '2'];
3017     ///
3018     /// assert_eq!(s.rfind(x), None);
3019     /// ```
3020     #[stable(feature = "rust1", since = "1.0.0")]
3021     #[inline]
3022     pub fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
3023         where P::Searcher: ReverseSearcher<'a>
3024     {
3025         pat.into_searcher(self).next_match_back().map(|(i, _)| i)
3026     }
3027
3028     /// An iterator over substrings of this string slice, separated by
3029     /// characters matched by a pattern.
3030     ///
3031     /// The pattern can be a `&str`, [`char`], or a closure that determines the
3032     /// split.
3033     ///
3034     /// # Iterator behavior
3035     ///
3036     /// The returned iterator will be a [`DoubleEndedIterator`] if the pattern
3037     /// allows a reverse search and forward/reverse search yields the same
3038     /// elements. This is true for, eg, [`char`] but not for `&str`.
3039     ///
3040     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3041     ///
3042     /// If the pattern allows a reverse search but its results might differ
3043     /// from a forward search, the [`rsplit`] method can be used.
3044     ///
3045     /// [`rsplit`]: #method.rsplit
3046     ///
3047     /// # Examples
3048     ///
3049     /// Simple patterns:
3050     ///
3051     /// ```
3052     /// let v: Vec<&str> = "Mary had a little lamb".split(' ').collect();
3053     /// assert_eq!(v, ["Mary", "had", "a", "little", "lamb"]);
3054     ///
3055     /// let v: Vec<&str> = "".split('X').collect();
3056     /// assert_eq!(v, [""]);
3057     ///
3058     /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
3059     /// assert_eq!(v, ["lion", "", "tiger", "leopard"]);
3060     ///
3061     /// let v: Vec<&str> = "lion::tiger::leopard".split("::").collect();
3062     /// assert_eq!(v, ["lion", "tiger", "leopard"]);
3063     ///
3064     /// let v: Vec<&str> = "abc1def2ghi".split(char::is_numeric).collect();
3065     /// assert_eq!(v, ["abc", "def", "ghi"]);
3066     ///
3067     /// let v: Vec<&str> = "lionXtigerXleopard".split(char::is_uppercase).collect();
3068     /// assert_eq!(v, ["lion", "tiger", "leopard"]);
3069     /// ```
3070     ///
3071     /// A more complex pattern, using a closure:
3072     ///
3073     /// ```
3074     /// let v: Vec<&str> = "abc1defXghi".split(|c| c == '1' || c == 'X').collect();
3075     /// assert_eq!(v, ["abc", "def", "ghi"]);
3076     /// ```
3077     ///
3078     /// If a string contains multiple contiguous separators, you will end up
3079     /// with empty strings in the output:
3080     ///
3081     /// ```
3082     /// let x = "||||a||b|c".to_string();
3083     /// let d: Vec<_> = x.split('|').collect();
3084     ///
3085     /// assert_eq!(d, &["", "", "", "", "a", "", "b", "c"]);
3086     /// ```
3087     ///
3088     /// Contiguous separators are separated by the empty string.
3089     ///
3090     /// ```
3091     /// let x = "(///)".to_string();
3092     /// let d: Vec<_> = x.split('/').collect();
3093     ///
3094     /// assert_eq!(d, &["(", "", "", ")"]);
3095     /// ```
3096     ///
3097     /// Separators at the start or end of a string are neighbored
3098     /// by empty strings.
3099     ///
3100     /// ```
3101     /// let d: Vec<_> = "010".split("0").collect();
3102     /// assert_eq!(d, &["", "1", ""]);
3103     /// ```
3104     ///
3105     /// When the empty string is used as a separator, it separates
3106     /// every character in the string, along with the beginning
3107     /// and end of the string.
3108     ///
3109     /// ```
3110     /// let f: Vec<_> = "rust".split("").collect();
3111     /// assert_eq!(f, &["", "r", "u", "s", "t", ""]);
3112     /// ```
3113     ///
3114     /// Contiguous separators can lead to possibly surprising behavior
3115     /// when whitespace is used as the separator. This code is correct:
3116     ///
3117     /// ```
3118     /// let x = "    a  b c".to_string();
3119     /// let d: Vec<_> = x.split(' ').collect();
3120     ///
3121     /// assert_eq!(d, &["", "", "", "", "a", "", "b", "c"]);
3122     /// ```
3123     ///
3124     /// It does _not_ give you:
3125     ///
3126     /// ```,ignore
3127     /// assert_eq!(d, &["a", "b", "c"]);
3128     /// ```
3129     ///
3130     /// Use [`split_whitespace`] for this behavior.
3131     ///
3132     /// [`split_whitespace`]: #method.split_whitespace
3133     #[stable(feature = "rust1", since = "1.0.0")]
3134     #[inline]
3135     pub fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
3136         Split(SplitInternal {
3137             start: 0,
3138             end: self.len(),
3139             matcher: pat.into_searcher(self),
3140             allow_trailing_empty: true,
3141             finished: false,
3142         })
3143     }
3144
3145     /// An iterator over substrings of the given string slice, separated by
3146     /// characters matched by a pattern and yielded in reverse order.
3147     ///
3148     /// The pattern can be a `&str`, [`char`], or a closure that determines the
3149     /// split.
3150     ///
3151     /// # Iterator behavior
3152     ///
3153     /// The returned iterator requires that the pattern supports a reverse
3154     /// search, and it will be a [`DoubleEndedIterator`] if a forward/reverse
3155     /// search yields the same elements.
3156     ///
3157     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3158     ///
3159     /// For iterating from the front, the [`split`] method can be used.
3160     ///
3161     /// [`split`]: #method.split
3162     ///
3163     /// # Examples
3164     ///
3165     /// Simple patterns:
3166     ///
3167     /// ```
3168     /// let v: Vec<&str> = "Mary had a little lamb".rsplit(' ').collect();
3169     /// assert_eq!(v, ["lamb", "little", "a", "had", "Mary"]);
3170     ///
3171     /// let v: Vec<&str> = "".rsplit('X').collect();
3172     /// assert_eq!(v, [""]);
3173     ///
3174     /// let v: Vec<&str> = "lionXXtigerXleopard".rsplit('X').collect();
3175     /// assert_eq!(v, ["leopard", "tiger", "", "lion"]);
3176     ///
3177     /// let v: Vec<&str> = "lion::tiger::leopard".rsplit("::").collect();
3178     /// assert_eq!(v, ["leopard", "tiger", "lion"]);
3179     /// ```
3180     ///
3181     /// A more complex pattern, using a closure:
3182     ///
3183     /// ```
3184     /// let v: Vec<&str> = "abc1defXghi".rsplit(|c| c == '1' || c == 'X').collect();
3185     /// assert_eq!(v, ["ghi", "def", "abc"]);
3186     /// ```
3187     #[stable(feature = "rust1", since = "1.0.0")]
3188     #[inline]
3189     pub fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
3190         where P::Searcher: ReverseSearcher<'a>
3191     {
3192         RSplit(self.split(pat).0)
3193     }
3194
3195     /// An iterator over substrings of the given string slice, separated by
3196     /// characters matched by a pattern.
3197     ///
3198     /// The pattern can be a `&str`, [`char`], or a closure that determines the
3199     /// split.
3200     ///
3201     /// Equivalent to [`split`], except that the trailing substring
3202     /// is skipped if empty.
3203     ///
3204     /// [`split`]: #method.split
3205     ///
3206     /// This method can be used for string data that is _terminated_,
3207     /// rather than _separated_ by a pattern.
3208     ///
3209     /// # Iterator behavior
3210     ///
3211     /// The returned iterator will be a [`DoubleEndedIterator`] if the pattern
3212     /// allows a reverse search and forward/reverse search yields the same
3213     /// elements. This is true for, eg, [`char`] but not for `&str`.
3214     ///
3215     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3216     ///
3217     /// If the pattern allows a reverse search but its results might differ
3218     /// from a forward search, the [`rsplit_terminator`] method can be used.
3219     ///
3220     /// [`rsplit_terminator`]: #method.rsplit_terminator
3221     ///
3222     /// # Examples
3223     ///
3224     /// Basic usage:
3225     ///
3226     /// ```
3227     /// let v: Vec<&str> = "A.B.".split_terminator('.').collect();
3228     /// assert_eq!(v, ["A", "B"]);
3229     ///
3230     /// let v: Vec<&str> = "A..B..".split_terminator(".").collect();
3231     /// assert_eq!(v, ["A", "", "B", ""]);
3232     /// ```
3233     #[stable(feature = "rust1", since = "1.0.0")]
3234     #[inline]
3235     pub fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
3236         SplitTerminator(SplitInternal {
3237             allow_trailing_empty: false,
3238             ..self.split(pat).0
3239         })
3240     }
3241
3242     /// An iterator over substrings of `self`, separated by characters
3243     /// matched by a pattern and yielded in reverse order.
3244     ///
3245     /// The pattern can be a simple `&str`, [`char`], or a closure that
3246     /// determines the split.
3247     /// Additional libraries might provide more complex patterns like
3248     /// regular expressions.
3249     ///
3250     /// Equivalent to [`split`], except that the trailing substring is
3251     /// skipped if empty.
3252     ///
3253     /// [`split`]: #method.split
3254     ///
3255     /// This method can be used for string data that is _terminated_,
3256     /// rather than _separated_ by a pattern.
3257     ///
3258     /// # Iterator behavior
3259     ///
3260     /// The returned iterator requires that the pattern supports a
3261     /// reverse search, and it will be double ended if a forward/reverse
3262     /// search yields the same elements.
3263     ///
3264     /// For iterating from the front, the [`split_terminator`] method can be
3265     /// used.
3266     ///
3267     /// [`split_terminator`]: #method.split_terminator
3268     ///
3269     /// # Examples
3270     ///
3271     /// ```
3272     /// let v: Vec<&str> = "A.B.".rsplit_terminator('.').collect();
3273     /// assert_eq!(v, ["B", "A"]);
3274     ///
3275     /// let v: Vec<&str> = "A..B..".rsplit_terminator(".").collect();
3276     /// assert_eq!(v, ["", "B", "", "A"]);
3277     /// ```
3278     #[stable(feature = "rust1", since = "1.0.0")]
3279     #[inline]
3280     pub fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
3281         where P::Searcher: ReverseSearcher<'a>
3282     {
3283         RSplitTerminator(self.split_terminator(pat).0)
3284     }
3285
3286     /// An iterator over substrings of the given string slice, separated by a
3287     /// pattern, restricted to returning at most `n` items.
3288     ///
3289     /// If `n` substrings are returned, the last substring (the `n`th substring)
3290     /// will contain the remainder of the string.
3291     ///
3292     /// The pattern can be a `&str`, [`char`], or a closure that determines the
3293     /// split.
3294     ///
3295     /// # Iterator behavior
3296     ///
3297     /// The returned iterator will not be double ended, because it is
3298     /// not efficient to support.
3299     ///
3300     /// If the pattern allows a reverse search, the [`rsplitn`] method can be
3301     /// used.
3302     ///
3303     /// [`rsplitn`]: #method.rsplitn
3304     ///
3305     /// # Examples
3306     ///
3307     /// Simple patterns:
3308     ///
3309     /// ```
3310     /// let v: Vec<&str> = "Mary had a little lambda".splitn(3, ' ').collect();
3311     /// assert_eq!(v, ["Mary", "had", "a little lambda"]);
3312     ///
3313     /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(3, "X").collect();
3314     /// assert_eq!(v, ["lion", "", "tigerXleopard"]);
3315     ///
3316     /// let v: Vec<&str> = "abcXdef".splitn(1, 'X').collect();
3317     /// assert_eq!(v, ["abcXdef"]);
3318     ///
3319     /// let v: Vec<&str> = "".splitn(1, 'X').collect();
3320     /// assert_eq!(v, [""]);
3321     /// ```
3322     ///
3323     /// A more complex pattern, using a closure:
3324     ///
3325     /// ```
3326     /// let v: Vec<&str> = "abc1defXghi".splitn(2, |c| c == '1' || c == 'X').collect();
3327     /// assert_eq!(v, ["abc", "defXghi"]);
3328     /// ```
3329     #[stable(feature = "rust1", since = "1.0.0")]
3330     #[inline]
3331     pub fn splitn<'a, P: Pattern<'a>>(&'a self, n: usize, pat: P) -> SplitN<'a, P> {
3332         SplitN(SplitNInternal {
3333             iter: self.split(pat).0,
3334             count: n,
3335         })
3336     }
3337
3338     /// An iterator over substrings of this string slice, separated by a
3339     /// pattern, starting from the end of the string, restricted to returning
3340     /// at most `n` items.
3341     ///
3342     /// If `n` substrings are returned, the last substring (the `n`th substring)
3343     /// will contain the remainder of the string.
3344     ///
3345     /// The pattern can be a `&str`, [`char`], or a closure that
3346     /// determines the split.
3347     ///
3348     /// # Iterator behavior
3349     ///
3350     /// The returned iterator will not be double ended, because it is not
3351     /// efficient to support.
3352     ///
3353     /// For splitting from the front, the [`splitn`] method can be used.
3354     ///
3355     /// [`splitn`]: #method.splitn
3356     ///
3357     /// # Examples
3358     ///
3359     /// Simple patterns:
3360     ///
3361     /// ```
3362     /// let v: Vec<&str> = "Mary had a little lamb".rsplitn(3, ' ').collect();
3363     /// assert_eq!(v, ["lamb", "little", "Mary had a"]);
3364     ///
3365     /// let v: Vec<&str> = "lionXXtigerXleopard".rsplitn(3, 'X').collect();
3366     /// assert_eq!(v, ["leopard", "tiger", "lionX"]);
3367     ///
3368     /// let v: Vec<&str> = "lion::tiger::leopard".rsplitn(2, "::").collect();
3369     /// assert_eq!(v, ["leopard", "lion::tiger"]);
3370     /// ```
3371     ///
3372     /// A more complex pattern, using a closure:
3373     ///
3374     /// ```
3375     /// let v: Vec<&str> = "abc1defXghi".rsplitn(2, |c| c == '1' || c == 'X').collect();
3376     /// assert_eq!(v, ["ghi", "abc1def"]);
3377     /// ```
3378     #[stable(feature = "rust1", since = "1.0.0")]
3379     #[inline]
3380     pub fn rsplitn<'a, P: Pattern<'a>>(&'a self, n: usize, pat: P) -> RSplitN<'a, P>
3381         where P::Searcher: ReverseSearcher<'a>
3382     {
3383         RSplitN(self.splitn(n, pat).0)
3384     }
3385
3386     /// An iterator over the disjoint matches of a pattern within the given string
3387     /// slice.
3388     ///
3389     /// The pattern can be a `&str`, [`char`], or a closure that
3390     /// determines if a character matches.
3391     ///
3392     /// # Iterator behavior
3393     ///
3394     /// The returned iterator will be a [`DoubleEndedIterator`] if the pattern
3395     /// allows a reverse search and forward/reverse search yields the same
3396     /// elements. This is true for, eg, [`char`] but not for `&str`.
3397     ///
3398     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3399     ///
3400     /// If the pattern allows a reverse search but its results might differ
3401     /// from a forward search, the [`rmatches`] method can be used.
3402     ///
3403     /// [`rmatches`]: #method.rmatches
3404     ///
3405     /// # Examples
3406     ///
3407     /// Basic usage:
3408     ///
3409     /// ```
3410     /// let v: Vec<&str> = "abcXXXabcYYYabc".matches("abc").collect();
3411     /// assert_eq!(v, ["abc", "abc", "abc"]);
3412     ///
3413     /// let v: Vec<&str> = "1abc2abc3".matches(char::is_numeric).collect();
3414     /// assert_eq!(v, ["1", "2", "3"]);
3415     /// ```
3416     #[stable(feature = "str_matches", since = "1.2.0")]
3417     #[inline]
3418     pub fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
3419         Matches(MatchesInternal(pat.into_searcher(self)))
3420     }
3421
3422     /// An iterator over the disjoint matches of a pattern within this string slice,
3423     /// yielded in reverse order.
3424     ///
3425     /// The pattern can be a `&str`, [`char`], or a closure that determines if
3426     /// a character matches.
3427     ///
3428     /// # Iterator behavior
3429     ///
3430     /// The returned iterator requires that the pattern supports a reverse
3431     /// search, and it will be a [`DoubleEndedIterator`] if a forward/reverse
3432     /// search yields the same elements.
3433     ///
3434     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3435     ///
3436     /// For iterating from the front, the [`matches`] method can be used.
3437     ///
3438     /// [`matches`]: #method.matches
3439     ///
3440     /// # Examples
3441     ///
3442     /// Basic usage:
3443     ///
3444     /// ```
3445     /// let v: Vec<&str> = "abcXXXabcYYYabc".rmatches("abc").collect();
3446     /// assert_eq!(v, ["abc", "abc", "abc"]);
3447     ///
3448     /// let v: Vec<&str> = "1abc2abc3".rmatches(char::is_numeric).collect();
3449     /// assert_eq!(v, ["3", "2", "1"]);
3450     /// ```
3451     #[stable(feature = "str_matches", since = "1.2.0")]
3452     #[inline]
3453     pub fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
3454         where P::Searcher: ReverseSearcher<'a>
3455     {
3456         RMatches(self.matches(pat).0)
3457     }
3458
3459     /// An iterator over the disjoint matches of a pattern within this string
3460     /// slice as well as the index that the match starts at.
3461     ///
3462     /// For matches of `pat` within `self` that overlap, only the indices
3463     /// corresponding to the first match are returned.
3464     ///
3465     /// The pattern can be a `&str`, [`char`], or a closure that determines
3466     /// if a character matches.
3467     ///
3468     /// # Iterator behavior
3469     ///
3470     /// The returned iterator will be a [`DoubleEndedIterator`] if the pattern
3471     /// allows a reverse search and forward/reverse search yields the same
3472     /// elements. This is true for, eg, [`char`] but not for `&str`.
3473     ///
3474     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3475     ///
3476     /// If the pattern allows a reverse search but its results might differ
3477     /// from a forward search, the [`rmatch_indices`] method can be used.
3478     ///
3479     /// [`rmatch_indices`]: #method.rmatch_indices
3480     ///
3481     /// # Examples
3482     ///
3483     /// Basic usage:
3484     ///
3485     /// ```
3486     /// let v: Vec<_> = "abcXXXabcYYYabc".match_indices("abc").collect();
3487     /// assert_eq!(v, [(0, "abc"), (6, "abc"), (12, "abc")]);
3488     ///
3489     /// let v: Vec<_> = "1abcabc2".match_indices("abc").collect();
3490     /// assert_eq!(v, [(1, "abc"), (4, "abc")]);
3491     ///
3492     /// let v: Vec<_> = "ababa".match_indices("aba").collect();
3493     /// assert_eq!(v, [(0, "aba")]); // only the first `aba`
3494     /// ```
3495     #[stable(feature = "str_match_indices", since = "1.5.0")]
3496     #[inline]
3497     pub fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
3498         MatchIndices(MatchIndicesInternal(pat.into_searcher(self)))
3499     }
3500
3501     /// An iterator over the disjoint matches of a pattern within `self`,
3502     /// yielded in reverse order along with the index of the match.
3503     ///
3504     /// For matches of `pat` within `self` that overlap, only the indices
3505     /// corresponding to the last match are returned.
3506     ///
3507     /// The pattern can be a `&str`, [`char`], or a closure that determines if a
3508     /// character matches.
3509     ///
3510     /// # Iterator behavior
3511     ///
3512     /// The returned iterator requires that the pattern supports a reverse
3513     /// search, and it will be a [`DoubleEndedIterator`] if a forward/reverse
3514     /// search yields the same elements.
3515     ///
3516     /// [`DoubleEndedIterator`]: iter/trait.DoubleEndedIterator.html
3517     ///
3518     /// For iterating from the front, the [`match_indices`] method can be used.
3519     ///
3520     /// [`match_indices`]: #method.match_indices
3521     ///
3522     /// # Examples
3523     ///
3524     /// Basic usage:
3525     ///
3526     /// ```
3527     /// let v: Vec<_> = "abcXXXabcYYYabc".rmatch_indices("abc").collect();
3528     /// assert_eq!(v, [(12, "abc"), (6, "abc"), (0, "abc")]);
3529     ///
3530     /// let v: Vec<_> = "1abcabc2".rmatch_indices("abc").collect();
3531     /// assert_eq!(v, [(4, "abc"), (1, "abc")]);
3532     ///
3533     /// let v: Vec<_> = "ababa".rmatch_indices("aba").collect();
3534     /// assert_eq!(v, [(2, "aba")]); // only the last `aba`
3535     /// ```
3536     #[stable(feature = "str_match_indices", since = "1.5.0")]
3537     #[inline]
3538     pub fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
3539         where P::Searcher: ReverseSearcher<'a>
3540     {
3541         RMatchIndices(self.match_indices(pat).0)
3542     }
3543
3544     /// Returns a string slice with leading and trailing whitespace removed.
3545     ///
3546     /// 'Whitespace' is defined according to the terms of the Unicode Derived
3547     /// Core Property `White_Space`.
3548     ///
3549     /// # Examples
3550     ///
3551     /// Basic usage:
3552     ///
3553     /// ```
3554     /// let s = " Hello\tworld\t";
3555     ///
3556     /// assert_eq!("Hello\tworld", s.trim());
3557     /// ```
3558     #[stable(feature = "rust1", since = "1.0.0")]
3559     pub fn trim(&self) -> &str {
3560         self.trim_matches(|c: char| c.is_whitespace())
3561     }
3562
3563     /// Returns a string slice with leading whitespace removed.
3564     ///
3565     /// 'Whitespace' is defined according to the terms of the Unicode Derived
3566     /// Core Property `White_Space`.
3567     ///
3568     /// # Text directionality
3569     ///
3570     /// A string is a sequence of bytes. `start` in this context means the first
3571     /// position of that byte string; for a left-to-right language like English or
3572     /// Russian, this will be left side; and for right-to-left languages like
3573     /// like Arabic or Hebrew, this will be the right side.
3574     ///
3575     /// # Examples
3576     ///
3577     /// Basic usage:
3578     ///
3579     /// ```
3580     /// let s = " Hello\tworld\t";
3581     /// assert_eq!("Hello\tworld\t", s.trim_start());
3582     /// ```
3583     ///
3584     /// Directionality:
3585     ///
3586     /// ```
3587     /// let s = "  English  ";
3588     /// assert!(Some('E') == s.trim_start().chars().next());
3589     ///
3590     /// let s = "  עברית  ";
3591     /// assert!(Some('ע') == s.trim_start().chars().next());
3592     /// ```
3593     #[stable(feature = "trim_direction", since = "1.30.0")]
3594     pub fn trim_start(&self) -> &str {
3595         self.trim_start_matches(|c: char| c.is_whitespace())
3596     }
3597
3598     /// Returns a string slice with trailing whitespace removed.
3599     ///
3600     /// 'Whitespace' is defined according to the terms of the Unicode Derived
3601     /// Core Property `White_Space`.
3602     ///
3603     /// # Text directionality
3604     ///
3605     /// A string is a sequence of bytes. `end` in this context means the last
3606     /// position of that byte string; for a left-to-right language like English or
3607     /// Russian, this will be right side; and for right-to-left languages like
3608     /// like Arabic or Hebrew, this will be the left side.
3609     ///
3610     /// # Examples
3611     ///
3612     /// Basic usage:
3613     ///
3614     /// ```
3615     /// let s = " Hello\tworld\t";
3616     /// assert_eq!(" Hello\tworld", s.trim_end());
3617     /// ```
3618     ///
3619     /// Directionality:
3620     ///
3621     /// ```
3622     /// let s = "  English  ";
3623     /// assert!(Some('h') == s.trim_end().chars().rev().next());
3624     ///
3625     /// let s = "  עברית  ";
3626     /// assert!(Some('ת') == s.trim_end().chars().rev().next());
3627     /// ```
3628     #[stable(feature = "trim_direction", since = "1.30.0")]
3629     pub fn trim_end(&self) -> &str {
3630         self.trim_end_matches(|c: char| c.is_whitespace())
3631     }
3632
3633     /// Returns a string slice with leading whitespace removed.
3634     ///
3635     /// 'Whitespace' is defined according to the terms of the Unicode Derived
3636     /// Core Property `White_Space`.
3637     ///
3638     /// # Text directionality
3639     ///
3640     /// A string is a sequence of bytes. 'Left' in this context means the first
3641     /// position of that byte string; for a language like Arabic or Hebrew
3642     /// which are 'right to left' rather than 'left to right', this will be
3643     /// the _right_ side, not the left.
3644     ///
3645     /// # Examples
3646     ///
3647     /// Basic usage:
3648     ///
3649     /// ```
3650     /// let s = " Hello\tworld\t";
3651     ///
3652     /// assert_eq!("Hello\tworld\t", s.trim_left());
3653     /// ```
3654     ///
3655     /// Directionality:
3656     ///
3657     /// ```
3658     /// let s = "  English";
3659     /// assert!(Some('E') == s.trim_left().chars().next());
3660     ///
3661     /// let s = "  עברית";
3662     /// assert!(Some('ע') == s.trim_left().chars().next());
3663     /// ```
3664     #[stable(feature = "rust1", since = "1.0.0")]
3665     #[rustc_deprecated(reason = "superseded by `trim_start`", since = "1.33.0")]
3666     pub fn trim_left(&self) -> &str {
3667         self.trim_start()
3668     }
3669
3670     /// Returns a string slice with trailing whitespace removed.
3671     ///
3672     /// 'Whitespace' is defined according to the terms of the Unicode Derived
3673     /// Core Property `White_Space`.
3674     ///
3675     /// # Text directionality
3676     ///
3677     /// A string is a sequence of bytes. 'Right' in this context means the last
3678     /// position of that byte string; for a language like Arabic or Hebrew
3679     /// which are 'right to left' rather than 'left to right', this will be
3680     /// the _left_ side, not the right.
3681     ///
3682     /// # Examples
3683     ///
3684     /// Basic usage:
3685     ///
3686     /// ```
3687     /// let s = " Hello\tworld\t";
3688     ///
3689     /// assert_eq!(" Hello\tworld", s.trim_right());
3690     /// ```
3691     ///
3692     /// Directionality:
3693     ///
3694     /// ```
3695     /// let s = "English  ";
3696     /// assert!(Some('h') == s.trim_right().chars().rev().next());
3697     ///
3698     /// let s = "עברית  ";
3699     /// assert!(Some('ת') == s.trim_right().chars().rev().next());
3700     /// ```
3701     #[stable(feature = "rust1", since = "1.0.0")]
3702     #[rustc_deprecated(reason = "superseded by `trim_end`", since = "1.33.0")]
3703     pub fn trim_right(&self) -> &str {
3704         self.trim_end()
3705     }
3706
3707     /// Returns a string slice with all prefixes and suffixes that match a
3708     /// pattern repeatedly removed.
3709     ///
3710     /// The pattern can be a [`char`] or a closure that determines if a
3711     /// character matches.
3712     ///
3713     /// # Examples
3714     ///
3715     /// Simple patterns:
3716     ///
3717     /// ```
3718     /// assert_eq!("11foo1bar11".trim_matches('1'), "foo1bar");
3719     /// assert_eq!("123foo1bar123".trim_matches(char::is_numeric), "foo1bar");
3720     ///
3721     /// let x: &[_] = &['1', '2'];
3722     /// assert_eq!("12foo1bar12".trim_matches(x), "foo1bar");
3723     /// ```
3724     ///
3725     /// A more complex pattern, using a closure:
3726     ///
3727     /// ```
3728     /// assert_eq!("1foo1barXX".trim_matches(|c| c == '1' || c == 'X'), "foo1bar");
3729     /// ```
3730     #[stable(feature = "rust1", since = "1.0.0")]
3731     pub fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
3732         where P::Searcher: DoubleEndedSearcher<'a>
3733     {
3734         let mut i = 0;
3735         let mut j = 0;
3736         let mut matcher = pat.into_searcher(self);
3737         if let Some((a, b)) = matcher.next_reject() {
3738             i = a;
3739             j = b; // Remember earliest known match, correct it below if
3740                    // last match is different
3741         }
3742         if let Some((_, b)) = matcher.next_reject_back() {
3743             j = b;
3744         }
3745         unsafe {
3746             // Searcher is known to return valid indices
3747             self.get_unchecked(i..j)
3748         }
3749     }
3750
3751     /// Returns a string slice with all prefixes that match a pattern
3752     /// repeatedly removed.
3753     ///
3754     /// The pattern can be a `&str`, [`char`], or a closure that determines if
3755     /// a character matches.
3756     ///
3757     /// # Text directionality
3758     ///
3759     /// A string is a sequence of bytes. 'Left' in this context means the first
3760     /// position of that byte string; for a language like Arabic or Hebrew
3761     /// which are 'right to left' rather than 'left to right', this will be
3762     /// the _right_ side, not the left.
3763     ///
3764     /// # Examples
3765     ///
3766     /// Basic usage:
3767     ///
3768     /// ```
3769     /// assert_eq!("11foo1bar11".trim_start_matches('1'), "foo1bar11");
3770     /// assert_eq!("123foo1bar123".trim_start_matches(char::is_numeric), "foo1bar123");
3771     ///
3772     /// let x: &[_] = &['1', '2'];
3773     /// assert_eq!("12foo1bar12".trim_start_matches(x), "foo1bar12");
3774     /// ```
3775     #[stable(feature = "trim_direction", since = "1.30.0")]
3776     pub fn trim_start_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str {
3777         let mut i = self.len();
3778         let mut matcher = pat.into_searcher(self);
3779         if let Some((a, _)) = matcher.next_reject() {
3780             i = a;
3781         }
3782         unsafe {
3783             // Searcher is known to return valid indices
3784             self.get_unchecked(i..self.len())
3785         }
3786     }
3787
3788     /// Returns a string slice with all suffixes that match a pattern
3789     /// repeatedly removed.
3790     ///
3791     /// The pattern can be a `&str`, [`char`], or a closure that
3792     /// determines if a character matches.
3793     ///
3794     /// # Text directionality
3795     ///
3796     /// A string is a sequence of bytes. 'Right' in this context means the last
3797     /// position of that byte string; for a language like Arabic or Hebrew
3798     /// which are 'right to left' rather than 'left to right', this will be
3799     /// the _left_ side, not the right.
3800     ///
3801     /// # Examples
3802     ///
3803     /// Simple patterns:
3804     ///
3805     /// ```
3806     /// assert_eq!("11foo1bar11".trim_end_matches('1'), "11foo1bar");
3807     /// assert_eq!("123foo1bar123".trim_end_matches(char::is_numeric), "123foo1bar");
3808     ///
3809     /// let x: &[_] = &['1', '2'];
3810     /// assert_eq!("12foo1bar12".trim_end_matches(x), "12foo1bar");
3811     /// ```
3812     ///
3813     /// A more complex pattern, using a closure:
3814     ///
3815     /// ```
3816     /// assert_eq!("1fooX".trim_end_matches(|c| c == '1' || c == 'X'), "1foo");
3817     /// ```
3818     #[stable(feature = "trim_direction", since = "1.30.0")]
3819     pub fn trim_end_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
3820         where P::Searcher: ReverseSearcher<'a>
3821     {
3822         let mut j = 0;
3823         let mut matcher = pat.into_searcher(self);
3824         if let Some((_, b)) = matcher.next_reject_back() {
3825             j = b;
3826         }
3827         unsafe {
3828             // Searcher is known to return valid indices
3829             self.get_unchecked(0..j)
3830         }
3831     }
3832
3833     /// Returns a string slice with all prefixes that match a pattern
3834     /// repeatedly removed.
3835     ///
3836     /// The pattern can be a `&str`, [`char`], or a closure that determines if
3837     /// a character matches.
3838     ///
3839     /// [`char`]: primitive.char.html
3840     ///
3841     /// # Text directionality
3842     ///
3843     /// A string is a sequence of bytes. 'Left' in this context means the first
3844     /// position of that byte string; for a language like Arabic or Hebrew
3845     /// which are 'right to left' rather than 'left to right', this will be
3846     /// the _right_ side, not the left.
3847     ///
3848     /// # Examples
3849     ///
3850     /// Basic usage:
3851     ///
3852     /// ```
3853     /// assert_eq!("11foo1bar11".trim_left_matches('1'), "foo1bar11");
3854     /// assert_eq!("123foo1bar123".trim_left_matches(char::is_numeric), "foo1bar123");
3855     ///
3856     /// let x: &[_] = &['1', '2'];
3857     /// assert_eq!("12foo1bar12".trim_left_matches(x), "foo1bar12");
3858     /// ```
3859     #[stable(feature = "rust1", since = "1.0.0")]
3860     #[rustc_deprecated(reason = "superseded by `trim_start_matches`", since = "1.33.0")]
3861     pub fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str {
3862         self.trim_start_matches(pat)
3863     }
3864
3865     /// Returns a string slice with all suffixes that match a pattern
3866     /// repeatedly removed.
3867     ///
3868     /// The pattern can be a `&str`, [`char`], or a closure that
3869     /// determines if a character matches.
3870     ///
3871     /// [`char`]: primitive.char.html
3872     ///
3873     /// # Text directionality
3874     ///
3875     /// A string is a sequence of bytes. 'Right' in this context means the last
3876     /// position of that byte string; for a language like Arabic or Hebrew
3877     /// which are 'right to left' rather than 'left to right', this will be
3878     /// the _left_ side, not the right.
3879     ///
3880     /// # Examples
3881     ///
3882     /// Simple patterns:
3883     ///
3884     /// ```
3885     /// assert_eq!("11foo1bar11".trim_right_matches('1'), "11foo1bar");
3886     /// assert_eq!("123foo1bar123".trim_right_matches(char::is_numeric), "123foo1bar");
3887     ///
3888     /// let x: &[_] = &['1', '2'];
3889     /// assert_eq!("12foo1bar12".trim_right_matches(x), "12foo1bar");
3890     /// ```
3891     ///
3892     /// A more complex pattern, using a closure:
3893     ///
3894     /// ```
3895     /// assert_eq!("1fooX".trim_right_matches(|c| c == '1' || c == 'X'), "1foo");
3896     /// ```
3897     #[stable(feature = "rust1", since = "1.0.0")]
3898     #[rustc_deprecated(reason = "superseded by `trim_end_matches`", since = "1.33.0")]
3899     pub fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
3900         where P::Searcher: ReverseSearcher<'a>
3901     {
3902         self.trim_end_matches(pat)
3903     }
3904
3905     /// Parses this string slice into another type.
3906     ///
3907     /// Because `parse` is so general, it can cause problems with type
3908     /// inference. As such, `parse` is one of the few times you'll see
3909     /// the syntax affectionately known as the 'turbofish': `::<>`. This
3910     /// helps the inference algorithm understand specifically which type
3911     /// you're trying to parse into.
3912     ///
3913     /// `parse` can parse any type that implements the [`FromStr`] trait.
3914     ///
3915     /// [`FromStr`]: str/trait.FromStr.html
3916     ///
3917     /// # Errors
3918     ///
3919     /// Will return [`Err`] if it's not possible to parse this string slice into
3920     /// the desired type.
3921     ///
3922     /// [`Err`]: str/trait.FromStr.html#associatedtype.Err
3923     ///
3924     /// # Examples
3925     ///
3926     /// Basic usage
3927     ///
3928     /// ```
3929     /// let four: u32 = "4".parse().unwrap();
3930     ///
3931     /// assert_eq!(4, four);
3932     /// ```
3933     ///
3934     /// Using the 'turbofish' instead of annotating `four`:
3935     ///
3936     /// ```
3937     /// let four = "4".parse::<u32>();
3938     ///
3939     /// assert_eq!(Ok(4), four);
3940     /// ```
3941     ///
3942     /// Failing to parse:
3943     ///
3944     /// ```
3945     /// let nope = "j".parse::<u32>();
3946     ///
3947     /// assert!(nope.is_err());
3948     /// ```
3949     #[inline]
3950     #[stable(feature = "rust1", since = "1.0.0")]
3951     pub fn parse<F: FromStr>(&self) -> Result<F, F::Err> {
3952         FromStr::from_str(self)
3953     }
3954
3955     /// Checks if all characters in this string are within the ASCII range.
3956     ///
3957     /// # Examples
3958     ///
3959     /// ```
3960     /// let ascii = "hello!\n";
3961     /// let non_ascii = "Grüße, Jürgen ❤";
3962     ///
3963     /// assert!(ascii.is_ascii());
3964     /// assert!(!non_ascii.is_ascii());
3965     /// ```
3966     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
3967     #[inline]
3968     pub fn is_ascii(&self) -> bool {
3969         // We can treat each byte as character here: all multibyte characters
3970         // start with a byte that is not in the ascii range, so we will stop
3971         // there already.
3972         self.bytes().all(|b| b.is_ascii())
3973     }
3974
3975     /// Checks that two strings are an ASCII case-insensitive match.
3976     ///
3977     /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
3978     /// but without allocating and copying temporaries.
3979     ///
3980     /// # Examples
3981     ///
3982     /// ```
3983     /// assert!("Ferris".eq_ignore_ascii_case("FERRIS"));
3984     /// assert!("Ferrös".eq_ignore_ascii_case("FERRöS"));
3985     /// assert!(!"Ferrös".eq_ignore_ascii_case("FERRÖS"));
3986     /// ```
3987     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
3988     #[inline]
3989     pub fn eq_ignore_ascii_case(&self, other: &str) -> bool {
3990         self.as_bytes().eq_ignore_ascii_case(other.as_bytes())
3991     }
3992
3993     /// Converts this string to its ASCII upper case equivalent in-place.
3994     ///
3995     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
3996     /// but non-ASCII letters are unchanged.
3997     ///
3998     /// To return a new uppercased value without modifying the existing one, use
3999     /// [`to_ascii_uppercase`].
4000     ///
4001     /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
4002     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
4003     pub fn make_ascii_uppercase(&mut self) {
4004         let me = unsafe { self.as_bytes_mut() };
4005         me.make_ascii_uppercase()
4006     }
4007
4008     /// Converts this string to its ASCII lower case equivalent in-place.
4009     ///
4010     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
4011     /// but non-ASCII letters are unchanged.
4012     ///
4013     /// To return a new lowercased value without modifying the existing one, use
4014     /// [`to_ascii_lowercase`].
4015     ///
4016     /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
4017     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
4018     pub fn make_ascii_lowercase(&mut self) {
4019         let me = unsafe { self.as_bytes_mut() };
4020         me.make_ascii_lowercase()
4021     }
4022 }
4023
4024 #[stable(feature = "rust1", since = "1.0.0")]
4025 impl AsRef<[u8]> for str {
4026     #[inline]
4027     fn as_ref(&self) -> &[u8] {
4028         self.as_bytes()
4029     }
4030 }
4031
4032 #[stable(feature = "rust1", since = "1.0.0")]
4033 impl Default for &str {
4034     /// Creates an empty str
4035     fn default() -> Self { "" }
4036 }
4037
4038 #[stable(feature = "default_mut_str", since = "1.28.0")]
4039 impl Default for &mut str {
4040     /// Creates an empty mutable str
4041     fn default() -> Self { unsafe { from_utf8_unchecked_mut(&mut []) } }
4042 }
4043
4044 /// An iterator over the non-whitespace substrings of a string,
4045 /// separated by any amount of whitespace.
4046 ///
4047 /// This struct is created by the [`split_whitespace`] method on [`str`].
4048 /// See its documentation for more.
4049 ///
4050 /// [`split_whitespace`]: ../../std/primitive.str.html#method.split_whitespace
4051 /// [`str`]: ../../std/primitive.str.html
4052 #[stable(feature = "split_whitespace", since = "1.1.0")]
4053 #[derive(Clone, Debug)]
4054 pub struct SplitWhitespace<'a> {
4055     inner: Filter<Split<'a, IsWhitespace>, IsNotEmpty>,
4056 }
4057
4058 /// An iterator over the non-ASCII-whitespace substrings of a string,
4059 /// separated by any amount of ASCII whitespace.
4060 ///
4061 /// This struct is created by the [`split_ascii_whitespace`] method on [`str`].
4062 /// See its documentation for more.
4063 ///
4064 /// [`split_ascii_whitespace`]: ../../std/primitive.str.html#method.split_ascii_whitespace
4065 /// [`str`]: ../../std/primitive.str.html
4066 #[unstable(feature = "split_ascii_whitespace", issue = "48656")]
4067 #[derive(Clone, Debug)]
4068 pub struct SplitAsciiWhitespace<'a> {
4069     inner: Map<Filter<SliceSplit<'a, u8, IsAsciiWhitespace>, IsNotEmpty>, UnsafeBytesToStr>,
4070 }
4071
4072 #[derive(Clone)]
4073 struct IsWhitespace;
4074
4075 impl FnOnce<(char, )> for IsWhitespace {
4076     type Output = bool;
4077
4078     #[inline]
4079     extern "rust-call" fn call_once(mut self, arg: (char, )) -> bool {
4080         self.call_mut(arg)
4081     }
4082 }
4083
4084 impl FnMut<(char, )> for IsWhitespace {
4085     #[inline]
4086     extern "rust-call" fn call_mut(&mut self, arg: (char, )) -> bool {
4087         arg.0.is_whitespace()
4088     }
4089 }
4090
4091 #[derive(Clone)]
4092 struct IsAsciiWhitespace;
4093
4094 impl<'a> FnOnce<(&'a u8, )> for IsAsciiWhitespace {
4095     type Output = bool;
4096
4097     #[inline]
4098     extern "rust-call" fn call_once(mut self, arg: (&u8, )) -> bool {
4099         self.call_mut(arg)
4100     }
4101 }
4102
4103 impl<'a> FnMut<(&'a u8, )> for IsAsciiWhitespace {
4104     #[inline]
4105     extern "rust-call" fn call_mut(&mut self, arg: (&u8, )) -> bool {
4106         arg.0.is_ascii_whitespace()
4107     }
4108 }
4109
4110 #[derive(Clone)]
4111 struct IsNotEmpty;
4112
4113 impl<'a, 'b> FnOnce<(&'a &'b str, )> for IsNotEmpty {
4114     type Output = bool;
4115
4116     #[inline]
4117     extern "rust-call" fn call_once(mut self, arg: (&'a &'b str, )) -> bool {
4118         self.call_mut(arg)
4119     }
4120 }
4121
4122 impl<'a, 'b> FnMut<(&'a &'b str, )> for IsNotEmpty {
4123     #[inline]
4124     extern "rust-call" fn call_mut(&mut self, arg: (&'a &'b str, )) -> bool {
4125         !arg.0.is_empty()
4126     }
4127 }
4128
4129 impl<'a, 'b> FnOnce<(&'a &'b [u8], )> for IsNotEmpty {
4130     type Output = bool;
4131
4132     #[inline]
4133     extern "rust-call" fn call_once(mut self, arg: (&'a &'b [u8], )) -> bool {
4134         self.call_mut(arg)
4135     }
4136 }
4137
4138 impl<'a, 'b> FnMut<(&'a &'b [u8], )> for IsNotEmpty {
4139     #[inline]
4140     extern "rust-call" fn call_mut(&mut self, arg: (&'a &'b [u8], )) -> bool {
4141         !arg.0.is_empty()
4142     }
4143 }
4144
4145 #[derive(Clone)]
4146 struct UnsafeBytesToStr;
4147
4148 impl<'a> FnOnce<(&'a [u8], )> for UnsafeBytesToStr {
4149     type Output = &'a str;
4150
4151     #[inline]
4152     extern "rust-call" fn call_once(mut self, arg: (&'a [u8], )) -> &'a str {
4153         self.call_mut(arg)
4154     }
4155 }
4156
4157 impl<'a> FnMut<(&'a [u8], )> for UnsafeBytesToStr {
4158     #[inline]
4159     extern "rust-call" fn call_mut(&mut self, arg: (&'a [u8], )) -> &'a str {
4160         unsafe { from_utf8_unchecked(arg.0) }
4161     }
4162 }
4163
4164
4165 #[stable(feature = "split_whitespace", since = "1.1.0")]
4166 impl<'a> Iterator for SplitWhitespace<'a> {
4167     type Item = &'a str;
4168
4169     #[inline]
4170     fn next(&mut self) -> Option<&'a str> {
4171         self.inner.next()
4172     }
4173
4174     #[inline]
4175     fn size_hint(&self) -> (usize, Option<usize>) {
4176         self.inner.size_hint()
4177     }
4178 }
4179
4180 #[stable(feature = "split_whitespace", since = "1.1.0")]
4181 impl<'a> DoubleEndedIterator for SplitWhitespace<'a> {
4182     #[inline]
4183     fn next_back(&mut self) -> Option<&'a str> {
4184         self.inner.next_back()
4185     }
4186 }
4187
4188 #[stable(feature = "fused", since = "1.26.0")]
4189 impl FusedIterator for SplitWhitespace<'_> {}
4190
4191 #[unstable(feature = "split_ascii_whitespace", issue = "48656")]
4192 impl<'a> Iterator for SplitAsciiWhitespace<'a> {
4193     type Item = &'a str;
4194
4195     #[inline]
4196     fn next(&mut self) -> Option<&'a str> {
4197         self.inner.next()
4198     }
4199
4200     #[inline]
4201     fn size_hint(&self) -> (usize, Option<usize>) {
4202         self.inner.size_hint()
4203     }
4204 }
4205
4206 #[unstable(feature = "split_ascii_whitespace", issue = "48656")]
4207 impl<'a> DoubleEndedIterator for SplitAsciiWhitespace<'a> {
4208     #[inline]
4209     fn next_back(&mut self) -> Option<&'a str> {
4210         self.inner.next_back()
4211     }
4212 }
4213
4214 #[unstable(feature = "split_ascii_whitespace", issue = "48656")]
4215 impl FusedIterator for SplitAsciiWhitespace<'_> {}
4216
4217 /// An iterator of [`u16`] over the string encoded as UTF-16.
4218 ///
4219 /// [`u16`]: ../../std/primitive.u16.html
4220 ///
4221 /// This struct is created by the [`encode_utf16`] method on [`str`].
4222 /// See its documentation for more.
4223 ///
4224 /// [`encode_utf16`]: ../../std/primitive.str.html#method.encode_utf16
4225 /// [`str`]: ../../std/primitive.str.html
4226 #[derive(Clone)]
4227 #[stable(feature = "encode_utf16", since = "1.8.0")]
4228 pub struct EncodeUtf16<'a> {
4229     chars: Chars<'a>,
4230     extra: u16,
4231 }
4232
4233 #[stable(feature = "collection_debug", since = "1.17.0")]
4234 impl fmt::Debug for EncodeUtf16<'_> {
4235     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
4236         f.pad("EncodeUtf16 { .. }")
4237     }
4238 }
4239
4240 #[stable(feature = "encode_utf16", since = "1.8.0")]
4241 impl<'a> Iterator for EncodeUtf16<'a> {
4242     type Item = u16;
4243
4244     #[inline]
4245     fn next(&mut self) -> Option<u16> {
4246         if self.extra != 0 {
4247             let tmp = self.extra;
4248             self.extra = 0;
4249             return Some(tmp);
4250         }
4251
4252         let mut buf = [0; 2];
4253         self.chars.next().map(|ch| {
4254             let n = ch.encode_utf16(&mut buf).len();
4255             if n == 2 {
4256                 self.extra = buf[1];
4257             }
4258             buf[0]
4259         })
4260     }
4261
4262     #[inline]
4263     fn size_hint(&self) -> (usize, Option<usize>) {
4264         let (low, high) = self.chars.size_hint();
4265         // every char gets either one u16 or two u16,
4266         // so this iterator is between 1 or 2 times as
4267         // long as the underlying iterator.
4268         (low, high.and_then(|n| n.checked_mul(2)))
4269     }
4270 }
4271
4272 #[stable(feature = "fused", since = "1.26.0")]
4273 impl FusedIterator for EncodeUtf16<'_> {}