harmos_domain/model/storage/query/
scalar.rs

1/* ***
2 *
3 * Harmos
4 *
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * ***
8 */
9
10/* === Modules === */
11
12/* === Re-Exports === */
13
14/* === Imports === */
15
16// Standard Library Imports
17use std::cmp::Ordering;
18use std::num::NonZeroU128;
19
20// Third Party Imports
21use serde::{Deserialize, Serialize};
22
23// Local Imports
24use crate::MessageError;
25use crate::model::storage::codec::{
26    Flag, Float, Nested, Percent, Signed as SignedInt, Text, Unsigned, Wide, WideNonZero, WideSigned, coded, product, variants,
27};
28use crate::{Aggregate, Error, MemorySize, Result};
29
30/* === Constants === */
31
32/* === Macros === */
33
34/* === Type Aliases === */
35
36/* === Structs === */
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
39#[serde(deny_unknown_fields)]
40pub struct ExactNumber {
41    pub negative: bool,
42    pub numerator: u128,
43    pub denominator: NonZeroU128,
44}
45
46/* === Enums === */
47
48#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
49pub enum ScalarValue {
50    Missing,
51    Null,
52    Bool(bool),
53    Signed(i64),
54    Unsigned(u64),
55    Float(f64),
56    Text(String),
57    Datetime(i128),
58    Exact(ExactNumber),
59}
60#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
61pub enum ScalarKind {
62    Bool,
63    Signed,
64    Unsigned,
65    Float,
66    Text,
67    Datetime,
68    Exact,
69}
70// What a storage group-by reduces a column to. `Len` and `Last` are row
71// selections rather than statistics: `Len` counts rows including missing and
72// null values, and `Last` keeps the value captured latest, so they stay here.
73// Every statistic is a member of the contract `Aggregate` vocabulary.
74#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
75#[serde(rename_all = "snake_case")]
76pub enum Agg {
77    Len,
78    Last,
79    Of(Aggregate),
80}
81
82/* === Traits === */
83
84/* === Implementations === */
85
86impl ExactNumber {
87    pub fn new(negative: bool, numerator: u128, denominator: NonZeroU128) -> Self {
88        let factor = gcd(numerator, denominator.get());
89        Self {
90            negative: negative && numerator != 0,
91            numerator: numerator / factor,
92            denominator: NonZeroU128::new(denominator.get() / factor).unwrap(),
93        }
94    }
95
96    pub fn checked_add(self, other: Self) -> Result<Self> {
97        let common = gcd(self.denominator.get(), other.denominator.get());
98        let a = other.denominator.get() / common;
99        let b = self.denominator.get() / common;
100        let left = self.numerator.checked_mul(a).ok_or(invalid("exact arithmetic overflow"))?;
101        let right = other.numerator.checked_mul(b).ok_or(invalid("exact arithmetic overflow"))?;
102        let (negative, numerator) = if self.negative == other.negative {
103            (self.negative, left.checked_add(right).ok_or(invalid("exact arithmetic overflow"))?)
104        } else if left >= right {
105            (self.negative, left - right)
106        } else {
107            (other.negative, right - left)
108        };
109        let denominator = self.denominator.get().checked_mul(a).ok_or(invalid("exact arithmetic overflow"))?;
110        Ok(Self::new(negative, numerator, NonZeroU128::new(denominator).unwrap()))
111    }
112
113    pub fn divide(self, count: u128) -> Result<Self> {
114        let factor = gcd(self.numerator, count);
115        let denominator = self.denominator.get().checked_mul(count / factor).ok_or(invalid("exact arithmetic overflow"))?;
116        Ok(Self::new(self.negative, self.numerator / factor, NonZeroU128::new(denominator).unwrap()))
117    }
118
119    fn compare(self, other: Self) -> Ordering {
120        match (self.negative, other.negative) {
121            (true, false) => Ordering::Less,
122            (false, true) => Ordering::Greater,
123            _ => {
124                let order = ratio_cmp(self.numerator, self.denominator.get(), other.numerator, other.denominator.get());
125                if self.negative { order.reverse() } else { order }
126            }
127        }
128    }
129}
130impl ScalarValue {
131    pub fn check(&self) -> Result<()> {
132        if matches!(self, Self::Float(value) if !value.is_finite()) {
133            return Err(invalid("nonfinite scalar"));
134        }
135        if let Self::Exact(value) = self
136            && ExactNumber::new(value.negative, value.numerator, value.denominator) != *value
137        {
138            return Err(invalid("noncanonical exact number"));
139        }
140        Ok(())
141    }
142
143    pub fn kind(&self) -> Option<ScalarKind> {
144        Some(match self {
145            Self::Missing | Self::Null => return None,
146            Self::Bool(_) => ScalarKind::Bool,
147            Self::Signed(_) => ScalarKind::Signed,
148            Self::Unsigned(_) => ScalarKind::Unsigned,
149            Self::Float(_) => ScalarKind::Float,
150            Self::Text(_) => ScalarKind::Text,
151            Self::Datetime(_) => ScalarKind::Datetime,
152            Self::Exact(_) => ScalarKind::Exact,
153        })
154    }
155
156    pub fn compare(&self, other: &Self) -> Result<Ordering> {
157        self.check()?;
158        other.check()?;
159        if matches!(self, Self::Missing) {
160            return Ok(if matches!(other, Self::Missing) { Ordering::Equal } else { Ordering::Less });
161        }
162        if matches!(other, Self::Missing) {
163            return Ok(Ordering::Greater);
164        }
165        if matches!(self, Self::Null) {
166            return Ok(if matches!(other, Self::Null) { Ordering::Equal } else { Ordering::Less });
167        }
168        if matches!(other, Self::Null) {
169            return Ok(Ordering::Greater);
170        }
171        Ok(match (self, other) {
172            (Self::Bool(a), Self::Bool(b)) => a.cmp(b),
173            (Self::Signed(a), Self::Signed(b)) => a.cmp(b),
174            (Self::Unsigned(a), Self::Unsigned(b)) => a.cmp(b),
175            (Self::Float(a), Self::Float(b)) => a.partial_cmp(b).unwrap(),
176            (Self::Text(a), Self::Text(b)) => a.cmp(b),
177            (Self::Datetime(a), Self::Datetime(b)) => a.cmp(b),
178            (a, b) if exact(a).is_some() && exact(b).is_some() => exact(a).unwrap().compare(exact(b).unwrap()),
179            _ => return Err(invalid("incompatible scalar comparison")),
180        })
181    }
182}
183impl MemorySize for ScalarValue {
184    fn memory_size(&self) -> usize {
185        std::mem::size_of::<Self>().saturating_add(match self {
186            Self::Text(text) => text.capacity(),
187            _ => 0,
188        })
189    }
190}
191
192impl Agg {
193    // Statistics answered from the ordered values, which hold scratch per
194    // accumulator; every other reduction runs in constant space.
195    pub fn retains_values(&self) -> bool {
196        matches!(self, Self::Of(kind) if !kind.mergeable())
197    }
198}
199
200impl From<Aggregate> for Agg {
201    fn from(kind: Aggregate) -> Self {
202        Self::Of(kind)
203    }
204}
205
206impl MemorySize for Agg {
207    fn memory_size(&self) -> usize {
208        std::mem::size_of::<Self>()
209    }
210}
211
212impl MemorySize for ExactNumber {
213    fn memory_size(&self) -> usize {
214        std::mem::size_of::<Self>()
215    }
216}
217
218// Only The Reduced Form Of An Exact Fraction Is Accepted On Decode.
219product!(
220    ExactNumber {
221        negative: Flag => 1,
222        numerator: Wide => 2,
223        denominator: WideNonZero => 3,
224    },
225    check = |value: &ExactNumber| {
226        if ExactNumber::new(value.negative, value.numerator, value.denominator) == *value {
227            Ok(())
228        } else {
229            Err(MessageError::borrowed("exact number is not reduced"))
230        }
231    }
232);
233
234coded!(ScalarKind { Bool, Signed, Unsigned, Float, Text, Datetime, Exact });
235variants!(Agg {
236    0, 1, "len": Self::Len => {} => Self::Len;
237    1, 2, "last": Self::Last => {} => Self::Last;
238    2, 3, "count": Self::Of(Aggregate::Count) => {} => Self::Of(Aggregate::Count);
239    3, 4, "sum": Self::Of(Aggregate::Sum) => {} => Self::Of(Aggregate::Sum);
240    4, 5, "mean": Self::Of(Aggregate::Mean) => {} => Self::Of(Aggregate::Mean);
241    5, 6, "median": Self::Of(Aggregate::Median) => {} => Self::Of(Aggregate::Median);
242    6, 7, "min": Self::Of(Aggregate::Min) => {} => Self::Of(Aggregate::Min);
243    7, 8, "max": Self::Of(Aggregate::Max) => {} => Self::Of(Aggregate::Max);
244    8, 9, "rms": Self::Of(Aggregate::Rms) => {} => Self::Of(Aggregate::Rms);
245    9, 10, "std": Self::Of(Aggregate::Std) => {} => Self::Of(Aggregate::Std);
246    10, 11, "percentile": Self::Of(Aggregate::Percentile(rank)) => { rank: Percent => 1 } => Self::Of(Aggregate::Percentile(rank));
247});
248
249variants!(ScalarValue {
250    0, 1, "missing": Self::Missing => {} => Self::Missing;
251    1, 2, "null": Self::Null => {} => Self::Null;
252    2, 3, "bool": Self::Bool(value) => { value: Flag => 1 } => Self::Bool(value);
253    3, 4, "signed": Self::Signed(value) => { value: SignedInt => 1 } => Self::Signed(value);
254    4, 5, "unsigned": Self::Unsigned(value) => { value: Unsigned => 1 } => Self::Unsigned(value);
255    5, 6, "float": Self::Float(value) => { value: Float => 1 } => Self::Float(value);
256    6, 7, "text": Self::Text(value) => { value: Text => 1 } => Self::Text(value);
257    7, 8, "datetime": Self::Datetime(value) => { value: WideSigned => 1 } => Self::Datetime(value);
258    8, 9, "exact": Self::Exact(value) => { value: Nested<ExactNumber> => 1 } => Self::Exact(value);
259});
260
261/* === Public Functions === */
262
263/* === Private Functions === */
264
265fn invalid(reason: &'static str) -> Error {
266    Error::InvalidInput { field: "storage reduce", reason }
267}
268fn gcd(mut a: u128, mut b: u128) -> u128 {
269    while b != 0 {
270        (a, b) = (b, a % b);
271    }
272    a
273}
274pub fn exact(value: &ScalarValue) -> Option<ExactNumber> {
275    Some(match value {
276        ScalarValue::Signed(value) => ExactNumber::new(*value < 0, u128::from(value.unsigned_abs()), NonZeroU128::MIN),
277        ScalarValue::Unsigned(value) => ExactNumber::new(false, u128::from(*value), NonZeroU128::MIN),
278        ScalarValue::Exact(value) => *value,
279        _ => return None,
280    })
281}
282// Continued-Fraction Comparison Avoids Cross-Product Overflow.
283pub fn ratio_cmp(mut a: u128, mut b: u128, mut c: u128, mut d: u128) -> Ordering {
284    let mut reverse = false;
285    loop {
286        let order = (a / b).cmp(&(c / d));
287        if !order.is_eq() {
288            return if reverse { order.reverse() } else { order };
289        }
290        let (r, s) = (a % b, c % d);
291        if r == 0 || s == 0 {
292            let order = r.cmp(&s);
293            return if reverse { order.reverse() } else { order };
294        }
295        (a, b, c, d) = (b, r, d, s);
296        reverse = !reverse;
297    }
298}
299
300/* === Tests === */
harmos_domain/model/storage/query/scalar.rs

harmos_domain/model/storage/query/
scalar.rs
