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