src/librustc/infer/type_variable.rs

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