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

spacetimedb_sats/
layout.rs
