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