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