//! Code for creating and manipulating observations about clock skew.

// TODO:

//   - See if we can safely report a "no-confidence" value with even fewer

//     observations than we currently collect.

//   - If the universe of fallbacks and/or the guard sample size and/or the list

//     of bridges is very small, see if we can still use that to make a

//     low-confidence value.

use std::time::{Duration, Instant};

use tor_proto::ClockSkew;

/// A single observation related to reported clock skew.

#[derive(Debug, Clone)]

pub(crate) struct SkewObservation {

    /// The reported clock skew

    pub(crate) skew: ClockSkew,

    /// The time when we added this observation.

    pub(crate) when: Instant,

}

impl SkewObservation {

    /// Return true if this observation has been made more recently than

    /// `cutoff`. If cutoff is None, consider it's very far in the past.

}

/// An estimate of how skewed our clock is, plus a summary of why we think so.

//

// SEMVER NOTE: this type is re-exported from tor-circmgr.

#[derive(Clone, Debug)]

pub struct SkewEstimate {

    /// Our best guess for the magnitude of the skew.

    estimate: ClockSkew,

    /// The number of observations leading to this estimate.

    n_observations: usize,

    /// A description of how confident we are.

    confidence: Confidence,

}

/// Subjective description of how sure we are that our clock is/isn't skewed.

#[derive(Clone, Debug)]

enum Confidence {

    /// We aren't very sure about our estimate.

    None,

    /// It seems plausible that our clock is skewed

    Low,

    /// We are pretty confident that our clock is skewed.

    High,

}

/// How bad does clock skew need to be before we'll tell the user that it's a

/// problem?

const SIGNIFICANCE_THRESHOLD: Duration = Duration::from_secs(15 * 60);

impl std::fmt::Display for SkewEstimate {

        /// Format the whole-second part of `d`.

        ///

        /// We don't care about fractions here, since skew only mattes if it's

        /// on the order of many minutes.

        };

}

impl SkewEstimate {

    /// Return our best estimate for the current clock skew.

    /// Return true if this estimate is worth telling the user about.

    /// Compute an estimate of how skewed we think our clock is, based on the

    /// reports in `skews`.

        // Use the mean of the remaining observations to determine our estimate.

        // Use the standard deviation to determine how confident we should be in

        // our estimate.

        //

        // TODO: probably we should be using a real statistical test instead,

        // but that seems like overkill.

            // Avoid divide-by-zero below: if the standard deviation is less

            // than 1 second then the mean is probably right.

        } else {

                // If we're saying that we are skewed, look at how many standard

                // deviations we are from zero.

            } else {

                // If we're saying that we're not skewed, look at how many

                // standard deviations zero is from "skewed".

            };

            } else {

            }

        };

}

/// Remove all outliers from `values`, and convert the resulting times into

/// `f64`s.

///

/// We guarantee that no more than 1/2 of the input will be discarded.

///

/// # Panics

///

/// Panics if values is empty.

    // Compute the quartiles  of our observations.

/// Compute and return the mean and standard deviation of `values`.

///

/// Returns `(Nan,Nan)` if `values` is empty.

#[cfg(test)]

mod test {

    // @@ begin test lint list maintained by maint/add_warning @@

    #![allow(clippy::bool_assert_comparison)]

    #![allow(clippy::clone_on_copy)]

    #![allow(clippy::dbg_macro)]

    #![allow(clippy::mixed_attributes_style)]

    #![allow(clippy::print_stderr)]

    #![allow(clippy::print_stdout)]

    #![allow(clippy::single_char_pattern)]

    #![allow(clippy::unwrap_used)]

    #![allow(clippy::unchecked_duration_subtraction)]

    #![allow(clippy::useless_vec)]

    #![allow(clippy::needless_pass_by_value)]

    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->

    use super::*;

    use float_eq::assert_float_eq;

    /// Tolerance for float comparison.

    const TOL: f64 = 0.00001;

    #[test]

    fn mean_stddev() {

        // This case is trivial.

        let a = [17.0];

        let (m, s) = mean_and_standard_deviation(&a[..]);

        assert_float_eq!(m, 17.0, abs <= TOL);

        assert_float_eq!(s, 0.0, abs <= TOL);

        // Computed these by hand using a calculator.

        let a = [1.0, 2.0, 3.0, 4.0];

        let (m, s) = mean_and_standard_deviation(&a[..]);

        assert_float_eq!(m, 2.5, abs <= TOL);

        assert_float_eq!(s, 1.11803398, abs <= TOL);

        // Generated these using numpy from normal distribution with stddev=1,

        // mean=0.

        let a = [

            1.34528777,

            0.17855632,

            -0.08147599,

            0.14845672,

            0.6838537,

            -1.59034826,

            0.06777352,

            -2.42469117,

            -0.12017179,

            0.47098959,

        ];

        let (m, s) = mean_and_standard_deviation(&a[..]);

        assert_float_eq!(m, -0.132176959, abs <= TOL);

        assert_float_eq!(s, 1.0398321132, abs <= TOL);

    }

