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 /// 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>),
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)
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)
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 {
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))
51 impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> {
52 fn reverse(&mut self, undo: UndoLog<'tcx>) {
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),
61 pub struct TypeVariableStorage<'tcx> {
62 values: sv::SnapshotVecStorage<Delegate>,
64 /// Two variables are unified in `eq_relations` when we have a
65 /// constraint `?X == ?Y`. This table also stores, for each key,
67 eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
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
78 /// This works because `?1` and `?3` are unified in the
79 /// `sub_relations` relation (not in `eq_relations`). Then when we
80 /// process the `Box<?3> <: ?1` constraint, we do an occurs check
81 /// on `Box<?3>` and find a potential cycle.
83 /// This is reasonable because, in Rust, subtypes have the same
84 /// "skeleton" and hence there is no possible type such that
85 /// (e.g.) `Box<?3> <: ?3` for any `?3`.
86 sub_relations: ut::UnificationTableStorage<ty::TyVid>,
89 pub struct TypeVariableTable<'a, 'tcx> {
90 storage: &'a mut TypeVariableStorage<'tcx>,
92 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
95 #[derive(Copy, Clone, Debug)]
96 pub struct TypeVariableOrigin {
97 pub kind: TypeVariableOriginKind,
101 /// Reasons to create a type inference variable
102 #[derive(Copy, Clone, Debug)]
103 pub enum TypeVariableOriginKind {
105 NormalizeProjectionType,
107 TypeParameterDefinition(Symbol, Option<DefId>),
109 /// One of the upvars or closure kind parameters in a `ClosureSubsts`
110 /// (before it has been determined).
111 // FIXME(eddyb) distinguish upvar inference variables from the rest.
113 SubstitutionPlaceholder,
120 pub(crate) struct TypeVariableData {
121 origin: TypeVariableOrigin,
125 #[derive(Copy, Clone, Debug)]
126 pub enum TypeVariableValue<'tcx> {
127 Known { value: Ty<'tcx> },
128 Unknown { universe: ty::UniverseIndex },
131 impl<'tcx> TypeVariableValue<'tcx> {
132 /// If this value is known, returns the type it is known to be.
133 /// Otherwise, `None`.
134 pub fn known(&self) -> Option<Ty<'tcx>> {
136 TypeVariableValue::Unknown { .. } => None,
137 TypeVariableValue::Known { value } => Some(value),
141 pub fn is_unknown(&self) -> bool {
143 TypeVariableValue::Unknown { .. } => true,
144 TypeVariableValue::Known { .. } => false,
149 pub(crate) struct Instantiate;
151 pub(crate) struct Delegate;
153 impl<'tcx> TypeVariableStorage<'tcx> {
154 pub fn new() -> TypeVariableStorage<'tcx> {
155 TypeVariableStorage {
156 values: sv::SnapshotVecStorage::new(),
157 eq_relations: ut::UnificationTableStorage::new(),
158 sub_relations: ut::UnificationTableStorage::new(),
163 pub(crate) fn with_log<'a>(
165 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
166 ) -> TypeVariableTable<'a, 'tcx> {
167 TypeVariableTable { storage: self, undo_log }
171 impl<'tcx> TypeVariableTable<'_, 'tcx> {
172 /// Returns the diverges flag given when `vid` was created.
174 /// Note that this function does not return care whether
175 /// `vid` has been unified with something else or not.
176 pub fn var_diverges(&self, vid: ty::TyVid) -> bool {
177 self.storage.values.get(vid.index as usize).diverging
180 /// Returns the origin that was given when `vid` was created.
182 /// Note that this function does not return care whether
183 /// `vid` has been unified with something else or not.
184 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
185 &self.storage.values.get(vid.index as usize).origin
188 /// Records that `a == b`, depending on `dir`.
190 /// Precondition: neither `a` nor `b` are known.
191 pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
192 debug_assert!(self.probe(a).is_unknown());
193 debug_assert!(self.probe(b).is_unknown());
194 self.eq_relations().union(a, b);
195 self.sub_relations().union(a, b);
198 /// Records that `a <: b`, depending on `dir`.
200 /// Precondition: neither `a` nor `b` are known.
201 pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
202 debug_assert!(self.probe(a).is_unknown());
203 debug_assert!(self.probe(b).is_unknown());
204 self.sub_relations().union(a, b);
207 /// Instantiates `vid` with the type `ty`.
209 /// Precondition: `vid` must not have been previously instantiated.
210 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
211 let vid = self.root_var(vid);
212 debug_assert!(self.probe(vid).is_unknown());
214 self.eq_relations().probe_value(vid).is_unknown(),
215 "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
218 self.eq_relations().probe_value(vid)
220 self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
222 // Hack: we only need this so that `types_escaping_snapshot`
223 // can see what has been unified; see the Delegate impl for
225 self.undo_log.push(Instantiate);
228 /// Creates a new type variable.
230 /// - `diverging`: indicates if this is a "diverging" type
231 /// variable, e.g., one created as the type of a `return`
232 /// expression. The code in this module doesn't care if a
233 /// variable is diverging, but the main Rust type-checker will
234 /// sometimes "unify" such variables with the `!` or `()` types.
235 /// - `origin`: indicates *why* the type variable was created.
236 /// The code in this module doesn't care, but it can be useful
237 /// for improving error messages.
240 universe: ty::UniverseIndex,
242 origin: TypeVariableOrigin,
244 let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
246 let sub_key = self.sub_relations().new_key(());
247 assert_eq!(eq_key.vid, sub_key);
249 let index = self.values().push(TypeVariableData { origin, diverging });
250 assert_eq!(eq_key.vid.index, index as u32);
253 "new_var(index={:?}, universe={:?}, diverging={:?}, origin={:?}",
254 eq_key.vid, universe, diverging, origin,
260 /// Returns the number of type variables created thus far.
261 pub fn num_vars(&self) -> usize {
262 self.storage.values.len()
265 /// Returns the "root" variable of `vid` in the `eq_relations`
266 /// equivalence table. All type variables that have been equated
267 /// will yield the same root variable (per the union-find
268 /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
269 /// b` (transitively).
270 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
271 self.eq_relations().find(vid).vid
274 /// Returns the "root" variable of `vid` in the `sub_relations`
275 /// equivalence table. All type variables that have been are
276 /// related via equality or subtyping will yield the same root
277 /// variable (per the union-find algorithm), so `sub_root_var(a)
278 /// == sub_root_var(b)` implies that:
280 /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
281 pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
282 self.sub_relations().find(vid)
285 /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
286 /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
287 pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
288 self.sub_root_var(a) == self.sub_root_var(b)
291 /// Retrieves the type to which `vid` has been instantiated, if
293 pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
294 self.inlined_probe(vid)
297 /// An always-inlined variant of `probe`, for very hot call sites.
299 pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
300 self.eq_relations().inlined_probe_value(vid)
303 /// If `t` is a type-inference variable, and it has been
304 /// instantiated, then return the with which it was
305 /// instantiated. Otherwise, returns `t`.
306 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
308 ty::Infer(ty::TyVar(v)) => match self.probe(v) {
309 TypeVariableValue::Unknown { .. } => t,
310 TypeVariableValue::Known { value } => value,
319 ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
320 self.storage.values.with_log(self.undo_log)
324 fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
325 self.storage.eq_relations.with_log(self.undo_log)
329 fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
330 self.storage.sub_relations.with_log(self.undo_log)
333 /// Returns a range of the type variables created during the snapshot.
334 pub fn vars_since_snapshot(
337 ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
338 let range = TyVid { index: value_count as u32 }..TyVid { index: self.num_vars() as u32 };
340 range.start..range.end,
341 (range.start.index..range.end.index)
342 .map(|index| self.storage.values.get(index as usize).origin)
347 /// Returns indices of all variables that are not yet
349 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
350 (0..self.storage.values.len())
352 let vid = ty::TyVid { index: i as u32 };
353 match self.probe(vid) {
354 TypeVariableValue::Unknown { .. } => Some(vid),
355 TypeVariableValue::Known { .. } => None,
362 impl sv::SnapshotVecDelegate for Delegate {
363 type Value = TypeVariableData;
364 type Undo = Instantiate;
366 fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
367 // We don't actually have to *do* anything to reverse an
368 // instantiation; the value for a variable is stored in the
369 // `eq_relations` and hence its rollback code will handle
370 // it. In fact, we could *almost* just remove the
371 // `SnapshotVec` entirely, except that we would have to
372 // reproduce *some* of its logic, since we want to know which
373 // type variables have been instantiated since the snapshot
374 // was started, so we can implement `types_escaping_snapshot`.
376 // (If we extended the `UnificationTable` to let us see which
377 // values have been unified and so forth, that might also
382 ///////////////////////////////////////////////////////////////////////////
384 /// These structs (a newtyped TyVid) are used as the unification key
385 /// for the `eq_relations`; they carry a `TypeVariableValue` along
387 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
388 pub(crate) struct TyVidEqKey<'tcx> {
391 // in the table, we map each ty-vid to one of these:
392 phantom: PhantomData<TypeVariableValue<'tcx>>,
395 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
396 fn from(vid: ty::TyVid) -> Self {
397 TyVidEqKey { vid, phantom: PhantomData }
401 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
402 type Value = TypeVariableValue<'tcx>;
403 fn index(&self) -> u32 {
406 fn from_index(i: u32) -> Self {
407 TyVidEqKey::from(ty::TyVid { index: i })
409 fn tag() -> &'static str {
414 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
415 type Error = ut::NoError;
417 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
418 match (value1, value2) {
419 // We never equate two type variables, both of which
420 // have known types. Instead, we recursively equate
422 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
423 bug!("equating two type variables, both of which have known types")
426 // If one side is known, prefer that one.
427 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
428 (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
430 // If both sides are *unknown*, it hardly matters, does it?
432 &TypeVariableValue::Unknown { universe: universe1 },
433 &TypeVariableValue::Unknown { universe: universe2 },
435 // If we unify two unbound variables, ?T and ?U, then whatever
436 // value they wind up taking (which must be the same value) must
437 // be nameable by both universes. Therefore, the resulting
438 // universe is the minimum of the two universes, because that is
439 // the one which contains the fewest names in scope.
440 let universe = cmp::min(universe1, universe2);
441 Ok(TypeVariableValue::Unknown { universe })