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