src/liballoc/boxed.rs

   1 //! A pointer type for heap allocation.
   2 //!
   3 //! [`Box<T>`], casually referred to as a 'box', provides the simplest form of
   4 //! heap allocation in Rust. Boxes provide ownership for this allocation, and
   5 //! drop their contents when they go out of scope.
   6 //!
   7 //! # Examples
   8 //!
   9 //! Move a value from the stack to the heap by creating a [`Box`]:
  10 //!
  11 //! ```
  12 //! let val: u8 = 5;
  13 //! let boxed: Box<u8> = Box::new(val);
  14 //! ```
  15 //!
  16 //! Move a value from a [`Box`] back to the stack by [dereferencing]:
  17 //!
  18 //! ```
  19 //! let boxed: Box<u8> = Box::new(5);
  20 //! let val: u8 = *boxed;
  21 //! ```
  22 //!
  23 //! Creating a recursive data structure:
  24 //!
  25 //! ```
  26 //! #[derive(Debug)]
  27 //! enum List<T> {
  28 //!     Cons(T, Box<List<T>>),
  29 //!     Nil,
  30 //! }
  31 //!
  32 //! let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
  33 //! println!("{:?}", list);
  34 //! ```
  35 //!
  36 //! This will print `Cons(1, Cons(2, Nil))`.
  37 //!
  38 //! Recursive structures must be boxed, because if the definition of `Cons`
  39 //! looked like this:
  40 //!
  41 //! ```compile_fail,E0072
  42 //! # enum List<T> {
  43 //! Cons(T, List<T>),
  44 //! # }
  45 //! ```
  46 //!
  47 //! It wouldn't work. This is because the size of a `List` depends on how many
  48 //! elements are in the list, and so we don't know how much memory to allocate
  49 //! for a `Cons`. By introducing a [`Box<T>`], which has a defined size, we know how
  50 //! big `Cons` needs to be.
  51 //!
  52 //! # Memory layout
  53 //!
  54 //! For non-zero-sized values, a [`Box`] will use the [`Global`] allocator for
  55 //! its allocation. It is valid to convert both ways between a [`Box`] and a
  56 //! raw pointer allocated with the [`Global`] allocator, given that the
  57 //! [`Layout`] used with the allocator is correct for the type. More precisely,
  58 //! a `value: *mut T` that has been allocated with the [`Global`] allocator
  59 //! with `Layout::for_value(&*value)` may be converted into a box using
  60 //! [`Box::<T>::from_raw(value)`]. Conversely, the memory backing a `value: *mut
  61 //! T` obtained from [`Box::<T>::into_raw`] may be deallocated using the
  62 //! [`Global`] allocator with [`Layout::for_value(&*value)`].
  63 //!
  64 //!
  65 //! [dereferencing]: ../../std/ops/trait.Deref.html
  66 //! [`Box`]: struct.Box.html
  67 //! [`Box<T>`]: struct.Box.html
  68 //! [`Box::<T>::from_raw(value)`]: struct.Box.html#method.from_raw
  69 //! [`Box::<T>::into_raw`]: struct.Box.html#method.into_raw
  70 //! [`Global`]: ../alloc/struct.Global.html
  71 //! [`Layout`]: ../alloc/struct.Layout.html
  72 //! [`Layout::for_value(&*value)`]: ../alloc/struct.Layout.html#method.for_value
  73
  74 #![stable(feature = "rust1", since = "1.0.0")]
  75
  76 use core::any::Any;
  77 use core::array::LengthAtMost32;
  78 use core::borrow;
  79 use core::cmp::Ordering;
  80 use core::convert::{From, TryFrom};
  81 use core::fmt;
  82 use core::future::Future;
  83 use core::hash::{Hash, Hasher};
  84 use core::iter::{Iterator, FromIterator, FusedIterator};
  85 use core::marker::{Unpin, Unsize};
  86 use core::mem;
  87 use core::pin::Pin;
  88 use core::ops::{
  89     CoerceUnsized, DispatchFromDyn, Deref, DerefMut, Receiver, Generator, GeneratorState
  90 };
  91 use core::ptr::{self, NonNull, Unique};
  92 use core::slice;
  93 use core::task::{Context, Poll};
  94
  95 use crate::alloc::{self, Global, Alloc};
  96 use crate::vec::Vec;
  97 use crate::raw_vec::RawVec;
  98 use crate::str::from_boxed_utf8_unchecked;
  99
 100 /// A pointer type for heap allocation.
 101 ///
 102 /// See the [module-level documentation](../../std/boxed/index.html) for more.
 103 #[lang = "owned_box"]
 104 #[fundamental]
 105 #[stable(feature = "rust1", since = "1.0.0")]
 106 pub struct Box<T: ?Sized>(Unique<T>);
 107
 108 impl<T> Box<T> {
 109     /// Allocates memory on the heap and then places `x` into it.
 110     ///
 111     /// This doesn't actually allocate if `T` is zero-sized.
 112     ///
 113     /// # Examples
 114     ///
 115     /// ```
 116     /// let five = Box::new(5);
 117     /// ```
 118     #[stable(feature = "rust1", since = "1.0.0")]
 119     #[inline(always)]
 120     pub fn new(x: T) -> Box<T> {
 121         box x
 122     }
 123
 124     /// Constructs a new box with uninitialized contents.
 125     ///
 126     /// # Examples
 127     ///
 128     /// ```
 129     /// #![feature(new_uninit)]
 130     ///
 131     /// let mut five = Box::<u32>::new_uninit();
 132     ///
 133     /// let five = unsafe {
 134     ///     // Deferred initialization:
 135     ///     five.as_mut_ptr().write(5);
 136     ///
 137     ///     five.assume_init()
 138     /// };
 139     ///
 140     /// assert_eq!(*five, 5)
 141     /// ```
 142     #[unstable(feature = "new_uninit", issue = "63291")]
 143     pub fn new_uninit() -> Box<mem::MaybeUninit<T>> {
 144         let layout = alloc::Layout::new::<mem::MaybeUninit<T>>();
 145         let ptr = unsafe {
 146             Global.alloc(layout)
 147                 .unwrap_or_else(|_| alloc::handle_alloc_error(layout))
 148         };
 149         Box(ptr.cast().into())
 150     }
 151
 152     /// Constructs a new `Pin<Box<T>>`. If `T` does not implement `Unpin`, then
 153     /// `x` will be pinned in memory and unable to be moved.
 154     #[stable(feature = "pin", since = "1.33.0")]
 155     #[inline(always)]
 156     pub fn pin(x: T) -> Pin<Box<T>> {
 157         (box x).into()
 158     }
 159 }
 160
 161 impl<T> Box<[T]> {
 162     /// Constructs a new boxed slice with uninitialized contents.
 163     ///
 164     /// # Examples
 165     ///
 166     /// ```
 167     /// #![feature(new_uninit)]
 168     ///
 169     /// let mut values = Box::<[u32]>::new_uninit_slice(3);
 170     ///
 171     /// let values = unsafe {
 172     ///     // Deferred initialization:
 173     ///     values[0].as_mut_ptr().write(1);
 174     ///     values[1].as_mut_ptr().write(2);
 175     ///     values[2].as_mut_ptr().write(3);
 176     ///
 177     ///     values.assume_init()
 178     /// };
 179     ///
 180     /// assert_eq!(*values, [1, 2, 3])
 181     /// ```
 182     #[unstable(feature = "new_uninit", issue = "63291")]
 183     pub fn new_uninit_slice(len: usize) -> Box<[mem::MaybeUninit<T>]> {
 184         let layout = alloc::Layout::array::<mem::MaybeUninit<T>>(len).unwrap();
 185         let ptr = unsafe { alloc::alloc(layout) };
 186         let unique = Unique::new(ptr).unwrap_or_else(|| alloc::handle_alloc_error(layout));
 187         let slice = unsafe { slice::from_raw_parts_mut(unique.cast().as_ptr(), len) };
 188         Box(Unique::from(slice))
 189     }
 190 }
 191
 192 impl<T> Box<mem::MaybeUninit<T>> {
 193     /// Converts to `Box<T>`.
 194     ///
 195     /// # Safety
 196     ///
 197     /// As with [`MaybeUninit::assume_init`],
 198     /// it is up to the caller to guarantee that the value
 199     /// really is in an initialized state.
 200     /// Calling this when the content is not yet fully initialized
 201     /// causes immediate undefined behavior.
 202     ///
 203     /// [`MaybeUninit::assume_init`]: ../../std/mem/union.MaybeUninit.html#method.assume_init
 204     ///
 205     /// # Examples
 206     ///
 207     /// ```
 208     /// #![feature(new_uninit)]
 209     ///
 210     /// let mut five = Box::<u32>::new_uninit();
 211     ///
 212     /// let five: Box<u32> = unsafe {
 213     ///     // Deferred initialization:
 214     ///     five.as_mut_ptr().write(5);
 215     ///
 216     ///     five.assume_init()
 217     /// };
 218     ///
 219     /// assert_eq!(*five, 5)
 220     /// ```
 221     #[unstable(feature = "new_uninit", issue = "63291")]
 222     #[inline]
 223     pub unsafe fn assume_init(self) -> Box<T> {
 224         Box(Box::into_unique(self).cast())
 225     }
 226 }
 227
 228 impl<T> Box<[mem::MaybeUninit<T>]> {
 229     /// Converts to `Box<[T]>`.
 230     ///
 231     /// # Safety
 232     ///
 233     /// As with [`MaybeUninit::assume_init`],
 234     /// it is up to the caller to guarantee that the values
 235     /// really are in an initialized state.
 236     /// Calling this when the content is not yet fully initialized
 237     /// causes immediate undefined behavior.
 238     ///
 239     /// [`MaybeUninit::assume_init`]: ../../std/mem/union.MaybeUninit.html#method.assume_init
 240     ///
 241     /// # Examples
 242     ///
 243     /// ```
 244     /// #![feature(new_uninit)]
 245     ///
 246     /// let mut values = Box::<[u32]>::new_uninit_slice(3);
 247     ///
 248     /// let values = unsafe {
 249     ///     // Deferred initialization:
 250     ///     values[0].as_mut_ptr().write(1);
 251     ///     values[1].as_mut_ptr().write(2);
 252     ///     values[2].as_mut_ptr().write(3);
 253     ///
 254     ///     values.assume_init()
 255     /// };
 256     ///
 257     /// assert_eq!(*values, [1, 2, 3])
 258     /// ```
 259     #[unstable(feature = "new_uninit", issue = "63291")]
 260     #[inline]
 261     pub unsafe fn assume_init(self) -> Box<[T]> {
 262         Box(Unique::new_unchecked(Box::into_raw(self) as _))
 263     }
 264 }
 265
 266 impl<T: ?Sized> Box<T> {
 267     /// Constructs a box from a raw pointer.
 268     ///
 269     /// After calling this function, the raw pointer is owned by the
 270     /// resulting `Box`. Specifically, the `Box` destructor will call
 271     /// the destructor of `T` and free the allocated memory. For this
 272     /// to be safe, the memory must have been allocated in accordance
 273     /// with the [memory layout] used by `Box` .
 274     ///
 275     /// # Safety
 276     ///
 277     /// This function is unsafe because improper use may lead to
 278     /// memory problems. For example, a double-free may occur if the
 279     /// function is called twice on the same raw pointer.
 280     ///
 281     /// # Examples
 282     /// Recreate a `Box` which was previously converted to a raw pointer
 283     /// using [`Box::into_raw`]:
 284     /// ```
 285     /// let x = Box::new(5);
 286     /// let ptr = Box::into_raw(x);
 287     /// let x = unsafe { Box::from_raw(ptr) };
 288     /// ```
 289     /// Manually create a `Box` from scratch by using the global allocator:
 290     /// ```
 291     /// use std::alloc::{alloc, Layout};
 292     ///
 293     /// unsafe {
 294     ///     let ptr = alloc(Layout::new::<i32>()) as *mut i32;
 295     ///     *ptr = 5;
 296     ///     let x = Box::from_raw(ptr);
 297     /// }
 298     /// ```
 299     ///
 300     /// [memory layout]: index.html#memory-layout
 301     /// [`Layout`]: ../alloc/struct.Layout.html
 302     /// [`Box::into_raw`]: struct.Box.html#method.into_raw
 303     #[stable(feature = "box_raw", since = "1.4.0")]
 304     #[inline]
 305     pub unsafe fn from_raw(raw: *mut T) -> Self {
 306         Box(Unique::new_unchecked(raw))
 307     }
 308
 309     /// Consumes the `Box`, returning a wrapped raw pointer.
 310     ///
 311     /// The pointer will be properly aligned and non-null.
 312     ///
 313     /// After calling this function, the caller is responsible for the
 314     /// memory previously managed by the `Box`. In particular, the
 315     /// caller should properly destroy `T` and release the memory, taking
 316     /// into account the [memory layout] used by `Box`. The easiest way to
 317     /// do this is to convert the raw pointer back into a `Box` with the
 318     /// [`Box::from_raw`] function, allowing the `Box` destructor to perform
 319     /// the cleanup.
 320     ///
 321     /// Note: this is an associated function, which means that you have
 322     /// to call it as `Box::into_raw(b)` instead of `b.into_raw()`. This
 323     /// is so that there is no conflict with a method on the inner type.
 324     ///
 325     /// # Examples
 326     /// Converting the raw pointer back into a `Box` with [`Box::from_raw`]
 327     /// for automatic cleanup:
 328     /// ```
 329     /// let x = Box::new(String::from("Hello"));
 330     /// let ptr = Box::into_raw(x);
 331     /// let x = unsafe { Box::from_raw(ptr) };
 332     /// ```
 333     /// Manual cleanup by explicitly running the destructor and deallocating
 334     /// the memory:
 335     /// ```
 336     /// use std::alloc::{dealloc, Layout};
 337     /// use std::ptr;
 338     ///
 339     /// let x = Box::new(String::from("Hello"));
 340     /// let p = Box::into_raw(x);
 341     /// unsafe {
 342     ///     ptr::drop_in_place(p);
 343     ///     dealloc(p as *mut u8, Layout::new::<String>());
 344     /// }
 345     /// ```
 346     ///
 347     /// [memory layout]: index.html#memory-layout
 348     /// [`Box::from_raw`]: struct.Box.html#method.from_raw
 349     #[stable(feature = "box_raw", since = "1.4.0")]
 350     #[inline]
 351     pub fn into_raw(b: Box<T>) -> *mut T {
 352         Box::into_raw_non_null(b).as_ptr()
 353     }
 354
 355     /// Consumes the `Box`, returning the wrapped pointer as `NonNull<T>`.
 356     ///
 357     /// After calling this function, the caller is responsible for the
 358     /// memory previously managed by the `Box`. In particular, the
 359     /// caller should properly destroy `T` and release the memory. The
 360     /// easiest way to do so is to convert the `NonNull<T>` pointer
 361     /// into a raw pointer and back into a `Box` with the [`Box::from_raw`]
 362     /// function.
 363     ///
 364     /// Note: this is an associated function, which means that you have
 365     /// to call it as `Box::into_raw_non_null(b)`
 366     /// instead of `b.into_raw_non_null()`. This
 367     /// is so that there is no conflict with a method on the inner type.
 368     ///
 369     /// [`Box::from_raw`]: struct.Box.html#method.from_raw
 370     ///
 371     /// # Examples
 372     ///
 373     /// ```
 374     /// #![feature(box_into_raw_non_null)]
 375     ///
 376     /// let x = Box::new(5);
 377     /// let ptr = Box::into_raw_non_null(x);
 378     ///
 379     /// // Clean up the memory by converting the NonNull pointer back
 380     /// // into a Box and letting the Box be dropped.
 381     /// let x = unsafe { Box::from_raw(ptr.as_ptr()) };
 382     /// ```
 383     #[unstable(feature = "box_into_raw_non_null", issue = "47336")]
 384     #[inline]
 385     pub fn into_raw_non_null(b: Box<T>) -> NonNull<T> {
 386         Box::into_unique(b).into()
 387     }
 388
 389     #[unstable(feature = "ptr_internals", issue = "0", reason = "use into_raw_non_null instead")]
 390     #[inline]
 391     #[doc(hidden)]
 392     pub fn into_unique(b: Box<T>) -> Unique<T> {
 393         let mut unique = b.0;
 394         mem::forget(b);
 395         // Box is kind-of a library type, but recognized as a "unique pointer" by
 396         // Stacked Borrows.  This function here corresponds to "reborrowing to
 397         // a raw pointer", but there is no actual reborrow here -- so
 398         // without some care, the pointer we are returning here still carries
 399         // the tag of `b`, with `Unique` permission.
 400         // We round-trip through a mutable reference to avoid that.
 401         unsafe { Unique::new_unchecked(unique.as_mut() as *mut T) }
 402     }
 403
 404     /// Consumes and leaks the `Box`, returning a mutable reference,
 405     /// `&'a mut T`. Note that the type `T` must outlive the chosen lifetime
 406     /// `'a`. If the type has only static references, or none at all, then this
 407     /// may be chosen to be `'static`.
 408     ///
 409     /// This function is mainly useful for data that lives for the remainder of
 410     /// the program's life. Dropping the returned reference will cause a memory
 411     /// leak. If this is not acceptable, the reference should first be wrapped
 412     /// with the [`Box::from_raw`] function producing a `Box`. This `Box` can
 413     /// then be dropped which will properly destroy `T` and release the
 414     /// allocated memory.
 415     ///
 416     /// Note: this is an associated function, which means that you have
 417     /// to call it as `Box::leak(b)` instead of `b.leak()`. This
 418     /// is so that there is no conflict with a method on the inner type.
 419     ///
 420     /// [`Box::from_raw`]: struct.Box.html#method.from_raw
 421     ///
 422     /// # Examples
 423     ///
 424     /// Simple usage:
 425     ///
 426     /// ```
 427     /// let x = Box::new(41);
 428     /// let static_ref: &'static mut usize = Box::leak(x);
 429     /// *static_ref += 1;
 430     /// assert_eq!(*static_ref, 42);
 431     /// ```
 432     ///
 433     /// Unsized data:
 434     ///
 435     /// ```
 436     /// let x = vec![1, 2, 3].into_boxed_slice();
 437     /// let static_ref = Box::leak(x);
 438     /// static_ref[0] = 4;
 439     /// assert_eq!(*static_ref, [4, 2, 3]);
 440     /// ```
 441     #[stable(feature = "box_leak", since = "1.26.0")]
 442     #[inline]
 443     pub fn leak<'a>(b: Box<T>) -> &'a mut T
 444     where
 445         T: 'a // Technically not needed, but kept to be explicit.
 446     {
 447         unsafe { &mut *Box::into_raw(b) }
 448     }
 449
 450     /// Converts a `Box<T>` into a `Pin<Box<T>>`
 451     ///
 452     /// This conversion does not allocate on the heap and happens in place.
 453     ///
 454     /// This is also available via [`From`].
 455     #[unstable(feature = "box_into_pin", issue = "62370")]
 456     pub fn into_pin(boxed: Box<T>) -> Pin<Box<T>> {
 457         // It's not possible to move or replace the insides of a `Pin<Box<T>>`
 458         // when `T: !Unpin`,  so it's safe to pin it directly without any
 459         // additional requirements.
 460         unsafe { Pin::new_unchecked(boxed) }
 461     }
 462 }
 463
 464 #[stable(feature = "rust1", since = "1.0.0")]
 465 unsafe impl<#[may_dangle] T: ?Sized> Drop for Box<T> {
 466     fn drop(&mut self) {
 467         // FIXME: Do nothing, drop is currently performed by compiler.
 468     }
 469 }
 470
 471 #[stable(feature = "rust1", since = "1.0.0")]
 472 impl<T: Default> Default for Box<T> {
 473     /// Creates a `Box<T>`, with the `Default` value for T.
 474     fn default() -> Box<T> {
 475         box Default::default()
 476     }
 477 }
 478
 479 #[stable(feature = "rust1", since = "1.0.0")]
 480 impl<T> Default for Box<[T]> {
 481     fn default() -> Box<[T]> {
 482         Box::<[T; 0]>::new([])
 483     }
 484 }
 485
 486 #[stable(feature = "default_box_extra", since = "1.17.0")]
 487 impl Default for Box<str> {
 488     fn default() -> Box<str> {
 489         unsafe { from_boxed_utf8_unchecked(Default::default()) }
 490     }
 491 }
 492
 493 #[stable(feature = "rust1", since = "1.0.0")]
 494 impl<T: Clone> Clone for Box<T> {
 495     /// Returns a new box with a `clone()` of this box's contents.
 496     ///
 497     /// # Examples
 498     ///
 499     /// ```
 500     /// let x = Box::new(5);
 501     /// let y = x.clone();
 502     ///
 503     /// // The value is the same
 504     /// assert_eq!(x, y);
 505     ///
 506     /// // But they are unique objects
 507     /// assert_ne!(&*x as *const i32, &*y as *const i32);
 508     /// ```
 509     #[rustfmt::skip]
 510     #[inline]
 511     fn clone(&self) -> Box<T> {
 512         box { (**self).clone() }
 513     }
 514
 515     /// Copies `source`'s contents into `self` without creating a new allocation.
 516     ///
 517     /// # Examples
 518     ///
 519     /// ```
 520     /// let x = Box::new(5);
 521     /// let mut y = Box::new(10);
 522     /// let yp: *const i32 = &*y;
 523     ///
 524     /// y.clone_from(&x);
 525     ///
 526     /// // The value is the same
 527     /// assert_eq!(x, y);
 528     ///
 529     /// // And no allocation occurred
 530     /// assert_eq!(yp, &*y);
 531     /// ```
 532     #[inline]
 533     fn clone_from(&mut self, source: &Box<T>) {
 534         (**self).clone_from(&(**source));
 535     }
 536 }
 537
 538
 539 #[stable(feature = "box_slice_clone", since = "1.3.0")]
 540 impl Clone for Box<str> {
 541     fn clone(&self) -> Self {
 542         // this makes a copy of the data
 543         let buf: Box<[u8]> = self.as_bytes().into();
 544         unsafe {
 545             from_boxed_utf8_unchecked(buf)
 546         }
 547     }
 548 }
 549
 550 #[stable(feature = "rust1", since = "1.0.0")]
 551 impl<T: ?Sized + PartialEq> PartialEq for Box<T> {
 552     #[inline]
 553     fn eq(&self, other: &Box<T>) -> bool {
 554         PartialEq::eq(&**self, &**other)
 555     }
 556     #[inline]
 557     fn ne(&self, other: &Box<T>) -> bool {
 558         PartialEq::ne(&**self, &**other)
 559     }
 560 }
 561 #[stable(feature = "rust1", since = "1.0.0")]
 562 impl<T: ?Sized + PartialOrd> PartialOrd for Box<T> {
 563     #[inline]
 564     fn partial_cmp(&self, other: &Box<T>) -> Option<Ordering> {
 565         PartialOrd::partial_cmp(&**self, &**other)
 566     }
 567     #[inline]
 568     fn lt(&self, other: &Box<T>) -> bool {
 569         PartialOrd::lt(&**self, &**other)
 570     }
 571     #[inline]
 572     fn le(&self, other: &Box<T>) -> bool {
 573         PartialOrd::le(&**self, &**other)
 574     }
 575     #[inline]
 576     fn ge(&self, other: &Box<T>) -> bool {
 577         PartialOrd::ge(&**self, &**other)
 578     }
 579     #[inline]
 580     fn gt(&self, other: &Box<T>) -> bool {
 581         PartialOrd::gt(&**self, &**other)
 582     }
 583 }
 584 #[stable(feature = "rust1", since = "1.0.0")]
 585 impl<T: ?Sized + Ord> Ord for Box<T> {
 586     #[inline]
 587     fn cmp(&self, other: &Box<T>) -> Ordering {
 588         Ord::cmp(&**self, &**other)
 589     }
 590 }
 591 #[stable(feature = "rust1", since = "1.0.0")]
 592 impl<T: ?Sized + Eq> Eq for Box<T> {}
 593
 594 #[stable(feature = "rust1", since = "1.0.0")]
 595 impl<T: ?Sized + Hash> Hash for Box<T> {
 596     fn hash<H: Hasher>(&self, state: &mut H) {
 597         (**self).hash(state);
 598     }
 599 }
 600
 601 #[stable(feature = "indirect_hasher_impl", since = "1.22.0")]
 602 impl<T: ?Sized + Hasher> Hasher for Box<T> {
 603     fn finish(&self) -> u64 {
 604         (**self).finish()
 605     }
 606     fn write(&mut self, bytes: &[u8]) {
 607         (**self).write(bytes)
 608     }
 609     fn write_u8(&mut self, i: u8) {
 610         (**self).write_u8(i)
 611     }
 612     fn write_u16(&mut self, i: u16) {
 613         (**self).write_u16(i)
 614     }
 615     fn write_u32(&mut self, i: u32) {
 616         (**self).write_u32(i)
 617     }
 618     fn write_u64(&mut self, i: u64) {
 619         (**self).write_u64(i)
 620     }
 621     fn write_u128(&mut self, i: u128) {
 622         (**self).write_u128(i)
 623     }
 624     fn write_usize(&mut self, i: usize) {
 625         (**self).write_usize(i)
 626     }
 627     fn write_i8(&mut self, i: i8) {
 628         (**self).write_i8(i)
 629     }
 630     fn write_i16(&mut self, i: i16) {
 631         (**self).write_i16(i)
 632     }
 633     fn write_i32(&mut self, i: i32) {
 634         (**self).write_i32(i)
 635     }
 636     fn write_i64(&mut self, i: i64) {
 637         (**self).write_i64(i)
 638     }
 639     fn write_i128(&mut self, i: i128) {
 640         (**self).write_i128(i)
 641     }
 642     fn write_isize(&mut self, i: isize) {
 643         (**self).write_isize(i)
 644     }
 645 }
 646
 647 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
 648 impl<T> From<T> for Box<T> {
 649     /// Converts a generic type `T` into a `Box<T>`
 650     ///
 651     /// The conversion allocates on the heap and moves `t`
 652     /// from the stack into it.
 653     ///
 654     /// # Examples
 655     /// ```rust
 656     /// let x = 5;
 657     /// let boxed = Box::new(5);
 658     ///
 659     /// assert_eq!(Box::from(x), boxed);
 660     /// ```
 661     fn from(t: T) -> Self {
 662         Box::new(t)
 663     }
 664 }
 665
 666 #[stable(feature = "pin", since = "1.33.0")]
 667 impl<T: ?Sized> From<Box<T>> for Pin<Box<T>> {
 668     /// Converts a `Box<T>` into a `Pin<Box<T>>`
 669     ///
 670     /// This conversion does not allocate on the heap and happens in place.
 671     fn from(boxed: Box<T>) -> Self {
 672         Box::into_pin(boxed)
 673     }
 674 }
 675
 676 #[stable(feature = "box_from_slice", since = "1.17.0")]
 677 impl<T: Copy> From<&[T]> for Box<[T]> {
 678     /// Converts a `&[T]` into a `Box<[T]>`
 679     ///
 680     /// This conversion allocates on the heap
 681     /// and performs a copy of `slice`.
 682     ///
 683     /// # Examples
 684     /// ```rust
 685     /// // create a &[u8] which will be used to create a Box<[u8]>
 686     /// let slice: &[u8] = &[104, 101, 108, 108, 111];
 687     /// let boxed_slice: Box<[u8]> = Box::from(slice);
 688     ///
 689     /// println!("{:?}", boxed_slice);
 690     /// ```
 691     fn from(slice: &[T]) -> Box<[T]> {
 692         let len = slice.len();
 693         let buf = RawVec::with_capacity(len);
 694         unsafe {
 695             ptr::copy_nonoverlapping(slice.as_ptr(), buf.ptr(), len);
 696             buf.into_box()
 697         }
 698     }
 699 }
 700
 701 #[stable(feature = "box_from_slice", since = "1.17.0")]
 702 impl From<&str> for Box<str> {
 703     /// Converts a `&str` into a `Box<str>`
 704     ///
 705     /// This conversion allocates on the heap
 706     /// and performs a copy of `s`.
 707     ///
 708     /// # Examples
 709     /// ```rust
 710     /// let boxed: Box<str> = Box::from("hello");
 711     /// println!("{}", boxed);
 712     /// ```
 713     #[inline]
 714     fn from(s: &str) -> Box<str> {
 715         unsafe { from_boxed_utf8_unchecked(Box::from(s.as_bytes())) }
 716     }
 717 }
 718
 719 #[stable(feature = "boxed_str_conv", since = "1.19.0")]
 720 impl From<Box<str>> for Box<[u8]> {
 721     /// Converts a `Box<str>>` into a `Box<[u8]>`
 722     ///
 723     /// This conversion does not allocate on the heap and happens in place.
 724     ///
 725     /// # Examples
 726     /// ```rust
 727     /// // create a Box<str> which will be used to create a Box<[u8]>
 728     /// let boxed: Box<str> = Box::from("hello");
 729     /// let boxed_str: Box<[u8]> = Box::from(boxed);
 730     ///
 731     /// // create a &[u8] which will be used to create a Box<[u8]>
 732     /// let slice: &[u8] = &[104, 101, 108, 108, 111];
 733     /// let boxed_slice = Box::from(slice);
 734     ///
 735     /// assert_eq!(boxed_slice, boxed_str);
 736     /// ```
 737     #[inline]
 738     fn from(s: Box<str>) -> Self {
 739         unsafe { Box::from_raw(Box::into_raw(s) as *mut [u8]) }
 740     }
 741 }
 742
 743 #[unstable(feature = "boxed_slice_try_from", issue = "0")]
 744 impl<T, const N: usize> TryFrom<Box<[T]>> for Box<[T; N]>
 745 where
 746     [T; N]: LengthAtMost32,
 747 {
 748     type Error = Box<[T]>;
 749
 750     fn try_from(boxed_slice: Box<[T]>) -> Result<Self, Self::Error> {
 751         if boxed_slice.len() == N {
 752             Ok(unsafe { Box::from_raw(Box::into_raw(boxed_slice) as *mut [T; N]) })
 753         } else {
 754             Err(boxed_slice)
 755         }
 756     }
 757 }
 758
 759 impl Box<dyn Any> {
 760     #[inline]
 761     #[stable(feature = "rust1", since = "1.0.0")]
 762     /// Attempt to downcast the box to a concrete type.
 763     ///
 764     /// # Examples
 765     ///
 766     /// ```
 767     /// use std::any::Any;
 768     ///
 769     /// fn print_if_string(value: Box<dyn Any>) {
 770     ///     if let Ok(string) = value.downcast::<String>() {
 771     ///         println!("String ({}): {}", string.len(), string);
 772     ///     }
 773     /// }
 774     ///
 775     /// let my_string = "Hello World".to_string();
 776     /// print_if_string(Box::new(my_string));
 777     /// print_if_string(Box::new(0i8));
 778     /// ```
 779     pub fn downcast<T: Any>(self) -> Result<Box<T>, Box<dyn Any>> {
 780         if self.is::<T>() {
 781             unsafe {
 782                 let raw: *mut dyn Any = Box::into_raw(self);
 783                 Ok(Box::from_raw(raw as *mut T))
 784             }
 785         } else {
 786             Err(self)
 787         }
 788     }
 789 }
 790
 791 impl Box<dyn Any + Send> {
 792     #[inline]
 793     #[stable(feature = "rust1", since = "1.0.0")]
 794     /// Attempt to downcast the box to a concrete type.
 795     ///
 796     /// # Examples
 797     ///
 798     /// ```
 799     /// use std::any::Any;
 800     ///
 801     /// fn print_if_string(value: Box<dyn Any + Send>) {
 802     ///     if let Ok(string) = value.downcast::<String>() {
 803     ///         println!("String ({}): {}", string.len(), string);
 804     ///     }
 805     /// }
 806     ///
 807     /// let my_string = "Hello World".to_string();
 808     /// print_if_string(Box::new(my_string));
 809     /// print_if_string(Box::new(0i8));
 810     /// ```
 811     pub fn downcast<T: Any>(self) -> Result<Box<T>, Box<dyn Any + Send>> {
 812         <Box<dyn Any>>::downcast(self).map_err(|s| unsafe {
 813             // reapply the Send marker
 814             Box::from_raw(Box::into_raw(s) as *mut (dyn Any + Send))
 815         })
 816     }
 817 }
 818
 819 #[stable(feature = "rust1", since = "1.0.0")]
 820 impl<T: fmt::Display + ?Sized> fmt::Display for Box<T> {
 821     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 822         fmt::Display::fmt(&**self, f)
 823     }
 824 }
 825
 826 #[stable(feature = "rust1", since = "1.0.0")]
 827 impl<T: fmt::Debug + ?Sized> fmt::Debug for Box<T> {
 828     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 829         fmt::Debug::fmt(&**self, f)
 830     }
 831 }
 832
 833 #[stable(feature = "rust1", since = "1.0.0")]
 834 impl<T: ?Sized> fmt::Pointer for Box<T> {
 835     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 836         // It's not possible to extract the inner Uniq directly from the Box,
 837         // instead we cast it to a *const which aliases the Unique
 838         let ptr: *const T = &**self;
 839         fmt::Pointer::fmt(&ptr, f)
 840     }
 841 }
 842
 843 #[stable(feature = "rust1", since = "1.0.0")]
 844 impl<T: ?Sized> Deref for Box<T> {
 845     type Target = T;
 846
 847     fn deref(&self) -> &T {
 848         &**self
 849     }
 850 }
 851
 852 #[stable(feature = "rust1", since = "1.0.0")]
 853 impl<T: ?Sized> DerefMut for Box<T> {
 854     fn deref_mut(&mut self) -> &mut T {
 855         &mut **self
 856     }
 857 }
 858
 859 #[unstable(feature = "receiver_trait", issue = "0")]
 860 impl<T: ?Sized> Receiver for Box<T> {}
 861
 862 #[stable(feature = "rust1", since = "1.0.0")]
 863 impl<I: Iterator + ?Sized> Iterator for Box<I> {
 864     type Item = I::Item;
 865     fn next(&mut self) -> Option<I::Item> {
 866         (**self).next()
 867     }
 868     fn size_hint(&self) -> (usize, Option<usize>) {
 869         (**self).size_hint()
 870     }
 871     fn nth(&mut self, n: usize) -> Option<I::Item> {
 872         (**self).nth(n)
 873     }
 874     fn last(self) -> Option<I::Item> {
 875         BoxIter::last(self)
 876     }
 877 }
 878
 879 trait BoxIter {
 880     type Item;
 881     fn last(self) -> Option<Self::Item>;
 882 }
 883
 884 impl<I: Iterator + ?Sized> BoxIter for Box<I> {
 885     type Item = I::Item;
 886     default fn last(self) -> Option<I::Item> {
 887         #[inline]
 888         fn some<T>(_: Option<T>, x: T) -> Option<T> {
 889             Some(x)
 890         }
 891
 892         self.fold(None, some)
 893     }
 894 }
 895
 896 /// Specialization for sized `I`s that uses `I`s implementation of `last()`
 897 /// instead of the default.
 898 #[stable(feature = "rust1", since = "1.0.0")]
 899 impl<I: Iterator> BoxIter for Box<I> {
 900     fn last(self) -> Option<I::Item> {
 901         (*self).last()
 902     }
 903 }
 904
 905 #[stable(feature = "rust1", since = "1.0.0")]
 906 impl<I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for Box<I> {
 907     fn next_back(&mut self) -> Option<I::Item> {
 908         (**self).next_back()
 909     }
 910     fn nth_back(&mut self, n: usize) -> Option<I::Item> {
 911         (**self).nth_back(n)
 912     }
 913 }
 914 #[stable(feature = "rust1", since = "1.0.0")]
 915 impl<I: ExactSizeIterator + ?Sized> ExactSizeIterator for Box<I> {
 916     fn len(&self) -> usize {
 917         (**self).len()
 918     }
 919     fn is_empty(&self) -> bool {
 920         (**self).is_empty()
 921     }
 922 }
 923
 924 #[stable(feature = "fused", since = "1.26.0")]
 925 impl<I: FusedIterator + ?Sized> FusedIterator for Box<I> {}
 926
 927 #[stable(feature = "boxed_closure_impls", since = "1.35.0")]
 928 impl<A, F: FnOnce<A> + ?Sized> FnOnce<A> for Box<F> {
 929     type Output = <F as FnOnce<A>>::Output;
 930
 931     extern "rust-call" fn call_once(self, args: A) -> Self::Output {
 932         <F as FnOnce<A>>::call_once(*self, args)
 933     }
 934 }
 935
 936 #[stable(feature = "boxed_closure_impls", since = "1.35.0")]
 937 impl<A, F: FnMut<A> + ?Sized> FnMut<A> for Box<F> {
 938     extern "rust-call" fn call_mut(&mut self, args: A) -> Self::Output {
 939         <F as FnMut<A>>::call_mut(self, args)
 940     }
 941 }
 942
 943 #[stable(feature = "boxed_closure_impls", since = "1.35.0")]
 944 impl<A, F: Fn<A> + ?Sized> Fn<A> for Box<F> {
 945     extern "rust-call" fn call(&self, args: A) -> Self::Output {
 946         <F as Fn<A>>::call(self, args)
 947     }
 948 }
 949
 950 #[unstable(feature = "coerce_unsized", issue = "27732")]
 951 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Box<U>> for Box<T> {}
 952
 953 #[unstable(feature = "dispatch_from_dyn", issue = "0")]
 954 impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Box<U>> for Box<T> {}
 955
 956 #[stable(feature = "boxed_slice_from_iter", since = "1.32.0")]
 957 impl<A> FromIterator<A> for Box<[A]> {
 958     fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
 959         iter.into_iter().collect::<Vec<_>>().into_boxed_slice()
 960     }
 961 }
 962
 963 #[stable(feature = "box_slice_clone", since = "1.3.0")]
 964 impl<T: Clone> Clone for Box<[T]> {
 965     fn clone(&self) -> Self {
 966         let mut new = BoxBuilder {
 967             data: RawVec::with_capacity(self.len()),
 968             len: 0,
 969         };
 970
 971         let mut target = new.data.ptr();
 972
 973         for item in self.iter() {
 974             unsafe {
 975                 ptr::write(target, item.clone());
 976                 target = target.offset(1);
 977             };
 978
 979             new.len += 1;
 980         }
 981
 982         return unsafe { new.into_box() };
 983
 984         // Helper type for responding to panics correctly.
 985         struct BoxBuilder<T> {
 986             data: RawVec<T>,
 987             len: usize,
 988         }
 989
 990         impl<T> BoxBuilder<T> {
 991             unsafe fn into_box(self) -> Box<[T]> {
 992                 let raw = ptr::read(&self.data);
 993                 mem::forget(self);
 994                 raw.into_box()
 995             }
 996         }
 997
 998         impl<T> Drop for BoxBuilder<T> {
 999             fn drop(&mut self) {
1000                 let mut data = self.data.ptr();
1001                 let max = unsafe { data.add(self.len) };
1002
1003                 while data != max {
1004                     unsafe {
1005                         ptr::read(data);
1006                         data = data.offset(1);
1007                     }
1008                 }
1009             }
1010         }
1011     }
1012 }
1013
1014 #[stable(feature = "box_borrow", since = "1.1.0")]
1015 impl<T: ?Sized> borrow::Borrow<T> for Box<T> {
1016     fn borrow(&self) -> &T {
1017         &**self
1018     }
1019 }
1020
1021 #[stable(feature = "box_borrow", since = "1.1.0")]
1022 impl<T: ?Sized> borrow::BorrowMut<T> for Box<T> {
1023     fn borrow_mut(&mut self) -> &mut T {
1024         &mut **self
1025     }
1026 }
1027
1028 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1029 impl<T: ?Sized> AsRef<T> for Box<T> {
1030     fn as_ref(&self) -> &T {
1031         &**self
1032     }
1033 }
1034
1035 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1036 impl<T: ?Sized> AsMut<T> for Box<T> {
1037     fn as_mut(&mut self) -> &mut T {
1038         &mut **self
1039     }
1040 }
1041
1042 /* Nota bene
1043  *
1044  *  We could have chosen not to add this impl, and instead have written a
1045  *  function of Pin<Box<T>> to Pin<T>. Such a function would not be sound,
1046  *  because Box<T> implements Unpin even when T does not, as a result of
1047  *  this impl.
1048  *
1049  *  We chose this API instead of the alternative for a few reasons:
1050  *      - Logically, it is helpful to understand pinning in regard to the
1051  *        memory region being pointed to. For this reason none of the
1052  *        standard library pointer types support projecting through a pin
1053  *        (Box<T> is the only pointer type in std for which this would be
1054  *        safe.)
1055  *      - It is in practice very useful to have Box<T> be unconditionally
1056  *        Unpin because of trait objects, for which the structural auto
1057  *        trait functionality does not apply (e.g., Box<dyn Foo> would
1058  *        otherwise not be Unpin).
1059  *
1060  *  Another type with the same semantics as Box but only a conditional
1061  *  implementation of `Unpin` (where `T: Unpin`) would be valid/safe, and
1062  *  could have a method to project a Pin<T> from it.
1063  */
1064 #[stable(feature = "pin", since = "1.33.0")]
1065 impl<T: ?Sized> Unpin for Box<T> { }
1066
1067 #[unstable(feature = "generator_trait", issue = "43122")]
1068 impl<G: ?Sized + Generator + Unpin> Generator for Box<G> {
1069     type Yield = G::Yield;
1070     type Return = G::Return;
1071
1072     fn resume(mut self: Pin<&mut Self>) -> GeneratorState<Self::Yield, Self::Return> {
1073         G::resume(Pin::new(&mut *self))
1074     }
1075 }
1076
1077 #[unstable(feature = "generator_trait", issue = "43122")]
1078 impl<G: ?Sized + Generator> Generator for Pin<Box<G>> {
1079     type Yield = G::Yield;
1080     type Return = G::Return;
1081
1082     fn resume(mut self: Pin<&mut Self>) -> GeneratorState<Self::Yield, Self::Return> {
1083         G::resume((*self).as_mut())
1084     }
1085 }
1086
1087 #[stable(feature = "futures_api", since = "1.36.0")]
1088 impl<F: ?Sized + Future + Unpin> Future for Box<F> {
1089     type Output = F::Output;
1090
1091     fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
1092         F::poll(Pin::new(&mut *self), cx)
1093     }
1094 }