src/librustc/ty/fast_reject.rs

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