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