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

rustc_type_ir/
interner.rs
