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