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