graven/

rt.rs

//! Support for code generated by the Graven compiler (and the hand-written code in
//! `graven-schemas` that freezes its pattern). Items marked `#[doc(hidden)]` are called only
//! by generated code; the rest ([`ListR`], [`VListR`], [`VStrList`], [`ListW`],
//! [`StreamW`]) appear in generated signatures.
//!
//! All `unsafe` of the generated pattern lives here and in
//! [`TableRef::str_unchecked`]: [`FromVerified::from_verified`], [`VListR::new`] and
//! [`VStrList::new`]. Generated code has no `unsafe` blocks of its own beyond calling these
//! fixed-contract functions, each item carrying `#[allow(unsafe_code)]` and a `// SAFETY:`
//! comment that cites the invariant below.
//!
//! # Generated pattern (frozen by hand in `graven-schemas`)
//!
//! - **The caller charges the header.** [`FromTable::verify`] never charges its own header
//!   (`2 + fixed_len`). The public inherent method `X::verify(&self, ctx)` is the "as root"
//!   entry point: it charges `2 + fixed_len` and calls `FromTable::verify`; `X::verified` /
//!   `X::verified_with` only call the inherent `X::verify` (they do not charge again). A
//!   table/union field charges `2 + fixed_len` of the target and calls the child's
//!   `FromTable::verify` (or the child's inherent `verify`, which does both); [`ListR::verify`]
//!   charges the elements and calls `FromTable::verify` on each one. `[string]` / `[bytes]` go
//!   through [`verify_strs`] / [`verify_bytes_list`]. The totals are those of spec §7.3.
//! - **A single kind of view.** Every table generates `XVerified<'a>` with explicit accessors
//!   (never `Deref`) and `reader()`; strings via `str_unchecked`, tables via `YVerified`,
//!   table lists via [`VListR`], `[string]` via [`VStrList`], unions via an enum with an
//!   `Unknown(u16)` that is not descended into.
//! - **Every table can be a root.** `X::SCHEMA_ID`, `read`, `verified`, `verified_with`,
//!   `from_bytes`, `XW::root`, `XW::to_bytes`, `XW::seal`.
//!
//! # Invariants for the code generator (codegen)
//!
//! The `*Verified` views skip UTF-8 validation, relying on the `verify()` that already
//! ran. That is only sound if the generated code maintains, for every type `X`:
//!
//! 1. **Same edge, same type.** An `XVerified` is only created (via
//!    [`FromVerified::from_verified`]) over a table that the root's `verify()` reached
//!    successfully **along the same edge** (same field of the same parent table, same list
//!    element) and **with the same reader type `X`**. Being "reachable" is not enough: the
//!    same bytes can be pointed to by two edges as tables of different types, and `verify`
//!    only validated the type of the edge it walked.
//! 2. **`str_unchecked` mirrors `str`.** Every `str_unchecked(off)` call in a view
//!    corresponds to a validating `str(off)` call, at the same offset, in that type's
//!    `verify`. Likewise, every [`VStrList`] in a view corresponds to a [`verify_strs`] call
//!    over the same list (same offset) in that type's `verify`; a `VStrList` is only sound
//!    for lists verified by `verify_strs`.
//! 3. **Nothing beyond what `verify` walks.** Views never follow edges that `verify` skips:
//!    union tags unknown to the reader, fields beyond the reader's layout, reserved fields.
//! 4. **`VListR<T>` with `verify`'s `T`.** [`VListR::new`] is only called with the same `T`
//!    that `verify` used for that list.
//! 5. **`verify` is `#[inline]`.** The generated `verify` functions carry `#[inline]` (its
//!    absence once caused a performance regression in verified reads).
//! 6. **Strings validated by `str()`.** `verify` MUST validate every string by calling
//!    `str()` (which checks UTF-8), never by charging `bytes(off).len()` to the budget
//!    without validating; otherwise item 2 no longer holds.
//!
//! Items 2 and 6 also hold for `[string]`: `verify` MUST call [`verify_strs`] (never
//! [`verify_bytes_list`]) on every list that the view exposes as a [`VStrList`].
//!
//! The mutation test in `graven-schemas/tests/verified.rs`
//! (`verified_matches_checked_under_mutation`) is the acceptance gate: for mutated messages
//! that pass `verify`, every read through the verified view MUST equal the checked read.

use crate::{Bit, Error, StrList, StreamListW, TableList, TableListW, TableRef, VerifyCtx, envelope};
#[doc(hidden)]
pub use alloc::vec::Vec;
use core::marker::PhantomData;

