src/libcore/str/mod.rs

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