src/liballoc/rc.rs

   1 //! Single-threaded reference-counting pointers. 'Rc' stands for 'Reference
   2 //! Counted'.
   3 //!
   4 //! The type [`Rc<T>`][`Rc`] provides shared ownership of a value of type `T`,
   5 //! allocated in the heap. Invoking [`clone`][clone] on [`Rc`] produces a new
   6 //! pointer to the same value in the heap. When the last [`Rc`] pointer to a
   7 //! given value is destroyed, the pointed-to value is also destroyed.
   8 //!
   9 //! Shared references in Rust disallow mutation by default, and [`Rc`]
  10 //! is no exception: you cannot generally obtain a mutable reference to
  11 //! something inside an [`Rc`]. If you need mutability, put a [`Cell`]
  12 //! or [`RefCell`] inside the [`Rc`]; see [an example of mutability
  13 //! inside an Rc][mutability].
  14 //!
  15 //! [`Rc`] uses non-atomic reference counting. This means that overhead is very
  16 //! low, but an [`Rc`] cannot be sent between threads, and consequently [`Rc`]
  17 //! does not implement [`Send`][send]. As a result, the Rust compiler
  18 //! will check *at compile time* that you are not sending [`Rc`]s between
  19 //! threads. If you need multi-threaded, atomic reference counting, use
  20 //! [`sync::Arc`][arc].
  21 //!
  22 //! The [`downgrade`][downgrade] method can be used to create a non-owning
  23 //! [`Weak`] pointer. A [`Weak`] pointer can be [`upgrade`][upgrade]d
  24 //! to an [`Rc`], but this will return [`None`] if the value has
  25 //! already been dropped.
  26 //!
  27 //! A cycle between [`Rc`] pointers will never be deallocated. For this reason,
  28 //! [`Weak`] is used to break cycles. For example, a tree could have strong
  29 //! [`Rc`] pointers from parent nodes to children, and [`Weak`] pointers from
  30 //! children back to their parents.
  31 //!
  32 //! `Rc<T>` automatically dereferences to `T` (via the [`Deref`] trait),
  33 //! so you can call `T`'s methods on a value of type [`Rc<T>`][`Rc`]. To avoid name
  34 //! clashes with `T`'s methods, the methods of [`Rc<T>`][`Rc`] itself are associated
  35 //! functions, called using function-like syntax:
  36 //!
  37 //! ```
  38 //! use std::rc::Rc;
  39 //! let my_rc = Rc::new(());
  40 //!
  41 //! Rc::downgrade(&my_rc);
  42 //! ```
  43 //!
  44 //! [`Weak<T>`][`Weak`] does not auto-dereference to `T`, because the value may have
  45 //! already been destroyed.
  46 //!
  47 //! # Cloning references
  48 //!
  49 //! Creating a new reference from an existing reference counted pointer is done using the
  50 //! `Clone` trait implemented for [`Rc<T>`][`Rc`] and [`Weak<T>`][`Weak`].
  51 //!
  52 //! ```
  53 //! use std::rc::Rc;
  54 //! let foo = Rc::new(vec![1.0, 2.0, 3.0]);
  55 //! // The two syntaxes below are equivalent.
  56 //! let a = foo.clone();
  57 //! let b = Rc::clone(&foo);
  58 //! // a and b both point to the same memory location as foo.
  59 //! ```
  60 //!
  61 //! The `Rc::clone(&from)` syntax is the most idiomatic because it conveys more explicitly
  62 //! the meaning of the code. In the example above, this syntax makes it easier to see that
  63 //! this code is creating a new reference rather than copying the whole content of foo.
  64 //!
  65 //! # Examples
  66 //!
  67 //! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`.
  68 //! We want to have our `Gadget`s point to their `Owner`. We can't do this with
  69 //! unique ownership, because more than one gadget may belong to the same
  70 //! `Owner`. [`Rc`] allows us to share an `Owner` between multiple `Gadget`s,
  71 //! and have the `Owner` remain allocated as long as any `Gadget` points at it.
  72 //!
  73 //! ```
  74 //! use std::rc::Rc;
  75 //!
  76 //! struct Owner {
  77 //!     name: String,
  78 //!     // ...other fields
  79 //! }
  80 //!
  81 //! struct Gadget {
  82 //!     id: i32,
  83 //!     owner: Rc<Owner>,
  84 //!     // ...other fields
  85 //! }
  86 //!
  87 //! fn main() {
  88 //!     // Create a reference-counted `Owner`.
  89 //!     let gadget_owner: Rc<Owner> = Rc::new(
  90 //!         Owner {
  91 //!             name: "Gadget Man".to_string(),
  92 //!         }
  93 //!     );
  94 //!
  95 //!     // Create `Gadget`s belonging to `gadget_owner`. Cloning the `Rc<Owner>`
  96 //!     // value gives us a new pointer to the same `Owner` value, incrementing
  97 //!     // the reference count in the process.
  98 //!     let gadget1 = Gadget {
  99 //!         id: 1,
 100 //!         owner: Rc::clone(&gadget_owner),
 101 //!     };
 102 //!     let gadget2 = Gadget {
 103 //!         id: 2,
 104 //!         owner: Rc::clone(&gadget_owner),
 105 //!     };
 106 //!
 107 //!     // Dispose of our local variable `gadget_owner`.
 108 //!     drop(gadget_owner);
 109 //!
 110 //!     // Despite dropping `gadget_owner`, we're still able to print out the name
 111 //!     // of the `Owner` of the `Gadget`s. This is because we've only dropped a
 112 //!     // single `Rc<Owner>`, not the `Owner` it points to. As long as there are
 113 //!     // other `Rc<Owner>` values pointing at the same `Owner`, it will remain
 114 //!     // allocated. The field projection `gadget1.owner.name` works because
 115 //!     // `Rc<Owner>` automatically dereferences to `Owner`.
 116 //!     println!("Gadget {} owned by {}", gadget1.id, gadget1.owner.name);
 117 //!     println!("Gadget {} owned by {}", gadget2.id, gadget2.owner.name);
 118 //!
 119 //!     // At the end of the function, `gadget1` and `gadget2` are destroyed, and
 120 //!     // with them the last counted references to our `Owner`. Gadget Man now
 121 //!     // gets destroyed as well.
 122 //! }
 123 //! ```
 124 //!
 125 //! If our requirements change, and we also need to be able to traverse from
 126 //! `Owner` to `Gadget`, we will run into problems. An [`Rc`] pointer from `Owner`
 127 //! to `Gadget` introduces a cycle between the values. This means that their
 128 //! reference counts can never reach 0, and the values will remain allocated
 129 //! forever: a memory leak. In order to get around this, we can use [`Weak`]
 130 //! pointers.
 131 //!
 132 //! Rust actually makes it somewhat difficult to produce this loop in the first
 133 //! place. In order to end up with two values that point at each other, one of
 134 //! them needs to be mutable. This is difficult because [`Rc`] enforces
 135 //! memory safety by only giving out shared references to the value it wraps,
 136 //! and these don't allow direct mutation. We need to wrap the part of the
 137 //! value we wish to mutate in a [`RefCell`], which provides *interior
 138 //! mutability*: a method to achieve mutability through a shared reference.
 139 //! [`RefCell`] enforces Rust's borrowing rules at runtime.
 140 //!
 141 //! ```
 142 //! use std::rc::Rc;
 143 //! use std::rc::Weak;
 144 //! use std::cell::RefCell;
 145 //!
 146 //! struct Owner {
 147 //!     name: String,
 148 //!     gadgets: RefCell<Vec<Weak<Gadget>>>,
 149 //!     // ...other fields
 150 //! }
 151 //!
 152 //! struct Gadget {
 153 //!     id: i32,
 154 //!     owner: Rc<Owner>,
 155 //!     // ...other fields
 156 //! }
 157 //!
 158 //! fn main() {
 159 //!     // Create a reference-counted `Owner`. Note that we've put the `Owner`'s
 160 //!     // vector of `Gadget`s inside a `RefCell` so that we can mutate it through
 161 //!     // a shared reference.
 162 //!     let gadget_owner: Rc<Owner> = Rc::new(
 163 //!         Owner {
 164 //!             name: "Gadget Man".to_string(),
 165 //!             gadgets: RefCell::new(vec![]),
 166 //!         }
 167 //!     );
 168 //!
 169 //!     // Create `Gadget`s belonging to `gadget_owner`, as before.
 170 //!     let gadget1 = Rc::new(
 171 //!         Gadget {
 172 //!             id: 1,
 173 //!             owner: Rc::clone(&gadget_owner),
 174 //!         }
 175 //!     );
 176 //!     let gadget2 = Rc::new(
 177 //!         Gadget {
 178 //!             id: 2,
 179 //!             owner: Rc::clone(&gadget_owner),
 180 //!         }
 181 //!     );
 182 //!
 183 //!     // Add the `Gadget`s to their `Owner`.
 184 //!     {
 185 //!         let mut gadgets = gadget_owner.gadgets.borrow_mut();
 186 //!         gadgets.push(Rc::downgrade(&gadget1));
 187 //!         gadgets.push(Rc::downgrade(&gadget2));
 188 //!
 189 //!         // `RefCell` dynamic borrow ends here.
 190 //!     }
 191 //!
 192 //!     // Iterate over our `Gadget`s, printing their details out.
 193 //!     for gadget_weak in gadget_owner.gadgets.borrow().iter() {
 194 //!
 195 //!         // `gadget_weak` is a `Weak<Gadget>`. Since `Weak` pointers can't
 196 //!         // guarantee the value is still allocated, we need to call
 197 //!         // `upgrade`, which returns an `Option<Rc<Gadget>>`.
 198 //!         //
 199 //!         // In this case we know the value still exists, so we simply
 200 //!         // `unwrap` the `Option`. In a more complicated program, you might
 201 //!         // need graceful error handling for a `None` result.
 202 //!
 203 //!         let gadget = gadget_weak.upgrade().unwrap();
 204 //!         println!("Gadget {} owned by {}", gadget.id, gadget.owner.name);
 205 //!     }
 206 //!
 207 //!     // At the end of the function, `gadget_owner`, `gadget1`, and `gadget2`
 208 //!     // are destroyed. There are now no strong (`Rc`) pointers to the
 209 //!     // gadgets, so they are destroyed. This zeroes the reference count on
 210 //!     // Gadget Man, so he gets destroyed as well.
 211 //! }
 212 //! ```
 213 //!
 214 //! [`Rc`]: struct.Rc.html
 215 //! [`Weak`]: struct.Weak.html
 216 //! [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 217 //! [`Cell`]: ../../std/cell/struct.Cell.html
 218 //! [`RefCell`]: ../../std/cell/struct.RefCell.html
 219 //! [send]: ../../std/marker/trait.Send.html
 220 //! [arc]: ../../std/sync/struct.Arc.html
 221 //! [`Deref`]: ../../std/ops/trait.Deref.html
 222 //! [downgrade]: struct.Rc.html#method.downgrade
 223 //! [upgrade]: struct.Weak.html#method.upgrade
 224 //! [`None`]: ../../std/option/enum.Option.html#variant.None
 225 //! [mutability]: ../../std/cell/index.html#introducing-mutability-inside-of-something-immutable
 226
 227 #![stable(feature = "rust1", since = "1.0.0")]
 228
 229 #[cfg(not(test))]
 230 use crate::boxed::Box;
 231 #[cfg(test)]
 232 use std::boxed::Box;
 233
 234 use core::any::Any;
 235 use core::borrow;
 236 use core::cell::Cell;
 237 use core::cmp::Ordering;
 238 use core::fmt;
 239 use core::hash::{Hash, Hasher};
 240 use core::intrinsics::abort;
 241 use core::marker::{self, Unpin, Unsize, PhantomData};
 242 use core::mem::{self, align_of, align_of_val, forget, size_of_val};
 243 use core::ops::{Deref, Receiver, CoerceUnsized, DispatchFromDyn};
 244 use core::pin::Pin;
 245 use core::ptr::{self, NonNull};
 246 use core::slice::from_raw_parts_mut;
 247 use core::convert::From;
 248 use core::usize;
 249
 250 use crate::alloc::{Global, Alloc, Layout, box_free, handle_alloc_error};
 251 use crate::string::String;
 252 use crate::vec::Vec;
 253
 254 struct RcBox<T: ?Sized> {
 255     strong: Cell<usize>,
 256     weak: Cell<usize>,
 257     value: T,
 258 }
 259
 260 /// A single-threaded reference-counting pointer. 'Rc' stands for 'Reference
 261 /// Counted'.
 262 ///
 263 /// See the [module-level documentation](./index.html) for more details.
 264 ///
 265 /// The inherent methods of `Rc` are all associated functions, which means
 266 /// that you have to call them as e.g., [`Rc::get_mut(&mut value)`][get_mut] instead of
 267 /// `value.get_mut()`. This avoids conflicts with methods of the inner
 268 /// type `T`.
 269 ///
 270 /// [get_mut]: #method.get_mut
 271 #[cfg_attr(not(test), lang = "rc")]
 272 #[stable(feature = "rust1", since = "1.0.0")]
 273 pub struct Rc<T: ?Sized> {
 274     ptr: NonNull<RcBox<T>>,
 275     phantom: PhantomData<T>,
 276 }
 277
 278 #[stable(feature = "rust1", since = "1.0.0")]
 279 impl<T: ?Sized> !marker::Send for Rc<T> {}
 280 #[stable(feature = "rust1", since = "1.0.0")]
 281 impl<T: ?Sized> !marker::Sync for Rc<T> {}
 282
 283 #[unstable(feature = "coerce_unsized", issue = "27732")]
 284 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Rc<U>> for Rc<T> {}
 285
 286 #[unstable(feature = "dispatch_from_dyn", issue = "0")]
 287 impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Rc<U>> for Rc<T> {}
 288
 289 impl<T> Rc<T> {
 290     /// Constructs a new `Rc<T>`.
 291     ///
 292     /// # Examples
 293     ///
 294     /// ```
 295     /// use std::rc::Rc;
 296     ///
 297     /// let five = Rc::new(5);
 298     /// ```
 299     #[stable(feature = "rust1", since = "1.0.0")]
 300     pub fn new(value: T) -> Rc<T> {
 301         Rc {
 302             // there is an implicit weak pointer owned by all the strong
 303             // pointers, which ensures that the weak destructor never frees
 304             // the allocation while the strong destructor is running, even
 305             // if the weak pointer is stored inside the strong one.
 306             ptr: Box::into_raw_non_null(box RcBox {
 307                 strong: Cell::new(1),
 308                 weak: Cell::new(1),
 309                 value,
 310             }),
 311             phantom: PhantomData,
 312         }
 313     }
 314
 315     /// Constructs a new `Pin<Rc<T>>`. If `T` does not implement `Unpin`, then
 316     /// `value` will be pinned in memory and unable to be moved.
 317     #[stable(feature = "pin", since = "1.33.0")]
 318     pub fn pin(value: T) -> Pin<Rc<T>> {
 319         unsafe { Pin::new_unchecked(Rc::new(value)) }
 320     }
 321
 322     /// Returns the contained value, if the `Rc` has exactly one strong reference.
 323     ///
 324     /// Otherwise, an [`Err`][result] is returned with the same `Rc` that was
 325     /// passed in.
 326     ///
 327     /// This will succeed even if there are outstanding weak references.
 328     ///
 329     /// [result]: ../../std/result/enum.Result.html
 330     ///
 331     /// # Examples
 332     ///
 333     /// ```
 334     /// use std::rc::Rc;
 335     ///
 336     /// let x = Rc::new(3);
 337     /// assert_eq!(Rc::try_unwrap(x), Ok(3));
 338     ///
 339     /// let x = Rc::new(4);
 340     /// let _y = Rc::clone(&x);
 341     /// assert_eq!(*Rc::try_unwrap(x).unwrap_err(), 4);
 342     /// ```
 343     #[inline]
 344     #[stable(feature = "rc_unique", since = "1.4.0")]
 345     pub fn try_unwrap(this: Self) -> Result<T, Self> {
 346         if Rc::strong_count(&this) == 1 {
 347             unsafe {
 348                 let val = ptr::read(&*this); // copy the contained object
 349
 350                 // Indicate to Weaks that they can't be promoted by decrementing
 351                 // the strong count, and then remove the implicit "strong weak"
 352                 // pointer while also handling drop logic by just crafting a
 353                 // fake Weak.
 354                 this.dec_strong();
 355                 let _weak = Weak { ptr: this.ptr };
 356                 forget(this);
 357                 Ok(val)
 358             }
 359         } else {
 360             Err(this)
 361         }
 362     }
 363 }
 364
 365 impl<T: ?Sized> Rc<T> {
 366     /// Consumes the `Rc`, returning the wrapped pointer.
 367     ///
 368     /// To avoid a memory leak the pointer must be converted back to an `Rc` using
 369     /// [`Rc::from_raw`][from_raw].
 370     ///
 371     /// [from_raw]: struct.Rc.html#method.from_raw
 372     ///
 373     /// # Examples
 374     ///
 375     /// ```
 376     /// use std::rc::Rc;
 377     ///
 378     /// let x = Rc::new(10);
 379     /// let x_ptr = Rc::into_raw(x);
 380     /// assert_eq!(unsafe { *x_ptr }, 10);
 381     /// ```
 382     #[stable(feature = "rc_raw", since = "1.17.0")]
 383     pub fn into_raw(this: Self) -> *const T {
 384         let ptr: *const T = &*this;
 385         mem::forget(this);
 386         ptr
 387     }
 388
 389     /// Constructs an `Rc` from a raw pointer.
 390     ///
 391     /// The raw pointer must have been previously returned by a call to a
 392     /// [`Rc::into_raw`][into_raw].
 393     ///
 394     /// This function is unsafe because improper use may lead to memory problems. For example, a
 395     /// double-free may occur if the function is called twice on the same raw pointer.
 396     ///
 397     /// [into_raw]: struct.Rc.html#method.into_raw
 398     ///
 399     /// # Examples
 400     ///
 401     /// ```
 402     /// use std::rc::Rc;
 403     ///
 404     /// let x = Rc::new(10);
 405     /// let x_ptr = Rc::into_raw(x);
 406     ///
 407     /// unsafe {
 408     ///     // Convert back to an `Rc` to prevent leak.
 409     ///     let x = Rc::from_raw(x_ptr);
 410     ///     assert_eq!(*x, 10);
 411     ///
 412     ///     // Further calls to `Rc::from_raw(x_ptr)` would be memory unsafe.
 413     /// }
 414     ///
 415     /// // The memory was freed when `x` went out of scope above, so `x_ptr` is now dangling!
 416     /// ```
 417     #[stable(feature = "rc_raw", since = "1.17.0")]
 418     pub unsafe fn from_raw(ptr: *const T) -> Self {
 419         let offset = data_offset(ptr);
 420
 421         // Reverse the offset to find the original RcBox.
 422         let fake_ptr = ptr as *mut RcBox<T>;
 423         let rc_ptr = set_data_ptr(fake_ptr, (ptr as *mut u8).offset(-offset));
 424
 425         Rc {
 426             ptr: NonNull::new_unchecked(rc_ptr),
 427             phantom: PhantomData,
 428         }
 429     }
 430
 431     /// Consumes the `Rc`, returning the wrapped pointer as `NonNull<T>`.
 432     ///
 433     /// # Examples
 434     ///
 435     /// ```
 436     /// #![feature(rc_into_raw_non_null)]
 437     ///
 438     /// use std::rc::Rc;
 439     ///
 440     /// let x = Rc::new(10);
 441     /// let ptr = Rc::into_raw_non_null(x);
 442     /// let deref = unsafe { *ptr.as_ref() };
 443     /// assert_eq!(deref, 10);
 444     /// ```
 445     #[unstable(feature = "rc_into_raw_non_null", issue = "47336")]
 446     #[inline]
 447     pub fn into_raw_non_null(this: Self) -> NonNull<T> {
 448         // safe because Rc guarantees its pointer is non-null
 449         unsafe { NonNull::new_unchecked(Rc::into_raw(this) as *mut _) }
 450     }
 451
 452     /// Creates a new [`Weak`][weak] pointer to this value.
 453     ///
 454     /// [weak]: struct.Weak.html
 455     ///
 456     /// # Examples
 457     ///
 458     /// ```
 459     /// use std::rc::Rc;
 460     ///
 461     /// let five = Rc::new(5);
 462     ///
 463     /// let weak_five = Rc::downgrade(&five);
 464     /// ```
 465     #[stable(feature = "rc_weak", since = "1.4.0")]
 466     pub fn downgrade(this: &Self) -> Weak<T> {
 467         this.inc_weak();
 468         // Make sure we do not create a dangling Weak
 469         debug_assert!(!is_dangling(this.ptr));
 470         Weak { ptr: this.ptr }
 471     }
 472
 473     /// Gets the number of [`Weak`][weak] pointers to this value.
 474     ///
 475     /// [weak]: struct.Weak.html
 476     ///
 477     /// # Examples
 478     ///
 479     /// ```
 480     /// use std::rc::Rc;
 481     ///
 482     /// let five = Rc::new(5);
 483     /// let _weak_five = Rc::downgrade(&five);
 484     ///
 485     /// assert_eq!(1, Rc::weak_count(&five));
 486     /// ```
 487     #[inline]
 488     #[stable(feature = "rc_counts", since = "1.15.0")]
 489     pub fn weak_count(this: &Self) -> usize {
 490         this.weak() - 1
 491     }
 492
 493     /// Gets the number of strong (`Rc`) pointers to this value.
 494     ///
 495     /// # Examples
 496     ///
 497     /// ```
 498     /// use std::rc::Rc;
 499     ///
 500     /// let five = Rc::new(5);
 501     /// let _also_five = Rc::clone(&five);
 502     ///
 503     /// assert_eq!(2, Rc::strong_count(&five));
 504     /// ```
 505     #[inline]
 506     #[stable(feature = "rc_counts", since = "1.15.0")]
 507     pub fn strong_count(this: &Self) -> usize {
 508         this.strong()
 509     }
 510
 511     /// Returns `true` if there are no other `Rc` or [`Weak`][weak] pointers to
 512     /// this inner value.
 513     ///
 514     /// [weak]: struct.Weak.html
 515     #[inline]
 516     fn is_unique(this: &Self) -> bool {
 517         Rc::weak_count(this) == 0 && Rc::strong_count(this) == 1
 518     }
 519
 520     /// Returns a mutable reference to the inner value, if there are
 521     /// no other `Rc` or [`Weak`][weak] pointers to the same value.
 522     ///
 523     /// Returns [`None`] otherwise, because it is not safe to
 524     /// mutate a shared value.
 525     ///
 526     /// See also [`make_mut`][make_mut], which will [`clone`][clone]
 527     /// the inner value when it's shared.
 528     ///
 529     /// [weak]: struct.Weak.html
 530     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 531     /// [make_mut]: struct.Rc.html#method.make_mut
 532     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 533     ///
 534     /// # Examples
 535     ///
 536     /// ```
 537     /// use std::rc::Rc;
 538     ///
 539     /// let mut x = Rc::new(3);
 540     /// *Rc::get_mut(&mut x).unwrap() = 4;
 541     /// assert_eq!(*x, 4);
 542     ///
 543     /// let _y = Rc::clone(&x);
 544     /// assert!(Rc::get_mut(&mut x).is_none());
 545     /// ```
 546     #[inline]
 547     #[stable(feature = "rc_unique", since = "1.4.0")]
 548     pub fn get_mut(this: &mut Self) -> Option<&mut T> {
 549         if Rc::is_unique(this) {
 550             unsafe {
 551                 Some(&mut this.ptr.as_mut().value)
 552             }
 553         } else {
 554             None
 555         }
 556     }
 557
 558     #[inline]
 559     #[stable(feature = "ptr_eq", since = "1.17.0")]
 560     /// Returns `true` if the two `Rc`s point to the same value (not
 561     /// just values that compare as equal).
 562     ///
 563     /// # Examples
 564     ///
 565     /// ```
 566     /// use std::rc::Rc;
 567     ///
 568     /// let five = Rc::new(5);
 569     /// let same_five = Rc::clone(&five);
 570     /// let other_five = Rc::new(5);
 571     ///
 572     /// assert!(Rc::ptr_eq(&five, &same_five));
 573     /// assert!(!Rc::ptr_eq(&five, &other_five));
 574     /// ```
 575     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
 576         this.ptr.as_ptr() == other.ptr.as_ptr()
 577     }
 578 }
 579
 580 impl<T: Clone> Rc<T> {
 581     /// Makes a mutable reference into the given `Rc`.
 582     ///
 583     /// If there are other `Rc` or [`Weak`][weak] pointers to the same value,
 584     /// then `make_mut` will invoke [`clone`][clone] on the inner value to
 585     /// ensure unique ownership. This is also referred to as clone-on-write.
 586     ///
 587     /// See also [`get_mut`][get_mut], which will fail rather than cloning.
 588     ///
 589     /// [weak]: struct.Weak.html
 590     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 591     /// [get_mut]: struct.Rc.html#method.get_mut
 592     ///
 593     /// # Examples
 594     ///
 595     /// ```
 596     /// use std::rc::Rc;
 597     ///
 598     /// let mut data = Rc::new(5);
 599     ///
 600     /// *Rc::make_mut(&mut data) += 1;        // Won't clone anything
 601     /// let mut other_data = Rc::clone(&data);    // Won't clone inner data
 602     /// *Rc::make_mut(&mut data) += 1;        // Clones inner data
 603     /// *Rc::make_mut(&mut data) += 1;        // Won't clone anything
 604     /// *Rc::make_mut(&mut other_data) *= 2;  // Won't clone anything
 605     ///
 606     /// // Now `data` and `other_data` point to different values.
 607     /// assert_eq!(*data, 8);
 608     /// assert_eq!(*other_data, 12);
 609     /// ```
 610     #[inline]
 611     #[stable(feature = "rc_unique", since = "1.4.0")]
 612     pub fn make_mut(this: &mut Self) -> &mut T {
 613         if Rc::strong_count(this) != 1 {
 614             // Gotta clone the data, there are other Rcs
 615             *this = Rc::new((**this).clone())
 616         } else if Rc::weak_count(this) != 0 {
 617             // Can just steal the data, all that's left is Weaks
 618             unsafe {
 619                 let mut swap = Rc::new(ptr::read(&this.ptr.as_ref().value));
 620                 mem::swap(this, &mut swap);
 621                 swap.dec_strong();
 622                 // Remove implicit strong-weak ref (no need to craft a fake
 623                 // Weak here -- we know other Weaks can clean up for us)
 624                 swap.dec_weak();
 625                 forget(swap);
 626             }
 627         }
 628         // This unsafety is ok because we're guaranteed that the pointer
 629         // returned is the *only* pointer that will ever be returned to T. Our
 630         // reference count is guaranteed to be 1 at this point, and we required
 631         // the `Rc<T>` itself to be `mut`, so we're returning the only possible
 632         // reference to the inner value.
 633         unsafe {
 634             &mut this.ptr.as_mut().value
 635         }
 636     }
 637 }
 638
 639 impl Rc<dyn Any> {
 640     #[inline]
 641     #[stable(feature = "rc_downcast", since = "1.29.0")]
 642     /// Attempt to downcast the `Rc<dyn Any>` to a concrete type.
 643     ///
 644     /// # Examples
 645     ///
 646     /// ```
 647     /// use std::any::Any;
 648     /// use std::rc::Rc;
 649     ///
 650     /// fn print_if_string(value: Rc<dyn Any>) {
 651     ///     if let Ok(string) = value.downcast::<String>() {
 652     ///         println!("String ({}): {}", string.len(), string);
 653     ///     }
 654     /// }
 655     ///
 656     /// fn main() {
 657     ///     let my_string = "Hello World".to_string();
 658     ///     print_if_string(Rc::new(my_string));
 659     ///     print_if_string(Rc::new(0i8));
 660     /// }
 661     /// ```
 662     pub fn downcast<T: Any>(self) -> Result<Rc<T>, Rc<dyn Any>> {
 663         if (*self).is::<T>() {
 664             let ptr = self.ptr.cast::<RcBox<T>>();
 665             forget(self);
 666             Ok(Rc { ptr, phantom: PhantomData })
 667         } else {
 668             Err(self)
 669         }
 670     }
 671 }
 672
 673 impl<T: ?Sized> Rc<T> {
 674     // Allocates an `RcBox<T>` with sufficient space for an unsized value
 675     unsafe fn allocate_for_ptr(ptr: *const T) -> *mut RcBox<T> {
 676         // Calculate layout using the given value.
 677         // Previously, layout was calculated on the expression
 678         // `&*(ptr as *const RcBox<T>)`, but this created a misaligned
 679         // reference (see #54908).
 680         let layout = Layout::new::<RcBox<()>>()
 681             .extend(Layout::for_value(&*ptr)).unwrap().0
 682             .pad_to_align().unwrap();
 683
 684         let mem = Global.alloc(layout)
 685             .unwrap_or_else(|_| handle_alloc_error(layout));
 686
 687         // Initialize the RcBox
 688         let inner = set_data_ptr(ptr as *mut T, mem.as_ptr() as *mut u8) as *mut RcBox<T>;
 689         debug_assert_eq!(Layout::for_value(&*inner), layout);
 690
 691         ptr::write(&mut (*inner).strong, Cell::new(1));
 692         ptr::write(&mut (*inner).weak, Cell::new(1));
 693
 694         inner
 695     }
 696
 697     fn from_box(v: Box<T>) -> Rc<T> {
 698         unsafe {
 699             let box_unique = Box::into_unique(v);
 700             let bptr = box_unique.as_ptr();
 701
 702             let value_size = size_of_val(&*bptr);
 703             let ptr = Self::allocate_for_ptr(bptr);
 704
 705             // Copy value as bytes
 706             ptr::copy_nonoverlapping(
 707                 bptr as *const T as *const u8,
 708                 &mut (*ptr).value as *mut _ as *mut u8,
 709                 value_size);
 710
 711             // Free the allocation without dropping its contents
 712             box_free(box_unique);
 713
 714             Rc { ptr: NonNull::new_unchecked(ptr), phantom: PhantomData }
 715         }
 716     }
 717 }
 718
 719 // Sets the data pointer of a `?Sized` raw pointer.
 720 //
 721 // For a slice/trait object, this sets the `data` field and leaves the rest
 722 // unchanged. For a sized raw pointer, this simply sets the pointer.
 723 unsafe fn set_data_ptr<T: ?Sized, U>(mut ptr: *mut T, data: *mut U) -> *mut T {
 724     ptr::write(&mut ptr as *mut _ as *mut *mut u8, data as *mut u8);
 725     ptr
 726 }
 727
 728 impl<T> Rc<[T]> {
 729     // Copy elements from slice into newly allocated Rc<[T]>
 730     //
 731     // Unsafe because the caller must either take ownership or bind `T: Copy`
 732     unsafe fn copy_from_slice(v: &[T]) -> Rc<[T]> {
 733         let v_ptr = v as *const [T];
 734         let ptr = Self::allocate_for_ptr(v_ptr);
 735
 736         ptr::copy_nonoverlapping(
 737             v.as_ptr(),
 738             &mut (*ptr).value as *mut [T] as *mut T,
 739             v.len());
 740
 741         Rc { ptr: NonNull::new_unchecked(ptr), phantom: PhantomData }
 742     }
 743 }
 744
 745 trait RcFromSlice<T> {
 746     fn from_slice(slice: &[T]) -> Self;
 747 }
 748
 749 impl<T: Clone> RcFromSlice<T> for Rc<[T]> {
 750     #[inline]
 751     default fn from_slice(v: &[T]) -> Self {
 752         // Panic guard while cloning T elements.
 753         // In the event of a panic, elements that have been written
 754         // into the new RcBox will be dropped, then the memory freed.
 755         struct Guard<T> {
 756             mem: NonNull<u8>,
 757             elems: *mut T,
 758             layout: Layout,
 759             n_elems: usize,
 760         }
 761
 762         impl<T> Drop for Guard<T> {
 763             fn drop(&mut self) {
 764                 unsafe {
 765                     let slice = from_raw_parts_mut(self.elems, self.n_elems);
 766                     ptr::drop_in_place(slice);
 767
 768                     Global.dealloc(self.mem, self.layout.clone());
 769                 }
 770             }
 771         }
 772
 773         unsafe {
 774             let v_ptr = v as *const [T];
 775             let ptr = Self::allocate_for_ptr(v_ptr);
 776
 777             let mem = ptr as *mut _ as *mut u8;
 778             let layout = Layout::for_value(&*ptr);
 779
 780             // Pointer to first element
 781             let elems = &mut (*ptr).value as *mut [T] as *mut T;
 782
 783             let mut guard = Guard{
 784                 mem: NonNull::new_unchecked(mem),
 785                 elems: elems,
 786                 layout: layout,
 787                 n_elems: 0,
 788             };
 789
 790             for (i, item) in v.iter().enumerate() {
 791                 ptr::write(elems.add(i), item.clone());
 792                 guard.n_elems += 1;
 793             }
 794
 795             // All clear. Forget the guard so it doesn't free the new RcBox.
 796             forget(guard);
 797
 798             Rc { ptr: NonNull::new_unchecked(ptr), phantom: PhantomData }
 799         }
 800     }
 801 }
 802
 803 impl<T: Copy> RcFromSlice<T> for Rc<[T]> {
 804     #[inline]
 805     fn from_slice(v: &[T]) -> Self {
 806         unsafe { Rc::copy_from_slice(v) }
 807     }
 808 }
 809
 810 #[stable(feature = "rust1", since = "1.0.0")]
 811 impl<T: ?Sized> Deref for Rc<T> {
 812     type Target = T;
 813
 814     #[inline(always)]
 815     fn deref(&self) -> &T {
 816         &self.inner().value
 817     }
 818 }
 819
 820 #[unstable(feature = "receiver_trait", issue = "0")]
 821 impl<T: ?Sized> Receiver for Rc<T> {}
 822
 823 #[stable(feature = "rust1", since = "1.0.0")]
 824 unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
 825     /// Drops the `Rc`.
 826     ///
 827     /// This will decrement the strong reference count. If the strong reference
 828     /// count reaches zero then the only other references (if any) are
 829     /// [`Weak`], so we `drop` the inner value.
 830     ///
 831     /// # Examples
 832     ///
 833     /// ```
 834     /// use std::rc::Rc;
 835     ///
 836     /// struct Foo;
 837     ///
 838     /// impl Drop for Foo {
 839     ///     fn drop(&mut self) {
 840     ///         println!("dropped!");
 841     ///     }
 842     /// }
 843     ///
 844     /// let foo  = Rc::new(Foo);
 845     /// let foo2 = Rc::clone(&foo);
 846     ///
 847     /// drop(foo);    // Doesn't print anything
 848     /// drop(foo2);   // Prints "dropped!"
 849     /// ```
 850     ///
 851     /// [`Weak`]: ../../std/rc/struct.Weak.html
 852     fn drop(&mut self) {
 853         unsafe {
 854             self.dec_strong();
 855             if self.strong() == 0 {
 856                 // destroy the contained object
 857                 ptr::drop_in_place(self.ptr.as_mut());
 858
 859                 // remove the implicit "strong weak" pointer now that we've
 860                 // destroyed the contents.
 861                 self.dec_weak();
 862
 863                 if self.weak() == 0 {
 864                     Global.dealloc(self.ptr.cast(), Layout::for_value(self.ptr.as_ref()));
 865                 }
 866             }
 867         }
 868     }
 869 }
 870
 871 #[stable(feature = "rust1", since = "1.0.0")]
 872 impl<T: ?Sized> Clone for Rc<T> {
 873     /// Makes a clone of the `Rc` pointer.
 874     ///
 875     /// This creates another pointer to the same inner value, increasing the
 876     /// strong reference count.
 877     ///
 878     /// # Examples
 879     ///
 880     /// ```
 881     /// use std::rc::Rc;
 882     ///
 883     /// let five = Rc::new(5);
 884     ///
 885     /// let _ = Rc::clone(&five);
 886     /// ```
 887     #[inline]
 888     fn clone(&self) -> Rc<T> {
 889         self.inc_strong();
 890         Rc { ptr: self.ptr, phantom: PhantomData }
 891     }
 892 }
 893
 894 #[stable(feature = "rust1", since = "1.0.0")]
 895 impl<T: Default> Default for Rc<T> {
 896     /// Creates a new `Rc<T>`, with the `Default` value for `T`.
 897     ///
 898     /// # Examples
 899     ///
 900     /// ```
 901     /// use std::rc::Rc;
 902     ///
 903     /// let x: Rc<i32> = Default::default();
 904     /// assert_eq!(*x, 0);
 905     /// ```
 906     #[inline]
 907     fn default() -> Rc<T> {
 908         Rc::new(Default::default())
 909     }
 910 }
 911
 912 #[stable(feature = "rust1", since = "1.0.0")]
 913 trait RcEqIdent<T: ?Sized + PartialEq> {
 914     fn eq(&self, other: &Rc<T>) -> bool;
 915     fn ne(&self, other: &Rc<T>) -> bool;
 916 }
 917
 918 #[stable(feature = "rust1", since = "1.0.0")]
 919 impl<T: ?Sized + PartialEq> RcEqIdent<T> for Rc<T> {
 920     #[inline]
 921     default fn eq(&self, other: &Rc<T>) -> bool {
 922         **self == **other
 923     }
 924
 925     #[inline]
 926     default fn ne(&self, other: &Rc<T>) -> bool {
 927         **self != **other
 928     }
 929 }
 930
 931 /// We're doing this specialization here, and not as a more general optimization on `&T`, because it
 932 /// would otherwise add a cost to all equality checks on refs. We assume that `Rc`s are used to
 933 /// store large values, that are slow to clone, but also heavy to check for equality, causing this
 934 /// cost to pay off more easily. It's also more likely to have two `Rc` clones, that point to
 935 /// the same value, than two `&T`s.
 936 #[stable(feature = "rust1", since = "1.0.0")]
 937 impl<T: ?Sized + Eq> RcEqIdent<T> for Rc<T> {
 938     #[inline]
 939     fn eq(&self, other: &Rc<T>) -> bool {
 940         Rc::ptr_eq(self, other) || **self == **other
 941     }
 942
 943     #[inline]
 944     fn ne(&self, other: &Rc<T>) -> bool {
 945         !Rc::ptr_eq(self, other) && **self != **other
 946     }
 947 }
 948
 949 #[stable(feature = "rust1", since = "1.0.0")]
 950 impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
 951     /// Equality for two `Rc`s.
 952     ///
 953     /// Two `Rc`s are equal if their inner values are equal.
 954     ///
 955     /// If `T` also implements `Eq`, two `Rc`s that point to the same value are
 956     /// always equal.
 957     ///
 958     /// # Examples
 959     ///
 960     /// ```
 961     /// use std::rc::Rc;
 962     ///
 963     /// let five = Rc::new(5);
 964     ///
 965     /// assert!(five == Rc::new(5));
 966     /// ```
 967     #[inline]
 968     fn eq(&self, other: &Rc<T>) -> bool {
 969         RcEqIdent::eq(self, other)
 970     }
 971
 972     /// Inequality for two `Rc`s.
 973     ///
 974     /// Two `Rc`s are unequal if their inner values are unequal.
 975     ///
 976     /// If `T` also implements `Eq`, two `Rc`s that point to the same value are
 977     /// never unequal.
 978     ///
 979     /// # Examples
 980     ///
 981     /// ```
 982     /// use std::rc::Rc;
 983     ///
 984     /// let five = Rc::new(5);
 985     ///
 986     /// assert!(five != Rc::new(6));
 987     /// ```
 988     #[inline]
 989     fn ne(&self, other: &Rc<T>) -> bool {
 990         RcEqIdent::ne(self, other)
 991     }
 992 }
 993
 994 #[stable(feature = "rust1", since = "1.0.0")]
 995 impl<T: ?Sized + Eq> Eq for Rc<T> {}
 996
 997 #[stable(feature = "rust1", since = "1.0.0")]
 998 impl<T: ?Sized + PartialOrd> PartialOrd for Rc<T> {
 999     /// Partial comparison for two `Rc`s.
1000     ///
1001     /// The two are compared by calling `partial_cmp()` on their inner values.
1002     ///
1003     /// # Examples
1004     ///
1005     /// ```
1006     /// use std::rc::Rc;
1007     /// use std::cmp::Ordering;
1008     ///
1009     /// let five = Rc::new(5);
1010     ///
1011     /// assert_eq!(Some(Ordering::Less), five.partial_cmp(&Rc::new(6)));
1012     /// ```
1013     #[inline(always)]
1014     fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
1015         (**self).partial_cmp(&**other)
1016     }
1017
1018     /// Less-than comparison for two `Rc`s.
1019     ///
1020     /// The two are compared by calling `<` on their inner values.
1021     ///
1022     /// # Examples
1023     ///
1024     /// ```
1025     /// use std::rc::Rc;
1026     ///
1027     /// let five = Rc::new(5);
1028     ///
1029     /// assert!(five < Rc::new(6));
1030     /// ```
1031     #[inline(always)]
1032     fn lt(&self, other: &Rc<T>) -> bool {
1033         **self < **other
1034     }
1035
1036     /// 'Less than or equal to' comparison for two `Rc`s.
1037     ///
1038     /// The two are compared by calling `<=` on their inner values.
1039     ///
1040     /// # Examples
1041     ///
1042     /// ```
1043     /// use std::rc::Rc;
1044     ///
1045     /// let five = Rc::new(5);
1046     ///
1047     /// assert!(five <= Rc::new(5));
1048     /// ```
1049     #[inline(always)]
1050     fn le(&self, other: &Rc<T>) -> bool {
1051         **self <= **other
1052     }
1053
1054     /// Greater-than comparison for two `Rc`s.
1055     ///
1056     /// The two are compared by calling `>` on their inner values.
1057     ///
1058     /// # Examples
1059     ///
1060     /// ```
1061     /// use std::rc::Rc;
1062     ///
1063     /// let five = Rc::new(5);
1064     ///
1065     /// assert!(five > Rc::new(4));
1066     /// ```
1067     #[inline(always)]
1068     fn gt(&self, other: &Rc<T>) -> bool {
1069         **self > **other
1070     }
1071
1072     /// 'Greater than or equal to' comparison for two `Rc`s.
1073     ///
1074     /// The two are compared by calling `>=` on their inner values.
1075     ///
1076     /// # Examples
1077     ///
1078     /// ```
1079     /// use std::rc::Rc;
1080     ///
1081     /// let five = Rc::new(5);
1082     ///
1083     /// assert!(five >= Rc::new(5));
1084     /// ```
1085     #[inline(always)]
1086     fn ge(&self, other: &Rc<T>) -> bool {
1087         **self >= **other
1088     }
1089 }
1090
1091 #[stable(feature = "rust1", since = "1.0.0")]
1092 impl<T: ?Sized + Ord> Ord for Rc<T> {
1093     /// Comparison for two `Rc`s.
1094     ///
1095     /// The two are compared by calling `cmp()` on their inner values.
1096     ///
1097     /// # Examples
1098     ///
1099     /// ```
1100     /// use std::rc::Rc;
1101     /// use std::cmp::Ordering;
1102     ///
1103     /// let five = Rc::new(5);
1104     ///
1105     /// assert_eq!(Ordering::Less, five.cmp(&Rc::new(6)));
1106     /// ```
1107     #[inline]
1108     fn cmp(&self, other: &Rc<T>) -> Ordering {
1109         (**self).cmp(&**other)
1110     }
1111 }
1112
1113 #[stable(feature = "rust1", since = "1.0.0")]
1114 impl<T: ?Sized + Hash> Hash for Rc<T> {
1115     fn hash<H: Hasher>(&self, state: &mut H) {
1116         (**self).hash(state);
1117     }
1118 }
1119
1120 #[stable(feature = "rust1", since = "1.0.0")]
1121 impl<T: ?Sized + fmt::Display> fmt::Display for Rc<T> {
1122     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1123         fmt::Display::fmt(&**self, f)
1124     }
1125 }
1126
1127 #[stable(feature = "rust1", since = "1.0.0")]
1128 impl<T: ?Sized + fmt::Debug> fmt::Debug for Rc<T> {
1129     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1130         fmt::Debug::fmt(&**self, f)
1131     }
1132 }
1133
1134 #[stable(feature = "rust1", since = "1.0.0")]
1135 impl<T: ?Sized> fmt::Pointer for Rc<T> {
1136     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1137         fmt::Pointer::fmt(&(&**self as *const T), f)
1138     }
1139 }
1140
1141 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
1142 impl<T> From<T> for Rc<T> {
1143     fn from(t: T) -> Self {
1144         Rc::new(t)
1145     }
1146 }
1147
1148 #[stable(feature = "shared_from_slice", since = "1.21.0")]
1149 impl<T: Clone> From<&[T]> for Rc<[T]> {
1150     #[inline]
1151     fn from(v: &[T]) -> Rc<[T]> {
1152         <Self as RcFromSlice<T>>::from_slice(v)
1153     }
1154 }
1155
1156 #[stable(feature = "shared_from_slice", since = "1.21.0")]
1157 impl From<&str> for Rc<str> {
1158     #[inline]
1159     fn from(v: &str) -> Rc<str> {
1160         let rc = Rc::<[u8]>::from(v.as_bytes());
1161         unsafe { Rc::from_raw(Rc::into_raw(rc) as *const str) }
1162     }
1163 }
1164
1165 #[stable(feature = "shared_from_slice", since = "1.21.0")]
1166 impl From<String> for Rc<str> {
1167     #[inline]
1168     fn from(v: String) -> Rc<str> {
1169         Rc::from(&v[..])
1170     }
1171 }
1172
1173 #[stable(feature = "shared_from_slice", since = "1.21.0")]
1174 impl<T: ?Sized> From<Box<T>> for Rc<T> {
1175     #[inline]
1176     fn from(v: Box<T>) -> Rc<T> {
1177         Rc::from_box(v)
1178     }
1179 }
1180
1181 #[stable(feature = "shared_from_slice", since = "1.21.0")]
1182 impl<T> From<Vec<T>> for Rc<[T]> {
1183     #[inline]
1184     fn from(mut v: Vec<T>) -> Rc<[T]> {
1185         unsafe {
1186             let rc = Rc::copy_from_slice(&v);
1187
1188             // Allow the Vec to free its memory, but not destroy its contents
1189             v.set_len(0);
1190
1191             rc
1192         }
1193     }
1194 }
1195
1196 /// `Weak` is a version of [`Rc`] that holds a non-owning reference to the
1197 /// managed value. The value is accessed by calling [`upgrade`] on the `Weak`
1198 /// pointer, which returns an [`Option`]`<`[`Rc`]`<T>>`.
1199 ///
1200 /// Since a `Weak` reference does not count towards ownership, it will not
1201 /// prevent the inner value from being dropped, and `Weak` itself makes no
1202 /// guarantees about the value still being present and may return [`None`]
1203 /// when [`upgrade`]d.
1204 ///
1205 /// A `Weak` pointer is useful for keeping a temporary reference to the value
1206 /// within [`Rc`] without extending its lifetime. It is also used to prevent
1207 /// circular references between [`Rc`] pointers, since mutual owning references
1208 /// would never allow either [`Rc`] to be dropped. For example, a tree could
1209 /// have strong [`Rc`] pointers from parent nodes to children, and `Weak`
1210 /// pointers from children back to their parents.
1211 ///
1212 /// The typical way to obtain a `Weak` pointer is to call [`Rc::downgrade`].
1213 ///
1214 /// [`Rc`]: struct.Rc.html
1215 /// [`Rc::downgrade`]: struct.Rc.html#method.downgrade
1216 /// [`upgrade`]: struct.Weak.html#method.upgrade
1217 /// [`Option`]: ../../std/option/enum.Option.html
1218 /// [`None`]: ../../std/option/enum.Option.html#variant.None
1219 #[stable(feature = "rc_weak", since = "1.4.0")]
1220 pub struct Weak<T: ?Sized> {
1221     // This is a `NonNull` to allow optimizing the size of this type in enums,
1222     // but it is not necessarily a valid pointer.
1223     // `Weak::new` sets this to `usize::MAX` so that it doesn’t need
1224     // to allocate space on the heap.  That's not a value a real pointer
1225     // will ever have because RcBox has alignment at least 2.
1226     ptr: NonNull<RcBox<T>>,
1227 }
1228
1229 #[stable(feature = "rc_weak", since = "1.4.0")]
1230 impl<T: ?Sized> !marker::Send for Weak<T> {}
1231 #[stable(feature = "rc_weak", since = "1.4.0")]
1232 impl<T: ?Sized> !marker::Sync for Weak<T> {}
1233
1234 #[unstable(feature = "coerce_unsized", issue = "27732")]
1235 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
1236
1237 #[unstable(feature = "dispatch_from_dyn", issue = "0")]
1238 impl<T: ?Sized + Unsize<U>, U: ?Sized> DispatchFromDyn<Weak<U>> for Weak<T> {}
1239
1240 impl<T> Weak<T> {
1241     /// Constructs a new `Weak<T>`, without allocating any memory.
1242     /// Calling [`upgrade`] on the return value always gives [`None`].
1243     ///
1244     /// [`upgrade`]: #method.upgrade
1245     /// [`None`]: ../../std/option/enum.Option.html
1246     ///
1247     /// # Examples
1248     ///
1249     /// ```
1250     /// use std::rc::Weak;
1251     ///
1252     /// let empty: Weak<i64> = Weak::new();
1253     /// assert!(empty.upgrade().is_none());
1254     /// ```
1255     #[stable(feature = "downgraded_weak", since = "1.10.0")]
1256     pub fn new() -> Weak<T> {
1257         Weak {
1258             ptr: NonNull::new(usize::MAX as *mut RcBox<T>).expect("MAX is not 0"),
1259         }
1260     }
1261
1262     /// Returns a raw pointer to the object `T` pointed to by this `Weak<T>`.
1263     ///
1264     /// It is up to the caller to ensure that the object is still alive when accessing it through
1265     /// the pointer.
1266     ///
1267     /// The pointer may be [`null`] or be dangling in case the object has already been destroyed.
1268     ///
1269     /// # Examples
1270     ///
1271     /// ```
1272     /// #![feature(weak_into_raw)]
1273     ///
1274     /// use std::rc::{Rc, Weak};
1275     /// use std::ptr;
1276     ///
1277     /// let strong = Rc::new(42);
1278     /// let weak = Rc::downgrade(&strong);
1279     /// // Both point to the same object
1280     /// assert!(ptr::eq(&*strong, Weak::as_raw(&weak)));
1281     /// // The strong here keeps it alive, so we can still access the object.
1282     /// assert_eq!(42, unsafe { *Weak::as_raw(&weak) });
1283     ///
1284     /// drop(strong);
1285     /// // But not any more. We can do Weak::as_raw(&weak), but accessing the pointer would lead to
1286     /// // undefined behaviour.
1287     /// // assert_eq!(42, unsafe { *Weak::as_raw(&weak) });
1288     /// ```
1289     ///
1290     /// [`null`]: ../../std/ptr/fn.null.html
1291     #[unstable(feature = "weak_into_raw", issue = "60728")]
1292     pub fn as_raw(this: &Self) -> *const T {
1293         match this.inner() {
1294             None => ptr::null(),
1295             Some(inner) => {
1296                 let offset = data_offset_sized::<T>();
1297                 let ptr = inner as *const RcBox<T>;
1298                 // Note: while the pointer we create may already point to dropped value, the
1299                 // allocation still lives (it must hold the weak point as long as we are alive).
1300                 // Therefore, the offset is OK to do, it won't get out of the allocation.
1301                 let ptr = unsafe { (ptr as *const u8).offset(offset) };
1302                 ptr as *const T
1303             }
1304         }
1305     }
1306
1307     /// Consumes the `Weak<T>` and turns it into a raw pointer.
1308     ///
1309     /// This converts the weak pointer into a raw pointer, preserving the original weak count. It
1310     /// can be turned back into the `Weak<T>` with [`from_raw`].
1311     ///
1312     /// The same restrictions of accessing the target of the pointer as with
1313     /// [`as_raw`] apply.
1314     ///
1315     /// # Examples
1316     ///
1317     /// ```
1318     /// #![feature(weak_into_raw)]
1319     ///
1320     /// use std::rc::{Rc, Weak};
1321     ///
1322     /// let strong = Rc::new(42);
1323     /// let weak = Rc::downgrade(&strong);
1324     /// let raw = Weak::into_raw(weak);
1325     ///
1326     /// assert_eq!(1, Rc::weak_count(&strong));
1327     /// assert_eq!(42, unsafe { *raw });
1328     ///
1329     /// drop(unsafe { Weak::from_raw(raw) });
1330     /// assert_eq!(0, Rc::weak_count(&strong));
1331     /// ```
1332     ///
1333     /// [`from_raw`]: struct.Weak.html#method.from_raw
1334     /// [`as_raw`]: struct.Weak.html#method.as_raw
1335     #[unstable(feature = "weak_into_raw", issue = "60728")]
1336     pub fn into_raw(this: Self) -> *const T {
1337         let result = Self::as_raw(&this);
1338         mem::forget(this);
1339         result
1340     }
1341
1342     /// Converts a raw pointer previously created by [`into_raw`] back into `Weak<T>`.
1343     ///
1344     /// This can be used to safely get a strong reference (by calling [`upgrade`]
1345     /// later) or to deallocate the weak count by dropping the `Weak<T>`.
1346     ///
1347     /// It takes ownership of one weak count. In case a [`null`] is passed, a dangling [`Weak`] is
1348     /// returned.
1349     ///
1350     /// # Safety
1351     ///
1352     /// The pointer must represent one valid weak count. In other words, it must point to `T` which
1353     /// is or *was* managed by an [`Rc`] and the weak count of that [`Rc`] must not have reached
1354     /// 0. It is allowed for the strong count to be 0.
1355     ///
1356     /// # Examples
1357     ///
1358     /// ```
1359     /// #![feature(weak_into_raw)]
1360     ///
1361     /// use std::rc::{Rc, Weak};
1362     ///
1363     /// let strong = Rc::new(42);
1364     ///
1365     /// let raw_1 = Weak::into_raw(Rc::downgrade(&strong));
1366     /// let raw_2 = Weak::into_raw(Rc::downgrade(&strong));
1367     ///
1368     /// assert_eq!(2, Rc::weak_count(&strong));
1369     ///
1370     /// assert_eq!(42, *Weak::upgrade(&unsafe { Weak::from_raw(raw_1) }).unwrap());
1371     /// assert_eq!(1, Rc::weak_count(&strong));
1372     ///
1373     /// drop(strong);
1374     ///
1375     /// // Decrement the last weak count.
1376     /// assert!(Weak::upgrade(&unsafe { Weak::from_raw(raw_2) }).is_none());
1377     /// ```
1378     ///
1379     /// [`null`]: ../../std/ptr/fn.null.html
1380     /// [`into_raw`]: struct.Weak.html#method.into_raw
1381     /// [`upgrade`]: struct.Weak.html#method.upgrade
1382     /// [`Rc`]: struct.Rc.html
1383     /// [`Weak`]: struct.Weak.html
1384     #[unstable(feature = "weak_into_raw", issue = "60728")]
1385     pub unsafe fn from_raw(ptr: *const T) -> Self {
1386         if ptr.is_null() {
1387             Self::new()
1388         } else {
1389             // See Rc::from_raw for details
1390             let offset = data_offset(ptr);
1391             let fake_ptr = ptr as *mut RcBox<T>;
1392             let ptr = set_data_ptr(fake_ptr, (ptr as *mut u8).offset(-offset));
1393             Weak {
1394                 ptr: NonNull::new(ptr).expect("Invalid pointer passed to from_raw"),
1395             }
1396         }
1397     }
1398 }
1399
1400 pub(crate) fn is_dangling<T: ?Sized>(ptr: NonNull<T>) -> bool {
1401     let address = ptr.as_ptr() as *mut () as usize;
1402     address == usize::MAX
1403 }
1404
1405 impl<T: ?Sized> Weak<T> {
1406     /// Attempts to upgrade the `Weak` pointer to an [`Rc`], extending
1407     /// the lifetime of the value if successful.
1408     ///
1409     /// Returns [`None`] if the value has since been dropped.
1410     ///
1411     /// [`Rc`]: struct.Rc.html
1412     /// [`None`]: ../../std/option/enum.Option.html
1413     ///
1414     /// # Examples
1415     ///
1416     /// ```
1417     /// use std::rc::Rc;
1418     ///
1419     /// let five = Rc::new(5);
1420     ///
1421     /// let weak_five = Rc::downgrade(&five);
1422     ///
1423     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
1424     /// assert!(strong_five.is_some());
1425     ///
1426     /// // Destroy all strong pointers.
1427     /// drop(strong_five);
1428     /// drop(five);
1429     ///
1430     /// assert!(weak_five.upgrade().is_none());
1431     /// ```
1432     #[stable(feature = "rc_weak", since = "1.4.0")]
1433     pub fn upgrade(&self) -> Option<Rc<T>> {
1434         let inner = self.inner()?;
1435         if inner.strong() == 0 {
1436             None
1437         } else {
1438             inner.inc_strong();
1439             Some(Rc { ptr: self.ptr, phantom: PhantomData })
1440         }
1441     }
1442
1443     /// Gets the number of strong (`Rc`) pointers pointing to this value.
1444     ///
1445     /// If `self` was created using [`Weak::new`], this will return 0.
1446     ///
1447     /// [`Weak::new`]: #method.new
1448     #[unstable(feature = "weak_counts", issue = "57977")]
1449     pub fn strong_count(&self) -> usize {
1450         if let Some(inner) = self.inner() {
1451             inner.strong()
1452         } else {
1453             0
1454         }
1455     }
1456
1457     /// Gets the number of `Weak` pointers pointing to this value.
1458     ///
1459     /// If `self` was created using [`Weak::new`], this will return `None`. If
1460     /// not, the returned value is at least 1, since `self` still points to the
1461     /// value.
1462     ///
1463     /// [`Weak::new`]: #method.new
1464     #[unstable(feature = "weak_counts", issue = "57977")]
1465     pub fn weak_count(&self) -> Option<usize> {
1466         self.inner().map(|inner| {
1467             if inner.strong() > 0 {
1468                 inner.weak() - 1  // subtract the implicit weak ptr
1469             } else {
1470                 inner.weak()
1471             }
1472         })
1473     }
1474
1475     /// Returns `None` when the pointer is dangling and there is no allocated `RcBox`
1476     /// (i.e., when this `Weak` was created by `Weak::new`).
1477     #[inline]
1478     fn inner(&self) -> Option<&RcBox<T>> {
1479         if is_dangling(self.ptr) {
1480             None
1481         } else {
1482             Some(unsafe { self.ptr.as_ref() })
1483         }
1484     }
1485
1486     /// Returns `true` if the two `Weak`s point to the same value (not just values
1487     /// that compare as equal).
1488     ///
1489     /// # Notes
1490     ///
1491     /// Since this compares pointers it means that `Weak::new()` will equal each
1492     /// other, even though they don't point to any value.
1493     ///
1494     /// # Examples
1495     ///
1496     /// ```
1497     /// #![feature(weak_ptr_eq)]
1498     /// use std::rc::{Rc, Weak};
1499     ///
1500     /// let first_rc = Rc::new(5);
1501     /// let first = Rc::downgrade(&first_rc);
1502     /// let second = Rc::downgrade(&first_rc);
1503     ///
1504     /// assert!(Weak::ptr_eq(&first, &second));
1505     ///
1506     /// let third_rc = Rc::new(5);
1507     /// let third = Rc::downgrade(&third_rc);
1508     ///
1509     /// assert!(!Weak::ptr_eq(&first, &third));
1510     /// ```
1511     ///
1512     /// Comparing `Weak::new`.
1513     ///
1514     /// ```
1515     /// #![feature(weak_ptr_eq)]
1516     /// use std::rc::{Rc, Weak};
1517     ///
1518     /// let first = Weak::new();
1519     /// let second = Weak::new();
1520     /// assert!(Weak::ptr_eq(&first, &second));
1521     ///
1522     /// let third_rc = Rc::new(());
1523     /// let third = Rc::downgrade(&third_rc);
1524     /// assert!(!Weak::ptr_eq(&first, &third));
1525     /// ```
1526     #[inline]
1527     #[unstable(feature = "weak_ptr_eq", issue = "55981")]
1528     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
1529         this.ptr.as_ptr() == other.ptr.as_ptr()
1530     }
1531 }
1532
1533 #[stable(feature = "rc_weak", since = "1.4.0")]
1534 impl<T: ?Sized> Drop for Weak<T> {
1535     /// Drops the `Weak` pointer.
1536     ///
1537     /// # Examples
1538     ///
1539     /// ```
1540     /// use std::rc::{Rc, Weak};
1541     ///
1542     /// struct Foo;
1543     ///
1544     /// impl Drop for Foo {
1545     ///     fn drop(&mut self) {
1546     ///         println!("dropped!");
1547     ///     }
1548     /// }
1549     ///
1550     /// let foo = Rc::new(Foo);
1551     /// let weak_foo = Rc::downgrade(&foo);
1552     /// let other_weak_foo = Weak::clone(&weak_foo);
1553     ///
1554     /// drop(weak_foo);   // Doesn't print anything
1555     /// drop(foo);        // Prints "dropped!"
1556     ///
1557     /// assert!(other_weak_foo.upgrade().is_none());
1558     /// ```
1559     fn drop(&mut self) {
1560         if let Some(inner) = self.inner() {
1561             inner.dec_weak();
1562             // the weak count starts at 1, and will only go to zero if all
1563             // the strong pointers have disappeared.
1564             if inner.weak() == 0 {
1565                 unsafe {
1566                     Global.dealloc(self.ptr.cast(), Layout::for_value(self.ptr.as_ref()));
1567                 }
1568             }
1569         }
1570     }
1571 }
1572
1573 #[stable(feature = "rc_weak", since = "1.4.0")]
1574 impl<T: ?Sized> Clone for Weak<T> {
1575     /// Makes a clone of the `Weak` pointer that points to the same value.
1576     ///
1577     /// # Examples
1578     ///
1579     /// ```
1580     /// use std::rc::{Rc, Weak};
1581     ///
1582     /// let weak_five = Rc::downgrade(&Rc::new(5));
1583     ///
1584     /// let _ = Weak::clone(&weak_five);
1585     /// ```
1586     #[inline]
1587     fn clone(&self) -> Weak<T> {
1588         if let Some(inner) = self.inner() {
1589             inner.inc_weak()
1590         }
1591         Weak { ptr: self.ptr }
1592     }
1593 }
1594
1595 #[stable(feature = "rc_weak", since = "1.4.0")]
1596 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
1597     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1598         write!(f, "(Weak)")
1599     }
1600 }
1601
1602 #[stable(feature = "downgraded_weak", since = "1.10.0")]
1603 impl<T> Default for Weak<T> {
1604     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
1605     /// it. Calling [`upgrade`] on the return value always gives [`None`].
1606     ///
1607     /// [`None`]: ../../std/option/enum.Option.html
1608     /// [`upgrade`]: ../../std/rc/struct.Weak.html#method.upgrade
1609     ///
1610     /// # Examples
1611     ///
1612     /// ```
1613     /// use std::rc::Weak;
1614     ///
1615     /// let empty: Weak<i64> = Default::default();
1616     /// assert!(empty.upgrade().is_none());
1617     /// ```
1618     fn default() -> Weak<T> {
1619         Weak::new()
1620     }
1621 }
1622
1623 // NOTE: We checked_add here to deal with mem::forget safely. In particular
1624 // if you mem::forget Rcs (or Weaks), the ref-count can overflow, and then
1625 // you can free the allocation while outstanding Rcs (or Weaks) exist.
1626 // We abort because this is such a degenerate scenario that we don't care about
1627 // what happens -- no real program should ever experience this.
1628 //
1629 // This should have negligible overhead since you don't actually need to
1630 // clone these much in Rust thanks to ownership and move-semantics.
1631
1632 #[doc(hidden)]
1633 trait RcBoxPtr<T: ?Sized> {
1634     fn inner(&self) -> &RcBox<T>;
1635
1636     #[inline]
1637     fn strong(&self) -> usize {
1638         self.inner().strong.get()
1639     }
1640
1641     #[inline]
1642     fn inc_strong(&self) {
1643         // We want to abort on overflow instead of dropping the value.
1644         // The reference count will never be zero when this is called;
1645         // nevertheless, we insert an abort here to hint LLVM at
1646         // an otherwise missed optimization.
1647         if self.strong() == 0 || self.strong() == usize::max_value() {
1648             unsafe { abort(); }
1649         }
1650         self.inner().strong.set(self.strong() + 1);
1651     }
1652
1653     #[inline]
1654     fn dec_strong(&self) {
1655         self.inner().strong.set(self.strong() - 1);
1656     }
1657
1658     #[inline]
1659     fn weak(&self) -> usize {
1660         self.inner().weak.get()
1661     }
1662
1663     #[inline]
1664     fn inc_weak(&self) {
1665         // We want to abort on overflow instead of dropping the value.
1666         // The reference count will never be zero when this is called;
1667         // nevertheless, we insert an abort here to hint LLVM at
1668         // an otherwise missed optimization.
1669         if self.weak() == 0 || self.weak() == usize::max_value() {
1670             unsafe { abort(); }
1671         }
1672         self.inner().weak.set(self.weak() + 1);
1673     }
1674
1675     #[inline]
1676     fn dec_weak(&self) {
1677         self.inner().weak.set(self.weak() - 1);
1678     }
1679 }
1680
1681 impl<T: ?Sized> RcBoxPtr<T> for Rc<T> {
1682     #[inline(always)]
1683     fn inner(&self) -> &RcBox<T> {
1684         unsafe {
1685             self.ptr.as_ref()
1686         }
1687     }
1688 }
1689
1690 impl<T: ?Sized> RcBoxPtr<T> for RcBox<T> {
1691     #[inline(always)]
1692     fn inner(&self) -> &RcBox<T> {
1693         self
1694     }
1695 }
1696
1697 #[cfg(test)]
1698 mod tests {
1699     use super::{Rc, Weak};
1700     use std::boxed::Box;
1701     use std::cell::RefCell;
1702     use std::option::Option::{self, None, Some};
1703     use std::result::Result::{Err, Ok};
1704     use std::mem::drop;
1705     use std::clone::Clone;
1706     use std::convert::From;
1707
1708     #[test]
1709     fn test_clone() {
1710         let x = Rc::new(RefCell::new(5));
1711         let y = x.clone();
1712         *x.borrow_mut() = 20;
1713         assert_eq!(*y.borrow(), 20);
1714     }
1715
1716     #[test]
1717     fn test_simple() {
1718         let x = Rc::new(5);
1719         assert_eq!(*x, 5);
1720     }
1721
1722     #[test]
1723     fn test_simple_clone() {
1724         let x = Rc::new(5);
1725         let y = x.clone();
1726         assert_eq!(*x, 5);
1727         assert_eq!(*y, 5);
1728     }
1729
1730     #[test]
1731     fn test_destructor() {
1732         let x: Rc<Box<_>> = Rc::new(box 5);
1733         assert_eq!(**x, 5);
1734     }
1735
1736     #[test]
1737     fn test_live() {
1738         let x = Rc::new(5);
1739         let y = Rc::downgrade(&x);
1740         assert!(y.upgrade().is_some());
1741     }
1742
1743     #[test]
1744     fn test_dead() {
1745         let x = Rc::new(5);
1746         let y = Rc::downgrade(&x);
1747         drop(x);
1748         assert!(y.upgrade().is_none());
1749     }
1750
1751     #[test]
1752     fn weak_self_cyclic() {
1753         struct Cycle {
1754             x: RefCell<Option<Weak<Cycle>>>,
1755         }
1756
1757         let a = Rc::new(Cycle { x: RefCell::new(None) });
1758         let b = Rc::downgrade(&a.clone());
1759         *a.x.borrow_mut() = Some(b);
1760
1761         // hopefully we don't double-free (or leak)...
1762     }
1763
1764     #[test]
1765     fn is_unique() {
1766         let x = Rc::new(3);
1767         assert!(Rc::is_unique(&x));
1768         let y = x.clone();
1769         assert!(!Rc::is_unique(&x));
1770         drop(y);
1771         assert!(Rc::is_unique(&x));
1772         let w = Rc::downgrade(&x);
1773         assert!(!Rc::is_unique(&x));
1774         drop(w);
1775         assert!(Rc::is_unique(&x));
1776     }
1777
1778     #[test]
1779     fn test_strong_count() {
1780         let a = Rc::new(0);
1781         assert!(Rc::strong_count(&a) == 1);
1782         let w = Rc::downgrade(&a);
1783         assert!(Rc::strong_count(&a) == 1);
1784         let b = w.upgrade().expect("upgrade of live rc failed");
1785         assert!(Rc::strong_count(&b) == 2);
1786         assert!(Rc::strong_count(&a) == 2);
1787         drop(w);
1788         drop(a);
1789         assert!(Rc::strong_count(&b) == 1);
1790         let c = b.clone();
1791         assert!(Rc::strong_count(&b) == 2);
1792         assert!(Rc::strong_count(&c) == 2);
1793     }
1794
1795     #[test]
1796     fn test_weak_count() {
1797         let a = Rc::new(0);
1798         assert!(Rc::strong_count(&a) == 1);
1799         assert!(Rc::weak_count(&a) == 0);
1800         let w = Rc::downgrade(&a);
1801         assert!(Rc::strong_count(&a) == 1);
1802         assert!(Rc::weak_count(&a) == 1);
1803         drop(w);
1804         assert!(Rc::strong_count(&a) == 1);
1805         assert!(Rc::weak_count(&a) == 0);
1806         let c = a.clone();
1807         assert!(Rc::strong_count(&a) == 2);
1808         assert!(Rc::weak_count(&a) == 0);
1809         drop(c);
1810     }
1811
1812     #[test]
1813     fn weak_counts() {
1814         assert_eq!(Weak::weak_count(&Weak::<u64>::new()), None);
1815         assert_eq!(Weak::strong_count(&Weak::<u64>::new()), 0);
1816
1817         let a = Rc::new(0);
1818         let w = Rc::downgrade(&a);
1819         assert_eq!(Weak::strong_count(&w), 1);
1820         assert_eq!(Weak::weak_count(&w), Some(1));
1821         let w2 = w.clone();
1822         assert_eq!(Weak::strong_count(&w), 1);
1823         assert_eq!(Weak::weak_count(&w), Some(2));
1824         assert_eq!(Weak::strong_count(&w2), 1);
1825         assert_eq!(Weak::weak_count(&w2), Some(2));
1826         drop(w);
1827         assert_eq!(Weak::strong_count(&w2), 1);
1828         assert_eq!(Weak::weak_count(&w2), Some(1));
1829         let a2 = a.clone();
1830         assert_eq!(Weak::strong_count(&w2), 2);
1831         assert_eq!(Weak::weak_count(&w2), Some(1));
1832         drop(a2);
1833         drop(a);
1834         assert_eq!(Weak::strong_count(&w2), 0);
1835         assert_eq!(Weak::weak_count(&w2), Some(1));
1836         drop(w2);
1837     }
1838
1839     #[test]
1840     fn try_unwrap() {
1841         let x = Rc::new(3);
1842         assert_eq!(Rc::try_unwrap(x), Ok(3));
1843         let x = Rc::new(4);
1844         let _y = x.clone();
1845         assert_eq!(Rc::try_unwrap(x), Err(Rc::new(4)));
1846         let x = Rc::new(5);
1847         let _w = Rc::downgrade(&x);
1848         assert_eq!(Rc::try_unwrap(x), Ok(5));
1849     }
1850
1851     #[test]
1852     fn into_from_raw() {
1853         let x = Rc::new(box "hello");
1854         let y = x.clone();
1855
1856         let x_ptr = Rc::into_raw(x);
1857         drop(y);
1858         unsafe {
1859             assert_eq!(**x_ptr, "hello");
1860
1861             let x = Rc::from_raw(x_ptr);
1862             assert_eq!(**x, "hello");
1863
1864             assert_eq!(Rc::try_unwrap(x).map(|x| *x), Ok("hello"));
1865         }
1866     }
1867
1868     #[test]
1869     fn test_into_from_raw_unsized() {
1870         use std::fmt::Display;
1871         use std::string::ToString;
1872
1873         let rc: Rc<str> = Rc::from("foo");
1874
1875         let ptr = Rc::into_raw(rc.clone());
1876         let rc2 = unsafe { Rc::from_raw(ptr) };
1877
1878         assert_eq!(unsafe { &*ptr }, "foo");
1879         assert_eq!(rc, rc2);
1880
1881         let rc: Rc<dyn Display> = Rc::new(123);
1882
1883         let ptr = Rc::into_raw(rc.clone());
1884         let rc2 = unsafe { Rc::from_raw(ptr) };
1885
1886         assert_eq!(unsafe { &*ptr }.to_string(), "123");
1887         assert_eq!(rc2.to_string(), "123");
1888     }
1889
1890     #[test]
1891     fn get_mut() {
1892         let mut x = Rc::new(3);
1893         *Rc::get_mut(&mut x).unwrap() = 4;
1894         assert_eq!(*x, 4);
1895         let y = x.clone();
1896         assert!(Rc::get_mut(&mut x).is_none());
1897         drop(y);
1898         assert!(Rc::get_mut(&mut x).is_some());
1899         let _w = Rc::downgrade(&x);
1900         assert!(Rc::get_mut(&mut x).is_none());
1901     }
1902
1903     #[test]
1904     fn test_cowrc_clone_make_unique() {
1905         let mut cow0 = Rc::new(75);
1906         let mut cow1 = cow0.clone();
1907         let mut cow2 = cow1.clone();
1908
1909         assert!(75 == *Rc::make_mut(&mut cow0));
1910         assert!(75 == *Rc::make_mut(&mut cow1));
1911         assert!(75 == *Rc::make_mut(&mut cow2));
1912
1913         *Rc::make_mut(&mut cow0) += 1;
1914         *Rc::make_mut(&mut cow1) += 2;
1915         *Rc::make_mut(&mut cow2) += 3;
1916
1917         assert!(76 == *cow0);
1918         assert!(77 == *cow1);
1919         assert!(78 == *cow2);
1920
1921         // none should point to the same backing memory
1922         assert!(*cow0 != *cow1);
1923         assert!(*cow0 != *cow2);
1924         assert!(*cow1 != *cow2);
1925     }
1926
1927     #[test]
1928     fn test_cowrc_clone_unique2() {
1929         let mut cow0 = Rc::new(75);
1930         let cow1 = cow0.clone();
1931         let cow2 = cow1.clone();
1932
1933         assert!(75 == *cow0);
1934         assert!(75 == *cow1);
1935         assert!(75 == *cow2);
1936
1937         *Rc::make_mut(&mut cow0) += 1;
1938
1939         assert!(76 == *cow0);
1940         assert!(75 == *cow1);
1941         assert!(75 == *cow2);
1942
1943         // cow1 and cow2 should share the same contents
1944         // cow0 should have a unique reference
1945         assert!(*cow0 != *cow1);
1946         assert!(*cow0 != *cow2);
1947         assert!(*cow1 == *cow2);
1948     }
1949
1950     #[test]
1951     fn test_cowrc_clone_weak() {
1952         let mut cow0 = Rc::new(75);
1953         let cow1_weak = Rc::downgrade(&cow0);
1954
1955         assert!(75 == *cow0);
1956         assert!(75 == *cow1_weak.upgrade().unwrap());
1957
1958         *Rc::make_mut(&mut cow0) += 1;
1959
1960         assert!(76 == *cow0);
1961         assert!(cow1_weak.upgrade().is_none());
1962     }
1963
1964     #[test]
1965     fn test_show() {
1966         let foo = Rc::new(75);
1967         assert_eq!(format!("{:?}", foo), "75");
1968     }
1969
1970     #[test]
1971     fn test_unsized() {
1972         let foo: Rc<[i32]> = Rc::new([1, 2, 3]);
1973         assert_eq!(foo, foo.clone());
1974     }
1975
1976     #[test]
1977     fn test_from_owned() {
1978         let foo = 123;
1979         let foo_rc = Rc::from(foo);
1980         assert!(123 == *foo_rc);
1981     }
1982
1983     #[test]
1984     fn test_new_weak() {
1985         let foo: Weak<usize> = Weak::new();
1986         assert!(foo.upgrade().is_none());
1987     }
1988
1989     #[test]
1990     fn test_ptr_eq() {
1991         let five = Rc::new(5);
1992         let same_five = five.clone();
1993         let other_five = Rc::new(5);
1994
1995         assert!(Rc::ptr_eq(&five, &same_five));
1996         assert!(!Rc::ptr_eq(&five, &other_five));
1997     }
1998
1999     #[test]
2000     fn test_from_str() {
2001         let r: Rc<str> = Rc::from("foo");
2002
2003         assert_eq!(&r[..], "foo");
2004     }
2005
2006     #[test]
2007     fn test_copy_from_slice() {
2008         let s: &[u32] = &[1, 2, 3];
2009         let r: Rc<[u32]> = Rc::from(s);
2010
2011         assert_eq!(&r[..], [1, 2, 3]);
2012     }
2013
2014     #[test]
2015     fn test_clone_from_slice() {
2016         #[derive(Clone, Debug, Eq, PartialEq)]
2017         struct X(u32);
2018
2019         let s: &[X] = &[X(1), X(2), X(3)];
2020         let r: Rc<[X]> = Rc::from(s);
2021
2022         assert_eq!(&r[..], s);
2023     }
2024
2025     #[test]
2026     #[should_panic]
2027     fn test_clone_from_slice_panic() {
2028         use std::string::{String, ToString};
2029
2030         struct Fail(u32, String);
2031
2032         impl Clone for Fail {
2033             fn clone(&self) -> Fail {
2034                 if self.0 == 2 {
2035                     panic!();
2036                 }
2037                 Fail(self.0, self.1.clone())
2038             }
2039         }
2040
2041         let s: &[Fail] = &[
2042             Fail(0, "foo".to_string()),
2043             Fail(1, "bar".to_string()),
2044             Fail(2, "baz".to_string()),
2045         ];
2046
2047         // Should panic, but not cause memory corruption
2048         let _r: Rc<[Fail]> = Rc::from(s);
2049     }
2050
2051     #[test]
2052     fn test_from_box() {
2053         let b: Box<u32> = box 123;
2054         let r: Rc<u32> = Rc::from(b);
2055
2056         assert_eq!(*r, 123);
2057     }
2058
2059     #[test]
2060     fn test_from_box_str() {
2061         use std::string::String;
2062
2063         let s = String::from("foo").into_boxed_str();
2064         let r: Rc<str> = Rc::from(s);
2065
2066         assert_eq!(&r[..], "foo");
2067     }
2068
2069     #[test]
2070     fn test_from_box_slice() {
2071         let s = vec![1, 2, 3].into_boxed_slice();
2072         let r: Rc<[u32]> = Rc::from(s);
2073
2074         assert_eq!(&r[..], [1, 2, 3]);
2075     }
2076
2077     #[test]
2078     fn test_from_box_trait() {
2079         use std::fmt::Display;
2080         use std::string::ToString;
2081
2082         let b: Box<dyn Display> = box 123;
2083         let r: Rc<dyn Display> = Rc::from(b);
2084
2085         assert_eq!(r.to_string(), "123");
2086     }
2087
2088     #[test]
2089     fn test_from_box_trait_zero_sized() {
2090         use std::fmt::Debug;
2091
2092         let b: Box<dyn Debug> = box ();
2093         let r: Rc<dyn Debug> = Rc::from(b);
2094
2095         assert_eq!(format!("{:?}", r), "()");
2096     }
2097
2098     #[test]
2099     fn test_from_vec() {
2100         let v = vec![1, 2, 3];
2101         let r: Rc<[u32]> = Rc::from(v);
2102
2103         assert_eq!(&r[..], [1, 2, 3]);
2104     }
2105
2106     #[test]
2107     fn test_downcast() {
2108         use std::any::Any;
2109
2110         let r1: Rc<dyn Any> = Rc::new(i32::max_value());
2111         let r2: Rc<dyn Any> = Rc::new("abc");
2112
2113         assert!(r1.clone().downcast::<u32>().is_err());
2114
2115         let r1i32 = r1.downcast::<i32>();
2116         assert!(r1i32.is_ok());
2117         assert_eq!(r1i32.unwrap(), Rc::new(i32::max_value()));
2118
2119         assert!(r2.clone().downcast::<i32>().is_err());
2120
2121         let r2str = r2.downcast::<&'static str>();
2122         assert!(r2str.is_ok());
2123         assert_eq!(r2str.unwrap(), Rc::new("abc"));
2124     }
2125 }
2126
2127 #[stable(feature = "rust1", since = "1.0.0")]
2128 impl<T: ?Sized> borrow::Borrow<T> for Rc<T> {
2129     fn borrow(&self) -> &T {
2130         &**self
2131     }
2132 }
2133
2134 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
2135 impl<T: ?Sized> AsRef<T> for Rc<T> {
2136     fn as_ref(&self) -> &T {
2137         &**self
2138     }
2139 }
2140
2141 #[stable(feature = "pin", since = "1.33.0")]
2142 impl<T: ?Sized> Unpin for Rc<T> { }
2143
2144 unsafe fn data_offset<T: ?Sized>(ptr: *const T) -> isize {
2145     // Align the unsized value to the end of the RcBox.
2146     // Because it is ?Sized, it will always be the last field in memory.
2147     let align = align_of_val(&*ptr);
2148     let layout = Layout::new::<RcBox<()>>();
2149     (layout.size() + layout.padding_needed_for(align)) as isize
2150 }
2151
2152 /// Computes the offset of the data field within ArcInner.
2153 ///
2154 /// Unlike [`data_offset`], this doesn't need the pointer, but it works only on `T: Sized`.
2155 fn data_offset_sized<T>() -> isize {
2156     let align = align_of::<T>();
2157     let layout = Layout::new::<RcBox<()>>();
2158     (layout.size() + layout.padding_needed_for(align)) as isize
2159 }