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