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