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::fx::FxHashMap;
  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
  28     /// Two variables are unified in `eq_relations` when we have a
  29     /// constraint `?X == ?Y`.
  30     eq_relations: ut::UnificationTable<ty::TyVid>,
  31
  32     /// Two variables are unified in `eq_relations` when we have a
  33     /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
  34     /// table exists only to help with the occurs check. In particular,
  35     /// we want to report constraints like these as an occurs check
  36     /// violation:
  37     ///
  38     ///     ?1 <: ?3
  39     ///     Box<?3> <: ?1
  40     ///
  41     /// This works because `?1` and `?3` are unified in the
  42     /// `sub_relations` relation (not in `eq_relations`). Then when we
  43     /// process the `Box<?3> <: ?1` constraint, we do an occurs check
  44     /// on `Box<?3>` and find a potential cycle.
  45     ///
  46     /// This is reasonable because, in Rust, subtypes have the same
  47     /// "skeleton" and hence there is no possible type such that
  48     /// (e.g.)  `Box<?3> <: ?3` for any `?3`.
  49     sub_relations: ut::UnificationTable<ty::TyVid>,
  50 }
  51
  52 /// Reasons to create a type inference variable
  53 #[derive(Copy, Clone, Debug)]
  54 pub enum TypeVariableOrigin {
  55     MiscVariable(Span),
  56     NormalizeProjectionType(Span),
  57     TypeInference(Span),
  58     TypeParameterDefinition(Span, ast::Name),
  59     TransformedUpvar(Span),
  60     SubstitutionPlaceholder(Span),
  61     AutoDeref(Span),
  62     AdjustmentType(Span),
  63     DivergingStmt(Span),
  64     DivergingBlockExpr(Span),
  65     DivergingFn(Span),
  66     LatticeVariable(Span),
  67     Generalized(ty::TyVid),
  68 }
  69
  70 pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
  71
  72 struct TypeVariableData<'tcx> {
  73     value: TypeVariableValue<'tcx>,
  74     origin: TypeVariableOrigin,
  75     diverging: bool
  76 }
  77
  78 enum TypeVariableValue<'tcx> {
  79     Known(Ty<'tcx>),
  80     Bounded {
  81         default: Option<Default<'tcx>>
  82     }
  83 }
  84
  85 // We will use this to store the required information to recapitulate what happened when
  86 // an error occurs.
  87 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  88 pub struct Default<'tcx> {
  89     pub ty: Ty<'tcx>,
  90     /// The span where the default was incurred
  91     pub origin_span: Span,
  92     /// The definition that the default originates from
  93     pub def_id: DefId
  94 }
  95
  96 pub struct Snapshot {
  97     snapshot: sv::Snapshot,
  98     eq_snapshot: ut::Snapshot<ty::TyVid>,
  99     sub_snapshot: ut::Snapshot<ty::TyVid>,
 100 }
 101
 102 struct Instantiate<'tcx> {
 103     vid: ty::TyVid,
 104     default: Option<Default<'tcx>>,
 105 }
 106
 107 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
 108
 109 impl<'tcx> TypeVariableTable<'tcx> {
 110     pub fn new() -> TypeVariableTable<'tcx> {
 111         TypeVariableTable {
 112             values: sv::SnapshotVec::new(),
 113             eq_relations: ut::UnificationTable::new(),
 114             sub_relations: ut::UnificationTable::new(),
 115         }
 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`, depending on `dir`.
 134     ///
 135     /// Precondition: neither `a` nor `b` are known.
 136     pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
 137         debug_assert!(self.probe(a).is_none());
 138         debug_assert!(self.probe(b).is_none());
 139         self.eq_relations.union(a, b);
 140         self.sub_relations.union(a, b);
 141     }
 142
 143     /// Records that `a <: b`, depending on `dir`.
 144     ///
 145     /// Precondition: neither `a` nor `b` are known.
 146     pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
 147         debug_assert!(self.probe(a).is_none());
 148         debug_assert!(self.probe(b).is_none());
 149         self.sub_relations.union(a, b);
 150     }
 151
 152     /// Instantiates `vid` with the type `ty`.
 153     ///
 154     /// Precondition: `vid` must not have been previously instantiated.
 155     pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
 156         let vid = self.root_var(vid);
 157         debug_assert!(self.probe_root(vid).is_none());
 158
 159         let old_value = {
 160             let vid_data = &mut self.values[vid.index as usize];
 161             mem::replace(&mut vid_data.value, TypeVariableValue::Known(ty))
 162         };
 163
 164         match old_value {
 165             TypeVariableValue::Bounded { default } => {
 166                 self.values.record(Instantiate { vid: vid, default: default });
 167             }
 168             TypeVariableValue::Known(old_ty) => {
 169                 bug!("instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
 170                      vid, ty, old_ty)
 171             }
 172         }
 173     }
 174
 175     pub fn new_var(&mut self,
 176                    diverging: bool,
 177                    origin: TypeVariableOrigin,
 178                    default: Option<Default<'tcx>>,) -> ty::TyVid {
 179         debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
 180         self.eq_relations.new_key(());
 181         self.sub_relations.new_key(());
 182         let index = self.values.push(TypeVariableData {
 183             value: Bounded { default: default },
 184             origin: origin,
 185             diverging: diverging
 186         });
 187         let v = ty::TyVid { index: index as u32 };
 188         debug!("new_var: diverging={:?} index={:?}", diverging, v);
 189         v
 190     }
 191
 192     pub fn num_vars(&self) -> usize {
 193         self.values.len()
 194     }
 195
 196     /// Returns the "root" variable of `vid` in the `eq_relations`
 197     /// equivalence table. All type variables that have been equated
 198     /// will yield the same root variable (per the union-find
 199     /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
 200     /// b` (transitively).
 201     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 202         self.eq_relations.find(vid)
 203     }
 204
 205     /// Returns the "root" variable of `vid` in the `sub_relations`
 206     /// equivalence table. All type variables that have been are
 207     /// related via equality or subtyping will yield the same root
 208     /// variable (per the union-find algorithm), so `sub_root_var(a)
 209     /// == sub_root_var(b)` implies that:
 210     ///
 211     ///     exists X. (a <: X || X <: a) && (b <: X || X <: b)
 212     pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 213         self.sub_relations.find(vid)
 214     }
 215
 216     /// True if `a` and `b` have same "sub-root" (i.e., exists some
 217     /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
 218     pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
 219         self.sub_root_var(a) == self.sub_root_var(b)
 220     }
 221
 222     pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
 223         let vid = self.root_var(vid);
 224         self.probe_root(vid)
 225     }
 226
 227     pub fn origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
 228         self.values.get(vid.index as usize).origin.clone()
 229     }
 230
 231     /// Retrieves the type of `vid` given that it is currently a root in the unification table
 232     pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
 233         debug_assert!(self.root_var(vid) == vid);
 234         match self.values.get(vid.index as usize).value {
 235             Bounded { .. } => None,
 236             Known(t) => Some(t)
 237         }
 238     }
 239
 240     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 241         match t.sty {
 242             ty::TyInfer(ty::TyVar(v)) => {
 243                 match self.probe(v) {
 244                     None => t,
 245                     Some(u) => u
 246                 }
 247             }
 248             _ => t,
 249         }
 250     }
 251
 252     pub fn snapshot(&mut self) -> Snapshot {
 253         Snapshot {
 254             snapshot: self.values.start_snapshot(),
 255             eq_snapshot: self.eq_relations.snapshot(),
 256             sub_snapshot: self.sub_relations.snapshot(),
 257         }
 258     }
 259
 260     pub fn rollback_to(&mut self, s: Snapshot) {
 261         debug!("rollback_to{:?}", {
 262             for action in self.values.actions_since_snapshot(&s.snapshot) {
 263                 match *action {
 264                     sv::UndoLog::NewElem(index) => {
 265                         debug!("inference variable _#{}t popped", index)
 266                     }
 267                     _ => { }
 268                 }
 269             }
 270         });
 271
 272         let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
 273         self.values.rollback_to(snapshot);
 274         self.eq_relations.rollback_to(eq_snapshot);
 275         self.sub_relations.rollback_to(sub_snapshot);
 276     }
 277
 278     pub fn commit(&mut self, s: Snapshot) {
 279         let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
 280         self.values.commit(snapshot);
 281         self.eq_relations.commit(eq_snapshot);
 282         self.sub_relations.commit(sub_snapshot);
 283     }
 284
 285     /// Returns a map `{V1 -> V2}`, where the keys `{V1}` are
 286     /// ty-variables created during the snapshot, and the values
 287     /// `{V2}` are the root variables that they were unified with,
 288     /// along with their origin.
 289     pub fn types_created_since_snapshot(&mut self, s: &Snapshot) -> TypeVariableMap {
 290         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 291
 292         actions_since_snapshot
 293             .iter()
 294             .filter_map(|action| match action {
 295                 &sv::UndoLog::NewElem(index) => Some(ty::TyVid { index: index as u32 }),
 296                 _ => None,
 297             })
 298             .map(|vid| {
 299                 let origin = self.values.get(vid.index as usize).origin.clone();
 300                 (vid, origin)
 301             })
 302             .collect()
 303     }
 304
 305     pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
 306         /*!
 307          * Find the set of type variables that existed *before* `s`
 308          * but which have only been unified since `s` started, and
 309          * return the types with which they were unified. So if we had
 310          * a type variable `V0`, then we started the snapshot, then we
 311          * created a type variable `V1`, unifed `V0` with `T0`, and
 312          * unified `V1` with `T1`, this function would return `{T0}`.
 313          */
 314
 315         let mut new_elem_threshold = u32::MAX;
 316         let mut escaping_types = Vec::new();
 317         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 318         debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
 319         for action in actions_since_snapshot {
 320             match *action {
 321                 sv::UndoLog::NewElem(index) => {
 322                     // if any new variables were created during the
 323                     // snapshot, remember the lower index (which will
 324                     // always be the first one we see). Note that this
 325                     // action must precede those variables being
 326                     // specified.
 327                     new_elem_threshold = min(new_elem_threshold, index as u32);
 328                     debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
 329                 }
 330
 331                 sv::UndoLog::Other(Instantiate { vid, .. }) => {
 332                     if vid.index < new_elem_threshold {
 333                         // quick check to see if this variable was
 334                         // created since the snapshot started or not.
 335                         let escaping_type = match self.values.get(vid.index as usize).value {
 336                             Bounded { .. } => bug!(),
 337                             Known(ty) => ty,
 338                         };
 339                         escaping_types.push(escaping_type);
 340                     }
 341                     debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
 342                 }
 343
 344                 _ => { }
 345             }
 346         }
 347
 348         escaping_types
 349     }
 350
 351     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
 352         (0..self.values.len())
 353             .filter_map(|i| {
 354                 let vid = ty::TyVid { index: i as u32 };
 355                 if self.probe(vid).is_some() {
 356                     None
 357                 } else {
 358                     Some(vid)
 359                 }
 360             })
 361             .collect()
 362     }
 363 }
 364
 365 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
 366     type Value = TypeVariableData<'tcx>;
 367     type Undo = Instantiate<'tcx>;
 368
 369     fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: Instantiate<'tcx>) {
 370         let Instantiate { vid, default } = action;
 371         values[vid.index as usize].value = Bounded {
 372             default: default
 373         };
 374     }
 375 }