src/librustc/infer/fudge.rs

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