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