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