verit-core 0.2.0

//! Deterministic struct layout. Because the layout is a pure function of the
//! schema, a schema id fully determines every byte offset — the schema acts
//! as one shared "vtable" for every message that uses it, which is what makes
//! per-message zero-copy access possible without per-object tables.
//!
//! Two layout disciplines:
//!
//! - **Fixed** (sparse and dense structs): every field has a constant slot
//!   offset. Sparse structs prefix a presence bitmap; dense structs omit it.
//! - **Packed** (sparse data, small wire): only *present* fields get slots,
//!   laid down in size-class order after the presence bitmap. A field's offset
//!   is recovered in O(1) from the bitmap with popcount rank queries — no
//!   per-object vtable, no wasted slots. See [`PackedLayout`].

use crate::schema::{FieldDef, StructMode, Type};

/// Slot size classes, largest first. Packed fields are grouped by these so
/// that natural alignment is preserved without padding between elements.
const CLASS_SIZES: [u32; 4] = [8, 4, 2, 1];

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum StructLayout {
    Fixed(FixedLayout),
    Packed(PackedLayout),
}

impl StructLayout {
    pub fn align(&self) -> u32 {
        match self {
            StructLayout::Fixed(f) => f.align,
            StructLayout::Packed(p) => p.align,
        }
    }

    pub fn is_packed(&self) -> bool {
        matches!(self, StructLayout::Packed(_))
    }

    /// Access the fixed layout, panicking if this is a packed struct. Callers
    /// that never handle packed types (e.g. codegen, which rejects them) use
    /// this; the panic marks a real invariant break, not user error.
    pub fn as_fixed(&self) -> &FixedLayout {
        match self {
            StructLayout::Fixed(f) => f,
            StructLayout::Packed(_) => panic!("expected a fixed-layout struct, found packed"),
        }
    }

    pub fn as_packed(&self) -> &PackedLayout {
        match self {
            StructLayout::Packed(p) => p,
            StructLayout::Fixed(_) => panic!("expected a packed struct, found fixed"),
        }
    }
}

/// Fixed layout: constant slot offset per field. `bitmap_bytes` is 0 for a
/// dense struct (no presence bitmap), otherwise `ceil(field_count / 8)`.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FixedLayout {
    pub bitmap_bytes: u32,
    /// Slot offset (relative to the struct block start) per field position.
    pub slots: Vec<u32>,
    /// Total block size, padded to `align`.
    pub size: u32,
    /// Max field alignment (at least 1).
    pub align: u32,
    pub dense: bool,
}

/// Packed layout: the block is a presence bitmap followed by slots for the
/// *present* fields only, grouped into size classes (8/4/2/1 bytes) in that
/// order. Block size and every slot offset depend on which fields are
/// present, so both are computed per message from the bitmap — in O(1) via
/// popcount. Limited to 64 fields so the bitmap fits one `u64` rank word.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PackedLayout {
    /// Presence bitmap size, `ceil(field_count / 8)` bytes (1..=8).
    pub bitmap_bytes: u32,
    /// Offset where field data begins: `align_up(bitmap_bytes, align)`.
    pub data_start: u32,
    /// Max field alignment across the schema (>= 1).
    pub align: u32,
    /// Per field position (ID-sorted).
    pub fields: Vec<PackedField>,
    /// `class_masks[k]` has bit `p` set iff field `p` belongs to size class
    /// `CLASS_SIZES[k]`.
    pub class_masks: [u64; 4],
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PackedField {
    /// Slot size class in bytes (1/2/4/8). Heap refs are the 4-byte class.
    pub size: u32,
    pub align: u32,
    /// Index into `CLASS_SIZES` for this field's class.
    pub class: usize,
    /// Bits of `class_masks[class]` for positions strictly before this field;
    /// its popcount gives the field's rank within its class.
    pub same_low_mask: u64,
}

impl PackedLayout {
    /// Byte offset of field `pos` (which must be present) given the message's
    /// presence `bitmap`. O(1): a fixed number of popcounts.
    pub fn field_offset(&self, bitmap: u64, pos: usize) -> u32 {
        let f = &self.fields[pos];
        let mut off = self.data_start;
        // Bytes consumed by all present fields in strictly larger classes.
        for (&mask, &size) in self
            .class_masks
            .iter()
            .zip(CLASS_SIZES.iter())
            .take(f.class)
        {
            off += (bitmap & mask).count_ones() * size;
        }
        // Plus present same-class fields that precede this one.
        off += (bitmap & f.same_low_mask).count_ones() * f.size;
        off
    }

    /// Total block size for a message with this presence `bitmap`.
    pub fn block_size(&self, bitmap: u64) -> u32 {
        let mut off = self.data_start;
        for (&mask, &size) in self.class_masks.iter().zip(CLASS_SIZES.iter()) {
            off += (bitmap & mask).count_ones() * size;
        }
        align_up(off, self.align)
    }
}

