Skip to main content

elly_core/
sym.rs

1//! The realm's symbol store: every name and symbol of code parsed into a
2//! [`Ctx`], and every symbol made while it evaluates, as a [`Sym`] index.
3//!
4//! The symbols the builtins raise or return, and the builtin modules' aliases
5//! and item names, are **fixed**: a static table sorted by text, with ids
6//! `0..N_FIXED` in that order, so a name-sorted table of them is also sorted by
7//! `Sym`. Interning searches the realm's index first, then the fixed table, and
8//! only then makes an entry, with an id from `N_FIXED` on. See
9//! `docs/done/2026-10-05_elly-ctx-syms.md`.
10
11use alloc::vec::Vec;
12
13use hashbrown::HashTable;
14
15use crate::code::Text;
16use crate::value::fnv1a;
17use crate::Ctx;
18
19/// A name or symbol, interned in a realm (a [`Ctx`]). Two `Sym`s of one realm
20/// are equal exactly when their texts are; a `Sym` means nothing in another
21/// realm, except a fixed one, which every realm shares.
22#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
23pub struct Sym(u32);
24
25/// Declares the fixed symbols, sorted by text: an associated `Sym` constant
26/// each, numbered in order, and the [`FIXED`] table of their texts.
27macro_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        /// How many fixed symbols there are; the first interned id.
38        const N_FIXED: u32 = Fixed::_Count as u32;
39
40        /// The fixed symbols' texts, indexed by id. Sorted, which a test asserts.
41        static FIXED: [&str; N_FIXED as usize] = [$($text,)*];
42    };
43}
44
45// The builtin modules' aliases (`MOD_*`), then the tags builtins raise and the
46// items of the builtin modules, in one list sorted by text (bytewise, so the
47// capitalized aliases come first).
48fixed_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/// What a symbol means as a list **projection** (`xs.0`): all ASCII digits
145/// make it an index, anything else a member name. Computed once, when the
146/// symbol is interned.
147#[derive(Debug, Clone, Copy, PartialEq, Eq)]
148pub(crate) enum Projection {
149    /// Not all digits: a member name such as `.get`.
150    Name,
151    /// All digits, and the index they spell.
152    Index(u32),
153    /// All digits, but too many for a `u32`: `.bad_projection`.
154    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/// The symbols a realm interned, beyond the fixed ones.
167#[derive(Default)]
168pub(crate) struct Symbols {
169    /// Entry `i` is `Sym(N_FIXED + i)`.
170    entries: Vec<Entry>,
171    /// The ids of the symbols this realm has looked up, hashed by their text:
172    /// its own entries, and each fixed symbol from its first lookup on, so a
173    /// repeated name costs one probe. Each text is stored once, in its entry or
174    /// in [`FIXED`].
175    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
203/// The fixed symbol spelled `s`, if any.
204pub(crate) fn fixed(s: &str) -> Option<Sym> {
205    FIXED.binary_search(&s).ok().map(|i| Sym(i as u32))
206}
207
208impl Ctx {
209    /// The symbol spelled `s` in this realm, interning it on first use.
210    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    /// The symbol spelled `s`, if this realm has one; interns nothing. For a
240    /// host asking for a member by name: a name never interned names nothing.
241    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    /// The text of `sym`, which must belong to this realm.
249    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    /// Runs `f` on the text of `sym` without cloning it. `f` runs while the
257    /// store is borrowed, so it must not intern.
258    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    /// What `sym` means as a list projection.
266    pub(crate) fn projection(&self, sym: Sym) -> Projection {
267        if sym.0 < N_FIXED {
268            // No fixed symbol is all digits; `fixed_are_sorted_names` checks.
269            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}