sim_kernel/
table.rs

1//! The table contract: the pluggable [`Table`] and [`Dir`] backend protocol.
2//!
3//! The kernel defines the table/directory protocols and a backend registry;
4//! concrete table representations are libs loaded against it, with `AssocTable`
5//! provided as a baseline backend rather than kernel-fixed behavior.
6
7use std::{
8    collections::BTreeMap,
9    sync::{Arc, RwLock, RwLockReadGuard, RwLockWriteGuard},
10};
11
12use crate::{
13    catalog::CatalogBackend,
14    env::Cx,
15    error::{Error, Result},
16    expr::Expr,
17    id::{CORE_TABLE_CLASS_ID, Symbol},
18    object::{ClassRef, Object},
19    value::{RuntimeObject, Value},
20};
21
22/// Expected state supplied to an atomic table compare-exchange.
23#[derive(Clone, Debug, PartialEq)]
24pub enum TableExpected {
25    /// The key must not be present (distinct from a present `nil`).
26    Absent,
27    /// The key must contain a value with this canonical semantic expression.
28    Value(Expr),
29}
30
31/// Mutation performed when a table compare-exchange matches.
32#[derive(Clone)]
33pub enum TableReplacement {
34    /// Remove the entry.
35    Delete,
36    /// Store this value.
37    Value(Value),
38}
39
40/// State observed at the linearization point of compare-exchange.
41#[derive(Clone, Debug, PartialEq)]
42pub enum TableObserved {
43    /// The key was absent.
44    Absent,
45    /// The key was present, including when this expression is `nil`.
46    Value(Expr),
47}
48
49/// Result of an atomic table compare-exchange.
50#[derive(Clone, Debug, PartialEq)]
51pub struct TableCompareExchange {
52    /// Whether the replacement was applied.
53    pub exchanged: bool,
54    /// State observed before any successful replacement.
55    pub observed: TableObserved,
56}
57
58/// Universal map surface. Keys are symbols; values are runtime values.
59pub trait Table: RuntimeObject {
60    /// Symbol identifying the backend representation.
61    fn backend_symbol(&self) -> Symbol;
62
63    /// Looks up `key`, returning nil when absent.
64    fn get(&self, cx: &mut Cx, key: Symbol) -> Result<Value>;
65
66    /// Inserts or replaces the value for `key`.
67    fn set(&self, cx: &mut Cx, key: Symbol, value: Value) -> Result<()>;
68
69    /// Whether `key` is present.
70    fn has(&self, cx: &mut Cx, key: Symbol) -> Result<bool>;
71
72    /// Removes `key`, returning its prior value or nil.
73    fn del(&self, cx: &mut Cx, key: Symbol) -> Result<Value>;
74
75    /// All keys, in backend order.
76    fn keys(&self, cx: &mut Cx) -> Result<Vec<Symbol>>;
77
78    /// All key/value pairs, in backend order.
79    fn entries(&self, cx: &mut Cx) -> Result<Vec<(Symbol, Value)>>;
80
81    /// Number of entries.
82    fn len(&self, cx: &mut Cx) -> Result<usize>;
83
84    /// Whether the table has no entries.
85    fn is_empty(&self, cx: &mut Cx) -> Result<bool> {
86        Ok(self.len(cx)? == 0)
87    }
88
89    /// Removes all entries.
90    fn clear(&self, cx: &mut Cx) -> Result<()>;
91
92    /// Atomically replaces `key` iff its state equals `expected`.
93    ///
94    /// Equality is canonical semantic [`Expr`] equality. Implementations must
95    /// establish one linearization point or honestly report unsupported.
96    fn compare_exchange(
97        &self,
98        _cx: &mut Cx,
99        _key: Symbol,
100        _expected: TableExpected,
101        _replacement: TableReplacement,
102    ) -> Result<TableCompareExchange> {
103        Err(Error::Eval(format!(
104            "table/compare-exchange unsupported by {}",
105            self.backend_symbol()
106        )))
107    }
108
109    /// Projects the table to an [`Expr::Map`].
110    fn as_table_expr(&self, cx: &mut Cx) -> Result<Expr> {
111        let entries = self.entries(cx)?;
112        let mut pairs = Vec::with_capacity(entries.len());
113        for (key, value) in entries {
114            pairs.push((Expr::Symbol(key), value.object().as_expr(cx)?));
115        }
116        Ok(Expr::Map(pairs))
117    }
118
119    /// Order-insensitive equality against another table's entries.
120    fn table_eq(&self, cx: &mut Cx, other: &dyn Table) -> Result<bool> {
121        let mut left = self.entries(cx)?;
122        let mut right = other.entries(cx)?;
123        left.sort_by(|a, b| a.0.cmp(&b.0));
124        right.sort_by(|a, b| a.0.cmp(&b.0));
125        Ok(left == right)
126    }
127}
128
129/// Hierarchical table surface for backends that support nested subtables.
130pub trait Dir: Table {
131    /// Creates a nested subtable under `name`, returning it.
132    fn mkdir(&self, cx: &mut Cx, name: Symbol) -> Result<Value>;
133
134    /// Opens the subtable at `name`, or `Ok(None)` when absent.
135    fn opendir(&self, cx: &mut Cx, name: Symbol) -> Result<Option<Value>>;
136
137    /// Removes the subtable at `name`, returning it.
138    fn rmdir(&self, cx: &mut Cx, name: Symbol) -> Result<Value>;
139
140    /// Whether `name` resolves to a subtable.
141    fn is_dir(&self, cx: &mut Cx, name: Symbol) -> Result<bool>;
142}
143
144/// Baseline table backend backed by an association list under a lock.
145// sim-non-citizen(reason = "kernel table backing object; canonical form is native table entries", kind = "private", descriptor = "")
146// AssocTable is the built-in bootstrap table backend. It implements the same
147// Table/TableBackend contracts as loadable table backends.
148pub struct AssocTable {
149    entries: RwLock<Vec<(Symbol, Value)>>,
150}
151
152impl AssocTable {
153    /// Builds an empty table.
154    pub fn new() -> Self {
155        Self {
156            entries: RwLock::new(Vec::new()),
157        }
158    }
159
160    /// Builds a table seeded with the given entries.
161    pub fn with_entries(entries: Vec<(Symbol, Value)>) -> Self {
162        Self {
163            entries: RwLock::new(entries),
164        }
165    }
166
167    fn read_entries(&self) -> Result<RwLockReadGuard<'_, Vec<(Symbol, Value)>>> {
168        self.entries.read().map_err(|_| poisoned_table_error())
169    }
170
171    fn write_entries(&self) -> Result<RwLockWriteGuard<'_, Vec<(Symbol, Value)>>> {
172        self.entries.write().map_err(|_| poisoned_table_error())
173    }
174}
175
176impl Default for AssocTable {
177    fn default() -> Self {
178        Self::new()
179    }
180}
181
182impl Object for AssocTable {
183    fn display(&self, _cx: &mut Cx) -> Result<String> {
184        Ok(format!("table[{}]", self.read_entries()?.len()))
185    }
186
187    fn as_any(&self) -> &dyn std::any::Any {
188        self
189    }
190}
191
192impl crate::ObjectCompat for AssocTable {
193    fn class(&self, cx: &mut Cx) -> Result<ClassRef> {
194        let symbol = Symbol::qualified("core", "Table");
195        if let Some(value) = cx.registry().class_by_symbol(&symbol) {
196            return Ok(value.clone());
197        }
198        cx.factory().class_stub(CORE_TABLE_CLASS_ID, symbol)
199    }
200    fn as_expr(&self, cx: &mut Cx) -> Result<Expr> {
201        self.as_table_expr(cx)
202    }
203    fn truth(&self, _cx: &mut Cx) -> Result<bool> {
204        Ok(!self.read_entries()?.is_empty())
205    }
206    fn as_table_impl(&self) -> Option<&dyn Table> {
207        Some(self)
208    }
209}
210
211impl Table for AssocTable {
212    fn backend_symbol(&self) -> Symbol {
213        Symbol::qualified("core", "Table")
214    }
215
216    fn get(&self, cx: &mut Cx, key: Symbol) -> Result<Value> {
217        let guard = self.read_entries()?;
218        match guard.iter().find(|(candidate, _)| *candidate == key) {
219            Some((_, value)) => Ok(value.clone()),
220            None => cx.factory().nil(),
221        }
222    }
223
224    fn set(&self, _cx: &mut Cx, key: Symbol, value: Value) -> Result<()> {
225        let mut guard = self.write_entries()?;
226        if let Some((_, slot)) = guard.iter_mut().find(|(candidate, _)| *candidate == key) {
227            *slot = value;
228        } else {
229            guard.push((key, value));
230        }
231        Ok(())
232    }
233
234    fn has(&self, _cx: &mut Cx, key: Symbol) -> Result<bool> {
235        Ok(self
236            .read_entries()?
237            .iter()
238            .any(|(candidate, _)| *candidate == key))
239    }
240
241    fn del(&self, cx: &mut Cx, key: Symbol) -> Result<Value> {
242        let mut guard = self.write_entries()?;
243        if let Some(index) = guard.iter().position(|(candidate, _)| *candidate == key) {
244            Ok(guard.remove(index).1)
245        } else {
246            cx.factory().nil()
247        }
248    }
249
250    fn keys(&self, _cx: &mut Cx) -> Result<Vec<Symbol>> {
251        Ok(self
252            .read_entries()?
253            .iter()
254            .map(|(key, _)| key.clone())
255            .collect())
256    }
257
258    fn entries(&self, _cx: &mut Cx) -> Result<Vec<(Symbol, Value)>> {
259        Ok(self.read_entries()?.clone())
260    }
261
262    fn len(&self, _cx: &mut Cx) -> Result<usize> {
263        Ok(self.read_entries()?.len())
264    }
265
266    fn clear(&self, _cx: &mut Cx) -> Result<()> {
267        self.write_entries()?.clear();
268        Ok(())
269    }
270
271    fn compare_exchange(
272        &self,
273        cx: &mut Cx,
274        key: Symbol,
275        expected: TableExpected,
276        replacement: TableReplacement,
277    ) -> Result<TableCompareExchange> {
278        let replacement = match replacement {
279            TableReplacement::Delete => None,
280            TableReplacement::Value(value) => Some((value.object().as_expr(cx)?, value)),
281        };
282        let mut guard = self.write_entries()?;
283        let index = guard.iter().position(|(candidate, _)| *candidate == key);
284        let observed = match index {
285            Some(index) => TableObserved::Value(guard[index].1.object().as_expr(cx)?),
286            None => TableObserved::Absent,
287        };
288        let matches = match (&expected, &observed) {
289            (TableExpected::Absent, TableObserved::Absent) => true,
290            (TableExpected::Value(left), TableObserved::Value(right)) => left == right,
291            _ => false,
292        };
293        if matches {
294            match (index, replacement) {
295                (Some(index), None) => {
296                    guard.remove(index);
297                }
298                (None, None) => {}
299                (Some(index), Some((_, value))) => guard[index].1 = value,
300                (None, Some((_, value))) => guard.push((key, value)),
301            }
302        }
303        Ok(TableCompareExchange {
304            exchanged: matches,
305            observed,
306        })
307    }
308}
309
310fn poisoned_table_error() -> Error {
311    Error::Eval("assoc table lock poisoned".to_owned())
312}
313
314/// Factory protocol for constructing tables in a particular representation.
315pub trait TableBackend: Send + Sync {
316    /// Stable name the backend is registered and selected under.
317    fn name(&self) -> &str;
318
319    /// Builds a table from an initial set of entries.
320    fn new_table(&self, cx: &mut Cx, entries: Vec<(Symbol, Value)>) -> Result<Value>;
321}
322
323/// Registry of named table backends with one active default.
324pub struct TableRegistry {
325    backends: BTreeMap<String, Arc<dyn TableBackend>>,
326    active: String,
327}
328
329impl TableRegistry {
330    /// Builds a registry preloaded with the `assoc` and catalog backends.
331    pub fn new() -> Self {
332        let mut registry = Self {
333            backends: BTreeMap::new(),
334            active: "assoc".to_owned(),
335        };
336        registry.register(Arc::new(AssocBackend));
337        registry.register(Arc::new(CatalogBackend));
338        registry
339    }
340
341    /// Registers a backend under its own name, replacing any prior one.
342    pub fn register(&mut self, backend: Arc<dyn TableBackend>) {
343        self.backends.insert(backend.name().to_owned(), backend);
344    }
345
346    /// Selects the active backend by name, erroring if it is unknown.
347    pub fn set_active(&mut self, name: &str) -> Result<()> {
348        if self.backends.contains_key(name) {
349            self.active = name.to_owned();
350            Ok(())
351        } else {
352            Err(Error::Eval(format!("unknown table backend: {name}")))
353        }
354    }
355
356    /// Name of the currently active backend.
357    pub fn active(&self) -> &str {
358        &self.active
359    }
360
361    /// Builds a table using the active backend.
362    pub fn new_table(&self, cx: &mut Cx, entries: Vec<(Symbol, Value)>) -> Result<Value> {
363        self.backend()?.new_table(cx, entries)
364    }
365
366    fn backend(&self) -> Result<&Arc<dyn TableBackend>> {
367        self.backends
368            .get(&self.active)
369            .ok_or_else(|| Error::Eval("active table backend missing".to_owned()))
370    }
371}
372
373impl Default for TableRegistry {
374    fn default() -> Self {
375        Self::new()
376    }
377}
378
379struct AssocBackend;
380
381impl TableBackend for AssocBackend {
382    fn name(&self) -> &str {
383        "assoc"
384    }
385
386    fn new_table(&self, cx: &mut Cx, entries: Vec<(Symbol, Value)>) -> Result<Value> {
387        cx.factory()
388            .opaque(Arc::new(AssocTable::with_entries(entries)))
389    }
390}
391
392#[cfg(test)]
393#[path = "table_tests.rs"]
394mod table_tests;
sim_kernel/table.rs

sim_kernel/
table.rs
