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