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