src/liballoc/rc.rs

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #![allow(deprecated)]
  12
  13 //! Single-threaded reference-counting pointers.
  14 //!
  15 //! The type [`Rc<T>`][`Rc`] provides shared ownership of a value of type `T`,
  16 //! allocated in the heap. Invoking [`clone`][clone] on [`Rc`] produces a new
  17 //! pointer to the same value in the heap. When the last [`Rc`] pointer to a
  18 //! given value is destroyed, the pointed-to value is also destroyed.
  19 //!
  20 //! Shared references in Rust disallow mutation by default, and [`Rc`]
  21 //! is no exception: you cannot obtain a mutable reference to
  22 //! something inside an [`Rc`]. If you need mutability, put a [`Cell`]
  23 //! or [`RefCell`] inside the [`Rc`]; see [an example of mutability
  24 //! inside an Rc][mutability].
  25 //!
  26 //! [`Rc`] uses non-atomic reference counting. This means that overhead is very
  27 //! low, but an [`Rc`] cannot be sent between threads, and consequently [`Rc`]
  28 //! does not implement [`Send`][send]. As a result, the Rust compiler
  29 //! will check *at compile time* that you are not sending [`Rc`]s between
  30 //! threads. If you need multi-threaded, atomic reference counting, use
  31 //! [`sync::Arc`][arc].
  32 //!
  33 //! The [`downgrade`][downgrade] method can be used to create a non-owning
  34 //! [`Weak`] pointer. A [`Weak`] pointer can be [`upgrade`][upgrade]d
  35 //! to an [`Rc`], but this will return [`None`] if the value has
  36 //! already been dropped.
  37 //!
  38 //! A cycle between [`Rc`] pointers will never be deallocated. For this reason,
  39 //! [`Weak`] is used to break cycles. For example, a tree could have strong
  40 //! [`Rc`] pointers from parent nodes to children, and [`Weak`] pointers from
  41 //! children back to their parents.
  42 //!
  43 //! `Rc<T>` automatically dereferences to `T` (via the [`Deref`] trait),
  44 //! so you can call `T`'s methods on a value of type [`Rc<T>`][`Rc`]. To avoid name
  45 //! clashes with `T`'s methods, the methods of [`Rc<T>`][`Rc`] itself are [associated
  46 //! functions][assoc], called using function-like syntax:
  47 //!
  48 //! ```
  49 //! use std::rc::Rc;
  50 //! let my_rc = Rc::new(());
  51 //!
  52 //! Rc::downgrade(&my_rc);
  53 //! ```
  54 //!
  55 //! [`Weak<T>`][`Weak`] does not auto-dereference to `T`, because the value may have
  56 //! already been destroyed.
  57 //!
  58 //! # Examples
  59 //!
  60 //! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`.
  61 //! We want to have our `Gadget`s point to their `Owner`. We can't do this with
  62 //! unique ownership, because more than one gadget may belong to the same
  63 //! `Owner`. [`Rc`] allows us to share an `Owner` between multiple `Gadget`s,
  64 //! and have the `Owner` remain allocated as long as any `Gadget` points at it.
  65 //!
  66 //! ```
  67 //! use std::rc::Rc;
  68 //!
  69 //! struct Owner {
  70 //!     name: String,
  71 //!     // ...other fields
  72 //! }
  73 //!
  74 //! struct Gadget {
  75 //!     id: i32,
  76 //!     owner: Rc<Owner>,
  77 //!     // ...other fields
  78 //! }
  79 //!
  80 //! fn main() {
  81 //!     // Create a reference-counted `Owner`.
  82 //!     let gadget_owner: Rc<Owner> = Rc::new(
  83 //!         Owner {
  84 //!             name: "Gadget Man".to_string(),
  85 //!         }
  86 //!     );
  87 //!
  88 //!     // Create `Gadget`s belonging to `gadget_owner`. Cloning the `Rc<Owner>`
  89 //!     // value gives us a new pointer to the same `Owner` value, incrementing
  90 //!     // the reference count in the process.
  91 //!     let gadget1 = Gadget {
  92 //!         id: 1,
  93 //!         owner: gadget_owner.clone(),
  94 //!     };
  95 //!     let gadget2 = Gadget {
  96 //!         id: 2,
  97 //!         owner: gadget_owner.clone(),
  98 //!     };
  99 //!
 100 //!     // Dispose of our local variable `gadget_owner`.
 101 //!     drop(gadget_owner);
 102 //!
 103 //!     // Despite dropping `gadget_owner`, we're still able to print out the name
 104 //!     // of the `Owner` of the `Gadget`s. This is because we've only dropped a
 105 //!     // single `Rc<Owner>`, not the `Owner` it points to. As long as there are
 106 //!     // other `Rc<Owner>` values pointing at the same `Owner`, it will remain
 107 //!     // allocated. The field projection `gadget1.owner.name` works because
 108 //!     // `Rc<Owner>` automatically dereferences to `Owner`.
 109 //!     println!("Gadget {} owned by {}", gadget1.id, gadget1.owner.name);
 110 //!     println!("Gadget {} owned by {}", gadget2.id, gadget2.owner.name);
 111 //!
 112 //!     // At the end of the function, `gadget1` and `gadget2` are destroyed, and
 113 //!     // with them the last counted references to our `Owner`. Gadget Man now
 114 //!     // gets destroyed as well.
 115 //! }
 116 //! ```
 117 //!
 118 //! If our requirements change, and we also need to be able to traverse from
 119 //! `Owner` to `Gadget`, we will run into problems. An [`Rc`] pointer from `Owner`
 120 //! to `Gadget` introduces a cycle between the values. This means that their
 121 //! reference counts can never reach 0, and the values will remain allocated
 122 //! forever: a memory leak. In order to get around this, we can use [`Weak`]
 123 //! pointers.
 124 //!
 125 //! Rust actually makes it somewhat difficult to produce this loop in the first
 126 //! place. In order to end up with two values that point at each other, one of
 127 //! them needs to be mutable. This is difficult because [`Rc`] enforces
 128 //! memory safety by only giving out shared references to the value it wraps,
 129 //! and these don't allow direct mutation. We need to wrap the part of the
 130 //! value we wish to mutate in a [`RefCell`], which provides *interior
 131 //! mutability*: a method to achieve mutability through a shared reference.
 132 //! [`RefCell`] enforces Rust's borrowing rules at runtime.
 133 //!
 134 //! ```
 135 //! use std::rc::Rc;
 136 //! use std::rc::Weak;
 137 //! use std::cell::RefCell;
 138 //!
 139 //! struct Owner {
 140 //!     name: String,
 141 //!     gadgets: RefCell<Vec<Weak<Gadget>>>,
 142 //!     // ...other fields
 143 //! }
 144 //!
 145 //! struct Gadget {
 146 //!     id: i32,
 147 //!     owner: Rc<Owner>,
 148 //!     // ...other fields
 149 //! }
 150 //!
 151 //! fn main() {
 152 //!     // Create a reference-counted `Owner`. Note that we've put the `Owner`'s
 153 //!     // vector of `Gadget`s inside a `RefCell` so that we can mutate it through
 154 //!     // a shared reference.
 155 //!     let gadget_owner: Rc<Owner> = Rc::new(
 156 //!         Owner {
 157 //!             name: "Gadget Man".to_string(),
 158 //!             gadgets: RefCell::new(vec![]),
 159 //!         }
 160 //!     );
 161 //!
 162 //!     // Create `Gadget`s belonging to `gadget_owner`, as before.
 163 //!     let gadget1 = Rc::new(
 164 //!         Gadget {
 165 //!             id: 1,
 166 //!             owner: gadget_owner.clone(),
 167 //!         }
 168 //!     );
 169 //!     let gadget2 = Rc::new(
 170 //!         Gadget {
 171 //!             id: 2,
 172 //!             owner: gadget_owner.clone(),
 173 //!         }
 174 //!     );
 175 //!
 176 //!     // Add the `Gadget`s to their `Owner`.
 177 //!     {
 178 //!         let mut gadgets = gadget_owner.gadgets.borrow_mut();
 179 //!         gadgets.push(Rc::downgrade(&gadget1));
 180 //!         gadgets.push(Rc::downgrade(&gadget2));
 181 //!
 182 //!         // `RefCell` dynamic borrow ends here.
 183 //!     }
 184 //!
 185 //!     // Iterate over our `Gadget`s, printing their details out.
 186 //!     for gadget_weak in gadget_owner.gadgets.borrow().iter() {
 187 //!
 188 //!         // `gadget_weak` is a `Weak<Gadget>`. Since `Weak` pointers can't
 189 //!         // guarantee the value is still allocated, we need to call
 190 //!         // `upgrade`, which returns an `Option<Rc<Gadget>>`.
 191 //!         //
 192 //!         // In this case we know the value still exists, so we simply
 193 //!         // `unwrap` the `Option`. In a more complicated program, you might
 194 //!         // need graceful error handling for a `None` result.
 195 //!
 196 //!         let gadget = gadget_weak.upgrade().unwrap();
 197 //!         println!("Gadget {} owned by {}", gadget.id, gadget.owner.name);
 198 //!     }
 199 //!
 200 //!     // At the end of the function, `gadget_owner`, `gadget1`, and `gadget2`
 201 //!     // are destroyed. There are now no strong (`Rc`) pointers to the
 202 //!     // gadgets, so they are destroyed. This zeroes the reference count on
 203 //!     // Gadget Man, so he gets destroyed as well.
 204 //! }
 205 //! ```
 206 //!
 207 //! [`Rc`]: struct.Rc.html
 208 //! [`Weak`]: struct.Weak.html
 209 //! [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 210 //! [`Cell`]: ../../std/cell/struct.Cell.html
 211 //! [`RefCell`]: ../../std/cell/struct.RefCell.html
 212 //! [send]: ../../std/marker/trait.Send.html
 213 //! [arc]: ../../std/sync/struct.Arc.html
 214 //! [`Deref`]: ../../std/ops/trait.Deref.html
 215 //! [downgrade]: struct.Rc.html#method.downgrade
 216 //! [upgrade]: struct.Weak.html#method.upgrade
 217 //! [`None`]: ../../std/option/enum.Option.html#variant.None
 218 //! [assoc]: ../../book/first-edition/method-syntax.html#associated-functions
 219 //! [mutability]: ../../std/cell/index.html#introducing-mutability-inside-of-something-immutable
 220
 221 #![stable(feature = "rust1", since = "1.0.0")]
 222
 223 #[cfg(not(test))]
 224 use boxed::Box;
 225 #[cfg(test)]
 226 use std::boxed::Box;
 227
 228 use core::borrow;
 229 use core::cell::Cell;
 230 use core::cmp::Ordering;
 231 use core::fmt;
 232 use core::hash::{Hash, Hasher};
 233 use core::intrinsics::{abort, assume};
 234 use core::marker;
 235 use core::marker::Unsize;
 236 use core::mem::{self, align_of_val, forget, size_of, size_of_val, uninitialized};
 237 use core::ops::Deref;
 238 use core::ops::CoerceUnsized;
 239 use core::ptr::{self, Shared};
 240 use core::convert::From;
 241
 242 use heap::{allocate, deallocate, box_free};
 243 use raw_vec::RawVec;
 244
 245 struct RcBox<T: ?Sized> {
 246     strong: Cell<usize>,
 247     weak: Cell<usize>,
 248     value: T,
 249 }
 250
 251 /// A single-threaded reference-counting pointer.
 252 ///
 253 /// See the [module-level documentation](./index.html) for more details.
 254 ///
 255 /// The inherent methods of `Rc` are all associated functions, which means
 256 /// that you have to call them as e.g. [`Rc::get_mut(&value)`][get_mut] instead of
 257 /// `value.get_mut()`. This avoids conflicts with methods of the inner
 258 /// type `T`.
 259 ///
 260 /// [get_mut]: #method.get_mut
 261 #[stable(feature = "rust1", since = "1.0.0")]
 262 pub struct Rc<T: ?Sized> {
 263     ptr: Shared<RcBox<T>>,
 264 }
 265
 266 #[stable(feature = "rust1", since = "1.0.0")]
 267 impl<T: ?Sized> !marker::Send for Rc<T> {}
 268 #[stable(feature = "rust1", since = "1.0.0")]
 269 impl<T: ?Sized> !marker::Sync for Rc<T> {}
 270
 271 #[unstable(feature = "coerce_unsized", issue = "27732")]
 272 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Rc<U>> for Rc<T> {}
 273
 274 impl<T> Rc<T> {
 275     /// Constructs a new `Rc<T>`.
 276     ///
 277     /// # Examples
 278     ///
 279     /// ```
 280     /// use std::rc::Rc;
 281     ///
 282     /// let five = Rc::new(5);
 283     /// ```
 284     #[stable(feature = "rust1", since = "1.0.0")]
 285     pub fn new(value: T) -> Rc<T> {
 286         unsafe {
 287             Rc {
 288                 // there is an implicit weak pointer owned by all the strong
 289                 // pointers, which ensures that the weak destructor never frees
 290                 // the allocation while the strong destructor is running, even
 291                 // if the weak pointer is stored inside the strong one.
 292                 ptr: Shared::new(Box::into_raw(box RcBox {
 293                     strong: Cell::new(1),
 294                     weak: Cell::new(1),
 295                     value: value,
 296                 })),
 297             }
 298         }
 299     }
 300
 301     /// Returns the contained value, if the `Rc` has exactly one strong reference.
 302     ///
 303     /// Otherwise, an [`Err`][result] is returned with the same `Rc` that was
 304     /// passed in.
 305     ///
 306     /// This will succeed even if there are outstanding weak references.
 307     ///
 308     /// [result]: ../../std/result/enum.Result.html
 309     ///
 310     /// # Examples
 311     ///
 312     /// ```
 313     /// use std::rc::Rc;
 314     ///
 315     /// let x = Rc::new(3);
 316     /// assert_eq!(Rc::try_unwrap(x), Ok(3));
 317     ///
 318     /// let x = Rc::new(4);
 319     /// let _y = x.clone();
 320     /// assert_eq!(*Rc::try_unwrap(x).unwrap_err(), 4);
 321     /// ```
 322     #[inline]
 323     #[stable(feature = "rc_unique", since = "1.4.0")]
 324     pub fn try_unwrap(this: Self) -> Result<T, Self> {
 325         if Rc::strong_count(&this) == 1 {
 326             unsafe {
 327                 let val = ptr::read(&*this); // copy the contained object
 328
 329                 // Indicate to Weaks that they can't be promoted by decrememting
 330                 // the strong count, and then remove the implicit "strong weak"
 331                 // pointer while also handling drop logic by just crafting a
 332                 // fake Weak.
 333                 this.dec_strong();
 334                 let _weak = Weak { ptr: this.ptr };
 335                 forget(this);
 336                 Ok(val)
 337             }
 338         } else {
 339             Err(this)
 340         }
 341     }
 342
 343     /// Checks whether [`Rc::try_unwrap`][try_unwrap] would return
 344     /// [`Ok`].
 345     ///
 346     /// [try_unwrap]: struct.Rc.html#method.try_unwrap
 347     /// [`Ok`]: ../../std/result/enum.Result.html#variant.Ok
 348     #[unstable(feature = "rc_would_unwrap",
 349                reason = "just added for niche usecase",
 350                issue = "28356")]
 351     #[rustc_deprecated(since = "1.15.0", reason = "too niche; use `strong_count` instead")]
 352     pub fn would_unwrap(this: &Self) -> bool {
 353         Rc::strong_count(&this) == 1
 354     }
 355
 356     /// Consumes the `Rc`, returning the wrapped pointer.
 357     ///
 358     /// To avoid a memory leak the pointer must be converted back to an `Rc` using
 359     /// [`Rc::from_raw`][from_raw].
 360     ///
 361     /// [from_raw]: struct.Rc.html#method.from_raw
 362     ///
 363     /// # Examples
 364     ///
 365     /// ```
 366     /// use std::rc::Rc;
 367     ///
 368     /// let x = Rc::new(10);
 369     /// let x_ptr = Rc::into_raw(x);
 370     /// assert_eq!(unsafe { *x_ptr }, 10);
 371     /// ```
 372     #[stable(feature = "rc_raw", since = "1.17.0")]
 373     pub fn into_raw(this: Self) -> *const T {
 374         let ptr = unsafe { &mut (*this.ptr.as_mut_ptr()).value as *const _ };
 375         mem::forget(this);
 376         ptr
 377     }
 378
 379     /// Constructs an `Rc` from a raw pointer.
 380     ///
 381     /// The raw pointer must have been previously returned by a call to a
 382     /// [`Rc::into_raw`][into_raw].
 383     ///
 384     /// This function is unsafe because improper use may lead to memory problems. For example, a
 385     /// double-free may occur if the function is called twice on the same raw pointer.
 386     ///
 387     /// [into_raw]: struct.Rc.html#method.into_raw
 388     ///
 389     /// # Examples
 390     ///
 391     /// ```
 392     /// use std::rc::Rc;
 393     ///
 394     /// let x = Rc::new(10);
 395     /// let x_ptr = Rc::into_raw(x);
 396     ///
 397     /// unsafe {
 398     ///     // Convert back to an `Rc` to prevent leak.
 399     ///     let x = Rc::from_raw(x_ptr);
 400     ///     assert_eq!(*x, 10);
 401     ///
 402     ///     // Further calls to `Rc::from_raw(x_ptr)` would be memory unsafe.
 403     /// }
 404     ///
 405     /// // The memory was freed when `x` went out of scope above, so `x_ptr` is now dangling!
 406     /// ```
 407     #[stable(feature = "rc_raw", since = "1.17.0")]
 408     pub unsafe fn from_raw(ptr: *const T) -> Self {
 409         // To find the corresponding pointer to the `RcBox` we need to subtract the offset of the
 410         // `value` field from the pointer.
 411         Rc { ptr: Shared::new((ptr as *const u8).offset(-offset_of!(RcBox<T>, value)) as *const _) }
 412     }
 413 }
 414
 415 impl Rc<str> {
 416     /// Constructs a new `Rc<str>` from a string slice.
 417     #[doc(hidden)]
 418     #[unstable(feature = "rustc_private",
 419                reason = "for internal use in rustc",
 420                issue = "0")]
 421     pub fn __from_str(value: &str) -> Rc<str> {
 422         unsafe {
 423             // Allocate enough space for `RcBox<str>`.
 424             let aligned_len = 2 + (value.len() + size_of::<usize>() - 1) / size_of::<usize>();
 425             let vec = RawVec::<usize>::with_capacity(aligned_len);
 426             let ptr = vec.ptr();
 427             forget(vec);
 428             // Initialize fields of `RcBox<str>`.
 429             *ptr.offset(0) = 1; // strong: Cell::new(1)
 430             *ptr.offset(1) = 1; // weak: Cell::new(1)
 431             ptr::copy_nonoverlapping(value.as_ptr(), ptr.offset(2) as *mut u8, value.len());
 432             // Combine the allocation address and the string length into a fat pointer to `RcBox`.
 433             let rcbox_ptr: *mut RcBox<str> = mem::transmute([ptr as usize, value.len()]);
 434             assert!(aligned_len * size_of::<usize>() == size_of_val(&*rcbox_ptr));
 435             Rc { ptr: Shared::new(rcbox_ptr) }
 436         }
 437     }
 438 }
 439
 440 impl<T> Rc<[T]> {
 441     /// Constructs a new `Rc<[T]>` from a `Box<[T]>`.
 442     #[doc(hidden)]
 443     #[unstable(feature = "rustc_private",
 444                reason = "for internal use in rustc",
 445                issue = "0")]
 446     pub fn __from_array(value: Box<[T]>) -> Rc<[T]> {
 447         unsafe {
 448             let ptr: *mut RcBox<[T]> =
 449                 mem::transmute([mem::align_of::<RcBox<[T; 1]>>(), value.len()]);
 450             // FIXME(custom-DST): creating this invalid &[T] is dubiously defined,
 451             // we should have a better way of getting the size/align
 452             // of a DST from its unsized part.
 453             let ptr = allocate(size_of_val(&*ptr), align_of_val(&*ptr));
 454             let ptr: *mut RcBox<[T]> = mem::transmute([ptr as usize, value.len()]);
 455
 456             // Initialize the new RcBox.
 457             ptr::write(&mut (*ptr).strong, Cell::new(1));
 458             ptr::write(&mut (*ptr).weak, Cell::new(1));
 459             ptr::copy_nonoverlapping(
 460                 value.as_ptr(),
 461                 &mut (*ptr).value as *mut [T] as *mut T,
 462                 value.len());
 463
 464             // Free the original allocation without freeing its (moved) contents.
 465             box_free(Box::into_raw(value));
 466
 467             Rc { ptr: Shared::new(ptr as *const _) }
 468         }
 469     }
 470 }
 471
 472 impl<T: ?Sized> Rc<T> {
 473     /// Creates a new [`Weak`][weak] pointer 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     ///
 484     /// let weak_five = Rc::downgrade(&five);
 485     /// ```
 486     #[stable(feature = "rc_weak", since = "1.4.0")]
 487     pub fn downgrade(this: &Self) -> Weak<T> {
 488         this.inc_weak();
 489         Weak { ptr: this.ptr }
 490     }
 491
 492     /// Gets the number of [`Weak`][weak] pointers to this value.
 493     ///
 494     /// [weak]: struct.Weak.html
 495     ///
 496     /// # Examples
 497     ///
 498     /// ```
 499     /// use std::rc::Rc;
 500     ///
 501     /// let five = Rc::new(5);
 502     /// let _weak_five = Rc::downgrade(&five);
 503     ///
 504     /// assert_eq!(1, Rc::weak_count(&five));
 505     /// ```
 506     #[inline]
 507     #[stable(feature = "rc_counts", since = "1.15.0")]
 508     pub fn weak_count(this: &Self) -> usize {
 509         this.weak() - 1
 510     }
 511
 512     /// Gets the number of strong (`Rc`) pointers to this value.
 513     ///
 514     /// # Examples
 515     ///
 516     /// ```
 517     /// use std::rc::Rc;
 518     ///
 519     /// let five = Rc::new(5);
 520     /// let _also_five = five.clone();
 521     ///
 522     /// assert_eq!(2, Rc::strong_count(&five));
 523     /// ```
 524     #[inline]
 525     #[stable(feature = "rc_counts", since = "1.15.0")]
 526     pub fn strong_count(this: &Self) -> usize {
 527         this.strong()
 528     }
 529
 530     /// Returns true if there are no other `Rc` or [`Weak`][weak] pointers to
 531     /// this inner value.
 532     ///
 533     /// [weak]: struct.Weak.html
 534     #[inline]
 535     #[unstable(feature = "is_unique", reason = "uniqueness has unclear meaning",
 536                issue = "28356")]
 537     #[rustc_deprecated(since = "1.15.0",
 538                        reason = "too niche; use `strong_count` and `weak_count` instead")]
 539     pub fn is_unique(this: &Self) -> bool {
 540         Rc::weak_count(this) == 0 && Rc::strong_count(this) == 1
 541     }
 542
 543     /// Returns a mutable reference to the inner value, if there are
 544     /// no other `Rc` or [`Weak`][weak] pointers to the same value.
 545     ///
 546     /// Returns [`None`] otherwise, because it is not safe to
 547     /// mutate a shared value.
 548     ///
 549     /// See also [`make_mut`][make_mut], which will [`clone`][clone]
 550     /// the inner value when it's shared.
 551     ///
 552     /// [weak]: struct.Weak.html
 553     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 554     /// [make_mut]: struct.Rc.html#method.make_mut
 555     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 556     ///
 557     /// # Examples
 558     ///
 559     /// ```
 560     /// use std::rc::Rc;
 561     ///
 562     /// let mut x = Rc::new(3);
 563     /// *Rc::get_mut(&mut x).unwrap() = 4;
 564     /// assert_eq!(*x, 4);
 565     ///
 566     /// let _y = x.clone();
 567     /// assert!(Rc::get_mut(&mut x).is_none());
 568     /// ```
 569     #[inline]
 570     #[stable(feature = "rc_unique", since = "1.4.0")]
 571     pub fn get_mut(this: &mut Self) -> Option<&mut T> {
 572         if Rc::is_unique(this) {
 573             let inner = unsafe { &mut *this.ptr.as_mut_ptr() };
 574             Some(&mut inner.value)
 575         } else {
 576             None
 577         }
 578     }
 579
 580     #[inline]
 581     #[stable(feature = "ptr_eq", since = "1.17.0")]
 582     /// Returns true if the two `Rc`s point to the same value (not
 583     /// just values that compare as equal).
 584     ///
 585     /// # Examples
 586     ///
 587     /// ```
 588     /// use std::rc::Rc;
 589     ///
 590     /// let five = Rc::new(5);
 591     /// let same_five = five.clone();
 592     /// let other_five = Rc::new(5);
 593     ///
 594     /// assert!(Rc::ptr_eq(&five, &same_five));
 595     /// assert!(!Rc::ptr_eq(&five, &other_five));
 596     /// ```
 597     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
 598         let this_ptr: *const RcBox<T> = *this.ptr;
 599         let other_ptr: *const RcBox<T> = *other.ptr;
 600         this_ptr == other_ptr
 601     }
 602 }
 603
 604 impl<T: Clone> Rc<T> {
 605     /// Makes a mutable reference into the given `Rc`.
 606     ///
 607     /// If there are other `Rc` or [`Weak`][weak] pointers to the same value,
 608     /// then `make_mut` will invoke [`clone`][clone] on the inner value to
 609     /// ensure unique ownership. This is also referred to as clone-on-write.
 610     ///
 611     /// See also [`get_mut`][get_mut], which will fail rather than cloning.
 612     ///
 613     /// [weak]: struct.Weak.html
 614     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 615     /// [get_mut]: struct.Rc.html#method.get_mut
 616     ///
 617     /// # Examples
 618     ///
 619     /// ```
 620     /// use std::rc::Rc;
 621     ///
 622     /// let mut data = Rc::new(5);
 623     ///
 624     /// *Rc::make_mut(&mut data) += 1;        // Won't clone anything
 625     /// let mut other_data = data.clone();    // Won't clone inner data
 626     /// *Rc::make_mut(&mut data) += 1;        // Clones inner data
 627     /// *Rc::make_mut(&mut data) += 1;        // Won't clone anything
 628     /// *Rc::make_mut(&mut other_data) *= 2;  // Won't clone anything
 629     ///
 630     /// // Now `data` and `other_data` point to different values.
 631     /// assert_eq!(*data, 8);
 632     /// assert_eq!(*other_data, 12);
 633     /// ```
 634     #[inline]
 635     #[stable(feature = "rc_unique", since = "1.4.0")]
 636     pub fn make_mut(this: &mut Self) -> &mut T {
 637         if Rc::strong_count(this) != 1 {
 638             // Gotta clone the data, there are other Rcs
 639             *this = Rc::new((**this).clone())
 640         } else if Rc::weak_count(this) != 0 {
 641             // Can just steal the data, all that's left is Weaks
 642             unsafe {
 643                 let mut swap = Rc::new(ptr::read(&(**this.ptr).value));
 644                 mem::swap(this, &mut swap);
 645                 swap.dec_strong();
 646                 // Remove implicit strong-weak ref (no need to craft a fake
 647                 // Weak here -- we know other Weaks can clean up for us)
 648                 swap.dec_weak();
 649                 forget(swap);
 650             }
 651         }
 652         // This unsafety is ok because we're guaranteed that the pointer
 653         // returned is the *only* pointer that will ever be returned to T. Our
 654         // reference count is guaranteed to be 1 at this point, and we required
 655         // the `Rc<T>` itself to be `mut`, so we're returning the only possible
 656         // reference to the inner value.
 657         let inner = unsafe { &mut *this.ptr.as_mut_ptr() };
 658         &mut inner.value
 659     }
 660 }
 661
 662 #[stable(feature = "rust1", since = "1.0.0")]
 663 impl<T: ?Sized> Deref for Rc<T> {
 664     type Target = T;
 665
 666     #[inline(always)]
 667     fn deref(&self) -> &T {
 668         &self.inner().value
 669     }
 670 }
 671
 672 #[stable(feature = "rust1", since = "1.0.0")]
 673 unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
 674     /// Drops the `Rc`.
 675     ///
 676     /// This will decrement the strong reference count. If the strong reference
 677     /// count reaches zero then the only other references (if any) are
 678     /// [`Weak`][weak], so we `drop` the inner value.
 679     ///
 680     /// [weak]: struct.Weak.html
 681     ///
 682     /// # Examples
 683     ///
 684     /// ```
 685     /// use std::rc::Rc;
 686     ///
 687     /// struct Foo;
 688     ///
 689     /// impl Drop for Foo {
 690     ///     fn drop(&mut self) {
 691     ///         println!("dropped!");
 692     ///     }
 693     /// }
 694     ///
 695     /// let foo  = Rc::new(Foo);
 696     /// let foo2 = foo.clone();
 697     ///
 698     /// drop(foo);    // Doesn't print anything
 699     /// drop(foo2);   // Prints "dropped!"
 700     /// ```
 701     fn drop(&mut self) {
 702         unsafe {
 703             let ptr = self.ptr.as_mut_ptr();
 704
 705             self.dec_strong();
 706             if self.strong() == 0 {
 707                 // destroy the contained object
 708                 ptr::drop_in_place(&mut (*ptr).value);
 709
 710                 // remove the implicit "strong weak" pointer now that we've
 711                 // destroyed the contents.
 712                 self.dec_weak();
 713
 714                 if self.weak() == 0 {
 715                     deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr))
 716                 }
 717             }
 718         }
 719     }
 720 }
 721
 722 #[stable(feature = "rust1", since = "1.0.0")]
 723 impl<T: ?Sized> Clone for Rc<T> {
 724     /// Makes a clone of the `Rc` pointer.
 725     ///
 726     /// This creates another pointer to the same inner value, increasing the
 727     /// strong reference count.
 728     ///
 729     /// # Examples
 730     ///
 731     /// ```
 732     /// use std::rc::Rc;
 733     ///
 734     /// let five = Rc::new(5);
 735     ///
 736     /// five.clone();
 737     /// ```
 738     #[inline]
 739     fn clone(&self) -> Rc<T> {
 740         self.inc_strong();
 741         Rc { ptr: self.ptr }
 742     }
 743 }
 744
 745 #[stable(feature = "rust1", since = "1.0.0")]
 746 impl<T: Default> Default for Rc<T> {
 747     /// Creates a new `Rc<T>`, with the `Default` value for `T`.
 748     ///
 749     /// # Examples
 750     ///
 751     /// ```
 752     /// use std::rc::Rc;
 753     ///
 754     /// let x: Rc<i32> = Default::default();
 755     /// assert_eq!(*x, 0);
 756     /// ```
 757     #[inline]
 758     fn default() -> Rc<T> {
 759         Rc::new(Default::default())
 760     }
 761 }
 762
 763 #[stable(feature = "rust1", since = "1.0.0")]
 764 impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
 765     /// Equality for two `Rc`s.
 766     ///
 767     /// Two `Rc`s are equal if their inner values are equal.
 768     ///
 769     /// # Examples
 770     ///
 771     /// ```
 772     /// use std::rc::Rc;
 773     ///
 774     /// let five = Rc::new(5);
 775     ///
 776     /// assert!(five == Rc::new(5));
 777     /// ```
 778     #[inline(always)]
 779     fn eq(&self, other: &Rc<T>) -> bool {
 780         **self == **other
 781     }
 782
 783     /// Inequality for two `Rc`s.
 784     ///
 785     /// Two `Rc`s are unequal if their inner values are unequal.
 786     ///
 787     /// # Examples
 788     ///
 789     /// ```
 790     /// use std::rc::Rc;
 791     ///
 792     /// let five = Rc::new(5);
 793     ///
 794     /// assert!(five != Rc::new(6));
 795     /// ```
 796     #[inline(always)]
 797     fn ne(&self, other: &Rc<T>) -> bool {
 798         **self != **other
 799     }
 800 }
 801
 802 #[stable(feature = "rust1", since = "1.0.0")]
 803 impl<T: ?Sized + Eq> Eq for Rc<T> {}
 804
 805 #[stable(feature = "rust1", since = "1.0.0")]
 806 impl<T: ?Sized + PartialOrd> PartialOrd for Rc<T> {
 807     /// Partial comparison for two `Rc`s.
 808     ///
 809     /// The two are compared by calling `partial_cmp()` on their inner values.
 810     ///
 811     /// # Examples
 812     ///
 813     /// ```
 814     /// use std::rc::Rc;
 815     /// use std::cmp::Ordering;
 816     ///
 817     /// let five = Rc::new(5);
 818     ///
 819     /// assert_eq!(Some(Ordering::Less), five.partial_cmp(&Rc::new(6)));
 820     /// ```
 821     #[inline(always)]
 822     fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
 823         (**self).partial_cmp(&**other)
 824     }
 825
 826     /// Less-than comparison for two `Rc`s.
 827     ///
 828     /// The two are compared by calling `<` on their inner values.
 829     ///
 830     /// # Examples
 831     ///
 832     /// ```
 833     /// use std::rc::Rc;
 834     ///
 835     /// let five = Rc::new(5);
 836     ///
 837     /// assert!(five < Rc::new(6));
 838     /// ```
 839     #[inline(always)]
 840     fn lt(&self, other: &Rc<T>) -> bool {
 841         **self < **other
 842     }
 843
 844     /// 'Less than or equal to' comparison for two `Rc`s.
 845     ///
 846     /// The two are compared by calling `<=` on their inner values.
 847     ///
 848     /// # Examples
 849     ///
 850     /// ```
 851     /// use std::rc::Rc;
 852     ///
 853     /// let five = Rc::new(5);
 854     ///
 855     /// assert!(five <= Rc::new(5));
 856     /// ```
 857     #[inline(always)]
 858     fn le(&self, other: &Rc<T>) -> bool {
 859         **self <= **other
 860     }
 861
 862     /// Greater-than comparison for two `Rc`s.
 863     ///
 864     /// The two are compared by calling `>` on their inner values.
 865     ///
 866     /// # Examples
 867     ///
 868     /// ```
 869     /// use std::rc::Rc;
 870     ///
 871     /// let five = Rc::new(5);
 872     ///
 873     /// assert!(five > Rc::new(4));
 874     /// ```
 875     #[inline(always)]
 876     fn gt(&self, other: &Rc<T>) -> bool {
 877         **self > **other
 878     }
 879
 880     /// 'Greater than or equal to' comparison for two `Rc`s.
 881     ///
 882     /// The two are compared by calling `>=` on their inner values.
 883     ///
 884     /// # Examples
 885     ///
 886     /// ```
 887     /// use std::rc::Rc;
 888     ///
 889     /// let five = Rc::new(5);
 890     ///
 891     /// assert!(five >= Rc::new(5));
 892     /// ```
 893     #[inline(always)]
 894     fn ge(&self, other: &Rc<T>) -> bool {
 895         **self >= **other
 896     }
 897 }
 898
 899 #[stable(feature = "rust1", since = "1.0.0")]
 900 impl<T: ?Sized + Ord> Ord for Rc<T> {
 901     /// Comparison for two `Rc`s.
 902     ///
 903     /// The two are compared by calling `cmp()` on their inner values.
 904     ///
 905     /// # Examples
 906     ///
 907     /// ```
 908     /// use std::rc::Rc;
 909     /// use std::cmp::Ordering;
 910     ///
 911     /// let five = Rc::new(5);
 912     ///
 913     /// assert_eq!(Ordering::Less, five.cmp(&Rc::new(6)));
 914     /// ```
 915     #[inline]
 916     fn cmp(&self, other: &Rc<T>) -> Ordering {
 917         (**self).cmp(&**other)
 918     }
 919 }
 920
 921 #[stable(feature = "rust1", since = "1.0.0")]
 922 impl<T: ?Sized + Hash> Hash for Rc<T> {
 923     fn hash<H: Hasher>(&self, state: &mut H) {
 924         (**self).hash(state);
 925     }
 926 }
 927
 928 #[stable(feature = "rust1", since = "1.0.0")]
 929 impl<T: ?Sized + fmt::Display> fmt::Display for Rc<T> {
 930     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 931         fmt::Display::fmt(&**self, f)
 932     }
 933 }
 934
 935 #[stable(feature = "rust1", since = "1.0.0")]
 936 impl<T: ?Sized + fmt::Debug> fmt::Debug for Rc<T> {
 937     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 938         fmt::Debug::fmt(&**self, f)
 939     }
 940 }
 941
 942 #[stable(feature = "rust1", since = "1.0.0")]
 943 impl<T: ?Sized> fmt::Pointer for Rc<T> {
 944     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 945         fmt::Pointer::fmt(&*self.ptr, f)
 946     }
 947 }
 948
 949 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
 950 impl<T> From<T> for Rc<T> {
 951     fn from(t: T) -> Self {
 952         Rc::new(t)
 953     }
 954 }
 955
 956 /// `Weak` is a version of [`Rc`] that holds a non-owning reference to the
 957 /// managed value. The value is accessed by calling [`upgrade`] on the `Weak`
 958 /// pointer, which returns an [`Option`]`<`[`Rc`]`<T>>`.
 959 ///
 960 /// Since a `Weak` reference does not count towards ownership, it will not
 961 /// prevent the inner value from being dropped, and `Weak` itself makes no
 962 /// guarantees about the value still being present and may return [`None`]
 963 /// when [`upgrade`]d.
 964 ///
 965 /// A `Weak` pointer is useful for keeping a temporary reference to the value
 966 /// within [`Rc`] without extending its lifetime. It is also used to prevent
 967 /// circular references between [`Rc`] pointers, since mutual owning references
 968 /// would never allow either [`Arc`] to be dropped. For example, a tree could
 969 /// have strong [`Rc`] pointers from parent nodes to children, and `Weak`
 970 /// pointers from children back to their parents.
 971 ///
 972 /// The typical way to obtain a `Weak` pointer is to call [`Rc::downgrade`].
 973 ///
 974 /// [`Rc`]: struct.Rc.html
 975 /// [`Rc::downgrade`]: struct.Rc.html#method.downgrade
 976 /// [`upgrade`]: struct.Weak.html#method.upgrade
 977 /// [`Option`]: ../../std/option/enum.Option.html
 978 /// [`None`]: ../../std/option/enum.Option.html#variant.None
 979 #[stable(feature = "rc_weak", since = "1.4.0")]
 980 pub struct Weak<T: ?Sized> {
 981     ptr: Shared<RcBox<T>>,
 982 }
 983
 984 #[stable(feature = "rc_weak", since = "1.4.0")]
 985 impl<T: ?Sized> !marker::Send for Weak<T> {}
 986 #[stable(feature = "rc_weak", since = "1.4.0")]
 987 impl<T: ?Sized> !marker::Sync for Weak<T> {}
 988
 989 #[unstable(feature = "coerce_unsized", issue = "27732")]
 990 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
 991
 992 impl<T> Weak<T> {
 993     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
 994     /// it. Calling [`upgrade`] on the return value always gives [`None`].
 995     ///
 996     /// [`upgrade`]: struct.Weak.html#method.upgrade
 997     /// [`None`]: ../../std/option/enum.Option.html
 998     ///
 999     /// # Examples
1000     ///
1001     /// ```
1002     /// use std::rc::Weak;
1003     ///
1004     /// let empty: Weak<i64> = Weak::new();
1005     /// assert!(empty.upgrade().is_none());
1006     /// ```
1007     #[stable(feature = "downgraded_weak", since = "1.10.0")]
1008     pub fn new() -> Weak<T> {
1009         unsafe {
1010             Weak {
1011                 ptr: Shared::new(Box::into_raw(box RcBox {
1012                     strong: Cell::new(0),
1013                     weak: Cell::new(1),
1014                     value: uninitialized(),
1015                 })),
1016             }
1017         }
1018     }
1019 }
1020
1021 impl<T: ?Sized> Weak<T> {
1022     /// Attempts to upgrade the `Weak` pointer to an [`Rc`], extending
1023     /// the lifetime of the value if successful.
1024     ///
1025     /// Returns [`None`] if the value has since been dropped.
1026     ///
1027     /// [`Rc`]: struct.Rc.html
1028     /// [`None`]: ../../std/option/enum.Option.html
1029     ///
1030     /// # Examples
1031     ///
1032     /// ```
1033     /// use std::rc::Rc;
1034     ///
1035     /// let five = Rc::new(5);
1036     ///
1037     /// let weak_five = Rc::downgrade(&five);
1038     ///
1039     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
1040     /// assert!(strong_five.is_some());
1041     ///
1042     /// // Destroy all strong pointers.
1043     /// drop(strong_five);
1044     /// drop(five);
1045     ///
1046     /// assert!(weak_five.upgrade().is_none());
1047     /// ```
1048     #[stable(feature = "rc_weak", since = "1.4.0")]
1049     pub fn upgrade(&self) -> Option<Rc<T>> {
1050         if self.strong() == 0 {
1051             None
1052         } else {
1053             self.inc_strong();
1054             Some(Rc { ptr: self.ptr })
1055         }
1056     }
1057 }
1058
1059 #[stable(feature = "rc_weak", since = "1.4.0")]
1060 impl<T: ?Sized> Drop for Weak<T> {
1061     /// Drops the `Weak` pointer.
1062     ///
1063     /// # Examples
1064     ///
1065     /// ```
1066     /// use std::rc::Rc;
1067     ///
1068     /// struct Foo;
1069     ///
1070     /// impl Drop for Foo {
1071     ///     fn drop(&mut self) {
1072     ///         println!("dropped!");
1073     ///     }
1074     /// }
1075     ///
1076     /// let foo = Rc::new(Foo);
1077     /// let weak_foo = Rc::downgrade(&foo);
1078     /// let other_weak_foo = weak_foo.clone();
1079     ///
1080     /// drop(weak_foo);   // Doesn't print anything
1081     /// drop(foo);        // Prints "dropped!"
1082     ///
1083     /// assert!(other_weak_foo.upgrade().is_none());
1084     /// ```
1085     fn drop(&mut self) {
1086         unsafe {
1087             let ptr = *self.ptr;
1088
1089             self.dec_weak();
1090             // the weak count starts at 1, and will only go to zero if all
1091             // the strong pointers have disappeared.
1092             if self.weak() == 0 {
1093                 deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr))
1094             }
1095         }
1096     }
1097 }
1098
1099 #[stable(feature = "rc_weak", since = "1.4.0")]
1100 impl<T: ?Sized> Clone for Weak<T> {
1101     /// Makes a clone of the `Weak` pointer that points to the same value.
1102     ///
1103     /// # Examples
1104     ///
1105     /// ```
1106     /// use std::rc::Rc;
1107     ///
1108     /// let weak_five = Rc::downgrade(&Rc::new(5));
1109     ///
1110     /// weak_five.clone();
1111     /// ```
1112     #[inline]
1113     fn clone(&self) -> Weak<T> {
1114         self.inc_weak();
1115         Weak { ptr: self.ptr }
1116     }
1117 }
1118
1119 #[stable(feature = "rc_weak", since = "1.4.0")]
1120 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
1121     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1122         write!(f, "(Weak)")
1123     }
1124 }
1125
1126 #[stable(feature = "downgraded_weak", since = "1.10.0")]
1127 impl<T> Default for Weak<T> {
1128     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
1129     /// it. Calling [`upgrade`] on the return value always gives [`None`].
1130     ///
1131     /// [`upgrade`]: struct.Weak.html#method.upgrade
1132     /// [`None`]: ../../std/option/enum.Option.html
1133     ///
1134     /// # Examples
1135     ///
1136     /// ```
1137     /// use std::rc::Weak;
1138     ///
1139     /// let empty: Weak<i64> = Default::default();
1140     /// assert!(empty.upgrade().is_none());
1141     /// ```
1142     fn default() -> Weak<T> {
1143         Weak::new()
1144     }
1145 }
1146
1147 // NOTE: We checked_add here to deal with mem::forget safety. In particular
1148 // if you mem::forget Rcs (or Weaks), the ref-count can overflow, and then
1149 // you can free the allocation while outstanding Rcs (or Weaks) exist.
1150 // We abort because this is such a degenerate scenario that we don't care about
1151 // what happens -- no real program should ever experience this.
1152 //
1153 // This should have negligible overhead since you don't actually need to
1154 // clone these much in Rust thanks to ownership and move-semantics.
1155
1156 #[doc(hidden)]
1157 trait RcBoxPtr<T: ?Sized> {
1158     fn inner(&self) -> &RcBox<T>;
1159
1160     #[inline]
1161     fn strong(&self) -> usize {
1162         self.inner().strong.get()
1163     }
1164
1165     #[inline]
1166     fn inc_strong(&self) {
1167         self.inner().strong.set(self.strong().checked_add(1).unwrap_or_else(|| unsafe { abort() }));
1168     }
1169
1170     #[inline]
1171     fn dec_strong(&self) {
1172         self.inner().strong.set(self.strong() - 1);
1173     }
1174
1175     #[inline]
1176     fn weak(&self) -> usize {
1177         self.inner().weak.get()
1178     }
1179
1180     #[inline]
1181     fn inc_weak(&self) {
1182         self.inner().weak.set(self.weak().checked_add(1).unwrap_or_else(|| unsafe { abort() }));
1183     }
1184
1185     #[inline]
1186     fn dec_weak(&self) {
1187         self.inner().weak.set(self.weak() - 1);
1188     }
1189 }
1190
1191 impl<T: ?Sized> RcBoxPtr<T> for Rc<T> {
1192     #[inline(always)]
1193     fn inner(&self) -> &RcBox<T> {
1194         unsafe {
1195             // Safe to assume this here, as if it weren't true, we'd be breaking
1196             // the contract anyway.
1197             // This allows the null check to be elided in the destructor if we
1198             // manipulated the reference count in the same function.
1199             assume(!(*(&self.ptr as *const _ as *const *const ())).is_null());
1200             &(**self.ptr)
1201         }
1202     }
1203 }
1204
1205 impl<T: ?Sized> RcBoxPtr<T> for Weak<T> {
1206     #[inline(always)]
1207     fn inner(&self) -> &RcBox<T> {
1208         unsafe {
1209             // Safe to assume this here, as if it weren't true, we'd be breaking
1210             // the contract anyway.
1211             // This allows the null check to be elided in the destructor if we
1212             // manipulated the reference count in the same function.
1213             assume(!(*(&self.ptr as *const _ as *const *const ())).is_null());
1214             &(**self.ptr)
1215         }
1216     }
1217 }
1218
1219 #[cfg(test)]
1220 mod tests {
1221     use super::{Rc, Weak};
1222     use std::boxed::Box;
1223     use std::cell::RefCell;
1224     use std::option::Option;
1225     use std::option::Option::{None, Some};
1226     use std::result::Result::{Err, Ok};
1227     use std::mem::drop;
1228     use std::clone::Clone;
1229     use std::convert::From;
1230
1231     #[test]
1232     fn test_clone() {
1233         let x = Rc::new(RefCell::new(5));
1234         let y = x.clone();
1235         *x.borrow_mut() = 20;
1236         assert_eq!(*y.borrow(), 20);
1237     }
1238
1239     #[test]
1240     fn test_simple() {
1241         let x = Rc::new(5);
1242         assert_eq!(*x, 5);
1243     }
1244
1245     #[test]
1246     fn test_simple_clone() {
1247         let x = Rc::new(5);
1248         let y = x.clone();
1249         assert_eq!(*x, 5);
1250         assert_eq!(*y, 5);
1251     }
1252
1253     #[test]
1254     fn test_destructor() {
1255         let x: Rc<Box<_>> = Rc::new(box 5);
1256         assert_eq!(**x, 5);
1257     }
1258
1259     #[test]
1260     fn test_live() {
1261         let x = Rc::new(5);
1262         let y = Rc::downgrade(&x);
1263         assert!(y.upgrade().is_some());
1264     }
1265
1266     #[test]
1267     fn test_dead() {
1268         let x = Rc::new(5);
1269         let y = Rc::downgrade(&x);
1270         drop(x);
1271         assert!(y.upgrade().is_none());
1272     }
1273
1274     #[test]
1275     fn weak_self_cyclic() {
1276         struct Cycle {
1277             x: RefCell<Option<Weak<Cycle>>>,
1278         }
1279
1280         let a = Rc::new(Cycle { x: RefCell::new(None) });
1281         let b = Rc::downgrade(&a.clone());
1282         *a.x.borrow_mut() = Some(b);
1283
1284         // hopefully we don't double-free (or leak)...
1285     }
1286
1287     #[test]
1288     fn is_unique() {
1289         let x = Rc::new(3);
1290         assert!(Rc::is_unique(&x));
1291         let y = x.clone();
1292         assert!(!Rc::is_unique(&x));
1293         drop(y);
1294         assert!(Rc::is_unique(&x));
1295         let w = Rc::downgrade(&x);
1296         assert!(!Rc::is_unique(&x));
1297         drop(w);
1298         assert!(Rc::is_unique(&x));
1299     }
1300
1301     #[test]
1302     fn test_strong_count() {
1303         let a = Rc::new(0);
1304         assert!(Rc::strong_count(&a) == 1);
1305         let w = Rc::downgrade(&a);
1306         assert!(Rc::strong_count(&a) == 1);
1307         let b = w.upgrade().expect("upgrade of live rc failed");
1308         assert!(Rc::strong_count(&b) == 2);
1309         assert!(Rc::strong_count(&a) == 2);
1310         drop(w);
1311         drop(a);
1312         assert!(Rc::strong_count(&b) == 1);
1313         let c = b.clone();
1314         assert!(Rc::strong_count(&b) == 2);
1315         assert!(Rc::strong_count(&c) == 2);
1316     }
1317
1318     #[test]
1319     fn test_weak_count() {
1320         let a = Rc::new(0);
1321         assert!(Rc::strong_count(&a) == 1);
1322         assert!(Rc::weak_count(&a) == 0);
1323         let w = Rc::downgrade(&a);
1324         assert!(Rc::strong_count(&a) == 1);
1325         assert!(Rc::weak_count(&a) == 1);
1326         drop(w);
1327         assert!(Rc::strong_count(&a) == 1);
1328         assert!(Rc::weak_count(&a) == 0);
1329         let c = a.clone();
1330         assert!(Rc::strong_count(&a) == 2);
1331         assert!(Rc::weak_count(&a) == 0);
1332         drop(c);
1333     }
1334
1335     #[test]
1336     fn try_unwrap() {
1337         let x = Rc::new(3);
1338         assert_eq!(Rc::try_unwrap(x), Ok(3));
1339         let x = Rc::new(4);
1340         let _y = x.clone();
1341         assert_eq!(Rc::try_unwrap(x), Err(Rc::new(4)));
1342         let x = Rc::new(5);
1343         let _w = Rc::downgrade(&x);
1344         assert_eq!(Rc::try_unwrap(x), Ok(5));
1345     }
1346
1347     #[test]
1348     fn into_from_raw() {
1349         let x = Rc::new(box "hello");
1350         let y = x.clone();
1351
1352         let x_ptr = Rc::into_raw(x);
1353         drop(y);
1354         unsafe {
1355             assert_eq!(**x_ptr, "hello");
1356
1357             let x = Rc::from_raw(x_ptr);
1358             assert_eq!(**x, "hello");
1359
1360             assert_eq!(Rc::try_unwrap(x).map(|x| *x), Ok("hello"));
1361         }
1362     }
1363
1364     #[test]
1365     fn get_mut() {
1366         let mut x = Rc::new(3);
1367         *Rc::get_mut(&mut x).unwrap() = 4;
1368         assert_eq!(*x, 4);
1369         let y = x.clone();
1370         assert!(Rc::get_mut(&mut x).is_none());
1371         drop(y);
1372         assert!(Rc::get_mut(&mut x).is_some());
1373         let _w = Rc::downgrade(&x);
1374         assert!(Rc::get_mut(&mut x).is_none());
1375     }
1376
1377     #[test]
1378     fn test_cowrc_clone_make_unique() {
1379         let mut cow0 = Rc::new(75);
1380         let mut cow1 = cow0.clone();
1381         let mut cow2 = cow1.clone();
1382
1383         assert!(75 == *Rc::make_mut(&mut cow0));
1384         assert!(75 == *Rc::make_mut(&mut cow1));
1385         assert!(75 == *Rc::make_mut(&mut cow2));
1386
1387         *Rc::make_mut(&mut cow0) += 1;
1388         *Rc::make_mut(&mut cow1) += 2;
1389         *Rc::make_mut(&mut cow2) += 3;
1390
1391         assert!(76 == *cow0);
1392         assert!(77 == *cow1);
1393         assert!(78 == *cow2);
1394
1395         // none should point to the same backing memory
1396         assert!(*cow0 != *cow1);
1397         assert!(*cow0 != *cow2);
1398         assert!(*cow1 != *cow2);
1399     }
1400
1401     #[test]
1402     fn test_cowrc_clone_unique2() {
1403         let mut cow0 = Rc::new(75);
1404         let cow1 = cow0.clone();
1405         let cow2 = cow1.clone();
1406
1407         assert!(75 == *cow0);
1408         assert!(75 == *cow1);
1409         assert!(75 == *cow2);
1410
1411         *Rc::make_mut(&mut cow0) += 1;
1412
1413         assert!(76 == *cow0);
1414         assert!(75 == *cow1);
1415         assert!(75 == *cow2);
1416
1417         // cow1 and cow2 should share the same contents
1418         // cow0 should have a unique reference
1419         assert!(*cow0 != *cow1);
1420         assert!(*cow0 != *cow2);
1421         assert!(*cow1 == *cow2);
1422     }
1423
1424     #[test]
1425     fn test_cowrc_clone_weak() {
1426         let mut cow0 = Rc::new(75);
1427         let cow1_weak = Rc::downgrade(&cow0);
1428
1429         assert!(75 == *cow0);
1430         assert!(75 == *cow1_weak.upgrade().unwrap());
1431
1432         *Rc::make_mut(&mut cow0) += 1;
1433
1434         assert!(76 == *cow0);
1435         assert!(cow1_weak.upgrade().is_none());
1436     }
1437
1438     #[test]
1439     fn test_show() {
1440         let foo = Rc::new(75);
1441         assert_eq!(format!("{:?}", foo), "75");
1442     }
1443
1444     #[test]
1445     fn test_unsized() {
1446         let foo: Rc<[i32]> = Rc::new([1, 2, 3]);
1447         assert_eq!(foo, foo.clone());
1448     }
1449
1450     #[test]
1451     fn test_from_owned() {
1452         let foo = 123;
1453         let foo_rc = Rc::from(foo);
1454         assert!(123 == *foo_rc);
1455     }
1456
1457     #[test]
1458     fn test_new_weak() {
1459         let foo: Weak<usize> = Weak::new();
1460         assert!(foo.upgrade().is_none());
1461     }
1462
1463     #[test]
1464     fn test_ptr_eq() {
1465         let five = Rc::new(5);
1466         let same_five = five.clone();
1467         let other_five = Rc::new(5);
1468
1469         assert!(Rc::ptr_eq(&five, &same_five));
1470         assert!(!Rc::ptr_eq(&five, &other_five));
1471     }
1472 }
1473
1474 #[stable(feature = "rust1", since = "1.0.0")]
1475 impl<T: ?Sized> borrow::Borrow<T> for Rc<T> {
1476     fn borrow(&self) -> &T {
1477         &**self
1478     }
1479 }
1480
1481 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1482 impl<T: ?Sized> AsRef<T> for Rc<T> {
1483     fn as_ref(&self) -> &T {
1484         &**self
1485     }
1486 }