src/libcore/str/mod.rs

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