compiler/rustc_middle/src/ty/fast_reject.rs

   1 use crate::ich::StableHashingContext;
   2 use crate::ty::{self, Ty, TyCtxt};
   3 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   4 use rustc_hir::def_id::DefId;
   5 use std::fmt::Debug;
   6 use std::hash::Hash;
   7 use std::mem;
   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, PartialOrd, Ord, TyEncodable, TyDecodable)]
  20 pub enum SimplifiedTypeGen<D>
  21 where
  22     D: Copy + Debug + Ord + Eq,
  23 {
  24     BoolSimplifiedType,
  25     CharSimplifiedType,
  26     IntSimplifiedType(ty::IntTy),
  27     UintSimplifiedType(ty::UintTy),
  28     FloatSimplifiedType(ty::FloatTy),
  29     AdtSimplifiedType(D),
  30     StrSimplifiedType,
  31     ArraySimplifiedType,
  32     PtrSimplifiedType,
  33     NeverSimplifiedType,
  34     TupleSimplifiedType(usize),
  35     /// A trait object, all of whose components are markers
  36     /// (e.g., `dyn Send + Sync`).
  37     MarkerTraitObjectSimplifiedType,
  38     TraitSimplifiedType(D),
  39     ClosureSimplifiedType(D),
  40     GeneratorSimplifiedType(D),
  41     GeneratorWitnessSimplifiedType(usize),
  42     OpaqueSimplifiedType(D),
  43     FunctionSimplifiedType(usize),
  44     ParameterSimplifiedType,
  45     ForeignSimplifiedType(DefId),
  46 }
  47
  48 /// Tries to simplify a type by dropping type parameters, deref'ing away any reference types, etc.
  49 /// The idea is to get something simple that we can use to quickly decide if two types could unify
  50 /// during method lookup.
  51 ///
  52 /// If `can_simplify_params` is false, then we will fail to simplify type parameters entirely. This
  53 /// is useful when those type parameters would be instantiated with fresh type variables, since
  54 /// then we can't say much about whether two types would unify. Put another way,
  55 /// `can_simplify_params` should be true if type parameters appear free in `ty` and `false` if they
  56 /// are to be considered bound.
  57 pub fn simplify_type(
  58     tcx: TyCtxt<'_>,
  59     ty: Ty<'_>,
  60     can_simplify_params: bool,
  61 ) -> Option<SimplifiedType> {
  62     match *ty.kind() {
  63         ty::Bool => Some(BoolSimplifiedType),
  64         ty::Char => Some(CharSimplifiedType),
  65         ty::Int(int_type) => Some(IntSimplifiedType(int_type)),
  66         ty::Uint(uint_type) => Some(UintSimplifiedType(uint_type)),
  67         ty::Float(float_type) => Some(FloatSimplifiedType(float_type)),
  68         ty::Adt(def, _) => Some(AdtSimplifiedType(def.did)),
  69         ty::Str => Some(StrSimplifiedType),
  70         ty::Array(..) | ty::Slice(_) => Some(ArraySimplifiedType),
  71         ty::RawPtr(_) => Some(PtrSimplifiedType),
  72         ty::Dynamic(ref trait_info, ..) => match trait_info.principal_def_id() {
  73             Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => {
  74                 Some(TraitSimplifiedType(principal_def_id))
  75             }
  76             _ => Some(MarkerTraitObjectSimplifiedType),
  77         },
  78         ty::Ref(_, ty, _) => {
  79             // since we introduce auto-refs during method lookup, we
  80             // just treat &T and T as equivalent from the point of
  81             // view of possibly unifying
  82             simplify_type(tcx, ty, can_simplify_params)
  83         }
  84         ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)),
  85         ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)),
  86         ty::GeneratorWitness(ref tys) => {
  87             Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len()))
  88         }
  89         ty::Never => Some(NeverSimplifiedType),
  90         ty::Tuple(ref tys) => Some(TupleSimplifiedType(tys.len())),
  91         ty::FnPtr(ref f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())),
  92         ty::Projection(_) | ty::Param(_) => {
  93             if can_simplify_params {
  94                 // In normalized types, projections don't unify with
  95                 // anything. when lazy normalization happens, this
  96                 // will change. It would still be nice to have a way
  97                 // to deal with known-not-to-unify-with-anything
  98                 // projections (e.g., the likes of <__S as Encoder>::Error).
  99                 Some(ParameterSimplifiedType)
 100             } else {
 101                 None
 102             }
 103         }
 104         ty::Opaque(def_id, _) => Some(OpaqueSimplifiedType(def_id)),
 105         ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)),
 106         ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None,
 107     }
 108 }
 109
 110 impl<D: Copy + Debug + Ord + Eq> SimplifiedTypeGen<D> {
 111     pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U>
 112     where
 113         F: Fn(D) -> U,
 114         U: Copy + Debug + Ord + Eq,
 115     {
 116         match self {
 117             BoolSimplifiedType => BoolSimplifiedType,
 118             CharSimplifiedType => CharSimplifiedType,
 119             IntSimplifiedType(t) => IntSimplifiedType(t),
 120             UintSimplifiedType(t) => UintSimplifiedType(t),
 121             FloatSimplifiedType(t) => FloatSimplifiedType(t),
 122             AdtSimplifiedType(d) => AdtSimplifiedType(map(d)),
 123             StrSimplifiedType => StrSimplifiedType,
 124             ArraySimplifiedType => ArraySimplifiedType,
 125             PtrSimplifiedType => PtrSimplifiedType,
 126             NeverSimplifiedType => NeverSimplifiedType,
 127             MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType,
 128             TupleSimplifiedType(n) => TupleSimplifiedType(n),
 129             TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
 130             ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
 131             GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
 132             GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n),
 133             OpaqueSimplifiedType(d) => OpaqueSimplifiedType(map(d)),
 134             FunctionSimplifiedType(n) => FunctionSimplifiedType(n),
 135             ParameterSimplifiedType => ParameterSimplifiedType,
 136             ForeignSimplifiedType(d) => ForeignSimplifiedType(d),
 137         }
 138     }
 139 }
 140
 141 impl<'a, D> HashStable<StableHashingContext<'a>> for SimplifiedTypeGen<D>
 142 where
 143     D: Copy + Debug + Ord + Eq + HashStable<StableHashingContext<'a>>,
 144 {
 145     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 146         mem::discriminant(self).hash_stable(hcx, hasher);
 147         match *self {
 148             BoolSimplifiedType
 149             | CharSimplifiedType
 150             | StrSimplifiedType
 151             | ArraySimplifiedType
 152             | PtrSimplifiedType
 153             | NeverSimplifiedType
 154             | ParameterSimplifiedType
 155             | MarkerTraitObjectSimplifiedType => {
 156                 // nothing to do
 157             }
 158             IntSimplifiedType(t) => t.hash_stable(hcx, hasher),
 159             UintSimplifiedType(t) => t.hash_stable(hcx, hasher),
 160             FloatSimplifiedType(t) => t.hash_stable(hcx, hasher),
 161             AdtSimplifiedType(d) => d.hash_stable(hcx, hasher),
 162             TupleSimplifiedType(n) => n.hash_stable(hcx, hasher),
 163             TraitSimplifiedType(d) => d.hash_stable(hcx, hasher),
 164             ClosureSimplifiedType(d) => d.hash_stable(hcx, hasher),
 165             GeneratorSimplifiedType(d) => d.hash_stable(hcx, hasher),
 166             GeneratorWitnessSimplifiedType(n) => n.hash_stable(hcx, hasher),
 167             OpaqueSimplifiedType(d) => d.hash_stable(hcx, hasher),
 168             FunctionSimplifiedType(n) => n.hash_stable(hcx, hasher),
 169             ForeignSimplifiedType(d) => d.hash_stable(hcx, hasher),
 170         }
 171     }
 172 }