pbt 0.4.25

use {
    crate::{
        cache,
        multiset::Multiset,
        reflection::{
            AlgebraicTypeFormer, Erased, ErasedTermBuckets, PrecomputedTypeFormer, Type, info,
            type_of,
        },
        scc::StronglyConnectedComponents,
        search,
        size::{Size, Sizes},
    },
    alloc::{collections::BTreeSet, vec::Vec},
    core::{fmt, mem, num::NonZero, ops::Deref, ptr},
    wyrand::WyRand,
};

/// Wrapper around a constructor function that generates a value directly.
#[non_exhaustive]
#[derive(Clone, Copy, Hash)]
pub struct ArbitraryFn<T> {
    /// Generate one application of this constructor directly.
    pub call: for<'prng, 'swarm> fn(
        &'prng mut WyRand,
        &'swarm mut Swarm,
        Sizes,
    ) -> Result<Option<T>, MaybeUninstantiable>,
}

/// Constructor exclusions sampled once for every algebraic type in one term.
#[derive(Default)]
pub struct Swarm {
    /// Exclusions for the types encountered while generating this term.
    ///
    /// A hand-rolled inline buffer for the first few entries regressed the
    /// small generation benchmark, so this stays as the plain `Vec`.
    entries: Vec<SwarmEntry>,
}

/// Constructor exclusions and cached loop availability for one algebraic type in one swarm.
struct SwarmEntry {
    /// The 1-indexed constructors masked out for this type.
    excluded_variant_indices: ExcludedVariantIndices,
    /// The number of potential loop constructors not masked out for this type.
    n_available_potential_loops: usize,
    /// The type whose constructors were sampled.
    ty: Type,
}

/// Masked constructors for one type.
enum ExcludedVariantIndices {
    /// A compact bit mask for the common case where constructor indices fit.
    BitMask(usize),
    /// A plain list for enums too wide to fit in one machine word.
    Indices(Box<[NonZero<usize>]>),
}

impl ExcludedVariantIndices {
    /// Whether this 1-indexed constructor is masked out.
    #[inline]
    #[must_use]
    fn contains(&self, index: NonZero<usize>) -> bool {
        match *self {
            Self::BitMask(mask) => {
                // SAFETY: `index` is nonzero, so subtracting one cannot underflow.
                let zero_based = unsafe { index.get().unchecked_sub(1) };
                mask & (1_usize << zero_based) != 0
            }
            Self::Indices(ref indices) => indices.contains(&index),
        }
    }

    /// Whether no constructors are masked out.
    #[inline]
    #[must_use]
    fn is_empty(&self) -> bool {
        match *self {
            Self::BitMask(mask) => mask == 0,
            Self::Indices(ref indices) => indices.is_empty(),
        }
    }

