src/libcore/str/mod.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! String manipulation
  12 //!
  13 //! For more details, see std::str
  14
  15 #![stable(feature = "rust1", since = "1.0.0")]
  16
  17 use self::pattern::Pattern;
  18 use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher};
  19
  20 use char;
  21 use fmt;
  22 use iter::{Map, Cloned, FusedIterator, TrustedLen, Filter};
  23 use iter_private::TrustedRandomAccess;
  24 use slice::{self, SliceIndex, Split as SliceSplit};
  25 use mem;
  26
  27 pub mod pattern;
  28
  29 #[unstable(feature = "str_internals", issue = "0")]
  30 #[allow(missing_docs)]
  31 pub mod lossy;
  32
  33 /// A trait to abstract the idea of creating a new instance of a type from a
  34 /// string.
  35 ///
  36 /// `FromStr`'s [`from_str`] method is often used implicitly, through
  37 /// [`str`]'s [`parse`] method. See [`parse`]'s documentation for examples.
  38 ///
  39 /// [`from_str`]: #tymethod.from_str
  40 /// [`str`]: ../../std/primitive.str.html
  41 /// [`parse`]: ../../std/primitive.str.html#method.parse
  42 ///
  43 /// # Examples
  44 ///
  45 /// Basic implementation of `FromStr` on an example `Point` type:
  46 ///
  47 /// ```
  48 /// use std::str::FromStr;
  49 /// use std::num::ParseIntError;
  50 ///
  51 /// #[derive(Debug, PartialEq)]
  52 /// struct Point {
  53 ///     x: i32,
  54 ///     y: i32
  55 /// }
  56 ///
  57 /// impl FromStr for Point {
  58 ///     type Err = ParseIntError;
  59 ///
  60 ///     fn from_str(s: &str) -> Result<Self, Self::Err> {
  61 ///         let coords: Vec<&str> = s.trim_matches(|p| p == '(' || p == ')' )
  62 ///                                  .split(',')
  63 ///                                  .collect();
  64 ///
  65 ///         let x_fromstr = coords[0].parse::<i32>()?;
  66 ///         let y_fromstr = coords[1].parse::<i32>()?;
  67 ///
  68 ///         Ok(Point { x: x_fromstr, y: y_fromstr })
  69 ///     }
  70 /// }
  71 ///
  72 /// let p = Point::from_str("(1,2)");
  73 /// assert_eq!(p.unwrap(), Point{ x: 1, y: 2} )
  74 /// ```
  75 #[stable(feature = "rust1", since = "1.0.0")]
  76 pub trait FromStr: Sized {
  77     /// The associated error which can be returned from parsing.
  78     #[stable(feature = "rust1", since = "1.0.0")]
  79     type Err;
  80
  81     /// Parses a string `s` to return a value of this type.
  82     ///
  83     /// If parsing succeeds, return the value inside [`Ok`], otherwise
  84     /// when the string is ill-formatted return an error specific to the
  85     /// inside [`Err`]. The error type is specific to implementation of the trait.
  86     ///
  87     /// [`Ok`]: ../../std/result/enum.Result.html#variant.Ok
  88     /// [`Err`]: ../../std/result/enum.Result.html#variant.Err
  89     ///
  90     /// # Examples
  91     ///
  92     /// Basic usage with [`i32`][ithirtytwo], a type that implements `FromStr`:
  93     ///
  94     /// [ithirtytwo]: ../../std/primitive.i32.html
  95     ///
  96     /// ```
  97     /// use std::str::FromStr;
  98     ///
  99     /// let s = "5";
 100     /// let x = i32::from_str(s).unwrap();
 101     ///
 102     /// assert_eq!(5, x);
 103     /// ```
 104     #[stable(feature = "rust1", since = "1.0.0")]
 105     fn from_str(s: &str) -> Result<Self, Self::Err>;
 106 }
 107
 108 #[stable(feature = "rust1", since = "1.0.0")]
 109 impl FromStr for bool {
 110     type Err = ParseBoolError;
 111
 112     /// Parse a `bool` from a string.
 113     ///
 114     /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
 115     /// actually be parseable.
 116     ///
 117     /// # Examples
 118     ///
 119     /// ```
 120     /// use std::str::FromStr;
 121     ///
 122     /// assert_eq!(FromStr::from_str("true"), Ok(true));
 123     /// assert_eq!(FromStr::from_str("false"), Ok(false));
 124     /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
 125     /// ```
 126     ///
 127     /// Note, in many cases, the `.parse()` method on `str` is more proper.
 128     ///
 129     /// ```
 130     /// assert_eq!("true".parse(), Ok(true));
 131     /// assert_eq!("false".parse(), Ok(false));
 132     /// assert!("not even a boolean".parse::<bool>().is_err());
 133     /// ```
 134     #[inline]
 135     fn from_str(s: &str) -> Result<bool, ParseBoolError> {
 136         match s {
 137             "true"  => Ok(true),
 138             "false" => Ok(false),
 139             _       => Err(ParseBoolError { _priv: () }),
 140         }
 141     }
 142 }
 143
 144 /// An error returned when parsing a `bool` using [`from_str`] fails
 145 ///
 146 /// [`from_str`]: ../../std/primitive.bool.html#method.from_str
 147 #[derive(Debug, Clone, PartialEq, Eq)]
 148 #[stable(feature = "rust1", since = "1.0.0")]
 149 pub struct ParseBoolError { _priv: () }
 150
 151 #[stable(feature = "rust1", since = "1.0.0")]
 152 impl fmt::Display for ParseBoolError {
 153     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 154         "provided string was not `true` or `false`".fmt(f)
 155     }
 156 }
 157
 158 /*
 159 Section: Creating a string
 160 */
 161
 162 /// Errors which can occur when attempting to interpret a sequence of [`u8`]
 163 /// as a string.
 164 ///
 165 /// [`u8`]: ../../std/primitive.u8.html
 166 ///
 167 /// As such, the `from_utf8` family of functions and methods for both [`String`]s
 168 /// and [`&str`]s make use of this error, for example.
 169 ///
 170 /// [`String`]: ../../std/string/struct.String.html#method.from_utf8
 171 /// [`&str`]: ../../std/str/fn.from_utf8.html
 172 ///
 173 /// # Examples
 174 ///
 175 /// This error type’s methods can be used to create functionality
 176 /// similar to `String::from_utf8_lossy` without allocating heap memory:
 177 ///
 178 /// ```
 179 /// fn from_utf8_lossy<F>(mut input: &[u8], mut push: F) where F: FnMut(&str) {
 180 ///     loop {
 181 ///         match ::std::str::from_utf8(input) {
 182 ///             Ok(valid) => {
 183 ///                 push(valid);
 184 ///                 break
 185 ///             }
 186 ///             Err(error) => {
 187 ///                 let (valid, after_valid) = input.split_at(error.valid_up_to());
 188 ///                 unsafe {
 189 ///                     push(::std::str::from_utf8_unchecked(valid))
 190 ///                 }
 191 ///                 push("\u{FFFD}");
 192 ///
 193 ///                 if let Some(invalid_sequence_length) = error.error_len() {
 194 ///                     input = &after_valid[invalid_sequence_length..]
 195 ///                 } else {
 196 ///                     break
 197 ///                 }
 198 ///             }
 199 ///         }
 200 ///     }
 201 /// }
 202 /// ```
 203 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
 204 #[stable(feature = "rust1", since = "1.0.0")]
 205 pub struct Utf8Error {
 206     valid_up_to: usize,
 207     error_len: Option<u8>,
 208 }
 209
 210 impl Utf8Error {
 211     /// Returns the index in the given string up to which valid UTF-8 was
 212     /// verified.
 213     ///
 214     /// It is the maximum index such that `from_utf8(&input[..index])`
 215     /// would return `Ok(_)`.
 216     ///
 217     /// # Examples
 218     ///
 219     /// Basic usage:
 220     ///
 221     /// ```
 222     /// use std::str;
 223     ///
 224     /// // some invalid bytes, in a vector
 225     /// let sparkle_heart = vec![0, 159, 146, 150];
 226     ///
 227     /// // std::str::from_utf8 returns a Utf8Error
 228     /// let error = str::from_utf8(&sparkle_heart).unwrap_err();
 229     ///
 230     /// // the second byte is invalid here
 231     /// assert_eq!(1, error.valid_up_to());
 232     /// ```
 233     #[stable(feature = "utf8_error", since = "1.5.0")]
 234     pub fn valid_up_to(&self) -> usize { self.valid_up_to }
 235
 236     /// Provide more information about the failure:
 237     ///
 238     /// * `None`: the end of the input was reached unexpectedly.
 239     ///   `self.valid_up_to()` is 1 to 3 bytes from the end of the input.
 240     ///   If a byte stream (such as a file or a network socket) is being decoded incrementally,
 241     ///   this could be a valid `char` whose UTF-8 byte sequence is spanning multiple chunks.
 242     ///
 243     /// * `Some(len)`: an unexpected byte was encountered.
 244     ///   The length provided is that of the invalid byte sequence
 245     ///   that starts at the index given by `valid_up_to()`.
 246     ///   Decoding should resume after that sequence
 247     ///   (after inserting a [`U+FFFD REPLACEMENT CHARACTER`][U+FFFD]) in case of
 248     ///   lossy decoding.
 249     ///
 250     /// [U+FFFD]: ../../std/char/constant.REPLACEMENT_CHARACTER.html
 251     #[stable(feature = "utf8_error_error_len", since = "1.20.0")]
 252     pub fn error_len(&self) -> Option<usize> {
 253         self.error_len.map(|len| len as usize)
 254     }
 255 }
 256
 257 /// Converts a slice of bytes to a string slice.
 258 ///
 259 /// A string slice ([`&str`]) is made of bytes ([`u8`]), and a byte slice
 260 /// ([`&[u8]`][byteslice]) is made of bytes, so this function converts between
 261 /// the two. Not all byte slices are valid string slices, however: [`&str`] requires
 262 /// that it is valid UTF-8. `from_utf8()` checks to ensure that the bytes are valid
 263 /// UTF-8, and then does the conversion.
 264 ///
 265 /// [`&str`]: ../../std/primitive.str.html
 266 /// [`u8`]: ../../std/primitive.u8.html
 267 /// [byteslice]: ../../std/primitive.slice.html
 268 ///
 269 /// If you are sure that the byte slice is valid UTF-8, and you don't want to
 270 /// incur the overhead of the validity check, there is an unsafe version of
 271 /// this function, [`from_utf8_unchecked`][fromutf8u], which has the same
 272 /// behavior but skips the check.
 273 ///
 274 /// [fromutf8u]: fn.from_utf8_unchecked.html
 275 ///
 276 /// If you need a `String` instead of a `&str`, consider
 277 /// [`String::from_utf8`][string].
 278 ///
 279 /// [string]: ../../std/string/struct.String.html#method.from_utf8
 280 ///
 281 /// Because you can stack-allocate a `[u8; N]`, and you can take a
 282 /// [`&[u8]`][byteslice] of it, this function is one way to have a
 283 /// stack-allocated string. There is an example of this in the
 284 /// examples section below.
 285 ///
 286 /// [byteslice]: ../../std/primitive.slice.html
 287 ///
 288 /// # Errors
 289 ///
 290 /// Returns `Err` if the slice is not UTF-8 with a description as to why the
 291 /// provided slice is not UTF-8.
 292 ///
 293 /// # Examples
 294 ///
 295 /// Basic usage:
 296 ///
 297 /// ```
 298 /// use std::str;
 299 ///
 300 /// // some bytes, in a vector
 301 /// let sparkle_heart = vec![240, 159, 146, 150];
 302 ///
 303 /// // We know these bytes are valid, so just use `unwrap()`.
 304 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 305 ///
 306 /// assert_eq!("💖", sparkle_heart);
 307 /// ```
 308 ///
 309 /// Incorrect bytes:
 310 ///
 311 /// ```
 312 /// use std::str;
 313 ///
 314 /// // some invalid bytes, in a vector
 315 /// let sparkle_heart = vec![0, 159, 146, 150];
 316 ///
 317 /// assert!(str::from_utf8(&sparkle_heart).is_err());
 318 /// ```
 319 ///
 320 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 321 /// errors that can be returned.
 322 ///
 323 /// [error]: struct.Utf8Error.html
 324 ///
 325 /// A "stack allocated string":
 326 ///
 327 /// ```
 328 /// use std::str;
 329 ///
 330 /// // some bytes, in a stack-allocated array
 331 /// let sparkle_heart = [240, 159, 146, 150];
 332 ///
 333 /// // We know these bytes are valid, so just use `unwrap()`.
 334 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 335 ///
 336 /// assert_eq!("💖", sparkle_heart);
 337 /// ```
 338 #[stable(feature = "rust1", since = "1.0.0")]
 339 pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
 340     run_utf8_validation(v)?;
 341     Ok(unsafe { from_utf8_unchecked(v) })
 342 }
 343
 344 /// Converts a mutable slice of bytes to a mutable string slice.
 345 ///
 346 /// # Examples
 347 ///
 348 /// Basic usage:
 349 ///
 350 /// ```
 351 /// use std::str;
 352 ///
 353 /// // "Hello, Rust!" as a mutable vector
 354 /// let mut hellorust = vec![72, 101, 108, 108, 111, 44, 32, 82, 117, 115, 116, 33];
 355 ///
 356 /// // As we know these bytes are valid, we can use `unwrap()`
 357 /// let outstr = str::from_utf8_mut(&mut hellorust).unwrap();
 358 ///
 359 /// assert_eq!("Hello, Rust!", outstr);
 360 /// ```
 361 ///
 362 /// Incorrect bytes:
 363 ///
 364 /// ```
 365 /// use std::str;
 366 ///
 367 /// // Some invalid bytes in a mutable vector
 368 /// let mut invalid = vec![128, 223];
 369 ///
 370 /// assert!(str::from_utf8_mut(&mut invalid).is_err());
 371 /// ```
 372 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 373 /// errors that can be returned.
 374 ///
 375 /// [error]: struct.Utf8Error.html
 376 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 377 pub fn from_utf8_mut(v: &mut [u8]) -> Result<&mut str, Utf8Error> {
 378     run_utf8_validation(v)?;
 379     Ok(unsafe { from_utf8_unchecked_mut(v) })
 380 }
 381
 382 /// Converts a slice of bytes to a string slice without checking
 383 /// that the string contains valid UTF-8.
 384 ///
 385 /// See the safe version, [`from_utf8`][fromutf8], for more information.
 386 ///
 387 /// [fromutf8]: fn.from_utf8.html
 388 ///
 389 /// # Safety
 390 ///
 391 /// This function is unsafe because it does not check that the bytes passed to
 392 /// it are valid UTF-8. If this constraint is violated, undefined behavior
 393 /// results, as the rest of Rust assumes that [`&str`]s are valid UTF-8.
 394 ///
 395 /// [`&str`]: ../../std/primitive.str.html
 396 ///
 397 /// # Examples
 398 ///
 399 /// Basic usage:
 400 ///
 401 /// ```
 402 /// use std::str;
 403 ///
 404 /// // some bytes, in a vector
 405 /// let sparkle_heart = vec![240, 159, 146, 150];
 406 ///
 407 /// let sparkle_heart = unsafe {
 408 ///     str::from_utf8_unchecked(&sparkle_heart)
 409 /// };
 410 ///
 411 /// assert_eq!("💖", sparkle_heart);
 412 /// ```
 413 #[inline]
 414 #[stable(feature = "rust1", since = "1.0.0")]
 415 pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
 416     &*(v as *const [u8] as *const str)
 417 }
 418
 419 /// Converts a slice of bytes to a string slice without checking
 420 /// that the string contains valid UTF-8; mutable version.
 421 ///
 422 /// See the immutable version, [`from_utf8_unchecked()`][fromutf8], for more information.
 423 ///
 424 /// [fromutf8]: fn.from_utf8_unchecked.html
 425 ///
 426 /// # Examples
 427 ///
 428 /// Basic usage:
 429 ///
 430 /// ```
 431 /// use std::str;
 432 ///
 433 /// let mut heart = vec![240, 159, 146, 150];
 434 /// let heart = unsafe { str::from_utf8_unchecked_mut(&mut heart) };
 435 ///
 436 /// assert_eq!("💖", heart);
 437 /// ```
 438 #[inline]
 439 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 440 pub unsafe fn from_utf8_unchecked_mut(v: &mut [u8]) -> &mut str {
 441     &mut *(v as *mut [u8] as *mut str)
 442 }
 443
 444 #[stable(feature = "rust1", since = "1.0.0")]
 445 impl fmt::Display for Utf8Error {
 446     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 447         if let Some(error_len) = self.error_len {
 448             write!(f, "invalid utf-8 sequence of {} bytes from index {}",
 449                    error_len, self.valid_up_to)
 450         } else {
 451             write!(f, "incomplete utf-8 byte sequence from index {}", self.valid_up_to)
 452         }
 453     }
 454 }
 455
 456 /*
 457 Section: Iterators
 458 */
 459
 460 /// An iterator over the [`char`]s of a string slice.
 461 ///
 462 /// [`char`]: ../../std/primitive.char.html
 463 ///
 464 /// This struct is created by the [`chars`] method on [`str`].
 465 /// See its documentation for more.
 466 ///
 467 /// [`chars`]: ../../std/primitive.str.html#method.chars
 468 /// [`str`]: ../../std/primitive.str.html
 469 #[derive(Clone, Debug)]
 470 #[stable(feature = "rust1", since = "1.0.0")]
 471 pub struct Chars<'a> {
 472     iter: slice::Iter<'a, u8>
 473 }
 474
 475 /// Returns the initial codepoint accumulator for the first byte.
 476 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
 477 /// for width 3, and 3 bits for width 4.
 478 #[inline]
 479 fn utf8_first_byte(byte: u8, width: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
 480
 481 /// Returns the value of `ch` updated with continuation byte `byte`.
 482 #[inline]
 483 fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
 484
 485 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
 486 /// bits `10`).
 487 #[inline]
 488 fn utf8_is_cont_byte(byte: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
 489
 490 #[inline]
 491 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 492     match opt {
 493         Some(&byte) => byte,
 494         None => 0,
 495     }
 496 }
 497
 498 /// Reads the next code point out of a byte iterator (assuming a
 499 /// UTF-8-like encoding).
 500 #[unstable(feature = "str_internals", issue = "0")]
 501 #[inline]
 502 pub fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
 503     // Decode UTF-8
 504     let x = *bytes.next()?;
 505     if x < 128 {
 506         return Some(x as u32)
 507     }
 508
 509     // Multibyte case follows
 510     // Decode from a byte combination out of: [[[x y] z] w]
 511     // NOTE: Performance is sensitive to the exact formulation here
 512     let init = utf8_first_byte(x, 2);
 513     let y = unwrap_or_0(bytes.next());
 514     let mut ch = utf8_acc_cont_byte(init, y);
 515     if x >= 0xE0 {
 516         // [[x y z] w] case
 517         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 518         let z = unwrap_or_0(bytes.next());
 519         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
 520         ch = init << 12 | y_z;
 521         if x >= 0xF0 {
 522             // [x y z w] case
 523             // use only the lower 3 bits of `init`
 524             let w = unwrap_or_0(bytes.next());
 525             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
 526         }
 527     }
 528
 529     Some(ch)
 530 }
 531
 532 /// Reads the last code point out of a byte iterator (assuming a
 533 /// UTF-8-like encoding).
 534 #[inline]
 535 fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
 536     where I: DoubleEndedIterator<Item = &'a u8>,
 537 {
 538     // Decode UTF-8
 539     let w = match *bytes.next_back()? {
 540         next_byte if next_byte < 128 => return Some(next_byte as u32),
 541         back_byte => back_byte,
 542     };
 543
 544     // Multibyte case follows
 545     // Decode from a byte combination out of: [x [y [z w]]]
 546     let mut ch;
 547     let z = unwrap_or_0(bytes.next_back());
 548     ch = utf8_first_byte(z, 2);
 549     if utf8_is_cont_byte(z) {
 550         let y = unwrap_or_0(bytes.next_back());
 551         ch = utf8_first_byte(y, 3);
 552         if utf8_is_cont_byte(y) {
 553             let x = unwrap_or_0(bytes.next_back());
 554             ch = utf8_first_byte(x, 4);
 555             ch = utf8_acc_cont_byte(ch, y);
 556         }
 557         ch = utf8_acc_cont_byte(ch, z);
 558     }
 559     ch = utf8_acc_cont_byte(ch, w);
 560
 561     Some(ch)
 562 }
 563
 564 #[stable(feature = "rust1", since = "1.0.0")]
 565 impl<'a> Iterator for Chars<'a> {
 566     type Item = char;
 567
 568     #[inline]
 569     fn next(&mut self) -> Option<char> {
 570         next_code_point(&mut self.iter).map(|ch| {
 571             // str invariant says `ch` is a valid Unicode Scalar Value
 572             unsafe {
 573                 char::from_u32_unchecked(ch)
 574             }
 575         })
 576     }
 577
 578     #[inline]
 579     fn count(self) -> usize {
 580         // length in `char` is equal to the number of non-continuation bytes
 581         let bytes_len = self.iter.len();
 582         let mut cont_bytes = 0;
 583         for &byte in self.iter {
 584             cont_bytes += utf8_is_cont_byte(byte) as usize;
 585         }
 586         bytes_len - cont_bytes
 587     }
 588
 589     #[inline]
 590     fn size_hint(&self) -> (usize, Option<usize>) {
 591         let len = self.iter.len();
 592         // `(len + 3)` can't overflow, because we know that the `slice::Iter`
 593         // belongs to a slice in memory which has a maximum length of
 594         // `isize::MAX` (that's well below `usize::MAX`).
 595         ((len + 3) / 4, Some(len))
 596     }
 597
 598     #[inline]
 599     fn last(mut self) -> Option<char> {
 600         // No need to go through the entire string.
 601         self.next_back()
 602     }
 603 }
 604
 605 #[stable(feature = "rust1", since = "1.0.0")]
 606 impl<'a> DoubleEndedIterator for Chars<'a> {
 607     #[inline]
 608     fn next_back(&mut self) -> Option<char> {
 609         next_code_point_reverse(&mut self.iter).map(|ch| {
 610             // str invariant says `ch` is a valid Unicode Scalar Value
 611             unsafe {
 612                 char::from_u32_unchecked(ch)
 613             }
 614         })
 615     }
 616 }
 617
 618 #[stable(feature = "fused", since = "1.26.0")]
 619 impl FusedIterator for Chars<'_> {}
 620
 621 impl<'a> Chars<'a> {
 622     /// View the underlying data as a subslice of the original data.
 623     ///
 624     /// This has the same lifetime as the original slice, and so the
 625     /// iterator can continue to be used while this exists.
 626     ///
 627     /// # Examples
 628     ///
 629     /// ```
 630     /// let mut chars = "abc".chars();
 631     ///
 632     /// assert_eq!(chars.as_str(), "abc");
 633     /// chars.next();
 634     /// assert_eq!(chars.as_str(), "bc");
 635     /// chars.next();
 636     /// chars.next();
 637     /// assert_eq!(chars.as_str(), "");
 638     /// ```
 639     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 640     #[inline]
 641     pub fn as_str(&self) -> &'a str {
 642         unsafe { from_utf8_unchecked(self.iter.as_slice()) }
 643     }
 644 }
 645
 646 /// An iterator over the [`char`]s of a string slice, and their positions.
 647 ///
 648 /// [`char`]: ../../std/primitive.char.html
 649 ///
 650 /// This struct is created by the [`char_indices`] method on [`str`].
 651 /// See its documentation for more.
 652 ///
 653 /// [`char_indices`]: ../../std/primitive.str.html#method.char_indices
 654 /// [`str`]: ../../std/primitive.str.html
 655 #[derive(Clone, Debug)]
 656 #[stable(feature = "rust1", since = "1.0.0")]
 657 pub struct CharIndices<'a> {
 658     front_offset: usize,
 659     iter: Chars<'a>,
 660 }
 661
 662 #[stable(feature = "rust1", since = "1.0.0")]
 663 impl<'a> Iterator for CharIndices<'a> {
 664     type Item = (usize, char);
 665
 666     #[inline]
 667     fn next(&mut self) -> Option<(usize, char)> {
 668         let pre_len = self.iter.iter.len();
 669         match self.iter.next() {
 670             None => None,
 671             Some(ch) => {
 672                 let index = self.front_offset;
 673                 let len = self.iter.iter.len();
 674                 self.front_offset += pre_len - len;
 675                 Some((index, ch))
 676             }
 677         }
 678     }
 679
 680     #[inline]
 681     fn count(self) -> usize {
 682         self.iter.count()
 683     }
 684
 685     #[inline]
 686     fn size_hint(&self) -> (usize, Option<usize>) {
 687         self.iter.size_hint()
 688     }
 689
 690     #[inline]
 691     fn last(mut self) -> Option<(usize, char)> {
 692         // No need to go through the entire string.
 693         self.next_back()
 694     }
 695 }
 696
 697 #[stable(feature = "rust1", since = "1.0.0")]
 698 impl<'a> DoubleEndedIterator for CharIndices<'a> {
 699     #[inline]
 700     fn next_back(&mut self) -> Option<(usize, char)> {
 701         self.iter.next_back().map(|ch| {
 702             let index = self.front_offset + self.iter.iter.len();
 703             (index, ch)
 704         })
 705     }
 706 }
 707
 708 #[stable(feature = "fused", since = "1.26.0")]
 709 impl FusedIterator for CharIndices<'_> {}
 710
 711 impl<'a> CharIndices<'a> {
 712     /// View the underlying data as a subslice of the original data.
 713     ///
 714     /// This has the same lifetime as the original slice, and so the
 715     /// iterator can continue to be used while this exists.
 716     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 717     #[inline]
 718     pub fn as_str(&self) -> &'a str {
 719         self.iter.as_str()
 720     }
 721 }
 722
 723 /// An iterator over the bytes of a string slice.
 724 ///
 725 /// This struct is created by the [`bytes`] method on [`str`].
 726 /// See its documentation for more.
 727 ///
 728 /// [`bytes`]: ../../std/primitive.str.html#method.bytes
 729 /// [`str`]: ../../std/primitive.str.html
 730 #[stable(feature = "rust1", since = "1.0.0")]
 731 #[derive(Clone, Debug)]
 732 pub struct Bytes<'a>(Cloned<slice::Iter<'a, u8>>);
 733
 734 #[stable(feature = "rust1", since = "1.0.0")]
 735 impl Iterator for Bytes<'_> {
 736     type Item = u8;
 737
 738     #[inline]
 739     fn next(&mut self) -> Option<u8> {
 740         self.0.next()
 741     }
 742
 743     #[inline]
 744     fn size_hint(&self) -> (usize, Option<usize>) {
 745         self.0.size_hint()
 746     }
 747
 748     #[inline]
 749     fn count(self) -> usize {
 750         self.0.count()
 751     }
 752
 753     #[inline]
 754     fn last(self) -> Option<Self::Item> {
 755         self.0.last()
 756     }
 757
 758     #[inline]
 759     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 760         self.0.nth(n)
 761     }
 762
 763     #[inline]
 764     fn all<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 765         self.0.all(f)
 766     }
 767
 768     #[inline]
 769     fn any<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 770         self.0.any(f)
 771     }
 772
 773     #[inline]
 774     fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where
 775         P: FnMut(&Self::Item) -> bool
 776     {
 777         self.0.find(predicate)
 778     }
 779
 780     #[inline]
 781     fn position<P>(&mut self, predicate: P) -> Option<usize> where
 782         P: FnMut(Self::Item) -> bool
 783     {
 784         self.0.position(predicate)
 785     }
 786
 787     #[inline]
 788     fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
 789         P: FnMut(Self::Item) -> bool
 790     {
 791         self.0.rposition(predicate)
 792     }
 793 }
 794
 795 #[stable(feature = "rust1", since = "1.0.0")]
 796 impl DoubleEndedIterator for Bytes<'_> {
 797     #[inline]
 798     fn next_back(&mut self) -> Option<u8> {
 799         self.0.next_back()
 800     }
 801
 802     #[inline]
 803     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where
 804         P: FnMut(&Self::Item) -> bool
 805     {
 806         self.0.rfind(predicate)
 807     }
 808 }
 809
 810 #[stable(feature = "rust1", since = "1.0.0")]
 811 impl ExactSizeIterator for Bytes<'_> {
 812     #[inline]
 813     fn len(&self) -> usize {
 814         self.0.len()
 815     }
 816
 817     #[inline]
 818     fn is_empty(&self) -> bool {
 819         self.0.is_empty()
 820     }
 821 }
 822
 823 #[stable(feature = "fused", since = "1.26.0")]
 824 impl FusedIterator for Bytes<'_> {}
 825
 826 #[unstable(feature = "trusted_len", issue = "37572")]
 827 unsafe impl TrustedLen for Bytes<'_> {}
 828
 829 #[doc(hidden)]
 830 unsafe impl<'a> TrustedRandomAccess for Bytes<'a> {
 831     unsafe fn get_unchecked(&mut self, i: usize) -> u8 {
 832         self.0.get_unchecked(i)
 833     }
 834     fn may_have_side_effect() -> bool { false }
 835 }
 836
 837 /// This macro generates a Clone impl for string pattern API
 838 /// wrapper types of the form X<'a, P>
 839 macro_rules! derive_pattern_clone {
 840     (clone $t:ident with |$s:ident| $e:expr) => {
 841         impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
 842             where P::Searcher: Clone
 843         {
 844             fn clone(&self) -> Self {
 845                 let $s = self;
 846                 $e
 847             }
 848         }
 849     }
 850 }
 851
 852 /// This macro generates two public iterator structs
 853 /// wrapping a private internal one that makes use of the `Pattern` API.
 854 ///
 855 /// For all patterns `P: Pattern<'a>` the following items will be
 856 /// generated (generics omitted):
 857 ///
 858 /// struct $forward_iterator($internal_iterator);
 859 /// struct $reverse_iterator($internal_iterator);
 860 ///
 861 /// impl Iterator for $forward_iterator
 862 /// { /* internal ends up calling Searcher::next_match() */ }
 863 ///
 864 /// impl DoubleEndedIterator for $forward_iterator
 865 ///       where P::Searcher: DoubleEndedSearcher
 866 /// { /* internal ends up calling Searcher::next_match_back() */ }
 867 ///
 868 /// impl Iterator for $reverse_iterator
 869 ///       where P::Searcher: ReverseSearcher
 870 /// { /* internal ends up calling Searcher::next_match_back() */ }
 871 ///
 872 /// impl DoubleEndedIterator for $reverse_iterator
 873 ///       where P::Searcher: DoubleEndedSearcher
 874 /// { /* internal ends up calling Searcher::next_match() */ }
 875 ///
 876 /// The internal one is defined outside the macro, and has almost the same
 877 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
 878 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
 879 ///
 880 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
 881 /// `Pattern` might not return the same elements, so actually implementing
 882 /// `DoubleEndedIterator` for it would be incorrect.
 883 /// (See the docs in `str::pattern` for more details)
 884 ///
 885 /// However, the internal struct still represents a single ended iterator from
 886 /// either end, and depending on pattern is also a valid double ended iterator,
 887 /// so the two wrapper structs implement `Iterator`
 888 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
 889 /// to the complex impls seen above.
 890 macro_rules! generate_pattern_iterators {
 891     {
 892         // Forward iterator
 893         forward:
 894             $(#[$forward_iterator_attribute:meta])*
 895             struct $forward_iterator:ident;
 896
 897         // Reverse iterator
 898         reverse:
 899             $(#[$reverse_iterator_attribute:meta])*
 900             struct $reverse_iterator:ident;
 901
 902         // Stability of all generated items
 903         stability:
 904             $(#[$common_stability_attribute:meta])*
 905
 906         // Internal almost-iterator that is being delegated to
 907         internal:
 908             $internal_iterator:ident yielding ($iterty:ty);
 909
 910         // Kind of delegation - either single ended or double ended
 911         delegate $($t:tt)*
 912     } => {
 913         $(#[$forward_iterator_attribute])*
 914         $(#[$common_stability_attribute])*
 915         pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 916
 917         $(#[$common_stability_attribute])*
 918         impl<'a, P: Pattern<'a>> fmt::Debug for $forward_iterator<'a, P>
 919             where P::Searcher: fmt::Debug
 920         {
 921             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 922                 f.debug_tuple(stringify!($forward_iterator))
 923                     .field(&self.0)
 924                     .finish()
 925             }
 926         }
 927
 928         $(#[$common_stability_attribute])*
 929         impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
 930             type Item = $iterty;
 931
 932             #[inline]
 933             fn next(&mut self) -> Option<$iterty> {
 934                 self.0.next()
 935             }
 936         }
 937
 938         $(#[$common_stability_attribute])*
 939         impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
 940             where P::Searcher: Clone
 941         {
 942             fn clone(&self) -> Self {
 943                 $forward_iterator(self.0.clone())
 944             }
 945         }
 946
 947         $(#[$reverse_iterator_attribute])*
 948         $(#[$common_stability_attribute])*
 949         pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 950
 951         $(#[$common_stability_attribute])*
 952         impl<'a, P: Pattern<'a>> fmt::Debug for $reverse_iterator<'a, P>
 953             where P::Searcher: fmt::Debug
 954         {
 955             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 956                 f.debug_tuple(stringify!($reverse_iterator))
 957                     .field(&self.0)
 958                     .finish()
 959             }
 960         }
 961
 962         $(#[$common_stability_attribute])*
 963         impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
 964             where P::Searcher: ReverseSearcher<'a>
 965         {
 966             type Item = $iterty;
 967
 968             #[inline]
 969             fn next(&mut self) -> Option<$iterty> {
 970                 self.0.next_back()
 971             }
 972         }
 973
 974         $(#[$common_stability_attribute])*
 975         impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
 976             where P::Searcher: Clone
 977         {
 978             fn clone(&self) -> Self {
 979                 $reverse_iterator(self.0.clone())
 980             }
 981         }
 982
 983         #[stable(feature = "fused", since = "1.26.0")]
 984         impl<'a, P: Pattern<'a>> FusedIterator for $forward_iterator<'a, P> {}
 985
 986         #[stable(feature = "fused", since = "1.26.0")]
 987         impl<'a, P: Pattern<'a>> FusedIterator for $reverse_iterator<'a, P>
 988             where P::Searcher: ReverseSearcher<'a> {}
 989
 990         generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
 991                                                 $forward_iterator,
 992                                                 $reverse_iterator, $iterty);
 993     };
 994     {
 995         double ended; with $(#[$common_stability_attribute:meta])*,
 996                            $forward_iterator:ident,
 997                            $reverse_iterator:ident, $iterty:ty
 998     } => {
 999         $(#[$common_stability_attribute])*
1000         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
1001             where P::Searcher: DoubleEndedSearcher<'a>
1002         {
1003             #[inline]
1004             fn next_back(&mut self) -> Option<$iterty> {
1005                 self.0.next_back()
1006             }
1007         }
1008
1009         $(#[$common_stability_attribute])*
1010         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
1011             where P::Searcher: DoubleEndedSearcher<'a>
1012         {
1013             #[inline]
1014             fn next_back(&mut self) -> Option<$iterty> {
1015                 self.0.next()
1016             }
1017         }
1018     };
1019     {
1020         single ended; with $(#[$common_stability_attribute:meta])*,
1021                            $forward_iterator:ident,
1022                            $reverse_iterator:ident, $iterty:ty
1023     } => {}
1024 }
1025
1026 derive_pattern_clone!{
1027     clone SplitInternal
1028     with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
1029 }
1030
1031 struct SplitInternal<'a, P: Pattern<'a>> {
1032     start: usize,
1033     end: usize,
1034     matcher: P::Searcher,
1035     allow_trailing_empty: bool,
1036     finished: bool,
1037 }
1038
1039 impl<'a, P: Pattern<'a>> fmt::Debug for SplitInternal<'a, P> where P::Searcher: fmt::Debug {
1040     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1041         f.debug_struct("SplitInternal")
1042             .field("start", &self.start)
1043             .field("end", &self.end)
1044             .field("matcher", &self.matcher)
1045             .field("allow_trailing_empty", &self.allow_trailing_empty)
1046             .field("finished", &self.finished)
1047             .finish()
1048     }
1049 }
1050
1051 impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
1052     #[inline]
1053     fn get_end(&mut self) -> Option<&'a str> {
1054         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
1055             self.finished = true;
1056             unsafe {
1057                 let string = self.matcher.haystack().get_unchecked(self.start..self.end);
1058                 Some(string)
1059             }
1060         } else {
1061             None
1062         }
1063     }
1064
1065     #[inline]
1066     fn next(&mut self) -> Option<&'a str> {
1067         if self.finished { return None }
1068
1069         let haystack = self.matcher.haystack();
1070         match self.matcher.next_match() {
1071             Some((a, b)) => unsafe {
1072                 let elt = haystack.get_unchecked(self.start..a);
1073                 self.start = b;
1074                 Some(elt)
1075             },
1076             None => self.get_end(),
1077         }
1078     }
1079
1080     #[inline]
1081     fn next_back(&mut self) -> Option<&'a str>
1082         where P::Searcher: ReverseSearcher<'a>
1083     {
1084         if self.finished { return None }
1085
1086         if !self.allow_trailing_empty {
1087             self.allow_trailing_empty = true;
1088             match self.next_back() {
1089                 Some(elt) if !elt.is_empty() => return Some(elt),
1090                 _ => if self.finished { return None }
1091             }
1092         }
1093
1094         let haystack = self.matcher.haystack();
1095         match self.matcher.next_match_back() {
1096             Some((a, b)) => unsafe {
1097                 let elt = haystack.get_unchecked(b..self.end);
1098                 self.end = a;
1099                 Some(elt)
1100             },
1101             None => unsafe {
1102                 self.finished = true;
1103                 Some(haystack.get_unchecked(self.start..self.end))
1104             },
1105         }
1106     }
1107 }
1108
1109 generate_pattern_iterators! {
1110     forward:
1111         /// Created with the method [`split`].
1112         ///
1113         /// [`split`]: ../../std/primitive.str.html#method.split
1114         struct Split;
1115     reverse:
1116         /// Created with the method [`rsplit`].
1117         ///
1118         /// [`rsplit`]: ../../std/primitive.str.html#method.rsplit
1119         struct RSplit;
1120     stability:
1121         #[stable(feature = "rust1", since = "1.0.0")]
1122     internal:
1123         SplitInternal yielding (&'a str);
1124     delegate double ended;
1125 }
1126
1127 generate_pattern_iterators! {
1128     forward:
1129         /// Created with the method [`split_terminator`].
1130         ///
1131         /// [`split_terminator`]: ../../std/primitive.str.html#method.split_terminator
1132         struct SplitTerminator;
1133     reverse:
1134         /// Created with the method [`rsplit_terminator`].
1135         ///
1136         /// [`rsplit_terminator`]: ../../std/primitive.str.html#method.rsplit_terminator
1137         struct RSplitTerminator;
1138     stability:
1139         #[stable(feature = "rust1", since = "1.0.0")]
1140     internal:
1141         SplitInternal yielding (&'a str);
1142     delegate double ended;
1143 }
1144
1145 derive_pattern_clone!{
1146     clone SplitNInternal
1147     with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
1148 }
1149
1150 struct SplitNInternal<'a, P: Pattern<'a>> {
1151     iter: SplitInternal<'a, P>,
1152     /// The number of splits remaining
1153     count: usize,
1154 }
1155
1156 impl<'a, P: Pattern<'a>> fmt::Debug for SplitNInternal<'a, P> where P::Searcher: fmt::Debug {
1157     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1158         f.debug_struct("SplitNInternal")
1159             .field("iter", &self.iter)
1160             .field("count", &self.count)
1161             .finish()
1162     }
1163 }
1164
1165 impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
1166     #[inline]
1167     fn next(&mut self) -> Option<&'a str> {
1168         match self.count {
1169             0 => None,
1170             1 => { self.count = 0; self.iter.get_end() }
1171             _ => { self.count -= 1; self.iter.next() }
1172         }
1173     }
1174
1175     #[inline]
1176     fn next_back(&mut self) -> Option<&'a str>
1177         where P::Searcher: ReverseSearcher<'a>
1178     {
1179         match self.count {
1180             0 => None,
1181             1 => { self.count = 0; self.iter.get_end() }
1182             _ => { self.count -= 1; self.iter.next_back() }
1183         }
1184     }
1185 }
1186
1187 generate_pattern_iterators! {
1188     forward:
1189         /// Created with the method [`splitn`].
1190         ///
1191         /// [`splitn`]: ../../std/primitive.str.html#method.splitn
1192         struct SplitN;
1193     reverse:
1194         /// Created with the method [`rsplitn`].
1195         ///
1196         /// [`rsplitn`]: ../../std/primitive.str.html#method.rsplitn
1197         struct RSplitN;
1198     stability:
1199         #[stable(feature = "rust1", since = "1.0.0")]
1200     internal:
1201         SplitNInternal yielding (&'a str);
1202     delegate single ended;
1203 }
1204
1205 derive_pattern_clone!{
1206     clone MatchIndicesInternal
1207     with |s| MatchIndicesInternal(s.0.clone())
1208 }
1209
1210 struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
1211
1212 impl<'a, P: Pattern<'a>> fmt::Debug for MatchIndicesInternal<'a, P> where P::Searcher: fmt::Debug {
1213     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1214         f.debug_tuple("MatchIndicesInternal")
1215             .field(&self.0)
1216             .finish()
1217     }
1218 }
1219
1220 impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
1221     #[inline]
1222     fn next(&mut self) -> Option<(usize, &'a str)> {
1223         self.0.next_match().map(|(start, end)| unsafe {
1224             (start, self.0.haystack().get_unchecked(start..end))
1225         })
1226     }
1227
1228     #[inline]
1229     fn next_back(&mut self) -> Option<(usize, &'a str)>
1230         where P::Searcher: ReverseSearcher<'a>
1231     {
1232         self.0.next_match_back().map(|(start, end)| unsafe {
1233             (start, self.0.haystack().get_unchecked(start..end))
1234         })
1235     }
1236 }
1237
1238 generate_pattern_iterators! {
1239     forward:
1240         /// Created with the method [`match_indices`].
1241         ///
1242         /// [`match_indices`]: ../../std/primitive.str.html#method.match_indices
1243         struct MatchIndices;
1244     reverse:
1245         /// Created with the method [`rmatch_indices`].
1246         ///
1247         /// [`rmatch_indices`]: ../../std/primitive.str.html#method.rmatch_indices
1248         struct RMatchIndices;
1249     stability:
1250         #[stable(feature = "str_match_indices", since = "1.5.0")]
1251     internal:
1252         MatchIndicesInternal yielding ((usize, &'a str));
1253     delegate double ended;
1254 }
1255
1256 derive_pattern_clone!{
1257     clone MatchesInternal
1258     with |s| MatchesInternal(s.0.clone())
1259 }
1260
1261 struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
1262
1263 impl<'a, P: Pattern<'a>> fmt::Debug for MatchesInternal<'a, P> where P::Searcher: fmt::Debug {
1264     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1265         f.debug_tuple("MatchesInternal")
1266             .field(&self.0)
1267             .finish()
1268     }
1269 }
1270
1271 impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
1272     #[inline]
1273     fn next(&mut self) -> Option<&'a str> {
1274         self.0.next_match().map(|(a, b)| unsafe {
1275             // Indices are known to be on utf8 boundaries
1276             self.0.haystack().get_unchecked(a..b)
1277         })
1278     }
1279
1280     #[inline]
1281     fn next_back(&mut self) -> Option<&'a str>
1282         where P::Searcher: ReverseSearcher<'a>
1283     {
1284         self.0.next_match_back().map(|(a, b)| unsafe {
1285             // Indices are known to be on utf8 boundaries
1286             self.0.haystack().get_unchecked(a..b)
1287         })
1288     }
1289 }
1290
1291 generate_pattern_iterators! {
1292     forward:
1293         /// Created with the method [`matches`].
1294         ///
1295         /// [`matches`]: ../../std/primitive.str.html#method.matches
1296         struct Matches;
1297     reverse:
1298         /// Created with the method [`rmatches`].
1299         ///
1300         /// [`rmatches`]: ../../std/primitive.str.html#method.rmatches
1301         struct RMatches;
1302     stability:
1303         #[stable(feature = "str_matches", since = "1.2.0")]
1304     internal:
1305         MatchesInternal yielding (&'a str);
1306     delegate double ended;
1307 }
1308
1309 /// An iterator over the lines of a string, as string slices.
1310 ///
1311 /// This struct is created with the [`lines`] method on [`str`].
1312 /// See its documentation for more.
1313 ///
1314 /// [`lines`]: ../../std/primitive.str.html#method.lines
1315 /// [`str`]: ../../std/primitive.str.html
1316 #[stable(feature = "rust1", since = "1.0.0")]
1317 #[derive(Clone, Debug)]
1318 pub struct Lines<'a>(Map<SplitTerminator<'a, char>, LinesAnyMap>);
1319
1320 #[stable(feature = "rust1", since = "1.0.0")]
1321 impl<'a> Iterator for Lines<'a> {
1322     type Item = &'a str;
1323
1324     #[inline]
1325     fn next(&mut self) -> Option<&'a str> {
1326         self.0.next()
1327     }
1328
1329     #[inline]
1330     fn size_hint(&self) -> (usize, Option<usize>) {
1331         self.0.size_hint()
1332     }
1333 }
1334
1335 #[stable(feature = "rust1", since = "1.0.0")]
1336 impl<'a> DoubleEndedIterator for Lines<'a> {
1337     #[inline]
1338     fn next_back(&mut self) -> Option<&'a str> {
1339         self.0.next_back()
1340     }
1341 }
1342
1343 #[stable(feature = "fused", since = "1.26.0")]
1344 impl FusedIterator for Lines<'_> {}
1345
1346 /// Created with the method [`lines_any`].
1347 ///
1348 /// [`lines_any`]: ../../std/primitive.str.html#method.lines_any
1349 #[stable(feature = "rust1", since = "1.0.0")]
1350 #[rustc_deprecated(since = "1.4.0", reason = "use lines()/Lines instead now")]
1351 #[derive(Clone, Debug)]
1352 #[allow(deprecated)]
1353 pub struct LinesAny<'a>(Lines<'a>);
1354
1355 /// A nameable, cloneable fn type
1356 #[derive(Clone)]
1357 struct LinesAnyMap;
1358
1359 impl<'a> Fn<(&'a str,)> for LinesAnyMap {
1360     #[inline]
1361     extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
1362         let l = line.len();
1363         if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
1364         else { line }
1365     }
1366 }
1367
1368 impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
1369     #[inline]
1370     extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
1371         Fn::call(&*self, (line,))
1372     }
1373 }
1374
1375 impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
1376     type Output = &'a str;
1377
1378     #[inline]
1379     extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
1380         Fn::call(&self, (line,))
1381     }
1382 }
1383
1384 #[stable(feature = "rust1", since = "1.0.0")]
1385 #[allow(deprecated)]
1386 impl<'a> Iterator for LinesAny<'a> {
1387     type Item = &'a str;
1388
1389     #[inline]
1390     fn next(&mut self) -> Option<&'a str> {
1391         self.0.next()
1392     }
1393
1394     #[inline]
1395     fn size_hint(&self) -> (usize, Option<usize>) {
1396         self.0.size_hint()
1397     }
1398 }
1399
1400 #[stable(feature = "rust1", since = "1.0.0")]
1401 #[allow(deprecated)]
1402 impl<'a> DoubleEndedIterator for LinesAny<'a> {
1403     #[inline]
1404     fn next_back(&mut self) -> Option<&'a str> {
1405         self.0.next_back()
1406     }
1407 }
1408
1409 #[stable(feature = "fused", since = "1.26.0")]
1410 #[allow(deprecated)]
1411 impl FusedIterator for LinesAny<'_> {}
1412
1413 /*
1414 Section: UTF-8 validation
1415 */
1416
1417 // use truncation to fit u64 into usize
1418 const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;
1419
1420 /// Returns `true` if any byte in the word `x` is nonascii (>= 128).
1421 #[inline]
1422 fn contains_nonascii(x: usize) -> bool {
1423     (x & NONASCII_MASK) != 0
1424 }
1425
1426 /// Walks through `iter` checking that it's a valid UTF-8 sequence,
1427 /// returning `true` in that case, or, if it is invalid, `false` with
1428 /// `iter` reset such that it is pointing at the first byte in the
1429 /// invalid sequence.
1430 #[inline]
1431 fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
1432     let mut index = 0;
1433     let len = v.len();
1434
1435     let usize_bytes = mem::size_of::<usize>();
1436     let ascii_block_size = 2 * usize_bytes;
1437     let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
1438
1439     while index < len {
1440         let old_offset = index;
1441         macro_rules! err {
1442             ($error_len: expr) => {
1443                 return Err(Utf8Error {
1444                     valid_up_to: old_offset,
1445                     error_len: $error_len,
1446                 })
1447             }
1448         }
1449
1450         macro_rules! next { () => {{
1451             index += 1;
1452             // we needed data, but there was none: error!
1453             if index >= len {
1454                 err!(None)
1455             }
1456             v[index]
1457         }}}
1458
1459         let first = v[index];
1460         if first >= 128 {
1461             let w = UTF8_CHAR_WIDTH[first as usize];
1462             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
1463             //        first  C2 80        last DF BF
1464             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
1465             //        first  E0 A0 80     last EF BF BF
1466             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
1467             //               ED A0 80 to       ED BF BF
1468             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1469             //        first  F0 90 80 80  last F4 8F BF BF
1470             //
1471             // Use the UTF-8 syntax from the RFC
1472             //
1473             // https://tools.ietf.org/html/rfc3629
1474             // UTF8-1      = %x00-7F
1475             // UTF8-2      = %xC2-DF UTF8-tail
1476             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1477             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1478             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1479             //               %xF4 %x80-8F 2( UTF8-tail )
1480             match w {
1481                 2 => if next!() & !CONT_MASK != TAG_CONT_U8 {
1482                     err!(Some(1))
1483                 },
1484                 3 => {
1485                     match (first, next!()) {
1486                         (0xE0         , 0xA0 ..= 0xBF) |
1487                         (0xE1 ..= 0xEC, 0x80 ..= 0xBF) |
1488                         (0xED         , 0x80 ..= 0x9F) |
1489                         (0xEE ..= 0xEF, 0x80 ..= 0xBF) => {}
1490                         _ => err!(Some(1))
1491                     }
1492                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1493                         err!(Some(2))
1494                     }
1495                 }
1496                 4 => {
1497                     match (first, next!()) {
1498                         (0xF0         , 0x90 ..= 0xBF) |
1499                         (0xF1 ..= 0xF3, 0x80 ..= 0xBF) |
1500                         (0xF4         , 0x80 ..= 0x8F) => {}
1501                         _ => err!(Some(1))
1502                     }
1503                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1504                         err!(Some(2))
1505                     }
1506                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1507                         err!(Some(3))
1508                     }
1509                 }
1510                 _ => err!(Some(1))
1511             }
1512             index += 1;
1513         } else {
1514             // Ascii case, try to skip forward quickly.
1515             // When the pointer is aligned, read 2 words of data per iteration
1516             // until we find a word containing a non-ascii byte.
1517             let ptr = v.as_ptr();
1518             let align = unsafe {
1519                 // the offset is safe, because `index` is guaranteed inbounds
1520                 ptr.add(index).align_offset(usize_bytes)
1521             };
1522             if align == 0 {
1523                 while index < blocks_end {
1524                     unsafe {
1525                         let block = ptr.add(index) as *const usize;
1526                         // break if there is a nonascii byte
1527                         let zu = contains_nonascii(*block);
1528                         let zv = contains_nonascii(*block.offset(1));
1529                         if zu | zv {
1530                             break;
1531                         }
1532                     }
1533                     index += ascii_block_size;
1534                 }
1535                 // step from the point where the wordwise loop stopped
1536                 while index < len && v[index] < 128 {
1537                     index += 1;
1538                 }
1539             } else {
1540                 index += 1;
1541             }
1542         }
1543     }
1544
1545     Ok(())
1546 }
1547
1548 // https://tools.ietf.org/html/rfc3629
1549 static UTF8_CHAR_WIDTH: [u8; 256] = [
1550 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1551 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1552 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1553 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1554 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1555 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1556 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1557 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1558 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1559 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1560 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1561 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1562 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1563 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1564 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1565 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1566 ];
1567
1568 /// Given a first byte, determines how many bytes are in this UTF-8 character.
1569 #[unstable(feature = "str_internals", issue = "0")]
1570 #[inline]
1571 pub fn utf8_char_width(b: u8) -> usize {
1572     UTF8_CHAR_WIDTH[b as usize] as usize
1573 }
1574
1575 /// Mask of the value bits of a continuation byte.
1576 const CONT_MASK: u8 = 0b0011_1111;
1577 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte.
1578 const TAG_CONT_U8: u8 = 0b1000_0000;
1579
1580 /*
1581 Section: Trait implementations
1582 */
1583
1584 mod traits {
1585     use cmp::Ordering;
1586     use ops;
1587     use slice::{self, SliceIndex};
1588
1589     /// Implements ordering of strings.
1590     ///
1591     /// Strings are ordered  lexicographically by their byte values.  This orders Unicode code
1592     /// points based on their positions in the code charts.  This is not necessarily the same as
1593     /// "alphabetical" order, which varies by language and locale.  Sorting strings according to
1594     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1595     /// the `str` type.
1596     #[stable(feature = "rust1", since = "1.0.0")]
1597     impl Ord for str {
1598         #[inline]
1599         fn cmp(&self, other: &str) -> Ordering {
1600             self.as_bytes().cmp(other.as_bytes())
1601         }
1602     }
1603
1604     #[stable(feature = "rust1", since = "1.0.0")]
1605     impl PartialEq for str {
1606         #[inline]
1607         fn eq(&self, other: &str) -> bool {
1608             self.as_bytes() == other.as_bytes()
1609         }
1610         #[inline]
1611         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1612     }
1613
1614     #[stable(feature = "rust1", since = "1.0.0")]
1615     impl Eq for str {}
1616
1617     /// Implements comparison operations on strings.
1618     ///
1619     /// Strings are compared lexicographically by their byte values.  This compares Unicode code
1620     /// points based on their positions in the code charts.  This is not necessarily the same as
1621     /// "alphabetical" order, which varies by language and locale.  Comparing strings according to
1622     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1623     /// the `str` type.
1624     #[stable(feature = "rust1", since = "1.0.0")]
1625     impl PartialOrd for str {
1626         #[inline]
1627         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1628             Some(self.cmp(other))
1629         }
1630     }
1631
1632     /// Implements substring slicing with syntax `&self[begin .. end]`.
1633     ///
1634     /// Returns a slice of the given string from the byte range
1635     /// [`begin`..`end`).
1636     ///
1637     /// This operation is `O(1)`.
1638     ///
1639     /// # Panics
1640     ///
1641     /// Panics if `begin` or `end` does not point to the starting
1642     /// byte offset of a character (as defined by `is_char_boundary`).
1643     /// Requires that `begin <= end` and `end <= len` where `len` is the
1644     /// length of the string.
1645     ///
1646     /// # Examples
1647     ///
1648     /// ```
1649     /// let s = "Löwe 老虎 Léopard";
1650     /// assert_eq!(&s[0 .. 1], "L");
1651     ///
1652     /// assert_eq!(&s[1 .. 9], "öwe 老");
1653     ///
1654     /// // these will panic:
1655     /// // byte 2 lies within `ö`:
1656     /// // &s[2 ..3];
1657     ///
1658     /// // byte 8 lies within `老`
1659     /// // &s[1 .. 8];
1660     ///
1661     /// // byte 100 is outside the string
1662     /// // &s[3 .. 100];
1663     /// ```
1664     #[stable(feature = "rust1", since = "1.0.0")]
1665     impl ops::Index<ops::Range<usize>> for str {
1666         type Output = str;
1667         #[inline]
1668         fn index(&self, index: ops::Range<usize>) -> &str {
1669             index.index(self)
1670         }
1671     }
1672
1673     /// Implements mutable substring slicing with syntax
1674     /// `&mut self[begin .. end]`.
1675     ///
1676     /// Returns a mutable slice of the given string from the byte range
1677     /// [`begin`..`end`).
1678     ///
1679     /// This operation is `O(1)`.
1680     ///
1681     /// # Panics
1682     ///
1683     /// Panics if `begin` or `end` does not point to the starting
1684     /// byte offset of a character (as defined by `is_char_boundary`).
1685     /// Requires that `begin <= end` and `end <= len` where `len` is the
1686     /// length of the string.
1687     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1688     impl ops::IndexMut<ops::Range<usize>> for str {
1689         #[inline]
1690         fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
1691             index.index_mut(self)
1692         }
1693     }
1694
1695     /// Implements substring slicing with syntax `&self[.. end]`.
1696     ///
1697     /// Returns a slice of the string from the beginning to byte offset
1698     /// `end`.
1699     ///
1700     /// Equivalent to `&self[0 .. end]`.
1701     #[stable(feature = "rust1", since = "1.0.0")]
1702     impl ops::Index<ops::RangeTo<usize>> for str {
1703         type Output = str;
1704
1705         #[inline]
1706         fn index(&self, index: ops::RangeTo<usize>) -> &str {
1707             index.index(self)
1708         }
1709     }
1710
1711     /// Implements mutable substring slicing with syntax `&mut self[.. end]`.
1712     ///
1713     /// Returns a mutable slice of the string from the beginning to byte offset
1714     /// `end`.
1715     ///
1716     /// Equivalent to `&mut self[0 .. end]`.
1717     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1718     impl ops::IndexMut<ops::RangeTo<usize>> for str {
1719         #[inline]
1720         fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
1721             index.index_mut(self)
1722         }
1723     }
1724
1725     /// Implements substring slicing with syntax `&self[begin ..]`.
1726     ///
1727     /// Returns a slice of the string from byte offset `begin`
1728     /// to the end of the string.
1729     ///
1730     /// Equivalent to `&self[begin .. len]`.
1731     #[stable(feature = "rust1", since = "1.0.0")]
1732     impl ops::Index<ops::RangeFrom<usize>> for str {
1733         type Output = str;
1734
1735         #[inline]
1736         fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1737             index.index(self)
1738         }
1739     }
1740
1741     /// Implements mutable substring slicing with syntax `&mut self[begin ..]`.
1742     ///
1743     /// Returns a mutable slice of the string from byte offset `begin`
1744     /// to the end of the string.
1745     ///
1746     /// Equivalent to `&mut self[begin .. len]`.
1747     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1748     impl ops::IndexMut<ops::RangeFrom<usize>> for str {
1749         #[inline]
1750         fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
1751             index.index_mut(self)
1752         }
1753     }
1754
1755     /// Implements substring slicing with syntax `&self[..]`.
1756     ///
1757     /// Returns a slice of the whole string. This operation can
1758     /// never panic.
1759     ///
1760     /// Equivalent to `&self[0 .. len]`.
1761     #[stable(feature = "rust1", since = "1.0.0")]
1762     impl ops::Index<ops::RangeFull> for str {
1763         type Output = str;
1764
1765         #[inline]
1766         fn index(&self, _index: ops::RangeFull) -> &str {
1767             self
1768         }
1769     }
1770
1771     /// Implements mutable substring slicing with syntax `&mut self[..]`.
1772     ///
1773     /// Returns a mutable slice of the whole string. This operation can
1774     /// never panic.
1775     ///
1776     /// Equivalent to `&mut self[0 .. len]`.
1777     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1778     impl ops::IndexMut<ops::RangeFull> for str {
1779         #[inline]
1780         fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
1781             self
1782         }
1783     }
1784
1785     #[stable(feature = "inclusive_range", since = "1.26.0")]
1786     impl ops::Index<ops::RangeInclusive<usize>> for str {
1787         type Output = str;
1788
1789         #[inline]
1790         fn index(&self, index: ops::RangeInclusive<usize>) -> &str {
1791             index.index(self)
1792         }
1793     }
1794
1795     #[stable(feature = "inclusive_range", since = "1.26.0")]
1796     impl ops::Index<ops::RangeToInclusive<usize>> for str {
1797         type Output = str;
1798
1799         #[inline]
1800         fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
1801             index.index(self)
1802         }
1803     }
1804
1805     #[stable(feature = "inclusive_range", since = "1.26.0")]
1806     impl ops::IndexMut<ops::RangeInclusive<usize>> for str {
1807         #[inline]
1808         fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
1809             index.index_mut(self)
1810         }
1811     }
1812     #[stable(feature = "inclusive_range", since = "1.26.0")]
1813     impl ops::IndexMut<ops::RangeToInclusive<usize>> for str {
1814         #[inline]
1815         fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
1816             index.index_mut(self)
1817         }
1818     }
1819
1820     #[inline(never)]
1821     #[cold]
1822     fn str_index_overflow_fail() -> ! {
1823         panic!("attempted to index str up to maximum usize");
1824     }
1825
1826     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1827     impl SliceIndex<str> for ops::RangeFull {
1828         type Output = str;
1829         #[inline]
1830         fn get(self, slice: &str) -> Option<&Self::Output> {
1831             Some(slice)
1832         }
1833         #[inline]
1834         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1835             Some(slice)
1836         }
1837         #[inline]
1838         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1839             slice
1840         }
1841         #[inline]
1842         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1843             slice
1844         }
1845         #[inline]
1846         fn index(self, slice: &str) -> &Self::Output {
1847             slice
1848         }
1849         #[inline]
1850         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1851             slice
1852         }
1853     }
1854
1855     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1856     impl SliceIndex<str> for ops::Range<usize> {
1857         type Output = str;
1858         #[inline]
1859         fn get(self, slice: &str) -> Option<&Self::Output> {
1860             if self.start <= self.end &&
1861                slice.is_char_boundary(self.start) &&
1862                slice.is_char_boundary(self.end) {
1863                 Some(unsafe { self.get_unchecked(slice) })
1864             } else {
1865                 None
1866             }
1867         }
1868         #[inline]
1869         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1870             if self.start <= self.end &&
1871                slice.is_char_boundary(self.start) &&
1872                slice.is_char_boundary(self.end) {
1873                 Some(unsafe { self.get_unchecked_mut(slice) })
1874             } else {
1875                 None
1876             }
1877         }
1878         #[inline]
1879         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1880             let ptr = slice.as_ptr().add(self.start);
1881             let len = self.end - self.start;
1882             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1883         }
1884         #[inline]
1885         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1886             let ptr = slice.as_ptr().add(self.start);
1887             let len = self.end - self.start;
1888             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1889         }
1890         #[inline]
1891         fn index(self, slice: &str) -> &Self::Output {
1892             let (start, end) = (self.start, self.end);
1893             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1894         }
1895         #[inline]
1896         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1897             // is_char_boundary checks that the index is in [0, .len()]
1898             // canot reuse `get` as above, because of NLL trouble
1899             if self.start <= self.end &&
1900                slice.is_char_boundary(self.start) &&
1901                slice.is_char_boundary(self.end) {
1902                 unsafe { self.get_unchecked_mut(slice) }
1903             } else {
1904                 super::slice_error_fail(slice, self.start, self.end)
1905             }
1906         }
1907     }
1908
1909     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1910     impl SliceIndex<str> for ops::RangeTo<usize> {
1911         type Output = str;
1912         #[inline]
1913         fn get(self, slice: &str) -> Option<&Self::Output> {
1914             if slice.is_char_boundary(self.end) {
1915                 Some(unsafe { self.get_unchecked(slice) })
1916             } else {
1917                 None
1918             }
1919         }
1920         #[inline]
1921         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1922             if slice.is_char_boundary(self.end) {
1923                 Some(unsafe { self.get_unchecked_mut(slice) })
1924             } else {
1925                 None
1926             }
1927         }
1928         #[inline]
1929         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1930             let ptr = slice.as_ptr();
1931             super::from_utf8_unchecked(slice::from_raw_parts(ptr, self.end))
1932         }
1933         #[inline]
1934         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1935             let ptr = slice.as_ptr();
1936             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, self.end))
1937         }
1938         #[inline]
1939         fn index(self, slice: &str) -> &Self::Output {
1940             let end = self.end;
1941             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, 0, end))
1942         }
1943         #[inline]
1944         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1945             // is_char_boundary checks that the index is in [0, .len()]
1946             if slice.is_char_boundary(self.end) {
1947                 unsafe { self.get_unchecked_mut(slice) }
1948             } else {
1949                 super::slice_error_fail(slice, 0, self.end)
1950             }
1951         }
1952     }
1953
1954     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1955     impl SliceIndex<str> for ops::RangeFrom<usize> {
1956         type Output = str;
1957         #[inline]
1958         fn get(self, slice: &str) -> Option<&Self::Output> {
1959             if slice.is_char_boundary(self.start) {
1960                 Some(unsafe { self.get_unchecked(slice) })
1961             } else {
1962                 None
1963             }
1964         }
1965         #[inline]
1966         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1967             if slice.is_char_boundary(self.start) {
1968                 Some(unsafe { self.get_unchecked_mut(slice) })
1969             } else {
1970                 None
1971             }
1972         }
1973         #[inline]
1974         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1975             let ptr = slice.as_ptr().add(self.start);
1976             let len = slice.len() - self.start;
1977             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1978         }
1979         #[inline]
1980         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1981             let ptr = slice.as_ptr().add(self.start);
1982             let len = slice.len() - self.start;
1983             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1984         }
1985         #[inline]
1986         fn index(self, slice: &str) -> &Self::Output {
1987             let (start, end) = (self.start, slice.len());
1988             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1989         }
1990         #[inline]
1991         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1992             // is_char_boundary checks that the index is in [0, .len()]
1993             if slice.is_char_boundary(self.start) {
1994                 unsafe { self.get_unchecked_mut(slice) }
1995             } else {
1996                 super::slice_error_fail(slice, self.start, slice.len())
1997             }
1998         }
1999     }
2000
2001     #[stable(feature = "inclusive_range", since = "1.26.0")]
2002     impl SliceIndex<str> for ops::RangeInclusive<usize> {
2003         type Output = str;
2004         #[inline]
2005         fn get(self, slice: &str) -> Option<&Self::Output> {
2006             if *self.end() == usize::max_value() { None }
2007             else { (*self.start()..self.end()+1).get(slice) }
2008         }
2009         #[inline]
2010         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2011             if *self.end() == usize::max_value() { None }
2012             else { (*self.start()..self.end()+1).get_mut(slice) }
2013         }
2014         #[inline]
2015         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2016             (*self.start()..self.end()+1).get_unchecked(slice)
2017         }
2018         #[inline]
2019         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2020             (*self.start()..self.end()+1).get_unchecked_mut(slice)
2021         }
2022         #[inline]
2023         fn index(self, slice: &str) -> &Self::Output {
2024             if *self.end() == usize::max_value() { str_index_overflow_fail(); }
2025             (*self.start()..self.end()+1).index(slice)
2026         }
2027         #[inline]
2028         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2029             if *self.end() == usize::max_value() { str_index_overflow_fail(); }
2030             (*self.start()..self.end()+1).index_mut(slice)
2031         }
2032     }
2033
2034
2035
2036     #[stable(feature = "inclusive_range", since = "1.26.0")]
2037     impl SliceIndex<str> for ops::RangeToInclusive<usize> {
2038         type Output = str;
2039         #[inline]
2040         fn get(self, slice: &str) -> Option<&Self::Output> {
2041             if self.end == usize::max_value() { None }
2042             else { (..self.end+1).get(slice) }
2043         }
2044         #[inline]
2045         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2046             if self.end == usize::max_value() { None }
2047             else { (..self.end+1).get_mut(slice) }
2048         }
2049         #[inline]
2050         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2051             (..self.end+1).get_unchecked(slice)
2052         }
2053         #[inline]
2054         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2055             (..self.end+1).get_unchecked_mut(slice)
2056         }
2057         #[inline]
2058         fn index(self, slice: &str) -> &Self::Output {
2059             if self.end == usize::max_value() { str_index_overflow_fail(); }
2060             (..self.end+1).index(slice)
2061         }
2062         #[inline]
2063         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2064             if self.end == usize::max_value() { str_index_overflow_fail(); }
2065             (..self.end+1).index_mut(slice)
2066         }
2067     }
2068 }
2069
2070 // truncate `&str` to length at most equal to `max`
2071 // return `true` if it were truncated, and the new str.
2072 fn truncate_to_char_boundary(s: &str, mut max: usize) -> (bool, &str) {
2073     if max >= s.len() {
2074         (false, s)
2075     } else {
2076         while !s.is_char_boundary(max) {
2077             max -= 1;
2078         }
2079         (true, &s[..max])
2080     }
2081 }
2082
2083 #[inline(never)]
2084 #[cold]
2085 fn slice_error_fail(s: &str, begin: usize, end: usize) -> ! {
2086     const MAX_DISPLAY_LENGTH: usize = 256;
2087     let (truncated, s_trunc) = truncate_to_char_boundary(s, MAX_DISPLAY_LENGTH);
2088     let ellipsis = if truncated { "[...]" } else { "" };
2089
2090     // 1. out of bounds
2091     if begin > s.len() || end > s.len() {
2092         let oob_index = if begin > s.len() { begin } else { end };
2093         panic!("byte index {} is out of bounds of `{}`{}", oob_index, s_trunc, ellipsis);
2094     }
2095
2096     // 2. begin <= end
2097     assert!(begin <= end, "begin <= end ({} <= {}) when slicing `{}`{}",
2098             begin, end, s_trunc, ellipsis);
2099
2100     // 3. character boundary
2101     let index = if !s.is_char_boundary(begin) { begin } else { end };
2102     // find the character
2103     let mut char_start = index;
2104     while !s.is_char_boundary(char_start) {
2105         char_start -= 1;
2106     }
2107     // `char_start` must be less than len and a char boundary
2108     let ch = s[char_start..].chars().next().unwrap();
2109     let char_range = char_start .. char_start + ch.len_utf8();
2110     panic!("byte index {} is not a char boundary; it is inside {:?} (bytes {:?}) of `{}`{}",
2111            index, ch, char_range, s_trunc, ellipsis);
2112 }
2113
2114 #[lang = "str"]
2115 #[cfg(not(test))]
2116 impl str {
2117     /// Returns the length of `self`.
2118     ///
2119     /// This length is in bytes, not [`char`]s or graphemes. In other words,
2120     /// it may not be what a human considers the length of the string.
2121     ///
2122     /// # Examples
2123     ///
2124     /// Basic usage:
2125     ///
2126     /// ```
2127     /// let len = "foo".len();
2128     /// assert_eq!(3, len);
2129     ///
2130     /// let len = "ƒoo".len(); // fancy f!
2131     /// assert_eq!(4, len);
2132     /// ```
2133     #[stable(feature = "rust1", since = "1.0.0")]
2134     #[inline]
2135     #[rustc_const_unstable(feature = "const_str_len")]
2136     pub const fn len(&self) -> usize {
2137         self.as_bytes().len()
2138     }
2139
2140     /// Returns `true` if `self` has a length of zero bytes.
2141     ///
2142     /// # Examples
2143     ///
2144     /// Basic usage:
2145     ///
2146     /// ```
2147     /// let s = "";
2148     /// assert!(s.is_empty());
2149     ///
2150     /// let s = "not empty";
2151     /// assert!(!s.is_empty());
2152     /// ```
2153     #[inline]
2154     #[stable(feature = "rust1", since = "1.0.0")]
2155     #[rustc_const_unstable(feature = "const_str_len")]
2156     pub const fn is_empty(&self) -> bool {
2157         self.len() == 0
2158     }
2159
2160     /// Checks that `index`-th byte lies at the start and/or end of a
2161     /// UTF-8 code point sequence.
2162     ///
2163     /// The start and end of the string (when `index == self.len()`) are
2164     /// considered to be
2165     /// boundaries.
2166     ///
2167     /// Returns `false` if `index` is greater than `self.len()`.
2168     ///
2169     /// # Examples
2170     ///
2171     /// ```
2172     /// let s = "Löwe 老虎 Léopard";
2173     /// assert!(s.is_char_boundary(0));
2174     /// // start of `老`
2175     /// assert!(s.is_char_boundary(6));
2176     /// assert!(s.is_char_boundary(s.len()));
2177     ///
2178     /// // second byte of `ö`
2179     /// assert!(!s.is_char_boundary(2));
2180     ///
2181     /// // third byte of `老`
2182     /// assert!(!s.is_char_boundary(8));
2183     /// ```
2184     #[stable(feature = "is_char_boundary", since = "1.9.0")]
2185     #[inline]
2186     pub fn is_char_boundary(&self, index: usize) -> bool {
2187         // 0 and len are always ok.
2188         // Test for 0 explicitly so that it can optimize out the check
2189         // easily and skip reading string data for that case.
2190         if index == 0 || index == self.len() { return true; }
2191         match self.as_bytes().get(index) {
2192             None => false,
2193             // This is bit magic equivalent to: b < 128 || b >= 192
2194             Some(&b) => (b as i8) >= -0x40,
2195         }
2196     }
2197
2198     /// Converts a string slice to a byte slice. To convert the byte slice back
2199     /// into a string slice, use the [`str::from_utf8`] function.
2200     ///
2201     /// [`str::from_utf8`]: ./str/fn.from_utf8.html
2202     ///
2203     /// # Examples
2204     ///
2205     /// Basic usage:
2206     ///
2207     /// ```
2208     /// let bytes = "bors".as_bytes();
2209     /// assert_eq!(b"bors", bytes);
2210     /// ```
2211     #[stable(feature = "rust1", since = "1.0.0")]
2212     #[inline(always)]
2213     #[rustc_const_unstable(feature="const_str_as_bytes")]
2214     pub const fn as_bytes(&self) -> &[u8] {
2215         union Slices<'a> {
2216             str: &'a str,
2217             slice: &'a [u8],
2218         }
2219         unsafe { Slices { str: self }.slice }
2220     }
2221
2222     /// Converts a mutable string slice to a mutable byte slice. To convert the
2223     /// mutable byte slice back into a mutable string slice, use the
2224     /// [`str::from_utf8_mut`] function.
2225     ///
2226     /// [`str::from_utf8_mut`]: ./str/fn.from_utf8_mut.html
2227     ///
2228     /// # Examples
2229     ///
2230     /// Basic usage:
2231     ///
2232     /// ```
2233     /// let mut s = String::from("Hello");
2234     /// let bytes = unsafe { s.as_bytes_mut() };
2235     ///
2236     /// assert_eq!(b"Hello", bytes);
2237     /// ```
2238     ///
2239     /// Mutability:
2240     ///
2241     /// ```
2242     /// let mut s = String::from("🗻∈🌏");
2243     ///
2244     /// unsafe {
2245     ///     let bytes = s.as_bytes_mut();
2246     ///
2247     ///     bytes[0] = 0xF0;
2248     ///     bytes[1] = 0x9F;
2249     ///     bytes[2] = 0x8D;
2250     ///     bytes[3] = 0x94;
2251     /// }
2252     ///
2253     /// assert_eq!("🍔∈🌏", s);
2254     /// ```
2255     #[stable(feature = "str_mut_extras", since = "1.20.0")]
2256     #[inline(always)]
2257     pub unsafe fn as_bytes_mut(&mut self) -> &mut [u8] {
2258         &mut *(self as *mut str as *mut [u8])
2259     }
2260
2261     /// Converts a string slice to a raw pointer.
2262     ///
2263     /// As string slices are a slice of bytes, the raw pointer points to a
2264     /// [`u8`]. This pointer will be pointing to the first byte of the string
2265     /// slice.
2266     ///
2267     /// [`u8`]: primitive.u8.html
2268     ///
2269     /// # Examples
2270     ///
2271     /// Basic usage:
2272     ///
2273     /// ```
2274     /// let s = "Hello";
2275     /// let ptr = s.as_ptr();
2276     /// ```
2277     #[stable(feature = "rust1", since = "1.0.0")]
2278     #[inline]
2279     #[rustc_const_unstable(feature = "const_str_as_ptr")]
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<'_> {}