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