rustc_type_ir/
interner.rs

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

rustc_type_ir/
interner.rs
