// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/nqe/observation_buffer.h"

#include <stddef.h>

#include <memory>
#include <utility>
#include <vector>

#include "base/logging.h"
#include "base/macros.h"
#include "base/memory/ptr_util.h"
#include "base/test/simple_test_tick_clock.h"
#include "base/time/time.h"
#include "net/nqe/network_quality_observation.h"
#include "net/nqe/network_quality_observation_source.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace net {

namespace nqe {

namespace internal {

namespace {

// Verify that the buffer size is never exceeded.
TEST(NetworkQualityObservationBufferTest, BoundedBuffer) {
  ObservationBuffer<int32_t> observation_buffer(1.0);
  const base::TimeTicks now =
      base::TimeTicks() + base::TimeDelta::FromSeconds(1);
  for (int i = 1; i <= 1000; ++i) {
    observation_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_TCP));
    // The number of entries should be at most the maximum buffer size.
    EXPECT_GE(300u, observation_buffer.Size());
  }
}

// Test disabled on OS_WIN to avoid linking errors when calling
// SetTickClockForTesting.
// TODO(tbansal): crbug.com/651963. Pass the clock through NQE's constructor.
#if !defined(OS_WIN)
// Verify that the percentiles are monotonically non-decreasing when a weight is
// applied.
TEST(NetworkQualityObservationBufferTest, GetPercentileWithWeights) {
  std::unique_ptr<base::SimpleTestTickClock> tick_clock(
      new base::SimpleTestTickClock());
  base::SimpleTestTickClock* tick_clock_ptr = tick_clock.get();

  ObservationBuffer<int32_t> observation_buffer(0.98);
  observation_buffer.SetTickClockForTesting(std::move(tick_clock));
  const base::TimeTicks now = tick_clock_ptr->NowTicks();
  for (int i = 1; i <= 100; ++i) {
    tick_clock_ptr->Advance(base::TimeDelta::FromSeconds(1));
    observation_buffer.AddObservation(Observation<int32_t>(
        i, tick_clock_ptr->NowTicks(), NETWORK_QUALITY_OBSERVATION_SOURCE_TCP));
  }
  EXPECT_EQ(100U, observation_buffer.Size());

  int32_t result_lowest = INT32_MAX;
  int32_t result_highest = INT32_MIN;

  for (int i = 1; i <= 100; ++i) {
    // Verify that i'th percentile is more than i-1'th percentile.
    int32_t result_i;
    EXPECT_TRUE(observation_buffer.GetPercentile(
        now, &result_i, i, std::vector<NetworkQualityObservationSource>()));
    result_lowest = std::min(result_lowest, result_i);

    result_highest = std::max(result_highest, result_i);

    int32_t result_i_1;
    EXPECT_TRUE(observation_buffer.GetPercentile(
        now, &result_i_1, i - 1,
        std::vector<NetworkQualityObservationSource>()));

    EXPECT_LE(result_i_1, result_i);
  }
  EXPECT_LT(result_lowest, result_highest);
}
#endif

// Verifies that the percentiles are correctly computed. All observations have
// the same timestamp.
TEST(NetworkQualityObservationBufferTest, PercentileSameTimestamps) {
  ObservationBuffer<int32_t> int_buffer(0.5);
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  ASSERT_EQ(0u, int_buffer.Size());
  ASSERT_LT(0u, int_buffer.Capacity());
  ASSERT_EQ(0u, time_delta_buffer.Size());
  ASSERT_LT(0u, time_delta_buffer.Capacity());

  const base::TimeTicks now = base::TimeTicks::Now();

  int32_t result;
  base::TimeDelta time_delta_result;

  // Percentiles should be unavailable when no observations are available.
  EXPECT_FALSE(
      int_buffer.GetPercentile(base::TimeTicks(), &result, 50,
                               std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      base::TimeTicks(), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));

  // Insert samples from {1,2,3,..., 100}. First insert odd samples, then even
  // samples. This helps in verifying that the order of samples does not matter.
  for (int i = 1; i <= 99; i += 2) {
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    EXPECT_TRUE(int_buffer.GetPercentile(
        base::TimeTicks(), &result, 50,
        std::vector<NetworkQualityObservationSource>()));
    ASSERT_EQ(static_cast<size_t>(i / 2 + 1), int_buffer.Size());
    EXPECT_TRUE(time_delta_buffer.GetPercentile(
        base::TimeTicks(), &time_delta_result, 50,
        std::vector<NetworkQualityObservationSource>()));
    ASSERT_EQ(static_cast<size_t>(i / 2 + 1), time_delta_buffer.Size());
  }

  for (int i = 2; i <= 100; i += 2) {
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    EXPECT_TRUE(int_buffer.GetPercentile(
        base::TimeTicks(), &result, 50,
        std::vector<NetworkQualityObservationSource>()));
    ASSERT_EQ(static_cast<size_t>(i / 2 + 50), int_buffer.Size());
    EXPECT_TRUE(time_delta_buffer.GetPercentile(
        base::TimeTicks(), &time_delta_result, 50,
        std::vector<NetworkQualityObservationSource>()));
    ASSERT_EQ(static_cast<size_t>(i / 2 + 50), time_delta_buffer.Size());
  }

  ASSERT_EQ(100u, int_buffer.Size());
  ASSERT_EQ(100u, time_delta_buffer.Size());

  for (int i = 0; i <= 100; ++i) {
    // Checks if the difference between the two integers is less than 1. This is
    // required because computed percentiles may be slightly different from
    // what is expected due to floating point computation errors and integer
    // rounding off errors.
    EXPECT_TRUE(int_buffer.GetPercentile(
        base::TimeTicks(), &result, i,
        std::vector<NetworkQualityObservationSource>()));
    EXPECT_TRUE(time_delta_buffer.GetPercentile(
        base::TimeTicks(), &time_delta_result, i,
        std::vector<NetworkQualityObservationSource>()));
    EXPECT_NEAR(result, i, 1);
    EXPECT_NEAR(time_delta_result.InMilliseconds(), i, 1);
  }

  EXPECT_FALSE(int_buffer.GetPercentile(
      now + base::TimeDelta::FromSeconds(1), &result, 50,
      std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      now + base::TimeDelta::FromSeconds(1), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));

  // Percentiles should be unavailable when no observations are available.
  int_buffer.Clear();
  time_delta_buffer.Clear();
  EXPECT_FALSE(
      int_buffer.GetPercentile(base::TimeTicks(), &result, 50,
                               std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      base::TimeTicks(), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));
}

// Verifies that the percentiles are correctly computed. Observations have
// different timestamps with half the observations being very old and the rest
// of them being very recent. Percentiles should factor in recent observations
// much more heavily than older samples.
TEST(NetworkQualityObservationBufferTest, PercentileDifferentTimestamps) {
  ObservationBuffer<int32_t> int_buffer(0.5);
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  const base::TimeTicks now = base::TimeTicks::Now();
  const base::TimeTicks very_old = now - base::TimeDelta::FromDays(7);

  int32_t result;
  base::TimeDelta time_delta_result;

  // Network quality should be unavailable when no observations are available.
  EXPECT_FALSE(
      int_buffer.GetPercentile(base::TimeTicks(), &result, 50,
                               std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      base::TimeTicks(), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));

  // First 50 samples have very old timestamps.
  for (int i = 1; i <= 50; ++i) {
    int_buffer.AddObservation(Observation<int32_t>(
        i, very_old, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(Observation<base::TimeDelta>(
        base::TimeDelta::FromMilliseconds(i), very_old,
        NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // Next 50 (i.e., from 51 to 100) have recent timestamps.
  for (int i = 51; i <= 100; ++i) {
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // Older samples have very little weight. So, all percentiles are >= 51
  // (lowest value among recent observations).
  for (int i = 1; i < 100; ++i) {
    // Checks if the difference between the two integers is less than 1. This is
    // required because computed percentiles may be slightly different from
    // what is expected due to floating point computation errors and integer
    // rounding off errors.
    EXPECT_TRUE(int_buffer.GetPercentile(
        very_old, &result, i, std::vector<NetworkQualityObservationSource>()));
    EXPECT_NEAR(result, 51 + 0.49 * i, 1);

    EXPECT_TRUE(time_delta_buffer.GetPercentile(
        very_old, &time_delta_result, i,
        std::vector<NetworkQualityObservationSource>()));
    EXPECT_NEAR(time_delta_result.InMilliseconds(), 51 + 0.49 * i, 1);
  }

  EXPECT_FALSE(int_buffer.GetPercentile(
      now + base::TimeDelta::FromSeconds(1), &result, 50,
      std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      now + base::TimeDelta::FromSeconds(1), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));
}

#if !defined(OS_WIN)
// Disabled on OS_WIN since the GetUnweightedAverage() and
// GetUnweightedAverage() functions are not yet called outside tests, and so the
// compiler on Windows does not generate the object code for these functions.
// TODO(tbansal): crbug.com/656170 Enable these tests on Windows once these
// functions are called outside the tests.
TEST(NetworkQualityObservationBufferTest,
     UnweightedAverageDifferentTimestamps) {
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  ObservationBuffer<int32_t> int_buffer(0.5);
  const base::TimeTicks now = base::TimeTicks::Now();
  const base::TimeTicks very_old = now - base::TimeDelta::FromDays(7);

  base::TimeDelta time_delta_result;
  int32_t int_result;

  // Network quality should be unavailable when no observations are available.
  EXPECT_FALSE(time_delta_buffer.GetUnweightedAverage(
      base::TimeTicks(), std::vector<NetworkQualityObservationSource>(),
      &time_delta_result));
  EXPECT_FALSE(int_buffer.GetUnweightedAverage(
      base::TimeTicks(), std::vector<NetworkQualityObservationSource>(),
      &int_result));

  // The first 50 samples have very old timestamps.
  for (int i = 1; i <= 50; ++i) {
    time_delta_buffer.AddObservation(Observation<base::TimeDelta>(
        base::TimeDelta::FromMilliseconds(i), very_old,
        NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    int_buffer.AddObservation(Observation<int32_t>(
        i, very_old, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // The next 50 (i.e., from 51 to 100) samples have recent timestamps.
  for (int i = 51; i <= 100; ++i) {
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // All samples have equal weight. So, the unweighted average is the average of
  // all samples.
  EXPECT_TRUE(time_delta_buffer.GetUnweightedAverage(
      very_old, std::vector<NetworkQualityObservationSource>(),
      &time_delta_result));
  EXPECT_NEAR(time_delta_result.InMilliseconds(), (1 + 100) / 2, 1);

  EXPECT_TRUE(int_buffer.GetUnweightedAverage(
      very_old, std::vector<NetworkQualityObservationSource>(), &int_result));
  EXPECT_NEAR(int_result, (1 + 100) / 2, 1);

  EXPECT_FALSE(time_delta_buffer.GetUnweightedAverage(
      now + base::TimeDelta::FromSeconds(1),
      std::vector<NetworkQualityObservationSource>(), &time_delta_result));
  EXPECT_FALSE(int_buffer.GetUnweightedAverage(
      now + base::TimeDelta::FromSeconds(1),
      std::vector<NetworkQualityObservationSource>(), &int_result));
}

TEST(NetworkQualityObservationBufferTest, WeightedAverageDifferentTimestamps) {
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  ObservationBuffer<int32_t> int_buffer(0.5);
  const base::TimeTicks now = base::TimeTicks::Now();
  const base::TimeTicks very_old = now - base::TimeDelta::FromDays(7);

  base::TimeDelta time_delta_result;
  int32_t int_result;

  // Network quality should be unavailable when no observations are available.
  EXPECT_FALSE(time_delta_buffer.GetWeightedAverage(
      base::TimeTicks(), std::vector<NetworkQualityObservationSource>(),
      &time_delta_result));
  EXPECT_FALSE(int_buffer.GetWeightedAverage(
      base::TimeTicks(), std::vector<NetworkQualityObservationSource>(),
      &int_result));

  // The first 50 samples have very old timestamps.
  for (int i = 1; i <= 50; ++i) {
    time_delta_buffer.AddObservation(Observation<base::TimeDelta>(
        base::TimeDelta::FromMilliseconds(i), very_old,
        NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    int_buffer.AddObservation(Observation<int32_t>(
        i, very_old, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // The next 50 (i.e., from 51 to 100) samples have recent timestamps.
  for (int i = 51; i <= 100; ++i) {
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // The older samples have very little weight, and so the weighted average must
  // be approximately equal to the average of all recent samples.
  EXPECT_TRUE(time_delta_buffer.GetWeightedAverage(
      very_old, std::vector<NetworkQualityObservationSource>(),
      &time_delta_result));
  EXPECT_NEAR(time_delta_result.InMilliseconds(), (51 + 100) / 2, 1);

  EXPECT_TRUE(int_buffer.GetWeightedAverage(
      very_old, std::vector<NetworkQualityObservationSource>(), &int_result));
  EXPECT_NEAR(int_result, (51 + 100) / 2, 1);

  EXPECT_FALSE(time_delta_buffer.GetWeightedAverage(
      now + base::TimeDelta::FromSeconds(1),
      std::vector<NetworkQualityObservationSource>(), &time_delta_result));
  EXPECT_FALSE(int_buffer.GetWeightedAverage(
      now + base::TimeDelta::FromSeconds(1),
      std::vector<NetworkQualityObservationSource>(), &int_result));
}
#endif  // !defined(OS_WIN)

// Verifies that the percentiles are correctly computed when some of the
// observation sources are disallowed. All observations have the same timestamp.
TEST(NetworkQualityObservationBufferTest, DisallowedObservationSources) {
  ObservationBuffer<int32_t> int_buffer(0.5);
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  const base::TimeTicks now = base::TimeTicks::Now();

  int32_t result;
  base::TimeDelta time_delta_result;

  // Network quality should be unavailable when no observations are available.
  EXPECT_FALSE(
      int_buffer.GetPercentile(base::TimeTicks(), &result, 50,
                               std::vector<NetworkQualityObservationSource>()));
  EXPECT_FALSE(time_delta_buffer.GetPercentile(
      base::TimeTicks(), &time_delta_result, 50,
      std::vector<NetworkQualityObservationSource>()));

  // Insert samples from {1,2,3,..., 100}. First insert odd samples, then even
  // samples. This helps in verifying that the order of samples does not matter.
  for (int i = 1; i <= 99; i += 2) {
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  // Add samples for TCP and QUIC observations which should not be taken into
  // account when computing the percentile.
  for (int i = 1; i <= 99; i += 2) {
    int_buffer.AddObservation(Observation<int32_t>(
        10000, now, NETWORK_QUALITY_OBSERVATION_SOURCE_TCP));
    int_buffer.AddObservation(Observation<int32_t>(
        10000, now, NETWORK_QUALITY_OBSERVATION_SOURCE_QUIC));
    time_delta_buffer.AddObservation(Observation<base::TimeDelta>(
        base::TimeDelta::FromMilliseconds(10000), now,
        NETWORK_QUALITY_OBSERVATION_SOURCE_TCP));
    time_delta_buffer.AddObservation(Observation<base::TimeDelta>(
        base::TimeDelta::FromMilliseconds(10000), now,
        NETWORK_QUALITY_OBSERVATION_SOURCE_QUIC));
  }

  for (int i = 2; i <= 100; i += 2) {
    int_buffer.AddObservation(
        Observation<int32_t>(i, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
    time_delta_buffer.AddObservation(
        Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(i), now,
                                     NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  }

  std::vector<NetworkQualityObservationSource> disallowed_observation_sources;
  disallowed_observation_sources.push_back(
      NETWORK_QUALITY_OBSERVATION_SOURCE_TCP);
  disallowed_observation_sources.push_back(
      NETWORK_QUALITY_OBSERVATION_SOURCE_QUIC);

  for (int i = 0; i <= 100; ++i) {
    // Checks if the difference between the two integers is less than 1. This is
    // required because computed percentiles may be slightly different from
    // what is expected due to floating point computation errors and integer
    // rounding off errors.
    EXPECT_TRUE(int_buffer.GetPercentile(base::TimeTicks(), &result, i,
                                         disallowed_observation_sources));
    EXPECT_NEAR(result, i, 1);
    EXPECT_TRUE(
        time_delta_buffer.GetPercentile(base::TimeTicks(), &time_delta_result,
                                        i, disallowed_observation_sources));
    EXPECT_NEAR(time_delta_result.InMilliseconds(), i, 1);
  }

  // Now check the percentile value for TCP and QUIC observations.
  disallowed_observation_sources.clear();
  disallowed_observation_sources.push_back(
      NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP);
  for (int i = 0; i <= 100; ++i) {
    // Checks if the difference between the two integers is less than 1. This is
    // required because computed percentiles may be slightly different from
    // what is expected due to floating point computation errors and integer
    // rounding off errors.
    EXPECT_TRUE(int_buffer.GetPercentile(base::TimeTicks(), &result, i,
                                         disallowed_observation_sources));
    EXPECT_NEAR(result, 10000, 1);
    EXPECT_TRUE(
        time_delta_buffer.GetPercentile(base::TimeTicks(), &time_delta_result,
                                        i, disallowed_observation_sources));
    EXPECT_NEAR(time_delta_result.InMilliseconds(), 10000, 1);
  }
}

TEST(NetworkQualityObservationBufferTest, TestGetMedianRTTSince) {
  ObservationBuffer<int32_t> int_buffer(0.5);
  ObservationBuffer<base::TimeDelta> time_delta_buffer(0.5);
  base::TimeTicks now = base::TimeTicks::Now();
  base::TimeTicks old = now - base::TimeDelta::FromMilliseconds(1);
  ASSERT_NE(old, now);

  // First sample has very old timestamp.
  int_buffer.AddObservation(
      Observation<int32_t>(1, old, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  time_delta_buffer.AddObservation(
      Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(1), old,
                                   NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));

  int_buffer.AddObservation(
      Observation<int32_t>(100, now, NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));
  time_delta_buffer.AddObservation(
      Observation<base::TimeDelta>(base::TimeDelta::FromMilliseconds(100), now,
                                   NETWORK_QUALITY_OBSERVATION_SOURCE_HTTP));

  const struct {
    base::TimeTicks start_timestamp;
    bool expect_network_quality_available;
    base::TimeDelta expected_url_request_rtt;
    int32_t expected_downstream_throughput;
  } tests[] = {
      {now + base::TimeDelta::FromSeconds(10), false,
       base::TimeDelta::FromMilliseconds(0), 0},
      {now, true, base::TimeDelta::FromMilliseconds(100), 100},
      {now - base::TimeDelta::FromMicroseconds(500), true,
       base::TimeDelta::FromMilliseconds(100), 100},

  };

  for (const auto& test : tests) {
    base::TimeDelta url_request_rtt;
    int32_t downstream_throughput_kbps;
    std::vector<NetworkQualityObservationSource> disallowed_observation_sources;

    EXPECT_EQ(
        test.expect_network_quality_available,
        time_delta_buffer.GetPercentile(test.start_timestamp, &url_request_rtt,
                                        50, disallowed_observation_sources));
    EXPECT_EQ(test.expect_network_quality_available,
              int_buffer.GetPercentile(test.start_timestamp,
                                       &downstream_throughput_kbps, 50,
                                       disallowed_observation_sources));

    if (test.expect_network_quality_available) {
      EXPECT_EQ(test.expected_url_request_rtt, url_request_rtt);
      EXPECT_EQ(test.expected_downstream_throughput,
                downstream_throughput_kbps);
    }
  }
}

}  // namespace

}  // namespace internal

}  // namespace nqe

}  // namespace net