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.
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>),
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)
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)
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 {
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))
52 impl<'tcx> Rollback<UndoLog<'tcx>> for TypeVariableStorage<'tcx> {
53 fn reverse(&mut self, undo: UndoLog<'tcx>) {
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),
63 pub struct TypeVariableStorage<'tcx> {
64 values: sv::SnapshotVecStorage<Delegate>,
66 /// Two variables are unified in `eq_relations` when we have a
67 /// constraint `?X == ?Y`. This table also stores, for each key,
69 eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
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
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`.)
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.
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`.
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>,
107 pub struct TypeVariableTable<'a, 'tcx> {
108 storage: &'a mut TypeVariableStorage<'tcx>,
110 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
113 #[derive(Copy, Clone, Debug)]
114 pub struct TypeVariableOrigin {
115 pub kind: TypeVariableOriginKind,
119 /// Reasons to create a type inference variable
120 #[derive(Copy, Clone, Debug)]
121 pub enum TypeVariableOriginKind {
123 NormalizeProjectionType,
125 OpaqueTypeInference(DefId),
126 TypeParameterDefinition(Symbol, Option<DefId>),
128 /// One of the upvars or closure kind parameters in a `ClosureSubsts`
129 /// (before it has been determined).
130 // FIXME(eddyb) distinguish upvar inference variables from the rest.
132 SubstitutionPlaceholder,
136 /// In type check, when we are type checking a function that
137 /// returns `-> dyn Foo`, we substitute a type variable for the
138 /// return type for diagnostic purposes.
144 pub(crate) struct TypeVariableData {
145 origin: TypeVariableOrigin,
148 #[derive(Copy, Clone, Debug)]
149 pub enum TypeVariableValue<'tcx> {
150 Known { value: Ty<'tcx> },
151 Unknown { universe: ty::UniverseIndex },
154 impl<'tcx> TypeVariableValue<'tcx> {
155 /// If this value is known, returns the type it is known to be.
156 /// Otherwise, `None`.
157 pub fn known(&self) -> Option<Ty<'tcx>> {
159 TypeVariableValue::Unknown { .. } => None,
160 TypeVariableValue::Known { value } => Some(value),
164 pub fn is_unknown(&self) -> bool {
166 TypeVariableValue::Unknown { .. } => true,
167 TypeVariableValue::Known { .. } => false,
173 pub(crate) struct Instantiate;
175 pub(crate) struct Delegate;
177 impl<'tcx> TypeVariableStorage<'tcx> {
178 pub fn new() -> TypeVariableStorage<'tcx> {
179 TypeVariableStorage {
180 values: sv::SnapshotVecStorage::new(),
181 eq_relations: ut::UnificationTableStorage::new(),
182 sub_relations: ut::UnificationTableStorage::new(),
187 pub(crate) fn with_log<'a>(
189 undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
190 ) -> TypeVariableTable<'a, 'tcx> {
191 TypeVariableTable { storage: self, undo_log }
195 impl<'tcx> TypeVariableTable<'_, 'tcx> {
196 /// Returns the origin that was given when `vid` was created.
198 /// Note that this function does not return care whether
199 /// `vid` has been unified with something else or not.
200 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
201 &self.storage.values.get(vid.as_usize()).origin
204 /// Records that `a == b`, depending on `dir`.
206 /// Precondition: neither `a` nor `b` are known.
207 pub fn equate(&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.eq_relations().union(a, b);
211 self.sub_relations().union(a, b);
214 /// Records that `a <: b`, depending on `dir`.
216 /// Precondition: neither `a` nor `b` are known.
217 pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
218 debug_assert!(self.probe(a).is_unknown());
219 debug_assert!(self.probe(b).is_unknown());
220 self.sub_relations().union(a, b);
223 /// Instantiates `vid` with the type `ty`.
225 /// Precondition: `vid` must not have been previously instantiated.
226 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
227 let vid = self.root_var(vid);
228 debug_assert!(self.probe(vid).is_unknown());
230 self.eq_relations().probe_value(vid).is_unknown(),
231 "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
234 self.eq_relations().probe_value(vid)
236 self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
238 // Hack: we only need this so that `types_escaping_snapshot`
239 // can see what has been unified; see the Delegate impl for
241 self.undo_log.push(Instantiate);
244 /// Creates a new type variable.
246 /// - `diverging`: indicates if this is a "diverging" type
247 /// variable, e.g., one created as the type of a `return`
248 /// expression. The code in this module doesn't care if a
249 /// variable is diverging, but the main Rust type-checker will
250 /// sometimes "unify" such variables with the `!` or `()` types.
251 /// - `origin`: indicates *why* the type variable was created.
252 /// The code in this module doesn't care, but it can be useful
253 /// for improving error messages.
256 universe: ty::UniverseIndex,
257 origin: TypeVariableOrigin,
259 let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
261 let sub_key = self.sub_relations().new_key(());
262 assert_eq!(eq_key.vid, sub_key);
264 let index = self.values().push(TypeVariableData { origin });
265 assert_eq!(eq_key.vid.as_u32(), index as u32);
267 debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin);
272 /// Returns the number of type variables created thus far.
273 pub fn num_vars(&self) -> usize {
274 self.storage.values.len()
277 /// Returns the "root" variable of `vid` in the `eq_relations`
278 /// equivalence table. All type variables that have been equated
279 /// will yield the same root variable (per the union-find
280 /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
281 /// b` (transitively).
282 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
283 self.eq_relations().find(vid).vid
286 /// Returns the "root" variable of `vid` in the `sub_relations`
287 /// equivalence table. All type variables that have been are
288 /// related via equality or subtyping will yield the same root
289 /// variable (per the union-find algorithm), so `sub_root_var(a)
290 /// == sub_root_var(b)` implies that:
292 /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
294 pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
295 self.sub_relations().find(vid)
298 /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
299 /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
300 pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
301 self.sub_root_var(a) == self.sub_root_var(b)
304 /// Retrieves the type to which `vid` has been instantiated, if
306 pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
307 self.inlined_probe(vid)
310 /// An always-inlined variant of `probe`, for very hot call sites.
312 pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
313 self.eq_relations().inlined_probe_value(vid)
316 /// If `t` is a type-inference variable, and it has been
317 /// instantiated, then return the with which it was
318 /// instantiated. Otherwise, returns `t`.
319 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
321 ty::Infer(ty::TyVar(v)) => match self.probe(v) {
322 TypeVariableValue::Unknown { .. } => t,
323 TypeVariableValue::Known { value } => value,
332 ) -> sv::SnapshotVec<Delegate, &mut Vec<TypeVariableData>, &mut InferCtxtUndoLogs<'tcx>> {
333 self.storage.values.with_log(self.undo_log)
337 fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
338 self.storage.eq_relations.with_log(self.undo_log)
342 fn sub_relations(&mut self) -> super::UnificationTable<'_, 'tcx, ty::TyVid> {
343 self.storage.sub_relations.with_log(self.undo_log)
346 /// Returns a range of the type variables created during the snapshot.
347 pub fn vars_since_snapshot(
350 ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
351 let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
353 range.start..range.end,
354 (range.start.as_usize()..range.end.as_usize())
355 .map(|index| self.storage.values.get(index).origin)
360 /// Returns indices of all variables that are not yet
362 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
363 (0..self.storage.values.len())
365 let vid = ty::TyVid::from_usize(i);
366 match self.probe(vid) {
367 TypeVariableValue::Unknown { .. } => Some(vid),
368 TypeVariableValue::Known { .. } => None,
375 impl sv::SnapshotVecDelegate for Delegate {
376 type Value = TypeVariableData;
377 type Undo = Instantiate;
379 fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
380 // We don't actually have to *do* anything to reverse an
381 // instantiation; the value for a variable is stored in the
382 // `eq_relations` and hence its rollback code will handle
383 // it. In fact, we could *almost* just remove the
384 // `SnapshotVec` entirely, except that we would have to
385 // reproduce *some* of its logic, since we want to know which
386 // type variables have been instantiated since the snapshot
387 // was started, so we can implement `types_escaping_snapshot`.
389 // (If we extended the `UnificationTable` to let us see which
390 // values have been unified and so forth, that might also
395 ///////////////////////////////////////////////////////////////////////////
397 /// These structs (a newtyped TyVid) are used as the unification key
398 /// for the `eq_relations`; they carry a `TypeVariableValue` along
400 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
401 pub(crate) struct TyVidEqKey<'tcx> {
404 // in the table, we map each ty-vid to one of these:
405 phantom: PhantomData<TypeVariableValue<'tcx>>,
408 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
409 #[inline] // make this function eligible for inlining - it is quite hot.
410 fn from(vid: ty::TyVid) -> Self {
411 TyVidEqKey { vid, phantom: PhantomData }
415 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
416 type Value = TypeVariableValue<'tcx>;
418 fn index(&self) -> u32 {
422 fn from_index(i: u32) -> Self {
423 TyVidEqKey::from(ty::TyVid::from_u32(i))
425 fn tag() -> &'static str {
430 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
431 type Error = ut::NoError;
433 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
434 match (value1, value2) {
435 // We never equate two type variables, both of which
436 // have known types. Instead, we recursively equate
438 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
439 bug!("equating two type variables, both of which have known types")
442 // If one side is known, prefer that one.
443 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
444 (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
446 // If both sides are *unknown*, it hardly matters, does it?
448 &TypeVariableValue::Unknown { universe: universe1 },
449 &TypeVariableValue::Unknown { universe: universe2 },
451 // If we unify two unbound variables, ?T and ?U, then whatever
452 // value they wind up taking (which must be the same value) must
453 // be nameable by both universes. Therefore, the resulting
454 // universe is the minimum of the two universes, because that is
455 // the one which contains the fewest names in scope.
456 let universe = cmp::min(universe1, universe2);
457 Ok(TypeVariableValue::Unknown { universe })