library/alloc/src/string.rs

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