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

rustc_type_ir/
interner.rs
