rustc_infer/infer/
freshen.rs

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.
4//!
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 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.
11//!
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 args,
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.
17//!
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.
20//!
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//! two freshened types - this works even with the closure encoding.
25//!
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".
33
34use std::collections::hash_map::Entry;
35
36use rustc_data_structures::fx::FxHashMap;
37use rustc_middle::bug;
38use rustc_middle::ty::{
39    self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt,
40};
41
42use super::InferCtxt;
43
44pub struct TypeFreshener<'a, 'tcx> {
45    infcx: &'a InferCtxt<'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, ty::Const<'tcx>>,
50}
51
52impl<'a, 'tcx> TypeFreshener<'a, 'tcx> {
53    pub fn new(infcx: &'a InferCtxt<'tcx>) -> TypeFreshener<'a, 'tcx> {
54        TypeFreshener {
55            infcx,
56            ty_freshen_count: 0,
57            const_freshen_count: 0,
58            ty_freshen_map: Default::default(),
59            const_freshen_map: Default::default(),
60        }
61    }
62
63    fn freshen_ty<F>(&mut self, input: Result<Ty<'tcx>, ty::InferTy>, mk_fresh: F) -> Ty<'tcx>
64    where
65        F: FnOnce(u32) -> Ty<'tcx>,
66    {
67        match input {
68            Ok(ty) => ty.fold_with(self),
69            Err(key) => match self.ty_freshen_map.entry(key) {
70                Entry::Occupied(entry) => *entry.get(),
71                Entry::Vacant(entry) => {
72                    let index = self.ty_freshen_count;
73                    self.ty_freshen_count += 1;
74                    let t = mk_fresh(index);
75                    entry.insert(t);
76                    t
77                }
78            },
79        }
80    }
81
82    fn freshen_const<F>(
83        &mut self,
84        input: Result<ty::Const<'tcx>, ty::InferConst>,
85        freshener: F,
86    ) -> ty::Const<'tcx>
87    where
88        F: FnOnce(u32) -> ty::InferConst,
89    {
90        match input {
91            Ok(ct) => ct.fold_with(self),
92            Err(key) => match self.const_freshen_map.entry(key) {
93                Entry::Occupied(entry) => *entry.get(),
94                Entry::Vacant(entry) => {
95                    let index = self.const_freshen_count;
96                    self.const_freshen_count += 1;
97                    let ct = ty::Const::new_infer(self.infcx.tcx, freshener(index));
98                    entry.insert(ct);
99                    ct
100                }
101            },
102        }
103    }
104}
105
106impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for TypeFreshener<'a, 'tcx> {
107    fn cx(&self) -> TyCtxt<'tcx> {
108        self.infcx.tcx
109    }
110
111    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
112        match r.kind() {
113            // Leave bound regions alone, since they affect selection via the leak check.
114            ty::ReBound(..) => r,
115            // Leave error regions alone, since they affect selection b/c of incompleteness.
116            ty::ReError(_) => r,
117
118            ty::ReEarlyParam(..)
119            | ty::ReLateParam(_)
120            | ty::ReVar(_)
121            | ty::RePlaceholder(..)
122            | ty::ReStatic
123            | ty::ReErased => self.cx().lifetimes.re_erased,
124        }
125    }
126
127    #[inline]
128    fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
129        if !t.has_infer() && !t.has_erasable_regions() {
130            t
131        } else {
132            match *t.kind() {
133                ty::Infer(v) => self.fold_infer_ty(v).unwrap_or(t),
134
135                // This code is hot enough that a non-debug assertion here makes a noticeable
136                // difference on benchmarks like `wg-grammar`.
137                #[cfg(debug_assertions)]
138                ty::Placeholder(..) | ty::Bound(..) => bug!("unexpected type {:?}", t),
139
140                _ => t.super_fold_with(self),
141            }
142        }
143    }
144
145    fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
146        match ct.kind() {
147            ty::ConstKind::Infer(ty::InferConst::Var(v)) => {
148                let mut inner = self.infcx.inner.borrow_mut();
149                let input =
150                    inner.const_unification_table().probe_value(v).known().ok_or_else(|| {
151                        ty::InferConst::Var(inner.const_unification_table().find(v).vid)
152                    });
153                drop(inner);
154                self.freshen_const(input, ty::InferConst::Fresh)
155            }
156            ty::ConstKind::Infer(ty::InferConst::Fresh(i)) => {
157                if i >= self.const_freshen_count {
158                    bug!(
159                        "Encountered a freshend const with id {} \
160                            but our counter is only at {}",
161                        i,
162                        self.const_freshen_count,
163                    );
164                }
165                ct
166            }
167
168            ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => {
169                bug!("unexpected const {:?}", ct)
170            }
171
172            ty::ConstKind::Param(_)
173            | ty::ConstKind::Value(_)
174            | ty::ConstKind::Unevaluated(..)
175            | ty::ConstKind::Expr(..)
176            | ty::ConstKind::Error(_) => ct.super_fold_with(self),
177        }
178    }
179}
180
181impl<'a, 'tcx> TypeFreshener<'a, 'tcx> {
182    // This is separate from `fold_ty` to keep that method small and inlinable.
183    #[inline(never)]
184    fn fold_infer_ty(&mut self, v: ty::InferTy) -> Option<Ty<'tcx>> {
185        match v {
186            ty::TyVar(v) => {
187                let mut inner = self.infcx.inner.borrow_mut();
188                let input = inner
189                    .type_variables()
190                    .probe(v)
191                    .known()
192                    .ok_or_else(|| ty::TyVar(inner.type_variables().root_var(v)));
193                drop(inner);
194                Some(self.freshen_ty(input, |n| Ty::new_fresh(self.infcx.tcx, n)))
195            }
196
197            ty::IntVar(v) => {
198                let mut inner = self.infcx.inner.borrow_mut();
199                let value = inner.int_unification_table().probe_value(v);
200                let input = match value {
201                    ty::IntVarValue::IntType(ty) => Ok(Ty::new_int(self.infcx.tcx, ty)),
202                    ty::IntVarValue::UintType(ty) => Ok(Ty::new_uint(self.infcx.tcx, ty)),
203                    ty::IntVarValue::Unknown => {
204                        Err(ty::IntVar(inner.int_unification_table().find(v)))
205                    }
206                };
207                drop(inner);
208                Some(self.freshen_ty(input, |n| Ty::new_fresh_int(self.infcx.tcx, n)))
209            }
210
211            ty::FloatVar(v) => {
212                let mut inner = self.infcx.inner.borrow_mut();
213                let value = inner.float_unification_table().probe_value(v);
214                let input = match value {
215                    ty::FloatVarValue::Known(ty) => Ok(Ty::new_float(self.infcx.tcx, ty)),
216                    ty::FloatVarValue::Unknown => {
217                        Err(ty::FloatVar(inner.float_unification_table().find(v)))
218                    }
219                };
220                drop(inner);
221                Some(self.freshen_ty(input, |n| Ty::new_fresh_float(self.infcx.tcx, n)))
222            }
223
224            ty::FreshTy(ct) | ty::FreshIntTy(ct) | ty::FreshFloatTy(ct) => {
225                if ct >= self.ty_freshen_count {
226                    bug!(
227                        "Encountered a freshend type with id {} \
228                          but our counter is only at {}",
229                        ct,
230                        self.ty_freshen_count
231                    );
232                }
233                None
234            }
235        }
236    }
237}