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