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