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