tracing_rc/rc/
trace.rs

1use crate::rc::GcVisitor;
2
3/// Must be implemented for any value which will be stored inside of a [`Gc`](crate::rc::Gc).
4///
5/// While this is implemented for many of Rust's basic types, it's not
6/// recommended that you store them in a [`Gc`](crate::rc::Gc) unless they contain possibly cyclic
7/// references as there is still a real cost to doing so. You're probably better off using
8/// [`std::rc::Rc`] in cases where you know a type can't participate in cycles.
9/// Visit the gc pointers owned by this type.
10pub trait Trace {
11    ///
12    /// It is recommended that you simply call `visit_children(visitor)` on each value owned by the
13    /// implementor which may participate in a reference cycle. The default implementation for
14    /// `Gc` will appropriately notify the collector when it is visited.
15    ///
16    /// Improper implementation of this trait will not cause undefined behavior; however, if you
17    /// fail to report a value you may leak memory and if you report a value you don't own (or
18    /// report a value more than once), you may cause the collector to clean it up prematurely.
19    /// Attemting to access a value which has been cleaned up will cause a panic, but will not cause
20    /// undefined behavior.
21    ///
22    /// # Example
23    /// ```
24    /// # use std::collections::HashMap;
25    /// # use tracing_rc::{
26    /// #     empty_trace,
27    /// #     rc::{
28    /// #         Gc,
29    /// #         GcVisitor,
30    /// #         Trace,
31    /// #         collect_full,
32    /// #     },
33    /// # };
34    ///
35    /// struct GraphNode<T: 'static> {
36    ///     neighbors: Vec<Gc<GraphNode<T>>>,
37    ///     data: T,
38    /// }
39    ///
40    /// impl<T: 'static> Trace for GraphNode<T> {
41    ///     fn visit_children(&self, visitor: &mut GcVisitor) {
42    ///         self.neighbors.visit_children(visitor);
43    ///     }
44    /// }
45    /// # #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
46    /// # struct NodeId(usize);
47    /// empty_trace!(NodeId);
48    ///
49    /// struct Graph<T: 'static> {
50    ///     nodes: HashMap<NodeId, Gc<GraphNode<T>>>,
51    /// }
52    ///
53    /// impl<T: 'static> Trace for Graph<T> {
54    ///     fn visit_children(&self, visitor: &mut GcVisitor) {
55    ///         self.nodes.visit_children(visitor);
56    ///     }
57    /// }
58    /// # fn build_graph<T>() -> Graph<T> { Graph{ nodes: HashMap::default() } }
59    /// # fn operate_on_graph(_: &Graph<usize>) { }
60    ///
61    /// // Usage:
62    /// # fn main() {
63    /// {
64    ///     {
65    ///         let graph: Graph<usize> = build_graph();
66    ///         operate_on_graph(&graph);
67    ///     }
68    ///     // None of the graph nodes will remain allocated after this call.
69    ///     collect_full();
70    /// }
71    /// # }
72    /// ```
73    ///
74    /// # Examples of improper implementations
75    /// - You should not report Gcs owned by the inner contents of Gcs.
76    /// ```
77    /// # use tracing_rc::rc::{
78    /// #     Gc,
79    /// #     GcVisitor,
80    /// #     Trace,
81    /// # };
82    /// struct MyStruct {
83    ///     ptr: Gc<MyStruct>,
84    ///     other_ptr: Gc<MyStruct>,
85    /// }
86    ///
87    /// impl Trace for MyStruct {
88    ///     fn visit_children(&self, visitor: &mut GcVisitor) {
89    ///         // This is normal and ok.
90    ///         self.ptr.visit_children(visitor);
91    ///         // This is also acceptable
92    ///         visitor.visit_node(&self.other_ptr);
93    ///
94    ///         // This will not cause undefined behavior, but it is wrong and may cause panics if
95    ///         // it causes the collector to believe the node is dead, and the program later
96    ///         // attempts to access the now dead value.
97    ///         self.ptr.borrow().ptr.visit_children(visitor);
98    ///     }
99    /// }
100    /// ```
101    /// - You should not report a unique Gc instance twice.
102    /// ```
103    /// # use tracing_rc::rc::{
104    /// #     Gc,
105    /// #     GcVisitor,
106    /// #     Trace,
107    /// # };
108    /// struct MyStruct {
109    ///     ptr: Gc<usize>,
110    /// }
111    ///
112    /// impl Trace for MyStruct {
113    ///     fn visit_children(&self, visitor: &mut GcVisitor) {
114    ///         // This is normal and ok.
115    ///         visitor.visit_node(&self.ptr);
116    ///
117    ///         // This is wrong and may cause panics.
118    ///         visitor.visit_node(&self.ptr);
119    ///     }
120    /// }
121    /// ```
122    /// - You should not report Gcs that are not owned by your object.
123    ///     - It is acceptable skip reporting, although doing so will result in memory leaks.
124    /// ```
125    /// # use tracing_rc::rc::{
126    /// #     Gc,
127    /// #     GcVisitor,
128    /// #     Trace,
129    /// # };
130    /// thread_local! { static GLOBAL_PTR: Gc<usize> = Gc::new(10)}
131    ///
132    /// struct MyStruct {
133    ///     ptr: Gc<MyStruct>,
134    ///     leaks: Gc<usize>,
135    /// }
136    ///
137    /// impl Trace for MyStruct {
138    ///     fn visit_children(&self, visitor: &mut GcVisitor) {
139    ///         // This is normal and ok.
140    ///         visitor.visit_node(&self.ptr);
141    ///
142    ///         // Leaving this line commented out will leak, which is safe.
143    ///         // Uncommenting it is safe and will allow leaks to be cleaned up.
144    ///         // visitor(self.leaks.node());
145    ///
146    ///         // This is wrong and will cause GLOBAL_PTR to be cleaned up. If anything tries to
147    ///         // access GLOBAL_PTR without checking if it is still alive, a panic will occur.
148    ///         GLOBAL_PTR.with(|ptr| visitor.visit_node(ptr));
149    ///     }
150    /// }
151    /// ```
152    fn visit_children(&self, visitor: &mut GcVisitor);
153}
154
155/// Implements a no-op [`Trace`] for a type.
156///
157/// This will cause memory leaks if it is used to implement tracing on a type which ends up
158/// participating in a cycle. This is useful for types that are e.g. used as a key in
159/// [`std::collections::HashMap`], but are not actually `Gc` pointers.
160#[macro_export]
161macro_rules! empty_trace {
162    ($t:path) => {
163        impl $crate::rc::Trace for $t {
164            #[inline]
165            fn visit_children(&self, _: &mut $crate::rc::GcVisitor) {}
166        }
167    };
168    ($first:path, $($rest:path),+) => {
169        empty_trace!($first);
170        empty_trace!($($rest),+);
171    };
172}
173
174empty_trace!(f32, f64);
175empty_trace!(i8, i16, i32, i64, isize, i128);
176empty_trace!(u8, u16, u32, u64, usize, u128);
177empty_trace!(bool, char);
178empty_trace!(std::string::String);
179
180impl Trace for () {
181    fn visit_children(&self, _: &mut GcVisitor) {}
182}
183
184impl<T: Trace> Trace for std::cell::RefCell<T> {
185    fn visit_children(&self, visitor: &mut GcVisitor) {
186        T::visit_children(&self.borrow(), visitor);
187    }
188}
189
190impl<T: Trace> Trace for std::option::Option<T> {
191    fn visit_children(&self, visitor: &mut GcVisitor) {
192        if let Some(inner) = self {
193            inner.visit_children(visitor);
194        }
195    }
196}
197
198impl<T: Trace> Trace for std::vec::Vec<T> {
199    fn visit_children(&self, visitor: &mut GcVisitor) {
200        for elem in self.iter() {
201            elem.visit_children(visitor);
202        }
203    }
204}
205
206impl<T: Trace> Trace for std::boxed::Box<T> {
207    fn visit_children(&self, visitor: &mut GcVisitor) {
208        T::visit_children(self, visitor);
209    }
210}
211
212impl<T: Trace, const S: usize> Trace for [T; S] {
213    fn visit_children(&self, visitor: &mut GcVisitor) {
214        for elem in self.iter() {
215            elem.visit_children(visitor);
216        }
217    }
218}
219
220impl<T: Trace> Trace for [T] {
221    fn visit_children(&self, visitor: &mut GcVisitor) {
222        for elem in self.iter() {
223            elem.visit_children(visitor);
224        }
225    }
226}
227
228impl<V: Trace> Trace for std::collections::BinaryHeap<V> {
229    fn visit_children(&self, visitor: &mut GcVisitor) {
230        for v in self.iter() {
231            v.visit_children(visitor);
232        }
233    }
234}
235
236impl<K: Trace, V: Trace> Trace for std::collections::BTreeMap<K, V> {
237    fn visit_children(&self, visitor: &mut GcVisitor) {
238        for (k, v) in self.iter() {
239            k.visit_children(visitor);
240            v.visit_children(visitor);
241        }
242    }
243}
244
245impl<V: Trace> Trace for std::collections::BTreeSet<V> {
246    fn visit_children(&self, visitor: &mut GcVisitor) {
247        for v in self.iter() {
248            v.visit_children(visitor);
249        }
250    }
251}
252
253impl<K: Trace, V: Trace, S: std::hash::BuildHasher> Trace for std::collections::HashMap<K, V, S> {
254    fn visit_children(&self, visitor: &mut GcVisitor) {
255        for (k, v) in self.iter() {
256            k.visit_children(visitor);
257            v.visit_children(visitor);
258        }
259    }
260}
261
262impl<V: Trace, S: std::hash::BuildHasher> Trace for std::collections::HashSet<V, S> {
263    fn visit_children(&self, visitor: &mut GcVisitor) {
264        for v in self.iter() {
265            v.visit_children(visitor);
266        }
267    }
268}
269
270impl<V: Trace> Trace for std::collections::LinkedList<V> {
271    fn visit_children(&self, visitor: &mut GcVisitor) {
272        for v in self.iter() {
273            v.visit_children(visitor);
274        }
275    }
276}
277
278impl<V: Trace> Trace for std::collections::VecDeque<V> {
279    fn visit_children(&self, visitor: &mut GcVisitor) {
280        for v in self.iter() {
281            v.visit_children(visitor);
282        }
283    }
284}