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

boa_gc/
trace.rs
