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

spacetimedb_table/
layout.rs
