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 126293 : fn hash(text: &[u8]) -> u64 {
35 : const K: u64 = 0x517c_c1b7_2722_0a95;
36 126293 : let mut h: u64 = text.len() as u64;
37 126293 : let mut chunks = text.chunks_exact(8);
38 126293 : for chunk in &mut chunks {
39 79664 : let word = u64::from_le_bytes(chunk.try_into().unwrap());
40 79664 : h = (h.rotate_left(5) ^ word).wrapping_mul(K);
41 79664 : }
42 410810 : for &b in chunks.remainder() {
43 410794 : h = (h.rotate_left(5) ^ b as u64).wrapping_mul(K);
44 410794 : }
45 126293 : h
46 126293 : }
47 :
48 : impl NameRegistry {
49 : /// The number of names
50 3736 : pub fn len(&self) -> usize {
51 3736 : self.names.len()
52 3736 : }
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 4488 : pub fn get(&self, id: NameId) -> &RegisteredName {
61 4488 : &self.names[id as usize]
62 4488 : }
63 :
64 : /// All names in id order
65 7577 : pub fn iter(&self) -> impl Iterator<Item = &RegisteredName> {
66 7577 : self.names.iter()
67 7577 : }
68 :
69 : /// The slot of a name text: either the slot holding it or the empty slot where it belongs
70 108213 : fn slot(&self, text: &str) -> usize {
71 108213 : let mask = self.table.len() - 1;
72 108213 : let mut slot = hash(text.as_bytes()) as usize & mask;
73 : loop {
74 135753 : match self.table[slot] {
75 55472 : 0 => return slot,
76 80281 : id if self.names[id as usize - 1].text == text => return slot,
77 27540 : _ => slot = (slot + 1) & mask,
78 : }
79 : }
80 108213 : }
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 6664 : fn grow(&mut self) {
94 6664 : let capacity = (self.table.len() * 2).max(64);
95 6664 : self.table = vec![0; capacity];
96 6664 : let mask = capacity - 1;
97 20329 : for (i, name) in self.names.iter().enumerate() {
98 18080 : let mut slot = hash(name.text.as_bytes()) as usize & mask;
99 21567 : while self.table[slot] != 0 {
100 3487 : slot = (slot + 1) & mask;
101 3487 : }
102 18080 : self.table[slot] = i as u32 + 1;
103 : }
104 6664 : }
105 :
106 : /// Register a name. A known name counts another occurrence and keeps its first location.
107 107206 : pub fn register(&mut self, text: &str, location: TextSpan) -> NameId {
108 107206 : if (self.names.len() + 1) * 2 > self.table.len() {
109 6664 : self.grow();
110 100600 : }
111 107206 : let slot = self.slot(text);
112 107206 : match self.table[slot] {
113 : 0 => {
114 55471 : let id = self.names.len() as NameId;
115 55471 : self.names.push(RegisteredName {
116 55471 : name_id: id,
117 55471 : text: text.to_string(),
118 55471 : location,
119 55471 : occurrences: 1,
120 55471 : });
121 55471 : self.table[slot] = id + 1;
122 55471 : id
123 : }
124 51735 : id => {
125 51735 : self.names[id as usize - 1].occurrences += 1;
126 51735 : id - 1
127 : }
128 : }
129 107206 : }
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 : }
|
