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