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),
60 /// one of the upvars or closure kind parameters in a `ClosureSubsts`
61 /// (before it has been determined)
62 ClosureSynthetic(Span),
63 SubstitutionPlaceholder(Span),
67 DivergingBlockExpr(Span),
69 LatticeVariable(Span),
70 Generalized(ty::TyVid),
73 pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
75 struct TypeVariableData<'tcx> {
76 value: TypeVariableValue<'tcx>,
77 origin: TypeVariableOrigin,
81 enum TypeVariableValue<'tcx> {
84 default: Option<Default<'tcx>>
88 // We will use this to store the required information to recapitulate what happened when
90 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
91 pub struct Default<'tcx> {
93 /// The span where the default was incurred
94 pub origin_span: Span,
95 /// The definition that the default originates from
100 snapshot: sv::Snapshot,
101 eq_snapshot: ut::Snapshot<ty::TyVid>,
102 sub_snapshot: ut::Snapshot<ty::TyVid>,
105 struct Instantiate<'tcx> {
107 default: Option<Default<'tcx>>,
110 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
112 impl<'tcx> TypeVariableTable<'tcx> {
113 pub fn new() -> TypeVariableTable<'tcx> {
115 values: sv::SnapshotVec::new(),
116 eq_relations: ut::UnificationTable::new(),
117 sub_relations: ut::UnificationTable::new(),
121 pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> {
122 match &self.values.get(vid.index as usize).value {
124 &Bounded { ref default, .. } => default.clone()
128 pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
129 self.values.get(vid.index as usize).diverging
132 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
133 &self.values.get(vid.index as usize).origin
136 /// Records that `a == b`, depending on `dir`.
138 /// Precondition: neither `a` nor `b` are known.
139 pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
140 debug_assert!(self.probe(a).is_none());
141 debug_assert!(self.probe(b).is_none());
142 self.eq_relations.union(a, b);
143 self.sub_relations.union(a, b);
146 /// Records that `a <: b`, depending on `dir`.
148 /// Precondition: neither `a` nor `b` are known.
149 pub fn sub(&mut self, a: ty::TyVid, b: ty::TyVid) {
150 debug_assert!(self.probe(a).is_none());
151 debug_assert!(self.probe(b).is_none());
152 self.sub_relations.union(a, b);
155 /// Instantiates `vid` with the type `ty`.
157 /// Precondition: `vid` must not have been previously instantiated.
158 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
159 let vid = self.root_var(vid);
160 debug_assert!(self.probe_root(vid).is_none());
163 let vid_data = &mut self.values[vid.index as usize];
164 mem::replace(&mut vid_data.value, TypeVariableValue::Known(ty))
168 TypeVariableValue::Bounded { default } => {
169 self.values.record(Instantiate { vid: vid, default: default });
171 TypeVariableValue::Known(old_ty) => {
172 bug!("instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
178 pub fn new_var(&mut self,
180 origin: TypeVariableOrigin,
181 default: Option<Default<'tcx>>,) -> ty::TyVid {
182 debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
183 self.eq_relations.new_key(());
184 self.sub_relations.new_key(());
185 let index = self.values.push(TypeVariableData {
186 value: Bounded { default: default },
190 let v = ty::TyVid { index: index as u32 };
191 debug!("new_var: diverging={:?} index={:?}", diverging, v);
195 pub fn num_vars(&self) -> usize {
199 /// Returns the "root" variable of `vid` in the `eq_relations`
200 /// equivalence table. All type variables that have been equated
201 /// will yield the same root variable (per the union-find
202 /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
203 /// b` (transitively).
204 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
205 self.eq_relations.find(vid)
208 /// Returns the "root" variable of `vid` in the `sub_relations`
209 /// equivalence table. All type variables that have been are
210 /// related via equality or subtyping will yield the same root
211 /// variable (per the union-find algorithm), so `sub_root_var(a)
212 /// == sub_root_var(b)` implies that:
214 /// exists X. (a <: X || X <: a) && (b <: X || X <: b)
215 pub fn sub_root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
216 self.sub_relations.find(vid)
219 /// True if `a` and `b` have same "sub-root" (i.e., exists some
220 /// type X such that `forall i in {a, b}. (i <: X || X <: i)`.
221 pub fn sub_unified(&mut self, a: ty::TyVid, b: ty::TyVid) -> bool {
222 self.sub_root_var(a) == self.sub_root_var(b)
225 pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
226 let vid = self.root_var(vid);
230 pub fn origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
231 self.values.get(vid.index as usize).origin.clone()
234 /// Retrieves the type of `vid` given that it is currently a root in the unification table
235 pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
236 debug_assert!(self.root_var(vid) == vid);
237 match self.values.get(vid.index as usize).value {
238 Bounded { .. } => None,
243 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
245 ty::TyInfer(ty::TyVar(v)) => {
246 match self.probe(v) {
255 pub fn snapshot(&mut self) -> Snapshot {
257 snapshot: self.values.start_snapshot(),
258 eq_snapshot: self.eq_relations.snapshot(),
259 sub_snapshot: self.sub_relations.snapshot(),
263 pub fn rollback_to(&mut self, s: Snapshot) {
264 debug!("rollback_to{:?}", {
265 for action in self.values.actions_since_snapshot(&s.snapshot) {
267 sv::UndoLog::NewElem(index) => {
268 debug!("inference variable _#{}t popped", index)
275 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
276 self.values.rollback_to(snapshot);
277 self.eq_relations.rollback_to(eq_snapshot);
278 self.sub_relations.rollback_to(sub_snapshot);
281 pub fn commit(&mut self, s: Snapshot) {
282 let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
283 self.values.commit(snapshot);
284 self.eq_relations.commit(eq_snapshot);
285 self.sub_relations.commit(sub_snapshot);
288 /// Returns a map `{V1 -> V2}`, where the keys `{V1}` are
289 /// ty-variables created during the snapshot, and the values
290 /// `{V2}` are the root variables that they were unified with,
291 /// along with their origin.
292 pub fn types_created_since_snapshot(&mut self, s: &Snapshot) -> TypeVariableMap {
293 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
295 actions_since_snapshot
297 .filter_map(|action| match action {
298 &sv::UndoLog::NewElem(index) => Some(ty::TyVid { index: index as u32 }),
302 let origin = self.values.get(vid.index as usize).origin.clone();
308 pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
310 * Find the set of type variables that existed *before* `s`
311 * but which have only been unified since `s` started, and
312 * return the types with which they were unified. So if we had
313 * a type variable `V0`, then we started the snapshot, then we
314 * created a type variable `V1`, unifed `V0` with `T0`, and
315 * unified `V1` with `T1`, this function would return `{T0}`.
318 let mut new_elem_threshold = u32::MAX;
319 let mut escaping_types = Vec::new();
320 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
321 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
322 for action in actions_since_snapshot {
324 sv::UndoLog::NewElem(index) => {
325 // if any new variables were created during the
326 // snapshot, remember the lower index (which will
327 // always be the first one we see). Note that this
328 // action must precede those variables being
330 new_elem_threshold = min(new_elem_threshold, index as u32);
331 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
334 sv::UndoLog::Other(Instantiate { vid, .. }) => {
335 if vid.index < new_elem_threshold {
336 // quick check to see if this variable was
337 // created since the snapshot started or not.
338 let escaping_type = match self.values.get(vid.index as usize).value {
339 Bounded { .. } => bug!(),
342 escaping_types.push(escaping_type);
344 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
354 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
355 (0..self.values.len())
357 let vid = ty::TyVid { index: i as u32 };
358 if self.probe(vid).is_some() {
368 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
369 type Value = TypeVariableData<'tcx>;
370 type Undo = Instantiate<'tcx>;
372 fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: Instantiate<'tcx>) {
373 let Instantiate { vid, default } = action;
374 values[vid.index as usize].value = Bounded {