src/liballoc/string.rs

   1 //! A UTF-8 encoded, growable string.
   2 //!
   3 //! This module contains the [`String`] type, a trait for converting
   4 //! [`ToString`]s, and several error types that may result from working with
   5 //! [`String`]s.
   6 //!
   7 //! [`ToString`]: trait.ToString.html
   8 //!
   9 //! # Examples
  10 //!
  11 //! There are multiple ways to create a new [`String`] from a string literal:
  12 //!
  13 //! ```
  14 //! let s = "Hello".to_string();
  15 //!
  16 //! let s = String::from("world");
  17 //! let s: String = "also this".into();
  18 //! ```
  19 //!
  20 //! You can create a new [`String`] from an existing one by concatenating with
  21 //! `+`:
  22 //!
  23 //! [`String`]: struct.String.html
  24 //!
  25 //! ```
  26 //! let s = "Hello".to_string();
  27 //!
  28 //! let message = s + " world!";
  29 //! ```
  30 //!
  31 //! If you have a vector of valid UTF-8 bytes, you can make a [`String`] out of
  32 //! it. You can do the reverse too.
  33 //!
  34 //! ```
  35 //! let sparkle_heart = vec![240, 159, 146, 150];
  36 //!
  37 //! // We know these bytes are valid, so we'll use `unwrap()`.
  38 //! let sparkle_heart = String::from_utf8(sparkle_heart).unwrap();
  39 //!
  40 //! assert_eq!("💖", sparkle_heart);
  41 //!
  42 //! let bytes = sparkle_heart.into_bytes();
  43 //!
  44 //! assert_eq!(bytes, [240, 159, 146, 150]);
  45 //! ```
  46
  47 #![stable(feature = "rust1", since = "1.0.0")]
  48
  49 use core::{
  50     char::{decode_utf16, REPLACEMENT_CHARACTER},
  51     fmt,
  52     hash,
  53     iter::{FromIterator, FusedIterator},
  54     ops::{
  55         self,
  56         Bound::{Excluded, Included, Unbounded},
  57         Add, AddAssign, Index, IndexMut, RangeBounds,
  58     },
  59     ptr,
  60     str::{
  61         pattern::Pattern,
  62         lossy,
  63     }
  64 };
  65
  66 use crate::{
  67     collections::CollectionAllocErr,
  68     borrow::{Cow, ToOwned},
  69     boxed::Box,
  70     str::{self, from_boxed_utf8_unchecked, FromStr, Utf8Error, Chars},
  71     vec::Vec,
  72 };
  73
  74 /// A UTF-8 encoded, growable string.
  75 ///
  76 /// The `String` type is the most common string type that has ownership over the
  77 /// contents of the string. It has a close relationship with its borrowed
  78 /// counterpart, the primitive [`str`].
  79 ///
  80 /// [`str`]: ../../std/primitive.str.html
  81 ///
  82 /// # Examples
  83 ///
  84 /// You can create a `String` from a literal string with [`String::from`]:
  85 ///
  86 /// ```
  87 /// let hello = String::from("Hello, world!");
  88 /// ```
  89 ///
  90 /// You can append a [`char`] to a `String` with the [`push`] method, and
  91 /// append a [`&str`] with the [`push_str`] method:
  92 ///
  93 /// ```
  94 /// let mut hello = String::from("Hello, ");
  95 ///
  96 /// hello.push('w');
  97 /// hello.push_str("orld!");
  98 /// ```
  99 ///
 100 /// [`String::from`]: #method.from
 101 /// [`char`]: ../../std/primitive.char.html
 102 /// [`push`]: #method.push
 103 /// [`push_str`]: #method.push_str
 104 ///
 105 /// If you have a vector of UTF-8 bytes, you can create a `String` from it with
 106 /// the [`from_utf8`] method:
 107 ///
 108 /// ```
 109 /// // some bytes, in a vector
 110 /// let sparkle_heart = vec![240, 159, 146, 150];
 111 ///
 112 /// // We know these bytes are valid, so we'll use `unwrap()`.
 113 /// let sparkle_heart = String::from_utf8(sparkle_heart).unwrap();
 114 ///
 115 /// assert_eq!("💖", sparkle_heart);
 116 /// ```
 117 ///
 118 /// [`from_utf8`]: #method.from_utf8
 119 ///
 120 /// # UTF-8
 121 ///
 122 /// `String`s are always valid UTF-8. This has a few implications, the first of
 123 /// which is that if you need a non-UTF-8 string, consider [`OsString`]. It is
 124 /// similar, but without the UTF-8 constraint. The second implication is that
 125 /// you cannot index into a `String`:
 126 ///
 127 /// ```compile_fail,E0277
 128 /// let s = "hello";
 129 ///
 130 /// println!("The first letter of s is {}", s[0]); // ERROR!!!
 131 /// ```
 132 ///
 133 /// [`OsString`]: ../../std/ffi/struct.OsString.html
 134 ///
 135 /// Indexing is intended to be a constant-time operation, but UTF-8 encoding
 136 /// does not allow us to do this. Furthermore, it's not clear what sort of
 137 /// thing the index should return: a byte, a codepoint, or a grapheme cluster.
 138 /// The [`bytes`] and [`chars`] methods return iterators over the first
 139 /// two, respectively.
 140 ///
 141 /// [`bytes`]: #method.bytes
 142 /// [`chars`]: #method.chars
 143 ///
 144 /// # Deref
 145 ///
 146 /// `String`s implement [`Deref`]`<Target=str>`, and so inherit all of [`str`]'s
 147 /// methods. In addition, this means that you can pass a `String` to a
 148 /// function which takes a [`&str`] by using an ampersand (`&`):
 149 ///
 150 /// ```
 151 /// fn takes_str(s: &str) { }
 152 ///
 153 /// let s = String::from("Hello");
 154 ///
 155 /// takes_str(&s);
 156 /// ```
 157 ///
 158 /// This will create a [`&str`] from the `String` and pass it in. This
 159 /// conversion is very inexpensive, and so generally, functions will accept
 160 /// [`&str`]s as arguments unless they need a `String` for some specific
 161 /// reason.
 162 ///
 163 /// In certain cases Rust doesn't have enough information to make this
 164 /// conversion, known as [`Deref`] coercion. In the following example a string
 165 /// slice [`&'a str`][`&str`] implements the trait `TraitExample`, and the function
 166 /// `example_func` takes anything that implements the trait. In this case Rust
 167 /// would need to make two implicit conversions, which Rust doesn't have the
 168 /// means to do. For that reason, the following example will not compile.
 169 ///
 170 /// ```compile_fail,E0277
 171 /// trait TraitExample {}
 172 ///
 173 /// impl<'a> TraitExample for &'a str {}
 174 ///
 175 /// fn example_func<A: TraitExample>(example_arg: A) {}
 176 ///
 177 /// fn main() {
 178 ///     let example_string = String::from("example_string");
 179 ///     example_func(&example_string);
 180 /// }
 181 /// ```
 182 ///
 183 /// There are two options that would work instead. The first would be to
 184 /// change the line `example_func(&example_string);` to
 185 /// `example_func(example_string.as_str());`, using the method [`as_str()`]
 186 /// to explicitly extract the string slice containing the string. The second
 187 /// way changes `example_func(&example_string);` to
 188 /// `example_func(&*example_string);`. In this case we are dereferencing a
 189 /// `String` to a [`str`][`&str`], then referencing the [`str`][`&str`] back to
 190 /// [`&str`]. The second way is more idiomatic, however both work to do the
 191 /// conversion explicitly rather than relying on the implicit conversion.
 192 ///
 193 /// # Representation
 194 ///
 195 /// A `String` is made up of three components: a pointer to some bytes, a
 196 /// length, and a capacity. The pointer points to an internal buffer `String`
 197 /// uses to store its data. The length is the number of bytes currently stored
 198 /// in the buffer, and the capacity is the size of the buffer in bytes. As such,
 199 /// the length will always be less than or equal to the capacity.
 200 ///
 201 /// This buffer is always stored on the heap.
 202 ///
 203 /// You can look at these with the [`as_ptr`], [`len`], and [`capacity`]
 204 /// methods:
 205 ///
 206 /// ```
 207 /// use std::mem;
 208 ///
 209 /// let story = String::from("Once upon a time...");
 210 ///
 211 /// let ptr = story.as_ptr();
 212 /// let len = story.len();
 213 /// let capacity = story.capacity();
 214 ///
 215 /// // story has nineteen bytes
 216 /// assert_eq!(19, len);
 217 ///
 218 /// // Now that we have our parts, we throw the story away.
 219 /// mem::forget(story);
 220 ///
 221 /// // We can re-build a String out of ptr, len, and capacity. This is all
 222 /// // unsafe because we are responsible for making sure the components are
 223 /// // valid:
 224 /// let s = unsafe { String::from_raw_parts(ptr as *mut _, len, capacity) } ;
 225 ///
 226 /// assert_eq!(String::from("Once upon a time..."), s);
 227 /// ```
 228 ///
 229 /// [`as_ptr`]: #method.as_ptr
 230 /// [`len`]: #method.len
 231 /// [`capacity`]: #method.capacity
 232 ///
 233 /// If a `String` has enough capacity, adding elements to it will not
 234 /// re-allocate. For example, consider this program:
 235 ///
 236 /// ```
 237 /// let mut s = String::new();
 238 ///
 239 /// println!("{}", s.capacity());
 240 ///
 241 /// for _ in 0..5 {
 242 ///     s.push_str("hello");
 243 ///     println!("{}", s.capacity());
 244 /// }
 245 /// ```
 246 ///
 247 /// This will output the following:
 248 ///
 249 /// ```text
 250 /// 0
 251 /// 5
 252 /// 10
 253 /// 20
 254 /// 20
 255 /// 40
 256 /// ```
 257 ///
 258 /// At first, we have no memory allocated at all, but as we append to the
 259 /// string, it increases its capacity appropriately. If we instead use the
 260 /// [`with_capacity`] method to allocate the correct capacity initially:
 261 ///
 262 /// ```
 263 /// let mut s = String::with_capacity(25);
 264 ///
 265 /// println!("{}", s.capacity());
 266 ///
 267 /// for _ in 0..5 {
 268 ///     s.push_str("hello");
 269 ///     println!("{}", s.capacity());
 270 /// }
 271 /// ```
 272 ///
 273 /// [`with_capacity`]: #method.with_capacity
 274 ///
 275 /// We end up with a different output:
 276 ///
 277 /// ```text
 278 /// 25
 279 /// 25
 280 /// 25
 281 /// 25
 282 /// 25
 283 /// 25
 284 /// ```
 285 ///
 286 /// Here, there's no need to allocate more memory inside the loop.
 287 ///
 288 /// [`&str`]: ../../std/primitive.str.html
 289 /// [`Deref`]: ../../std/ops/trait.Deref.html
 290 /// [`as_str()`]: struct.String.html#method.as_str
 291 #[derive(PartialOrd, Eq, Ord)]
 292 #[stable(feature = "rust1", since = "1.0.0")]
 293 pub struct String {
 294     vec: Vec<u8>,
 295 }
 296
 297 /// A possible error value when converting a `String` from a UTF-8 byte vector.
 298 ///
 299 /// This type is the error type for the [`from_utf8`] method on [`String`]. It
 300 /// is designed in such a way to carefully avoid reallocations: the
 301 /// [`into_bytes`] method will give back the byte vector that was used in the
 302 /// conversion attempt.
 303 ///
 304 /// [`from_utf8`]: struct.String.html#method.from_utf8
 305 /// [`String`]: struct.String.html
 306 /// [`into_bytes`]: struct.FromUtf8Error.html#method.into_bytes
 307 ///
 308 /// The [`Utf8Error`] type provided by [`std::str`] represents an error that may
 309 /// occur when converting a slice of [`u8`]s to a [`&str`]. In this sense, it's
 310 /// an analogue to `FromUtf8Error`, and you can get one from a `FromUtf8Error`
 311 /// through the [`utf8_error`] method.
 312 ///
 313 /// [`Utf8Error`]: ../../std/str/struct.Utf8Error.html
 314 /// [`std::str`]: ../../std/str/index.html
 315 /// [`u8`]: ../../std/primitive.u8.html
 316 /// [`&str`]: ../../std/primitive.str.html
 317 /// [`utf8_error`]: #method.utf8_error
 318 ///
 319 /// # Examples
 320 ///
 321 /// Basic usage:
 322 ///
 323 /// ```
 324 /// // some invalid bytes, in a vector
 325 /// let bytes = vec![0, 159];
 326 ///
 327 /// let value = String::from_utf8(bytes);
 328 ///
 329 /// assert!(value.is_err());
 330 /// assert_eq!(vec![0, 159], value.unwrap_err().into_bytes());
 331 /// ```
 332 #[stable(feature = "rust1", since = "1.0.0")]
 333 #[derive(Debug)]
 334 pub struct FromUtf8Error {
 335     bytes: Vec<u8>,
 336     error: Utf8Error,
 337 }
 338
 339 /// A possible error value when converting a `String` from a UTF-16 byte slice.
 340 ///
 341 /// This type is the error type for the [`from_utf16`] method on [`String`].
 342 ///
 343 /// [`from_utf16`]: struct.String.html#method.from_utf16
 344 /// [`String`]: struct.String.html
 345 ///
 346 /// # Examples
 347 ///
 348 /// Basic usage:
 349 ///
 350 /// ```
 351 /// // 𝄞mu<invalid>ic
 352 /// let v = &[0xD834, 0xDD1E, 0x006d, 0x0075,
 353 ///           0xD800, 0x0069, 0x0063];
 354 ///
 355 /// assert!(String::from_utf16(v).is_err());
 356 /// ```
 357 #[stable(feature = "rust1", since = "1.0.0")]
 358 #[derive(Debug)]
 359 pub struct FromUtf16Error(());
 360
 361 impl String {
 362     /// Creates a new empty `String`.
 363     ///
 364     /// Given that the `String` is empty, this will not allocate any initial
 365     /// buffer. While that means that this initial operation is very
 366     /// inexpensive, it may cause excessive allocation later when you add
 367     /// data. If you have an idea of how much data the `String` will hold,
 368     /// consider the [`with_capacity`] method to prevent excessive
 369     /// re-allocation.
 370     ///
 371     /// [`with_capacity`]: #method.with_capacity
 372     ///
 373     /// # Examples
 374     ///
 375     /// Basic usage:
 376     ///
 377     /// ```
 378     /// let s = String::new();
 379     /// ```
 380     #[inline]
 381     #[stable(feature = "rust1", since = "1.0.0")]
 382     #[rustc_const_unstable(feature = "const_string_new")]
 383     pub const fn new() -> String {
 384         String { vec: Vec::new() }
 385     }
 386
 387     /// Creates a new empty `String` with a particular capacity.
 388     ///
 389     /// `String`s have an internal buffer to hold their data. The capacity is
 390     /// the length of that buffer, and can be queried with the [`capacity`]
 391     /// method. This method creates an empty `String`, but one with an initial
 392     /// buffer that can hold `capacity` bytes. This is useful when you may be
 393     /// appending a bunch of data to the `String`, reducing the number of
 394     /// reallocations it needs to do.
 395     ///
 396     /// [`capacity`]: #method.capacity
 397     ///
 398     /// If the given capacity is `0`, no allocation will occur, and this method
 399     /// is identical to the [`new`] method.
 400     ///
 401     /// [`new`]: #method.new
 402     ///
 403     /// # Examples
 404     ///
 405     /// Basic usage:
 406     ///
 407     /// ```
 408     /// let mut s = String::with_capacity(10);
 409     ///
 410     /// // The String contains no chars, even though it has capacity for more
 411     /// assert_eq!(s.len(), 0);
 412     ///
 413     /// // These are all done without reallocating...
 414     /// let cap = s.capacity();
 415     /// for _ in 0..10 {
 416     ///     s.push('a');
 417     /// }
 418     ///
 419     /// assert_eq!(s.capacity(), cap);
 420     ///
 421     /// // ...but this may make the vector reallocate
 422     /// s.push('a');
 423     /// ```
 424     #[inline]
 425     #[stable(feature = "rust1", since = "1.0.0")]
 426     pub fn with_capacity(capacity: usize) -> String {
 427         String { vec: Vec::with_capacity(capacity) }
 428     }
 429
 430     // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
 431     // required for this method definition, is not available. Since we don't
 432     // require this method for testing purposes, I'll just stub it
 433     // NB see the slice::hack module in slice.rs for more information
 434     #[inline]
 435     #[cfg(test)]
 436     pub fn from_str(_: &str) -> String {
 437         panic!("not available with cfg(test)");
 438     }
 439
 440     /// Converts a vector of bytes to a `String`.
 441     ///
 442     /// A string slice ([`&str`]) is made of bytes ([`u8`]), and a vector of bytes
 443     /// ([`Vec<u8>`]) is made of bytes, so this function converts between the
 444     /// two. Not all byte slices are valid `String`s, however: `String`
 445     /// requires that it is valid UTF-8. `from_utf8()` checks to ensure that
 446     /// the bytes are valid UTF-8, and then does the conversion.
 447     ///
 448     /// If you are sure that the byte slice is valid UTF-8, and you don't want
 449     /// to incur the overhead of the validity check, there is an unsafe version
 450     /// of this function, [`from_utf8_unchecked`], which has the same behavior
 451     /// but skips the check.
 452     ///
 453     /// This method will take care to not copy the vector, for efficiency's
 454     /// sake.
 455     ///
 456     /// If you need a [`&str`] instead of a `String`, consider
 457     /// [`str::from_utf8`].
 458     ///
 459     /// The inverse of this method is [`as_bytes`].
 460     ///
 461     /// # Errors
 462     ///
 463     /// Returns [`Err`] if the slice is not UTF-8 with a description as to why the
 464     /// provided bytes are not UTF-8. The vector you moved in is also included.
 465     ///
 466     /// # Examples
 467     ///
 468     /// Basic usage:
 469     ///
 470     /// ```
 471     /// // some bytes, in a vector
 472     /// let sparkle_heart = vec![240, 159, 146, 150];
 473     ///
 474     /// // We know these bytes are valid, so we'll use `unwrap()`.
 475     /// let sparkle_heart = String::from_utf8(sparkle_heart).unwrap();
 476     ///
 477     /// assert_eq!("💖", sparkle_heart);
 478     /// ```
 479     ///
 480     /// Incorrect bytes:
 481     ///
 482     /// ```
 483     /// // some invalid bytes, in a vector
 484     /// let sparkle_heart = vec![0, 159, 146, 150];
 485     ///
 486     /// assert!(String::from_utf8(sparkle_heart).is_err());
 487     /// ```
 488     ///
 489     /// See the docs for [`FromUtf8Error`] for more details on what you can do
 490     /// with this error.
 491     ///
 492     /// [`from_utf8_unchecked`]: struct.String.html#method.from_utf8_unchecked
 493     /// [`&str`]: ../../std/primitive.str.html
 494     /// [`u8`]: ../../std/primitive.u8.html
 495     /// [`Vec<u8>`]: ../../std/vec/struct.Vec.html
 496     /// [`str::from_utf8`]: ../../std/str/fn.from_utf8.html
 497     /// [`as_bytes`]: struct.String.html#method.as_bytes
 498     /// [`FromUtf8Error`]: struct.FromUtf8Error.html
 499     /// [`Err`]: ../../stdresult/enum.Result.html#variant.Err
 500     #[inline]
 501     #[stable(feature = "rust1", since = "1.0.0")]
 502     pub fn from_utf8(vec: Vec<u8>) -> Result<String, FromUtf8Error> {
 503         match str::from_utf8(&vec) {
 504             Ok(..) => Ok(String { vec }),
 505             Err(e) => {
 506                 Err(FromUtf8Error {
 507                     bytes: vec,
 508                     error: e,
 509                 })
 510             }
 511         }
 512     }
 513
 514     /// Converts a slice of bytes to a string, including invalid characters.
 515     ///
 516     /// Strings are made of bytes ([`u8`]), and a slice of bytes
 517     /// ([`&[u8]`][byteslice]) is made of bytes, so this function converts
 518     /// between the two. Not all byte slices are valid strings, however: strings
 519     /// are required to be valid UTF-8. During this conversion,
 520     /// `from_utf8_lossy()` will replace any invalid UTF-8 sequences with
 521     /// [`U+FFFD REPLACEMENT CHARACTER`][U+FFFD], which looks like this: �
 522     ///
 523     /// [`u8`]: ../../std/primitive.u8.html
 524     /// [byteslice]: ../../std/primitive.slice.html
 525     /// [U+FFFD]: ../char/constant.REPLACEMENT_CHARACTER.html
 526     ///
 527     /// If you are sure that the byte slice is valid UTF-8, and you don't want
 528     /// to incur the overhead of the conversion, there is an unsafe version
 529     /// of this function, [`from_utf8_unchecked`], which has the same behavior
 530     /// but skips the checks.
 531     ///
 532     /// [`from_utf8_unchecked`]: struct.String.html#method.from_utf8_unchecked
 533     ///
 534     /// This function returns a [`Cow<'a, str>`]. If our byte slice is invalid
 535     /// UTF-8, then we need to insert the replacement characters, which will
 536     /// change the size of the string, and hence, require a `String`. But if
 537     /// it's already valid UTF-8, we don't need a new allocation. This return
 538     /// type allows us to handle both cases.
 539     ///
 540     /// [`Cow<'a, str>`]: ../../std/borrow/enum.Cow.html
 541     ///
 542     /// # Examples
 543     ///
 544     /// Basic usage:
 545     ///
 546     /// ```
 547     /// // some bytes, in a vector
 548     /// let sparkle_heart = vec![240, 159, 146, 150];
 549     ///
 550     /// let sparkle_heart = String::from_utf8_lossy(&sparkle_heart);
 551     ///
 552     /// assert_eq!("💖", sparkle_heart);
 553     /// ```
 554     ///
 555     /// Incorrect bytes:
 556     ///
 557     /// ```
 558     /// // some invalid bytes
 559     /// let input = b"Hello \xF0\x90\x80World";
 560     /// let output = String::from_utf8_lossy(input);
 561     ///
 562     /// assert_eq!("Hello �World", output);
 563     /// ```
 564     #[stable(feature = "rust1", since = "1.0.0")]
 565     pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> Cow<'a, str> {
 566         let mut iter = lossy::Utf8Lossy::from_bytes(v).chunks();
 567
 568         let (first_valid, first_broken) = if let Some(chunk) = iter.next() {
 569             let lossy::Utf8LossyChunk { valid, broken } = chunk;
 570             if valid.len() == v.len() {
 571                 debug_assert!(broken.is_empty());
 572                 return Cow::Borrowed(valid);
 573             }
 574             (valid, broken)
 575         } else {
 576             return Cow::Borrowed("");
 577         };
 578
 579         const REPLACEMENT: &str = "\u{FFFD}";
 580
 581         let mut res = String::with_capacity(v.len());
 582         res.push_str(first_valid);
 583         if !first_broken.is_empty() {
 584             res.push_str(REPLACEMENT);
 585         }
 586
 587         for lossy::Utf8LossyChunk { valid, broken } in iter {
 588             res.push_str(valid);
 589             if !broken.is_empty() {
 590                 res.push_str(REPLACEMENT);
 591             }
 592         }
 593
 594         Cow::Owned(res)
 595     }
 596
 597     /// Decode a UTF-16 encoded vector `v` into a `String`, returning [`Err`]
 598     /// if `v` contains any invalid data.
 599     ///
 600     /// [`Err`]: ../../std/result/enum.Result.html#variant.Err
 601     ///
 602     /// # Examples
 603     ///
 604     /// Basic usage:
 605     ///
 606     /// ```
 607     /// // 𝄞music
 608     /// let v = &[0xD834, 0xDD1E, 0x006d, 0x0075,
 609     ///           0x0073, 0x0069, 0x0063];
 610     /// assert_eq!(String::from("𝄞music"),
 611     ///            String::from_utf16(v).unwrap());
 612     ///
 613     /// // 𝄞mu<invalid>ic
 614     /// let v = &[0xD834, 0xDD1E, 0x006d, 0x0075,
 615     ///           0xD800, 0x0069, 0x0063];
 616     /// assert!(String::from_utf16(v).is_err());
 617     /// ```
 618     #[stable(feature = "rust1", since = "1.0.0")]
 619     pub fn from_utf16(v: &[u16]) -> Result<String, FromUtf16Error> {
 620         // This isn't done via collect::<Result<_, _>>() for performance reasons.
 621         // FIXME: the function can be simplified again when #48994 is closed.
 622         let mut ret = String::with_capacity(v.len());
 623         for c in decode_utf16(v.iter().cloned()) {
 624             if let Ok(c) = c {
 625                 ret.push(c);
 626             } else {
 627                 return Err(FromUtf16Error(()));
 628             }
 629         }
 630         Ok(ret)
 631     }
 632
 633     /// Decode a UTF-16 encoded slice `v` into a `String`, replacing
 634     /// invalid data with [the replacement character (`U+FFFD`)][U+FFFD].
 635     ///
 636     /// Unlike [`from_utf8_lossy`] which returns a [`Cow<'a, str>`],
 637     /// `from_utf16_lossy` returns a `String` since the UTF-16 to UTF-8
 638     /// conversion requires a memory allocation.
 639     ///
 640     /// [`from_utf8_lossy`]: #method.from_utf8_lossy
 641     /// [`Cow<'a, str>`]: ../borrow/enum.Cow.html
 642     /// [U+FFFD]: ../char/constant.REPLACEMENT_CHARACTER.html
 643     ///
 644     /// # Examples
 645     ///
 646     /// Basic usage:
 647     ///
 648     /// ```
 649     /// // 𝄞mus<invalid>ic<invalid>
 650     /// let v = &[0xD834, 0xDD1E, 0x006d, 0x0075,
 651     ///           0x0073, 0xDD1E, 0x0069, 0x0063,
 652     ///           0xD834];
 653     ///
 654     /// assert_eq!(String::from("𝄞mus\u{FFFD}ic\u{FFFD}"),
 655     ///            String::from_utf16_lossy(v));
 656     /// ```
 657     #[inline]
 658     #[stable(feature = "rust1", since = "1.0.0")]
 659     pub fn from_utf16_lossy(v: &[u16]) -> String {
 660         decode_utf16(v.iter().cloned()).map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)).collect()
 661     }
 662
 663     /// Creates a new `String` from a length, capacity, and pointer.
 664     ///
 665     /// # Safety
 666     ///
 667     /// This is highly unsafe, due to the number of invariants that aren't
 668     /// checked:
 669     ///
 670     /// * The memory at `ptr` needs to have been previously allocated by the
 671     ///   same allocator the standard library uses.
 672     /// * `length` needs to be less than or equal to `capacity`.
 673     /// * `capacity` needs to be the correct value.
 674     ///
 675     /// Violating these may cause problems like corrupting the allocator's
 676     /// internal data structures.
 677     ///
 678     /// The ownership of `ptr` is effectively transferred to the
 679     /// `String` which may then deallocate, reallocate or change the
 680     /// contents of memory pointed to by the pointer at will. Ensure
 681     /// that nothing else uses the pointer after calling this
 682     /// function.
 683     ///
 684     /// # Examples
 685     ///
 686     /// Basic usage:
 687     ///
 688     /// ```
 689     /// use std::mem;
 690     ///
 691     /// unsafe {
 692     ///     let s = String::from("hello");
 693     ///     let ptr = s.as_ptr();
 694     ///     let len = s.len();
 695     ///     let capacity = s.capacity();
 696     ///
 697     ///     mem::forget(s);
 698     ///
 699     ///     let s = String::from_raw_parts(ptr as *mut _, len, capacity);
 700     ///
 701     ///     assert_eq!(String::from("hello"), s);
 702     /// }
 703     /// ```
 704     #[inline]
 705     #[stable(feature = "rust1", since = "1.0.0")]
 706     pub unsafe fn from_raw_parts(buf: *mut u8, length: usize, capacity: usize) -> String {
 707         String { vec: Vec::from_raw_parts(buf, length, capacity) }
 708     }
 709
 710     /// Converts a vector of bytes to a `String` without checking that the
 711     /// string contains valid UTF-8.
 712     ///
 713     /// See the safe version, [`from_utf8`], for more details.
 714     ///
 715     /// [`from_utf8`]: struct.String.html#method.from_utf8
 716     ///
 717     /// # Safety
 718     ///
 719     /// This function is unsafe because it does not check that the bytes passed
 720     /// to it are valid UTF-8. If this constraint is violated, it may cause
 721     /// memory unsafety issues with future users of the `String`, as the rest of
 722     /// the standard library assumes that `String`s are valid UTF-8.
 723     ///
 724     /// # Examples
 725     ///
 726     /// Basic usage:
 727     ///
 728     /// ```
 729     /// // some bytes, in a vector
 730     /// let sparkle_heart = vec![240, 159, 146, 150];
 731     ///
 732     /// let sparkle_heart = unsafe {
 733     ///     String::from_utf8_unchecked(sparkle_heart)
 734     /// };
 735     ///
 736     /// assert_eq!("💖", sparkle_heart);
 737     /// ```
 738     #[inline]
 739     #[stable(feature = "rust1", since = "1.0.0")]
 740     pub unsafe fn from_utf8_unchecked(bytes: Vec<u8>) -> String {
 741         String { vec: bytes }
 742     }
 743
 744     /// Converts a `String` into a byte vector.
 745     ///
 746     /// This consumes the `String`, so we do not need to copy its contents.
 747     ///
 748     /// # Examples
 749     ///
 750     /// Basic usage:
 751     ///
 752     /// ```
 753     /// let s = String::from("hello");
 754     /// let bytes = s.into_bytes();
 755     ///
 756     /// assert_eq!(&[104, 101, 108, 108, 111][..], &bytes[..]);
 757     /// ```
 758     #[inline]
 759     #[stable(feature = "rust1", since = "1.0.0")]
 760     pub fn into_bytes(self) -> Vec<u8> {
 761         self.vec
 762     }
 763
 764     /// Extracts a string slice containing the entire `String`.
 765     ///
 766     /// # Examples
 767     ///
 768     /// Basic usage:
 769     ///
 770     /// ```
 771     /// let s = String::from("foo");
 772     ///
 773     /// assert_eq!("foo", s.as_str());
 774     /// ```
 775     #[inline]
 776     #[stable(feature = "string_as_str", since = "1.7.0")]
 777     pub fn as_str(&self) -> &str {
 778         self
 779     }
 780
 781     /// Converts a `String` into a mutable string slice.
 782     ///
 783     /// # Examples
 784     ///
 785     /// Basic usage:
 786     ///
 787     /// ```
 788     /// let mut s = String::from("foobar");
 789     /// let s_mut_str = s.as_mut_str();
 790     ///
 791     /// s_mut_str.make_ascii_uppercase();
 792     ///
 793     /// assert_eq!("FOOBAR", s_mut_str);
 794     /// ```
 795     #[inline]
 796     #[stable(feature = "string_as_str", since = "1.7.0")]
 797     pub fn as_mut_str(&mut self) -> &mut str {
 798         self
 799     }
 800
 801     /// Appends a given string slice onto the end of this `String`.
 802     ///
 803     /// # Examples
 804     ///
 805     /// Basic usage:
 806     ///
 807     /// ```
 808     /// let mut s = String::from("foo");
 809     ///
 810     /// s.push_str("bar");
 811     ///
 812     /// assert_eq!("foobar", s);
 813     /// ```
 814     #[inline]
 815     #[stable(feature = "rust1", since = "1.0.0")]
 816     pub fn push_str(&mut self, string: &str) {
 817         self.vec.extend_from_slice(string.as_bytes())
 818     }
 819
 820     /// Returns this `String`'s capacity, in bytes.
 821     ///
 822     /// # Examples
 823     ///
 824     /// Basic usage:
 825     ///
 826     /// ```
 827     /// let s = String::with_capacity(10);
 828     ///
 829     /// assert!(s.capacity() >= 10);
 830     /// ```
 831     #[inline]
 832     #[stable(feature = "rust1", since = "1.0.0")]
 833     pub fn capacity(&self) -> usize {
 834         self.vec.capacity()
 835     }
 836
 837     /// Ensures that this `String`'s capacity is at least `additional` bytes
 838     /// larger than its length.
 839     ///
 840     /// The capacity may be increased by more than `additional` bytes if it
 841     /// chooses, to prevent frequent reallocations.
 842     ///
 843     /// If you do not want this "at least" behavior, see the [`reserve_exact`]
 844     /// method.
 845     ///
 846     /// # Panics
 847     ///
 848     /// Panics if the new capacity overflows [`usize`].
 849     ///
 850     /// [`reserve_exact`]: struct.String.html#method.reserve_exact
 851     /// [`usize`]: ../../std/primitive.usize.html
 852     ///
 853     /// # Examples
 854     ///
 855     /// Basic usage:
 856     ///
 857     /// ```
 858     /// let mut s = String::new();
 859     ///
 860     /// s.reserve(10);
 861     ///
 862     /// assert!(s.capacity() >= 10);
 863     /// ```
 864     ///
 865     /// This may not actually increase the capacity:
 866     ///
 867     /// ```
 868     /// let mut s = String::with_capacity(10);
 869     /// s.push('a');
 870     /// s.push('b');
 871     ///
 872     /// // s now has a length of 2 and a capacity of 10
 873     /// assert_eq!(2, s.len());
 874     /// assert_eq!(10, s.capacity());
 875     ///
 876     /// // Since we already have an extra 8 capacity, calling this...
 877     /// s.reserve(8);
 878     ///
 879     /// // ... doesn't actually increase.
 880     /// assert_eq!(10, s.capacity());
 881     /// ```
 882     #[inline]
 883     #[stable(feature = "rust1", since = "1.0.0")]
 884     pub fn reserve(&mut self, additional: usize) {
 885         self.vec.reserve(additional)
 886     }
 887
 888     /// Ensures that this `String`'s capacity is `additional` bytes
 889     /// larger than its length.
 890     ///
 891     /// Consider using the [`reserve`] method unless you absolutely know
 892     /// better than the allocator.
 893     ///
 894     /// [`reserve`]: #method.reserve
 895     ///
 896     /// # Panics
 897     ///
 898     /// Panics if the new capacity overflows `usize`.
 899     ///
 900     /// # Examples
 901     ///
 902     /// Basic usage:
 903     ///
 904     /// ```
 905     /// let mut s = String::new();
 906     ///
 907     /// s.reserve_exact(10);
 908     ///
 909     /// assert!(s.capacity() >= 10);
 910     /// ```
 911     ///
 912     /// This may not actually increase the capacity:
 913     ///
 914     /// ```
 915     /// let mut s = String::with_capacity(10);
 916     /// s.push('a');
 917     /// s.push('b');
 918     ///
 919     /// // s now has a length of 2 and a capacity of 10
 920     /// assert_eq!(2, s.len());
 921     /// assert_eq!(10, s.capacity());
 922     ///
 923     /// // Since we already have an extra 8 capacity, calling this...
 924     /// s.reserve_exact(8);
 925     ///
 926     /// // ... doesn't actually increase.
 927     /// assert_eq!(10, s.capacity());
 928     /// ```
 929     #[inline]
 930     #[stable(feature = "rust1", since = "1.0.0")]
 931     pub fn reserve_exact(&mut self, additional: usize) {
 932         self.vec.reserve_exact(additional)
 933     }
 934
 935     /// Tries to reserve capacity for at least `additional` more elements to be inserted
 936     /// in the given `String`. The collection may reserve more space to avoid
 937     /// frequent reallocations. After calling `reserve`, capacity will be
 938     /// greater than or equal to `self.len() + additional`. Does nothing if
 939     /// capacity is already sufficient.
 940     ///
 941     /// # Errors
 942     ///
 943     /// If the capacity overflows, or the allocator reports a failure, then an error
 944     /// is returned.
 945     ///
 946     /// # Examples
 947     ///
 948     /// ```
 949     /// #![feature(try_reserve)]
 950     /// use std::collections::CollectionAllocErr;
 951     ///
 952     /// fn process_data(data: &str) -> Result<String, CollectionAllocErr> {
 953     ///     let mut output = String::new();
 954     ///
 955     ///     // Pre-reserve the memory, exiting if we can't
 956     ///     output.try_reserve(data.len())?;
 957     ///
 958     ///     // Now we know this can't OOM in the middle of our complex work
 959     ///     output.push_str(data);
 960     ///
 961     ///     Ok(output)
 962     /// }
 963     /// # process_data("rust").expect("why is the test harness OOMing on 4 bytes?");
 964     /// ```
 965     #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
 966     pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
 967         self.vec.try_reserve(additional)
 968     }
 969
 970     /// Tries to reserves the minimum capacity for exactly `additional` more elements to
 971     /// be inserted in the given `String`. After calling `reserve_exact`,
 972     /// capacity will be greater than or equal to `self.len() + additional`.
 973     /// Does nothing if the capacity is already sufficient.
 974     ///
 975     /// Note that the allocator may give the collection more space than it
 976     /// requests. Therefore capacity can not be relied upon to be precisely
 977     /// minimal. Prefer `reserve` if future insertions are expected.
 978     ///
 979     /// # Errors
 980     ///
 981     /// If the capacity overflows, or the allocator reports a failure, then an error
 982     /// is returned.
 983     ///
 984     /// # Examples
 985     ///
 986     /// ```
 987     /// #![feature(try_reserve)]
 988     /// use std::collections::CollectionAllocErr;
 989     ///
 990     /// fn process_data(data: &str) -> Result<String, CollectionAllocErr> {
 991     ///     let mut output = String::new();
 992     ///
 993     ///     // Pre-reserve the memory, exiting if we can't
 994     ///     output.try_reserve(data.len())?;
 995     ///
 996     ///     // Now we know this can't OOM in the middle of our complex work
 997     ///     output.push_str(data);
 998     ///
 999     ///     Ok(output)
