src/librustc/ty/fast_reject.rs

   1 use crate::hir::def_id::DefId;
   2 use crate::ich::StableHashingContext;
   3 use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
   4 use std::fmt::Debug;
   5 use std::hash::Hash;
   6 use std::mem;
   7 use syntax::ast;
   8 use crate::ty::{self, Ty, TyCtxt};
   9
  10 use self::SimplifiedTypeGen::*;
  11
  12 pub type SimplifiedType = SimplifiedTypeGen<DefId>;
  13
  14 /// See `simplify_type`
  15 ///
  16 /// Note that we keep this type generic over the type of identifier it uses
  17 /// because we sometimes need to use SimplifiedTypeGen values as stable sorting
  18 /// keys (in which case we use a DefPathHash as id-type) but in the general case
  19 /// the non-stable but fast to construct DefId-version is the better choice.
  20 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, RustcEncodable, RustcDecodable)]
  21 pub enum SimplifiedTypeGen<D>
  22     where D: Copy + Debug + Ord + Eq
  23 {
  24     BoolSimplifiedType,
  25     CharSimplifiedType,
  26     IntSimplifiedType(ast::IntTy),
  27     UintSimplifiedType(ast::UintTy),
  28     FloatSimplifiedType(ast::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, ..) => {
  73             match trait_info.principal_def_id() {
  74                 Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => {
  75                     Some(TraitSimplifiedType(principal_def_id))
  76                 }
  77                 _ => Some(MarkerTraitObjectSimplifiedType)
  78             }
  79         }
  80         ty::Ref(_, ty, _) => {
  81             // since we introduce auto-refs during method lookup, we
  82             // just treat &T and T as equivalent from the point of
  83             // view of possibly unifying
  84             simplify_type(tcx, ty, can_simplify_params)
  85         }
  86         ty::FnDef(def_id, _) |
  87         ty::Closure(def_id, _) => {
  88             Some(ClosureSimplifiedType(def_id))
  89         }
  90         ty::Generator(def_id, _, _) => {
  91             Some(GeneratorSimplifiedType(def_id))
  92         }
  93         ty::GeneratorWitness(ref tys) => {
  94             Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len()))
  95         }
  96         ty::Never => Some(NeverSimplifiedType),
  97         ty::Tuple(ref tys) => {
  98             Some(TupleSimplifiedType(tys.len()))
  99         }
 100         ty::FnPtr(ref f) => {
 101             Some(FunctionSimplifiedType(f.skip_binder().inputs().len()))
 102         }
 103         ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
 104         ty::Projection(_) | ty::Param(_) => {
 105             if can_simplify_params {
 106                 // In normalized types, projections don't unify with
 107                 // anything. when lazy normalization happens, this
 108                 // will change. It would still be nice to have a way
 109                 // to deal with known-not-to-unify-with-anything
 110                 // projections (e.g., the likes of <__S as Encoder>::Error).
 111                 Some(ParameterSimplifiedType)
 112             } else {
 113                 None
 114             }
 115         }
 116         ty::Opaque(def_id, _) => {
 117             Some(OpaqueSimplifiedType(def_id))
 118         }
 119         ty::Foreign(def_id) => {
 120             Some(ForeignSimplifiedType(def_id))
 121         }
 122         ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) | ty::Error => None,
 123     }
 124 }
 125
 126 impl<D: Copy + Debug + Ord + Eq> SimplifiedTypeGen<D> {
 127     pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U>
 128         where F: Fn(D) -> U,
 129               U: Copy + Debug + Ord + Eq,
 130     {
 131         match self {
 132             BoolSimplifiedType => BoolSimplifiedType,
 133             CharSimplifiedType => CharSimplifiedType,
 134             IntSimplifiedType(t) => IntSimplifiedType(t),
 135             UintSimplifiedType(t) => UintSimplifiedType(t),
 136             FloatSimplifiedType(t) => FloatSimplifiedType(t),
 137             AdtSimplifiedType(d) => AdtSimplifiedType(map(d)),
 138             StrSimplifiedType => StrSimplifiedType,
 139             ArraySimplifiedType => ArraySimplifiedType,
 140             PtrSimplifiedType => PtrSimplifiedType,
 141             NeverSimplifiedType => NeverSimplifiedType,
 142             MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType,
 143             TupleSimplifiedType(n) => TupleSimplifiedType(n),
 144             TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
 145             ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
 146             GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
 147             GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n),
 148             OpaqueSimplifiedType(d) => OpaqueSimplifiedType(map(d)),
 149             FunctionSimplifiedType(n) => FunctionSimplifiedType(n),
 150             ParameterSimplifiedType => ParameterSimplifiedType,
 151             ForeignSimplifiedType(d) => ForeignSimplifiedType(d),
 152         }
 153     }
 154 }
 155
 156 impl<'a, D> HashStable<StableHashingContext<'a>> for SimplifiedTypeGen<D>
 157 where
 158     D: Copy + Debug + Ord + Eq + HashStable<StableHashingContext<'a>>,
 159 {
 160     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 161         mem::discriminant(self).hash_stable(hcx, hasher);
 162         match *self {
 163             BoolSimplifiedType |
 164             CharSimplifiedType |
 165             StrSimplifiedType |
 166             ArraySimplifiedType |
 167             PtrSimplifiedType |
 168             NeverSimplifiedType |
 169             ParameterSimplifiedType |
 170             MarkerTraitObjectSimplifiedType => {
 171                 // nothing to do
 172             }
 173             IntSimplifiedType(t) => t.hash_stable(hcx, hasher),
 174             UintSimplifiedType(t) => t.hash_stable(hcx, hasher),
 175             FloatSimplifiedType(t) => t.hash_stable(hcx, hasher),
 176             AdtSimplifiedType(d) => d.hash_stable(hcx, hasher),
 177             TupleSimplifiedType(n) => n.hash_stable(hcx, hasher),
 178             TraitSimplifiedType(d) => d.hash_stable(hcx, hasher),
 179             ClosureSimplifiedType(d) => d.hash_stable(hcx, hasher),
 180             GeneratorSimplifiedType(d) => d.hash_stable(hcx, hasher),
 181             GeneratorWitnessSimplifiedType(n) => n.hash_stable(hcx, hasher),
 182             OpaqueSimplifiedType(d) => d.hash_stable(hcx, hasher),
 183             FunctionSimplifiedType(n) => n.hash_stable(hcx, hasher),
 184             ForeignSimplifiedType(d) => d.hash_stable(hcx, hasher),
 185         }
 186     }
 187 }