oxide_core/heap/
atom.rs

1//! The atom table and `PropertyKey`.
2//!
3//! An atom is a string record with `is_atom` set, found by content through the
4//! table. An atom lives as long as something holds it, like any string: a
5//! shape, a dictionary, a live dynamic unit's key list, a value. The atoms
6//! interned while the runtime is created or before the program runs are
7//! pinned and live as long as the heap ([`AtomMode`](super::AtomMode)); a
8//! swept atom leaves the table.
9//!
10//! `PropertyKey(u32)` is tagged: bit 31 marks an immediate array index
11//! (`0 ..= 2^31 - 1`), which never enters the atom table; otherwise bit 30
12//! separates symbols from atoms. Array indices from `2^31` to `2^32 - 2` are
13//! atoms whose record caches the index, so key ordering still treats them as
14//! indices.
15
16use std::fmt;
17
18use super::arena::Arena;
19use super::hash::FxHashMap;
20use super::string::{StringRecord, StringRepr};
21use crate::value::{StringId, SymbolId, Value};
22
23const INDEX_TAG: u32 = 1 << 31;
24const SYMBOL_TAG: u32 = 1 << 30;
25/// Exclusive bound on string and symbol indices that fit in a key.
26pub const KEY_INDEX_LIMIT: u32 = SYMBOL_TAG;
27
28#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
29pub struct PropertyKey(u32);
30
31#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub enum KeyKind {
33    Index(u32),
34    String(StringId),
35    Symbol(SymbolId),
36}
37
38impl PropertyKey {
39    /// An immediate index key, for `index < 2^31`.
40    #[inline]
41    pub const fn index(index: u32) -> Option<PropertyKey> {
42        if index < INDEX_TAG {
43            Some(PropertyKey(index | INDEX_TAG))
44        } else {
45            None
46        }
47    }
48
49    /// The key of an atom. Panics if the atom index does not fit (callers
50    /// allocate atoms below [`KEY_INDEX_LIMIT`]).
51    #[inline]
52    pub fn atom(id: StringId) -> PropertyKey {
53        assert!(id.0 < KEY_INDEX_LIMIT, "atom index out of key range");
54        PropertyKey(id.0)
55    }
56
57    #[inline]
58    pub fn symbol(id: SymbolId) -> PropertyKey {
59        assert!(id.0 < KEY_INDEX_LIMIT, "symbol index out of key range");
60        PropertyKey(id.0 | SYMBOL_TAG)
61    }
62
63    #[inline]
64    pub const fn kind(self) -> KeyKind {
65        if self.0 & INDEX_TAG != 0 {
66            KeyKind::Index(self.0 & !INDEX_TAG)
67        } else if self.0 & SYMBOL_TAG != 0 {
68            KeyKind::Symbol(SymbolId(self.0 & !SYMBOL_TAG))
69        } else {
70            KeyKind::String(StringId(self.0))
71        }
72    }
73
74    #[inline]
75    pub const fn raw(self) -> u32 {
76        self.0
77    }
78
79    /// The key whose [`raw`](Self::raw) bits are `bits`: an instruction's
80    /// `imm` field. Every bit pattern decodes to some key.
81    #[inline]
82    pub const fn from_raw(bits: u32) -> PropertyKey {
83        PropertyKey(bits)
84    }
85
86    /// The key as a value: an Int32 for an index, else the string or symbol.
87    #[inline]
88    pub const fn to_value(self) -> Value {
89        match self.kind() {
90            KeyKind::Index(index) => Value::int32(index as i32),
91            KeyKind::String(id) => Value::string(id),
92            KeyKind::Symbol(id) => Value::symbol(id),
93        }
94    }
95
96    /// The heap value the key keeps alive, if any.
97    #[inline]
98    pub const fn heap_value(self) -> Option<Value> {
99        match self.kind() {
100            KeyKind::Index(_) => None,
101            KeyKind::String(id) => Some(Value::string(id)),
102            KeyKind::Symbol(id) => Some(Value::symbol(id)),
103        }
104    }
105}
106
107impl fmt::Debug for PropertyKey {
108    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
109        match self.kind() {
110            KeyKind::Index(index) => write!(f, "Key::Index({index})"),
111            KeyKind::String(id) => write!(f, "Key::Atom({})", id.0),
112            KeyKind::Symbol(id) => write!(f, "Key::Symbol({})", id.0),
113        }
114    }
115}
116
117/// A bucket value: an atom index, or with [`OVERFLOW`] set an index into the
118/// collision lists. Atom indices stay below [`KEY_INDEX_LIMIT`], so the tag bit
119/// is free.
120const OVERFLOW: u32 = 1 << 31;
121
122/// Content → atom. Buckets are keyed by the content hash and compared by
123/// content against the string arena, so the table stores no second copy of any
124/// string; an entry is 8 bytes.
125#[derive(Default)]
126pub struct AtomTable {
127    buckets: FxHashMap<u32, u32>,
128    collisions: Vec<Vec<StringId>>,
129    /// Collision lists no bucket uses.
130    free_collisions: Vec<u32>,
131    count: usize,
132}
133
134impl AtomTable {
135    pub fn find(
136        &self,
137        strings: &Arena<StringRecord>,
138        repr: &StringRepr,
139        hash: u32,
140    ) -> Option<StringId> {
141        self.find_by(hash, |id| strings.get(id.0).flat() == Some(repr))
142    }
143
144    /// [`Self::find`] for the content of a one-byte representation.
145    pub fn find_one_byte(
146        &self,
147        strings: &Arena<StringRecord>,
148        bytes: &[u8],
149        hash: u32,
150    ) -> Option<StringId> {
151        self.find_by(hash, |id| {
152            matches!(strings.get(id.0).flat(), Some(StringRepr::OneByte(atom)) if **atom == *bytes)
153        })
154    }
155
156    fn find_by(&self, hash: u32, matches: impl Fn(&StringId) -> bool) -> Option<StringId> {
157        let bucket = *self.buckets.get(&hash)?;
158        if bucket & OVERFLOW == 0 {
159            let id = StringId(bucket);
160            matches(&id).then_some(id)
161        } else {
162            self.collisions[(bucket & !OVERFLOW) as usize]
163                .iter()
164                .copied()
165                .find(matches)
166        }
167    }
168
169    pub fn insert(&mut self, hash: u32, id: StringId) {
170        debug_assert!(id.0 < KEY_INDEX_LIMIT);
171        self.count += 1;
172        match self.buckets.get_mut(&hash) {
173            None => {
174                self.buckets.insert(hash, id.0);
175            }
176            Some(bucket) if *bucket & OVERFLOW == 0 => {
177                let ids = vec![StringId(*bucket), id];
178                let list = match self.free_collisions.pop() {
179                    Some(list) => {
180                        self.collisions[list as usize] = ids;
181                        list
182                    }
183                    None => {
184                        self.collisions.push(ids);
185                        self.collisions.len() as u32 - 1
186                    }
187                };
188                *bucket = list | OVERFLOW;
189            }
190            Some(bucket) => self.collisions[(*bucket & !OVERFLOW) as usize].push(id),
191        }
192    }
193
194    /// Removes atom `id`, whose content hashes to `hash` (it is being
195    /// swept).
196    pub fn remove(&mut self, hash: u32, id: StringId) {
197        let Some(bucket) = self.buckets.get_mut(&hash) else {
198            debug_assert!(false, "an atom outside the table");
199            return;
200        };
201        if *bucket & OVERFLOW == 0 {
202            debug_assert_eq!(*bucket, id.0);
203            self.buckets.remove(&hash);
204        } else {
205            let list = *bucket & !OVERFLOW;
206            let ids = &mut self.collisions[list as usize];
207            let Some(position) = ids.iter().position(|&other| other == id) else {
208                debug_assert!(false, "an atom outside the table");
209                return;
210            };
211            ids.swap_remove(position);
212            if let [last] = ids[..] {
213                *bucket = last.0;
214                self.collisions[list as usize] = Vec::new();
215                self.free_collisions.push(list);
216            }
217        }
218        self.count -= 1;
219    }
220
221    pub fn len(&self) -> usize {
222        self.count
223    }
224
225    pub fn is_empty(&self) -> bool {
226        self.count == 0
227    }
228
229    pub fn ids(&self) -> impl Iterator<Item = StringId> + '_ {
230        self.buckets.values().flat_map(move |&bucket| {
231            let ids: &[StringId] = if bucket & OVERFLOW == 0 {
232                &[]
233            } else {
234                &self.collisions[(bucket & !OVERFLOW) as usize]
235            };
236            let single = (bucket & OVERFLOW == 0).then_some(StringId(bucket));
237            single.into_iter().chain(ids.iter().copied())
238        })
239    }
240
241    /// Approximate bytes of the table itself (not the string records).
242    pub fn bytes(&self) -> usize {
243        self.buckets.capacity() * (size_of::<(u32, u32)>() + 1)
244            + self
245                .collisions
246                .iter()
247                .map(|ids| 24 + ids.capacity() * 4)
248                .sum::<usize>()
249    }
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255
256    #[test]
257    fn key_tags_round_trip() {
258        assert_eq!(PropertyKey::index(0).unwrap().kind(), KeyKind::Index(0));
259        let max = INDEX_TAG - 1;
260        assert_eq!(PropertyKey::index(max).unwrap().kind(), KeyKind::Index(max));
261        assert_eq!(PropertyKey::index(INDEX_TAG), None);
262        assert_eq!(
263            PropertyKey::atom(StringId(5)).kind(),
264            KeyKind::String(StringId(5))
265        );
266        assert_eq!(
267            PropertyKey::symbol(SymbolId(5)).kind(),
268            KeyKind::Symbol(SymbolId(5))
269        );
270        assert_ne!(
271            PropertyKey::atom(StringId(5)),
272            PropertyKey::symbol(SymbolId(5))
273        );
274        assert_eq!(PropertyKey::index(7).unwrap().to_value(), Value::int32(7));
275        assert_eq!(PropertyKey::index(7).unwrap().heap_value(), None);
276    }
277}
oxide_core/heap/atom.rs

oxide_core/heap/
atom.rs
