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 //! Note that you should be careful not to allow the output of freshening to leak to the user in
  23 //! error messages or in any other form. Freshening is only really useful as an internal detail.
  24 //!
  25 //! __An important detail concerning regions.__ The freshener also replaces *all* regions with
  26 //! 'erased. The reason behind this is that, in general, we do not take region relationships into
  27 //! account when making type-overloaded decisions. This is important because of the design of the
  28 //! region inferencer, which is not based on unification but rather on accumulating and then
  29 //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type
  30 //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type
  31 //! inferencer knows "so far".
  32
  33 use ty::{self, Ty, TyCtxt, TypeFoldable};
  34 use ty::fold::TypeFolder;
  35 use util::nodemap::FnvHashMap;
  36 use std::collections::hash_map::Entry;
  37
  38 use super::InferCtxt;
  39 use super::unify_key::ToType;
  40
  41 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  42     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
  43     freshen_count: u32,
  44     freshen_map: FnvHashMap<ty::InferTy, Ty<'tcx>>,
  45 }
  46
  47 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
  48     pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
  49                -> TypeFreshener<'a, 'gcx, 'tcx> {
  50         TypeFreshener {
  51             infcx: infcx,
  52             freshen_count: 0,
  53             freshen_map: FnvHashMap(),
  54         }
  55     }
  56
  57     fn freshen<F>(&mut self,
  58                   opt_ty: Option<Ty<'tcx>>,
  59                   key: ty::InferTy,
  60                   freshener: F)
  61                   -> Ty<'tcx> where
  62         F: FnOnce(u32) -> ty::InferTy,
  63     {
  64         if let Some(ty) = opt_ty {
  65             return ty.fold_with(self);
  66         }
  67
  68         match self.freshen_map.entry(key) {
  69             Entry::Occupied(entry) => *entry.get(),
  70             Entry::Vacant(entry) => {
  71                 let index = self.freshen_count;
  72                 self.freshen_count += 1;
  73                 let t = self.infcx.tcx.mk_infer(freshener(index));
  74                 entry.insert(t);
  75                 t
  76             }
  77         }
  78     }
  79 }
  80
  81 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
  82     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
  83         self.infcx.tcx
  84     }
  85
  86     fn fold_region(&mut self, r: &'tcx ty::Region) -> &'tcx ty::Region {
  87         match *r {
  88             ty::ReEarlyBound(..) |
  89             ty::ReLateBound(..) => {
  90                 // leave bound regions alone
  91                 r
  92             }
  93
  94             ty::ReStatic |
  95             ty::ReFree(_) |
  96             ty::ReScope(_) |
  97             ty::ReVar(_) |
  98             ty::ReSkolemized(..) |
  99             ty::ReEmpty |
 100             ty::ReErased => {
 101                 // replace all free regions with 'erased
 102                 self.tcx().mk_region(ty::ReErased)
 103             }
 104         }
 105     }
 106
 107     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 108         if !t.needs_infer() && !t.has_erasable_regions() {
 109             return t;
 110         }
 111
 112         let tcx = self.infcx.tcx;
 113
 114         match t.sty {
 115             ty::TyInfer(ty::TyVar(v)) => {
 116                 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v);
 117                 self.freshen(
 118                     opt_ty,
 119                     ty::TyVar(v),
 120                     ty::FreshTy)
 121             }
 122
 123             ty::TyInfer(ty::IntVar(v)) => {
 124                 self.freshen(
 125                     self.infcx.int_unification_table.borrow_mut()
 126                                                     .probe(v)
 127                                                     .map(|v| v.to_type(tcx)),
 128                     ty::IntVar(v),
 129                     ty::FreshIntTy)
 130             }
 131
 132             ty::TyInfer(ty::FloatVar(v)) => {
 133                 self.freshen(
 134                     self.infcx.float_unification_table.borrow_mut()
 135                                                       .probe(v)
 136                                                       .map(|v| v.to_type(tcx)),
 137                     ty::FloatVar(v),
 138                     ty::FreshFloatTy)
 139             }
 140
 141             ty::TyInfer(ty::FreshTy(c)) |
 142             ty::TyInfer(ty::FreshIntTy(c)) |
 143             ty::TyInfer(ty::FreshFloatTy(c)) => {
 144                 if c >= self.freshen_count {
 145                     bug!("Encountered a freshend type with id {} \
 146                           but our counter is only at {}",
 147                          c,
 148                          self.freshen_count);
 149                 }
 150                 t
 151             }
 152
 153             ty::TyBool |
 154             ty::TyChar |
 155             ty::TyInt(..) |
 156             ty::TyUint(..) |
 157             ty::TyFloat(..) |
 158             ty::TyAdt(..) |
 159             ty::TyBox(..) |
 160             ty::TyStr |
 161             ty::TyError |
 162             ty::TyArray(..) |
 163             ty::TySlice(..) |
 164             ty::TyRawPtr(..) |
 165             ty::TyRef(..) |
 166             ty::TyFnDef(..) |
 167             ty::TyFnPtr(_) |
 168             ty::TyTrait(..) |
 169             ty::TyClosure(..) |
 170             ty::TyNever |
 171             ty::TyTuple(..) |
 172             ty::TyProjection(..) |
 173             ty::TyParam(..) |
 174             ty::TyAnon(..) => {
 175                 t.super_fold_with(self)
 176             }
 177         }
 178     }
 179 }