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