src/liballoc/rc.rs

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