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    ///
193    /// See comment on [`IncompatibleTypeLayoutError`] about [`Box`]ing the error return.
194    fn ensure_compatible_with(&self, new: &Self) -> Result<(), Box<IncompatibleTypeLayoutError>> {
195        match (self, new) {
196            (Self::Sum(old), Self::Sum(new)) => old.ensure_compatible_with(new),
197            (Self::Product(old), Self::Product(new)) => old.view().ensure_compatible_with(new.view()),
198            (Self::Primitive(old), Self::Primitive(new)) => {
199                if old == new {
200                    Ok(())
201                } else {
202                    Err(Box::new(IncompatibleTypeLayoutError::DifferentPrimitiveTypes {
203                        old: old.algebraic_type(),
204                        new: new.algebraic_type(),
205                    }))
206                }
207            }
208            (Self::VarLen(VarLenType::Array(old)), Self::VarLen(VarLenType::Array(new))) => {
209                // NOTE(perf, centril): This might clone and heap allocate,
210                // but we don't care to avoid that and optimize right now,
211                // as this is only executed during upgrade / migration,
212                // and that doesn't need to be fast right now.
213                let old = AlgebraicTypeLayout::from(old.elem_ty.deref().clone());
214                let new = AlgebraicTypeLayout::from(new.elem_ty.deref().clone());
215                old.ensure_compatible_with(&new).map_err(|err| {
216                    Box::new(IncompatibleTypeLayoutError::IncompatibleArrayElements {
217                        old: old.algebraic_type(),
218                        new: new.algebraic_type(),
219                        err,
220                    })
221                })
222            }
223            (Self::VarLen(VarLenType::String), Self::VarLen(VarLenType::String)) => Ok(()),
224            _ => Err(Box::new(IncompatibleTypeLayoutError::DifferentKind {
225                old: self.algebraic_type(),
226                new: new.algebraic_type(),
227            })),
228        }
229    }
230}
231
232/// A collection of items, so that we can easily swap out the backing type.
233type Collection<T> = Box<[T]>;
234
235/// Fixed-length row portions must be at least large enough to store a `FreeCellRef`.
236pub const MIN_ROW_SIZE: Size = Size(2);
237
238/// Fixed-length row portions must also be sufficiently aligned to store a `FreeCellRef`.
239pub const MIN_ROW_ALIGN: Size = Size(2);
240
241/// Returns the minimum row size needed to store `required_bytes`
242/// accounting for the minimum row size and alignment.
243pub const fn row_size_for_bytes(required_bytes: usize) -> Size {
244    // Manual `Ord::max` because that function is not `const`.
245    if required_bytes > MIN_ROW_SIZE.len() {
246        Size(align_to(required_bytes, MIN_ROW_ALIGN.len()) as u16)
247    } else {
248        MIN_ROW_SIZE
249    }
250}
251
252/// Returns the minimum row size needed to store a `T`,
253/// accounting for the minimum row size and alignment.
254pub const fn row_size_for_type<T>() -> Size {
255    row_size_for_bytes(mem::size_of::<T>())
256}
257
258/// The type of a row, annotated with a [`Layout`].
259///
260/// This type ensures that the minimum row size is adhered to.
261#[derive(Debug, PartialEq, Eq, Clone)]
262pub struct RowTypeLayout {
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    ///
267    /// This is `Arc`ed at the row type level
268    /// as clones and drops of this showed up in flamegraphs.
269    /// A [`RowTypeLayout`] will typically be cloned once per table per transaction,
270    /// assuming the table is touched during that transaction.
271    /// This can be expensive for modules that have a lot of reducer calls per second.
272    pub elements: Arc<[ProductTypeElementLayout]>,
273}
274
275#[cfg(feature = "memory-usage")]
276impl spacetimedb_memory_usage::MemoryUsage for RowTypeLayout {
277    fn heap_usage(&self) -> usize {
278        let Self { layout, elements } = self;
279        layout.heap_usage() + elements.heap_usage()
280    }
281}
282
283impl RowTypeLayout {
284    /// Returns a view of this row type as a product type.
285    pub fn product(&self) -> ProductTypeLayoutView<'_> {
286        let elements = &*self.elements;
287        let layout = self.layout;
288        ProductTypeLayoutView { layout, elements }
289    }
290
291    /// Returns the row size for this row type.
292    pub fn size(&self) -> Size {
293        Size(self.product().size() as u16)
294    }
295
296    /// Can `self` be changed compatibly to `new`?
297    ///
298    /// If the types are incompatible, returns the incompatible sub-part and the reason.
299    /// See comment on [`IncompatibleTypeLayoutError`] about [`Box`]ing the error return.
300    pub fn ensure_compatible_with(&self, new: &RowTypeLayout) -> Result<(), Box<IncompatibleTypeLayoutError>> {
301        if self.layout != new.layout {
302            return Err(Box::new(IncompatibleTypeLayoutError::LayoutsNotEqual {
303                old: self.layout,
304                new: new.layout,
305            }));
306        }
307        self.product().ensure_compatible_with(new.product())
308    }
309}
310
311/// Reason why two [`RowTypeLayout`]s are incompatible for an auto-migration.
312///
313/// Reported by [`RowTypeLayout::ensure_compatible_with`] and friends.
314/// These methods are expected to return `Ok(())` except in the case of internal SpacetimeDB bugs,
315/// as migrations are validated by `spacetimedb_schema::auto_migrate` before executing,
316/// so we will [`Box`] these errors to keep the returned [`Result`] small and the happy path fast.
317#[derive(thiserror::Error, Debug, Clone)]
318pub enum IncompatibleTypeLayoutError {
319    #[error("Layout of new type {new:?} does not match layout of old type {old:?}")]
320    LayoutsNotEqual { old: Layout, new: Layout },
321    #[error("Product type elements at index {index} are incompatible: {err}")]
322    IncompatibleProductElements {
323        index: usize,
324        err: Box<IncompatibleTypeLayoutError>,
325    },
326    #[error("Sum type elements in variant {index} are incompatible: {err}")]
327    IncompatibleSumVariants {
328        index: usize,
329        err: Box<IncompatibleTypeLayoutError>,
330    },
331    #[error("New product type {new:?} has {} elements while old product type {old:?} has {} elements", .new.elements.len(), .old.elements.len())]
332    DifferentElementCounts { old: ProductType, new: ProductType },
333    #[error("New sum type {new:?} has {} variants, which is fewer than old sum type {old:?} with {} variants", .new.variants.len(), .old.variants.len())]
334    RemovedVariants { old: SumType, new: SumType },
335    #[error("New primitive type {new:?} is not the same as old primitive type {old:?}")]
336    DifferentPrimitiveTypes { old: AlgebraicType, new: AlgebraicType },
337    #[error("New array element type {new:?} is incompatible with old array element type {old:?}: {err}")]
338    IncompatibleArrayElements {
339        new: AlgebraicType,
340        old: AlgebraicType,
341        err: Box<IncompatibleTypeLayoutError>,
342    },
343    #[error("New type {new:?} is not the same kind (sum, product, primitive, etc.) as old type {old:?}")]
344    DifferentKind { old: AlgebraicType, new: AlgebraicType },
345}
346
347pub enum IncompatibleTypeReason {
348    LayoutsNotEqual,
349}
350
351impl HasLayout for RowTypeLayout {
352    fn layout(&self) -> &Layout {
353        &self.layout
354    }
355}
356
357impl Index<usize> for RowTypeLayout {
358    type Output = AlgebraicTypeLayout;
359    fn index(&self, index: usize) -> &Self::Output {
360        &self.elements[index].ty
361    }
362}
363
364/// A mirror of [`ProductType`] annotated with a [`Layout`].
365#[derive(Debug, PartialEq, Eq, Copy, Clone)]
366pub struct ProductTypeLayoutView<'a> {
367    /// The memoized layout of the product type.
368    pub layout: Layout,
369    /// The fields of the product type with their own layout annotations.
370    pub elements: &'a [ProductTypeElementLayout],
371}
372
373impl HasLayout for ProductTypeLayoutView<'_> {
374    fn layout(&self) -> &Layout {
375        &self.layout
376    }
377}
378
379impl ProductTypeLayoutView<'_> {
380    /// Can `self` be changed compatibly to `new`?
381    ///
382    /// See comment on [`IncompatibleTypeLayoutError`] about [`Box`]ing the error return.
383    // Intentionally fail fast rather than combining errors with [`spacetimedb_data_structures::error_stream`]
384    // because we've (at least theoretically) already passed through
385    // `spacetimedb_schema::auto_migrate::ensure_old_ty_upgradable_to_new` to get here,
386    // and that method has proper pretty error reporting with `ErrorStream`.
387    // The error here is for internal debugging.
388    fn ensure_compatible_with(self, new: Self) -> Result<(), Box<IncompatibleTypeLayoutError>> {
389        if self.elements.len() != new.elements.len() {
390            return Err(Box::new(IncompatibleTypeLayoutError::DifferentElementCounts {
391                old: self.product_type(),
392                new: new.product_type(),
393            }));
394        }
395        for (index, (old, new)) in self.elements.iter().zip(new.elements.iter()).enumerate() {
396            if let Err(err) = old.ty.ensure_compatible_with(&new.ty) {
397                return Err(Box::new(IncompatibleTypeLayoutError::IncompatibleProductElements {
398                    index,
399                    err,
400                }));
401            }
402        }
403        Ok(())
404    }
405}
406
407/// A mirror of [`ProductType`] annotated with a [`Layout`].
408#[derive(Debug, PartialEq, Eq, Clone)]
409pub struct ProductTypeLayout {
410    /// The memoized layout of the product type.
411    pub layout: Layout,
412    /// The fields of the product type with their own layout annotations.
413    pub elements: Collection<ProductTypeElementLayout>,
414}
415
416impl ProductTypeLayout {
417    /// Returns a view of this row type as a product type.
418    pub fn view(&self) -> ProductTypeLayoutView<'_> {
419        let elements = &*self.elements;
420        let layout = self.layout;
421        ProductTypeLayoutView { layout, elements }
422    }
423}
424
425#[cfg(feature = "memory-usage")]
426impl spacetimedb_memory_usage::MemoryUsage for ProductTypeLayout {
427    fn heap_usage(&self) -> usize {
428        let Self { layout, elements } = self;
429        layout.heap_usage() + elements.heap_usage()
430    }
431}
432
433impl HasLayout for ProductTypeLayout {
434    fn layout(&self) -> &Layout {
435        &self.layout
436    }
437}
438
439/// A mirrior of [`ProductTypeElement`] annotated with a [`Layout`].
440#[derive(Debug, PartialEq, Eq, Clone)]
441pub struct ProductTypeElementLayout {
442    /// The relative offset of a field's value to its parent product value.
443    pub offset: u16,
444
445    /// The type of the field.
446    pub ty: AlgebraicTypeLayout,
447
448    /// An optional name of the field.
449    ///
450    /// This allows us to convert back to `ProductTypeElement`,
451    /// which we do when reporting type errors.
452    pub name: Option<Box<str>>,
453}
454
455#[cfg(feature = "memory-usage")]
456impl spacetimedb_memory_usage::MemoryUsage for ProductTypeElementLayout {
457    fn heap_usage(&self) -> usize {
458        let Self { offset, ty, name } = self;
459        offset.heap_usage() + ty.heap_usage() + name.heap_usage()
460    }
461}
462
463/// A mirrior of [`SumType`] annotated with a [`Layout`].
464#[derive(Debug, PartialEq, Eq, Clone)]
465pub struct SumTypeLayout {
466    /// The layout of a sum value of this sum type.
467    pub layout: Layout,
468    /// The variants of the sum type.
469    pub variants: Collection<SumTypeVariantLayout>,
470    /// The relative offset of a sum value's payload for sums of this type.
471    /// Sum value tags are always at offset 0.
472    pub payload_offset: u16,
473}
474
475#[cfg(feature = "memory-usage")]
476impl spacetimedb_memory_usage::MemoryUsage for SumTypeLayout {
477    fn heap_usage(&self) -> usize {
478        let Self {
479            layout,
480            variants,
481            payload_offset,
482        } = self;
483        layout.heap_usage() + variants.heap_usage() + payload_offset.heap_usage()
484    }
485}
486
487impl HasLayout for SumTypeLayout {
488    fn layout(&self) -> &Layout {
489        &self.layout
490    }
491}
492
493/// A mirrior of [`SumTypeVariant`] annotated with a [`Layout`].
494#[derive(Debug, PartialEq, Eq, Clone)]
495pub struct SumTypeVariantLayout {
496    /// The type of the variant.
497    pub ty: AlgebraicTypeLayout,
498
499    /// An optional name of the variant.
500    ///
501    /// This allows us to convert back to `SumTypeVariant`,
502    /// which we do when reporting type errors.
503    pub name: Option<Box<str>>,
504}
505
506#[cfg(feature = "memory-usage")]
507impl spacetimedb_memory_usage::MemoryUsage for SumTypeVariantLayout {
508    fn heap_usage(&self) -> usize {
509        let Self { ty, name } = self;
510        ty.heap_usage() + name.heap_usage()
511    }
512}
513
514/// Scalar types, i.e. bools, integers and floats.
515/// These types do not require a `VarLenRef` indirection when stored in a `spacetimedb_table::table::Table`.
516#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
517pub enum PrimitiveType {
518    Bool,
519    I8,
520    U8,
521    I16,
522    U16,
523    I32,
524    U32,
525    I64,
526    U64,
527    I128,
528    U128,
529    I256,
530    U256,
531    F32,
532    F64,
533}
534
535#[cfg(feature = "memory-usage")]
536impl spacetimedb_memory_usage::MemoryUsage for PrimitiveType {}
537
538impl PrimitiveType {
539    pub fn algebraic_type(&self) -> AlgebraicType {
540        match self {
541            PrimitiveType::Bool => AlgebraicType::Bool,
542            PrimitiveType::I8 => AlgebraicType::I8,
543            PrimitiveType::U8 => AlgebraicType::U8,
544            PrimitiveType::I16 => AlgebraicType::I16,
545            PrimitiveType::U16 => AlgebraicType::U16,
546            PrimitiveType::I32 => AlgebraicType::I32,
547            PrimitiveType::U32 => AlgebraicType::U32,
548            PrimitiveType::I64 => AlgebraicType::I64,
549            PrimitiveType::U64 => AlgebraicType::U64,
550            PrimitiveType::I128 => AlgebraicType::I128,
551            PrimitiveType::U128 => AlgebraicType::U128,
552            PrimitiveType::I256 => AlgebraicType::I256,
553            PrimitiveType::U256 => AlgebraicType::U256,
554            PrimitiveType::F32 => AlgebraicType::F32,
555            PrimitiveType::F64 => AlgebraicType::F64,
556        }
557    }
558}
559
560impl HasLayout for PrimitiveType {
561    fn layout(&self) -> &'static Layout {
562        match self {
563            Self::Bool | Self::I8 | Self::U8 => &Layout {
564                size: 1,
565                align: 1,
566                fixed: true,
567            },
568            Self::I16 | Self::U16 => &Layout {
569                size: 2,
570                align: 2,
571                fixed: true,
572            },
573            Self::I32 | Self::U32 | Self::F32 => &Layout {
574                size: 4,
575                align: 4,
576                fixed: true,
577            },
578            Self::I64 | Self::U64 | Self::F64 => &Layout {
579                size: 8,
580                align: 8,
581                fixed: true,
582            },
583            Self::I128 | Self::U128 => &Layout {
584                size: 16,
585                align: 16,
586                fixed: true,
587            },
588            Self::I256 | Self::U256 => &Layout {
589                size: 32,
590                align: 32,
591                fixed: true,
592            },
593        }
594    }
595}
596
597/// Types requiring a `VarLenRef` indirection,
598/// i.e. strings, arrays, and maps.
599#[derive(Debug, PartialEq, Eq, Clone)]
600pub enum VarLenType {
601    /// The string type corresponds to `AlgebraicType::String`.
602    String,
603    /// An array type. The inner `AlgebraicType` is stored here.
604    ///
605    /// Previously, the outer type, i.e., `AlgebraicType::Array` was stored.
606    /// However, this is both more inefficient and bug prone.
607    Array(ArrayType),
608}
609
610#[cfg(feature = "memory-usage")]
611impl spacetimedb_memory_usage::MemoryUsage for VarLenType {
612    fn heap_usage(&self) -> usize {
613        match self {
614            VarLenType::String => 0,
615            VarLenType::Array(x) => x.heap_usage(),
616        }
617    }
618}
619
620/// The layout of var-len objects. Aligned at a `u16` which it has 2 of.
621pub const VAR_LEN_REF_LAYOUT: Layout = Layout {
622    size: 4,
623    align: 2,
624    fixed: false,
625};
626
627impl HasLayout for VarLenType {
628    fn layout(&self) -> &Layout {
629        &VAR_LEN_REF_LAYOUT
630    }
631}
632
633// # Conversions from `AlgebraicType` and friends
634
635impl From<AlgebraicType> for AlgebraicTypeLayout {
636    fn from(ty: AlgebraicType) -> Self {
637        match ty {
638            AlgebraicType::Sum(sum) => AlgebraicTypeLayout::Sum(sum.into()),
639            AlgebraicType::Product(prod) => AlgebraicTypeLayout::Product(prod.into()),
640
641            AlgebraicType::String => AlgebraicTypeLayout::VarLen(VarLenType::String),
642            AlgebraicType::Array(array) => AlgebraicTypeLayout::VarLen(VarLenType::Array(array)),
643
644            AlgebraicType::Bool => AlgebraicTypeLayout::Bool,
645            AlgebraicType::I8 => AlgebraicTypeLayout::I8,
646            AlgebraicType::U8 => AlgebraicTypeLayout::U8,
647            AlgebraicType::I16 => AlgebraicTypeLayout::I16,
648            AlgebraicType::U16 => AlgebraicTypeLayout::U16,
649            AlgebraicType::I32 => AlgebraicTypeLayout::I32,
650            AlgebraicType::U32 => AlgebraicTypeLayout::U32,
651            AlgebraicType::I64 => AlgebraicTypeLayout::I64,
652            AlgebraicType::U64 => AlgebraicTypeLayout::U64,
653            AlgebraicType::I128 => AlgebraicTypeLayout::I128,
654            AlgebraicType::U128 => AlgebraicTypeLayout::U128,
655            AlgebraicType::I256 => AlgebraicTypeLayout::I256,
656            AlgebraicType::U256 => AlgebraicTypeLayout::U256,
657            AlgebraicType::F32 => AlgebraicTypeLayout::F32,
658            AlgebraicType::F64 => AlgebraicTypeLayout::F64,
659
660            AlgebraicType::Ref(_) => todo!("Refs unsupported without typespace context"),
661        }
662    }
663}
664
665/// Constructs the layout form of `ty`, returning the elements as `C` as well as the memoized `Layout`.
666fn product_type_layout<C: FromIterator<ProductTypeElementLayout>>(ty: ProductType) -> (C, Layout) {
667    let mut current_offset: usize = 0;
668
669    // Minimum possible alignment is 1, even though minimum possible size is 0.
670    // This is consistent with Rust.
671    let mut max_child_align = 1;
672
673    let mut fixed = true;
674    let elements = Vec::from(ty.elements)
675        .into_iter()
676        .map(|elem| {
677            let layout_type: AlgebraicTypeLayout = elem.algebraic_type.into();
678            fixed &= layout_type.layout().fixed;
679            let this_offset = align_to(current_offset, layout_type.align());
680            max_child_align = usize::max(max_child_align, layout_type.align());
681
682            current_offset = this_offset + layout_type.size();
683
684            ProductTypeElementLayout {
685                offset: this_offset as u16,
686                name: elem.name,
687                ty: layout_type,
688            }
689        })
690        .collect();
691
692    let layout = Layout {
693        align: max_child_align as u16,
694        size: align_to(current_offset, max_child_align) as u16,
695        fixed,
696    };
697
698    (elements, layout)
699}
700
701impl From<ProductType> for RowTypeLayout {
702    fn from(ty: ProductType) -> Self {
703        let (elements, mut layout) = product_type_layout(ty);
704        layout.size = row_size_for_bytes(layout.size as usize).0;
705        Self { layout, elements }
706    }
707}
708
709impl From<ProductType> for ProductTypeLayout {
710    fn from(ty: ProductType) -> Self {
711        let (elements, layout) = product_type_layout(ty);
712        Self { layout, elements }
713    }
714}
715
716impl From<SumType> for SumTypeLayout {
717    fn from(ty: SumType) -> Self {
718        let mut max_child_size = 0;
719
720        // Minimum possible alignment is 1, even though minimum possible size is 0.
721        // This is consistent with Rust.
722        let mut max_child_align = 0;
723
724        let mut fixed = true;
725        let variants = Vec::from(ty.variants)
726            .into_iter()
727            .map(|variant| {
728                let layout_type: AlgebraicTypeLayout = variant.algebraic_type.into();
729                fixed &= layout_type.layout().fixed;
730
731                max_child_align = usize::max(max_child_align, layout_type.align());
732                max_child_size = usize::max(max_child_size, layout_type.size());
733
734                SumTypeVariantLayout {
735                    ty: layout_type,
736                    name: variant.name,
737                }
738            })
739            .collect::<Vec<_>>()
740            .into();
741
742        // Guarantees that tag fits inside align.
743        let align = u16::max(max_child_align as u16, 1);
744
745        // Ensure the payload field is sufficiently aligned for all its members.
746        // `max_child_size` and `max_child_align` will already be consistent
747        // if the most-aligned variant is also the largest,
748        // but this is not necessarily the case.
749        // E.g. if variant A is a product of 31 `u8`s, and variant B is a single `u64`,
750        // `max_child_size` will be 31 and `max_child_align` will be 8.
751        // Note that `payload_size` may be 0.
752        let payload_size = align_to(max_child_size, max_child_align);
753
754        // [tag | pad to align | payload]
755        let size = align + payload_size as u16;
756        let payload_offset = align;
757        let layout = Layout { align, size, fixed };
758        Self {
759            layout,
760            payload_offset,
761            variants,
762        }
763    }
764}
765
766// # Conversions to `AlgebraicType` and friends
767// Used for error reporting.
768
769impl AlgebraicTypeLayout {
770    /// Convert an `AlgebraicTypeLayout` back into an `AlgebraicType`,
771    /// removing layout information.
772    ///
773    /// This operation is O(n) in the number of nodes in the argument,
774    /// and may heap-allocate.
775    /// It is intended for use in error paths, where performance is a secondary concern.
776    pub fn algebraic_type(&self) -> AlgebraicType {
777        match self {
778            Self::Primitive(prim) => prim.algebraic_type(),
779            Self::VarLen(VarLenType::String) => AlgebraicType::String,
780            Self::VarLen(VarLenType::Array(array)) => AlgebraicType::Array(array.clone()),
781            Self::Product(prod) => AlgebraicType::Product(prod.view().product_type()),
782            Self::Sum(sum) => AlgebraicType::Sum(sum.sum_type()),
783        }
784    }
785}
786
787impl ProductTypeLayoutView<'_> {
788    pub fn product_type(&self) -> ProductType {
789        ProductType {
790            elements: self
791                .elements
792                .iter()
793                .map(ProductTypeElementLayout::product_type_element)
794                .collect(),
795        }
796    }
797
798    /// Convert a `ProductTypeLayout` back into an `AlgebraicType::Product`,
799    /// removing layout information.
800    ///
801    /// This operation is O(n) in the number of nodes in the argument,
802    /// and will heap-allocate.
803    /// It is intended for use in error paths, where performance is a secondary concern.
804    pub fn algebraic_type(&self) -> AlgebraicType {
805        AlgebraicType::Product(self.product_type())
806    }
807}
808
809impl ProductTypeElementLayout {
810    fn product_type_element(&self) -> ProductTypeElement {
811        ProductTypeElement {
812            algebraic_type: self.ty.algebraic_type(),
813            name: self.name.clone(),
814        }
815    }
816}
817
818impl SumTypeLayout {
819    fn sum_type(&self) -> SumType {
820        SumType {
821            variants: self
822                .variants
823                .iter()
824                .map(SumTypeVariantLayout::sum_type_variant)
825                .collect(),
826        }
827    }
828
829    /// Can `self` be changed compatibly to `new`?
830    ///
831    /// In the case of sums, the old variants need only be a prefix of the new.
832    ///
833    /// See comment on [`IncompatibleTypeLayoutError`] about [`Box`]ing the error return.
834    // Intentionally fail fast rather than combining errors with [`spacetimedb_data_structures::error_stream`]
835    // because we've (at least theoretically) already passed through
836    // `spacetimedb_schema::auto_migrate::ensure_old_ty_upgradable_to_new` to get here,
837    // and that method has proper pretty error reporting with `ErrorStream`.
838    // The error here is for internal debugging.
839    fn ensure_compatible_with(&self, new: &SumTypeLayout) -> Result<(), Box<IncompatibleTypeLayoutError>> {
840        if self.variants.len() > new.variants.len() {
841            return Err(Box::new(IncompatibleTypeLayoutError::RemovedVariants {
842                old: self.sum_type(),
843                new: new.sum_type(),
844            }));
845        }
846        for (index, (old, new)) in self.variants.iter().zip(self.variants.iter()).enumerate() {
847            if let Err(err) = old.ty.ensure_compatible_with(&new.ty) {
848                return Err(Box::new(IncompatibleTypeLayoutError::IncompatibleSumVariants {
849                    index,
850                    err,
851                }));
852            }
853        }
854        Ok(())
855    }
856}
857
858impl SumTypeVariantLayout {
859    fn sum_type_variant(&self) -> SumTypeVariant {
860        SumTypeVariant {
861            algebraic_type: self.ty.algebraic_type(),
862            name: self.name.clone(),
863        }
864    }
865
866    /// Returns whether the variant has the given name.
867    pub fn has_name(&self, name: &str) -> bool {
868        self.name.as_deref() == Some(name)
869    }
870
871    /// Returns whether this is a unit variant.
872    pub fn is_unit(&self) -> bool {
873        self.ty.as_product().is_some_and(|ty| ty.elements.is_empty())
874    }
875}
876
877// # Inspecting layout
878
879impl SumTypeLayout {
880    pub fn offset_of_variant_data(&self, _variant_tag: u8) -> usize {
881        // Store the tag at the start, similar to BSATN.
882        // Unlike BSATN, there is also padding.
883        //
884        // ```ignore
885        // [ tag | padding to variant data align | variant data ]
886        // ```
887        //
888        self.payload_offset as usize
889    }
890
891    pub fn offset_of_tag(&self) -> usize {
892        // Store the tag at the start, similar to BSATN.
893        //
894        // ```ignore
895        // [ tag | padding to variant data align | variant data ]
896        // ```
897        //
898        0
899    }
900}
901
902impl<'de> DeserializeSeed<'de> for &AlgebraicTypeLayout {
903    type Output = AlgebraicValue;
904
905    fn deserialize<D: Deserializer<'de>>(self, de: D) -> Result<Self::Output, D::Error> {
906        match self {
907            AlgebraicTypeLayout::Sum(ty) => ty.deserialize(de).map(Into::into),
908            AlgebraicTypeLayout::Product(ty) => ty.view().deserialize(de).map(Into::into),
909            AlgebraicTypeLayout::Primitive(PrimitiveType::Bool) => bool::deserialize(de).map(Into::into),
910            AlgebraicTypeLayout::Primitive(PrimitiveType::I8) => i8::deserialize(de).map(Into::into),
911            AlgebraicTypeLayout::Primitive(PrimitiveType::U8) => u8::deserialize(de).map(Into::into),
912            AlgebraicTypeLayout::Primitive(PrimitiveType::I16) => i16::deserialize(de).map(Into::into),
913            AlgebraicTypeLayout::Primitive(PrimitiveType::U16) => u16::deserialize(de).map(Into::into),
914            AlgebraicTypeLayout::Primitive(PrimitiveType::I32) => i32::deserialize(de).map(Into::into),
915            AlgebraicTypeLayout::Primitive(PrimitiveType::U32) => u32::deserialize(de).map(Into::into),
916            AlgebraicTypeLayout::Primitive(PrimitiveType::I64) => i64::deserialize(de).map(Into::into),
917            AlgebraicTypeLayout::Primitive(PrimitiveType::U64) => u64::deserialize(de).map(Into::into),
918            AlgebraicTypeLayout::Primitive(PrimitiveType::I128) => i128::deserialize(de).map(Into::into),
919            AlgebraicTypeLayout::Primitive(PrimitiveType::U128) => u128::deserialize(de).map(Into::into),
920            AlgebraicTypeLayout::Primitive(PrimitiveType::I256) => i256::deserialize(de).map(Into::into),
921            AlgebraicTypeLayout::Primitive(PrimitiveType::U256) => u256::deserialize(de).map(Into::into),
922            AlgebraicTypeLayout::Primitive(PrimitiveType::F32) => f32::deserialize(de).map(Into::into),
923            AlgebraicTypeLayout::Primitive(PrimitiveType::F64) => f64::deserialize(de).map(Into::into),
924            AlgebraicTypeLayout::VarLen(VarLenType::Array(ty)) => {
925                WithTypespace::empty(ty).deserialize(de).map(AlgebraicValue::Array)
926            }
927            AlgebraicTypeLayout::VarLen(VarLenType::String) => <Box<str>>::deserialize(de).map(Into::into),
928        }
929    }
930}
931
932impl<'de> DeserializeSeed<'de> for ProductTypeLayoutView<'_> {
933    type Output = ProductValue;
934
935    fn deserialize<D: Deserializer<'de>>(self, de: D) -> Result<Self::Output, D::Error> {
936        de.deserialize_product(self)
937    }
938}
939
940impl<'de> ProductVisitor<'de> for ProductTypeLayoutView<'_> {
941    type Output = ProductValue;
942
943    fn product_name(&self) -> Option<&str> {
944        None
945    }
946    fn product_len(&self) -> usize {
947        self.elements.len()
948    }
949
950    fn visit_seq_product<A: SeqProductAccess<'de>>(self, mut tup: A) -> Result<Self::Output, A::Error> {
951        let mut elems: Vec<AlgebraicValue> = Vec::with_capacity(self.product_len());
952        for (i, elem_ty) in self.elements.iter().enumerate() {
953            let Some(elem_val) = tup.next_element_seed(&elem_ty.ty)? else {
954                return Err(A::Error::invalid_product_length(i, &self));
955            };
956            elems.push(elem_val);
957        }
958        Ok(elems.into())
959    }
960
961    fn visit_named_product<A: NamedProductAccess<'de>>(self, _: A) -> Result<Self::Output, A::Error> {
962        unreachable!()
963    }
964}
965
966impl<'de> DeserializeSeed<'de> for &SumTypeLayout {
967    type Output = SumValue;
968
969    fn deserialize<D: Deserializer<'de>>(self, deserializer: D) -> Result<Self::Output, D::Error> {
970        deserializer.deserialize_sum(self)
971    }
972}
973
974impl<'de> SumVisitor<'de> for &SumTypeLayout {
975    type Output = SumValue;
976
977    fn sum_name(&self) -> Option<&str> {
978        None
979    }
980
981    fn is_option(&self) -> bool {
982        match &*self.variants {
983            [first, second]
984                if second.is_unit() // Done first to avoid pointer indirection when it doesn't matter.
985                    && first.has_name(OPTION_SOME_TAG)
986                    && second.has_name(OPTION_NONE_TAG) =>
987            {
988                true
989            }
990            _ => false,
991        }
992    }
993
994    fn visit_sum<A: SumAccess<'de>>(self, data: A) -> Result<Self::Output, A::Error> {
995        let (tag, data) = data.variant(self)?;
996        // Find the variant type by `tag`.
997        let variant_ty = &self.variants[tag as usize].ty;
998
999        let value = data.deserialize_seed(variant_ty)?;
1000        Ok(SumValue::new(tag, value))
1001    }
1002}
1003
1004impl VariantVisitor<'_> for &SumTypeLayout {
1005    type Output = u8;
1006
1007    fn variant_names(&self) -> impl '_ + Iterator<Item = &str> {
1008        // Provide the names known from the `SumType`.
1009        self.variants.iter().filter_map(|v| v.name.as_deref())
1010    }
1011
1012    fn visit_tag<E: Error>(self, tag: u8) -> Result<Self::Output, E> {
1013        // Verify that tag identifies a valid variant in `SumType`.
1014        self.variants
1015            .get(tag as usize)
1016            .ok_or_else(|| E::unknown_variant_tag(tag, &self))?;
1017
1018        Ok(tag)
1019    }
1020
1021    fn visit_name<E: Error>(self, name: &str) -> Result<Self::Output, E> {
1022        // Translate the variant `name` to its tag.
1023        self.variants
1024            .iter()
1025            .position(|var| var.has_name(name))
1026            .map(|pos| pos as u8)
1027            .ok_or_else(|| E::unknown_variant_name(name, &self))
1028    }
1029}
1030
1031#[cfg(test)]
1032mod test {
1033    use super::*;
1034    use crate::proptest::generate_algebraic_type;
1035    use itertools::Itertools as _;
1036    use proptest::collection::vec;
1037    use proptest::prelude::*;
1038
1039    #[test]
1040    fn align_to_expected() {
1041        fn assert_alignment(offset: usize, alignment: usize, expected: usize) {
1042            assert_eq!(
1043                align_to(offset, alignment),
1044                expected,
1045                "align_to({}, {}): expected {} but found {}",
1046                offset,
1047                alignment,
1048                expected,
1049                align_to(offset, alignment)
1050            );
1051        }
1052
1053        for align in [1usize, 2, 4, 8, 16, 32, 64] {
1054            assert_alignment(0, align, 0);
1055
1056            for offset in 1..=align {
1057                assert_alignment(offset, align, align);
1058            }
1059            for offset in (align + 1)..=(align * 2) {
1060                assert_alignment(offset, align, align * 2);
1061            }
1062        }
1063    }
1064
1065    fn assert_size_align(ty: AlgebraicType, size: usize, align: usize) {
1066        let layout = AlgebraicTypeLayout::from(ty);
1067        assert_eq!(layout.size(), size);
1068        assert_eq!(layout.align(), align);
1069    }
1070
1071    #[test]
1072    fn known_product_expected_size_align() {
1073        for (ty, size, align) in [
1074            (AlgebraicType::product::<[AlgebraicType; 0]>([]), 0, 1),
1075            (AlgebraicType::product([AlgebraicType::U8]), 1, 1),
1076            (AlgebraicType::product([AlgebraicType::I8]), 1, 1),
1077            (AlgebraicType::product([AlgebraicType::Bool]), 1, 1),
1078            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U8]), 2, 1),
1079            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U16]), 4, 2),
1080            (
1081                AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U8, AlgebraicType::U16]),
1082                4,
1083                2,
1084            ),
1085            (
1086                AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U16, AlgebraicType::U8]),
1087                6,
1088                2,
1089            ),
1090            (
1091                AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U8, AlgebraicType::U8]),
1092                4,
1093                2,
1094            ),
1095            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U32]), 8, 4),
1096            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U64]), 16, 8),
1097            (AlgebraicType::product([AlgebraicType::U8, AlgebraicType::U128]), 32, 16),
1098            (AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U8]), 4, 2),
1099            (AlgebraicType::product([AlgebraicType::U32, AlgebraicType::U8]), 8, 4),
1100            (AlgebraicType::product([AlgebraicType::U64, AlgebraicType::U8]), 16, 8),
1101            (AlgebraicType::product([AlgebraicType::U128, AlgebraicType::U8]), 32, 16),
1102            (AlgebraicType::product([AlgebraicType::U16, AlgebraicType::U16]), 4, 2),
1103            (AlgebraicType::product([AlgebraicType::U32, AlgebraicType::U32]), 8, 4),
1104            (AlgebraicType::product([AlgebraicType::U64, AlgebraicType::U64]), 16, 8),
1105            (
1106                AlgebraicType::product([AlgebraicType::U128, AlgebraicType::U128]),
1107                32,
1108                16,
1109            ),
1110            (AlgebraicType::product([AlgebraicType::String]), 4, 2),
1111            (
1112                AlgebraicType::product([AlgebraicType::String, AlgebraicType::U16]),
1113                6,
1114                2,
1115            ),
1116            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I8]), 2, 1),
1117            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I16]), 4, 2),
1118            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I32]), 8, 4),
1119            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I64]), 16, 8),
1120            (AlgebraicType::product([AlgebraicType::I8, AlgebraicType::I128]), 32, 16),
1121            (AlgebraicType::product([AlgebraicType::I16, AlgebraicType::I8]), 4, 2),
1122            (AlgebraicType::product([AlgebraicType::I32, AlgebraicType::I8]), 8, 4),
1123            (AlgebraicType::product([AlgebraicType::I64, AlgebraicType::I8]), 16, 8),
1124            (AlgebraicType::product([AlgebraicType::I128, AlgebraicType::I8]), 32, 16),
1125            (AlgebraicType::product([AlgebraicType::I16, AlgebraicType::I16]), 4, 2),
1126            (AlgebraicType::product([AlgebraicType::I32, AlgebraicType::I32]), 8, 4),
1127            (AlgebraicType::product([AlgebraicType::I64, AlgebraicType::I64]), 16, 8),
1128            (
1129                AlgebraicType::product([AlgebraicType::I128, AlgebraicType::I128]),
1130                32,
1131                16,
1132            ),
1133            (
1134                AlgebraicType::product([AlgebraicType::I256, AlgebraicType::U256]),
1135                64,
1136                32,
1137            ),
1138            (
1139                AlgebraicType::product([AlgebraicType::String, AlgebraicType::I16]),
1140                6,
1141                2,
1142            ),
1143        ] {
1144            assert_size_align(ty, size, align);
1145        }
1146    }
1147
1148    #[test]
1149    fn known_sum_expected_size_align() {
1150        for (ty, size, align) in [
1151            (AlgebraicType::sum([AlgebraicType::U8]), 2, 1),
1152            (AlgebraicType::sum([AlgebraicType::I8]), 2, 1),
1153            (AlgebraicType::sum([AlgebraicType::Bool]), 2, 1),
1154            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U8]), 2, 1),
1155            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U16]), 4, 2),
1156            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U32]), 8, 4),
1157            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U64]), 16, 8),
1158            (AlgebraicType::sum([AlgebraicType::U8, AlgebraicType::U128]), 32, 16),
1159            (AlgebraicType::sum([AlgebraicType::U16, AlgebraicType::U8]), 4, 2),
1160            (AlgebraicType::sum([AlgebraicType::U32, AlgebraicType::U8]), 8, 4),
1161            (AlgebraicType::sum([AlgebraicType::U64, AlgebraicType::U8]), 16, 8),
1162            (AlgebraicType::sum([AlgebraicType::U128, AlgebraicType::U8]), 32, 16),
1163            (AlgebraicType::sum([AlgebraicType::U16, AlgebraicType::U16]), 4, 2),
1164            (AlgebraicType::sum([AlgebraicType::U32, AlgebraicType::U32]), 8, 4),
1165            (AlgebraicType::sum([AlgebraicType::U64, AlgebraicType::U64]), 16, 8),
1166            (AlgebraicType::sum([AlgebraicType::U128, AlgebraicType::U128]), 32, 16),
1167            (AlgebraicType::sum([AlgebraicType::String]), 6, 2),
1168            (AlgebraicType::sum([AlgebraicType::String, AlgebraicType::U16]), 6, 2),
1169            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I8]), 2, 1),
1170            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I16]), 4, 2),
1171            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I32]), 8, 4),
1172            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I64]), 16, 8),
1173            (AlgebraicType::sum([AlgebraicType::I8, AlgebraicType::I128]), 32, 16),
1174            (AlgebraicType::sum([AlgebraicType::I16, AlgebraicType::I8]), 4, 2),
1175            (AlgebraicType::sum([AlgebraicType::I32, AlgebraicType::I8]), 8, 4),
1176            (AlgebraicType::sum([AlgebraicType::I64, AlgebraicType::I8]), 16, 8),
1177            (AlgebraicType::sum([AlgebraicType::I128, AlgebraicType::I8]), 32, 16),
1178            (AlgebraicType::sum([AlgebraicType::I16, AlgebraicType::I16]), 4, 2),
1179            (AlgebraicType::sum([AlgebraicType::I32, AlgebraicType::I32]), 8, 4),
1180            (AlgebraicType::sum([AlgebraicType::I64, AlgebraicType::I64]), 16, 8),
1181            (AlgebraicType::sum([AlgebraicType::I128, AlgebraicType::I128]), 32, 16),
1182            (AlgebraicType::sum([AlgebraicType::I256, AlgebraicType::I128]), 64, 32),
1183            (AlgebraicType::sum([AlgebraicType::I256, AlgebraicType::U256]), 64, 32),
1184            (AlgebraicType::sum([AlgebraicType::String, AlgebraicType::I16]), 6, 2),
1185        ] {
1186            assert_size_align(ty, size, align);
1187        }
1188    }
1189
1190    proptest! {
1191        fn variant_order_irrelevant_for_layout(
1192            variants in vec(generate_algebraic_type(), 0..5)
1193        ) {
1194            use crate::SumTypeVariant;
1195
1196            let len = variants.len();
1197            // Compute all permutations of the sum type with `variants`.
1198            let sum_permutations = variants
1199                .into_iter()
1200                .permutations(len)
1201                .map(|vars| vars.into_iter().map(SumTypeVariant::from).collect::<Box<[_]>>())
1202                .map(AlgebraicType::sum);
1203            // Compute the layouts of each equivalent sum type.
1204            let mut sum_layout_perms = sum_permutations
1205                .map(AlgebraicTypeLayout::from)
1206                .map(|ty| *ty.layout());
1207            // Assert that they are in fact equal in terms of layout.
1208            prop_assert!(sum_layout_perms.all_equal());
1209        }
1210
1211        #[test]
1212        fn size_always_multiple_of_align(ty in generate_algebraic_type()) {
1213            let layout = AlgebraicTypeLayout::from(ty);
1214
1215            if layout.size() == 0 {
1216                assert_eq!(layout.align(), 1);
1217            } else {
1218                assert_eq!(layout.size() % layout.align(), 0);
1219            }
1220        }
1221    }
1222
1223    #[test]
1224    fn infinite_recursion_in_ensure_compatible_with_with_array_type() {
1225        let ty = AlgebraicTypeLayout::from(AlgebraicType::array(AlgebraicType::U64));
1226        // This would previously cause an infinite recursion / stack overflow
1227        // due the setup where `AlgebraicTypeLayout::VarLen(Array(x))` stored
1228        // `x = Box::new(AlgebraicType::Array(elem_ty))`.
1229        // The method `AlgebraicTypeLayout::ensure_compatible_with` was not setup to handle that.
1230        // To avoid such bugs in the future, `x` is now `elem_ty` instead.
1231        assert!(ty.ensure_compatible_with(&ty).is_ok());
1232    }
1233}
spacetimedb_sats/layout.rs

spacetimedb_sats/
layout.rs
