/*
 * Copyright (c) Facebook, Inc. and its affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <folly/stats/TimeseriesHistogram.h>

#include <random>

#include <folly/portability/GTest.h>

using namespace folly;
using std::chrono::seconds;

namespace {
namespace IntMTMHTS {
enum Levels {
  MINUTE,
  TEN_MINUTE,
  HOUR,
  ALLTIME,
  NUM_LEVELS,
};

const seconds kDurations[] = {
    seconds(60),
    seconds(600),
    seconds(3600),
    seconds(0),
};
} // namespace IntMTMHTS

namespace IntMHTS {
enum Levels {
  MINUTE,
  HOUR,
  ALLTIME,
  NUM_LEVELS,
};

const seconds kDurations[] = {
    seconds(60),
    seconds(3600),
    seconds(0),
};
} // namespace IntMHTS

typedef std::mt19937 RandomInt32;

using StatsClock = folly::LegacyStatsClock<std::chrono::seconds>;
StatsClock::time_point mkTimePoint(int value) {
  return StatsClock::time_point(StatsClock::duration(value));
}
} // namespace

TEST(TimeseriesHistogram, Percentile) {
  RandomInt32 random(5);
  // [10, 109], 12 buckets including above and below
  {
    TimeseriesHistogram<int> h(
        10,
        10,
        110,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    EXPECT_EQ(0, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));

    EXPECT_EQ(12, h.getNumBuckets());
    EXPECT_EQ(10, h.getBucketSize());
    EXPECT_EQ(10, h.getMin());
    EXPECT_EQ(110, h.getMax());

    for (size_t i = 0; i < h.getNumBuckets(); ++i) {
      EXPECT_EQ(4, h.getBucket(i).numLevels());
    }

    int maxVal = 120;
    h.addValue(mkTimePoint(0), 0);
    h.addValue(mkTimePoint(0), maxVal);
    for (int i = 0; i < 98; i++) {
      h.addValue(mkTimePoint(0), random() % maxVal);
    }

    h.update(mkTimePoint(1500000000));
    // bucket 0 stores everything below min, so its minimum
    // is the lowest possible number
    EXPECT_EQ(
        std::numeric_limits<int>::min(),
        h.getPercentileBucketMin(1, IntMTMHTS::ALLTIME));
    EXPECT_EQ(110, h.getPercentileBucketMin(99, IntMTMHTS::ALLTIME));

    EXPECT_EQ(-2, h.getPercentileEstimate(0, IntMTMHTS::ALLTIME));
    EXPECT_EQ(-1, h.getPercentileEstimate(1, IntMTMHTS::ALLTIME));
    EXPECT_EQ(119, h.getPercentileEstimate(99, IntMTMHTS::ALLTIME));
    EXPECT_EQ(120, h.getPercentileEstimate(100, IntMTMHTS::ALLTIME));
  }
}

TEST(TimeseriesHistogram, String) {
  RandomInt32 random(5);
  // [10, 109], 12 buckets including above and below
  {
    TimeseriesHistogram<int> hist(
        10,
        10,
        110,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    int maxVal = 120;
    hist.addValue(mkTimePoint(0), 0);
    hist.addValue(mkTimePoint(0), maxVal);
    for (int i = 0; i < 98; i++) {
      hist.addValue(mkTimePoint(0), random() % maxVal);
    }

    hist.update(mkTimePoint(0));

    const char* const kStringValues1[IntMTMHTS::NUM_LEVELS] = {
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
    };

    CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());

    for (size_t level = 0; level < hist.getNumLevels(); ++level) {
      EXPECT_EQ(kStringValues1[level], hist.getString(level));
    }

    const char* const kStringValues2[IntMTMHTS::NUM_LEVELS] = {
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
        "-2147483648:12:4,10:8:13,20:8:24,30:6:34,40:13:46,50:8:54,60:7:64,"
        "70:7:74,80:8:84,90:10:94,100:3:103,110:10:115",
    };

    CHECK_EQ(IntMTMHTS::NUM_LEVELS, hist.getNumLevels());

    for (size_t level = 0; level < hist.getNumLevels(); ++level) {
      EXPECT_EQ(kStringValues2[level], hist.getString(level));
    }
  }
}

TEST(TimeseriesHistogram, Clear) {
  {
    TimeseriesHistogram<int> hist(
        10,
        0,
        100,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    for (int now = 0; now < 3600; now++) {
      for (int i = 0; i < 100; i++) {
        hist.addValue(mkTimePoint(now), i, 2); // adds each item 2 times
      }
    }

    // check clearing
    hist.clear();

    for (size_t b = 0; b < hist.getNumBuckets(); ++b) {
      EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::MINUTE));
      EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::HOUR));
      EXPECT_EQ(0, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
    }

    for (int pct = 0; pct <= 100; pct++) {
      EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
      EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
      EXPECT_EQ(0, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));

      EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::MINUTE));
      EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::HOUR));
      EXPECT_EQ(0, hist.getPercentileEstimate(pct, IntMTMHTS::ALLTIME));
    }
  }
}

TEST(TimeseriesHistogram, Basic) {
  {
    TimeseriesHistogram<int> hist(
        10,
        0,
        100,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    for (int now = 0; now < 3600; now++) {
      for (int i = 0; i < 100; i++) {
        hist.addValue(mkTimePoint(now), i);
      }
    }

    hist.update(mkTimePoint(3599));
    for (int pct = 1; pct <= 100; pct++) {
      int expected = (pct - 1) / 10 * 10;
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
      EXPECT_EQ(
          expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
    }

    for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
      EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
      EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
      EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
    }
    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
    EXPECT_EQ(
        0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));

    EXPECT_EQ(6000, hist.count(IntMTMHTS::MINUTE));
    EXPECT_EQ(60000, hist.count(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(360000, hist.count(IntMTMHTS::HOUR));
    EXPECT_EQ(360000, hist.count(IntMTMHTS::ALLTIME));

    // Each second we added 4950 total over 100 data points
    EXPECT_EQ(297000, hist.sum(IntMTMHTS::MINUTE));
    EXPECT_EQ(2970000, hist.sum(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(17820000, hist.sum(IntMTMHTS::HOUR));
    EXPECT_EQ(17820000, hist.sum(IntMTMHTS::ALLTIME));

    EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::MINUTE));
    EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::HOUR));
    EXPECT_EQ(49, hist.avg<int>(IntMTMHTS::ALLTIME));
    EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::MINUTE));
    EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::HOUR));
    EXPECT_EQ(49.5, hist.avg<double>(IntMTMHTS::ALLTIME));

    EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::MINUTE));
    EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::HOUR));
    EXPECT_EQ(4950, hist.rate<int>(IntMTMHTS::ALLTIME));
    EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::MINUTE));
    EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::HOUR));
    EXPECT_EQ(4950, hist.rate<double>(IntMTMHTS::ALLTIME));

    EXPECT_EQ(1000, hist.count(mkTimePoint(10), mkTimePoint(20)));
    EXPECT_EQ(49500, hist.sum(mkTimePoint(10), mkTimePoint(20)));
    EXPECT_EQ(4950, hist.rate(mkTimePoint(10), mkTimePoint(20)));
    EXPECT_EQ(49.5, hist.avg<double>(mkTimePoint(10), mkTimePoint(20)));

    EXPECT_EQ(200, hist.count(mkTimePoint(3550), mkTimePoint(3552)));
    EXPECT_EQ(9900, hist.sum(mkTimePoint(3550), mkTimePoint(3552)));
    EXPECT_EQ(4950, hist.rate(mkTimePoint(3550), mkTimePoint(3552)));
    EXPECT_EQ(49.5, hist.avg<double>(mkTimePoint(3550), mkTimePoint(3552)));

    EXPECT_EQ(0, hist.count(mkTimePoint(4550), mkTimePoint(4552)));
    EXPECT_EQ(0, hist.sum(mkTimePoint(4550), mkTimePoint(4552)));
    EXPECT_EQ(0, hist.rate(mkTimePoint(4550), mkTimePoint(4552)));
    EXPECT_EQ(0, hist.avg<double>(mkTimePoint(4550), mkTimePoint(4552)));
  }

  // -----------------

  {
    TimeseriesHistogram<int> hist(
        10,
        0,
        100,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    for (int now = 0; now < 3600; now++) {
      for (int i = 0; i < 100; i++) {
        hist.addValue(mkTimePoint(now), i, 2); // adds each item 2 times
      }
    }

    hist.update(mkTimePoint(3599));
    for (int pct = 1; pct <= 100; pct++) {
      int expected = (pct - 1) / 10 * 10;
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
      EXPECT_EQ(
          expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
    }

    for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
      EXPECT_EQ(600 * 2, hist.getBucket(b).count(IntMTMHTS::MINUTE));
      EXPECT_EQ(6000 * 2, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::HOUR));
      EXPECT_EQ(36000 * 2, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
    }
    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
    EXPECT_EQ(
        0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));
  }

  // -----------------

  {
    TimeseriesHistogram<int> hist(
        10,
        0,
        100,
        MultiLevelTimeSeries<int>(
            60, IntMTMHTS::NUM_LEVELS, IntMTMHTS::kDurations));

    for (int now = 0; now < 3600; now++) {
      for (int i = 0; i < 50; i++) {
        hist.addValue(mkTimePoint(now), i * 2, 2); // adds each item 2 times
      }
    }

    hist.update(mkTimePoint(3599));
    for (int pct = 1; pct <= 100; pct++) {
      int expected = (pct - 1) / 10 * 10;
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::MINUTE));
      EXPECT_EQ(
          expected, hist.getPercentileBucketMin(pct, IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::HOUR));
      EXPECT_EQ(expected, hist.getPercentileBucketMin(pct, IntMTMHTS::ALLTIME));
    }

    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::MINUTE));
    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::HOUR));
    EXPECT_EQ(0, hist.getBucket(0).count(IntMTMHTS::ALLTIME));
    EXPECT_EQ(
        0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::MINUTE));
    EXPECT_EQ(
        0,
        hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::TEN_MINUTE));
    EXPECT_EQ(
        0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::HOUR));
    EXPECT_EQ(
        0, hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::ALLTIME));

    for (size_t b = 1; (b + 1) < hist.getNumBuckets(); ++b) {
      EXPECT_EQ(600, hist.getBucket(b).count(IntMTMHTS::MINUTE));
      EXPECT_EQ(6000, hist.getBucket(b).count(IntMTMHTS::TEN_MINUTE));
      EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::HOUR));
      EXPECT_EQ(36000, hist.getBucket(b).count(IntMTMHTS::ALLTIME));
    }

    for (int i = 0; i < 100; ++i) {
      hist.addValue(mkTimePoint(3599), 200 + i);
    }
    hist.update(mkTimePoint(3599));
    EXPECT_EQ(
        100,
        hist.getBucket(hist.getNumBuckets() - 1).count(IntMTMHTS::ALLTIME));
  }
}

TEST(TimeseriesHistogram, QueryByInterval) {
  TimeseriesHistogram<int> mhts(
      8,
      8,
      120,
      MultiLevelTimeSeries<int>(60, IntMHTS::NUM_LEVELS, IntMHTS::kDurations));

  mhts.update(mkTimePoint(0));

  int curTime;
  for (curTime = 0; curTime < 7200; curTime++) {
    mhts.addValue(mkTimePoint(curTime), 1);
  }
  for (curTime = 7200; curTime < 7200 + 3540; curTime++) {
    mhts.addValue(mkTimePoint(curTime), 10);
  }
  for (curTime = 7200 + 3540; curTime < 7200 + 3600; curTime++) {
    mhts.addValue(mkTimePoint(curTime), 100);
  }

  mhts.update(mkTimePoint(7200 + 3600 - 1));

  struct TimeInterval {
    TimeInterval(int s, int e) : start(mkTimePoint(s)), end(mkTimePoint(e)) {}

    StatsClock::time_point start;
    StatsClock::time_point end;
  };
  TimeInterval intervals[12] = {
      {curTime - 60, curTime},
      {curTime - 3600, curTime},
      {curTime - 7200, curTime},
      {curTime - 3600, curTime - 60},
      {curTime - 7200, curTime - 60},
      {curTime - 7200, curTime - 3600},
      {curTime - 50, curTime - 20},
      {curTime - 3020, curTime - 20},
      {curTime - 7200, curTime - 20},
      {curTime - 3000, curTime - 1000},
      {curTime - 7200, curTime - 1000},
      {curTime - 7200, curTime - 3600},
  };

  int expectedSums[12] = {
      6000,
      41400,
      32400,
      35400,
      32129,
      16200,
      3000,
      33600,
      32308,
      20000,
      27899,
      16200,
  };

  int expectedCounts[12] = {
      60,
      3600,
      7200,
      3540,
      7139,
      3600,
      30,
      3000,
      7178,
      2000,
      6199,
      3600,
  };

  // The first 7200 values added all fell below the histogram minimum,
  // and went into the bucket that tracks all of the too-small values.
  // This bucket reports a minimum value of the smallest possible integer.
  int belowMinBucket = std::numeric_limits<int>::min();

  int expectedValues[12][3] = {
      {96, 96, 96},
      {8, 8, 96},
      {belowMinBucket, belowMinBucket, 8}, // alltime
      {8, 8, 8},
      {belowMinBucket, belowMinBucket, 8}, // alltime
      {belowMinBucket, belowMinBucket, 8}, // alltime
      {96, 96, 96},
      {8, 8, 96},
      {belowMinBucket, belowMinBucket, 8}, // alltime
      {8, 8, 8},
      {belowMinBucket, belowMinBucket, 8}, // alltime
      {belowMinBucket, belowMinBucket, 8} // alltime
  };

  for (int i = 0; i < 12; i++) {
    const auto& itv = intervals[i];
    int s = mhts.sum(itv.start, itv.end);
    EXPECT_EQ(expectedSums[i], s);

    int c = mhts.count(itv.start, itv.end);
    EXPECT_EQ(expectedCounts[i], c);
  }

  // 3 levels
  for (int i = 1; i <= 100; i++) {
    EXPECT_EQ(96, mhts.getPercentileBucketMin(i, 0));
    EXPECT_EQ(
        96,
        mhts.getPercentileBucketMin(
            i, mkTimePoint(curTime - 60), mkTimePoint(curTime)));
    EXPECT_EQ(
        8,
        mhts.getPercentileBucketMin(
            i, mkTimePoint(curTime - 3540), mkTimePoint(curTime - 60)));
  }

  EXPECT_EQ(8, mhts.getPercentileBucketMin(1, 1));
  EXPECT_EQ(8, mhts.getPercentileBucketMin(98, 1));
  EXPECT_EQ(96, mhts.getPercentileBucketMin(99, 1));
  EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 1));

  EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(1, 2));
  EXPECT_EQ(belowMinBucket, mhts.getPercentileBucketMin(66, 2));
  EXPECT_EQ(8, mhts.getPercentileBucketMin(67, 2));
  EXPECT_EQ(8, mhts.getPercentileBucketMin(99, 2));
  EXPECT_EQ(96, mhts.getPercentileBucketMin(100, 2));

  // 0 is currently the value for bucket 0 (below min)
  for (int i = 0; i < 12; i++) {
    const auto& itv = intervals[i];
    int v = mhts.getPercentileBucketMin(1, itv.start, itv.end);
    EXPECT_EQ(expectedValues[i][0], v);

    v = mhts.getPercentileBucketMin(50, itv.start, itv.end);
    EXPECT_EQ(expectedValues[i][1], v);

    v = mhts.getPercentileBucketMin(99, itv.start, itv.end);
    EXPECT_EQ(expectedValues[i][2], v);
  }

  for (int i = 0; i < 12; i++) {
    const auto& itv = intervals[i];
    // Some of the older intervals that fall in the alltime bucket
    // are off by 1 or 2 in their estimated counts.
    size_t tolerance = 0;
    if (itv.start <= mkTimePoint(curTime - 7200)) {
      tolerance = 2;
    } else if (itv.start <= mkTimePoint(curTime - 3000)) {
      tolerance = 1;
    }
    size_t actualCount = (itv.end - itv.start).count();
    size_t estimatedCount = mhts.count(itv.start, itv.end);
    EXPECT_GE(actualCount, estimatedCount);
    EXPECT_LE(actualCount - tolerance, estimatedCount);
  }
}
