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