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