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