compiler/rustc_middle/src/ty/fast_reject.rs

   1 use crate::mir::Mutability;
   2 use crate::ty::subst::GenericArgKind;
   3 use crate::ty::{self, Ty, TyCtxt, TypeVisitable};
   4 use rustc_hir::def_id::DefId;
   5 use std::fmt::Debug;
   6 use std::hash::Hash;
   7 use std::iter;
   8
   9 use self::SimplifiedTypeGen::*;
  10
  11 pub type SimplifiedType = SimplifiedTypeGen<DefId>;
  12
  13 /// See `simplify_type`
  14 ///
  15 /// Note that we keep this type generic over the type of identifier it uses
  16 /// because we sometimes need to use SimplifiedTypeGen values as stable sorting
  17 /// keys (in which case we use a DefPathHash as id-type) but in the general case
  18 /// the non-stable but fast to construct DefId-version is the better choice.
  19 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable, HashStable)]
  20 pub enum SimplifiedTypeGen<D>
  21 where
  22     D: Copy + Debug + Eq,
  23 {
  24     BoolSimplifiedType,
  25     CharSimplifiedType,
  26     IntSimplifiedType(ty::IntTy),
  27     UintSimplifiedType(ty::UintTy),
  28     FloatSimplifiedType(ty::FloatTy),
  29     AdtSimplifiedType(D),
  30     ForeignSimplifiedType(D),
  31     StrSimplifiedType,
  32     ArraySimplifiedType,
  33     SliceSimplifiedType,
  34     RefSimplifiedType(Mutability),
  35     PtrSimplifiedType(Mutability),
  36     NeverSimplifiedType,
  37     TupleSimplifiedType(usize),
  38     /// A trait object, all of whose components are markers
  39     /// (e.g., `dyn Send + Sync`).
  40     MarkerTraitObjectSimplifiedType,
  41     TraitSimplifiedType(D),
  42     ClosureSimplifiedType(D),
  43     GeneratorSimplifiedType(D),
  44     GeneratorWitnessSimplifiedType(usize),
  45     FunctionSimplifiedType(usize),
  46     PlaceholderSimplifiedType,
  47 }
  48
  49 /// Generic parameters are pretty much just bound variables, e.g.
  50 /// the type of `fn foo<'a, T>(x: &'a T) -> u32 { ... }` can be thought of as
  51 /// `for<'a, T> fn(&'a T) -> u32`.
  52 ///
  53 /// Typecheck of `foo` has to succeed for all possible generic arguments, so
  54 /// during typeck, we have to treat its generic parameters as if they
  55 /// were placeholders.
  56 ///
  57 /// But when calling `foo` we only have to provide a specific generic argument.
  58 /// In that case the generic parameters are instantiated with inference variables.
  59 /// As we use `simplify_type` before that instantiation happens, we just treat
  60 /// generic parameters as if they were inference variables in that case.
  61 #[derive(PartialEq, Eq, Debug, Clone, Copy)]
  62 pub enum TreatParams {
  63     /// Treat parameters as placeholders in the given environment.
  64     ///
  65     /// Note that this also causes us to treat projections as if they were
  66     /// placeholders. This is only correct if the given projection cannot
  67     /// be normalized in the current context. Even if normalization fails,
  68     /// it may still succeed later if the projection contains any inference
  69     /// variables.
  70     AsPlaceholder,
  71     AsInfer,
  72 }
  73
  74 /// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists.
  75 ///
  76 /// **This function should only be used if you need to store or retrieve the type from some
  77 /// hashmap. If you want to quickly decide whether two types may unify, use the [DeepRejectCtxt]
  78 /// instead.**
  79 ///
  80 /// The idea is to get something simple that we can use to quickly decide if two types could unify,
  81 /// for example during method lookup. If this function returns `Some(x)` it can only unify with
  82 /// types for which this method returns either `Some(x)` as well or `None`.
  83 ///
  84 /// A special case here are parameters and projections, which are only injective
  85 /// if they are treated as placeholders.
  86 ///
  87 /// For example when storing impls based on their simplified self type, we treat
  88 /// generic parameters as if they were inference variables. We must not simplify them here,
  89 /// as they can unify with any other type.
  90 ///
  91 /// With projections we have to be even more careful, as treating them as placeholders
  92 /// is only correct if they are fully normalized.
  93 ///
  94 /// ¹ meaning that if the outermost layers are different, then the whole types are also different.
  95 pub fn simplify_type<'tcx>(
  96     tcx: TyCtxt<'tcx>,
  97     ty: Ty<'tcx>,
  98     treat_params: TreatParams,
  99 ) -> Option<SimplifiedType> {
 100     match *ty.kind() {
 101         ty::Bool => Some(BoolSimplifiedType),
 102         ty::Char => Some(CharSimplifiedType),
 103         ty::Int(int_type) => Some(IntSimplifiedType(int_type)),
 104         ty::Uint(uint_type) => Some(UintSimplifiedType(uint_type)),
 105         ty::Float(float_type) => Some(FloatSimplifiedType(float_type)),
 106         ty::Adt(def, _) => Some(AdtSimplifiedType(def.did())),
 107         ty::Str => Some(StrSimplifiedType),
 108         ty::Array(..) => Some(ArraySimplifiedType),
 109         ty::Slice(..) => Some(SliceSimplifiedType),
 110         ty::RawPtr(ptr) => Some(PtrSimplifiedType(ptr.mutbl)),
 111         ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() {
 112             Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => {
 113                 Some(TraitSimplifiedType(principal_def_id))
 114             }
 115             _ => Some(MarkerTraitObjectSimplifiedType),
 116         },
 117         ty::Ref(_, _, mutbl) => Some(RefSimplifiedType(mutbl)),
 118         ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)),
 119         ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)),
 120         ty::GeneratorWitness(tys) => Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len())),
 121         ty::Never => Some(NeverSimplifiedType),
 122         ty::Tuple(tys) => Some(TupleSimplifiedType(tys.len())),
 123         ty::FnPtr(f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())),
 124         ty::Placeholder(..) => Some(PlaceholderSimplifiedType),
 125         ty::Param(_) => match treat_params {
 126             TreatParams::AsPlaceholder => Some(PlaceholderSimplifiedType),
 127             TreatParams::AsInfer => None,
 128         },
 129         ty::Alias(..) => match treat_params {
 130             // When treating `ty::Param` as a placeholder, projections also
 131             // don't unify with anything else as long as they are fully normalized.
 132             //
 133             // We will have to be careful with lazy normalization here.
 134             TreatParams::AsPlaceholder if !ty.has_non_region_infer() => {
 135                 debug!("treating `{}` as a placeholder", ty);
 136                 Some(PlaceholderSimplifiedType)
 137             }
 138             TreatParams::AsPlaceholder | TreatParams::AsInfer => None,
 139         },
 140         ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)),
 141         ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None,
 142     }
 143 }
 144
 145 impl<D: Copy + Debug + Eq> SimplifiedTypeGen<D> {
 146     pub fn def(self) -> Option<D> {
 147         match self {
 148             AdtSimplifiedType(d)
 149             | ForeignSimplifiedType(d)
 150             | TraitSimplifiedType(d)
 151             | ClosureSimplifiedType(d)
 152             | GeneratorSimplifiedType(d) => Some(d),
 153             _ => None,
 154         }
 155     }
 156
 157     pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U>
 158     where
 159         F: Fn(D) -> U,
 160         U: Copy + Debug + Eq,
 161     {
 162         match self {
 163             BoolSimplifiedType => BoolSimplifiedType,
 164             CharSimplifiedType => CharSimplifiedType,
 165             IntSimplifiedType(t) => IntSimplifiedType(t),
 166             UintSimplifiedType(t) => UintSimplifiedType(t),
 167             FloatSimplifiedType(t) => FloatSimplifiedType(t),
 168             AdtSimplifiedType(d) => AdtSimplifiedType(map(d)),
 169             ForeignSimplifiedType(d) => ForeignSimplifiedType(map(d)),
 170             StrSimplifiedType => StrSimplifiedType,
 171             ArraySimplifiedType => ArraySimplifiedType,
 172             SliceSimplifiedType => SliceSimplifiedType,
 173             RefSimplifiedType(m) => RefSimplifiedType(m),
 174             PtrSimplifiedType(m) => PtrSimplifiedType(m),
 175             NeverSimplifiedType => NeverSimplifiedType,
 176             MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType,
 177             TupleSimplifiedType(n) => TupleSimplifiedType(n),
 178             TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
 179             ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
 180             GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
 181             GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n),
 182             FunctionSimplifiedType(n) => FunctionSimplifiedType(n),
 183             PlaceholderSimplifiedType => PlaceholderSimplifiedType,
 184         }
 185     }
 186 }
 187
 188 /// Given generic arguments from an obligation and an impl,
 189 /// could these two be unified after replacing parameters in the
 190 /// the impl with inference variables.
 191 ///
 192 /// For obligations, parameters won't be replaced by inference
 193 /// variables and only unify with themselves. We treat them
 194 /// the same way we treat placeholders.
 195 ///
 196 /// We also use this function during coherence. For coherence the
 197 /// impls only have to overlap for some value, so we treat parameters
 198 /// on both sides like inference variables. This behavior is toggled
 199 /// using the `treat_obligation_params` field.
 200 #[derive(Debug, Clone, Copy)]
 201 pub struct DeepRejectCtxt {
 202     pub treat_obligation_params: TreatParams,
 203 }
 204
 205 impl DeepRejectCtxt {
 206     pub fn generic_args_may_unify<'tcx>(
 207         self,
 208         obligation_arg: ty::GenericArg<'tcx>,
 209         impl_arg: ty::GenericArg<'tcx>,
 210     ) -> bool {
 211         match (obligation_arg.unpack(), impl_arg.unpack()) {
 212             // We don't fast reject based on regions for now.
 213             (GenericArgKind::Lifetime(_), GenericArgKind::Lifetime(_)) => true,
 214             (GenericArgKind::Type(obl), GenericArgKind::Type(imp)) => {
 215                 self.types_may_unify(obl, imp)
 216             }
 217             (GenericArgKind::Const(obl), GenericArgKind::Const(imp)) => {
 218                 self.consts_may_unify(obl, imp)
 219             }
 220             _ => bug!("kind mismatch: {obligation_arg} {impl_arg}"),
 221         }
 222     }
 223
 224     pub fn types_may_unify<'tcx>(self, obligation_ty: Ty<'tcx>, impl_ty: Ty<'tcx>) -> bool {
 225         match impl_ty.kind() {
 226             // Start by checking whether the type in the impl may unify with
 227             // pretty much everything. Just return `true` in that case.
 228             ty::Param(_) | ty::Error(_) | ty::Alias(..) => return true,
 229             // These types only unify with inference variables or their own
 230             // variant.
 231             ty::Bool
 232             | ty::Char
 233             | ty::Int(_)
 234             | ty::Uint(_)
 235             | ty::Float(_)
 236             | ty::Adt(..)
 237             | ty::Str
 238             | ty::Array(..)
 239             | ty::Slice(..)
 240             | ty::RawPtr(..)
 241             | ty::Dynamic(..)
 242             | ty::Ref(..)
 243             | ty::Never
 244             | ty::Tuple(..)
 245             | ty::FnPtr(..)
 246             | ty::Foreign(..) => {}
 247             ty::FnDef(..)
 248             | ty::Closure(..)
 249             | ty::Generator(..)
 250             | ty::GeneratorWitness(..)
 251             | ty::Placeholder(..)
 252             | ty::Bound(..)
 253             | ty::Infer(_) => bug!("unexpected impl_ty: {impl_ty}"),
 254         }
 255
 256         let k = impl_ty.kind();
 257         match *obligation_ty.kind() {
 258             // Purely rigid types, use structural equivalence.
 259             ty::Bool
 260             | ty::Char
 261             | ty::Int(_)
 262             | ty::Uint(_)
 263             | ty::Float(_)
 264             | ty::Str
 265             | ty::Never
 266             | ty::Foreign(_) => obligation_ty == impl_ty,
 267             ty::Ref(_, obl_ty, obl_mutbl) => match k {
 268                 &ty::Ref(_, impl_ty, impl_mutbl) => {
 269                     obl_mutbl == impl_mutbl && self.types_may_unify(obl_ty, impl_ty)
 270                 }
 271                 _ => false,
 272             },
 273             ty::Adt(obl_def, obl_substs) => match k {
 274                 &ty::Adt(impl_def, impl_substs) => {
 275                     obl_def == impl_def
 276                         && iter::zip(obl_substs, impl_substs)
 277                             .all(|(obl, imp)| self.generic_args_may_unify(obl, imp))
 278                 }
 279                 _ => false,
 280             },
 281             ty::Slice(obl_ty) => {
 282                 matches!(k, &ty::Slice(impl_ty) if self.types_may_unify(obl_ty, impl_ty))
 283             }
 284             ty::Array(obl_ty, obl_len) => match k {
 285                 &ty::Array(impl_ty, impl_len) => {
 286                     self.types_may_unify(obl_ty, impl_ty)
 287                         && self.consts_may_unify(obl_len, impl_len)
 288                 }
 289                 _ => false,
 290             },
 291             ty::Tuple(obl) => match k {
 292                 &ty::Tuple(imp) => {
 293                     obl.len() == imp.len()
 294                         && iter::zip(obl, imp).all(|(obl, imp)| self.types_may_unify(obl, imp))
 295                 }
 296                 _ => false,
 297             },
 298             ty::RawPtr(obl) => match k {
 299                 ty::RawPtr(imp) => obl.mutbl == imp.mutbl && self.types_may_unify(obl.ty, imp.ty),
 300                 _ => false,
 301             },
 302             ty::Dynamic(obl_preds, ..) => {
 303                 // Ideally we would walk the existential predicates here or at least
 304                 // compare their length. But considering that the relevant `Relate` impl
 305                 // actually sorts and deduplicates these, that doesn't work.
 306                 matches!(k, ty::Dynamic(impl_preds, ..) if
 307                     obl_preds.principal_def_id() == impl_preds.principal_def_id()
 308                 )
 309             }
 310             ty::FnPtr(obl_sig) => match k {
 311                 ty::FnPtr(impl_sig) => {
 312                     let ty::FnSig { inputs_and_output, c_variadic, unsafety, abi } =
 313                         obl_sig.skip_binder();
 314                     let impl_sig = impl_sig.skip_binder();
 315
 316                     abi == impl_sig.abi
 317                         && c_variadic == impl_sig.c_variadic
 318                         && unsafety == impl_sig.unsafety
 319                         && inputs_and_output.len() == impl_sig.inputs_and_output.len()
 320                         && iter::zip(inputs_and_output, impl_sig.inputs_and_output)
 321                             .all(|(obl, imp)| self.types_may_unify(obl, imp))
 322                 }
 323                 _ => false,
 324             },
 325
 326             // Impls cannot contain these types as these cannot be named directly.
 327             ty::FnDef(..) | ty::Closure(..) | ty::Generator(..) => false,
 328
 329             ty::Placeholder(..) => false,
 330
 331             // Depending on the value of `treat_obligation_params`, we either
 332             // treat generic parameters like placeholders or like inference variables.
 333             ty::Param(_) => match self.treat_obligation_params {
 334                 TreatParams::AsPlaceholder => false,
 335                 TreatParams::AsInfer => true,
 336             },
 337
 338             ty::Infer(_) => true,
 339
 340             // As we're walking the whole type, it may encounter projections
 341             // inside of binders and what not, so we're just going to assume that
 342             // projections can unify with other stuff.
 343             //
 344             // Looking forward to lazy normalization this is the safer strategy anyways.
 345             ty::Alias(..) => true,
 346
 347             ty::Error(_) => true,
 348
 349             ty::GeneratorWitness(..) | ty::Bound(..) => {
 350                 bug!("unexpected obligation type: {:?}", obligation_ty)
 351             }
 352         }
 353     }
 354
 355     pub fn consts_may_unify(self, obligation_ct: ty::Const<'_>, impl_ct: ty::Const<'_>) -> bool {
 356         match impl_ct.kind() {
 357             ty::ConstKind::Expr(_)
 358             | ty::ConstKind::Param(_)
 359             | ty::ConstKind::Unevaluated(_)
 360             | ty::ConstKind::Error(_) => {
 361                 return true;
 362             }
 363             ty::ConstKind::Value(_) => {}
 364             ty::ConstKind::Infer(_) | ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => {
 365                 bug!("unexpected impl arg: {:?}", impl_ct)
 366             }
 367         }
 368
 369         let k = impl_ct.kind();
 370         match obligation_ct.kind() {
 371             ty::ConstKind::Param(_) => match self.treat_obligation_params {
 372                 TreatParams::AsPlaceholder => false,
 373                 TreatParams::AsInfer => true,
 374             },
 375
 376             // As we don't necessarily eagerly evaluate constants,
 377             // they might unify with any value.
 378             ty::ConstKind::Expr(_) | ty::ConstKind::Unevaluated(_) | ty::ConstKind::Error(_) => {
 379                 true
 380             }
 381             ty::ConstKind::Value(obl) => match k {
 382                 ty::ConstKind::Value(imp) => obl == imp,
 383                 _ => true,
 384             },
 385
 386             ty::ConstKind::Infer(_) => true,
 387
 388             ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => {
 389                 bug!("unexpected obl const: {:?}", obligation_ct)
 390             }
 391         }
 392     }
 393 }