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     /// ``` text
  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     OpaqueTypeInference(DefId),
 126     TypeParameterDefinition(Symbol, Option<DefId>),
 127
 128     /// One of the upvars or closure kind parameters in a `ClosureSubsts`
 129     /// (before it has been determined).
 130     // FIXME(eddyb) distinguish upvar inference variables from the rest.
 131     ClosureSynthetic,
 132     SubstitutionPlaceholder,
 133     AutoDeref,
 134     AdjustmentType,
 135
 136     /// In type check, when we are type checking a function that
 137     /// returns `-> dyn Foo`, we substitute a type variable for the
 138     /// return type for diagnostic purposes.
 139     DynReturnFn,
 140     LatticeVariable,
 141 }
 142
 143 #[derive(Clone)]
 144 pub(crate) struct TypeVariableData {
 145     origin: TypeVariableOrigin,
 146 }
 147
 148 #[derive(Copy, Clone, Debug)]
 149 pub enum TypeVariableValue<'tcx> {
 150     Known { value: Ty<'tcx> },
 151     Unknown { universe: ty::UniverseIndex },
 152 }
 153
 154 impl<'tcx> TypeVariableValue<'tcx> {
 155     /// If this value is known, returns the type it is known to be.
 156     /// Otherwise, `None`.
 157     pub fn known(&self) -> Option<Ty<'tcx>> {
 158         match *self {
 159             TypeVariableValue::Unknown { .. } => None,
 160             TypeVariableValue::Known { value } => Some(value),
 161         }
 162     }
 163
 164     pub fn is_unknown(&self) -> bool {
 165         match *self {
 166             TypeVariableValue::Unknown { .. } => true,
 167             TypeVariableValue::Known { .. } => false,
 168         }
 169     }
 170 }
 171
 172 #[derive(Clone)]
 173 pub(crate) struct Instantiate;
 174
 175 pub(crate) struct Delegate;
 176
 177 impl<'tcx> TypeVariableStorage<'tcx> {
 178     pub fn new() -> TypeVariableStorage<'tcx> {
 179         TypeVariableStorage {
 180             values: sv::SnapshotVecStorage::new(),
 181             eq_relations: ut::UnificationTableStorage::new(),
 182             sub_relations: ut::UnificationTableStorage::new(),
 183         }
 184     }
 185
 186     #[inline]
 187     pub(crate) fn with_log<'a>(
 188         &'a mut self,
 189         undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
 190     ) -> TypeVariableTable<'a, 'tcx> {
 191         TypeVariableTable { storage: self, undo_log }
 192     }
 193 }
 194
 195 impl<'tcx> TypeVariableTable<'_, 'tcx> {
 196     /// Returns the origin that was given when `vid` was created.
 197     ///
 198     /// Note that this function does not return care whether
 199     /// `vid` has been unified with something else or not.
 200     pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
 201         &self.storage.values.get(vid.as_usize()).origin
 202     }
 203
 204     /// Records that `a == b`, depending on `dir`.
 205     ///
 206     /// Precondition: neither `a` nor `b` are known.
 207     pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
 208         debug_assert!(self.probe(a).is_unknown());
 209         debug_assert!(self.probe(b).is_unknown());
 210         self.eq_relations().union(a, b);
 211         self.sub_relations().union(a, b);
 212     }
 213
 214     /// Records that `a <: b`, depending on `dir`.
 215     ///
 216     /// Precondition: neither `a` nor `b` are known.
 217     pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
 218         debug_assert!(self.probe(a).is_unknown());
 219         debug_assert!(self.probe(b).is_unknown());
 220         self.sub_relations().union(a, b);
 221     }
 222
 223     /// Instantiates `vid` with the type `ty`.
 224     ///
 225     /// Precondition: `vid` must not have been previously instantiated.
 226     pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
 227         let vid = self.root_var(vid);
 228         debug_assert!(self.probe(vid).is_unknown());
 229         debug_assert!(
 230             self.eq_relations().probe_value(vid).is_unknown(),
 231             "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
 232             vid,
 233             ty,
 234             self.eq_relations().probe_value(vid)
 235         );
 236         self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
 237
 238         // Hack: we only need this so that `types_escaping_snapshot`
 239         // can see what has been unified; see the Delegate impl for
 240         // more details.
 241         self.undo_log.push(Instantiate);
 242     }
 243
 244     /// Creates a new type variable.
 245     ///
 246     /// - `diverging`: indicates if this is a "diverging" type
 247     ///   variable, e.g.,  one created as the type of a `return`
 248     ///   expression. The code in this module doesn't care if a
 249     ///   variable is diverging, but the main Rust type-checker will
 250     ///   sometimes "unify" such variables with the `!` or `()` types.
 251     /// - `origin`: indicates *why* the type variable was created.
 252     ///   The code in this module doesn't care, but it can be useful
 253     ///   for improving error messages.
 254     pub fn new_var(
 255         &mut self,
 256         universe: ty::UniverseIndex,
 257         origin: TypeVariableOrigin,
 258     ) -> ty::TyVid {
 259         let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
 260
 261         let sub_key = self.sub_relations().new_key(());
 262         assert_eq!(eq_key.vid, sub_key);
 263
 264         let index = self.values().push(TypeVariableData { origin });
 265         assert_eq!(eq_key.vid.as_u32(), index as u32);
 266
 267         debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin);
 268
 269         eq_key.vid
 270     }
 271
 272     /// Returns the number of type variables created thus far.
 273     pub fn num_vars(&self) -> usize {
 274         self.storage.values.len()
 275     }
 276
 277     /// Returns the "root" variable of `vid` in the `eq_relations`
 278     /// equivalence table. All type variables that have been equated
 279     /// will yield the same root variable (per the union-find
 280     /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
 281     /// b` (transitively).
 282     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 283         self.eq_relations().find(vid).vid
 284     }
 285
 286     /// Returns the "root" variable of `vid` in the `sub_relations`
 287     /// equivalence table. All type variables that have been are
 288     /// related via equality or subtyping will yield the same root
 289     /// variable (per the union-find algorithm), so `sub_root_var(a)
 290     /// == sub_root_var(b)` implies that:
 291     /// ```text
 292     /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
 293     /// ```
 294     pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 295         self.sub_relations().find(vid)
 296     }
 297
 298     /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
 299     /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
 300     pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
 301         self.sub_root_var(a) == self.sub_root_var(b)
 302     }
 303
 304     /// Retrieves the type to which `vid` has been instantiated, if
 305     /// any.
 306     pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 307         self.inlined_probe(vid)
 308     }
 309
 310     /// An always-inlined variant of `probe`, for very hot call sites.
 311     #[inline(always)]
 312     pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 313         self.eq_relations().inlined_probe_value(vid)
 314     }
 315
 316     /// If `t` is a type-inference variable, and it has been
 317     /// instantiated, then return the with which it was
 318     /// instantiated. Otherwise, returns `t`.
 319     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 320         match *t.kind() {
 321             ty::Infer(ty::TyVar(v)) => match self.probe(v) {
 322                 TypeVariableValue::Unknown { .. } => t,
 323                 TypeVariableValue::Known { value } => value,
 324             },
 325             _ => t,
 326         }
 327     }
 328
 329     #[inline]
 330     fn values(
 331         &mut self,
 332     ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
 333         self.storage.values.with_log(self.undo_log)
 334     }
 335
 336     #[inline]
 337     fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
 338         self.storage.eq_relations.with_log(self.undo_log)
 339     }
 340
 341     #[inline]
 342     fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
 343         self.storage.sub_relations.with_log(self.undo_log)
 344     }
 345
 346     /// Returns a range of the type variables created during the snapshot.
 347     pub fn vars_since_snapshot(
 348         &mut self,
 349         value_count: usize,
 350     ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
 351         let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
 352         (
 353             range.start..range.end,
 354             (range.start.as_usize()..range.end.as_usize())
 355                 .map(|index| self.storage.values.get(index).origin)
 356                 .collect(),
 357         )
 358     }
 359
 360     /// Returns indices of all variables that are not yet
 361     /// instantiated.
 362     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
 363         (0..self.storage.values.len())
 364             .filter_map(|i| {
 365                 let vid = ty::TyVid::from_usize(i);
 366                 match self.probe(vid) {
 367                     TypeVariableValue::Unknown { .. } => Some(vid),
 368                     TypeVariableValue::Known { .. } => None,
 369                 }
 370             })
 371             .collect()
 372     }
 373 }
 374
 375 impl sv::SnapshotVecDelegate for Delegate {
 376     type Value = TypeVariableData;
 377     type Undo = Instantiate;
 378
 379     fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
 380         // We don't actually have to *do* anything to reverse an
 381         // instantiation; the value for a variable is stored in the
 382         // `eq_relations` and hence its rollback code will handle
 383         // it. In fact, we could *almost* just remove the
 384         // `SnapshotVec` entirely, except that we would have to
 385         // reproduce *some* of its logic, since we want to know which
 386         // type variables have been instantiated since the snapshot
 387         // was started, so we can implement `types_escaping_snapshot`.
 388         //
 389         // (If we extended the `UnificationTable` to let us see which
 390         // values have been unified and so forth, that might also
 391         // suffice.)
 392     }
 393 }
 394
 395 ///////////////////////////////////////////////////////////////////////////
 396
 397 /// These structs (a newtyped TyVid) are used as the unification key
 398 /// for the `eq_relations`; they carry a `TypeVariableValue` along
 399 /// with them.
 400 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 401 pub(crate) struct TyVidEqKey<'tcx> {
 402     vid: ty::TyVid,
 403
 404     // in the table, we map each ty-vid to one of these:
 405     phantom: PhantomData<TypeVariableValue<'tcx>>,
 406 }
 407
 408 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
 409     #[inline] // make this function eligible for inlining - it is quite hot.
 410     fn from(vid: ty::TyVid) -> Self {
 411         TyVidEqKey { vid, phantom: PhantomData }
 412     }
 413 }
 414
 415 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
 416     type Value = TypeVariableValue<'tcx>;
 417     #[inline(always)]
 418     fn index(&self) -> u32 {
 419         self.vid.as_u32()
 420     }
 421     #[inline]
 422     fn from_index(i: u32) -> Self {
 423         TyVidEqKey::from(ty::TyVid::from_u32(i))
 424     }
 425     fn tag() -> &'static str {
 426         "TyVidEqKey"
 427     }
 428 }
 429
 430 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
 431     type Error = ut::NoError;
 432
 433     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
 434         match (value1, value2) {
 435             // We never equate two type variables, both of which
 436             // have known types. Instead, we recursively equate
 437             // those types.
 438             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
 439                 bug!("equating two type variables, both of which have known types")
 440             }
 441
 442             // If one side is known, prefer that one.
 443             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
 444             (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
 445
 446             // If both sides are *unknown*, it hardly matters, does it?
 447             (
 448                 &TypeVariableValue::Unknown { universe: universe1 },
 449                 &TypeVariableValue::Unknown { universe: universe2 },
 450             ) => {
 451                 // If we unify two unbound variables, ?T and ?U, then whatever
 452                 // value they wind up taking (which must be the same value) must
 453                 // be nameable by both universes. Therefore, the resulting
 454                 // universe is the minimum of the two universes, because that is
 455                 // the one which contains the fewest names in scope.
 456                 let universe = cmp::min(universe1, universe2);
 457                 Ok(TypeVariableValue::Unknown { universe })
 458             }
 459         }
 460     }
 461 }