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 //! 'static. 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 middle
::ty
::{self, Ty}
;
35 use middle
::ty_fold
::TypeFoldable
;
36 use middle
::ty_fold
::TypeFolder
;
37 use std
::collections
::hash_map
::{self, Entry}
;
40 use super::unify
::InferCtxtMethodsForSimplyUnifiableTypes
;
42 pub struct TypeFreshener
<'a
, 'tcx
:'a
> {
43 infcx
: &'a InferCtxt
<'a
, 'tcx
>,
45 freshen_map
: hash_map
::HashMap
<ty
::InferTy
, Ty
<'tcx
>>,
48 impl<'a
, 'tcx
> TypeFreshener
<'a
, 'tcx
> {
49 pub fn new(infcx
: &'a InferCtxt
<'a
, 'tcx
>) -> TypeFreshener
<'a
, 'tcx
> {
53 freshen_map
: hash_map
::HashMap
::new(),
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
= ty
::mk_infer(self.infcx
.tcx
, freshener(index
));
82 impl<'a
, 'tcx
> TypeFolder
<'tcx
> for TypeFreshener
<'a
, 'tcx
> {
83 fn tcx
<'b
>(&'b
self) -> &'b ty
::ctxt
<'tcx
> {
87 fn fold_region(&mut self, r
: ty
::Region
) -> ty
::Region
{
89 ty
::ReEarlyBound(..) |
90 ty
::ReLateBound(..) => {
91 // leave bound regions alone
100 // replace all free regions with 'static
106 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
108 ty
::ty_infer(ty
::TyVar(v
)) => {
109 self.freshen(self.infcx
.type_variables
.borrow().probe(v
),
114 ty
::ty_infer(ty
::IntVar(v
)) => {
115 self.freshen(self.infcx
.probe_var(v
),
120 ty
::ty_infer(ty
::FloatVar(v
)) => {
121 self.freshen(self.infcx
.probe_var(v
),
126 ty
::ty_infer(ty
::FreshTy(c
)) |
127 ty
::ty_infer(ty
::FreshIntTy(c
)) => {
128 if c
>= self.freshen_count
{
130 &format
!("Encountered a freshend type with id {} \
131 but our counter is only at {}",
133 self.freshen_count
));
156 ty
::ty_projection(..) |
157 ty
::ty_param(..) => {
158 ty_fold
::super_fold_ty(self, t
)