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