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}