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