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