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