    /// Sample masked constructors for swarm testing.
    #[inline]
    #[must_use]
    #[expect(
        clippy::as_conversions,
        reason = "fine: `usize::BITS` always fits into `usize`"
    )]
    fn sample(n_ctors: usize, prng: &mut WyRand) -> Self {
        if n_ctors <= usize::BITS as usize {
            Self::sample_bit_mask(n_ctors, prng)
        } else {
            Self::sample_indices(n_ctors, prng)
        }
    }

    /// Sample a bit mask for a type with few constructors.
    #[inline]
    #[must_use]
    #[expect(
        clippy::as_conversions,
        clippy::arithmetic_side_effects,
        clippy::cast_possible_truncation,
        clippy::integer_division_remainder_used,
        reason = "fine: every modulo divisor and shift is bounded by constructor count guards"
    )]
    fn sample_bit_mask(n_ctors: usize, prng: &mut WyRand) -> Self {
        if n_ctors <= 1 || (prng.rand() & 1) == 0 {
            return Self::BitMask(0);
        }

        // SAFETY: We returned above unless `n_ctors > 1`.
        let non_all_allowed_counts = unsafe { n_ctors.unchecked_sub(1) };
        // SAFETY: `non_all_allowed_counts > 0`, and adding one yields at most `n_ctors`.
        let allowed_count =
            unsafe { (prng.rand() as usize % non_all_allowed_counts).unchecked_add(1) };
        let mut allowed_mask = 0_usize;
        let mut n_allowed = 0_usize;
        while n_allowed < allowed_count {
            let zero_based = prng.rand() as usize % n_ctors;
            let bit = 1_usize << zero_based;
            if allowed_mask & bit == 0 {
                allowed_mask |= bit;
                // SAFETY: `n_allowed < allowed_count <= n_ctors <= usize::BITS`.
                n_allowed = unsafe { n_allowed.unchecked_add(1) };
            }
        }

        #[expect(
            clippy::arithmetic_side_effects,
            reason = "`n_ctors < usize::BITS`, so the shifted mask is nonzero"
        )]
        let all_constructors = if n_ctors == usize::BITS as usize {
            usize::MAX
        } else {
            (1_usize << n_ctors) - 1
        };
        Self::BitMask(all_constructors & !allowed_mask)
    }

    /// Sample explicit indices for an unusually wide enum.
    #[inline]
    #[must_use]
    #[expect(
        clippy::as_conversions,
        clippy::arithmetic_side_effects,
        clippy::cast_possible_truncation,
        clippy::integer_division_remainder_used,
        reason = "fine: random words are intentionally reduced modulo constructor counts"
    )]
    fn sample_indices(n_ctors: usize, prng: &mut WyRand) -> Self {
        if n_ctors <= 1 || (prng.rand() & 1) == 0 {
            return Self::Indices(Box::new([]));
        }

        // SAFETY: We returned above unless `n_ctors > 1`.
        let non_all_allowed_counts = unsafe { n_ctors.unchecked_sub(1) };
        // SAFETY: `non_all_allowed_counts > 0`, and adding one yields at most `n_ctors`.
        let allowed_count =
            unsafe { (prng.rand() as usize % non_all_allowed_counts).unchecked_add(1) };
        let mut allowed = Vec::new();
        while allowed.len() < allowed_count {
            let zero_based = prng.rand() as usize % n_ctors;
            // SAFETY: `zero_based < n_ctors`, so adding one cannot overflow.
            let one_based_usize = unsafe { zero_based.unchecked_add(1) };
            // SAFETY: We just added one.
            let one_based = unsafe { NonZero::new_unchecked(one_based_usize) };
            if !allowed.contains(&one_based) {
                allowed.push(one_based);
            }
        }

        let mut indices = Vec::new();
        for one_based_usize in 1..=n_ctors {
            // SAFETY: The inclusive range starts at one.
            let one_based = unsafe { NonZero::new_unchecked(one_based_usize) };
            if !allowed.contains(&one_based) {
                indices.push(one_based);
            }
        }
        Self::Indices(indices.into_boxed_slice())
    }
}

/// Wrapper around a constructor function that consumes erased field buckets.
#[non_exhaustive]
#[derive(Clone, Copy, Hash)]
pub struct CtorFn<T> {
    /// Function to pbt a term which is an
    /// application of this constructor to arbitrary fields.
    pub call: for<'terms> fn(&'terms mut ErasedTermBuckets) -> Option<T>,
}

/// A constructor function together with its stable constructor index and metadata.
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Hash)]
pub struct IndexedCtorFn<T> {
    /// Generate this constructor directly, without erased field buckets.
    pub arbitrary: ArbitraryFn<T>,
    /// Function to invoke this constructor on a collection of fields.
    pub call: CtorFn<T>,
    /// 1-indexed constructor/variant index.
    pub index: NonZero<usize>,
    /// The number of "big" types in this constructor:
    /// types that either are inductive themselves
    /// or contain a big type.
    pub n_big: usize,
}

/// Decompose this value into a
/// constructor (by index) and
/// its associated fields.
#[non_exhaustive]
#[repr(transparent)]
#[derive(Clone, Copy, Hash)]
pub struct ElimFn<T> {
    /// Function that decomposes a value into constructor index and immediate fields.
    pub call: fn(T) -> Decomposition,
}

/// Algebraic type description: introductions plus one elimination rule.
#[derive(Clone, Debug)]
#[expect(clippy::exhaustive_structs, reason = "constructed in macros")]
pub struct Algebraic<T> {
    /// The rule that decomposes a value into constructor index and fields.
    pub elimination_rule: ElimFn<T>,
    /// The rules that construct values from immediate fields.
    pub introduction_rules: Box<[IntroductionRule<T>]>,
}

/// Literal type description, used to bottom out structural recursion.
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Literal<T> {
    /// Parse a cached string payload.
    pub deserialize: fn(&str) -> Option<T>,
    /// Generate a literal directly from the PRNG.
    pub generate: for<'prng> fn(&'prng mut WyRand) -> T,
    /// Convert a literal into a cache payload.
    pub serialize: fn(&T) -> String,
    /// Produce smaller literal candidates.
    pub shrink: fn(T) -> Box<dyn Iterator<Item = T>>,
}