/// One required field of the reader's schema.
#[doc(hidden)]
pub enum Req {
    /// Optional scalar: only checks the slot is not partially covered
    /// (`docs/spec/graven-format-v1.md` §4.3: every inline slot gets §4.2 step 1).
    Slot { off: u16, size: u16 },
    Scalar { name: &'static str, off: u16, size: u16, bit: Bit },
    Bool { name: &'static str, bit: Bit },
    Ptr { name: &'static str, off: u16 },
    /// Required union `[u16 tag][i32 ptr]`: present ⇔ slot inside `fixed_len`, `tag ≠ 0`
    /// and `ptr ≠ 0` (spec §4.3).
    Union { name: &'static str, off: u16 },
}

/// Validate that every required field (per the reader's schema) is present.
#[doc(hidden)]
#[inline]
pub fn check_required(t: &TableRef<'_>, reqs: &[Req]) -> Result<(), Error> {
    for r in reqs {
        match *r {
            Req::Slot { off, size } => {
                t.slot_state(off, size)?;
            }
            Req::Scalar { name, off, size, bit } => {
                if !t.slot_state(off, size)? || !t.bit(bit) {
                    return Err(Error::Missing { field: name });
                }
            }
            Req::Bool { name, bit } => {
                if !t.bit(bit) {
                    return Err(Error::Missing { field: name });
                }
            }
            Req::Ptr { name, off } => {
                // Presence only; the target is bounds-checked when accessed.
                if !t.slot_state(off, 4)? || t.raw::<i32>(off) == 0 {
                    return Err(Error::Missing { field: name });
                }
            }
            Req::Union { name, off } => {
                // Presence only; the target is bounds-checked when accessed.
                if !t.slot_state(off, 6)? || t.raw::<u16>(off) == 0 || t.raw::<i32>(off + 2) == 0 {
                    return Err(Error::Missing { field: name });
                }
            }
        }
    }
    Ok(())
}

/// Precomputed fast path for `check_required` (`docs/spec/graven-format-v1.md` §4.3): when the writer's
/// `fixed_len` covers the reader's whole layout, presence is one AND per bit
/// byte plus a non-zero test per required pointer and union (tag and pointer).
#[doc(hidden)]
pub struct ReqMask {
    pub len: u16,
    pub bits: &'static [(u16, u8)],
    pub ptrs: &'static [u16],
    pub unions: &'static [u16],
}

/// Required-bit mask of `reqs` for bit byte `byte` (evaluated at compile time).
#[doc(hidden)]
pub const fn mask_for(reqs: &[Req], byte: u16) -> u8 {
    let mut m = 0u8;
    let mut i = 0;
    while i < reqs.len() {
        match reqs[i] {
            Req::Scalar { bit, .. } | Req::Bool { bit, .. } if bit.byte == byte => m |= 1 << bit.shift,
            _ => {}
        }
        i += 1;
    }
    m
}

#[doc(hidden)]
#[inline(always)]
pub fn check_required_fast(t: &TableRef<'_>, m: &ReqMask, reqs: &[Req]) -> Result<(), Error> {
    if t.fixed_len() >= m.len {
        let mut ok = true;
        for &(b, mask) in m.bits {
            ok &= t.fixed_byte(b) & mask == mask;
        }
        for &o in m.ptrs {
            ok &= t.raw::<i32>(o) != 0;
        }
        for &o in m.unions {
            ok &= t.raw::<u16>(o) != 0 && t.raw::<i32>(o + 2) != 0;
        }
        if ok {
            return Ok(());
        }
    }
    check_required(t, reqs)
}

/// Generated reader types.
#[doc(hidden)]
pub trait FromTable<'a>: Sized {
    fn from_ref(t: TableRef<'a>) -> Result<Self, Error>;
    /// Verifies everything below this table. Does **not** charge this table's own
    /// header (`2 + fixed_len`): the caller does (root: the inherent `X::verify`; nested:
    /// the parent; list element: [`ListR::verify`]).
    fn verify(&self, ctx: &mut VerifyCtx) -> Result<(), Error>;
}

/// Typed list of tables; an absent list reads as empty.
#[derive(Clone, Copy)]
pub struct ListR<'a, T> {
    inner: Option<TableList<'a>>,
    _t: PhantomData<T>,
}

impl<'a, T: FromTable<'a>> ListR<'a, T> {
    pub fn new(inner: Option<TableList<'a>>) -> Self {
        ListR { inner, _t: PhantomData }
    }
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.map_or(0, |l| l.len())
    }
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    #[inline]
    pub fn get(&self, i: usize) -> Result<T, Error> {
        match self.inner {
            Some(l) => T::from_ref(l.get(i)?),
            None => Err(Error::OutOfBounds),
        }
    }
    pub fn iter(&self) -> impl ExactSizeIterator<Item = Result<T, Error>> + 'a
    where
        T: 'a,
    {
        let s = ListR::<'a, T> { inner: self.inner, _t: PhantomData };
        (0..s.len()).map(move |i| s.get(i))
    }
    /// Charges the list (`6 + count × max(elem_fixed_len, 1)`, which covers the elements'
    /// fixed parts), then verifies every element.
    #[inline]
    pub fn verify(&self, ctx: &mut VerifyCtx) -> Result<(), Error> {
        if let Some(l) = self.inner {
            // max(1): a zero-width element list must still consume budget per element.
            let per = (l.elem_fixed_len() as usize).max(1);
            ctx.charge(l.len().saturating_mul(per).saturating_add(6))?;
        }
        for i in 0..self.len() {
            self.get(i)?.verify(ctx)?;
        }
        Ok(())
    }
}

/// Generated element writer descriptor. All-scalar tables push a `FixedW`.
#[doc(hidden)]
pub trait Elem {
    const FIXED_LEN: u16;
    const PTR_SLOTS: &'static [u16];
    type W<'x>;
    fn push_known<'x>(l: &'x mut TableListW<'_>) -> Self::W<'x>;
    fn push_stream<'x>(l: &'x mut StreamListW<'_, '_>) -> Self::W<'x>;
}

