src/librustc/infer/freshen.rs

   1 //! Freshening is the process of replacing unknown variables with fresh types. The idea is that
   2 //! the type, after freshening, contains no inference variables but instead contains either a
   3 //! value for each variable or fresh "arbitrary" types wherever a variable would have been.
   4 //!
   5 //! Freshening is used primarily to get a good type for inserting into a cache. The result
   6 //! summarizes what the type inferencer knows "so far". The primary place it is used right now is
   7 //! in the trait matching algorithm, which needs to be able to cache whether an `impl` self type
   8 //! matches some other type X -- *without* affecting `X`. That means if that if the type `X` is in
   9 //! fact an unbound type variable, we want the match to be regarded as ambiguous, because depending
  10 //! on what type that type variable is ultimately assigned, the match may or may not succeed.
  11 //!
  12 //! To handle closures, freshened types also have to contain the signature and kind of any
  13 //! closure in the local inference context, as otherwise the cache key might be invalidated.
  14 //! The way this is done is somewhat hacky - the closure signature is appended to the substs,
  15 //! as well as the closure kind "encoded" as a type. Also, special handling is needed when
  16 //! the closure signature contains a reference to the original closure.
  17 //!
  18 //! Note that you should be careful not to allow the output of freshening to leak to the user in
  19 //! error messages or in any other form. Freshening is only really useful as an internal detail.
  20 //!
  21 //! Because of the manipulation required to handle closures, doing arbitrary operations on
  22 //! freshened types is not recommended. However, in addition to doing equality/hash
  23 //! comparisons (for caching), it is possible to do a `ty::_match` operation between
  24 //! 2 freshened types - this works even with the closure encoding.
  25 //!
  26 //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with
  27 //! 'erased. The reason behind this is that, in general, we do not take region relationships into
  28 //! account when making type-overloaded decisions. This is important because of the design of the
  29 //! region inferencer, which is not based on unification but rather on accumulating and then
  30 //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type
  31 //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type
  32 //! inferencer knows "so far".
  33
  34 use crate::ty::fold::TypeFolder;
  35 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
  36
  37 use rustc_data_structures::fx::FxHashMap;
  38
  39 use std::collections::hash_map::Entry;
  40
  41 use super::unify_key::ToType;
  42 use super::InferCtxt;
  43
  44 pub struct TypeFreshener<'a, 'tcx> {
  45     infcx: &'a InferCtxt<'a, 'tcx>,
  46     ty_freshen_count: u32,
  47     const_freshen_count: u32,
  48     ty_freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
  49     const_freshen_map: FxHashMap<ty::InferConst<'tcx>, &'tcx ty::Const<'tcx>>,
  50 }
  51
  52 impl<'a, 'tcx> TypeFreshener<'a, 'tcx> {
  53     pub fn new(infcx: &'a InferCtxt<'a, 'tcx>) -> TypeFreshener<'a, 'tcx> {
  54         TypeFreshener {
  55             infcx,
  56             ty_freshen_count: 0,
  57             const_freshen_count: 0,
  58             ty_freshen_map: Default::default(),
  59             const_freshen_map: Default::default(),
  60         }
  61     }
  62
  63     fn freshen_ty<F>(
  64         &mut self,
  65         opt_ty: Option<Ty<'tcx>>,
  66         key: ty::InferTy,
  67         freshener: F,
  68     ) -> Ty<'tcx>
  69     where
  70         F: FnOnce(u32) -> ty::InferTy,
  71     {
  72         if let Some(ty) = opt_ty {
  73             return ty.fold_with(self);
  74         }
  75
  76         match self.ty_freshen_map.entry(key) {
  77             Entry::Occupied(entry) => *entry.get(),
  78             Entry::Vacant(entry) => {
  79                 let index = self.ty_freshen_count;
  80                 self.ty_freshen_count += 1;
  81                 let t = self.infcx.tcx.mk_ty_infer(freshener(index));
  82                 entry.insert(t);
  83                 t
  84             }
  85         }
  86     }
  87
  88     fn freshen_const<F>(
  89         &mut self,
  90         opt_ct: Option<&'tcx ty::Const<'tcx>>,
  91         key: ty::InferConst<'tcx>,
  92         freshener: F,
  93         ty: Ty<'tcx>,
  94     ) -> &'tcx ty::Const<'tcx>
  95     where
  96         F: FnOnce(u32) -> ty::InferConst<'tcx>,
  97     {
  98         if let Some(ct) = opt_ct {
  99             return ct.fold_with(self);
 100         }
 101
 102         match self.const_freshen_map.entry(key) {
 103             Entry::Occupied(entry) => *entry.get(),
 104             Entry::Vacant(entry) => {
 105                 let index = self.const_freshen_count;
 106                 self.const_freshen_count += 1;
 107                 let ct = self.infcx.tcx.mk_const_infer(freshener(index), ty);
 108                 entry.insert(ct);
 109                 ct
 110             }
 111         }
 112     }
 113 }
 114
 115 impl<'a, 'tcx> TypeFolder<'tcx> for TypeFreshener<'a, 'tcx> {
 116     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 117         self.infcx.tcx
 118     }
 119
 120     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 121         match *r {
 122             ty::ReLateBound(..) => {
 123                 // leave bound regions alone
 124                 r
 125             }
 126
 127             ty::ReStatic
 128             | ty::ReEarlyBound(..)
 129             | ty::ReFree(_)
 130             | ty::ReScope(_)
 131             | ty::ReVar(_)
 132             | ty::RePlaceholder(..)
 133             | ty::ReEmpty
 134             | ty::ReErased => {
 135                 // replace all free regions with 'erased
 136                 self.tcx().lifetimes.re_erased
 137             }
 138
 139             ty::ReClosureBound(..) => {
 140                 bug!("encountered unexpected region: {:?}", r,);
 141             }
 142         }
 143     }
 144
 145     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 146         if !t.needs_infer()
 147             && !t.has_erasable_regions()
 148             && !(t.has_closure_types() && self.infcx.in_progress_tables.is_some())
 149         {
 150             return t;
 151         }
 152
 153         let tcx = self.infcx.tcx;
 154
 155         match t.kind {
 156             ty::Infer(ty::TyVar(v)) => {
 157                 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known();
 158                 self.freshen_ty(opt_ty, ty::TyVar(v), ty::FreshTy)
 159             }
 160
 161             ty::Infer(ty::IntVar(v)) => self.freshen_ty(
 162                 self.infcx
 163                     .int_unification_table
 164                     .borrow_mut()
 165                     .probe_value(v)
 166                     .map(|v| v.to_type(tcx)),
 167                 ty::IntVar(v),
 168                 ty::FreshIntTy,
 169             ),
 170
 171             ty::Infer(ty::FloatVar(v)) => self.freshen_ty(
 172                 self.infcx
 173                     .float_unification_table
 174                     .borrow_mut()
 175                     .probe_value(v)
 176                     .map(|v| v.to_type(tcx)),
 177                 ty::FloatVar(v),
 178                 ty::FreshFloatTy,
 179             ),
 180
 181             ty::Infer(ty::FreshTy(ct))
 182             | ty::Infer(ty::FreshIntTy(ct))
 183             | ty::Infer(ty::FreshFloatTy(ct)) => {
 184                 if ct >= self.ty_freshen_count {
 185                     bug!(
 186                         "Encountered a freshend type with id {} \
 187                           but our counter is only at {}",
 188                         ct,
 189                         self.ty_freshen_count
 190                     );
 191                 }
 192                 t
 193             }
 194
 195             ty::Generator(..)
 196             | ty::Bool
 197             | ty::Char
 198             | ty::Int(..)
 199             | ty::Uint(..)
 200             | ty::Float(..)
 201             | ty::Adt(..)
 202             | ty::Str
 203             | ty::Error
 204             | ty::Array(..)
 205             | ty::Slice(..)
 206             | ty::RawPtr(..)
 207             | ty::Ref(..)
 208             | ty::FnDef(..)
 209             | ty::FnPtr(_)
 210             | ty::Dynamic(..)
 211             | ty::Never
 212             | ty::Tuple(..)
 213             | ty::Projection(..)
 214             | ty::UnnormalizedProjection(..)
 215             | ty::Foreign(..)
 216             | ty::Param(..)
 217             | ty::Closure(..)
 218             | ty::GeneratorWitness(..)
 219             | ty::Opaque(..) => t.super_fold_with(self),
 220
 221             ty::Placeholder(..) | ty::Bound(..) => bug!("unexpected type {:?}", t),
 222         }
 223     }
 224
 225     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 226         match ct.val {
 227             ty::ConstKind::Infer(ty::InferConst::Var(v)) => {
 228                 let opt_ct =
 229                     self.infcx.const_unification_table.borrow_mut().probe_value(v).val.known();
 230                 return self.freshen_const(
 231                     opt_ct,
 232                     ty::InferConst::Var(v),
 233                     ty::InferConst::Fresh,
 234                     ct.ty,
 235                 );
 236             }
 237             ty::ConstKind::Infer(ty::InferConst::Fresh(i)) => {
 238                 if i >= self.const_freshen_count {
 239                     bug!(
 240                         "Encountered a freshend const with id {} \
 241                             but our counter is only at {}",
 242                         i,
 243                         self.const_freshen_count,
 244                     );
 245                 }
 246                 return ct;
 247             }
 248
 249             ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => {
 250                 bug!("unexpected const {:?}", ct)
 251             }
 252
 253             ty::ConstKind::Param(_) | ty::ConstKind::Value(_) | ty::ConstKind::Unevaluated(..) => {}
 254         }
 255
 256         ct.super_fold_with(self)
 257     }
 258 }