/// The complete generation and shrinking description for one type.
#[non_exhaustive]
#[derive(Clone, Debug)]
pub enum TypeFormer<T> {
    /// A type built from a finite set of constructors.
    Algebraic(Algebraic<T>),
    /// A type generated and shrunk directly.
    Literal(Literal<T>),
}

/// Failure modes for generation attempts.
#[derive(Clone, Debug)]
#[expect(clippy::exhaustive_enums, reason = "used internally")]
pub enum MaybeUninstantiable {
    /// The current size was insufficient; a larger size might work.
    Retry,
    /// The type has no available value.
    Uninstantiable,
}

/// Decomposition of an algebraic value into its
/// constructor index and all immediate fields.
#[derive(Debug)]
#[expect(clippy::exhaustive_structs, reason = "constructed in macros")]
pub struct Decomposition {
    /// 1-indexed constructor/variant index.
    pub ctor_idx: NonZero<usize>,
    /// The immediate fields grouped into erased buckets by concrete type.
    pub fields: ErasedTermBuckets,
}

/// One constructor rule for an algebraic type.
#[derive(Clone, Debug)]
#[expect(clippy::exhaustive_structs, reason = "constructed in macros")]
pub struct IntroductionRule<T> {
    /// Generate this constructor directly, without erased field buckets.
    pub arbitrary: ArbitraryFn<T>,
    /// Function to invoke this constructor on a collection of fields.
    pub call: CtorFn<T>,
    /// The multiset of types necessary to call this constructor.
    pub immediate_dependencies: Multiset<Type>,
}

/// Types that can be generated, reflected, traversed, and shrunk by `pbt`.
pub trait Pbt: 'static + Clone + fmt::Debug + Eq {
    /// Register the immediate dependencies of `Self` within the current
    /// type-registration traversal.
    ///
    /// In practice, implementations should:
    /// compute `ty = ::pbt::reflection::type_of::<Self>()`,
    /// insert `ty` into `visited`,
    /// and then call `::pbt::reflection::register::<Dependency>(visited.clone(), sccs)`
    /// for each immediate dependency needed by `Self`.
    ///
    /// The surrounding registration walk is responsible for publishing the final
    /// type metadata and SCC node once this dependency recursion has completed.
    fn register_all_immediate_dependencies(
        visited: &mut BTreeSet<Type>,
        sccs: &mut StronglyConnectedComponents,
    );

    /// The exhaustive disjoint set of methods
    /// to pbt a term of this type.
    fn type_former() -> TypeFormer<Self>;

    /// Visit all terms of type `V` in this abstract syntax tree.
    /// Your implementation should always follow this formula:
    /// `pbt::pbt::visit_self(self).chain(... recurse into fields ...)`.
    fn visit_deep<V>(&self) -> impl Iterator<Item = V>
    where
        V: Pbt;
}

impl<T> ArbitraryFn<T> {
    /// Erase this direct constructor generator for storage in the global registry.
    #[inline]
    #[must_use]
    pub const fn erase(self) -> ArbitraryFn<Erased> {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<ArbitraryFn<T>, ArbitraryFn<Erased>>(self) }
    }

    /// Wrap a direct constructor generator.
    #[inline]
    pub const fn new(
        call: for<'prng, 'swarm> fn(
            &'prng mut WyRand,
            &'swarm mut Swarm,
            Sizes,
        ) -> Result<Option<T>, MaybeUninstantiable>,
    ) -> Self {
        Self { call }
    }
}

impl<T> CtorFn<T> {
    /// Erase this constructor function for storage in the global registry.
    #[inline]
    #[must_use]
    pub const fn erase(self) -> CtorFn<Erased> {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<CtorFn<T>, CtorFn<Erased>>(self) }
    }

    /// Wrap a constructor function.
    #[inline]
    pub const fn new(call: for<'terms> fn(&'terms mut ErasedTermBuckets) -> Option<T>) -> Self {
        Self { call }
    }
}

