catallaxy_runtime/
dict.rs

1//! Insertion-ordered open-addressing hash table (the CPython 3.6+ layout): a dense entry array in
2//! insertion order plus a sparse index array.
3//!
4//! Key equality may require calling user code (`==` on a class), which could re-enter and mutate
5//! the table. So lookups are split: [`DictTable::candidates`] lists entries whose hash matches and
6//! whose keys are not bitwise-identical; the caller compares keys (possibly calling user code with
7//! no borrow held) and then acts by entry index, rechecking [`DictTable::version`].
8//!
9//! `Dyn` records (parsed JSON objects) start in *shape mode*: their string keys live in a shared,
10//! immutable [`Shape`] (a hidden class), reached through a transition tree from the empty shape,
11//! and the table holds only the values. Objects parsed from the same kind of document share one
12//! shape, so a `Dyn` member access can cache `(shape, slot)` per site. Deleting a key, adding a
13//! non-string key, or growing past [`MAX_SHAPE_KEYS`] converts the table to the ordinary layout.
14
15use std::sync::{Arc, LazyLock, Once};
16
17use catallaxy_gc::{RootSource, Tracer};
18use parking_lot::Mutex;
19use rustc_hash::FxHashMap;
20
21use crate::object::{mark_value, str_of};
22use crate::value::Value;
23
24/// Records with more keys than this use the ordinary table layout.
25pub const MAX_SHAPE_KEYS: usize = 32;
26/// Past this many shapes, new records use the ordinary layout (bounds memory for documents with
27/// unbounded key sets).
28const MAX_SHAPES: usize = 1 << 16;
29
30/// A hidden class: an ordered list of string keys. Shapes are immutable and live forever; their
31/// keys are frozen strings kept alive by a global root.
32pub struct Shape {
33    pub id: u32,
34    keys: Vec<(u64, Value)>,
35    transitions: Mutex<FxHashMap<Box<str>, Arc<Shape>>>,
36}
37
38struct ShapeRegistry {
39    count: usize,
40    /// Every key held by any shape, for the GC.
41    keys: Vec<Value>,
42}
43
44static REGISTRY: Mutex<ShapeRegistry> = Mutex::new(ShapeRegistry { count: 1, keys: Vec::new() });
45static ROOT_SHAPE: LazyLock<Arc<Shape>> =
46    LazyLock::new(|| Arc::new(Shape { id: 0, keys: Vec::new(), transitions: Mutex::new(FxHashMap::default()) }));
47static SHAPE_ROOTS: Once = Once::new();
48
49struct ShapeKeyRoots;
50impl RootSource for ShapeKeyRoots {
51    fn trace_roots(&self, t: &mut Tracer) {
52        // The world is stopped, so no mutator holds the registry lock.
53        for &k in REGISTRY.lock().keys.iter() {
54            mark_value(t, k);
55        }
56    }
57}
58
59impl Shape {
60    pub fn len(&self) -> usize {
61        self.keys.len()
62    }
63    pub fn is_empty(&self) -> bool {
64        self.keys.is_empty()
65    }
66
67    /// The slot of the string key `k`, if present.
68    #[inline]
69    pub fn slot_of(&self, hash: u64, k: &str) -> Option<usize> {
70        self.keys.iter().position(|&(h, key)| h == hash && str_of(key) == Some(k))
71    }
72
73    /// The shape with `key` appended, or `None` if the shape limit is reached.
74    fn add(self: &Arc<Shape>, hash: u64, key: Value) -> Option<Arc<Shape>> {
75        let k = str_of(key)?;
76        let mut tr = self.transitions.lock();
77        if let Some(next) = tr.get(k) {
78            return Some(next.clone());
79        }
80        let mut reg = REGISTRY.lock();
81        if reg.count >= MAX_SHAPES {
82            return None;
83        }
84        SHAPE_ROOTS.call_once(|| catallaxy_gc::add_global_roots(Box::new(ShapeKeyRoots)));
85        let id = reg.count as u32;
86        reg.count += 1;
87        reg.keys.push(key);
88        let mut keys = self.keys.clone();
89        keys.push((hash, key));
90        let next = Arc::new(Shape { id, keys, transitions: Mutex::new(FxHashMap::default()) });
91        tr.insert(k.into(), next.clone());
92        Some(next)
93    }
94}
95
96#[derive(Copy, Clone)]
97pub struct Entry {
98    pub hash: u64,
99    pub key: Value,
100    pub value: Value,
101}
102
103const EMPTY: u32 = u32::MAX;
104
105#[derive(Default)]
106pub struct DictTable {
107    entries: Vec<Entry>,
108    indices: Vec<u32>,
109    live: usize,
110    version: u64,
111    /// Set in shape mode; then `values` holds the entries and `entries`/`indices` are empty.
112    shape: Option<Arc<Shape>>,
113    values: Vec<Value>,
114}
115
116/// Result of probing for a key.
117pub enum Probe {
118    /// An entry with a bitwise-identical key (always equal).
119    Found(usize),
120    /// No entry with this hash; nothing to compare.
121    Absent,
122    /// Entries with the same hash that need an equality check, in probe order.
123    Check(Vec<usize>),
124}
125
126impl DictTable {
127    pub fn new() -> Self {
128        DictTable::default()
129    }
130
131    pub fn with_capacity(n: usize) -> Self {
132        let mut t = DictTable::default();
133        if n > 0 {
134            t.entries.reserve(n);
135            t.indices = vec![EMPTY; (n * 3 / 2).next_power_of_two().max(8)];
136        }
137        t
138    }
139
140    /// An empty table in shape mode, for `Dyn` records.
141    pub fn record(n: usize) -> Self {
142        DictTable { shape: Some(ROOT_SHAPE.clone()), values: Vec::with_capacity(n), ..DictTable::default() }
143    }
144
145    /// The hidden class, if the table is in shape mode.
146    #[inline]
147    pub fn shape(&self) -> Option<&Arc<Shape>> {
148        self.shape.as_ref()
149    }
150
151    /// The value in `slot` of a shape-mode table.
152    #[inline]
153    pub fn slot_value(&self, slot: usize) -> Option<Value> {
154        self.values.get(slot).copied()
155    }
156
157    /// Leaves shape mode, keeping entry indices (entry `i` is slot `i`).
158    fn leave_shape_mode(&mut self) {
159        let Some(shape) = self.shape.take() else { return };
160        let values = std::mem::take(&mut self.values);
161        let n = values.len();
162        self.entries = Vec::with_capacity(n + 1);
163        self.indices = vec![EMPTY; ((n + 1) * 3).next_power_of_two().max(8)];
164        for (i, (&(hash, key), value)) in shape.keys.iter().zip(values).enumerate() {
165            self.entries.push(Entry { hash, key, value });
166            self.place(hash, i as u32);
167        }
168        crate::note_external(self.heap_bytes());
169    }
170
171    pub fn len(&self) -> usize {
172        self.live
173    }
174    pub fn is_empty(&self) -> bool {
175        self.live == 0
176    }
177    pub fn version(&self) -> u64 {
178        self.version
179    }
180
181    pub fn heap_bytes(&self) -> usize {
182        self.entries.capacity() * std::mem::size_of::<Entry>() + self.indices.capacity() * 4 + self.values.capacity() * 8
183    }
184
185    pub fn trace(&self, t: &mut Tracer) {
186        // Shape keys are global roots.
187        for &v in &self.values {
188            mark_value(t, v);
189        }
190        for e in &self.entries {
191            if e.key != Value::TOMBSTONE {
192                mark_value(t, e.key);
193                mark_value(t, e.value);
194            }
195        }
196    }
197
198    /// Live entries in insertion order.
199    pub fn iter(&self) -> impl Iterator<Item = Entry> + '_ {
200        (0..self.raw_len()).filter_map(|i| self.raw_entry(i))
201    }
202
203    pub fn entry(&self, idx: usize) -> Entry {
204        match &self.shape {
205            Some(shape) => {
206                let (hash, key) = shape.keys[idx];
207                Entry { hash, key, value: self.values[idx] }
208            }
209            None => self.entries[idx],
210        }
211    }
212
213    pub fn set_value_at(&mut self, idx: usize, v: Value) {
214        match self.shape {
215            Some(_) => self.values[idx] = v,
216            None => self.entries[idx].value = v,
217        }
218    }
219
220    /// Entry index of the n-th live entry (for indexed iteration that tolerates growth).
221    pub fn raw_len(&self) -> usize {
222        match self.shape {
223            Some(_) => self.values.len(),
224            None => self.entries.len(),
225        }
226    }
227    pub fn raw_entry(&self, i: usize) -> Option<Entry> {
228        match self.shape {
229            Some(_) => (i < self.values.len()).then(|| self.entry(i)),
230            None => self.entries.get(i).filter(|e| e.key != Value::TOMBSTONE).copied(),
231        }
232    }
233
234    pub fn probe(&self, hash: u64, key: Value) -> Probe {
235        if let Some(shape) = &self.shape {
236            // Shape keys are all strings, and strings equal only strings.
237            return match str_of(key).and_then(|k| shape.slot_of(hash, k)) {
238                Some(i) => Probe::Found(i),
239                None => Probe::Absent,
240            };
241        }
242        if self.indices.is_empty() {
243            return Probe::Absent;
244        }
245        let mask = self.indices.len() - 1;
246        let mut i = (hash as usize) & mask;
247        let mut perturb = hash;
248        let mut check = Vec::new();
249        loop {
250            let ix = self.indices[i];
251            if ix == EMPTY {
252                return if check.is_empty() { Probe::Absent } else { Probe::Check(check) };
253            }
254            let e = &self.entries[ix as usize];
255            if e.key != Value::TOMBSTONE && e.hash == hash {
256                if e.key == key {
257                    return Probe::Found(ix as usize);
258                }
259                check.push(ix as usize);
260            }
261            perturb >>= 5;
262            i = (i.wrapping_mul(5).wrapping_add(1).wrapping_add(perturb as usize)) & mask;
263        }
264    }
265
266    /// Appends a new entry (the caller has established the key is absent).
267    pub fn insert_new(&mut self, hash: u64, key: Value, value: Value) {
268        if let Some(shape) = &self.shape {
269            if shape.len() < MAX_SHAPE_KEYS {
270                if let Some(next) = shape.add(hash, key) {
271                    self.shape = Some(next);
272                    self.values.push(value);
273                    self.live += 1;
274                    self.version += 1;
275                    return;
276                }
277            }
278            self.leave_shape_mode();
279        }
280        if (self.entries.len() + 1) * 3 >= self.indices.len() * 2 {
281            self.grow();
282        }
283        let idx = self.entries.len() as u32;
284        self.entries.push(Entry { hash, key, value });
285        self.place(hash, idx);
286        self.live += 1;
287        self.version += 1;
288    }
289
290    fn place(&mut self, hash: u64, idx: u32) {
291        let mask = self.indices.len() - 1;
292        let mut i = (hash as usize) & mask;
293        let mut perturb = hash;
294        while self.indices[i] != EMPTY {
295            perturb >>= 5;
296            i = (i.wrapping_mul(5).wrapping_add(1).wrapping_add(perturb as usize)) & mask;
297        }
298        self.indices[i] = idx;
299    }
300
301    fn grow(&mut self) {
302        // Compact tombstones and rebuild the index.
303        if self.live < self.entries.len() {
304            self.entries.retain(|e| e.key != Value::TOMBSTONE);
305        }
306        let want = ((self.live + 1) * 3).next_power_of_two().max(8);
307        self.indices = vec![EMPTY; want];
308        for i in 0..self.entries.len() {
309            let h = self.entries[i].hash;
310            self.place(h, i as u32);
311        }
312        crate::note_external(want * 4);
313    }
314
315    /// Removes the entry at `idx`, returning its value.
316    pub fn remove_at(&mut self, idx: usize) -> Value {
317        self.leave_shape_mode();
318        let e = &mut self.entries[idx];
319        let v = e.value;
320        e.key = Value::TOMBSTONE;
321        e.value = Value::NIL;
322        self.live -= 1;
323        self.version += 1;
324        // The index slot keeps pointing at the tombstone so probe chains stay intact.
325        v
326    }
327
328    pub fn clear(&mut self) {
329        if self.shape.is_some() {
330            self.shape = Some(ROOT_SHAPE.clone());
331        }
332        self.values.clear();
333        self.entries.clear();
334        self.indices.clear();
335        self.live = 0;
336        self.version += 1;
337    }
338
339    pub fn first_live(&self) -> Option<usize> {
340        if self.shape.is_some() {
341            return (!self.values.is_empty()).then_some(0);
342        }
343        self.entries.iter().position(|e| e.key != Value::TOMBSTONE)
344    }
345}
346
347impl Clone for DictTable {
348    fn clone(&self) -> Self {
349        if let Some(shape) = &self.shape {
350            return DictTable {
351                shape: Some(shape.clone()),
352                values: self.values.clone(),
353                live: self.live,
354                ..DictTable::default()
355            };
356        }
357        let mut t = DictTable::with_capacity(self.live);
358        for e in self.iter() {
359            t.insert_new(e.hash, e.key, e.value);
360        }
361        t
362    }
363}
catallaxy_runtime/dict.rs

catallaxy_runtime/
dict.rs
