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