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