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