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