boa_gc/

trace.rs

usestd::{    any::TypeId,    borrow::{Cow, ToOwned},    cell::{Cell, OnceCell},    collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque},    hash::{BuildHasher, Hash},    marker::PhantomData,    num::{        NonZeroI8, NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI128, NonZeroIsize, NonZeroU8,        NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU128, NonZeroUsize,    },    path::{Path, PathBuf},    rc::Rc,    sync::atomic,};usecrate::GcErasedPointer;/// A queue used to trace [`crate::Gc<T>`] non-recursively.#[doc(hidden)]#[allow(missing_debug_implementations)]pub structTracer {    queue: VecDeque<GcErasedPointer>,}implTracer {pub(crate)fnnew() ->Self{Self{            queue: VecDeque::default(),        }    }pub(crate)fnenqueue(&mutself, node: GcErasedPointer) {self.queue.push_back(node);    }/// Traces through all the queued nodes until the queue is empty.    ///    /// # Safety    ///    /// All the pointers inside of the queue must point to valid memory.pub(crate)unsafe fntrace_until_empty(&mutself) {while letSome(node) =self.queue.pop_front() {letnode_ref =unsafe{ node.as_ref() };ifnode_ref.is_marked() {continue;            }            node_ref.header.mark();lettrace_fn = node_ref.trace_fn();// SAFETY: The function pointer is appropriate for this node type because we extract it from it's VTable.            // Additionally, the node pointer is valid per the caller's guarantee.unsafe{ trace_fn(node,self) }        }    }pub(crate)fnis_empty(&mutself) -> bool {self.queue.is_empty()    }}/// Substitute for the [`Drop`] trait for garbage collected types.pub traitFinalize {/// Cleanup logic for a type.fnfinalize(&self) {}}/// The Trace trait, which needs to be implemented on garbage-collected objects.////// # Safety////// - An incorrect implementation of the trait can result in heap overflows, data corruption,///   use-after-free, or Undefined Behaviour in general.////// - Calling any of the functions marked as `unsafe` outside of the context of the garbage collector///   can result in Undefined Behaviour.pub unsafe traitTrace: Finalize {/// Marks all contained `Gc`s.    ///    /// # Safety    ///    /// See [`Trace`].unsafe fntrace(&self, tracer:&mutTracer);/// Trace handles located in GC heap, and mark them as non root.    ///    /// # Safety    ///    /// See [`Trace`].unsafe fntrace_non_roots(&self);/// Runs [`Finalize::finalize`] on this object and all    /// contained subobjects.fnrun_finalizer(&self);}/// Utility macro to define an empty implementation of [`Trace`].////// Use this for marking types as not containing any `Trace` types.#[macro_export]macro_rules! empty_trace {    () => {#[inline]unsafe fntrace(&self, _tracer:&mut$crate::Tracer) {}#[inline]unsafe fntrace_non_roots(&self) {}#[inline]fnrun_finalizer(&self) {$crate::Finalize::finalize(self)        }    };}/// Utility macro to manually implement [`Trace`] on a type.////// You define a `this` parameter name and pass in a body, which should call `mark` on every/// traceable element inside the body. The mark implementation will automatically delegate to the/// correct method on the argument.////// # Safety////// Misusing the `mark` function may result in Undefined Behaviour.#[macro_export]macro_rules! custom_trace {    ($this:ident,$marker:ident,$body:expr) => {#[inline]unsafe fntrace(&self, tracer:&mut$crate::Tracer) {letmut$marker= |it:&dyn$crate::Trace| {// SAFETY: The implementor must ensure that `trace` is correctly implemented.unsafe{$crate::Trace::trace(it, tracer);                }            };let$this=self;$body}#[inline]unsafe fntrace_non_roots(&self) {fn$marker<T:$crate::Trace+?Sized>(it:&T) {// SAFETY: The implementor must ensure that `trace` is correctly implemented.unsafe{$crate::Trace::trace_non_roots(it);                }            }let$this=self;$body}#[inline]fnrun_finalizer(&self) {fn$marker<T:$crate::Trace+?Sized>(it:&T) {$crate::Trace::run_finalizer(it);            }$crate::Finalize::finalize(self);let$this=self;$body}    };}impl<T:?Sized> Finalizefor&'staticT {}// SAFETY: 'static references don't need to be traced, since they live indefinitely.unsafe impl<T:?Sized> Tracefor&'staticT {empty_trace!();}macro_rules! simple_empty_finalize_trace {    ($($T:ty),*) => {        $(implFinalizefor$T{}// SAFETY:            // Primitive types and string types don't have inner nodes that need to be marked.unsafe implTracefor$T{empty_trace!(); }        )*    }}simple_empty_finalize_trace![    (),    bool,    isize,    usize,    i8,    u8,    i16,    u16,    i32,    u32,    i64,    u64,    i128,    u128,    f32,    f64,    char,    TypeId,    String,    str,    Rc<str>,    Path,    PathBuf,    NonZeroIsize,    NonZeroUsize,    NonZeroI8,    NonZeroU8,    NonZeroI16,    NonZeroU16,    NonZeroI32,    NonZeroU32,    NonZeroI64,    NonZeroU64,    NonZeroI128,    NonZeroU128];#[cfg(target_has_atomic ="8")]simple_empty_finalize_trace![atomic::AtomicBool, atomic::AtomicI8, atomic::AtomicU8];#[cfg(target_has_atomic ="16")]simple_empty_finalize_trace![atomic::AtomicI16, atomic::AtomicU16];#[cfg(target_has_atomic ="32")]simple_empty_finalize_trace![atomic::AtomicI32, atomic::AtomicU32];#[cfg(target_has_atomic ="64")]simple_empty_finalize_trace![atomic::AtomicI64, atomic::AtomicU64];#[cfg(target_has_atomic ="ptr")]simple_empty_finalize_trace![atomic::AtomicIsize, atomic::AtomicUsize];impl<T: Trace,constN: usize> Finalizefor[T; N] {}// SAFETY:// All elements inside the array are correctly marked.unsafe impl<T: Trace,constN: usize> Tracefor[T; N] {custom_trace!(this, mark, {forvinthis {            mark(v);        }    });}macro_rules! fn_finalize_trace_one {    ($ty:ty $(,$args:ident)*) => {impl<Ret $(,$args)*> Finalizefor$ty{}// SAFETY:        // Function pointers don't have inner nodes that need to be marked.unsafe impl<Ret $(,$args)*> Tracefor$ty{empty_trace!(); }    }}macro_rules! fn_finalize_trace_group {    () => {fn_finalize_trace_one!(extern"Rust"fn() -> Ret);fn_finalize_trace_one!(extern"C"fn() -> Ret);fn_finalize_trace_one!(unsafe extern"Rust"fn() -> Ret);fn_finalize_trace_one!(unsafe extern"C"fn() -> Ret);    };    ($($args:ident),*) => {fn_finalize_trace_one!(extern"Rust"fn($($args),*) -> Ret, $($args),*);fn_finalize_trace_one!(extern"C"fn($($args),*) -> Ret, $($args),*);fn_finalize_trace_one!(extern"C"fn($($args),*, ...) -> Ret, $($args),*);fn_finalize_trace_one!(unsafe extern"Rust"fn($($args),*) -> Ret, $($args),*);fn_finalize_trace_one!(unsafe extern"C"fn($($args),*) -> Ret, $($args),*);fn_finalize_trace_one!(unsafe extern"C"fn($($args),*, ...) -> Ret, $($args),*);    }}macro_rules! tuple_finalize_trace {    () => {};// This case is handled above, by simple_finalize_empty_trace!().($($args:ident),*) => {impl<$($args),*> Finalizefor($($args,)*) {}// SAFETY:        // All elements inside the tuple are correctly marked.unsafe impl<$($args:$crate::Trace),*> Tracefor($($args,)*) {custom_trace!(this, mark, {#[allow(non_snake_case, unused_unsafe, unused_mut)]letmutavoid_lints = |&($(ref$args,)*):&($($args,)*)| {// SAFETY: The implementor must ensure a correct implementation.unsafe{ $(mark($args);)* }                };                avoid_lints(this)            });        }    }}macro_rules! type_arg_tuple_based_finalize_trace_impls {    ($(($($args:ident),*);)*) => {        $(fn_finalize_trace_group!($($args),*);tuple_finalize_trace!($($args),*);        )*    }}type_arg_tuple_based_finalize_trace_impls![    ();    (A);    (A, B);    (A, B, C);    (A, B, C, D);    (A, B, C, D, E);    (A, B, C, D, E, F);    (A, B, C, D, E, F, G);    (A, B, C, D, E, F, G, H);    (A, B, C, D, E, F, G, H, I);    (A, B, C, D, E, F, G, H, I, J);    (A, B, C, D, E, F, G, H, I, J, K);    (A, B, C, D, E, F, G, H, I, J, K, L);];impl<T: Trace +?Sized> FinalizeforBox<T> {}// SAFETY: The inner value of the `Box` is correctly marked.unsafe impl<T: Trace +?Sized> TraceforBox<T> {#[inline]unsafe fntrace(&self, tracer:&mutTracer) {// SAFETY: The implementor must ensure that `trace` is correctly implemented.unsafe{            Trace::trace(&**self, tracer);        }    }#[inline]unsafe fntrace_non_roots(&self) {// SAFETY: The implementor must ensure that `trace_non_roots` is correctly implemented.unsafe{            Trace::trace_non_roots(&**self);        }    }#[inline]fnrun_finalizer(&self) {        Finalize::finalize(self);        Trace::run_finalizer(&**self);    }}impl<T: Trace> FinalizeforBox<[T]> {}// SAFETY: All the inner elements of the `Box` array are correctly marked.unsafe impl<T: Trace> TraceforBox<[T]> {custom_trace!(this, mark, {forein&**this {            mark(e);        }    });}impl<T: Trace> FinalizeforVec<T> {}// SAFETY: All the inner elements of the `Vec` are correctly marked.unsafe impl<T: Trace> TraceforVec<T> {custom_trace!(this, mark, {foreinthis {            mark(e);        }    });}#[cfg(feature ="thin-vec")]impl<T: Trace> Finalizeforthin_vec::ThinVec<T> {}#[cfg(feature ="thin-vec")]// SAFETY: All the inner elements of the `Vec` are correctly marked.unsafe impl<T: Trace> Traceforthin_vec::ThinVec<T> {custom_trace!(this, mark, {foreinthis {            mark(e);        }    });}impl<T: Trace> FinalizeforOption<T> {}// SAFETY: The inner value of the `Option` is correctly marked.unsafe impl<T: Trace> TraceforOption<T> {custom_trace!(this, mark, {if letSome(refv) =*this {            mark(v);        }    });}impl<T: Trace, E: Trace> FinalizeforResult<T, E> {}// SAFETY: Both inner values of the `Result` are correctly marked.unsafe impl<T: Trace, E: Trace> TraceforResult<T, E> {custom_trace!(this, mark, {match*this {Ok(refv) => mark(v),Err(refv) => mark(v),        }    });}impl<T: Ord + Trace> FinalizeforBinaryHeap<T> {}// SAFETY: All the elements of the `BinaryHeap` are correctly marked.unsafe impl<T: Ord + Trace> TraceforBinaryHeap<T> {custom_trace!(this, mark, {forvinthis {            mark(v);        }    });}impl<K: Trace, V: Trace> FinalizeforBTreeMap<K, V> {}// SAFETY: All the elements of the `BTreeMap` are correctly marked.unsafe impl<K: Trace, V: Trace> TraceforBTreeMap<K, V> {custom_trace!(this, mark, {for(k, v)inthis {            mark(k);            mark(v);        }    });}impl<T: Trace> FinalizeforBTreeSet<T> {}// SAFETY: All the elements of the `BTreeSet` are correctly marked.unsafe impl<T: Trace> TraceforBTreeSet<T> {custom_trace!(this, mark, {forvinthis {            mark(v);        }    });}impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Finalizeforhashbrown::hash_map::HashMap<K, V, S>{}// SAFETY: All the elements of the `HashMap` are correctly marked.unsafe impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> Traceforhashbrown::hash_map::HashMap<K, V, S>{custom_trace!(this, mark, {for(k, v)inthis {            mark(k);            mark(v);        }    });}impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> FinalizeforHashMap<K, V, S> {}// SAFETY: All the elements of the `HashMap` are correctly marked.unsafe impl<K: Eq + Hash + Trace, V: Trace, S: BuildHasher> TraceforHashMap<K, V, S> {custom_trace!(this, mark, {for(k, v)inthis {            mark(k);            mark(v);        }    });}impl<T: Eq + Hash + Trace, S: BuildHasher> FinalizeforHashSet<T, S> {}// SAFETY: All the elements of the `HashSet` are correctly marked.unsafe impl<T: Eq + Hash + Trace, S: BuildHasher> TraceforHashSet<T, S> {custom_trace!(this, mark, {forvinthis {            mark(v);        }    });}impl<T: Eq + Hash + Trace> FinalizeforLinkedList<T> {}// SAFETY: All the elements of the `LinkedList` are correctly marked.unsafe impl<T: Eq + Hash + Trace> TraceforLinkedList<T> {custom_trace!(this, mark, {#[allow(clippy::explicit_iter_loop)]forvinthis.iter() {            mark(v);        }    });}impl<T> FinalizeforPhantomData<T> {}// SAFETY: A `PhantomData` doesn't have inner data that needs to be marked.unsafe impl<T> TraceforPhantomData<T> {empty_trace!();}impl<T: Trace> FinalizeforVecDeque<T> {}// SAFETY: All the elements of the `VecDeque` are correctly marked.unsafe impl<T: Trace> TraceforVecDeque<T> {custom_trace!(this, mark, {forvinthis {            mark(v);        }    });}impl<T: ToOwned + Trace +?Sized> FinalizeforCow<'static, T> {}// SAFETY: 'static references don't need to be traced, since they live indefinitely, and the owned// variant is correctly marked.unsafe impl<T: ToOwned + Trace +?Sized> TraceforCow<'static, T>whereT::Owned: Trace,{custom_trace!(this, mark, {if letCow::Owned(v) = this {            mark(v);        }    });}impl<T: Trace> FinalizeforCell<Option<T>> {}// SAFETY: Taking and setting is done in a single action, and recursive traces should find a `None`// value instead of the original `T`, making this safe.unsafe impl<T: Trace> TraceforCell<Option<T>> {custom_trace!(this, mark, {if letSome(v) = this.take() {            mark(&v);            this.set(Some(v));        }    });}impl<T: Trace> FinalizeforOnceCell<T> {}// SAFETY: We only trace the inner cell if the cell has a value.unsafe impl<T: Trace> TraceforOnceCell<T> {custom_trace!(this, mark, {if letSome(v) = this.get() {            mark(v);        }    });}#[cfg(feature ="icu")]modicu {useicu_locale_core::{LanguageIdentifier, Locale};use crate::{Finalize, Trace};implFinalizeforLanguageIdentifier {}// SAFETY: `LanguageIdentifier` doesn't have any traceable data.unsafe implTraceforLanguageIdentifier {empty_trace!();    }implFinalizeforLocale {}// SAFETY: `LanguageIdentifier` doesn't have any traceable data.unsafe implTraceforLocale {empty_trace!();    }}#[cfg(feature ="boa_string")]modboa_string_trace {use crate::{Finalize, Trace};// SAFETY: `boa_string::JsString` doesn't have any traceable data.unsafe implTraceforboa_string::JsString {empty_trace!();    }implFinalizeforboa_string::JsString {}}#[cfg(feature ="either")]modeither_trace {use crate::{Finalize, Trace};impl<L: Trace, R: Trace> Finalizeforeither::Either<L, R> {}unsafe impl<L: Trace, R: Trace> Traceforeither::Either<L, R> {custom_trace!(this, mark, {matchthis {                either::Either::Left(l) => mark(l),                either::Either::Right(r) => mark(r),            }        });    }}