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