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

spacetimedb_sats/
layout.rs
