src/librustc/infer/freshen.rs

   1 // Copyright 2014 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 //! Freshening is the process of replacing unknown variables with fresh types. The idea is that
  12 //! the type, after freshening, contains no inference variables but instead contains either a
  13 //! value for each variable or fresh "arbitrary" types wherever a variable would have been.
  14 //!
  15 //! Freshening is used primarily to get a good type for inserting into a cache. The result
  16 //! summarizes what the type inferencer knows "so far". The primary place it is used right now is
  17 //! in the trait matching algorithm, which needs to be able to cache whether an `impl` self type
  18 //! matches some other type X -- *without* affecting `X`. That means if that if the type `X` is in
  19 //! fact an unbound type variable, we want the match to be regarded as ambiguous, because depending
  20 //! on what type that type variable is ultimately assigned, the match may or may not succeed.
  21 //!
  22 //! To handle closures, freshened types also have to contain the signature and kind of any
  23 //! closure in the local inference context, as otherwise the cache key might be invalidated.
  24 //! The way this is done is somewhat hacky - the closure signature is appended to the substs,
  25 //! as well as the closure kind "encoded" as a type. Also, special handling is needed when
  26 //! the closure signature contains a reference to the original closure.
  27 //!
  28 //! Note that you should be careful not to allow the output of freshening to leak to the user in
  29 //! error messages or in any other form. Freshening is only really useful as an internal detail.
  30 //!
  31 //! Because of the manipulation required to handle closures, doing arbitrary operations on
  32 //! freshened types is not recommended. However, in addition to doing equality/hash
  33 //! comparisons (for caching), it is possible to do a `ty::_match` operation between
  34 //! 2 freshened types - this works even with the closure encoding.
  35 //!
  36 //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with
  37 //! 'erased. The reason behind this is that, in general, we do not take region relationships into
  38 //! account when making type-overloaded decisions. This is important because of the design of the
  39 //! region inferencer, which is not based on unification but rather on accumulating and then
  40 //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type
  41 //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type
  42 //! inferencer knows "so far".
  43
  44 use ty::{self, Ty, TyCtxt, TypeFoldable};
  45 use ty::fold::TypeFolder;
  46 use ty::subst::Substs;
  47 use util::nodemap::FxHashMap;
  48 use hir::def_id::DefId;
  49
  50 use std::collections::hash_map::Entry;
  51
  52 use super::InferCtxt;
  53 use super::unify_key::ToType;
  54
  55 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  56     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
  57     freshen_count: u32,
  58     freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
  59     closure_set: Vec<DefId>,
  60 }
  61
  62 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
  63     pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
  64                -> TypeFreshener<'a, 'gcx, 'tcx> {
  65         TypeFreshener {
  66             infcx,
  67             freshen_count: 0,
  68             freshen_map: FxHashMap(),
  69             closure_set: vec![],
  70         }
  71     }
  72
  73     fn freshen<F>(&mut self,
  74                   opt_ty: Option<Ty<'tcx>>,
  75                   key: ty::InferTy,
  76                   freshener: F)
  77                   -> Ty<'tcx> where
  78         F: FnOnce(u32) -> ty::InferTy,
  79     {
  80         if let Some(ty) = opt_ty {
  81             return ty.fold_with(self);
  82         }
  83
  84         match self.freshen_map.entry(key) {
  85             Entry::Occupied(entry) => *entry.get(),
  86             Entry::Vacant(entry) => {
  87                 let index = self.freshen_count;
  88                 self.freshen_count += 1;
  89                 let t = self.infcx.tcx.mk_infer(freshener(index));
  90                 entry.insert(t);
  91                 t
  92             }
  93         }
  94     }
  95
  96     fn next_fresh<F>(&mut self,
  97                      freshener: F)
  98                      -> Ty<'tcx>
  99         where F: FnOnce(u32) -> ty::InferTy,
 100     {
 101         let index = self.freshen_count;
 102         self.freshen_count += 1;
 103         self.infcx.tcx.mk_infer(freshener(index))
 104     }
 105
 106     fn freshen_closure_like<M, C>(&mut self,
 107                                   def_id: DefId,
 108                                   substs: ty::ClosureSubsts<'tcx>,
 109                                   t: Ty<'tcx>,
 110                                   markers: M,
 111                                   combine: C)
 112                                   -> Ty<'tcx>
 113         where M: FnOnce(&mut Self) -> (Ty<'tcx>, Ty<'tcx>),
 114               C: FnOnce(&'tcx Substs<'tcx>) -> Ty<'tcx>
 115     {
 116         let tcx = self.infcx.tcx;
 117
 118         let closure_in_progress = self.infcx.in_progress_tables.map_or(false, |tables| {
 119             tcx.hir.as_local_node_id(def_id).map_or(false, |closure_id| {
 120                 tables.borrow().local_id_root ==
 121                     Some(DefId::local(tcx.hir.node_to_hir_id(closure_id).owner))
 122             })
 123         });
 124
 125         if !closure_in_progress {
 126             // If this closure belongs to another infcx, its kind etc. were
 127             // fully inferred and its signature/kind are exactly what's listed
 128             // in its infcx. So we don't need to add the markers for them.
 129             return t.super_fold_with(self);
 130         }
 131
 132         // We are encoding a closure in progress. Because we want our freshening
 133         // key to contain all inference information needed to make sense of our
 134         // value, we need to encode the closure signature and kind. The way
 135         // we do that is to add them as 2 variables to the closure substs,
 136         // basically because it's there (and nobody cares about adding extra stuff
 137         // to substs).
 138         //
 139         // This means the "freshened" closure substs ends up looking like
 140         //     fresh_substs = [PARENT_SUBSTS* ; UPVARS* ; SIG_MARKER ; KIND_MARKER]
 141         let (marker_1, marker_2) = if self.closure_set.contains(&def_id) {
 142             // We found the closure def-id within its own signature. Just
 143             // leave a new freshened type - any matching operations would
 144             // have found and compared the exterior closure already to
 145             // get here.
 146             //
 147             // In that case, we already know what the signature would
 148             // be - the parent closure on the stack already contains a
 149             // "copy" of the signature, so there is no reason to encode
 150             // it again for injectivity. Just use a fresh type variable
 151             // to make everything comparable.
 152             //
 153             // For example (closure kinds omitted for clarity)
 154             //     t=[closure FOO sig=[closure BAR sig=[closure FOO ..]]]
 155             // Would get encoded to
 156             //     t=[closure FOO sig=[closure BAR sig=[closure FOO sig=$0]]]
 157             //
 158             // and we can decode by having
 159             //     $0=[closure BAR {sig doesn't exist in decode}]
 160             // and get
 161             //     t=[closure FOO]
 162             //     sig[FOO] = [closure BAR]
 163             //     sig[BAR] = [closure FOO]
 164             (self.next_fresh(ty::FreshTy), self.next_fresh(ty::FreshTy))
 165         } else {
 166             self.closure_set.push(def_id);
 167             let markers = markers(self);
 168             self.closure_set.pop();
 169             markers
 170         };
 171
 172         combine(tcx.mk_substs(
 173             substs.substs.iter().map(|k| k.fold_with(self)).chain(
 174                 [marker_1, marker_2].iter().cloned().map(From::from)
 175                     )))
 176     }
 177 }
 178
 179 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
 180     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 181         self.infcx.tcx
 182     }
 183
 184     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 185         match *r {
 186             ty::ReLateBound(..) => {
 187                 // leave bound regions alone
 188                 r
 189             }
 190
 191             ty::ReStatic |
 192             ty::ReEarlyBound(..) |
 193             ty::ReFree(_) |
 194             ty::ReScope(_) |
 195             ty::ReVar(_) |
 196             ty::ReSkolemized(..) |
 197             ty::ReEmpty |
 198             ty::ReErased => {
 199                 // replace all free regions with 'erased
 200                 self.tcx().types.re_erased
 201             }
 202         }
 203     }
 204
 205     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 206         if !t.needs_infer() && !t.has_erasable_regions() &&
 207             !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) {
 208             return t;
 209         }
 210
 211         let tcx = self.infcx.tcx;
 212
 213         match t.sty {
 214             ty::TyInfer(ty::TyVar(v)) => {
 215                 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v);
 216                 self.freshen(
 217                     opt_ty,
 218                     ty::TyVar(v),
 219                     ty::FreshTy)
 220             }
 221
 222             ty::TyInfer(ty::IntVar(v)) => {
 223                 self.freshen(
 224                     self.infcx.int_unification_table.borrow_mut()
 225                                                     .probe(v)
 226                                                     .map(|v| v.to_type(tcx)),
 227                     ty::IntVar(v),
 228                     ty::FreshIntTy)
 229             }
 230
 231             ty::TyInfer(ty::FloatVar(v)) => {
 232                 self.freshen(
 233                     self.infcx.float_unification_table.borrow_mut()
 234                                                       .probe(v)
 235                                                       .map(|v| v.to_type(tcx)),
 236                     ty::FloatVar(v),
 237                     ty::FreshFloatTy)
 238             }
 239
 240             ty::TyInfer(ty::FreshTy(c)) |
 241             ty::TyInfer(ty::FreshIntTy(c)) |
 242             ty::TyInfer(ty::FreshFloatTy(c)) => {
 243                 if c >= self.freshen_count {
 244                     bug!("Encountered a freshend type with id {} \
 245                           but our counter is only at {}",
 246                          c,
 247                          self.freshen_count);
 248                 }
 249                 t
 250             }
 251
 252             ty::TyClosure(def_id, substs) => {
 253                 self.freshen_closure_like(
 254                     def_id, substs, t,
 255                     |this| {
 256                         // HACK: use a "random" integer type to mark the kind. Because
 257                         // different closure kinds shouldn't get unified during
 258                         // selection, the "subtyping" relationship (where any kind is
 259                         // better than no kind) shouldn't  matter here, just that the
 260                         // types are different.
 261                         let closure_kind = this.infcx.closure_kind(def_id);
 262                         let closure_kind_marker = match closure_kind {
 263                             None => tcx.types.i8,
 264                             Some(ty::ClosureKind::Fn) => tcx.types.i16,
 265                             Some(ty::ClosureKind::FnMut) => tcx.types.i32,
 266                             Some(ty::ClosureKind::FnOnce) => tcx.types.i64,
 267                         };
 268
 269                         let closure_sig = this.infcx.fn_sig(def_id);
 270                         (tcx.mk_fn_ptr(closure_sig.fold_with(this)),
 271                          closure_kind_marker)
 272                     },
 273                     |substs| tcx.mk_closure(def_id, substs)
 274                 )
 275             }
 276
 277             ty::TyGenerator(def_id, substs, interior) => {
 278                 self.freshen_closure_like(
 279                     def_id, substs, t,
 280                     |this| {
 281                         let gen_sig = this.infcx.generator_sig(def_id).unwrap();
 282                         // FIXME: want to revise this strategy when generator
 283                         // signatures can actually contain LBRs.
 284                         let sig = this.tcx().no_late_bound_regions(&gen_sig)
 285                             .unwrap_or_else(|| {
 286                                 bug!("late-bound regions in signature of {:?}",
 287                                      def_id)
 288                             });
 289                         (sig.yield_ty, sig.return_ty).fold_with(this)
 290                     },
 291                     |substs| {
 292                         tcx.mk_generator(def_id, ty::ClosureSubsts { substs }, interior)
 293                     }
 294                 )
 295             }
 296
 297             ty::TyBool |
 298             ty::TyChar |
 299             ty::TyInt(..) |
 300             ty::TyUint(..) |
 301             ty::TyFloat(..) |
 302             ty::TyAdt(..) |
 303             ty::TyStr |
 304             ty::TyError |
 305             ty::TyArray(..) |
 306             ty::TySlice(..) |
 307             ty::TyRawPtr(..) |
 308             ty::TyRef(..) |
 309             ty::TyFnDef(..) |
 310             ty::TyFnPtr(_) |
 311             ty::TyDynamic(..) |
 312             ty::TyNever |
 313             ty::TyTuple(..) |
 314             ty::TyProjection(..) |
 315             ty::TyForeign(..) |
 316             ty::TyParam(..) |
 317             ty::TyAnon(..) => {
 318                 t.super_fold_with(self)
 319             }
 320         }
 321     }
 322 }