Skip to main content

dive_core/
handle.rs

1//! Handles: 64-bit tagged value words.
2//!
3//! The low three bits are a tag. Scalars are inline; compounds are an index
4//! into the persistent store or into the owning worker's transient arena.
5
6/// The tag of a handle.
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub enum Tag {
9    /// A 61-bit signed integer.
10    Int,
11    /// A boolean.
12    Bool,
13    /// A string id into the string table.
14    Str,
15    /// A model value: its name's id in the string table. A model value and
16    /// the string with the same text are different values.
17    Model,
18    /// A compound in the persistent store.
19    Persistent,
20    /// A compound in a worker's transient arena.
21    Transient,
22    /// The empty marker: an unassigned variable or an unforced thunk.
23    Empty,
24}
25
26const TAG_BITS: u32 = 3;
27const TAG_MASK: u64 = 0b111;
28const T_INT: u64 = 0;
29const T_BOOL: u64 = 1;
30const T_STR: u64 = 2;
31const T_MODEL: u64 = 3;
32// Tag 6 is unused: big integers are compounds (`Kind::BigInt`).
33const T_PERSISTENT: u64 = 4;
34const T_TRANSIENT: u64 = 5;
35const T_EMPTY: u64 = 7;
36
37const SHARD_BITS: u32 = 8;
38const CLASS_BITS: u32 = 2;
39/// The number of store size classes (`store.rs`).
40pub(crate) const CLASSES: usize = 4;
41/// The store class of persistent lazy nodes (constants only).
42pub(crate) const LAZY_CLASS: u8 = 3;
43/// The bound on a node index within one shard and size class.
44pub(crate) const MAX_CLASS_INDEX: u64 = (1 << 29) - 1;
45
46/// The largest inline integer.
47pub const INT_MAX: i64 = (1 << 60) - 1;
48/// The smallest inline integer.
49pub const INT_MIN: i64 = -(1 << 60);
50
51/// A value word. Equal handles are equal values; for two persistent handles
52/// the converse holds too, because the store is hash-consed.
53#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
54pub struct Handle(pub(crate) u64);
55
56impl std::fmt::Debug for Handle {
57    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
58        match self.tag() {
59            Tag::Int => write!(f, "Int({})", self.int_unchecked()),
60            Tag::Bool => write!(f, "Bool({})", self.0 >> TAG_BITS != 0),
61            Tag::Str => write!(f, "Str#{}", self.0 >> TAG_BITS),
62            Tag::Model => write!(f, "Model#{}", self.0 >> TAG_BITS),
63            Tag::Persistent => {
64                let (s, c, i) = self.persistent_parts();
65                write!(f, "P{s}:{c}:{i}")
66            }
67            Tag::Transient => {
68                let (e, i) = self.transient_parts();
69                write!(f, "T{e}:{i}")
70            }
71            Tag::Empty => write!(f, "Empty"),
72        }
73    }
74}
75
76impl Handle {
77    /// The empty marker.
78    pub const EMPTY: Self = Self(T_EMPTY);
79    /// `TRUE`.
80    pub const TRUE: Self = Self((1 << TAG_BITS) | T_BOOL);
81    /// `FALSE`.
82    pub const FALSE: Self = Self(T_BOOL);
83
84    /// The raw bits, for hashing keys.
85    #[must_use]
86    pub const fn bits(self) -> u64 {
87        self.0
88    }
89
90    /// The tag.
91    #[must_use]
92    pub const fn tag(self) -> Tag {
93        match self.0 & TAG_MASK {
94            T_INT => Tag::Int,
95            T_BOOL => Tag::Bool,
96            T_STR => Tag::Str,
97            T_MODEL => Tag::Model,
98            T_PERSISTENT => Tag::Persistent,
99            T_TRANSIENT => Tag::Transient,
100            _ => Tag::Empty,
101        }
102    }
103
104    /// An inline integer, if it fits in 61 bits.
105    #[must_use]
106    pub const fn int(v: i64) -> Option<Self> {
107        if v < INT_MIN || v > INT_MAX {
108            None
109        } else {
110            #[allow(clippy::cast_sign_loss, reason = "two's complement packing")]
111            Some(Self(((v << TAG_BITS) as u64) | T_INT))
112        }
113    }
114
115    /// A boolean.
116    #[must_use]
117    pub const fn bool(b: bool) -> Self {
118        if b { Self::TRUE } else { Self::FALSE }
119    }
120
121    /// A string by id.
122    #[must_use]
123    pub const fn string(id: u32) -> Self {
124        Self(((id as u64) << TAG_BITS) | T_STR)
125    }
126
127    /// A model value by its name's string id.
128    #[must_use]
129    pub const fn model(id: u32) -> Self {
130        Self(((id as u64) << TAG_BITS) | T_MODEL)
131    }
132
133    pub(crate) const fn persistent(shard: u8, class: u8, index: u64) -> Self {
134        Self(
135            (((index << (SHARD_BITS + CLASS_BITS))
136                | ((class as u64) << SHARD_BITS)
137                | shard as u64)
138                << TAG_BITS)
139                | T_PERSISTENT,
140        )
141    }
142
143    pub(crate) const fn transient(epoch: u32, index: u32) -> Self {
144        Self(((((epoch as u64) << 32) | index as u64) << TAG_BITS) | T_TRANSIENT)
145    }
146
147    /// The integer, if this is one.
148    #[must_use]
149    pub const fn as_int(self) -> Option<i64> {
150        if self.0 & TAG_MASK == T_INT {
151            Some(self.int_unchecked())
152        } else {
153            None
154        }
155    }
156
157    #[allow(clippy::cast_possible_wrap, reason = "two's complement unpacking")]
158    const fn int_unchecked(self) -> i64 {
159        (self.0 as i64) >> TAG_BITS
160    }
161
162    /// The boolean, if this is one.
163    #[must_use]
164    pub const fn as_bool(self) -> Option<bool> {
165        if self.0 & TAG_MASK == T_BOOL {
166            Some(self.0 >> TAG_BITS != 0)
167        } else {
168            None
169        }
170    }
171
172    /// The string id, if this is a string.
173    #[must_use]
174    pub const fn as_str_id(self) -> Option<u32> {
175        if self.0 & TAG_MASK == T_STR {
176            #[allow(clippy::cast_possible_truncation, reason = "ids are 32-bit")]
177            Some((self.0 >> TAG_BITS) as u32)
178        } else {
179            None
180        }
181    }
182
183    /// The name's string id, if this is a model value.
184    #[must_use]
185    pub const fn as_model_id(self) -> Option<u32> {
186        if self.0 & TAG_MASK == T_MODEL {
187            #[allow(clippy::cast_possible_truncation, reason = "ids are 32-bit")]
188            Some((self.0 >> TAG_BITS) as u32)
189        } else {
190            None
191        }
192    }
193
194    /// Whether this is a compound (persistent or transient).
195    #[must_use]
196    pub const fn is_compound(self) -> bool {
197        matches!(self.0 & TAG_MASK, T_PERSISTENT | T_TRANSIENT)
198    }
199
200    /// Whether this is a transient compound.
201    #[must_use]
202    pub const fn is_transient(self) -> bool {
203        self.0 & TAG_MASK == T_TRANSIENT
204    }
205
206    /// Whether this is a persistent compound.
207    #[must_use]
208    pub const fn is_persistent(self) -> bool {
209        self.0 & TAG_MASK == T_PERSISTENT
210    }
211
212    /// Whether this is a persistent lazy node (a lazy constant), which is
213    /// not hash-consed by value: such handles must not be compared.
214    #[must_use]
215    /// Lazy values and view-flagged nodes ([`crate::node::flags::VIEW`])
216    /// share this class: both are interned structurally, apart from
217    /// identities.
218    pub const fn is_lazy_persistent(self) -> bool {
219        self.is_persistent() && self.persistent_parts().1 == LAZY_CLASS
220    }
221
222    /// Whether this is the empty marker.
223    #[must_use]
224    pub const fn is_empty(self) -> bool {
225        self.0 & TAG_MASK == T_EMPTY
226    }
227
228    /// The shard, size class and index of a persistent handle.
229    #[allow(clippy::cast_possible_truncation, reason = "packed fields")]
230    #[inline]
231    pub(crate) const fn persistent_parts(self) -> (u8, u8, u64) {
232        let p = self.0 >> TAG_BITS;
233        (
234            (p & 0xff) as u8,
235            ((p >> SHARD_BITS) & ((1 << CLASS_BITS) - 1)) as u8,
236            p >> (SHARD_BITS + CLASS_BITS),
237        )
238    }
239
240    #[allow(clippy::cast_possible_truncation, reason = "packed fields")]
241    pub(crate) const fn transient_parts(self) -> (u32, u32) {
242        let p = self.0 >> TAG_BITS;
243        ((p >> 32) as u32, p as u32)
244    }
245}
246
247/// The 64-bit finalizer used for every hash (a `splitmix64`-style mixer).
248#[must_use]
249#[inline]
250pub const fn mix64(mut z: u64) -> u64 {
251    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
252    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
253    z ^ (z >> 31)
254}
255
256/// Combines a key hash and a value hash (an entry of a function or record).
257#[must_use]
258#[inline]
259pub const fn mix2(a: u64, b: u64) -> u64 {
260    mix64(a ^ b.rotate_left(29).wrapping_mul(0x9e37_79b9_7f4a_7c15))
261}
262
263pub(crate) const K_BOOL: u64 = 0x1f83_d9ab_fb41_bd6b;
264pub(crate) const K_INT: u64 = 0x5be0_cd19_137e_2179;
265pub(crate) const K_STR: u64 = 0x6a09_e667_f3bc_c908;
266pub(crate) const K_SET: u64 = 0x3c6e_f372_fe94_f82b;
267pub(crate) const K_FCN: u64 = 0xa54f_f53a_5f1d_36f1;
268pub(crate) const K_SYM: u64 = 0x510e_527f_ade6_82d1;
269pub(crate) const K_MODEL: u64 = 0x1f83_d9ab_5be0_cd19;
270/// The kind constant of a state hash.
271pub const K_STATE: u64 = 0x9b05_688c_2b3e_6c1f;
272
273/// `fin(K, len, Σ)`: the final mix of an additive hash.
274#[must_use]
275#[inline]
276pub const fn fin(k: u64, len: u64, sum: u64) -> u64 {
277    mix64(sum ^ mix64(k.wrapping_add(len.wrapping_mul(0x9e37_79b9_7f4a_7c15))))
278}
279
280/// The hash of a scalar handle (`None` for a compound).
281#[must_use]
282#[inline]
283pub const fn scalar_hash(h: Handle) -> Option<u64> {
284    match h.0 & TAG_MASK {
285        T_INT => Some(int_hash(h.int_unchecked())),
286        T_BOOL => Some(mix64(K_BOOL ^ (h.0 >> TAG_BITS))),
287        T_STR => Some(mix64(K_STR ^ (h.0 >> TAG_BITS))),
288        T_MODEL => Some(mix64(K_MODEL ^ (h.0 >> TAG_BITS))),
289        _ => None,
290    }
291}
292
293/// The hash of an integer, shared by integer keys of functions.
294#[must_use]
295#[inline]
296pub const fn int_hash(v: i64) -> u64 {
297    #[allow(clippy::cast_sign_loss, reason = "bit reinterpretation for hashing")]
298    mix64((v as u64) ^ K_INT)
299}
300
301/// The contribution of variable `i` with value hash `h` to a state's sum.
302#[must_use]
303#[inline]
304pub const fn state_term(i: usize, h: u64) -> u64 {
305    mix2(mix64(K_STATE ^ i as u64), h)
306}
307
308#[cfg(test)]
309mod tests {
310    use super::*;
311
312    #[test]
313    fn integers_round_trip_at_the_bounds() {
314        for v in [0, 1, -1, INT_MAX, INT_MIN, 12345, -9876] {
315            let h = Handle::int(v).unwrap_or(Handle::EMPTY);
316            assert_eq!(h.as_int(), Some(v));
317            assert_eq!(h.tag(), Tag::Int);
318        }
319        assert!(Handle::int(INT_MAX + 1).is_none());
320        assert!(Handle::int(INT_MIN - 1).is_none());
321    }
322
323    #[test]
324    fn compound_parts_round_trip() {
325        let p = Handle::persistent(200, 2, (1 << 40) + 7);
326        assert_eq!(p.persistent_parts(), (200, 2, (1 << 40) + 7));
327        assert!(p.is_persistent());
328        let t = Handle::transient(0x1fff_ffff, 0xffff_fff0);
329        assert_eq!(t.transient_parts(), (0x1fff_ffff, 0xffff_fff0));
330        assert!(t.is_transient());
331        assert_eq!(Handle::TRUE.as_bool(), Some(true));
332        assert_eq!(Handle::FALSE.as_bool(), Some(false));
333        assert_eq!(Handle::string(9).as_str_id(), Some(9));
334        assert!(Handle::EMPTY.is_empty());
335    }
336}