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