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