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