rustc_type_ir/
fast_reject.rs

1use std::fmt::Debug;
2use std::hash::Hash;
3use std::iter;
4use std::marker::PhantomData;
5
6use rustc_ast_ir::Mutability;
7#[cfg(feature = "nightly")]
8use rustc_data_structures::fingerprint::Fingerprint;
9#[cfg(feature = "nightly")]
10use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
11#[cfg(feature = "nightly")]
12use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext};
13
14use crate::inherent::*;
15use crate::visit::TypeVisitableExt as _;
16use crate::{self as ty, Interner};
17
18/// See `simplify_type`.
19#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
20#[cfg_attr(
21    feature = "nightly",
22    derive(Encodable_NoContext, Decodable_NoContext, HashStable_NoContext)
23)]
24pub enum SimplifiedType<DefId> {
25    Bool,
26    Char,
27    Int(ty::IntTy),
28    Uint(ty::UintTy),
29    Float(ty::FloatTy),
30    Adt(DefId),
31    Foreign(DefId),
32    Str,
33    Array,
34    Slice,
35    Ref(Mutability),
36    Ptr(Mutability),
37    Never,
38    Tuple(usize),
39    /// A trait object, all of whose components are markers
40    /// (e.g., `dyn Send + Sync`).
41    MarkerTraitObject,
42    Trait(DefId),
43    Closure(DefId),
44    Coroutine(DefId),
45    CoroutineWitness(DefId),
46    Function(usize),
47    UnsafeBinder,
48    Placeholder,
49    Error,
50}
51
52#[cfg(feature = "nightly")]
53impl<HCX: Clone, DefId: HashStable<HCX>> ToStableHashKey<HCX> for SimplifiedType<DefId> {
54    type KeyType = Fingerprint;
55
56    #[inline]
57    fn to_stable_hash_key(&self, hcx: &HCX) -> Fingerprint {
58        let mut hasher = StableHasher::new();
59        let mut hcx: HCX = hcx.clone();
60        self.hash_stable(&mut hcx, &mut hasher);
61        hasher.finish()
62    }
63}
64
65/// Generic parameters are pretty much just bound variables, e.g.
66/// the type of `fn foo<'a, T>(x: &'a T) -> u32 { ... }` can be thought of as
67/// `for<'a, T> fn(&'a T) -> u32`.
68///
69/// Typecheck of `foo` has to succeed for all possible generic arguments, so
70/// during typeck, we have to treat its generic parameters as if they
71/// were placeholders.
72///
73/// But when calling `foo` we only have to provide a specific generic argument.
74/// In that case the generic parameters are instantiated with inference variables.
75/// As we use `simplify_type` before that instantiation happens, we just treat
76/// generic parameters as if they were inference variables in that case.
77#[derive(PartialEq, Eq, Debug, Clone, Copy)]
78pub enum TreatParams {
79    /// Treat parameters as infer vars. This is the correct mode for caching
80    /// an impl's type for lookup.
81    InstantiateWithInfer,
82    /// Treat parameters as placeholders in the given environment. This is the
83    /// correct mode for *lookup*, as during candidate selection.
84    ///
85    /// This also treats projections with inference variables as infer vars
86    /// since they could be further normalized.
87    // FIXME(@lcnr): This treats aliases as rigid. This is only correct if the
88    // type has been structurally normalized. We should reflect this requirement
89    // in the variant name. It is currently incorrectly used in diagnostics.
90    AsRigid,
91}
92
93/// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists.
94///
95/// **This function should only be used if you need to store or retrieve the type from some
96/// hashmap. If you want to quickly decide whether two types may unify, use the [DeepRejectCtxt]
97/// instead.**
98///
99/// The idea is to get something simple that we can use to quickly decide if two types could unify,
100/// for example during method lookup. If this function returns `Some(x)` it can only unify with
101/// types for which this method returns either `Some(x)` as well or `None`.
102///
103/// A special case here are parameters and projections, which are only injective
104/// if they are treated as placeholders.
105///
106/// For example when storing impls based on their simplified self type, we treat
107/// generic parameters as if they were inference variables. We must not simplify them here,
108/// as they can unify with any other type.
109///
110/// With projections we have to be even more careful, as treating them as placeholders
111/// is only correct if they are fully normalized.
112///
113/// ¹ meaning that if the outermost layers are different, then the whole types are also different.
114pub fn simplify_type<I: Interner>(
115    cx: I,
116    ty: I::Ty,
117    treat_params: TreatParams,
118) -> Option<SimplifiedType<I::DefId>> {
119    match ty.kind() {
120        ty::Bool => Some(SimplifiedType::Bool),
121        ty::Char => Some(SimplifiedType::Char),
122        ty::Int(int_type) => Some(SimplifiedType::Int(int_type)),
123        ty::Uint(uint_type) => Some(SimplifiedType::Uint(uint_type)),
124        ty::Float(float_type) => Some(SimplifiedType::Float(float_type)),
125        ty::Adt(def, _) => Some(SimplifiedType::Adt(def.def_id().into())),
126        ty::Str => Some(SimplifiedType::Str),
127        ty::Array(..) => Some(SimplifiedType::Array),
128        ty::Slice(..) => Some(SimplifiedType::Slice),
129        ty::Pat(ty, ..) => simplify_type(cx, ty, treat_params),
130        ty::RawPtr(_, mutbl) => Some(SimplifiedType::Ptr(mutbl)),
131        ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() {
132            Some(principal_def_id) if !cx.trait_is_auto(principal_def_id) => {
133                Some(SimplifiedType::Trait(principal_def_id.into()))
134            }
135            _ => Some(SimplifiedType::MarkerTraitObject),
136        },
137        ty::Ref(_, _, mutbl) => Some(SimplifiedType::Ref(mutbl)),
138        ty::FnDef(def_id, _) => Some(SimplifiedType::Closure(def_id.into())),
139        ty::Closure(def_id, _) => Some(SimplifiedType::Closure(def_id.into())),
140        ty::CoroutineClosure(def_id, _) => Some(SimplifiedType::Closure(def_id.into())),
141        ty::Coroutine(def_id, _) => Some(SimplifiedType::Coroutine(def_id.into())),
142        ty::CoroutineWitness(def_id, _) => Some(SimplifiedType::CoroutineWitness(def_id.into())),
143        ty::Never => Some(SimplifiedType::Never),
144        ty::Tuple(tys) => Some(SimplifiedType::Tuple(tys.len())),
145        ty::FnPtr(sig_tys, _hdr) => {
146            Some(SimplifiedType::Function(sig_tys.skip_binder().inputs().len()))
147        }
148        ty::UnsafeBinder(_) => Some(SimplifiedType::UnsafeBinder),
149        ty::Placeholder(..) => Some(SimplifiedType::Placeholder),
150        ty::Param(_) => match treat_params {
151            TreatParams::AsRigid => Some(SimplifiedType::Placeholder),
152            TreatParams::InstantiateWithInfer => None,
153        },
154        ty::Alias(..) => match treat_params {
155            // When treating `ty::Param` as a placeholder, projections also
156            // don't unify with anything else as long as they are fully normalized.
157            TreatParams::AsRigid
158                if !ty.has_non_region_infer() || cx.next_trait_solver_globally() =>
159            {
160                Some(SimplifiedType::Placeholder)
161            }
162            TreatParams::AsRigid | TreatParams::InstantiateWithInfer => None,
163        },
164        ty::Foreign(def_id) => Some(SimplifiedType::Foreign(def_id.into())),
165        ty::Error(_) => Some(SimplifiedType::Error),
166        ty::Bound(..) | ty::Infer(_) => None,
167    }
168}
169
170impl<DefId> SimplifiedType<DefId> {
171    pub fn def(self) -> Option<DefId> {
172        match self {
173            SimplifiedType::Adt(d)
174            | SimplifiedType::Foreign(d)
175            | SimplifiedType::Trait(d)
176            | SimplifiedType::Closure(d)
177            | SimplifiedType::Coroutine(d)
178            | SimplifiedType::CoroutineWitness(d) => Some(d),
179            _ => None,
180        }
181    }
182}
183
184/// Given generic arguments, could they be unified after
185/// replacing parameters with inference variables or placeholders.
186/// This behavior is toggled using the const generics.
187///
188/// We use this to quickly reject impl/wc candidates without needing
189/// to instantiate generic arguments/having to enter a probe.
190///
191/// We also use this function during coherence. For coherence the
192/// impls only have to overlap for some value, so we treat parameters
193/// on both sides like inference variables.
194#[derive(Debug, Clone, Copy)]
195pub struct DeepRejectCtxt<
196    I: Interner,
197    const INSTANTIATE_LHS_WITH_INFER: bool,
198    const INSTANTIATE_RHS_WITH_INFER: bool,
199> {
200    _interner: PhantomData<I>,
201}
202
203impl<I: Interner> DeepRejectCtxt<I, false, false> {
204    /// Treat parameters in both the lhs and the rhs as rigid.
205    pub fn relate_rigid_rigid(_interner: I) -> DeepRejectCtxt<I, false, false> {
206        DeepRejectCtxt { _interner: PhantomData }
207    }
208}
209
210impl<I: Interner> DeepRejectCtxt<I, true, true> {
211    /// Treat parameters in both the lhs and the rhs as infer vars.
212    pub fn relate_infer_infer(_interner: I) -> DeepRejectCtxt<I, true, true> {
213        DeepRejectCtxt { _interner: PhantomData }
214    }
215}
216
217impl<I: Interner> DeepRejectCtxt<I, false, true> {
218    /// Treat parameters in the lhs as rigid, and in rhs as infer vars.
219    pub fn relate_rigid_infer(_interner: I) -> DeepRejectCtxt<I, false, true> {
220        DeepRejectCtxt { _interner: PhantomData }
221    }
222}
223
224impl<I: Interner, const INSTANTIATE_LHS_WITH_INFER: bool, const INSTANTIATE_RHS_WITH_INFER: bool>
225    DeepRejectCtxt<I, INSTANTIATE_LHS_WITH_INFER, INSTANTIATE_RHS_WITH_INFER>
226{
227    // Quite arbitrary. Large enough to only affect a very tiny amount of impls/crates
228    // and small enough to prevent hangs.
229    const STARTING_DEPTH: usize = 8;
230
231    pub fn args_may_unify(
232        self,
233        obligation_args: I::GenericArgs,
234        impl_args: I::GenericArgs,
235    ) -> bool {
236        self.args_may_unify_inner(obligation_args, impl_args, Self::STARTING_DEPTH)
237    }
238
239    pub fn types_may_unify(self, lhs: I::Ty, rhs: I::Ty) -> bool {
240        self.types_may_unify_inner(lhs, rhs, Self::STARTING_DEPTH)
241    }
242
243    pub fn types_may_unify_with_depth(self, lhs: I::Ty, rhs: I::Ty, depth_limit: usize) -> bool {
244        self.types_may_unify_inner(lhs, rhs, depth_limit)
245    }
246
247    fn args_may_unify_inner(
248        self,
249        obligation_args: I::GenericArgs,
250        impl_args: I::GenericArgs,
251        depth: usize,
252    ) -> bool {
253        // No need to decrement the depth here as this function is only
254        // recursively reachable via `types_may_unify_inner` which already
255        // increments the depth for us.
256        iter::zip(obligation_args.iter(), impl_args.iter()).all(|(obl, imp)| {
257            match (obl.kind(), imp.kind()) {
258                // We don't fast reject based on regions.
259                (ty::GenericArgKind::Lifetime(_), ty::GenericArgKind::Lifetime(_)) => true,
260                (ty::GenericArgKind::Type(obl), ty::GenericArgKind::Type(imp)) => {
261                    self.types_may_unify_inner(obl, imp, depth)
262                }
263                (ty::GenericArgKind::Const(obl), ty::GenericArgKind::Const(imp)) => {
264                    self.consts_may_unify_inner(obl, imp)
265                }
266                _ => panic!("kind mismatch: {obl:?} {imp:?}"),
267            }
268        })
269    }
270
271    fn types_may_unify_inner(self, lhs: I::Ty, rhs: I::Ty, depth: usize) -> bool {
272        if lhs == rhs {
273            return true;
274        }
275
276        match rhs.kind() {
277            // Start by checking whether the `rhs` type may unify with
278            // pretty much everything. Just return `true` in that case.
279            ty::Param(_) => {
280                if INSTANTIATE_RHS_WITH_INFER {
281                    return true;
282                }
283            }
284            ty::Error(_) | ty::Alias(..) | ty::Bound(..) => return true,
285            ty::Infer(var) => return self.var_and_ty_may_unify(var, lhs),
286
287            // These types only unify with inference variables or their own
288            // variant.
289            ty::Bool
290            | ty::Char
291            | ty::Int(_)
292            | ty::Uint(_)
293            | ty::Float(_)
294            | ty::Adt(..)
295            | ty::Str
296            | ty::Array(..)
297            | ty::Slice(..)
298            | ty::RawPtr(..)
299            | ty::Dynamic(..)
300            | ty::Pat(..)
301            | ty::Ref(..)
302            | ty::Never
303            | ty::Tuple(..)
304            | ty::FnDef(..)
305            | ty::FnPtr(..)
306            | ty::Closure(..)
307            | ty::CoroutineClosure(..)
308            | ty::Coroutine(..)
309            | ty::CoroutineWitness(..)
310            | ty::Foreign(_)
311            | ty::Placeholder(_)
312            | ty::UnsafeBinder(_) => {}
313        };
314
315        // The type system needs to support exponentially large types
316        // as long as they are self-similar. While most other folders
317        // use caching to handle them, this folder exists purely as a
318        // perf optimization and is incredibly hot. In pretty much all
319        // uses checking the cache is slower than simply recursing, so
320        // we instead just add an arbitrary depth cutoff.
321        //
322        // We only decrement the depth here as the match on `rhs`
323        // does not recurse.
324        let Some(depth) = depth.checked_sub(1) else {
325            return true;
326        };
327
328        // For purely rigid types, use structural equivalence.
329        match lhs.kind() {
330            ty::Ref(_, lhs_ty, lhs_mutbl) => match rhs.kind() {
331                ty::Ref(_, rhs_ty, rhs_mutbl) => {
332                    lhs_mutbl == rhs_mutbl && self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
333                }
334                _ => false,
335            },
336
337            ty::Adt(lhs_def, lhs_args) => match rhs.kind() {
338                ty::Adt(rhs_def, rhs_args) => {
339                    lhs_def == rhs_def && self.args_may_unify_inner(lhs_args, rhs_args, depth)
340                }
341                _ => false,
342            },
343
344            // Depending on the value of const generics, we either treat generic parameters
345            // like placeholders or like inference variables.
346            ty::Param(lhs) => {
347                INSTANTIATE_LHS_WITH_INFER
348                    || match rhs.kind() {
349                        ty::Param(rhs) => lhs == rhs,
350                        _ => false,
351                    }
352            }
353
354            // Placeholder types don't unify with anything on their own.
355            ty::Placeholder(lhs) => {
356                matches!(rhs.kind(), ty::Placeholder(rhs) if lhs == rhs)
357            }
358
359            ty::Infer(var) => self.var_and_ty_may_unify(var, rhs),
360
361            // As we're walking the whole type, it may encounter projections
362            // inside of binders and what not, so we're just going to assume that
363            // projections can unify with other stuff.
364            //
365            // Looking forward to lazy normalization this is the safer strategy anyways.
366            ty::Alias(..) => true,
367
368            ty::Int(_)
369            | ty::Uint(_)
370            | ty::Float(_)
371            | ty::Str
372            | ty::Bool
373            | ty::Char
374            | ty::Never
375            | ty::Foreign(_) => lhs == rhs,
376
377            ty::Tuple(lhs) => match rhs.kind() {
378                ty::Tuple(rhs) => {
379                    lhs.len() == rhs.len()
380                        && iter::zip(lhs.iter(), rhs.iter())
381                            .all(|(lhs, rhs)| self.types_may_unify_inner(lhs, rhs, depth))
382                }
383                _ => false,
384            },
385
386            ty::Array(lhs_ty, lhs_len) => match rhs.kind() {
387                ty::Array(rhs_ty, rhs_len) => {
388                    self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
389                        && self.consts_may_unify_inner(lhs_len, rhs_len)
390                }
391                _ => false,
392            },
393
394            ty::RawPtr(lhs_ty, lhs_mutbl) => match rhs.kind() {
395                ty::RawPtr(rhs_ty, rhs_mutbl) => {
396                    lhs_mutbl == rhs_mutbl && self.types_may_unify_inner(lhs_ty, rhs_ty, depth)
397                }
398                _ => false,
399            },
400
401            ty::Slice(lhs_ty) => {
402                matches!(rhs.kind(), ty::Slice(rhs_ty) if self.types_may_unify_inner(lhs_ty, rhs_ty, depth))
403            }
404
405            ty::Dynamic(lhs_preds, ..) => {
406                // Ideally we would walk the existential predicates here or at least
407                // compare their length. But considering that the relevant `Relate` impl
408                // actually sorts and deduplicates these, that doesn't work.
409                matches!(rhs.kind(), ty::Dynamic(rhs_preds, ..) if
410                    lhs_preds.principal_def_id() == rhs_preds.principal_def_id()
411                )
412            }
413
414            ty::FnPtr(lhs_sig_tys, lhs_hdr) => match rhs.kind() {
415                ty::FnPtr(rhs_sig_tys, rhs_hdr) => {
416                    let lhs_sig_tys = lhs_sig_tys.skip_binder().inputs_and_output;
417                    let rhs_sig_tys = rhs_sig_tys.skip_binder().inputs_and_output;
418
419                    lhs_hdr == rhs_hdr
420                        && lhs_sig_tys.len() == rhs_sig_tys.len()
421                        && iter::zip(lhs_sig_tys.iter(), rhs_sig_tys.iter())
422                            .all(|(lhs, rhs)| self.types_may_unify_inner(lhs, rhs, depth))
423                }
424                _ => false,
425            },
426
427            ty::Bound(..) => true,
428
429            ty::FnDef(lhs_def_id, lhs_args) => match rhs.kind() {
430                ty::FnDef(rhs_def_id, rhs_args) => {
431                    lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
432                }
433                _ => false,
434            },
435
436            ty::Closure(lhs_def_id, lhs_args) => match rhs.kind() {
437                ty::Closure(rhs_def_id, rhs_args) => {
438                    lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
439                }
440                _ => false,
441            },
442
443            ty::CoroutineClosure(lhs_def_id, lhs_args) => match rhs.kind() {
444                ty::CoroutineClosure(rhs_def_id, rhs_args) => {
445                    lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
446                }
447                _ => false,
448            },
449
450            ty::Coroutine(lhs_def_id, lhs_args) => match rhs.kind() {
451                ty::Coroutine(rhs_def_id, rhs_args) => {
452                    lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
453                }
454                _ => false,
455            },
456
457            ty::CoroutineWitness(lhs_def_id, lhs_args) => match rhs.kind() {
458                ty::CoroutineWitness(rhs_def_id, rhs_args) => {
459                    lhs_def_id == rhs_def_id && self.args_may_unify_inner(lhs_args, rhs_args, depth)
460                }
461                _ => false,
462            },
463
464            ty::Pat(lhs_ty, _) => {
465                // FIXME(pattern_types): take pattern into account
466                matches!(rhs.kind(), ty::Pat(rhs_ty, _) if self.types_may_unify_inner(lhs_ty, rhs_ty, depth))
467            }
468
469            ty::UnsafeBinder(lhs_ty) => match rhs.kind() {
470                ty::UnsafeBinder(rhs_ty) => {
471                    self.types_may_unify(lhs_ty.skip_binder(), rhs_ty.skip_binder())
472                }
473                _ => false,
474            },
475
476            ty::Error(..) => true,
477        }
478    }
479
480    // Unlike `types_may_unify_inner`, this does not take a depth as
481    // we never recurse from this function.
482    fn consts_may_unify_inner(self, lhs: I::Const, rhs: I::Const) -> bool {
483        match rhs.kind() {
484            ty::ConstKind::Param(_) => {
485                if INSTANTIATE_RHS_WITH_INFER {
486                    return true;
487                }
488            }
489
490            ty::ConstKind::Expr(_)
491            | ty::ConstKind::Unevaluated(_)
492            | ty::ConstKind::Error(_)
493            | ty::ConstKind::Infer(_)
494            | ty::ConstKind::Bound(..) => {
495                return true;
496            }
497
498            ty::ConstKind::Value(..) | ty::ConstKind::Placeholder(_) => {}
499        };
500
501        match lhs.kind() {
502            ty::ConstKind::Value(lhs_val) => match rhs.kind() {
503                ty::ConstKind::Value(rhs_val) => lhs_val.valtree() == rhs_val.valtree(),
504                _ => false,
505            },
506
507            ty::ConstKind::Param(lhs) => {
508                INSTANTIATE_LHS_WITH_INFER
509                    || match rhs.kind() {
510                        ty::ConstKind::Param(rhs) => lhs == rhs,
511                        _ => false,
512                    }
513            }
514
515            // Placeholder consts don't unify with anything on their own
516            ty::ConstKind::Placeholder(lhs) => {
517                matches!(rhs.kind(), ty::ConstKind::Placeholder(rhs) if lhs == rhs)
518            }
519
520            // As we don't necessarily eagerly evaluate constants,
521            // they might unify with any value.
522            ty::ConstKind::Expr(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => {
523                true
524            }
525
526            ty::ConstKind::Infer(_) | ty::ConstKind::Bound(..) => true,
527        }
528    }
529
530    fn var_and_ty_may_unify(self, var: ty::InferTy, ty: I::Ty) -> bool {
531        if !ty.is_known_rigid() {
532            return true;
533        }
534
535        match var {
536            ty::IntVar(_) => ty.is_integral(),
537            ty::FloatVar(_) => ty.is_floating_point(),
538            _ => true,
539        }
540    }
541}
rustc_type_ir/fast_reject.rs

rustc_type_ir/
fast_reject.rs
