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