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