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