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 //! Thread-local reference-counted boxes (the `Rc<T>` type).
  14 //!
  15 //! The `Rc<T>` type provides shared ownership of an immutable value.
  16 //! Destruction is deterministic, and will occur as soon as the last owner is
  17 //! gone. It is marked as non-sendable because it avoids the overhead of atomic
  18 //! reference counting.
  19 //!
  20 //! The `downgrade` method can be used to create a non-owning `Weak<T>` pointer
  21 //! to the box. A `Weak<T>` pointer can be upgraded to an `Rc<T>` pointer, but
  22 //! will return `None` if the value has already been dropped.
  23 //!
  24 //! For example, a tree with parent pointers can be represented by putting the
  25 //! nodes behind strong `Rc<T>` pointers, and then storing the parent pointers
  26 //! as `Weak<T>` pointers.
  27 //!
  28 //! # Examples
  29 //!
  30 //! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`.
  31 //! We want to have our `Gadget`s point to their `Owner`. We can't do this with
  32 //! unique ownership, because more than one gadget may belong to the same
  33 //! `Owner`. `Rc<T>` allows us to share an `Owner` between multiple `Gadget`s,
  34 //! and have the `Owner` remain allocated as long as any `Gadget` points at it.
  35 //!
  36 //! ```rust
  37 //! use std::rc::Rc;
  38 //!
  39 //! struct Owner {
  40 //!     name: String
  41 //!     // ...other fields
  42 //! }
  43 //!
  44 //! struct Gadget {
  45 //!     id: i32,
  46 //!     owner: Rc<Owner>
  47 //!     // ...other fields
  48 //! }
  49 //!
  50 //! fn main() {
  51 //!     // Create a reference counted Owner.
  52 //!     let gadget_owner : Rc<Owner> = Rc::new(
  53 //!         Owner { name: String::from("Gadget Man") }
  54 //!     );
  55 //!
  56 //!     // Create Gadgets belonging to gadget_owner. To increment the reference
  57 //!     // count we clone the `Rc<T>` object.
  58 //!     let gadget1 = Gadget { id: 1, owner: gadget_owner.clone() };
  59 //!     let gadget2 = Gadget { id: 2, owner: gadget_owner.clone() };
  60 //!
  61 //!     drop(gadget_owner);
  62 //!
  63 //!     // Despite dropping gadget_owner, we're still able to print out the name
  64 //!     // of the Owner of the Gadgets. This is because we've only dropped the
  65 //!     // reference count object, not the Owner it wraps. As long as there are
  66 //!     // other `Rc<T>` objects pointing at the same Owner, it will remain
  67 //!     // allocated. Notice that the `Rc<T>` wrapper around Gadget.owner gets
  68 //!     // automatically dereferenced for us.
  69 //!     println!("Gadget {} owned by {}", gadget1.id, gadget1.owner.name);
  70 //!     println!("Gadget {} owned by {}", gadget2.id, gadget2.owner.name);
  71 //!
  72 //!     // At the end of the method, gadget1 and gadget2 get destroyed, and with
  73 //!     // them the last counted references to our Owner. Gadget Man now gets
  74 //!     // destroyed as well.
  75 //! }
  76 //! ```
  77 //!
  78 //! If our requirements change, and we also need to be able to traverse from
  79 //! Owner → Gadget, we will run into problems: an `Rc<T>` pointer from Owner
  80 //! → Gadget introduces a cycle between the objects. This means that their
  81 //! reference counts can never reach 0, and the objects will remain allocated: a
  82 //! memory leak. In order to get around this, we can use `Weak<T>` pointers.
  83 //! These pointers don't contribute to the total count.
  84 //!
  85 //! Rust actually makes it somewhat difficult to produce this loop in the first
  86 //! place: in order to end up with two objects that point at each other, one of
  87 //! them needs to be mutable. This is problematic because `Rc<T>` enforces
  88 //! memory safety by only giving out shared references to the object it wraps,
  89 //! and these don't allow direct mutation. We need to wrap the part of the
  90 //! object we wish to mutate in a `RefCell`, which provides *interior
  91 //! mutability*: a method to achieve mutability through a shared reference.
  92 //! `RefCell` enforces Rust's borrowing rules at runtime.  Read the `Cell`
  93 //! documentation for more details on interior mutability.
  94 //!
  95 //! ```rust
  96 //! use std::rc::Rc;
  97 //! use std::rc::Weak;
  98 //! use std::cell::RefCell;
  99 //!
 100 //! struct Owner {
 101 //!     name: String,
 102 //!     gadgets: RefCell<Vec<Weak<Gadget>>>,
 103 //!     // ...other fields
 104 //! }
 105 //!
 106 //! struct Gadget {
 107 //!     id: i32,
 108 //!     owner: Rc<Owner>,
 109 //!     // ...other fields
 110 //! }
 111 //!
 112 //! fn main() {
 113 //!     // Create a reference counted Owner. Note the fact that we've put the
 114 //!     // Owner's vector of Gadgets inside a RefCell so that we can mutate it
 115 //!     // through a shared reference.
 116 //!     let gadget_owner : Rc<Owner> = Rc::new(
 117 //!         Owner {
 118 //!             name: "Gadget Man".to_string(),
 119 //!             gadgets: RefCell::new(Vec::new()),
 120 //!         }
 121 //!     );
 122 //!
 123 //!     // Create Gadgets belonging to gadget_owner as before.
 124 //!     let gadget1 = Rc::new(Gadget{id: 1, owner: gadget_owner.clone()});
 125 //!     let gadget2 = Rc::new(Gadget{id: 2, owner: gadget_owner.clone()});
 126 //!
 127 //!     // Add the Gadgets to their Owner. To do this we mutably borrow from
 128 //!     // the RefCell holding the Owner's Gadgets.
 129 //!     gadget_owner.gadgets.borrow_mut().push(Rc::downgrade(&gadget1));
 130 //!     gadget_owner.gadgets.borrow_mut().push(Rc::downgrade(&gadget2));
 131 //!
 132 //!     // Iterate over our Gadgets, printing their details out
 133 //!     for gadget_opt in gadget_owner.gadgets.borrow().iter() {
 134 //!
 135 //!         // gadget_opt is a Weak<Gadget>. Since weak pointers can't guarantee
 136 //!         // that their object is still allocated, we need to call upgrade()
 137 //!         // on them to turn them into a strong reference. This returns an
 138 //!         // Option, which contains a reference to our object if it still
 139 //!         // exists.
 140 //!         let gadget = gadget_opt.upgrade().unwrap();
 141 //!         println!("Gadget {} owned by {}", gadget.id, gadget.owner.name);
 142 //!     }
 143 //!
 144 //!     // At the end of the method, gadget_owner, gadget1 and gadget2 get
 145 //!     // destroyed. There are now no strong (`Rc<T>`) references to the gadgets.
 146 //!     // Once they get destroyed, the Gadgets get destroyed. This zeroes the
 147 //!     // reference count on Gadget Man, they get destroyed as well.
 148 //! }
 149 //! ```
 150
 151 #![stable(feature = "rust1", since = "1.0.0")]
 152
 153 #[cfg(not(test))]
 154 use boxed::Box;
 155 #[cfg(test)]
 156 use std::boxed::Box;
 157
 158 use core::borrow;
 159 use core::cell::Cell;
 160 use core::cmp::Ordering;
 161 use core::fmt;
 162 use core::hash::{Hasher, Hash};
 163 use core::intrinsics::{assume, abort};
 164 use core::marker;
 165 use core::marker::Unsize;
 166 use core::mem::{self, align_of_val, size_of_val, forget, uninitialized};
 167 use core::ops::Deref;
 168 use core::ops::CoerceUnsized;
 169 use core::ptr::{self, Shared};
 170 use core::convert::From;
 171
 172 use heap::deallocate;
 173
 174 struct RcBox<T: ?Sized> {
 175     strong: Cell<usize>,
 176     weak: Cell<usize>,
 177     value: T,
 178 }
 179
 180
 181 /// A reference-counted pointer type over an immutable value.
 182 ///
 183 /// See the [module level documentation](./index.html) for more details.
 184 #[unsafe_no_drop_flag]
 185 #[stable(feature = "rust1", since = "1.0.0")]
 186 pub struct Rc<T: ?Sized> {
 187     ptr: Shared<RcBox<T>>,
 188 }
 189
 190 #[stable(feature = "rust1", since = "1.0.0")]
 191 impl<T: ?Sized> !marker::Send for Rc<T> {}
 192 #[stable(feature = "rust1", since = "1.0.0")]
 193 impl<T: ?Sized> !marker::Sync for Rc<T> {}
 194
 195 #[unstable(feature = "coerce_unsized", issue = "27732")]
 196 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Rc<U>> for Rc<T> {}
 197
 198 impl<T> Rc<T> {
 199     /// Constructs a new `Rc<T>`.
 200     ///
 201     /// # Examples
 202     ///
 203     /// ```
 204     /// use std::rc::Rc;
 205     ///
 206     /// let five = Rc::new(5);
 207     /// ```
 208     #[stable(feature = "rust1", since = "1.0.0")]
 209     pub fn new(value: T) -> Rc<T> {
 210         unsafe {
 211             Rc {
 212                 // there is an implicit weak pointer owned by all the strong
 213                 // pointers, which ensures that the weak destructor never frees
 214                 // the allocation while the strong destructor is running, even
 215                 // if the weak pointer is stored inside the strong one.
 216                 ptr: Shared::new(Box::into_raw(box RcBox {
 217                     strong: Cell::new(1),
 218                     weak: Cell::new(1),
 219                     value: value,
 220                 })),
 221             }
 222         }
 223     }
 224
 225     /// Unwraps the contained value if the `Rc<T>` has exactly one strong reference.
 226     ///
 227     /// Otherwise, an `Err` is returned with the same `Rc<T>`.
 228     ///
 229     /// This will succeed even if there are outstanding weak references.
 230     ///
 231     /// # Examples
 232     ///
 233     /// ```
 234     /// use std::rc::Rc;
 235     ///
 236     /// let x = Rc::new(3);
 237     /// assert_eq!(Rc::try_unwrap(x), Ok(3));
 238     ///
 239     /// let x = Rc::new(4);
 240     /// let _y = x.clone();
 241     /// assert_eq!(Rc::try_unwrap(x), Err(Rc::new(4)));
 242     /// ```
 243     #[inline]
 244     #[stable(feature = "rc_unique", since = "1.4.0")]
 245     pub fn try_unwrap(this: Self) -> Result<T, Self> {
 246         if Rc::would_unwrap(&this) {
 247             unsafe {
 248                 let val = ptr::read(&*this); // copy the contained object
 249
 250                 // Indicate to Weaks that they can't be promoted by decrememting
 251                 // the strong count, and then remove the implicit "strong weak"
 252                 // pointer while also handling drop logic by just crafting a
 253                 // fake Weak.
 254                 this.dec_strong();
 255                 let _weak = Weak { ptr: this.ptr };
 256                 forget(this);
 257                 Ok(val)
 258             }
 259         } else {
 260             Err(this)
 261         }
 262     }
 263
 264     /// Checks if `Rc::try_unwrap` would return `Ok`.
 265     #[unstable(feature = "rc_would_unwrap",
 266                reason = "just added for niche usecase",
 267                issue = "28356")]
 268     pub fn would_unwrap(this: &Self) -> bool {
 269         Rc::strong_count(&this) == 1
 270     }
 271 }
 272
 273 impl<T: ?Sized> Rc<T> {
 274     /// Downgrades the `Rc<T>` to a `Weak<T>` reference.
 275     ///
 276     /// # Examples
 277     ///
 278     /// ```
 279     /// use std::rc::Rc;
 280     ///
 281     /// let five = Rc::new(5);
 282     ///
 283     /// let weak_five = Rc::downgrade(&five);
 284     /// ```
 285     #[stable(feature = "rc_weak", since = "1.4.0")]
 286     pub fn downgrade(this: &Self) -> Weak<T> {
 287         this.inc_weak();
 288         Weak { ptr: this.ptr }
 289     }
 290
 291     /// Get the number of weak references to this value.
 292     #[inline]
 293     #[unstable(feature = "rc_counts", reason = "not clearly useful",
 294                issue = "28356")]
 295     pub fn weak_count(this: &Self) -> usize {
 296         this.weak() - 1
 297     }
 298
 299     /// Get the number of strong references to this value.
 300     #[inline]
 301     #[unstable(feature = "rc_counts", reason = "not clearly useful",
 302                issue = "28356")]
 303     pub fn strong_count(this: &Self) -> usize {
 304         this.strong()
 305     }
 306
 307     /// Returns true if there are no other `Rc` or `Weak<T>` values that share
 308     /// the same inner value.
 309     ///
 310     /// # Examples
 311     ///
 312     /// ```
 313     /// #![feature(rc_counts)]
 314     ///
 315     /// use std::rc::Rc;
 316     ///
 317     /// let five = Rc::new(5);
 318     ///
 319     /// assert!(Rc::is_unique(&five));
 320     /// ```
 321     #[inline]
 322     #[unstable(feature = "rc_counts", reason = "uniqueness has unclear meaning",
 323                issue = "28356")]
 324     pub fn is_unique(this: &Self) -> bool {
 325         Rc::weak_count(this) == 0 && Rc::strong_count(this) == 1
 326     }
 327
 328     /// Returns a mutable reference to the contained value if the `Rc<T>` has
 329     /// one strong reference and no weak references.
 330     ///
 331     /// Returns `None` if the `Rc<T>` is not unique.
 332     ///
 333     /// # Examples
 334     ///
 335     /// ```
 336     /// use std::rc::Rc;
 337     ///
 338     /// let mut x = Rc::new(3);
 339     /// *Rc::get_mut(&mut x).unwrap() = 4;
 340     /// assert_eq!(*x, 4);
 341     ///
 342     /// let _y = x.clone();
 343     /// assert!(Rc::get_mut(&mut x).is_none());
 344     /// ```
 345     #[inline]
 346     #[stable(feature = "rc_unique", since = "1.4.0")]
 347     pub fn get_mut(this: &mut Self) -> Option<&mut T> {
 348         if Rc::is_unique(this) {
 349             let inner = unsafe { &mut **this.ptr };
 350             Some(&mut inner.value)
 351         } else {
 352             None
 353         }
 354     }
 355 }
 356
 357 impl<T: Clone> Rc<T> {
 358     /// Make a mutable reference into the given `Rc<T>` by cloning the inner
 359     /// data if the `Rc<T>` doesn't have one strong reference and no weak
 360     /// references.
 361     ///
 362     /// This is also referred to as a copy-on-write.
 363     ///
 364     /// # Examples
 365     ///
 366     /// ```
 367     /// use std::rc::Rc;
 368     ///
 369     /// let mut data = Rc::new(5);
 370     ///
 371     /// *Rc::make_mut(&mut data) += 1;             // Won't clone anything
 372     /// let mut other_data = data.clone(); // Won't clone inner data
 373     /// *Rc::make_mut(&mut data) += 1;             // Clones inner data
 374     /// *Rc::make_mut(&mut data) += 1;             // Won't clone anything
 375     /// *Rc::make_mut(&mut other_data) *= 2;       // Won't clone anything
 376     ///
 377     /// // Note: data and other_data now point to different numbers
 378     /// assert_eq!(*data, 8);
 379     /// assert_eq!(*other_data, 12);
 380     ///
 381     /// ```
 382     #[inline]
 383     #[stable(feature = "rc_unique", since = "1.4.0")]
 384     pub fn make_mut(this: &mut Self) -> &mut T {
 385         if Rc::strong_count(this) != 1 {
 386             // Gotta clone the data, there are other Rcs
 387             *this = Rc::new((**this).clone())
 388         } else if Rc::weak_count(this) != 0 {
 389             // Can just steal the data, all that's left is Weaks
 390             unsafe {
 391                 let mut swap = Rc::new(ptr::read(&(**this.ptr).value));
 392                 mem::swap(this, &mut swap);
 393                 swap.dec_strong();
 394                 // Remove implicit strong-weak ref (no need to craft a fake
 395                 // Weak here -- we know other Weaks can clean up for us)
 396                 swap.dec_weak();
 397                 forget(swap);
 398             }
 399         }
 400         // This unsafety is ok because we're guaranteed that the pointer
 401         // returned is the *only* pointer that will ever be returned to T. Our
 402         // reference count is guaranteed to be 1 at this point, and we required
 403         // the `Rc<T>` itself to be `mut`, so we're returning the only possible
 404         // reference to the inner value.
 405         let inner = unsafe { &mut **this.ptr };
 406         &mut inner.value
 407     }
 408 }
 409
 410 #[stable(feature = "rust1", since = "1.0.0")]
 411 impl<T: ?Sized> Deref for Rc<T> {
 412     type Target = T;
 413
 414     #[inline(always)]
 415     fn deref(&self) -> &T {
 416         &self.inner().value
 417     }
 418 }
 419
 420 #[stable(feature = "rust1", since = "1.0.0")]
 421 impl<T: ?Sized> Drop for Rc<T> {
 422     /// Drops the `Rc<T>`.
 423     ///
 424     /// This will decrement the strong reference count. If the strong reference
 425     /// count becomes zero and the only other references are `Weak<T>` ones,
 426     /// `drop`s the inner value.
 427     ///
 428     /// # Examples
 429     ///
 430     /// ```
 431     /// use std::rc::Rc;
 432     ///
 433     /// {
 434     ///     let five = Rc::new(5);
 435     ///
 436     ///     // stuff
 437     ///
 438     ///     drop(five); // explicit drop
 439     /// }
 440     /// {
 441     ///     let five = Rc::new(5);
 442     ///
 443     ///     // stuff
 444     ///
 445     /// } // implicit drop
 446     /// ```
 447     #[unsafe_destructor_blind_to_params]
 448     fn drop(&mut self) {
 449         unsafe {
 450             let ptr = *self.ptr;
 451             let thin = ptr as *const ();
 452
 453             if thin as usize != mem::POST_DROP_USIZE {
 454                 self.dec_strong();
 455                 if self.strong() == 0 {
 456                     // destroy the contained object
 457                     ptr::drop_in_place(&mut (*ptr).value);
 458
 459                     // remove the implicit "strong weak" pointer now that we've
 460                     // destroyed the contents.
 461                     self.dec_weak();
 462
 463                     if self.weak() == 0 {
 464                         deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr))
 465                     }
 466                 }
 467             }
 468         }
 469     }
 470 }
 471
 472 #[stable(feature = "rust1", since = "1.0.0")]
 473 impl<T: ?Sized> Clone for Rc<T> {
 474     /// Makes a clone of the `Rc<T>`.
 475     ///
 476     /// When you clone an `Rc<T>`, it will create another pointer to the data and
 477     /// increase the strong reference counter.
 478     ///
 479     /// # Examples
 480     ///
 481     /// ```
 482     /// use std::rc::Rc;
 483     ///
 484     /// let five = Rc::new(5);
 485     ///
 486     /// five.clone();
 487     /// ```
 488     #[inline]
 489     fn clone(&self) -> Rc<T> {
 490         self.inc_strong();
 491         Rc { ptr: self.ptr }
 492     }
 493 }
 494
 495 #[stable(feature = "rust1", since = "1.0.0")]
 496 impl<T: Default> Default for Rc<T> {
 497     /// Creates a new `Rc<T>`, with the `Default` value for `T`.
 498     ///
 499     /// # Examples
 500     ///
 501     /// ```
 502     /// use std::rc::Rc;
 503     ///
 504     /// let x: Rc<i32> = Default::default();
 505     /// ```
 506     #[inline]
 507     fn default() -> Rc<T> {
 508         Rc::new(Default::default())
 509     }
 510 }
 511
 512 #[stable(feature = "rust1", since = "1.0.0")]
 513 impl<T: ?Sized + PartialEq> PartialEq for Rc<T> {
 514     /// Equality for two `Rc<T>`s.
 515     ///
 516     /// Two `Rc<T>`s are equal if their inner value are equal.
 517     ///
 518     /// # Examples
 519     ///
 520     /// ```
 521     /// use std::rc::Rc;
 522     ///
 523     /// let five = Rc::new(5);
 524     ///
 525     /// five == Rc::new(5);
 526     /// ```
 527     #[inline(always)]
 528     fn eq(&self, other: &Rc<T>) -> bool {
 529         **self == **other
 530     }
 531
 532     /// Inequality for two `Rc<T>`s.
 533     ///
 534     /// Two `Rc<T>`s are unequal if their inner value are unequal.
 535     ///
 536     /// # Examples
 537     ///
 538     /// ```
 539     /// use std::rc::Rc;
 540     ///
 541     /// let five = Rc::new(5);
 542     ///
 543     /// five != Rc::new(5);
 544     /// ```
 545     #[inline(always)]
 546     fn ne(&self, other: &Rc<T>) -> bool {
 547         **self != **other
 548     }
 549 }
 550
 551 #[stable(feature = "rust1", since = "1.0.0")]
 552 impl<T: ?Sized + Eq> Eq for Rc<T> {}
 553
 554 #[stable(feature = "rust1", since = "1.0.0")]
 555 impl<T: ?Sized + PartialOrd> PartialOrd for Rc<T> {
 556     /// Partial comparison for two `Rc<T>`s.
 557     ///
 558     /// The two are compared by calling `partial_cmp()` on their inner values.
 559     ///
 560     /// # Examples
 561     ///
 562     /// ```
 563     /// use std::rc::Rc;
 564     ///
 565     /// let five = Rc::new(5);
 566     ///
 567     /// five.partial_cmp(&Rc::new(5));
 568     /// ```
 569     #[inline(always)]
 570     fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
 571         (**self).partial_cmp(&**other)
 572     }
 573
 574     /// Less-than comparison for two `Rc<T>`s.
 575     ///
 576     /// The two are compared by calling `<` on their inner values.
 577     ///
 578     /// # Examples
 579     ///
 580     /// ```
 581     /// use std::rc::Rc;
 582     ///
 583     /// let five = Rc::new(5);
 584     ///
 585     /// five < Rc::new(5);
 586     /// ```
 587     #[inline(always)]
 588     fn lt(&self, other: &Rc<T>) -> bool {
 589         **self < **other
 590     }
 591
 592     /// 'Less-than or equal to' comparison for two `Rc<T>`s.
 593     ///
 594     /// The two are compared by calling `<=` on their inner values.
 595     ///
 596     /// # Examples
 597     ///
 598     /// ```
 599     /// use std::rc::Rc;
 600     ///
 601     /// let five = Rc::new(5);
 602     ///
 603     /// five <= Rc::new(5);
 604     /// ```
 605     #[inline(always)]
 606     fn le(&self, other: &Rc<T>) -> bool {
 607         **self <= **other
 608     }
 609
 610     /// Greater-than comparison for two `Rc<T>`s.
 611     ///
 612     /// The two are compared by calling `>` on their inner values.
 613     ///
 614     /// # Examples
 615     ///
 616     /// ```
 617     /// use std::rc::Rc;
 618     ///
 619     /// let five = Rc::new(5);
 620     ///
 621     /// five > Rc::new(5);
 622     /// ```
 623     #[inline(always)]
 624     fn gt(&self, other: &Rc<T>) -> bool {
 625         **self > **other
 626     }
 627
 628     /// 'Greater-than or equal to' comparison for two `Rc<T>`s.
 629     ///
 630     /// The two are compared by calling `>=` on their inner values.
 631     ///
 632     /// # Examples
 633     ///
 634     /// ```
 635     /// use std::rc::Rc;
 636     ///
 637     /// let five = Rc::new(5);
 638     ///
 639     /// five >= Rc::new(5);
 640     /// ```
 641     #[inline(always)]
 642     fn ge(&self, other: &Rc<T>) -> bool {
 643         **self >= **other
 644     }
 645 }
 646
 647 #[stable(feature = "rust1", since = "1.0.0")]
 648 impl<T: ?Sized + Ord> Ord for Rc<T> {
 649     /// Comparison for two `Rc<T>`s.
 650     ///
 651     /// The two are compared by calling `cmp()` on their inner values.
 652     ///
 653     /// # Examples
 654     ///
 655     /// ```
 656     /// use std::rc::Rc;
 657     ///
 658     /// let five = Rc::new(5);
 659     ///
 660     /// five.partial_cmp(&Rc::new(5));
 661     /// ```
 662     #[inline]
 663     fn cmp(&self, other: &Rc<T>) -> Ordering {
 664         (**self).cmp(&**other)
 665     }
 666 }
 667
 668 #[stable(feature = "rust1", since = "1.0.0")]
 669 impl<T: ?Sized + Hash> Hash for Rc<T> {
 670     fn hash<H: Hasher>(&self, state: &mut H) {
 671         (**self).hash(state);
 672     }
 673 }
 674
 675 #[stable(feature = "rust1", since = "1.0.0")]
 676 impl<T: ?Sized + fmt::Display> fmt::Display for Rc<T> {
 677     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 678         fmt::Display::fmt(&**self, f)
 679     }
 680 }
 681
 682 #[stable(feature = "rust1", since = "1.0.0")]
 683 impl<T: ?Sized + fmt::Debug> fmt::Debug for Rc<T> {
 684     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 685         fmt::Debug::fmt(&**self, f)
 686     }
 687 }
 688
 689 #[stable(feature = "rust1", since = "1.0.0")]
 690 impl<T: ?Sized> fmt::Pointer for Rc<T> {
 691     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 692         fmt::Pointer::fmt(&*self.ptr, f)
 693     }
 694 }
 695
 696 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
 697 impl<T> From<T> for Rc<T> {
 698     fn from(t: T) -> Self {
 699         Rc::new(t)
 700     }
 701 }
 702
 703 /// A weak version of `Rc<T>`.
 704 ///
 705 /// Weak references do not count when determining if the inner value should be
 706 /// dropped.
 707 ///
 708 /// See the [module level documentation](./index.html) for more.
 709 #[unsafe_no_drop_flag]
 710 #[stable(feature = "rc_weak", since = "1.4.0")]
 711 pub struct Weak<T: ?Sized> {
 712     ptr: Shared<RcBox<T>>,
 713 }
 714
 715 #[stable(feature = "rc_weak", since = "1.4.0")]
 716 impl<T: ?Sized> !marker::Send for Weak<T> {}
 717 #[stable(feature = "rc_weak", since = "1.4.0")]
 718 impl<T: ?Sized> !marker::Sync for Weak<T> {}
 719
 720 #[unstable(feature = "coerce_unsized", issue = "27732")]
 721 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
 722
 723 impl<T: ?Sized> Weak<T> {
 724     /// Upgrades a weak reference to a strong reference.
 725     ///
 726     /// Upgrades the `Weak<T>` reference to an `Rc<T>`, if possible.
 727     ///
 728     /// Returns `None` if there were no strong references and the data was
 729     /// destroyed.
 730     ///
 731     /// # Examples
 732     ///
 733     /// ```
 734     /// use std::rc::Rc;
 735     ///
 736     /// let five = Rc::new(5);
 737     ///
 738     /// let weak_five = Rc::downgrade(&five);
 739     ///
 740     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
 741     /// ```
 742     #[stable(feature = "rc_weak", since = "1.4.0")]
 743     pub fn upgrade(&self) -> Option<Rc<T>> {
 744         if self.strong() == 0 {
 745             None
 746         } else {
 747             self.inc_strong();
 748             Some(Rc { ptr: self.ptr })
 749         }
 750     }
 751 }
 752
 753 #[stable(feature = "rc_weak", since = "1.4.0")]
 754 impl<T: ?Sized> Drop for Weak<T> {
 755     /// Drops the `Weak<T>`.
 756     ///
 757     /// This will decrement the weak reference count.
 758     ///
 759     /// # Examples
 760     ///
 761     /// ```
 762     /// use std::rc::Rc;
 763     ///
 764     /// {
 765     ///     let five = Rc::new(5);
 766     ///     let weak_five = Rc::downgrade(&five);
 767     ///
 768     ///     // stuff
 769     ///
 770     ///     drop(weak_five); // explicit drop
 771     /// }
 772     /// {
 773     ///     let five = Rc::new(5);
 774     ///     let weak_five = Rc::downgrade(&five);
 775     ///
 776     ///     // stuff
 777     ///
 778     /// } // implicit drop
 779     /// ```
 780     fn drop(&mut self) {
 781         unsafe {
 782             let ptr = *self.ptr;
 783             let thin = ptr as *const ();
 784
 785             if thin as usize != mem::POST_DROP_USIZE {
 786                 self.dec_weak();
 787                 // the weak count starts at 1, and will only go to zero if all
 788                 // the strong pointers have disappeared.
 789                 if self.weak() == 0 {
 790                     deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr))
 791                 }
 792             }
 793         }
 794     }
 795 }
 796
 797 #[stable(feature = "rc_weak", since = "1.4.0")]
 798 impl<T: ?Sized> Clone for Weak<T> {
 799     /// Makes a clone of the `Weak<T>`.
 800     ///
 801     /// This increases the weak reference count.
 802     ///
 803     /// # Examples
 804     ///
 805     /// ```
 806     /// use std::rc::Rc;
 807     ///
 808     /// let weak_five = Rc::downgrade(&Rc::new(5));
 809     ///
 810     /// weak_five.clone();
 811     /// ```
 812     #[inline]
 813     fn clone(&self) -> Weak<T> {
 814         self.inc_weak();
 815         Weak { ptr: self.ptr }
 816     }
 817 }
 818
 819 #[stable(feature = "rc_weak", since = "1.4.0")]
 820 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
 821     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 822         write!(f, "(Weak)")
 823     }
 824 }
 825
 826 impl<T> Weak<T> {
 827     /// Constructs a new `Weak<T>` without an accompanying instance of T.
 828     ///
 829     /// This allocates memory for T, but does not initialize it. Calling
 830     /// Weak<T>::upgrade() on the return value always gives None.
 831     ///
 832     /// # Examples
 833     ///
 834     /// ```
 835     /// #![feature(downgraded_weak)]
 836     ///
 837     /// use std::rc::Weak;
 838     ///
 839     /// let empty: Weak<i64> = Weak::new();
 840     /// ```
 841     #[unstable(feature = "downgraded_weak",
 842                reason = "recently added",
 843                issue="30425")]
 844     pub fn new() -> Weak<T> {
 845         unsafe {
 846             Weak {
 847                 ptr: Shared::new(Box::into_raw(box RcBox {
 848                     strong: Cell::new(0),
 849                     weak: Cell::new(1),
 850                     value: uninitialized(),
 851                 })),
 852             }
 853         }
 854     }
 855 }
 856
 857 // NOTE: We checked_add here to deal with mem::forget safety. In particular
 858 // if you mem::forget Rcs (or Weaks), the ref-count can overflow, and then
 859 // you can free the allocation while outstanding Rcs (or Weaks) exist.
 860 // We abort because this is such a degenerate scenario that we don't care about
 861 // what happens -- no real program should ever experience this.
 862 //
 863 // This should have negligible overhead since you don't actually need to
 864 // clone these much in Rust thanks to ownership and move-semantics.
 865
 866 #[doc(hidden)]
 867 trait RcBoxPtr<T: ?Sized> {
 868     fn inner(&self) -> &RcBox<T>;
 869
 870     #[inline]
 871     fn strong(&self) -> usize {
 872         self.inner().strong.get()
 873     }
 874
 875     #[inline]
 876     fn inc_strong(&self) {
 877         self.inner().strong.set(self.strong().checked_add(1).unwrap_or_else(|| unsafe { abort() }));
 878     }
 879
 880     #[inline]
 881     fn dec_strong(&self) {
 882         self.inner().strong.set(self.strong() - 1);
 883     }
 884
 885     #[inline]
 886     fn weak(&self) -> usize {
 887         self.inner().weak.get()
 888     }
 889
 890     #[inline]
 891     fn inc_weak(&self) {
 892         self.inner().weak.set(self.weak().checked_add(1).unwrap_or_else(|| unsafe { abort() }));
 893     }
 894
 895     #[inline]
 896     fn dec_weak(&self) {
 897         self.inner().weak.set(self.weak() - 1);
 898     }
 899 }
 900
 901 impl<T: ?Sized> RcBoxPtr<T> for Rc<T> {
 902     #[inline(always)]
 903     fn inner(&self) -> &RcBox<T> {
 904         unsafe {
 905             // Safe to assume this here, as if it weren't true, we'd be breaking
 906             // the contract anyway.
 907             // This allows the null check to be elided in the destructor if we
 908             // manipulated the reference count in the same function.
 909             assume(!(*(&self.ptr as *const _ as *const *const ())).is_null());
 910             &(**self.ptr)
 911         }
 912     }
 913 }
 914
 915 impl<T: ?Sized> RcBoxPtr<T> for Weak<T> {
 916     #[inline(always)]
 917     fn inner(&self) -> &RcBox<T> {
 918         unsafe {
 919             // Safe to assume this here, as if it weren't true, we'd be breaking
 920             // the contract anyway.
 921             // This allows the null check to be elided in the destructor if we
 922             // manipulated the reference count in the same function.
 923             assume(!(*(&self.ptr as *const _ as *const *const ())).is_null());
 924             &(**self.ptr)
 925         }
 926     }
 927 }
 928
 929 #[cfg(test)]
 930 mod tests {
 931     use super::{Rc, Weak};
 932     use std::boxed::Box;
 933     use std::cell::RefCell;
 934     use std::option::Option;
 935     use std::option::Option::{Some, None};
 936     use std::result::Result::{Err, Ok};
 937     use std::mem::drop;
 938     use std::clone::Clone;
 939     use std::convert::From;
 940
 941     #[test]
 942     fn test_clone() {
 943         let x = Rc::new(RefCell::new(5));
 944         let y = x.clone();
 945         *x.borrow_mut() = 20;
 946         assert_eq!(*y.borrow(), 20);
 947     }
 948
 949     #[test]
 950     fn test_simple() {
 951         let x = Rc::new(5);
 952         assert_eq!(*x, 5);
 953     }
 954
 955     #[test]
 956     fn test_simple_clone() {
 957         let x = Rc::new(5);
 958         let y = x.clone();
 959         assert_eq!(*x, 5);
 960         assert_eq!(*y, 5);
 961     }
 962
 963     #[test]
 964     fn test_destructor() {
 965         let x: Rc<Box<_>> = Rc::new(box 5);
 966         assert_eq!(**x, 5);
 967     }
 968
 969     #[test]
 970     fn test_live() {
 971         let x = Rc::new(5);
 972         let y = Rc::downgrade(&x);
 973         assert!(y.upgrade().is_some());
 974     }
 975
 976     #[test]
 977     fn test_dead() {
 978         let x = Rc::new(5);
 979         let y = Rc::downgrade(&x);
 980         drop(x);
 981         assert!(y.upgrade().is_none());
 982     }
 983
 984     #[test]
 985     fn weak_self_cyclic() {
 986         struct Cycle {
 987             x: RefCell<Option<Weak<Cycle>>>,
 988         }
 989
 990         let a = Rc::new(Cycle { x: RefCell::new(None) });
 991         let b = Rc::downgrade(&a.clone());
 992         *a.x.borrow_mut() = Some(b);
 993
 994         // hopefully we don't double-free (or leak)...
 995     }
 996
 997     #[test]
 998     fn is_unique() {
 999         let x = Rc::new(3);
1000         assert!(Rc::is_unique(&x));
1001         let y = x.clone();
1002         assert!(!Rc::is_unique(&x));
1003         drop(y);
1004         assert!(Rc::is_unique(&x));
1005         let w = Rc::downgrade(&x);
1006         assert!(!Rc::is_unique(&x));
1007         drop(w);
1008         assert!(Rc::is_unique(&x));
1009     }
1010
1011     #[test]
1012     fn test_strong_count() {
1013         let a = Rc::new(0);
1014         assert!(Rc::strong_count(&a) == 1);
1015         let w = Rc::downgrade(&a);
1016         assert!(Rc::strong_count(&a) == 1);
1017         let b = w.upgrade().expect("upgrade of live rc failed");
1018         assert!(Rc::strong_count(&b) == 2);
1019         assert!(Rc::strong_count(&a) == 2);
1020         drop(w);
1021         drop(a);
1022         assert!(Rc::strong_count(&b) == 1);
1023         let c = b.clone();
1024         assert!(Rc::strong_count(&b) == 2);
1025         assert!(Rc::strong_count(&c) == 2);
1026     }
1027
1028     #[test]
1029     fn test_weak_count() {
1030         let a = Rc::new(0);
1031         assert!(Rc::strong_count(&a) == 1);
1032         assert!(Rc::weak_count(&a) == 0);
1033         let w = Rc::downgrade(&a);
1034         assert!(Rc::strong_count(&a) == 1);
1035         assert!(Rc::weak_count(&a) == 1);
1036         drop(w);
1037         assert!(Rc::strong_count(&a) == 1);
1038         assert!(Rc::weak_count(&a) == 0);
1039         let c = a.clone();
1040         assert!(Rc::strong_count(&a) == 2);
1041         assert!(Rc::weak_count(&a) == 0);
1042         drop(c);
1043     }
1044
1045     #[test]
1046     fn try_unwrap() {
1047         let x = Rc::new(3);
1048         assert_eq!(Rc::try_unwrap(x), Ok(3));
1049         let x = Rc::new(4);
1050         let _y = x.clone();
1051         assert_eq!(Rc::try_unwrap(x), Err(Rc::new(4)));
1052         let x = Rc::new(5);
1053         let _w = Rc::downgrade(&x);
1054         assert_eq!(Rc::try_unwrap(x), Ok(5));
1055     }
1056
1057     #[test]
1058     fn get_mut() {
1059         let mut x = Rc::new(3);
1060         *Rc::get_mut(&mut x).unwrap() = 4;
1061         assert_eq!(*x, 4);
1062         let y = x.clone();
1063         assert!(Rc::get_mut(&mut x).is_none());
1064         drop(y);
1065         assert!(Rc::get_mut(&mut x).is_some());
1066         let _w = Rc::downgrade(&x);
1067         assert!(Rc::get_mut(&mut x).is_none());
1068     }
1069
1070     #[test]
1071     fn test_cowrc_clone_make_unique() {
1072         let mut cow0 = Rc::new(75);
1073         let mut cow1 = cow0.clone();
1074         let mut cow2 = cow1.clone();
1075
1076         assert!(75 == *Rc::make_mut(&mut cow0));
1077         assert!(75 == *Rc::make_mut(&mut cow1));
1078         assert!(75 == *Rc::make_mut(&mut cow2));
1079
1080         *Rc::make_mut(&mut cow0) += 1;
1081         *Rc::make_mut(&mut cow1) += 2;
1082         *Rc::make_mut(&mut cow2) += 3;
1083
1084         assert!(76 == *cow0);
1085         assert!(77 == *cow1);
1086         assert!(78 == *cow2);
1087
1088         // none should point to the same backing memory
1089         assert!(*cow0 != *cow1);
1090         assert!(*cow0 != *cow2);
1091         assert!(*cow1 != *cow2);
1092     }
1093
1094     #[test]
1095     fn test_cowrc_clone_unique2() {
1096         let mut cow0 = Rc::new(75);
1097         let cow1 = cow0.clone();
1098         let cow2 = cow1.clone();
1099
1100         assert!(75 == *cow0);
1101         assert!(75 == *cow1);
1102         assert!(75 == *cow2);
1103
1104         *Rc::make_mut(&mut cow0) += 1;
1105
1106         assert!(76 == *cow0);
1107         assert!(75 == *cow1);
1108         assert!(75 == *cow2);
1109
1110         // cow1 and cow2 should share the same contents
1111         // cow0 should have a unique reference
1112         assert!(*cow0 != *cow1);
1113         assert!(*cow0 != *cow2);
1114         assert!(*cow1 == *cow2);
1115     }
1116
1117     #[test]
1118     fn test_cowrc_clone_weak() {
1119         let mut cow0 = Rc::new(75);
1120         let cow1_weak = Rc::downgrade(&cow0);
1121
1122         assert!(75 == *cow0);
1123         assert!(75 == *cow1_weak.upgrade().unwrap());
1124
1125         *Rc::make_mut(&mut cow0) += 1;
1126
1127         assert!(76 == *cow0);
1128         assert!(cow1_weak.upgrade().is_none());
1129     }
1130
1131     #[test]
1132     fn test_show() {
1133         let foo = Rc::new(75);
1134         assert_eq!(format!("{:?}", foo), "75");
1135     }
1136
1137     #[test]
1138     fn test_unsized() {
1139         let foo: Rc<[i32]> = Rc::new([1, 2, 3]);
1140         assert_eq!(foo, foo.clone());
1141     }
1142
1143     #[test]
1144     fn test_from_owned() {
1145         let foo = 123;
1146         let foo_rc = Rc::from(foo);
1147         assert!(123 == *foo_rc);
1148     }
1149
1150     #[test]
1151     fn test_new_weak() {
1152         let foo: Weak<usize> = Weak::new();
1153         assert!(foo.upgrade().is_none());
1154     }
1155 }
1156
1157 #[stable(feature = "rust1", since = "1.0.0")]
1158 impl<T: ?Sized> borrow::Borrow<T> for Rc<T> {
1159     fn borrow(&self) -> &T {
1160         &**self
1161     }
1162 }
1163
1164 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1165 impl<T: ?Sized> AsRef<T> for Rc<T> {
1166     fn as_ref(&self) -> &T {
1167         &**self
1168     }
1169 }