boa_gc/
trace.rs

1use std::{
2    any::TypeId,
3    borrow::{Cow, ToOwned},
4    cell::{Cell, OnceCell},
5    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque},
6    hash::{BuildHasher, Hash},
7    marker::PhantomData,
8    num::{
9        NonZeroI8, NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI128, NonZeroIsize, NonZeroU8,
10        NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU128, NonZeroUsize,
11    },
12    path::{Path, PathBuf},
13    rc::Rc,
14    sync::atomic,
15};
16
17use crate::GcErasedPointer;
18
19/// A queue used to trace [`crate::Gc<T>`] non-recursively.
20#[doc(hidden)]
21#[allow(missing_debug_implementations)]
22pub struct Tracer {
23    queue: VecDeque<GcErasedPointer>,
24}
25
26impl Tracer {
27    pub(crate) fn new() -> Self {
28        Self {
29            queue: VecDeque::default(),
30        }
31    }
32
33    pub(crate) fn enqueue(&mut self, node: GcErasedPointer) {
34        self.queue.push_back(node);
35    }
36
37    /// Traces through all the queued nodes until the queue is empty.
38    ///
39    /// # Safety
40    ///
41    /// All the pointers inside of the queue must point to valid memory.
42    pub(crate) unsafe fn trace_until_empty(&mut self) {
43        while let Some(node) = self.queue.pop_front() {
44            let node_ref = unsafe { node.as_ref() };
45            if node_ref.is_marked() {
46                continue;
47            }
48            node_ref.header.mark();
49            let trace_fn = node_ref.trace_fn();
50
51            // SAFETY: The function pointer is appropriate for this node type because we extract it from it's VTable.
52            // Additionally, the node pointer is valid per the caller's guarantee.
53            unsafe { trace_fn(node, self) }
54        }
55    }
56
57    pub(crate) fn is_empty(&mut self) -> bool {
58        self.queue.is_empty()
59    }
60}
61
62/// Substitute for the [`Drop`] trait for garbage collected types.
63pub trait Finalize {
64    /// Cleanup logic for a type.
65    fn finalize(&self) {}
66}
67
68/// The Trace trait, which needs to be implemented on garbage-collected objects.
69///
70/// # Safety
71///
72/// - An incorrect implementation of the trait can result in heap overflows, data corruption,
73///   use-after-free, or Undefined Behaviour in general.
74///
75/// - Calling any of the functions marked as `unsafe` outside of the context of the garbage collector
76///   can result in Undefined Behaviour.
77pub unsafe trait Trace: Finalize {
78    /// Marks all contained `Gc`s.
79    ///
80    /// # Safety
81    ///
82    /// See [`Trace`].
83    unsafe fn trace(&self, tracer: &mut Tracer);
84
85    /// Trace handles located in GC heap, and mark them as non root.
86    ///
87    /// # Safety
88    ///
89    /// See [`Trace`].
90    unsafe fn trace_non_roots(&self);
91
92    /// Runs [`Finalize::finalize`] on this object and all
93    /// contained subobjects.
94    fn run_finalizer(&self);
95}
96
97/// Utility macro to define an empty implementation of [`Trace`].
98///
99/// Use this for marking types as not containing any `Trace` types.
100#[macro_export]
101macro_rules! empty_trace {
102    () => {
103        #[inline]
104        unsafe fn trace(&self, _tracer: &mut $crate::Tracer) {}
105        #[inline]
106        unsafe fn trace_non_roots(&self) {}
107        #[inline]
108        fn run_finalizer(&self) {
109            $crate::Finalize::finalize(self)
110        }
111    };
112}
113
114/// Utility macro to manually implement [`Trace`] on a type.
115///
116/// You define a `this` parameter name and pass in a body, which should call `mark` on every
117/// traceable element inside the body. The mark implementation will automatically delegate to the
118/// correct method on the argument.
119///
120/// # Safety
121///
122/// Misusing the `mark` function may result in Undefined Behaviour.
123#[macro_export]
124macro_rules! custom_trace {
125    ($this:ident, $marker:ident, $body:expr) => {
126        #[inline]
127        unsafe fn trace(&self, tracer: &mut $crate::Tracer) {
128            let mut $marker = |it: &dyn $crate::Trace| {
129                // SAFETY: The implementor must ensure that `trace` is correctly implemented.
130                unsafe {
131                    $crate::Trace::trace(it, tracer);
132                }
133            };
134            let $this = self;
135            $body
136        }
137        #[inline]
138        unsafe fn trace_non_roots(&self) {
139            fn $marker<T: $crate::Trace + ?Sized>(it: &T) {
140                // SAFETY: The implementor must ensure that `trace` is correctly implemented.
141                unsafe {
142                    $crate::Trace::trace_non_roots(it);
143                }
144            }
145            let $this = self;
146            $body
147        }
148        #[inline]
149        fn run_finalizer(&self) {
150            fn $marker<T: $crate::Trace + ?Sized>(it: &T) {
151                $crate::Trace::run_finalizer(it);
152            }
153            $crate::Finalize::finalize(self);
154            let $this = self;
155            $body
156        }
157    };
158}
159
160impl<T: ?Sized> Finalize for &'static T {}
161// SAFETY: 'static references don't need to be traced, since they live indefinitely.
162unsafe impl<T: ?Sized> Trace for &'static T {
163    empty_trace!();
164}
165
166macro_rules! simple_empty_finalize_trace {
167    ($($T:ty),*) => {
168        $(
169            impl Finalize for $T {}
170
171            // SAFETY:
172            // Primitive types and string types don't have inner nodes that need to be marked.
173            unsafe impl Trace for $T { empty_trace!(); }
174        )*
175    }
176}
177
178simple_empty_finalize_trace![
179    (),
180    bool,
181    isize,
182    usize,
183    i8,
184    u8,
185    i16,
186    u16,
187    i32,
188    u32,
189    i64,
190    u64,
191    i128,
192    u128,
193    f32,
194    f64,
195    char,
196    TypeId,
197    String,
198    str,
199    Rc<str>,
200    Path,
201    PathBuf,
202    NonZeroIsize,
203    NonZeroUsize,
204    NonZeroI8,
205    NonZeroU8,
206    NonZeroI16,
207    NonZeroU16,
208    NonZeroI32,
209    NonZeroU32,
210    NonZeroI64,
211    NonZeroU64,
212    NonZeroI128,
213    NonZeroU128
214];
215
216#[cfg(target_has_atomic = "8")]
217simple_empty_finalize_trace![atomic::AtomicBool, atomic::AtomicI8, atomic::AtomicU8];
218
219#[cfg(target_has_atomic = "16")]
220simple_empty_finalize_trace![atomic::AtomicI16, atomic::AtomicU16];
221
222#[cfg(target_has_atomic = "32")]
223simple_empty_finalize_trace![atomic::AtomicI32, atomic::AtomicU32];
224
225#[cfg(target_has_atomic = "64")]
226simple_empty_finalize_trace![atomic::AtomicI64, atomic::AtomicU64];
227
228#[cfg(target_has_atomic = "ptr")]
229simple_empty_finalize_trace![atomic::AtomicIsize, atomic::AtomicUsize];
230
231impl<T: Trace, const N: usize> Finalize for [T; N] {}
232// SAFETY:
233// All elements inside the array are correctly marked.
234unsafe impl<T: Trace, const N: usize> Trace for [T; N] {
235    custom_trace!(this, mark, {
236        for v in this {
237            mark(v);
238        }
239    });
240}
241
242macro_rules! fn_finalize_trace_one {
243    ($ty:ty $(,$args:ident)*) => {
244        impl<Ret $(,$args)*> Finalize for $ty {}
245        // SAFETY:
246        // Function pointers don't have inner nodes that need to be marked.
247        unsafe impl<Ret $(,$args)*> Trace for $ty { empty_trace!(); }
248    }
249}
250macro_rules! fn_finalize_trace_group {
251    () => {
252        fn_finalize_trace_one!(extern "Rust" fn () -> Ret);
253        fn_finalize_trace_one!(extern "C" fn () -> Ret);
254        fn_finalize_trace_one!(unsafe extern "Rust" fn () -> Ret);
255        fn_finalize_trace_one!(unsafe extern "C" fn () -> Ret);
256    };
257    ($($args:ident),*) => {
258        fn_finalize_trace_one!(extern "Rust" fn ($($args),*) -> Ret, $($args),*);
259        fn_finalize_trace_one!(extern "C" fn ($($args),*) -> Ret, $($args),*);
260        fn_finalize_trace_one!(extern "C" fn ($($args),*, ...) -> Ret, $($args),*);
261        fn_finalize_trace_one!(unsafe extern "Rust" fn ($($args),*) -> Ret, $($args),*);
262        fn_finalize_trace_one!(unsafe extern "C" fn ($($args),*) -> Ret, $($args),*);
263        fn_finalize_trace_one!(unsafe extern "C" fn ($($args),*, ...) -> Ret, $($args),*);
264    }
265}
266
267macro_rules! tuple_finalize_trace {
268    () => {}; // This case is handled above, by simple_finalize_empty_trace!().
269    ($($args:ident),*) => {
270        impl<$($args),*> Finalize for ($($args,)*) {}
271        // SAFETY:
272        // All elements inside the tuple are correctly marked.
273        unsafe impl<$($args: $crate::Trace),*> Trace for ($($args,)*) {
274            custom_trace!(this, mark, {
275                #[allow(non_snake_case, unused_unsafe, unused_mut)]
276                let mut avoid_lints = |&($(ref $args,)*): &($($args,)*)| {
277                    // SAFETY: The implementor must ensure a correct implementation.
278                    unsafe { $(mark($args);)* }
279                };
280                avoid_lints(this)
281            });
282        }
283    }
284}
285
286macro_rules! type_arg_tuple_based_finalize_trace_impls {
287    ($(($($args:ident),*);)*) => {
288        $(
289            fn_finalize_trace_group!($($args),*);
290            tuple_finalize_trace!($($args),*);
291        )*
292    }
293}
294
295type_arg_tuple_based_finalize_trace_impls![
296    ();
297    (A);
298    (A, B);
299    (A, B, C);
300    (A, B, C, D);
301    (A, B, C, D, E);
302    (A, B, C, D, E, F);
303    (A, B, C, D, E, F, G);
304    (A, B, C, D, E, F, G, H);
305    (A, B, C, D, E, F, G, H, I);
306    (A, B, C, D, E, F, G, H, I, J);
307    (A, B, C, D, E, F, G, H, I, J, K);
308    (A, B, C, D, E, F, G, H, I, J, K, L);
309];
310
311impl<T: Trace + ?Sized> Finalize for Box<T> {}
312// SAFETY: The inner value of the `Box` is correctly marked.
313unsafe impl<T: Trace + ?Sized> Trace for Box<T> {
314    #[inline]
315    unsafe fn trace(&self, tracer: &mut Tracer) {
316        // SAFETY: The implementor must ensure that `trace` is correctly implemented.
317        unsafe {
318            Trace::trace(&**self, tracer);
319        }
320    }
321    #[inline]
322    unsafe fn trace_non_roots(&self) {
323        // SAFETY: The implementor must ensure that `trace_non_roots` is correctly implemented.
324        unsafe {
325            Trace::trace_non_roots(&**self);
326        }
327    }
328    #[inline]
329    fn run_finalizer(&self) {
330        Finalize::finalize(self);
331        Trace::run_finalizer(&**self);
332    }
333}
334
335impl<T: Trace> Finalize for Box<[T]> {}
336// SAFETY: All the inner elements of the `Box` array are correctly marked.
337unsafe impl<T: Trace> Trace for Box<[T]> {
338    custom_trace!(this, mark, {
339        for e in &**this {
340            mark(e);
341        }
342    });
343}
344
345impl<T: Trace> Finalize for Vec<T> {}
346// SAFETY: All the inner elements of the `Vec` are correctly marked.
347unsafe impl<T: Trace> Trace for Vec<T> {
348    custom_trace!(this, mark, {
349        for e in this {
350            mark(e);
351        }
352    });
353}
354
355#[cfg(feature = "thin-vec")]
356impl<T: Trace> Finalize for thin_vec::ThinVec<T> {}
357
358#[cfg(feature = "thin-vec")]
359// SAFETY: All the inner elements of the `Vec` are correctly marked.
360unsafe impl<T: Trace> Trace for thin_vec::ThinVec<T> {
361    custom_trace!(this, mark, {
362        for e in this {
363            mark(e);
364        }
365    });
366}
367
368impl<T: Trace> Finalize for Option<T> {}
369// SAFETY: The inner value of the `Option` is correctly marked.
370unsafe impl<T: Trace> Trace for Option<T> {
371    custom_trace!(this, mark, {
372        if let Some(ref v) = *this {
373            mark(v);
374        }
375    });
376}
377
378impl<T: Trace, E: Trace> Finalize for Result<T, E> {}
379// SAFETY: Both inner values of the `Result` are correctly marked.
380unsafe impl<T: Trace, E: Trace> Trace for Result<T, E> {
381    custom_trace!(this, mark, {
382        match *this {
383            Ok(ref v) => mark(v),
384            Err(ref v) => mark(v),
385        }
386    });
387}
388
389impl<T: Ord + Trace> Finalize for BinaryHeap<T> {}
390// SAFETY: All the elements of the `BinaryHeap` are correctly marked.
391unsafe impl<T: Ord + Trace> Trace for BinaryHeap<T> {
392    custom_trace!(this, mark, {
393        for v in this {
394            mark(v);
395        }
396    });
397}
398
399impl<K: Trace, V: Trace> Finalize for BTreeMap<K, V> {}
400// SAFETY: All the elements of the `BTreeMap` are correctly marked.
401unsafe impl<K: Trace, V: Trace> Trace for BTreeMap<K, V> {
402    custom_trace!(this, mark, {
403        for (k, v) in this {
404            mark(k);
405            mark(v);
406        }
407    });
408}
409
410impl<T: Trace> Finalize for BTreeSet<T> {}
411// SAFETY: All the elements of the `BTreeSet` are correctly marked.
412unsafe impl<T: Trace> Trace for BTreeSet<T> {
413    custom_trace!(this, mark, {
414        for v in this {
415            mark(v);
416        }
417    });
418}
419
420impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Finalize
421    for hashbrown::hash_map::HashMap<K, V, S>
422{
423}
424// SAFETY: All the elements of the `HashMap` are correctly marked.
425unsafe impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Trace
426    for hashbrown::hash_map::HashMap<K, V, S>
427{
428    custom_trace!(this, mark, {
429        for (k, v) in this {
430            mark(k);
431            mark(v);
432        }
433    });
434}
435
436impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Finalize for HashMap<K, V, S> {}
437// SAFETY: All the elements of the `HashMap` are correctly marked.
438unsafe impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Trace for HashMap<K, V, S> {
439    custom_trace!(this, mark, {
440        for (k, v) in this {
441            mark(k);
442            mark(v);
443        }
444    });
445}
446
447impl<T: Eq + Hash + Trace, S: BuildHasher> Finalize for HashSet<T, S> {}
448// SAFETY: All the elements of the `HashSet` are correctly marked.
449unsafe impl<T: Eq + Hash + Trace, S: BuildHasher> Trace for HashSet<T, S> {
450    custom_trace!(this, mark, {
451        for v in this {
452            mark(v);
453        }
454    });
455}
456
457impl<T: Eq + Hash + Trace> Finalize for LinkedList<T> {}
458// SAFETY: All the elements of the `LinkedList` are correctly marked.
459unsafe impl<T: Eq + Hash + Trace> Trace for LinkedList<T> {
460    custom_trace!(this, mark, {
461        #[allow(clippy::explicit_iter_loop)]
462        for v in this.iter() {
463            mark(v);
464        }
465    });
466}
467
468impl<T> Finalize for PhantomData<T> {}
469// SAFETY: A `PhantomData` doesn't have inner data that needs to be marked.
470unsafe impl<T> Trace for PhantomData<T> {
471    empty_trace!();
472}
473
474impl<T: Trace> Finalize for VecDeque<T> {}
475// SAFETY: All the elements of the `VecDeque` are correctly marked.
476unsafe impl<T: Trace> Trace for VecDeque<T> {
477    custom_trace!(this, mark, {
478        for v in this {
479            mark(v);
480        }
481    });
482}
483
484impl<T: ToOwned + Trace + ?Sized> Finalize for Cow<'static, T> {}
485// SAFETY: 'static references don't need to be traced, since they live indefinitely, and the owned
486// variant is correctly marked.
487unsafe impl<T: ToOwned + Trace + ?Sized> Trace for Cow<'static, T>
488where
489    T::Owned: Trace,
490{
491    custom_trace!(this, mark, {
492        if let Cow::Owned(v) = this {
493            mark(v);
494        }
495    });
496}
497
498impl<T: Trace> Finalize for Cell<Option<T>> {}
499// SAFETY: Taking and setting is done in a single action, and recursive traces should find a `None`
500// value instead of the original `T`, making this safe.
501unsafe impl<T: Trace> Trace for Cell<Option<T>> {
502    custom_trace!(this, mark, {
503        if let Some(v) = this.take() {
504            mark(&v);
505            this.set(Some(v));
506        }
507    });
508}
509
510impl<T: Trace> Finalize for OnceCell<T> {}
511// SAFETY: We only trace the inner cell if the cell has a value.
512unsafe impl<T: Trace> Trace for OnceCell<T> {
513    custom_trace!(this, mark, {
514        if let Some(v) = this.get() {
515            mark(v);
516        }
517    });
518}
519
520#[cfg(feature = "icu")]
521mod icu {
522    use icu_locale_core::{LanguageIdentifier, Locale};
523
524    use crate::{Finalize, Trace};
525
526    impl Finalize for LanguageIdentifier {}
527
528    // SAFETY: `LanguageIdentifier` doesn't have any traceable data.
529    unsafe impl Trace for LanguageIdentifier {
530        empty_trace!();
531    }
532
533    impl Finalize for Locale {}
534
535    // SAFETY: `LanguageIdentifier` doesn't have any traceable data.
536    unsafe impl Trace for Locale {
537        empty_trace!();
538    }
539}
540
541#[cfg(feature = "boa_string")]
542mod boa_string_trace {
543    use crate::{Finalize, Trace};
544
545    // SAFETY: `boa_string::JsString` doesn't have any traceable data.
546    unsafe impl Trace for boa_string::JsString {
547        empty_trace!();
548    }
549
550    impl Finalize for boa_string::JsString {}
551}
552
553#[cfg(feature = "either")]
554mod either_trace {
555    use crate::{Finalize, Trace};
556
557    impl<L: Trace, R: Trace> Finalize for either::Either<L, R> {}
558
559    unsafe impl<L: Trace, R: Trace> Trace for either::Either<L, R> {
560        custom_trace!(this, mark, {
561            match this {
562                either::Either::Left(l) => mark(l),
563                either::Either::Right(r) => mark(r),
564            }
565        });
566    }
567}
boa_gc/trace.rs

boa_gc/
trace.rs
