spacetimedb_sats/
algebraic_value.rs

1pub mod de;
2pub mod ser;
3
4use crate::{AlgebraicType, ArrayValue, ProductValue, SumValue};
5use core::mem;
6use core::ops::{Bound, RangeBounds};
7use derive_more::From;
8use enum_as_inner::EnumAsInner;
9
10pub use ethnum::{i256, u256};
11
12/// Totally ordered [`f32`] allowing all IEEE-754 floating point values.
13pub type F32 = decorum::Total<f32>;
14
15/// Totally ordered [`f64`] allowing all IEEE-754 floating point values.
16pub type F64 = decorum::Total<f64>;
17
18/// A value in SATS typed at some [`AlgebraicType`].
19///
20/// Values are type erased, so they do not store their type.
21/// This is important mainly for space efficiency,
22/// including network latency and bandwidth.
23///
24/// These are only values and not expressions.
25/// That is, they are canonical and cannot be simplified further by some evaluation.
26/// So forms like `42 + 24` are not represented in an `AlgebraicValue`.
27#[derive(EnumAsInner, Debug, Clone, Eq, PartialEq, Ord, PartialOrd, From)]
28pub enum AlgebraicValue {
29    /// The minimum value in the total ordering.
30    /// Cannot be serialized and only exists to facilitate range index scans.
31    /// This variant must always be first.
32    Min,
33
34    /// A structural sum value.
35    ///
36    /// Given a sum type `{ N_0(T_0), N_1(T_1), ..., N_n(T_n) }`
37    /// where `N_i` denotes a variant name
38    /// and where `T_i` denotes the type the variant stores,
39    /// a sum value makes a specific choice as to the variant.
40    /// So for example, we might chose `N_1(T_1)`
41    /// and represent this choice with `(1, v)` where `v` is a value of type `T_1`.
42    Sum(SumValue),
43    /// A structural product value.
44    ///
45    /// Given a product type `{ N_0: T_0, N_1: T_1, ..., N_n: T_n }`
46    /// where `N_i` denotes a field / element name
47    /// and where `T_i` denotes the type the field stores,
48    /// a product value stores a value `v_i` of type `T_i` for each field `N_i`.
49    Product(ProductValue),
50    /// A homogeneous array of `AlgebraicValue`s.
51    /// The array has the type [`AlgebraicType::Array(elem_ty)`].
52    ///
53    /// The contained values are stored packed in a representation appropriate for their type.
54    /// See [`ArrayValue`] for details on the representation.
55    Array(ArrayValue),
56    /// A [`bool`] value of type [`AlgebraicType::Bool`].
57    Bool(bool),
58    /// An [`i8`] value of type [`AlgebraicType::I8`].
59    I8(i8),
60    /// A [`u8`] value of type [`AlgebraicType::U8`].
61    U8(u8),
62    /// An [`i16`] value of type [`AlgebraicType::I16`].
63    I16(i16),
64    /// A [`u16`] value of type [`AlgebraicType::U16`].
65    U16(u16),
66    /// An [`i32`] value of type [`AlgebraicType::I32`].
67    I32(i32),
68    /// A [`u32`] value of type [`AlgebraicType::U32`].
69    U32(u32),
70    /// An [`i64`] value of type [`AlgebraicType::I64`].
71    I64(i64),
72    /// A [`u64`] value of type [`AlgebraicType::U64`].
73    U64(u64),
74    /// An [`i128`] value of type [`AlgebraicType::I128`].
75    ///
76    /// We pack these to shrink `AlgebraicValue`.
77    I128(Packed<i128>),
78    /// A [`u128`] value of type [`AlgebraicType::U128`].
79    ///
80    /// We pack these to to shrink `AlgebraicValue`.
81    U128(Packed<u128>),
82    /// An [`i256`] value of type [`AlgebraicType::I256`].
83    ///
84    /// We box these up to shrink `AlgebraicValue`.
85    I256(Box<i256>),
86    /// A [`u256`] value of type [`AlgebraicType::U256`].
87    ///
88    /// We pack these to shrink `AlgebraicValue`.
89    U256(Box<u256>),
90    /// A totally ordered [`F32`] value of type [`AlgebraicType::F32`].
91    ///
92    /// All floating point values defined in IEEE-754 are supported.
93    /// However, unlike the primitive [`f32`], a [total order] is established.
94    ///
95    /// [total order]: https://docs.rs/decorum/0.3.1/decorum/#total-ordering
96    F32(F32),
97    /// A totally ordered [`F64`] value of type [`AlgebraicType::F64`].
98    ///
99    /// All floating point values defined in IEEE-754 are supported.
100    /// However, unlike the primitive [`f64`], a [total order] is established.
101    ///
102    /// [total order]: https://docs.rs/decorum/0.3.1/decorum/#total-ordering
103    F64(F64),
104    /// A UTF-8 string value of type [`AlgebraicType::String`].
105    ///
106    /// Uses Rust's standard representation of strings.
107    String(Box<str>),
108
109    /// The maximum value in the total ordering.
110    /// Cannot be serialized and only exists to facilitate range index scans.
111    /// This variant must always be last.
112    Max,
113}
114
115/// Wraps `T` making the outer type packed with alignment 1.
116#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
117#[repr(Rust, packed)]
118pub struct Packed<T>(pub T);
119
120impl<T> From<T> for Packed<T> {
121    fn from(value: T) -> Self {
122        Self(value)
123    }
124}
125
126#[allow(non_snake_case)]
127impl AlgebraicValue {
128    /// Extract the value and replace it with a dummy one that is cheap to make.
129    pub fn take(&mut self) -> Self {
130        mem::replace(self, Self::U8(0))
131    }
132
133    /// Interpret the value as a byte slice or `None` if it isn't a byte slice.
134    #[inline]
135    pub fn as_bytes(&self) -> Option<&[u8]> {
136        match self {
137            Self::Array(ArrayValue::U8(a)) => Some(a),
138            _ => None,
139        }
140    }
141
142    /// The canonical unit value defined as the nullary product value `()`.
143    ///
144    /// The type of `UNIT` is `()`.
145    pub fn unit() -> Self {
146        Self::product([])
147    }
148
149    /// Returns an [`AlgebraicValue`] representing `v: Box<[u8]>`.
150    #[inline]
151    pub const fn Bytes(v: Box<[u8]>) -> Self {
152        Self::Array(ArrayValue::U8(v))
153    }
154
155    /// Converts `self` into a byte string, if applicable.
156    pub fn into_bytes(self) -> Result<Box<[u8]>, Self> {
157        match self {
158            Self::Array(ArrayValue::U8(v)) => Ok(v),
159            _ => Err(self),
160        }
161    }
162
163    /// Converts `self` into an `Option<AlgebraicValue>`, if applicable.
164    pub fn into_option(self) -> Result<Option<Self>, Self> {
165        match self {
166            AlgebraicValue::Sum(sum_value) => match sum_value.tag {
167                0 => Ok(Some(*sum_value.value)),
168                1 => Ok(None),
169                _ => Err(AlgebraicValue::Sum(sum_value)),
170            },
171            _ => Err(self),
172        }
173    }
174
175    /// Returns an [`AlgebraicValue`] for `some: v`.
176    ///
177    /// The `some` variant is assigned the tag `0`.
178    #[inline]
179    pub fn OptionSome(v: Self) -> Self {
180        Self::sum(0, v)
181    }
182
183    /// Returns an [`AlgebraicValue`] for `none`.
184    ///
185    /// The `none` variant is assigned the tag `1`.
186    #[inline]
187    pub fn OptionNone() -> Self {
188        Self::sum(1, Self::unit())
189    }
190
191    /// Converts `self` into `Result<Result<AlgebraicValue, AlgebraicValue>, Self>`, if applicable.
192    pub fn into_result(self) -> Result<Result<Self, Self>, Self> {
193        match self {
194            AlgebraicValue::Sum(sum_value) => match sum_value.tag {
195                0 => Ok(Ok(*sum_value.value)),
196                1 => Ok(Err(*sum_value.value)),
197                _ => Err(AlgebraicValue::Sum(sum_value)),
198            },
199            _ => Err(self),
200        }
201    }
202
203    /// Returns an [`AlgebraicValue`] for ` Ok: v`.
204    ///
205    /// The `Ok` variant is assigned the tag `0`.
206    #[inline]
207    pub fn ResultOk(v: Self) -> Self {
208        Self::sum(0, v)
209    }
210
211    /// Returns an [`AlgebraicValue`] for ` Err: v`.
212    ///
213    /// The `Err` variant is assigned the tag `1`.
214    #[inline]
215    pub fn ResultErr(v: Self) -> Self {
216        Self::sum(1, v)
217    }
218
219    /// Returns an [`AlgebraicValue`] representing a sum value with `tag` and `value`.
220    pub fn sum(tag: u8, value: Self) -> Self {
221        Self::Sum(SumValue::new(tag, value))
222    }
223
224    /// Returns an [`AlgebraicValue`] representing a sum value with `tag` and empty [AlgebraicValue::product], that is
225    /// valid for simple enums without payload.
226    pub fn enum_simple(tag: u8) -> Self {
227        Self::Sum(SumValue::new_simple(tag))
228    }
229
230    /// Returns an [`AlgebraicValue`] representing a product value with the given `elements`.
231    pub fn product(elements: impl Into<ProductValue>) -> Self {
232        Self::Product(elements.into())
233    }
234
235    /// Returns the [`AlgebraicType`] of the product value `x`.
236    pub(crate) fn type_of_product(x: &ProductValue) -> Option<AlgebraicType> {
237        let mut elems = Vec::with_capacity(x.elements.len());
238        for elem in &*x.elements {
239            elems.push(elem.type_of()?.into());
240        }
241        Some(AlgebraicType::product(elems.into_boxed_slice()))
242    }
243
244    /// Infer the [`AlgebraicType`] of an [`AlgebraicValue`].
245    ///
246    /// This function is partial
247    /// as type inference is not possible for `AlgebraicValue` in the case of sums.
248    /// Thus the method only answers for the decidable subset.
249    ///
250    /// # A note on sums
251    ///
252    /// The type of a sum value must be a sum type and *not* a product type.
253    /// Suppose `x.tag` is for the variant `VarName(VarType)`.
254    /// Then `VarType` is *not* the same type as `{ VarName(VarType) | r }`
255    /// where `r` represents a polymorphic variants component.
256    ///
257    /// To assign this a correct type we either have to store the type with the value
258    /// r alternatively, we must have polymorphic variants (see row polymorphism)
259    /// *and* derive the correct variant name.
260    pub fn type_of(&self) -> Option<AlgebraicType> {
261        match self {
262            Self::Sum(_) => None,
263            Self::Product(x) => Self::type_of_product(x),
264            Self::Array(x) => x.type_of().map(Into::into),
265            Self::Bool(_) => Some(AlgebraicType::Bool),
266            Self::I8(_) => Some(AlgebraicType::I8),
267            Self::U8(_) => Some(AlgebraicType::U8),
268            Self::I16(_) => Some(AlgebraicType::I16),
269            Self::U16(_) => Some(AlgebraicType::U16),
270            Self::I32(_) => Some(AlgebraicType::I32),
271            Self::U32(_) => Some(AlgebraicType::U32),
272            Self::I64(_) => Some(AlgebraicType::I64),
273            Self::U64(_) => Some(AlgebraicType::U64),
274            Self::I128(_) => Some(AlgebraicType::I128),
275            Self::U128(_) => Some(AlgebraicType::U128),
276            Self::I256(_) => Some(AlgebraicType::I256),
277            Self::U256(_) => Some(AlgebraicType::U256),
278            Self::F32(_) => Some(AlgebraicType::F32),
279            Self::F64(_) => Some(AlgebraicType::F64),
280            Self::String(_) => Some(AlgebraicType::String),
281            AlgebraicValue::Min | AlgebraicValue::Max => None,
282        }
283    }
284
285    /// Returns whether this value represents a numeric zero.
286    ///
287    /// Can only be true where the type is numeric.
288    pub fn is_numeric_zero(&self) -> bool {
289        match *self {
290            Self::I8(x) => x == 0,
291            Self::U8(x) => x == 0,
292            Self::I16(x) => x == 0,
293            Self::U16(x) => x == 0,
294            Self::I32(x) => x == 0,
295            Self::U32(x) => x == 0,
296            Self::I64(x) => x == 0,
297            Self::U64(x) => x == 0,
298            Self::I128(x) => x.0 == 0,
299            Self::U128(x) => x.0 == 0,
300            Self::I256(ref x) => **x == i256::ZERO,
301            Self::U256(ref x) => **x == u256::ZERO,
302            Self::F32(x) => x == 0.0,
303            Self::F64(x) => x == 0.0,
304            _ => false,
305        }
306    }
307
308    /// Constructs an `AlgebraicValue` from an `i128` according to the given `AlgebraicType`.
309    ///
310    /// Returns `None` if the type is not a supported integer type.
311    pub fn from_i128(ty: &AlgebraicType, value: i128) -> Option<Self> {
312        let val = match ty {
313            AlgebraicType::I8 => (value as i8).into(),
314            AlgebraicType::I16 => (value as i16).into(),
315            AlgebraicType::I32 => (value as i32).into(),
316            AlgebraicType::I64 => (value as i64).into(),
317            AlgebraicType::I128 => value.into(),
318            AlgebraicType::I256 => i256::from(value).into(),
319
320            AlgebraicType::U8 => (value as u8).into(),
321            AlgebraicType::U16 => (value as u16).into(),
322            AlgebraicType::U32 => (value as u32).into(),
323            AlgebraicType::U64 => (value as u64).into(),
324            AlgebraicType::U128 => (value as u128).into(),
325            AlgebraicType::U256 => (u256::from(value as u128)).into(),
326
327            _ => return None,
328        };
329        Some(val)
330    }
331}
332
333impl<T: Into<AlgebraicValue>> From<Option<T>> for AlgebraicValue {
334    fn from(value: Option<T>) -> Self {
335        match value {
336            None => AlgebraicValue::OptionNone(),
337            Some(x) => AlgebraicValue::OptionSome(x.into()),
338        }
339    }
340}
341
342/// An AlgebraicValue can be interpreted as a range containing a only the value itself.
343/// This is useful for BTrees where single key scans are still viewed range scans.
344impl RangeBounds<AlgebraicValue> for &AlgebraicValue {
345    fn start_bound(&self) -> Bound<&AlgebraicValue> {
346        Bound::Included(self)
347    }
348    fn end_bound(&self) -> Bound<&AlgebraicValue> {
349        Bound::Included(self)
350    }
351}
352
353impl RangeBounds<AlgebraicValue> for AlgebraicValue {
354    fn start_bound(&self) -> Bound<&AlgebraicValue> {
355        Bound::Included(self)
356    }
357    fn end_bound(&self) -> Bound<&AlgebraicValue> {
358        Bound::Included(self)
359    }
360}
361
362#[cfg(test)]
363mod tests {
364    use crate::satn::Satn;
365    use crate::{AlgebraicType, AlgebraicValue, ArrayValue, Typespace, ValueWithType, WithTypespace};
366
367    fn in_space<'a, T: crate::Value>(ts: &'a Typespace, ty: &'a T::Type, val: &'a T) -> ValueWithType<'a, T> {
368        WithTypespace::new(ts, ty).with_value(val)
369    }
370
371    #[test]
372    fn unit() {
373        let val = AlgebraicValue::unit();
374        let unit = AlgebraicType::unit();
375        let typespace = Typespace::new(vec![]);
376        assert_eq!(in_space(&typespace, &unit, &val).to_satn(), "()");
377    }
378
379    #[test]
380    fn product_value() {
381        let product_type = AlgebraicType::product([("foo", AlgebraicType::I32)]);
382        let typespace = Typespace::new(vec![]);
383        let product_value = AlgebraicValue::product([AlgebraicValue::I32(42)]);
384        assert_eq!(
385            "(foo = 42)",
386            in_space(&typespace, &product_type, &product_value).to_satn(),
387        );
388    }
389
390    #[test]
391    fn option_some() {
392        let option = AlgebraicType::option(AlgebraicType::never());
393        let sum_value = AlgebraicValue::OptionNone();
394        let typespace = Typespace::new(vec![]);
395        assert_eq!("(none = ())", in_space(&typespace, &option, &sum_value).to_satn(),);
396    }
397
398    #[test]
399    fn result() {
400        let result = AlgebraicType::result(AlgebraicType::U8, AlgebraicType::String);
401        let ok = AlgebraicValue::ResultOk(AlgebraicValue::U8(42));
402        let typespace = Typespace::new(vec![]);
403        assert_eq!("(ok = 42)", in_space(&typespace, &result, &ok).to_satn(),);
404
405        let err = AlgebraicValue::ResultErr(AlgebraicValue::String("error".into()));
406        assert_eq!("(err = \"error\")", in_space(&typespace, &result, &err).to_satn(),);
407    }
408
409    #[test]
410    fn primitive() {
411        let u8 = AlgebraicType::U8;
412        let value = AlgebraicValue::U8(255);
413        let typespace = Typespace::new(vec![]);
414        assert_eq!(in_space(&typespace, &u8, &value).to_satn(), "255");
415    }
416
417    #[test]
418    fn array() {
419        let array = AlgebraicType::array(AlgebraicType::U8);
420        let value = AlgebraicValue::Array(ArrayValue::Sum([].into()));
421        let typespace = Typespace::new(vec![]);
422        assert_eq!(in_space(&typespace, &array, &value).to_satn(), "[]");
423    }
424
425    #[test]
426    fn array_of_values() {
427        let array = AlgebraicType::array(AlgebraicType::U8);
428        let value = AlgebraicValue::Array([3u8].into());
429        let typespace = Typespace::new(vec![]);
430        assert_eq!(in_space(&typespace, &array, &value).to_satn(), "0x03");
431    }
432}
spacetimedb_sats/algebraic_value.rs

spacetimedb_sats/
algebraic_value.rs
