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