src/libcore/str/mod.rs

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