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.
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.
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.
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.
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.
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".
33 use ty::{self, Ty, TyCtxt, TypeFoldable};
34 use ty::fold::TypeFolder;
35 use util::nodemap::FnvHashMap;
36 use std::collections::hash_map::Entry;
39 use super::unify_key::ToType;
41 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
42 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
44 freshen_map: FnvHashMap<ty::InferTy, Ty<'tcx>>,
47 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
48 pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
49 -> TypeFreshener<'a, 'gcx, 'tcx> {
53 freshen_map: FnvHashMap(),
57 fn freshen<F>(&mut self,
58 opt_ty: Option<Ty<'tcx>>,
62 F: FnOnce(u32) -> ty::InferTy,
65 Some(ty) => { return ty.fold_with(self); }
69 match self.freshen_map.entry(key) {
70 Entry::Occupied(entry) => *entry.get(),
71 Entry::Vacant(entry) => {
72 let index = self.freshen_count;
73 self.freshen_count += 1;
74 let t = self.infcx.tcx.mk_infer(freshener(index));
82 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
83 fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
87 fn fold_region(&mut self, r: &'tcx ty::Region) -> &'tcx ty::Region {
89 ty::ReEarlyBound(..) |
90 ty::ReLateBound(..) => {
91 // leave bound regions alone
99 ty::ReSkolemized(..) |
102 // replace all free regions with 'erased
103 self.tcx().mk_region(ty::ReErased)
108 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
109 if !t.needs_infer() && !t.has_erasable_regions() {
113 let tcx = self.infcx.tcx;
116 ty::TyInfer(ty::TyVar(v)) => {
117 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v);
124 ty::TyInfer(ty::IntVar(v)) => {
126 self.infcx.int_unification_table.borrow_mut()
128 .map(|v| v.to_type(tcx)),
133 ty::TyInfer(ty::FloatVar(v)) => {
135 self.infcx.float_unification_table.borrow_mut()
137 .map(|v| v.to_type(tcx)),
142 ty::TyInfer(ty::FreshTy(c)) |
143 ty::TyInfer(ty::FreshIntTy(c)) |
144 ty::TyInfer(ty::FreshFloatTy(c)) => {
145 if c >= self.freshen_count {
146 bug!("Encountered a freshend type with id {} \
147 but our counter is only at {}",
174 ty::TyProjection(..) |
177 t.super_fold_with(self)