src/libcore/str.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 mem;
  20 use char;
  21 use char::Char;
  22 use cmp::{Eq, mod};
  23 use default::Default;
  24 use iter::{Map, Iterator};
  25 use iter::{DoubleEndedIterator, ExactSize};
  26 use iter::range;
  27 use kinds::Sized;
  28 use num::{CheckedMul, Saturating};
  29 use option::{Option, None, Some};
  30 use raw::Repr;
  31 use slice::{mod, SlicePrelude};
  32 use uint;
  33
  34 /*
  35 Section: Creating a string
  36 */
  37
  38 /// Converts a vector to a string slice without performing any allocations.
  39 ///
  40 /// Once the slice has been validated as utf-8, it is transmuted in-place and
  41 /// returned as a '&str' instead of a '&[u8]'
  42 ///
  43 /// Returns None if the slice is not utf-8.
  44 pub fn from_utf8<'a>(v: &'a [u8]) -> Option<&'a str> {
  45     if is_utf8(v) {
  46         Some(unsafe { raw::from_utf8(v) })
  47     } else { None }
  48 }
  49
  50 /// Something that can be used to compare against a character
  51 pub trait CharEq {
  52     /// Determine if the splitter should split at the given character
  53     fn matches(&mut self, char) -> bool;
  54     /// Indicate if this is only concerned about ASCII characters,
  55     /// which can allow for a faster implementation.
  56     fn only_ascii(&self) -> bool;
  57 }
  58
  59 impl CharEq for char {
  60     #[inline]
  61     fn matches(&mut self, c: char) -> bool { *self == c }
  62
  63     #[inline]
  64     fn only_ascii(&self) -> bool { (*self as uint) < 128 }
  65 }
  66
  67 impl<'a> CharEq for |char|: 'a -> bool {
  68     #[inline]
  69     fn matches(&mut self, c: char) -> bool { (*self)(c) }
  70
  71     #[inline]
  72     fn only_ascii(&self) -> bool { false }
  73 }
  74
  75 impl CharEq for extern "Rust" fn(char) -> bool {
  76     #[inline]
  77     fn matches(&mut self, c: char) -> bool { (*self)(c) }
  78
  79     #[inline]
  80     fn only_ascii(&self) -> bool { false }
  81 }
  82
  83 impl<'a> CharEq for &'a [char] {
  84     #[inline]
  85     fn matches(&mut self, c: char) -> bool {
  86         self.iter().any(|&mut m| m.matches(c))
  87     }
  88
  89     #[inline]
  90     fn only_ascii(&self) -> bool {
  91         self.iter().all(|m| m.only_ascii())
  92     }
  93 }
  94
  95 /*
  96 Section: Iterators
  97 */
  98
  99 /// Iterator for the char (representing *Unicode Scalar Values*) of a string
 100 ///
 101 /// Created with the method `.chars()`.
 102 #[deriving(Clone)]
 103 pub struct Chars<'a> {
 104     iter: slice::Items<'a, u8>
 105 }
 106
 107 // Return the initial codepoint accumulator for the first byte.
 108 // The first byte is special, only want bottom 5 bits for width 2, 4 bits
 109 // for width 3, and 3 bits for width 4
 110 macro_rules! utf8_first_byte(
 111     ($byte:expr, $width:expr) => (($byte & (0x7F >> $width)) as u32)
 112 )
 113
 114 // return the value of $ch updated with continuation byte $byte
 115 macro_rules! utf8_acc_cont_byte(
 116     ($ch:expr, $byte:expr) => (($ch << 6) | ($byte & CONT_MASK) as u32)
 117 )
 118
 119 macro_rules! utf8_is_cont_byte(
 120     ($byte:expr) => (($byte & !CONT_MASK) == TAG_CONT_U8)
 121 )
 122
 123 #[inline]
 124 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 125     match opt {
 126         Some(&byte) => byte,
 127         None => 0,
 128     }
 129 }
 130
 131 impl<'a> Iterator<char> for Chars<'a> {
 132     #[inline]
 133     fn next(&mut self) -> Option<char> {
 134         // Decode UTF-8, using the valid UTF-8 invariant
 135         let x = match self.iter.next() {
 136             None => return None,
 137             Some(&next_byte) if next_byte < 128 => return Some(next_byte as char),
 138             Some(&next_byte) => next_byte,
 139         };
 140
 141         // Multibyte case follows
 142         // Decode from a byte combination out of: [[[x y] z] w]
 143         // NOTE: Performance is sensitive to the exact formulation here
 144         let init = utf8_first_byte!(x, 2);
 145         let y = unwrap_or_0(self.iter.next());
 146         let mut ch = utf8_acc_cont_byte!(init, y);
 147         if x >= 0xE0 {
 148             // [[x y z] w] case
 149             // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 150             let z = unwrap_or_0(self.iter.next());
 151             let y_z = utf8_acc_cont_byte!((y & CONT_MASK) as u32, z);
 152             ch = init << 12 | y_z;
 153             if x >= 0xF0 {
 154                 // [x y z w] case
 155                 // use only the lower 3 bits of `init`
 156                 let w = unwrap_or_0(self.iter.next());
 157                 ch = (init & 7) << 18 | utf8_acc_cont_byte!(y_z, w);
 158             }
 159         }
 160
 161         // str invariant says `ch` is a valid Unicode Scalar Value
 162         unsafe {
 163             Some(mem::transmute(ch))
 164         }
 165     }
 166
 167     #[inline]
 168     fn size_hint(&self) -> (uint, Option<uint>) {
 169         let (len, _) = self.iter.size_hint();
 170         (len.saturating_add(3) / 4, Some(len))
 171     }
 172 }
 173
 174 impl<'a> DoubleEndedIterator<char> for Chars<'a> {
 175     #[inline]
 176     fn next_back(&mut self) -> Option<char> {
 177         let w = match self.iter.next_back() {
 178             None => return None,
 179             Some(&back_byte) if back_byte < 128 => return Some(back_byte as char),
 180             Some(&back_byte) => back_byte,
 181         };
 182
 183         // Multibyte case follows
 184         // Decode from a byte combination out of: [x [y [z w]]]
 185         let mut ch;
 186         let z = unwrap_or_0(self.iter.next_back());
 187         ch = utf8_first_byte!(z, 2);
 188         if utf8_is_cont_byte!(z) {
 189             let y = unwrap_or_0(self.iter.next_back());
 190             ch = utf8_first_byte!(y, 3);
 191             if utf8_is_cont_byte!(y) {
 192                 let x = unwrap_or_0(self.iter.next_back());
 193                 ch = utf8_first_byte!(x, 4);
 194                 ch = utf8_acc_cont_byte!(ch, y);
 195             }
 196             ch = utf8_acc_cont_byte!(ch, z);
 197         }
 198         ch = utf8_acc_cont_byte!(ch, w);
 199
 200         // str invariant says `ch` is a valid Unicode Scalar Value
 201         unsafe {
 202             Some(mem::transmute(ch))
 203         }
 204     }
 205 }
 206
 207 /// External iterator for a string's characters and their byte offsets.
 208 /// Use with the `std::iter` module.
 209 #[deriving(Clone)]
 210 pub struct CharOffsets<'a> {
 211     front_offset: uint,
 212     iter: Chars<'a>,
 213 }
 214
 215 impl<'a> Iterator<(uint, char)> for CharOffsets<'a> {
 216     #[inline]
 217     fn next(&mut self) -> Option<(uint, char)> {
 218         let (pre_len, _) = self.iter.iter.size_hint();
 219         match self.iter.next() {
 220             None => None,
 221             Some(ch) => {
 222                 let index = self.front_offset;
 223                 let (len, _) = self.iter.iter.size_hint();
 224                 self.front_offset += pre_len - len;
 225                 Some((index, ch))
 226             }
 227         }
 228     }
 229
 230     #[inline]
 231     fn size_hint(&self) -> (uint, Option<uint>) {
 232         self.iter.size_hint()
 233     }
 234 }
 235
 236 impl<'a> DoubleEndedIterator<(uint, char)> for CharOffsets<'a> {
 237     #[inline]
 238     fn next_back(&mut self) -> Option<(uint, char)> {
 239         match self.iter.next_back() {
 240             None => None,
 241             Some(ch) => {
 242                 let (len, _) = self.iter.iter.size_hint();
 243                 let index = self.front_offset + len;
 244                 Some((index, ch))
 245             }
 246         }
 247     }
 248 }
 249
 250 /// External iterator for a string's bytes.
 251 /// Use with the `std::iter` module.
 252 pub type Bytes<'a> =
 253     Map<'a, &'a u8, u8, slice::Items<'a, u8>>;
 254
 255 /// An iterator over the substrings of a string, separated by `sep`.
 256 #[deriving(Clone)]
 257 pub struct CharSplits<'a, Sep> {
 258     /// The slice remaining to be iterated
 259     string: &'a str,
 260     sep: Sep,
 261     /// Whether an empty string at the end is allowed
 262     allow_trailing_empty: bool,
 263     only_ascii: bool,
 264     finished: bool,
 265 }
 266
 267 /// An iterator over the substrings of a string, separated by `sep`,
 268 /// splitting at most `count` times.
 269 #[deriving(Clone)]
 270 pub struct CharSplitsN<'a, Sep> {
 271     iter: CharSplits<'a, Sep>,
 272     /// The number of splits remaining
 273     count: uint,
 274     invert: bool,
 275 }
 276
 277 /// An iterator over the lines of a string, separated by either `\n` or (`\r\n`).
 278 pub type AnyLines<'a> =
 279     Map<'a, &'a str, &'a str, CharSplits<'a, char>>;
 280
 281 impl<'a, Sep> CharSplits<'a, Sep> {
 282     #[inline]
 283     fn get_end(&mut self) -> Option<&'a str> {
 284         if !self.finished && (self.allow_trailing_empty || self.string.len() > 0) {
 285             self.finished = true;
 286             Some(self.string)
 287         } else {
 288             None
 289         }
 290     }
 291 }
 292
 293 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplits<'a, Sep> {
 294     #[inline]
 295     fn next(&mut self) -> Option<&'a str> {
 296         if self.finished { return None }
 297
 298         let mut next_split = None;
 299         if self.only_ascii {
 300             for (idx, byte) in self.string.bytes().enumerate() {
 301                 if self.sep.matches(byte as char) && byte < 128u8 {
 302                     next_split = Some((idx, idx + 1));
 303                     break;
 304                 }
 305             }
 306         } else {
 307             for (idx, ch) in self.string.char_indices() {
 308                 if self.sep.matches(ch) {
 309                     next_split = Some((idx, self.string.char_range_at(idx).next));
 310                     break;
 311                 }
 312             }
 313         }
 314         match next_split {
 315             Some((a, b)) => unsafe {
 316                 let elt = raw::slice_unchecked(self.string, 0, a);
 317                 self.string = raw::slice_unchecked(self.string, b, self.string.len());
 318                 Some(elt)
 319             },
 320             None => self.get_end(),
 321         }
 322     }
 323 }
 324
 325 impl<'a, Sep: CharEq> DoubleEndedIterator<&'a str>
 326 for CharSplits<'a, Sep> {
 327     #[inline]
 328     fn next_back(&mut self) -> Option<&'a str> {
 329         if self.finished { return None }
 330
 331         if !self.allow_trailing_empty {
 332             self.allow_trailing_empty = true;
 333             match self.next_back() {
 334                 Some(elt) if !elt.is_empty() => return Some(elt),
 335                 _ => if self.finished { return None }
 336             }
 337         }
 338         let len = self.string.len();
 339         let mut next_split = None;
 340
 341         if self.only_ascii {
 342             for (idx, byte) in self.string.bytes().enumerate().rev() {
 343                 if self.sep.matches(byte as char) && byte < 128u8 {
 344                     next_split = Some((idx, idx + 1));
 345                     break;
 346                 }
 347             }
 348         } else {
 349             for (idx, ch) in self.string.char_indices().rev() {
 350                 if self.sep.matches(ch) {
 351                     next_split = Some((idx, self.string.char_range_at(idx).next));
 352                     break;
 353                 }
 354             }
 355         }
 356         match next_split {
 357             Some((a, b)) => unsafe {
 358                 let elt = raw::slice_unchecked(self.string, b, len);
 359                 self.string = raw::slice_unchecked(self.string, 0, a);
 360                 Some(elt)
 361             },
 362             None => { self.finished = true; Some(self.string) }
 363         }
 364     }
 365 }
 366
 367 impl<'a, Sep: CharEq> Iterator<&'a str> for CharSplitsN<'a, Sep> {
 368     #[inline]
 369     fn next(&mut self) -> Option<&'a str> {
 370         if self.count != 0 {
 371             self.count -= 1;
 372             if self.invert { self.iter.next_back() } else { self.iter.next() }
 373         } else {
 374             self.iter.get_end()
 375         }
 376     }
 377 }
 378
 379 /// The internal state of an iterator that searches for matches of a substring
 380 /// within a larger string using naive search
 381 #[deriving(Clone)]
 382 struct NaiveSearcher {
 383     position: uint
 384 }
 385
 386 impl NaiveSearcher {
 387     fn new() -> NaiveSearcher {
 388         NaiveSearcher { position: 0 }
 389     }
 390
 391     fn next(&mut self, haystack: &[u8], needle: &[u8]) -> Option<(uint, uint)> {
 392         while self.position + needle.len() <= haystack.len() {
 393             if haystack[self.position .. self.position + needle.len()] == needle {
 394                 let match_pos = self.position;
 395                 self.position += needle.len(); // add 1 for all matches
 396                 return Some((match_pos, match_pos + needle.len()));
 397             } else {
 398                 self.position += 1;
 399             }
 400         }
 401         None
 402     }
 403 }
 404
 405 /// The internal state of an iterator that searches for matches of a substring
 406 /// within a larger string using two-way search
 407 #[deriving(Clone)]
 408 struct TwoWaySearcher {
 409     // constants
 410     crit_pos: uint,
 411     period: uint,
 412     byteset: u64,
 413
 414     // variables
 415     position: uint,
 416     memory: uint
 417 }
 418
 419 /*
 420     This is the Two-Way search algorithm, which was introduced in the paper:
 421     Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
 422
 423     Here's some background information.
 424
 425     A *word* is a string of symbols. The *length* of a word should be a familiar
 426     notion, and here we denote it for any word x by |x|.
 427     (We also allow for the possibility of the *empty word*, a word of length zero).
 428
 429     If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
 430     *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
 431     For example, both 1 and 2 are periods for the string "aa". As another example,
 432     the only period of the string "abcd" is 4.
 433
 434     We denote by period(x) the *smallest* period of x (provided that x is non-empty).
 435     This is always well-defined since every non-empty word x has at least one period,
 436     |x|. We sometimes call this *the period* of x.
 437
 438     If u, v and x are words such that x = uv, where uv is the concatenation of u and
 439     v, then we say that (u, v) is a *factorization* of x.
 440
 441     Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
 442     that both of the following hold
 443
 444       - either w is a suffix of u or u is a suffix of w
 445       - either w is a prefix of v or v is a prefix of w
 446
 447     then w is said to be a *repetition* for the factorization (u, v).
 448
 449     Just to unpack this, there are four possibilities here. Let w = "abc". Then we
 450     might have:
 451
 452       - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
 453       - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
 454       - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
 455       - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
 456
 457     Note that the word vu is a repetition for any factorization (u,v) of x = uv,
 458     so every factorization has at least one repetition.
 459
 460     If x is a string and (u, v) is a factorization for x, then a *local period* for
 461     (u, v) is an integer r such that there is some word w such that |w| = r and w is
 462     a repetition for (u, v).
 463
 464     We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
 465     call this *the local period* of (u, v). Provided that x = uv is non-empty, this
 466     is well-defined (because each non-empty word has at least one factorization, as
 467     noted above).
 468
 469     It can be proven that the following is an equivalent definition of a local period
 470     for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
 471     all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
 472     defined. (i.e. i > 0 and i + r < |x|).
 473
 474     Using the above reformulation, it is easy to prove that
 475
 476         1 <= local_period(u, v) <= period(uv)
 477
 478     A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
 479     *critical factorization*.
 480
 481     The algorithm hinges on the following theorem, which is stated without proof:
 482
 483     **Critical Factorization Theorem** Any word x has at least one critical
 484     factorization (u, v) such that |u| < period(x).
 485
 486     The purpose of maximal_suffix is to find such a critical factorization.
 487
 488 */
 489 impl TwoWaySearcher {
 490     fn new(needle: &[u8]) -> TwoWaySearcher {
 491         let (crit_pos1, period1) = TwoWaySearcher::maximal_suffix(needle, false);
 492         let (crit_pos2, period2) = TwoWaySearcher::maximal_suffix(needle, true);
 493
 494         let crit_pos;
 495         let period;
 496         if crit_pos1 > crit_pos2 {
 497             crit_pos = crit_pos1;
 498             period = period1;
 499         } else {
 500             crit_pos = crit_pos2;
 501             period = period2;
 502         }
 503
 504         // This isn't in the original algorithm, as far as I'm aware.
 505         let byteset = needle.iter()
 506                             .fold(0, |a, &b| (1 << ((b & 0x3f) as uint)) | a);
 507
 508         // A particularly readable explanation of what's going on here can be found
 509         // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
 510         // see the code for "Algorithm CP" on p. 323.
 511         //
 512         // What's going on is we have some critical factorization (u, v) of the
 513         // needle, and we want to determine whether u is a suffix of
 514         // v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
 515         // "Algorithm CP2", which is optimized for when the period of the needle
 516         // is large.
 517         if needle[..crit_pos] == needle[period.. period + crit_pos] {
 518             TwoWaySearcher {
 519                 crit_pos: crit_pos,
 520                 period: period,
 521                 byteset: byteset,
 522
 523                 position: 0,
 524                 memory: 0
 525             }
 526         } else {
 527             TwoWaySearcher {
 528                 crit_pos: crit_pos,
 529                 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
 530                 byteset: byteset,
 531
 532                 position: 0,
 533                 memory: uint::MAX // Dummy value to signify that the period is long
 534             }
 535         }
 536     }
 537
 538     // One of the main ideas of Two-Way is that we factorize the needle into
 539     // two halves, (u, v), and begin trying to find v in the haystack by scanning
 540     // left to right. If v matches, we try to match u by scanning right to left.
 541     // How far we can jump when we encounter a mismatch is all based on the fact
 542     // that (u, v) is a critical factorization for the needle.
 543     #[inline]
 544     fn next(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> Option<(uint, uint)> {
 545         'search: loop {
 546             // Check that we have room to search in
 547             if self.position + needle.len() > haystack.len() {
 548                 return None;
 549             }
 550
 551             // Quickly skip by large portions unrelated to our substring
 552             if (self.byteset >>
 553                     ((haystack[self.position + needle.len() - 1] & 0x3f)
 554                      as uint)) & 1 == 0 {
 555                 self.position += needle.len();
 556                 if !long_period {
 557                     self.memory = 0;
 558                 }
 559                 continue 'search;
 560             }
 561
 562             // See if the right part of the needle matches
 563             let start = if long_period { self.crit_pos }
 564                         else { cmp::max(self.crit_pos, self.memory) };
 565             for i in range(start, needle.len()) {
 566                 if needle[i] != haystack[self.position + i] {
 567                     self.position += i - self.crit_pos + 1;
 568                     if !long_period {
 569                         self.memory = 0;
 570                     }
 571                     continue 'search;
 572                 }
 573             }
 574
 575             // See if the left part of the needle matches
 576             let start = if long_period { 0 } else { self.memory };
 577             for i in range(start, self.crit_pos).rev() {
 578                 if needle[i] != haystack[self.position + i] {
 579                     self.position += self.period;
 580                     if !long_period {
 581                         self.memory = needle.len() - self.period;
 582                     }
 583                     continue 'search;
 584                 }
 585             }
 586
 587             // We have found a match!
 588             let match_pos = self.position;
 589             self.position += needle.len(); // add self.period for all matches
 590             if !long_period {
 591                 self.memory = 0; // set to needle.len() - self.period for all matches
 592             }
 593             return Some((match_pos, match_pos + needle.len()));
 594         }
 595     }
 596
 597     // Computes a critical factorization (u, v) of `arr`.
 598     // Specifically, returns (i, p), where i is the starting index of v in some
 599     // critical factorization (u, v) and p = period(v)
 600     #[inline]
 601     fn maximal_suffix(arr: &[u8], reversed: bool) -> (uint, uint) {
 602         let mut left = -1; // Corresponds to i in the paper
 603         let mut right = 0; // Corresponds to j in the paper
 604         let mut offset = 1; // Corresponds to k in the paper
 605         let mut period = 1; // Corresponds to p in the paper
 606
 607         while right + offset < arr.len() {
 608             let a;
 609             let b;
 610             if reversed {
 611                 a = arr[left + offset];
 612                 b = arr[right + offset];
 613             } else {
 614                 a = arr[right + offset];
 615                 b = arr[left + offset];
 616             }
 617             if a < b {
 618                 // Suffix is smaller, period is entire prefix so far.
 619                 right += offset;
 620                 offset = 1;
 621                 period = right - left;
 622             } else if a == b {
 623                 // Advance through repetition of the current period.
 624                 if offset == period {
 625                     right += offset;
 626                     offset = 1;
 627                 } else {
 628                     offset += 1;
 629                 }
 630             } else {
 631                 // Suffix is larger, start over from current location.
 632                 left = right;
 633                 right += 1;
 634                 offset = 1;
 635                 period = 1;
 636             }
 637         }
 638         (left + 1, period)
 639     }
 640 }
 641
 642 /// The internal state of an iterator that searches for matches of a substring
 643 /// within a larger string using a dynamically chosen search algorithm
 644 #[deriving(Clone)]
 645 enum Searcher {
 646     Naive(NaiveSearcher),
 647     TwoWay(TwoWaySearcher),
 648     TwoWayLong(TwoWaySearcher)
 649 }
 650
 651 impl Searcher {
 652     fn new(haystack: &[u8], needle: &[u8]) -> Searcher {
 653         // FIXME: Tune this.
 654         // FIXME(#16715): This unsigned integer addition will probably not
 655         // overflow because that would mean that the memory almost solely
 656         // consists of the needle. Needs #16715 to be formally fixed.
 657         if needle.len() + 20 > haystack.len() {
 658             Naive(NaiveSearcher::new())
 659         } else {
 660             let searcher = TwoWaySearcher::new(needle);
 661             if searcher.memory == uint::MAX { // If the period is long
 662                 TwoWayLong(searcher)
 663             } else {
 664                 TwoWay(searcher)
 665             }
 666         }
 667     }
 668 }
 669
 670 /// An iterator over the start and end indices of the matches of a
 671 /// substring within a larger string
 672 #[deriving(Clone)]
 673 pub struct MatchIndices<'a> {
 674     // constants
 675     haystack: &'a str,
 676     needle: &'a str,
 677     searcher: Searcher
 678 }
 679
 680 /// An iterator over the substrings of a string separated by a given
 681 /// search string
 682 #[deriving(Clone)]
 683 pub struct StrSplits<'a> {
 684     it: MatchIndices<'a>,
 685     last_end: uint,
 686     finished: bool
 687 }
 688
 689 impl<'a> Iterator<(uint, uint)> for MatchIndices<'a> {
 690     #[inline]
 691     fn next(&mut self) -> Option<(uint, uint)> {
 692         match self.searcher {
 693             Naive(ref mut searcher)
 694                 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes()),
 695             TwoWay(ref mut searcher)
 696                 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), false),
 697             TwoWayLong(ref mut searcher)
 698                 => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), true)
 699         }
 700     }
 701 }
 702
 703 impl<'a> Iterator<&'a str> for StrSplits<'a> {
 704     #[inline]
 705     fn next(&mut self) -> Option<&'a str> {
 706         if self.finished { return None; }
 707
 708         match self.it.next() {
 709             Some((from, to)) => {
 710                 let ret = Some(self.it.haystack.slice(self.last_end, from));
 711                 self.last_end = to;
 712                 ret
 713             }
 714             None => {
 715                 self.finished = true;
 716                 Some(self.it.haystack.slice(self.last_end, self.it.haystack.len()))
 717             }
 718         }
 719     }
 720 }
 721
 722 /// External iterator for a string's UTF16 codeunits.
 723 /// Use with the `std::iter` module.
 724 #[deriving(Clone)]
 725 pub struct Utf16CodeUnits<'a> {
 726     chars: Chars<'a>,
 727     extra: u16
 728 }
 729
 730 impl<'a> Iterator<u16> for Utf16CodeUnits<'a> {
 731     #[inline]
 732     fn next(&mut self) -> Option<u16> {
 733         if self.extra != 0 {
 734             let tmp = self.extra;
 735             self.extra = 0;
 736             return Some(tmp);
 737         }
 738
 739         let mut buf = [0u16, ..2];
 740         self.chars.next().map(|ch| {
 741             let n = ch.encode_utf16(buf[mut]).unwrap_or(0);
 742             if n == 2 { self.extra = buf[1]; }
 743             buf[0]
 744         })
 745     }
 746
 747     #[inline]
 748     fn size_hint(&self) -> (uint, Option<uint>) {
 749         let (low, high) = self.chars.size_hint();
 750         // every char gets either one u16 or two u16,
 751         // so this iterator is between 1 or 2 times as
 752         // long as the underlying iterator.
 753         (low, high.and_then(|n| n.checked_mul(&2)))
 754     }
 755 }
 756
 757 /*
 758 Section: Comparing strings
 759 */
 760
 761 // share the implementation of the lang-item vs. non-lang-item
 762 // eq_slice.
 763 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
 764 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
 765 #[inline]
 766 fn eq_slice_(a: &str, b: &str) -> bool {
 767     #[allow(improper_ctypes)]
 768     extern { fn memcmp(s1: *const i8, s2: *const i8, n: uint) -> i32; }
 769     a.len() == b.len() && unsafe {
 770         memcmp(a.as_ptr() as *const i8,
 771                b.as_ptr() as *const i8,
 772                a.len()) == 0
 773     }
 774 }
 775
 776 /// Bytewise slice equality
 777 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
 778 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
 779 #[lang="str_eq"]
 780 #[inline]
 781 pub fn eq_slice(a: &str, b: &str) -> bool {
 782     eq_slice_(a, b)
 783 }
 784
 785 /*
 786 Section: Misc
 787 */
 788
 789 /// Walk through `iter` checking that it's a valid UTF-8 sequence,
 790 /// returning `true` in that case, or, if it is invalid, `false` with
 791 /// `iter` reset such that it is pointing at the first byte in the
 792 /// invalid sequence.
 793 #[inline(always)]
 794 fn run_utf8_validation_iterator(iter: &mut slice::Items<u8>) -> bool {
 795     loop {
 796         // save the current thing we're pointing at.
 797         let old = *iter;
 798
 799         // restore the iterator we had at the start of this codepoint.
 800         macro_rules! err ( () => { {*iter = old; return false} });
 801         macro_rules! next ( () => {
 802                 match iter.next() {
 803                     Some(a) => *a,
 804                     // we needed data, but there was none: error!
 805                     None => err!()
 806                 }
 807             });
 808
 809         let first = match iter.next() {
 810             Some(&b) => b,
 811             // we're at the end of the iterator and a codepoint
 812             // boundary at the same time, so this string is valid.
 813             None => return true
 814         };
 815
 816         // ASCII characters are always valid, so only large
 817         // bytes need more examination.
 818         if first >= 128 {
 819             let w = utf8_char_width(first);
 820             let second = next!();
 821             // 2-byte encoding is for codepoints  \u0080 to  \u07ff
 822             //        first  C2 80        last DF BF
 823             // 3-byte encoding is for codepoints  \u0800 to  \uffff
 824             //        first  E0 A0 80     last EF BF BF
 825             //   excluding surrogates codepoints  \ud800 to  \udfff
 826             //               ED A0 80 to       ED BF BF
 827             // 4-byte encoding is for codepoints \u10000 to \u10ffff
 828             //        first  F0 90 80 80  last F4 8F BF BF
 829             //
 830             // Use the UTF-8 syntax from the RFC
 831             //
 832             // https://tools.ietf.org/html/rfc3629
 833             // UTF8-1      = %x00-7F
 834             // UTF8-2      = %xC2-DF UTF8-tail
 835             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
 836             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
 837             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
 838             //               %xF4 %x80-8F 2( UTF8-tail )
 839             match w {
 840                 2 => if second & !CONT_MASK != TAG_CONT_U8 {err!()},
 841                 3 => {
 842                     match (first, second, next!() & !CONT_MASK) {
 843                         (0xE0         , 0xA0 ... 0xBF, TAG_CONT_U8) |
 844                         (0xE1 ... 0xEC, 0x80 ... 0xBF, TAG_CONT_U8) |
 845                         (0xED         , 0x80 ... 0x9F, TAG_CONT_U8) |
 846                         (0xEE ... 0xEF, 0x80 ... 0xBF, TAG_CONT_U8) => {}
 847                         _ => err!()
 848                     }
 849                 }
 850                 4 => {
 851                     match (first, second, next!() & !CONT_MASK, next!() & !CONT_MASK) {
 852                         (0xF0         , 0x90 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
 853                         (0xF1 ... 0xF3, 0x80 ... 0xBF, TAG_CONT_U8, TAG_CONT_U8) |
 854                         (0xF4         , 0x80 ... 0x8F, TAG_CONT_U8, TAG_CONT_U8) => {}
 855                         _ => err!()
 856                     }
 857                 }
 858                 _ => err!()
 859             }
 860         }
 861     }
 862 }
 863
 864 /// Determines if a vector of bytes contains valid UTF-8.
 865 pub fn is_utf8(v: &[u8]) -> bool {
 866     run_utf8_validation_iterator(&mut v.iter())
 867 }
 868
 869 /// Determines if a vector of `u16` contains valid UTF-16
 870 pub fn is_utf16(v: &[u16]) -> bool {
 871     let mut it = v.iter();
 872     macro_rules! next ( ($ret:expr) => {
 873             match it.next() { Some(u) => *u, None => return $ret }
 874         }
 875     )
 876     loop {
 877         let u = next!(true);
 878
 879         match char::from_u32(u as u32) {
 880             Some(_) => {}
 881             None => {
 882                 let u2 = next!(false);
 883                 if u < 0xD7FF || u > 0xDBFF ||
 884                     u2 < 0xDC00 || u2 > 0xDFFF { return false; }
 885             }
 886         }
 887     }
 888 }
 889
 890 /// An iterator that decodes UTF-16 encoded codepoints from a vector
 891 /// of `u16`s.
 892 #[deriving(Clone)]
 893 pub struct Utf16Items<'a> {
 894     iter: slice::Items<'a, u16>
 895 }
 896 /// The possibilities for values decoded from a `u16` stream.
 897 #[deriving(PartialEq, Eq, Clone, Show)]
 898 pub enum Utf16Item {
 899     /// A valid codepoint.
 900     ScalarValue(char),
 901     /// An invalid surrogate without its pair.
 902     LoneSurrogate(u16)
 903 }
 904
 905 impl Utf16Item {
 906     /// Convert `self` to a `char`, taking `LoneSurrogate`s to the
 907     /// replacement character (U+FFFD).
 908     #[inline]
 909     pub fn to_char_lossy(&self) -> char {
 910         match *self {
 911             ScalarValue(c) => c,
 912             LoneSurrogate(_) => '\uFFFD'
 913         }
 914     }
 915 }
 916
 917 impl<'a> Iterator<Utf16Item> for Utf16Items<'a> {
 918     fn next(&mut self) -> Option<Utf16Item> {
 919         let u = match self.iter.next() {
 920             Some(u) => *u,
 921             None => return None
 922         };
 923
 924         if u < 0xD800 || 0xDFFF < u {
 925             // not a surrogate
 926             Some(ScalarValue(unsafe {mem::transmute(u as u32)}))
 927         } else if u >= 0xDC00 {
 928             // a trailing surrogate
 929             Some(LoneSurrogate(u))
 930         } else {
 931             // preserve state for rewinding.
 932             let old = self.iter;
 933
 934             let u2 = match self.iter.next() {
 935                 Some(u2) => *u2,
 936                 // eof
 937                 None => return Some(LoneSurrogate(u))
 938             };
 939             if u2 < 0xDC00 || u2 > 0xDFFF {
 940                 // not a trailing surrogate so we're not a valid
 941                 // surrogate pair, so rewind to redecode u2 next time.
 942                 self.iter = old;
 943                 return Some(LoneSurrogate(u))
 944             }
 945
 946             // all ok, so lets decode it.
 947             let c = ((u - 0xD800) as u32 << 10 | (u2 - 0xDC00) as u32) + 0x1_0000;
 948             Some(ScalarValue(unsafe {mem::transmute(c)}))
 949         }
 950     }
 951
 952     #[inline]
 953     fn size_hint(&self) -> (uint, Option<uint>) {
 954         let (low, high) = self.iter.size_hint();
 955         // we could be entirely valid surrogates (2 elements per
 956         // char), or entirely non-surrogates (1 element per char)
 957         (low / 2, high)
 958     }
 959 }
 960
 961 /// Create an iterator over the UTF-16 encoded codepoints in `v`,
 962 /// returning invalid surrogates as `LoneSurrogate`s.
 963 ///
 964 /// # Example
 965 ///
 966 /// ```rust
 967 /// use std::str;
 968 /// use std::str::{ScalarValue, LoneSurrogate};
 969 ///
 970 /// // 𝄞mus<invalid>ic<invalid>
 971 /// let v = [0xD834, 0xDD1E, 0x006d, 0x0075,
 972 ///          0x0073, 0xDD1E, 0x0069, 0x0063,
 973 ///          0xD834];
 974 ///
 975 /// assert_eq!(str::utf16_items(v).collect::<Vec<_>>(),
 976 ///            vec![ScalarValue('𝄞'),
 977 ///                 ScalarValue('m'), ScalarValue('u'), ScalarValue('s'),
 978 ///                 LoneSurrogate(0xDD1E),
 979 ///                 ScalarValue('i'), ScalarValue('c'),
 980 ///                 LoneSurrogate(0xD834)]);
 981 /// ```
 982 pub fn utf16_items<'a>(v: &'a [u16]) -> Utf16Items<'a> {
 983     Utf16Items { iter : v.iter() }
 984 }
 985
 986 /// Return a slice of `v` ending at (and not including) the first NUL
 987 /// (0).
 988 ///
 989 /// # Example
 990 ///
 991 /// ```rust
 992 /// use std::str;
 993 ///
 994 /// // "abcd"
 995 /// let mut v = ['a' as u16, 'b' as u16, 'c' as u16, 'd' as u16];
 996 /// // no NULs so no change
 997 /// assert_eq!(str::truncate_utf16_at_nul(v), v.as_slice());
 998 ///
 999 /// // "ab\0d"
