1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
//! An "interner" is a data structure that associates values with usize tags and
//! allows bidirectional lookup; i.e. given a value, one can easily find the
//! type, and vice versa.
use ast::Name;
use std::borrow::Borrow;
use std::collections::HashMap;
use std::rc::Rc;
#[derive(PartialEq, Eq, Hash)]
struct RcStr(Rc<String>);
impl Borrow<str> for RcStr {
fn borrow(&self) -> &str {
&self.0
}
}
#[derive(Default)]
pub struct Interner {
names: HashMap<RcStr, Name>,
strings: Vec<Rc<String>>,
}
/// When traits can extend traits, we should extend index<Name,T> to get []
impl Interner {
pub fn new() -> Self {
Interner::default()
}
pub fn prefill(init: &[&str]) -> Self {
let mut this = Interner::new();
for &string in init {
this.intern(string);
}
this
}
pub fn intern<T: Borrow<str> + Into<String>>(&mut self, string: T) -> Name {
if let Some(&name) = self.names.get(string.borrow()) {
return name;
}
let name = Name(self.strings.len() as u32);
let string = Rc::new(string.into());
self.strings.push(string.clone());
self.names.insert(RcStr(string), name);
name
}
pub fn gensym(&mut self, string: &str) -> Name {
let gensym = Name(self.strings.len() as u32);
// leave out of `names` to avoid colliding
self.strings.push(Rc::new(string.to_owned()));
gensym
}
/// Create a gensym with the same name as an existing entry.
pub fn gensym_copy(&mut self, name: Name) -> Name {
let gensym = Name(self.strings.len() as u32);
// leave out of `names` to avoid colliding
let string = self.strings[name.0 as usize].clone();
self.strings.push(string);
gensym
}
pub fn get(&self, name: Name) -> Rc<String> {
self.strings[name.0 as usize].clone()
}
pub fn find(&self, string: &str) -> Option<Name> {
self.names.get(string).cloned()
}
}
#[cfg(test)]
mod tests {
use super::*;
use ast::Name;
#[test]
fn interner_tests() {
let mut i: Interner = Interner::new();
// first one is zero:
assert_eq!(i.intern("dog"), Name(0));
// re-use gets the same entry:
assert_eq!(i.intern ("dog"), Name(0));
// different string gets a different #:
assert_eq!(i.intern("cat"), Name(1));
assert_eq!(i.intern("cat"), Name(1));
// dog is still at zero
assert_eq!(i.intern("dog"), Name(0));
// gensym gets 3
assert_eq!(i.gensym("zebra"), Name(2));
// gensym of same string gets new number :
assert_eq!(i.gensym("zebra"), Name(3));
// gensym of *existing* string gets new number:
assert_eq!(i.gensym("dog"), Name(4));
// gensym tests again with gensym_copy:
assert_eq!(i.gensym_copy(Name(2)), Name(5));
assert_eq!(*i.get(Name(5)), "zebra");
assert_eq!(i.gensym_copy(Name(2)), Name(6));
assert_eq!(*i.get(Name(6)), "zebra");
assert_eq!(*i.get(Name(0)), "dog");
assert_eq!(*i.get(Name(1)), "cat");
assert_eq!(*i.get(Name(2)), "zebra");
assert_eq!(*i.get(Name(3)), "zebra");
assert_eq!(*i.get(Name(4)), "dog");
}
}
|
