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::snapshot_vec as sv;
22 use rustc_data_structures::unify as ut;
24 pub struct TypeVariableTable<'tcx> {
25 values: sv::SnapshotVec<Delegate<'tcx>>,
26 eq_relations: ut::UnificationTable<ty::TyVid>,
29 /// Reasons to create a type inference variable
31 pub enum TypeVariableOrigin {
33 NormalizeProjectionType(Span),
35 TypeParameterDefinition(Span, ast::Name),
36 TransformedUpvar(Span),
37 SubstitutionPlaceholder(Span),
41 DivergingBlockExpr(Span),
43 LatticeVariable(Span),
46 struct TypeVariableData<'tcx> {
47 value: TypeVariableValue<'tcx>,
48 origin: TypeVariableOrigin,
52 enum TypeVariableValue<'tcx> {
55 default: Option<Default<'tcx>>
59 // We will use this to store the required information to recapitulate what happened when
61 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
62 pub struct Default<'tcx> {
64 /// The span where the default was incurred
65 pub origin_span: Span,
66 /// The definition that the default originates from
71 snapshot: sv::Snapshot,
72 eq_snapshot: ut::Snapshot<ty::TyVid>,
75 struct Instantiate<'tcx> {
77 default: Option<Default<'tcx>>,
80 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
82 impl<'tcx> TypeVariableTable<'tcx> {
83 pub fn new() -> TypeVariableTable<'tcx> {
85 values: sv::SnapshotVec::new(),
86 eq_relations: ut::UnificationTable::new(),
90 pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> {
91 match &self.values.get(vid.index as usize).value {
93 &Bounded { ref default, .. } => default.clone()
97 pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
98 self.values.get(vid.index as usize).diverging
101 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
102 &self.values.get(vid.index as usize).origin
105 /// Records that `a == b`, depending on `dir`.
107 /// Precondition: neither `a` nor `b` are known.
108 pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
109 debug_assert!(self.probe(a).is_none());
110 debug_assert!(self.probe(b).is_none());
111 self.eq_relations.union(a, b);
114 /// Instantiates `vid` with the type `ty`.
116 /// Precondition: `vid` must be a root in the unification table
117 /// and has not previously been instantiated.
118 pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
119 debug_assert!(self.root_var(vid) == vid);
120 debug_assert!(self.probe(vid).is_none());
123 let vid_data = &mut self.values[vid.index as usize];
124 mem::replace(&mut vid_data.value, TypeVariableValue::Known(ty))
128 TypeVariableValue::Bounded { default } => {
129 self.values.record(Instantiate { vid: vid, default: default });
131 TypeVariableValue::Known(old_ty) => {
132 bug!("instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
138 pub fn new_var(&mut self,
140 origin: TypeVariableOrigin,
141 default: Option<Default<'tcx>>,) -> ty::TyVid {
142 debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
143 self.eq_relations.new_key(());
144 let index = self.values.push(TypeVariableData {
145 value: Bounded { default: default },
149 let v = ty::TyVid { index: index as u32 };
150 debug!("new_var: diverging={:?} index={:?}", diverging, v);
154 pub fn num_vars(&self) -> usize {
158 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
159 self.eq_relations.find(vid)
162 pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
163 let vid = self.root_var(vid);
167 /// Retrieves the type of `vid` given that it is currently a root in the unification table
168 pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
169 debug_assert!(self.root_var(vid) == vid);
170 match self.values.get(vid.index as usize).value {
171 Bounded { .. } => None,
176 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
178 ty::TyInfer(ty::TyVar(v)) => {
179 match self.probe(v) {
188 pub fn snapshot(&mut self) -> Snapshot {
190 snapshot: self.values.start_snapshot(),
191 eq_snapshot: self.eq_relations.snapshot(),
195 pub fn rollback_to(&mut self, s: Snapshot) {
196 debug!("rollback_to{:?}", {
197 for action in self.values.actions_since_snapshot(&s.snapshot) {
199 sv::UndoLog::NewElem(index) => {
200 debug!("inference variable _#{}t popped", index)
207 self.values.rollback_to(s.snapshot);
208 self.eq_relations.rollback_to(s.eq_snapshot);
211 pub fn commit(&mut self, s: Snapshot) {
212 self.values.commit(s.snapshot);
213 self.eq_relations.commit(s.eq_snapshot);
216 pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
218 * Find the set of type variables that existed *before* `s`
219 * but which have only been unified since `s` started, and
220 * return the types with which they were unified. So if we had
221 * a type variable `V0`, then we started the snapshot, then we
222 * created a type variable `V1`, unifed `V0` with `T0`, and
223 * unified `V1` with `T1`, this function would return `{T0}`.
226 let mut new_elem_threshold = u32::MAX;
227 let mut escaping_types = Vec::new();
228 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
229 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
230 for action in actions_since_snapshot {
232 sv::UndoLog::NewElem(index) => {
233 // if any new variables were created during the
234 // snapshot, remember the lower index (which will
235 // always be the first one we see). Note that this
236 // action must precede those variables being
238 new_elem_threshold = min(new_elem_threshold, index as u32);
239 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
242 sv::UndoLog::Other(Instantiate { vid, .. }) => {
243 if vid.index < new_elem_threshold {
244 // quick check to see if this variable was
245 // created since the snapshot started or not.
246 let escaping_type = match self.values.get(vid.index as usize).value {
247 Bounded { .. } => bug!(),
250 escaping_types.push(escaping_type);
252 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
262 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
263 (0..self.values.len())
265 let vid = ty::TyVid { index: i as u32 };
266 if self.probe(vid).is_some() {
276 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
277 type Value = TypeVariableData<'tcx>;
278 type Undo = Instantiate<'tcx>;
280 fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: Instantiate<'tcx>) {
281 let Instantiate { vid, default } = action;
282 values[vid.index as usize].value = Bounded {