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     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     /// ```text
 291     /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
 292     /// ```
 293     pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
 294         self.sub_relations().find(vid)
 295     }
 296
 297     /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
 298     /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
 299     pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
 300         self.sub_root_var(a) == self.sub_root_var(b)
 301     }
 302
 303     /// Retrieves the type to which `vid` has been instantiated, if
 304     /// any.
 305     pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 306         self.inlined_probe(vid)
 307     }
 308
 309     /// An always-inlined variant of `probe`, for very hot call sites.
 310     #[inline(always)]
 311     pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
 312         self.eq_relations().inlined_probe_value(vid)
 313     }
 314
 315     /// If `t` is a type-inference variable, and it has been
 316     /// instantiated, then return the with which it was
 317     /// instantiated. Otherwise, returns `t`.
 318     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 319         match *t.kind() {
 320             ty::Infer(ty::TyVar(v)) => match self.probe(v) {
 321                 TypeVariableValue::Unknown { .. } => t,
 322                 TypeVariableValue::Known { value } => value,
 323             },
 324             _ => t,
 325         }
 326     }
 327
 328     #[inline]
 329     fn values(
 330         &mut self,
 331     ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
 332         self.storage.values.with_log(self.undo_log)
 333     }
 334
 335     #[inline]
 336     fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
 337         self.storage.eq_relations.with_log(self.undo_log)
 338     }
 339
 340     #[inline]
 341     fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
 342         self.storage.sub_relations.with_log(self.undo_log)
 343     }
 344
 345     /// Returns a range of the type variables created during the snapshot.
 346     pub fn vars_since_snapshot(
 347         &mut self,
 348         value_count: usize,
 349     ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
 350         let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
 351         (
 352             range.start..range.end,
 353             (range.start.as_usize()..range.end.as_usize())
 354                 .map(|index| self.storage.values.get(index).origin)
 355                 .collect(),
 356         )
 357     }
 358
 359     /// Returns indices of all variables that are not yet
 360     /// instantiated.
 361     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
 362         (0..self.storage.values.len())
 363             .filter_map(|i| {
 364                 let vid = ty::TyVid::from_usize(i);
 365                 match self.probe(vid) {
 366                     TypeVariableValue::Unknown { .. } => Some(vid),
 367                     TypeVariableValue::Known { .. } => None,
 368                 }
 369             })
 370             .collect()
 371     }
 372 }
 373
 374 impl sv::SnapshotVecDelegate for Delegate {
 375     type Value = TypeVariableData;
 376     type Undo = Instantiate;
 377
 378     fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
 379         // We don't actually have to *do* anything to reverse an
 380         // instantiation; the value for a variable is stored in the
 381         // `eq_relations` and hence its rollback code will handle
 382         // it. In fact, we could *almost* just remove the
 383         // `SnapshotVec` entirely, except that we would have to
 384         // reproduce *some* of its logic, since we want to know which
 385         // type variables have been instantiated since the snapshot
 386         // was started, so we can implement `types_escaping_snapshot`.
 387         //
 388         // (If we extended the `UnificationTable` to let us see which
 389         // values have been unified and so forth, that might also
 390         // suffice.)
 391     }
 392 }
 393
 394 ///////////////////////////////////////////////////////////////////////////
 395
 396 /// These structs (a newtyped TyVid) are used as the unification key
 397 /// for the `eq_relations`; they carry a `TypeVariableValue` along
 398 /// with them.
 399 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 400 pub(crate) struct TyVidEqKey<'tcx> {
 401     vid: ty::TyVid,
 402
 403     // in the table, we map each ty-vid to one of these:
 404     phantom: PhantomData<TypeVariableValue<'tcx>>,
 405 }
 406
 407 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
 408     #[inline] // make this function eligible for inlining - it is quite hot.
 409     fn from(vid: ty::TyVid) -> Self {
 410         TyVidEqKey { vid, phantom: PhantomData }
 411     }
 412 }
 413
 414 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
 415     type Value = TypeVariableValue<'tcx>;
 416     #[inline(always)]
 417     fn index(&self) -> u32 {
 418         self.vid.as_u32()
 419     }
 420     #[inline]
 421     fn from_index(i: u32) -> Self {
 422         TyVidEqKey::from(ty::TyVid::from_u32(i))
 423     }
 424     fn tag() -> &'static str {
 425         "TyVidEqKey"
 426     }
 427 }
 428
 429 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
 430     type Error = ut::NoError;
 431
 432     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
 433         match (value1, value2) {
 434             // We never equate two type variables, both of which
 435             // have known types.  Instead, we recursively equate
 436             // those types.
 437             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
 438                 bug!("equating two type variables, both of which have known types")
 439             }
 440
 441             // If one side is known, prefer that one.
 442             (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
 443             (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
 444
 445             // If both sides are *unknown*, it hardly matters, does it?
 446             (
 447                 &TypeVariableValue::Unknown { universe: universe1 },
 448                 &TypeVariableValue::Unknown { universe: universe2 },
 449             ) => {
 450                 // If we unify two unbound variables, ?T and ?U, then whatever
 451                 // value they wind up taking (which must be the same value) must
 452                 // be nameable by both universes. Therefore, the resulting
 453                 // universe is the minimum of the two universes, because that is
 454                 // the one which contains the fewest names in scope.
 455                 let universe = cmp::min(universe1, universe2);
 456                 Ok(TypeVariableValue::Unknown { universe })
 457             }
 458         }
 459     }
 460 }