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.
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.
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.
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.
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.
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".
34 use rustc_middle
::ty
::fold
::TypeFolder
;
35 use rustc_middle
::ty
::{self, Ty, TyCtxt, TypeFoldable}
;
37 use rustc_data_structures
::fx
::FxHashMap
;
39 use std
::collections
::hash_map
::Entry
;
41 use super::unify_key
::ToType
;
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
>>,
52 impl<'a
, 'tcx
> TypeFreshener
<'a
, 'tcx
> {
53 pub fn new(infcx
: &'a InferCtxt
<'a
, 'tcx
>) -> TypeFreshener
<'a
, 'tcx
> {
57 const_freshen_count
: 0,
58 ty_freshen_map
: Default
::default(),
59 const_freshen_map
: Default
::default(),
65 opt_ty
: Option
<Ty
<'tcx
>>,
70 F
: FnOnce(u32) -> ty
::InferTy
,
72 if let Some(ty
) = opt_ty
{
73 return ty
.fold_with(self);
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
));
90 opt_ct
: Option
<&'tcx ty
::Const
<'tcx
>>,
91 key
: ty
::InferConst
<'tcx
>,
94 ) -> &'tcx ty
::Const
<'tcx
>
96 F
: FnOnce(u32) -> ty
::InferConst
<'tcx
>,
98 if let Some(ct
) = opt_ct
{
99 return ct
.fold_with(self);
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
);
115 impl<'a
, 'tcx
> TypeFolder
<'tcx
> for TypeFreshener
<'a
, 'tcx
> {
116 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
120 fn fold_region(&mut self, r
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
122 ty
::ReLateBound(..) => {
123 // leave bound regions alone
128 | ty
::ReEarlyBound(..)
131 | ty
::RePlaceholder(..)
134 // replace all free regions with 'erased
135 self.tcx().lifetimes
.re_erased
140 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
141 if !t
.needs_infer() && !t
.has_erasable_regions() {
145 let tcx
= self.infcx
.tcx
;
148 ty
::Infer(ty
::TyVar(v
)) => {
149 let opt_ty
= self.infcx
.inner
.borrow_mut().type_variables().probe(v
).known();
150 self.freshen_ty(opt_ty
, ty
::TyVar(v
), ty
::FreshTy
)
153 ty
::Infer(ty
::IntVar(v
)) => self.freshen_ty(
157 .int_unification_table()
159 .map(|v
| v
.to_type(tcx
)),
164 ty
::Infer(ty
::FloatVar(v
)) => self.freshen_ty(
168 .float_unification_table()
170 .map(|v
| v
.to_type(tcx
)),
175 ty
::Infer(ty
::FreshTy(ct
) | ty
::FreshIntTy(ct
) | ty
::FreshFloatTy(ct
)) => {
176 if ct
>= self.ty_freshen_count
{
178 "Encountered a freshend type with id {} \
179 but our counter is only at {}",
181 self.ty_freshen_count
209 | ty
::GeneratorWitness(..)
210 | ty
::Opaque(..) => t
.super_fold_with(self),
212 ty
::Placeholder(..) | ty
::Bound(..) => bug
!("unexpected type {:?}", t
),
216 fn fold_const(&mut self, ct
: &'tcx ty
::Const
<'tcx
>) -> &'tcx ty
::Const
<'tcx
> {
218 ty
::ConstKind
::Infer(ty
::InferConst
::Var(v
)) => {
223 .const_unification_table()
227 return self.freshen_const(
229 ty
::InferConst
::Var(v
),
230 ty
::InferConst
::Fresh
,
234 ty
::ConstKind
::Infer(ty
::InferConst
::Fresh(i
)) => {
235 if i
>= self.const_freshen_count
{
237 "Encountered a freshend const with id {} \
238 but our counter is only at {}",
240 self.const_freshen_count
,
246 ty
::ConstKind
::Bound(..) | ty
::ConstKind
::Placeholder(_
) => {
247 bug
!("unexpected const {:?}", ct
)
250 ty
::ConstKind
::Param(_
)
251 | ty
::ConstKind
::Value(_
)
252 | ty
::ConstKind
::Unevaluated(..)
253 | ty
::ConstKind
::Error(_
) => {}
256 ct
.super_fold_with(self)