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