1000 /// v[2] = 0;
1001 /// let b: &[_] = &['a' as u16, 'b' as u16];
1002 /// assert_eq!(str::truncate_utf16_at_nul(v), b);
1003 /// ```
1004 pub fn truncate_utf16_at_nul<'a>(v: &'a [u16]) -> &'a [u16] {
1005     match v.iter().position(|c| *c == 0) {
1006         // don't include the 0
1007         Some(i) => v[..i],
1008         None => v
1009     }
1010 }
1011
1012 // https://tools.ietf.org/html/rfc3629
1013 static UTF8_CHAR_WIDTH: [u8, ..256] = [
1014 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1015 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1016 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1017 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1018 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1019 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1020 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1021 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1022 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1023 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1024 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1025 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1026 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1027 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1028 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1029 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1030 ];
1031
1032 /// Given a first byte, determine how many bytes are in this UTF-8 character
1033 #[inline]
1034 pub fn utf8_char_width(b: u8) -> uint {
1035     return UTF8_CHAR_WIDTH[b as uint] as uint;
1036 }
1037
1038 /// Struct that contains a `char` and the index of the first byte of
1039 /// the next `char` in a string.  This can be used as a data structure
1040 /// for iterating over the UTF-8 bytes of a string.
1041 pub struct CharRange {
1042     /// Current `char`
1043     pub ch: char,
1044     /// Index of the first byte of the next `char`
1045     pub next: uint,
1046 }
1047
1048 /// Mask of the value bits of a continuation byte
1049 const CONT_MASK: u8 = 0b0011_1111u8;
1050 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte
1051 const TAG_CONT_U8: u8 = 0b1000_0000u8;
1052
1053 /// Unsafe operations
1054 pub mod raw {
1055     use mem;
1056     use ptr::RawPtr;
1057     use raw::Slice;
1058     use slice::SlicePrelude;
1059     use str::{is_utf8, StrPrelude};
1060
1061     /// Converts a slice of bytes to a string slice without checking
1062     /// that the string contains valid UTF-8.
1063     pub unsafe fn from_utf8<'a>(v: &'a [u8]) -> &'a str {
1064         mem::transmute(v)
1065     }
1066
1067     /// Form a slice from a C string. Unsafe because the caller must ensure the
1068     /// C string has the static lifetime, or else the return value may be
1069     /// invalidated later.
1070     pub unsafe fn c_str_to_static_slice(s: *const i8) -> &'static str {
1071         let s = s as *const u8;
1072         let mut curr = s;
1073         let mut len = 0u;
1074         while *curr != 0u8 {
1075             len += 1u;
1076             curr = s.offset(len as int);
1077         }
1078         let v = Slice { data: s, len: len };
1079         assert!(is_utf8(::mem::transmute(v)));
1080         ::mem::transmute(v)
1081     }
1082
1083     /// Takes a bytewise (not UTF-8) slice from a string.
1084     ///
1085     /// Returns the substring from [`begin`..`end`).
1086     ///
1087     /// # Panics
1088     ///
1089     /// If begin is greater than end.
1090     /// If end is greater than the length of the string.
1091     #[inline]
1092     pub unsafe fn slice_bytes<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1093         assert!(begin <= end);
1094         assert!(end <= s.len());
1095         slice_unchecked(s, begin, end)
1096     }
1097
1098     /// Takes a bytewise (not UTF-8) slice from a string.
1099     ///
1100     /// Returns the substring from [`begin`..`end`).
1101     ///
1102     /// Caller must check slice boundaries!
1103     #[inline]
1104     pub unsafe fn slice_unchecked<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
1105         mem::transmute(Slice {
1106                 data: s.as_ptr().offset(begin as int),
1107                 len: end - begin,
1108             })
1109     }
1110 }
1111
1112 /*
1113 Section: Trait implementations
1114 */
1115
1116 #[allow(missing_docs)]
1117 pub mod traits {
1118     use cmp::{Ord, Ordering, Less, Equal, Greater, PartialEq, PartialOrd, Equiv, Eq};
1119     use iter::Iterator;
1120     use option::{Option, Some};
1121     use ops;
1122     use str::{Str, StrPrelude, eq_slice};
1123
1124     // NOTE(stage0): remove impl after a snapshot
1125     #[cfg(stage0)]
1126     impl<'a> Ord for &'a str {
1127         #[inline]
1128         fn cmp(&self, other: & &'a str) -> Ordering {
1129             for (s_b, o_b) in self.bytes().zip(other.bytes()) {
1130                 match s_b.cmp(&o_b) {
1131                     Greater => return Greater,
1132                     Less => return Less,
1133                     Equal => ()
1134                 }
1135             }
1136
1137             self.len().cmp(&other.len())
1138         }
1139     }
1140
1141     #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1142     impl Ord for str {
1143         #[inline]
1144         fn cmp(&self, other: &str) -> Ordering {
1145             for (s_b, o_b) in self.bytes().zip(other.bytes()) {
1146                 match s_b.cmp(&o_b) {
1147                     Greater => return Greater,
1148                     Less => return Less,
1149                     Equal => ()
1150                 }
1151             }
1152
1153             self.len().cmp(&other.len())
1154         }
1155     }
1156
1157     // NOTE(stage0): remove impl after a snapshot
1158     #[cfg(stage0)]
1159     impl<'a> PartialEq for &'a str {
1160         #[inline]
1161         fn eq(&self, other: & &'a str) -> bool {
1162             eq_slice((*self), (*other))
1163         }
1164         #[inline]
1165         fn ne(&self, other: & &'a str) -> bool { !(*self).eq(other) }
1166     }
1167
1168     #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1169     impl PartialEq for str {
1170         #[inline]
1171         fn eq(&self, other: &str) -> bool {
1172             eq_slice(self, other)
1173         }
1174         #[inline]
1175         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1176     }
1177
1178     // NOTE(stage0): remove impl after a snapshot
1179     #[cfg(stage0)]
1180     impl<'a> Eq for &'a str {}
1181
1182     #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1183     impl Eq for str {}
1184
1185     // NOTE(stage0): remove impl after a snapshot
1186     #[cfg(stage0)]
1187     impl<'a> PartialOrd for &'a str {
1188         #[inline]
1189         fn partial_cmp(&self, other: &&'a str) -> Option<Ordering> {
1190             Some(self.cmp(other))
1191         }
1192     }
1193
1194     #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1195     impl PartialOrd for str {
1196         #[inline]
1197         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1198             Some(self.cmp(other))
1199         }
1200     }
1201
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 pub trait Str {
1232     /// Work with `self` as a slice.
1233     fn as_slice<'a>(&'a self) -> &'a str;
1234 }
1235
1236 impl<'a> Str for &'a str {
1237     #[inline]
1238     fn as_slice<'a>(&'a self) -> &'a str { *self }
1239 }
1240
1241 /// Methods for string slices
1242 pub trait StrPrelude for Sized? {
1243     /// Returns true if one string contains another
1244     ///
1245     /// # Arguments
1246     ///
1247     /// - needle - The string to look for
1248     ///
1249     /// # Example
1250     ///
1251     /// ```rust
1252     /// assert!("bananas".contains("nana"));
1253     /// ```
1254     fn contains(&self, needle: &str) -> bool;
1255
1256     /// Returns true if a string contains a char.
1257     ///
1258     /// # Arguments
1259     ///
1260     /// - needle - The char to look for
1261     ///
1262     /// # Example
1263     ///
1264     /// ```rust
1265     /// assert!("hello".contains_char('e'));
1266     /// ```
1267     fn contains_char(&self, needle: char) -> bool;
1268
1269     /// An iterator over the characters of `self`. Note, this iterates
1270     /// over Unicode code-points, not Unicode graphemes.
1271     ///
1272     /// # Example
1273     ///
1274     /// ```rust
1275     /// let v: Vec<char> = "abc åäö".chars().collect();
1276     /// assert_eq!(v, vec!['a', 'b', 'c', ' ', 'å', 'ä', 'ö']);
1277     /// ```
1278     fn chars<'a>(&'a self) -> Chars<'a>;
1279
1280     /// An iterator over the bytes of `self`
1281     ///
1282     /// # Example
1283     ///
1284     /// ```rust
1285     /// let v: Vec<u8> = "bors".bytes().collect();
1286     /// assert_eq!(v, b"bors".to_vec());
1287     /// ```
1288     fn bytes<'a>(&'a self) -> Bytes<'a>;
1289
1290     /// An iterator over the characters of `self` and their byte offsets.
1291     fn char_indices<'a>(&'a self) -> CharOffsets<'a>;
1292
1293     /// An iterator over substrings of `self`, separated by characters
1294     /// matched by `sep`.
1295     ///
1296     /// # Example
1297     ///
1298     /// ```rust
1299     /// let v: Vec<&str> = "Mary had a little lamb".split(' ').collect();
1300     /// assert_eq!(v, vec!["Mary", "had", "a", "little", "lamb"]);
1301     ///
1302     /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_digit()).collect();
1303     /// assert_eq!(v, vec!["abc", "def", "ghi"]);
1304     ///
1305     /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').collect();
1306     /// assert_eq!(v, vec!["lion", "", "tiger", "leopard"]);
1307     ///
1308     /// let v: Vec<&str> = "".split('X').collect();
1309     /// assert_eq!(v, vec![""]);
1310     /// ```
1311     fn split<'a, Sep: CharEq>(&'a self, sep: Sep) -> CharSplits<'a, Sep>;
1312
1313     /// An iterator over substrings of `self`, separated by characters
1314     /// matched by `sep`, restricted to splitting at most `count`
1315     /// times.
1316     ///
1317     /// # Example
1318     ///
1319     /// ```rust
1320     /// let v: Vec<&str> = "Mary had a little lambda".splitn(2, ' ').collect();
1321     /// assert_eq!(v, vec!["Mary", "had", "a little lambda"]);
1322     ///
1323     /// let v: Vec<&str> = "abc1def2ghi".splitn(1, |c: char| c.is_digit()).collect();
1324     /// assert_eq!(v, vec!["abc", "def2ghi"]);
1325     ///
1326     /// let v: Vec<&str> = "lionXXtigerXleopard".splitn(2, 'X').collect();
1327     /// assert_eq!(v, vec!["lion", "", "tigerXleopard"]);
1328     ///
1329     /// let v: Vec<&str> = "abcXdef".splitn(0, 'X').collect();
1330     /// assert_eq!(v, vec!["abcXdef"]);
1331     ///
1332     /// let v: Vec<&str> = "".splitn(1, 'X').collect();
1333     /// assert_eq!(v, vec![""]);
1334     /// ```
1335     fn splitn<'a, Sep: CharEq>(&'a self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1336
1337     /// An iterator over substrings of `self`, separated by characters
1338     /// matched by `sep`.
1339     ///
1340     /// Equivalent to `split`, except that the trailing substring
1341     /// is skipped if empty (terminator semantics).
1342     ///
1343     /// # Example
1344     ///
1345     /// ```rust
1346     /// let v: Vec<&str> = "A.B.".split_terminator('.').collect();
1347     /// assert_eq!(v, vec!["A", "B"]);
1348     ///
1349     /// let v: Vec<&str> = "A..B..".split_terminator('.').collect();
1350     /// assert_eq!(v, vec!["A", "", "B", ""]);
1351     ///
1352     /// let v: Vec<&str> = "Mary had a little lamb".split(' ').rev().collect();
1353     /// assert_eq!(v, vec!["lamb", "little", "a", "had", "Mary"]);
1354     ///
1355     /// let v: Vec<&str> = "abc1def2ghi".split(|c: char| c.is_digit()).rev().collect();
1356     /// assert_eq!(v, vec!["ghi", "def", "abc"]);
1357     ///
1358     /// let v: Vec<&str> = "lionXXtigerXleopard".split('X').rev().collect();
1359     /// assert_eq!(v, vec!["leopard", "tiger", "", "lion"]);
1360     /// ```
1361     fn split_terminator<'a, Sep: CharEq>(&'a self, sep: Sep) -> CharSplits<'a, Sep>;
1362
1363     /// An iterator over substrings of `self`, separated by characters
1364     /// matched by `sep`, starting from the end of the string.
1365     /// Restricted to splitting at most `count` times.
1366     ///
1367     /// # Example
1368     ///
1369     /// ```rust
1370     /// let v: Vec<&str> = "Mary had a little lamb".rsplitn(2, ' ').collect();
1371     /// assert_eq!(v, vec!["lamb", "little", "Mary had a"]);
1372     ///
1373     /// let v: Vec<&str> = "abc1def2ghi".rsplitn(1, |c: char| c.is_digit()).collect();
1374     /// assert_eq!(v, vec!["ghi", "abc1def"]);
1375     ///
1376     /// let v: Vec<&str> = "lionXXtigerXleopard".rsplitn(2, 'X').collect();
1377     /// assert_eq!(v, vec!["leopard", "tiger", "lionX"]);
1378     /// ```
1379     fn rsplitn<'a, Sep: CharEq>(&'a self, count: uint, sep: Sep) -> CharSplitsN<'a, Sep>;
1380
1381     /// An iterator over the start and end indices of the disjoint
1382     /// matches of `sep` within `self`.
1383     ///
1384     /// That is, each returned value `(start, end)` satisfies
1385     /// `self.slice(start, end) == sep`. For matches of `sep` within
1386     /// `self` that overlap, only the indices corresponding to the
1387     /// first match are returned.
1388     ///
1389     /// # Example
1390     ///
1391     /// ```rust
1392     /// let v: Vec<(uint, uint)> = "abcXXXabcYYYabc".match_indices("abc").collect();
1393     /// assert_eq!(v, vec![(0,3), (6,9), (12,15)]);
1394     ///
1395     /// let v: Vec<(uint, uint)> = "1abcabc2".match_indices("abc").collect();
1396     /// assert_eq!(v, vec![(1,4), (4,7)]);
1397     ///
1398     /// let v: Vec<(uint, uint)> = "ababa".match_indices("aba").collect();
1399     /// assert_eq!(v, vec![(0, 3)]); // only the first `aba`
1400     /// ```
1401     fn match_indices<'a>(&'a self, sep: &'a str) -> MatchIndices<'a>;
1402
1403     /// An iterator over the substrings of `self` separated by `sep`.
1404     ///
1405     /// # Example
1406     ///
1407     /// ```rust
1408     /// let v: Vec<&str> = "abcXXXabcYYYabc".split_str("abc").collect();
1409     /// assert_eq!(v, vec!["", "XXX", "YYY", ""]);
1410     ///
1411     /// let v: Vec<&str> = "1abcabc2".split_str("abc").collect();
1412     /// assert_eq!(v, vec!["1", "", "2"]);
1413     /// ```
1414     fn split_str<'a>(&'a self, &'a str) -> StrSplits<'a>;
1415
1416     /// An iterator over the lines of a string (subsequences separated
1417     /// by `\n`). This does not include the empty string after a
1418     /// trailing `\n`.
1419     ///
1420     /// # Example
1421     ///
1422     /// ```rust
1423     /// let four_lines = "foo\nbar\n\nbaz\n";
1424     /// let v: Vec<&str> = four_lines.lines().collect();
1425     /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1426     /// ```
1427     fn lines<'a>(&'a self) -> CharSplits<'a, char>;
1428
1429     /// An iterator over the lines of a string, separated by either
1430     /// `\n` or `\r\n`. As with `.lines()`, this does not include an
1431     /// empty trailing line.
1432     ///
1433     /// # Example
1434     ///
1435     /// ```rust
1436     /// let four_lines = "foo\r\nbar\n\r\nbaz\n";
1437     /// let v: Vec<&str> = four_lines.lines_any().collect();
1438     /// assert_eq!(v, vec!["foo", "bar", "", "baz"]);
1439     /// ```
1440     fn lines_any<'a>(&'a self) -> AnyLines<'a>;
1441
1442     /// Returns the number of Unicode code points (`char`) that a
1443     /// string holds.
1444     ///
1445     /// This does not perform any normalization, and is `O(n)`, since
1446     /// UTF-8 is a variable width encoding of code points.
1447     ///
1448     /// *Warning*: The number of code points in a string does not directly
1449     /// correspond to the number of visible characters or width of the
1450     /// visible text due to composing characters, and double- and
1451     /// zero-width ones.
1452     ///
1453     /// See also `.len()` for the byte length.
1454     ///
1455     /// # Example
1456     ///
1457     /// ```rust
1458     /// // composed forms of `ö` and `é`
1459     /// let c = "Löwe 老虎 Léopard"; // German, Simplified Chinese, French
1460     /// // decomposed forms of `ö` and `é`
1461     /// let d = "Lo\u0308we 老虎 Le\u0301opard";
1462     ///
1463     /// assert_eq!(c.char_len(), 15);
1464     /// assert_eq!(d.char_len(), 17);
1465     ///
1466     /// assert_eq!(c.len(), 21);
1467     /// assert_eq!(d.len(), 23);
1468     ///
1469     /// // the two strings *look* the same
1470     /// println!("{}", c);
1471     /// println!("{}", d);
1472     /// ```
1473     fn char_len(&self) -> uint;
1474
1475     /// Returns a slice of the given string from the byte range
1476     /// [`begin`..`end`).
1477     ///
1478     /// This operation is `O(1)`.
1479     ///
1480     /// Panics when `begin` and `end` do not point to valid characters
1481     /// or point beyond the last character of the string.
1482     ///
1483     /// See also `slice_to` and `slice_from` for slicing prefixes and
1484     /// suffixes of strings, and `slice_chars` for slicing based on
1485     /// code point counts.
1486     ///
1487     /// # Example
1488     ///
1489     /// ```rust
1490     /// let s = "Löwe 老虎 Léopard";
1491     /// assert_eq!(s.slice(0, 1), "L");
1492     ///
1493     /// assert_eq!(s.slice(1, 9), "öwe 老");
1494     ///
1495     /// // these will panic:
1496     /// // byte 2 lies within `ö`:
1497     /// // s.slice(2, 3);
1498     ///
1499     /// // byte 8 lies within `老`
1500     /// // s.slice(1, 8);
1501     ///
1502     /// // byte 100 is outside the string
1503     /// // s.slice(3, 100);
1504     /// ```
1505     fn slice<'a>(&'a self, begin: uint, end: uint) -> &'a str;
1506
1507     /// Returns a slice of the string from `begin` to its end.
1508     ///
1509     /// Equivalent to `self.slice(begin, self.len())`.
1510     ///
1511     /// Panics when `begin` does not point to a valid character, or is
1512     /// out of bounds.
1513     ///
1514     /// See also `slice`, `slice_to` and `slice_chars`.
1515     fn slice_from<'a>(&'a self, begin: uint) -> &'a str;
1516
1517     /// Returns a slice of the string from the beginning to byte
1518     /// `end`.
1519     ///
1520     /// Equivalent to `self.slice(0, end)`.
1521     ///
1522     /// Panics when `end` does not point to a valid character, or is
1523     /// out of bounds.
1524     ///
1525     /// See also `slice`, `slice_from` and `slice_chars`.
1526     fn slice_to<'a>(&'a self, end: uint) -> &'a str;
1527
1528     /// Returns a slice of the string from the character range
1529     /// [`begin`..`end`).
1530     ///
1531     /// That is, start at the `begin`-th code point of the string and
1532     /// continue to the `end`-th code point. This does not detect or
1533     /// handle edge cases such as leaving a combining character as the
1534     /// first code point of the string.
1535     ///
1536     /// Due to the design of UTF-8, this operation is `O(end)`.
1537     /// See `slice`, `slice_to` and `slice_from` for `O(1)`
1538     /// variants that use byte indices rather than code point
1539     /// indices.
1540     ///
1541     /// Panics if `begin` > `end` or the either `begin` or `end` are
1542     /// beyond the last character of the string.
1543     ///
1544     /// # Example
1545     ///
1546     /// ```rust
1547     /// let s = "Löwe 老虎 Léopard";
1548     /// assert_eq!(s.slice_chars(0, 4), "Löwe");
1549     /// assert_eq!(s.slice_chars(5, 7), "老虎");
1550     /// ```
1551     fn slice_chars<'a>(&'a self, begin: uint, end: uint) -> &'a str;
1552
1553     /// Returns true if `needle` is a prefix of the string.
1554     ///
1555     /// # Example
1556     ///
1557     /// ```rust
1558     /// assert!("banana".starts_with("ba"));
1559     /// ```
1560     fn starts_with(&self, needle: &str) -> bool;
1561
1562     /// Returns true if `needle` is a suffix of the string.
1563     ///
1564     /// # Example
1565     ///
1566     /// ```rust
1567     /// assert!("banana".ends_with("nana"));
1568     /// ```
1569     fn ends_with(&self, needle: &str) -> bool;
1570
1571     /// Returns a string with characters that match `to_trim` removed from the left and the right.
1572     ///
1573     /// # Arguments
1574     ///
1575     /// * to_trim - a character matcher
1576     ///
1577     /// # Example
1578     ///
1579     /// ```rust
1580     /// assert_eq!("11foo1bar11".trim_chars('1'), "foo1bar")
1581     /// let x: &[_] = &['1', '2'];
1582     /// assert_eq!("12foo1bar12".trim_chars(x), "foo1bar")
1583     /// assert_eq!("123foo1bar123".trim_chars(|c: char| c.is_digit()), "foo1bar")
1584     /// ```
1585     fn trim_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1586
1587     /// Returns a string with leading `chars_to_trim` removed.
1588     ///
1589     /// # Arguments
1590     ///
1591     /// * to_trim - a character matcher
1592     ///
1593     /// # Example
1594     ///
1595     /// ```rust
1596     /// assert_eq!("11foo1bar11".trim_left_chars('1'), "foo1bar11")
1597     /// let x: &[_] = &['1', '2'];
1598     /// assert_eq!("12foo1bar12".trim_left_chars(x), "foo1bar12")
1599     /// assert_eq!("123foo1bar123".trim_left_chars(|c: char| c.is_digit()), "foo1bar123")
1600     /// ```
1601     fn trim_left_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1602
1603     /// Returns a string with trailing `chars_to_trim` removed.
1604     ///
1605     /// # Arguments
1606     ///
1607     /// * to_trim - a character matcher
1608     ///
1609     /// # Example
1610     ///
1611     /// ```rust
1612     /// assert_eq!("11foo1bar11".trim_right_chars('1'), "11foo1bar")
1613     /// let x: &[_] = &['1', '2'];
1614     /// assert_eq!("12foo1bar12".trim_right_chars(x), "12foo1bar")
1615     /// assert_eq!("123foo1bar123".trim_right_chars(|c: char| c.is_digit()), "123foo1bar")
1616     /// ```
1617     fn trim_right_chars<'a, C: CharEq>(&'a self, to_trim: C) -> &'a str;
1618
1619     /// Check that `index`-th byte lies at the start and/or end of a
1620     /// UTF-8 code point sequence.
1621     ///
1622     /// The start and end of the string (when `index == self.len()`)
1623     /// are considered to be boundaries.
1624     ///
1625     /// Panics if `index` is greater than `self.len()`.
1626     ///
1627     /// # Example
1628     ///
1629     /// ```rust
1630     /// let s = "Löwe 老虎 Léopard";
1631     /// assert!(s.is_char_boundary(0));
1632     /// // start of `老`
1633     /// assert!(s.is_char_boundary(6));
1634     /// assert!(s.is_char_boundary(s.len()));
1635     ///
1636     /// // second byte of `ö`
1637     /// assert!(!s.is_char_boundary(2));
1638     ///
1639     /// // third byte of `老`
1640     /// assert!(!s.is_char_boundary(8));
1641     /// ```
1642     fn is_char_boundary(&self, index: uint) -> bool;
1643
1644     /// Pluck a character out of a string and return the index of the next
1645     /// character.
1646     ///
1647     /// This function can be used to iterate over the Unicode characters of a
1648     /// string.
1649     ///
1650     /// # Example
1651     ///
1652     /// This example manually iterates through the characters of a
1653     /// string; this should normally be done by `.chars()` or
1654     /// `.char_indices`.
1655     ///
1656     /// ```rust
1657     /// use std::str::CharRange;
1658     ///
1659     /// let s = "中华Việt Nam";
1660     /// let mut i = 0u;
1661     /// while i < s.len() {
1662     ///     let CharRange {ch, next} = s.char_range_at(i);
1663     ///     println!("{}: {}", i, ch);
1664     ///     i = next;
1665     /// }
1666     /// ```
1667     ///
1668     /// ## Output
1669     ///
1670     /// ```ignore
1671     /// 0: 中
1672     /// 3: 华
1673     /// 6: V
1674     /// 7: i
1675     /// 8: ệ
1676     /// 11: t
1677     /// 12:
1678     /// 13: N
1679     /// 14: a
1680     /// 15: m
1681     /// ```
1682     ///
1683     /// # Arguments
1684     ///
1685     /// * s - The string
1686     /// * i - The byte offset of the char to extract
1687     ///
1688     /// # Return value
1689     ///
1690     /// A record {ch: char, next: uint} containing the char value and the byte
1691     /// index of the next Unicode character.
1692     ///
1693     /// # Panics
1694     ///
1695     /// If `i` is greater than or equal to the length of the string.
1696     /// If `i` is not the index of the beginning of a valid UTF-8 character.
1697     fn char_range_at(&self, start: uint) -> CharRange;
1698
1699     /// Given a byte position and a str, return the previous char and its position.
1700     ///
1701     /// This function can be used to iterate over a Unicode string in reverse.
1702     ///
1703     /// Returns 0 for next index if called on start index 0.
1704     ///
1705     /// # Panics
1706     ///
1707     /// If `i` is greater than the length of the string.
1708     /// If `i` is not an index following a valid UTF-8 character.
1709     fn char_range_at_reverse(&self, start: uint) -> CharRange;
1710
1711     /// Plucks the character starting at the `i`th byte of a string.
1712     ///
1713     /// # Example
1714     ///
1715     /// ```rust
1716     /// let s = "abπc";
1717     /// assert_eq!(s.char_at(1), 'b');
1718     /// assert_eq!(s.char_at(2), 'π');
1719     /// assert_eq!(s.char_at(4), 'c');
1720     /// ```
1721     ///
1722     /// # Panics
1723     ///
1724     /// If `i` is greater than or equal to the length of the string.
1725     /// If `i` is not the index of the beginning of a valid UTF-8 character.
1726     fn char_at(&self, i: uint) -> char;
1727
1728     /// Plucks the character ending at the `i`th byte of a string.
1729     ///
1730     /// # Panics
1731     ///
1732     /// If `i` is greater than the length of the string.
1733     /// If `i` is not an index following a valid UTF-8 character.
1734     fn char_at_reverse(&self, i: uint) -> char;
1735
1736     /// Work with the byte buffer of a string as a byte slice.
1737     ///
1738     /// # Example
1739     ///
1740     /// ```rust
1741     /// assert_eq!("bors".as_bytes(), b"bors");
1742     /// ```
1743     fn as_bytes<'a>(&'a self) -> &'a [u8];
1744
1745     /// Returns the byte index of the first character of `self` that
1746     /// matches `search`.
1747     ///
1748     /// # Return value
1749     ///
1750     /// `Some` containing the byte index of the last matching character
1751     /// or `None` if there is no match
1752     ///
1753     /// # Example
1754     ///
1755     /// ```rust
1756     /// let s = "Löwe 老虎 Léopard";
1757     ///
1758     /// assert_eq!(s.find('L'), Some(0));
1759     /// assert_eq!(s.find('é'), Some(14));
1760     ///
1761     /// // the first space
1762     /// assert_eq!(s.find(|c: char| c.is_whitespace()), Some(5));
1763     ///
1764     /// // neither are found
1765     /// let x: &[_] = &['1', '2'];
1766     /// assert_eq!(s.find(x), None);
1767     /// ```
1768     fn find<C: CharEq>(&self, search: C) -> Option<uint>;
1769
1770     /// Returns the byte index of the last character of `self` that
1771     /// matches `search`.
1772     ///
1773     /// # Return value
1774     ///
1775     /// `Some` containing the byte index of the last matching character
1776     /// or `None` if there is no match.
1777     ///
1778     /// # Example
1779     ///
1780     /// ```rust
1781     /// let s = "Löwe 老虎 Léopard";
1782     ///
1783     /// assert_eq!(s.rfind('L'), Some(13));
1784     /// assert_eq!(s.rfind('é'), Some(14));
1785     ///
1786     /// // the second space
1787     /// assert_eq!(s.rfind(|c: char| c.is_whitespace()), Some(12));
1788     ///
1789     /// // searches for an occurrence of either `1` or `2`, but neither are found
1790     /// let x: &[_] = &['1', '2'];
1791     /// assert_eq!(s.rfind(x), None);
1792     /// ```
1793     fn rfind<C: CharEq>(&self, search: C) -> Option<uint>;
1794
1795     /// Returns the byte index of the first matching substring
1796     ///
1797     /// # Arguments
1798     ///
1799     /// * `needle` - The string to search for
1800     ///
1801     /// # Return value
1802     ///
1803     /// `Some` containing the byte index of the first matching substring
1804     /// or `None` if there is no match.
1805     ///
1806     /// # Example
1807     ///
1808     /// ```rust
1809     /// let s = "Löwe 老虎 Léopard";
1810     ///
1811     /// assert_eq!(s.find_str("老虎 L"), Some(6));
1812     /// assert_eq!(s.find_str("muffin man"), None);
1813     /// ```
1814     fn find_str(&self, &str) -> Option<uint>;
1815
1816     /// Retrieves the first character from a string slice and returns
1817     /// it. This does not allocate a new string; instead, it returns a
1818     /// slice that point one character beyond the character that was
1819     /// shifted. If the string does not contain any characters,
1820     /// a tuple of None and an empty string is returned instead.
1821     ///
1822     /// # Example
1823     ///
1824     /// ```rust
1825     /// let s = "Löwe 老虎 Léopard";
1826     /// let (c, s1) = s.slice_shift_char();
1827     /// assert_eq!(c, Some('L'));
1828     /// assert_eq!(s1, "öwe 老虎 Léopard");
1829     ///
1830     /// let (c, s2) = s1.slice_shift_char();
1831     /// assert_eq!(c, Some('ö'));
1832     /// assert_eq!(s2, "we 老虎 Léopard");
1833     /// ```
1834     fn slice_shift_char<'a>(&'a self) -> (Option<char>, &'a str);
1835
1836     /// Returns the byte offset of an inner slice relative to an enclosing outer slice.
1837     ///
1838     /// Panics if `inner` is not a direct slice contained within self.
1839     ///
1840     /// # Example
1841     ///
1842     /// ```rust
1843     /// let string = "a\nb\nc";
1844     /// let lines: Vec<&str> = string.lines().collect();
1845     /// let lines = lines.as_slice();
1846     ///
1847     /// assert!(string.subslice_offset(lines[0]) == 0); // &"a"
1848     /// assert!(string.subslice_offset(lines[1]) == 2); // &"b"
1849     /// assert!(string.subslice_offset(lines[2]) == 4); // &"c"
1850     /// ```
1851     fn subslice_offset(&self, inner: &str) -> uint;
1852
1853     /// Return an unsafe pointer to the strings buffer.
1854     ///
1855     /// The caller must ensure that the string outlives this pointer,
1856     /// and that it is not reallocated (e.g. by pushing to the
1857     /// string).
1858     fn as_ptr(&self) -> *const u8;
1859
1860     /// Return an iterator of `u16` over the string encoded as UTF-16.
1861     fn utf16_units<'a>(&'a self) -> Utf16CodeUnits<'a>;
1862
1863     /// Return the number of bytes in this string
1864     ///
1865     /// # Example
1866     ///
1867     /// ```
1868     /// assert_eq!("foo".len(), 3);
1869     /// assert_eq!("ƒoo".len(), 4);
1870     /// ```
1871     #[experimental = "not triaged yet"]
1872     fn len(&self) -> uint;
1873
1874     /// Returns true if this slice contains no bytes
1875     ///
1876     /// # Example
1877     ///
1878     /// ```
1879     /// assert!("".is_empty());
1880     /// ```
1881     #[inline]
1882     #[experimental = "not triaged yet"]
1883     fn is_empty(&self) -> bool { self.len() == 0 }
1884 }
1885
1886 #[inline(never)]
1887 fn slice_error_fail(s: &str, begin: uint, end: uint) -> ! {
1888     assert!(begin <= end);
1889     panic!("index {} and/or {} in `{}` do not lie on character boundary",
1890           begin, end, s);
1891 }
1892
1893 impl StrPrelude for str {
1894     #[inline]
1895     fn contains(&self, needle: &str) -> bool {
1896         self.find_str(needle).is_some()
1897     }
1898
1899     #[inline]
1900     fn contains_char(&self, needle: char) -> bool {
1901         self.find(needle).is_some()
1902     }
1903
1904     #[inline]
1905     fn chars(&self) -> Chars {
1906         Chars{iter: self.as_bytes().iter()}
1907     }
1908
1909     #[inline]
1910     fn bytes(&self) -> Bytes {
1911         self.as_bytes().iter().map(|&b| b)
1912     }
1913
1914     #[inline]
1915     fn char_indices(&self) -> CharOffsets {
1916         CharOffsets{front_offset: 0, iter: self.chars()}
1917     }
1918
1919     #[inline]
1920     fn split<Sep: CharEq>(&self, sep: Sep) -> CharSplits<Sep> {
1921         CharSplits {
1922             string: self,
1923             only_ascii: sep.only_ascii(),
1924             sep: sep,
1925             allow_trailing_empty: true,
1926             finished: false,
1927         }
1928     }
1929
1930     #[inline]
1931     fn splitn<Sep: CharEq>(&self, count: uint, sep: Sep)
1932         -> CharSplitsN<Sep> {
1933         CharSplitsN {
1934             iter: self.split(sep),
1935             count: count,
1936             invert: false,
1937         }
1938     }
1939
1940     #[inline]
1941     fn split_terminator<Sep: CharEq>(&self, sep: Sep)
1942         -> CharSplits<Sep> {
1943         CharSplits {
1944             allow_trailing_empty: false,
1945             ..self.split(sep)
1946         }
1947     }
1948
1949     #[inline]
1950     fn rsplitn<Sep: CharEq>(&self, count: uint, sep: Sep)
1951         -> CharSplitsN<Sep> {
1952         CharSplitsN {
1953             iter: self.split(sep),
1954             count: count,
1955             invert: true,
1956         }
1957     }
1958
1959     #[inline]
1960     fn match_indices<'a>(&'a self, sep: &'a str) -> MatchIndices<'a> {
1961         assert!(!sep.is_empty())
1962         MatchIndices {
1963             haystack: self,
1964             needle: sep,
1965             searcher: Searcher::new(self.as_bytes(), sep.as_bytes())
1966         }
1967     }
1968
1969     #[inline]
1970     fn split_str<'a>(&'a self, sep: &'a str) -> StrSplits<'a> {
1971         StrSplits {
1972             it: self.match_indices(sep),
1973             last_end: 0,
1974             finished: false
1975         }
1976     }
1977
1978     #[inline]
1979     fn lines(&self) -> CharSplits<char> {
1980         self.split_terminator('\n')
1981     }
1982
1983     fn lines_any(&self) -> AnyLines {
1984         self.lines().map(|line| {
1985             let l = line.len();
1986             if l > 0 && line.as_bytes()[l - 1] == b'\r' { line.slice(0, l - 1) }
1987             else { line }
1988         })
1989     }
1990
1991     #[inline]
1992     fn char_len(&self) -> uint { self.chars().count() }
1993
1994     #[inline]
1995     fn slice(&self, begin: uint, end: uint) -> &str {
1996         // is_char_boundary checks that the index is in [0, .len()]
1997         if begin <= end &&
1998            self.is_char_boundary(begin) &&
1999            self.is_char_boundary(end) {
2000             unsafe { raw::slice_unchecked(self, begin, end) }
2001         } else {
2002             slice_error_fail(self, begin, end)
2003         }
2004     }
2005
2006     #[inline]
2007     fn slice_from(&self, begin: uint) -> &str {
2008         // is_char_boundary checks that the index is in [0, .len()]
2009         if self.is_char_boundary(begin) {
2010             unsafe { raw::slice_unchecked(self, begin, self.len()) }
2011         } else {
2012             slice_error_fail(self, begin, self.len())
2013         }
2014     }
2015
2016     #[inline]
2017     fn slice_to(&self, end: uint) -> &str {
2018         // is_char_boundary checks that the index is in [0, .len()]
2019         if self.is_char_boundary(end) {
2020             unsafe { raw::slice_unchecked(self, 0, end) }
2021         } else {
2022             slice_error_fail(self, 0, end)
2023         }
2024     }
2025
2026     fn slice_chars(&self, begin: uint, end: uint) -> &str {
2027         assert!(begin <= end);
2028         let mut count = 0;
2029         let mut begin_byte = None;
2030         let mut end_byte = None;
2031
2032         // This could be even more efficient by not decoding,
2033         // only finding the char boundaries
2034         for (idx, _) in self.char_indices() {
2035             if count == begin { begin_byte = Some(idx); }
2036             if count == end { end_byte = Some(idx); break; }
2037             count += 1;
2038         }
2039         if begin_byte.is_none() && count == begin { begin_byte = Some(self.len()) }
2040         if end_byte.is_none() && count == end { end_byte = Some(self.len()) }
2041
2042         match (begin_byte, end_byte) {
2043             (None, _) => panic!("slice_chars: `begin` is beyond end of string"),
2044             (_, None) => panic!("slice_chars: `end` is beyond end of string"),
2045             (Some(a), Some(b)) => unsafe { raw::slice_bytes(self, a, b) }
2046         }
2047     }
2048
2049     #[inline]
2050     fn starts_with(&self, needle: &str) -> bool {
2051         let n = needle.len();
2052         self.len() >= n && needle.as_bytes() == self.as_bytes()[..n]
2053     }
2054
2055     #[inline]
2056     fn ends_with(&self, needle: &str) -> bool {
2057         let (m, n) = (self.len(), needle.len());
2058         m >= n && needle.as_bytes() == self.as_bytes()[m-n..]
2059     }
2060
2061     #[inline]
2062     fn trim_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2063         let cur = match self.find(|c: char| !to_trim.matches(c)) {
2064             None => "",
2065             Some(i) => unsafe { raw::slice_bytes(self, i, self.len()) }
2066         };
2067         match cur.rfind(|c: char| !to_trim.matches(c)) {
2068             None => "",
2069             Some(i) => {
2070                 let right = cur.char_range_at(i).next;
2071                 unsafe { raw::slice_bytes(cur, 0, right) }
2072             }
2073         }
2074     }
2075
2076     #[inline]
2077     fn trim_left_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2078         match self.find(|c: char| !to_trim.matches(c)) {
2079             None => "",
2080             Some(first) => unsafe { raw::slice_bytes(self, first, self.len()) }
2081         }
2082     }
2083
2084     #[inline]
2085     fn trim_right_chars<C: CharEq>(&self, mut to_trim: C) -> &str {
2086         match self.rfind(|c: char| !to_trim.matches(c)) {
2087             None => "",
2088             Some(last) => {
2089                 let next = self.char_range_at(last).next;
2090                 unsafe { raw::slice_bytes(self, 0u, next) }
2091             }
2092         }
2093     }
2094
2095     #[inline]
2096     fn is_char_boundary(&self, index: uint) -> bool {
2097         if index == self.len() { return true; }
2098         match self.as_bytes().get(index) {
2099             None => false,
2100             Some(&b) => b < 128u8 || b >= 192u8,
2101         }
2102     }
2103
2104     #[inline]
2105     fn char_range_at(&self, i: uint) -> CharRange {
2106         if self.as_bytes()[i] < 128u8 {
2107             return CharRange {ch: self.as_bytes()[i] as char, next: i + 1 };
2108         }
2109
2110         // Multibyte case is a fn to allow char_range_at to inline cleanly
2111         fn multibyte_char_range_at(s: &str, i: uint) -> CharRange {
2112             let mut val = s.as_bytes()[i] as u32;
2113             let w = UTF8_CHAR_WIDTH[val as uint] as uint;
2114             assert!((w != 0));
2115
2116             val = utf8_first_byte!(val, w);
2117             val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
2118             if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
2119             if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
2120
2121             return CharRange {ch: unsafe { mem::transmute(val) }, next: i + w};
2122         }
2123
2124         return multibyte_char_range_at(self, i);
2125     }
2126
2127     #[inline]
2128     fn char_range_at_reverse(&self, start: uint) -> CharRange {
2129         let mut prev = start;
2130
2131         prev = prev.saturating_sub(1);
2132         if self.as_bytes()[prev] < 128 {
2133             return CharRange{ch: self.as_bytes()[prev] as char, next: prev}
2134         }
2135
2136         // Multibyte case is a fn to allow char_range_at_reverse to inline cleanly
2137         fn multibyte_char_range_at_reverse(s: &str, mut i: uint) -> CharRange {
2138             // while there is a previous byte == 10......
2139             while i > 0 && s.as_bytes()[i] & !CONT_MASK == TAG_CONT_U8 {
2140                 i -= 1u;
2141             }
2142
2143             let mut val = s.as_bytes()[i] as u32;
2144             let w = UTF8_CHAR_WIDTH[val as uint] as uint;
2145             assert!((w != 0));
2146
2147             val = utf8_first_byte!(val, w);
2148             val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 1]);
2149             if w > 2 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 2]); }
2150             if w > 3 { val = utf8_acc_cont_byte!(val, s.as_bytes()[i + 3]); }
2151
2152             return CharRange {ch: unsafe { mem::transmute(val) }, next: i};
2153         }
2154
2155         return multibyte_char_range_at_reverse(self, prev);
2156     }
2157
2158     #[inline]
2159     fn char_at(&self, i: uint) -> char {
2160         self.char_range_at(i).ch
2161     }
2162
2163     #[inline]
2164     fn char_at_reverse(&self, i: uint) -> char {
2165         self.char_range_at_reverse(i).ch
2166     }
2167
2168     #[inline]
2169     fn as_bytes(&self) -> &[u8] {
2170         unsafe { mem::transmute(self) }
2171     }
2172
2173     fn find<C: CharEq>(&self, mut search: C) -> Option<uint> {
2174         if search.only_ascii() {
2175             self.bytes().position(|b| search.matches(b as char))
2176         } else {
2177             for (index, c) in self.char_indices() {
2178                 if search.matches(c) { return Some(index); }
2179             }
2180             None
2181         }
2182     }
2183
2184     fn rfind<C: CharEq>(&self, mut search: C) -> Option<uint> {
2185         if search.only_ascii() {
2186             self.bytes().rposition(|b| search.matches(b as char))
2187         } else {
2188             for (index, c) in self.char_indices().rev() {
2189                 if search.matches(c) { return Some(index); }
2190             }
2191             None
2192         }
2193     }
2194
2195     fn find_str(&self, needle: &str) -> Option<uint> {
2196         if needle.is_empty() {
2197             Some(0)
2198         } else {
2199             self.match_indices(needle)
2200                 .next()
2201                 .map(|(start, _end)| start)
2202         }
2203     }
2204
2205     #[inline]
2206     fn slice_shift_char(&self) -> (Option<char>, &str) {
2207         if self.is_empty() {
2208             return (None, self);
2209         } else {
2210             let CharRange {ch, next} = self.char_range_at(0u);
2211             let next_s = unsafe { raw::slice_bytes(self, next, self.len()) };
2212             return (Some(ch), next_s);
2213         }
2214     }
2215
2216     fn subslice_offset(&self, inner: &str) -> uint {
2217         let a_start = self.as_ptr() as uint;
2218         let a_end = a_start + self.len();
2219         let b_start = inner.as_ptr() as uint;
2220         let b_end = b_start + inner.len();
2221
2222         assert!(a_start <= b_start);
2223         assert!(b_end <= a_end);
2224         b_start - a_start
2225     }
2226
2227     #[inline]
2228     fn as_ptr(&self) -> *const u8 {
2229         self.repr().data
2230     }
2231
2232     #[inline]
2233     fn utf16_units(&self) -> Utf16CodeUnits {
2234         Utf16CodeUnits{ chars: self.chars(), extra: 0}
2235     }
2236
2237     #[inline]
2238     fn len(&self) -> uint { self.repr().len }
2239 }
2240
2241 impl<'a> Default for &'a str {
2242     fn default() -> &'a str { "" }
2243 }