rustc_type_ir/
interner.rs

1use std::fmt::Debug;
2use std::hash::Hash;
3use std::ops::Deref;
4
5use rustc_ast_ir::Movability;
6use rustc_index::bit_set::DenseBitSet;
7
8use crate::fold::TypeFoldable;
9use crate::inherent::*;
10use crate::ir_print::IrPrint;
11use crate::lang_items::TraitSolverLangItem;
12use crate::relate::Relate;
13use crate::solve::{CanonicalInput, ExternalConstraintsData, PredefinedOpaquesData, QueryResult};
14use crate::visit::{Flags, TypeVisitable};
15use crate::{self as ty, search_graph};
16
17#[cfg_attr(feature = "nightly", rustc_diagnostic_item = "type_ir_interner")]
18pub trait Interner:
19    Sized
20    + Copy
21    + IrPrint<ty::AliasTy<Self>>
22    + IrPrint<ty::AliasTerm<Self>>
23    + IrPrint<ty::TraitRef<Self>>
24    + IrPrint<ty::TraitPredicate<Self>>
25    + IrPrint<ty::HostEffectPredicate<Self>>
26    + IrPrint<ty::ExistentialTraitRef<Self>>
27    + IrPrint<ty::ExistentialProjection<Self>>
28    + IrPrint<ty::ProjectionPredicate<Self>>
29    + IrPrint<ty::NormalizesTo<Self>>
30    + IrPrint<ty::SubtypePredicate<Self>>
31    + IrPrint<ty::CoercePredicate<Self>>
32    + IrPrint<ty::FnSig<Self>>
33    + IrPrint<ty::PatternKind<Self>>
34{
35    type DefId: DefId<Self>;
36    type LocalDefId: Copy + Debug + Hash + Eq + Into<Self::DefId> + TypeFoldable<Self>;
37    type Span: Span<Self>;
38
39    type GenericArgs: GenericArgs<Self>;
40    type GenericArgsSlice: Copy + Debug + Hash + Eq + SliceLike<Item = Self::GenericArg>;
41    type GenericArg: GenericArg<Self>;
42    type Term: Term<Self>;
43
44    type BoundVarKinds: Copy + Debug + Hash + Eq + SliceLike<Item = Self::BoundVarKind> + Default;
45    type BoundVarKind: Copy + Debug + Hash + Eq;
46
47    type PredefinedOpaques: Copy
48        + Debug
49        + Hash
50        + Eq
51        + TypeFoldable<Self>
52        + Deref<Target = PredefinedOpaquesData<Self>>;
53    fn mk_predefined_opaques_in_body(
54        self,
55        data: PredefinedOpaquesData<Self>,
56    ) -> Self::PredefinedOpaques;
57
58    type LocalDefIds: Copy
59        + Debug
60        + Hash
61        + Default
62        + Eq
63        + TypeVisitable<Self>
64        + SliceLike<Item = Self::LocalDefId>;
65
66    type CanonicalVarKinds: Copy
67        + Debug
68        + Hash
69        + Eq
70        + SliceLike<Item = ty::CanonicalVarKind<Self>>
71        + Default;
72    fn mk_canonical_var_kinds(
73        self,
74        kinds: &[ty::CanonicalVarKind<Self>],
75    ) -> Self::CanonicalVarKinds;
76
77    type ExternalConstraints: Copy
78        + Debug
79        + Hash
80        + Eq
81        + TypeFoldable<Self>
82        + Deref<Target = ExternalConstraintsData<Self>>;
83    fn mk_external_constraints(
84        self,
85        data: ExternalConstraintsData<Self>,
86    ) -> Self::ExternalConstraints;
87
88    type DepNodeIndex;
89    type Tracked<T: Debug + Clone>: Debug;
90    fn mk_tracked<T: Debug + Clone>(
91        self,
92        data: T,
93        dep_node: Self::DepNodeIndex,
94    ) -> Self::Tracked<T>;
95    fn get_tracked<T: Debug + Clone>(self, tracked: &Self::Tracked<T>) -> T;
96    fn with_cached_task<T>(self, task: impl FnOnce() -> T) -> (T, Self::DepNodeIndex);
97
98    // Kinds of tys
99    type Ty: Ty<Self>;
100    type Tys: Tys<Self>;
101    type FnInputTys: Copy + Debug + Hash + Eq + SliceLike<Item = Self::Ty> + TypeVisitable<Self>;
102    type ParamTy: Copy + Debug + Hash + Eq + ParamLike;
103    type BoundTy: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
104    type PlaceholderTy: PlaceholderLike;
105
106    // Things stored inside of tys
107    type ErrorGuaranteed: Copy + Debug + Hash + Eq;
108    type BoundExistentialPredicates: BoundExistentialPredicates<Self>;
109    type AllocId: Copy + Debug + Hash + Eq;
110    type Pat: Copy
111        + Debug
112        + Hash
113        + Eq
114        + Debug
115        + Relate<Self>
116        + Flags
117        + IntoKind<Kind = ty::PatternKind<Self>>;
118    type PatList: Copy
119        + Debug
120        + Hash
121        + Default
122        + Eq
123        + TypeVisitable<Self>
124        + SliceLike<Item = Self::Pat>;
125    type Safety: Safety<Self>;
126    type Abi: Abi<Self>;
127
128    // Kinds of consts
129    type Const: Const<Self>;
130    type PlaceholderConst: PlaceholderLike;
131    type ParamConst: Copy + Debug + Hash + Eq + ParamLike;
132    type BoundConst: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
133    type ValueConst: ValueConst<Self>;
134    type ExprConst: ExprConst<Self>;
135    type ValTree: Copy + Debug + Hash + Eq;
136
137    // Kinds of regions
138    type Region: Region<Self>;
139    type EarlyParamRegion: Copy + Debug + Hash + Eq + ParamLike;
140    type LateParamRegion: Copy + Debug + Hash + Eq;
141    type BoundRegion: Copy + Debug + Hash + Eq + BoundVarLike<Self>;
142    type PlaceholderRegion: PlaceholderLike;
143
144    // Predicates
145    type ParamEnv: ParamEnv<Self>;
146    type Predicate: Predicate<Self>;
147    type Clause: Clause<Self>;
148    type Clauses: Clauses<Self>;
149
150    fn with_global_cache<R>(self, f: impl FnOnce(&mut search_graph::GlobalCache<Self>) -> R) -> R;
151
152    fn evaluation_is_concurrent(&self) -> bool;
153
154    fn expand_abstract_consts<T: TypeFoldable<Self>>(self, t: T) -> T;
155
156    type GenericsOf: GenericsOf<Self>;
157    fn generics_of(self, def_id: Self::DefId) -> Self::GenericsOf;
158
159    type VariancesOf: Copy + Debug + SliceLike<Item = ty::Variance>;
160    fn variances_of(self, def_id: Self::DefId) -> Self::VariancesOf;
161
162    fn opt_alias_variances(
163        self,
164        kind: impl Into<ty::AliasTermKind>,
165        def_id: Self::DefId,
166    ) -> Option<Self::VariancesOf>;
167
168    fn type_of(self, def_id: Self::DefId) -> ty::EarlyBinder<Self, Self::Ty>;
169    fn type_of_opaque_hir_typeck(self, def_id: Self::LocalDefId)
170    -> ty::EarlyBinder<Self, Self::Ty>;
171
172    type AdtDef: AdtDef<Self>;
173    fn adt_def(self, adt_def_id: Self::DefId) -> Self::AdtDef;
174
175    fn alias_ty_kind(self, alias: ty::AliasTy<Self>) -> ty::AliasTyKind;
176
177    fn alias_term_kind(self, alias: ty::AliasTerm<Self>) -> ty::AliasTermKind;
178
179    fn trait_ref_and_own_args_for_alias(
180        self,
181        def_id: Self::DefId,
182        args: Self::GenericArgs,
183    ) -> (ty::TraitRef<Self>, Self::GenericArgsSlice);
184
185    fn mk_args(self, args: &[Self::GenericArg]) -> Self::GenericArgs;
186
187    fn mk_args_from_iter<I, T>(self, args: I) -> T::Output
188    where
189        I: Iterator<Item = T>,
190        T: CollectAndApply<Self::GenericArg, Self::GenericArgs>;
191
192    fn check_args_compatible(self, def_id: Self::DefId, args: Self::GenericArgs) -> bool;
193
194    fn debug_assert_args_compatible(self, def_id: Self::DefId, args: Self::GenericArgs);
195
196    /// Assert that the args from an `ExistentialTraitRef` or `ExistentialProjection`
197    /// are compatible with the `DefId`.
198    fn debug_assert_existential_args_compatible(self, def_id: Self::DefId, args: Self::GenericArgs);
199
200    fn mk_type_list_from_iter<I, T>(self, args: I) -> T::Output
201    where
202        I: Iterator<Item = T>,
203        T: CollectAndApply<Self::Ty, Self::Tys>;
204
205    fn parent(self, def_id: Self::DefId) -> Self::DefId;
206
207    fn recursion_limit(self) -> usize;
208
209    type Features: Features<Self>;
210    fn features(self) -> Self::Features;
211
212    fn coroutine_hidden_types(
213        self,
214        def_id: Self::DefId,
215    ) -> ty::EarlyBinder<Self, ty::Binder<Self, ty::CoroutineWitnessTypes<Self>>>;
216
217    fn fn_sig(
218        self,
219        def_id: Self::DefId,
220    ) -> ty::EarlyBinder<Self, ty::Binder<Self, ty::FnSig<Self>>>;
221
222    fn coroutine_movability(self, def_id: Self::DefId) -> Movability;
223
224    fn coroutine_for_closure(self, def_id: Self::DefId) -> Self::DefId;
225
226    fn generics_require_sized_self(self, def_id: Self::DefId) -> bool;
227
228    fn item_bounds(
229        self,
230        def_id: Self::DefId,
231    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;
232
233    fn item_self_bounds(
234        self,
235        def_id: Self::DefId,
236    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;
237
238    fn item_non_self_bounds(
239        self,
240        def_id: Self::DefId,
241    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;
242
243    fn predicates_of(
244        self,
245        def_id: Self::DefId,
246    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;
247
248    fn own_predicates_of(
249        self,
250        def_id: Self::DefId,
251    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = Self::Clause>>;
252
253    fn explicit_super_predicates_of(
254        self,
255        def_id: Self::DefId,
256    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = (Self::Clause, Self::Span)>>;
257
258    fn explicit_implied_predicates_of(
259        self,
260        def_id: Self::DefId,
261    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = (Self::Clause, Self::Span)>>;
262
263    fn impl_is_const(self, def_id: Self::DefId) -> bool;
264    fn fn_is_const(self, def_id: Self::DefId) -> bool;
265    fn alias_has_const_conditions(self, def_id: Self::DefId) -> bool;
266    fn const_conditions(
267        self,
268        def_id: Self::DefId,
269    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = ty::Binder<Self, ty::TraitRef<Self>>>>;
270    fn explicit_implied_const_bounds(
271        self,
272        def_id: Self::DefId,
273    ) -> ty::EarlyBinder<Self, impl IntoIterator<Item = ty::Binder<Self, ty::TraitRef<Self>>>>;
274
275    fn impl_self_is_guaranteed_unsized(self, def_id: Self::DefId) -> bool;
276
277    fn has_target_features(self, def_id: Self::DefId) -> bool;
278
279    fn require_lang_item(self, lang_item: TraitSolverLangItem) -> Self::DefId;
280
281    fn is_lang_item(self, def_id: Self::DefId, lang_item: TraitSolverLangItem) -> bool;
282
283    fn is_default_trait(self, def_id: Self::DefId) -> bool;
284
285    fn as_lang_item(self, def_id: Self::DefId) -> Option<TraitSolverLangItem>;
286
287    fn associated_type_def_ids(self, def_id: Self::DefId) -> impl IntoIterator<Item = Self::DefId>;
288
289    fn for_each_relevant_impl(
290        self,
291        trait_def_id: Self::DefId,
292        self_ty: Self::Ty,
293        f: impl FnMut(Self::DefId),
294    );
295
296    fn has_item_definition(self, def_id: Self::DefId) -> bool;
297
298    fn impl_specializes(self, impl_def_id: Self::DefId, victim_def_id: Self::DefId) -> bool;
299
300    fn impl_is_default(self, impl_def_id: Self::DefId) -> bool;
301
302    fn impl_trait_ref(self, impl_def_id: Self::DefId) -> ty::EarlyBinder<Self, ty::TraitRef<Self>>;
303
304    fn impl_polarity(self, impl_def_id: Self::DefId) -> ty::ImplPolarity;
305
306    fn trait_is_auto(self, trait_def_id: Self::DefId) -> bool;
307
308    fn trait_is_coinductive(self, trait_def_id: Self::DefId) -> bool;
309
310    fn trait_is_alias(self, trait_def_id: Self::DefId) -> bool;
311
312    fn trait_is_dyn_compatible(self, trait_def_id: Self::DefId) -> bool;
313
314    fn trait_is_fundamental(self, def_id: Self::DefId) -> bool;
315
316    fn trait_may_be_implemented_via_object(self, trait_def_id: Self::DefId) -> bool;
317
318    /// Returns `true` if this is an `unsafe trait`.
319    fn trait_is_unsafe(self, trait_def_id: Self::DefId) -> bool;
320
321    fn is_impl_trait_in_trait(self, def_id: Self::DefId) -> bool;
322
323    fn delay_bug(self, msg: impl ToString) -> Self::ErrorGuaranteed;
324
325    fn is_general_coroutine(self, coroutine_def_id: Self::DefId) -> bool;
326    fn coroutine_is_async(self, coroutine_def_id: Self::DefId) -> bool;
327    fn coroutine_is_gen(self, coroutine_def_id: Self::DefId) -> bool;
328    fn coroutine_is_async_gen(self, coroutine_def_id: Self::DefId) -> bool;
329
330    type UnsizingParams: Deref<Target = DenseBitSet<u32>>;
331    fn unsizing_params_for_adt(self, adt_def_id: Self::DefId) -> Self::UnsizingParams;
332
333    fn find_const_ty_from_env(
334        self,
335        param_env: Self::ParamEnv,
336        placeholder: Self::PlaceholderConst,
337    ) -> Self::Ty;
338
339    fn anonymize_bound_vars<T: TypeFoldable<Self>>(
340        self,
341        binder: ty::Binder<Self, T>,
342    ) -> ty::Binder<Self, T>;
343
344    fn opaque_types_defined_by(self, defining_anchor: Self::LocalDefId) -> Self::LocalDefIds;
345
346    fn opaque_types_and_coroutines_defined_by(
347        self,
348        defining_anchor: Self::LocalDefId,
349    ) -> Self::LocalDefIds;
350}
351
352/// Imagine you have a function `F: FnOnce(&[T]) -> R`, plus an iterator `iter`
353/// that produces `T` items. You could combine them with
354/// `f(&iter.collect::<Vec<_>>())`, but this requires allocating memory for the
355/// `Vec`.
356///
357/// This trait allows for faster implementations, intended for cases where the
358/// number of items produced by the iterator is small. There is a blanket impl
359/// for `T` items, but there is also a fallible impl for `Result<T, E>` items.
360pub trait CollectAndApply<T, R>: Sized {
361    type Output;
362
363    /// Produce a result of type `Self::Output` from `iter`. The result will
364    /// typically be produced by applying `f` on the elements produced by
365    /// `iter`, though this may not happen in some impls, e.g. if an error
366    /// occurred during iteration.
367    fn collect_and_apply<I, F>(iter: I, f: F) -> Self::Output
368    where
369        I: Iterator<Item = Self>,
370        F: FnOnce(&[T]) -> R;
371}
372
373/// The blanket impl that always collects all elements and applies `f`.
374impl<T, R> CollectAndApply<T, R> for T {
375    type Output = R;
376
377    /// Equivalent to `f(&iter.collect::<Vec<_>>())`.
378    fn collect_and_apply<I, F>(mut iter: I, f: F) -> R
379    where
380        I: Iterator<Item = T>,
381        F: FnOnce(&[T]) -> R,
382    {
383        // This code is hot enough that it's worth specializing for the most
384        // common length lists, to avoid the overhead of `Vec` creation.
385
386        let Some(t0) = iter.next() else {
387            return f(&[]);
388        };
389
390        let Some(t1) = iter.next() else {
391            return f(&[t0]);
392        };
393
394        let Some(t2) = iter.next() else {
395            return f(&[t0, t1]);
396        };
397
398        let Some(t3) = iter.next() else {
399            return f(&[t0, t1, t2]);
400        };
401
402        let Some(t4) = iter.next() else {
403            return f(&[t0, t1, t2, t3]);
404        };
405
406        let Some(t5) = iter.next() else {
407            return f(&[t0, t1, t2, t3, t4]);
408        };
409
410        let Some(t6) = iter.next() else {
411            return f(&[t0, t1, t2, t3, t4, t5]);
412        };
413
414        let Some(t7) = iter.next() else {
415            return f(&[t0, t1, t2, t3, t4, t5, t6]);
416        };
417
418        let Some(t8) = iter.next() else {
419            return f(&[t0, t1, t2, t3, t4, t5, t6, t7]);
420        };
421
422        f(&[t0, t1, t2, t3, t4, t5, t6, t7, t8].into_iter().chain(iter).collect::<Vec<_>>())
423    }
424}
425
426/// A fallible impl that will fail, without calling `f`, if there are any
427/// errors during collection.
428impl<T, R, E> CollectAndApply<T, R> for Result<T, E> {
429    type Output = Result<R, E>;
430
431    /// Equivalent to `Ok(f(&iter.collect::<Result<Vec<_>>>()?))`.
432    fn collect_and_apply<I, F>(mut iter: I, f: F) -> Result<R, E>
433    where
434        I: Iterator<Item = Result<T, E>>,
435        F: FnOnce(&[T]) -> R,
436    {
437        // This code is hot enough that it's worth specializing for the most
438        // common length lists, to avoid the overhead of `Vec` creation.
439
440        let Some(t0) = iter.next() else {
441            return Ok(f(&[]));
442        };
443        let t0 = t0?;
444
445        let Some(t1) = iter.next() else {
446            return Ok(f(&[t0]));
447        };
448        let t1 = t1?;
449
450        let Some(t2) = iter.next() else {
451            return Ok(f(&[t0, t1]));
452        };
453        let t2 = t2?;
454
455        let Some(t3) = iter.next() else {
456            return Ok(f(&[t0, t1, t2]));
457        };
458        let t3 = t3?;
459
460        let Some(t4) = iter.next() else {
461            return Ok(f(&[t0, t1, t2, t3]));
462        };
463        let t4 = t4?;
464
465        let Some(t5) = iter.next() else {
466            return Ok(f(&[t0, t1, t2, t3, t4]));
467        };
468        let t5 = t5?;
469
470        let Some(t6) = iter.next() else {
471            return Ok(f(&[t0, t1, t2, t3, t4, t5]));
472        };
473        let t6 = t6?;
474
475        let Some(t7) = iter.next() else {
476            return Ok(f(&[t0, t1, t2, t3, t4, t5, t6]));
477        };
478        let t7 = t7?;
479
480        let Some(t8) = iter.next() else {
481            return Ok(f(&[t0, t1, t2, t3, t4, t5, t6, t7]));
482        };
483        let t8 = t8?;
484
485        Ok(f(&[Ok(t0), Ok(t1), Ok(t2), Ok(t3), Ok(t4), Ok(t5), Ok(t6), Ok(t7), Ok(t8)]
486            .into_iter()
487            .chain(iter)
488            .collect::<Result<Vec<_>, _>>()?))
489    }
490}
491
492impl<I: Interner> search_graph::Cx for I {
493    type Input = CanonicalInput<I>;
494    type Result = QueryResult<I>;
495
496    type DepNodeIndex = I::DepNodeIndex;
497    type Tracked<T: Debug + Clone> = I::Tracked<T>;
498    fn mk_tracked<T: Debug + Clone>(
499        self,
500        data: T,
501        dep_node_index: I::DepNodeIndex,
502    ) -> I::Tracked<T> {
503        I::mk_tracked(self, data, dep_node_index)
504    }
505    fn get_tracked<T: Debug + Clone>(self, tracked: &I::Tracked<T>) -> T {
506        I::get_tracked(self, tracked)
507    }
508    fn with_cached_task<T>(self, task: impl FnOnce() -> T) -> (T, I::DepNodeIndex) {
509        I::with_cached_task(self, task)
510    }
511    fn with_global_cache<R>(self, f: impl FnOnce(&mut search_graph::GlobalCache<Self>) -> R) -> R {
512        I::with_global_cache(self, f)
513    }
514    fn evaluation_is_concurrent(&self) -> bool {
515        self.evaluation_is_concurrent()
516    }
517}