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 pub use self::RelationDir
::*;
12 use self::TypeVariableValue
::*;
13 use self::UndoEntry
::*;
15 use middle
::ty
::{self, Ty}
;
17 use std
::marker
::PhantomData
;
20 use rustc_data_structures
::snapshot_vec
as sv
;
22 pub struct TypeVariableTable
<'tcx
> {
23 values
: sv
::SnapshotVec
<Delegate
<'tcx
>>,
26 struct TypeVariableData
<'tcx
> {
27 value
: TypeVariableValue
<'tcx
>,
31 enum TypeVariableValue
<'tcx
> {
33 Bounded(Vec
<Relation
>),
37 snapshot
: sv
::Snapshot
41 // The type of the var was specified.
42 SpecifyVar(ty
::TyVid
, Vec
<Relation
>),
43 Relate(ty
::TyVid
, ty
::TyVid
),
46 struct Delegate
<'tcx
>(PhantomData
<&'
tcx ()>);
48 type Relation
= (RelationDir
, ty
::TyVid
);
50 #[derive(Copy, Clone, PartialEq, Debug)]
51 pub enum RelationDir
{
52 SubtypeOf
, SupertypeOf
, EqTo
, BiTo
56 fn opposite(self) -> RelationDir
{
58 SubtypeOf
=> SupertypeOf
,
59 SupertypeOf
=> SubtypeOf
,
66 impl<'tcx
> TypeVariableTable
<'tcx
> {
67 pub fn new() -> TypeVariableTable
<'tcx
> {
68 TypeVariableTable { values: sv::SnapshotVec::new() }
71 fn relations
<'a
>(&'a
mut self, a
: ty
::TyVid
) -> &'a
mut Vec
<Relation
> {
72 relations(self.values
.get_mut(a
.index
as usize))
75 pub fn var_diverges
<'a
>(&'a
self, vid
: ty
::TyVid
) -> bool
{
76 self.values
.get(vid
.index
as usize).diverging
79 /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
81 /// Precondition: neither `a` nor `b` are known.
82 pub fn relate_vars(&mut self, a
: ty
::TyVid
, dir
: RelationDir
, b
: ty
::TyVid
) {
84 self.relations(a
).push((dir
, b
));
85 self.relations(b
).push((dir
.opposite(), a
));
86 self.values
.record(Relate(a
, b
));
90 /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the
91 /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)`
92 /// where `vid1` is some other variable id.
93 pub fn instantiate_and_push(
97 stack
: &mut Vec
<(Ty
<'tcx
>, RelationDir
, ty
::TyVid
)>)
100 let value_ptr
= &mut self.values
.get_mut(vid
.index
as usize).value
;
101 mem
::replace(value_ptr
, Known(ty
))
104 let relations
= match old_value
{
106 Known(_
) => panic
!("Asked to instantiate variable that is \
107 already instantiated")
110 for &(dir
, vid
) in &relations
{
111 stack
.push((ty
, dir
, vid
));
114 self.values
.record(SpecifyVar(vid
, relations
));
117 pub fn new_var(&mut self, diverging
: bool
) -> ty
::TyVid
{
118 let index
= self.values
.push(TypeVariableData
{
119 value
: Bounded(vec
![]),
122 ty
::TyVid { index: index as u32 }
125 pub fn probe(&self, vid
: ty
::TyVid
) -> Option
<Ty
<'tcx
>> {
126 match self.values
.get(vid
.index
as usize).value
{
132 pub fn replace_if_possible(&self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
134 ty
::TyInfer(ty
::TyVar(v
)) => {
135 match self.probe(v
) {
144 pub fn snapshot(&mut self) -> Snapshot
{
145 Snapshot { snapshot: self.values.start_snapshot() }
148 pub fn rollback_to(&mut self, s
: Snapshot
) {
149 self.values
.rollback_to(s
.snapshot
);
152 pub fn commit(&mut self, s
: Snapshot
) {
153 self.values
.commit(s
.snapshot
);
156 pub fn types_escaping_snapshot(&self, s
: &Snapshot
) -> Vec
<Ty
<'tcx
>> {
158 * Find the set of type variables that existed *before* `s`
159 * but which have only been unified since `s` started, and
160 * return the types with which they were unified. So if we had
161 * a type variable `V0`, then we started the snapshot, then we
162 * created a type variable `V1`, unifed `V0` with `T0`, and
163 * unified `V1` with `T1`, this function would return `{T0}`.
166 let mut new_elem_threshold
= u32::MAX
;
167 let mut escaping_types
= Vec
::new();
168 let actions_since_snapshot
= self.values
.actions_since_snapshot(&s
.snapshot
);
169 debug
!("actions_since_snapshot.len() = {}", actions_since_snapshot
.len());
170 for action
in actions_since_snapshot
{
172 sv
::UndoLog
::NewElem(index
) => {
173 // if any new variables were created during the
174 // snapshot, remember the lower index (which will
175 // always be the first one we see). Note that this
176 // action must precede those variables being
178 new_elem_threshold
= min(new_elem_threshold
, index
as u32);
179 debug
!("NewElem({}) new_elem_threshold={}", index
, new_elem_threshold
);
182 sv
::UndoLog
::Other(SpecifyVar(vid
, _
)) => {
183 if vid
.index
< new_elem_threshold
{
184 // quick check to see if this variable was
185 // created since the snapshot started or not.
186 let escaping_type
= self.probe(vid
).unwrap();
187 escaping_types
.push(escaping_type
);
189 debug
!("SpecifyVar({:?}) new_elem_threshold={}", vid
, new_elem_threshold
);
200 impl<'tcx
> sv
::SnapshotVecDelegate
for Delegate
<'tcx
> {
201 type Value
= TypeVariableData
<'tcx
>;
202 type Undo
= UndoEntry
;
204 fn reverse(values
: &mut Vec
<TypeVariableData
<'tcx
>>, action
: UndoEntry
) {
206 SpecifyVar(vid
, relations
) => {
207 values
[vid
.index
as usize].value
= Bounded(relations
);
211 relations(&mut (*values
)[a
.index
as usize]).pop();
212 relations(&mut (*values
)[b
.index
as usize]).pop();
218 fn relations
<'a
>(v
: &'a
mut TypeVariableData
) -> &'a
mut Vec
<Relation
> {
220 Known(_
) => panic
!("var_sub_var: variable is known"),
221 Bounded(ref mut relations
) => relations