compiler/rustc_infer/src/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 crate::infer::InferCtxtUndoLogs;
   7
   8 use rustc_data_structures::snapshot_vec as sv;
   9 use rustc_data_structures::unify as ut;
  10 use std::cmp;
  11 use std::marker::PhantomData;
  12 use std::ops::Range;
  13
  14 use rustc_data_structures::undo_log::{Rollback, UndoLogs};
  15
  16 /// Represents a single undo-able action that affects a type inference variable.
  17 #[derive(Clone)]
  18 pub(crate) enum UndoLog<'tcx> {
  19     EqRelation(sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>),
  20     SubRelation(sv::UndoLog<ut::Delegate<ty::TyVid>>),
  21     Values(sv::UndoLog<Delegate>),
  22 }
  23
  24 /// Convert from a specific kind of undo to the more general UndoLog
  25 impl<'tcx> From<sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>> for UndoLog<'tcx> {
  26     fn from(l: sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>) -> Self {
  27         UndoLog::EqRelation(l)
  28     }
  29 }
  30
  31 /// Convert from a specific kind of undo to the more general UndoLog
  32 impl<'tcx> From<sv::UndoLog<ut::Delegate<ty::TyVid>>> for UndoLog<'tcx> {
  33     fn from(l: sv::UndoLog<ut::Delegate<ty::TyVid>>) -> Self {
  34         UndoLog::SubRelation(l)
  35     }
  36 }
  37
  38 /// Convert from a specific kind of undo to the more general UndoLog
  39 impl<'tcx> From<sv::UndoLog<Delegate>> for UndoLog<'tcx> {
  40     fn from(l: sv::UndoLog<Delegate>) -> Self {
  41         UndoLog::Values(l)
  42     }
  43 }
  44
  45 /// Convert from a specific kind of undo to the more general UndoLog
  46 impl<'tcx> From<Instantiate> for UndoLog<'tcx> {
  47     fn from(l: Instantiate) -> Self {
  48         UndoLog::Values(sv::UndoLog::Other(l))
  49     }
  50 }
  51
  52 impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> {
  53     fn reverse(&mut self, undo: UndoLog<'tcx>) {
  54         match undo {
  55             UndoLog::EqRelation(undo) => self.eq_relations.reverse(undo),
  56             UndoLog::SubRelation(undo) => self.sub_relations.reverse(undo),
  57             UndoLog::Values(undo) => self.values.reverse(undo),
  58         }
  59     }
  60 }
  61
  62 #[derive(Clone)]
  63 pub struct TypeVariableStorage<'tcx> {
  64     values: sv::SnapshotVecStorage<Delegate>,
  65
  66     /// Two variables are unified in `eq_relations` when we have a
  67     /// constraint `?X == ?Y`. This table also stores, for each key,
  68     /// the known value.
  69     eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
  70
  71     /// Two variables are unified in `sub_relations` when we have a
  72     /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
  73     /// table exists only to help with the occurs check. In particular,
  74     /// we want to report constraints like these as an occurs check
  75     /// violation:
  76     ///
  77     ///     ?1 <: ?3
  78     ///     Box<?3> <: ?1
  79     ///
  80     /// Without this second table, what would happen in a case like
  81     /// this is that we would instantiate `?1` with a generalized
  82     /// type like `Box<?6>`. We would then relate `Box<?3> <: Box<?6>`
  83     /// and infer that `?3 <: ?6`. Next, since `?1` was instantiated,
  84     /// we would process `?1 <: ?3`, generalize `?1 = Box<?6>` to `Box<?9>`,
  85     /// and instantiate `?3` with `Box<?9>`. Finally, we would relate
  86     /// `?6 <: ?9`. But now that we instantiated `?3`, we can process
  87     /// `?3 <: ?6`, which gives us `Box<?9> <: ?6`... and the cycle
  88     /// continues. (This is `occurs-check-2.rs`.)
  89     ///
  90     /// What prevents this cycle is that when we generalize
  91     /// `Box<?3>` to `Box<?6>`, we also sub-unify `?3` and `?6`
  92     /// (in the generalizer). When we then process `Box<?6> <: ?3`,
  93     /// the occurs check then fails because `?6` and `?3` are sub-unified,
  94     /// and hence generalization fails.
  95     ///
  96     /// This is reasonable because, in Rust, subtypes have the same
  97     /// "skeleton" and hence there is no possible type such that
  98     /// (e.g.)  `Box<?3> <: ?3` for any `?3`.
  99     ///
 100     /// In practice, we sometimes sub-unify variables in other spots, such
 101     /// as when processing subtype predicates. This is not necessary but is
 102     /// done to aid diagnostics, as it allows us to be more effective when
 103     /// we guide the user towards where they should insert type hints.
 104     sub_relations: ut::UnificationTableStorage<ty::TyVid>,
 105 }
 106
 107 pub struct TypeVariableTable<'a, 'tcx> {
 108     storage: &'a mut TypeVariableStorage<'tcx>,
 109
 110     undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 111 }
 112
 113 #[derive(Copy, Clone, Debug)]
 114 pub struct TypeVariableOrigin {
 115     pub kind: TypeVariableOriginKind,
 116     pub span: Span,
 117 }
 118
 119 /// Reasons to create a type inference variable
 120 #[derive(Copy, Clone, Debug)]
 121 pub enum TypeVariableOriginKind {
 122     MiscVariable,
 123     NormalizeProjectionType,
 124     TypeInference,
 125     TypeParameterDefinition(Symbol, Option<DefId>),
 126
 127     /// One of the upvars or closure kind parameters in a `ClosureSubsts`
 128     /// (before it has been determined).
 129     // FIXME(eddyb) distinguish upvar inference variables from the rest.
 130     ClosureSynthetic,
 131     SubstitutionPlaceholder,
 132     AutoDeref,
 133     AdjustmentType,
 134
 135     /// In type check, when we are type checking a function that
 136     /// returns `-> dyn Foo`, we substitute a type variable for the
 137     /// return type for diagnostic purposes.
 138     DynReturnFn,
 139     LatticeVariable,
 140 }
 141
 142 #[derive(Clone)]
 143 pub(crate) struct TypeVariableData {
 144     origin: TypeVariableOrigin,
 145 }
 146
 147 #[derive(Copy, Clone, Debug)]
 148 pub enum TypeVariableValue<'tcx> {
 149     Known { value: Ty<'tcx> },
 150     Unknown { universe: ty::UniverseIndex },
 151 }
 152
 153 impl<'tcx> TypeVariableValue<'tcx> {
 154     /// If this value is known, returns the type it is known to be.
 155     /// Otherwise, `None`.
 156     pub fn known(&self) -> Option<Ty<'tcx>> {
 157         match *self {
 158             TypeVariableValue::Unknown { .. } => None,
 159             TypeVariableValue::Known { value } => Some(value),
 160         }
 161     }
 162
 163     pub fn is_unknown(&self) -> bool {
 164         match *self {
 165             TypeVariableValue::Unknown { .. } => true,
 166             TypeVariableValue::Known { .. } => false,
 167         }
 168     }
 169 }
 170
 171 #[derive(Clone)]
 172 pub(crate) struct Instantiate;
 173
 174 pub(crate) struct Delegate;
 175
 176 impl<'tcx> TypeVariableStorage<'tcx> {
 177     pub fn new() -> TypeVariableStorage<'tcx> {
 178         TypeVariableStorage {
 179             values: sv::SnapshotVecStorage::new(),
 180             eq_relations: ut::UnificationTableStorage::new(),
 181             sub_relations: ut::UnificationTableStorage::new(),
 182         }
 183     }
 184
 185     #[inline]
 186     pub(crate) fn with_log<'a>(
 187         &'a mut self,
 188         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 189     ) -> TypeVariableTable<'a, 'tcx> {
 190         TypeVariableTable { storage: self, undo_log }
 191     }
 192 }
 193
 194 impl<'tcx> TypeVariableTable<'_, 'tcx> {
 195     /// Returns the origin that was given when `vid` was created.
 196     ///
 197     /// Note that this function does not return care whether
 198     /// `vid` has been unified with something else or not.
 199     pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
 200         &self.storage.values.get(vid.as_usize()).origin
 201     }
 202
 203     /// Records that `a == b`, depending on `dir`.
 204     ///
 205     /// Precondition: neither `a` nor `b` are known.
 206     pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
 207         debug_assert!(self.probe(a).is_unknown());
 208         debug_assert!(self.probe(b).is_unknown());
 209         self.eq_relations().union(a, b);
 210         self.sub_relations().union(a, b);
 211     }
 212
 213     /// Records that `a <: b`, depending on `dir`.
 214     ///
 215     /// Precondition: neither `a` nor `b` are known.
 216     pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
 217         debug_assert!(self.probe(a).is_unknown());
 218         debug_assert!(self.probe(b).is_unknown());
 219         self.sub_relations().union(a, b);
 220     }
 221
 222     /// Instantiates `vid` with the type `ty`.
 223     ///
 224     /// Precondition: `vid` must not have been previously instantiated.
 225     pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
 226         let vid = self.root_var(vid);
 227         debug_assert!(self.probe(vid).is_unknown());
 228         debug_assert!(
 229             self.eq_relations().probe_value(vid).is_unknown(),
 230             "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
 231             vid,
 232             ty,
 233             self.eq_relations().probe_value(vid)
 234         );
 235         self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
 236
 237         // Hack: we only need this so that `types_escaping_snapshot`
 238         // can see what has been unified; see the Delegate impl for
 239         // more details.
 240         self.undo_log.push(Instantiate);
 241     }
 242
 243     /// Creates a new type variable.
 244     ///
 245     /// - `diverging`: indicates if this is a "diverging" type
 246     ///   variable, e.g.,  one created as the type of a `return`
 247     ///   expression. The code in this module doesn't care if a
 248     ///   variable is diverging, but the main Rust type-checker will
 249     ///   sometimes "unify" such variables with the `!` or `()` types.
 250     /// - `origin`: indicates *why* the type variable was created.
 251     ///   The code in this module doesn't care, but it can be useful
 252     ///   for improving error messages.
 253     pub fn new_var(
 254         &mut self,
 255         universe: ty::UniverseIndex,
 256         origin: TypeVariableOrigin,
 257     ) -> ty::TyVid {
 258         let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
 259
 260         let sub_key = self.sub_relations().new_key(());
 261         assert_eq!(eq_key.vid, sub_key);
 262
 263         let index = self.values().push(TypeVariableData { origin });
 264         assert_eq!(eq_key.vid.as_u32(), index as u32);
 265
 266         debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin);
 267
 268         eq_key.vid
 269     }
 270
 271     /// Returns the number of type variables created thus far.
 272     pub fn num_vars(&self) -> usize {
 273         self.storage.values.len()
 274     }
 275
 276     /// Returns the "root" variable of `vid` in the `eq_relations`
 277     /// equivalence table. All type variables that have been equated
 278     /// will yield the same root variable (per the union-find
 279     /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
 280     /// b` (transitively).
 281     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 282         self.eq_relations().find(vid).vid
 283     }
 284
 285     /// Returns the "root" variable of `vid` in the `sub_relations`
 286     /// equivalence table. All type variables that have been are
 287     /// related via equality or subtyping will yield the same root
 288     /// variable (per the union-find algorithm), so `sub_root_var(a)
 289     /// == sub_root_var(b)` implies that:
 290     ///
 291     ///     exists X. (a <: X || X <: a) && (b <: X || X <: b)
 292     pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 293         self.sub_relations().find(vid)
 294     }
 295
 296     /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
 297     /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
 298     pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
 299         self.sub_root_var(a) == self.sub_root_var(b)
 300     }
 301
 302     /// Retrieves the type to which `vid` has been instantiated, if
 303     /// any.
 304     pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 305         self.inlined_probe(vid)
 306     }
 307
 308     /// An always-inlined variant of `probe`, for very hot call sites.
 309     #[inline(always)]
 310     pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 311         self.eq_relations().inlined_probe_value(vid)
 312     }
 313
 314     /// If `t` is a type-inference variable, and it has been
 315     /// instantiated, then return the with which it was
 316     /// instantiated. Otherwise, returns `t`.
 317     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 318         match *t.kind() {
 319             ty::Infer(ty::TyVar(v)) => match self.probe(v) {
 320                 TypeVariableValue::Unknown { .. } => t,
 321                 TypeVariableValue::Known { value } => value,
 322             },
 323             _ => t,
 324         }
 325     }
 326
 327     #[inline]
 328     fn values(
 329         &mut self,
 330     ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
 331         self.storage.values.with_log(self.undo_log)
 332     }
 333
 334     #[inline]
 335     fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
 336         self.storage.eq_relations.with_log(self.undo_log)
 337     }
 338
 339     #[inline]
 340     fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
 341         self.storage.sub_relations.with_log(self.undo_log)
 342     }
 343
 344     /// Returns a range of the type variables created during the snapshot.
 345     pub fn vars_since_snapshot(
 346         &mut self,
 347         value_count: usize,
 348     ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
 349         let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
 350         (
 351             range.start..range.end,
 352             (range.start.as_usize()..range.end.as_usize())
 353                 .map(|index| self.storage.values.get(index).origin)
 354                 .collect(),
 355         )
 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.storage.values.len())
 362             .filter_map(|i| {
 363                 let vid = ty::TyVid::from_usize(i);
 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 pub(crate) 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     #[inline] // make this function eligible for inlining - it is quite hot.
 408     fn from(vid: ty::TyVid) -> Self {
 409         TyVidEqKey { vid, phantom: PhantomData }
 410     }
 411 }
 412
 413 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
 414     type Value = TypeVariableValue<'tcx>;
 415     #[inline(always)]
 416     fn index(&self) -> u32 {
 417         self.vid.as_u32()
 418     }
 419     #[inline]
 420     fn from_index(i: u32) -> Self {
 421         TyVidEqKey::from(ty::TyVid::from_u32(i))
 422     }
 423     fn tag() -> &'static str {
 424         "TyVidEqKey"
 425     }
 426 }
 427
 428 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
 429     type Error = ut::NoError;
 430
 431     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
 432         match (value1, value2) {
 433             // We never equate two type variables, both of which
 434             // have known types.  Instead, we recursively equate
 435             // those types.
 436             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
 437                 bug!("equating two type variables, both of which have known types")
 438             }
 439
 440             // If one side is known, prefer that one.
 441             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
 442             (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
 443
 444             // If both sides are *unknown*, it hardly matters, does it?
 445             (
 446                 &TypeVariableValue::Unknown { universe: universe1 },
 447                 &TypeVariableValue::Unknown { universe: universe2 },
 448             ) => {
 449                 // If we unify two unbound variables, ?T and ?U, then whatever
 450                 // value they wind up taking (which must be the same value) must
 451                 // be nameable by both universes. Therefore, the resulting
 452                 // universe is the minimum of the two universes, because that is
 453                 // the one which contains the fewest names in scope.
 454                 let universe = cmp::min(universe1, universe2);
 455                 Ok(TypeVariableValue::Unknown { universe })
 456             }
 457         }
 458     }
 459 }