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