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