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