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