src/librustc/middle/typeck/infer/skolemize.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 /*!
  12  * Skolemization is the process of replacing unknown variables with
  13  * fresh types. The idea is that the type, after skolemization,
  14  * contains no inference variables but instead contains either a value
  15  * for each variable or fresh "arbitrary" types wherever a variable
  16  * would have been.
  17  *
  18  * Skolemization is used primarily to get a good type for inserting
  19  * into a cache. The result summarizes what the type inferencer knows
  20  * "so far". The primary place it is used right now is in the trait
  21  * matching algorithm, which needs to be able to cache whether an
  22  * `impl` self type matches some other type X -- *without* affecting
  23  * `X`. That means if that if the type `X` is in fact an unbound type
  24  * variable, we want the match to be regarded as ambiguous, because
  25  * depending on what type that type variable is ultimately assigned,
  26  * the match may or may not succeed.
  27  *
  28  * Note that you should be careful not to allow the output of
  29  * skolemization to leak to the user in error messages or in any other
  30  * form. Skolemization is only really useful as an internal detail.
  31  *
  32  * __An important detail concerning regions.__ The skolemizer also
  33  * replaces *all* regions with 'static. The reason behind this is
  34  * that, in general, we do not take region relationships into account
  35  * when making type-overloaded decisions. This is important because of
  36  * the design of the region inferencer, which is not based on
  37  * unification but rather on accumulating and then solving a set of
  38  * constraints. In contrast, the type inferencer assigns a value to
  39  * each type variable only once, and it does so as soon as it can, so
  40  * it is reasonable to ask what the type inferencer knows "so far".
  41  */
  42
  43 use middle::ty::{mod, Ty};
  44 use middle::ty_fold;
  45 use middle::ty_fold::TypeFoldable;
  46 use middle::ty_fold::TypeFolder;
  47 use std::collections::hash_map;
  48
  49 use super::InferCtxt;
  50 use super::unify::InferCtxtMethodsForSimplyUnifiableTypes;
  51
  52 pub struct TypeSkolemizer<'a, 'tcx:'a> {
  53     infcx: &'a InferCtxt<'a, 'tcx>,
  54     skolemization_count: uint,
  55     skolemization_map: hash_map::HashMap<ty::InferTy, Ty<'tcx>>,
  56 }
  57
  58 impl<'a, 'tcx> TypeSkolemizer<'a, 'tcx> {
  59     pub fn new<'tcx>(infcx: &'a InferCtxt<'a, 'tcx>) -> TypeSkolemizer<'a, 'tcx> {
  60         TypeSkolemizer {
  61             infcx: infcx,
  62             skolemization_count: 0,
  63             skolemization_map: hash_map::HashMap::new(),
  64         }
  65     }
  66
  67     fn skolemize(&mut self,
  68                  opt_ty: Option<Ty<'tcx>>,
  69                  key: ty::InferTy,
  70                  skolemizer: |uint| -> ty::InferTy)
  71                  -> Ty<'tcx>
  72     {
  73         match opt_ty {
  74             Some(ty) => { return ty.fold_with(self); }
  75             None => { }
  76         }
  77
  78         match self.skolemization_map.entry(key) {
  79             hash_map::Occupied(entry) => *entry.get(),
  80             hash_map::Vacant(entry) => {
  81                 let index = self.skolemization_count;
  82                 self.skolemization_count += 1;
  83                 let t = ty::mk_infer(self.infcx.tcx, skolemizer(index));
  84                 entry.set(t);
  85                 t
  86             }
  87         }
  88     }
  89 }
  90
  91 impl<'a, 'tcx> TypeFolder<'tcx> for TypeSkolemizer<'a, 'tcx> {
  92     fn tcx<'b>(&'b self) -> &'b ty::ctxt<'tcx> {
  93         self.infcx.tcx
  94     }
  95
  96     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
  97         match r {
  98             ty::ReEarlyBound(..) |
  99             ty::ReLateBound(..) => {
 100                 // leave bound regions alone
 101                 r
 102             }
 103
 104             ty::ReStatic |
 105             ty::ReFree(_) |
 106             ty::ReScope(_) |
 107             ty::ReInfer(_) |
 108             ty::ReEmpty => {
 109                 // replace all free regions with 'static
 110                 ty::ReStatic
 111             }
 112         }
 113     }
 114
 115     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 116         match t.sty {
 117             ty::ty_infer(ty::TyVar(v)) => {
 118                 self.skolemize(self.infcx.type_variables.borrow().probe(v),
 119                                ty::TyVar(v),
 120                                ty::SkolemizedTy)
 121             }
 122
 123             ty::ty_infer(ty::IntVar(v)) => {
 124                 self.skolemize(self.infcx.probe_var(v),
 125                                ty::IntVar(v),
 126                                ty::SkolemizedIntTy)
 127             }
 128
 129             ty::ty_infer(ty::FloatVar(v)) => {
 130                 self.skolemize(self.infcx.probe_var(v),
 131                                ty::FloatVar(v),
 132                                ty::SkolemizedIntTy)
 133             }
 134
 135             ty::ty_infer(ty::SkolemizedTy(c)) |
 136             ty::ty_infer(ty::SkolemizedIntTy(c)) => {
 137                 if c >= self.skolemization_count {
 138                     self.tcx().sess.bug(
 139                         format!("Encountered a skolemized type with id {} \
 140                                  but our counter is only at {}",
 141                                 c,
 142                                 self.skolemization_count).as_slice());
 143                 }
 144                 t
 145             }
 146
 147             ty::ty_open(..) => {
 148                 self.tcx().sess.bug("Cannot skolemize an open existential type");
 149             }
 150
 151             ty::ty_bool |
 152             ty::ty_char |
 153             ty::ty_int(..) |
 154             ty::ty_uint(..) |
 155             ty::ty_float(..) |
 156             ty::ty_enum(..) |
 157             ty::ty_uniq(..) |
 158             ty::ty_str |
 159             ty::ty_err |
 160             ty::ty_vec(..) |
 161             ty::ty_ptr(..) |
 162             ty::ty_rptr(..) |
 163             ty::ty_bare_fn(..) |
 164             ty::ty_closure(..) |
 165             ty::ty_trait(..) |
 166             ty::ty_struct(..) |
 167             ty::ty_unboxed_closure(..) |
 168             ty::ty_tup(..) |
 169             ty::ty_param(..) => {
 170                 ty_fold::super_fold_ty(self, t)
 171             }
 172         }
 173     }
 174 }