spacetimedb_sats/
algebraic_value.rs

1pub mod de;
2pub mod ser;
3
4use crate::{impl_deserialize, AlgebraicType, ArrayValue, Deserialize, 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)`][AlgebraicType::Array].
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_deserialize!([T: Deserialize<'de>] Packed<T>, de => <_>::deserialize(de).map(Packed));
121
122impl<T> From<T> for Packed<T> {
123    fn from(value: T) -> Self {
124        Self(value)
125    }
126}
127
128#[allow(non_snake_case)]
129impl AlgebraicValue {
130    /// Extract the value and replace it with a dummy one that is cheap to make.
131    pub fn take(&mut self) -> Self {
132        mem::replace(self, Self::U8(0))
133    }
134
135    /// Interpret the value as a byte slice or `None` if it isn't a byte slice.
136    #[inline]
137    pub fn as_bytes(&self) -> Option<&[u8]> {
138        match self {
139            Self::Array(ArrayValue::U8(a)) => Some(a),
140            _ => None,
141        }
142    }
143
144    /// The canonical unit value defined as the nullary product value `()`.
145    ///
146    /// The type of `UNIT` is `()`.
147    pub fn unit() -> Self {
148        Self::product([])
149    }
150
151    /// Returns an [`AlgebraicValue`] representing `v: Box<[u8]>`.
152    #[inline]
153    pub const fn Bytes(v: Box<[u8]>) -> Self {
154        Self::Array(ArrayValue::U8(v))
155    }
156
157    /// Converts `self` into a byte string, if applicable.
158    pub fn into_bytes(self) -> Result<Box<[u8]>, Self> {
159        match self {
160            Self::Array(ArrayValue::U8(v)) => Ok(v),
161            _ => Err(self),
162        }
163    }
164
165    /// Converts `self` into an `Option<AlgebraicValue>`, if applicable.
166    pub fn into_option(self) -> Result<Option<Self>, Self> {
167        match self {
168            AlgebraicValue::Sum(sum_value) => match sum_value.tag {
169                0 => Ok(Some(*sum_value.value)),
170                1 => Ok(None),
171                _ => Err(AlgebraicValue::Sum(sum_value)),
172            },
173            _ => Err(self),
174        }
175    }
176
177    /// Returns an [`AlgebraicValue`] for `some: v`.
178    ///
179    /// The `some` variant is assigned the tag `0`.
180    #[inline]
181    pub fn OptionSome(v: Self) -> Self {
182        Self::sum(0, v)
183    }
184
185    /// Returns an [`AlgebraicValue`] for `none`.
186    ///
187    /// The `none` variant is assigned the tag `1`.
188    #[inline]
189    pub fn OptionNone() -> Self {
190        Self::sum(1, Self::unit())
191    }
192
193    /// Converts `self` into `Result<Result<AlgebraicValue, AlgebraicValue>, Self>`, if applicable.
194    pub fn into_result(self) -> Result<Result<Self, Self>, Self> {
195        match self {
196            AlgebraicValue::Sum(sum_value) => match sum_value.tag {
197                0 => Ok(Ok(*sum_value.value)),
198                1 => Ok(Err(*sum_value.value)),
199                _ => Err(AlgebraicValue::Sum(sum_value)),
200            },
201            _ => Err(self),
202        }
203    }
204
205    /// Returns an [`AlgebraicValue`] for ` Ok: v`.
206    ///
207    /// The `Ok` variant is assigned the tag `0`.
208    #[inline]
209    pub fn ResultOk(v: Self) -> Self {
210        Self::sum(0, v)
211    }
212
213    /// Returns an [`AlgebraicValue`] for ` Err: v`.
214    ///
215    /// The `Err` variant is assigned the tag `1`.
216    #[inline]
217    pub fn ResultErr(v: Self) -> Self {
218        Self::sum(1, v)
219    }
220
221    /// Returns an [`AlgebraicValue`] representing a sum value with `tag` and `value`.
222    pub fn sum(tag: u8, value: Self) -> Self {
223        Self::Sum(SumValue::new(tag, value))
224    }
225
226    /// Returns an [`AlgebraicValue`] representing a sum value with `tag` and empty [AlgebraicValue::product], that is
227    /// valid for simple enums without payload.
228    pub fn enum_simple(tag: u8) -> Self {
229        Self::Sum(SumValue::new_simple(tag))
230    }
231
232    /// Returns an [`AlgebraicValue`] representing a product value with the given `elements`.
233    pub fn product(elements: impl Into<ProductValue>) -> Self {
234        Self::Product(elements.into())
235    }
236
237    /// Returns the [`AlgebraicType`] of the product value `x`.
238    pub(crate) fn type_of_product(x: &ProductValue) -> Option<AlgebraicType> {
239        let mut elems = Vec::with_capacity(x.elements.len());
240        for elem in &*x.elements {
241            elems.push(elem.type_of()?.into());
242        }
243        Some(AlgebraicType::product(elems.into_boxed_slice()))
244    }
245
246    /// Infer the [`AlgebraicType`] of an [`AlgebraicValue`].
247    ///
248    /// This function is partial
249    /// as type inference is not possible for `AlgebraicValue` in the case of sums.
250    /// Thus the method only answers for the decidable subset.
251    ///
252    /// # A note on sums
253    ///
254    /// The type of a sum value must be a sum type and *not* a product type.
255    /// Suppose `x.tag` is for the variant `VarName(VarType)`.
256    /// Then `VarType` is *not* the same type as `{ VarName(VarType) | r }`
257    /// where `r` represents a polymorphic variants component.
258    ///
259    /// To assign this a correct type we either have to store the type with the value
260    /// r alternatively, we must have polymorphic variants (see row polymorphism)
261    /// *and* derive the correct variant name.
262    pub fn type_of(&self) -> Option<AlgebraicType> {
263        match self {
264            Self::Sum(_) => None,
265            Self::Product(x) => Self::type_of_product(x),
266            Self::Array(x) => x.type_of().map(Into::into),
267            Self::Bool(_) => Some(AlgebraicType::Bool),
268            Self::I8(_) => Some(AlgebraicType::I8),
269            Self::U8(_) => Some(AlgebraicType::U8),
270            Self::I16(_) => Some(AlgebraicType::I16),
271            Self::U16(_) => Some(AlgebraicType::U16),
272            Self::I32(_) => Some(AlgebraicType::I32),
273            Self::U32(_) => Some(AlgebraicType::U32),
274            Self::I64(_) => Some(AlgebraicType::I64),
275            Self::U64(_) => Some(AlgebraicType::U64),
276            Self::I128(_) => Some(AlgebraicType::I128),
277            Self::U128(_) => Some(AlgebraicType::U128),
278            Self::I256(_) => Some(AlgebraicType::I256),
279            Self::U256(_) => Some(AlgebraicType::U256),
280            Self::F32(_) => Some(AlgebraicType::F32),
281            Self::F64(_) => Some(AlgebraicType::F64),
282            Self::String(_) => Some(AlgebraicType::String),
283            AlgebraicValue::Min | AlgebraicValue::Max => None,
284        }
285    }
286
287    /// Returns whether this value represents a numeric zero.
288    ///
289    /// Can only be true where the type is numeric.
290    pub fn is_numeric_zero(&self) -> bool {
291        match *self {
292            Self::I8(x) => x == 0,
293            Self::U8(x) => x == 0,
294            Self::I16(x) => x == 0,
295            Self::U16(x) => x == 0,
296            Self::I32(x) => x == 0,
297            Self::U32(x) => x == 0,
298            Self::I64(x) => x == 0,
299            Self::U64(x) => x == 0,
300            Self::I128(x) => x.0 == 0,
301            Self::U128(x) => x.0 == 0,
302            Self::I256(ref x) => **x == i256::ZERO,
303            Self::U256(ref x) => **x == u256::ZERO,
304            Self::F32(x) => x == 0.0,
305            Self::F64(x) => x == 0.0,
306            _ => false,
307        }
308    }
309
310    /// Constructs an `AlgebraicValue` from an `i128` according to the given `AlgebraicType`.
311    ///
312    /// Returns `None` if the type is not a supported integer type.
313    pub fn from_i128(ty: &AlgebraicType, value: i128) -> Option<Self> {
314        let val = match ty {
315            AlgebraicType::I8 => (value as i8).into(),
316            AlgebraicType::I16 => (value as i16).into(),
317            AlgebraicType::I32 => (value as i32).into(),
318            AlgebraicType::I64 => (value as i64).into(),
319            AlgebraicType::I128 => value.into(),
320            AlgebraicType::I256 => i256::from(value).into(),
321
322            AlgebraicType::U8 => (value as u8).into(),
323            AlgebraicType::U16 => (value as u16).into(),
324            AlgebraicType::U32 => (value as u32).into(),
325            AlgebraicType::U64 => (value as u64).into(),
326            AlgebraicType::U128 => (value as u128).into(),
327            AlgebraicType::U256 => (u256::from(value as u128)).into(),
328
329            _ => return None,
330        };
331        Some(val)
332    }
333}
334
335impl<T: Into<AlgebraicValue>> From<Option<T>> for AlgebraicValue {
336    fn from(value: Option<T>) -> Self {
337        match value {
338            None => AlgebraicValue::OptionNone(),
339            Some(x) => AlgebraicValue::OptionSome(x.into()),
340        }
341    }
342}
343
344/// An AlgebraicValue can be interpreted as a range containing a only the value itself.
345/// This is useful for BTrees where single key scans are still viewed range scans.
346impl RangeBounds<AlgebraicValue> for &AlgebraicValue {
347    fn start_bound(&self) -> Bound<&AlgebraicValue> {
348        Bound::Included(self)
349    }
350    fn end_bound(&self) -> Bound<&AlgebraicValue> {
351        Bound::Included(self)
352    }
353}
354
355impl RangeBounds<AlgebraicValue> for AlgebraicValue {
356    fn start_bound(&self) -> Bound<&AlgebraicValue> {
357        Bound::Included(self)
358    }
359    fn end_bound(&self) -> Bound<&AlgebraicValue> {
360        Bound::Included(self)
361    }
362}
363
364#[cfg(test)]
365mod tests {
366    use crate::satn::Satn;
367    use crate::{AlgebraicType, AlgebraicValue, ArrayValue, Typespace, ValueWithType, WithTypespace};
368
369    fn in_space<'a, T: crate::Value>(ts: &'a Typespace, ty: &'a T::Type, val: &'a T) -> ValueWithType<'a, T> {
370        WithTypespace::new(ts, ty).with_value(val)
371    }
372
373    #[test]
374    fn unit() {
375        let val = AlgebraicValue::unit();
376        let unit = AlgebraicType::unit();
377        let typespace = Typespace::new(vec![]);
378        assert_eq!(in_space(&typespace, &unit, &val).to_satn(), "()");
379    }
380
381    #[test]
382    fn product_value() {
383        let product_type = AlgebraicType::product([("foo", AlgebraicType::I32)]);
384        let typespace = Typespace::new(vec![]);
385        let product_value = AlgebraicValue::product([AlgebraicValue::I32(42)]);
386        assert_eq!(
387            "(foo = 42)",
388            in_space(&typespace, &product_type, &product_value).to_satn(),
389        );
390    }
391
392    #[test]
393    fn option_some() {
394        let option = AlgebraicType::option(AlgebraicType::never());
395        let sum_value = AlgebraicValue::OptionNone();
396        let typespace = Typespace::new(vec![]);
397        assert_eq!("(none = ())", in_space(&typespace, &option, &sum_value).to_satn(),);
398    }
399
400    #[test]
401    fn result() {
402        let result = AlgebraicType::result(AlgebraicType::U8, AlgebraicType::String);
403        let ok = AlgebraicValue::ResultOk(AlgebraicValue::U8(42));
404        let typespace = Typespace::new(vec![]);
405        assert_eq!("(ok = 42)", in_space(&typespace, &result, &ok).to_satn(),);
406
407        let err = AlgebraicValue::ResultErr(AlgebraicValue::String("error".into()));
408        assert_eq!("(err = \"error\")", in_space(&typespace, &result, &err).to_satn(),);
409    }
410
411    #[test]
412    fn primitive() {
413        let u8 = AlgebraicType::U8;
414        let value = AlgebraicValue::U8(255);
415        let typespace = Typespace::new(vec![]);
416        assert_eq!(in_space(&typespace, &u8, &value).to_satn(), "255");
417    }
418
419    #[test]
420    fn array() {
421        let array = AlgebraicType::array(AlgebraicType::U8);
422        let value = AlgebraicValue::Array(ArrayValue::Sum([].into()));
423        let typespace = Typespace::new(vec![]);
424        assert_eq!(in_space(&typespace, &array, &value).to_satn(), "[]");
425    }
426
427    #[test]
428    fn array_of_values() {
429        let array = AlgebraicType::array(AlgebraicType::U8);
430        let value = AlgebraicValue::Array([3u8].into());
431        let typespace = Typespace::new(vec![]);
432        assert_eq!(in_space(&typespace, &array, &value).to_satn(), "0x03");
433    }
434}
spacetimedb_sats/algebraic_value.rs

spacetimedb_sats/
algebraic_value.rs
