1use alloc::vec::Vec;
12
13use hashbrown::HashTable;
14
15use crate::code::Text;
16use crate::value::fnv1a;
17use crate::Ctx;
18
19#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
23pub struct Sym(u32);
24
25macro_rules! fixed_syms {
28 ($($name:ident = $text:literal,)*) => {
29 #[allow(non_camel_case_types, clippy::upper_case_acronyms)]
30 #[repr(u32)]
31 enum Fixed { $($name,)* _Count }
32
33 impl Sym {
34 $(pub const $name: Sym = Sym(Fixed::$name as u32);)*
35 }
36
37 const N_FIXED: u32 = Fixed::_Count as u32;
39
40 static FIXED: [&str; N_FIXED as usize] = [$($text,)*];
42 };
43}
44
45fixed_syms! {
49 MOD_BOOL = "Bool",
50 MOD_ERR = "Err",
51 MOD_FUN = "Fun",
52 MOD_INT = "Int",
53 MOD_ITER = "Iter",
54 MOD_LIST = "List",
55 MOD_MAP = "Map",
56 MOD_MOD = "Mod",
57 MOD_STR = "Str",
58 MOD_SYM = "Sym",
59 MOD_UNIT = "Unit",
60 SIG_BREAK = "__break",
61 SIG_CONTINUE = "__continue",
62 SIG_RETURN = "__return",
63 SIG_YIELD = "__yield",
64 ADD = "add",
65 AND = "and",
66 APPEND = "append",
67 BAD_CODEPOINT = "bad_codepoint",
68 BAD_PROJECTION = "bad_projection",
69 BAD_SYMBOL = "bad_symbol",
70 CANNOT_PARSE_INT = "cannot_parse_int",
71 CAT = "cat",
72 CATCH = "catch",
73 CHARS = "chars",
74 COUNT = "count",
75 DIV_BY_ZERO = "div_by_zero",
76 DIVREM = "divrem",
77 EACH = "each",
78 EMPTY = "empty",
79 EQ = "eq",
80 EXPORTS = "exports",
81 FALSE = "false",
82 FOLD = "fold",
83 FOR = "for",
84 FOREIGN_OBJECT = "foreign_object",
85 FROM = "from",
86 GE = "ge",
87 GET = "get",
88 GETS = "gets",
89 GT = "gt",
90 INDEX = "index",
91 ITER = "iter",
92 ITER_END = "iter_end",
93 LE = "le",
94 LIST_SIZE_MISMATCH = "list_size_mismatch",
95 LT = "lt",
96 MAP_SIZE_MISMATCH = "map_size_mismatch",
97 MERGE = "merge",
98 MISSING_KEY = "missing_key",
99 MISSING_PROPERTY = "missing_property",
100 MODULE_ARITY = "module_arity",
101 MUL = "mul",
102 NAME = "name",
103 NEGATIVE_EXPONENT = "negative_exponent",
104 NEXT = "next",
105 NIL = "nil",
106 NO_MATCH = "no_match",
107 NO_MODULE = "no_module",
108 NOT = "not",
109 NOT_A_BOOL = "not_a_bool",
110 NOT_A_LIST = "not_a_list",
111 NOT_A_MAP = "not_a_map",
112 NOT_A_MODULE = "not_a_module",
113 NOT_A_PAIR = "not_a_pair",
114 NOT_A_STR = "not_a_str",
115 NOT_A_SYM = "not_a_sym",
116 NOT_AN_INT = "not_an_int",
117 NOT_AN_ITER = "not_an_iter",
118 NOT_AN_OBJECT = "not_an_object",
119 NOT_APPLICABLE = "not_applicable",
120 NOT_IN_LOOP = "not_in_loop",
121 NOT_INT = "not_int",
122 NOT_ITERABLE = "not_iterable",
123 NOT_STRING = "not_string",
124 NOT_UNIT = "not_unit",
125 OR = "or",
126 PARSE = "parse",
127 POW = "pow",
128 PROJECTION_OUT_OF_RANGE = "projection_out_of_range",
129 RAISE = "raise",
130 RANGE = "range",
131 RUN = "run",
132 SIZE = "size",
133 SPLIT = "split",
134 STR = "str",
135 SUB = "sub",
136 TRUE = "true",
137 UPTO = "upto",
138 WITH = "with",
139 WITHOUT = "without",
140 YIELD_IN_FOLD = "yield_in_fold",
141 ZIP = "zip",
142}
143
144#[derive(Debug, Clone, Copy, PartialEq, Eq)]
148pub(crate) enum Projection {
149 Name,
151 Index(u32),
153 TooLarge,
155}
156
157impl Projection {
158 fn of(text: &str) -> Projection {
159 if text.is_empty() || !text.bytes().all(|b| b.is_ascii_digit()) {
160 return Projection::Name;
161 }
162 text.parse().map_or(Projection::TooLarge, Projection::Index)
163 }
164}
165
166#[derive(Default)]
168pub(crate) struct Symbols {
169 entries: Vec<Entry>,
171 index: HashTable<u32>,
176}
177
178struct Entry {
179 text: Text,
180 hash: u64,
181 proj: Projection,
182}
183
184impl Symbols {
185 fn find(&self, s: &str, hash: u64) -> Option<Sym> {
186 self.index
187 .find(hash, |&id| self.str_of(id) == s)
188 .map(|&id| Sym(id))
189 }
190
191 fn str_of(&self, id: u32) -> &str {
192 match FIXED.get(id as usize) {
193 Some(s) => s,
194 None => &self.entries[(id - N_FIXED) as usize].text,
195 }
196 }
197
198 fn entry(&self, sym: Sym) -> &Entry {
199 &self.entries[(sym.0 - N_FIXED) as usize]
200 }
201}
202
203pub(crate) fn fixed(s: &str) -> Option<Sym> {
205 FIXED.binary_search(&s).ok().map(|i| Sym(i as u32))
206}
207
208impl Ctx {
209 pub fn intern(&self, s: &str) -> Sym {
211 let hash = fnv1a(s.as_bytes());
212 let mut syms = self.syms.borrow_mut();
213 if let Some(sym) = syms.find(s, hash) {
214 return sym;
215 }
216 let Symbols { entries, index } = &mut *syms;
217 let sym = match fixed(s) {
218 Some(sym) => sym,
219 None => {
220 let id = u32::try_from(entries.len())
221 .ok()
222 .and_then(|i| i.checked_add(N_FIXED))
223 .expect("fewer than 2^32 symbols");
224 entries.push(Entry {
225 text: Text::from(s),
226 hash,
227 proj: Projection::of(s),
228 });
229 Sym(id)
230 }
231 };
232 index.insert_unique(hash, sym.0, |&id| match FIXED.get(id as usize) {
233 Some(s) => fnv1a(s.as_bytes()),
234 None => entries[(id - N_FIXED) as usize].hash,
235 });
236 sym
237 }
238
239 pub fn sym(&self, s: &str) -> Option<Sym> {
242 self.syms
243 .borrow()
244 .find(s, fnv1a(s.as_bytes()))
245 .or_else(|| fixed(s))
246 }
247
248 pub fn text(&self, sym: Sym) -> Text {
250 match FIXED.get(sym.0 as usize) {
251 Some(s) => Text::from_static(s),
252 None => self.syms.borrow().entry(sym).text.clone(),
253 }
254 }
255
256 pub(crate) fn with_str<R>(&self, sym: Sym, f: impl FnOnce(&str) -> R) -> R {
259 match FIXED.get(sym.0 as usize) {
260 Some(s) => f(s),
261 None => f(&self.syms.borrow().entry(sym).text),
262 }
263 }
264
265 pub(crate) fn projection(&self, sym: Sym) -> Projection {
267 if sym.0 < N_FIXED {
268 return Projection::Name;
270 }
271 self.syms.borrow().entry(sym).proj
272 }
273}
274
275#[cfg(test)]
276mod tests {
277 use super::*;
278
279 #[test]
280 fn fixed_are_sorted_names() {
281 assert!(
282 FIXED.windows(2).all(|w| w[0] < w[1]),
283 "sorted, no duplicates"
284 );
285 assert!(FIXED.iter().all(|s| Projection::of(s) == Projection::Name));
286 assert_eq!(FIXED[Sym::DIV_BY_ZERO.0 as usize], "div_by_zero");
287 assert_eq!(FIXED[Sym::MOD_STR.0 as usize], "Str");
288 assert_eq!(FIXED[Sym::STR.0 as usize], "str");
289 }
290
291 #[test]
292 fn a_fixed_symbol_is_found_not_interned() {
293 let ctx = Ctx::new();
294 assert_eq!(ctx.intern("no_match"), Sym::NO_MATCH);
295 assert_eq!(ctx.sym("Int"), Some(Sym::MOD_INT));
296 assert_eq!(ctx.text(Sym::ADD), "add");
297 assert!(ctx.syms.borrow().entries.is_empty());
298 }
299
300 #[test]
301 fn interning_twice_gives_one_symbol() {
302 let ctx = Ctx::new();
303 let a = ctx.intern("apple");
304 let b = ctx.intern("banana");
305 assert_ne!(a, b);
306 assert_eq!(ctx.intern("apple"), a);
307 assert_eq!(ctx.text(a), "apple");
308 assert_eq!(ctx.with_str(b, str::len), 6);
309 assert_eq!(ctx.syms.borrow().entries.len(), 2);
310 }
311
312 #[test]
313 fn looking_up_interns_nothing() {
314 let ctx = Ctx::new();
315 assert_eq!(ctx.sym("pear"), None);
316 assert!(ctx.syms.borrow().entries.is_empty());
317 let p = ctx.intern("pear");
318 assert_eq!(ctx.sym("pear"), Some(p));
319 }
320
321 #[test]
322 fn many_symbols_stay_distinct() {
323 let ctx = Ctx::new();
324 let syms: Vec<Sym> = (0..1000)
325 .map(|i| ctx.intern(&alloc::format!("s{i}")))
326 .collect();
327 for (i, &s) in syms.iter().enumerate() {
328 assert_eq!(ctx.intern(&alloc::format!("s{i}")), s);
329 assert_eq!(ctx.text(s), alloc::format!("s{i}").as_str());
330 }
331 }
332
333 #[test]
334 fn a_projection_is_computed_once_interned() {
335 let ctx = Ctx::new();
336 let p = |s| ctx.projection(ctx.intern(s));
337 assert_eq!(p("0"), Projection::Index(0));
338 assert_eq!(p("12"), Projection::Index(12));
339 assert_eq!(p("4294967295"), Projection::Index(u32::MAX));
340 assert_eq!(p("4294967296"), Projection::TooLarge);
341 assert_eq!(p("1a"), Projection::Name);
342 assert_eq!(p("get"), Projection::Name);
343 assert_eq!(p(""), Projection::Name);
344 }
345}