cactusref/
adopt.rs

1use core::ptr;
2
3use crate::link::Link;
4use crate::Rc;
5
6mod sealed {
7    use crate::Rc;
8
9    #[doc(hidden)]
10    pub trait Sealed {}
11
12    impl<T> Sealed for Rc<T> {}
13}
14
15/// Build a graph of linked [`Rc`] smart pointers to enable busting cycles on
16/// drop.
17///
18/// Calling [`adopt_unchecked`] builds an object graph which can be used by to
19/// detect cycles.
20///
21/// # Safety
22///
23/// Implementors of this trait must ensure that bookkeeping edges in the object
24/// graph is correct because these links are used to determine whether an `Rc`
25/// is reachable in `Rc`'s `Drop` implementation. Failure to properly bookkeep
26/// the object graph will result in *[undefined behavior]*.
27///
28/// Undefined behavior may include:
29///
30/// - Memory leaks.
31/// - Double-frees.
32/// - Dangling `Rc`s which will cause a use after free.
33///
34/// [`adopt_unchecked`]: Adopt::adopt_unchecked
35/// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
36pub unsafe trait Adopt: sealed::Sealed {
37    /// Perform bookkeeping to record that `this` has an owned reference to
38    /// `other`.
39    ///
40    /// Adoption is a one-way link, or a directed edge in the object graph which
41    /// means "`this` owns `other`".
42    ///
43    /// `adopt` can be called multiple times for a pair of `Rc`s. Each call to
44    /// `adopt` indicates that `this` owns one distinct clone of `other`.
45    ///
46    /// This is an associated function that needs to be used as
47    /// `Adopt::adopt_unchecked(...)`. A method would interfere with methods of the same
48    /// name on the contents of a `Rc` used through `Deref`.
49    ///
50    /// # Safety
51    ///
52    /// Callers must ensure that `this` owns a strong reference to `other`.
53    ///
54    /// Callers should call [`unadopt`] when `this` no longer holds a strong
55    /// reference to `other` to avoid memory leaks, but this is not required for
56    /// soundness.
57    ///
58    /// [`unadopt`]: Adopt::unadopt
59    unsafe fn adopt_unchecked(this: &Self, other: &Self);
60
61    /// Perform bookkeeping to record that `this` has removed an owned reference
62    /// to `other`.
63    ///
64    /// Adoption is a one-way link, or a directed edge in the object graph which
65    /// means "`this` owns `other`".
66    ///
67    /// This is an associated function that needs to be used as
68    /// `Adopt::unadopt(...)`. A method would interfere with methods of the same
69    /// name on the contents of a `Rc` used through `Deref`.
70    ///
71    /// # Memory Leaks
72    ///
73    /// Failure to call this function when removing an owned `Rc` from `this`
74    /// is safe, but may result in a memory leak.
75    fn unadopt(this: &Self, other: &Self);
76}
77
78/// Implementation of [`Adopt`] for [`Rc`] which enables `Rc`s to form a cycle
79/// of strong references that are reaped by `Rc`'s [`Drop`] implementation.
80unsafe impl<T> Adopt for Rc<T> {
81    /// Perform bookkeeping to record that `this` has an owned reference to
82    /// `other`.
83    ///
84    /// Adoption is a one-way link, or a directed edge in the object graph which
85    /// means "`this` owns `other`".
86    ///
87    /// `adopt` can be called multiple times for a pair of `Rc`s. Each call to
88    /// `adopt` indicates that `this` owns one distinct clone of `other`.
89    ///
90    /// This is an associated function that needs to be used as
91    /// `Rc::adopt_unchecked(...)`. A method would interfere with methods of the same
92    /// name on the contents of a `Rc` used through `Deref`.
93    ///
94    /// # Safety
95    ///
96    /// Callers must ensure that `this` owns a strong reference to `other`.
97    ///
98    /// Callers should call [`unadopt`] when `this` no longer holds a strong
99    /// reference to `other` to avoid memory leaks, but this is not required for
100    /// soundness.
101    ///
102    /// Calling `adopt` does not increment the strong count of `other`. Callers
103    /// must ensure that `other` has been cloned and stored in the `T` contained
104    /// by `this`.
105    ///
106    /// # Examples
107    ///
108    /// The following implements a self-referential array.
109    ///
110    /// ```rust
111    /// use cactusref::{Adopt, Rc};
112    /// use std::cell::RefCell;
113    ///
114    /// #[derive(Default)]
115    /// struct Array {
116    ///     buffer: Vec<Rc<RefCell<Self>>>,
117    /// }
118    ///
119    /// let array = Rc::new(RefCell::new(Array::default()));
120    /// for _ in 0..10 {
121    ///     let item = Rc::clone(&array);
122    ///     unsafe {
123    ///         Rc::adopt_unchecked(&array, &item);
124    ///     }
125    ///     array.borrow_mut().buffer.push(item);
126    /// }
127    /// let weak = Rc::downgrade(&array);
128    /// // 1 for the array binding, 10 for the `Rc`s in buffer
129    /// assert_eq!(Rc::strong_count(&array), 11);
130    /// drop(array);
131    /// assert!(weak.upgrade().is_none());
132    /// assert_eq!(weak.weak_count(), 0);
133    /// ```
134    ///
135    /// [`unadopt`]: Rc::unadopt
136    unsafe fn adopt_unchecked(this: &Self, other: &Self) {
137        // Self-adoptions have no effect.
138        if ptr::eq(this, other) {
139            // Store a loopback reference to `other` in `this`. This bookkeeping
140            // logs a strong reference and is used for discovering cycles.
141            //
142            // SAFETY: `this` is a live `Rc` so the `links` on its inner
143            // allocation are an inhabited `MaybeUninit`.
144            let mut links = this.inner().links().borrow_mut();
145            links.insert(Link::loopback(other.ptr));
146            return;
147        }
148        // Store a forward reference to `other` in `this`. This bookkeeping logs
149        // a strong reference and is used for discovering cycles.
150        //
151        // SAFETY: `this` is a live `Rc` so the `links` on its inner allocation
152        // are an inhabited `MaybeUninit`.
153        let mut links = this.inner().links().borrow_mut();
154        links.insert(Link::forward(other.ptr));
155        // `this` and `other` may point to the same allocation. Drop the borrow
156        // on `links` before accessing `other` to avoid a already borrowed error
157        // from the `RefCell`.
158        drop(links);
159        // Store a backward reference to `this` in `other`. This bookkeeping is
160        // used for discovering cycles.
161        //
162        // SAFETY: `this` is a live `Rc` so the `links` on its inner allocation
163        // are an inhabited `MaybeUninit`.
164        let mut links = other.inner().links().borrow_mut();
165        links.insert(Link::backward(this.ptr));
166    }
167
168    /// Perform bookkeeping to record that `this` has removed an owned reference
169    /// to `other`.
170    ///
171    /// Adoption is a one-way link, or a directed edge in the object graph which
172    /// means "`this` owns `other`".
173    ///
174    /// This is an associated function that needs to be used as
175    /// `Adopt::unadopt(...)`. A method would interfere with methods of the same
176    /// name on the contents of a `Rc` used through `Deref`.
177    ///
178    /// # Memory Leaks
179    ///
180    /// Failure to call this function when removing an owned `Rc` from `this`
181    /// is safe, but may result in a memory leak.
182    ///
183    /// # Examples
184    ///
185    /// The following implements a self-referential array.
186    ///
187    /// ```rust
188    /// use cactusref::{Adopt, Rc};
189    /// use std::cell::RefCell;
190    ///
191    /// #[derive(Default)]
192    /// struct Array {
193    ///     buffer: Vec<Rc<RefCell<Self>>>,
194    /// }
195    ///
196    /// let array = Rc::new(RefCell::new(Array::default()));
197    /// for _ in 0..10 {
198    ///     let item = Rc::clone(&array);
199    ///     unsafe {
200    ///         Rc::adopt_unchecked(&array, &item);
201    ///     }
202    ///     array.borrow_mut().buffer.push(item);
203    /// }
204    /// let weak = Rc::downgrade(&array);
205    /// // 1 for the array binding, 10 for the `Rc`s in buffer
206    /// assert_eq!(Rc::strong_count(&array), 11);
207    ///
208    /// let head = array.borrow_mut().buffer.pop().unwrap();
209    /// Rc::unadopt(&array, &head);
210    ///
211    /// drop(head);
212    /// assert_eq!(Rc::strong_count(&array), 10);
213    /// drop(array);
214    /// assert!(weak.upgrade().is_none());
215    /// assert_eq!(weak.weak_count(), 0);
216    /// ```
217    fn unadopt(this: &Self, other: &Self) {
218        // Self-adoptions have no effect.
219        if ptr::eq(this, other) {
220            // Remove a loopback reference to `other` in `this`. This bookkeeping
221            // logs a strong reference and is used for discovering cycles.
222            //
223            // SAFETY: `this` is a live `Rc` so the `links` on its inner
224            // allocation are an inhabited `MaybeUninit`.
225            let mut links = unsafe { this.inner().links().borrow_mut() };
226            links.remove(Link::loopback(other.ptr), 1);
227            return;
228        }
229        // Remove a forward reference to `other` in `this`. This bookkeeping
230        // removes a strong reference and is used for discovering cycles.
231        //
232        // SAFETY: `this` is a live `Rc` so the `links` on its inner allocation
233        // are an inhabited `MaybeUninit`.
234        let mut links = unsafe { this.inner().links().borrow_mut() };
235        links.remove(Link::forward(other.ptr), 1);
236        // `this` and `other` may point to the same allocation. Drop the borrow
237        // on `links` before accessing `other` to avoid a already borrowed error
238        // from the `RefCell`.
239        drop(links);
240        // Remove a backward reference to `this` in `other`. This bookkeeping is
241        // used for discovering cycles.
242        //
243        // SAFETY: `this` is a live `Rc` so the `links` on its inner allocation
244        // are an inhabited `MaybeUninit`.
245        let mut links = unsafe { other.inner().links().borrow_mut() };
246        links.remove(Link::backward(this.ptr), 1);
247    }
248}