vendor/bumpalo/src/collections/string.rs

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