1 use rustc_hir::def_id::DefId;
2 use rustc_middle::ty::{self, Ty, TyVid};
3 use rustc_span::symbol::Symbol;
6 use crate::infer::InferCtxtUndoLogs;
8 use rustc_data_structures::snapshot_vec as sv;
9 use rustc_data_structures::unify as ut;
11 use std::marker::PhantomData;
14 use rustc_data_structures::undo_log::{Rollback, UndoLogs};
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>),
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)
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)
34 impl<'tcx> From<sv::UndoLog<Delegate>> for UndoLog<'tcx> {
35 fn from(l: sv::UndoLog<Delegate>) -> Self {
40 impl<'tcx> From<Instantiate> for UndoLog<'tcx> {
41 fn from(l: Instantiate) -> Self {
42 UndoLog::Values(sv::UndoLog::Other(l))
46 impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> {
47 fn reverse(&mut self, undo: UndoLog<'tcx>) {
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),
56 pub struct TypeVariableStorage<'tcx> {
57 values: sv::SnapshotVecStorage<Delegate>,
59 /// Two variables are unified in `eq_relations` when we have a
60 /// constraint `?X == ?Y`. This table also stores, for each key,
62 eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
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
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.
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::UnificationTableStorage<ty::TyVid>,
84 pub struct TypeVariableTable<'a, 'tcx> {
85 values: &'a mut sv::SnapshotVecStorage<Delegate>,
87 eq_relations: &'a mut ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
89 sub_relations: &'a mut ut::UnificationTableStorage<ty::TyVid>,
91 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
94 #[derive(Copy, Clone, Debug)]
95 pub struct TypeVariableOrigin {
96 pub kind: TypeVariableOriginKind,
100 /// Reasons to create a type inference variable
101 #[derive(Copy, Clone, Debug)]
102 pub enum TypeVariableOriginKind {
104 NormalizeProjectionType,
106 TypeParameterDefinition(Symbol, Option<DefId>),
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.
112 SubstitutionPlaceholder,
119 pub(crate) struct TypeVariableData {
120 origin: TypeVariableOrigin,
124 #[derive(Copy, Clone, Debug)]
125 pub enum TypeVariableValue<'tcx> {
126 Known { value: Ty<'tcx> },
127 Unknown { universe: ty::UniverseIndex },
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>> {
135 TypeVariableValue::Unknown { .. } => None,
136 TypeVariableValue::Known { value } => Some(value),
140 pub fn is_unknown(&self) -> bool {
142 TypeVariableValue::Unknown { .. } => true,
143 TypeVariableValue::Known { .. } => false,
148 pub struct Snapshot<'tcx> {
150 _marker: PhantomData<&'tcx ()>,
153 pub(crate) struct Instantiate {
157 pub(crate) struct Delegate;
159 impl<'tcx> TypeVariableStorage<'tcx> {
160 pub fn new() -> TypeVariableStorage<'tcx> {
161 TypeVariableStorage {
162 values: sv::SnapshotVecStorage::new(),
163 eq_relations: ut::UnificationTableStorage::new(),
164 sub_relations: ut::UnificationTableStorage::new(),
168 pub(crate) fn with_log<'a>(
170 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
171 ) -> TypeVariableTable<'a, 'tcx> {
172 let TypeVariableStorage { values, eq_relations, sub_relations } = self;
173 TypeVariableTable { values, eq_relations, sub_relations, undo_log }
177 impl<'tcx> TypeVariableTable<'_, 'tcx> {
178 /// Returns the diverges flag given when `vid` was created.
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).diverging
186 /// Returns the origin that was given when `vid` was created.
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).origin
194 /// Records that `a == b`, depending on `dir`.
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);
204 /// Records that `a <: b`, depending on `dir`.
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);
213 /// Instantiates `vid` with the type `ty`.
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());
220 self.eq_relations().probe_value(vid).is_unknown(),
221 "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
224 self.eq_relations().probe_value(vid)
226 self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
228 // Hack: we only need this so that `types_escaping_snapshot`
229 // can see what has been unified; see the Delegate impl for
231 self.undo_log.push(Instantiate { vid });
234 /// Creates a new type variable.
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.
246 universe: ty::UniverseIndex,
248 origin: TypeVariableOrigin,
250 let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
252 let sub_key = self.sub_relations().new_key(());
253 assert_eq!(eq_key.vid, sub_key);
255 let index = self.values().push(TypeVariableData { origin, diverging });
256 assert_eq!(eq_key.vid.index, index as u32);
259 "new_var(index={:?}, universe={:?}, diverging={:?}, origin={:?}",
260 eq_key.vid, universe, diverging, origin,
266 /// Returns the number of type variables created thus far.
267 pub fn num_vars(&self) -> usize {
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
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:
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)
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)
297 /// Retrieves the type to which `vid` has been instantiated, if
299 pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
300 self.inlined_probe(vid)
303 /// An always-inlined variant of `probe`, for very hot call sites.
305 pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
306 self.eq_relations().inlined_probe_value(vid)
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> {
314 ty::Infer(ty::TyVar(v)) => match self.probe(v) {
315 TypeVariableValue::Unknown { .. } => t,
316 TypeVariableValue::Known { value } => value,
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 }
332 ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
333 self.values.with_log(self.undo_log)
336 fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
337 self.eq_relations.with_log(self.undo_log)
340 fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
341 self.sub_relations.with_log(self.undo_log)
344 /// Returns a range of the type variables created during the snapshot.
345 pub fn vars_since_snapshot(
348 ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
350 TyVid { index: s.value_count }..TyVid { index: self.eq_relations().len() as u32 };
352 range.start..range.end,
353 (range.start.index..range.end.index)
354 .map(|index| self.values.get(index as usize).origin)
359 /// Finds the set of type variables that existed *before* `s`
360 /// but which have only been unified since `s` started, and
361 /// return the types with which they were unified. So if we had
362 /// a type variable `V0`, then we started the snapshot, then we
363 /// created a type variable `V1`, unified `V0` with `T0`, and
364 /// unified `V1` with `T1`, this function would return `{T0}`.
365 pub fn types_escaping_snapshot(&mut self, s: &super::Snapshot<'tcx>) -> Vec<Ty<'tcx>> {
366 let mut new_elem_threshold = u32::MAX;
367 let mut escaping_types = Vec::new();
368 let actions_since_snapshot = self.undo_log.actions_since_snapshot(s);
369 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
370 for i in 0..actions_since_snapshot.len() {
371 let actions_since_snapshot = self.undo_log.actions_since_snapshot(s);
372 match actions_since_snapshot[i] {
373 super::UndoLog::TypeVariables(UndoLog::Values(sv::UndoLog::NewElem(index))) => {
374 // if any new variables were created during the
375 // snapshot, remember the lower index (which will
376 // always be the first one we see). Note that this
377 // action must precede those variables being
379 new_elem_threshold = cmp::min(new_elem_threshold, index as u32);
380 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
383 super::UndoLog::TypeVariables(UndoLog::Values(sv::UndoLog::Other(
384 Instantiate { vid, .. },
386 if vid.index < new_elem_threshold {
387 // quick check to see if this variable was
388 // created since the snapshot started or not.
389 let mut eq_relations = ut::UnificationTable::with_log(
390 &mut *self.eq_relations,
393 let escaping_type = match eq_relations.probe_value(vid) {
394 TypeVariableValue::Unknown { .. } => bug!(),
395 TypeVariableValue::Known { value } => value,
397 escaping_types.push(escaping_type);
399 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
409 /// Returns indices of all variables that are not yet
411 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
412 (0..self.values.len())
414 let vid = ty::TyVid { index: i as u32 };
415 match self.probe(vid) {
416 TypeVariableValue::Unknown { .. } => Some(vid),
417 TypeVariableValue::Known { .. } => None,
424 impl sv::SnapshotVecDelegate for Delegate {
425 type Value = TypeVariableData;
426 type Undo = Instantiate;
428 fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
429 // We don't actually have to *do* anything to reverse an
430 // instantiation; the value for a variable is stored in the
431 // `eq_relations` and hence its rollback code will handle
432 // it. In fact, we could *almost* just remove the
433 // `SnapshotVec` entirely, except that we would have to
434 // reproduce *some* of its logic, since we want to know which
435 // type variables have been instantiated since the snapshot
436 // was started, so we can implement `types_escaping_snapshot`.
438 // (If we extended the `UnificationTable` to let us see which
439 // values have been unified and so forth, that might also
444 ///////////////////////////////////////////////////////////////////////////
446 /// These structs (a newtyped TyVid) are used as the unification key
447 /// for the `eq_relations`; they carry a `TypeVariableValue` along
449 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
450 pub(crate) struct TyVidEqKey<'tcx> {
453 // in the table, we map each ty-vid to one of these:
454 phantom: PhantomData<TypeVariableValue<'tcx>>,
457 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
458 fn from(vid: ty::TyVid) -> Self {
459 TyVidEqKey { vid, phantom: PhantomData }
463 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
464 type Value = TypeVariableValue<'tcx>;
465 fn index(&self) -> u32 {
468 fn from_index(i: u32) -> Self {
469 TyVidEqKey::from(ty::TyVid { index: i })
471 fn tag() -> &'static str {
476 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
477 type Error = ut::NoError;
479 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
480 match (value1, value2) {
481 // We never equate two type variables, both of which
482 // have known types. Instead, we recursively equate
484 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
485 bug!("equating two type variables, both of which have known types")
488 // If one side is known, prefer that one.
489 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
490 (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
492 // If both sides are *unknown*, it hardly matters, does it?
494 &TypeVariableValue::Unknown { universe: universe1 },
495 &TypeVariableValue::Unknown { universe: universe2 },
497 // If we unify two unbound variables, ?T and ?U, then whatever
498 // value they wind up taking (which must be the same value) must
499 // be nameable by both universes. Therefore, the resulting
500 // universe is the minimum of the two universes, because that is
501 // the one which contains the fewest names in scope.
502 let universe = cmp::min(universe1, universe2);
503 Ok(TypeVariableValue::Unknown { universe })