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