src/librustc/infer/fudge.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use infer::type_variable::TypeVariableMap;
  12 use ty::{self, Ty, TyCtxt};
  13 use ty::fold::{TypeFoldable, TypeFolder};
  14
  15 use super::InferCtxt;
  16 use super::RegionVariableOrigin;
  17
  18 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
  19     /// This rather funky routine is used while processing expected
  20     /// types. What happens here is that we want to propagate a
  21     /// coercion through the return type of a fn to its
  22     /// argument. Consider the type of `Option::Some`, which is
  23     /// basically `for<T> fn(T) -> Option<T>`. So if we have an
  24     /// expression `Some(&[1, 2, 3])`, and that has the expected type
  25     /// `Option<&[u32]>`, we would like to type check `&[1, 2, 3]`
  26     /// with the expectation of `&[u32]`. This will cause us to coerce
  27     /// from `&[u32; 3]` to `&[u32]` and make the users life more
  28     /// pleasant.
  29     ///
  30     /// The way we do this is using `fudge_regions_if_ok`. What the
  31     /// routine actually does is to start a snapshot and execute the
  32     /// closure `f`. In our example above, what this closure will do
  33     /// is to unify the expectation (`Option<&[u32]>`) with the actual
  34     /// return type (`Option<?T>`, where `?T` represents the variable
  35     /// instantiated for `T`).  This will cause `?T` to be unified
  36     /// with `&?a [u32]`, where `?a` is a fresh lifetime variable. The
  37     /// input type (`?T`) is then returned by `f()`.
  38     ///
  39     /// At this point, `fudge_regions_if_ok` will normalize all type
  40     /// variables, converting `?T` to `&?a [u32]` and end the
  41     /// snapshot.  The problem is that we can't just return this type
  42     /// out, because it references the region variable `?a`, and that
  43     /// region variable was popped when we popped the snapshot.
  44     ///
  45     /// So what we do is to keep a list (`region_vars`, in the code below)
  46     /// of region variables created during the snapshot (here, `?a`). We
  47     /// fold the return value and replace any such regions with a *new*
  48     /// region variable (e.g., `?b`) and return the result (`&?b [u32]`).
  49     /// This can then be used as the expectation for the fn argument.
  50     ///
  51     /// The important point here is that, for soundness purposes, the
  52     /// regions in question are not particularly important. We will
  53     /// use the expected types to guide coercions, but we will still
  54     /// type-check the resulting types from those coercions against
  55     /// the actual types (`?T`, `Option<?T`) -- and remember that
  56     /// after the snapshot is popped, the variable `?T` is no longer
  57     /// unified.
  58     pub fn fudge_regions_if_ok<T, E, F>(&self,
  59                                         origin: &RegionVariableOrigin,
  60                                         f: F) -> Result<T, E> where
  61         F: FnOnce() -> Result<T, E>,
  62         T: TypeFoldable<'tcx>,
  63     {
  64         debug!("fudge_regions_if_ok(origin={:?})", origin);
  65
  66         let (type_variables, region_vars, value) = self.probe(|snapshot| {
  67             match f() {
  68                 Ok(value) => {
  69                     let value = self.resolve_type_vars_if_possible(&value);
  70
  71                     // At this point, `value` could in principle refer
  72                     // to types/regions that have been created during
  73                     // the snapshot. Once we exit `probe()`, those are
  74                     // going to be popped, so we will have to
  75                     // eliminate any references to them.
  76
  77                     let type_variables =
  78                         self.type_variables.borrow_mut().types_created_since_snapshot(
  79                             &snapshot.type_snapshot);
  80                     let region_vars =
  81                         self.borrow_region_constraints().vars_created_since_snapshot(
  82                             &snapshot.region_constraints_snapshot);
  83
  84                     Ok((type_variables, region_vars, value))
  85                 }
  86                 Err(e) => Err(e),
  87             }
  88         })?;
  89
  90         // At this point, we need to replace any of the now-popped
  91         // type/region variables that appear in `value` with a fresh
  92         // variable of the appropriate kind. We can't do this during
  93         // the probe because they would just get popped then too. =)
  94
  95         // Micro-optimization: if no variables have been created, then
  96         // `value` can't refer to any of them. =) So we can just return it.
  97         if type_variables.is_empty() && region_vars.is_empty() {
  98             return Ok(value);
  99         }
 100
 101         let mut fudger = RegionFudger {
 102             infcx: self,
 103             type_variables: &type_variables,
 104             region_vars: &region_vars,
 105             origin,
 106         };
 107
 108         Ok(value.fold_with(&mut fudger))
 109     }
 110 }
 111
 112 pub struct RegionFudger<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 113     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 114     type_variables: &'a TypeVariableMap,
 115     region_vars: &'a Vec<ty::RegionVid>,
 116     origin: &'a RegionVariableOrigin,
 117 }
 118
 119 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFudger<'a, 'gcx, 'tcx> {
 120     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 121         self.infcx.tcx
 122     }
 123
 124     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 125         match ty.sty {
 126             ty::TyInfer(ty::InferTy::TyVar(vid)) => {
 127                 match self.type_variables.get(&vid) {
 128                     None => {
 129                         // This variable was created before the
 130                         // "fudging".  Since we refresh all type
 131                         // variables to their binding anyhow, we know
 132                         // that it is unbound, so we can just return
 133                         // it.
 134                         debug_assert!(self.infcx.type_variables.borrow_mut()
 135                                       .probe(vid)
 136                                       .is_unknown());
 137                         ty
 138                     }
 139
 140                     Some(&origin) => {
 141                         // This variable was created during the
 142                         // fudging. Recreate it with a fresh variable
 143                         // here.
 144                         self.infcx.next_ty_var(origin)
 145                     }
 146                 }
 147             }
 148             _ => ty.super_fold_with(self),
 149         }
 150     }
 151
 152     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 153         match *r {
 154             ty::ReVar(v) if self.region_vars.contains(&v) => {
 155                 self.infcx.next_region_var(self.origin.clone())
 156             }
 157             _ => {
 158                 r
 159             }
 160         }
 161     }
 162 }