1use nodedb_types::Value;
34use rust_decimal::Decimal;
35use rust_decimal::prelude::ToPrimitive;
36
37use crate::expr::EvalError;
38use crate::numeric_cmp::{Numeric, parse_numeric_str};
39
40#[derive(Debug, Clone, Default, PartialEq)]
42pub struct ExactSum {
43 int: i128,
45 frac: Decimal,
47 has_decimal: bool,
49 exact_overflow: bool,
51 float: f64,
53 comp: f64,
56 has_float: bool,
58 count: u64,
60}
61
62impl ExactSum {
63 pub fn new() -> Self {
64 Self::default()
65 }
66
67 pub fn count(&self) -> u64 {
69 self.count
70 }
71
72 pub fn add_i64(&mut self, v: i64) {
74 self.add_int(i128::from(v));
75 }
76
77 pub fn add_u64(&mut self, v: u64) {
79 self.add_int(i128::from(v));
80 }
81
82 pub fn add_f64(&mut self, v: f64) {
84 self.float_add(v);
85 self.has_float = true;
86 self.count += 1;
87 }
88
89 pub fn add_value(&mut self, v: &Value) -> bool {
92 match v {
93 Value::Integer(i) => self.add_i64(*i),
94 Value::Float(f) => self.add_f64(*f),
95 Value::Decimal(d) => self.add_decimal(*d),
96 _ => return false,
97 }
98 true
99 }
100
101 pub fn add_decimal(&mut self, d: Decimal) {
104 if d.fract().is_zero()
105 && let Some(i) = d.to_i128()
106 {
107 self.add_int(i);
108 return;
109 }
110 match self.frac.checked_add(d) {
111 Some(total) => self.frac = total,
112 None => self.exact_overflow = true,
113 }
114 self.has_decimal = true;
115 self.count += 1;
116 }
117
118 pub fn merge(&mut self, other: &ExactSum) {
120 match self.int.checked_add(other.int) {
121 Some(total) => self.int = total,
122 None => self.exact_overflow = true,
123 }
124 match self.frac.checked_add(other.frac) {
125 Some(total) => self.frac = total,
126 None => self.exact_overflow = true,
127 }
128 self.exact_overflow |= other.exact_overflow;
129 self.has_decimal |= other.has_decimal;
130 self.float_add(other.float);
131 if self.float.is_finite() {
132 self.comp += other.comp;
133 }
134 self.has_float |= other.has_float;
135 self.count += other.count;
136 }
137
138 pub fn sum(&self) -> Result<Value, EvalError> {
140 if self.count == 0 {
141 return Ok(Value::Null);
142 }
143 if self.exact_overflow {
144 return Err(EvalError::NumericOverflow { function: "sum" });
145 }
146 if self.has_float {
147 return Ok(Value::Float(self.sum_f64()));
148 }
149 if self.has_decimal {
150 return self
151 .exact_decimal_total()
152 .map(Value::Decimal)
153 .ok_or(EvalError::NumericOverflow { function: "sum" });
154 }
155 if let Ok(i) = i64::try_from(self.int) {
156 return Ok(Value::Integer(i));
157 }
158 Decimal::try_from_i128_with_scale(self.int, 0)
159 .map(Value::Decimal)
160 .map_err(|_| EvalError::NumericOverflow { function: "sum" })
161 }
162
163 pub fn sum_f64(&self) -> f64 {
168 if !self.float.is_finite() {
169 return self.float;
170 }
171 self.int as f64 + self.frac.as_f64() + (self.float + self.comp)
172 }
173
174 fn exact_decimal_total(&self) -> Option<Decimal> {
177 Decimal::try_from_i128_with_scale(self.int, 0)
178 .ok()?
179 .checked_add(self.frac)
180 }
181
182 pub fn avg(&self) -> Result<Value, EvalError> {
184 match self.avg_f64()? {
185 Some(avg) => Ok(Value::Float(avg)),
186 None => Ok(Value::Null),
187 }
188 }
189
190 pub fn avg_f64(&self) -> Result<Option<f64>, EvalError> {
192 if self.count == 0 {
193 return Ok(None);
194 }
195 if self.exact_overflow {
196 return Err(EvalError::NumericOverflow { function: "avg" });
197 }
198 let n = i128::from(self.count);
199 let avg = if self.has_float {
200 self.sum_f64() / self.count as f64
201 } else if self.has_decimal {
202 let total = self
205 .exact_decimal_total()
206 .ok_or(EvalError::NumericOverflow { function: "avg" })?;
207 total
208 .checked_div(Decimal::from(self.count))
209 .and_then(|avg| avg.to_f64())
210 .ok_or(EvalError::NumericOverflow { function: "avg" })?
211 } else {
212 (self.int / n) as f64 + (self.int % n) as f64 / self.count as f64
215 };
216 Ok(Some(avg))
217 }
218
219 fn add_int(&mut self, v: i128) {
220 match self.int.checked_add(v) {
221 Some(total) => self.int = total,
222 None => self.exact_overflow = true,
223 }
224 self.count += 1;
225 }
226
227 fn float_add(&mut self, v: f64) {
231 let t = self.float + v;
232 if t.is_finite() {
233 if self.float.abs() >= v.abs() {
234 self.comp += (self.float - t) + v;
235 } else {
236 self.comp += (v - t) + self.float;
237 }
238 }
239 self.float = t;
240 }
241}
242
243pub fn sum_input(v: &Value) -> Option<Value> {
247 match v {
248 Value::Integer(_) | Value::Float(_) | Value::Decimal(_) => Some(v.clone()),
249 Value::String(s) => numeric_text(s),
250 _ => None,
251 }
252}
253
254pub fn numeric_text(s: &str) -> Option<Value> {
259 parse_numeric_str(s).map(numeric_to_value)
260}
261
262pub(crate) fn numeric_to_value(n: Numeric) -> Value {
266 match n {
267 Numeric::Int(i) => match i64::try_from(i) {
268 Ok(small) => Value::Integer(small),
269 Err(_) => Decimal::try_from_i128_with_scale(i, 0)
270 .map(Value::Decimal)
271 .unwrap_or(Value::Float(i as f64)),
272 },
273 Numeric::Decimal(d) => Value::Decimal(d),
274 Numeric::Float(f) => Value::Float(f),
275 }
276}
277
278const MSGPACK_FIELDS: usize = 9;
283
284impl zerompk::ToMessagePack for ExactSum {
285 fn write<W: zerompk::Write>(&self, writer: &mut W) -> zerompk::Result<()> {
286 writer.write_array_len(MSGPACK_FIELDS)?;
287 writer.write_i64((self.int >> 64) as i64)?;
288 writer.write_u64(self.int as u64)?;
289 writer.write_binary(&self.frac.serialize())?;
290 writer.write_boolean(self.has_decimal)?;
291 writer.write_boolean(self.exact_overflow)?;
292 writer.write_f64(self.float)?;
293 writer.write_f64(self.comp)?;
294 writer.write_boolean(self.has_float)?;
295 writer.write_u64(self.count)
296 }
297}
298
299impl<'a> zerompk::FromMessagePack<'a> for ExactSum {
300 fn read<R: zerompk::Read<'a>>(reader: &mut R) -> zerompk::Result<Self> {
301 reader.check_array_len(MSGPACK_FIELDS)?;
302 let hi = reader.read_i64()?;
303 let lo = reader.read_u64()?;
304 let frac_bytes = reader.read_binary()?;
305 let frac_bytes: [u8; 16] = frac_bytes
306 .as_ref()
307 .try_into()
308 .map_err(|_| zerompk::Error::BufferTooSmall)?;
309 Ok(Self {
310 int: (i128::from(hi) << 64) | i128::from(lo),
311 frac: Decimal::deserialize(frac_bytes),
312 has_decimal: reader.read_boolean()?,
313 exact_overflow: reader.read_boolean()?,
314 float: reader.read_f64()?,
315 comp: reader.read_f64()?,
316 has_float: reader.read_boolean()?,
317 count: reader.read_u64()?,
318 })
319 }
320}
321
322#[cfg(test)]
323mod tests {
324 use super::*;
325
326 const ABOVE: i64 = 9_007_199_254_740_993;
327 const AT: i64 = 9_007_199_254_740_992;
328
329 fn sum_of(values: &[Value]) -> Result<Value, EvalError> {
330 let mut acc = ExactSum::new();
331 for v in values {
332 acc.add_value(v);
333 }
334 acc.sum()
335 }
336
337 #[test]
338 fn integers_past_two_pow_53_sum_exactly() {
339 let total = sum_of(&[Value::Integer(ABOVE), Value::Integer(AT)]).unwrap();
340 assert_eq!(total, Value::Integer(18_014_398_509_481_985));
341 }
342
343 #[test]
344 fn nanosecond_timestamps_sum_exactly() {
345 let t = [
346 Value::Integer(1_700_000_000_000_000_001),
347 Value::Integer(1_700_000_000_000_000_002),
348 ];
349 assert_eq!(
350 sum_of(&t).unwrap(),
351 Value::Integer(3_400_000_000_000_000_003)
352 );
353 }
354
355 #[test]
356 fn total_past_i64_is_decimal() {
357 let total = sum_of(&[Value::Integer(i64::MAX), Value::Integer(i64::MAX)]).unwrap();
358 assert_eq!(
359 total,
360 Value::Decimal(Decimal::from_i128_with_scale(2 * i128::from(i64::MAX), 0))
361 );
362 }
363
364 #[test]
365 fn u64_above_i64_max_sums_exactly() {
366 let mut acc = ExactSum::new();
367 acc.add_u64(u64::MAX);
368 acc.add_value(&Value::from_u64(u64::MAX));
369 assert_eq!(
370 acc.sum().unwrap(),
371 Value::Decimal(Decimal::from_i128_with_scale(2 * i128::from(u64::MAX), 0))
372 );
373 let mut small = ExactSum::new();
374 small.add_u64(u64::MAX);
375 small.add_i64(-1);
376 small.add_i64(i64::MIN);
377 assert_eq!(small.sum().unwrap(), Value::Integer(i64::MAX - 1));
378 }
379
380 #[test]
381 fn total_past_decimal_range_is_overflow_error() {
382 let mut acc = ExactSum::new();
383 for _ in 0..4 {
385 acc.add_int(1i128 << 94);
386 }
387 assert_eq!(
388 acc.sum(),
389 Err(EvalError::NumericOverflow { function: "sum" })
390 );
391 }
392
393 #[test]
394 fn i128_overflow_is_overflow_error() {
395 let mut acc = ExactSum::new();
396 acc.add_int(i128::MAX);
397 acc.add_int(1);
398 assert_eq!(
399 acc.sum(),
400 Err(EvalError::NumericOverflow { function: "sum" })
401 );
402 assert_eq!(
403 acc.avg(),
404 Err(EvalError::NumericOverflow { function: "avg" })
405 );
406 }
407
408 #[test]
409 fn mixed_int_float_is_float() {
410 let total = sum_of(&[Value::Integer(2), Value::Float(0.5)]).unwrap();
411 assert_eq!(total, Value::Float(2.5));
412 let total = sum_of(&[Value::Integer(ABOVE), Value::Float(1.0)]).unwrap();
413 assert_eq!(total, Value::Float(ABOVE as f64 + 1.0));
414 }
415
416 #[test]
417 fn nan_input_makes_float_nan() {
418 let total = sum_of(&[Value::Integer(1), Value::Float(f64::NAN)]).unwrap();
419 assert!(matches!(total, Value::Float(f) if f.is_nan()));
420 }
421
422 #[test]
423 fn empty_is_null() {
424 let acc = ExactSum::new();
425 assert_eq!(acc.sum().unwrap(), Value::Null);
426 assert_eq!(acc.avg().unwrap(), Value::Null);
427 assert_eq!(sum_of(&[Value::String("x".into())]).unwrap(), Value::Null);
428 }
429
430 #[test]
431 fn avg_uses_the_exact_total() {
432 let mut acc = ExactSum::new();
433 acc.add_i64(ABOVE);
434 acc.add_i64(AT);
435 assert_eq!(acc.avg().unwrap(), Value::Float(AT as f64));
437 let mut big = ExactSum::new();
438 big.add_i64(i64::MAX);
439 big.add_i64(i64::MAX);
440 assert_eq!(big.avg().unwrap(), Value::Float(i64::MAX as f64));
441 let mut ints = ExactSum::new();
442 ints.add_i64(10);
443 ints.add_i64(20);
444 ints.add_i64(25);
445 assert_eq!(ints.avg_f64().unwrap(), Some(55.0 / 3.0));
446 }
447
448 #[test]
449 fn partial_merge_keeps_exactness() {
450 let mut a = ExactSum::new();
451 a.add_i64(ABOVE);
452 let mut b = ExactSum::new();
453 b.add_i64(AT);
454 b.add_i64(i64::MAX);
455 a.merge(&b);
456 let mut single = ExactSum::new();
457 for v in [ABOVE, AT, i64::MAX] {
458 single.add_i64(v);
459 }
460 assert_eq!(a.sum().unwrap(), single.sum().unwrap());
461 assert_eq!(a.count(), 3);
462 }
463
464 fn float_sum(values: &[f64]) -> f64 {
465 let mut acc = ExactSum::new();
466 for v in values {
467 acc.add_f64(*v);
468 }
469 match acc.sum().unwrap() {
470 Value::Float(f) => f,
471 other => panic!("expected a float SUM, got {other:?}"),
472 }
473 }
474
475 #[test]
478 fn non_finite_float_totals_follow_ieee() {
479 assert_eq!(float_sum(&[1e308, 1e308]), f64::INFINITY);
480 assert_eq!(float_sum(&[-1e308, -1e308]), f64::NEG_INFINITY);
481 assert_eq!(float_sum(&[f64::INFINITY, 1.0]), f64::INFINITY);
482 assert_eq!(float_sum(&[1.0, f64::NEG_INFINITY]), f64::NEG_INFINITY);
483 assert!(float_sum(&[f64::INFINITY, f64::NEG_INFINITY]).is_nan());
484 assert!(float_sum(&[f64::NAN, f64::INFINITY]).is_nan());
485 let mut avg = ExactSum::new();
486 avg.add_f64(1e308);
487 avg.add_f64(1e308);
488 assert_eq!(avg.avg().unwrap(), Value::Float(f64::INFINITY));
489 let mut mixed = ExactSum::new();
490 mixed.add_i64(5);
491 mixed.add_f64(f64::INFINITY);
492 assert_eq!(mixed.sum().unwrap(), Value::Float(f64::INFINITY));
493 }
494
495 #[test]
497 fn compensation_survives_large_cancelling_terms() {
498 assert_eq!(float_sum(&[1.0, 1e100, 1.0, -1e100]), 2.0);
499 assert_eq!(float_sum(&[0.1; 10]), 1.0);
500 }
501
502 #[test]
503 fn merge_keeps_non_finite_totals() {
504 let mut a = ExactSum::new();
505 a.add_f64(1e308);
506 let mut b = ExactSum::new();
507 b.add_f64(1e308);
508 a.merge(&b);
509 assert_eq!(a.sum().unwrap(), Value::Float(f64::INFINITY));
510 let mut pos = ExactSum::new();
511 pos.add_f64(f64::INFINITY);
512 let mut neg = ExactSum::new();
513 neg.add_f64(f64::NEG_INFINITY);
514 pos.merge(&neg);
515 assert!(matches!(pos.sum().unwrap(), Value::Float(f) if f.is_nan()));
516 let mut small = ExactSum::new();
517 small.add_f64(1.0);
518 let mut big = ExactSum::new();
519 big.add_f64(1e100);
520 big.add_f64(1.0);
521 big.add_f64(-1e100);
522 small.merge(&big);
523 assert_eq!(small.sum().unwrap(), Value::Float(2.0));
524 }
525
526 #[test]
527 fn msgpack_round_trip_keeps_non_finite_floats() {
528 for v in [f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
529 let mut acc = ExactSum::new();
530 acc.add_f64(v);
531 let bytes = zerompk::to_msgpack_vec(&acc).unwrap();
532 let back: ExactSum = zerompk::from_msgpack(&bytes).unwrap();
533 assert_eq!(back.count(), 1);
534 match (back.sum().unwrap(), acc.sum().unwrap()) {
535 (Value::Float(x), Value::Float(y)) => {
536 assert!(x == y || (x.is_nan() && y.is_nan()));
537 }
538 other => panic!("expected float sums, got {other:?}"),
539 }
540 }
541 }
542
543 #[test]
544 fn msgpack_round_trip_keeps_every_part() {
545 let mut big = ExactSum::new();
546 big.add_u64(u64::MAX);
547 big.add_u64(u64::MAX);
548 let mut negative = ExactSum::new();
549 negative.add_i64(i64::MIN);
550 negative.add_i64(i64::MIN);
551 negative.add_f64(0.1);
552 let mut overflow = ExactSum::new();
553 overflow.add_int(i128::MAX);
554 overflow.add_int(1);
555 for acc in [ExactSum::new(), big, negative, overflow] {
556 let bytes = zerompk::to_msgpack_vec(&acc).unwrap();
557 let back: ExactSum = zerompk::from_msgpack(&bytes).unwrap();
558 assert_eq!(back, acc);
559 assert_eq!(back.sum(), acc.sum());
560 }
561 }
562
563 #[test]
564 fn coerced_strings_stay_exact() {
565 let mut acc = ExactSum::new();
566 let text = sum_input(&Value::String("9007199254740993".into())).unwrap();
567 assert_eq!(text, Value::Integer(ABOVE));
568 assert!(acc.add_value(&text));
569 assert!(acc.add_value(&Value::Integer(AT)));
570 assert!(!acc.add_value(&Value::String("1".into())));
571 assert_eq!(acc.sum().unwrap(), Value::Integer(18_014_398_509_481_985));
572 assert_eq!(
573 sum_input(&Value::String("18446744073709551615".into())),
574 Some(Value::Decimal(Decimal::from(u64::MAX)))
575 );
576 assert_eq!(sum_input(&Value::String("x".into())), None);
577 assert_eq!(sum_input(&Value::Bool(true)), None);
578 }
579
580 fn dec(text: &str) -> Decimal {
581 Decimal::from_str_exact(text).unwrap()
582 }
583
584 #[test]
585 fn fractional_decimals_sum_exactly() {
586 let tenths = vec![Value::Decimal(dec("0.1")); 3];
587 assert_eq!(sum_of(&tenths).unwrap(), Value::Decimal(dec("0.3")));
588 let mixed = [Value::Decimal(dec("0.25")), Value::Integer(i64::MAX)];
589 assert_eq!(
590 sum_of(&mixed).unwrap(),
591 Value::Decimal(Decimal::from(i64::MAX) + dec("0.25"))
592 );
593 let with_float = [Value::Decimal(dec("0.5")), Value::Float(0.25)];
594 assert_eq!(sum_of(&with_float).unwrap(), Value::Float(0.75));
595 }
596
597 #[test]
598 fn decimal_avg_divides_the_exact_total() {
599 let mut acc = ExactSum::new();
600 acc.add_value(&Value::Decimal(dec("0.1")));
601 acc.add_value(&Value::Decimal(dec("0.2")));
602 assert_eq!(acc.avg().unwrap(), Value::Float(0.15));
603 }
604
605 #[test]
606 fn a_decimal_total_past_the_range_is_overflow_error() {
607 let mut acc = ExactSum::new();
608 acc.add_value(&Value::Decimal(Decimal::MAX - dec("0.5")));
609 acc.add_value(&Value::Decimal(Decimal::MAX - dec("0.5")));
610 assert_eq!(
611 acc.sum(),
612 Err(EvalError::NumericOverflow { function: "sum" })
613 );
614 let mut joined = ExactSum::new();
615 joined.add_value(&Value::Decimal(Decimal::MAX));
616 joined.add_value(&Value::Decimal(dec("0.5")));
617 assert_eq!(
618 joined.sum(),
619 Err(EvalError::NumericOverflow { function: "sum" })
620 );
621 }
622
623 #[test]
624 fn numeric_text_is_exact_where_it_can_be() {
625 assert_eq!(numeric_text("12"), Some(Value::Integer(12)));
626 assert_eq!(numeric_text("0.1"), Some(Value::Decimal(dec("0.1"))));
627 assert_eq!(numeric_text("1e3"), Some(Value::Float(1000.0)));
628 assert_eq!(numeric_text("x"), None);
629 let mut acc = ExactSum::new();
630 for text in ["0.1", "0.2"] {
631 assert!(acc.add_value(&sum_input(&Value::String(text.into())).unwrap()));
632 }
633 assert_eq!(acc.sum().unwrap(), Value::Decimal(dec("0.3")));
634 }
635
636 #[test]
637 fn decimal_parts_merge_and_round_trip() {
638 let mut a = ExactSum::new();
639 a.add_value(&Value::Decimal(dec("0.1")));
640 let mut b = ExactSum::new();
641 b.add_value(&Value::Decimal(dec("0.2")));
642 b.add_i64(1);
643 a.merge(&b);
644 assert_eq!(a.sum().unwrap(), Value::Decimal(dec("1.3")));
645 let bytes = zerompk::to_msgpack_vec(&a).unwrap();
646 let back: ExactSum = zerompk::from_msgpack(&bytes).unwrap();
647 assert_eq!(back, a);
648 }
649
650 #[test]
651 fn sum_inputs_sum_exactly() {
652 let mut acc = ExactSum::new();
653 for v in [
654 Value::Integer(ABOVE),
655 Value::from_u64(u64::MAX),
656 Value::String("2".into()),
657 ] {
658 assert!(acc.add_value(&sum_input(&v).unwrap()));
659 }
660 assert_eq!(sum_input(&Value::Null), None);
661 assert_eq!(
662 acc.sum().unwrap(),
663 Value::Decimal(Decimal::from_i128_with_scale(
664 i128::from(ABOVE) + i128::from(u64::MAX) + 2,
665 0
666 ))
667 );
668 }
669}