src/libsyntax/util/interner.rs

   1 // Copyright 2012 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 // An "interner" is a data structure that associates values with uint tags and
  12 // allows bidirectional lookup; i.e. given a value, one can easily find the
  13 // type, and vice versa.
  14
  15 use ast::Name;
  16
  17 use collections::HashMap;
  18 use std::cast;
  19 use std::cell::RefCell;
  20 use std::cmp::Equiv;
  21 use std::fmt;
  22 use std::hash::Hash;
  23 use std::rc::Rc;
  24
  25 pub struct Interner<T> {
  26     priv map: RefCell<HashMap<T, Name>>,
  27     priv vect: RefCell<Vec<T> >,
  28 }
  29
  30 // when traits can extend traits, we should extend index<Name,T> to get []
  31 impl<T: TotalEq + Hash + Clone + 'static> Interner<T> {
  32     pub fn new() -> Interner<T> {
  33         Interner {
  34             map: RefCell::new(HashMap::new()),
  35             vect: RefCell::new(Vec::new()),
  36         }
  37     }
  38
  39     pub fn prefill(init: &[T]) -> Interner<T> {
  40         let rv = Interner::new();
  41         for v in init.iter() {
  42             rv.intern((*v).clone());
  43         }
  44         rv
  45     }
  46
  47     pub fn intern(&self, val: T) -> Name {
  48         let mut map = self.map.borrow_mut();
  49         match (*map).find(&val) {
  50             Some(&idx) => return idx,
  51             None => (),
  52         }
  53
  54         let mut vect = self.vect.borrow_mut();
  55         let new_idx = (*vect).len() as Name;
  56         (*map).insert(val.clone(), new_idx);
  57         (*vect).push(val);
  58         new_idx
  59     }
  60
  61     pub fn gensym(&self, val: T) -> Name {
  62         let mut vect = self.vect.borrow_mut();
  63         let new_idx = (*vect).len() as Name;
  64         // leave out of .map to avoid colliding
  65         (*vect).push(val);
  66         new_idx
  67     }
  68
  69     pub fn get(&self, idx: Name) -> T {
  70         let vect = self.vect.borrow();
  71         (*(*vect).get(idx as uint)).clone()
  72     }
  73
  74     pub fn len(&self) -> uint {
  75         let vect = self.vect.borrow();
  76         (*vect).len()
  77     }
  78
  79     pub fn find_equiv<Q:Hash + Equiv<T>>(&self, val: &Q) -> Option<Name> {
  80         let map = self.map.borrow();
  81         match (*map).find_equiv(val) {
  82             Some(v) => Some(*v),
  83             None => None,
  84         }
  85     }
  86
  87     pub fn clear(&self) {
  88         *self.map.borrow_mut() = HashMap::new();
  89         *self.vect.borrow_mut() = Vec::new();
  90     }
  91 }
  92
  93 #[deriving(Clone, Eq, Hash, Ord)]
  94 pub struct RcStr {
  95     priv string: Rc<~str>,
  96 }
  97
  98 impl TotalEq for RcStr {
  99     fn equals(&self, other: &RcStr) -> bool {
 100         self.as_slice().equals(&other.as_slice())
 101     }
 102 }
 103
 104 impl TotalOrd for RcStr {
 105     fn cmp(&self, other: &RcStr) -> Ordering {
 106         self.as_slice().cmp(&other.as_slice())
 107     }
 108 }
 109
 110 impl Str for RcStr {
 111     #[inline]
 112     fn as_slice<'a>(&'a self) -> &'a str {
 113         let s: &'a str = *self.string;
 114         s
 115     }
 116
 117     #[inline]
 118     fn into_owned(self) -> ~str {
 119         self.string.to_owned()
 120     }
 121 }
 122
 123 impl fmt::Show for RcStr {
 124     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 125         use std::fmt::Show;
 126         self.as_slice().fmt(f)
 127     }
 128 }
 129
 130 impl RcStr {
 131     pub fn new(string: &str) -> RcStr {
 132         RcStr {
 133             string: Rc::new(string.to_owned()),
 134         }
 135     }
 136 }
 137
 138 // A StrInterner differs from Interner<String> in that it accepts
 139 // &str rather than RcStr, resulting in less allocation.
 140 pub struct StrInterner {
 141     priv map: RefCell<HashMap<RcStr, Name>>,
 142     priv vect: RefCell<Vec<RcStr> >,
 143 }
 144
 145 // when traits can extend traits, we should extend index<Name,T> to get []
 146 impl StrInterner {
 147     pub fn new() -> StrInterner {
 148         StrInterner {
 149             map: RefCell::new(HashMap::new()),
 150             vect: RefCell::new(Vec::new()),
 151         }
 152     }
 153
 154     pub fn prefill(init: &[&str]) -> StrInterner {
 155         let rv = StrInterner::new();
 156         for &v in init.iter() { rv.intern(v); }
 157         rv
 158     }
 159
 160     pub fn intern(&self, val: &str) -> Name {
 161         let mut map = self.map.borrow_mut();
 162         match map.find_equiv(&val) {
 163             Some(&idx) => return idx,
 164             None => (),
 165         }
 166
 167         let new_idx = self.len() as Name;
 168         let val = RcStr::new(val);
 169         map.insert(val.clone(), new_idx);
 170         self.vect.borrow_mut().push(val);
 171         new_idx
 172     }
 173
 174     pub fn gensym(&self, val: &str) -> Name {
 175         let new_idx = self.len() as Name;
 176         // leave out of .map to avoid colliding
 177         self.vect.borrow_mut().push(RcStr::new(val));
 178         new_idx
 179     }
 180
 181     // I want these gensyms to share name pointers
 182     // with existing entries. This would be automatic,
 183     // except that the existing gensym creates its
 184     // own managed ptr using to_managed. I think that
 185     // adding this utility function is the most
 186     // lightweight way to get what I want, though not
 187     // necessarily the cleanest.
 188
 189     // create a gensym with the same name as an existing
 190     // entry.
 191     pub fn gensym_copy(&self, idx : Name) -> Name {
 192         let new_idx = self.len() as Name;
 193         // leave out of map to avoid colliding
 194         let mut vect = self.vect.borrow_mut();
 195         let existing = (*vect.get(idx as uint)).clone();
 196         vect.push(existing);
 197         new_idx
 198     }
 199
 200     pub fn get(&self, idx: Name) -> RcStr {
 201         (*self.vect.borrow().get(idx as uint)).clone()
 202     }
 203
 204     /// Returns this string with lifetime tied to the interner. Since
 205     /// strings may never be removed from the interner, this is safe.
 206     pub fn get_ref<'a>(&'a self, idx: Name) -> &'a str {
 207         let vect = self.vect.borrow();
 208         let s: &str = vect.get(idx as uint).as_slice();
 209         unsafe {
 210             cast::transmute(s)
 211         }
 212     }
 213
 214     pub fn len(&self) -> uint {
 215         self.vect.borrow().len()
 216     }
 217
 218     pub fn find_equiv<Q:Hash + Equiv<RcStr>>(&self, val: &Q) -> Option<Name> {
 219         match (*self.map.borrow()).find_equiv(val) {
 220             Some(v) => Some(*v),
 221             None => None,
 222         }
 223     }
 224
 225     pub fn clear(&self) {
 226         *self.map.borrow_mut() = HashMap::new();
 227         *self.vect.borrow_mut() = Vec::new();
 228     }
 229 }
 230
 231 #[cfg(test)]
 232 mod tests {
 233     use super::*;
 234     #[test]
 235     #[should_fail]
 236     fn i1 () {
 237         let i : Interner<RcStr> = Interner::new();
 238         i.get(13);
 239     }
 240
 241     #[test]
 242     fn interner_tests () {
 243         let i : Interner<RcStr> = Interner::new();
 244         // first one is zero:
 245         assert_eq!(i.intern(RcStr::new("dog")), 0);
 246         // re-use gets the same entry:
 247         assert_eq!(i.intern(RcStr::new("dog")), 0);
 248         // different string gets a different #:
 249         assert_eq!(i.intern(RcStr::new("cat")), 1);
 250         assert_eq!(i.intern(RcStr::new("cat")), 1);
 251         // dog is still at zero
 252         assert_eq!(i.intern(RcStr::new("dog")), 0);
 253         // gensym gets 3
 254         assert_eq!(i.gensym(RcStr::new("zebra") ), 2);
 255         // gensym of same string gets new number :
 256         assert_eq!(i.gensym (RcStr::new("zebra") ), 3);
 257         // gensym of *existing* string gets new number:
 258         assert_eq!(i.gensym(RcStr::new("dog")), 4);
 259         assert_eq!(i.get(0), RcStr::new("dog"));
 260         assert_eq!(i.get(1), RcStr::new("cat"));
 261         assert_eq!(i.get(2), RcStr::new("zebra"));
 262         assert_eq!(i.get(3), RcStr::new("zebra"));
 263         assert_eq!(i.get(4), RcStr::new("dog"));
 264     }
 265
 266     #[test]
 267     fn i3 () {
 268         let i : Interner<RcStr> = Interner::prefill([
 269             RcStr::new("Alan"),
 270             RcStr::new("Bob"),
 271             RcStr::new("Carol")
 272         ]);
 273         assert_eq!(i.get(0), RcStr::new("Alan"));
 274         assert_eq!(i.get(1), RcStr::new("Bob"));
 275         assert_eq!(i.get(2), RcStr::new("Carol"));
 276         assert_eq!(i.intern(RcStr::new("Bob")), 1);
 277     }
 278
 279     #[test]
 280     fn string_interner_tests() {
 281         let i : StrInterner = StrInterner::new();
 282         // first one is zero:
 283         assert_eq!(i.intern("dog"), 0);
 284         // re-use gets the same entry:
 285         assert_eq!(i.intern ("dog"), 0);
 286         // different string gets a different #:
 287         assert_eq!(i.intern("cat"), 1);
 288         assert_eq!(i.intern("cat"), 1);
 289         // dog is still at zero
 290         assert_eq!(i.intern("dog"), 0);
 291         // gensym gets 3
 292         assert_eq!(i.gensym("zebra"), 2);
 293         // gensym of same string gets new number :
 294         assert_eq!(i.gensym("zebra"), 3);
 295         // gensym of *existing* string gets new number:
 296         assert_eq!(i.gensym("dog"), 4);
 297         // gensym tests again with gensym_copy:
 298         assert_eq!(i.gensym_copy(2), 5);
 299         assert_eq!(i.get(5), RcStr::new("zebra"));
 300         assert_eq!(i.gensym_copy(2), 6);
 301         assert_eq!(i.get(6), RcStr::new("zebra"));
 302         assert_eq!(i.get(0), RcStr::new("dog"));
 303         assert_eq!(i.get(1), RcStr::new("cat"));
 304         assert_eq!(i.get(2), RcStr::new("zebra"));
 305         assert_eq!(i.get(3), RcStr::new("zebra"));
 306         assert_eq!(i.get(4), RcStr::new("dog"));
 307     }
 308 }