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