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