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 impl<S: hash::Hasher, T: Hash<S>> Hash<S> for Rc<T> {
 690     #[inline]
 691     fn hash(&self, state: &mut S) {
 692         (**self).hash(state);
 693     }
 694 }
 695
 696 #[unstable = "Show is experimental."]
 697 impl<T: fmt::Show> fmt::Show for Rc<T> {
 698     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 699         write!(f, "Rc({:?})", **self)
 700     }
 701 }
 702
 703 #[stable]
 704 impl<T: fmt::String> fmt::String for Rc<T> {
 705     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 706         fmt::String::fmt(&**self, f)
 707     }
 708 }
 709
 710 /// A weak version of `Rc<T>`.
 711 ///
 712 /// Weak references do not count when determining if the inner value should be dropped.
 713 ///
 714 /// See the [module level documentation](../index.html) for more.
 715 #[unsafe_no_drop_flag]
 716 #[unstable = "Weak pointers may not belong in this module."]
 717 #[cfg(stage0)] // NOTE remove impl after next snapshot
 718 pub struct Weak<T> {
 719     // FIXME #12808: strange names to try to avoid interfering with
 720     // field accesses of the contained type via Deref
 721     _ptr: NonZero<*mut RcBox<T>>,
 722     _nosend: marker::NoSend,
 723     _noshare: marker::NoSync
 724 }
 725
 726 /// A weak version of `Rc<T>`.
 727 ///
 728 /// Weak references do not count when determining if the inner value should be dropped.
 729 ///
 730 /// See the [module level documentation](../index.html) for more.
 731 #[unsafe_no_drop_flag]
 732 #[unstable = "Weak pointers may not belong in this module."]
 733 #[cfg(not(stage0))] // NOTE remove cfg after next snapshot
 734 pub struct Weak<T> {
 735     // FIXME #12808: strange names to try to avoid interfering with
 736     // field accesses of the contained type via Deref
 737     _ptr: NonZero<*mut RcBox<T>>,
 738 }
 739
 740 #[cfg(not(stage0))] // NOTE remove cfg after next snapshot
 741 #[allow(unstable)]
 742 impl<T> !marker::Send for Weak<T> {}
 743
 744 #[cfg(not(stage0))] // NOTE remove cfg after next snapshot
 745 #[allow(unstable)]
 746 impl<T> !marker::Sync for Weak<T> {}
 747
 748
 749 #[unstable = "Weak pointers may not belong in this module."]
 750 impl<T> Weak<T> {
 751     /// Upgrades a weak reference to a strong reference.
 752     ///
 753     /// Upgrades the `Weak<T>` reference to an `Rc<T>`, if possible.
 754     ///
 755     /// Returns `None` if there were no strong references and the data was destroyed.
 756     ///
 757     /// # Examples
 758     ///
 759     /// ```
 760     /// use std::rc::Rc;
 761     ///
 762     /// let five = Rc::new(5i);
 763     ///
 764     /// let weak_five = five.downgrade();
 765     ///
 766     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
 767     /// ```
 768     #[cfg(stage0)] // NOTE remove after next snapshot
 769     pub fn upgrade(&self) -> Option<Rc<T>> {
 770         if self.strong() == 0 {
 771             None
 772         } else {
 773             self.inc_strong();
 774             Some(Rc { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoSync })
 775         }
 776     }
 777
 778     /// Upgrades a weak reference to a strong reference.
 779     ///
 780     /// Upgrades the `Weak<T>` reference to an `Rc<T>`, if possible.
 781     ///
 782     /// Returns `None` if there were no strong references and the data was destroyed.
 783     ///
 784     /// # Examples
 785     ///
 786     /// ```
 787     /// use std::rc::Rc;
 788     ///
 789     /// let five = Rc::new(5i);
 790     ///
 791     /// let weak_five = five.downgrade();
 792     ///
 793     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
 794     /// ```
 795     #[cfg(not(stage0))] // NOTE remove cfg after next snapshot
 796     pub fn upgrade(&self) -> Option<Rc<T>> {
 797         if self.strong() == 0 {
 798             None
 799         } else {
 800             self.inc_strong();
 801             Some(Rc { _ptr: self._ptr })
 802         }
 803     }
 804 }
 805
 806 #[unsafe_destructor]
 807 #[stable]
 808 impl<T> Drop for Weak<T> {
 809     /// Drops the `Weak<T>`.
 810     ///
 811     /// This will decrement the weak reference count.
 812     ///
 813     /// # Examples
 814     ///
 815     /// ```
 816     /// use std::rc::Rc;
 817     ///
 818     /// {
 819     ///     let five = Rc::new(5i);
 820     ///     let weak_five = five.downgrade();
 821     ///
 822     ///     // stuff
 823     ///
 824     ///     drop(weak_five); // explict drop
 825     /// }
 826     /// {
 827     ///     let five = Rc::new(5i);
 828     ///     let weak_five = five.downgrade();
 829     ///
 830     ///     // stuff
 831     ///
 832     /// } // implicit drop
 833     /// ```
 834     fn drop(&mut self) {
 835         unsafe {
 836             let ptr = *self._ptr;
 837             if !ptr.is_null() {
 838                 self.dec_weak();
 839                 // the weak count starts at 1, and will only go to zero if all the strong pointers
 840                 // have disappeared.
 841                 if self.weak() == 0 {
 842                     deallocate(ptr as *mut u8, size_of::<RcBox<T>>(),
 843                                min_align_of::<RcBox<T>>())
 844                 }
 845             }
 846         }
 847     }
 848 }
 849
 850 #[unstable = "Weak pointers may not belong in this module."]
 851 impl<T> Clone for Weak<T> {
 852     /// Makes a clone of the `Weak<T>`.
 853     ///
 854     /// This increases the weak reference count.
 855     ///
 856     /// # Examples
 857     ///
 858     /// ```
 859     /// use std::rc::Rc;
 860     ///
 861     /// let weak_five = Rc::new(5i).downgrade();
 862     ///
 863     /// weak_five.clone();
 864     /// ```
 865     #[inline]
 866     #[cfg(stage0)] // NOTE remove after next snapshot
 867     fn clone(&self) -> Weak<T> {
 868         self.inc_weak();
 869         Weak { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoSync }
 870     }
 871
 872     /// Makes a clone of the `Weak<T>`.
 873     ///
 874     /// This increases the weak reference count.
 875     ///
 876     /// # Examples
 877     ///
 878     /// ```
 879     /// use std::rc::Rc;
 880     ///
 881     /// let weak_five = Rc::new(5i).downgrade();
 882     ///
 883     /// weak_five.clone();
 884     /// ```
 885     #[inline]
 886     #[cfg(not(stage0))] // NOTE remove cfg after next snapshot
 887     fn clone(&self) -> Weak<T> {
 888         self.inc_weak();
 889         Weak { _ptr: self._ptr }
 890     }
 891 }
 892
 893 #[unstable = "Show is experimental."]
 894 impl<T: fmt::Show> fmt::Show for Weak<T> {
 895     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 896         write!(f, "(Weak)")
 897     }
 898 }
 899
 900 #[doc(hidden)]
 901 trait RcBoxPtr<T> {
 902     fn inner(&self) -> &RcBox<T>;
 903
 904     #[inline]
 905     fn strong(&self) -> uint { self.inner().strong.get() }
 906
 907     #[inline]
 908     fn inc_strong(&self) { self.inner().strong.set(self.strong() + 1); }
 909
 910     #[inline]
 911     fn dec_strong(&self) { self.inner().strong.set(self.strong() - 1); }
 912
 913     #[inline]
 914     fn weak(&self) -> uint { self.inner().weak.get() }
 915
 916     #[inline]
 917     fn inc_weak(&self) { self.inner().weak.set(self.weak() + 1); }
 918
 919     #[inline]
 920     fn dec_weak(&self) { self.inner().weak.set(self.weak() - 1); }
 921 }
 922
 923 impl<T> RcBoxPtr<T> for Rc<T> {
 924     #[inline(always)]
 925     fn inner(&self) -> &RcBox<T> { unsafe { &(**self._ptr) } }
 926 }
 927
 928 impl<T> RcBoxPtr<T> for Weak<T> {
 929     #[inline(always)]
 930     fn inner(&self) -> &RcBox<T> { unsafe { &(**self._ptr) } }
 931 }
 932
 933 #[cfg(test)]
 934 #[allow(unstable)]
 935 mod tests {
 936     use super::{Rc, Weak, weak_count, strong_count};
 937     use std::cell::RefCell;
 938     use std::option::Option;
 939     use std::option::Option::{Some, None};
 940     use std::result::Result::{Err, Ok};
 941     use std::mem::drop;
 942     use std::clone::Clone;
 943
 944     #[test]
 945     fn test_clone() {
 946         let x = Rc::new(RefCell::new(5i));
 947         let y = x.clone();
 948         *x.borrow_mut() = 20;
 949         assert_eq!(*y.borrow(), 20);
 950     }
 951
 952     #[test]
 953     fn test_simple() {
 954         let x = Rc::new(5i);
 955         assert_eq!(*x, 5);
 956     }
 957
 958     #[test]
 959     fn test_simple_clone() {
 960         let x = Rc::new(5i);
 961         let y = x.clone();
 962         assert_eq!(*x, 5);
 963         assert_eq!(*y, 5);
 964     }
 965
 966     #[test]
 967     fn test_destructor() {
 968         let x = Rc::new(box 5i);
 969         assert_eq!(**x, 5);
 970     }
 971
 972     #[test]
 973     fn test_live() {
 974         let x = Rc::new(5i);
 975         let y = x.downgrade();
 976         assert!(y.upgrade().is_some());
 977     }
 978
 979     #[test]
 980     fn test_dead() {
 981         let x = Rc::new(5i);
 982         let y = x.downgrade();
 983         drop(x);
 984         assert!(y.upgrade().is_none());
 985     }
 986
 987     #[test]
 988     fn weak_self_cyclic() {
 989         struct Cycle {
 990             x: RefCell<Option<Weak<Cycle>>>
 991         }
 992
 993         let a = Rc::new(Cycle { x: RefCell::new(None) });
 994         let b = a.clone().downgrade();
 995         *a.x.borrow_mut() = Some(b);
 996
 997         // hopefully we don't double-free (or leak)...
 998     }
 999
1000     #[test]
1001     fn is_unique() {
1002         let x = Rc::new(3u);
1003         assert!(super::is_unique(&x));
1004         let y = x.clone();
1005         assert!(!super::is_unique(&x));
1006         drop(y);
1007         assert!(super::is_unique(&x));
1008         let w = x.downgrade();
1009         assert!(!super::is_unique(&x));
1010         drop(w);
1011         assert!(super::is_unique(&x));
1012     }
1013
1014     #[test]
1015     fn test_strong_count() {
1016         let a = Rc::new(0u32);
1017         assert!(strong_count(&a) == 1);
1018         let w = a.downgrade();
1019         assert!(strong_count(&a) == 1);
1020         let b = w.upgrade().expect("upgrade of live rc failed");
1021         assert!(strong_count(&b) == 2);
1022         assert!(strong_count(&a) == 2);
1023         drop(w);
1024         drop(a);
1025         assert!(strong_count(&b) == 1);
1026         let c = b.clone();
1027         assert!(strong_count(&b) == 2);
1028         assert!(strong_count(&c) == 2);
1029     }
1030
1031     #[test]
1032     fn test_weak_count() {
1033         let a = Rc::new(0u32);
1034         assert!(strong_count(&a) == 1);
1035         assert!(weak_count(&a) == 0);
1036         let w = a.downgrade();
1037         assert!(strong_count(&a) == 1);
1038         assert!(weak_count(&a) == 1);
1039         drop(w);
1040         assert!(strong_count(&a) == 1);
1041         assert!(weak_count(&a) == 0);
1042         let c = a.clone();
1043         assert!(strong_count(&a) == 2);
1044         assert!(weak_count(&a) == 0);
1045         drop(c);
1046     }
1047
1048     #[test]
1049     fn try_unwrap() {
1050         let x = Rc::new(3u);
1051         assert_eq!(super::try_unwrap(x), Ok(3u));
1052         let x = Rc::new(4u);
1053         let _y = x.clone();
1054         assert_eq!(super::try_unwrap(x), Err(Rc::new(4u)));
1055         let x = Rc::new(5u);
1056         let _w = x.downgrade();
1057         assert_eq!(super::try_unwrap(x), Err(Rc::new(5u)));
1058     }
1059
1060     #[test]
1061     fn get_mut() {
1062         let mut x = Rc::new(3u);
1063         *super::get_mut(&mut x).unwrap() = 4u;
1064         assert_eq!(*x, 4u);
1065         let y = x.clone();
1066         assert!(super::get_mut(&mut x).is_none());
1067         drop(y);
1068         assert!(super::get_mut(&mut x).is_some());
1069         let _w = x.downgrade();
1070         assert!(super::get_mut(&mut x).is_none());
1071     }
1072
1073     #[test]
1074     fn test_cowrc_clone_make_unique() {
1075         let mut cow0 = Rc::new(75u);
1076         let mut cow1 = cow0.clone();
1077         let mut cow2 = cow1.clone();
1078
1079         assert!(75 == *cow0.make_unique());
1080         assert!(75 == *cow1.make_unique());
1081         assert!(75 == *cow2.make_unique());
1082
1083         *cow0.make_unique() += 1;
1084         *cow1.make_unique() += 2;
1085         *cow2.make_unique() += 3;
1086
1087         assert!(76 == *cow0);
1088         assert!(77 == *cow1);
1089         assert!(78 == *cow2);
1090
1091         // none should point to the same backing memory
1092         assert!(*cow0 != *cow1);
1093         assert!(*cow0 != *cow2);
1094         assert!(*cow1 != *cow2);
1095     }
1096
1097     #[test]
1098     fn test_cowrc_clone_unique2() {
1099         let mut cow0 = Rc::new(75u);
1100         let cow1 = cow0.clone();
1101         let cow2 = cow1.clone();
1102
1103         assert!(75 == *cow0);
1104         assert!(75 == *cow1);
1105         assert!(75 == *cow2);
1106
1107         *cow0.make_unique() += 1;
1108
1109         assert!(76 == *cow0);
1110         assert!(75 == *cow1);
1111         assert!(75 == *cow2);
1112
1113         // cow1 and cow2 should share the same contents
1114         // cow0 should have a unique reference
1115         assert!(*cow0 != *cow1);
1116         assert!(*cow0 != *cow2);
1117         assert!(*cow1 == *cow2);
1118     }
1119
1120     #[test]
1121     fn test_cowrc_clone_weak() {
1122         let mut cow0 = Rc::new(75u);
1123         let cow1_weak = cow0.downgrade();
1124
1125         assert!(75 == *cow0);
1126         assert!(75 == *cow1_weak.upgrade().unwrap());
1127
1128         *cow0.make_unique() += 1;
1129
1130         assert!(76 == *cow0);
1131         assert!(cow1_weak.upgrade().is_none());
1132     }
1133
1134     #[test]
1135     fn test_show() {
1136         let foo = Rc::new(75u);
1137         assert!(format!("{:?}", foo) == "Rc(75u)")
1138     }
1139
1140 }