/// Known-count typed list writer.
pub struct ListW<'a, E: Elem>(TableListW<'a>, PhantomData<E>);

impl<'a, E: Elem> ListW<'a, E> {
    pub fn new(l: TableListW<'a>) -> Self {
        ListW(l, PhantomData)
    }
    #[inline]
    pub fn push(&mut self) -> E::W<'_> {
        E::push_known(&mut self.0)
    }
}

/// Unknown-count typed list writer.
pub struct StreamW<'a, 'b, E: Elem>(StreamListW<'a, 'b>, PhantomData<E>);

impl<'a, 'b, E: Elem> StreamW<'a, 'b, E> {
    pub fn new(l: StreamListW<'a, 'b>) -> Self {
        StreamW(l, PhantomData)
    }
    #[inline]
    pub fn push(&mut self) -> E::W<'_> {
        E::push_stream(&mut self.0)
    }
    pub fn close(self) {
        self.0.close()
    }
}

/// Generated verified views (`XVerified<'a>`). Only the generated code calls this.
#[doc(hidden)]
pub trait FromVerified<'a>: Sized {
    /// # Safety
    /// Sound only if all of the following hold (see "Invariants for the code generator"
    /// in the module docs):
    ///
    /// 1. `t` was reached by a root `verify()` that succeeded on the same (immutable)
    ///    buffer, **along the same edge** (same field of the same parent table, same list
    ///    element) and **interpreted as the same reader type `Self`**. Being "reachable"
    ///    is not enough: the same bytes can be pointed to by two edges as two different
    ///    table types, and verify only validated them as the type of the edge it followed.
    /// 2. Every `str_unchecked(off)` call in `Self`'s accessors has a matching validating
    ///    `str(off)` call, at the same offset, in the `verify` of the checked type `Self`
    ///    wraps (and every [`VStrList`] a matching per-element [`StrList::get`]).
    /// 3. `Self`'s accessors never follow an edge that verify skips: union arms with a tag
    ///    unknown to the reader, fields beyond the reader's layout, reserved fields.
    /// 4. Every [`VListR<T>`] that `Self` hands out is built with the `T` that verify used
    ///    for that list.
    #[allow(unsafe_code)]
    unsafe fn from_verified(t: TableRef<'a>) -> Self;
}

/// Typed list of verified views; an absent list reads as empty. Only obtainable from a
/// verified view, so its elements are verified too.
#[derive(Clone, Copy)]
pub struct VListR<'a, T> {
    inner: Option<TableList<'a>>,
    _t: PhantomData<T>,
}