1000     /// }
1001     /// # process_data("rust").expect("why is the test harness OOMing on 4 bytes?");
1002     /// ```
1003     #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
1004     pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr>  {
1005         self.vec.try_reserve_exact(additional)
1006     }
1007
1008     /// Shrinks the capacity of this `String` to match its length.
1009     ///
1010     /// # Examples
1011     ///
1012     /// Basic usage:
1013     ///
1014     /// ```
1015     /// let mut s = String::from("foo");
1016     ///
1017     /// s.reserve(100);
1018     /// assert!(s.capacity() >= 100);
1019     ///
1020     /// s.shrink_to_fit();
1021     /// assert_eq!(3, s.capacity());
1022     /// ```
1023     #[inline]
1024     #[stable(feature = "rust1", since = "1.0.0")]
1025     pub fn shrink_to_fit(&mut self) {
1026         self.vec.shrink_to_fit()
1027     }
1028
1029     /// Shrinks the capacity of this `String` with a lower bound.
1030     ///
1031     /// The capacity will remain at least as large as both the length
1032     /// and the supplied value.
1033     ///
1034     /// Panics if the current capacity is smaller than the supplied
1035     /// minimum capacity.
1036     ///
1037     /// # Examples
1038     ///
1039     /// ```
1040     /// #![feature(shrink_to)]
1041     /// let mut s = String::from("foo");
1042     ///
1043     /// s.reserve(100);
1044     /// assert!(s.capacity() >= 100);
1045     ///
1046     /// s.shrink_to(10);
1047     /// assert!(s.capacity() >= 10);
1048     /// s.shrink_to(0);
1049     /// assert!(s.capacity() >= 3);
1050     /// ```
1051     #[inline]
1052     #[unstable(feature = "shrink_to", reason = "new API", issue="56431")]
1053     pub fn shrink_to(&mut self, min_capacity: usize) {
1054         self.vec.shrink_to(min_capacity)
1055     }
1056
1057     /// Appends the given [`char`] to the end of this `String`.
1058     ///
1059     /// [`char`]: ../../std/primitive.char.html
1060     ///
1061     /// # Examples
1062     ///
1063     /// Basic usage:
1064     ///
1065     /// ```
1066     /// let mut s = String::from("abc");
1067     ///
1068     /// s.push('1');
1069     /// s.push('2');
1070     /// s.push('3');
1071     ///
1072     /// assert_eq!("abc123", s);
1073     /// ```
1074     #[inline]
1075     #[stable(feature = "rust1", since = "1.0.0")]
1076     pub fn push(&mut self, ch: char) {
1077         match ch.len_utf8() {
1078             1 => self.vec.push(ch as u8),
1079             _ => self.vec.extend_from_slice(ch.encode_utf8(&mut [0; 4]).as_bytes()),
1080         }
1081     }
1082
1083     /// Returns a byte slice of this `String`'s contents.
1084     ///
1085     /// The inverse of this method is [`from_utf8`].
1086     ///
1087     /// [`from_utf8`]: #method.from_utf8
1088     ///
1089     /// # Examples
1090     ///
1091     /// Basic usage:
1092     ///
1093     /// ```
1094     /// let s = String::from("hello");
1095     ///
1096     /// assert_eq!(&[104, 101, 108, 108, 111], s.as_bytes());
1097     /// ```
1098     #[inline]
1099     #[stable(feature = "rust1", since = "1.0.0")]
1100     pub fn as_bytes(&self) -> &[u8] {
1101         &self.vec
1102     }
1103
1104     /// Shortens this `String` to the specified length.
1105     ///
1106     /// If `new_len` is greater than the string's current length, this has no
1107     /// effect.
1108     ///
1109     /// Note that this method has no effect on the allocated capacity
1110     /// of the string
1111     ///
1112     /// # Panics
1113     ///
1114     /// Panics if `new_len` does not lie on a [`char`] boundary.
1115     ///
1116     /// [`char`]: ../../std/primitive.char.html
1117     ///
1118     /// # Examples
1119     ///
1120     /// Basic usage:
1121     ///
1122     /// ```
1123     /// let mut s = String::from("hello");
1124     ///
1125     /// s.truncate(2);
1126     ///
1127     /// assert_eq!("he", s);
1128     /// ```
1129     #[inline]
1130     #[stable(feature = "rust1", since = "1.0.0")]
1131     pub fn truncate(&mut self, new_len: usize) {
1132         if new_len <= self.len() {
1133             assert!(self.is_char_boundary(new_len));
1134             self.vec.truncate(new_len)
1135         }
1136     }
1137
1138     /// Removes the last character from the string buffer and returns it.
1139     ///
1140     /// Returns [`None`] if this `String` is empty.
1141     ///
1142     /// [`None`]: ../../std/option/enum.Option.html#variant.None
1143     ///
1144     /// # Examples
1145     ///
1146     /// Basic usage:
1147     ///
1148     /// ```
1149     /// let mut s = String::from("foo");
1150     ///
1151     /// assert_eq!(s.pop(), Some('o'));
1152     /// assert_eq!(s.pop(), Some('o'));
1153     /// assert_eq!(s.pop(), Some('f'));
1154     ///
1155     /// assert_eq!(s.pop(), None);
1156     /// ```
1157     #[inline]
1158     #[stable(feature = "rust1", since = "1.0.0")]
1159     pub fn pop(&mut self) -> Option<char> {
1160         let ch = self.chars().rev().next()?;
1161         let newlen = self.len() - ch.len_utf8();
1162         unsafe {
1163             self.vec.set_len(newlen);
1164         }
1165         Some(ch)
1166     }
1167
1168     /// Removes a [`char`] from this `String` at a byte position and returns it.
1169     ///
1170     /// This is an `O(n)` operation, as it requires copying every element in the
1171     /// buffer.
1172     ///
1173     /// # Panics
1174     ///
1175     /// Panics if `idx` is larger than or equal to the `String`'s length,
1176     /// or if it does not lie on a [`char`] boundary.
1177     ///
1178     /// [`char`]: ../../std/primitive.char.html
1179     ///
1180     /// # Examples
1181     ///
1182     /// Basic usage:
1183     ///
1184     /// ```
1185     /// let mut s = String::from("foo");
1186     ///
1187     /// assert_eq!(s.remove(0), 'f');
1188     /// assert_eq!(s.remove(1), 'o');
1189     /// assert_eq!(s.remove(0), 'o');
1190     /// ```
1191     #[inline]
1192     #[stable(feature = "rust1", since = "1.0.0")]
1193     pub fn remove(&mut self, idx: usize) -> char {
1194         let ch = match self[idx..].chars().next() {
1195             Some(ch) => ch,
1196             None => panic!("cannot remove a char from the end of a string"),
1197         };
1198
1199         let next = idx + ch.len_utf8();
1200         let len = self.len();
1201         unsafe {
1202             ptr::copy(self.vec.as_ptr().add(next),
1203                       self.vec.as_mut_ptr().add(idx),
1204                       len - next);
1205             self.vec.set_len(len - (next - idx));
1206         }
1207         ch
1208     }
1209
1210     /// Retains only the characters specified by the predicate.
1211     ///
1212     /// In other words, remove all characters `c` such that `f(c)` returns `false`.
1213     /// This method operates in place and preserves the order of the retained
1214     /// characters.
1215     ///
1216     /// # Examples
1217     ///
1218     /// ```
1219     /// let mut s = String::from("f_o_ob_ar");
1220     ///
1221     /// s.retain(|c| c != '_');
1222     ///
1223     /// assert_eq!(s, "foobar");
1224     /// ```
1225     #[inline]
1226     #[stable(feature = "string_retain", since = "1.26.0")]
1227     pub fn retain<F>(&mut self, mut f: F)
1228         where F: FnMut(char) -> bool
1229     {
1230         let len = self.len();
1231         let mut del_bytes = 0;
1232         let mut idx = 0;
1233
1234         while idx < len {
1235             let ch = unsafe {
1236                 self.get_unchecked(idx..len).chars().next().unwrap()
1237             };
1238             let ch_len = ch.len_utf8();
1239
1240             if !f(ch) {
1241                 del_bytes += ch_len;
1242             } else if del_bytes > 0 {
1243                 unsafe {
1244                     ptr::copy(self.vec.as_ptr().add(idx),
1245                               self.vec.as_mut_ptr().add(idx - del_bytes),
1246                               ch_len);
1247                 }
1248             }
1249
1250             // Point idx to the next char
1251             idx += ch_len;
1252         }
1253
1254         if del_bytes > 0 {
1255             unsafe { self.vec.set_len(len - del_bytes); }
1256         }
1257     }
1258
1259     /// Inserts a character into this `String` at a byte position.
1260     ///
1261     /// This is an `O(n)` operation as it requires copying every element in the
1262     /// buffer.
1263     ///
1264     /// # Panics
1265     ///
1266     /// Panics if `idx` is larger than the `String`'s length, or if it does not
1267     /// lie on a [`char`] boundary.
1268     ///
1269     /// [`char`]: ../../std/primitive.char.html
1270     ///
1271     /// # Examples
1272     ///
1273     /// Basic usage:
1274     ///
1275     /// ```
1276     /// let mut s = String::with_capacity(3);
1277     ///
1278     /// s.insert(0, 'f');
1279     /// s.insert(1, 'o');
1280     /// s.insert(2, 'o');
1281     ///
1282     /// assert_eq!("foo", s);
1283     /// ```
1284     #[inline]
1285     #[stable(feature = "rust1", since = "1.0.0")]
1286     pub fn insert(&mut self, idx: usize, ch: char) {
1287         assert!(self.is_char_boundary(idx));
1288         let mut bits = [0; 4];
1289         let bits = ch.encode_utf8(&mut bits).as_bytes();
1290
1291         unsafe {
1292             self.insert_bytes(idx, bits);
1293         }
1294     }
1295
1296     unsafe fn insert_bytes(&mut self, idx: usize, bytes: &[u8]) {
1297         let len = self.len();
1298         let amt = bytes.len();
1299         self.vec.reserve(amt);
1300
1301         ptr::copy(self.vec.as_ptr().add(idx),
1302                   self.vec.as_mut_ptr().add(idx + amt),
1303                   len - idx);
1304         ptr::copy(bytes.as_ptr(),
1305                   self.vec.as_mut_ptr().add(idx),
1306                   amt);
1307         self.vec.set_len(len + amt);
1308     }
1309
1310     /// Inserts a string slice into this `String` at a byte position.
1311     ///
1312     /// This is an `O(n)` operation as it requires copying every element in the
1313     /// buffer.
1314     ///
1315     /// # Panics
1316     ///
1317     /// Panics if `idx` is larger than the `String`'s length, or if it does not
1318     /// lie on a [`char`] boundary.
1319     ///
1320     /// [`char`]: ../../std/primitive.char.html
1321     ///
1322     /// # Examples
1323     ///
1324     /// Basic usage:
1325     ///
1326     /// ```
1327     /// let mut s = String::from("bar");
1328     ///
1329     /// s.insert_str(0, "foo");
1330     ///
1331     /// assert_eq!("foobar", s);
1332     /// ```
1333     #[inline]
1334     #[stable(feature = "insert_str", since = "1.16.0")]
1335     pub fn insert_str(&mut self, idx: usize, string: &str) {
1336         assert!(self.is_char_boundary(idx));
1337
1338         unsafe {
1339             self.insert_bytes(idx, string.as_bytes());
1340         }
1341     }
1342
1343     /// Returns a mutable reference to the contents of this `String`.
1344     ///
1345     /// # Safety
1346     ///
1347     /// This function is unsafe because it does not check that the bytes passed
1348     /// to it are valid UTF-8. If this constraint is violated, it may cause
1349     /// memory unsafety issues with future users of the `String`, as the rest of
1350     /// the standard library assumes that `String`s are valid UTF-8.
1351     ///
1352     /// # Examples
1353     ///
1354     /// Basic usage:
1355     ///
1356     /// ```
1357     /// let mut s = String::from("hello");
1358     ///
1359     /// unsafe {
1360     ///     let vec = s.as_mut_vec();
1361     ///     assert_eq!(&[104, 101, 108, 108, 111][..], &vec[..]);
1362     ///
1363     ///     vec.reverse();
1364     /// }
1365     /// assert_eq!(s, "olleh");
1366     /// ```
1367     #[inline]
1368     #[stable(feature = "rust1", since = "1.0.0")]
1369     pub unsafe fn as_mut_vec(&mut self) -> &mut Vec<u8> {
1370         &mut self.vec
1371     }
1372
1373     /// Returns the length of this `String`, in bytes.
1374     ///
1375     /// # Examples
1376     ///
1377     /// Basic usage:
1378     ///
1379     /// ```
1380     /// let a = String::from("foo");
1381     ///
1382     /// assert_eq!(a.len(), 3);
1383     /// ```
1384     #[inline]
1385     #[stable(feature = "rust1", since = "1.0.0")]
1386     pub fn len(&self) -> usize {
1387         self.vec.len()
1388     }
1389
1390     /// Returns `true` if this `String` has a length of zero.
1391     ///
1392     /// Returns `false` otherwise.
1393     ///
1394     /// # Examples
1395     ///
1396     /// Basic usage:
1397     ///
1398     /// ```
1399     /// let mut v = String::new();
1400     /// assert!(v.is_empty());
1401     ///
1402     /// v.push('a');
1403     /// assert!(!v.is_empty());
1404     /// ```
1405     #[inline]
1406     #[stable(feature = "rust1", since = "1.0.0")]
1407     pub fn is_empty(&self) -> bool {
1408         self.len() == 0
1409     }
1410
1411     /// Splits the string into two at the given index.
1412     ///
1413     /// Returns a newly allocated `String`. `self` contains bytes `[0, at)`, and
1414     /// the returned `String` contains bytes `[at, len)`. `at` must be on the
1415     /// boundary of a UTF-8 code point.
1416     ///
1417     /// Note that the capacity of `self` does not change.
1418     ///
1419     /// # Panics
1420     ///
1421     /// Panics if `at` is not on a `UTF-8` code point boundary, or if it is beyond the last
1422     /// code point of the string.
1423     ///
1424     /// # Examples
1425     ///
1426     /// ```
1427     /// # fn main() {
1428     /// let mut hello = String::from("Hello, World!");
1429     /// let world = hello.split_off(7);
1430     /// assert_eq!(hello, "Hello, ");
1431     /// assert_eq!(world, "World!");
1432     /// # }
1433     /// ```
1434     #[inline]
1435     #[stable(feature = "string_split_off", since = "1.16.0")]
1436     pub fn split_off(&mut self, at: usize) -> String {
1437         assert!(self.is_char_boundary(at));
1438         let other = self.vec.split_off(at);
1439         unsafe { String::from_utf8_unchecked(other) }
1440     }
1441
1442     /// Truncates this `String`, removing all contents.
1443     ///
1444     /// While this means the `String` will have a length of zero, it does not
1445     /// touch its capacity.
1446     ///
1447     /// # Examples
1448     ///
1449     /// Basic usage:
1450     ///
1451     /// ```
1452     /// let mut s = String::from("foo");
1453     ///
1454     /// s.clear();
1455     ///
1456     /// assert!(s.is_empty());
1457     /// assert_eq!(0, s.len());
1458     /// assert_eq!(3, s.capacity());
1459     /// ```
1460     #[inline]
1461     #[stable(feature = "rust1", since = "1.0.0")]
1462     pub fn clear(&mut self) {
1463         self.vec.clear()
1464     }
1465
1466     /// Creates a draining iterator that removes the specified range in the `String`
1467     /// and yields the removed `chars`.
1468     ///
1469     /// Note: The element range is removed even if the iterator is not
1470     /// consumed until the end.
1471     ///
1472     /// # Panics
1473     ///
1474     /// Panics if the starting point or end point do not lie on a [`char`]
1475     /// boundary, or if they're out of bounds.
1476     ///
1477     /// [`char`]: ../../std/primitive.char.html
1478     ///
1479     /// # Examples
1480     ///
1481     /// Basic usage:
1482     ///
1483     /// ```
1484     /// let mut s = String::from("α is alpha, β is beta");
1485     /// let beta_offset = s.find('β').unwrap_or(s.len());
1486     ///
1487     /// // Remove the range up until the β from the string
1488     /// let t: String = s.drain(..beta_offset).collect();
1489     /// assert_eq!(t, "α is alpha, ");
1490     /// assert_eq!(s, "β is beta");
1491     ///
1492     /// // A full range clears the string
1493     /// s.drain(..);
1494     /// assert_eq!(s, "");
1495     /// ```
1496     #[stable(feature = "drain", since = "1.6.0")]
1497     pub fn drain<R>(&mut self, range: R) -> Drain
1498         where R: RangeBounds<usize>
1499     {
1500         // Memory safety
1501         //
1502         // The String version of Drain does not have the memory safety issues
1503         // of the vector version. The data is just plain bytes.
1504         // Because the range removal happens in Drop, if the Drain iterator is leaked,
1505         // the removal will not happen.
1506         let len = self.len();
1507         let start = match range.start_bound() {
1508             Included(&n) => n,
1509             Excluded(&n) => n + 1,
1510             Unbounded => 0,
1511         };
1512         let end = match range.end_bound() {
1513             Included(&n) => n + 1,
1514             Excluded(&n) => n,
1515             Unbounded => len,
1516         };
1517
1518         // Take out two simultaneous borrows. The &mut String won't be accessed
1519         // until iteration is over, in Drop.
1520         let self_ptr = self as *mut _;
1521         // slicing does the appropriate bounds checks
1522         let chars_iter = self[start..end].chars();
1523
1524         Drain {
1525             start,
1526             end,
1527             iter: chars_iter,
1528             string: self_ptr,
1529         }
1530     }
1531
1532     /// Removes the specified range in the string,
1533     /// and replaces it with the given string.
1534     /// The given string doesn't need to be the same length as the range.
1535     ///
1536     /// # Panics
1537     ///
1538     /// Panics if the starting point or end point do not lie on a [`char`]
1539     /// boundary, or if they're out of bounds.
1540     ///
1541     /// [`char`]: ../../std/primitive.char.html
1542     /// [`Vec::splice`]: ../../std/vec/struct.Vec.html#method.splice
1543     ///
1544     /// # Examples
1545     ///
1546     /// Basic usage:
1547     ///
1548     /// ```
1549     /// let mut s = String::from("α is alpha, β is beta");
1550     /// let beta_offset = s.find('β').unwrap_or(s.len());
1551     ///
1552     /// // Replace the range up until the β from the string
1553     /// s.replace_range(..beta_offset, "Α is capital alpha; ");
1554     /// assert_eq!(s, "Α is capital alpha; β is beta");
1555     /// ```
1556     #[stable(feature = "splice", since = "1.27.0")]
1557     pub fn replace_range<R>(&mut self, range: R, replace_with: &str)
1558         where R: RangeBounds<usize>
1559     {
1560         // Memory safety
1561         //
1562         // Replace_range does not have the memory safety issues of a vector Splice.
1563         // of the vector version. The data is just plain bytes.
1564
1565         match range.start_bound() {
1566              Included(&n) => assert!(self.is_char_boundary(n)),
1567              Excluded(&n) => assert!(self.is_char_boundary(n + 1)),
1568              Unbounded => {},
1569         };
1570         match range.end_bound() {
1571              Included(&n) => assert!(self.is_char_boundary(n + 1)),
1572              Excluded(&n) => assert!(self.is_char_boundary(n)),
1573              Unbounded => {},
1574         };
1575
1576         unsafe {
1577             self.as_mut_vec()
1578         }.splice(range, replace_with.bytes());
1579     }
1580
1581     /// Converts this `String` into a [`Box`]`<`[`str`]`>`.
1582     ///
1583     /// This will drop any excess capacity.
1584     ///
1585     /// [`Box`]: ../../std/boxed/struct.Box.html
1586     /// [`str`]: ../../std/primitive.str.html
1587     ///
1588     /// # Examples
1589     ///
1590     /// Basic usage:
1591     ///
1592     /// ```
1593     /// let s = String::from("hello");
1594     ///
1595     /// let b = s.into_boxed_str();
1596     /// ```
1597     #[stable(feature = "box_str", since = "1.4.0")]
1598     #[inline]
1599     pub fn into_boxed_str(self) -> Box<str> {
1600         let slice = self.vec.into_boxed_slice();
1601         unsafe { from_boxed_utf8_unchecked(slice) }
1602     }
1603 }
1604
1605 impl FromUtf8Error {
1606     /// Returns a slice of [`u8`]s bytes that were attempted to convert to a `String`.
1607     ///
1608     /// # Examples
1609     ///
1610     /// Basic usage:
1611     ///
1612     /// ```
1613     /// // some invalid bytes, in a vector
1614     /// let bytes = vec![0, 159];
1615     ///
1616     /// let value = String::from_utf8(bytes);
1617     ///
1618     /// assert_eq!(&[0, 159], value.unwrap_err().as_bytes());
1619     /// ```
1620     #[stable(feature = "from_utf8_error_as_bytes", since = "1.26.0")]
1621     pub fn as_bytes(&self) -> &[u8] {
1622         &self.bytes[..]
1623     }
1624
1625     /// Returns the bytes that were attempted to convert to a `String`.
1626     ///
1627     /// This method is carefully constructed to avoid allocation. It will
1628     /// consume the error, moving out the bytes, so that a copy of the bytes
1629     /// does not need to be made.
1630     ///
1631     /// # Examples
1632     ///
1633     /// Basic usage:
1634     ///
1635     /// ```
1636     /// // some invalid bytes, in a vector
1637     /// let bytes = vec![0, 159];
1638     ///
1639     /// let value = String::from_utf8(bytes);
1640     ///
1641     /// assert_eq!(vec![0, 159], value.unwrap_err().into_bytes());
1642     /// ```
1643     #[stable(feature = "rust1", since = "1.0.0")]
1644     pub fn into_bytes(self) -> Vec<u8> {
1645         self.bytes
1646     }
1647
1648     /// Fetch a `Utf8Error` to get more details about the conversion failure.
1649     ///
1650     /// The [`Utf8Error`] type provided by [`std::str`] represents an error that may
1651     /// occur when converting a slice of [`u8`]s to a [`&str`]. In this sense, it's
1652     /// an analogue to `FromUtf8Error`. See its documentation for more details
1653     /// on using it.
1654     ///
1655     /// [`Utf8Error`]: ../../std/str/struct.Utf8Error.html
1656     /// [`std::str`]: ../../std/str/index.html
1657     /// [`u8`]: ../../std/primitive.u8.html
1658     /// [`&str`]: ../../std/primitive.str.html
1659     ///
1660     /// # Examples
1661     ///
1662     /// Basic usage:
1663     ///
1664     /// ```
1665     /// // some invalid bytes, in a vector
1666     /// let bytes = vec![0, 159];
1667     ///
1668     /// let error = String::from_utf8(bytes).unwrap_err().utf8_error();
1669     ///
1670     /// // the first byte is invalid here
1671     /// assert_eq!(1, error.valid_up_to());
1672     /// ```
1673     #[stable(feature = "rust1", since = "1.0.0")]
1674     pub fn utf8_error(&self) -> Utf8Error {
1675         self.error
1676     }
1677 }
1678
1679 #[stable(feature = "rust1", since = "1.0.0")]
1680 impl fmt::Display for FromUtf8Error {
1681     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1682         fmt::Display::fmt(&self.error, f)
1683     }
1684 }
1685
1686 #[stable(feature = "rust1", since = "1.0.0")]
1687 impl fmt::Display for FromUtf16Error {
1688     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1689         fmt::Display::fmt("invalid utf-16: lone surrogate found", f)
1690     }
1691 }
1692
1693 #[stable(feature = "rust1", since = "1.0.0")]
1694 impl Clone for String {
1695     fn clone(&self) -> Self {
1696         String { vec: self.vec.clone() }
1697     }
1698
1699     fn clone_from(&mut self, source: &Self) {
1700         self.vec.clone_from(&source.vec);
1701     }
1702 }
1703
1704 #[stable(feature = "rust1", since = "1.0.0")]
1705 impl FromIterator<char> for String {
1706     fn from_iter<I: IntoIterator<Item = char>>(iter: I) -> String {
1707         let mut buf = String::new();
1708         buf.extend(iter);
1709         buf
1710     }
1711 }
1712
1713 #[stable(feature = "string_from_iter_by_ref", since = "1.17.0")]
1714 impl<'a> FromIterator<&'a char> for String {
1715     fn from_iter<I: IntoIterator<Item = &'a char>>(iter: I) -> String {
1716         let mut buf = String::new();
1717         buf.extend(iter);
1718         buf
1719     }
1720 }
1721
1722 #[stable(feature = "rust1", since = "1.0.0")]
1723 impl<'a> FromIterator<&'a str> for String {
1724     fn from_iter<I: IntoIterator<Item = &'a str>>(iter: I) -> String {
1725         let mut buf = String::new();
1726         buf.extend(iter);
1727         buf
1728     }
1729 }
1730
1731 #[stable(feature = "extend_string", since = "1.4.0")]
1732 impl FromIterator<String> for String {
1733     fn from_iter<I: IntoIterator<Item = String>>(iter: I) -> String {
1734         let mut iterator = iter.into_iter();
1735
1736         // Because we're iterating over `String`s, we can avoid at least
1737         // one allocation by getting the first string from the iterator
1738         // and appending to it all the subsequent strings.
1739         match iterator.next() {
1740             None => String::new(),
1741             Some(mut buf) => {
1742                 buf.extend(iterator);
1743                 buf
1744             }
1745         }
1746     }
1747 }
1748
1749 #[stable(feature = "herd_cows", since = "1.19.0")]
1750 impl<'a> FromIterator<Cow<'a, str>> for String {
1751     fn from_iter<I: IntoIterator<Item = Cow<'a, str>>>(iter: I) -> String {
1752         let mut iterator = iter.into_iter();
1753
1754         // Because we're iterating over CoWs, we can (potentially) avoid at least
1755         // one allocation by getting the first item and appending to it all the
1756         // subsequent items.
1757         match iterator.next() {
1758             None => String::new(),
1759             Some(cow) => {
1760                 let mut buf = cow.into_owned();
1761                 buf.extend(iterator);
1762                 buf
1763             }
1764         }
1765     }
1766 }
1767
1768 #[stable(feature = "rust1", since = "1.0.0")]
1769 impl Extend<char> for String {
1770     fn extend<I: IntoIterator<Item = char>>(&mut self, iter: I) {
1771         let iterator = iter.into_iter();
1772         let (lower_bound, _) = iterator.size_hint();
1773         self.reserve(lower_bound);
1774         iterator.for_each(move |c| self.push(c));
1775     }
1776 }
1777
1778 #[stable(feature = "extend_ref", since = "1.2.0")]
1779 impl<'a> Extend<&'a char> for String {
1780     fn extend<I: IntoIterator<Item = &'a char>>(&mut self, iter: I) {
1781         self.extend(iter.into_iter().cloned());
1782     }
1783 }
1784
1785 #[stable(feature = "rust1", since = "1.0.0")]
1786 impl<'a> Extend<&'a str> for String {
1787     fn extend<I: IntoIterator<Item = &'a str>>(&mut self, iter: I) {
1788         iter.into_iter().for_each(move |s| self.push_str(s));
1789     }
1790 }
1791
1792 #[stable(feature = "extend_string", since = "1.4.0")]
1793 impl Extend<String> for String {
1794     fn extend<I: IntoIterator<Item = String>>(&mut self, iter: I) {
1795         iter.into_iter().for_each(move |s| self.push_str(&s));
1796     }
1797 }
1798
1799 #[stable(feature = "herd_cows", since = "1.19.0")]
1800 impl<'a> Extend<Cow<'a, str>> for String {
1801     fn extend<I: IntoIterator<Item = Cow<'a, str>>>(&mut self, iter: I) {
1802         iter.into_iter().for_each(move |s| self.push_str(&s));
1803     }
1804 }
1805
1806 /// A convenience impl that delegates to the impl for `&str`
1807 #[unstable(feature = "pattern",
1808            reason = "API not fully fleshed out and ready to be stabilized",
1809            issue = "27721")]
1810 impl<'a, 'b> Pattern<'a> for &'b String {
1811     type Searcher = <&'b str as Pattern<'a>>::Searcher;
1812
1813     fn into_searcher(self, haystack: &'a str) -> <&'b str as Pattern<'a>>::Searcher {
1814         self[..].into_searcher(haystack)
1815     }
1816
1817     #[inline]
1818     fn is_contained_in(self, haystack: &'a str) -> bool {
1819         self[..].is_contained_in(haystack)
1820     }
1821
1822     #[inline]
1823     fn is_prefix_of(self, haystack: &'a str) -> bool {
1824         self[..].is_prefix_of(haystack)
1825     }
1826 }
1827
1828 #[stable(feature = "rust1", since = "1.0.0")]
1829 impl PartialEq for String {
1830     #[inline]
1831     fn eq(&self, other: &String) -> bool {
1832         PartialEq::eq(&self[..], &other[..])
1833     }
1834     #[inline]
1835     fn ne(&self, other: &String) -> bool {
1836         PartialEq::ne(&self[..], &other[..])
1837     }
1838 }
1839
1840 macro_rules! impl_eq {
1841     ($lhs:ty, $rhs: ty) => {
1842         #[stable(feature = "rust1", since = "1.0.0")]
1843         impl<'a, 'b> PartialEq<$rhs> for $lhs {
1844             #[inline]
1845             fn eq(&self, other: &$rhs) -> bool { PartialEq::eq(&self[..], &other[..]) }
1846             #[inline]
1847             fn ne(&self, other: &$rhs) -> bool { PartialEq::ne(&self[..], &other[..]) }
1848         }
1849
1850         #[stable(feature = "rust1", since = "1.0.0")]
1851         impl<'a, 'b> PartialEq<$lhs> for $rhs {
1852             #[inline]
1853             fn eq(&self, other: &$lhs) -> bool { PartialEq::eq(&self[..], &other[..]) }
1854             #[inline]
1855             fn ne(&self, other: &$lhs) -> bool { PartialEq::ne(&self[..], &other[..]) }
1856         }
1857
1858     }
1859 }
1860
1861 impl_eq! { String, str }
1862 impl_eq! { String, &'a str }
1863 impl_eq! { Cow<'a, str>, str }
1864 impl_eq! { Cow<'a, str>, &'b str }
1865 impl_eq! { Cow<'a, str>, String }
1866
1867 #[stable(feature = "rust1", since = "1.0.0")]
1868 impl Default for String {
1869     /// Creates an empty `String`.
1870     #[inline]
1871     fn default() -> String {
1872         String::new()
1873     }
1874 }
1875
1876 #[stable(feature = "rust1", since = "1.0.0")]
1877 impl fmt::Display for String {
1878     #[inline]
1879     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1880         fmt::Display::fmt(&**self, f)
1881     }
1882 }
1883
1884 #[stable(feature = "rust1", since = "1.0.0")]
1885 impl fmt::Debug for String {
1886     #[inline]
1887     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1888         fmt::Debug::fmt(&**self, f)
1889     }
1890 }
1891
1892 #[stable(feature = "rust1", since = "1.0.0")]
1893 impl hash::Hash for String {
1894     #[inline]
1895     fn hash<H: hash::Hasher>(&self, hasher: &mut H) {
1896         (**self).hash(hasher)
1897     }
1898 }
1899
1900 /// Implements the `+` operator for concatenating two strings.
1901 ///
1902 /// This consumes the `String` on the left-hand side and re-uses its buffer (growing it if
1903 /// necessary). This is done to avoid allocating a new `String` and copying the entire contents on
1904 /// every operation, which would lead to `O(n^2)` running time when building an `n`-byte string by
1905 /// repeated concatenation.
1906 ///
1907 /// The string on the right-hand side is only borrowed; its contents are copied into the returned
1908 /// `String`.
1909 ///
1910 /// # Examples
1911 ///
1912 /// Concatenating two `String`s takes the first by value and borrows the second:
1913 ///
1914 /// ```
1915 /// let a = String::from("hello");
1916 /// let b = String::from(" world");
1917 /// let c = a + &b;
1918 /// // `a` is moved and can no longer be used here.
1919 /// ```
1920 ///
1921 /// If you want to keep using the first `String`, you can clone it and append to the clone instead:
1922 ///
1923 /// ```
1924 /// let a = String::from("hello");
1925 /// let b = String::from(" world");
1926 /// let c = a.clone() + &b;
1927 /// // `a` is still valid here.
1928 /// ```
1929 ///
1930 /// Concatenating `&str` slices can be done by converting the first to a `String`:
1931 ///
1932 /// ```
1933 /// let a = "hello";
1934 /// let b = " world";
1935 /// let c = a.to_string() + b;
1936 /// ```
1937 #[stable(feature = "rust1", since = "1.0.0")]
1938 impl<'a> Add<&'a str> for String {
1939     type Output = String;
1940
1941     #[inline]
1942     fn add(mut self, other: &str) -> String {
1943         self.push_str(other);
1944         self
1945     }
1946 }
1947
1948 /// Implements the `+=` operator for appending to a `String`.
1949 ///
1950 /// This has the same behavior as the [`push_str`][String::push_str] method.
1951 #[stable(feature = "stringaddassign", since = "1.12.0")]
1952 impl<'a> AddAssign<&'a str> for String {
1953     #[inline]
1954     fn add_assign(&mut self, other: &str) {
1955         self.push_str(other);
1956     }
1957 }
1958
1959 #[stable(feature = "rust1", since = "1.0.0")]
1960 impl ops::Index<ops::Range<usize>> for String {
1961     type Output = str;
1962
1963     #[inline]
1964     fn index(&self, index: ops::Range<usize>) -> &str {
1965         &self[..][index]
1966     }
1967 }
1968 #[stable(feature = "rust1", since = "1.0.0")]
1969 impl ops::Index<ops::RangeTo<usize>> for String {
1970     type Output = str;
1971
1972     #[inline]
1973     fn index(&self, index: ops::RangeTo<usize>) -> &str {
1974         &self[..][index]
1975     }
1976 }
1977 #[stable(feature = "rust1", since = "1.0.0")]
1978 impl ops::Index<ops::RangeFrom<usize>> for String {
1979     type Output = str;
1980
1981     #[inline]
1982     fn index(&self, index: ops::RangeFrom<usize>) -> &str {
1983         &self[..][index]
1984     }
1985 }
1986 #[stable(feature = "rust1", since = "1.0.0")]
1987 impl ops::Index<ops::RangeFull> for String {
1988     type Output = str;
1989
1990     #[inline]
1991     fn index(&self, _index: ops::RangeFull) -> &str {
1992         unsafe { str::from_utf8_unchecked(&self.vec) }
1993     }
1994 }
1995 #[stable(feature = "inclusive_range", since = "1.26.0")]
1996 impl ops::Index<ops::RangeInclusive<usize>> for String {
1997     type Output = str;
1998
1999     #[inline]
2000     fn index(&self, index: ops::RangeInclusive<usize>) -> &str {
2001         Index::index(&**self, index)
2002     }
2003 }
2004 #[stable(feature = "inclusive_range", since = "1.26.0")]
2005 impl ops::Index<ops::RangeToInclusive<usize>> for String {
2006     type Output = str;
2007
2008     #[inline]
2009     fn index(&self, index: ops::RangeToInclusive<usize>) -> &str {
2010         Index::index(&**self, index)
2011     }
2012 }
2013
2014 #[stable(feature = "derefmut_for_string", since = "1.3.0")]
2015 impl ops::IndexMut<ops::Range<usize>> for String {
2016     #[inline]
2017     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str {
2018         &mut self[..][index]
2019     }
2020 }
2021 #[stable(feature = "derefmut_for_string", since = "1.3.0")]
2022 impl ops::IndexMut<ops::RangeTo<usize>> for String {
2023     #[inline]
2024     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str {
2025         &mut self[..][index]
2026     }
2027 }
2028 #[stable(feature = "derefmut_for_string", since = "1.3.0")]
2029 impl ops::IndexMut<ops::RangeFrom<usize>> for String {
2030     #[inline]
2031     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str {
2032         &mut self[..][index]
2033     }
2034 }
2035 #[stable(feature = "derefmut_for_string", since = "1.3.0")]
2036 impl ops::IndexMut<ops::RangeFull> for String {
2037     #[inline]
2038     fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str {
2039         unsafe { str::from_utf8_unchecked_mut(&mut *self.vec) }
2040     }
2041 }
2042 #[stable(feature = "inclusive_range", since = "1.26.0")]
2043 impl ops::IndexMut<ops::RangeInclusive<usize>> for String {
2044     #[inline]
2045     fn index_mut(&mut self, index: ops::RangeInclusive<usize>) -> &mut str {
2046         IndexMut::index_mut(&mut **self, index)
2047     }
2048 }
2049 #[stable(feature = "inclusive_range", since = "1.26.0")]
2050 impl ops::IndexMut<ops::RangeToInclusive<usize>> for String {
2051     #[inline]
2052     fn index_mut(&mut self, index: ops::RangeToInclusive<usize>) -> &mut str {
2053         IndexMut::index_mut(&mut **self, index)
2054     }
2055 }
2056
2057 #[stable(feature = "rust1", since = "1.0.0")]
2058 impl ops::Deref for String {
2059     type Target = str;
2060
2061     #[inline]
2062     fn deref(&self) -> &str {
2063         unsafe { str::from_utf8_unchecked(&self.vec) }
2064     }
2065 }
2066
2067 #[stable(feature = "derefmut_for_string", since = "1.3.0")]
2068 impl ops::DerefMut for String {
2069     #[inline]
2070     fn deref_mut(&mut self) -> &mut str {
2071         unsafe { str::from_utf8_unchecked_mut(&mut *self.vec) }
2072     }
2073 }
2074
2075 /// An error when parsing a `String`.
2076 ///
2077 /// This `enum` is slightly awkward: it will never actually exist. This error is
2078 /// part of the type signature of the implementation of [`FromStr`] on
2079 /// [`String`]. The return type of [`from_str`], requires that an error be
2080 /// defined, but, given that a [`String`] can always be made into a new
2081 /// [`String`] without error, this type will never actually be returned. As
2082 /// such, it is only here to satisfy said signature, and is useless otherwise.
2083 ///
2084 /// [`FromStr`]: ../../std/str/trait.FromStr.html
2085 /// [`String`]: struct.String.html
2086 /// [`from_str`]: ../../std/str/trait.FromStr.html#tymethod.from_str
2087 #[stable(feature = "str_parse_error", since = "1.5.0")]
2088 #[derive(Copy)]
2089 pub enum ParseError {}
2090
2091 #[stable(feature = "rust1", since = "1.0.0")]
2092 impl FromStr for String {
2093     type Err = ParseError;
2094     #[inline]
2095     fn from_str(s: &str) -> Result<String, ParseError> {
2096         Ok(String::from(s))
2097     }
2098 }
2099
2100 #[stable(feature = "str_parse_error", since = "1.5.0")]
2101 impl Clone for ParseError {
2102     fn clone(&self) -> ParseError {
2103         match *self {}
2104     }
2105 }
2106
2107 #[stable(feature = "str_parse_error", since = "1.5.0")]
2108 impl fmt::Debug for ParseError {
2109     fn fmt(&self, _: &mut fmt::Formatter) -> fmt::Result {
2110         match *self {}
2111     }
2112 }
2113
2114 #[stable(feature = "str_parse_error2", since = "1.8.0")]
2115 impl fmt::Display for ParseError {
2116     fn fmt(&self, _: &mut fmt::Formatter) -> fmt::Result {
2117         match *self {}
2118     }
2119 }
2120
2121 #[stable(feature = "str_parse_error", since = "1.5.0")]
2122 impl PartialEq for ParseError {
2123     fn eq(&self, _: &ParseError) -> bool {
2124         match *self {}
2125     }
2126 }
2127
2128 #[stable(feature = "str_parse_error", since = "1.5.0")]
2129 impl Eq for ParseError {}
2130
2131 /// A trait for converting a value to a `String`.
2132 ///
2133 /// This trait is automatically implemented for any type which implements the
2134 /// [`Display`] trait. As such, `ToString` shouldn't be implemented directly:
2135 /// [`Display`] should be implemented instead, and you get the `ToString`
2136 /// implementation for free.
2137 ///
2138 /// [`Display`]: ../../std/fmt/trait.Display.html
2139 #[stable(feature = "rust1", since = "1.0.0")]
2140 pub trait ToString {
2141     /// Converts the given value to a `String`.
2142     ///
2143     /// # Examples
2144     ///
2145     /// Basic usage:
2146     ///
2147     /// ```
2148     /// let i = 5;
2149     /// let five = String::from("5");
2150     ///
2151     /// assert_eq!(five, i.to_string());
2152     /// ```
2153     #[rustc_conversion_suggestion]
2154     #[stable(feature = "rust1", since = "1.0.0")]
2155     fn to_string(&self) -> String;
2156 }
2157
2158 /// # Panics
2159 ///
2160 /// In this implementation, the `to_string` method panics
2161 /// if the `Display` implementation returns an error.
2162 /// This indicates an incorrect `Display` implementation
2163 /// since `fmt::Write for String` never returns an error itself.
2164 #[stable(feature = "rust1", since = "1.0.0")]
2165 impl<T: fmt::Display + ?Sized> ToString for T {
2166     #[inline]
2167     default fn to_string(&self) -> String {
2168         use fmt::Write;
2169         let mut buf = String::new();
2170         buf.write_fmt(format_args!("{}", self))
2171            .expect("a Display implementation returned an error unexpectedly");
2172         buf.shrink_to_fit();
2173         buf
2174     }
2175 }
2176
2177 #[stable(feature = "str_to_string_specialization", since = "1.9.0")]
2178 impl ToString for str {
2179     #[inline]
2180     fn to_string(&self) -> String {
2181         String::from(self)
2182     }
2183 }
2184
2185 #[stable(feature = "cow_str_to_string_specialization", since = "1.17.0")]
2186 impl<'a> ToString for Cow<'a, str> {
2187     #[inline]
2188     fn to_string(&self) -> String {
2189         self[..].to_owned()
2190     }
2191 }
2192
2193 #[stable(feature = "string_to_string_specialization", since = "1.17.0")]
2194 impl ToString for String {
2195     #[inline]
2196     fn to_string(&self) -> String {
2197         self.to_owned()
2198     }
2199 }
2200
2201 #[stable(feature = "rust1", since = "1.0.0")]
2202 impl AsRef<str> for String {
2203     #[inline]
2204     fn as_ref(&self) -> &str {
2205         self
2206     }
2207 }
2208
2209 #[stable(feature = "rust1", since = "1.0.0")]
2210 impl AsRef<[u8]> for String {
2211     #[inline]
2212     fn as_ref(&self) -> &[u8] {
2213         self.as_bytes()
2214     }
2215 }
2216
2217 #[stable(feature = "rust1", since = "1.0.0")]
2218 impl<'a> From<&'a str> for String {
2219     #[inline]
2220     fn from(s: &'a str) -> String {
2221         s.to_owned()
2222     }
2223 }
2224
2225 // note: test pulls in libstd, which causes errors here
2226 #[cfg(not(test))]
2227 #[stable(feature = "string_from_box", since = "1.18.0")]
2228 impl From<Box<str>> for String {
2229     /// Converts the given boxed `str` slice to a `String`.
2230     /// It is notable that the `str` slice is owned.
2231     ///
2232     /// # Examples
2233     ///
2234     /// Basic usage:
2235     ///
2236     /// ```
2237     /// let s1: String = String::from("hello world");
2238     /// let s2: Box<str> = s1.into_boxed_str();
2239     /// let s3: String = String::from(s2);
2240     ///
2241     /// assert_eq!("hello world", s3)
2242     /// ```
2243     fn from(s: Box<str>) -> String {
2244         s.into_string()
2245     }
2246 }
2247
2248 #[stable(feature = "box_from_str", since = "1.20.0")]
2249 impl From<String> for Box<str> {
2250     /// Converts the given `String` to a boxed `str` slice that is owned.
2251     ///
2252     /// # Examples
2253     ///
2254     /// Basic usage:
2255     ///
2256     /// ```
2257     /// let s1: String = String::from("hello world");
2258     /// let s2: Box<str> = Box::from(s1);
2259     /// let s3: String = String::from(s2);
2260     ///
2261     /// assert_eq!("hello world", s3)
2262     /// ```
2263     fn from(s: String) -> Box<str> {
2264         s.into_boxed_str()
2265     }
2266 }
2267
2268 #[stable(feature = "string_from_cow_str", since = "1.14.0")]
2269 impl<'a> From<Cow<'a, str>> for String {
2270     fn from(s: Cow<'a, str>) -> String {
2271         s.into_owned()
2272     }
2273 }
2274
2275 #[stable(feature = "rust1", since = "1.0.0")]
2276 impl<'a> From<&'a str> for Cow<'a, str> {
2277     #[inline]
2278     fn from(s: &'a str) -> Cow<'a, str> {
2279         Cow::Borrowed(s)
2280     }
2281 }
2282
2283 #[stable(feature = "rust1", since = "1.0.0")]
2284 impl<'a> From<String> for Cow<'a, str> {
2285     #[inline]
2286     fn from(s: String) -> Cow<'a, str> {
2287         Cow::Owned(s)
2288     }
2289 }
2290
2291 #[stable(feature = "cow_from_string_ref", since = "1.28.0")]
2292 impl<'a> From<&'a String> for Cow<'a, str> {
2293     #[inline]
2294     fn from(s: &'a String) -> Cow<'a, str> {
2295         Cow::Borrowed(s.as_str())
2296     }
2297 }
2298
2299 #[stable(feature = "cow_str_from_iter", since = "1.12.0")]
2300 impl<'a> FromIterator<char> for Cow<'a, str> {
2301     fn from_iter<I: IntoIterator<Item = char>>(it: I) -> Cow<'a, str> {
2302         Cow::Owned(FromIterator::from_iter(it))
2303     }
2304 }
2305
2306 #[stable(feature = "cow_str_from_iter", since = "1.12.0")]
2307 impl<'a, 'b> FromIterator<&'b str> for Cow<'a, str> {
2308     fn from_iter<I: IntoIterator<Item = &'b str>>(it: I) -> Cow<'a, str> {
2309         Cow::Owned(FromIterator::from_iter(it))
2310     }
2311 }
2312
2313 #[stable(feature = "cow_str_from_iter", since = "1.12.0")]
2314 impl<'a> FromIterator<String> for Cow<'a, str> {
2315     fn from_iter<I: IntoIterator<Item = String>>(it: I) -> Cow<'a, str> {
2316         Cow::Owned(FromIterator::from_iter(it))
2317     }
2318 }
2319
2320 #[stable(feature = "from_string_for_vec_u8", since = "1.14.0")]
2321 impl From<String> for Vec<u8> {
2322     /// Converts the given `String` to a vector `Vec` that holds values of type `u8`.
2323     ///
2324     /// # Examples
2325     ///
2326     /// Basic usage:
2327     ///
2328     /// ```
2329     /// let s1 = String::from("hello world");
2330     /// let v1 = Vec::from(s1);
2331     ///
2332     /// for b in v1 {
2333     ///     println!("{}", b);
2334     /// }
2335     /// ```
2336     fn from(string: String) -> Vec<u8> {
2337         string.into_bytes()
2338     }
2339 }
2340
2341 #[stable(feature = "rust1", since = "1.0.0")]
2342 impl fmt::Write for String {
2343     #[inline]
2344     fn write_str(&mut self, s: &str) -> fmt::Result {
2345         self.push_str(s);
2346         Ok(())
2347     }
2348
2349     #[inline]
2350     fn write_char(&mut self, c: char) -> fmt::Result {
2351         self.push(c);
2352         Ok(())
2353     }
2354 }
2355
2356 /// A draining iterator for `String`.
2357 ///
2358 /// This struct is created by the [`drain`] method on [`String`]. See its
2359 /// documentation for more.
2360 ///
2361 /// [`drain`]: struct.String.html#method.drain
2362 /// [`String`]: struct.String.html
2363 #[stable(feature = "drain", since = "1.6.0")]
2364 pub struct Drain<'a> {
2365     /// Will be used as &'a mut String in the destructor
2366     string: *mut String,
2367     /// Start of part to remove
2368     start: usize,
2369     /// End of part to remove
2370     end: usize,
2371     /// Current remaining range to remove
2372     iter: Chars<'a>,
2373 }
2374
2375 #[stable(feature = "collection_debug", since = "1.17.0")]
2376 impl<'a> fmt::Debug for Drain<'a> {
2377     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2378         f.pad("Drain { .. }")
2379     }
2380 }
2381
2382 #[stable(feature = "drain", since = "1.6.0")]
2383 unsafe impl<'a> Sync for Drain<'a> {}
2384 #[stable(feature = "drain", since = "1.6.0")]
2385 unsafe impl<'a> Send for Drain<'a> {}
2386
2387 #[stable(feature = "drain", since = "1.6.0")]
2388 impl<'a> Drop for Drain<'a> {
2389     fn drop(&mut self) {
2390         unsafe {
2391             // Use Vec::drain. "Reaffirm" the bounds checks to avoid
2392             // panic code being inserted again.
2393             let self_vec = (*self.string).as_mut_vec();
2394             if self.start <= self.end && self.end <= self_vec.len() {
2395                 self_vec.drain(self.start..self.end);
2396             }
2397         }
2398     }
2399 }
2400
2401 #[stable(feature = "drain", since = "1.6.0")]
2402 impl<'a> Iterator for Drain<'a> {
2403     type Item = char;
2404
2405     #[inline]
2406     fn next(&mut self) -> Option<char> {
2407         self.iter.next()
2408     }
2409
2410     fn size_hint(&self) -> (usize, Option<usize>) {
2411         self.iter.size_hint()
2412     }
2413 }
2414
2415 #[stable(feature = "drain", since = "1.6.0")]
2416 impl<'a> DoubleEndedIterator for Drain<'a> {
2417     #[inline]
2418     fn next_back(&mut self) -> Option<char> {
2419         self.iter.next_back()
2420     }
2421 }
2422
2423 #[stable(feature = "fused", since = "1.26.0")]
2424 impl<'a> FusedIterator for Drain<'a> {}