impl ArbitraryFn<Erased> {
    /// Interpret this type-erased generator as a generator for a specific type.
    /// # Safety
    /// You'd better be damn well sure that you're specifying the right type.
    #[inline]
    #[must_use]
    pub const unsafe fn unerase<T>(
        self,
    ) -> for<'prng, 'swarm> fn(
        &'prng mut WyRand,
        &'swarm mut Swarm,
        Sizes,
    ) -> Result<Option<T>, MaybeUninstantiable> {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<ArbitraryFn<Erased>, ArbitraryFn<T>>(self) }.call
    }
}

impl CtorFn<Erased> {
    /// Interpret this type-erased generator as a generator for a specific type.
    /// # Safety
    /// You'd better be damn well sure that you're specifying the right type.
    #[inline]
    #[must_use]
    pub const unsafe fn unerase<T>(
        self,
    ) -> for<'terms> fn(&'terms mut ErasedTermBuckets) -> Option<T> {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<CtorFn<Erased>, CtorFn<T>>(self) }.call
    }
}

impl<T> fmt::Debug for ArbitraryFn<T> {
    #[inline]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("(|prng, sizes| ...)")
    }
}

impl<T> fmt::Debug for CtorFn<T> {
    #[inline]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("(|terms| ...)")
    }
}

impl<T> Deref for ArbitraryFn<T> {
    type Target = for<'prng, 'swarm> fn(
        &'prng mut WyRand,
        &'swarm mut Swarm,
        Sizes,
    ) -> Result<Option<T>, MaybeUninstantiable>;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.call
    }
}

impl<T> Deref for CtorFn<T> {
    type Target = for<'terms> fn(&'terms mut ErasedTermBuckets) -> Option<T>;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.call
    }
}

impl<T> Deref for IndexedCtorFn<T> {
    type Target = CtorFn<T>;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.call
    }
}

impl<T> ElimFn<T> {
    /// Erase this eliminator for storage in the global registry.
    #[inline]
    #[must_use]
    pub const fn erase(self) -> ElimFn<Erased> {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<ElimFn<T>, ElimFn<Erased>>(self) }
    }

    /// Wrap an eliminator function.
    #[inline]
    pub const fn new(call: fn(T) -> Decomposition) -> Self {
        Self { call }
    }
}

impl<T> fmt::Debug for ElimFn<T> {
    #[inline]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("(|ctor| ...)")
    }
}

impl ElimFn<Erased> {
    /// Interpret this type-erased generator as a generator for a specific type.
    /// # Safety
    /// You'd better be damn well sure that you're specifying the right type.
    #[inline]
    #[must_use]
    pub const unsafe fn unerase<T>(self) -> fn(T) -> Decomposition {
        // SAFETY: Same size, still a function pointer with the same arguments.
        unsafe { mem::transmute::<ElimFn<Erased>, ElimFn<T>>(self) }.call
    }
}

impl<T> Deref for ElimFn<T> {
    type Target = fn(T) -> Decomposition;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.call
    }
}

impl Swarm {
    /// Drop this attempt's exclusions while keeping storage for the next retry.
    #[inline]
    fn clear(&mut self) {
        self.entries.clear();
    }

    /// Get one sampled entry by a previously returned index.
    #[inline]
    fn entry(&self, index: usize) -> &SwarmEntry {
        // SAFETY: Callers use indices returned by `entry_index`, and swarm entries
        // are only appended until `clear` begins the next top-level attempt.
        unsafe { self.entries.get_unchecked(index) }
    }

    /// The entry index for `ty`, sampled once per swarm.
    #[inline]
    fn entry_index(
        &mut self,
        ty: Type,
        n_ctors: usize,
        potential_loops: &[IndexedCtorFn<Erased>],
        prng: &mut WyRand,
    ) -> usize {
        if let Some(index) = self.entries.iter().position(|entry| entry.ty == ty) {
            return index;
        }

        let excluded_variant_indices = ExcludedVariantIndices::sample(n_ctors, prng);
        let n_available_potential_loops = potential_loops
            .iter()
            .filter(|&ctor| !excluded_variant_indices.contains(ctor.index))
            .count();
        let index = self.entries.len();
        self.entries.push(SwarmEntry {
            excluded_variant_indices,
            n_available_potential_loops,
            ty,
        });
        index
    }
}

/// Generate an arbitrary value of `T`, increasing size on retryable failures.
#[inline]
pub fn arbitrary<T>(prng: &mut WyRand, mut size: Size) -> Option<T>
where
    T: Pbt,
{
    let mut swarm = Swarm::default();
    loop {
        swarm.clear();
        match try_arbitrary::<T>(prng, &mut swarm, size.copy_for_retry()) {
            Ok(t) => return Some(t),
            Err(MaybeUninstantiable::Retry) => size.increment(),
            Err(MaybeUninstantiable::Uninstantiable) => return None,
        }
    }
}

