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