rustc_type_ir/

interner.rs

use std::borrow::Borrow;
use std::fmt::Debug;
use std::hash::Hash;
use std::ops::Deref;

use rustc_ast_ir::Movability;
use rustc_ast_ir::visit::VisitorResult;
#[cfg(feature = "nightly")]
use rustc_data_structures::stable_hash::StableHash;
use rustc_index::bit_set::DenseBitSet;

use crate::fold::TypeFoldable;
use crate::inherent::*;
use crate::intern::Interned;
use crate::ir_print::IrPrint;
use crate::lang_items::{SolverAdtLangItem, SolverProjectionLangItem, SolverTraitLangItem};
use crate::relate::Relate;
use crate::search_graph::RequiredDepth;
use crate::solve::{
    AccessedOpaques, CanonicalInputData, Certainty, ExternalConstraintsData, QueryResult, inspect,
};
use crate::visit::{Flags, TypeVisitable};
use crate::{
    self as ty, AliasTermKind, BoundRegion, BoundVar, CanonicalParamEnvCache, DebruijnIndex,
    Region, RegionKind, RegionVid, TraitRef, search_graph,
};

/// The central trait in the shared abstraction layer, specifying all implementation-specific
/// details for rustc and rust-analyzer.
///
/// Among its essential responsibilities:
/// - it specifies the concrete types used by each implementation via its associated types; these
///   form the backbone of how each compiler frontend instantiates the shared IR.
/// - it provides the context required by the solver (e.g., querying lang items, enumerating all
///   blanket impls for a trait)
/// - it implements [IrPrint] for formatting and tracing.
///
/// In rustc, it is [implemented by TyCtxt][interner-impl-doc]. In rust-analyzer, the implementing
/// type is named [DbInterner][dbinterner-code] (as it performs most interning through the salsa
/// database).
///
/// More information can also be found in the dedicated chapter in the dev-guide, in [this
/// section][dev-guide].
///
/// [interner-impl-doc]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.TyCtxt.html#impl-Interner-for-TyCtxt%3C'tcx%3E
/// [dbinterner-code]: https://github.com/rust-lang/rust-analyzer/blob/a50c1ccc9cf3dab1afdc857a965a9992fbad7a53/crates/hir-ty/src/next_solver/interner.rs#L272
/// [dev-guide]: https://rustc-dev-guide.rust-lang.org/solve/sharing-crates-with-rust-analyzer.html#trait-interner
#[cfg_attr(feature = "nightly", rustc_diagnostic_item = "type_ir_interner")]
pub trait Interner:
    Sized
    + Copy
    + IrPrint<ty::AliasTy<Self>>
    + IrPrint<ty::AliasTerm<Self>>
    + IrPrint<ty::TraitRef<Self>>
    + IrPrint<ty::TraitClause<Self>>
    + IrPrint<ty::HostEffectClause<Self>>
    + IrPrint<ty::ExistentialTraitRef<Self>>
    + IrPrint<ty::ExistentialProjection<Self>>
    + IrPrint<ty::ProjectionClause<Self>>
    + IrPrint<ty::NormalizesTo<Self>>
    + IrPrint<ty::SubtypePredicate<Self>>
    + IrPrint<ty::CoercePredicate<Self>>
    + IrPrint<ty::FnSig<Self>>
    + IrPrint<ty::PatternKind<Self>>
{
    fn next_trait_solver_globally(self) -> bool {
        true
    }

    type DefId: DefId<Self>;
    type LocalDefId: Copy + Debug + Hash + Eq + Into<Self::DefId> + TypeFoldable<Self>;
    // Various more specific `DefId`s.
    //
    // rustc just defines them all to be `DefId`, but rust-analyzer uses different types so this is convenient for it.
    //
    // Note: The `TryFrom<DefId>` always succeeds (in rustc), so don't use it to check if some `DefId`
    // is of some specific type!
    type TraitId: SpecificDefId<Self>;
    type ForeignId: SpecificDefId<Self>;
    type FunctionId: SpecificDefId<Self>;
    type ClosureId: SpecificDefId<Self>;
    type CoroutineClosureId: SpecificDefId<Self>;
    type CoroutineId: SpecificDefId<Self>;
    type AdtId: SpecificDefId<Self>;
    type ImplId: SpecificDefId<Self>;
    type AnonConstId: SpecificDefId<Self>;
    type TraitAssocTyId: SpecificDefId<Self>
        + Into<Self::TraitAssocTermId>
        + TryFrom<Self::TraitAssocTermId>;
    type TraitAssocConstId: SpecificDefId<Self>
        + Into<Self::TraitAssocTermId>
        + TryFrom<Self::TraitAssocTermId>;
    type TraitAssocTermId: SpecificDefId<Self>;
    type OpaqueTyId: SpecificDefId<Self, Self::LocalOpaqueTyId>;
    type LocalOpaqueTyId: Copy
        + Debug
        + Hash
        + Eq
        + Into<Self::OpaqueTyId>
        + Into<Self::LocalDefId>
        + Into<Self::DefId>
        + TypeFoldable<Self>;
    type FreeTyAliasId: SpecificDefId<Self> + Into<Self::FreeTermAliasId>;
    type FreeConstAliasId: SpecificDefId<Self> + Into<Self::FreeTermAliasId>;
    type FreeTermAliasId: SpecificDefId<Self>;
    type ImplOrTraitAssocTyId: SpecificDefId<Self> + Into<Self::ImplOrTraitAssocTermId>;
    type ImplOrTraitAssocConstId: SpecificDefId<Self> + Into<Self::ImplOrTraitAssocTermId>;
    type ImplOrTraitAssocTermId: SpecificDefId<Self>;
    type InherentAssocTyId: SpecificDefId<Self> + Into<Self::InherentAssocTermId>;
    type InherentAssocConstId: SpecificDefId<Self> + Into<Self::InherentAssocTermId>;
    type InherentAssocTermId: SpecificDefId<Self>;
    type Span: Span<Self>;

    type GenericArgs: GenericArgs<Self>;
    type GenericArgsSlice: Copy + Debug + Hash + Eq + SliceLike<Item = Self::GenericArg>;
    type GenericArg: GenericArg<Self>;
    type Term: Term<Self>;

    type BoundVarKinds: BoundVarKinds<Self>;

    type PredefinedOpaques: Copy
        + Debug
        + Hash
        + Eq
        + TypeFoldable<Self>
        + SliceLike<Item = (ty::OpaqueTypeKey<Self>, Self::Ty)>;
    fn mk_predefined_opaques_in_body(
        self,
        data: &[(ty::OpaqueTypeKey<Self>, Self::Ty)],
    ) -> Self::PredefinedOpaques;

    type LocalDefIds: Copy
        + Debug
        + Hash
        + Default
        + Eq
        + TypeVisitable<Self>
        + SliceLike<Item = Self::LocalDefId>;

    type CanonicalVarKinds: Copy
        + Debug
        + Hash
        + Eq
        + SliceLike<Item = ty::CanonicalVarKind<Self>>
        + Default;
    fn mk_canonical_var_kinds(
        self,
        kinds: &[ty::CanonicalVarKind<Self>],
    ) -> Self::CanonicalVarKinds;

    type ExternalConstraints: Copy
        + Debug
        + Hash
        + Eq
        + TypeFoldable<Self>
        + Deref<Target = ExternalConstraintsData<Self>>;
    fn mk_external_constraints(
        self,
        data: ExternalConstraintsData<Self>,
    ) -> Self::ExternalConstraints;

    type DepNodeIndex;
    type Tracked<T: Debug + Clone>: Debug;
    fn mk_tracked<T: Debug + Clone>(
        self,
        data: T,
        dep_node: Self::DepNodeIndex,
    ) -> Self::Tracked<T>;
    fn get_tracked<T: Debug + Clone>(self, tracked: &Self::Tracked<T>) -> T;
    fn with_cached_task<T>(self, task: impl FnOnce() -> T) -> (T, Self::DepNodeIndex);

    // Kinds of tys
    type Ty: Ty<Self>;
    type Tys: Tys<Self>;
    type FnInputTys: Copy + Debug + Hash + Eq + SliceLike<Item = Self::Ty> + TypeVisitable<Self>;
    type ParamTy: ParamLike;
    type Symbol: Symbol<Self>;

    // Things stored inside of tys
    type ErrorGuaranteed: Copy + Debug + Hash + Eq;
    type BoundExistentialPredicates: BoundExistentialPredicates<Self>;
    type AllocId: Copy + Debug + Hash + Eq;
    type Pat: Copy
        + Debug
        + Hash
        + Eq
        + Debug
        + Relate<Self>
        + Flags
        + IntoKind<Kind = ty::PatternKind<Self>>;
    type PatList: Copy
        + Debug
        + Hash
        + Default
        + Eq
        + TypeVisitable<Self>
        + SliceLike<Item = Self::Pat>;
    type Safety: Safety<Self>;

    // Kinds of consts
    type Const: Const<Self>;
    type Consts: Copy + Debug + Hash + Eq + SliceLike<Item = Self::Const> + Default;
    type ParamConst: Copy + Debug + Hash + Eq + ParamLike;
    type ValueConst: ValueConst<Self>;
    type ExprConst: ExprConst<Self>;
    type ValTree: Copy + Debug + Hash + Eq + IntoKind<Kind = ty::ValTreeKind<Self>>;
    type ScalarInt: Copy + Debug + Hash + Eq;

    // Kinds of regions
    /// (2026/08/13)
    /// Do not uplift, the underlying types differ between r-a and rustc.
    ///
    /// See <https://github.com/rust-lang/rust/pull/160986#issuecomment-5269817932>.
    type EarlyParamRegion: ParamLike + RegionName<Self>;
    /// (2026/08/13)
    /// Do not uplift, the underlying types differ between r-a and rustc.
    ///
    /// See <https://github.com/rust-lang/rust/pull/160986#issuecomment-5269817932>.
    #[cfg(feature = "nightly")]
    type LateParamRegionKind: Clone
        + Copy
        + Debug
        + PartialEq
        + Eq
        + Hash
        + StableHash
        + DefIdGetter<Self>
        + RegionName<Self>;

    #[cfg(not(feature = "nightly"))]
    type LateParamRegionKind: Clone
        + Copy
        + Debug
        + PartialEq
        + Eq
        + Hash
        + DefIdGetter<Self>
        + RegionName<Self>;

    type InternedRegionKind: Interned<Self, Value = RegionKind<Self>>;

    type RegionAssumptions: Copy
        + Debug
        + Hash
        + Eq
        + SliceLike<Item = ty::OutlivesClause<Self, Self::GenericArg>>
        + TypeFoldable<Self>;

    // Predicates
    type ParamEnv: ParamEnv<Self>;
    type Predicate: Predicate<Self>;
    type Clause: Clause<Self>;
    type Clauses: Clauses<Self>;

    fn with_global_cache<R>(self, f: impl FnOnce(&mut search_graph::GlobalCache<Self>) -> R) -> R;

    fn with_canonical_param_env_cache<R>(
        self,
        f: impl FnOnce(&mut CanonicalParamEnvCache<Self>) -> R,
    ) -> R;

    /// Useful for testing. If a cache entry is replaced, this should
    /// (in theory) only happen when concurrent.
    fn assert_evaluation_is_concurrent(&self);

    fn expand_abstract_consts<T: TypeFoldable<Self>>(self, t: T) -> T;

    type GenericsOf: GenericsOf<Self>;
    fn generics_of(self, def_id: Self::DefId) -> Self::GenericsOf;

    type VariancesOf: Copy + Debug + SliceLike<Item = ty::Variance>;
    fn variances_of(self, def_id: Self::DefId) -> Self::VariancesOf;

    fn opt_alias_variances(
        self,
        kind: impl Into<ty::AliasTermKind<Self>>,
    ) -> Option<Self::VariancesOf>;

    fn type_of(self, def_id: Self::DefId) -> ty::EarlyBinder<Self, Self::Ty>;
    fn type_of_opaque_hir_typeck(
        self,
        def_id: Self::LocalOpaqueTyId,
    ) -> ty::EarlyBinder<Self, Self::Ty>;
    fn is_direct_const(self, alias: ty::AliasConstKind<Self>) -> bool;
    fn const_of_item(
        self,
        alias: ty::AliasConstKind<Self>,
    ) -> Option<ty::EarlyBinder<Self, Self::Const>>;
    fn anon_const_kind(self, def_id: Self::DefId) -> ty::AnonConstKind;

    fn def_span(self, def_id: Self::DefId) -> Self::Span;

    type AdtDef: AdtDef<Self>;
    fn adt_def(self, adt_def_id: Self::AdtId) -> Self::AdtDef;

    fn alias_const_kind_from_def_id(
        self,
        def_id: Self::DefId,
        inherent_args: ty::AliasConstInherentArgsKind,
    ) -> ty::AliasConstKind<Self>;

    // FIXME: remove in favor of explicit construction
    fn alias_term_kind_from_def_id(
        self,
        def_id: Self::DefId,
        inherent_args: ty::AliasConstInherentArgsKind,
    ) -> ty::AliasTermKind<Self>;

    fn trait_ref_and_own_args_for_alias(
        self,
        def_id: Self::TraitAssocTermId,
        args: Self::GenericArgs,
    ) -> (ty::TraitRef<Self>, Self::GenericArgsSlice);

    fn mk_args(self, args: &[Self::GenericArg]) -> Self::GenericArgs;

    fn mk_args_from_iter<I, T>(self, args: I) -> T::Output
    where
        I: Iterator<Item = T>,
        T: CollectAndApply<Self::GenericArg, Self::GenericArgs>;

    fn check_alias_term_args_compatible(
        self,
        term_kind: AliasTermKind<Self>,
        args: Self::GenericArgs,
    ) -> bool;

    fn debug_assert_args_compatible(self, def_id: Self::DefId, args: Self::GenericArgs);
    fn debug_assert_alias_term_args_compatible(
        self,
        term_kind: AliasTermKind<Self>,
        args: Self::GenericArgs,
    );

    /// Assert that the args from an `ExistentialTraitRef` or `ExistentialProjection`
    /// are compatible with the `DefId`.
    fn debug_assert_existential_args_compatible(self, def_id: Self::DefId, args: Self::GenericArgs);

    fn mk_type_list_from_iter<I, T>(self, args: I) -> T::Output
    where
        I: Iterator<Item = T>,
        T: CollectAndApply<Self::Ty, Self::Tys>;

    fn projection_parent(self, def_id: Self::TraitAssocTermId) -> Self::TraitId;

    /// This can be an impl, or a trait if this is a defaulted term.
    fn impl_or_trait_assoc_term_parent(self, def_id: Self::ImplOrTraitAssocTermId) -> Self::DefId;

    fn inherent_alias_term_parent(self, def_id: Self::InherentAssocTermId) -> Self::ImplId;

    fn recursion_limit(self) -> usize;

    type Features: Features<Self>;
    fn features(self) -> Self::Features;

    fn assumptions_on_binders(self) -> bool;

    fn renormalize_rigid_aliases(self) -> bool;

    fn coroutine_hidden_types(
        self,
        def_id: Self::CoroutineId,
    ) -> ty::EarlyBinder<Self, ty::Binder<Self, ty::CoroutineWitnessTypes<Self>>>;

    fn fn_sig(
        self,
        def_id: Self::FunctionId,
    ) -> ty::EarlyBinder<Self, ty::Binder<Self, ty::FnSig<Self>>>;

    fn coroutine_movability(self, def_id: Self::CoroutineId) -> Movability;

    fn coroutine_for_closure(self, def_id: Self::CoroutineClosureId) -> Self::CoroutineId;

    fn generics_require_sized_self(self, def_id: Self::DefId) -> bool;

    fn item_bounds(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn item_self_bounds(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn item_non_self_bounds(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn clauses_of(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn own_clauses_of(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn explicit_super_clauses_of(
        self,
        def_id: Self::TraitId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = (Self::Clause, Self::Span)>>;

    fn explicit_implied_clauses_of(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = (Self::Clause, Self::Span)>>;

    /// This is equivalent to computing the super-clauses of the trait for this impl
    /// and filtering them to the outlives clauses. This is purely for performance.
    fn impl_super_outlives(
        self,
        impl_def_id: Self::ImplId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;

    fn impl_is_const(self, def_id: Self::ImplId) -> bool;
    fn fn_is_const(self, def_id: Self::FunctionId) -> bool;
    fn closure_is_const(self, def_id: Self::ClosureId) -> bool;
    fn alias_has_const_conditions(self, def_id: Self::DefId) -> bool;
    fn const_conditions(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = ty::Binder<Self, ty::TraitRef<Self>>>>;
    fn explicit_implied_const_bounds(
        self,
        def_id: Self::DefId,
    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = ty::Binder<Self, ty::TraitRef<Self>>>>;

    fn impl_self_is_guaranteed_unsized(self, def_id: Self::ImplId) -> bool;

    fn has_target_features(self, def_id: Self::FunctionId) -> bool;

    fn require_projection_lang_item(
        self,
        lang_item: SolverProjectionLangItem,
    ) -> Self::TraitAssocTyId;

    fn require_trait_lang_item(self, lang_item: SolverTraitLangItem) -> Self::TraitId;

    fn require_adt_lang_item(self, lang_item: SolverAdtLangItem) -> Self::AdtId;

    fn is_projection_lang_item(
        self,
        def_id: Self::TraitAssocTyId,
        lang_item: SolverProjectionLangItem,
    ) -> bool;

    fn is_trait_lang_item(self, def_id: Self::TraitId, lang_item: SolverTraitLangItem) -> bool;

    fn is_adt_lang_item(self, def_id: Self::AdtId, lang_item: SolverAdtLangItem) -> bool;

    fn is_default_trait(self, def_id: Self::TraitId) -> bool;

    fn is_sizedness_trait(self, def_id: Self::TraitId) -> bool;

    fn as_projection_lang_item(
        self,
        def_id: Self::TraitAssocTyId,
    ) -> Option<SolverProjectionLangItem>;

    fn as_trait_lang_item(self, def_id: Self::TraitId) -> Option<SolverTraitLangItem>;

    fn as_adt_lang_item(self, def_id: Self::AdtId) -> Option<SolverAdtLangItem>;

    fn associated_type_def_ids(
        self,
        def_id: Self::TraitId,
    ) -> impl IntoIterator<Item = Self::DefId>;

    fn for_each_relevant_impl<R: VisitorResult>(
        self,
        trait_ref: TraitRef<Self>,
        f: impl FnMut(Self::ImplId) -> R,
    ) -> R;
    fn for_each_blanket_impl<R: VisitorResult>(
        self,
        trait_def_id: Self::TraitId,
        f: impl FnMut(Self::ImplId) -> R,
    ) -> R;

    fn has_item_definition(self, def_id: Self::ImplOrTraitAssocTermId) -> bool;

    fn impl_specializes(self, impl_def_id: Self::ImplId, victim_def_id: Self::ImplId) -> bool;

    fn impl_is_default(self, impl_def_id: Self::ImplId) -> bool;

    fn impl_trait_ref(self, impl_def_id: Self::ImplId)
    -> ty::EarlyBinder<Self, ty::TraitRef<Self>>;

    fn impl_polarity(self, impl_def_id: Self::ImplId) -> ty::ImplPolarity;

    fn is_fully_generic_for_reflection(self, impl_def_id: Self::ImplId) -> bool;

    fn trait_is_auto(self, trait_def_id: Self::TraitId) -> bool;

    fn trait_is_coinductive(self, trait_def_id: Self::TraitId) -> bool;

    fn trait_is_alias(self, trait_def_id: Self::TraitId) -> bool;

    fn trait_is_dyn_compatible(self, trait_def_id: Self::TraitId) -> bool;

    fn trait_is_fundamental(self, def_id: Self::TraitId) -> bool;

    /// Returns `true` if this is an `unsafe trait`.
    fn trait_is_unsafe(self, trait_def_id: Self::TraitId) -> bool;

    fn is_impl_trait_in_trait(self, def_id: Self::DefId) -> bool;

    fn delay_bug(self, msg: impl ToString) -> Self::ErrorGuaranteed;
    fn span_delayed_bug(self, span: Self::Span, msg: impl ToString) -> Self::ErrorGuaranteed;

    fn is_general_coroutine(self, coroutine_def_id: Self::CoroutineId) -> bool;
    fn coroutine_is_async(self, coroutine_def_id: Self::CoroutineId) -> bool;
    fn coroutine_is_gen(self, coroutine_def_id: Self::CoroutineId) -> bool;
    fn coroutine_is_async_gen(self, coroutine_def_id: Self::CoroutineId) -> bool;

    type UnsizingParams: Deref<Target = DenseBitSet<u32>>;
    fn unsizing_params_for_adt(self, adt_def_id: Self::AdtId) -> Self::UnsizingParams;

    fn anonymize_bound_vars<T: TypeFoldable<Self>>(
        self,
        binder: ty::Binder<Self, T>,
    ) -> ty::Binder<Self, T>;

    fn opaque_types_defined_by(self, defining_anchor: Self::LocalDefId) -> Self::LocalDefIds;

    fn opaque_types_and_coroutines_defined_by(
        self,
        defining_anchor: Self::LocalDefId,
    ) -> Self::LocalDefIds;

    type Probe: Debug + Hash + Eq + Borrow<inspect::Probe<Self>>;
    fn mk_probe(self, probe: inspect::Probe<Self>) -> Self::Probe;
    fn evaluate_root_goal_for_proof_tree_raw(
        self,
        canonical_goal: Self::CanonicalInput,
        root_depth: usize,
    ) -> (QueryResult<Self>, Self::Probe, RequiredDepth);

    fn item_name(self, item_index: Self::DefId) -> Self::Symbol;

    fn get_anon_re_bounds_lifetime(self, idx: usize, var_idx: usize) -> Option<Region<Self>>;

    fn get_anon_re_canonical_bounds_lifetime(self, idx: usize) -> Option<Region<Self>>;

    fn get_re_static_lifetime(self) -> Region<Self>;

    fn intern_re_var(self, rv: RegionVid) -> Region<Self>;

    fn intern_region(self, region_kind: RegionKind<Self>) -> Region<Self>;

    fn intern_bound_region(
        self,
        debruijn: DebruijnIndex,
        bound_region: BoundRegion<Self>,
    ) -> Region<Self>;

    fn intern_canonical_bound(self, var: BoundVar) -> Region<Self>;

    type CanonicalInput: Copy + Debug + Hash + Eq + Deref<Target = CanonicalInputData<Self>>;
    fn mk_canonical_input(self, data: CanonicalInputData<Self>) -> Self::CanonicalInput;
}

macro_rules! declare_lift_into {
    ($($assoc:ident),* $(,)?) => {
        /// An interner whose associated types can be lifted into another interner `J`.
        ///
        /// These are associated type bounds rather than `where` clauses so a caller with
        /// `I: LiftInto<J>` can rely on the individual associated type `Lift` bounds being
        /// implied.
        pub trait LiftInto<J>: Interner<$($assoc: crate::lift::Lift<J, Lifted = J::$assoc>,)*>
        where
            J: Interner,
        {}

        impl<I, J> LiftInto<J> for I
        where
            J: Interner,
            I: Interner<$($assoc: crate::lift::Lift<J, Lifted = J::$assoc>,)*>,
        {}
    };
}

declare_lift_into! {
    BoundVarKinds,
    Const,
    DefId,
    EarlyParamRegion,
    ErrorGuaranteed,
    FreeConstAliasId,
    FreeTyAliasId,
    GenericArg,
    GenericArgs,
    InherentAssocConstId,
    InherentAssocTyId,
    InternedRegionKind,
    OpaqueTyId,
    ParamEnv,
    PatList,
    RegionAssumptions,
    Symbol,
    Term,
    TraitAssocConstId,
    TraitAssocTermId,
    TraitAssocTyId,
    TraitId,
    Ty,
    Tys,
    AnonConstId,
}

/// Imagine you have a function `F: FnOnce(&[T]) -> R`, plus an iterator `iter`
/// that produces `T` items. You could combine them with
/// `f(&iter.collect::<Vec<_>>())`, but this requires allocating memory for the
/// `Vec`.
///
/// This trait allows for faster implementations, intended for cases where the
/// number of items produced by the iterator is small. There is a blanket impl
/// for `T` items, but there is also a fallible impl for `Result<T, E>` items.
pub trait CollectAndApply<T, R>: Sized {
    type Output;

    /// Produce a result of type `Self::Output` from `iter`. The result will
    /// typically be produced by applying `f` on the elements produced by
    /// `iter`, though this may not happen in some impls, e.g. if an error
    /// occurred during iteration.
    fn collect_and_apply<I, F>(iter: I, f: F) -> Self::Output
    where
        I: Iterator<Item = Self>,
        F: FnOnce(&[T]) -> R;
}

/// The blanket impl that always collects all elements and applies `f`.
impl<T, R> CollectAndApply<T, R> for T {
    type Output = R;

    /// Equivalent to `f(&iter.collect::<Vec<_>>())`.
    fn collect_and_apply<I, F>(mut iter: I, f: F) -> R
    where
        I: Iterator<Item = T>,
        F: FnOnce(&[T]) -> R,
    {
        // This code is hot enough that it's worth specializing for the most
        // common length lists, to avoid the overhead of `Vec` creation.

        let Some(t0) = iter.next() else {
            return f(&[]);
        };

        let Some(t1) = iter.next() else {
            return f(&[t0]);
        };

        let Some(t2) = iter.next() else {
            return f(&[t0, t1]);
        };

        let Some(t3) = iter.next() else {
            return f(&[t0, t1, t2]);
        };

        let Some(t4) = iter.next() else {
            return f(&[t0, t1, t2, t3]);
        };

        let Some(t5) = iter.next() else {
            return f(&[t0, t1, t2, t3, t4]);
        };

        let Some(t6) = iter.next() else {
            return f(&[t0, t1, t2, t3, t4, t5]);
        };

        let Some(t7) = iter.next() else {
            return f(&[t0, t1, t2, t3, t4, t5, t6]);
        };

        let Some(t8) = iter.next() else {
            return f(&[t0, t1, t2, t3, t4, t5, t6, t7]);
        };

        f(&[t0, t1, t2, t3, t4, t5, t6, t7, t8].into_iter().chain(iter).collect::<Vec<_>>())
    }
}

/// A fallible impl that will fail, without calling `f`, if there are any
/// errors during collection.
impl<T, R, E> CollectAndApply<T, R> for Result<T, E> {
    type Output = Result<R, E>;

    /// Equivalent to `Ok(f(&iter.collect::<Result<Vec<_>>>()?))`.
    fn collect_and_apply<I, F>(mut iter: I, f: F) -> Result<R, E>
    where
        I: Iterator<Item = Result<T, E>>,
        F: FnOnce(&[T]) -> R,
    {
        // This code is hot enough that it's worth specializing for the most
        // common length lists, to avoid the overhead of `Vec` creation.

        let Some(t0) = iter.next() else {
            return Ok(f(&[]));
        };
        let t0 = t0?;

        let Some(t1) = iter.next() else {
            return Ok(f(&[t0]));
        };
        let t1 = t1?;

        let Some(t2) = iter.next() else {
            return Ok(f(&[t0, t1]));
        };
        let t2 = t2?;

        let Some(t3) = iter.next() else {
            return Ok(f(&[t0, t1, t2]));
        };
        let t3 = t3?;

        let Some(t4) = iter.next() else {
            return Ok(f(&[t0, t1, t2, t3]));
        };
        let t4 = t4?;

        let Some(t5) = iter.next() else {
            return Ok(f(&[t0, t1, t2, t3, t4]));
        };
        let t5 = t5?;

        let Some(t6) = iter.next() else {
            return Ok(f(&[t0, t1, t2, t3, t4, t5]));
        };
        let t6 = t6?;

        let Some(t7) = iter.next() else {
            return Ok(f(&[t0, t1, t2, t3, t4, t5, t6]));
        };
        let t7 = t7?;

        let Some(t8) = iter.next() else {
            return Ok(f(&[t0, t1, t2, t3, t4, t5, t6, t7]));
        };
        let t8 = t8?;

        Ok(f(&[Ok(t0), Ok(t1), Ok(t2), Ok(t3), Ok(t4), Ok(t5), Ok(t6), Ok(t7), Ok(t8)]
            .into_iter()
            .chain(iter)
            .collect::<Result<Vec<_>, _>>()?))
    }
}

impl<I: Interner> search_graph::Cx for I {
    type Input = I::CanonicalInput;
    type Result = (QueryResult<I>, AccessedOpaques<I>);
    type AmbiguityKind = Certainty;

    type DepNodeIndex = I::DepNodeIndex;
    type Tracked<T: Debug + Clone> = I::Tracked<T>;
    fn mk_tracked<T: Debug + Clone>(
        self,
        data: T,
        dep_node_index: I::DepNodeIndex,
    ) -> I::Tracked<T> {
        I::mk_tracked(self, data, dep_node_index)
    }
    fn get_tracked<T: Debug + Clone>(self, tracked: &I::Tracked<T>) -> T {
        I::get_tracked(self, tracked)
    }
    fn with_cached_task<T>(self, task: impl FnOnce() -> T) -> (T, I::DepNodeIndex) {
        I::with_cached_task(self, task)
    }
    fn with_global_cache<R>(self, f: impl FnOnce(&mut search_graph::GlobalCache<Self>) -> R) -> R {
        I::with_global_cache(self, f)
    }
    fn assert_evaluation_is_concurrent(&self) {
        self.assert_evaluation_is_concurrent()
    }
}