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.
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.
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.
17 use std::borrow::BorrowFrom;
18 use std::cell::RefCell;
19 use std::cmp::Ordering;
20 use std::collections::HashMap;
23 use std::collections::hash_map::Hasher;
27 pub struct Interner<T> {
28 map: RefCell<HashMap<T, Name>>,
29 vect: RefCell<Vec<T> >,
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> {
36 map: RefCell::new(HashMap::new()),
37 vect: RefCell::new(Vec::new()),
41 pub fn prefill(init: &[T]) -> Interner<T> {
42 let rv = Interner::new();
43 for v in init.iter() {
44 rv.intern((*v).clone());
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,
56 let mut vect = self.vect.borrow_mut();
57 let new_idx = Name((*vect).len() as u32);
58 (*map).insert(val.clone(), new_idx);
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
71 pub fn get(&self, idx: Name) -> T {
72 let vect = self.vect.borrow();
73 (*vect)[idx.uint()].clone()
76 pub fn len(&self) -> uint {
77 let vect = self.vect.borrow();
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) {
91 *self.map.borrow_mut() = HashMap::new();
92 *self.vect.borrow_mut() = Vec::new();
96 #[derive(Clone, PartialEq, Hash, PartialOrd)]
102 pub fn new(string: &str) -> RcStr {
104 string: Rc::new(string.to_string()),
112 fn cmp(&self, other: &RcStr) -> Ordering {
117 impl fmt::Show for RcStr {
118 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
124 impl BorrowFrom<RcStr> for str {
125 fn borrow_from(owned: &RcStr) -> &str {
130 impl Deref for RcStr {
133 fn deref(&self) -> &str { &self.string[] }
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> >,
143 /// When traits can extend traits, we should extend index<Name,T> to get []
145 pub fn new() -> StrInterner {
147 map: RefCell::new(HashMap::new()),
148 vect: RefCell::new(Vec::new()),
152 pub fn prefill(init: &[&str]) -> StrInterner {
153 let rv = StrInterner::new();
154 for &v in init.iter() { rv.intern(v); }
158 pub fn intern(&self, val: &str) -> Name {
159 let mut map = self.map.borrow_mut();
161 Some(&idx) => return idx,
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);
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));
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.
187 /// Create a gensym with the same name as an existing
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();
198 pub fn get(&self, idx: Name) -> RcStr {
199 (*self.vect.borrow())[idx.uint()].clone()
202 pub fn len(&self) -> uint {
203 self.vect.borrow().len()
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) {
214 pub fn clear(&self) {
215 *self.map.borrow_mut() = HashMap::new();
216 *self.vect.borrow_mut() = Vec::new();
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();
233 let i : Interner<RcStr> = Interner::new();
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));
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"));
264 let i : Interner<RcStr> = Interner::prefill(&[
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));
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));
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"));