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_LIST = "List",
54    MOD_MAP = "Map",
55    MOD_MOD = "Mod",
56    MOD_STR = "Str",
57    MOD_SYM = "Sym",
58    MOD_UNIT = "Unit",
59    ADD = "add",
60    AND = "and",
61    APPEND = "append",
62    BAD_CODEPOINT = "bad_codepoint",
63    BAD_PROJECTION = "bad_projection",
64    BAD_SYMBOL = "bad_symbol",
65    CANNOT_PARSE_INT = "cannot_parse_int",
66    CAT = "cat",
67    CATCH = "catch",
68    DIV_BY_ZERO = "div_by_zero",
69    DIVREM = "divrem",
70    EQ = "eq",
71    EXPORTS = "exports",
72    FALSE = "false",
73    FOR = "for",
74    FOREIGN_OBJECT = "foreign_object",
75    FROM = "from",
76    GE = "ge",
77    GET = "get",
78    GETS = "gets",
79    GT = "gt",
80    LE = "le",
81    LIST_SIZE_MISMATCH = "list_size_mismatch",
82    LT = "lt",
83    MAP_SIZE_MISMATCH = "map_size_mismatch",
84    MERGE = "merge",
85    MISSING_KEY = "missing_key",
86    MISSING_PROPERTY = "missing_property",
87    MODULE_ARITY = "module_arity",
88    MUL = "mul",
89    NAME = "name",
90    NEGATIVE_EXPONENT = "negative_exponent",
91    NIL = "nil",
92    NO_MATCH = "no_match",
93    NO_MODULE = "no_module",
94    NOT = "not",
95    NOT_A_BOOL = "not_a_bool",
96    NOT_A_LIST = "not_a_list",
97    NOT_A_MAP = "not_a_map",
98    NOT_A_MODULE = "not_a_module",
99    NOT_A_STR = "not_a_str",
100    NOT_A_SYM = "not_a_sym",
101    NOT_AN_INT = "not_an_int",
102    NOT_AN_OBJECT = "not_an_object",
103    NOT_APPLICABLE = "not_applicable",
104    NOT_INT = "not_int",
105    NOT_STRING = "not_string",
106    NOT_UNIT = "not_unit",
107    OR = "or",
108    PACK = "pack",
109    PARSE = "parse",
110    POW = "pow",
111    PROJECTION_OUT_OF_RANGE = "projection_out_of_range",
112    RAISE = "raise",
113    SIZE = "size",
114    SPLIT = "split",
115    STR = "str",
116    SUB = "sub",
117    TRUE = "true",
118    UNPACK = "unpack",
119    WITH = "with",
120    WITHOUT = "without",
121}
122
123/// What a symbol means as a list **projection** (`xs.0`): all ASCII digits
124/// make it an index, anything else a member name. Computed once, when the
125/// symbol is interned.
126#[derive(Debug, Clone, Copy, PartialEq, Eq)]
127pub(crate) enum Projection {
128    /// Not all digits: a member name such as `.get`.
129    Name,
130    /// All digits, and the index they spell.
131    Index(u32),
132    /// All digits, but too many for a `u32`: `.bad_projection`.
133    TooLarge,
134}
135
136impl Projection {
137    fn of(text: &str) -> Projection {
138        if text.is_empty() || !text.bytes().all(|b| b.is_ascii_digit()) {
139            return Projection::Name;
140        }
141        text.parse().map_or(Projection::TooLarge, Projection::Index)
142    }
143}
144
145/// The symbols a realm interned, beyond the fixed ones.
146#[derive(Default)]
147pub(crate) struct Symbols {
148    /// Entry `i` is `Sym(N_FIXED + i)`.
149    entries: Vec<Entry>,
150    /// The ids of the symbols this realm has looked up, hashed by their text:
151    /// its own entries, and each fixed symbol from its first lookup on, so a
152    /// repeated name costs one probe. Each text is stored once, in its entry or
153    /// in [`FIXED`].
154    index: HashTable<u32>,
155}
156
157struct Entry {
158    text: Text,
159    hash: u64,
160    proj: Projection,
161}
162
163impl Symbols {
164    fn find(&self, s: &str, hash: u64) -> Option<Sym> {
165        self.index
166            .find(hash, |&id| self.str_of(id) == s)
167            .map(|&id| Sym(id))
168    }
169
170    fn str_of(&self, id: u32) -> &str {
171        match FIXED.get(id as usize) {
172            Some(s) => s,
173            None => &self.entries[(id - N_FIXED) as usize].text,
174        }
175    }
176
177    fn entry(&self, sym: Sym) -> &Entry {
178        &self.entries[(sym.0 - N_FIXED) as usize]
179    }
180}
181
182/// The fixed symbol spelled `s`, if any.
183pub(crate) fn fixed(s: &str) -> Option<Sym> {
184    FIXED.binary_search(&s).ok().map(|i| Sym(i as u32))
185}
186
187impl Ctx {
188    /// The symbol spelled `s` in this realm, interning it on first use.
189    pub fn intern(&self, s: &str) -> Sym {
190        let hash = fnv1a(s.as_bytes());
191        let mut syms = self.syms.borrow_mut();
192        if let Some(sym) = syms.find(s, hash) {
193            return sym;
194        }
195        let Symbols { entries, index } = &mut *syms;
196        let sym = match fixed(s) {
197            Some(sym) => sym,
198            None => {
199                let id = u32::try_from(entries.len())
200                    .ok()
201                    .and_then(|i| i.checked_add(N_FIXED))
202                    .expect("fewer than 2^32 symbols");
203                entries.push(Entry {
204                    text: Text::from(s),
205                    hash,
206                    proj: Projection::of(s),
207                });
208                Sym(id)
209            }
210        };
211        index.insert_unique(hash, sym.0, |&id| match FIXED.get(id as usize) {
212            Some(s) => fnv1a(s.as_bytes()),
213            None => entries[(id - N_FIXED) as usize].hash,
214        });
215        sym
216    }
217
218    /// The symbol spelled `s`, if this realm has one; interns nothing. For a
219    /// host asking for a member by name: a name never interned names nothing.
220    pub fn sym(&self, s: &str) -> Option<Sym> {
221        self.syms
222            .borrow()
223            .find(s, fnv1a(s.as_bytes()))
224            .or_else(|| fixed(s))
225    }
226
227    /// The text of `sym`, which must belong to this realm.
228    pub fn text(&self, sym: Sym) -> Text {
229        match FIXED.get(sym.0 as usize) {
230            Some(s) => Text::from_static(s),
231            None => self.syms.borrow().entry(sym).text.clone(),
232        }
233    }
234
235    /// Runs `f` on the text of `sym` without cloning it. `f` runs while the
236    /// store is borrowed, so it must not intern.
237    pub(crate) fn with_str<R>(&self, sym: Sym, f: impl FnOnce(&str) -> R) -> R {
238        match FIXED.get(sym.0 as usize) {
239            Some(s) => f(s),
240            None => f(&self.syms.borrow().entry(sym).text),
241        }
242    }
243
244    /// What `sym` means as a list projection.
245    pub(crate) fn projection(&self, sym: Sym) -> Projection {
246        if sym.0 < N_FIXED {
247            // No fixed symbol is all digits; `fixed_are_sorted_names` checks.
248            return Projection::Name;
249        }
250        self.syms.borrow().entry(sym).proj
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257
258    #[test]
259    fn fixed_are_sorted_names() {
260        assert!(
261            FIXED.windows(2).all(|w| w[0] < w[1]),
262            "sorted, no duplicates"
263        );
264        assert!(FIXED.iter().all(|s| Projection::of(s) == Projection::Name));
265        assert_eq!(FIXED[Sym::DIV_BY_ZERO.0 as usize], "div_by_zero");
266        assert_eq!(FIXED[Sym::MOD_STR.0 as usize], "Str");
267        assert_eq!(FIXED[Sym::STR.0 as usize], "str");
268    }
269
270    #[test]
271    fn a_fixed_symbol_is_found_not_interned() {
272        let ctx = Ctx::new();
273        assert_eq!(ctx.intern("no_match"), Sym::NO_MATCH);
274        assert_eq!(ctx.sym("Int"), Some(Sym::MOD_INT));
275        assert_eq!(ctx.text(Sym::ADD), "add");
276        assert!(ctx.syms.borrow().entries.is_empty());
277    }
278
279    #[test]
280    fn interning_twice_gives_one_symbol() {
281        let ctx = Ctx::new();
282        let a = ctx.intern("apple");
283        let b = ctx.intern("banana");
284        assert_ne!(a, b);
285        assert_eq!(ctx.intern("apple"), a);
286        assert_eq!(ctx.text(a), "apple");
287        assert_eq!(ctx.with_str(b, str::len), 6);
288        assert_eq!(ctx.syms.borrow().entries.len(), 2);
289    }
290
291    #[test]
292    fn looking_up_interns_nothing() {
293        let ctx = Ctx::new();
294        assert_eq!(ctx.sym("pear"), None);
295        assert!(ctx.syms.borrow().entries.is_empty());
296        let p = ctx.intern("pear");
297        assert_eq!(ctx.sym("pear"), Some(p));
298    }
299
300    #[test]
301    fn many_symbols_stay_distinct() {
302        let ctx = Ctx::new();
303        let syms: Vec<Sym> = (0..1000)
304            .map(|i| ctx.intern(&alloc::format!("s{i}")))
305            .collect();
306        for (i, &s) in syms.iter().enumerate() {
307            assert_eq!(ctx.intern(&alloc::format!("s{i}")), s);
308            assert_eq!(ctx.text(s), alloc::format!("s{i}").as_str());
309        }
310    }
311
312    #[test]
313    fn a_projection_is_computed_once_interned() {
314        let ctx = Ctx::new();
315        let p = |s| ctx.projection(ctx.intern(s));
316        assert_eq!(p("0"), Projection::Index(0));
317        assert_eq!(p("12"), Projection::Index(12));
318        assert_eq!(p("4294967295"), Projection::Index(u32::MAX));
319        assert_eq!(p("4294967296"), Projection::TooLarge);
320        assert_eq!(p("1a"), Projection::Name);
321        assert_eq!(p("get"), Projection::Name);
322        assert_eq!(p(""), Projection::Name);
323    }
324}
elly_core/sym.rs

elly_core/
sym.rs
