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