subetha_pointers/
self_desc_pointer.rs

1//! `SelfDescPointer<T>` - pointer carrying type ID + layout shape in
2//! stolen high bits.
3//!
4//! Layout: a single `u64` with the high 16 bits stolen:
5//! - bits 56..=63: `type_id` (u8)
6//! - bits 53..=55: `layout` shape (3 bits, [`LayoutShape`])
7//! - bits 0..=52:  the address (53-bit virtual; ample on x86_64 / Apple Silicon)
8//!
9//! The architectural win: a heterogeneous container of
10//! `SelfDescPointer`s can dispatch on type WITHOUT a vtable lookup.
11//! When the type universe is small enough to fit in 8 bits (256
12//! distinct types), the dispatch is a switch on the high byte; the
13//! compiler can compile this to a jump table inline at the call site.
14//!
15//! # Comparison vs Rust's existing options
16//!
17//! | Mechanism                    | Per-call cost | Type universe |
18//! |------------------------------|---------------|---------------|
19//! | `dyn Trait` vtable           | 1 indirect call | unbounded   |
20//! | `enum` with variants         | tag-match     | bounded      |
21//! | `SelfDescPointer<T>`         | switch on byte | <= 256       |
22//!
23//! The architectural shape mirrors JVM compressed-klass pointers
24//! (where the klass is encoded in the top bits of an object ref)
25//! but at a lighter weight: only 8 bits + 3 layout-shape bits
26//! stolen, vs JVM's full 32-bit compressed klass.
27//!
28//! # Bit budget
29//!
30//! - 8 bits for type ID: 256 distinct types in the universe. For
31//!   wider universes use `Box<dyn Trait>` or an enum.
32//! - 3 bits for layout shape: 8 shapes covered by [`LayoutShape`].
33//! - 53 bits for address: 8 PiB virtual memory; well above any
34//!   current process.
35
36use std::marker::PhantomData;
37
38/// Address mask: low 53 bits.
39pub const ADDR_MASK: u64 = (1u64 << 53) - 1;
40/// Shape field: 3 bits at positions 53..56.
41pub const SHAPE_SHIFT: u32 = 53;
42pub const SHAPE_MASK: u64 = 0b111 << SHAPE_SHIFT;
43/// Type ID field: 8 bits at positions 56..64.
44pub const TYPE_SHIFT: u32 = 56;
45pub const TYPE_MASK: u64 = 0xFFu64 << TYPE_SHIFT;
46
47/// Layout shape encoded in 3 bits.
48#[derive(Debug, Clone, Copy, PartialEq, Eq)]
49#[repr(u8)]
50pub enum LayoutShape {
51    /// Single scalar value.
52    Scalar = 0,
53    /// Fixed-size array; length is implicit in the type ID.
54    FixedArray = 1,
55    /// Ragged / variable-length array (`Vec`-like).
56    RaggedArray = 2,
57    /// Tree node (recursive structure).
58    Tree = 3,
59    /// Graph node (cyclic references).
60    Graph = 4,
61    /// Hash table bucket.
62    HashBucket = 5,
63    /// Sparse / null-able slot.
64    Sparse = 6,
65    /// Reserved for caller-defined extensions.
66    UserDefined = 7,
67}
68
69impl LayoutShape {
70    pub fn from_bits(b: u8) -> Self {
71        match b & 0b111 {
72            0 => Self::Scalar,
73            1 => Self::FixedArray,
74            2 => Self::RaggedArray,
75            3 => Self::Tree,
76            4 => Self::Graph,
77            5 => Self::HashBucket,
78            6 => Self::Sparse,
79            _ => Self::UserDefined,
80        }
81    }
82}
83
84/// 8-byte pointer with (type_id, layout_shape, address) packed.
85#[repr(transparent)]
86pub struct SelfDescPointer<T> {
87    raw: u64,
88    _phantom: PhantomData<*const T>,
89}
90
91unsafe impl<T: Send> Send for SelfDescPointer<T> {}
92unsafe impl<T: Sync> Sync for SelfDescPointer<T> {}
93
94impl<T> SelfDescPointer<T> {
95    /// Direction signature of `SelfDescPointer<T>`. Engages the
96    /// `K_type_tag` axis (type-id + layout-shape discriminant
97    /// stored at slot for runtime type dispatch without a vtable
98    /// indirection).
99    pub const SIGNATURE: subetha_core::AxisMask = subetha_core::AxisMask::from_axes(
100        &[subetha_core::Axis::TypeTag],
101    );
102
103    /// Construct from raw pointer + type ID + layout shape.
104    ///
105    /// # Safety
106    ///
107    /// `target` must fit in 53 bits (canonical 48-bit address is
108    /// always fine; the top 11 bits MUST be zero). Caller must keep
109    /// the target alive for the lifetime of this pointer.
110    pub unsafe fn from_raw(target: *const T, type_id: u8, shape: LayoutShape) -> Self {
111        let addr = target as u64;
112        debug_assert!(
113            addr & !ADDR_MASK == 0,
114            "address {addr:#x} has bits set above 53-bit boundary"
115        );
116        let raw = ((type_id as u64) << TYPE_SHIFT)
117            | ((shape as u64) << SHAPE_SHIFT)
118            | (addr & ADDR_MASK);
119        Self { raw, _phantom: PhantomData }
120    }
121
122    /// The address, with type and layout bits masked off.
123    #[inline]
124    pub fn as_raw(&self) -> *const T {
125        (self.raw & ADDR_MASK) as *const T
126    }
127
128    /// Encoded type ID (0..=255).
129    #[inline]
130    pub const fn type_id(&self) -> u8 {
131        (self.raw >> TYPE_SHIFT) as u8
132    }
133
134    /// Encoded layout shape.
135    #[inline]
136    pub fn layout_shape(&self) -> LayoutShape {
137        LayoutShape::from_bits(((self.raw >> SHAPE_SHIFT) & 0b111) as u8)
138    }
139
140    /// Raw u64 packing for serialization or fast compare.
141    #[inline]
142    pub const fn raw(&self) -> u64 { self.raw }
143
144    /// Update type_id in place.
145    pub fn set_type_id(&mut self, new_id: u8) {
146        self.raw = (self.raw & !TYPE_MASK) | ((new_id as u64) << TYPE_SHIFT);
147    }
148
149    /// Update layout_shape in place.
150    pub fn set_layout_shape(&mut self, new_shape: LayoutShape) {
151        self.raw = (self.raw & !SHAPE_MASK) | ((new_shape as u64) << SHAPE_SHIFT);
152    }
153}
154
155impl<T> Clone for SelfDescPointer<T> {
156    fn clone(&self) -> Self { *self }
157}
158impl<T> Copy for SelfDescPointer<T> {}
159
160impl<T> std::fmt::Debug for SelfDescPointer<T> {
161    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
162        write!(f, "SelfDescPointer {{ addr: {:#x}, type_id: {}, shape: {:?} }}",
163               self.raw & ADDR_MASK, self.type_id(), self.layout_shape())
164    }
165}
166
167impl<T> PartialEq for SelfDescPointer<T> {
168    fn eq(&self, other: &Self) -> bool { self.raw == other.raw }
169}
170impl<T> Eq for SelfDescPointer<T> {}
171impl<T> std::hash::Hash for SelfDescPointer<T> {
172    fn hash<H: std::hash::Hasher>(&self, s: &mut H) { self.raw.hash(s); }
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178
179    #[test]
180    fn layout_is_8_bytes() {
181        assert_eq!(std::mem::size_of::<SelfDescPointer<u64>>(), 8);
182        assert_eq!(std::mem::align_of::<SelfDescPointer<u64>>(), 8);
183    }
184
185    #[test]
186    fn type_id_round_trips() {
187        let p = unsafe {
188            SelfDescPointer::<u64>::from_raw(0x1FFF_FFFF as *const u64, 42, LayoutShape::Scalar)
189        };
190        assert_eq!(p.type_id(), 42);
191        assert_eq!(p.layout_shape(), LayoutShape::Scalar);
192    }
193
194    #[test]
195    fn address_round_trips_under_53_bit_mask() {
196        let addr: *const u64 = 0x0001_2345_6789_ABCD as *const u64;
197        // 0x0001_2345_6789_ABCD = 0b1_0010_0011_0100_0101_0110_0111_1000_1001_1010_1011_1100_1101
198        // That is 49 bits set; bit 48 is set; bit 53 is NOT set.
199        // Let's verify it fits in 53 bits.
200        let addr_u64 = addr as u64;
201        assert_eq!(addr_u64 & !ADDR_MASK, 0, "test address fits in 53 bits");
202        let p = unsafe { SelfDescPointer::from_raw(addr, 7, LayoutShape::Tree) };
203        assert_eq!(p.as_raw(), addr);
204        assert_eq!(p.type_id(), 7);
205        assert_eq!(p.layout_shape(), LayoutShape::Tree);
206    }
207
208    #[test]
209    fn each_layout_shape_round_trips() {
210        for shape in [
211            LayoutShape::Scalar,
212            LayoutShape::FixedArray,
213            LayoutShape::RaggedArray,
214            LayoutShape::Tree,
215            LayoutShape::Graph,
216            LayoutShape::HashBucket,
217            LayoutShape::Sparse,
218            LayoutShape::UserDefined,
219        ] {
220            let p = unsafe {
221                SelfDescPointer::<u64>::from_raw(std::ptr::dangling::<u64>(), 0, shape)
222            };
223            assert_eq!(p.layout_shape(), shape, "shape {shape:?} must round-trip");
224        }
225    }
226
227    #[test]
228    fn set_type_id_preserves_address_and_shape() {
229        let mut p = unsafe {
230            SelfDescPointer::<u64>::from_raw(0xCAFE as *const u64, 10, LayoutShape::HashBucket)
231        };
232        p.set_type_id(99);
233        assert_eq!(p.type_id(), 99);
234        assert_eq!(p.layout_shape(), LayoutShape::HashBucket);
235        assert_eq!(p.as_raw() as u64, 0xCAFE);
236    }
237
238    #[test]
239    fn set_layout_preserves_address_and_type() {
240        let mut p = unsafe {
241            SelfDescPointer::<u64>::from_raw(0xBEEF as *const u64, 33, LayoutShape::Scalar)
242        };
243        p.set_layout_shape(LayoutShape::Graph);
244        assert_eq!(p.layout_shape(), LayoutShape::Graph);
245        assert_eq!(p.type_id(), 33);
246        assert_eq!(p.as_raw() as u64, 0xBEEF);
247    }
248
249    #[test]
250    fn heterogeneous_dispatch_without_vtable() {
251        // Build a Vec of SelfDescPointers with varying type IDs.
252        // Dispatch on type_id without a vtable lookup.
253        let pointers = vec![
254            unsafe { SelfDescPointer::<u8>::from_raw(std::ptr::dangling::<u8>(), 1, LayoutShape::Scalar) },
255            unsafe { SelfDescPointer::<u8>::from_raw(0x2 as *const u8, 2, LayoutShape::FixedArray) },
256            unsafe { SelfDescPointer::<u8>::from_raw(0x3 as *const u8, 1, LayoutShape::Scalar) },
257            unsafe { SelfDescPointer::<u8>::from_raw(0x4 as *const u8, 3, LayoutShape::Tree) },
258        ];
259        let mut t1 = 0;
260        let mut t2 = 0;
261        let mut t3 = 0;
262        for p in &pointers {
263            match p.type_id() {
264                1 => t1 += 1,
265                2 => t2 += 1,
266                3 => t3 += 1,
267                _ => {}
268            }
269        }
270        assert_eq!((t1, t2, t3), (2, 1, 1));
271    }
272}
subetha_pointers/self_desc_pointer.rs

subetha_pointers/
self_desc_pointer.rs
