src/librustc/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 use hir::def_id::{DefId};
  15 use ty::{self, Ty};
  16 use syntax::codemap::Span;
  17
  18 use std::cmp::min;
  19 use std::marker::PhantomData;
  20 use std::mem;
  21 use std::u32;
  22 use rustc_data_structures::snapshot_vec as sv;
  23 use rustc_data_structures::unify as ut;
  24
  25 pub struct TypeVariableTable<'tcx> {
  26     values: sv::SnapshotVec<Delegate<'tcx>>,
  27     eq_relations: ut::UnificationTable<ty::TyVid>,
  28 }
  29
  30 struct TypeVariableData<'tcx> {
  31     value: TypeVariableValue<'tcx>,
  32     diverging: bool
  33 }
  34
  35 enum TypeVariableValue<'tcx> {
  36     Known(Ty<'tcx>),
  37     Bounded {
  38         relations: Vec<Relation>,
  39         default: Option<Default<'tcx>>
  40     }
  41 }
  42
  43 // We will use this to store the required information to recapitulate what happened when
  44 // an error occurs.
  45 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  46 pub struct Default<'tcx> {
  47     pub ty: Ty<'tcx>,
  48     /// The span where the default was incurred
  49     pub origin_span: Span,
  50     /// The definition that the default originates from
  51     pub def_id: DefId
  52 }
  53
  54 pub struct Snapshot {
  55     snapshot: sv::Snapshot,
  56     eq_snapshot: ut::Snapshot<ty::TyVid>,
  57 }
  58
  59 enum UndoEntry<'tcx> {
  60     // The type of the var was specified.
  61     SpecifyVar(ty::TyVid, Vec<Relation>, Option<Default<'tcx>>),
  62     Relate(ty::TyVid, ty::TyVid),
  63     RelateRange(ty::TyVid, usize),
  64 }
  65
  66 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
  67
  68 type Relation = (RelationDir, ty::TyVid);
  69
  70 #[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
  71 pub enum RelationDir {
  72     SubtypeOf, SupertypeOf, EqTo, BiTo
  73 }
  74
  75 impl RelationDir {
  76     fn opposite(self) -> RelationDir {
  77         match self {
  78             SubtypeOf => SupertypeOf,
  79             SupertypeOf => SubtypeOf,
  80             EqTo => EqTo,
  81             BiTo => BiTo,
  82         }
  83     }
  84 }
  85
  86 impl<'tcx> TypeVariableTable<'tcx> {
  87     pub fn new() -> TypeVariableTable<'tcx> {
  88         TypeVariableTable {
  89             values: sv::SnapshotVec::new(),
  90             eq_relations: ut::UnificationTable::new(),
  91         }
  92     }
  93
  94     fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
  95         relations(self.values.get_mut(a.index as usize))
  96     }
  97
  98     pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> {
  99         match &self.values.get(vid.index as usize).value {
 100             &Known(_) => None,
 101             &Bounded { ref default, .. } => default.clone()
 102         }
 103     }
 104
 105     pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
 106         self.values.get(vid.index as usize).diverging
 107     }
 108
 109     /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
 110     ///
 111     /// Precondition: neither `a` nor `b` are known.
 112     pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) {
 113         let a = self.root_var(a);
 114         let b = self.root_var(b);
 115         if a != b {
 116             if dir == EqTo {
 117                 // a and b must be equal which we mark in the unification table
 118                 let root = self.eq_relations.union(a, b);
 119                 // In addition to being equal, all relations from the variable which is no longer
 120                 // the root must be added to the root so they are not forgotten as the other
 121                 // variable should no longer be referenced (other than to get the root)
 122                 let other = if a == root { b } else { a };
 123                 let count = {
 124                     let (relations, root_relations) = if other.index < root.index {
 125                         let (pre, post) = self.values.split_at_mut(root.index as usize);
 126                         (relations(&mut pre[other.index as usize]), relations(&mut post[0]))
 127                     } else {
 128                         let (pre, post) = self.values.split_at_mut(other.index as usize);
 129                         (relations(&mut post[0]), relations(&mut pre[root.index as usize]))
 130                     };
 131                     root_relations.extend_from_slice(relations);
 132                     relations.len()
 133                 };
 134                 self.values.record(RelateRange(root, count));
 135             } else {
 136                 self.relations(a).push((dir, b));
 137                 self.relations(b).push((dir.opposite(), a));
 138                 self.values.record(Relate(a, b));
 139             }
 140         }
 141     }
 142
 143     /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the
 144     /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)`
 145     /// where `vid1` is some other variable id.
 146     ///
 147     /// Precondition: `vid` must be a root in the unification table
 148     pub fn instantiate_and_push(
 149         &mut self,
 150         vid: ty::TyVid,
 151         ty: Ty<'tcx>,
 152         stack: &mut Vec<(Ty<'tcx>, RelationDir, ty::TyVid)>)
 153     {
 154         debug_assert!(self.root_var(vid) == vid);
 155         let old_value = {
 156             let value_ptr = &mut self.values.get_mut(vid.index as usize).value;
 157             mem::replace(value_ptr, Known(ty))
 158         };
 159
 160         let (relations, default) = match old_value {
 161             Bounded { relations, default } => (relations, default),
 162             Known(_) => bug!("Asked to instantiate variable that is \
 163                               already instantiated")
 164         };
 165
 166         for &(dir, vid) in &relations {
 167             stack.push((ty, dir, vid));
 168         }
 169
 170         self.values.record(SpecifyVar(vid, relations, default));
 171     }
 172
 173     pub fn new_var(&mut self,
 174                    diverging: bool,
 175                    default: Option<Default<'tcx>>) -> ty::TyVid {
 176         self.eq_relations.new_key(());
 177         let index = self.values.push(TypeVariableData {
 178             value: Bounded { relations: vec![], default: default },
 179             diverging: diverging
 180         });
 181         ty::TyVid { index: index as u32 }
 182     }
 183
 184     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 185         self.eq_relations.find(vid)
 186     }
 187
 188     pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
 189         let vid = self.root_var(vid);
 190         self.probe_root(vid)
 191     }
 192
 193     /// Retrieves the type of `vid` given that it is currently a root in the unification table
 194     pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
 195         debug_assert!(self.root_var(vid) == vid);
 196         match self.values.get(vid.index as usize).value {
 197             Bounded { .. } => None,
 198             Known(t) => Some(t)
 199         }
 200     }
 201
 202     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 203         match t.sty {
 204             ty::TyInfer(ty::TyVar(v)) => {
 205                 match self.probe(v) {
 206                     None => t,
 207                     Some(u) => u
 208                 }
 209             }
 210             _ => t,
 211         }
 212     }
 213
 214     pub fn snapshot(&mut self) -> Snapshot {
 215         Snapshot {
 216             snapshot: self.values.start_snapshot(),
 217             eq_snapshot: self.eq_relations.snapshot(),
 218         }
 219     }
 220
 221     pub fn rollback_to(&mut self, s: Snapshot) {
 222         self.values.rollback_to(s.snapshot);
 223         self.eq_relations.rollback_to(s.eq_snapshot);
 224     }
 225
 226     pub fn commit(&mut self, s: Snapshot) {
 227         self.values.commit(s.snapshot);
 228         self.eq_relations.commit(s.eq_snapshot);
 229     }
 230
 231     pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
 232         /*!
 233          * Find the set of type variables that existed *before* `s`
 234          * but which have only been unified since `s` started, and
 235          * return the types with which they were unified. So if we had
 236          * a type variable `V0`, then we started the snapshot, then we
 237          * created a type variable `V1`, unifed `V0` with `T0`, and
 238          * unified `V1` with `T1`, this function would return `{T0}`.
 239          */
 240
 241         let mut new_elem_threshold = u32::MAX;
 242         let mut escaping_types = Vec::new();
 243         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 244         debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
 245         for action in actions_since_snapshot {
 246             match *action {
 247                 sv::UndoLog::NewElem(index) => {
 248                     // if any new variables were created during the
 249                     // snapshot, remember the lower index (which will
 250                     // always be the first one we see). Note that this
 251                     // action must precede those variables being
 252                     // specified.
 253                     new_elem_threshold = min(new_elem_threshold, index as u32);
 254                     debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
 255                 }
 256
 257                 sv::UndoLog::Other(SpecifyVar(vid, _, _)) => {
 258                     if vid.index < new_elem_threshold {
 259                         // quick check to see if this variable was
 260                         // created since the snapshot started or not.
 261                         let escaping_type = match self.values.get(vid.index as usize).value {
 262                             Bounded { .. } => bug!(),
 263                             Known(ty) => ty,
 264                         };
 265                         escaping_types.push(escaping_type);
 266                     }
 267                     debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
 268                 }
 269
 270                 _ => { }
 271             }
 272         }
 273
 274         escaping_types
 275     }
 276
 277     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
 278         (0..self.values.len())
 279             .filter_map(|i| {
 280                 let vid = ty::TyVid { index: i as u32 };
 281                 if self.probe(vid).is_some() {
 282                     None
 283                 } else {
 284                     Some(vid)
 285                 }
 286             })
 287             .collect()
 288     }
 289 }
 290
 291 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
 292     type Value = TypeVariableData<'tcx>;
 293     type Undo = UndoEntry<'tcx>;
 294
 295     fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: UndoEntry<'tcx>) {
 296         match action {
 297             SpecifyVar(vid, relations, default) => {
 298                 values[vid.index as usize].value = Bounded {
 299                     relations: relations,
 300                     default: default
 301                 };
 302             }
 303
 304             Relate(a, b) => {
 305                 relations(&mut (*values)[a.index as usize]).pop();
 306                 relations(&mut (*values)[b.index as usize]).pop();
 307             }
 308
 309             RelateRange(i, n) => {
 310                 let relations = relations(&mut (*values)[i.index as usize]);
 311                 for _ in 0..n {
 312                     relations.pop();
 313                 }
 314             }
 315         }
 316     }
 317 }
 318
 319 fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> {
 320     match v.value {
 321         Known(_) => bug!("var_sub_var: variable is known"),
 322         Bounded { ref mut relations, .. } => relations
 323     }
 324 }