/// Generate one constructor field.
/// # Errors
/// Returns [`MaybeUninstantiable::Retry`] or
/// [`MaybeUninstantiable::Uninstantiable`] from field generation after
/// draining unused field-size partitions for the abandoned constructor attempt.
#[inline]
pub fn try_arbitrary_field<T>(
    sizes: &mut Sizes,
    prng: &mut WyRand,
    swarm: &mut Swarm,
) -> Result<T, MaybeUninstantiable>
where
    T: Pbt,
{
    sizes
        .try_arbitrary::<T>(prng, swarm)
        .inspect_err(|_| sizes.discard_remaining())
}

/// Pick one constructor from `candidates` after removing this swarm's exclusions.
#[inline]
#[expect(
    clippy::as_conversions,
    clippy::cast_possible_truncation,
    reason = "fine: definitely not > `u64::MAX` constructors"
)]
fn choose_ctor<'ctors>(
    prng: &mut WyRand,
    excluded: &ExcludedVariantIndices,
    candidates: &'ctors [IndexedCtorFn<Erased>],
) -> Option<&'ctors IndexedCtorFn<Erased>> {
    let n = NonZero::new(candidates.len())?;
    if excluded.is_empty() {
        let i = prng.rand() as usize % n;
        // SAFETY: Bounded by length above (see `% n`).
        return Some(unsafe { candidates.get_unchecked(i) });
    }
    if candidates.len() == 1 {
        // SAFETY: We just checked the length.
        let ctor = unsafe { candidates.get_unchecked(0) };
        if excluded.contains(ctor.index) {
            return None;
        }
        return Some(ctor);
    }
    if candidates.iter().all(|ctor| excluded.contains(ctor.index)) {
        return None;
    }

    let mut canary = 0_u8;
    loop {
        let i = prng.rand() as usize % n;
        // SAFETY: Bounded by length above (see `% n`).
        let ctor = unsafe { candidates.get_unchecked(i) };
        if !excluded.contains(ctor.index) {
            return Some(ctor);
        }
        canary = canary.checked_add(1)?;
    }
}

/// Try to generate an arbitrary term of type `T`.
/// # Errors
/// Returns [`MaybeUninstantiable::Retry`] when rejection sampling could not
/// decide at this size, or [`MaybeUninstantiable::Uninstantiable`] when `T`
/// has no structurally available constructor.
#[inline]
pub fn try_arbitrary<T>(
    prng: &mut WyRand,
    swarm: &mut Swarm,
    size: Size,
) -> Result<T, MaybeUninstantiable>
where
    T: Pbt,
{
    let info = info::<T>();
    match info.type_former {
        PrecomputedTypeFormer::Algebraic(ref adt) => {
            let ty = info.vertex.ty;
            let n_ctors = adt.all_constructors.len();
            let potential_loops = adt.potential_loops();
            let potential_leaves = adt.potential_leaves();
            let swarm_entry_index = swarm.entry_index(ty, n_ctors, potential_loops, prng);
            let local_size =
                match NonZero::new(swarm.entry(swarm_entry_index).n_available_potential_loops) {
                    Some(branching_factor) => size.divided_by(branching_factor),
                    None => size,
                };
            let mut canary = 0_u8;
            loop {
                let (ctor, minus_one) = {
                    let excluded = &swarm.entry(swarm_entry_index).excluded_variant_indices;
                    if local_size.should_recurse(prng)
                        && let Some(ctor) = choose_ctor(prng, excluded, potential_loops)
                    {
                        (ctor, true)
                    } else {
                        let Some(ctor) = choose_ctor(prng, excluded, potential_leaves) else {
                            if potential_leaves.is_empty() {
                                return Err(MaybeUninstantiable::Uninstantiable);
                            }
                            return Err(MaybeUninstantiable::Retry);
                        };
                        (ctor, false)
                    }
                };
                let sizes = local_size.partition_into(ctor.n_big, prng, minus_one);
                // SAFETY: By the soundness of the type-`TypeId` relation,
                // which holds as long as no lifetime subtyping takes place,
                // and since only `'static` types have IDs and we can't generate functions,
                // it holds here.
                if let Some(result) = unsafe { ctor.arbitrary.unerase::<T>() }(prng, swarm, sizes)?
                {
                    return Ok(result);
                }

                // If that failed, then there's (almost surely) a Sigma-type,
                // in which case its instantiability might be size-dependent
                // (e.g. a non-empty vector/string/etc.), in which case
                // we should occasionally bump the size just in case:
                let Some(next_canary) = canary.checked_add(1) else {
                    return Err(MaybeUninstantiable::Retry);
                };
                canary = next_canary;
            }
        }
        PrecomputedTypeFormer::Literal {
            generate: erased_generate,
            ..
        } => {
            // SAFETY: Undoing an earlier transmute.
            let generate = unsafe {
                mem::transmute::<fn(&mut WyRand) -> Erased, fn(&mut WyRand) -> T>(erased_generate)
            };
            // All literals are instantiable.
            Ok(generate(prng))
        }
    }
}

