src/libcore/str/mod.rs

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