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 ty::{self, TyCtxt};
  12 use ty::fold::{TypeFoldable, TypeFolder};
  13
  14 use super::InferCtxt;
  15 use super::RegionVariableOrigin;
  16
  17 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
  18     /// This rather funky routine is used while processing expected
  19     /// types. What happens here is that we want to propagate a
  20     /// coercion through the return type of a fn to its
  21     /// argument. Consider the type of `Option::Some`, which is
  22     /// basically `for<T> fn(T) -> Option<T>`. So if we have an
  23     /// expression `Some(&[1, 2, 3])`, and that has the expected type
  24     /// `Option<&[u32]>`, we would like to type check `&[1, 2, 3]`
  25     /// with the expectation of `&[u32]`. This will cause us to coerce
  26     /// from `&[u32; 3]` to `&[u32]` and make the users life more
  27     /// pleasant.
  28     ///
  29     /// The way we do this is using `fudge_regions_if_ok`. What the
  30     /// routine actually does is to start a snapshot and execute the
  31     /// closure `f`. In our example above, what this closure will do
  32     /// is to unify the expectation (`Option<&[u32]>`) with the actual
  33     /// return type (`Option<?T>`, where `?T` represents the variable
  34     /// instantiated for `T`).  This will cause `?T` to be unified
  35     /// with `&?a [u32]`, where `?a` is a fresh lifetime variable. The
  36     /// input type (`?T`) is then returned by `f()`.
  37     ///
  38     /// At this point, `fudge_regions_if_ok` will normalize all type
  39     /// variables, converting `?T` to `&?a [u32]` and end the
  40     /// snapshot.  The problem is that we can't just return this type
  41     /// out, because it references the region variable `?a`, and that
  42     /// region variable was popped when we popped the snapshot.
  43     ///
  44     /// So what we do is to keep a list (`region_vars`, in the code below)
  45     /// of region variables created during the snapshot (here, `?a`). We
  46     /// fold the return value and replace any such regions with a *new*
  47     /// region variable (e.g., `?b`) and return the result (`&?b [u32]`).
  48     /// This can then be used as the expectation for the fn argument.
  49     ///
  50     /// The important point here is that, for soundness purposes, the
  51     /// regions in question are not particularly important. We will
  52     /// use the expected types to guide coercions, but we will still
  53     /// type-check the resulting types from those coercions against
  54     /// the actual types (`?T`, `Option<?T`) -- and remember that
  55     /// after the snapshot is popped, the variable `?T` is no longer
  56     /// unified.
  57     ///
  58     /// Assumptions:
  59     /// - no new type variables are created during `f()` (asserted
  60     ///   below); this simplifies our logic since we don't have to
  61     ///   check for escaping type variables
  62     pub fn fudge_regions_if_ok<T, E, F>(&self,
  63                                         origin: &RegionVariableOrigin,
  64                                         f: F) -> Result<T, E> where
  65         F: FnOnce() -> Result<T, E>,
  66         T: TypeFoldable<'tcx>,
  67     {
  68         let (region_vars, value) = self.probe(|snapshot| {
  69             let vars_at_start = self.type_variables.borrow().num_vars();
  70
  71             match f() {
  72                 Ok(value) => {
  73                     let value = self.resolve_type_vars_if_possible(&value);
  74
  75                     // At this point, `value` could in principle refer
  76                     // to regions that have been created during the
  77                     // snapshot (we assert below that `f()` does not
  78                     // create any new type variables, so there
  79                     // shouldn't be any of those). Once we exit
  80                     // `probe()`, those are going to be popped, so we
  81                     // will have to eliminate any references to them.
  82
  83                     assert_eq!(self.type_variables.borrow().num_vars(), vars_at_start,
  84                                "type variables were created during fudge_regions_if_ok");
  85                     let region_vars =
  86                         self.region_vars.vars_created_since_snapshot(
  87                             &snapshot.region_vars_snapshot);
  88
  89                     Ok((region_vars, value))
  90                 }
  91                 Err(e) => Err(e),
  92             }
  93         })?;
  94
  95         // At this point, we need to replace any of the now-popped
  96         // region variables that appear in `value` with a fresh region
  97         // variable. We can't do this during the probe because they
  98         // would just get popped then too. =)
  99
 100         // Micro-optimization: if no variables have been created, then
 101         // `value` can't refer to any of them. =) So we can just return it.
 102         if region_vars.is_empty() {
 103             return Ok(value);
 104         }
 105
 106         let mut fudger = RegionFudger {
 107             infcx: self,
 108             region_vars: &region_vars,
 109             origin: origin
 110         };
 111
 112         Ok(value.fold_with(&mut fudger))
 113     }
 114 }
 115
 116 pub struct RegionFudger<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 117     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 118     region_vars: &'a Vec<ty::RegionVid>,
 119     origin: &'a RegionVariableOrigin,
 120 }
 121
 122 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFudger<'a, 'gcx, 'tcx> {
 123     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 124         self.infcx.tcx
 125     }
 126
 127     fn fold_region(&mut self, r: &'tcx ty::Region) -> &'tcx ty::Region {
 128         match *r {
 129             ty::ReVar(v) if self.region_vars.contains(&v) => {
 130                 self.infcx.next_region_var(self.origin.clone())
 131             }
 132             _ => {
 133                 r
 134             }
 135         }
 136     }
 137 }