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