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