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