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