src/librustc/middle/infer/type_variable.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 pub use self::RelationDir::*;
  12 use self::TypeVariableValue::*;
  13 use self::UndoEntry::*;
  14
  15 use middle::ty::{self, Ty};
  16 use std::cmp::min;
  17 use std::mem;
  18 use std::u32;
  19 use util::snapshot_vec as sv;
  20
  21 pub struct TypeVariableTable<'tcx> {
  22     values: sv::SnapshotVec<Delegate<'tcx>>,
  23 }
  24
  25 struct TypeVariableData<'tcx> {
  26     value: TypeVariableValue<'tcx>,
  27     diverging: bool
  28 }
  29
  30 enum TypeVariableValue<'tcx> {
  31     Known(Ty<'tcx>),
  32     Bounded(Vec<Relation>),
  33 }
  34
  35 pub struct Snapshot {
  36     snapshot: sv::Snapshot
  37 }
  38
  39 enum UndoEntry {
  40     // The type of the var was specified.
  41     SpecifyVar(ty::TyVid, Vec<Relation>),
  42     Relate(ty::TyVid, ty::TyVid),
  43 }
  44
  45 struct Delegate<'tcx>;
  46
  47 type Relation = (RelationDir, ty::TyVid);
  48
  49 #[derive(Copy, PartialEq, Debug)]
  50 pub enum RelationDir {
  51     SubtypeOf, SupertypeOf, EqTo
  52 }
  53
  54 impl RelationDir {
  55     fn opposite(self) -> RelationDir {
  56         match self {
  57             SubtypeOf => SupertypeOf,
  58             SupertypeOf => SubtypeOf,
  59             EqTo => EqTo
  60         }
  61     }
  62 }
  63
  64 impl<'tcx> TypeVariableTable<'tcx> {
  65     pub fn new() -> TypeVariableTable<'tcx> {
  66         TypeVariableTable { values: sv::SnapshotVec::new(Delegate) }
  67     }
  68
  69     fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
  70         relations(self.values.get_mut(a.index as uint))
  71     }
  72
  73     pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
  74         self.values.get(vid.index as uint).diverging
  75     }
  76
  77     /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
  78     ///
  79     /// Precondition: neither `a` nor `b` are known.
  80     pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) {
  81         if a != b {
  82             self.relations(a).push((dir, b));
  83             self.relations(b).push((dir.opposite(), a));
  84             self.values.record(Relate(a, b));
  85         }
  86     }
  87
  88     /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the
  89     /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)`
  90     /// where `vid1` is some other variable id.
  91     pub fn instantiate_and_push(
  92         &mut self,
  93         vid: ty::TyVid,
  94         ty: Ty<'tcx>,
  95         stack: &mut Vec<(Ty<'tcx>, RelationDir, ty::TyVid)>)
  96     {
  97         let old_value = {
  98             let value_ptr = &mut self.values.get_mut(vid.index as uint).value;
  99             mem::replace(value_ptr, Known(ty))
 100         };
 101
 102         let relations = match old_value {
 103             Bounded(b) => b,
 104             Known(_) => panic!("Asked to instantiate variable that is \
 105                                already instantiated")
 106         };
 107
 108         for &(dir, vid) in &relations {
 109             stack.push((ty, dir, vid));
 110         }
 111
 112         self.values.record(SpecifyVar(vid, relations));
 113     }
 114
 115     pub fn new_var(&mut self, diverging: bool) -> ty::TyVid {
 116         let index = self.values.push(TypeVariableData {
 117             value: Bounded(vec![]),
 118             diverging: diverging
 119         });
 120         ty::TyVid { index: index as u32 }
 121     }
 122
 123     pub fn probe(&self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
 124         match self.values.get(vid.index as uint).value {
 125             Bounded(..) => None,
 126             Known(t) => Some(t)
 127         }
 128     }
 129
 130     pub fn replace_if_possible(&self, t: Ty<'tcx>) -> Ty<'tcx> {
 131         match t.sty {
 132             ty::ty_infer(ty::TyVar(v)) => {
 133                 match self.probe(v) {
 134                     None => t,
 135                     Some(u) => u
 136                 }
 137             }
 138             _ => t,
 139         }
 140     }
 141
 142     pub fn snapshot(&mut self) -> Snapshot {
 143         Snapshot { snapshot: self.values.start_snapshot() }
 144     }
 145
 146     pub fn rollback_to(&mut self, s: Snapshot) {
 147         self.values.rollback_to(s.snapshot);
 148     }
 149
 150     pub fn commit(&mut self, s: Snapshot) {
 151         self.values.commit(s.snapshot);
 152     }
 153
 154     pub fn types_escaping_snapshot(&self, s: &Snapshot) -> Vec<Ty<'tcx>> {
 155         /*!
 156          * Find the set of type variables that existed *before* `s`
 157          * but which have only been unified since `s` started, and
 158          * return the types with which they were unified. So if we had
 159          * a type variable `V0`, then we started the snapshot, then we
 160          * created a type variable `V1`, unifed `V0` with `T0`, and
 161          * unified `V1` with `T1`, this function would return `{T0}`.
 162          */
 163
 164         let mut new_elem_threshold = u32::MAX;
 165         let mut escaping_types = Vec::new();
 166         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 167         debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
 168         for action in actions_since_snapshot {
 169             match *action {
 170                 sv::UndoLog::NewElem(index) => {
 171                     // if any new variables were created during the
 172                     // snapshot, remember the lower index (which will
 173                     // always be the first one we see). Note that this
 174                     // action must precede those variables being
 175                     // specified.
 176                     new_elem_threshold = min(new_elem_threshold, index as u32);
 177                     debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
 178                 }
 179
 180                 sv::UndoLog::Other(SpecifyVar(vid, _)) => {
 181                     if vid.index < new_elem_threshold {
 182                         // quick check to see if this variable was
 183                         // created since the snapshot started or not.
 184                         let escaping_type = self.probe(vid).unwrap();
 185                         escaping_types.push(escaping_type);
 186                     }
 187                     debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
 188                 }
 189
 190                 _ => { }
 191             }
 192         }
 193
 194         escaping_types
 195     }
 196 }
 197
 198 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
 199     type Value = TypeVariableData<'tcx>;
 200     type Undo = UndoEntry;
 201
 202     fn reverse(&mut self,
 203                values: &mut Vec<TypeVariableData<'tcx>>,
 204                action: UndoEntry) {
 205         match action {
 206             SpecifyVar(vid, relations) => {
 207                 values[vid.index as uint].value = Bounded(relations);
 208             }
 209
 210             Relate(a, b) => {
 211                 relations(&mut (*values)[a.index as uint]).pop();
 212                 relations(&mut (*values)[b.index as uint]).pop();
 213             }
 214         }
 215     }
 216 }
 217
 218 fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> {
 219     match v.value {
 220         Known(_) => panic!("var_sub_var: variable is known"),
 221         Bounded(ref mut relations) => relations
 222     }
 223 }