src/libcore/str/mod.rs

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