verit_core/
layout.rs

1//! Deterministic struct layout. Because the layout is a pure function of the
2//! schema, a schema id fully determines every byte offset — the schema acts
3//! as one shared "vtable" for every message that uses it, which is what makes
4//! per-message zero-copy access possible without per-object tables.
5//!
6//! Two layout disciplines:
7//!
8//! - **Fixed** (sparse and dense structs): every field has a constant slot
9//!   offset. Sparse structs prefix a presence bitmap; dense structs omit it.
10//! - **Packed** (sparse data, small wire): only *present* fields get slots,
11//!   laid down in size-class order after the presence bitmap. A field's offset
12//!   is recovered in O(1) from the bitmap with popcount rank queries — no
13//!   per-object vtable, no wasted slots. See [`PackedLayout`].
14
15use crate::schema::{FieldDef, StructMode, Type};
16
17/// Slot size classes, largest first. Packed fields are grouped by these so
18/// that natural alignment is preserved without padding between elements.
19const CLASS_SIZES: [u32; 4] = [8, 4, 2, 1];
20
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub enum StructLayout {
23    Fixed(FixedLayout),
24    Packed(PackedLayout),
25}
26
27impl StructLayout {
28    pub fn align(&self) -> u32 {
29        match self {
30            StructLayout::Fixed(f) => f.align,
31            StructLayout::Packed(p) => p.align,
32        }
33    }
34
35    pub fn is_packed(&self) -> bool {
36        matches!(self, StructLayout::Packed(_))
37    }
38
39    /// Access the fixed layout, panicking if this is a packed struct. Callers
40    /// that never handle packed types (e.g. codegen, which rejects them) use
41    /// this; the panic marks a real invariant break, not user error.
42    pub fn as_fixed(&self) -> &FixedLayout {
43        match self {
44            StructLayout::Fixed(f) => f,
45            StructLayout::Packed(_) => panic!("expected a fixed-layout struct, found packed"),
46        }
47    }
48
49    pub fn as_packed(&self) -> &PackedLayout {
50        match self {
51            StructLayout::Packed(p) => p,
52            StructLayout::Fixed(_) => panic!("expected a packed struct, found fixed"),
53        }
54    }
55}
56
57/// Fixed layout: constant slot offset per field. `bitmap_bytes` is 0 for a
58/// dense struct (no presence bitmap), otherwise `ceil(field_count / 8)`.
59#[derive(Clone, Debug, PartialEq, Eq)]
60pub struct FixedLayout {
61    pub bitmap_bytes: u32,
62    /// Slot offset (relative to the struct block start) per field position.
63    pub slots: Vec<u32>,
64    /// Total block size, padded to `align`.
65    pub size: u32,
66    /// Max field alignment (at least 1).
67    pub align: u32,
68    pub dense: bool,
69}
70
71/// Packed layout: the block is a presence bitmap followed by slots for the
72/// *present* fields only, grouped into size classes (8/4/2/1 bytes) in that
73/// order. Block size and every slot offset depend on which fields are
74/// present, so both are computed per message from the bitmap — in O(1) via
75/// popcount. Limited to 64 fields so the bitmap fits one `u64` rank word.
76#[derive(Clone, Debug, PartialEq, Eq)]
77pub struct PackedLayout {
78    /// Presence bitmap size, `ceil(field_count / 8)` bytes (1..=8).
79    pub bitmap_bytes: u32,
80    /// Offset where field data begins: `align_up(bitmap_bytes, align)`.
81    pub data_start: u32,
82    /// Max field alignment across the schema (>= 1).
83    pub align: u32,
84    /// Per field position (ID-sorted).
85    pub fields: Vec<PackedField>,
86    /// `class_masks[k]` has bit `p` set iff field `p` belongs to size class
87    /// `CLASS_SIZES[k]`.
88    pub class_masks: [u64; 4],
89}
90
91#[derive(Clone, Debug, PartialEq, Eq)]
92pub struct PackedField {
93    /// Slot size class in bytes (1/2/4/8). Heap refs are the 4-byte class.
94    pub size: u32,
95    pub align: u32,
96    /// Index into `CLASS_SIZES` for this field's class.
97    pub class: usize,
98    /// Bits of `class_masks[class]` for positions strictly before this field;
99    /// its popcount gives the field's rank within its class.
100    pub same_low_mask: u64,
101}
102
103impl PackedLayout {
104    /// Byte offset of field `pos` (which must be present) given the message's
105    /// presence `bitmap`. O(1): a fixed number of popcounts.
106    pub fn field_offset(&self, bitmap: u64, pos: usize) -> u32 {
107        let f = &self.fields[pos];
108        let mut off = self.data_start;
109        // Bytes consumed by all present fields in strictly larger classes.
110        for (&mask, &size) in self
111            .class_masks
112            .iter()
113            .zip(CLASS_SIZES.iter())
114            .take(f.class)
115        {
116            off += (bitmap & mask).count_ones() * size;
117        }
118        // Plus present same-class fields that precede this one.
119        off += (bitmap & f.same_low_mask).count_ones() * f.size;
120        off
121    }
122
123    /// Total block size for a message with this presence `bitmap`.
124    pub fn block_size(&self, bitmap: u64) -> u32 {
125        let mut off = self.data_start;
126        for (&mask, &size) in self.class_masks.iter().zip(CLASS_SIZES.iter()) {
127            off += (bitmap & mask).count_ones() * size;
128        }
129        align_up(off, self.align)
130    }
131}
132
133pub fn align_up(x: u32, align: u32) -> u32 {
134    debug_assert!(align.is_power_of_two());
135    (x + align - 1) & !(align - 1)
136}
137
138/// Size and alignment of a field slot within a struct block. Heap types
139/// (string/bytes/list/struct) occupy a u32 absolute-offset slot.
140pub fn slot_size_align(ty: &Type) -> (u32, u32) {
141    match ty {
142        Type::Bool | Type::U8 | Type::I8 => (1, 1),
143        Type::U16 | Type::I16 => (2, 2),
144        Type::U32 | Type::I32 | Type::F32 | Type::Enum(_) => (4, 4),
145        Type::U64 | Type::I64 | Type::F64 => (8, 8),
146        Type::String
147        | Type::Bytes
148        | Type::List(_)
149        | Type::Struct(_)
150        | Type::Map(_, _)
151        | Type::Union(_) => (4, 4),
152    }
153}
154
155/// Byte offset of a `union`'s payload within its block: the `u32` tag sits at
156/// offset 0, then the payload slot at its natural alignment. Every
157/// implementation derives it the same way from the selected variant type.
158pub fn union_payload_offset(variant: &Type) -> u32 {
159    let (_, align) = slot_size_align(variant);
160    align_up(4, align)
161}
162
163/// Layout of one `map<K, V>` entry block. An entry is exactly a **dense
164/// 2-field struct** — key at implicit field id 0, value at id 1 — so every
165/// implementation derives the same key/value slot offsets, stride, and
166/// alignment from `K` and `V` alone, no schema type needed. `slots[0]` is the
167/// key offset, `slots[1]` the value; `size` is the entry stride.
168pub fn map_entry_layout(key: &Type, value: &Type) -> FixedLayout {
169    let fields = [
170        FieldDef {
171            id: 0,
172            name: String::new(),
173            ty: key.clone(),
174            default: None,
175        },
176        FieldDef {
177            id: 1,
178            name: String::new(),
179            ty: value.clone(),
180            default: None,
181        },
182    ];
183    compute_fixed(&fields, true)
184}
185
186fn class_index(size: u32) -> usize {
187    match size {
188        8 => 0,
189        4 => 1,
190        2 => 2,
191        _ => 3,
192    }
193}
194
195/// Compute the layout for a struct's fields (which must be ID-sorted, as they
196/// are in a validated schema).
197pub fn compute(fields: &[FieldDef], mode: StructMode) -> StructLayout {
198    match mode {
199        StructMode::Packed => StructLayout::Packed(compute_packed(fields)),
200        StructMode::Dense => StructLayout::Fixed(compute_fixed(fields, true)),
201        StructMode::Sparse => StructLayout::Fixed(compute_fixed(fields, false)),
202    }
203}
204
205/// Fixed placement: order fields by (alignment desc, id asc) so they pack
206/// without gaps after the bitmap.
207fn compute_fixed(fields: &[FieldDef], dense: bool) -> FixedLayout {
208    let n = fields.len();
209    let bitmap_bytes = if dense { 0 } else { (n as u32).div_ceil(8) };
210    let mut order: Vec<usize> = (0..n).collect();
211    order.sort_by_key(|&i| {
212        (
213            std::cmp::Reverse(slot_size_align(&fields[i].ty).1),
214            fields[i].id,
215        )
216    });
217    let mut cursor = bitmap_bytes;
218    let mut slots = vec![0u32; n];
219    let mut max_align = 1u32;
220    for i in order {
221        let (size, align) = slot_size_align(&fields[i].ty);
222        max_align = max_align.max(align);
223        cursor = align_up(cursor, align);
224        slots[i] = cursor;
225        cursor += size;
226    }
227    FixedLayout {
228        bitmap_bytes,
229        slots,
230        size: align_up(cursor, max_align),
231        align: max_align,
232        dense,
233    }
234}
235
236fn compute_packed(fields: &[FieldDef]) -> PackedLayout {
237    let n = fields.len();
238    debug_assert!(n <= 64, "packed structs are limited to 64 fields");
239    let bitmap_bytes = (n as u32).div_ceil(8);
240    let mut class_masks = [0u64; 4];
241    let mut sizes_aligns = Vec::with_capacity(n);
242    let mut max_align = 1u32;
243    for (p, f) in fields.iter().enumerate() {
244        let (size, align) = slot_size_align(&f.ty);
245        max_align = max_align.max(align);
246        let class = class_index(size);
247        class_masks[class] |= 1u64 << p;
248        sizes_aligns.push((size, align, class));
249    }
250    let align = max_align;
251    let data_start = align_up(bitmap_bytes, align);
252    let mut pfields = Vec::with_capacity(n);
253    for (p, &(size, align, class)) in sizes_aligns.iter().enumerate() {
254        let low_bits = if p == 0 { 0 } else { (1u64 << p) - 1 };
255        pfields.push(PackedField {
256            size,
257            align,
258            class,
259            same_low_mask: class_masks[class] & low_bits,
260        });
261    }
262    PackedLayout {
263        bitmap_bytes,
264        data_start,
265        align,
266        fields: pfields,
267        class_masks,
268    }
269}
verit_core/layout.rs

verit_core/
layout.rs
