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