verit_core/
encode.rs

1//! Encoder: `Schema` + `Value` tree → message bytes.
2//!
3//! Envelope: 24-byte header, optional inline canonical schema, padding to 8,
4//! then the payload arena. All offsets in the message are absolute u32 byte
5//! positions within the buffer. See the architecture docs.
6
7use crate::error::{Error, Result};
8use crate::layout::{align_up, slot_size_align};
9use crate::schema::{Schema, Type};
10use crate::value::Value;
11
12pub const MESSAGE_MAGIC: &[u8; 4] = b"VRT2";
13pub const FLAG_INLINE_SCHEMA: u16 = 1;
14/// Envelope: magic(4) flags(2) reserved(2) schema_id(16) root_off(4) schema_len(4).
15pub const HEADER_LEN: usize = 32;
16
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum SchemaMode {
19    /// Embed the full canonical schema: the message alone is self-describing.
20    Inline,
21    /// Carry only the 128-bit schema id (streams / registries amortize the
22    /// schema out of band).
23    HashOnly,
24}
25
26pub fn encode(schema: &Schema, root: &Value, mode: SchemaMode) -> Result<Vec<u8>> {
27    let root_fields = match root {
28        Value::Struct(fields) => fields,
29        other => {
30            return Err(Error::TypeMismatch {
31                expected: "struct".into(),
32                got: other.kind().into(),
33            })
34        }
35    };
36    let mut enc = Encoder {
37        schema,
38        buf: Vec::with_capacity(256),
39    };
40    enc.buf.extend_from_slice(MESSAGE_MAGIC);
41    let inline = mode == SchemaMode::Inline;
42    let flags: u16 = if inline { FLAG_INLINE_SCHEMA } else { 0 };
43    enc.buf.extend_from_slice(&flags.to_le_bytes());
44    enc.buf.extend_from_slice(&0u16.to_le_bytes()); // reserved
45    enc.buf.extend_from_slice(&schema.id().to_le_bytes()); // 16-byte schema id
46    enc.buf.extend_from_slice(&0u32.to_le_bytes()); // root offset, patched below
47    let schema_len = if inline {
48        schema.canonical_bytes().len()
49    } else {
50        0
51    };
52    let schema_len_u32 = u32::try_from(schema_len).map_err(|_| Error::MessageTooLarge)?;
53    enc.buf.extend_from_slice(&schema_len_u32.to_le_bytes());
54    if inline {
55        enc.buf.extend_from_slice(schema.canonical_bytes());
56    }
57    enc.pad_to(8)?;
58    let root_off = enc.write_struct(schema.root_index(), root_fields)?;
59    enc.buf[24..28].copy_from_slice(&root_off.to_le_bytes());
60    Ok(enc.buf)
61}
62
63enum ElemKind {
64    Scalar,
65    Ref,
66    InlineStruct(u16),
67}
68
69fn elem_info(schema: &Schema, elem: &Type) -> (u32, u32, ElemKind) {
70    match elem {
71        Type::Struct(i) => match schema.layout_unchecked(*i) {
72            // Fixed-size struct elements are stored inline at a constant
73            // stride. Packed struct elements are variable-size, so they ride
74            // in the list by u32 offset (the Ref discipline) instead.
75            crate::layout::StructLayout::Fixed(f) => (f.size, f.align, ElemKind::InlineStruct(*i)),
76            crate::layout::StructLayout::Packed(_) => (4, 4, ElemKind::Ref),
77        },
78        Type::String | Type::Bytes | Type::List(_) | Type::Map(_, _) | Type::Union(_) => {
79            (4, 4, ElemKind::Ref)
80        }
81        other => {
82            let (size, align) = slot_size_align(other);
83            (size, align, ElemKind::Scalar)
84        }
85    }
86}
87
88/// Total canonical order over map keys of a single key type: integers by value
89/// (sign-aware), `bool` false < true, enums by their u32, strings by UTF-8
90/// bytes. The encoder sorts entries by this so one logical map has exactly one
91/// byte encoding, regardless of insertion order (crucial for languages whose
92/// maps iterate in an unspecified order).
93fn key_cmp(a: &Value, b: &Value) -> std::cmp::Ordering {
94    use std::cmp::Ordering::Equal;
95    use Value::*;
96    match (a, b) {
97        (Bool(x), Bool(y)) => x.cmp(y),
98        (U8(x), U8(y)) => x.cmp(y),
99        (U16(x), U16(y)) => x.cmp(y),
100        (U32(x), U32(y)) => x.cmp(y),
101        (U64(x), U64(y)) => x.cmp(y),
102        (I8(x), I8(y)) => x.cmp(y),
103        (I16(x), I16(y)) => x.cmp(y),
104        (I32(x), I32(y)) => x.cmp(y),
105        (I64(x), I64(y)) => x.cmp(y),
106        (Enum(x), Enum(y)) => x.cmp(y),
107        (Str(x), Str(y)) => x.as_bytes().cmp(y.as_bytes()),
108        // Mixed or non-key variants: leave order unspecified here; the per-entry
109        // type check in `write_map` rejects a key of the wrong type.
110        _ => Equal,
111    }
112}
113
114fn type_mismatch(schema: &Schema, expected: &Type, got: &Value) -> Error {
115    Error::TypeMismatch {
116        expected: expected.describe(schema),
117        got: got.kind().into(),
118    }
119}
120
121struct Encoder<'s> {
122    schema: &'s Schema,
123    buf: Vec<u8>,
124}
125
126impl<'s> Encoder<'s> {
127    fn pos(&self) -> Result<u32> {
128        u32::try_from(self.buf.len()).map_err(|_| Error::MessageTooLarge)
129    }
130
131    fn pad_to(&mut self, align: u32) -> Result<u32> {
132        let pos = self.pos()?;
133        let target = align_up(pos, align);
134        self.buf.resize(self.buf.len() + (target - pos) as usize, 0);
135        Ok(target)
136    }
137
138    fn patch_u32(&mut self, at: u32, v: u32) {
139        let at = at as usize;
140        self.buf[at..at + 4].copy_from_slice(&v.to_le_bytes());
141    }
142
143    /// Reserve a zeroed, aligned fixed struct block and return its offset.
144    fn alloc_struct_block(&mut self, type_index: u16) -> Result<u32> {
145        let lay = self.schema.layout_unchecked(type_index).as_fixed();
146        let (align, size) = (lay.align, lay.size);
147        let base = self.pad_to(align)?;
148        self.buf.resize(self.buf.len() + size as usize, 0);
149        self.pos()?; // enforce the 4 GiB cap after growing
150        Ok(base)
151    }
152
153    fn write_struct(&mut self, type_index: u16, values: &[(u16, Value)]) -> Result<u32> {
154        if self.schema.struct_def_unchecked(type_index).is_packed() {
155            return self.write_packed_struct(type_index, values);
156        }
157        let base = self.alloc_struct_block(type_index)?;
158        self.fill_struct_at(base, type_index, values)?;
159        Ok(base)
160    }
161
162    /// Fill an already-reserved struct block: presence bits and scalar slots
163    /// in place, heap children appended afterwards with their offsets patched
164    /// into the slots.
165    fn fill_struct_at(
166        &mut self,
167        base: u32,
168        type_index: u16,
169        values: &[(u16, Value)],
170    ) -> Result<()> {
171        let schema = self.schema;
172        let sd = schema.struct_def_unchecked(type_index);
173        let lay = schema.layout_unchecked(type_index).as_fixed();
174        let mut heap_jobs: Vec<(u32, &Value, &'s Type)> = Vec::new();
175        let mut seen = vec![false; sd.fields.len()];
176        for (id, value) in values {
177            let pos = sd
178                .fields
179                .binary_search_by_key(id, |f| f.id)
180                .map_err(|_| Error::UnknownFieldId(*id))?;
181            if seen[pos] {
182                return Err(Error::DuplicateField(*id));
183            }
184            seen[pos] = true;
185            if !sd.is_dense() {
186                let bit_at = (base + pos as u32 / 8) as usize;
187                self.buf[bit_at] |= 1 << (pos % 8);
188            }
189            let slot = base + lay.slots[pos];
190            let ty = &sd.fields[pos].ty;
191            match ty {
192                Type::String
193                | Type::Bytes
194                | Type::List(_)
195                | Type::Struct(_)
196                | Type::Map(_, _)
197                | Type::Union(_) => {
198                    // Cheap shape check now for a good error; full check when written.
199                    let ok = matches!(
200                        (ty, value),
201                        (Type::String, Value::Str(_))
202                            | (Type::Bytes, Value::Bytes(_))
203                            | (Type::List(_), Value::List(_))
204                            | (Type::Struct(_), Value::Struct(_))
205                            | (Type::Map(_, _), Value::Map(_))
206                            | (Type::Union(_), Value::Union(..))
207                    );
208                    if !ok {
209                        return Err(type_mismatch(schema, ty, value));
210                    }
211                    heap_jobs.push((slot, value, ty));
212                }
213                _ => self.store_scalar_at(slot, value, ty)?,
214            }
215        }
216        if sd.is_dense() {
217            if let Some(pos) = seen.iter().position(|s| !s) {
218                return Err(Error::MissingField(sd.fields[pos].id));
219            }
220        }
221        for (slot, value, ty) in heap_jobs {
222            let off = self.write_heap(value, ty)?;
223            self.patch_u32(slot, off);
224        }
225        Ok(())
226    }
227
228    /// Encode a packed struct: presence bitmap, then present fields packed by
229    /// size class. Block size and slot offsets come from the popcount layout.
230    fn write_packed_struct(&mut self, type_index: u16, values: &[(u16, Value)]) -> Result<u32> {
231        let schema = self.schema;
232        let sd = schema.struct_def_unchecked(type_index);
233        let lay = schema.layout_unchecked(type_index).as_packed();
234
235        // Resolve ids to positions, detect duplicates, build the bitmap.
236        let mut bitmap = 0u64;
237        let mut present: Vec<(usize, &Value, &'s Type)> = Vec::with_capacity(values.len());
238        for (id, value) in values {
239            let pos = sd
240                .fields
241                .binary_search_by_key(id, |f| f.id)
242                .map_err(|_| Error::UnknownFieldId(*id))?;
243            let bit = 1u64 << pos;
244            if bitmap & bit != 0 {
245                return Err(Error::DuplicateField(*id));
246            }
247            bitmap |= bit;
248            present.push((pos, value, &sd.fields[pos].ty));
249        }
250
251        let size = lay.block_size(bitmap);
252        let base = self.pad_to(lay.align)?;
253        self.buf.resize(self.buf.len() + size as usize, 0);
254        self.pos()?;
255        // Write the presence bitmap (only the used low bytes).
256        let bmap_bytes = bitmap.to_le_bytes();
257        let bstart = base as usize;
258        self.buf[bstart..bstart + lay.bitmap_bytes as usize]
259            .copy_from_slice(&bmap_bytes[..lay.bitmap_bytes as usize]);
260
261        let mut heap_jobs: Vec<(u32, &Value, &'s Type)> = Vec::new();
262        for (pos, value, ty) in present {
263            let slot = base + lay.field_offset(bitmap, pos);
264            match ty {
265                Type::String
266                | Type::Bytes
267                | Type::List(_)
268                | Type::Struct(_)
269                | Type::Map(_, _)
270                | Type::Union(_) => {
271                    let ok = matches!(
272                        (ty, value),
273                        (Type::String, Value::Str(_))
274                            | (Type::Bytes, Value::Bytes(_))
275                            | (Type::List(_), Value::List(_))
276                            | (Type::Struct(_), Value::Struct(_))
277                            | (Type::Map(_, _), Value::Map(_))
278                            | (Type::Union(_), Value::Union(..))
279                    );
280                    if !ok {
281                        return Err(type_mismatch(schema, ty, value));
282                    }
283                    heap_jobs.push((slot, value, ty));
284                }
285                _ => self.store_scalar_at(slot, value, ty)?,
286            }
287        }
288        for (slot, value, ty) in heap_jobs {
289            let off = self.write_heap(value, ty)?;
290            self.patch_u32(slot, off);
291        }
292        Ok(base)
293    }
294
295    /// Write a scalar into an existing (zeroed) slot.
296    fn store_scalar_at(&mut self, at: u32, value: &Value, ty: &Type) -> Result<()> {
297        let at = at as usize;
298        let buf = &mut self.buf;
299        macro_rules! put {
300            ($bytes:expr) => {{
301                let b = $bytes;
302                buf[at..at + b.len()].copy_from_slice(&b);
303            }};
304        }
305        match (ty, value) {
306            (Type::Bool, Value::Bool(x)) => buf[at] = *x as u8,
307            (Type::U8, Value::U8(x)) => buf[at] = *x,
308            (Type::U16, Value::U16(x)) => put!(x.to_le_bytes()),
309            (Type::U32, Value::U32(x)) => put!(x.to_le_bytes()),
310            (Type::U64, Value::U64(x)) => put!(x.to_le_bytes()),
311            (Type::I8, Value::I8(x)) => buf[at] = *x as u8,
312            (Type::I16, Value::I16(x)) => put!(x.to_le_bytes()),
313            (Type::I32, Value::I32(x)) => put!(x.to_le_bytes()),
314            (Type::I64, Value::I64(x)) => put!(x.to_le_bytes()),
315            (Type::F32, Value::F32(x)) => put!(x.to_le_bytes()),
316            (Type::F64, Value::F64(x)) => put!(x.to_le_bytes()),
317            (Type::Enum(_), Value::Enum(x)) => put!(x.to_le_bytes()),
318            _ => return Err(type_mismatch(self.schema, ty, value)),
319        }
320        Ok(())
321    }
322
323    /// Append a scalar list element at the current (aligned) position.
324    fn push_scalar(&mut self, value: &Value, ty: &Type) -> Result<()> {
325        let buf = &mut self.buf;
326        match (ty, value) {
327            (Type::Bool, Value::Bool(x)) => buf.push(*x as u8),
328            (Type::U8, Value::U8(x)) => buf.push(*x),
329            (Type::U16, Value::U16(x)) => buf.extend_from_slice(&x.to_le_bytes()),
330            (Type::U32, Value::U32(x)) => buf.extend_from_slice(&x.to_le_bytes()),
331            (Type::U64, Value::U64(x)) => buf.extend_from_slice(&x.to_le_bytes()),
332            (Type::I8, Value::I8(x)) => buf.push(*x as u8),
333            (Type::I16, Value::I16(x)) => buf.extend_from_slice(&x.to_le_bytes()),
334            (Type::I32, Value::I32(x)) => buf.extend_from_slice(&x.to_le_bytes()),
335            (Type::I64, Value::I64(x)) => buf.extend_from_slice(&x.to_le_bytes()),
336            (Type::F32, Value::F32(x)) => buf.extend_from_slice(&x.to_le_bytes()),
337            (Type::F64, Value::F64(x)) => buf.extend_from_slice(&x.to_le_bytes()),
338            (Type::Enum(_), Value::Enum(x)) => buf.extend_from_slice(&x.to_le_bytes()),
339            _ => return Err(type_mismatch(self.schema, ty, value)),
340        }
341        Ok(())
342    }
343
344    /// Write a heap object (string, bytes, list, struct block) and return its
345    /// absolute offset.
346    fn write_heap(&mut self, value: &Value, ty: &Type) -> Result<u32> {
347        match (ty, value) {
348            (Type::String, Value::Str(s)) => self.write_blob(s.as_bytes()),
349            (Type::Bytes, Value::Bytes(b)) => self.write_blob(b),
350            (Type::Struct(i), Value::Struct(fields)) => self.write_struct(*i, fields),
351            (Type::List(elem), Value::List(items)) => self.write_list(elem, items),
352            (Type::Map(k, v), Value::Map(entries)) => self.write_map(k, v, entries),
353            (Type::Union(variants), Value::Union(tag, inner)) => {
354                self.write_union(variants, *tag, inner)
355            }
356            _ => Err(type_mismatch(self.schema, ty, value)),
357        }
358    }
359
360    /// Write a `union` value: `u32 tag`, then the selected variant's value at
361    /// its natural-aligned payload slot (scalar in place, or a u32 heap offset).
362    fn write_union(&mut self, variants: &[Type], tag: u32, inner: &Value) -> Result<u32> {
363        let vty = variants.get(tag as usize).ok_or(Error::BadUnionTag(tag))?;
364        let (pslot, palign) = slot_size_align(vty);
365        let payload_off = crate::layout::align_up(4, palign);
366        let block_align = palign.max(4);
367        let block_size = crate::layout::align_up(payload_off + pslot, block_align);
368        let base = self.pad_to(block_align)?;
369        self.buf.resize(self.buf.len() + block_size as usize, 0);
370        self.pos()?;
371        self.patch_u32(base, tag);
372        let slot = base + payload_off;
373        match vty {
374            Type::String
375            | Type::Bytes
376            | Type::List(_)
377            | Type::Struct(_)
378            | Type::Map(_, _)
379            | Type::Union(_) => {
380                let off = self.write_heap(inner, vty)?;
381                self.patch_u32(slot, off);
382            }
383            _ => self.store_scalar_at(slot, inner, vty)?,
384        }
385        Ok(base)
386    }
387
388    /// Write a `map<K, V>`: `count`, then `count` entry blocks (each a dense
389    /// 2-field {key, value} struct), entries sorted by key in canonical order.
390    /// Returns the map's absolute offset.
391    fn write_map(
392        &mut self,
393        key_ty: &Type,
394        val_ty: &Type,
395        entries: &[(Value, Value)],
396    ) -> Result<u32> {
397        let lay = crate::layout::map_entry_layout(key_ty, val_ty);
398        let (key_slot, val_slot) = (lay.slots[0], lay.slots[1]);
399
400        // Sort a view of the entries by key into canonical order (leaving the
401        // caller's Vec untouched), then reject duplicate keys.
402        let mut order: Vec<usize> = (0..entries.len()).collect();
403        order.sort_by(|&i, &j| key_cmp(&entries[i].0, &entries[j].0));
404        for w in order.windows(2) {
405            if key_cmp(&entries[w[0]].0, &entries[w[1]].0) == std::cmp::Ordering::Equal {
406                return Err(Error::DuplicateMapKey);
407            }
408        }
409
410        let count = u32::try_from(entries.len()).map_err(|_| Error::MessageTooLarge)?;
411        let off = self.pad_to(4)?;
412        self.buf.extend_from_slice(&count.to_le_bytes());
413        let base = self.pad_to(lay.align)?;
414        let total = (lay.size as usize)
415            .checked_mul(entries.len())
416            .ok_or(Error::MessageTooLarge)?;
417        self.buf.resize(self.buf.len() + total, 0);
418        self.pos()?;
419
420        // Two passes so all in-block scalars land before any heap object is
421        // appended (mirrors struct filling), keeping the entry region contiguous.
422        let mut heap_jobs: Vec<(u32, &Value, &Type)> = Vec::new();
423        for (rank, &i) in order.iter().enumerate() {
424            let entry_base = base + rank as u32 * lay.size;
425            for (slot_off, ty, val) in [
426                (key_slot, key_ty, &entries[i].0),
427                (val_slot, val_ty, &entries[i].1),
428            ] {
429                let slot = entry_base + slot_off;
430                match ty {
431                    Type::String
432                    | Type::Bytes
433                    | Type::List(_)
434                    | Type::Struct(_)
435                    | Type::Map(_, _) => {
436                        heap_jobs.push((slot, val, ty));
437                    }
438                    _ => self.store_scalar_at(slot, val, ty)?,
439                }
440            }
441        }
442        for (slot, val, ty) in heap_jobs {
443            let child = self.write_heap(val, ty)?;
444            self.patch_u32(slot, child);
445        }
446        Ok(off)
447    }
448
449    fn write_blob(&mut self, bytes: &[u8]) -> Result<u32> {
450        let len = u32::try_from(bytes.len()).map_err(|_| Error::MessageTooLarge)?;
451        let off = self.pad_to(4)?;
452        self.buf.extend_from_slice(&len.to_le_bytes());
453        self.buf.extend_from_slice(bytes);
454        self.pos()?;
455        Ok(off)
456    }
457
458    fn write_list(&mut self, elem: &Type, items: &[Value]) -> Result<u32> {
459        let schema = self.schema;
460        let (stride, elem_align, kind) = elem_info(schema, elem);
461        let count = u32::try_from(items.len()).map_err(|_| Error::MessageTooLarge)?;
462        let off = self.pad_to(4)?;
463        self.buf.extend_from_slice(&count.to_le_bytes());
464        self.pad_to(elem_align)?;
465        match kind {
466            ElemKind::Scalar => {
467                for item in items {
468                    self.push_scalar(item, elem)?;
469                }
470            }
471            ElemKind::Ref => {
472                let slots_base = self.pos()?;
473                self.buf.resize(
474                    self.buf.len() + items.len().checked_mul(4).ok_or(Error::MessageTooLarge)?,
475                    0,
476                );
477                self.pos()?;
478                for (i, item) in items.iter().enumerate() {
479                    let child = self.write_heap(item, elem)?;
480                    self.patch_u32(slots_base + (i as u32) * 4, child);
481                }
482            }
483            ElemKind::InlineStruct(type_index) => {
484                let base = self.pos()?;
485                let total = (stride as usize)
486                    .checked_mul(items.len())
487                    .ok_or(Error::MessageTooLarge)?;
488                self.buf.resize(self.buf.len() + total, 0);
489                self.pos()?;
490                for (i, item) in items.iter().enumerate() {
491                    let fields = match item {
492                        Value::Struct(fields) => fields,
493                        other => return Err(type_mismatch(schema, elem, other)),
494                    };
495                    self.fill_struct_at(base + (i as u32) * stride, type_index, fields)?;
496                }
497            }
498        }
499        self.pos()?;
500        Ok(off)
501    }
502}
verit_core/encode.rs

verit_core/
encode.rs
