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::collections::HashMap;
  18 use std::rc::Rc;
  19
  20 #[derive(Default)]
  21 pub struct Interner {
  22     names: HashMap<Rc<str>, Name>,
  23     strings: Vec<Rc<str>>,
  24 }
  25
  26 /// When traits can extend traits, we should extend index<Name,T> to get []
  27 impl Interner {
  28     pub fn new() -> Self {
  29         Interner::default()
  30     }
  31
  32     pub fn prefill(init: &[&str]) -> Self {
  33         let mut this = Interner::new();
  34         for &string in init {
  35             this.intern(string);
  36         }
  37         this
  38     }
  39
  40     pub fn intern(&mut self, string: &str) -> Name {
  41         if let Some(&name) = self.names.get(string) {
  42             return name;
  43         }
  44
  45         let name = Name(self.strings.len() as u32);
  46         let string = Rc::__from_str(string);
  47         self.strings.push(string.clone());
  48         self.names.insert(string, name);
  49         name
  50     }
  51
  52     pub fn gensym(&mut self, string: &str) -> Name {
  53         let gensym = Name(self.strings.len() as u32);
  54         // leave out of `names` to avoid colliding
  55         self.strings.push(Rc::__from_str(string));
  56         gensym
  57     }
  58
  59     /// Create a gensym with the same name as an existing entry.
  60     pub fn gensym_copy(&mut self, name: Name) -> Name {
  61         let gensym = Name(self.strings.len() as u32);
  62         // leave out of `names` to avoid colliding
  63         let string = self.strings[name.0 as usize].clone();
  64         self.strings.push(string);
  65         gensym
  66     }
  67
  68     pub fn get(&self, name: Name) -> Rc<str> {
  69         self.strings[name.0 as usize].clone()
  70     }
  71
  72     pub fn find(&self, string: &str) -> Option<Name> {
  73         self.names.get(string).cloned()
  74     }
  75 }
  76
  77 #[cfg(test)]
  78 mod tests {
  79     use super::*;
  80     use ast::Name;
  81
  82     #[test]
  83     fn interner_tests() {
  84         let mut i: Interner = Interner::new();
  85         // first one is zero:
  86         assert_eq!(i.intern("dog"), Name(0));
  87         // re-use gets the same entry:
  88         assert_eq!(i.intern ("dog"), Name(0));
  89         // different string gets a different #:
  90         assert_eq!(i.intern("cat"), Name(1));
  91         assert_eq!(i.intern("cat"), Name(1));
  92         // dog is still at zero
  93         assert_eq!(i.intern("dog"), Name(0));
  94         // gensym gets 3
  95         assert_eq!(i.gensym("zebra"), Name(2));
  96         // gensym of same string gets new number :
  97         assert_eq!(i.gensym("zebra"), Name(3));
  98         // gensym of *existing* string gets new number:
  99         assert_eq!(i.gensym("dog"), Name(4));
 100         // gensym tests again with gensym_copy:
 101         assert_eq!(i.gensym_copy(Name(2)), Name(5));
 102         assert_eq!(&*i.get(Name(5)), "zebra");
 103         assert_eq!(i.gensym_copy(Name(2)), Name(6));
 104         assert_eq!(&*i.get(Name(6)), "zebra");
 105         assert_eq!(&*i.get(Name(0)), "dog");
 106         assert_eq!(&*i.get(Name(1)), "cat");
 107         assert_eq!(&*i.get(Name(2)), "zebra");
 108         assert_eq!(&*i.get(Name(3)), "zebra");
 109         assert_eq!(&*i.get(Name(4)), "dog");
 110     }
 111 }