impl<'a, T: FromVerified<'a>> VListR<'a, T> {
    /// # Safety
    /// `inner` must be a list that a root `verify()` succeeded on (same immutable buffer),
    /// reached **along the same edge** that verify followed, and verify must have
    /// verified its elements as **exactly this `T`'s checked type** (not merely some
    /// table type at the same bytes). Every element view `T` then relies on the
    /// [`FromVerified::from_verified`] contract (conditions 1–4), which this caller
    /// vouches for on `T`'s behalf.
    #[doc(hidden)]
    #[allow(unsafe_code)]
    #[inline]
    pub unsafe fn new(inner: Option<TableList<'a>>) -> Self {
        VListR { inner, _t: PhantomData }
    }
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.map_or(0, |l| l.len())
    }
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    #[allow(unsafe_code)]
    #[inline]
    pub fn get(&self, i: usize) -> Result<T, Error> {
        match self.inner {
            // SAFETY: `VListR::new`'s contract says this list was verified, along this
            // edge, with elements of `T`'s checked type; `verify()` visits every element,
            // so element `i` satisfies `from_verified`'s contract for `T`.
            Some(l) => Ok(unsafe { T::from_verified(l.get(i)?) }),
            None => Err(Error::OutOfBounds),
        }
    }
    pub fn iter(&self) -> impl ExactSizeIterator<Item = Result<T, Error>> + 'a
    where
        T: 'a,
    {
        let s = VListR::<'a, T> { inner: self.inner, _t: PhantomData };
        (0..s.len()).map(move |i| s.get(i))
    }
}

/// `[string]` inside a verified message: [`get`](Self::get) skips UTF-8 validation. An
/// absent list reads as empty; a `0` element pointer reads as `""` (spec §5.6).
#[derive(Debug, Clone, Copy)]
pub struct VStrList<'a> {
    inner: Option<StrList<'a>>,
}

impl<'a> VStrList<'a> {
    /// # Safety
    /// `inner` must be a list that a root `verify()` succeeded on (same immutable buffer),
    /// reached **along the same edge** that verify followed, and verify must have passed
    /// this very list to [`verify_strs`] (which validates every element as UTF-8);
    /// a list checked only by [`verify_bytes_list`] does **not** qualify (invariants 1–3
    /// and 6 of the module docs).
    #[doc(hidden)]
    #[allow(unsafe_code)]
    #[inline]
    pub unsafe fn new(inner: Option<StrList<'a>>) -> Self {
        VStrList { inner }
    }
    #[inline]
    pub fn len(&self) -> usize {
        self.inner.map_or(0, |l| l.len())
    }
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
    /// Raw bytes of element `i`.
    #[inline]
    pub fn get_bytes(&self, i: usize) -> Result<&'a [u8], Error> {
        match self.inner {
            Some(l) => l.get_bytes(i),
            None => Err(Error::OutOfBounds),
        }
    }
    /// Element `i`, without re-validating UTF-8.
    #[allow(unsafe_code)]
    #[inline]
    pub fn get(&self, i: usize) -> Result<&'a str, Error> {
        let b = self.get_bytes(i)?;
        // SAFETY: `VStrList::new`'s contract says verify passed this very list (same edge,
        // same immutable buffer) to `verify_strs`, which validated every element as UTF-8.
        Ok(unsafe { core::str::from_utf8_unchecked(b) })
    }
    pub fn iter(&self) -> impl ExactSizeIterator<Item = Result<&'a str, Error>> + 'a {
        let s = *self;
        (0..s.len()).map(move |i| s.get(i))
    }
}

/// Verify step for a `[string]` field (spec §7.3): charges `4 + 4 × count`, then for each
/// element validates it as UTF-8 ([`StrList::get`]) and charges `4 + len`. An absent list
/// charges nothing. The only verify step that makes a [`VStrList`] over the list sound.
#[doc(hidden)]
#[inline]
pub fn verify_strs(l: Option<StrList<'_>>, ctx: &mut VerifyCtx) -> Result<(), Error> {
    let Some(l) = l else { return Ok(()) };
    ctx.charge(l.len().saturating_mul(4).saturating_add(4))?;
    for i in 0..l.len() {
        let s = l.get(i)?;
        ctx.charge(4 + s.len())?;
    }
    Ok(())
}

/// Verify step for a `[bytes]` field (spec §7.3): same charges as [`verify_strs`]
/// (`4 + 4 × count`, then `4 + len` per element), without UTF-8 validation.
#[doc(hidden)]
#[inline]
pub fn verify_bytes_list(l: Option<StrList<'_>>, ctx: &mut VerifyCtx) -> Result<(), Error> {
    let Some(l) = l else { return Ok(()) };
    ctx.charge(l.len().saturating_mul(4).saturating_add(4))?;
    for i in 0..l.len() {
        let b = l.get_bytes(i)?;
        ctx.charge(4 + b.len())?;
    }
    Ok(())
}

/// Envelope step of the generated `from_bytes`: decode and check the root's schema id,
/// returning the payload.
#[doc(hidden)]
#[inline]
pub fn open_envelope(buf: &[u8], expected: u64) -> Result<&[u8], Error> {
    let env = envelope::decode(buf)?;
    if env.schema_id != expected {
        return Err(Error::SchemaMismatch { expected, found: env.schema_id });
    }
    Ok(env.payload)
}