compiler/rustc_infer/src/infer/fudge.rs

   1 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
   2 use rustc_middle::ty::{self, ConstVid, FloatVid, IntVid, RegionVid, Ty, TyCtxt, TyVid};
   3
   4 use super::type_variable::TypeVariableOrigin;
   5 use super::InferCtxt;
   6 use super::{ConstVariableOrigin, RegionVariableOrigin, UnificationTable};
   7
   8 use rustc_data_structures::snapshot_vec as sv;
   9 use rustc_data_structures::unify as ut;
  10 use ut::UnifyKey;
  11
  12 use std::ops::Range;
  13
  14 fn vars_since_snapshot<'tcx, T>(
  15     table: &mut UnificationTable<'_, 'tcx, T>,
  16     snapshot_var_len: usize,
  17 ) -> Range<T>
  18 where
  19     T: UnifyKey,
  20     super::UndoLog<'tcx>: From<sv::UndoLog<ut::Delegate<T>>>,
  21 {
  22     T::from_index(snapshot_var_len as u32)..T::from_index(table.len() as u32)
  23 }
  24
  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);
  30     (
  31         range.start..range.end,
  32         (range.start.index..range.end.index)
  33             .map(|index| table.probe_value(ConstVid::from_index(index)).origin)
  34             .collect(),
  35     )
  36 }
  37
  38 struct VariableLengths {
  39     type_var_len: usize,
  40     const_var_len: usize,
  41     int_var_len: usize,
  42     float_var_len: usize,
  43     region_constraints_len: usize,
  44 }
  45
  46 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
  47     fn variable_lengths(&self) -> VariableLengths {
  48         let mut inner = self.inner.borrow_mut();
  49         VariableLengths {
  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(),
  55         }
  56     }
  57
  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
  67     /// pleasant.
  68     ///
  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()`.
  77     ///
  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.
  83     ///
  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.
  89     ///
  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
  96     /// unified.
  97     pub fn fudge_inference_if_ok<T, E, F>(&self, f: F) -> Result<T, E>
  98     where
  99         F: FnOnce() -> Result<T, E>,
 100         T: TypeFoldable<'tcx>,
 101     {
 102         debug!("fudge_inference_if_ok()");
 103
 104         let variable_lengths = self.variable_lengths();
 105         let (mut fudger, value) = self.probe(|_| {
 106             match f() {
 107                 Ok(value) => {
 108                     let value = self.resolve_vars_if_possible(value);
 109
 110                     // At this point, `value` could in principle refer
 111                     // to inference variables that have been created during
 112                     // the snapshot. Once we exit `probe()`, those are
 113                     // going to be popped, so we will have to
 114                     // eliminate any references to them.
 115
 116                     let mut inner = self.inner.borrow_mut();
 117                     let type_vars =
 118                         inner.type_variables().vars_since_snapshot(variable_lengths.type_var_len);
 119                     let int_vars = vars_since_snapshot(
 120                         &mut inner.int_unification_table(),
 121                         variable_lengths.int_var_len,
 122                     );
 123                     let float_vars = vars_since_snapshot(
 124                         &mut inner.float_unification_table(),
 125                         variable_lengths.float_var_len,
 126                     );
 127                     let region_vars = inner
 128                         .unwrap_region_constraints()
 129                         .vars_since_snapshot(variable_lengths.region_constraints_len);
 130                     let const_vars = const_vars_since_snapshot(
 131                         &mut inner.const_unification_table(),
 132                         variable_lengths.const_var_len,
 133                     );
 134
 135                     let fudger = InferenceFudger {
 136                         infcx: self,
 137                         type_vars,
 138                         int_vars,
 139                         float_vars,
 140                         region_vars,
 141                         const_vars,
 142                     };
 143
 144                     Ok((fudger, value))
 145                 }
 146                 Err(e) => Err(e),
 147             }
 148         })?;
 149
 150         // At this point, we need to replace any of the now-popped
 151         // type/region variables that appear in `value` with a fresh
 152         // variable of the appropriate kind. We can't do this during
 153         // the probe because they would just get popped then too. =)
 154
 155         // Micro-optimization: if no variables have been created, then
 156         // `value` can't refer to any of them. =) So we can just return it.
 157         if fudger.type_vars.0.is_empty()
 158             && fudger.int_vars.is_empty()
 159             && fudger.float_vars.is_empty()
 160             && fudger.region_vars.0.is_empty()
 161             && fudger.const_vars.0.is_empty()
 162         {
 163             Ok(value)
 164         } else {
 165             Ok(value.fold_with(&mut fudger))
 166         }
 167     }
 168 }
 169
 170 pub struct InferenceFudger<'a, 'tcx> {
 171     infcx: &'a InferCtxt<'a, 'tcx>,
 172     type_vars: (Range<TyVid>, Vec<TypeVariableOrigin>),
 173     int_vars: Range<IntVid>,
 174     float_vars: Range<FloatVid>,
 175     region_vars: (Range<RegionVid>, Vec<RegionVariableOrigin>),
 176     const_vars: (Range<ConstVid<'tcx>>, Vec<ConstVariableOrigin>),
 177 }
 178
 179 impl<'a, 'tcx> TypeFolder<'tcx> for InferenceFudger<'a, 'tcx> {
 180     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 181         self.infcx.tcx
 182     }
 183
 184     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 185         match *ty.kind() {
 186             ty::Infer(ty::InferTy::TyVar(vid)) => {
 187                 if self.type_vars.0.contains(&vid) {
 188                     // This variable was created during the fudging.
 189                     // Recreate it with a fresh variable here.
 190                     let idx = (vid.as_usize() - self.type_vars.0.start.as_usize()) as usize;
 191                     let origin = self.type_vars.1[idx];
 192                     self.infcx.next_ty_var(origin)
 193                 } else {
 194                     // This variable was created before the
 195                     // "fudging". Since we refresh all type
 196                     // variables to their binding anyhow, we know
 197                     // that it is unbound, so we can just return
 198                     // it.
 199                     debug_assert!(
 200                         self.infcx.inner.borrow_mut().type_variables().probe(vid).is_unknown()
 201                     );
 202                     ty
 203                 }
 204             }
 205             ty::Infer(ty::InferTy::IntVar(vid)) => {
 206                 if self.int_vars.contains(&vid) {
 207                     self.infcx.next_int_var()
 208                 } else {
 209                     ty
 210                 }
 211             }
 212             ty::Infer(ty::InferTy::FloatVar(vid)) => {
 213                 if self.float_vars.contains(&vid) {
 214                     self.infcx.next_float_var()
 215                 } else {
 216                     ty
 217                 }
 218             }
 219             _ => ty.super_fold_with(self),
 220         }
 221     }
 222
 223     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 224         if let ty::ReVar(vid) = *r {
 225             if self.region_vars.0.contains(&vid) {
 226                 let idx = vid.index() - self.region_vars.0.start.index();
 227                 let origin = self.region_vars.1[idx];
 228                 return self.infcx.next_region_var(origin);
 229             }
 230         }
 231         r
 232     }
 233
 234     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 235         if let ty::Const { val: ty::ConstKind::Infer(ty::InferConst::Var(vid)), ty } = ct {
 236             if self.const_vars.0.contains(&vid) {
 237                 // This variable was created during the fudging.
 238                 // Recreate it with a fresh variable here.
 239                 let idx = (vid.index - self.const_vars.0.start.index) as usize;
 240                 let origin = self.const_vars.1[idx];
 241                 self.infcx.next_const_var(ty, origin)
 242             } else {
 243                 ct
 244             }
 245         } else {
 246             ct.super_fold_with(self)
 247         }
 248     }
 249 }