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