src/librustc/infer/fudge.rs

   1 use crate::ty::{self, Ty, TyCtxt, TyVid, IntVid, FloatVid, RegionVid, ConstVid};
   2 use crate::ty::fold::{TypeFoldable, TypeFolder};
   3 use crate::mir::interpret::ConstValue;
   4
   5 use super::InferCtxt;
   6 use super::{RegionVariableOrigin, ConstVariableOrigin};
   7 use super::type_variable::TypeVariableOrigin;
   8
   9 use rustc_data_structures::unify as ut;
  10 use ut::UnifyKey;
  11
  12 use std::cell::RefMut;
  13 use std::ops::Range;
  14
  15 fn const_vars_since_snapshot<'tcx>(
  16     mut table: RefMut<'_, ut::UnificationTable<ut::InPlace<ConstVid<'tcx>>>>,
  17     snapshot: &ut::Snapshot<ut::InPlace<ConstVid<'tcx>>>,
  18 ) -> (Range<ConstVid<'tcx>>, Vec<ConstVariableOrigin>) {
  19     let range = table.vars_since_snapshot(snapshot);
  20     (range.start..range.end, (range.start.index..range.end.index).map(|index| {
  21         table.probe_value(ConstVid::from_index(index)).origin.clone()
  22     }).collect())
  23 }
  24
  25 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
  26     /// This rather funky routine is used while processing expected
  27     /// types. What happens here is that we want to propagate a
  28     /// coercion through the return type of a fn to its
  29     /// argument. Consider the type of `Option::Some`, which is
  30     /// basically `for<T> fn(T) -> Option<T>`. So if we have an
  31     /// expression `Some(&[1, 2, 3])`, and that has the expected type
  32     /// `Option<&[u32]>`, we would like to type check `&[1, 2, 3]`
  33     /// with the expectation of `&[u32]`. This will cause us to coerce
  34     /// from `&[u32; 3]` to `&[u32]` and make the users life more
  35     /// pleasant.
  36     ///
  37     /// The way we do this is using `fudge_inference_if_ok`. What the
  38     /// routine actually does is to start a snapshot and execute the
  39     /// closure `f`. In our example above, what this closure will do
  40     /// is to unify the expectation (`Option<&[u32]>`) with the actual
  41     /// return type (`Option<?T>`, where `?T` represents the variable
  42     /// instantiated for `T`). This will cause `?T` to be unified
  43     /// with `&?a [u32]`, where `?a` is a fresh lifetime variable. The
  44     /// input type (`?T`) is then returned by `f()`.
  45     ///
  46     /// At this point, `fudge_inference_if_ok` will normalize all type
  47     /// variables, converting `?T` to `&?a [u32]` and end the
  48     /// snapshot. The problem is that we can't just return this type
  49     /// out, because it references the region variable `?a`, and that
  50     /// region variable was popped when we popped the snapshot.
  51     ///
  52     /// So what we do is to keep a list (`region_vars`, in the code below)
  53     /// of region variables created during the snapshot (here, `?a`). We
  54     /// fold the return value and replace any such regions with a *new*
  55     /// region variable (e.g., `?b`) and return the result (`&?b [u32]`).
  56     /// This can then be used as the expectation for the fn argument.
  57     ///
  58     /// The important point here is that, for soundness purposes, the
  59     /// regions in question are not particularly important. We will
  60     /// use the expected types to guide coercions, but we will still
  61     /// type-check the resulting types from those coercions against
  62     /// the actual types (`?T`, `Option<?T>`) -- and remember that
  63     /// after the snapshot is popped, the variable `?T` is no longer
  64     /// unified.
  65     pub fn fudge_inference_if_ok<T, E, F>(
  66         &self,
  67         f: F,
  68     ) -> Result<T, E> where
  69         F: FnOnce() -> Result<T, E>,
  70         T: TypeFoldable<'tcx>,
  71     {
  72         debug!("fudge_inference_if_ok()");
  73
  74         let (mut fudger, value) = self.probe(|snapshot| {
  75             match f() {
  76                 Ok(value) => {
  77                     let value = self.resolve_vars_if_possible(&value);
  78
  79                     // At this point, `value` could in principle refer
  80                     // to inference variables that have been created during
  81                     // the snapshot. Once we exit `probe()`, those are
  82                     // going to be popped, so we will have to
  83                     // eliminate any references to them.
  84
  85                     let type_vars = self.type_variables.borrow_mut().vars_since_snapshot(
  86                         &snapshot.type_snapshot,
  87                     );
  88                     let int_vars = self.int_unification_table.borrow_mut().vars_since_snapshot(
  89                         &snapshot.int_snapshot,
  90                     );
  91                     let float_vars = self.float_unification_table.borrow_mut().vars_since_snapshot(
  92                         &snapshot.float_snapshot,
  93                     );
  94                     let region_vars = self.borrow_region_constraints().vars_since_snapshot(
  95                         &snapshot.region_constraints_snapshot,
  96                     );
  97                     let const_vars = const_vars_since_snapshot(
  98                         self.const_unification_table.borrow_mut(),
  99                         &snapshot.const_snapshot,
 100                     );
 101
 102                     let fudger = InferenceFudger {
 103                         infcx: self,
 104                         type_vars,
 105                         int_vars,
 106                         float_vars,
 107                         region_vars,
 108                         const_vars,
 109                     };
 110
 111                     Ok((fudger, value))
 112                 }
 113                 Err(e) => Err(e),
 114             }
 115         })?;
 116
 117         // At this point, we need to replace any of the now-popped
 118         // type/region variables that appear in `value` with a fresh
 119         // variable of the appropriate kind. We can't do this during
 120         // the probe because they would just get popped then too. =)
 121
 122         // Micro-optimization: if no variables have been created, then
 123         // `value` can't refer to any of them. =) So we can just return it.
 124         if fudger.type_vars.0.is_empty() &&
 125             fudger.int_vars.is_empty() &&
 126             fudger.float_vars.is_empty() &&
 127             fudger.region_vars.0.is_empty() &&
 128             fudger.const_vars.0.is_empty() {
 129             Ok(value)
 130         } else {
 131             Ok(value.fold_with(&mut fudger))
 132         }
 133     }
 134 }
 135
 136 pub struct InferenceFudger<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 137     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 138     type_vars: (Range<TyVid>, Vec<TypeVariableOrigin>),
 139     int_vars: Range<IntVid>,
 140     float_vars: Range<FloatVid>,
 141     region_vars: (Range<RegionVid>, Vec<RegionVariableOrigin>),
 142     const_vars: (Range<ConstVid<'tcx>>, Vec<ConstVariableOrigin>),
 143 }
 144
 145 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for InferenceFudger<'a, 'gcx, 'tcx> {
 146     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 147         self.infcx.tcx
 148     }
 149
 150     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 151         match ty.sty {
 152             ty::Infer(ty::InferTy::TyVar(vid)) => {
 153                 if self.type_vars.0.contains(&vid) {
 154                     // This variable was created during the fudging.
 155                     // Recreate it with a fresh variable here.
 156                     let idx = (vid.index - self.type_vars.0.start.index) as usize;
 157                     let origin = self.type_vars.1[idx];
 158                     self.infcx.next_ty_var(origin)
 159                 } else {
 160                     // This variable was created before the
 161                     // "fudging". Since we refresh all type
 162                     // variables to their binding anyhow, we know
 163                     // that it is unbound, so we can just return
 164                     // it.
 165                     debug_assert!(self.infcx.type_variables.borrow_mut()
 166                                   .probe(vid)
 167                                   .is_unknown());
 168                     ty
 169                 }
 170             }
 171             ty::Infer(ty::InferTy::IntVar(vid)) => {
 172                 if self.int_vars.contains(&vid) {
 173                     self.infcx.next_int_var()
 174                 } else {
 175                     ty
 176                 }
 177             }
 178             ty::Infer(ty::InferTy::FloatVar(vid)) => {
 179                 if self.float_vars.contains(&vid) {
 180                     self.infcx.next_float_var()
 181                 } else {
 182                     ty
 183                 }
 184             }
 185             _ => ty.super_fold_with(self),
 186         }
 187     }
 188
 189     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 190         if let ty::ReVar(vid) = *r {
 191             if self.region_vars.0.contains(&vid) {
 192                 let idx = vid.index() - self.region_vars.0.start.index();
 193                 let origin = self.region_vars.1[idx];
 194                 return self.infcx.next_region_var(origin);
 195             }
 196         }
 197         r
 198     }
 199
 200     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 201         if let ty::Const { val: ConstValue::Infer(ty::InferConst::Var(vid)), ty } = ct {
 202             if self.const_vars.0.contains(&vid) {
 203                 // This variable was created during the fudging.
 204                 // Recreate it with a fresh variable here.
 205                 let idx = (vid.index - self.const_vars.0.start.index) as usize;
 206                 let origin = self.const_vars.1[idx];
 207                 self.infcx.next_const_var(ty, origin)
 208             } else {
 209                 ct
 210             }
 211         } else {
 212             ct.super_fold_with(self)
 213         }
 214     }
 215 }