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