1 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
2 use rustc_middle::ty::{self, ConstVid, FloatVid, IntVid, RegionVid, Ty, TyCtxt, TyVid};
4 use super::type_variable::TypeVariableOrigin;
6 use super::{ConstVariableOrigin, RegionVariableOrigin, UnificationTable};
8 use rustc_data_structures::snapshot_vec as sv;
9 use rustc_data_structures::unify as ut;
14 fn vars_since_snapshot<'tcx, T>(
15 table: &mut UnificationTable<'_, 'tcx, T>,
16 snapshot_var_len: usize,
20 super::UndoLog<'tcx>: From<sv::UndoLog<ut::Delegate<T>>>,
22 T::from_index(snapshot_var_len as u32)..T::from_index(table.len() as u32)
25 fn const_vars_since_snapshot<'tcx>(
26 table: &mut UnificationTable<'_, 'tcx, ConstVid<'tcx>>,
27 snapshot_var_len: usize,
28 ) -> (Range<ConstVid<'tcx>>, Vec<ConstVariableOrigin>) {
29 let range = vars_since_snapshot(table, snapshot_var_len);
31 range.start..range.end,
32 (range.start.index..range.end.index)
33 .map(|index| table.probe_value(ConstVid::from_index(index)).origin)
38 struct VariableLengths {
43 region_constraints_len: usize,
46 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
47 fn variable_lengths(&self) -> VariableLengths {
48 let mut inner = self.inner.borrow_mut();
50 type_var_len: inner.type_variables().num_vars(),
51 const_var_len: inner.const_unification_table().len(),
52 int_var_len: inner.int_unification_table().len(),
53 float_var_len: inner.float_unification_table().len(),
54 region_constraints_len: inner.unwrap_region_constraints().num_region_vars(),
58 /// This rather funky routine is used while processing expected
59 /// types. What happens here is that we want to propagate a
60 /// coercion through the return type of a fn to its
61 /// argument. Consider the type of `Option::Some`, which is
62 /// basically `for<T> fn(T) -> Option<T>`. So if we have an
63 /// expression `Some(&[1, 2, 3])`, and that has the expected type
64 /// `Option<&[u32]>`, we would like to type check `&[1, 2, 3]`
65 /// with the expectation of `&[u32]`. This will cause us to coerce
66 /// from `&[u32; 3]` to `&[u32]` and make the users life more
69 /// The way we do this is using `fudge_inference_if_ok`. What the
70 /// routine actually does is to start a snapshot and execute the
71 /// closure `f`. In our example above, what this closure will do
72 /// is to unify the expectation (`Option<&[u32]>`) with the actual
73 /// return type (`Option<?T>`, where `?T` represents the variable
74 /// instantiated for `T`). This will cause `?T` to be unified
75 /// with `&?a [u32]`, where `?a` is a fresh lifetime variable. The
76 /// input type (`?T`) is then returned by `f()`.
78 /// At this point, `fudge_inference_if_ok` will normalize all type
79 /// variables, converting `?T` to `&?a [u32]` and end the
80 /// snapshot. The problem is that we can't just return this type
81 /// out, because it references the region variable `?a`, and that
82 /// region variable was popped when we popped the snapshot.
84 /// So what we do is to keep a list (`region_vars`, in the code below)
85 /// of region variables created during the snapshot (here, `?a`). We
86 /// fold the return value and replace any such regions with a *new*
87 /// region variable (e.g., `?b`) and return the result (`&?b [u32]`).
88 /// This can then be used as the expectation for the fn argument.
90 /// The important point here is that, for soundness purposes, the
91 /// regions in question are not particularly important. We will
92 /// use the expected types to guide coercions, but we will still
93 /// type-check the resulting types from those coercions against
94 /// the actual types (`?T`, `Option<?T>`) -- and remember that
95 /// after the snapshot is popped, the variable `?T` is no longer
97 #[instrument(skip(self, f), level = "debug")]
98 pub fn fudge_inference_if_ok<T, E, F>(&self, f: F) -> Result<T, E>
100 F: FnOnce() -> Result<T, E>,
101 T: TypeFoldable<'tcx>,
103 let variable_lengths = self.variable_lengths();
104 let (mut fudger, value) = self.probe(|_| {
107 let value = self.resolve_vars_if_possible(value);
109 // At this point, `value` could in principle refer
110 // to inference variables that have been created during
111 // the snapshot. Once we exit `probe()`, those are
112 // going to be popped, so we will have to
113 // eliminate any references to them.
115 let mut inner = self.inner.borrow_mut();
117 inner.type_variables().vars_since_snapshot(variable_lengths.type_var_len);
118 let int_vars = vars_since_snapshot(
119 &mut inner.int_unification_table(),
120 variable_lengths.int_var_len,
122 let float_vars = vars_since_snapshot(
123 &mut inner.float_unification_table(),
124 variable_lengths.float_var_len,
126 let region_vars = inner
127 .unwrap_region_constraints()
128 .vars_since_snapshot(variable_lengths.region_constraints_len);
129 let const_vars = const_vars_since_snapshot(
130 &mut inner.const_unification_table(),
131 variable_lengths.const_var_len,
134 let fudger = InferenceFudger {
149 // At this point, we need to replace any of the now-popped
150 // type/region variables that appear in `value` with a fresh
151 // variable of the appropriate kind. We can't do this during
152 // the probe because they would just get popped then too. =)
154 // Micro-optimization: if no variables have been created, then
155 // `value` can't refer to any of them. =) So we can just return it.
156 if fudger.type_vars.0.is_empty()
157 && fudger.int_vars.is_empty()
158 && fudger.float_vars.is_empty()
159 && fudger.region_vars.0.is_empty()
160 && fudger.const_vars.0.is_empty()
164 Ok(value.fold_with(&mut fudger))
169 pub struct InferenceFudger<'a, 'tcx> {
170 infcx: &'a InferCtxt<'a, 'tcx>,
171 type_vars: (Range<TyVid>, Vec<TypeVariableOrigin>),
172 int_vars: Range<IntVid>,
173 float_vars: Range<FloatVid>,
174 region_vars: (Range<RegionVid>, Vec<RegionVariableOrigin>),
175 const_vars: (Range<ConstVid<'tcx>>, Vec<ConstVariableOrigin>),
178 impl<'a, 'tcx> TypeFolder<'tcx> for InferenceFudger<'a, 'tcx> {
179 fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
183 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
185 ty::Infer(ty::InferTy::TyVar(vid)) => {
186 if self.type_vars.0.contains(&vid) {
187 // This variable was created during the fudging.
188 // Recreate it with a fresh variable here.
189 let idx = (vid.as_usize() - self.type_vars.0.start.as_usize()) as usize;
190 let origin = self.type_vars.1[idx];
191 self.infcx.next_ty_var(origin)
193 // This variable was created before the
194 // "fudging". Since we refresh all type
195 // variables to their binding anyhow, we know
196 // that it is unbound, so we can just return
199 self.infcx.inner.borrow_mut().type_variables().probe(vid).is_unknown()
204 ty::Infer(ty::InferTy::IntVar(vid)) => {
205 if self.int_vars.contains(&vid) {
206 self.infcx.next_int_var()
211 ty::Infer(ty::InferTy::FloatVar(vid)) => {
212 if self.float_vars.contains(&vid) {
213 self.infcx.next_float_var()
218 _ => ty.super_fold_with(self),
222 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
223 if let ty::ReVar(vid) = *r && self.region_vars.0.contains(&vid) {
224 let idx = vid.index() - self.region_vars.0.start.index();
225 let origin = self.region_vars.1[idx];
226 return self.infcx.next_region_var(origin);
231 fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
232 if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.val() {
233 if self.const_vars.0.contains(&vid) {
234 // This variable was created during the fudging.
235 // Recreate it with a fresh variable here.
236 let idx = (vid.index - self.const_vars.0.start.index) as usize;
237 let origin = self.const_vars.1[idx];
238 self.infcx.next_const_var(ct.ty(), origin)
243 ct.super_fold_with(self)