    #[test]

    fn outliers() {

        use ClockSkew::{Fast, Slow};

        let hour = Duration::from_secs(3600);

        // median will be 0. quartiles will ± 2 hours.  That makes

        // the IQR 4 hours, so nothing will be discarded.

        let a = vec![

            Slow(hour * 3),

            Slow(hour * 2),

            Slow(hour),

            ClockSkew::None,

            Fast(hour),

            Fast(hour * 2),

            Fast(hour * 3),

        ];

        let mut b = discard_outliers(a.clone());

        b.sort_by(|a, b| a.partial_cmp(b).unwrap());

        assert_eq!(b.len(), 7);

        for (ai, bi) in a.iter().zip(b.iter()) {

            assert_float_eq!(ai.as_secs_f64(), bi, abs <= TOL);

        }

        // Now try with a case that does have some outliers. This time, the IQR

        // will be 1 hour, so the first and last times will be discarded as

        // outliers.

        let a = vec![

            Slow(hour * 4),

            Slow(hour / 2),

            Slow(hour / 3),

            ClockSkew::None,

            Fast(hour / 3),

            Fast(hour / 2),

            Fast(hour * 4),

        ];

        let mut b = discard_outliers(a.clone());

        b.sort_by(|a, b| a.partial_cmp(b).unwrap());

        assert_eq!(b.len(), 5);

        for (ai, bi) in a[1..=5].iter().zip(b.iter()) {

            assert_float_eq!(ai.as_secs_f64(), bi, abs <= TOL);

        }

    }

    #[test]

    fn estimate_with_no_data() {

        // zero inputs -> output is none.

        let now = Instant::now();

        let est = SkewEstimate::estimate_skew([].iter(), now);

        assert!(est.is_none());

        // Same with fewer than min_observations.

        let year = Duration::from_secs(365 * 24 * 60 * 60);

        let obs = vec![

            SkewObservation {

                skew: ClockSkew::Fast(year),

                when: now

            };

            5

        ];

        let est = SkewEstimate::estimate_skew(obs.iter(), now);

        assert!(est.is_none());

        // Same with many observations all of which are obsolete.

        //

        // (advance the clock: not all Instant implementations let you go back a long time

        // before startup.)

        let now = now + year;

        let obs = vec![

            SkewObservation {

                skew: ClockSkew::Fast(year),

                when: now - year

            };

            100

        ];

        let est = SkewEstimate::estimate_skew(obs.iter(), now);

        assert!(est.is_none());

    }

    /// Construct a vector of SkewObservations from a slice of skew magnitudes

    /// expressed in minutes.

    fn from_minutes(mins: &[f64]) -> Vec<SkewObservation> {

        mins.iter()

            .map(|m| SkewObservation {

                skew: ClockSkew::from_secs_f64(m * 60.0).unwrap(),

                when: Instant::now(),

            })

            .collect()

    }

    #[test]

    fn estimate_skewed() {

        // The quartiles here are -22 and -10.  The IQR is therefore 12, so we

        // won't discard anything.

        //

        // The mean is -17.125: That's more than 15 minutes from zero, so we'll

        // say we're slow.

        //

        // The standard deviation is 7.67: that puts the mean between 2 and 3

        // standard deviations from zero, so we'll say we're skewed with "low"

        // confidence.

        let obs = from_minutes(&[-20.0, -10.0, -20.0, -25.0, 0.0, -18.0, -22.0, -22.0]);

        let est = SkewEstimate::estimate_skew(obs.iter(), Instant::now()).unwrap();

        assert_eq!(

            est.to_string(),

            "slow by around 17m 7s (based on 8 recent observations, with some confidence)"

        );

    }

    #[test]

    fn estimate_not_skewed() {

        // The quartiles here are -2 and 6: IRQ is 8, so we'll discard all the

        // huge values, leaving 8.

        //

        // Mean of the remaining items is 0.75 and standard deviation is 2.62:

        // we'll be pretty sure we're not much skewed.

        let obs = from_minutes(&[

            -100.0, 100.0, -3.0, -2.0, 0.0, 1.0, 0.5, 6.0, 3.0, 0.5, 99.0,

        ]);

        let est = SkewEstimate::estimate_skew(obs.iter(), Instant::now()).unwrap();

        assert_eq!(

            est.to_string(),

            "not skewed by more than 15m (based on 8 recent observations, with high confidence)"

        );

    }

}