jay/
symbol.rs

1//! The symbol table: J's `s:` names, held once each and referred to by a
2//! small integer.
3//!
4//! A symbol is an atom whose value is a name. Two symbols made from the
5//! same text ARE the same atom — `(s: <'a') = (s: <'a')` is 1 however far
6//! apart the two sentences stand — so the text lives in one process-wide
7//! table and an array of symbols is an array of indices into it. The table
8//! is append-only: an index, once handed out, names the same text for the
9//! life of the process, which is what lets [`Data::Symbol`] hold plain
10//! `u32`s and copy, slice and index like any other flat buffer.
11//!
12//! Index 0 is the empty name. It is the fill element, so overtaking an
13//! array of symbols needs no table lookup.
14//!
15//! Symbols order by their TEXT, not by the order they were interned in, so
16//! every comparison resolves its operands here first.
17//!
18//! [`Data::Symbol`]: crate::array::Data::Symbol
19
20use std::collections::HashMap;
21use std::sync::{Arc, OnceLock, RwLock};
22
23/// A symbol's index into the table. `u32` is the width J's own type code
24/// implies and leaves an array of symbols half the size of one of boxes.
25pub type Id = u32;
26
27/// The empty name, which is also the fill element.
28pub const EMPTY: Id = 0;
29
30struct Table {
31    names: Vec<Arc<str>>,
32    ids: HashMap<Arc<str>, Id>,
33}
34
35fn table() -> &'static RwLock<Table> {
36    static TABLE: OnceLock<RwLock<Table>> = OnceLock::new();
37    TABLE.get_or_init(|| {
38        let empty: Arc<str> = Arc::from("");
39        RwLock::new(Table {
40            names: vec![empty.clone()],
41            ids: HashMap::from([(empty, EMPTY)]),
42        })
43    })
44}
45
46/// The id of `name`, adding it to the table if it is new.
47///
48/// Panics only if the table is exhausted, which needs four billion distinct
49/// names in one process.
50pub fn intern(name: &str) -> Id {
51    let lock = table();
52    if let Some(&id) = lock.read().expect("symbol table").ids.get(name) {
53        return id;
54    }
55    let mut t = lock.write().expect("symbol table");
56    // Another thread may have added it between the two locks.
57    if let Some(&id) = t.ids.get(name) {
58        return id;
59    }
60    let id = Id::try_from(t.names.len()).expect("symbol table index");
61    let shared: Arc<str> = Arc::from(name);
62    t.names.push(shared.clone());
63    t.ids.insert(shared, id);
64    id
65}
66
67/// The name `id` stands for. An id this process never handed out gives the
68/// empty name rather than panicking; no caller can produce one.
69pub fn name(id: Id) -> Arc<str> {
70    table()
71        .read()
72        .expect("symbol table")
73        .names
74        .get(id as usize)
75        .cloned()
76        .unwrap_or_else(|| Arc::from(""))
77}
78
79/// The names of many ids under one lock, which is what a comparison, a sort
80/// or a display of a whole array wants.
81pub fn names(ids: &[Id]) -> Vec<Arc<str>> {
82    let t = table().read().expect("symbol table");
83    ids.iter()
84        .map(|&id| t.names.get(id as usize).cloned().unwrap_or_else(|| Arc::from("")))
85        .collect()
86}
87
88/// How many distinct names the process has interned, the empty one
89/// included. It only ever grows.
90pub fn interned() -> usize {
91    table().read().expect("symbol table").names.len()
92}
93
94/// Order two symbols by their names.
95pub fn cmp(a: Id, b: Id) -> std::cmp::Ordering {
96    if a == b {
97        return std::cmp::Ordering::Equal;
98    }
99    let t = table().read().expect("symbol table");
100    let of = |id: Id| t.names.get(id as usize).map(Arc::as_ref).unwrap_or("");
101    of(a).cmp(of(b))
102}
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn the_empty_name_is_id_zero() {
110        assert_eq!(intern(""), EMPTY);
111        assert_eq!(&*name(EMPTY), "");
112    }
113
114    #[test]
115    fn the_same_text_interns_to_the_same_id() {
116        let a = intern("libjay-test-alpha");
117        let b = intern("libjay-test-alpha");
118        assert_eq!(a, b);
119        assert_ne!(a, intern("libjay-test-beta"));
120        assert_eq!(&*name(a), "libjay-test-alpha");
121    }
122
123    #[test]
124    fn symbols_order_by_text_not_by_when_they_were_interned() {
125        // "zzz" is interned first and still sorts last.
126        let z = intern("libjay-test-zzz");
127        let a = intern("libjay-test-aaa");
128        assert!(z > a || a > z);
129        assert_eq!(cmp(z, a), std::cmp::Ordering::Greater);
130    }
131}
jay/symbol.rs

jay/
symbol.rs
