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