henad_core/explore/
reducer.rs

1//! Reducers that fold a run's samples of one stat column into one value.
2//!
3//! A reducer's output column is named `<stat column>:<kind>`, as in `Infected:max`, `Infected:first<=10` or
4//! `Recovered:mean@200..600`.
5
6use std::fmt;
7use std::str::FromStr;
8
9use crate::explore::stop::{Comparison, ComparisonError};
10use crate::export::StatColumns;
11use crate::view::StatDescriptor;
12
13/// Fold a reducer applies to its column's samples.
14#[derive(Debug, Clone, Copy, PartialEq)]
15pub enum ReducerKind {
16    /// Last finite sampled value.
17    Final,
18    /// Least finite sampled value.
19    Min,
20    /// Greatest finite sampled value.
21    Max,
22    /// Mean of the finite sampled values.
23    Mean,
24    /// First sampled tick of the greatest value.
25    ArgMax,
26    /// First sampled tick of the least value.
27    ArgMin,
28    /// First sampled tick whose value passes the comparison, empty when no sample passes.
29    FirstCrossing(Comparison),
30    /// Mean of the samples from tick `start` to tick `end` inclusive.
31    WindowMean {
32        /// First tick of the window.
33        start: u64,
34        /// Last tick of the window.
35        end: u64,
36    },
37}
38
39impl ReducerKind {
40    /// Kinds every column other than a histogram bucket gets by default.
41    pub const DEFAULTS: [Self; 4] = [Self::Final, Self::Min, Self::Max, Self::Mean];
42}
43
44impl fmt::Display for ReducerKind {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        match self {
47            Self::Final => f.write_str("final"),
48            Self::Min => f.write_str("min"),
49            Self::Max => f.write_str("max"),
50            Self::Mean => f.write_str("mean"),
51            Self::ArgMax => f.write_str("argmax"),
52            Self::ArgMin => f.write_str("argmin"),
53            Self::FirstCrossing(comparison) => write!(f, "first{comparison}"),
54            Self::WindowMean { start, end } => write!(f, "mean@{start}..{end}"),
55        }
56    }
57}
58
59impl FromStr for ReducerKind {
60    type Err = ReducerError;
61
62    /// Reads a kind as [`ReducerKind`]'s `Display` writes it.
63    fn from_str(raw: &str) -> Result<Self, Self::Err> {
64        match raw {
65            "final" => return Ok(Self::Final),
66            "min" => return Ok(Self::Min),
67            "max" => return Ok(Self::Max),
68            "mean" => return Ok(Self::Mean),
69            "argmax" => return Ok(Self::ArgMax),
70            "argmin" => return Ok(Self::ArgMin),
71            _ => {}
72        }
73        if let Some(comparison) = raw.strip_prefix("first") {
74            return comparison
75                .parse()
76                .map(Self::FirstCrossing)
77                .map_err(|source| ReducerError::Comparison {
78                    raw: raw.to_owned(),
79                    source,
80                });
81        }
82        if let Some(window) = raw.strip_prefix("mean@") {
83            let tick = |text: &str| text.parse::<u64>().ok();
84            return window
85                .split_once("..")
86                .and_then(|(start, end)| Some((tick(start)?, tick(end)?)))
87                .filter(|(start, end)| start <= end)
88                .map(|(start, end)| Self::WindowMean { start, end })
89                .ok_or_else(|| ReducerError::BadWindow { raw: raw.to_owned() });
90        }
91        Err(ReducerError::UnknownKind { raw: raw.to_owned() })
92    }
93}
94
95/// Returns whether `column` refers to a series of `stats`, as a label alone or followed by `.` and a component.
96pub(crate) fn names_a_stat(column: &str, stats: &[StatDescriptor]) -> bool {
97    stats.iter().any(|stat| {
98        column
99            .strip_prefix(stat.label)
100            .is_some_and(|rest| rest.is_empty() || rest.starts_with('.'))
101    })
102}
103
104/// A reducer as written, with its column given as text.
105#[derive(Debug, Clone, PartialEq)]
106pub struct ReducerSpec {
107    /// Stat column name, or a bare vector or histogram label for its magnitude or total.
108    pub column: String,
109    /// Fold the reducer applies.
110    pub kind: ReducerKind,
111}
112
113impl ReducerSpec {
114    /// Checks the column against the stat labels a model declares.
115    ///
116    /// A column passes when it is a label, or a label followed by `.` and a component. [`ReducerPlan::bind`] checks
117    /// the column again once a build provides the full column list.
118    ///
119    /// # Errors
120    ///
121    /// Returns [`ReducerError::UnknownColumn`] for a column that does not start with a stat label.
122    pub fn check_label(&self, stats: &[StatDescriptor]) -> Result<(), ReducerError> {
123        if names_a_stat(&self.column, stats) {
124            Ok(())
125        } else {
126            Err(ReducerError::UnknownColumn {
127                column: self.column.clone(),
128                known: stats.iter().map(|stat| stat.label.to_owned()).collect(),
129            })
130        }
131    }
132}
133
134impl FromStr for ReducerSpec {
135    type Err = ReducerError;
136
137    /// Reads `COLUMN:KIND`, split at the last `:`.
138    fn from_str(raw: &str) -> Result<Self, Self::Err> {
139        let (column, kind) = raw
140            .rsplit_once(':')
141            .ok_or_else(|| ReducerError::MissingKind { raw: raw.to_owned() })?;
142        Ok(Self {
143            column: column.to_owned(),
144            kind: kind.parse()?,
145        })
146    }
147}
148
149/// A reducer that cannot be read or bound.
150#[derive(Debug, Clone, PartialEq, Eq)]
151pub enum ReducerError {
152    /// A reducer with no `:` between the column and the kind.
153    MissingKind {
154        /// Reducer as written.
155        raw: String,
156    },
157    /// A kind no reducer has.
158    UnknownKind {
159        /// Kind as written.
160        raw: String,
161    },
162    /// A `first` kind whose comparison cannot be read.
163    Comparison {
164        /// Kind as written, or as [`ReducerKind`]'s `Display` writes it.
165        raw: String,
166        /// Reason the comparison is rejected.
167        source: ComparisonError,
168    },
169    /// A `mean@` kind whose window is not `START..END`, with `START` at most `END`.
170    BadWindow {
171        /// Kind as written, or as [`ReducerKind`]'s `Display` writes it.
172        raw: String,
173    },
174    /// A column that no stat series produces.
175    UnknownColumn {
176        /// Column as written in the reducer.
177        column: String,
178        /// Stat labels the model declares, or the column names once a build provides them.
179        known: Vec<String>,
180    },
181}
182
183impl fmt::Display for ReducerError {
184    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
185        match self {
186            Self::MissingKind { raw } => write!(f, "invalid reducer '{raw}', expected COLUMN:KIND"),
187            Self::UnknownKind { raw } => write!(
188                f,
189                "unknown reducer kind '{raw}', expected one of final, min, max, mean, argmax, argmin, first<=VALUE, \
190                 mean@START..END"
191            ),
192            Self::Comparison {
193                raw,
194                source: source @ ComparisonError::BadThreshold { .. },
195            } => {
196                write!(f, "invalid reducer kind '{raw}', {source}")
197            }
198            Self::Comparison { raw, .. } => write!(
199                f,
200                "invalid reducer kind '{raw}', expected 'first' followed by <, <=, >, >=, == or != and a number"
201            ),
202            Self::BadWindow { raw } => write!(f, "invalid reducer kind '{raw}', expected mean@START..END"),
203            Self::UnknownColumn { column, known } => {
204                write!(
205                    f,
206                    "unknown stat column '{column}', expected one of {}",
207                    known.join(", ")
208                )
209            }
210        }
211    }
212}
213
214impl std::error::Error for ReducerError {
215    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
216        match self {
217            Self::Comparison { source, .. } => Some(source),
218            Self::MissingKind { .. }
219            | Self::UnknownKind { .. }
220            | Self::BadWindow { .. }
221            | Self::UnknownColumn { .. } => None,
222        }
223    }
224}
225
226/// Reducers bound to the columns of one stat layout, in output order.
227#[derive(Debug, Clone, Default, PartialEq)]
228pub struct ReducerPlan {
229    columns: Vec<usize>,
230    kinds: Vec<ReducerKind>,
231    names: Vec<String>,
232}
233
234impl ReducerPlan {
235    /// Binds the default reducers when `defaults` is set, then each of `specs`, to columns of `columns`.
236    ///
237    /// The defaults come column by column. A reducer already bound, by default or by an earlier spec, is not bound
238    /// again.
239    ///
240    /// # Errors
241    ///
242    /// Returns [`ReducerError::UnknownColumn`] for a spec whose column [`StatColumns::resolve`] cannot find.
243    pub fn bind(columns: &StatColumns, specs: &[ReducerSpec], defaults: bool) -> Result<Self, ReducerError> {
244        let mut plan = Self::default();
245        if defaults {
246            for column in (0..columns.len()).filter(|&column| !columns.is_bucket(column)) {
247                for kind in ReducerKind::DEFAULTS {
248                    plan.add(columns, column, kind);
249                }
250            }
251        }
252        for spec in specs {
253            let column = columns
254                .resolve(&spec.column)
255                .ok_or_else(|| ReducerError::UnknownColumn {
256                    column: spec.column.clone(),
257                    known: (0..columns.len())
258                        .map(|column| columns.name(column).to_owned())
259                        .collect(),
260                })?;
261            plan.add(columns, column, spec.kind);
262        }
263        Ok(plan)
264    }
265
266    fn add(&mut self, columns: &StatColumns, column: usize, kind: ReducerKind) {
267        let bound = self
268            .columns
269            .iter()
270            .zip(&self.kinds)
271            .any(|(&bound_column, &bound_kind)| bound_column == column && bound_kind == kind);
272        if !bound {
273            self.columns.push(column);
274            self.kinds.push(kind);
275            self.names.push(format!("{}:{kind}", columns.name(column)));
276        }
277    }
278
279    /// Number of reducers.
280    pub fn len(&self) -> usize {
281        self.kinds.len()
282    }
283
284    /// Returns whether the plan binds no reducer.
285    pub fn is_empty(&self) -> bool {
286        self.kinds.is_empty()
287    }
288
289    /// Output column names, before CSV escaping.
290    pub fn names(&self) -> &[String] {
291        &self.names
292    }
293
294    /// Returns the stat column that reducer `i` reads.
295    ///
296    /// # Panics
297    ///
298    /// Panics when `i` is not below [`Self::len`].
299    pub fn column(&self, i: usize) -> usize {
300        self.columns[i]
301    }
302
303    /// Returns the fold that reducer `i` applies.
304    ///
305    /// # Panics
306    ///
307    /// Panics when `i` is not below [`Self::len`].
308    pub fn kind(&self, i: usize) -> ReducerKind {
309        self.kinds[i]
310    }
311}
312
313/// Running values of every reducer in a [`ReducerPlan`], over one run.
314#[derive(Debug, Clone, PartialEq)]
315pub struct ReducerState {
316    /// Last, least or greatest value so far, the sum for a mean, or the tick of a first crossing.
317    values: Vec<f64>,
318    /// Tick of the value kept by a [`ReducerKind::ArgMax`] or [`ReducerKind::ArgMin`] reducer.
319    ticks: Vec<u64>,
320    /// Number of finite values folded in so far, only those inside the window for a window mean, or 1 once a first
321    /// crossing is found.
322    counts: Vec<u64>,
323}
324
325impl ReducerState {
326    /// Returns the state of `plan`'s reducers before any sample.
327    pub fn new(plan: &ReducerPlan) -> Self {
328        Self {
329            values: vec![0.0; plan.len()],
330            ticks: vec![0; plan.len()],
331            counts: vec![0; plan.len()],
332        }
333    }
334
335    /// Folds in the sample taken at `tick`, where `row` holds a value per stat column. A value that is not finite
336    /// is skipped.
337    pub fn push(&mut self, plan: &ReducerPlan, tick: u64, row: &[f64]) {
338        for (i, ((value, kept_tick), count)) in self
339            .values
340            .iter_mut()
341            .zip(&mut self.ticks)
342            .zip(&mut self.counts)
343            .enumerate()
344        {
345            let sample = row[plan.columns[i]];
346            if !sample.is_finite() {
347                continue;
348            }
349            let replaces = match plan.kinds[i] {
350                ReducerKind::Final => true,
351                ReducerKind::Min | ReducerKind::ArgMin => *count == 0 || sample < *value,
352                ReducerKind::Max | ReducerKind::ArgMax => *count == 0 || sample > *value,
353                ReducerKind::Mean => {
354                    *value += sample;
355                    false
356                }
357                ReducerKind::FirstCrossing(comparison) => {
358                    if *count == 0 && comparison.holds(sample) {
359                        *value = tick as f64;
360                        *count = 1;
361                    }
362                    continue;
363                }
364                ReducerKind::WindowMean { start, end } => {
365                    if tick < start || tick > end {
366                        continue;
367                    }
368                    *value += sample;
369                    false
370                }
371            };
372            if replaces {
373                *value = sample;
374                *kept_tick = tick;
375            }
376            *count += 1;
377        }
378    }
379
380    /// Returns each reducer's value, or `None` for a reducer that saw no finite value, or no crossing.
381    pub fn finish(&self, plan: &ReducerPlan) -> Vec<Option<f64>> {
382        self.values
383            .iter()
384            .zip(&self.ticks)
385            .zip(&self.counts)
386            .zip(&plan.kinds)
387            .map(|(((&value, &tick), &count), kind)| match (count, kind) {
388                (0, _) => None,
389                (_, ReducerKind::Mean | ReducerKind::WindowMean { .. }) => Some(value / count as f64),
390                (_, ReducerKind::ArgMax | ReducerKind::ArgMin) => Some(tick as f64),
391                _ => Some(value),
392            })
393            .collect()
394    }
395}
396
397#[cfg(test)]
398mod tests {
399    use super::{ReducerError, ReducerKind, ReducerPlan, ReducerSpec, ReducerState};
400    use crate::export::StatColumns;
401    use crate::helpers::{stat, stat_histogram, stat_vec2};
402    use crate::view::StatDescriptor;
403
404    const COLOR: [u8; 4] = [0, 0, 0, 255];
405
406    fn columns() -> StatColumns {
407        StatColumns::plan(&[
408            stat("Infected", 0.0, COLOR),
409            stat_vec2("Velocity", 0.0, 0.0, COLOR),
410            stat_histogram("Speed", vec![0.0, 1.0, 2.0], vec![0, 0], COLOR),
411        ])
412    }
413
414    fn spec(raw: &str) -> ReducerSpec {
415        raw.parse().expect("a well-formed reducer")
416    }
417
418    #[test]
419    fn the_core_reducers_match_a_hand_computed_series() {
420        let columns = StatColumns::plan(&[stat("A", 0.0, COLOR)]);
421        let plan = ReducerPlan::bind(&columns, &[], true).expect("defaults always bind");
422        assert_eq!(plan.names(), ["A:final", "A:min", "A:max", "A:mean"]);
423        let mut state = ReducerState::new(&plan);
424        for (tick, value) in (0..).zip([3.0, 1.0, 4.0, 1.0, 5.0]) {
425            state.push(&plan, tick, &[value]);
426        }
427        assert_eq!(state.finish(&plan), [Some(5.0), Some(1.0), Some(5.0), Some(2.8)]);
428    }
429
430    #[test]
431    fn a_reducer_that_sees_no_finite_value_is_empty() {
432        let columns = StatColumns::plan(&[stat("A", 0.0, COLOR)]);
433        let plan = ReducerPlan::bind(&columns, &[], true).expect("defaults always bind");
434        let mut state = ReducerState::new(&plan);
435        assert_eq!(state.finish(&plan), [None; 4], "no samples");
436        state.push(&plan, 0, &[f64::NAN]);
437        state.push(&plan, 1, &[f64::INFINITY]);
438        assert_eq!(state.finish(&plan), [None; 4], "no finite samples");
439    }
440
441    /// Returns the values of the reducers `kinds` over column `A`, fed `(tick, value)` samples.
442    fn reduce(kinds: &[&str], samples: &[(u64, f64)]) -> Vec<Option<f64>> {
443        let columns = StatColumns::plan(&[stat("A", 0.0, COLOR)]);
444        let specs: Vec<ReducerSpec> = kinds.iter().map(|kind| spec(&format!("A:{kind}"))).collect();
445        let plan = ReducerPlan::bind(&columns, &specs, false).expect("column A exists");
446        let mut state = ReducerState::new(&plan);
447        for &(tick, value) in samples {
448            state.push(&plan, tick, &[value]);
449        }
450        state.finish(&plan)
451    }
452
453    #[test]
454    fn argmax_takes_the_first_tick_of_the_maximum() {
455        let samples = [(0, 2.0), (5, 7.0), (10, 1.0), (15, 7.0), (20, 1.0), (25, f64::NAN)];
456        assert_eq!(reduce(&["argmax", "argmin"], &samples), [Some(5.0), Some(10.0)]);
457        assert_eq!(reduce(&["argmax"], &[]), [None]);
458        assert_eq!(
459            reduce(&["argmax"], &[(0, f64::NAN), (5, f64::INFINITY)]),
460            [None],
461            "no finite sample"
462        );
463    }
464
465    #[test]
466    fn first_crossing_reports_the_first_sampled_tick() {
467        let samples = [(0, 30.0), (5, 12.0), (10, 9.0), (15, 20.0), (20, 4.0)];
468        assert_eq!(
469            reduce(&["first<=10", "first>12", "first==12", "first!=30"], &samples),
470            [Some(10.0), Some(0.0), Some(5.0), Some(5.0)]
471        );
472        assert_eq!(
473            reduce(&["first<10"], &[(0, f64::NAN), (5, 3.0)]),
474            [Some(5.0)],
475            "a NaN sample never crosses"
476        );
477    }
478
479    #[test]
480    fn a_crossing_that_never_happens_is_empty() {
481        assert_eq!(reduce(&["first<0"], &[(0, 1.0), (5, 0.0), (10, 2.0)]), [None]);
482        assert_eq!(reduce(&["first<0"], &[]), [None]);
483    }
484
485    #[test]
486    fn a_window_mean_covers_only_its_ticks() {
487        let samples = [(0, 100.0), (5, 1.0), (10, 2.0), (15, 3.0), (20, 100.0)];
488        assert_eq!(
489            reduce(&["mean@5..15", "mean@10..10", "mean@21..40", "mean"], &samples),
490            [Some(2.0), Some(2.0), None, Some(41.2)]
491        );
492        assert_eq!(
493            reduce(&["mean@0..10"], &[(0, 4.0), (5, f64::NAN), (10, 2.0)]),
494            [Some(3.0)],
495            "a value that is not finite is skipped"
496        );
497    }
498
499    #[test]
500    fn every_kind_reads_back_from_its_name() {
501        for name in [
502            "final",
503            "min",
504            "max",
505            "mean",
506            "argmax",
507            "argmin",
508            "first<=10",
509            "first>0.5",
510            "first==-2",
511            "first!=0",
512            "mean@200..600",
513            "mean@0..0",
514        ] {
515            let kind: ReducerKind = name.parse().expect("a known kind");
516            assert_eq!(kind.to_string(), name);
517        }
518        assert_eq!(
519            spec("Infected:first <= 10").kind.to_string(),
520            "first<=10",
521            "spaces around the comparator are dropped"
522        );
523        for bad in [
524            "first",
525            "first<=x",
526            "first=10",
527            "mean@",
528            "mean@600..200",
529            "mean@1..",
530            "mean@a..b",
531        ] {
532            let error = bad.parse::<ReducerKind>().expect_err("refused");
533            assert!(
534                matches!(error, ReducerError::Comparison { .. } | ReducerError::BadWindow { .. }),
535                "{bad} gave {error:?}"
536            );
537        }
538        let infinite = "first<=inf".parse::<ReducerKind>().expect_err("refused");
539        assert_eq!(
540            infinite.to_string(),
541            "invalid reducer kind 'first<=inf', threshold 'inf' is not a finite number",
542            "the message names the threshold, not the format"
543        );
544    }
545
546    #[test]
547    fn defaults_skip_buckets_and_specs_add_to_them() {
548        let columns = columns();
549        let plan = ReducerPlan::bind(&columns, &[spec("Infected:max"), spec("Velocity:mean")], true)
550            .expect("both columns exist");
551        let names: Vec<&str> = plan.names().iter().map(String::as_str).collect();
552        assert_eq!(
553            names.len(),
554            5 * 4,
555            "Infected, the three vector parts and the histogram total"
556        );
557        assert!(
558            !names.iter().any(|name| name.starts_with("Speed.[")),
559            "no bucket gets a default"
560        );
561        assert!(names.contains(&"Speed.total:mean"));
562        assert_eq!(
563            names.iter().filter(|&&name| name == "Infected:max").count(),
564            1,
565            "a spec repeating a default binds once"
566        );
567
568        let plan = ReducerPlan::bind(&columns, &[spec("Velocity:max"), spec("Speed.[0, 1):min")], false)
569            .expect("both columns exist");
570        assert_eq!(plan.names(), ["Velocity.magnitude:max", "Speed.[0, 1):min"]);
571        assert_eq!(plan.kind(1), ReducerKind::Min);
572    }
573
574    #[test]
575    fn a_reducer_is_read_as_column_and_kind() {
576        assert_eq!(
577            spec("Giant Component: Share:mean"),
578            ReducerSpec {
579                column: "Giant Component: Share".to_owned(),
580                kind: ReducerKind::Mean,
581            }
582        );
583        assert_eq!(
584            "Infected".parse::<ReducerSpec>(),
585            Err(ReducerError::MissingKind {
586                raw: "Infected".to_owned()
587            })
588        );
589        assert_eq!(
590            "Infected:median".parse::<ReducerSpec>(),
591            Err(ReducerError::UnknownKind {
592                raw: "median".to_owned()
593            })
594        );
595        for kind in ReducerKind::DEFAULTS {
596            assert_eq!(kind.to_string().parse(), Ok(kind));
597        }
598    }
599
600    #[test]
601    fn an_unknown_column_is_refused() {
602        let error = ReducerPlan::bind(&columns(), &[spec("Recovered:max")], false).expect_err("no such column");
603        assert!(
604            error
605                .to_string()
606                .starts_with("unknown stat column 'Recovered', expected one of Infected, "),
607            "{error}"
608        );
609
610        let stats = [
611            StatDescriptor::new("Infected", COLOR),
612            StatDescriptor::new("Velocity", COLOR),
613        ];
614        assert_eq!(spec("Infected:max").check_label(&stats), Ok(()));
615        assert_eq!(spec("Velocity.x:max").check_label(&stats), Ok(()));
616        assert!(spec("Infectedness:max").check_label(&stats).is_err());
617        assert!(spec("Recovered:max").check_label(&stats).is_err());
618    }
619}
henad_core/explore/reducer.rs

henad_core/explore/
reducer.rs
