1 use rustc::ty::{self, Ty, TyVid};
2 use rustc_hir::def_id::DefId;
3 use rustc_span::symbol::Symbol;
6 use rustc_data_structures::snapshot_vec as sv;
7 use rustc_data_structures::unify as ut;
9 use std::marker::PhantomData;
13 pub struct TypeVariableTable<'tcx> {
14 values: sv::SnapshotVec<Delegate>,
16 /// Two variables are unified in `eq_relations` when we have a
17 /// constraint `?X == ?Y`. This table also stores, for each key,
19 eq_relations: ut::UnificationTable<ut::InPlace<TyVidEqKey<'tcx>>>,
21 /// Two variables are unified in `sub_relations` when we have a
22 /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
23 /// table exists only to help with the occurs check. In particular,
24 /// we want to report constraints like these as an occurs check
30 /// This works because `?1` and `?3` are unified in the
31 /// `sub_relations` relation (not in `eq_relations`). Then when we
32 /// process the `Box<?3> <: ?1` constraint, we do an occurs check
33 /// on `Box<?3>` and find a potential cycle.
35 /// This is reasonable because, in Rust, subtypes have the same
36 /// "skeleton" and hence there is no possible type such that
37 /// (e.g.) `Box<?3> <: ?3` for any `?3`.
38 sub_relations: ut::UnificationTable<ut::InPlace<ty::TyVid>>,
41 #[derive(Copy, Clone, Debug)]
42 pub struct TypeVariableOrigin {
43 pub kind: TypeVariableOriginKind,
47 /// Reasons to create a type inference variable
48 #[derive(Copy, Clone, Debug)]
49 pub enum TypeVariableOriginKind {
51 NormalizeProjectionType,
53 TypeParameterDefinition(Symbol, Option<DefId>),
55 /// One of the upvars or closure kind parameters in a `ClosureSubsts`
56 /// (before it has been determined).
57 // FIXME(eddyb) distinguish upvar inference variables from the rest.
59 SubstitutionPlaceholder,
66 struct TypeVariableData {
67 origin: TypeVariableOrigin,
71 #[derive(Copy, Clone, Debug)]
72 pub enum TypeVariableValue<'tcx> {
73 Known { value: Ty<'tcx> },
74 Unknown { universe: ty::UniverseIndex },
77 impl<'tcx> TypeVariableValue<'tcx> {
78 /// If this value is known, returns the type it is known to be.
79 /// Otherwise, `None`.
80 pub fn known(&self) -> Option<Ty<'tcx>> {
82 TypeVariableValue::Unknown { .. } => None,
83 TypeVariableValue::Known { value } => Some(value),
87 pub fn is_unknown(&self) -> bool {
89 TypeVariableValue::Unknown { .. } => true,
90 TypeVariableValue::Known { .. } => false,
95 pub struct Snapshot<'tcx> {
96 snapshot: sv::Snapshot,
97 eq_snapshot: ut::Snapshot<ut::InPlace<TyVidEqKey<'tcx>>>,
98 sub_snapshot: ut::Snapshot<ut::InPlace<ty::TyVid>>,
107 impl<'tcx> TypeVariableTable<'tcx> {
108 pub fn new() -> TypeVariableTable<'tcx> {
110 values: sv::SnapshotVec::new(),
111 eq_relations: ut::UnificationTable::new(),
112 sub_relations: ut::UnificationTable::new(),
116 /// Returns the diverges flag given when `vid` was created.
118 /// Note that this function does not return care whether
119 /// `vid` has been unified with something else or not.
120 pub fn var_diverges(&self, vid: ty::TyVid) -> bool {
121 self.values.get(vid.index as usize).diverging
124 /// Returns the origin that was given when `vid` was created.
126 /// Note that this function does not return care whether
127 /// `vid` has been unified with something else or not.
128 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
129 &self.values.get(vid.index as usize).origin
132 /// Records that `a == b`, depending on `dir`.
134 /// Precondition: neither `a` nor `b` are known.
135 pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
136 debug_assert!(self.probe(a).is_unknown());
137 debug_assert!(self.probe(b).is_unknown());
138 self.eq_relations.union(a, b);
139 self.sub_relations.union(a, b);
142 /// Records that `a <: b`, depending on `dir`.
144 /// Precondition: neither `a` nor `b` are known.
145 pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
146 debug_assert!(self.probe(a).is_unknown());
147 debug_assert!(self.probe(b).is_unknown());
148 self.sub_relations.union(a, b);
151 /// Instantiates `vid` with the type `ty`.
153 /// Precondition: `vid` must not have been previously instantiated.
154 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
155 let vid = self.root_var(vid);
156 debug_assert!(self.probe(vid).is_unknown());
158 self.eq_relations.probe_value(vid).is_unknown(),
159 "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
162 self.eq_relations.probe_value(vid)
164 self.eq_relations.union_value(vid, TypeVariableValue::Known { value: ty });
166 // Hack: we only need this so that `types_escaping_snapshot`
167 // can see what has been unified; see the Delegate impl for
169 self.values.record(Instantiate { vid });
172 /// Creates a new type variable.
174 /// - `diverging`: indicates if this is a "diverging" type
175 /// variable, e.g., one created as the type of a `return`
176 /// expression. The code in this module doesn't care if a
177 /// variable is diverging, but the main Rust type-checker will
178 /// sometimes "unify" such variables with the `!` or `()` types.
179 /// - `origin`: indicates *why* the type variable was created.
180 /// The code in this module doesn't care, but it can be useful
181 /// for improving error messages.
184 universe: ty::UniverseIndex,
186 origin: TypeVariableOrigin,
188 let eq_key = self.eq_relations.new_key(TypeVariableValue::Unknown { universe });
190 let sub_key = self.sub_relations.new_key(());
191 assert_eq!(eq_key.vid, sub_key);
193 let index = self.values.push(TypeVariableData { origin, diverging });
194 assert_eq!(eq_key.vid.index, index as u32);
197 "new_var(index={:?}, universe={:?}, diverging={:?}, origin={:?}",
198 eq_key.vid, universe, diverging, origin,
204 /// Returns the number of type variables created thus far.
205 pub fn num_vars(&self) -> usize {
209 /// Returns the "root" variable of `vid` in the `eq_relations`
210 /// equivalence table. All type variables that have been equated
211 /// will yield the same root variable (per the union-find
212 /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
213 /// b` (transitively).
214 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
215 self.eq_relations.find(vid).vid
218 /// Returns the "root" variable of `vid` in the `sub_relations`
219 /// equivalence table. All type variables that have been are
220 /// related via equality or subtyping will yield the same root
221 /// variable (per the union-find algorithm), so `sub_root_var(a)
222 /// == sub_root_var(b)` implies that:
224 /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
225 pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
226 self.sub_relations.find(vid)
229 /// Returns `true` if `a` and `b` have same "sub-root" (i.e., exists some
230 /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
231 pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
232 self.sub_root_var(a) == self.sub_root_var(b)
235 /// Retrieves the type to which `vid` has been instantiated, if
237 pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
238 self.inlined_probe(vid)
241 /// An always-inlined variant of `probe`, for very hot call sites.
243 pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
244 self.eq_relations.inlined_probe_value(vid)
247 /// If `t` is a type-inference variable, and it has been
248 /// instantiated, then return the with which it was
249 /// instantiated. Otherwise, returns `t`.
250 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
252 ty::Infer(ty::TyVar(v)) => match self.probe(v) {
253 TypeVariableValue::Unknown { .. } => t,
254 TypeVariableValue::Known { value } => value,
260 /// Creates a snapshot of the type variable state. This snapshot
261 /// must later be committed (`commit()`) or rolled back
262 /// (`rollback_to()`). Nested snapshots are permitted, but must
263 /// be processed in a stack-like fashion.
264 pub fn snapshot(&mut self) -> Snapshot<'tcx> {
266 snapshot: self.values.start_snapshot(),
267 eq_snapshot: self.eq_relations.snapshot(),
268 sub_snapshot: self.sub_relations.snapshot(),
272 /// Undoes all changes since the snapshot was created. Any
273 /// snapshots created since that point must already have been
274 /// committed or rolled back.
275 pub fn rollback_to(&mut self, s: Snapshot<'tcx>) {
276 debug!("rollback_to{:?}", {
277 for action in self.values.actions_since_snapshot(&s.snapshot) {
278 if let sv::UndoLog::NewElem(index) = *action {
279 debug!("inference variable _#{}t popped", index)
284 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
285 self.values.rollback_to(snapshot);
286 self.eq_relations.rollback_to(eq_snapshot);
287 self.sub_relations.rollback_to(sub_snapshot);
290 /// Commits all changes since the snapshot was created, making
291 /// them permanent (unless this snapshot was created within
292 /// another snapshot). Any snapshots created since that point
293 /// must already have been committed or rolled back.
294 pub fn commit(&mut self, s: Snapshot<'tcx>) {
295 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
296 self.values.commit(snapshot);
297 self.eq_relations.commit(eq_snapshot);
298 self.sub_relations.commit(sub_snapshot);
301 /// Returns a range of the type variables created during the snapshot.
302 pub fn vars_since_snapshot(
305 ) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
306 let range = self.eq_relations.vars_since_snapshot(&s.eq_snapshot);
308 range.start.vid..range.end.vid,
309 (range.start.vid.index..range.end.vid.index)
310 .map(|index| self.values.get(index as usize).origin)
315 /// Finds the set of type variables that existed *before* `s`
316 /// but which have only been unified since `s` started, and
317 /// return the types with which they were unified. So if we had
318 /// a type variable `V0`, then we started the snapshot, then we
319 /// created a type variable `V1`, unified `V0` with `T0`, and
320 /// unified `V1` with `T1`, this function would return `{T0}`.
321 pub fn types_escaping_snapshot(&mut self, s: &Snapshot<'tcx>) -> Vec<Ty<'tcx>> {
322 let mut new_elem_threshold = u32::MAX;
323 let mut escaping_types = Vec::new();
324 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
325 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
326 for action in actions_since_snapshot {
328 sv::UndoLog::NewElem(index) => {
329 // if any new variables were created during the
330 // snapshot, remember the lower index (which will
331 // always be the first one we see). Note that this
332 // action must precede those variables being
334 new_elem_threshold = cmp::min(new_elem_threshold, index as u32);
335 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
338 sv::UndoLog::Other(Instantiate { vid, .. }) => {
339 if vid.index < new_elem_threshold {
340 // quick check to see if this variable was
341 // created since the snapshot started or not.
342 let escaping_type = match self.eq_relations.probe_value(vid) {
343 TypeVariableValue::Unknown { .. } => bug!(),
344 TypeVariableValue::Known { value } => value,
346 escaping_types.push(escaping_type);
348 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
358 /// Returns indices of all variables that are not yet
360 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
361 (0..self.values.len())
363 let vid = ty::TyVid { index: i as u32 };
364 match self.probe(vid) {
365 TypeVariableValue::Unknown { .. } => Some(vid),
366 TypeVariableValue::Known { .. } => None,
373 impl sv::SnapshotVecDelegate for Delegate {
374 type Value = TypeVariableData;
375 type Undo = Instantiate;
377 fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
378 // We don't actually have to *do* anything to reverse an
379 // instantiation; the value for a variable is stored in the
380 // `eq_relations` and hence its rollback code will handle
381 // it. In fact, we could *almost* just remove the
382 // `SnapshotVec` entirely, except that we would have to
383 // reproduce *some* of its logic, since we want to know which
384 // type variables have been instantiated since the snapshot
385 // was started, so we can implement `types_escaping_snapshot`.
387 // (If we extended the `UnificationTable` to let us see which
388 // values have been unified and so forth, that might also
393 ///////////////////////////////////////////////////////////////////////////
395 /// These structs (a newtyped TyVid) are used as the unification key
396 /// for the `eq_relations`; they carry a `TypeVariableValue` along
398 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
399 struct TyVidEqKey<'tcx> {
402 // in the table, we map each ty-vid to one of these:
403 phantom: PhantomData<TypeVariableValue<'tcx>>,
406 impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
407 fn from(vid: ty::TyVid) -> Self {
408 TyVidEqKey { vid, phantom: PhantomData }
412 impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
413 type Value = TypeVariableValue<'tcx>;
414 fn index(&self) -> u32 {
417 fn from_index(i: u32) -> Self {
418 TyVidEqKey::from(ty::TyVid { index: i })
420 fn tag() -> &'static str {
425 impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
426 type Error = ut::NoError;
428 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
429 match (value1, value2) {
430 // We never equate two type variables, both of which
431 // have known types. Instead, we recursively equate
433 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
434 bug!("equating two type variables, both of which have known types")
437 // If one side is known, prefer that one.
438 (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
439 (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
441 // If both sides are *unknown*, it hardly matters, does it?
443 &TypeVariableValue::Unknown { universe: universe1 },
444 &TypeVariableValue::Unknown { universe: universe2 },
446 // If we unify two unbound variables, ?T and ?U, then whatever
447 // value they wind up taking (which must be the same value) must
448 // be nameable by both universes. Therefore, the resulting
449 // universe is the minimum of the two universes, because that is
450 // the one which contains the fewest names in scope.
451 let universe = cmp::min(universe1, universe2);
452 Ok(TypeVariableValue::Unknown { universe })