src/libcollections/string.rs

   1 // Copyright 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 //! An owned, growable string that enforces that its contents are valid UTF-8.
  12
  13 #![stable(feature = "rust1", since = "1.0.0")]
  14
  15 use core::prelude::*;
  16
  17 use core::fmt;
  18 use core::hash;
  19 use core::iter::FromIterator;
  20 use core::mem;
  21 use core::ops::{self, Deref, Add, Index};
  22 use core::ptr;
  23 use core::slice;
  24 use core::str::pattern::Pattern;
  25 use rustc_unicode::str as unicode_str;
  26 use rustc_unicode::str::Utf16Item;
  27
  28 use borrow::{Cow, IntoCow};
  29 use range::RangeArgument;
  30 use str::{self, FromStr, Utf8Error, Chars};
  31 use vec::{DerefVec, Vec, as_vec};
  32 use boxed::Box;
  33
  34 /// A growable string stored as a UTF-8 encoded buffer.
  35 #[derive(Clone, PartialOrd, Eq, Ord)]
  36 #[stable(feature = "rust1", since = "1.0.0")]
  37 pub struct String {
  38     vec: Vec<u8>,
  39 }
  40
  41 /// A possible error value from the `String::from_utf8` function.
  42 #[stable(feature = "rust1", since = "1.0.0")]
  43 #[derive(Debug)]
  44 pub struct FromUtf8Error {
  45     bytes: Vec<u8>,
  46     error: Utf8Error,
  47 }
  48
  49 /// A possible error value from the `String::from_utf16` function.
  50 #[stable(feature = "rust1", since = "1.0.0")]
  51 #[derive(Debug)]
  52 pub struct FromUtf16Error(());
  53
  54 impl String {
  55     /// Creates a new string buffer initialized with the empty string.
  56     ///
  57     /// # Examples
  58     ///
  59     /// ```
  60     /// let mut s = String::new();
  61     /// ```
  62     #[inline]
  63     #[stable(feature = "rust1", since = "1.0.0")]
  64     pub fn new() -> String {
  65         String {
  66             vec: Vec::new(),
  67         }
  68     }
  69
  70     /// Creates a new string buffer with the given capacity.
  71     /// The string will be able to hold exactly `capacity` bytes without
  72     /// reallocating. If `capacity` is 0, the string will not allocate.
  73     ///
  74     /// # Examples
  75     ///
  76     /// ```
  77     /// let mut s = String::with_capacity(10);
  78     /// ```
  79     #[inline]
  80     #[stable(feature = "rust1", since = "1.0.0")]
  81     pub fn with_capacity(capacity: usize) -> String {
  82         String {
  83             vec: Vec::with_capacity(capacity),
  84         }
  85     }
  86
  87     /// Creates a new string buffer from the given string.
  88     ///
  89     /// # Examples
  90     ///
  91     /// ```
  92     /// # #![feature(collections)]
  93     /// let s = String::from("hello");
  94     /// assert_eq!(&s[..], "hello");
  95     /// ```
  96     #[inline]
  97     #[unstable(feature = "collections", reason = "use `String::from` instead")]
  98     #[deprecated(since = "1.2.0", reason = "use `String::from` instead")]
  99     #[cfg(not(test))]
 100     pub fn from_str(string: &str) -> String {
 101         String { vec: <[_]>::to_vec(string.as_bytes()) }
 102     }
 103
 104     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
 105     // required for this method definition, is not available. Since we don't
 106     // require this method for testing purposes, I'll just stub it
 107     // NB see the slice::hack module in slice.rs for more information
 108     #[inline]
 109     #[cfg(test)]
 110     pub fn from_str(_: &str) -> String {
 111         panic!("not available with cfg(test)");
 112     }
 113
 114     /// Returns the vector as a string buffer, if possible, taking care not to
 115     /// copy it.
 116     ///
 117     /// # Failure
 118     ///
 119     /// If the given vector is not valid UTF-8, then the original vector and the
 120     /// corresponding error is returned.
 121     ///
 122     /// # Examples
 123     ///
 124     /// ```
 125     /// let hello_vec = vec![104, 101, 108, 108, 111];
 126     /// let s = String::from_utf8(hello_vec).unwrap();
 127     /// assert_eq!(s, "hello");
 128     ///
 129     /// let invalid_vec = vec![240, 144, 128];
 130     /// let s = String::from_utf8(invalid_vec).err().unwrap();
 131     /// let err = s.utf8_error();
 132     /// assert_eq!(s.into_bytes(), [240, 144, 128]);
 133     /// ```
 134     #[inline]
 135     #[stable(feature = "rust1", since = "1.0.0")]
 136     pub fn from_utf8(vec: Vec<u8>) -> Result<String, FromUtf8Error> {
 137         match str::from_utf8(&vec) {
 138             Ok(..) => Ok(String { vec: vec }),
 139             Err(e) => Err(FromUtf8Error { bytes: vec, error: e })
 140         }
 141     }
 142
 143     /// Converts a vector of bytes to a new UTF-8 string.
 144     /// Any invalid UTF-8 sequences are replaced with U+FFFD REPLACEMENT CHARACTER.
 145     ///
 146     /// # Examples
 147     ///
 148     /// ```
 149     /// let input = b"Hello \xF0\x90\x80World";
 150     /// let output = String::from_utf8_lossy(input);
 151     /// assert_eq!(output, "Hello \u{FFFD}World");
 152     /// ```
 153     #[stable(feature = "rust1", since = "1.0.0")]
 154     pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> Cow<'a, str> {
 155         let mut i;
 156         match str::from_utf8(v) {
 157             Ok(s) => return Cow::Borrowed(s),
 158             Err(e) => i = e.valid_up_to(),
 159         }
 160
 161         const TAG_CONT_U8: u8 = 128;
 162         const REPLACEMENT: &'static [u8] = b"\xEF\xBF\xBD"; // U+FFFD in UTF-8
 163         let total = v.len();
 164         fn unsafe_get(xs: &[u8], i: usize) -> u8 {
 165             unsafe { *xs.get_unchecked(i) }
 166         }
 167         fn safe_get(xs: &[u8], i: usize, total: usize) -> u8 {
 168             if i >= total {
 169                 0
 170             } else {
 171                 unsafe_get(xs, i)
 172             }
 173         }
 174
 175         let mut res = String::with_capacity(total);
 176
 177         if i > 0 {
 178             unsafe {
 179                 res.as_mut_vec().push_all(&v[..i])
 180             };
 181         }
 182
 183         // subseqidx is the index of the first byte of the subsequence we're
 184         // looking at.  It's used to copy a bunch of contiguous good codepoints
 185         // at once instead of copying them one by one.
 186         let mut subseqidx = i;
 187
 188         while i < total {
 189             let i_ = i;
 190             let byte = unsafe_get(v, i);
 191             i += 1;
 192
 193             macro_rules! error { () => ({
 194                 unsafe {
 195                     if subseqidx != i_ {
 196                         res.as_mut_vec().push_all(&v[subseqidx..i_]);
 197                     }
 198                     subseqidx = i;
 199                     res.as_mut_vec().push_all(REPLACEMENT);
 200                 }
 201             })}
 202
 203             if byte < 128 {
 204                 // subseqidx handles this
 205             } else {
 206                 let w = unicode_str::utf8_char_width(byte);
 207
 208                 match w {
 209                     2 => {
 210                         if safe_get(v, i, total) & 192 != TAG_CONT_U8 {
 211                             error!();
 212                             continue;
 213                         }
 214                         i += 1;
 215                     }
 216                     3 => {
 217                         match (byte, safe_get(v, i, total)) {
 218                             (0xE0         , 0xA0 ... 0xBF) => (),
 219                             (0xE1 ... 0xEC, 0x80 ... 0xBF) => (),
 220                             (0xED         , 0x80 ... 0x9F) => (),
 221                             (0xEE ... 0xEF, 0x80 ... 0xBF) => (),
 222                             _ => {
 223                                 error!();
 224                                 continue;
 225                             }
 226                         }
 227                         i += 1;
 228                         if safe_get(v, i, total) & 192 != TAG_CONT_U8 {
 229                             error!();
 230                             continue;
 231                         }
 232                         i += 1;
 233                     }
 234                     4 => {
 235                         match (byte, safe_get(v, i, total)) {
 236                             (0xF0         , 0x90 ... 0xBF) => (),
 237                             (0xF1 ... 0xF3, 0x80 ... 0xBF) => (),
 238                             (0xF4         , 0x80 ... 0x8F) => (),
 239                             _ => {
 240                                 error!();
 241                                 continue;
 242                             }
 243                         }
 244                         i += 1;
 245                         if safe_get(v, i, total) & 192 != TAG_CONT_U8 {
 246                             error!();
 247                             continue;
 248                         }
 249                         i += 1;
 250                         if safe_get(v, i, total) & 192 != TAG_CONT_U8 {
 251                             error!();
 252                             continue;
 253                         }
 254                         i += 1;
 255                     }
 256                     _ => {
 257                         error!();
 258                         continue;
 259                     }
 260                 }
 261             }
 262         }
 263         if subseqidx < total {
 264             unsafe {
 265                 res.as_mut_vec().push_all(&v[subseqidx..total])
 266             };
 267         }
 268         Cow::Owned(res)
 269     }
 270
 271     /// Decode a UTF-16 encoded vector `v` into a `String`, returning `None`
 272     /// if `v` contains any invalid data.
 273     ///
 274     /// # Examples
 275     ///
 276     /// ```
 277     /// // 𝄞music
 278     /// let mut v = &mut [0xD834, 0xDD1E, 0x006d, 0x0075,
 279     ///                   0x0073, 0x0069, 0x0063];
 280     /// assert_eq!(String::from_utf16(v).unwrap(),
 281     ///            "𝄞music".to_string());
 282     ///
 283     /// // 𝄞mu<invalid>ic
 284     /// v[4] = 0xD800;
 285     /// assert!(String::from_utf16(v).is_err());
 286     /// ```
 287     #[stable(feature = "rust1", since = "1.0.0")]
 288     pub fn from_utf16(v: &[u16]) -> Result<String, FromUtf16Error> {
 289         let mut s = String::with_capacity(v.len());
 290         for c in unicode_str::utf16_items(v) {
 291             match c {
 292                 Utf16Item::ScalarValue(c) => s.push(c),
 293                 Utf16Item::LoneSurrogate(_) => return Err(FromUtf16Error(())),
 294             }
 295         }
 296         Ok(s)
 297     }
 298
 299     /// Decode a UTF-16 encoded vector `v` into a string, replacing
 300     /// invalid data with the replacement character (U+FFFD).
 301     ///
 302     /// # Examples
 303     ///
 304     /// ```
 305     /// // 𝄞mus<invalid>ic<invalid>
 306     /// let v = &[0xD834, 0xDD1E, 0x006d, 0x0075,
 307     ///           0x0073, 0xDD1E, 0x0069, 0x0063,
 308     ///           0xD834];
 309     ///
 310     /// assert_eq!(String::from_utf16_lossy(v),
 311     ///            "𝄞mus\u{FFFD}ic\u{FFFD}".to_string());
 312     /// ```
 313     #[inline]
 314     #[stable(feature = "rust1", since = "1.0.0")]
 315     pub fn from_utf16_lossy(v: &[u16]) -> String {
 316         unicode_str::utf16_items(v).map(|c| c.to_char_lossy()).collect()
 317     }
 318
 319     /// Creates a new `String` from a length, capacity, and pointer.
 320     ///
 321     /// # Unsafety
 322     ///
 323     /// This is _very_ unsafe because:
 324     ///
 325     /// * We call `Vec::from_raw_parts` to get a `Vec<u8>`. Therefore, this
 326     ///   function inherits all of its unsafety, see [its
 327     ///   documentation](../vec/struct.Vec.html#method.from_raw_parts)
 328     ///   for the invariants it expects, they also apply to this function.
 329     /// * We assume that the `Vec` contains valid UTF-8.
 330     #[inline]
 331     #[stable(feature = "rust1", since = "1.0.0")]
 332     pub unsafe fn from_raw_parts(buf: *mut u8, length: usize, capacity: usize) -> String {
 333         String {
 334             vec: Vec::from_raw_parts(buf, length, capacity),
 335         }
 336     }
 337
 338     /// Converts a vector of bytes to a new `String` without checking if
 339     /// it contains valid UTF-8. This is unsafe because it assumes that
 340     /// the UTF-8-ness of the vector has already been validated.
 341     #[inline]
 342     #[stable(feature = "rust1", since = "1.0.0")]
 343     pub unsafe fn from_utf8_unchecked(bytes: Vec<u8>) -> String {
 344         String { vec: bytes }
 345     }
 346
 347     /// Returns the underlying byte buffer, encoded as UTF-8.
 348     ///
 349     /// # Examples
 350     ///
 351     /// ```
 352     /// let s = String::from("hello");
 353     /// let bytes = s.into_bytes();
 354     /// assert_eq!(bytes, [104, 101, 108, 108, 111]);
 355     /// ```
 356     #[inline]
 357     #[stable(feature = "rust1", since = "1.0.0")]
 358     pub fn into_bytes(self) -> Vec<u8> {
 359         self.vec
 360     }
 361
 362     /// Extracts a string slice containing the entire string.
 363     #[inline]
 364     #[unstable(feature = "convert",
 365                reason = "waiting on RFC revision")]
 366     pub fn as_str(&self) -> &str {
 367         self
 368     }
 369
 370     /// Pushes the given string onto this string buffer.
 371     ///
 372     /// # Examples
 373     ///
 374     /// ```
 375     /// let mut s = String::from("foo");
 376     /// s.push_str("bar");
 377     /// assert_eq!(s, "foobar");
 378     /// ```
 379     #[inline]
 380     #[stable(feature = "rust1", since = "1.0.0")]
 381     pub fn push_str(&mut self, string: &str) {
 382         self.vec.push_all(string.as_bytes())
 383     }
 384
 385     /// Returns the number of bytes that this string buffer can hold without
 386     /// reallocating.
 387     ///
 388     /// # Examples
 389     ///
 390     /// ```
 391     /// let s = String::with_capacity(10);
 392     /// assert!(s.capacity() >= 10);
 393     /// ```
 394     #[inline]
 395     #[stable(feature = "rust1", since = "1.0.0")]
 396     pub fn capacity(&self) -> usize {
 397         self.vec.capacity()
 398     }
 399
 400     /// Reserves capacity for at least `additional` more bytes to be inserted
 401     /// in the given `String`. The collection may reserve more space to avoid
 402     /// frequent reallocations.
 403     ///
 404     /// # Panics
 405     ///
 406     /// Panics if the new capacity overflows `usize`.
 407     ///
 408     /// # Examples
 409     ///
 410     /// ```
 411     /// let mut s = String::new();
 412     /// s.reserve(10);
 413     /// assert!(s.capacity() >= 10);
 414     /// ```
 415     #[inline]
 416     #[stable(feature = "rust1", since = "1.0.0")]
 417     pub fn reserve(&mut self, additional: usize) {
 418         self.vec.reserve(additional)
 419     }
 420
 421     /// Reserves the minimum capacity for exactly `additional` more bytes to be
 422     /// inserted in the given `String`. Does nothing if the capacity is already
 423     /// sufficient.
 424     ///
 425     /// Note that the allocator may give the collection more space than it
 426     /// requests. Therefore capacity can not be relied upon to be precisely
 427     /// minimal. Prefer `reserve` if future insertions are expected.
 428     ///
 429     /// # Panics
 430     ///
 431     /// Panics if the new capacity overflows `usize`.
 432     ///
 433     /// # Examples
 434     ///
 435     /// ```
 436     /// let mut s = String::new();
 437     /// s.reserve_exact(10);
 438     /// assert!(s.capacity() >= 10);
 439     /// ```
 440     #[inline]
 441     #[stable(feature = "rust1", since = "1.0.0")]
 442     pub fn reserve_exact(&mut self, additional: usize) {
 443         self.vec.reserve_exact(additional)
 444     }
 445
 446     /// Shrinks the capacity of this string buffer to match its length.
 447     ///
 448     /// # Examples
 449     ///
 450     /// ```
 451     /// let mut s = String::from("foo");
 452     /// s.reserve(100);
 453     /// assert!(s.capacity() >= 100);
 454     /// s.shrink_to_fit();
 455     /// assert_eq!(s.capacity(), 3);
 456     /// ```
 457     #[inline]
 458     #[stable(feature = "rust1", since = "1.0.0")]
 459     pub fn shrink_to_fit(&mut self) {
 460         self.vec.shrink_to_fit()
 461     }
 462
 463     /// Adds the given character to the end of the string.
 464     ///
 465     /// # Examples
 466     ///
 467     /// ```
 468     /// let mut s = String::from("abc");
 469     /// s.push('1');
 470     /// s.push('2');
 471     /// s.push('3');
 472     /// assert_eq!(s, "abc123");
 473     /// ```
 474     #[inline]
 475     #[stable(feature = "rust1", since = "1.0.0")]
 476     pub fn push(&mut self, ch: char) {
 477         match ch.len_utf8() {
 478             1 => self.vec.push(ch as u8),
 479             ch_len => {
 480                 let cur_len = self.len();
 481                 // This may use up to 4 bytes.
 482                 self.vec.reserve(ch_len);
 483
 484                 unsafe {
 485                     // Attempt to not use an intermediate buffer by just pushing bytes
 486                     // directly onto this string.
 487                     let slice = slice::from_raw_parts_mut (
 488                         self.vec.as_mut_ptr().offset(cur_len as isize),
 489                         ch_len
 490                     );
 491                     let used = ch.encode_utf8(slice).unwrap_or(0);
 492                     self.vec.set_len(cur_len + used);
 493                 }
 494             }
 495         }
 496     }
 497
 498     /// Works with the underlying buffer as a byte slice.
 499     ///
 500     /// # Examples
 501     ///
 502     /// ```
 503     /// let s = String::from("hello");
 504     /// assert_eq!(s.as_bytes(), [104, 101, 108, 108, 111]);
 505     /// ```
 506     #[inline]
 507     #[stable(feature = "rust1", since = "1.0.0")]
 508     pub fn as_bytes(&self) -> &[u8] {
 509         &self.vec
 510     }
 511
 512     /// Shortens a string to the specified length.
 513     ///
 514     /// # Panics
 515     ///
 516     /// Panics if `new_len` > current length,
 517     /// or if `new_len` is not a character boundary.
 518     ///
 519     /// # Examples
 520     ///
 521     /// ```
 522     /// let mut s = String::from("hello");
 523     /// s.truncate(2);
 524     /// assert_eq!(s, "he");
 525     /// ```
 526     #[inline]
 527     #[stable(feature = "rust1", since = "1.0.0")]
 528     pub fn truncate(&mut self, new_len: usize) {
 529         assert!(self.is_char_boundary(new_len));
 530         self.vec.truncate(new_len)
 531     }
 532
 533     /// Removes the last character from the string buffer and returns it.
 534     /// Returns `None` if this string buffer is empty.
 535     ///
 536     /// # Examples
 537     ///
 538     /// ```
 539     /// let mut s = String::from("foo");
 540     /// assert_eq!(s.pop(), Some('o'));
 541     /// assert_eq!(s.pop(), Some('o'));
 542     /// assert_eq!(s.pop(), Some('f'));
 543     /// assert_eq!(s.pop(), None);
 544     /// ```
 545     #[inline]
 546     #[stable(feature = "rust1", since = "1.0.0")]
 547     pub fn pop(&mut self) -> Option<char> {
 548         let len = self.len();
 549         if len == 0 {
 550             return None
 551         }
 552
 553         let ch = self.char_at_reverse(len);
 554         unsafe {
 555             self.vec.set_len(len - ch.len_utf8());
 556         }
 557         Some(ch)
 558     }
 559
 560     /// Removes the character from the string buffer at byte position `idx` and
 561     /// returns it.
 562     ///
 563     /// # Warning
 564     ///
 565     /// This is an O(n) operation as it requires copying every element in the
 566     /// buffer.
 567     ///
 568     /// # Panics
 569     ///
 570     /// If `idx` does not lie on a character boundary, or if it is out of
 571     /// bounds, then this function will panic.
 572     ///
 573     /// # Examples
 574     ///
 575     /// ```
 576     /// let mut s = String::from("foo");
 577     /// assert_eq!(s.remove(0), 'f');
 578     /// assert_eq!(s.remove(1), 'o');
 579     /// assert_eq!(s.remove(0), 'o');
 580     /// ```
 581     #[inline]
 582     #[stable(feature = "rust1", since = "1.0.0")]
 583     pub fn remove(&mut self, idx: usize) -> char {
 584         let len = self.len();
 585         assert!(idx <= len);
 586
 587         let ch = self.char_at(idx);
 588         let next = idx + ch.len_utf8();
 589         unsafe {
 590             ptr::copy(self.vec.as_ptr().offset(next as isize),
 591                       self.vec.as_mut_ptr().offset(idx as isize),
 592                       len - next);
 593             self.vec.set_len(len - (next - idx));
 594         }
 595         ch
 596     }
 597
 598     /// Inserts a character into the string buffer at byte position `idx`.
 599     ///
 600     /// # Warning
 601     ///
 602     /// This is an O(n) operation as it requires copying every element in the
 603     /// buffer.
 604     ///
 605     /// # Panics
 606     ///
 607     /// If `idx` does not lie on a character boundary or is out of bounds, then
 608     /// this function will panic.
 609     #[inline]
 610     #[stable(feature = "rust1", since = "1.0.0")]
 611     pub fn insert(&mut self, idx: usize, ch: char) {
 612         let len = self.len();
 613         assert!(idx <= len);
 614         assert!(self.is_char_boundary(idx));
 615         self.vec.reserve(4);
 616         let mut bits = [0; 4];
 617         let amt = ch.encode_utf8(&mut bits).unwrap();
 618
 619         unsafe {
 620             ptr::copy(self.vec.as_ptr().offset(idx as isize),
 621                       self.vec.as_mut_ptr().offset((idx + amt) as isize),
 622                       len - idx);
 623             ptr::copy(bits.as_ptr(),
 624                       self.vec.as_mut_ptr().offset(idx as isize),
 625                       amt);
 626             self.vec.set_len(len + amt);
 627         }
 628     }
 629
 630     /// Views the string buffer as a mutable sequence of bytes.
 631     ///
 632     /// This is unsafe because it does not check
 633     /// to ensure that the resulting string will be valid UTF-8.
 634     ///
 635     /// # Examples
 636     ///
 637     /// ```
 638     /// let mut s = String::from("hello");
 639     /// unsafe {
 640     ///     let vec = s.as_mut_vec();
 641     ///     assert!(vec == &[104, 101, 108, 108, 111]);
 642     ///     vec.reverse();
 643     /// }
 644     /// assert_eq!(s, "olleh");
 645     /// ```
 646     #[inline]
 647     #[stable(feature = "rust1", since = "1.0.0")]
 648     pub unsafe fn as_mut_vec(&mut self) -> &mut Vec<u8> {
 649         &mut self.vec
 650     }
 651
 652     /// Returns the number of bytes in this string.
 653     ///
 654     /// # Examples
 655     ///
 656     /// ```
 657     /// let a = "foo".to_string();
 658     /// assert_eq!(a.len(), 3);
 659     /// ```
 660     #[inline]
 661     #[stable(feature = "rust1", since = "1.0.0")]
 662     pub fn len(&self) -> usize { self.vec.len() }
 663
 664     /// Returns true if the string contains no bytes
 665     ///
 666     /// # Examples
 667     ///
 668     /// ```
 669     /// let mut v = String::new();
 670     /// assert!(v.is_empty());
 671     /// v.push('a');
 672     /// assert!(!v.is_empty());
 673     /// ```
 674     #[inline]
 675     #[stable(feature = "rust1", since = "1.0.0")]
 676     pub fn is_empty(&self) -> bool { self.len() == 0 }
 677
 678     /// Truncates the string, returning it to 0 length.
 679     ///
 680     /// # Examples
 681     ///
 682     /// ```
 683     /// let mut s = "foo".to_string();
 684     /// s.clear();
 685     /// assert!(s.is_empty());
 686     /// ```
 687     #[inline]
 688     #[stable(feature = "rust1", since = "1.0.0")]
 689     pub fn clear(&mut self) {
 690         self.vec.clear()
 691     }
 692
 693     /// Create a draining iterator that removes the specified range in the string
 694     /// and yields the removed chars from start to end. The element range is
 695     /// removed even if the iterator is not consumed until the end.
 696     ///
 697     /// # Panics
 698     ///
 699     /// Panics if the starting point or end point are not on character boundaries,
 700     /// or if they are out of bounds.
 701     ///
 702     /// # Examples
 703     ///
 704     /// ```
 705     /// # #![feature(drain)]
 706     ///
 707     /// let mut s = String::from("α is alpha, β is beta");
 708     /// let beta_offset = s.find('β').unwrap_or(s.len());
 709     ///
 710     /// // Remove the range up until the β from the string
 711     /// let t: String = s.drain(..beta_offset).collect();
 712     /// assert_eq!(t, "α is alpha, ");
 713     /// assert_eq!(s, "β is beta");
 714     ///
 715     /// // A full range clears the string
 716     /// s.drain(..);
 717     /// assert_eq!(s, "");
 718     /// ```
 719     #[unstable(feature = "drain",
 720                reason = "recently added, matches RFC")]
 721     pub fn drain<R>(&mut self, range: R) -> Drain where R: RangeArgument<usize> {
 722         // Memory safety
 723         //
 724         // The String version of Drain does not have the memory safety issues
 725         // of the vector version. The data is just plain bytes.
 726         // Because the range removal happens in Drop, if the Drain iterator is leaked,
 727         // the removal will not happen.
 728         let len = self.len();
 729         let start = *range.start().unwrap_or(&0);
 730         let end = *range.end().unwrap_or(&len);
 731
 732         // Take out two simultaneous borrows. The &mut String won't be accessed
 733         // until iteration is over, in Drop.
 734         let self_ptr = self as *mut _;
 735         // slicing does the appropriate bounds checks
 736         let chars_iter = self[start..end].chars();
 737
 738         Drain {
 739             start: start,
 740             end: end,
 741             iter: chars_iter,
 742             string: self_ptr,
 743         }
 744     }
 745
 746     /// Converts the string into `Box<str>`.
 747     ///
 748     /// Note that this will drop any excess capacity.
 749     #[unstable(feature = "box_str",
 750                reason = "recently added, matches RFC")]
 751     pub fn into_boxed_slice(self) -> Box<str> {
 752         let slice = self.vec.into_boxed_slice();
 753         unsafe { mem::transmute::<Box<[u8]>, Box<str>>(slice) }
 754     }
 755 }
 756
 757 impl FromUtf8Error {
 758     /// Consumes this error, returning the bytes that were attempted to make a
 759     /// `String` with.
 760     #[stable(feature = "rust1", since = "1.0.0")]
 761     pub fn into_bytes(self) -> Vec<u8> { self.bytes }
 762
 763     /// Access the underlying UTF8-error that was the cause of this error.
 764     #[stable(feature = "rust1", since = "1.0.0")]
 765     pub fn utf8_error(&self) -> Utf8Error { self.error }
 766 }
 767
 768 #[stable(feature = "rust1", since = "1.0.0")]
 769 impl fmt::Display for FromUtf8Error {
 770     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 771         fmt::Display::fmt(&self.error, f)
 772     }
 773 }
 774
 775 #[stable(feature = "rust1", since = "1.0.0")]
 776 impl fmt::Display for FromUtf16Error {
 777     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 778         fmt::Display::fmt("invalid utf-16: lone surrogate found", f)
 779     }
 780 }
 781
 782 #[stable(feature = "rust1", since = "1.0.0")]
 783 impl FromIterator<char> for String {
 784     fn from_iter<I: IntoIterator<Item=char>>(iter: I) -> String {
 785         let mut buf = String::new();
 786         buf.extend(iter);
 787         buf
 788     }
 789 }
 790
 791 #[stable(feature = "rust1", since = "1.0.0")]
 792 impl<'a> FromIterator<&'a str> for String {
 793     fn from_iter<I: IntoIterator<Item=&'a str>>(iter: I) -> String {
 794         let mut buf = String::new();
 795         buf.extend(iter);
 796         buf
 797     }
 798 }
 799
 800 #[stable(feature = "rust1", since = "1.0.0")]
 801 impl Extend<char> for String {
 802     fn extend<I: IntoIterator<Item=char>>(&mut self, iterable: I) {
 803         let iterator = iterable.into_iter();
 804         let (lower_bound, _) = iterator.size_hint();
 805         self.reserve(lower_bound);
 806         for ch in iterator {
 807             self.push(ch)
 808         }
 809     }
 810 }
 811
 812 #[stable(feature = "extend_ref", since = "1.2.0")]
 813 impl<'a> Extend<&'a char> for String {
 814     fn extend<I: IntoIterator<Item=&'a char>>(&mut self, iter: I) {
 815         self.extend(iter.into_iter().cloned());
 816     }
 817 }
 818
 819 #[stable(feature = "rust1", since = "1.0.0")]
 820 impl<'a> Extend<&'a str> for String {
 821     fn extend<I: IntoIterator<Item=&'a str>>(&mut self, iterable: I) {
 822         let iterator = iterable.into_iter();
 823         // A guess that at least one byte per iterator element will be needed.
 824         let (lower_bound, _) = iterator.size_hint();
 825         self.reserve(lower_bound);
 826         for s in iterator {
 827             self.push_str(s)
 828         }
 829     }
 830 }
 831
 832 /// A convenience impl that delegates to the impl for `&str`
 833 impl<'a, 'b> Pattern<'a> for &'b String {
 834     type Searcher = <&'b str as Pattern<'a>>::Searcher;
 835
 836     fn into_searcher(self, haystack: &'a str) -> <&'b str as Pattern<'a>>::Searcher {
 837         self[..].into_searcher(haystack)
 838     }
 839
 840     #[inline]
 841     fn is_contained_in(self, haystack: &'a str) -> bool {
 842         self[..].is_contained_in(haystack)
 843     }
 844
 845     #[inline]
 846     fn is_prefix_of(self, haystack: &'a str) -> bool {
 847         self[..].is_prefix_of(haystack)
 848     }
 849 }
 850
 851 #[stable(feature = "rust1", since = "1.0.0")]
 852 impl PartialEq for String {
 853     #[inline]
 854     fn eq(&self, other: &String) -> bool { PartialEq::eq(&self[..], &other[..]) }
 855     #[inline]
 856     fn ne(&self, other: &String) -> bool { PartialEq::ne(&self[..], &other[..]) }
 857 }
 858
 859 macro_rules! impl_eq {
 860     ($lhs:ty, $rhs: ty) => {
 861         #[stable(feature = "rust1", since = "1.0.0")]
 862         impl<'a> PartialEq<$rhs> for $lhs {
 863             #[inline]
 864             fn eq(&self, other: &$rhs) -> bool { PartialEq::eq(&self[..], &other[..]) }
 865             #[inline]
 866             fn ne(&self, other: &$rhs) -> bool { PartialEq::ne(&self[..], &other[..]) }
 867         }
 868
 869         #[stable(feature = "rust1", since = "1.0.0")]
 870         impl<'a> PartialEq<$lhs> for $rhs {
 871             #[inline]
 872             fn eq(&self, other: &$lhs) -> bool { PartialEq::eq(&self[..], &other[..]) }
 873             #[inline]
 874             fn ne(&self, other: &$lhs) -> bool { PartialEq::ne(&self[..], &other[..]) }
 875         }
 876
 877     }
 878 }
 879
 880 impl_eq! { String, str }
 881 impl_eq! { String, &'a str }
 882 impl_eq! { Cow<'a, str>, str }
 883 impl_eq! { Cow<'a, str>, String }
 884
 885 #[stable(feature = "rust1", since = "1.0.0")]
 886 impl<'a, 'b> PartialEq<&'b str> for Cow<'a, str> {
 887     #[inline]
 888     fn eq(&self, other: &&'b str) -> bool { PartialEq::eq(&self[..], &other[..]) }
 889     #[inline]
 890     fn ne(&self, other: &&'b str) -> bool { PartialEq::ne(&self[..], &other[..]) }
 891 }
 892
 893 #[stable(feature = "rust1", since = "1.0.0")]
 894 impl<'a, 'b> PartialEq<Cow<'a, str>> for &'b str {
 895     #[inline]
 896     fn eq(&self, other: &Cow<'a, str>) -> bool { PartialEq::eq(&self[..], &other[..]) }
 897     #[inline]
 898     fn ne(&self, other: &Cow<'a, str>) -> bool { PartialEq::ne(&self[..], &other[..]) }
 899 }
 900
 901 #[stable(feature = "rust1", since = "1.0.0")]
 902 impl Default for String {
 903     #[inline]
 904     #[stable(feature = "rust1", since = "1.0.0")]
 905     fn default() -> String {
 906         String::new()
 907     }
 908 }
 909
 910 #[stable(feature = "rust1", since = "1.0.0")]
 911 impl fmt::Display for String {
 912     #[inline]
 913     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 914         fmt::Display::fmt(&**self, f)
 915     }
 916 }
 917
 918 #[stable(feature = "rust1", since = "1.0.0")]
 919 impl fmt::Debug for String {
 920     #[inline]
 921     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 922         fmt::Debug::fmt(&**self, f)
 923     }
 924 }
 925
 926 #[stable(feature = "rust1", since = "1.0.0")]
 927 impl hash::Hash for String {
 928     #[inline]
 929     fn hash<H: hash::Hasher>(&self, hasher: &mut H) {
 930         (**self).hash(hasher)
 931     }
 932 }
 933
 934 #[stable(feature = "rust1", since = "1.0.0")]
 935 impl<'a> Add<&'a str> for String {
 936     type Output = String;
 937
 938     #[inline]
 939     fn add(mut self, other: &str) -> String {
 940         self.push_str(other);
 941         self
 942     }
 943 }
 944
 945 #[stable(feature = "rust1", since = "1.0.0")]
 946 impl ops::Index<ops::Range<usize>> for String {
 947     type Output = str;
 948
 949     #[inline]
 950     fn index(&self, index: ops::Range<usize>) -> &str {
 951         &self[..][index]
 952     }
 953 }
 954 #[stable(feature = "rust1", since = "1.0.0")]
 955 impl ops::Index<ops::RangeTo<usize>> for String {
 956     type Output = str;
 957
 958     #[inline]
 959     fn index(&self, index: ops::RangeTo<usize>) -> &str {
 960         &self[..][index]
 961     }
 962 }
 963 #[stable(feature = "rust1", since = "1.0.0")]
 964 impl ops::Index<ops::RangeFrom<usize>> for String {
 965     type Output = str;
 966
 967     #[inline]
 968     fn index(&self, index: ops::RangeFrom<usize>) -> &str {
 969         &self[..][index]
 970     }
 971 }
 972 #[stable(feature = "rust1", since = "1.0.0")]
 973 impl ops::Index<ops::RangeFull> for String {
 974     type Output = str;
 975
 976     #[inline]
 977     fn index(&self, _index: ops::RangeFull) -> &str {
 978         unsafe { mem::transmute(&*self.vec) }
 979     }
 980 }
 981
 982 #[stable(feature = "rust1", since = "1.0.0")]
 983 impl ops::Deref for String {
 984     type Target = str;
 985
 986     #[inline]
 987     fn deref(&self) -> &str {
 988         unsafe { mem::transmute(&self.vec[..]) }
 989     }
 990 }
 991
 992 /// Wrapper type providing a `&String` reference via `Deref`.
 993 #[unstable(feature = "collections")]
 994 #[deprecated(since = "1.2.0",
 995              reason = "replaced with deref coercions or Borrow")]
 996 #[allow(deprecated)]
 997 pub struct DerefString<'a> {
 998     x: DerefVec<'a, u8>
 999 }
1000
1001 #[allow(deprecated)]
1002 impl<'a> Deref for DerefString<'a> {
1003     type Target = String;
1004
1005     #[inline]
1006     fn deref<'b>(&'b self) -> &'b String {
1007         unsafe { mem::transmute(&*self.x) }
1008     }
1009 }
1010
1011 /// Converts a string slice to a wrapper type providing a `&String` reference.
1012 ///
1013 /// # Examples
1014 ///
1015 /// ```
1016 /// # #![feature(collections)]
1017 /// use std::string::as_string;
1018 ///
1019 /// // Let's pretend we have a function that requires `&String`
1020 /// fn string_consumer(s: &String) {
1021 ///     assert_eq!(s, "foo");
1022 /// }
1023 ///
1024 /// // Provide a `&String` from a `&str` without allocating
1025 /// string_consumer(&as_string("foo"));
1026 /// ```
1027 #[unstable(feature = "collections")]
1028 #[deprecated(since = "1.2.0",
1029              reason = "replaced with deref coercions or Borrow")]
1030 #[allow(deprecated)]
1031 pub fn as_string<'a>(x: &'a str) -> DerefString<'a> {
1032     DerefString { x: as_vec(x.as_bytes()) }
1033 }
1034
1035 /// Error returned from `String::from`
1036 #[unstable(feature = "str_parse_error", reason = "may want to be replaced with \
1037                                                   Void if it ever exists")]
1038 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
1039 pub struct ParseError(());
1040
1041 #[stable(feature = "rust1", since = "1.0.0")]
1042 impl FromStr for String {
1043     type Err = ParseError;
1044     #[inline]
1045     fn from_str(s: &str) -> Result<String, ParseError> {
1046         Ok(String::from(s))
1047     }
1048 }
1049
1050 /// A generic trait for converting a value to a string
1051 #[stable(feature = "rust1", since = "1.0.0")]
1052 pub trait ToString {
1053     /// Converts the value of `self` to an owned string
1054     #[stable(feature = "rust1", since = "1.0.0")]
1055     fn to_string(&self) -> String;
1056 }
1057
1058 #[stable(feature = "rust1", since = "1.0.0")]
1059 impl<T: fmt::Display + ?Sized> ToString for T {
1060     #[inline]
1061     fn to_string(&self) -> String {
1062         use core::fmt::Write;
1063         let mut buf = String::new();
1064         let _ = buf.write_fmt(format_args!("{}", self));
1065         buf.shrink_to_fit();
1066         buf
1067     }
1068 }
1069
1070 #[stable(feature = "rust1", since = "1.0.0")]
1071 impl AsRef<str> for String {
1072     #[inline]
1073     fn as_ref(&self) -> &str {
1074         self
1075     }
1076 }
1077
1078 #[stable(feature = "rust1", since = "1.0.0")]
1079 impl AsRef<[u8]> for String {
1080     #[inline]
1081     fn as_ref(&self) -> &[u8] {
1082         self.as_bytes()
1083     }
1084 }
1085
1086 #[stable(feature = "rust1", since = "1.0.0")]
1087 impl<'a> From<&'a str> for String {
1088     #[cfg(not(test))]
1089     #[inline]
1090     fn from(s: &'a str) -> String {
1091         String { vec: <[_]>::to_vec(s.as_bytes()) }
1092     }
1093
1094     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
1095     // required for this method definition, is not available. Since we don't
1096     // require this method for testing purposes, I'll just stub it
1097     // NB see the slice::hack module in slice.rs for more information
1098     #[inline]
1099     #[cfg(test)]
1100     fn from(_: &str) -> String {
1101         panic!("not available with cfg(test)");
1102     }
1103 }
1104
1105 #[stable(feature = "rust1", since = "1.0.0")]
1106 impl<'a> From<&'a str> for Cow<'a, str> {
1107     #[inline]
1108     fn from(s: &'a str) -> Cow<'a, str> {
1109         Cow::Borrowed(s)
1110     }
1111 }
1112
1113 #[stable(feature = "rust1", since = "1.0.0")]
1114 impl<'a> From<String> for Cow<'a, str> {
1115     #[inline]
1116     fn from(s: String) -> Cow<'a, str> {
1117         Cow::Owned(s)
1118     }
1119 }
1120
1121 #[stable(feature = "rust1", since = "1.0.0")]
1122 impl Into<Vec<u8>> for String {
1123     fn into(self) -> Vec<u8> {
1124         self.into_bytes()
1125     }
1126 }
1127
1128 #[unstable(feature = "into_cow", reason = "may be replaced by `convert::Into`")]
1129 impl IntoCow<'static, str> for String {
1130     #[inline]
1131     fn into_cow(self) -> Cow<'static, str> {
1132         Cow::Owned(self)
1133     }
1134 }
1135
1136 #[unstable(feature = "into_cow", reason = "may be replaced by `convert::Into`")]
1137 impl<'a> IntoCow<'a, str> for &'a str {
1138     #[inline]
1139     fn into_cow(self) -> Cow<'a, str> {
1140         Cow::Borrowed(self)
1141     }
1142 }
1143
1144 #[stable(feature = "rust1", since = "1.0.0")]
1145 impl fmt::Write for String {
1146     #[inline]
1147     fn write_str(&mut self, s: &str) -> fmt::Result {
1148         self.push_str(s);
1149         Ok(())
1150     }
1151
1152     #[inline]
1153     fn write_char(&mut self, c: char) -> fmt::Result {
1154         self.push(c);
1155         Ok(())
1156     }
1157 }
1158
1159 /// A draining iterator for `String`.
1160 #[unstable(feature = "drain", reason = "recently added")]
1161 pub struct Drain<'a> {
1162     /// Will be used as &'a mut String in the destructor
1163     string: *mut String,
1164     /// Start of part to remove
1165     start: usize,
1166     /// End of part to remove
1167     end: usize,
1168     /// Current remaining range to remove
1169     iter: Chars<'a>,
1170 }
1171
1172 unsafe impl<'a> Sync for Drain<'a> {}
1173 unsafe impl<'a> Send for Drain<'a> {}
1174
1175 #[unstable(feature = "drain", reason = "recently added")]
1176 impl<'a> Drop for Drain<'a> {
1177     fn drop(&mut self) {
1178         unsafe {
1179             // Use Vec::drain. "Reaffirm" the bounds checks to avoid
1180             // panic code being inserted again.
1181             let self_vec = (*self.string).as_mut_vec();
1182             if self.start <= self.end && self.end <= self_vec.len() {
1183                 self_vec.drain(self.start..self.end);
1184             }
1185         }
1186     }
1187 }
1188
1189 #[unstable(feature = "drain", reason = "recently added")]
1190 impl<'a> Iterator for Drain<'a> {
1191     type Item = char;
1192
1193     #[inline]
1194     fn next(&mut self) -> Option<char> {
1195         self.iter.next()
1196     }
1197
1198     fn size_hint(&self) -> (usize, Option<usize>) {
1199         self.iter.size_hint()
1200     }
1201 }
1202
1203 #[unstable(feature = "drain", reason = "recently added")]
1204 impl<'a> DoubleEndedIterator for Drain<'a> {
1205     #[inline]
1206     fn next_back(&mut self) -> Option<char> {
1207         self.iter.next_back()
1208     }
1209 }