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}