src/libcore/str/mod.rs

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