src/librustc/middle/typeck/infer/type_variable.rs

   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.
   4 //
   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.
  10
  11 use middle::ty;
  12 use std::mem;
  13 use util::snapshot_vec as sv;
  14
  15 pub struct TypeVariableTable {
  16     values: sv::SnapshotVec<TypeVariableData,UndoEntry,Delegate>,
  17 }
  18
  19 struct TypeVariableData {
  20     value: TypeVariableValue
  21 }
  22
  23 enum TypeVariableValue {
  24     Known(ty::t),
  25     Bounded(Vec<Relation>),
  26 }
  27
  28 pub struct Snapshot {
  29     snapshot: sv::Snapshot
  30 }
  31
  32 enum UndoEntry {
  33     // The type of the var was specified.
  34     SpecifyVar(ty::TyVid, Vec<Relation>),
  35     Relate(ty::TyVid, ty::TyVid),
  36 }
  37
  38 struct Delegate;
  39
  40 type Relation = (RelationDir, ty::TyVid);
  41
  42 #[deriving(PartialEq,Show)]
  43 pub enum RelationDir {
  44     SubtypeOf, SupertypeOf, EqTo
  45 }
  46
  47 impl RelationDir {
  48     fn opposite(self) -> RelationDir {
  49         match self {
  50             SubtypeOf => SupertypeOf,
  51             SupertypeOf => SubtypeOf,
  52             EqTo => EqTo
  53         }
  54     }
  55 }
  56
  57 impl TypeVariableTable {
  58     pub fn new() -> TypeVariableTable {
  59         TypeVariableTable { values: sv::SnapshotVec::new(Delegate) }
  60     }
  61
  62     fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
  63         relations(self.values.get_mut(a.index))
  64     }
  65
  66     pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) {
  67         /*!
  68          * Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
  69          *
  70          * Precondition: neither `a` nor `b` are known.
  71          */
  72
  73         if a != b {
  74             self.relations(a).push((dir, b));
  75             self.relations(b).push((dir.opposite(), a));
  76             self.values.record(Relate(a, b));
  77         }
  78     }
  79
  80     pub fn instantiate_and_push(
  81         &mut self,
  82         vid: ty::TyVid,
  83         ty: ty::t,
  84         stack: &mut Vec<(ty::t, RelationDir, ty::TyVid)>)
  85     {
  86         /*!
  87          * Instantiates `vid` with the type `ty` and then pushes an
  88          * entry onto `stack` for each of the relations of `vid` to
  89          * other variables. The relations will have the form `(ty,
  90          * dir, vid1)` where `vid1` is some other variable id.
  91          */
  92
  93         let old_value = {
  94             let value_ptr = &mut self.values.get_mut(vid.index).value;
  95             mem::replace(value_ptr, Known(ty))
  96         };
  97
  98         let relations = match old_value {
  99             Bounded(b) => b,
 100             Known(_) => fail!("Asked to instantiate variable that is \
 101                                already instantiated")
 102         };
 103
 104         for &(dir, vid) in relations.iter() {
 105             stack.push((ty, dir, vid));
 106         }
 107
 108         self.values.record(SpecifyVar(vid, relations));
 109     }
 110
 111     pub fn new_var(&mut self) -> ty::TyVid {
 112         let index =
 113             self.values.push(
 114                 TypeVariableData { value: Bounded(Vec::new()) });
 115         ty::TyVid { index: index }
 116     }
 117
 118     pub fn probe(&self, vid: ty::TyVid) -> Option<ty::t> {
 119         match self.values.get(vid.index).value {
 120             Bounded(..) => None,
 121             Known(t) => Some(t)
 122         }
 123     }
 124
 125     pub fn replace_if_possible(&self, t: ty::t) -> ty::t {
 126         match ty::get(t).sty {
 127             ty::ty_infer(ty::TyVar(v)) => {
 128                 match self.probe(v) {
 129                     None => t,
 130                     Some(u) => u
 131                 }
 132             }
 133             _ => t,
 134         }
 135     }
 136
 137     pub fn snapshot(&mut self) -> Snapshot {
 138         Snapshot { snapshot: self.values.start_snapshot() }
 139     }
 140
 141     pub fn rollback_to(&mut self, s: Snapshot) {
 142         self.values.rollback_to(s.snapshot);
 143     }
 144
 145     pub fn commit(&mut self, s: Snapshot) {
 146         self.values.commit(s.snapshot);
 147     }
 148 }
 149
 150 impl sv::SnapshotVecDelegate<TypeVariableData,UndoEntry> for Delegate {
 151     fn reverse(&mut self,
 152                values: &mut Vec<TypeVariableData>,
 153                action: UndoEntry) {
 154         match action {
 155             SpecifyVar(vid, relations) => {
 156                 values.get_mut(vid.index).value = Bounded(relations);
 157             }
 158
 159             Relate(a, b) => {
 160                 relations(values.get_mut(a.index)).pop();
 161                 relations(values.get_mut(b.index)).pop();
 162             }
 163         }
 164     }
 165 }
 166
 167 fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> {
 168     match v.value {
 169         Known(_) => fail!("var_sub_var: variable is known"),
 170         Bounded(ref mut relations) => relations
 171     }
 172 }
 173