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 #![stable(feature = "rust1", since = "1.0.0")]
  16
  17 use self::pattern::Pattern;
  18 use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher};
  19
  20 use char;
  21 use convert::TryFrom;
  22 use fmt;
  23 use iter::{Map, Cloned, FusedIterator};
  24 use slice::{self, SliceIndex};
  25 use mem;
  26 use intrinsics::align_offset;
  27
  28 pub mod pattern;
  29
  30 /// A trait to abstract the idea of creating a new instance of a type from a
  31 /// string.
  32 ///
  33 /// `FromStr`'s [`from_str`] method is often used implicitly, through
  34 /// [`str`]'s [`parse`] method. See [`parse`]'s documentation for examples.
  35 ///
  36 /// [`from_str`]: #tymethod.from_str
  37 /// [`str`]: ../../std/primitive.str.html
  38 /// [`parse`]: ../../std/primitive.str.html#method.parse
  39 ///
  40 /// # Examples
  41 ///
  42 /// Basic implementation of `FromStr` on an example `Point` type:
  43 ///
  44 /// ```
  45 /// use std::str::FromStr;
  46 /// use std::num::ParseIntError;
  47 ///
  48 /// #[derive(Debug, PartialEq)]
  49 /// struct Point {
  50 ///     x: i32,
  51 ///     y: i32
  52 /// }
  53 ///
  54 /// impl FromStr for Point {
  55 ///     type Err = ParseIntError;
  56 ///
  57 ///     fn from_str(s: &str) -> Result<Self, Self::Err> {
  58 ///         let coords: Vec<&str> = s.trim_matches(|p| p == '(' || p == ')' )
  59 ///                                  .split(",")
  60 ///                                  .collect();
  61 ///
  62 ///         let x_fromstr = coords[0].parse::<i32>()?;
  63 ///         let y_fromstr = coords[1].parse::<i32>()?;
  64 ///
  65 ///         Ok(Point { x: x_fromstr, y: y_fromstr })
  66 ///     }
  67 /// }
  68 ///
  69 /// let p = Point::from_str("(1,2)");
  70 /// assert_eq!(p.unwrap(), Point{ x: 1, y: 2} )
  71 /// ```
  72 #[stable(feature = "rust1", since = "1.0.0")]
  73 pub trait FromStr: Sized {
  74     /// The associated error which can be returned from parsing.
  75     #[stable(feature = "rust1", since = "1.0.0")]
  76     type Err;
  77
  78     /// Parses a string `s` to return a value of this type.
  79     ///
  80     /// If parsing succeeds, return the value inside `Ok`, otherwise
  81     /// when the string is ill-formatted return an error specific to the
  82     /// inside `Err`. The error type is specific to implementation of the trait.
  83     ///
  84     /// # Examples
  85     ///
  86     /// Basic usage with [`i32`][ithirtytwo], a type that implements `FromStr`:
  87     ///
  88     /// [ithirtytwo]: ../../std/primitive.i32.html
  89     ///
  90     /// ```
  91     /// use std::str::FromStr;
  92     ///
  93     /// let s = "5";
  94     /// let x = i32::from_str(s).unwrap();
  95     ///
  96     /// assert_eq!(5, x);
  97     /// ```
  98     #[stable(feature = "rust1", since = "1.0.0")]
  99     fn from_str(s: &str) -> Result<Self, Self::Err>;
 100 }
 101
 102 #[stable(feature = "rust1", since = "1.0.0")]
 103 impl FromStr for bool {
 104     type Err = ParseBoolError;
 105
 106     /// Parse a `bool` from a string.
 107     ///
 108     /// Yields a `Result<bool, ParseBoolError>`, because `s` may or may not
 109     /// actually be parseable.
 110     ///
 111     /// # Examples
 112     ///
 113     /// ```
 114     /// use std::str::FromStr;
 115     ///
 116     /// assert_eq!(FromStr::from_str("true"), Ok(true));
 117     /// assert_eq!(FromStr::from_str("false"), Ok(false));
 118     /// assert!(<bool as FromStr>::from_str("not even a boolean").is_err());
 119     /// ```
 120     ///
 121     /// Note, in many cases, the `.parse()` method on `str` is more proper.
 122     ///
 123     /// ```
 124     /// assert_eq!("true".parse(), Ok(true));
 125     /// assert_eq!("false".parse(), Ok(false));
 126     /// assert!("not even a boolean".parse::<bool>().is_err());
 127     /// ```
 128     #[inline]
 129     fn from_str(s: &str) -> Result<bool, ParseBoolError> {
 130         match s {
 131             "true"  => Ok(true),
 132             "false" => Ok(false),
 133             _       => Err(ParseBoolError { _priv: () }),
 134         }
 135     }
 136 }
 137
 138 /// An error returned when parsing a `bool` using [`from_str`] fails
 139 ///
 140 /// [`from_str`]: ../../std/primitive.bool.html#method.from_str
 141 #[derive(Debug, Clone, PartialEq, Eq)]
 142 #[stable(feature = "rust1", since = "1.0.0")]
 143 pub struct ParseBoolError { _priv: () }
 144
 145 #[stable(feature = "rust1", since = "1.0.0")]
 146 impl fmt::Display for ParseBoolError {
 147     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 148         "provided string was not `true` or `false`".fmt(f)
 149     }
 150 }
 151
 152 /*
 153 Section: Creating a string
 154 */
 155
 156 /// Errors which can occur when attempting to interpret a sequence of [`u8`]
 157 /// as a string.
 158 ///
 159 /// [`u8`]: ../../std/primitive.u8.html
 160 ///
 161 /// As such, the `from_utf8` family of functions and methods for both [`String`]s
 162 /// and [`&str`]s make use of this error, for example.
 163 ///
 164 /// [`String`]: ../../std/string/struct.String.html#method.from_utf8
 165 /// [`&str`]: ../../std/str/fn.from_utf8.html
 166 #[derive(Copy, Eq, PartialEq, Clone, Debug)]
 167 #[stable(feature = "rust1", since = "1.0.0")]
 168 pub struct Utf8Error {
 169     valid_up_to: usize,
 170     error_len: Option<u8>,
 171 }
 172
 173 impl Utf8Error {
 174     /// Returns the index in the given string up to which valid UTF-8 was
 175     /// verified.
 176     ///
 177     /// It is the maximum index such that `from_utf8(&input[..index])`
 178     /// would return `Ok(_)`.
 179     ///
 180     /// # Examples
 181     ///
 182     /// Basic usage:
 183     ///
 184     /// ```
 185     /// use std::str;
 186     ///
 187     /// // some invalid bytes, in a vector
 188     /// let sparkle_heart = vec![0, 159, 146, 150];
 189     ///
 190     /// // std::str::from_utf8 returns a Utf8Error
 191     /// let error = str::from_utf8(&sparkle_heart).unwrap_err();
 192     ///
 193     /// // the second byte is invalid here
 194     /// assert_eq!(1, error.valid_up_to());
 195     /// ```
 196     #[stable(feature = "utf8_error", since = "1.5.0")]
 197     pub fn valid_up_to(&self) -> usize { self.valid_up_to }
 198
 199     /// Provide more information about the failure:
 200     ///
 201     /// * `None`: the end of the input was reached unexpectedly.
 202     ///   `self.valid_up_to()` is 1 to 3 bytes from the end of the input.
 203     ///   If a byte stream (such as a file or a network socket) is being decoded incrementally,
 204     ///   this could be a valid `char` whose UTF-8 byte sequence is spanning multiple chunks.
 205     ///
 206     /// * `Some(len)`: an unexpected byte was encountered.
 207     ///   The length provided is that of the invalid byte sequence
 208     ///   that starts at the index given by `valid_up_to()`.
 209     ///   Decoding should resume after that sequence
 210     ///   (after inserting a U+FFFD REPLACEMENT CHARACTER) in case of lossy decoding.
 211     #[stable(feature = "utf8_error_error_len", since = "1.20.0")]
 212     pub fn error_len(&self) -> Option<usize> {
 213         self.error_len.map(|len| len as usize)
 214     }
 215 }
 216
 217 /// Converts a slice of bytes to a string slice.
 218 ///
 219 /// A string slice ([`&str`]) is made of bytes ([`u8`]), and a byte slice
 220 /// ([`&[u8]`][byteslice]) is made of bytes, so this function converts between
 221 /// the two. Not all byte slices are valid string slices, however: [`&str`] requires
 222 /// that it is valid UTF-8. `from_utf8()` checks to ensure that the bytes are valid
 223 /// UTF-8, and then does the conversion.
 224 ///
 225 /// [`&str`]: ../../std/primitive.str.html
 226 /// [`u8`]: ../../std/primitive.u8.html
 227 /// [byteslice]: ../../std/primitive.slice.html
 228 ///
 229 /// If you are sure that the byte slice is valid UTF-8, and you don't want to
 230 /// incur the overhead of the validity check, there is an unsafe version of
 231 /// this function, [`from_utf8_unchecked`][fromutf8u], which has the same
 232 /// behavior but skips the check.
 233 ///
 234 /// [fromutf8u]: fn.from_utf8_unchecked.html
 235 ///
 236 /// If you need a `String` instead of a `&str`, consider
 237 /// [`String::from_utf8`][string].
 238 ///
 239 /// [string]: ../../std/string/struct.String.html#method.from_utf8
 240 ///
 241 /// Because you can stack-allocate a `[u8; N]`, and you can take a
 242 /// [`&[u8]`][byteslice] of it, this function is one way to have a
 243 /// stack-allocated string. There is an example of this in the
 244 /// examples section below.
 245 ///
 246 /// [byteslice]: ../../std/primitive.slice.html
 247 ///
 248 /// # Errors
 249 ///
 250 /// Returns `Err` if the slice is not UTF-8 with a description as to why the
 251 /// provided slice is not UTF-8.
 252 ///
 253 /// # Examples
 254 ///
 255 /// Basic usage:
 256 ///
 257 /// ```
 258 /// use std::str;
 259 ///
 260 /// // some bytes, in a vector
 261 /// let sparkle_heart = vec![240, 159, 146, 150];
 262 ///
 263 /// // We know these bytes are valid, so just use `unwrap()`.
 264 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 265 ///
 266 /// assert_eq!("💖", sparkle_heart);
 267 /// ```
 268 ///
 269 /// Incorrect bytes:
 270 ///
 271 /// ```
 272 /// use std::str;
 273 ///
 274 /// // some invalid bytes, in a vector
 275 /// let sparkle_heart = vec![0, 159, 146, 150];
 276 ///
 277 /// assert!(str::from_utf8(&sparkle_heart).is_err());
 278 /// ```
 279 ///
 280 /// See the docs for [`Utf8Error`][error] for more details on the kinds of
 281 /// errors that can be returned.
 282 ///
 283 /// [error]: struct.Utf8Error.html
 284 ///
 285 /// A "stack allocated string":
 286 ///
 287 /// ```
 288 /// use std::str;
 289 ///
 290 /// // some bytes, in a stack-allocated array
 291 /// let sparkle_heart = [240, 159, 146, 150];
 292 ///
 293 /// // We know these bytes are valid, so just use `unwrap()`.
 294 /// let sparkle_heart = str::from_utf8(&sparkle_heart).unwrap();
 295 ///
 296 /// assert_eq!("💖", sparkle_heart);
 297 /// ```
 298 #[stable(feature = "rust1", since = "1.0.0")]
 299 pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
 300     run_utf8_validation(v)?;
 301     Ok(unsafe { from_utf8_unchecked(v) })
 302 }
 303
 304 /// Converts a mutable slice of bytes to a mutable string slice.
 305 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 306 pub fn from_utf8_mut(v: &mut [u8]) -> Result<&mut str, Utf8Error> {
 307     run_utf8_validation(v)?;
 308     Ok(unsafe { from_utf8_unchecked_mut(v) })
 309 }
 310
 311 /// Forms a str from a pointer and a length.
 312 ///
 313 /// The `len` argument is the number of bytes in the string.
 314 ///
 315 /// # Safety
 316 ///
 317 /// This function is unsafe as there is no guarantee that the given pointer is
 318 /// valid for `len` bytes, nor whether the lifetime inferred is a suitable
 319 /// lifetime for the returned str.
 320 ///
 321 /// The data must be valid UTF-8
 322 ///
 323 /// `p` must be non-null, even for zero-length strs, because non-zero bits
 324 /// are required to distinguish between a zero-length str within `Some()`
 325 /// from `None`. `p` can be a bogus non-dereferencable pointer, such as `0x1`,
 326 /// for zero-length strs, though.
 327 ///
 328 /// # Caveat
 329 ///
 330 /// The lifetime for the returned str is inferred from its usage. To
 331 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
 332 /// source lifetime is safe in the context, such as by providing a helper
 333 /// function taking the lifetime of a host value for the str, or by explicit
 334 /// annotation.
 335 /// Performs the same functionality as `from_raw_parts`, except that a mutable
 336 /// str is returned.
 337 ///
 338 unsafe fn from_raw_parts_mut<'a>(p: *mut u8, len: usize) -> &'a mut str {
 339     from_utf8_unchecked_mut(slice::from_raw_parts_mut(p, len))
 340 }
 341
 342 /// Converts a slice of bytes to a string slice without checking
 343 /// that the string contains valid UTF-8.
 344 ///
 345 /// See the safe version, [`from_utf8`][fromutf8], for more information.
 346 ///
 347 /// [fromutf8]: fn.from_utf8.html
 348 ///
 349 /// # Safety
 350 ///
 351 /// This function is unsafe because it does not check that the bytes passed to
 352 /// it are valid UTF-8. If this constraint is violated, undefined behavior
 353 /// results, as the rest of Rust assumes that [`&str`]s are valid UTF-8.
 354 ///
 355 /// [`&str`]: ../../std/primitive.str.html
 356 ///
 357 /// # Examples
 358 ///
 359 /// Basic usage:
 360 ///
 361 /// ```
 362 /// use std::str;
 363 ///
 364 /// // some bytes, in a vector
 365 /// let sparkle_heart = vec![240, 159, 146, 150];
 366 ///
 367 /// let sparkle_heart = unsafe {
 368 ///     str::from_utf8_unchecked(&sparkle_heart)
 369 /// };
 370 ///
 371 /// assert_eq!("💖", sparkle_heart);
 372 /// ```
 373 #[inline]
 374 #[stable(feature = "rust1", since = "1.0.0")]
 375 pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
 376     mem::transmute(v)
 377 }
 378
 379 /// Converts a slice of bytes to a string slice without checking
 380 /// that the string contains valid UTF-8; mutable version.
 381 ///
 382 /// See the immutable version, [`from_utf8_unchecked()`][fromutf8], for more information.
 383 ///
 384 /// [fromutf8]: fn.from_utf8_unchecked.html
 385 #[inline]
 386 #[stable(feature = "str_mut_extras", since = "1.20.0")]
 387 pub unsafe fn from_utf8_unchecked_mut(v: &mut [u8]) -> &mut str {
 388     mem::transmute(v)
 389 }
 390
 391 #[stable(feature = "rust1", since = "1.0.0")]
 392 impl fmt::Display for Utf8Error {
 393     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 394         if let Some(error_len) = self.error_len {
 395             write!(f, "invalid utf-8 sequence of {} bytes from index {}",
 396                    error_len, self.valid_up_to)
 397         } else {
 398             write!(f, "incomplete utf-8 byte sequence from index {}", self.valid_up_to)
 399         }
 400     }
 401 }
 402
 403 /*
 404 Section: Iterators
 405 */
 406
 407 /// An iterator over the [`char`]s of a string slice.
 408 ///
 409 /// [`char`]: ../../std/primitive.char.html
 410 ///
 411 /// This struct is created by the [`chars`] method on [`str`].
 412 /// See its documentation for more.
 413 ///
 414 /// [`chars`]: ../../std/primitive.str.html#method.chars
 415 /// [`str`]: ../../std/primitive.str.html
 416 #[derive(Clone, Debug)]
 417 #[stable(feature = "rust1", since = "1.0.0")]
 418 pub struct Chars<'a> {
 419     iter: slice::Iter<'a, u8>
 420 }
 421
 422 /// Returns the initial codepoint accumulator for the first byte.
 423 /// The first byte is special, only want bottom 5 bits for width 2, 4 bits
 424 /// for width 3, and 3 bits for width 4.
 425 #[inline]
 426 fn utf8_first_byte(byte: u8, width: u32) -> u32 { (byte & (0x7F >> width)) as u32 }
 427
 428 /// Returns the value of `ch` updated with continuation byte `byte`.
 429 #[inline]
 430 fn utf8_acc_cont_byte(ch: u32, byte: u8) -> u32 { (ch << 6) | (byte & CONT_MASK) as u32 }
 431
 432 /// Checks whether the byte is a UTF-8 continuation byte (i.e. starts with the
 433 /// bits `10`).
 434 #[inline]
 435 fn utf8_is_cont_byte(byte: u8) -> bool { (byte & !CONT_MASK) == TAG_CONT_U8 }
 436
 437 #[inline]
 438 fn unwrap_or_0(opt: Option<&u8>) -> u8 {
 439     match opt {
 440         Some(&byte) => byte,
 441         None => 0,
 442     }
 443 }
 444
 445 /// Reads the next code point out of a byte iterator (assuming a
 446 /// UTF-8-like encoding).
 447 #[unstable(feature = "str_internals", issue = "0")]
 448 #[inline]
 449 pub fn next_code_point<'a, I: Iterator<Item = &'a u8>>(bytes: &mut I) -> Option<u32> {
 450     // Decode UTF-8
 451     let x = match bytes.next() {
 452         None => return None,
 453         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 454         Some(&next_byte) => next_byte,
 455     };
 456
 457     // Multibyte case follows
 458     // Decode from a byte combination out of: [[[x y] z] w]
 459     // NOTE: Performance is sensitive to the exact formulation here
 460     let init = utf8_first_byte(x, 2);
 461     let y = unwrap_or_0(bytes.next());
 462     let mut ch = utf8_acc_cont_byte(init, y);
 463     if x >= 0xE0 {
 464         // [[x y z] w] case
 465         // 5th bit in 0xE0 .. 0xEF is always clear, so `init` is still valid
 466         let z = unwrap_or_0(bytes.next());
 467         let y_z = utf8_acc_cont_byte((y & CONT_MASK) as u32, z);
 468         ch = init << 12 | y_z;
 469         if x >= 0xF0 {
 470             // [x y z w] case
 471             // use only the lower 3 bits of `init`
 472             let w = unwrap_or_0(bytes.next());
 473             ch = (init & 7) << 18 | utf8_acc_cont_byte(y_z, w);
 474         }
 475     }
 476
 477     Some(ch)
 478 }
 479
 480 /// Reads the last code point out of a byte iterator (assuming a
 481 /// UTF-8-like encoding).
 482 #[inline]
 483 fn next_code_point_reverse<'a, I>(bytes: &mut I) -> Option<u32>
 484     where I: DoubleEndedIterator<Item = &'a u8>,
 485 {
 486     // Decode UTF-8
 487     let w = match bytes.next_back() {
 488         None => return None,
 489         Some(&next_byte) if next_byte < 128 => return Some(next_byte as u32),
 490         Some(&back_byte) => back_byte,
 491     };
 492
 493     // Multibyte case follows
 494     // Decode from a byte combination out of: [x [y [z w]]]
 495     let mut ch;
 496     let z = unwrap_or_0(bytes.next_back());
 497     ch = utf8_first_byte(z, 2);
 498     if utf8_is_cont_byte(z) {
 499         let y = unwrap_or_0(bytes.next_back());
 500         ch = utf8_first_byte(y, 3);
 501         if utf8_is_cont_byte(y) {
 502             let x = unwrap_or_0(bytes.next_back());
 503             ch = utf8_first_byte(x, 4);
 504             ch = utf8_acc_cont_byte(ch, y);
 505         }
 506         ch = utf8_acc_cont_byte(ch, z);
 507     }
 508     ch = utf8_acc_cont_byte(ch, w);
 509
 510     Some(ch)
 511 }
 512
 513 #[stable(feature = "rust1", since = "1.0.0")]
 514 impl<'a> Iterator for Chars<'a> {
 515     type Item = char;
 516
 517     #[inline]
 518     fn next(&mut self) -> Option<char> {
 519         next_code_point(&mut self.iter).map(|ch| {
 520             // str invariant says `ch` is a valid Unicode Scalar Value
 521             unsafe {
 522                 char::from_u32_unchecked(ch)
 523             }
 524         })
 525     }
 526
 527     #[inline]
 528     fn count(self) -> usize {
 529         // length in `char` is equal to the number of non-continuation bytes
 530         let bytes_len = self.iter.len();
 531         let mut cont_bytes = 0;
 532         for &byte in self.iter {
 533             cont_bytes += utf8_is_cont_byte(byte) as usize;
 534         }
 535         bytes_len - cont_bytes
 536     }
 537
 538     #[inline]
 539     fn size_hint(&self) -> (usize, Option<usize>) {
 540         let len = self.iter.len();
 541         // `(len + 3)` can't overflow, because we know that the `slice::Iter`
 542         // belongs to a slice in memory which has a maximum length of
 543         // `isize::MAX` (that's well below `usize::MAX`).
 544         ((len + 3) / 4, Some(len))
 545     }
 546
 547     #[inline]
 548     fn last(mut self) -> Option<char> {
 549         // No need to go through the entire string.
 550         self.next_back()
 551     }
 552 }
 553
 554 #[stable(feature = "rust1", since = "1.0.0")]
 555 impl<'a> DoubleEndedIterator for Chars<'a> {
 556     #[inline]
 557     fn next_back(&mut self) -> Option<char> {
 558         next_code_point_reverse(&mut self.iter).map(|ch| {
 559             // str invariant says `ch` is a valid Unicode Scalar Value
 560             unsafe {
 561                 char::from_u32_unchecked(ch)
 562             }
 563         })
 564     }
 565 }
 566
 567 #[unstable(feature = "fused", issue = "35602")]
 568 impl<'a> FusedIterator for Chars<'a> {}
 569
 570 impl<'a> Chars<'a> {
 571     /// View the underlying data as a subslice of the original data.
 572     ///
 573     /// This has the same lifetime as the original slice, and so the
 574     /// iterator can continue to be used while this exists.
 575     ///
 576     /// # Examples
 577     ///
 578     /// ```
 579     /// let mut chars = "abc".chars();
 580     ///
 581     /// assert_eq!(chars.as_str(), "abc");
 582     /// chars.next();
 583     /// assert_eq!(chars.as_str(), "bc");
 584     /// chars.next();
 585     /// chars.next();
 586     /// assert_eq!(chars.as_str(), "");
 587     /// ```
 588     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 589     #[inline]
 590     pub fn as_str(&self) -> &'a str {
 591         unsafe { from_utf8_unchecked(self.iter.as_slice()) }
 592     }
 593 }
 594
 595 /// An iterator over the [`char`]s of a string slice, and their positions.
 596 ///
 597 /// [`char`]: ../../std/primitive.char.html
 598 ///
 599 /// This struct is created by the [`char_indices`] method on [`str`].
 600 /// See its documentation for more.
 601 ///
 602 /// [`char_indices`]: ../../std/primitive.str.html#method.char_indices
 603 /// [`str`]: ../../std/primitive.str.html
 604 #[derive(Clone, Debug)]
 605 #[stable(feature = "rust1", since = "1.0.0")]
 606 pub struct CharIndices<'a> {
 607     front_offset: usize,
 608     iter: Chars<'a>,
 609 }
 610
 611 #[stable(feature = "rust1", since = "1.0.0")]
 612 impl<'a> Iterator for CharIndices<'a> {
 613     type Item = (usize, char);
 614
 615     #[inline]
 616     fn next(&mut self) -> Option<(usize, char)> {
 617         let pre_len = self.iter.iter.len();
 618         match self.iter.next() {
 619             None => None,
 620             Some(ch) => {
 621                 let index = self.front_offset;
 622                 let len = self.iter.iter.len();
 623                 self.front_offset += pre_len - len;
 624                 Some((index, ch))
 625             }
 626         }
 627     }
 628
 629     #[inline]
 630     fn count(self) -> usize {
 631         self.iter.count()
 632     }
 633
 634     #[inline]
 635     fn size_hint(&self) -> (usize, Option<usize>) {
 636         self.iter.size_hint()
 637     }
 638
 639     #[inline]
 640     fn last(mut self) -> Option<(usize, char)> {
 641         // No need to go through the entire string.
 642         self.next_back()
 643     }
 644 }
 645
 646 #[stable(feature = "rust1", since = "1.0.0")]
 647 impl<'a> DoubleEndedIterator for CharIndices<'a> {
 648     #[inline]
 649     fn next_back(&mut self) -> Option<(usize, char)> {
 650         match self.iter.next_back() {
 651             None => None,
 652             Some(ch) => {
 653                 let index = self.front_offset + self.iter.iter.len();
 654                 Some((index, ch))
 655             }
 656         }
 657     }
 658 }
 659
 660 #[unstable(feature = "fused", issue = "35602")]
 661 impl<'a> FusedIterator for CharIndices<'a> {}
 662
 663 impl<'a> CharIndices<'a> {
 664     /// View the underlying data as a subslice of the original data.
 665     ///
 666     /// This has the same lifetime as the original slice, and so the
 667     /// iterator can continue to be used while this exists.
 668     #[stable(feature = "iter_to_slice", since = "1.4.0")]
 669     #[inline]
 670     pub fn as_str(&self) -> &'a str {
 671         self.iter.as_str()
 672     }
 673 }
 674
 675 /// An iterator over the bytes of a string slice.
 676 ///
 677 /// This struct is created by the [`bytes`] method on [`str`].
 678 /// See its documentation for more.
 679 ///
 680 /// [`bytes`]: ../../std/primitive.str.html#method.bytes
 681 /// [`str`]: ../../std/primitive.str.html
 682 #[stable(feature = "rust1", since = "1.0.0")]
 683 #[derive(Clone, Debug)]
 684 pub struct Bytes<'a>(Cloned<slice::Iter<'a, u8>>);
 685
 686 #[stable(feature = "rust1", since = "1.0.0")]
 687 impl<'a> Iterator for Bytes<'a> {
 688     type Item = u8;
 689
 690     #[inline]
 691     fn next(&mut self) -> Option<u8> {
 692         self.0.next()
 693     }
 694
 695     #[inline]
 696     fn size_hint(&self) -> (usize, Option<usize>) {
 697         self.0.size_hint()
 698     }
 699
 700     #[inline]
 701     fn count(self) -> usize {
 702         self.0.count()
 703     }
 704
 705     #[inline]
 706     fn last(self) -> Option<Self::Item> {
 707         self.0.last()
 708     }
 709
 710     #[inline]
 711     fn nth(&mut self, n: usize) -> Option<Self::Item> {
 712         self.0.nth(n)
 713     }
 714
 715     #[inline]
 716     fn all<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 717         self.0.all(f)
 718     }
 719
 720     #[inline]
 721     fn any<F>(&mut self, f: F) -> bool where F: FnMut(Self::Item) -> bool {
 722         self.0.any(f)
 723     }
 724
 725     #[inline]
 726     fn find<P>(&mut self, predicate: P) -> Option<Self::Item> where
 727         P: FnMut(&Self::Item) -> bool
 728     {
 729         self.0.find(predicate)
 730     }
 731
 732     #[inline]
 733     fn position<P>(&mut self, predicate: P) -> Option<usize> where
 734         P: FnMut(Self::Item) -> bool
 735     {
 736         self.0.position(predicate)
 737     }
 738
 739     #[inline]
 740     fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
 741         P: FnMut(Self::Item) -> bool
 742     {
 743         self.0.rposition(predicate)
 744     }
 745 }
 746
 747 #[stable(feature = "rust1", since = "1.0.0")]
 748 impl<'a> DoubleEndedIterator for Bytes<'a> {
 749     #[inline]
 750     fn next_back(&mut self) -> Option<u8> {
 751         self.0.next_back()
 752     }
 753
 754     #[inline]
 755     fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item> where
 756         P: FnMut(&Self::Item) -> bool
 757     {
 758         self.0.rfind(predicate)
 759     }
 760 }
 761
 762 #[stable(feature = "rust1", since = "1.0.0")]
 763 impl<'a> ExactSizeIterator for Bytes<'a> {
 764     #[inline]
 765     fn len(&self) -> usize {
 766         self.0.len()
 767     }
 768
 769     #[inline]
 770     fn is_empty(&self) -> bool {
 771         self.0.is_empty()
 772     }
 773 }
 774
 775 #[unstable(feature = "fused", issue = "35602")]
 776 impl<'a> FusedIterator for Bytes<'a> {}
 777
 778 /// This macro generates a Clone impl for string pattern API
 779 /// wrapper types of the form X<'a, P>
 780 macro_rules! derive_pattern_clone {
 781     (clone $t:ident with |$s:ident| $e:expr) => {
 782         impl<'a, P: Pattern<'a>> Clone for $t<'a, P>
 783             where P::Searcher: Clone
 784         {
 785             fn clone(&self) -> Self {
 786                 let $s = self;
 787                 $e
 788             }
 789         }
 790     }
 791 }
 792
 793 /// This macro generates two public iterator structs
 794 /// wrapping a private internal one that makes use of the `Pattern` API.
 795 ///
 796 /// For all patterns `P: Pattern<'a>` the following items will be
 797 /// generated (generics omitted):
 798 ///
 799 /// struct $forward_iterator($internal_iterator);
 800 /// struct $reverse_iterator($internal_iterator);
 801 ///
 802 /// impl Iterator for $forward_iterator
 803 /// { /* internal ends up calling Searcher::next_match() */ }
 804 ///
 805 /// impl DoubleEndedIterator for $forward_iterator
 806 ///       where P::Searcher: DoubleEndedSearcher
 807 /// { /* internal ends up calling Searcher::next_match_back() */ }
 808 ///
 809 /// impl Iterator for $reverse_iterator
 810 ///       where P::Searcher: ReverseSearcher
 811 /// { /* internal ends up calling Searcher::next_match_back() */ }
 812 ///
 813 /// impl DoubleEndedIterator for $reverse_iterator
 814 ///       where P::Searcher: DoubleEndedSearcher
 815 /// { /* internal ends up calling Searcher::next_match() */ }
 816 ///
 817 /// The internal one is defined outside the macro, and has almost the same
 818 /// semantic as a DoubleEndedIterator by delegating to `pattern::Searcher` and
 819 /// `pattern::ReverseSearcher` for both forward and reverse iteration.
 820 ///
 821 /// "Almost", because a `Searcher` and a `ReverseSearcher` for a given
 822 /// `Pattern` might not return the same elements, so actually implementing
 823 /// `DoubleEndedIterator` for it would be incorrect.
 824 /// (See the docs in `str::pattern` for more details)
 825 ///
 826 /// However, the internal struct still represents a single ended iterator from
 827 /// either end, and depending on pattern is also a valid double ended iterator,
 828 /// so the two wrapper structs implement `Iterator`
 829 /// and `DoubleEndedIterator` depending on the concrete pattern type, leading
 830 /// to the complex impls seen above.
 831 macro_rules! generate_pattern_iterators {
 832     {
 833         // Forward iterator
 834         forward:
 835             $(#[$forward_iterator_attribute:meta])*
 836             struct $forward_iterator:ident;
 837
 838         // Reverse iterator
 839         reverse:
 840             $(#[$reverse_iterator_attribute:meta])*
 841             struct $reverse_iterator:ident;
 842
 843         // Stability of all generated items
 844         stability:
 845             $(#[$common_stability_attribute:meta])*
 846
 847         // Internal almost-iterator that is being delegated to
 848         internal:
 849             $internal_iterator:ident yielding ($iterty:ty);
 850
 851         // Kind of delegation - either single ended or double ended
 852         delegate $($t:tt)*
 853     } => {
 854         $(#[$forward_iterator_attribute])*
 855         $(#[$common_stability_attribute])*
 856         pub struct $forward_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 857
 858         $(#[$common_stability_attribute])*
 859         impl<'a, P: Pattern<'a>> fmt::Debug for $forward_iterator<'a, P>
 860             where P::Searcher: fmt::Debug
 861         {
 862             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 863                 f.debug_tuple(stringify!($forward_iterator))
 864                     .field(&self.0)
 865                     .finish()
 866             }
 867         }
 868
 869         $(#[$common_stability_attribute])*
 870         impl<'a, P: Pattern<'a>> Iterator for $forward_iterator<'a, P> {
 871             type Item = $iterty;
 872
 873             #[inline]
 874             fn next(&mut self) -> Option<$iterty> {
 875                 self.0.next()
 876             }
 877         }
 878
 879         $(#[$common_stability_attribute])*
 880         impl<'a, P: Pattern<'a>> Clone for $forward_iterator<'a, P>
 881             where P::Searcher: Clone
 882         {
 883             fn clone(&self) -> Self {
 884                 $forward_iterator(self.0.clone())
 885             }
 886         }
 887
 888         $(#[$reverse_iterator_attribute])*
 889         $(#[$common_stability_attribute])*
 890         pub struct $reverse_iterator<'a, P: Pattern<'a>>($internal_iterator<'a, P>);
 891
 892         $(#[$common_stability_attribute])*
 893         impl<'a, P: Pattern<'a>> fmt::Debug for $reverse_iterator<'a, P>
 894             where P::Searcher: fmt::Debug
 895         {
 896             fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 897                 f.debug_tuple(stringify!($reverse_iterator))
 898                     .field(&self.0)
 899                     .finish()
 900             }
 901         }
 902
 903         $(#[$common_stability_attribute])*
 904         impl<'a, P: Pattern<'a>> Iterator for $reverse_iterator<'a, P>
 905             where P::Searcher: ReverseSearcher<'a>
 906         {
 907             type Item = $iterty;
 908
 909             #[inline]
 910             fn next(&mut self) -> Option<$iterty> {
 911                 self.0.next_back()
 912             }
 913         }
 914
 915         $(#[$common_stability_attribute])*
 916         impl<'a, P: Pattern<'a>> Clone for $reverse_iterator<'a, P>
 917             where P::Searcher: Clone
 918         {
 919             fn clone(&self) -> Self {
 920                 $reverse_iterator(self.0.clone())
 921             }
 922         }
 923
 924         #[unstable(feature = "fused", issue = "35602")]
 925         impl<'a, P: Pattern<'a>> FusedIterator for $forward_iterator<'a, P> {}
 926
 927         #[unstable(feature = "fused", issue = "35602")]
 928         impl<'a, P: Pattern<'a>> FusedIterator for $reverse_iterator<'a, P>
 929             where P::Searcher: ReverseSearcher<'a> {}
 930
 931         generate_pattern_iterators!($($t)* with $(#[$common_stability_attribute])*,
 932                                                 $forward_iterator,
 933                                                 $reverse_iterator, $iterty);
 934     };
 935     {
 936         double ended; with $(#[$common_stability_attribute:meta])*,
 937                            $forward_iterator:ident,
 938                            $reverse_iterator:ident, $iterty:ty
 939     } => {
 940         $(#[$common_stability_attribute])*
 941         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $forward_iterator<'a, P>
 942             where P::Searcher: DoubleEndedSearcher<'a>
 943         {
 944             #[inline]
 945             fn next_back(&mut self) -> Option<$iterty> {
 946                 self.0.next_back()
 947             }
 948         }
 949
 950         $(#[$common_stability_attribute])*
 951         impl<'a, P: Pattern<'a>> DoubleEndedIterator for $reverse_iterator<'a, P>
 952             where P::Searcher: DoubleEndedSearcher<'a>
 953         {
 954             #[inline]
 955             fn next_back(&mut self) -> Option<$iterty> {
 956                 self.0.next()
 957             }
 958         }
 959     };
 960     {
 961         single ended; with $(#[$common_stability_attribute:meta])*,
 962                            $forward_iterator:ident,
 963                            $reverse_iterator:ident, $iterty:ty
 964     } => {}
 965 }
 966
 967 derive_pattern_clone!{
 968     clone SplitInternal
 969     with |s| SplitInternal { matcher: s.matcher.clone(), ..*s }
 970 }
 971
 972 struct SplitInternal<'a, P: Pattern<'a>> {
 973     start: usize,
 974     end: usize,
 975     matcher: P::Searcher,
 976     allow_trailing_empty: bool,
 977     finished: bool,
 978 }
 979
 980 impl<'a, P: Pattern<'a>> fmt::Debug for SplitInternal<'a, P> where P::Searcher: fmt::Debug {
 981     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 982         f.debug_struct("SplitInternal")
 983             .field("start", &self.start)
 984             .field("end", &self.end)
 985             .field("matcher", &self.matcher)
 986             .field("allow_trailing_empty", &self.allow_trailing_empty)
 987             .field("finished", &self.finished)
 988             .finish()
 989     }
 990 }
 991
 992 impl<'a, P: Pattern<'a>> SplitInternal<'a, P> {
 993     #[inline]
 994     fn get_end(&mut self) -> Option<&'a str> {
 995         if !self.finished && (self.allow_trailing_empty || self.end - self.start > 0) {
 996             self.finished = true;
 997             unsafe {
 998                 let string = self.matcher.haystack().slice_unchecked(self.start, self.end);
 999                 Some(string)
1000             }
1001         } else {
1002             None
1003         }
1004     }
1005
1006     #[inline]
1007     fn next(&mut self) -> Option<&'a str> {
1008         if self.finished { return None }
1009
1010         let haystack = self.matcher.haystack();
1011         match self.matcher.next_match() {
1012             Some((a, b)) => unsafe {
1013                 let elt = haystack.slice_unchecked(self.start, a);
1014                 self.start = b;
1015                 Some(elt)
1016             },
1017             None => self.get_end(),
1018         }
1019     }
1020
1021     #[inline]
1022     fn next_back(&mut self) -> Option<&'a str>
1023         where P::Searcher: ReverseSearcher<'a>
1024     {
1025         if self.finished { return None }
1026
1027         if !self.allow_trailing_empty {
1028             self.allow_trailing_empty = true;
1029             match self.next_back() {
1030                 Some(elt) if !elt.is_empty() => return Some(elt),
1031                 _ => if self.finished { return None }
1032             }
1033         }
1034
1035         let haystack = self.matcher.haystack();
1036         match self.matcher.next_match_back() {
1037             Some((a, b)) => unsafe {
1038                 let elt = haystack.slice_unchecked(b, self.end);
1039                 self.end = a;
1040                 Some(elt)
1041             },
1042             None => unsafe {
1043                 self.finished = true;
1044                 Some(haystack.slice_unchecked(self.start, self.end))
1045             },
1046         }
1047     }
1048 }
1049
1050 generate_pattern_iterators! {
1051     forward:
1052         /// Created with the method [`split`].
1053         ///
1054         /// [`split`]: ../../std/primitive.str.html#method.split
1055         struct Split;
1056     reverse:
1057         /// Created with the method [`rsplit`].
1058         ///
1059         /// [`rsplit`]: ../../std/primitive.str.html#method.rsplit
1060         struct RSplit;
1061     stability:
1062         #[stable(feature = "rust1", since = "1.0.0")]
1063     internal:
1064         SplitInternal yielding (&'a str);
1065     delegate double ended;
1066 }
1067
1068 generate_pattern_iterators! {
1069     forward:
1070         /// Created with the method [`split_terminator`].
1071         ///
1072         /// [`split_terminator`]: ../../std/primitive.str.html#method.split_terminator
1073         struct SplitTerminator;
1074     reverse:
1075         /// Created with the method [`rsplit_terminator`].
1076         ///
1077         /// [`rsplit_terminator`]: ../../std/primitive.str.html#method.rsplit_terminator
1078         struct RSplitTerminator;
1079     stability:
1080         #[stable(feature = "rust1", since = "1.0.0")]
1081     internal:
1082         SplitInternal yielding (&'a str);
1083     delegate double ended;
1084 }
1085
1086 derive_pattern_clone!{
1087     clone SplitNInternal
1088     with |s| SplitNInternal { iter: s.iter.clone(), ..*s }
1089 }
1090
1091 struct SplitNInternal<'a, P: Pattern<'a>> {
1092     iter: SplitInternal<'a, P>,
1093     /// The number of splits remaining
1094     count: usize,
1095 }
1096
1097 impl<'a, P: Pattern<'a>> fmt::Debug for SplitNInternal<'a, P> where P::Searcher: fmt::Debug {
1098     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1099         f.debug_struct("SplitNInternal")
1100             .field("iter", &self.iter)
1101             .field("count", &self.count)
1102             .finish()
1103     }
1104 }
1105
1106 impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> {
1107     #[inline]
1108     fn next(&mut self) -> Option<&'a str> {
1109         match self.count {
1110             0 => None,
1111             1 => { self.count = 0; self.iter.get_end() }
1112             _ => { self.count -= 1; self.iter.next() }
1113         }
1114     }
1115
1116     #[inline]
1117     fn next_back(&mut self) -> Option<&'a str>
1118         where P::Searcher: ReverseSearcher<'a>
1119     {
1120         match self.count {
1121             0 => None,
1122             1 => { self.count = 0; self.iter.get_end() }
1123             _ => { self.count -= 1; self.iter.next_back() }
1124         }
1125     }
1126 }
1127
1128 generate_pattern_iterators! {
1129     forward:
1130         /// Created with the method [`splitn`].
1131         ///
1132         /// [`splitn`]: ../../std/primitive.str.html#method.splitn
1133         struct SplitN;
1134     reverse:
1135         /// Created with the method [`rsplitn`].
1136         ///
1137         /// [`rsplitn`]: ../../std/primitive.str.html#method.rsplitn
1138         struct RSplitN;
1139     stability:
1140         #[stable(feature = "rust1", since = "1.0.0")]
1141     internal:
1142         SplitNInternal yielding (&'a str);
1143     delegate single ended;
1144 }
1145
1146 derive_pattern_clone!{
1147     clone MatchIndicesInternal
1148     with |s| MatchIndicesInternal(s.0.clone())
1149 }
1150
1151 struct MatchIndicesInternal<'a, P: Pattern<'a>>(P::Searcher);
1152
1153 impl<'a, P: Pattern<'a>> fmt::Debug for MatchIndicesInternal<'a, P> where P::Searcher: fmt::Debug {
1154     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1155         f.debug_tuple("MatchIndicesInternal")
1156             .field(&self.0)
1157             .finish()
1158     }
1159 }
1160
1161 impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> {
1162     #[inline]
1163     fn next(&mut self) -> Option<(usize, &'a str)> {
1164         self.0.next_match().map(|(start, end)| unsafe {
1165             (start, self.0.haystack().slice_unchecked(start, end))
1166         })
1167     }
1168
1169     #[inline]
1170     fn next_back(&mut self) -> Option<(usize, &'a str)>
1171         where P::Searcher: ReverseSearcher<'a>
1172     {
1173         self.0.next_match_back().map(|(start, end)| unsafe {
1174             (start, self.0.haystack().slice_unchecked(start, end))
1175         })
1176     }
1177 }
1178
1179 generate_pattern_iterators! {
1180     forward:
1181         /// Created with the method [`match_indices`].
1182         ///
1183         /// [`match_indices`]: ../../std/primitive.str.html#method.match_indices
1184         struct MatchIndices;
1185     reverse:
1186         /// Created with the method [`rmatch_indices`].
1187         ///
1188         /// [`rmatch_indices`]: ../../std/primitive.str.html#method.rmatch_indices
1189         struct RMatchIndices;
1190     stability:
1191         #[stable(feature = "str_match_indices", since = "1.5.0")]
1192     internal:
1193         MatchIndicesInternal yielding ((usize, &'a str));
1194     delegate double ended;
1195 }
1196
1197 derive_pattern_clone!{
1198     clone MatchesInternal
1199     with |s| MatchesInternal(s.0.clone())
1200 }
1201
1202 struct MatchesInternal<'a, P: Pattern<'a>>(P::Searcher);
1203
1204 impl<'a, P: Pattern<'a>> fmt::Debug for MatchesInternal<'a, P> where P::Searcher: fmt::Debug {
1205     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1206         f.debug_tuple("MatchesInternal")
1207             .field(&self.0)
1208             .finish()
1209     }
1210 }
1211
1212 impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> {
1213     #[inline]
1214     fn next(&mut self) -> Option<&'a str> {
1215         self.0.next_match().map(|(a, b)| unsafe {
1216             // Indices are known to be on utf8 boundaries
1217             self.0.haystack().slice_unchecked(a, b)
1218         })
1219     }
1220
1221     #[inline]
1222     fn next_back(&mut self) -> Option<&'a str>
1223         where P::Searcher: ReverseSearcher<'a>
1224     {
1225         self.0.next_match_back().map(|(a, b)| unsafe {
1226             // Indices are known to be on utf8 boundaries
1227             self.0.haystack().slice_unchecked(a, b)
1228         })
1229     }
1230 }
1231
1232 generate_pattern_iterators! {
1233     forward:
1234         /// Created with the method [`matches`].
1235         ///
1236         /// [`matches`]: ../../std/primitive.str.html#method.matches
1237         struct Matches;
1238     reverse:
1239         /// Created with the method [`rmatches`].
1240         ///
1241         /// [`rmatches`]: ../../std/primitive.str.html#method.rmatches
1242         struct RMatches;
1243     stability:
1244         #[stable(feature = "str_matches", since = "1.2.0")]
1245     internal:
1246         MatchesInternal yielding (&'a str);
1247     delegate double ended;
1248 }
1249
1250 /// An iterator over the lines of a string, as string slices.
1251 ///
1252 /// This struct is created with the [`lines`] method on [`str`].
1253 /// See its documentation for more.
1254 ///
1255 /// [`lines`]: ../../std/primitive.str.html#method.lines
1256 /// [`str`]: ../../std/primitive.str.html
1257 #[stable(feature = "rust1", since = "1.0.0")]
1258 #[derive(Clone, Debug)]
1259 pub struct Lines<'a>(Map<SplitTerminator<'a, char>, LinesAnyMap>);
1260
1261 #[stable(feature = "rust1", since = "1.0.0")]
1262 impl<'a> Iterator for Lines<'a> {
1263     type Item = &'a str;
1264
1265     #[inline]
1266     fn next(&mut self) -> Option<&'a str> {
1267         self.0.next()
1268     }
1269
1270     #[inline]
1271     fn size_hint(&self) -> (usize, Option<usize>) {
1272         self.0.size_hint()
1273     }
1274 }
1275
1276 #[stable(feature = "rust1", since = "1.0.0")]
1277 impl<'a> DoubleEndedIterator for Lines<'a> {
1278     #[inline]
1279     fn next_back(&mut self) -> Option<&'a str> {
1280         self.0.next_back()
1281     }
1282 }
1283
1284 #[unstable(feature = "fused", issue = "35602")]
1285 impl<'a> FusedIterator for Lines<'a> {}
1286
1287 /// Created with the method [`lines_any`].
1288 ///
1289 /// [`lines_any`]: ../../std/primitive.str.html#method.lines_any
1290 #[stable(feature = "rust1", since = "1.0.0")]
1291 #[rustc_deprecated(since = "1.4.0", reason = "use lines()/Lines instead now")]
1292 #[derive(Clone, Debug)]
1293 #[allow(deprecated)]
1294 pub struct LinesAny<'a>(Lines<'a>);
1295
1296 /// A nameable, cloneable fn type
1297 #[derive(Clone)]
1298 struct LinesAnyMap;
1299
1300 impl<'a> Fn<(&'a str,)> for LinesAnyMap {
1301     #[inline]
1302     extern "rust-call" fn call(&self, (line,): (&'a str,)) -> &'a str {
1303         let l = line.len();
1304         if l > 0 && line.as_bytes()[l - 1] == b'\r' { &line[0 .. l - 1] }
1305         else { line }
1306     }
1307 }
1308
1309 impl<'a> FnMut<(&'a str,)> for LinesAnyMap {
1310     #[inline]
1311     extern "rust-call" fn call_mut(&mut self, (line,): (&'a str,)) -> &'a str {
1312         Fn::call(&*self, (line,))
1313     }
1314 }
1315
1316 impl<'a> FnOnce<(&'a str,)> for LinesAnyMap {
1317     type Output = &'a str;
1318
1319     #[inline]
1320     extern "rust-call" fn call_once(self, (line,): (&'a str,)) -> &'a str {
1321         Fn::call(&self, (line,))
1322     }
1323 }
1324
1325 #[stable(feature = "rust1", since = "1.0.0")]
1326 #[allow(deprecated)]
1327 impl<'a> Iterator for LinesAny<'a> {
1328     type Item = &'a str;
1329
1330     #[inline]
1331     fn next(&mut self) -> Option<&'a str> {
1332         self.0.next()
1333     }
1334
1335     #[inline]
1336     fn size_hint(&self) -> (usize, Option<usize>) {
1337         self.0.size_hint()
1338     }
1339 }
1340
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 #[allow(deprecated)]
1343 impl<'a> DoubleEndedIterator for LinesAny<'a> {
1344     #[inline]
1345     fn next_back(&mut self) -> Option<&'a str> {
1346         self.0.next_back()
1347     }
1348 }
1349
1350 #[unstable(feature = "fused", issue = "35602")]
1351 #[allow(deprecated)]
1352 impl<'a> FusedIterator for LinesAny<'a> {}
1353
1354 /*
1355 Section: Comparing strings
1356 */
1357
1358 /// Bytewise slice equality
1359 /// NOTE: This function is (ab)used in rustc::middle::trans::_match
1360 /// to compare &[u8] byte slices that are not necessarily valid UTF-8.
1361 #[lang = "str_eq"]
1362 #[inline]
1363 fn eq_slice(a: &str, b: &str) -> bool {
1364     a.as_bytes() == b.as_bytes()
1365 }
1366
1367 /*
1368 Section: UTF-8 validation
1369 */
1370
1371 // use truncation to fit u64 into usize
1372 const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;
1373
1374 /// Returns `true` if any byte in the word `x` is nonascii (>= 128).
1375 #[inline]
1376 fn contains_nonascii(x: usize) -> bool {
1377     (x & NONASCII_MASK) != 0
1378 }
1379
1380 /// Walks through `iter` checking that it's a valid UTF-8 sequence,
1381 /// returning `true` in that case, or, if it is invalid, `false` with
1382 /// `iter` reset such that it is pointing at the first byte in the
1383 /// invalid sequence.
1384 #[inline]
1385 fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
1386     let mut index = 0;
1387     let len = v.len();
1388
1389     let usize_bytes = mem::size_of::<usize>();
1390     let ascii_block_size = 2 * usize_bytes;
1391     let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
1392
1393     while index < len {
1394         let old_offset = index;
1395         macro_rules! err {
1396             ($error_len: expr) => {
1397                 return Err(Utf8Error {
1398                     valid_up_to: old_offset,
1399                     error_len: $error_len,
1400                 })
1401             }
1402         }
1403
1404         macro_rules! next { () => {{
1405             index += 1;
1406             // we needed data, but there was none: error!
1407             if index >= len {
1408                 err!(None)
1409             }
1410             v[index]
1411         }}}
1412
1413         let first = v[index];
1414         if first >= 128 {
1415             let w = UTF8_CHAR_WIDTH[first as usize];
1416             // 2-byte encoding is for codepoints  \u{0080} to  \u{07ff}
1417             //        first  C2 80        last DF BF
1418             // 3-byte encoding is for codepoints  \u{0800} to  \u{ffff}
1419             //        first  E0 A0 80     last EF BF BF
1420             //   excluding surrogates codepoints  \u{d800} to  \u{dfff}
1421             //               ED A0 80 to       ED BF BF
1422             // 4-byte encoding is for codepoints \u{1000}0 to \u{10ff}ff
1423             //        first  F0 90 80 80  last F4 8F BF BF
1424             //
1425             // Use the UTF-8 syntax from the RFC
1426             //
1427             // https://tools.ietf.org/html/rfc3629
1428             // UTF8-1      = %x00-7F
1429             // UTF8-2      = %xC2-DF UTF8-tail
1430             // UTF8-3      = %xE0 %xA0-BF UTF8-tail / %xE1-EC 2( UTF8-tail ) /
1431             //               %xED %x80-9F UTF8-tail / %xEE-EF 2( UTF8-tail )
1432             // UTF8-4      = %xF0 %x90-BF 2( UTF8-tail ) / %xF1-F3 3( UTF8-tail ) /
1433             //               %xF4 %x80-8F 2( UTF8-tail )
1434             match w {
1435                 2 => if next!() & !CONT_MASK != TAG_CONT_U8 {
1436                     err!(Some(1))
1437                 },
1438                 3 => {
1439                     match (first, next!()) {
1440                         (0xE0         , 0xA0 ... 0xBF) |
1441                         (0xE1 ... 0xEC, 0x80 ... 0xBF) |
1442                         (0xED         , 0x80 ... 0x9F) |
1443                         (0xEE ... 0xEF, 0x80 ... 0xBF) => {}
1444                         _ => err!(Some(1))
1445                     }
1446                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1447                         err!(Some(2))
1448                     }
1449                 }
1450                 4 => {
1451                     match (first, next!()) {
1452                         (0xF0         , 0x90 ... 0xBF) |
1453                         (0xF1 ... 0xF3, 0x80 ... 0xBF) |
1454                         (0xF4         , 0x80 ... 0x8F) => {}
1455                         _ => err!(Some(1))
1456                     }
1457                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1458                         err!(Some(2))
1459                     }
1460                     if next!() & !CONT_MASK != TAG_CONT_U8 {
1461                         err!(Some(3))
1462                     }
1463                 }
1464                 _ => err!(Some(1))
1465             }
1466             index += 1;
1467         } else {
1468             // Ascii case, try to skip forward quickly.
1469             // When the pointer is aligned, read 2 words of data per iteration
1470             // until we find a word containing a non-ascii byte.
1471             let ptr = v.as_ptr();
1472             let align = unsafe {
1473                 // the offset is safe, because `index` is guaranteed inbounds
1474                 align_offset(ptr.offset(index as isize) as *const (), usize_bytes)
1475             };
1476             if align == 0 {
1477                 while index < blocks_end {
1478                     unsafe {
1479                         let block = ptr.offset(index as isize) as *const usize;
1480                         // break if there is a nonascii byte
1481                         let zu = contains_nonascii(*block);
1482                         let zv = contains_nonascii(*block.offset(1));
1483                         if zu | zv {
1484                             break;
1485                         }
1486                     }
1487                     index += ascii_block_size;
1488                 }
1489                 // step from the point where the wordwise loop stopped
1490                 while index < len && v[index] < 128 {
1491                     index += 1;
1492                 }
1493             } else {
1494                 index += 1;
1495             }
1496         }
1497     }
1498
1499     Ok(())
1500 }
1501
1502 // https://tools.ietf.org/html/rfc3629
1503 static UTF8_CHAR_WIDTH: [u8; 256] = [
1504 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1505 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x1F
1506 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1507 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x3F
1508 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1509 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x5F
1510 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1511 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, // 0x7F
1512 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1513 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0x9F
1514 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1515 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // 0xBF
1516 0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
1517 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, // 0xDF
1518 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, // 0xEF
1519 4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0, // 0xFF
1520 ];
1521
1522 /// Given a first byte, determines how many bytes are in this UTF-8 character.
1523 #[unstable(feature = "str_internals", issue = "0")]
1524 #[inline]
1525 pub fn utf8_char_width(b: u8) -> usize {
1526     return UTF8_CHAR_WIDTH[b as usize] as usize;
1527 }
1528
1529 /// Mask of the value bits of a continuation byte.
1530 const CONT_MASK: u8 = 0b0011_1111;
1531 /// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte.
1532 const TAG_CONT_U8: u8 = 0b1000_0000;
1533
1534 /*
1535 Section: Trait implementations
1536 */
1537
1538 mod traits {
1539     use cmp::Ordering;
1540     use ops;
1541     use slice::{self, SliceIndex};
1542     use str::eq_slice;
1543
1544     /// Implements ordering of strings.
1545     ///
1546     /// Strings are ordered  lexicographically by their byte values.  This orders Unicode code
1547     /// points based on their positions in the code charts.  This is not necessarily the same as
1548     /// "alphabetical" order, which varies by language and locale.  Sorting strings according to
1549     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1550     /// the `str` type.
1551     #[stable(feature = "rust1", since = "1.0.0")]
1552     impl Ord for str {
1553         #[inline]
1554         fn cmp(&self, other: &str) -> Ordering {
1555             self.as_bytes().cmp(other.as_bytes())
1556         }
1557     }
1558
1559     #[stable(feature = "rust1", since = "1.0.0")]
1560     impl PartialEq for str {
1561         #[inline]
1562         fn eq(&self, other: &str) -> bool {
1563             eq_slice(self, other)
1564         }
1565         #[inline]
1566         fn ne(&self, other: &str) -> bool { !(*self).eq(other) }
1567     }
1568
1569     #[stable(feature = "rust1", since = "1.0.0")]
1570     impl Eq for str {}
1571
1572     /// Implements comparison operations on strings.
1573     ///
1574     /// Strings are compared lexicographically by their byte values.  This compares Unicode code
1575     /// points based on their positions in the code charts.  This is not necessarily the same as
1576     /// "alphabetical" order, which varies by language and locale.  Comparing strings according to
1577     /// culturally-accepted standards requires locale-specific data that is outside the scope of
1578     /// the `str` type.
1579     #[stable(feature = "rust1", since = "1.0.0")]
1580     impl PartialOrd for str {
1581         #[inline]
1582         fn partial_cmp(&self, other: &str) -> Option<Ordering> {
1583             Some(self.cmp(other))
1584         }
1585     }
1586
1587     /// Implements substring slicing with syntax `&self[begin .. end]`.
1588     ///
1589     /// Returns a slice of the given string from the byte range
1590     /// [`begin`..`end`).
1591     ///
1592     /// This operation is `O(1)`.
1593     ///
1594     /// # Panics
1595     ///
1596     /// Panics if `begin` or `end` does not point to the starting
1597     /// byte offset of a character (as defined by `is_char_boundary`).
1598     /// Requires that `begin <= end` and `end <= len` where `len` is the
1599     /// length of the string.
1600     ///
1601     /// # Examples
1602     ///
1603     /// ```
1604     /// let s = "Löwe 老虎 Léopard";
1605     /// assert_eq!(&s[0 .. 1], "L");
1606     ///
1607     /// assert_eq!(&s[1 .. 9], "öwe 老");
1608     ///
1609     /// // these will panic:
1610     /// // byte 2 lies within `ö`:
1611     /// // &s[2 ..3];
1612     ///
1613     /// // byte 8 lies within `老`
1614     /// // &s[1 .. 8];
1615     ///
1616     /// // byte 100 is outside the string
1617     /// // &s[3 .. 100];
1618     /// ```
1619     #[stable(feature = "rust1", since = "1.0.0")]
1620     impl ops::Index<ops::Range<usize>> for str {
1621         type Output = str;
1622         #[inline]
1623         fn index(&self, index: ops::Range<usize>) -> &str {
1624             index.index(self)
1625         }
1626     }
1627
1628     /// Implements mutable substring slicing with syntax
1629     /// `&mut self[begin .. end]`.
1630     ///
1631     /// Returns a mutable slice of the given string from the byte range
1632     /// [`begin`..`end`).
1633     ///
1634     /// This operation is `O(1)`.
1635     ///
1636     /// # Panics
1637     ///
1638     /// Panics if `begin` or `end` does not point to the starting
1639     /// byte offset of a character (as defined by `is_char_boundary`).
1640     /// Requires that `begin <= end` and `end <= len` where `len` is the
1641     /// length of the string.
1642     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1643     impl ops::IndexMut<ops::Range<usize>> for str {
1644         #[inline]
1645         fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
1646             index.index_mut(self)
1647         }
1648     }
1649
1650     /// Implements substring slicing with syntax `&self[.. end]`.
1651     ///
1652     /// Returns a slice of the string from the beginning to byte offset
1653     /// `end`.
1654     ///
1655     /// Equivalent to `&self[0 .. end]`.
1656     #[stable(feature = "rust1", since = "1.0.0")]
1657     impl ops::Index<ops::RangeTo<usize>> for str {
1658         type Output = str;
1659
1660         #[inline]
1661         fn index(&self, index: ops::RangeTo<usize>) -> &str {
1662             index.index(self)
1663         }
1664     }
1665
1666     /// Implements mutable substring slicing with syntax `&mut self[.. end]`.
1667     ///
1668     /// Returns a mutable slice of the string from the beginning to byte offset
1669     /// `end`.
1670     ///
1671     /// Equivalent to `&mut self[0 .. end]`.
1672     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1673     impl ops::IndexMut<ops::RangeTo<usize>> for str {
1674         #[inline]
1675         fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
1676             index.index_mut(self)
1677         }
1678     }
1679
1680     /// Implements substring slicing with syntax `&self[begin ..]`.
1681     ///
1682     /// Returns a slice of the string from byte offset `begin`
1683     /// to the end of the string.
1684     ///
1685     /// Equivalent to `&self[begin .. len]`.
1686     #[stable(feature = "rust1", since = "1.0.0")]
1687     impl ops::Index<ops::RangeFrom<usize>> for str {
1688         type Output = str;
1689
1690         #[inline]
1691         fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1692             index.index(self)
1693         }
1694     }
1695
1696     /// Implements mutable substring slicing with syntax `&mut self[begin ..]`.
1697     ///
1698     /// Returns a mutable slice of the string from byte offset `begin`
1699     /// to the end of the string.
1700     ///
1701     /// Equivalent to `&mut self[begin .. len]`.
1702     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1703     impl ops::IndexMut<ops::RangeFrom<usize>> for str {
1704         #[inline]
1705         fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
1706             index.index_mut(self)
1707         }
1708     }
1709
1710     /// Implements substring slicing with syntax `&self[..]`.
1711     ///
1712     /// Returns a slice of the whole string. This operation can
1713     /// never panic.
1714     ///
1715     /// Equivalent to `&self[0 .. len]`.
1716     #[stable(feature = "rust1", since = "1.0.0")]
1717     impl ops::Index<ops::RangeFull> for str {
1718         type Output = str;
1719
1720         #[inline]
1721         fn index(&self, _index: ops::RangeFull) -> &str {
1722             self
1723         }
1724     }
1725
1726     /// Implements mutable substring slicing with syntax `&mut self[..]`.
1727     ///
1728     /// Returns a mutable slice of the whole string. This operation can
1729     /// never panic.
1730     ///
1731     /// Equivalent to `&mut self[0 .. len]`.
1732     #[stable(feature = "derefmut_for_string", since = "1.3.0")]
1733     impl ops::IndexMut<ops::RangeFull> for str {
1734         #[inline]
1735         fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
1736             self
1737         }
1738     }
1739
1740     #[unstable(feature = "inclusive_range",
1741                reason = "recently added, follows RFC",
1742                issue = "28237")]
1743     impl ops::Index<ops::RangeInclusive<usize>> for str {
1744         type Output = str;
1745
1746         #[inline]
1747         fn index(&self, index: ops::RangeInclusive<usize>) -> &str {
1748             index.index(self)
1749         }
1750     }
1751
1752     #[unstable(feature = "inclusive_range",
1753                reason = "recently added, follows RFC",
1754                issue = "28237")]
1755     impl ops::Index<ops::RangeToInclusive<usize>> for str {
1756         type Output = str;
1757
1758         #[inline]
1759         fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
1760             index.index(self)
1761         }
1762     }
1763
1764     #[unstable(feature = "inclusive_range",
1765                reason = "recently added, follows RFC",
1766                issue = "28237")]
1767     impl ops::IndexMut<ops::RangeInclusive<usize>> for str {
1768         #[inline]
1769         fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
1770             index.index_mut(self)
1771         }
1772     }
1773     #[unstable(feature = "inclusive_range",
1774                reason = "recently added, follows RFC",
1775                issue = "28237")]
1776     impl ops::IndexMut<ops::RangeToInclusive<usize>> for str {
1777         #[inline]
1778         fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
1779             index.index_mut(self)
1780         }
1781     }
1782
1783     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1784     impl SliceIndex<str> for ops::RangeFull {
1785         type Output = str;
1786         #[inline]
1787         fn get(self, slice: &str) -> Option<&Self::Output> {
1788             Some(slice)
1789         }
1790         #[inline]
1791         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1792             Some(slice)
1793         }
1794         #[inline]
1795         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1796             slice
1797         }
1798         #[inline]
1799         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1800             slice
1801         }
1802         #[inline]
1803         fn index(self, slice: &str) -> &Self::Output {
1804             slice
1805         }
1806         #[inline]
1807         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1808             slice
1809         }
1810     }
1811
1812     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1813     impl SliceIndex<str> for ops::Range<usize> {
1814         type Output = str;
1815         #[inline]
1816         fn get(self, slice: &str) -> Option<&Self::Output> {
1817             if self.start <= self.end &&
1818                slice.is_char_boundary(self.start) &&
1819                slice.is_char_boundary(self.end) {
1820                 Some(unsafe { self.get_unchecked(slice) })
1821             } else {
1822                 None
1823             }
1824         }
1825         #[inline]
1826         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1827             if self.start <= self.end &&
1828                slice.is_char_boundary(self.start) &&
1829                slice.is_char_boundary(self.end) {
1830                 Some(unsafe { self.get_unchecked_mut(slice) })
1831             } else {
1832                 None
1833             }
1834         }
1835         #[inline]
1836         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1837             let ptr = slice.as_ptr().offset(self.start as isize);
1838             let len = self.end - self.start;
1839             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1840         }
1841         #[inline]
1842         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1843             let ptr = slice.as_ptr().offset(self.start as isize);
1844             let len = self.end - self.start;
1845             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1846         }
1847         #[inline]
1848         fn index(self, slice: &str) -> &Self::Output {
1849             let (start, end) = (self.start, self.end);
1850             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1851         }
1852         #[inline]
1853         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1854             // is_char_boundary checks that the index is in [0, .len()]
1855             // canot reuse `get` as above, because of NLL trouble
1856             if self.start <= self.end &&
1857                slice.is_char_boundary(self.start) &&
1858                slice.is_char_boundary(self.end) {
1859                 unsafe { self.get_unchecked_mut(slice) }
1860             } else {
1861                 super::slice_error_fail(slice, self.start, self.end)
1862             }
1863         }
1864     }
1865
1866     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1867     impl SliceIndex<str> for ops::RangeTo<usize> {
1868         type Output = str;
1869         #[inline]
1870         fn get(self, slice: &str) -> Option<&Self::Output> {
1871             if slice.is_char_boundary(self.end) {
1872                 Some(unsafe { self.get_unchecked(slice) })
1873             } else {
1874                 None
1875             }
1876         }
1877         #[inline]
1878         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1879             if slice.is_char_boundary(self.end) {
1880                 Some(unsafe { self.get_unchecked_mut(slice) })
1881             } else {
1882                 None
1883             }
1884         }
1885         #[inline]
1886         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1887             let ptr = slice.as_ptr();
1888             super::from_utf8_unchecked(slice::from_raw_parts(ptr, self.end))
1889         }
1890         #[inline]
1891         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1892             let ptr = slice.as_ptr();
1893             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, self.end))
1894         }
1895         #[inline]
1896         fn index(self, slice: &str) -> &Self::Output {
1897             let end = self.end;
1898             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, 0, end))
1899         }
1900         #[inline]
1901         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1902             // is_char_boundary checks that the index is in [0, .len()]
1903             if slice.is_char_boundary(self.end) {
1904                 unsafe { self.get_unchecked_mut(slice) }
1905             } else {
1906                 super::slice_error_fail(slice, 0, self.end)
1907             }
1908         }
1909     }
1910
1911     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1912     impl SliceIndex<str> for ops::RangeFrom<usize> {
1913         type Output = str;
1914         #[inline]
1915         fn get(self, slice: &str) -> Option<&Self::Output> {
1916             if slice.is_char_boundary(self.start) {
1917                 Some(unsafe { self.get_unchecked(slice) })
1918             } else {
1919                 None
1920             }
1921         }
1922         #[inline]
1923         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1924             if slice.is_char_boundary(self.start) {
1925                 Some(unsafe { self.get_unchecked_mut(slice) })
1926             } else {
1927                 None
1928             }
1929         }
1930         #[inline]
1931         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1932             let ptr = slice.as_ptr().offset(self.start as isize);
1933             let len = slice.len() - self.start;
1934             super::from_utf8_unchecked(slice::from_raw_parts(ptr, len))
1935         }
1936         #[inline]
1937         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1938             let ptr = slice.as_ptr().offset(self.start as isize);
1939             let len = slice.len() - self.start;
1940             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, len))
1941         }
1942         #[inline]
1943         fn index(self, slice: &str) -> &Self::Output {
1944             let (start, end) = (self.start, slice.len());
1945             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, start, end))
1946         }
1947         #[inline]
1948         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1949             // is_char_boundary checks that the index is in [0, .len()]
1950             if slice.is_char_boundary(self.start) {
1951                 unsafe { self.get_unchecked_mut(slice) }
1952             } else {
1953                 super::slice_error_fail(slice, self.start, slice.len())
1954             }
1955         }
1956     }
1957
1958     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
1959     impl SliceIndex<str> for ops::RangeInclusive<usize> {
1960         type Output = str;
1961         #[inline]
1962         fn get(self, slice: &str) -> Option<&Self::Output> {
1963             if let Some(end) = self.end.checked_add(1) {
1964                 (self.start..end).get(slice)
1965             } else {
1966                 None
1967             }
1968         }
1969         #[inline]
1970         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
1971             if let Some(end) = self.end.checked_add(1) {
1972                 (self.start..end).get_mut(slice)
1973             } else {
1974                 None
1975             }
1976         }
1977         #[inline]
1978         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
1979             (self.start..self.end+1).get_unchecked(slice)
1980         }
1981         #[inline]
1982         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
1983             (self.start..self.end+1).get_unchecked_mut(slice)
1984         }
1985         #[inline]
1986         fn index(self, slice: &str) -> &Self::Output {
1987             assert!(self.end != usize::max_value(),
1988                 "attempted to index str up to maximum usize");
1989             (self.start..self.end+1).index(slice)
1990         }
1991         #[inline]
1992         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
1993             assert!(self.end != usize::max_value(),
1994                 "attempted to index str up to maximum usize");
1995             (self.start..self.end+1).index_mut(slice)
1996         }
1997     }
1998
1999
2000
2001     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2002     impl SliceIndex<str> for ops::RangeToInclusive<usize> {
2003         type Output = str;
2004         #[inline]
2005         fn get(self, slice: &str) -> Option<&Self::Output> {
2006             if self.end < usize::max_value() && slice.is_char_boundary(self.end + 1) {
2007                 Some(unsafe { self.get_unchecked(slice) })
2008             } else {
2009                 None
2010             }
2011         }
2012         #[inline]
2013         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
2014             if self.end < usize::max_value() && slice.is_char_boundary(self.end + 1) {
2015                 Some(unsafe { self.get_unchecked_mut(slice) })
2016             } else {
2017                 None
2018             }
2019         }
2020         #[inline]
2021         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
2022             let ptr = slice.as_ptr();
2023             super::from_utf8_unchecked(slice::from_raw_parts(ptr, self.end + 1))
2024         }
2025         #[inline]
2026         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
2027             let ptr = slice.as_ptr();
2028             super::from_utf8_unchecked_mut(slice::from_raw_parts_mut(ptr as *mut u8, self.end + 1))
2029         }
2030         #[inline]
2031         fn index(self, slice: &str) -> &Self::Output {
2032             assert!(self.end != usize::max_value(),
2033                 "attempted to index str up to maximum usize");
2034             let end = self.end + 1;
2035             self.get(slice).unwrap_or_else(|| super::slice_error_fail(slice, 0, end))
2036         }
2037         #[inline]
2038         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
2039             assert!(self.end != usize::max_value(),
2040                 "attempted to index str up to maximum usize");
2041             if slice.is_char_boundary(self.end) {
2042                 unsafe { self.get_unchecked_mut(slice) }
2043             } else {
2044                 super::slice_error_fail(slice, 0, self.end + 1)
2045             }
2046         }
2047     }
2048
2049 }
2050
2051
2052 /// Methods for string slices
2053 #[allow(missing_docs)]
2054 #[doc(hidden)]
2055 #[unstable(feature = "core_str_ext",
2056            reason = "stable interface provided by `impl str` in later crates",
2057            issue = "32110")]
2058 pub trait StrExt {
2059     // NB there are no docs here are they're all located on the StrExt trait in
2060     // liballoc, not here.
2061
2062     #[stable(feature = "core", since = "1.6.0")]
2063     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
2064     #[stable(feature = "core", since = "1.6.0")]
2065     fn chars(&self) -> Chars;
2066     #[stable(feature = "core", since = "1.6.0")]
2067     fn bytes(&self) -> Bytes;
2068     #[stable(feature = "core", since = "1.6.0")]
2069     fn char_indices(&self) -> CharIndices;
2070     #[stable(feature = "core", since = "1.6.0")]
2071     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P>;
2072     #[stable(feature = "core", since = "1.6.0")]
2073     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
2074         where P::Searcher: ReverseSearcher<'a>;
2075     #[stable(feature = "core", since = "1.6.0")]
2076     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P>;
2077     #[stable(feature = "core", since = "1.6.0")]
2078     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
2079         where P::Searcher: ReverseSearcher<'a>;
2080     #[stable(feature = "core", since = "1.6.0")]
2081     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P>;
2082     #[stable(feature = "core", since = "1.6.0")]
2083     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
2084         where P::Searcher: ReverseSearcher<'a>;
2085     #[stable(feature = "core", since = "1.6.0")]
2086     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P>;
2087     #[stable(feature = "core", since = "1.6.0")]
2088     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
2089         where P::Searcher: ReverseSearcher<'a>;
2090     #[stable(feature = "core", since = "1.6.0")]
2091     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P>;
2092     #[stable(feature = "core", since = "1.6.0")]
2093     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
2094         where P::Searcher: ReverseSearcher<'a>;
2095     #[stable(feature = "core", since = "1.6.0")]
2096     fn lines(&self) -> Lines;
2097     #[stable(feature = "core", since = "1.6.0")]
2098     #[rustc_deprecated(since = "1.6.0", reason = "use lines() instead now")]
2099     #[allow(deprecated)]
2100     fn lines_any(&self) -> LinesAny;
2101     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2102     fn get<I: SliceIndex<str>>(&self, i: I) -> Option<&I::Output>;
2103     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2104     fn get_mut<I: SliceIndex<str>>(&mut self, i: I) -> Option<&mut I::Output>;
2105     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2106     unsafe fn get_unchecked<I: SliceIndex<str>>(&self, i: I) -> &I::Output;
2107     #[stable(feature = "str_checked_slicing", since = "1.20.0")]
2108     unsafe fn get_unchecked_mut<I: SliceIndex<str>>(&mut self, i: I) -> &mut I::Output;
2109     #[stable(feature = "core", since = "1.6.0")]
2110     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str;
2111     #[stable(feature = "core", since = "1.6.0")]
2112     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str;
2113     #[stable(feature = "core", since = "1.6.0")]
2114     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool;
2115     #[stable(feature = "core", since = "1.6.0")]
2116     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
2117         where P::Searcher: ReverseSearcher<'a>;
2118     #[stable(feature = "core", since = "1.6.0")]
2119     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2120         where P::Searcher: DoubleEndedSearcher<'a>;
2121     #[stable(feature = "core", since = "1.6.0")]
2122     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str;
2123     #[stable(feature = "core", since = "1.6.0")]
2124     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2125         where P::Searcher: ReverseSearcher<'a>;
2126     #[stable(feature = "is_char_boundary", since = "1.9.0")]
2127     fn is_char_boundary(&self, index: usize) -> bool;
2128     #[stable(feature = "core", since = "1.6.0")]
2129     fn as_bytes(&self) -> &[u8];
2130     #[stable(feature = "str_mut_extras", since = "1.20.0")]
2131     unsafe fn as_bytes_mut(&mut self) -> &mut [u8];
2132     #[stable(feature = "core", since = "1.6.0")]
2133     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
2134     #[stable(feature = "core", since = "1.6.0")]
2135     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
2136         where P::Searcher: ReverseSearcher<'a>;
2137     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>;
2138     #[stable(feature = "core", since = "1.6.0")]
2139     fn split_at(&self, mid: usize) -> (&str, &str);
2140     #[stable(feature = "core", since = "1.6.0")]
2141     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str);
2142     #[stable(feature = "core", since = "1.6.0")]
2143     fn as_ptr(&self) -> *const u8;
2144     #[stable(feature = "core", since = "1.6.0")]
2145     fn len(&self) -> usize;
2146     #[stable(feature = "core", since = "1.6.0")]
2147     fn is_empty(&self) -> bool;
2148     #[stable(feature = "core", since = "1.6.0")]
2149     fn parse<'a, T: TryFrom<&'a str>>(&'a self) -> Result<T, T::Error>;
2150 }
2151
2152 // truncate `&str` to length at most equal to `max`
2153 // return `true` if it were truncated, and the new str.
2154 fn truncate_to_char_boundary(s: &str, mut max: usize) -> (bool, &str) {
2155     if max >= s.len() {
2156         (false, s)
2157     } else {
2158         while !s.is_char_boundary(max) {
2159             max -= 1;
2160         }
2161         (true, &s[..max])
2162     }
2163 }
2164
2165 #[inline(never)]
2166 #[cold]
2167 fn slice_error_fail(s: &str, begin: usize, end: usize) -> ! {
2168     const MAX_DISPLAY_LENGTH: usize = 256;
2169     let (truncated, s_trunc) = truncate_to_char_boundary(s, MAX_DISPLAY_LENGTH);
2170     let ellipsis = if truncated { "[...]" } else { "" };
2171
2172     // 1. out of bounds
2173     if begin > s.len() || end > s.len() {
2174         let oob_index = if begin > s.len() { begin } else { end };
2175         panic!("byte index {} is out of bounds of `{}`{}", oob_index, s_trunc, ellipsis);
2176     }
2177
2178     // 2. begin <= end
2179     assert!(begin <= end, "begin <= end ({} <= {}) when slicing `{}`{}",
2180             begin, end, s_trunc, ellipsis);
2181
2182     // 3. character boundary
2183     let index = if !s.is_char_boundary(begin) { begin } else { end };
2184     // find the character
2185     let mut char_start = index;
2186     while !s.is_char_boundary(char_start) {
2187         char_start -= 1;
2188     }
2189     // `char_start` must be less than len and a char boundary
2190     let ch = s[char_start..].chars().next().unwrap();
2191     let char_range = char_start .. char_start + ch.len_utf8();
2192     panic!("byte index {} is not a char boundary; it is inside {:?} (bytes {:?}) of `{}`{}",
2193            index, ch, char_range, s_trunc, ellipsis);
2194 }
2195
2196 #[stable(feature = "core", since = "1.6.0")]
2197 impl StrExt for str {
2198     #[inline]
2199     fn contains<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2200         pat.is_contained_in(self)
2201     }
2202
2203     #[inline]
2204     fn chars(&self) -> Chars {
2205         Chars{iter: self.as_bytes().iter()}
2206     }
2207
2208     #[inline]
2209     fn bytes(&self) -> Bytes {
2210         Bytes(self.as_bytes().iter().cloned())
2211     }
2212
2213     #[inline]
2214     fn char_indices(&self) -> CharIndices {
2215         CharIndices { front_offset: 0, iter: self.chars() }
2216     }
2217
2218     #[inline]
2219     fn split<'a, P: Pattern<'a>>(&'a self, pat: P) -> Split<'a, P> {
2220         Split(SplitInternal {
2221             start: 0,
2222             end: self.len(),
2223             matcher: pat.into_searcher(self),
2224             allow_trailing_empty: true,
2225             finished: false,
2226         })
2227     }
2228
2229     #[inline]
2230     fn rsplit<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplit<'a, P>
2231         where P::Searcher: ReverseSearcher<'a>
2232     {
2233         RSplit(self.split(pat).0)
2234     }
2235
2236     #[inline]
2237     fn splitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> SplitN<'a, P> {
2238         SplitN(SplitNInternal {
2239             iter: self.split(pat).0,
2240             count,
2241         })
2242     }
2243
2244     #[inline]
2245     fn rsplitn<'a, P: Pattern<'a>>(&'a self, count: usize, pat: P) -> RSplitN<'a, P>
2246         where P::Searcher: ReverseSearcher<'a>
2247     {
2248         RSplitN(self.splitn(count, pat).0)
2249     }
2250
2251     #[inline]
2252     fn split_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> SplitTerminator<'a, P> {
2253         SplitTerminator(SplitInternal {
2254             allow_trailing_empty: false,
2255             ..self.split(pat).0
2256         })
2257     }
2258
2259     #[inline]
2260     fn rsplit_terminator<'a, P: Pattern<'a>>(&'a self, pat: P) -> RSplitTerminator<'a, P>
2261         where P::Searcher: ReverseSearcher<'a>
2262     {
2263         RSplitTerminator(self.split_terminator(pat).0)
2264     }
2265
2266     #[inline]
2267     fn matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> Matches<'a, P> {
2268         Matches(MatchesInternal(pat.into_searcher(self)))
2269     }
2270
2271     #[inline]
2272     fn rmatches<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatches<'a, P>
2273         where P::Searcher: ReverseSearcher<'a>
2274     {
2275         RMatches(self.matches(pat).0)
2276     }
2277
2278     #[inline]
2279     fn match_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> MatchIndices<'a, P> {
2280         MatchIndices(MatchIndicesInternal(pat.into_searcher(self)))
2281     }
2282
2283     #[inline]
2284     fn rmatch_indices<'a, P: Pattern<'a>>(&'a self, pat: P) -> RMatchIndices<'a, P>
2285         where P::Searcher: ReverseSearcher<'a>
2286     {
2287         RMatchIndices(self.match_indices(pat).0)
2288     }
2289     #[inline]
2290     fn lines(&self) -> Lines {
2291         Lines(self.split_terminator('\n').map(LinesAnyMap))
2292     }
2293
2294     #[inline]
2295     #[allow(deprecated)]
2296     fn lines_any(&self) -> LinesAny {
2297         LinesAny(self.lines())
2298     }
2299
2300     #[inline]
2301     fn get<I: SliceIndex<str>>(&self, i: I) -> Option<&I::Output> {
2302         i.get(self)
2303     }
2304
2305     #[inline]
2306     fn get_mut<I: SliceIndex<str>>(&mut self, i: I) -> Option<&mut I::Output> {
2307         i.get_mut(self)
2308     }
2309
2310     #[inline]
2311     unsafe fn get_unchecked<I: SliceIndex<str>>(&self, i: I) -> &I::Output {
2312         i.get_unchecked(self)
2313     }
2314
2315     #[inline]
2316     unsafe fn get_unchecked_mut<I: SliceIndex<str>>(&mut self, i: I) -> &mut I::Output {
2317         i.get_unchecked_mut(self)
2318     }
2319
2320     #[inline]
2321     unsafe fn slice_unchecked(&self, begin: usize, end: usize) -> &str {
2322         (begin..end).get_unchecked(self)
2323     }
2324
2325     #[inline]
2326     unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str {
2327         (begin..end).get_unchecked_mut(self)
2328     }
2329
2330     #[inline]
2331     fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool {
2332         pat.is_prefix_of(self)
2333     }
2334
2335     #[inline]
2336     fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool
2337         where P::Searcher: ReverseSearcher<'a>
2338     {
2339         pat.is_suffix_of(self)
2340     }
2341
2342     #[inline]
2343     fn trim_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2344         where P::Searcher: DoubleEndedSearcher<'a>
2345     {
2346         let mut i = 0;
2347         let mut j = 0;
2348         let mut matcher = pat.into_searcher(self);
2349         if let Some((a, b)) = matcher.next_reject() {
2350             i = a;
2351             j = b; // Remember earliest known match, correct it below if
2352                    // last match is different
2353         }
2354         if let Some((_, b)) = matcher.next_reject_back() {
2355             j = b;
2356         }
2357         unsafe {
2358             // Searcher is known to return valid indices
2359             self.slice_unchecked(i, j)
2360         }
2361     }
2362
2363     #[inline]
2364     fn trim_left_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str {
2365         let mut i = self.len();
2366         let mut matcher = pat.into_searcher(self);
2367         if let Some((a, _)) = matcher.next_reject() {
2368             i = a;
2369         }
2370         unsafe {
2371             // Searcher is known to return valid indices
2372             self.slice_unchecked(i, self.len())
2373         }
2374     }
2375
2376     #[inline]
2377     fn trim_right_matches<'a, P: Pattern<'a>>(&'a self, pat: P) -> &'a str
2378         where P::Searcher: ReverseSearcher<'a>
2379     {
2380         let mut j = 0;
2381         let mut matcher = pat.into_searcher(self);
2382         if let Some((_, b)) = matcher.next_reject_back() {
2383             j = b;
2384         }
2385         unsafe {
2386             // Searcher is known to return valid indices
2387             self.slice_unchecked(0, j)
2388         }
2389     }
2390
2391     #[inline]
2392     fn is_char_boundary(&self, index: usize) -> bool {
2393         // 0 and len are always ok.
2394         // Test for 0 explicitly so that it can optimize out the check
2395         // easily and skip reading string data for that case.
2396         if index == 0 || index == self.len() { return true; }
2397         match self.as_bytes().get(index) {
2398             None => false,
2399             // This is bit magic equivalent to: b < 128 || b >= 192
2400             Some(&b) => (b as i8) >= -0x40,
2401         }
2402     }
2403
2404     #[inline]
2405     fn as_bytes(&self) -> &[u8] {
2406         unsafe { mem::transmute(self) }
2407     }
2408
2409     #[inline]
2410     unsafe fn as_bytes_mut(&mut self) -> &mut [u8] {
2411         mem::transmute(self)
2412     }
2413
2414     fn find<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
2415         pat.into_searcher(self).next_match().map(|(i, _)| i)
2416     }
2417
2418     fn rfind<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>
2419         where P::Searcher: ReverseSearcher<'a>
2420     {
2421         pat.into_searcher(self).next_match_back().map(|(i, _)| i)
2422     }
2423
2424     fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize> {
2425         self.find(pat)
2426     }
2427
2428     #[inline]
2429     fn split_at(&self, mid: usize) -> (&str, &str) {
2430         // is_char_boundary checks that the index is in [0, .len()]
2431         if self.is_char_boundary(mid) {
2432             unsafe {
2433                 (self.slice_unchecked(0, mid),
2434                  self.slice_unchecked(mid, self.len()))
2435             }
2436         } else {
2437             slice_error_fail(self, 0, mid)
2438         }
2439     }
2440
2441     fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str) {
2442         // is_char_boundary checks that the index is in [0, .len()]
2443         if self.is_char_boundary(mid) {
2444             let len = self.len();
2445             let ptr = self.as_ptr() as *mut u8;
2446             unsafe {
2447                 (from_raw_parts_mut(ptr, mid),
2448                  from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
2449             }
2450         } else {
2451             slice_error_fail(self, 0, mid)
2452         }
2453     }
2454
2455     #[inline]
2456     fn as_ptr(&self) -> *const u8 {
2457         self as *const str as *const u8
2458     }
2459
2460     #[inline]
2461     fn len(&self) -> usize {
2462         self.as_bytes().len()
2463     }
2464
2465     #[inline]
2466     fn is_empty(&self) -> bool { self.len() == 0 }
2467
2468     #[inline]
2469     fn parse<'a, T>(&'a self) -> Result<T, T::Error> where T: TryFrom<&'a str> {
2470         T::try_from(self)
2471     }
2472 }
2473
2474 #[stable(feature = "rust1", since = "1.0.0")]
2475 impl AsRef<[u8]> for str {
2476     #[inline]
2477     fn as_ref(&self) -> &[u8] {
2478         self.as_bytes()
2479     }
2480 }
2481
2482 #[stable(feature = "rust1", since = "1.0.0")]
2483 impl<'a> Default for &'a str {
2484     /// Creates an empty str
2485     fn default() -> &'a str { "" }
2486 }