pub fn align_up(x: u32, align: u32) -> u32 {
    debug_assert!(align.is_power_of_two());
    (x + align - 1) & !(align - 1)
}

/// Size and alignment of a field slot within a struct block. Heap types
/// (string/bytes/list/struct) occupy a u32 absolute-offset slot.
pub fn slot_size_align(ty: &Type) -> (u32, u32) {
    match ty {
        Type::Bool | Type::U8 | Type::I8 => (1, 1),
        Type::U16 | Type::I16 => (2, 2),
        Type::U32 | Type::I32 | Type::F32 | Type::Enum(_) => (4, 4),
        Type::U64 | Type::I64 | Type::F64 => (8, 8),
        Type::String
        | Type::Bytes
        | Type::List(_)
        | Type::Struct(_)
        | Type::Map(_, _)
        | Type::Union(_) => (4, 4),
    }
}

/// Byte offset of a `union`'s payload within its block: the `u32` tag sits at
/// offset 0, then the payload slot at its natural alignment. Every
/// implementation derives it the same way from the selected variant type.
pub fn union_payload_offset(variant: &Type) -> u32 {
    let (_, align) = slot_size_align(variant);
    align_up(4, align)
}

/// Layout of one `map<K, V>` entry block. An entry is exactly a **dense
/// 2-field struct** — key at implicit field id 0, value at id 1 — so every
/// implementation derives the same key/value slot offsets, stride, and
/// alignment from `K` and `V` alone, no schema type needed. `slots[0]` is the
/// key offset, `slots[1]` the value; `size` is the entry stride.
pub fn map_entry_layout(key: &Type, value: &Type) -> FixedLayout {
    let fields = [
        FieldDef {
            id: 0,
            name: String::new(),
            ty: key.clone(),
            default: None,
        },
        FieldDef {
            id: 1,
            name: String::new(),
            ty: value.clone(),
            default: None,
        },
    ];
    compute_fixed(&fields, true)
}

fn class_index(size: u32) -> usize {
    match size {
        8 => 0,
        4 => 1,
        2 => 2,
        _ => 3,
    }
}

/// Compute the layout for a struct's fields (which must be ID-sorted, as they
/// are in a validated schema).
pub fn compute(fields: &[FieldDef], mode: StructMode) -> StructLayout {
    match mode {
        StructMode::Packed => StructLayout::Packed(compute_packed(fields)),
        StructMode::Dense => StructLayout::Fixed(compute_fixed(fields, true)),
        StructMode::Sparse => StructLayout::Fixed(compute_fixed(fields, false)),
    }
}

/// Fixed placement: order fields by (alignment desc, id asc) so they pack
/// without gaps after the bitmap.
fn compute_fixed(fields: &[FieldDef], dense: bool) -> FixedLayout {
    let n = fields.len();
    let bitmap_bytes = if dense { 0 } else { (n as u32).div_ceil(8) };
    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by_key(|&i| {
        (
            std::cmp::Reverse(slot_size_align(&fields[i].ty).1),
            fields[i].id,
        )
    });
    let mut cursor = bitmap_bytes;
    let mut slots = vec![0u32; n];
    let mut max_align = 1u32;
    for i in order {
        let (size, align) = slot_size_align(&fields[i].ty);
        max_align = max_align.max(align);
        cursor = align_up(cursor, align);
        slots[i] = cursor;
        cursor += size;
    }
    FixedLayout {
        bitmap_bytes,
        slots,
        size: align_up(cursor, max_align),
        align: max_align,
        dense,
    }
}

fn compute_packed(fields: &[FieldDef]) -> PackedLayout {
    let n = fields.len();
    debug_assert!(n <= 64, "packed structs are limited to 64 fields");
    let bitmap_bytes = (n as u32).div_ceil(8);
    let mut class_masks = [0u64; 4];
    let mut sizes_aligns = Vec::with_capacity(n);
    let mut max_align = 1u32;
    for (p, f) in fields.iter().enumerate() {
        let (size, align) = slot_size_align(&f.ty);
        max_align = max_align.max(align);
        let class = class_index(size);
        class_masks[class] |= 1u64 << p;
        sizes_aligns.push((size, align, class));
    }
    let align = max_align;
    let data_start = align_up(bitmap_bytes, align);
    let mut pfields = Vec::with_capacity(n);
    for (p, &(size, align, class)) in sizes_aligns.iter().enumerate() {
        let low_bits = if p == 0 { 0 } else { (1u64 << p) - 1 };
        pfields.push(PackedField {
            size,
            align,
            class,
            same_low_mask: class_masks[class] & low_bits,
        });
    }
    PackedLayout {
        bitmap_bytes,
        data_start,
        align,
        fields: pfields,
        class_masks,
    }
}