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