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

boa_gc/
trace.rs
