windowed_stats/experimental/series/
interpolation.rs

1// Copyright 2024 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Sample and aggregation interpolation.
6
7use std::fmt::{self, Debug, Formatter};
8use std::marker::PhantomData;
9use std::num::NonZeroUsize;
10
11use crate::experimental::series::statistic::{FoldError, Statistic};
12
13// The distinction between `InterpolationKind` and `Interpolation` provides an important feature:
14// the interpolation for a `TimeMatrix` is specified nominally and any and all type parameters are
15// implicitly and consistently forwarded from the `Statistic` type parameter. Consider this type:
16//
17// ```
18// TimeMatrix<Sum<u64>, LastSample>
19// ```
20//
21// Notice that `LastSample` is **not** parameterized. Instead, this parameter is lifted into the
22// `InterpolationKind::Output` GAT. Without this separation of type constructor and closed output
23// type, this type would require redundant and decoupled input parameters:
24//
25// ```
26// TimeMatrix<Sum<u64>, LastSample<u64>>
27// ```
28//
29// This loses the necessary relationship between the sample types (`u64`): they must be the same!
30
31/// A kind of [`Interpolation`].
32///
33/// Interpolation kinds are nominal type constructors. The `Output` GAT provides a mapping from a
34/// kind (with no type parameters) to a generic type constructor for a parameterized type. For
35/// example, the [`LastSample`] kind has [`LastSampleOutput`] as its associated output type.
36pub trait InterpolationKind {
37    // TODO(https://fxbug.dev/372328823): The mapping from `InterpolationKind` types to their
38    //                                    associated `Output` types prevents type inference in many
39    //                                    APIs that construct a `TimeMatrix`. This means that
40    //                                    `InterpolationKind` type parameters must often be
41    //                                    annotated explicitly, even when the type appears in an
42    //                                    expression of a function argument.
43    //
44    //                                    Refactor interpolation so that these type annotations are
45    //                                    less commonly needed (or are not needed at all).
46    /// The parameterized [`Interpolation`] associated with this kind.
47    type Output<T>: Interpolation<T>
48    where
49        T: Clone;
50}
51
52/// A type that observes data in order to synthesize and fold interpolated samples into a
53/// [`Statistic`].
54///
55/// `Interpolation`s mediate the aggregation of a [`Statistic`] by folding synthetic samples for
56/// [sampling periods][`SamplingInterval`] in which no data has been observed.
57///
58/// [`SamplingInterval`]: crate::experimental::series::interval::SamplingInterval
59pub trait Interpolation<T>: Clone {
60    /// Folds an interpolated sample `n` times into the given [`Statistic`].
61    fn interpolate<F>(&self, statistic: &mut F, n: NonZeroUsize) -> Result<(), FoldError>
62    where
63        F: Statistic<Sample = T>;
64
65    /// Observes a (real) sample and potentially updates the state of the interpolation.
66    fn observe(&mut self, _sample: T) {}
67}
68
69/// An [`Interpolation`] kind over a constant sample.
70#[derive(Debug)]
71pub enum ConstantSample {}
72
73impl ConstantSample {
74    pub fn default<T>() -> ConstantSampleOutput<T>
75    where
76        T: Default,
77    {
78        ConstantSampleOutput::default()
79    }
80
81    pub fn new<T>(sample: T) -> ConstantSampleOutput<T> {
82        ConstantSampleOutput(sample)
83    }
84}
85
86impl InterpolationKind for ConstantSample {
87    type Output<T>
88        = ConstantSampleOutput<T>
89    where
90        T: Clone;
91}
92
93#[derive(Clone, Copy, Debug, Default)]
94pub struct ConstantSampleOutput<T>(pub T);
95
96impl<T> Interpolation<T> for ConstantSampleOutput<T>
97where
98    T: Clone,
99{
100    fn interpolate<F>(&self, statistic: &mut F, n: NonZeroUsize) -> Result<(), FoldError>
101    where
102        F: Statistic<Sample = T>,
103    {
104        statistic.fill(self.0.clone(), n)
105    }
106}
107
108/// An [`Interpolation`] kind over the last observed sample.
109#[derive(Debug)]
110pub enum LastSample {}
111
112impl LastSample {
113    pub fn or<T>(sample: T) -> LastSampleOutput<T> {
114        LastSampleOutput::or(sample)
115    }
116}
117
118impl InterpolationKind for LastSample {
119    type Output<T>
120        = LastSampleOutput<T>
121    where
122        T: Clone;
123}
124
125#[derive(Clone, Copy, Debug, Default)]
126pub struct LastSampleOutput<T>(T);
127
128impl<T> LastSampleOutput<T> {
129    pub fn or(sample: T) -> Self {
130        LastSampleOutput(sample)
131    }
132}
133
134impl<T> Interpolation<T> for LastSampleOutput<T>
135where
136    T: Clone,
137{
138    fn interpolate<F>(&self, statistic: &mut F, n: NonZeroUsize) -> Result<(), FoldError>
139    where
140        F: Statistic<Sample = T>,
141    {
142        statistic.fill(self.0.clone(), n)
143    }
144
145    fn observe(&mut self, sample: T) {
146        self.0 = sample;
147    }
148}
149
150/// An [`Interpolation`] kind that samples nothing in periods with no data (i.e., does nothing).
151#[derive(Debug)]
152pub enum NoSample {}
153
154impl NoSample {
155    pub fn new<T>() -> NoSampleOutput<T> {
156        NoSampleOutput::default()
157    }
158}
159
160impl InterpolationKind for NoSample {
161    type Output<T>
162        = NoSampleOutput<T>
163    where
164        T: Clone;
165}
166
167pub struct NoSampleOutput<T>(PhantomData<fn() -> T>);
168
169impl<T> Clone for NoSampleOutput<T> {
170    fn clone(&self) -> Self {
171        NoSampleOutput::default()
172    }
173}
174
175impl<T> Copy for NoSampleOutput<T> {}
176
177impl<T> Debug for NoSampleOutput<T> {
178    fn fmt(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
179        formatter.debug_struct("NoSampleOutput").finish_non_exhaustive()
180    }
181}
182
183impl<T> Default for NoSampleOutput<T> {
184    fn default() -> Self {
185        NoSampleOutput(PhantomData)
186    }
187}
188
189impl<T> Interpolation<T> for NoSampleOutput<T>
190where
191    T: Clone,
192{
193    fn interpolate<F>(&self, _statistic: &mut F, _n: NonZeroUsize) -> Result<(), FoldError>
194    where
195        F: Statistic<Sample = T>,
196    {
197        Ok(())
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use std::num::NonZeroUsize;
204
205    use crate::experimental::series::interpolation::{
206        ConstantSample, Interpolation, LastSample, NoSample,
207    };
208    use crate::experimental::series::statistic::{Max, Statistic};
209
210    #[test]
211    fn interpolate_constant() {
212        let mut max = Max::<u64>::default();
213        let mut constant = ConstantSample::new(1u64);
214
215        constant.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
216        assert_eq!(max.aggregation().unwrap(), 1);
217
218        constant.observe(7); // Observe a sample.
219        constant.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
220        // The observation of the sample `7` is ignored by `Constant`. Interpolating again samples
221        // the constant `1`, and so the aggregation is unchanged.
222        assert_eq!(max.aggregation().unwrap(), 1);
223    }
224
225    #[test]
226    fn interpolate_last_sample() {
227        let mut max = Max::<u64>::default();
228        let mut last = LastSample::or(1u64);
229
230        last.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
231        assert_eq!(max.aggregation().unwrap(), 1);
232
233        last.observe(7); // Observe a sample.
234        last.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
235        // `LastSample` caches the last observed sample: `7` is remembered. Interpolating again
236        // folds this cached sample, and so the aggregation is now `7`.
237        assert_eq!(max.aggregation().unwrap(), 7);
238    }
239
240    #[test]
241    fn interpolate_no_sample() {
242        let mut max = Max::<u64>::default();
243        let mut none = NoSample::new();
244
245        none.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
246        assert_eq!(max.aggregation(), None);
247
248        none.observe(7); // Observe a sample.
249        none.interpolate(&mut max, NonZeroUsize::MIN).unwrap();
250        // The observation of the sample `7` is ignored by `NoSample`. Interpolation does nothing,
251        // and so the aggregation is unchanged.
252        assert_eq!(max.aggregation(), None);
253    }
254}