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