/// Check that eliminating a term and them
/// immediately constructing it again
/// is a no-op, i.e. the identity function.
/// # Panics
/// If that's not the case.
#[inline]
pub fn check_eta_expansion<T>()
where
    T: Pbt,
{
    let info = info::<T>();
    let PrecomputedTypeFormer::Algebraic(AlgebraicTypeFormer {
        ref all_constructors,
        eliminator: erased_eliminator,
        ..
    }) = info.type_former
    else {
        return;
    };
    // SAFETY: Undoing an earlier transmute.
    let eliminator = unsafe { mem::transmute::<ElimFn<Erased>, ElimFn<T>>(erased_eliminator) };
    let () = search::assert_eq(32, |orig: &T| {
        let Decomposition {
            ctor_idx,
            mut fields,
        } = eliminator(orig.clone());
        // SAFETY: By the correct implementation of `eliminator`
        // (i.e., by macro logic plus the few implementations in this crate).
        #[expect(clippy::multiple_unsafe_ops_per_block, reason = "logically grouped")]
        let (ctor, _) = *unsafe { all_constructors.get_unchecked(ctor_idx.get().unchecked_sub(1)) };
        // SAFETY: By the soundness of the type-`TypeId` relation,
        // which holds as long as no lifetime subtyping takes place,
        // and since only `'static` types have IDs and we can't generate functions,
        // it holds here.
        let f = unsafe { ctor.unerase::<T>() };
        let constructed = f(&mut fields);
        assert!(
            fields.is_empty(),
            "internal `pbt` error: leftover terms after applying a constructor: {fields:#?}",
        );
        (constructed, Some(orig.clone()))
    });
}

/// Yield `s` as a `V` if `S` and `V` are the same registered type.
#[inline]
pub fn visit_self<V, S>(s: &S) -> impl Iterator<Item = V>
where
    V: Pbt,
    S: Pbt,
{
    visit_self_opt::<V, S>(s).cloned().into_iter()
}

/// Borrow `s` as a `V` if `S` and `V` are the same registered type.
#[inline]
pub fn visit_self_opt<V, S>(s: &S) -> Option<&V>
where
    V: Pbt,
    S: 'static,
{
    (type_of::<V>() == type_of::<S>()).then(|| {
        let source_ptr: *const S = ptr::from_ref(s);
        let target_ptr: *const V = source_ptr.cast();
        // SAFETY: `S` and `V` are the same type.
        unsafe { &*target_ptr }
    })
}

/// Move `s` out as a `V` if `S` and `V` are the same registered type.
#[inline]
pub fn visit_self_owned<V, S>(s: S) -> Option<V>
where
    V: Pbt,
    S: Pbt,
{
    (type_of::<V>() == type_of::<S>()).then(|| {
        let source_ptr: *const S = ptr::from_ref(&s);
        let target_ptr: *const V = source_ptr.cast();
        // SAFETY: `S` and `V` are the same type.
        let v: V = unsafe { ptr::read(target_ptr) };
        #[expect(clippy::mem_forget, reason = "intentional")]
        let () = mem::forget(s);
        v
    })
}

/// Deserialize a cached witness term of type `T` and push it into a typed term bucket.
#[inline]
pub(crate) fn deserialize_cached_term_into_buckets<T>(
    term: &cache::CachedTerm,
    terms: &mut ErasedTermBuckets,
) -> bool
where
    T: Pbt,
{
    let Some(value) = cache::deserialize_term::<T>(term) else {
        return false;
    };
    terms.push(value);
    true
}