1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use self::TypeVariableValue::*;
12 use hir::def_id::{DefId};
18 use std::marker::PhantomData;
21 use rustc_data_structures::fx::FxHashMap;
22 use rustc_data_structures::snapshot_vec as sv;
23 use rustc_data_structures::unify as ut;
25 pub struct TypeVariableTable<'tcx> {
26 values: sv::SnapshotVec<Delegate<'tcx>>,
28 /// Two variables are unified in `eq_relations` when we have a
29 /// constraint `?X == ?Y`.
30 eq_relations: ut::UnificationTable<ty::TyVid>,
32 /// Two variables are unified in `eq_relations` when we have a
33 /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
34 /// table exists only to help with the occurs check. In particular,
35 /// we want to report constraints like these as an occurs check
41 /// This works because `?1` and `?3` are unified in the
42 /// `sub_relations` relation (not in `eq_relations`). Then when we
43 /// process the `Box<?3> <: ?1` constraint, we do an occurs check
44 /// on `Box<?3>` and find a potential cycle.
46 /// This is reasonable because, in Rust, subtypes have the same
47 /// "skeleton" and hence there is no possible type such that
48 /// (e.g.) `Box<?3> <: ?3` for any `?3`.
49 sub_relations: ut::UnificationTable<ty::TyVid>,
52 /// Reasons to create a type inference variable
53 #[derive(Copy, Clone, Debug)]
54 pub enum TypeVariableOrigin {
56 NormalizeProjectionType(Span),
58 TypeParameterDefinition(Span, ast::Name),
59 TransformedUpvar(Span),
60 SubstitutionPlaceholder(Span),
64 DivergingBlockExpr(Span),
66 LatticeVariable(Span),
67 Generalized(ty::TyVid),
70 pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
72 struct TypeVariableData<'tcx> {
73 value: TypeVariableValue<'tcx>,
74 origin: TypeVariableOrigin,
78 enum TypeVariableValue<'tcx> {
81 default: Option<Default<'tcx>>
85 // We will use this to store the required information to recapitulate what happened when
87 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
88 pub struct Default<'tcx> {
90 /// The span where the default was incurred
91 pub origin_span: Span,
92 /// The definition that the default originates from
97 snapshot: sv::Snapshot,
98 eq_snapshot: ut::Snapshot<ty::TyVid>,
99 sub_snapshot: ut::Snapshot<ty::TyVid>,
102 struct Instantiate<'tcx> {
104 default: Option<Default<'tcx>>,
107 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
109 impl<'tcx> TypeVariableTable<'tcx> {
110 pub fn new() -> TypeVariableTable<'tcx> {
112 values: sv::SnapshotVec::new(),
113 eq_relations: ut::UnificationTable::new(),
114 sub_relations: ut::UnificationTable::new(),
118 pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> {
119 match &self.values.get(vid.index as usize).value {
121 &Bounded { ref default, .. } => default.clone()
125 pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
126 self.values.get(vid.index as usize).diverging
129 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
130 &self.values.get(vid.index as usize).origin
133 /// Records that `a == b`, depending on `dir`.
135 /// Precondition: neither `a` nor `b` are known.
136 pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
137 debug_assert!(self.probe(a).is_none());
138 debug_assert!(self.probe(b).is_none());
139 self.eq_relations.union(a, b);
140 self.sub_relations.union(a, b);
143 /// Records that `a <: b`, depending on `dir`.
145 /// Precondition: neither `a` nor `b` are known.
146 pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
147 debug_assert!(self.probe(a).is_none());
148 debug_assert!(self.probe(b).is_none());
149 self.sub_relations.union(a, b);
152 /// Instantiates `vid` with the type `ty`.
154 /// Precondition: `vid` must not have been previously instantiated.
155 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
156 let vid = self.root_var(vid);
157 debug_assert!(self.probe_root(vid).is_none());
160 let vid_data = &mut self.values[vid.index as usize];
161 mem::replace(&mut vid_data.value, TypeVariableValue::Known(ty))
165 TypeVariableValue::Bounded { default } => {
166 self.values.record(Instantiate { vid: vid, default: default });
168 TypeVariableValue::Known(old_ty) => {
169 bug!("instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
175 pub fn new_var(&mut self,
177 origin: TypeVariableOrigin,
178 default: Option<Default<'tcx>>,) -> ty::TyVid {
179 debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
180 self.eq_relations.new_key(());
181 self.sub_relations.new_key(());
182 let index = self.values.push(TypeVariableData {
183 value: Bounded { default: default },
187 let v = ty::TyVid { index: index as u32 };
188 debug!("new_var: diverging={:?} index={:?}", diverging, v);
192 pub fn num_vars(&self) -> usize {
196 /// Returns the "root" variable of `vid` in the `eq_relations`
197 /// equivalence table. All type variables that have been equated
198 /// will yield the same root variable (per the union-find
199 /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
200 /// b` (transitively).
201 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
202 self.eq_relations.find(vid)
205 /// Returns the "root" variable of `vid` in the `sub_relations`
206 /// equivalence table. All type variables that have been are
207 /// related via equality or subtyping will yield the same root
208 /// variable (per the union-find algorithm), so `sub_root_var(a)
209 /// == sub_root_var(b)` implies that:
211 /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
212 pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
213 self.sub_relations.find(vid)
216 /// True if `a` and `b` have same "sub-root" (i.e., exists some
217 /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
218 pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
219 self.sub_root_var(a) == self.sub_root_var(b)
222 pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
223 let vid = self.root_var(vid);
227 pub fn origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
228 self.values.get(vid.index as usize).origin.clone()
231 /// Retrieves the type of `vid` given that it is currently a root in the unification table
232 pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
233 debug_assert!(self.root_var(vid) == vid);
234 match self.values.get(vid.index as usize).value {
235 Bounded { .. } => None,
240 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
242 ty::TyInfer(ty::TyVar(v)) => {
243 match self.probe(v) {
252 pub fn snapshot(&mut self) -> Snapshot {
254 snapshot: self.values.start_snapshot(),
255 eq_snapshot: self.eq_relations.snapshot(),
256 sub_snapshot: self.sub_relations.snapshot(),
260 pub fn rollback_to(&mut self, s: Snapshot) {
261 debug!("rollback_to{:?}", {
262 for action in self.values.actions_since_snapshot(&s.snapshot) {
264 sv::UndoLog::NewElem(index) => {
265 debug!("inference variable _#{}t popped", index)
272 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
273 self.values.rollback_to(snapshot);
274 self.eq_relations.rollback_to(eq_snapshot);
275 self.sub_relations.rollback_to(sub_snapshot);
278 pub fn commit(&mut self, s: Snapshot) {
279 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
280 self.values.commit(snapshot);
281 self.eq_relations.commit(eq_snapshot);
282 self.sub_relations.commit(sub_snapshot);
285 /// Returns a map `{V1 -> V2}`, where the keys `{V1}` are
286 /// ty-variables created during the snapshot, and the values
287 /// `{V2}` are the root variables that they were unified with,
288 /// along with their origin.
289 pub fn types_created_since_snapshot(&mut self, s: &Snapshot) -> TypeVariableMap {
290 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
292 actions_since_snapshot
294 .filter_map(|action| match action {
295 &sv::UndoLog::NewElem(index) => Some(ty::TyVid { index: index as u32 }),
299 let origin = self.values.get(vid.index as usize).origin.clone();
305 pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
307 * Find the set of type variables that existed *before* `s`
308 * but which have only been unified since `s` started, and
309 * return the types with which they were unified. So if we had
310 * a type variable `V0`, then we started the snapshot, then we
311 * created a type variable `V1`, unifed `V0` with `T0`, and
312 * unified `V1` with `T1`, this function would return `{T0}`.
315 let mut new_elem_threshold = u32::MAX;
316 let mut escaping_types = Vec::new();
317 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
318 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
319 for action in actions_since_snapshot {
321 sv::UndoLog::NewElem(index) => {
322 // if any new variables were created during the
323 // snapshot, remember the lower index (which will
324 // always be the first one we see). Note that this
325 // action must precede those variables being
327 new_elem_threshold = min(new_elem_threshold, index as u32);
328 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
331 sv::UndoLog::Other(Instantiate { vid, .. }) => {
332 if vid.index < new_elem_threshold {
333 // quick check to see if this variable was
334 // created since the snapshot started or not.
335 let escaping_type = match self.values.get(vid.index as usize).value {
336 Bounded { .. } => bug!(),
339 escaping_types.push(escaping_type);
341 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
351 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
352 (0..self.values.len())
354 let vid = ty::TyVid { index: i as u32 };
355 if self.probe(vid).is_some() {
365 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
366 type Value = TypeVariableData<'tcx>;
367 type Undo = Instantiate<'tcx>;
369 fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: Instantiate<'tcx>) {
370 let Instantiate { vid, default } = action;
371 values[vid.index as usize].value = Bounded {