src/librustc_infer/infer/type_variable.rs

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