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 syntax::symbol::InternedString;
  12 use syntax_pos::Span;
  13 use ty::{self, Ty};
  14
  15 use std::cmp;
  16 use std::marker::PhantomData;
  17 use std::u32;
  18 use rustc_data_structures::fx::FxHashMap;
  19 use rustc_data_structures::snapshot_vec as sv;
  20 use rustc_data_structures::unify as ut;
  21
  22 pub struct TypeVariableTable<'tcx> {
  23     values: sv::SnapshotVec<Delegate>,
  24
  25     /// Two variables are unified in `eq_relations` when we have a
  26     /// constraint `?X == ?Y`. This table also stores, for each key,
  27     /// the known value.
  28     eq_relations: ut::UnificationTable<ut::InPlace<TyVidEqKey<'tcx>>>,
  29
  30     /// Two variables are unified in `eq_relations` when we have a
  31     /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
  32     /// table exists only to help with the occurs check. In particular,
  33     /// we want to report constraints like these as an occurs check
  34     /// violation:
  35     ///
  36     ///     ?1 <: ?3
  37     ///     Box<?3> <: ?1
  38     ///
  39     /// This works because `?1` and `?3` are unified in the
  40     /// `sub_relations` relation (not in `eq_relations`). Then when we
  41     /// process the `Box<?3> <: ?1` constraint, we do an occurs check
  42     /// on `Box<?3>` and find a potential cycle.
  43     ///
  44     /// This is reasonable because, in Rust, subtypes have the same
  45     /// "skeleton" and hence there is no possible type such that
  46     /// (e.g.)  `Box<?3> <: ?3` for any `?3`.
  47     sub_relations: ut::UnificationTable<ut::InPlace<ty::TyVid>>,
  48 }
  49
  50 /// Reasons to create a type inference variable
  51 #[derive(Copy, Clone, Debug)]
  52 pub enum TypeVariableOrigin {
  53     MiscVariable(Span),
  54     NormalizeProjectionType(Span),
  55     TypeInference(Span),
  56     TypeParameterDefinition(Span, InternedString),
  57
  58     /// one of the upvars or closure kind parameters in a `ClosureSubsts`
  59     /// (before it has been determined)
  60     ClosureSynthetic(Span),
  61     SubstitutionPlaceholder(Span),
  62     AutoDeref(Span),
  63     AdjustmentType(Span),
  64     DivergingStmt(Span),
  65     DivergingBlockExpr(Span),
  66     DivergingFn(Span),
  67     LatticeVariable(Span),
  68     Generalized(ty::TyVid),
  69 }
  70
  71 pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
  72
  73 struct TypeVariableData {
  74     origin: TypeVariableOrigin,
  75     diverging: bool,
  76 }
  77
  78 #[derive(Copy, Clone, Debug)]
  79 pub enum TypeVariableValue<'tcx> {
  80     Known { value: Ty<'tcx> },
  81     Unknown { universe: ty::UniverseIndex },
  82 }
  83
  84 impl<'tcx> TypeVariableValue<'tcx> {
  85     /// If this value is known, returns the type it is known to be.
  86     /// Otherwise, `None`.
  87     pub fn known(&self) -> Option<Ty<'tcx>> {
  88         match *self {
  89             TypeVariableValue::Unknown { .. } => None,
  90             TypeVariableValue::Known { value } => Some(value),
  91         }
  92     }
  93
  94     pub fn is_unknown(&self) -> bool {
  95         match *self {
  96             TypeVariableValue::Unknown { .. } => true,
  97             TypeVariableValue::Known { .. } => false,
  98         }
  99     }
 100 }
 101
 102 pub struct Snapshot<'tcx> {
 103     snapshot: sv::Snapshot,
 104     eq_snapshot: ut::Snapshot<ut::InPlace<TyVidEqKey<'tcx>>>,
 105     sub_snapshot: ut::Snapshot<ut::InPlace<ty::TyVid>>,
 106 }
 107
 108 struct Instantiate {
 109     vid: ty::TyVid,
 110 }
 111
 112 struct Delegate;
 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     /// Returns the diverges flag given when `vid` was created.
 124     ///
 125     /// Note that this function does not return care whether
 126     /// `vid` has been unified with something else or not.
 127     pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
 128         self.values.get(vid.index as usize).diverging
 129     }
 130
 131     /// Returns the origin that was given when `vid` was created.
 132     ///
 133     /// Note that this function does not return care whether
 134     /// `vid` has been unified with something else or not.
 135     pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
 136         &self.values.get(vid.index as usize).origin
 137     }
 138
 139     /// Records that `a == b`, depending on `dir`.
 140     ///
 141     /// Precondition: neither `a` nor `b` are known.
 142     pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
 143         debug_assert!(self.probe(a).is_unknown());
 144         debug_assert!(self.probe(b).is_unknown());
 145         self.eq_relations.union(a, b);
 146         self.sub_relations.union(a, b);
 147     }
 148
 149     /// Records that `a <: b`, depending on `dir`.
 150     ///
 151     /// Precondition: neither `a` nor `b` are known.
 152     pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
 153         debug_assert!(self.probe(a).is_unknown());
 154         debug_assert!(self.probe(b).is_unknown());
 155         self.sub_relations.union(a, b);
 156     }
 157
 158     /// Instantiates `vid` with the type `ty`.
 159     ///
 160     /// Precondition: `vid` must not have been previously instantiated.
 161     pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
 162         let vid = self.root_var(vid);
 163         debug_assert!(self.probe(vid).is_unknown());
 164         debug_assert!(self.eq_relations.probe_value(vid).is_unknown(),
 165                       "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
 166                       vid, ty, self.eq_relations.probe_value(vid));
 167         self.eq_relations.union_value(vid, TypeVariableValue::Known { value: ty });
 168
 169         // Hack: we only need this so that `types_escaping_snapshot`
 170         // can see what has been unified; see the Delegate impl for
 171         // more details.
 172         self.values.record(Instantiate { vid });
 173     }
 174
 175     /// Creates a new type variable.
 176     ///
 177     /// - `diverging`: indicates if this is a "diverging" type
 178     ///   variable, e.g.,  one created as the type of a `return`
 179     ///   expression. The code in this module doesn't care if a
 180     ///   variable is diverging, but the main Rust type-checker will
 181     ///   sometimes "unify" such variables with the `!` or `()` types.
 182     /// - `origin`: indicates *why* the type variable was created.
 183     ///   The code in this module doesn't care, but it can be useful
 184     ///   for improving error messages.
 185     pub fn new_var(&mut self,
 186                    universe: ty::UniverseIndex,
 187                    diverging: bool,
 188                    origin: TypeVariableOrigin)
 189                    -> ty::TyVid {
 190         let eq_key = self.eq_relations.new_key(TypeVariableValue::Unknown { universe });
 191
 192         let sub_key = self.sub_relations.new_key(());
 193         assert_eq!(eq_key.vid, sub_key);
 194
 195         let index = self.values.push(TypeVariableData {
 196             origin,
 197             diverging,
 198         });
 199         assert_eq!(eq_key.vid.index, index as u32);
 200
 201         debug!("new_var(index={:?}, diverging={:?}, origin={:?}", eq_key.vid, diverging, origin);
 202
 203         eq_key.vid
 204     }
 205
 206     /// Returns the number of type variables created thus far.
 207     pub fn num_vars(&self) -> usize {
 208         self.values.len()
 209     }
 210
 211     /// Returns the "root" variable of `vid` in the `eq_relations`
 212     /// equivalence table. All type variables that have been equated
 213     /// will yield the same root variable (per the union-find
 214     /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
 215     /// b` (transitively).
 216     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 217         self.eq_relations.find(vid).vid
 218     }
 219
 220     /// Returns the "root" variable of `vid` in the `sub_relations`
 221     /// equivalence table. All type variables that have been are
 222     /// related via equality or subtyping will yield the same root
 223     /// variable (per the union-find algorithm), so `sub_root_var(a)
 224     /// == sub_root_var(b)` implies that:
 225     ///
 226     ///     exists X. (a <: X || X <: a) && (b <: X || X <: b)
 227     pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 228         self.sub_relations.find(vid)
 229     }
 230
 231     /// True if `a` and `b` have same "sub-root" (i.e., exists some
 232     /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
 233     pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
 234         self.sub_root_var(a) == self.sub_root_var(b)
 235     }
 236
 237     /// Retrieves the type to which `vid` has been instantiated, if
 238     /// any.
 239     pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 240         self.eq_relations.probe_value(vid)
 241     }
 242
 243     /// If `t` is a type-inference variable, and it has been
 244     /// instantiated, then return the with which it was
 245     /// instantiated. Otherwise, returns `t`.
 246     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 247         match t.sty {
 248             ty::Infer(ty::TyVar(v)) => {
 249                 match self.probe(v) {
 250                     TypeVariableValue::Unknown { .. } => t,
 251                     TypeVariableValue::Known { value } => value,
 252                 }
 253             }
 254             _ => t,
 255         }
 256     }
 257
 258     /// Creates a snapshot of the type variable state.  This snapshot
 259     /// must later be committed (`commit()`) or rolled back
 260     /// (`rollback_to()`).  Nested snapshots are permitted, but must
 261     /// be processed in a stack-like fashion.
 262     pub fn snapshot(&mut self) -> Snapshot<'tcx> {
 263         Snapshot {
 264             snapshot: self.values.start_snapshot(),
 265             eq_snapshot: self.eq_relations.snapshot(),
 266             sub_snapshot: self.sub_relations.snapshot(),
 267         }
 268     }
 269
 270     /// Undoes all changes since the snapshot was created. Any
 271     /// snapshots created since that point must already have been
 272     /// committed or rolled back.
 273     pub fn rollback_to(&mut self, s: Snapshot<'tcx>) {
 274         debug!("rollback_to{:?}", {
 275             for action in self.values.actions_since_snapshot(&s.snapshot) {
 276                 if let sv::UndoLog::NewElem(index) = *action {
 277                     debug!("inference variable _#{}t popped", index)
 278                 }
 279             }
 280         });
 281
 282         let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
 283         self.values.rollback_to(snapshot);
 284         self.eq_relations.rollback_to(eq_snapshot);
 285         self.sub_relations.rollback_to(sub_snapshot);
 286     }
 287
 288     /// Commits all changes since the snapshot was created, making
 289     /// them permanent (unless this snapshot was created within
 290     /// another snapshot). Any snapshots created since that point
 291     /// must already have been committed or rolled back.
 292     pub fn commit(&mut self, s: Snapshot<'tcx>) {
 293         let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
 294         self.values.commit(snapshot);
 295         self.eq_relations.commit(eq_snapshot);
 296         self.sub_relations.commit(sub_snapshot);
 297     }
 298
 299     /// Returns a map `{V1 -> V2}`, where the keys `{V1}` are
 300     /// ty-variables created during the snapshot, and the values
 301     /// `{V2}` are the root variables that they were unified with,
 302     /// along with their origin.
 303     pub fn types_created_since_snapshot(&mut self, s: &Snapshot<'tcx>) -> TypeVariableMap {
 304         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 305
 306         actions_since_snapshot
 307             .iter()
 308             .filter_map(|action| match action {
 309                 &sv::UndoLog::NewElem(index) => Some(ty::TyVid { index: index as u32 }),
 310                 _ => None,
 311             })
 312             .map(|vid| {
 313                 let origin = self.values.get(vid.index as usize).origin.clone();
 314                 (vid, origin)
 315             })
 316             .collect()
 317     }
 318
 319     /// Find the set of type variables that existed *before* `s`
 320     /// but which have only been unified since `s` started, and
 321     /// return the types with which they were unified. So if we had
 322     /// a type variable `V0`, then we started the snapshot, then we
 323     /// created a type variable `V1`, unified `V0` with `T0`, and
 324     /// unified `V1` with `T1`, this function would return `{T0}`.
 325     pub fn types_escaping_snapshot(&mut self, s: &Snapshot<'tcx>) -> Vec<Ty<'tcx>> {
 326         let mut new_elem_threshold = u32::MAX;
 327         let mut escaping_types = Vec::new();
 328         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 329         debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
 330         for action in actions_since_snapshot {
 331             match *action {
 332                 sv::UndoLog::NewElem(index) => {
 333                     // if any new variables were created during the
 334                     // snapshot, remember the lower index (which will
 335                     // always be the first one we see). Note that this
 336                     // action must precede those variables being
 337                     // specified.
 338                     new_elem_threshold = cmp::min(new_elem_threshold, index as u32);
 339                     debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
 340                 }
 341
 342                 sv::UndoLog::Other(Instantiate { vid, .. }) => {
 343                     if vid.index < new_elem_threshold {
 344                         // quick check to see if this variable was
 345                         // created since the snapshot started or not.
 346                         let escaping_type = match self.eq_relations.probe_value(vid) {
 347                             TypeVariableValue::Unknown { .. } => bug!(),
 348                             TypeVariableValue::Known { value } => value,
 349                         };
 350                         escaping_types.push(escaping_type);
 351                     }
 352                     debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
 353                 }
 354
 355                 _ => { }
 356             }
 357         }
 358
 359         escaping_types
 360     }
 361
 362     /// Returns indices of all variables that are not yet
 363     /// instantiated.
 364     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
 365         (0..self.values.len())
 366             .filter_map(|i| {
 367                 let vid = ty::TyVid { index: i as u32 };
 368                 match self.probe(vid) {
 369                     TypeVariableValue::Unknown { .. } => Some(vid),
 370                     TypeVariableValue::Known { .. } => None,
 371                 }
 372             })
 373             .collect()
 374     }
 375 }
 376
 377 impl sv::SnapshotVecDelegate for Delegate {
 378     type Value = TypeVariableData;
 379     type Undo = Instantiate;
 380
 381     fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
 382         // We don't actually have to *do* anything to reverse an
 383         // instanation; the value for a variable is stored in the
 384         // `eq_relations` and hence its rollback code will handle
 385         // it. In fact, we could *almost* just remove the
 386         // `SnapshotVec` entirely, except that we would have to
 387         // reproduce *some* of its logic, since we want to know which
 388         // type variables have been instantiated since the snapshot
 389         // was started, so we can implement `types_escaping_snapshot`.
 390         //
 391         // (If we extended the `UnificationTable` to let us see which
 392         // values have been unified and so forth, that might also
 393         // suffice.)
 394     }
 395 }
 396
 397 ///////////////////////////////////////////////////////////////////////////
 398
 399 /// These structs (a newtyped TyVid) are used as the unification key
 400 /// for the `eq_relations`; they carry a `TypeVariableValue` along
 401 /// with them.
 402 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 403 struct TyVidEqKey<'tcx> {
 404     vid: ty::TyVid,
 405
 406     // in the table, we map each ty-vid to one of these:
 407     phantom: PhantomData<TypeVariableValue<'tcx>>,
 408 }
 409
 410 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
 411     fn from(vid: ty::TyVid) -> Self {
 412         TyVidEqKey { vid, phantom: PhantomData }
 413     }
 414 }
 415
 416 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
 417     type Value = TypeVariableValue<'tcx>;
 418     fn index(&self) -> u32 { self.vid.index }
 419     fn from_index(i: u32) -> Self { TyVidEqKey::from(ty::TyVid { index: i }) }
 420     fn tag() -> &'static str { "TyVidEqKey" }
 421 }
 422
 423 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
 424     type Error = ut::NoError;
 425
 426     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
 427         match (value1, value2) {
 428             // We never equate two type variables, both of which
 429             // have known types.  Instead, we recursively equate
 430             // those types.
 431             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
 432                 bug!("equating two type variables, both of which have known types")
 433             }
 434
 435             // If one side is known, prefer that one.
 436             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
 437             (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
 438
 439             // If both sides are *unknown*, it hardly matters, does it?
 440             (&TypeVariableValue::Unknown { universe: universe1 },
 441              &TypeVariableValue::Unknown { universe: universe2 }) =>  {
 442                 // If we unify two unbound variables, ?T and ?U, then whatever
 443                 // value they wind up taking (which must be the same value) must
 444                 // be nameable by both universes. Therefore, the resulting
 445                 // universe is the minimum of the two universes, because that is
 446                 // the one which contains the fewest names in scope.
 447                 let universe = cmp::min(universe1, universe2);
 448                 Ok(TypeVariableValue::Unknown { universe })
 449             }
 450         }
 451     }
 452 }
 453
 454 /// Raw `TyVid` are used as the unification key for `sub_relations`;
 455 /// they carry no values.
 456 impl ut::UnifyKey for ty::TyVid {
 457     type Value = ();
 458     fn index(&self) -> u32 { self.index }
 459     fn from_index(i: u32) -> ty::TyVid { ty::TyVid { index: i } }
 460     fn tag() -> &'static str { "TyVid" }
 461 }
 462