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

rustc_type_ir/
fast_reject.rs
