Line data Source code
1 : //! The names of a script: identifiers and keywords that may be used as names.
2 :
3 : use crate::span::TextSpan;
4 :
5 : /// The id of a registered name, unique within a script
6 : pub type NameId = u32;
7 :
8 : /// A registered name
9 : #[derive(Clone, Debug, PartialEq, Eq)]
10 : pub struct RegisteredName {
11 : /// The name id
12 : pub name_id: NameId,
13 : /// The text (lower-cased unless the name was quoted)
14 : pub text: String,
15 : /// The location of the first occurrence (empty for names without one)
16 : pub location: TextSpan,
17 : /// The number of occurrences
18 : pub occurrences: u32,
19 : }
20 :
21 : /// The names of a script, ids are assigned in order of first registration.
22 : ///
23 : /// An open-addressing table over the names (name id + 1 per slot, 0 = empty), so the texts are
24 : /// stored once.
25 : #[derive(Clone, Debug, Default)]
26 : pub struct NameRegistry {
27 : /// The names indexed by name id
28 : names: Vec<RegisteredName>,
29 : /// The hash slots holding name id + 1, 0 for an empty slot, the length is a power of two
30 : table: Vec<u32>,
31 : }
32 :
33 : /// A fast hash for short names (FxHash over 8-byte words)
34 129177 : fn hash(text: &[u8]) -> u64 {
35 : const K: u64 = 0x517c_c1b7_2722_0a95;
36 129177 : let mut h: u64 = text.len() as u64;
37 129177 : let mut chunks = text.chunks_exact(8);
38 129177 : for chunk in &mut chunks {
39 80124 : let word = u64::from_le_bytes(chunk.try_into().unwrap());
40 80124 : h = (h.rotate_left(5) ^ word).wrapping_mul(K);
41 80124 : }
42 418558 : for &b in chunks.remainder() {
43 418544 : h = (h.rotate_left(5) ^ b as u64).wrapping_mul(K);
44 418544 : }
45 129177 : h
46 129177 : }
47 :
48 : impl NameRegistry {
49 : /// The number of names
50 4005 : pub fn len(&self) -> usize {
51 4005 : self.names.len()
52 4005 : }
53 :
54 : /// Are there no names?
55 0 : pub fn is_empty(&self) -> bool {
56 0 : self.names.is_empty()
57 0 : }
58 :
59 : /// Get a name
60 4900 : pub fn get(&self, id: NameId) -> &RegisteredName {
61 4900 : &self.names[id as usize]
62 4900 : }
63 :
64 : /// All names in id order
65 8112 : pub fn iter(&self) -> impl Iterator<Item = &RegisteredName> {
66 8112 : self.names.iter()
67 8112 : }
68 :
69 : /// The slot of a name text: either the slot holding it or the empty slot where it belongs
70 110873 : fn slot(&self, text: &str) -> usize {
71 110873 : let mask = self.table.len() - 1;
72 110873 : let mut slot = hash(text.as_bytes()) as usize & mask;
73 : loop {
74 138585 : match self.table[slot] {
75 57835 : 0 => return slot,
76 80750 : id if self.names[id as usize - 1].text == text => return slot,
77 27712 : _ => slot = (slot + 1) & mask,
78 : }
79 : }
80 110873 : }
81 :
82 : /// Find a name by its text
83 1007 : pub fn find(&self, text: &str) -> Option<NameId> {
84 1007 : if self.table.is_empty() {
85 0 : return None;
86 1007 : }
87 1007 : match self.table[self.slot(text)] {
88 1 : 0 => None,
89 1006 : id => Some(id - 1),
90 : }
91 1007 : }
92 :
93 7145 : fn grow(&mut self) {
94 7145 : let capacity = (self.table.len() * 2).max(64);
95 7145 : self.table = vec![0; capacity];
96 7145 : let mask = capacity - 1;
97 20750 : for (i, name) in self.names.iter().enumerate() {
98 18304 : let mut slot = hash(name.text.as_bytes()) as usize & mask;
99 21812 : while self.table[slot] != 0 {
100 3508 : slot = (slot + 1) & mask;
101 3508 : }
102 18304 : self.table[slot] = i as u32 + 1;
103 : }
104 7145 : }
105 :
106 : /// Register a name. A known name counts another occurrence and keeps its first location.
107 109866 : pub fn register(&mut self, text: &str, location: TextSpan) -> NameId {
108 109866 : if (self.names.len() + 1) * 2 > self.table.len() {
109 7145 : self.grow();
110 102776 : }
111 109866 : let slot = self.slot(text);
112 109866 : match self.table[slot] {
113 : 0 => {
114 57834 : let id = self.names.len() as NameId;
115 57834 : self.names.push(RegisteredName {
116 57834 : name_id: id,
117 57834 : text: text.to_string(),
118 57834 : location,
119 57834 : occurrences: 1,
120 57834 : });
121 57834 : self.table[slot] = id + 1;
122 57834 : id
123 : }
124 52032 : id => {
125 52032 : self.names[id as usize - 1].occurrences += 1;
126 52032 : id - 1
127 : }
128 : }
129 109866 : }
130 : }
131 :
132 : #[cfg(test)]
133 : mod tests {
134 : use super::*;
135 :
136 : #[test]
137 1 : fn registers_names_once() {
138 1 : let mut names = NameRegistry::default();
139 1 : assert_eq!(names.register("foo", TextSpan::new(0, 3)), 0);
140 1 : assert_eq!(names.register("bar", TextSpan::new(4, 3)), 1);
141 1 : assert_eq!(names.register("foo", TextSpan::new(8, 3)), 0);
142 1 : assert_eq!(names.len(), 2);
143 1 : assert_eq!(names.get(0).occurrences, 2);
144 1 : assert_eq!(names.get(0).location, TextSpan::new(0, 3));
145 1 : assert_eq!(names.find("bar"), Some(1));
146 1 : assert_eq!(names.find("baz"), None);
147 1 : }
148 :
149 : #[test]
150 1 : fn grows() {
151 1 : let mut names = NameRegistry::default();
152 1000 : for i in 0..1000 {
153 1000 : assert_eq!(names.register(&format!("name{i}"), TextSpan::default()), i);
154 : }
155 1000 : for i in 0..1000 {
156 1000 : assert_eq!(names.find(&format!("name{i}")), Some(i));
157 1000 : assert_eq!(names.register(&format!("name{i}"), TextSpan::default()), i);
158 : }
159 1 : assert_eq!(names.len(), 1000);
160 1 : }
161 : }
|
