spacetimedb_table/
layout.rs

1//! Defines [`Layout`], which encompasses the fixed size and alignment of an object,
2//! e.g., a row, or a column, or some other sub-division of a row.
3//!
4//! `Layout` annotated versions of SATS types are also provided,
5//! such as [`ProductTypeLayout`] and [`AlgebraicTypeLayout`].
6//! These, and others, determine what the layout of objects typed at those types are.
7//! They also implement [`HasLayout`] which generalizes over layout annotated types.
8
9use crate::MemoryUsage;
10
11use super::{
12    indexes::Size,
13    var_len::{VarLenGranule, VarLenRef},
14};
15use core::mem;
16use core::ops::Index;
17use enum_as_inner::EnumAsInner;
18use spacetimedb_sats::{
19    bsatn,
20    de::{
21        Deserialize, DeserializeSeed, Deserializer, Error, NamedProductAccess, ProductVisitor, SeqProductAccess,
22        SumAccess, SumVisitor, ValidNames, VariantAccess as _, VariantVisitor,
23    },
24    i256,
25    sum_type::{OPTION_NONE_TAG, OPTION_SOME_TAG},
26    u256, AlgebraicType, AlgebraicValue, ProductType, ProductTypeElement, ProductValue, SumType, SumTypeVariant,
27    SumValue, WithTypespace,
28};
29pub use spacetimedb_schema::type_for_generate::PrimitiveType;
30
31/// Aligns a `base` offset to the `required_alignment` (in the positive direction) and returns it.
32///
33/// When `base` is already aligned, `base` will be returned.
34pub const fn align_to(base: usize, required_alignment: usize) -> usize {
35    if required_alignment == 0 {
36        // Avoid computing the remainder below, as that panics.
37        // This path is reachable for e.g., uninhabited types.
38        base
39    } else {
40        let misalignment = base % required_alignment;
41        if misalignment == 0 {
42            base
43        } else {
44            let padding = required_alignment - misalignment;
45            base + padding
46        }
47    }
48}
49
50// TODO(perf): try out using just an offset relative to the row start itself.
51// The main drawback is that nested types start at non-zero.
52// Primitives and var-len refs now also need to store more data
53// but this shouldn't cost anything as this would be padding anyways.
54// The main upside is that ser/de/eq/row_hash
55// need not do any alignment adjustments and carry a current offset.
56// This removes a data dependence and could possibly improve instruction-level parallelism.
57
58/// The layout of a fixed object
59/// or the layout that fixed objects of a type will have.
60#[derive(Copy, Clone, Debug, PartialEq, Eq)]
61pub struct Layout {
62    /// The size object / expected object in bytes.
63    pub size: u16,
64    /// The alignment of the object / expected object in bytes.
65    pub align: u16,
66    /// Whether this is the layout of a fixed object
67    /// and not the layout of a var-len type's fixed component.
68    pub fixed: bool,
69}
70
71impl MemoryUsage for Layout {}
72
73/// A type which knows what its layout is.
74///
75/// This does not refer to layout in Rust.
76pub trait HasLayout {
77    /// Returns the layout for objects of this type.
78    fn layout(&self) -> &Layout;
79
80    /// Returns the size, in bytes, for objects of this type.
81    ///
82    /// Intentionally returns `usize` rather than [`Size`],
83    /// so callers will have to explicitly convert
84    /// with [`row_size_for_bytes`].
85    fn size(&self) -> usize {
86        self.layout().size as usize
87    }
88
89    /// Returns the alignment, in bytes, for objects of this type.
90    ///
91    /// Intentionally returns `usize` rather than [`Size`],
92    /// so callers will have to explicitly convert
93    /// with [`row_size_for_bytes`].
94    fn align(&self) -> usize {
95        self.layout().align as usize
96    }
97}
98
99/// Mostly a mirror of [`AlgebraicType`] annotated with a [`Layout`].
100///
101/// Notable differences from `AlgebraicType`:
102///
103/// - `Ref`s are not supported.
104///   Supporting recursive types remains a TODO(future-work).
105///   Note that the previous Spacetime datastore did not support recursive types in tables.
106///
107/// - Scalar types (`ty.is_scalar()`) are separated into [`PrimitveType`] (atomically-sized types like integers).
108/// - Variable length types are separated into [`VarLenType`] (strings, arrays, and maps).
109///   This separation allows cleaner pattern-matching, e.g. in `HasLayout::layout`,
110///   where `VarLenType` returns a static ref to [`VAR_LEN_REF_LAYOUT`],
111///   and `PrimitiveType` dispatches on its variant to return a static ref
112///   to a type-specific `Layout`.
113#[derive(Debug, PartialEq, Eq, Clone, EnumAsInner)]
114pub enum AlgebraicTypeLayout {
115    /// A sum type, annotated with its layout.
116    Sum(SumTypeLayout),
117    /// A product type, annotated with its layout.
118    Product(ProductTypeLayout),
119    /// A primitive type, annotated with its layout.
120    Primitive(PrimitiveType),
121    /// A variable length type, annotated with its layout.
122    VarLen(VarLenType),
123}
124
125impl MemoryUsage for AlgebraicTypeLayout {
126    fn heap_usage(&self) -> usize {
127        match self {
128            AlgebraicTypeLayout::Sum(x) => x.heap_usage(),
129            AlgebraicTypeLayout::Product(x) => x.heap_usage(),
130            AlgebraicTypeLayout::Primitive(x) => x.heap_usage(),
131            AlgebraicTypeLayout::VarLen(x) => x.heap_usage(),
132        }
133    }
134}
135
136impl HasLayout for AlgebraicTypeLayout {
137    fn layout(&self) -> &Layout {
138        match self {
139            Self::Sum(ty) => ty.layout(),
140            Self::Product(ty) => ty.layout(),
141            Self::Primitive(ty) => ty.layout(),
142            Self::VarLen(ty) => ty.layout(),
143        }
144    }
145}
146
147#[allow(non_upper_case_globals)]
148impl AlgebraicTypeLayout {
149    pub const Bool: Self = Self::Primitive(PrimitiveType::Bool);
150    pub const I8: Self = Self::Primitive(PrimitiveType::I8);
151    pub const U8: Self = Self::Primitive(PrimitiveType::U8);
152    pub const I16: Self = Self::Primitive(PrimitiveType::I16);
153    pub const U16: Self = Self::Primitive(PrimitiveType::U16);
154    pub const I32: Self = Self::Primitive(PrimitiveType::I32);
155    pub const U32: Self = Self::Primitive(PrimitiveType::U32);
156    pub const I64: Self = Self::Primitive(PrimitiveType::I64);
157    pub const U64: Self = Self::Primitive(PrimitiveType::U64);
158    pub const I128: Self = Self::Primitive(PrimitiveType::I128);
159    pub const U128: Self = Self::Primitive(PrimitiveType::U128);
160    pub const I256: Self = Self::Primitive(PrimitiveType::I256);
161    pub const U256: Self = Self::Primitive(PrimitiveType::U256);
162    pub const F32: Self = Self::Primitive(PrimitiveType::F32);
163    pub const F64: Self = Self::Primitive(PrimitiveType::F64);
164    pub const String: Self = Self::VarLen(VarLenType::String);
165}
166
167/// A collection of items, so that we can easily swap out the backing type.
168type Collection<T> = Box<[T]>;
169
170/// Fixed-length row portions must be at least large enough to store a `FreeCellRef`.
171pub const MIN_ROW_SIZE: Size = Size(2);
172
173/// Fixed-length row portions must also be sufficiently aligned to store a `FreeCellRef`.
174pub const MIN_ROW_ALIGN: Size = Size(2);
175
176/// Returns the minimum row size needed to store `required_bytes`
177/// accounting for the minimum row size and alignment.
178pub const fn row_size_for_bytes(required_bytes: usize) -> Size {
179    // Manual `Ord::max` because that function is not `const`.
180    if required_bytes > MIN_ROW_SIZE.len() {
181        Size(align_to(required_bytes, MIN_ROW_ALIGN.len()) as u16)
182    } else {
183        MIN_ROW_SIZE
184    }
185}
186
187/// Returns the minimum row size needed to store a `T`,
188/// accounting for the minimum row size and alignment.
189pub const fn row_size_for_type<T>() -> Size {
190    row_size_for_bytes(mem::size_of::<T>())
191}
192
193/// The type of a row, annotated with a [`Layout`].
194///
195/// This type ensures that the minimum row size is adhered to.
196#[derive(Debug, PartialEq, Eq, Clone)]
197pub struct RowTypeLayout(ProductTypeLayout);
198
199impl MemoryUsage for RowTypeLayout {
200    fn heap_usage(&self) -> usize {
201        let Self(layout) = self;
202        layout.heap_usage()
203    }
204}
205
206impl RowTypeLayout {
207    /// Returns a view of this row type as a product type.
208    pub fn product(&self) -> &ProductTypeLayout {
209        &self.0
210    }
211
212    /// Returns the row size for this row type.
213    pub fn size(&self) -> Size {
214        Size(self.0.size() as u16)
215    }
216}
217
218impl From<ProductTypeLayout> for RowTypeLayout {
219    fn from(mut cols: ProductTypeLayout) -> Self {
220        cols.layout.size = row_size_for_bytes(cols.layout.size as usize).0;
221        Self(cols)
222    }
223}
224
225impl From<ProductType> for RowTypeLayout {
226    fn from(ty: ProductType) -> Self {
227        ProductTypeLayout::from(ty).into()
228    }
229}
230
231impl HasLayout for RowTypeLayout {
232    fn layout(&self) -> &Layout {
233        self.0.layout()
234    }
235}
236
237impl Index<usize> for RowTypeLayout {
238    type Output = AlgebraicTypeLayout;
239    fn index(&self, index: usize) -> &Self::Output {
240        &self.0.elements[index].ty
241    }
242}
243
244/// A mirror of [`ProductType`] annotated with a [`Layout`].
245#[derive(Debug, PartialEq, Eq, Clone)]
246pub struct ProductTypeLayout {
247    /// The memoized layout of the product type.
248    pub layout: Layout,
249    /// The fields of the product type with their own layout annotations.
250    pub elements: Collection<ProductTypeElementLayout>,
251}
252
253impl MemoryUsage for ProductTypeLayout {
254    fn heap_usage(&self) -> usize {
255        let Self { layout, elements } = self;
256        layout.heap_usage() + elements.heap_usage()
257    }
258}
259
260impl HasLayout for ProductTypeLayout {
261    fn layout(&self) -> &Layout {
262        &self.layout
263    }
264}
265
266/// A mirrior of [`ProductTypeElement`] annotated with a [`Layout`].
267#[derive(Debug, PartialEq, Eq, Clone)]
268pub struct ProductTypeElementLayout {
269    /// The relative offset of a field's value to its parent product value.
270    pub offset: u16,
271
272    /// The type of the field.
273    pub ty: AlgebraicTypeLayout,
274
275    /// An optional name of the field.
276    ///
277    /// This allows us to convert back to `ProductTypeElement`,
278    /// which we do when reporting type errors.
279    pub name: Option<Box<str>>,
280}
281
282impl MemoryUsage for ProductTypeElementLayout {
283    fn heap_usage(&self) -> usize {
284        let Self { offset, ty, name } = self;
285        offset.heap_usage() + ty.heap_usage() + name.heap_usage()
286    }
287}
288
289/// A mirrior of [`SumType`] annotated with a [`Layout`].
290#[derive(Debug, PartialEq, Eq, Clone)]
291pub struct SumTypeLayout {
292    /// The layout of a sum value of this sum type.
293    pub layout: Layout,
294    /// The variants of the sum type.
295    pub variants: Collection<SumTypeVariantLayout>,
296    /// The relative offset of a sum value's payload for sums of this type.
297    /// Sum value tags are always at offset 0.
298    pub payload_offset: u16,
299}
300
301impl MemoryUsage for SumTypeLayout {
302    fn heap_usage(&self) -> usize {
303        let Self {
304            layout,
305            variants,
306            payload_offset,
307        } = self;
308        layout.heap_usage() + variants.heap_usage() + payload_offset.heap_usage()
309    }
310}
311
312impl HasLayout for SumTypeLayout {
313    fn layout(&self) -> &Layout {
314        &self.layout
315    }
316}
317
318/// A mirrior of [`SumTypeVariant`] annotated with a [`Layout`].
319#[derive(Debug, PartialEq, Eq, Clone)]
320pub struct SumTypeVariantLayout {
321    /// The type of the variant.
322    pub ty: AlgebraicTypeLayout,
323
324    /// An optional name of the variant.
325    ///
326    /// This allows us to convert back to `SumTypeVariant`,
327    /// which we do when reporting type errors.
328    pub name: Option<Box<str>>,
329}
330
331impl MemoryUsage for SumTypeVariantLayout {
332    fn heap_usage(&self) -> usize {
333        let Self { ty, name } = self;
334        ty.heap_usage() + name.heap_usage()
335    }
336}
337
338impl MemoryUsage for PrimitiveType {}
339
340impl HasLayout for PrimitiveType {
341    fn layout(&self) -> &'static Layout {
342        match self {
343            Self::Bool | Self::I8 | Self::U8 => &Layout {
344                size: 1,
345                align: 1,
346                fixed: true,
347            },
348            Self::I16 | Self::U16 => &Layout {
349                size: 2,
350                align: 2,
351                fixed: true,
352            },
353            Self::I32 | Self::U32 | Self::F32 => &Layout {
354                size: 4,
355                align: 4,
356                fixed: true,
357            },
358            Self::I64 | Self::U64 | Self::F64 => &Layout {
359                size: 8,
360                align: 8,
361                fixed: true,
362            },
363            Self::I128 | Self::U128 => &Layout {
364                size: 16,
365                align: 16,
366                fixed: true,
367            },
368            Self::I256 | Self::U256 => &Layout {
369                size: 32,
370                align: 32,
371                fixed: true,
372            },
373        }
374    }
375}
376
377/// Types requiring a `VarLenRef` indirection,
378/// i.e. strings, arrays, and maps.
379#[derive(Debug, PartialEq, Eq, Clone)]
380pub enum VarLenType {
381    /// The string type corresponds to `AlgebraicType::String`.
382    String,
383    /// An array type. The whole outer `AlgebraicType` is stored here.
384    ///
385    /// Storing the whole `AlgebraicType` here allows us to directly call BSATN ser/de,
386    /// and to report type errors.
387    Array(Box<AlgebraicType>),
388}
389
390impl MemoryUsage for VarLenType {
391    fn heap_usage(&self) -> usize {
392        match self {
393            VarLenType::String => 0,
394            VarLenType::Array(x) => x.heap_usage(),
395        }
396    }
397}
398
399/// The layout of var-len objects. Aligned at a `u16` which it has 2 of.
400const VAR_LEN_REF_LAYOUT: Layout = Layout {
401    size: 4,
402    align: 2,
403    fixed: false,
404};
405const _: () = assert!(VAR_LEN_REF_LAYOUT.size as usize == mem::size_of::<VarLenRef>());
406const _: () = assert!(VAR_LEN_REF_LAYOUT.align as usize == mem::align_of::<VarLenRef>());
407
408impl HasLayout for VarLenType {
409    fn layout(&self) -> &Layout {
410        &VAR_LEN_REF_LAYOUT
411    }
412}
413
414// # Conversions from `AlgebraicType` and friends
415
416impl From<AlgebraicType> for AlgebraicTypeLayout {
417    fn from(ty: AlgebraicType) -> Self {
418        match ty {
419            AlgebraicType::Sum(sum) => AlgebraicTypeLayout::Sum(sum.into()),
420            AlgebraicType::Product(prod) => AlgebraicTypeLayout::Product(prod.into()),
421
422            AlgebraicType::String => AlgebraicTypeLayout::VarLen(VarLenType::String),
423            AlgebraicType::Array(_) => AlgebraicTypeLayout::VarLen(VarLenType::Array(Box::new(ty))),
424
425            AlgebraicType::Bool => AlgebraicTypeLayout::Bool,
426            AlgebraicType::I8 => AlgebraicTypeLayout::I8,
427            AlgebraicType::U8 => AlgebraicTypeLayout::U8,
428            AlgebraicType::I16 => AlgebraicTypeLayout::I16,
429            AlgebraicType::U16 => AlgebraicTypeLayout::U16,
430            AlgebraicType::I32 => AlgebraicTypeLayout::I32,
431            AlgebraicType::U32 => AlgebraicTypeLayout::U32,
432            AlgebraicType::I64 => AlgebraicTypeLayout::I64,
433            AlgebraicType::U64 => AlgebraicTypeLayout::U64,
434            AlgebraicType::I128 => AlgebraicTypeLayout::I128,
435            AlgebraicType::U128 => AlgebraicTypeLayout::U128,
436            AlgebraicType::I256 => AlgebraicTypeLayout::I256,
437            AlgebraicType::U256 => AlgebraicTypeLayout::U256,
438            AlgebraicType::F32 => AlgebraicTypeLayout::F32,
439            AlgebraicType::F64 => AlgebraicTypeLayout::F64,
440
441            AlgebraicType::Ref(_) => todo!("Refs unsupported without typespace context"),
442        }
443    }
444}
445
446impl From<ProductType> for ProductTypeLayout {
447    fn from(ty: ProductType) -> Self {
448        let mut current_offset: usize = 0;
449
450        // Minimum possible alignment is 1, even though minimum possible size is 0.
451        // This is consistent with Rust.
452        let mut max_child_align = 1;
453
454        let mut fixed = true;
455        let elements = Vec::from(ty.elements)
456            .into_iter()
457            .map(|elem| {
458                let layout_type: AlgebraicTypeLayout = elem.algebraic_type.into();
459                fixed &= layout_type.layout().fixed;
460                let this_offset = align_to(current_offset, layout_type.align());
461                max_child_align = usize::max(max_child_align, layout_type.align());
462
463                current_offset = this_offset + layout_type.size();
464
465                ProductTypeElementLayout {
466                    offset: this_offset as u16,
467                    name: elem.name,
468                    ty: layout_type,
469                }
470            })
471            .collect::<Vec<_>>()
472            .into();
473
474        let layout = Layout {
475            align: max_child_align as u16,
476            size: align_to(current_offset, max_child_align) as u16,
477            fixed,
478        };
479
480        Self { layout, elements }
481    }
482}
483
484impl From<SumType> for SumTypeLayout {
485    fn from(ty: SumType) -> Self {
486        let mut max_child_size = 0;
487
488        // Minimum possible alignment is 1, even though minimum possible size is 0.
489        // This is consistent with Rust.
490        let mut max_child_align = 0;
491
492        let mut fixed = true;
493        let variants = Vec::from(ty.variants)
494            .into_iter()
495            .map(|variant| {
496                let layout_type: AlgebraicTypeLayout = variant.algebraic_type.into();
497                fixed &= layout_type.layout().fixed;
498
499                max_child_align = usize::max(max_child_align, layout_type.align());
500                max_child_size = usize::max(max_child_size, layout_type.size());
501
502                SumTypeVariantLayout {
503                    ty: layout_type,
504                    name: variant.name,
505                }
506            })
507            .collect::<Vec<_>>()
508            .into();
509
510        // Guarantees that tag fits inside align.
511        let align = u16::max(max_child_align as u16, 1);
512
513        // Ensure the payload field is sufficiently aligned for all its members.
514        // `max_child_size` and `max_child_align` will already be consistent
515        // if the most-aligned variant is also the largest,
516        // but this is not necessarily the case.
517        // E.g. if variant A is a product of 31 `u8`s, and variant B is a single `u64`,
518        // `max_child_size` will be 31 and `max_child_align` will be 8.
519        // Note that `payload_size` may be 0.
520        let payload_size = align_to(max_child_size, max_child_align);
521
522        // [tag | pad to align | payload]
523        let size = align + payload_size as u16;
524        let payload_offset = align;
525        let layout = Layout { align, size, fixed };
526        Self {
527            layout,
528            payload_offset,
529            variants,
530        }
531    }
532}
533
534// # Conversions to `AlgebraicType` and friends
535// Used for error reporting.
536
537impl AlgebraicTypeLayout {
538    /// Convert an `AlgebraicTypeLayout` back into an `AlgebraicType`,
539    /// removing layout information.
540    ///
541    /// This operation is O(n) in the number of nodes in the argument,
542    /// and may heap-allocate.
543    /// It is intended for use in error paths, where performance is a secondary concern.
544    pub fn algebraic_type(&self) -> AlgebraicType {
545        match self {
546            AlgebraicTypeLayout::Primitive(prim) => prim.algebraic_type(),
547            AlgebraicTypeLayout::VarLen(var_len) => var_len.algebraic_type(),
548            AlgebraicTypeLayout::Product(prod) => AlgebraicType::Product(prod.product_type()),
549            AlgebraicTypeLayout::Sum(sum) => AlgebraicType::Sum(sum.sum_type()),
550        }
551    }
552}
553
554impl VarLenType {
555    fn algebraic_type(&self) -> AlgebraicType {
556        match self {
557            VarLenType::String => AlgebraicType::String,
558            VarLenType::Array(ty) => ty.as_ref().clone(),
559        }
560    }
561}
562
563impl ProductTypeLayout {
564    pub(crate) fn product_type(&self) -> ProductType {
565        ProductType {
566            elements: self
567                .elements
568                .iter()
569                .map(ProductTypeElementLayout::product_type_element)
570                .collect(),
571        }
572    }
573
574    /// Convert a `ProductTypeLayout` back into an `AlgebraicType::Product`,
575    /// removing layout information.
576    ///
577    /// This operation is O(n) in the number of nodes in the argument,
578    /// and will heap-allocate.
579    /// It is intended for use in error paths, where performance is a secondary concern.
580    pub fn algebraic_type(&self) -> AlgebraicType {
581        AlgebraicType::Product(self.product_type())
582    }
583}
584
585impl ProductTypeElementLayout {
586    fn product_type_element(&self) -> ProductTypeElement {
587        ProductTypeElement {
588            algebraic_type: self.ty.algebraic_type(),
589            name: self.name.clone(),
590        }
591    }
592}
593
594impl SumTypeLayout {
595    fn sum_type(&self) -> SumType {
596        SumType {
597            variants: self
598                .variants
599                .iter()
600                .map(SumTypeVariantLayout::sum_type_variant)
601                .collect(),
602        }
603    }
604}
605
606impl SumTypeVariantLayout {
607    fn sum_type_variant(&self) -> SumTypeVariant {
608        SumTypeVariant {
609            algebraic_type: self.ty.algebraic_type(),
610            name: self.name.clone(),
611        }
612    }
613
614    /// Returns whether the variant has the given name.
615    pub fn has_name(&self, name: &str) -> bool {
616        self.name.as_deref() == Some(name)
617    }
618
619    /// Returns whether this is a unit variant.
620    pub fn is_unit(&self) -> bool {
621        self.ty.as_product().is_some_and(|ty| ty.elements.is_empty())
622    }
623}
624
625// # Inspecting layout
626
627impl SumTypeLayout {
628    pub fn offset_of_variant_data(&self, _variant_tag: u8) -> usize {
629        // Store the tag at the start, similar to BSATN.
630        // Unlike BSATN, there is also padding.
631        //
632        // ```ignore
633        // [ tag | padding to variant data align | variant data ]
634        // ```
635        //
636        self.payload_offset as usize
637    }
638
639    pub fn offset_of_tag(&self) -> usize {
640        // Store the tag at the start, similar to BSATN.
641        //
642        // ```ignore
643        // [ tag | padding to variant data align | variant data ]
644        // ```
645        //
646        0
647    }
648}
649
650impl ProductTypeLayout {
651    /// Returns the offset of the element at `field_idx`.
652    pub fn offset_of_element(&self, field_idx: usize) -> usize {
653        self.elements[field_idx].offset as usize
654    }
655}
656
657/// Counts the number of [`VarLenGranule`] allocations required to store `val` in a page.
658pub fn required_var_len_granules_for_row(val: &ProductValue) -> usize {
659    fn traverse_av(val: &AlgebraicValue, count: &mut usize) {
660        match val {
661            AlgebraicValue::Product(val) => traverse_product(val, count),
662            AlgebraicValue::Sum(val) => traverse_av(&val.value, count),
663            AlgebraicValue::Array(_) => add_for_bytestring(bsatn_len(val), count),
664            AlgebraicValue::String(val) => add_for_bytestring(val.len(), count),
665            _ => (),
666        }
667    }
668
669    fn traverse_product(val: &ProductValue, count: &mut usize) {
670        for elt in val {
671            traverse_av(elt, count);
672        }
673    }
674
675    fn add_for_bytestring(len_in_bytes: usize, count: &mut usize) {
676        *count += VarLenGranule::bytes_to_granules(len_in_bytes).0;
677    }
678
679    let mut required_granules: usize = 0;
680    traverse_product(val, &mut required_granules);
681    required_granules
682}
683
684/// Computes the size of `val` when BSATN encoding without actually encoding.
685pub fn bsatn_len(val: &AlgebraicValue) -> usize {
686    // We store arrays and maps BSATN-encoded,
687    // so we need to go through BSATN encoding to determine the size of the resulting byte blob,
688    // but we don't actually need that byte blob in this calculation,
689    // instead, we can just count them as a serialization format.
690    bsatn::to_len(val).unwrap()
691}
692
693impl<'de> DeserializeSeed<'de> for &AlgebraicTypeLayout {
694    type Output = AlgebraicValue;
695
696    fn deserialize<D: Deserializer<'de>>(self, de: D) -> Result<Self::Output, D::Error> {
697        match self {
698            AlgebraicTypeLayout::Sum(ty) => ty.deserialize(de).map(Into::into),
699            AlgebraicTypeLayout::Product(ty) => ty.deserialize(de).map(Into::into),
700            AlgebraicTypeLayout::Primitive(PrimitiveType::Bool) => bool::deserialize(de).map(Into::into),
701            AlgebraicTypeLayout::Primitive(PrimitiveType::I8) => i8::deserialize(de).map(Into::into),
702            AlgebraicTypeLayout::Primitive(PrimitiveType::U8) => u8::deserialize(de).map(Into::into),
703            AlgebraicTypeLayout::Primitive(PrimitiveType::I16) => i16::deserialize(de).map(Into::into),
704            AlgebraicTypeLayout::Primitive(PrimitiveType::U16) => u16::deserialize(de).map(Into::into),
705            AlgebraicTypeLayout::Primitive(PrimitiveType::I32) => i32::deserialize(de).map(Into::into),
706            AlgebraicTypeLayout::Primitive(PrimitiveType::U32) => u32::deserialize(de).map(Into::into),
707            AlgebraicTypeLayout::Primitive(PrimitiveType::I64) => i64::deserialize(de).map(Into::into),
708            AlgebraicTypeLayout::Primitive(PrimitiveType::U64) => u64::deserialize(de).map(Into::into),
709            AlgebraicTypeLayout::Primitive(PrimitiveType::I128) => i128::deserialize(de).map(Into::into),
710            AlgebraicTypeLayout::Primitive(PrimitiveType::U128) => u128::deserialize(de).map(Into::into),
711            AlgebraicTypeLayout::Primitive(PrimitiveType::I256) => i256::deserialize(de).map(Into::into),
712            AlgebraicTypeLayout::Primitive(PrimitiveType::U256) => u256::deserialize(de).map(Into::into),
713            AlgebraicTypeLayout::Primitive(PrimitiveType::F32) => f32::deserialize(de).map(Into::into),
714            AlgebraicTypeLayout::Primitive(PrimitiveType::F64) => f64::deserialize(de).map(Into::into),
715            AlgebraicTypeLayout::VarLen(VarLenType::Array(ty)) => WithTypespace::empty(&**ty).deserialize(de),
716            AlgebraicTypeLayout::VarLen(VarLenType::String) => <Box<str>>::deserialize(de).map(Into::into),
717        }
718    }
719}
720
721impl<'de> DeserializeSeed<'de> for &ProductTypeLayout {
722    type Output = ProductValue;
723
724    fn deserialize<D: Deserializer<'de>>(self, de: D) -> Result<Self::Output, D::Error> {
725        de.deserialize_product(self)
726    }
727}
728
729impl<'de> ProductVisitor<'de> for &ProductTypeLayout {
730    type Output = ProductValue;
731
732    fn product_name(&self) -> Option<&str> {
733        None
734    }
735    fn product_len(&self) -> usize {
736        self.elements.len()
737    }
738
739    fn visit_seq_product<A: SeqProductAccess<'de>>(self, mut tup: A) -> Result<Self::Output, A::Error> {
740        let mut elems: Vec<AlgebraicValue> = Vec::with_capacity(self.product_len());
741        for (i, elem_ty) in self.elements.iter().enumerate() {
742            let Some(elem_val) = tup.next_element_seed(&elem_ty.ty)? else {
743                return Err(A::Error::invalid_product_length(i, &self));
744            };
745            elems.push(elem_val);
746        }
747        Ok(elems.into())
748    }
749
750    fn visit_named_product<A: NamedProductAccess<'de>>(self, _: A) -> Result<Self::Output, A::Error> {
751        unreachable!()
752    }
753}
754
755impl<'de> DeserializeSeed<'de> for &SumTypeLayout {
756    type Output = SumValue;
757
758    fn deserialize<D: Deserializer<'de>>(self, deserializer: D) -> Result<Self::Output, D::Error> {
759        deserializer.deserialize_sum(self)
760    }
761}
762
763impl<'de> SumVisitor<'de> for &SumTypeLayout {
764    type Output = SumValue;
765
766    fn sum_name(&self) -> Option<&str> {
767        None
768    }
769
770    fn is_option(&self) -> bool {
771        match &*self.variants {
772            [first, second]
773                if second.is_unit() // Done first to avoid pointer indirection when it doesn't matter.
774                    && first.has_name(OPTION_SOME_TAG)
775                    && second.has_name(OPTION_NONE_TAG) =>
776            {
777                true
778            }
779            _ => false,
780        }
781    }
782
783    fn visit_sum<A: SumAccess<'de>>(self, data: A) -> Result<Self::Output, A::Error> {
784        let (tag, data) = data.variant(self)?;
785        // Find the variant type by `tag`.
786        let variant_ty = &self.variants[tag as usize].ty;
787
788        let value = Box::new(data.deserialize_seed(variant_ty)?);
789        Ok(SumValue { tag, value })
790    }
791}
792
793impl VariantVisitor for &SumTypeLayout {
794    type Output = u8;
795
796    fn variant_names(&self, names: &mut dyn ValidNames) {
797        // Provide the names known from the `SumType`.
798        names.extend(self.variants.iter().filter_map(|v| v.name.as_deref()));
799    }
800
801    fn visit_tag<E: Error>(self, tag: u8) -> Result<Self::Output, E> {
802        // Verify that tag identifies a valid variant in `SumType`.
803        self.variants
804            .get(tag as usize)
805            .ok_or_else(|| E::unknown_variant_tag(tag, &self))?;
806
807        Ok(tag)
808    }
809
810    fn visit_name<E: Error>(self, name: &str) -> Result<Self::Output, E> {
811        // Translate the variant `name` to its tag.
812        self.variants
813            .iter()
814            .position(|var| var.has_name(name))
815            .map(|pos| pos as u8)
816            .ok_or_else(|| E::unknown_variant_name(name, &self))
817    }
818}
819
820#[cfg(test)]
821mod test {
822    use super::*;
823    use itertools::Itertools as _;
824    use proptest::collection::vec;
825    use proptest::prelude::*;
826    use spacetimedb_sats::proptest::generate_algebraic_type;
827
828    #[test]
829    fn align_to_expected() {
830        fn assert_alignment(offset: usize, alignment: usize, expected: usize) {
831            assert_eq!(
832                align_to(offset, alignment),
833                expected,
834                "align_to({}, {}): expected {} but found {}",
835                offset,
836                alignment,
837                expected,
838                align_to(offset, alignment)
839            );
840        }
841
842        for align in [1usize, 2, 4, 8, 16, 32, 64] {
843            assert_alignment(0, align, 0);
844
845            for offset in 1..=align {
846                assert_alignment(offset, align, align);
847            }
848            for offset in (align + 1)..=(align * 2) {
849                assert_alignment(offset, align, align * 2);
850            }
851        }
852    }
853
854    fn assert_size_align(ty: AlgebraicType, size: usize, align: usize) {
855        let layout = AlgebraicTypeLayout::from(ty);
856        assert_eq!(layout.size(), size);
857        assert_eq!(layout.align(), align);
858    }
859
860    #[test]
861    fn known_product_expected_size_align() {
862        for (ty, size, align) in [
863            (AlgebraicType::product::<[AlgebraicType; 0]>([]), 0, 1),
864            (AlgebraicType::product([AlgebraicType::U8]), 1, 1),
865            (AlgebraicType::product([AlgebraicType::I8]), 1, 1),
866            (AlgebraicType::product([AlgebraicType::Bool]), 1, 1),
867            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U8]), 2, 1),
868            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U16]), 4, 2),
869            (
870                AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U8, AlgebraicType::U16]),
871                4,
872                2,
873            ),
874            (
875                AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U16, AlgebraicType::U8]),
876                6,
877                2,
878            ),
879            (
880                AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U8, AlgebraicType::U8]),
881                4,
882                2,
883            ),
884            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U32]), 8, 4),
885            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U64]), 16, 8),
886            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U128]), 32, 16),
887            (AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U8]), 4, 2),
888            (AlgebraicType::product([AlgebraicType::U32, AlgebraicType::U8]), 8, 4),
889            (AlgebraicType::product([AlgebraicType::U64, AlgebraicType::U8]), 16, 8),
890            (AlgebraicType::product([AlgebraicType::U128, AlgebraicType::U8]), 32, 16),
891            (AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U16]), 4, 2),
892            (AlgebraicType::product([AlgebraicType::U32, AlgebraicType::U32]), 8, 4),
893            (AlgebraicType::product([AlgebraicType::U64, AlgebraicType::U64]), 16, 8),
894            (
895                AlgebraicType::product([AlgebraicType::U128, AlgebraicType::U128]),
896                32,
897                16,
898            ),
899            (AlgebraicType::product([AlgebraicType::String]), 4, 2),
900            (
901                AlgebraicType::product([AlgebraicType::String, AlgebraicType::U16]),
902                6,
903                2,
904            ),
905            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I8]), 2, 1),
906            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I16]), 4, 2),
907            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I32]), 8, 4),
908            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I64]), 16, 8),
909            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I128]), 32, 16),
910            (AlgebraicType::product([AlgebraicType::I16, AlgebraicType::I8]), 4, 2),
911            (AlgebraicType::product([AlgebraicType::I32, AlgebraicType::I8]), 8, 4),
912            (AlgebraicType::product([AlgebraicType::I64, AlgebraicType::I8]), 16, 8),
913            (AlgebraicType::product([AlgebraicType::I128, AlgebraicType::I8]), 32, 16),
914            (AlgebraicType::product([AlgebraicType::I16, AlgebraicType::I16]), 4, 2),
915            (AlgebraicType::product([AlgebraicType::I32, AlgebraicType::I32]), 8, 4),
916            (AlgebraicType::product([AlgebraicType::I64, AlgebraicType::I64]), 16, 8),
917            (
918                AlgebraicType::product([AlgebraicType::I128, AlgebraicType::I128]),
919                32,
920                16,
921            ),
922            (
923                AlgebraicType::product([AlgebraicType::I256, AlgebraicType::U256]),
924                64,
925                32,
926            ),
927            (
928                AlgebraicType::product([AlgebraicType::String, AlgebraicType::I16]),
929                6,
930                2,
931            ),
932        ] {
933            assert_size_align(ty, size, align);
934        }
935    }
936
937    #[test]
938    fn known_sum_expected_size_align() {
939        for (ty, size, align) in [
940            (AlgebraicType::sum([AlgebraicType::U8]), 2, 1),
941            (AlgebraicType::sum([AlgebraicType::I8]), 2, 1),
942            (AlgebraicType::sum([AlgebraicType::Bool]), 2, 1),
943            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U8]), 2, 1),
944            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U16]), 4, 2),
945            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U32]), 8, 4),
946            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U64]), 16, 8),
947            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U128]), 32, 16),
948            (AlgebraicType::sum([AlgebraicType::U16, AlgebraicType::U8]), 4, 2),
949            (AlgebraicType::sum([AlgebraicType::U32, AlgebraicType::U8]), 8, 4),
950            (AlgebraicType::sum([AlgebraicType::U64, AlgebraicType::U8]), 16, 8),
951            (AlgebraicType::sum([AlgebraicType::U128, AlgebraicType::U8]), 32, 16),
952            (AlgebraicType::sum([AlgebraicType::U16, AlgebraicType::U16]), 4, 2),
953            (AlgebraicType::sum([AlgebraicType::U32, AlgebraicType::U32]), 8, 4),
954            (AlgebraicType::sum([AlgebraicType::U64, AlgebraicType::U64]), 16, 8),
955            (AlgebraicType::sum([AlgebraicType::U128, AlgebraicType::U128]), 32, 16),
956            (AlgebraicType::sum([AlgebraicType::String]), 6, 2),
957            (AlgebraicType::sum([AlgebraicType::String, AlgebraicType::U16]), 6, 2),
958            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I8]), 2, 1),
959            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I16]), 4, 2),
960            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I32]), 8, 4),
961            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I64]), 16, 8),
962            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I128]), 32, 16),
963            (AlgebraicType::sum([AlgebraicType::I16, AlgebraicType::I8]), 4, 2),
964            (AlgebraicType::sum([AlgebraicType::I32, AlgebraicType::I8]), 8, 4),
965            (AlgebraicType::sum([AlgebraicType::I64, AlgebraicType::I8]), 16, 8),
966            (AlgebraicType::sum([AlgebraicType::I128, AlgebraicType::I8]), 32, 16),
967            (AlgebraicType::sum([AlgebraicType::I16, AlgebraicType::I16]), 4, 2),
968            (AlgebraicType::sum([AlgebraicType::I32, AlgebraicType::I32]), 8, 4),
969            (AlgebraicType::sum([AlgebraicType::I64, AlgebraicType::I64]), 16, 8),
970            (AlgebraicType::sum([AlgebraicType::I128, AlgebraicType::I128]), 32, 16),
971            (AlgebraicType::sum([AlgebraicType::I256, AlgebraicType::I128]), 64, 32),
972            (AlgebraicType::sum([AlgebraicType::I256, AlgebraicType::U256]), 64, 32),
973            (AlgebraicType::sum([AlgebraicType::String, AlgebraicType::I16]), 6, 2),
974        ] {
975            assert_size_align(ty, size, align);
976        }
977    }
978
979    proptest! {
980        fn variant_order_irrelevant_for_layout(
981            variants in vec(generate_algebraic_type(), 0..5)
982        ) {
983            use spacetimedb_sats::SumTypeVariant;
984
985            let len = variants.len();
986            // Compute all permutations of the sum type with `variants`.
987            let sum_permutations = variants
988                .into_iter()
989                .permutations(len)
990                .map(|vars| vars.into_iter().map(SumTypeVariant::from).collect::<Box<[_]>>())
991                .map(AlgebraicType::sum);
992            // Compute the layouts of each equivalent sum type.
993            let mut sum_layout_perms = sum_permutations
994                .map(AlgebraicTypeLayout::from)
995                .map(|ty| *ty.layout());
996            // Assert that they are in fact equal in terms of layout.
997            prop_assert!(sum_layout_perms.all_equal());
998        }
999
1000        #[test]
1001        fn size_always_multiple_of_align(ty in generate_algebraic_type()) {
1002            let layout = AlgebraicTypeLayout::from(ty);
1003
1004            if layout.size() == 0 {
1005                assert_eq!(layout.align(), 1);
1006            } else {
1007                assert_eq!(layout.size() % layout.align(), 0);
1008            }
1009        }
1010    }
1011}
spacetimedb_table/layout.rs

spacetimedb_table/
layout.rs
