// Copyright 2015 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 <stddef.h>
#include <stdint.h>

#include <string>
#include <vector>

#include "base/bind.h"
#include "base/callback_helpers.h"
#include "base/containers/circular_deque.h"
#include "base/test/simple_test_tick_clock.h"
#include "media/base/fake_single_thread_task_runner.h"
#include "media/base/test_random.h"
#include "media/blink/multibuffer.h"
#include "media/blink/multibuffer_reader.h"
#include "testing/gtest/include/gtest/gtest.h"

const int kBlockSizeShift = 8;
const size_t kBlockSize = 1UL << kBlockSizeShift;

namespace media {

class FakeMultiBufferDataProvider;

namespace {
std::vector<FakeMultiBufferDataProvider*> writers;
}  // namespace

class FakeMultiBufferDataProvider : public MultiBuffer::DataProvider {
 public:
  FakeMultiBufferDataProvider(MultiBufferBlockId pos,
                              size_t file_size,
                              int max_blocks_after_defer,
                              bool must_read_whole_file,
                              MultiBuffer* multibuffer,
                              TestRandom* rnd)
      : pos_(pos),
        blocks_until_deferred_(1 << 30),
        max_blocks_after_defer_(max_blocks_after_defer),
        file_size_(file_size),
        must_read_whole_file_(must_read_whole_file),
        multibuffer_(multibuffer),
        rnd_(rnd) {
    writers.push_back(this);
  }

  ~FakeMultiBufferDataProvider() override {
    if (must_read_whole_file_) {
      CHECK_GE(pos_ * kBlockSize, file_size_);
    }
    for (size_t i = 0; i < writers.size(); i++) {
      if (writers[i] == this) {
        writers[i] = writers.back();
        writers.pop_back();
        return;
      }
    }
    LOG(FATAL) << "Couldn't find myself in writers!";
  }

  MultiBufferBlockId Tell() const override { return pos_; }

  bool Available() const override { return !fifo_.empty(); }
  int64_t AvailableBytes() const override { return 0; }

  scoped_refptr<DataBuffer> Read() override {
    DCHECK(Available());
    scoped_refptr<DataBuffer> ret = fifo_.front();
    fifo_.pop_front();
    ++pos_;
    return ret;
  }

  void SetDeferred(bool deferred) override {
    if (deferred) {
      if (max_blocks_after_defer_ > 0) {
        blocks_until_deferred_ = rnd_->Rand() % max_blocks_after_defer_;
      } else if (max_blocks_after_defer_ < 0) {
        blocks_until_deferred_ = -max_blocks_after_defer_;
      } else {
        blocks_until_deferred_ = 0;
      }
    } else {
      blocks_until_deferred_ = 1 << 30;
    }
  }

  bool Advance() {
    if (blocks_until_deferred_ == 0)
      return false;
    --blocks_until_deferred_;

    bool ret = true;
    scoped_refptr<DataBuffer> block = new DataBuffer(kBlockSize);
    size_t x = 0;
    size_t byte_pos = (fifo_.size() + pos_) * kBlockSize;
    for (x = 0; x < kBlockSize; x++, byte_pos++) {
      if (byte_pos >= file_size_)
        break;
      block->writable_data()[x] =
          static_cast<uint8_t>((byte_pos * 15485863) >> 16);
    }
    block->set_data_size(static_cast<int>(x));
    fifo_.push_back(block);
    if (byte_pos == file_size_) {
      fifo_.push_back(DataBuffer::CreateEOSBuffer());
      ret = false;
    }
    multibuffer_->OnDataProviderEvent(this);
    return ret;
  }

 private:
  base::circular_deque<scoped_refptr<DataBuffer>> fifo_;
  MultiBufferBlockId pos_;
  int32_t blocks_until_deferred_;
  int32_t max_blocks_after_defer_;
  size_t file_size_;
  bool must_read_whole_file_;
  MultiBuffer* multibuffer_;
  TestRandom* rnd_;
};

class TestMultiBuffer : public MultiBuffer {
 public:
  explicit TestMultiBuffer(int32_t shift,
                           const scoped_refptr<MultiBuffer::GlobalLRU>& lru,
                           TestRandom* rnd)
      : MultiBuffer(shift, lru),
        range_supported_(false),
        create_ok_(true),
        max_writers_(10000),
        file_size_(1 << 30),
        max_blocks_after_defer_(0),
        must_read_whole_file_(false),
        writers_created_(0),
        rnd_(rnd) {}

  void SetMaxWriters(size_t max_writers) { max_writers_ = max_writers; }

  void CheckPresentState() {
    IntervalMap<MultiBufferBlockId, int32_t> tmp;
    for (auto i = data_.begin(); i != data_.end(); ++i) {
      CHECK(i->second);  // Null poineters are not allowed in data_
      CHECK_NE(!!pinned_[i->first], lru_->Contains(this, i->first))
          << " i->first = " << i->first;
      tmp.IncrementInterval(i->first, i->first + 1, 1);
    }
    IntervalMap<MultiBufferBlockId, int32_t>::const_iterator tmp_iterator =
        tmp.begin();
    IntervalMap<MultiBufferBlockId, int32_t>::const_iterator present_iterator =
        present_.begin();
    while (tmp_iterator != tmp.end() && present_iterator != present_.end()) {
      EXPECT_EQ(tmp_iterator.interval_begin(),
                present_iterator.interval_begin());
      EXPECT_EQ(tmp_iterator.interval_end(), present_iterator.interval_end());
      EXPECT_EQ(tmp_iterator.value(), present_iterator.value());
      ++tmp_iterator;
      ++present_iterator;
    }
    EXPECT_TRUE(tmp_iterator == tmp.end());
    EXPECT_TRUE(present_iterator == present_.end());
  }

  void CheckLRUState() {
    for (auto i = data_.begin(); i != data_.end(); ++i) {
      CHECK(i->second);  // Null poineters are not allowed in data_
      CHECK_NE(!!pinned_[i->first], lru_->Contains(this, i->first))
          << " i->first = " << i->first;
      CHECK_EQ(1, present_[i->first]) << " i->first = " << i->first;
    }
  }

  void SetFileSize(size_t file_size) { file_size_ = file_size; }

  void SetMaxBlocksAfterDefer(int32_t max_blocks_after_defer) {
    max_blocks_after_defer_ = max_blocks_after_defer;
  }

  void SetMustReadWholeFile(bool must_read_whole_file) {
    must_read_whole_file_ = must_read_whole_file;
  }

  int32_t writers_created() const { return writers_created_; }

  void SetRangeSupported(bool supported) { range_supported_ = supported; }

 protected:
  std::unique_ptr<DataProvider> CreateWriter(const MultiBufferBlockId& pos,
                                             bool) override {
    DCHECK(create_ok_);
    writers_created_++;
    CHECK_LT(writers.size(), max_writers_);
    return std::unique_ptr<DataProvider>(new FakeMultiBufferDataProvider(
        pos, file_size_, max_blocks_after_defer_, must_read_whole_file_, this,
        rnd_));
  }
  void Prune(size_t max_to_free) override {
    // Prune should not cause additional writers to be spawned.
    create_ok_ = false;
    MultiBuffer::Prune(max_to_free);
    create_ok_ = true;
  }

  bool RangeSupported() const override { return range_supported_; }

 private:
  bool range_supported_;
  bool create_ok_;
  size_t max_writers_;
  size_t file_size_;
  int32_t max_blocks_after_defer_;
  bool must_read_whole_file_;
  int32_t writers_created_;
  TestRandom* rnd_;
};

class MultiBufferTest : public testing::Test {
 public:
  MultiBufferTest()
      : rnd_(42),
        task_runner_(new FakeSingleThreadTaskRunner(&clock_)),
        lru_(new MultiBuffer::GlobalLRU(task_runner_)),
        multibuffer_(kBlockSizeShift, lru_, &rnd_) {}

  void TearDown() override {
    // Make sure we have nothing left to prune.
    lru_->Prune(1000000);
    // Run the outstanding callback to make sure everything is freed.
    task_runner_->Sleep(base::TimeDelta::FromSeconds(30));
  }

  void Advance() {
    CHECK(writers.size());
    writers[rnd_.Rand() % writers.size()]->Advance();
  }

  bool AdvanceAll() {
    bool advanced = false;
    for (size_t i = 0; i < writers.size(); i++) {
      advanced |= writers[i]->Advance();
    }
    multibuffer_.CheckLRUState();
    return advanced;
  }

 protected:
  TestRandom rnd_;
  base::SimpleTestTickClock clock_;
  scoped_refptr<FakeSingleThreadTaskRunner> task_runner_;
  scoped_refptr<MultiBuffer::GlobalLRU> lru_;
  TestMultiBuffer multibuffer_;
};

TEST_F(MultiBufferTest, ReadAll) {
  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  multibuffer_.SetMustReadWholeFile(true);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPinRange(2000, 5000);
  reader.SetPreload(1000, 1000);
  while (pos < end) {
    unsigned char buffer[27];
    buffer[17] = 17;
    size_t to_read = std::min<size_t>(end - pos, 17);
    int64_t bytes_read = reader.TryRead(buffer, to_read);
    if (bytes_read) {
      EXPECT_EQ(buffer[17], 17);
      for (int64_t i = 0; i < bytes_read; i++) {
        uint8_t expected = static_cast<uint8_t>((pos * 15485863) >> 16);
        EXPECT_EQ(expected, buffer[i]) << " pos = " << pos;
        pos++;
      }
    } else {
      Advance();
    }
  }
}

TEST_F(MultiBufferTest, ReadAllAdvanceFirst) {
  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  multibuffer_.SetMustReadWholeFile(true);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPinRange(2000, 5000);
  reader.SetPreload(1000, 1000);
  while (pos < end) {
    unsigned char buffer[27];
    buffer[17] = 17;
    size_t to_read = std::min<size_t>(end - pos, 17);
    while (AdvanceAll()) {
    }
    int64_t bytes = reader.TryRead(buffer, to_read);
    EXPECT_GT(bytes, 0);
    EXPECT_EQ(buffer[17], 17);
    for (int64_t i = 0; i < bytes; i++) {
      uint8_t expected = static_cast<uint8_t>((pos * 15485863) >> 16);
      EXPECT_EQ(expected, buffer[i]) << " pos = " << pos;
      pos++;
    }
  }
}

// Checks that if the data provider provides too much data after we told it
// to defer, we kill it.
TEST_F(MultiBufferTest, ReadAllAdvanceFirst_NeverDefer) {
  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  multibuffer_.SetMaxBlocksAfterDefer(-10000);
  multibuffer_.SetRangeSupported(true);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPinRange(2000, 5000);
  reader.SetPreload(1000, 1000);
  while (pos < end) {
    unsigned char buffer[27];
    buffer[17] = 17;
    size_t to_read = std::min<size_t>(end - pos, 17);
    while (AdvanceAll()) {
    }
    int64_t bytes = reader.TryRead(buffer, to_read);
    EXPECT_GT(bytes, 0);
    EXPECT_EQ(buffer[17], 17);
    for (int64_t i = 0; i < bytes; i++) {
      uint8_t expected = static_cast<uint8_t>((pos * 15485863) >> 16);
      EXPECT_EQ(expected, buffer[i]) << " pos = " << pos;
      pos++;
    }
  }
  EXPECT_GT(multibuffer_.writers_created(), 1);
}

// Same as ReadAllAdvanceFirst_NeverDefer, but the url doesn't support
// ranges, so we don't destroy it no matter how much data it provides.
TEST_F(MultiBufferTest, ReadAllAdvanceFirst_NeverDefer2) {
  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  multibuffer_.SetMustReadWholeFile(true);
  multibuffer_.SetMaxBlocksAfterDefer(-10000);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPinRange(2000, 5000);
  reader.SetPreload(1000, 1000);
  while (pos < end) {
    unsigned char buffer[27];
    buffer[17] = 17;
    size_t to_read = std::min<size_t>(end - pos, 17);
    while (AdvanceAll()) {
    }
    int64_t bytes = reader.TryRead(buffer, to_read);
    EXPECT_GT(bytes, 0);
    EXPECT_EQ(buffer[17], 17);
    for (int64_t i = 0; i < bytes; i++) {
      uint8_t expected = static_cast<uint8_t>((pos * 15485863) >> 16);
      EXPECT_EQ(expected, buffer[i]) << " pos = " << pos;
      pos++;
    }
  }
}

TEST_F(MultiBufferTest, LRUTest) {
  int64_t max_size = 17;
  int64_t current_size = 0;
  lru_->IncrementMaxSize(max_size);

  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPreload(10000, 10000);
  // Note, no pinning, all data should end up in LRU.
  EXPECT_EQ(current_size, lru_->Size());
  current_size += max_size;
  while (AdvanceAll()) {
  }
  EXPECT_EQ(current_size, lru_->Size());
  lru_->IncrementMaxSize(-max_size);
  lru_->Prune(3);
  current_size -= 3;
  EXPECT_EQ(current_size, lru_->Size());
  lru_->Prune(3);
  current_size -= 3;
  EXPECT_EQ(current_size, lru_->Size());
  lru_->Prune(1000);
  EXPECT_EQ(0, lru_->Size());
}

TEST_F(MultiBufferTest, LRUTest2) {
  int64_t max_size = 17;
  int64_t current_size = 0;
  lru_->IncrementMaxSize(max_size);

  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPreload(10000, 10000);
  // Note, no pinning, all data should end up in LRU.
  EXPECT_EQ(current_size, lru_->Size());
  current_size += max_size;
  while (AdvanceAll()) {
  }
  EXPECT_EQ(current_size, lru_->Size());
  // Pruning shouldn't do anything here, because LRU is small enough already.
  lru_->Prune(3);
  EXPECT_EQ(current_size, lru_->Size());
  // However TryFree should still work
  lru_->TryFree(3);
  current_size -= 3;
  EXPECT_EQ(current_size, lru_->Size());
  lru_->TryFreeAll();
  EXPECT_EQ(0, lru_->Size());
  lru_->IncrementMaxSize(-max_size);
}

TEST_F(MultiBufferTest, LRUTestExpirationTest) {
  int64_t max_size = 17;
  int64_t current_size = 0;
  lru_->IncrementMaxSize(max_size);

  multibuffer_.SetMaxWriters(1);
  size_t pos = 0;
  size_t end = 10000;
  multibuffer_.SetFileSize(10000);
  MultiBufferReader reader(&multibuffer_, pos, end,
                           base::Callback<void(int64_t, int64_t)>());
  reader.SetPreload(10000, 10000);
  // Note, no pinning, all data should end up in LRU.
  EXPECT_EQ(current_size, lru_->Size());
  current_size += max_size;
  while (AdvanceAll()) {
  }
  EXPECT_EQ(current_size, lru_->Size());
  EXPECT_FALSE(lru_->Pruneable());

  // Make 3 packets pruneable.
  lru_->IncrementMaxSize(-3);
  max_size -= 3;

  // There should be no change after 29 seconds.
  task_runner_->Sleep(base::TimeDelta::FromSeconds(29));
  EXPECT_EQ(current_size, lru_->Size());
  EXPECT_TRUE(lru_->Pruneable());

  // After 30 seconds, pruning should have happened.
  task_runner_->Sleep(base::TimeDelta::FromSeconds(30));
  current_size -= 3;
  EXPECT_EQ(current_size, lru_->Size());
  EXPECT_FALSE(lru_->Pruneable());

  // Make the rest of the packets pruneable.
  lru_->IncrementMaxSize(-max_size);

  // After another 30 seconds, everything should be pruned.
  task_runner_->Sleep(base::TimeDelta::FromSeconds(30));
  EXPECT_EQ(0, lru_->Size());
  EXPECT_FALSE(lru_->Pruneable());
}

class ReadHelper {
 public:
  ReadHelper(size_t end,
             size_t max_read_size,
             MultiBuffer* multibuffer,
             TestRandom* rnd)
      : pos_(0),
        end_(end),
        max_read_size_(max_read_size),
        read_size_(0),
        rnd_(rnd),
        reader_(multibuffer,
                pos_,
                end_,
                base::Callback<void(int64_t, int64_t)>()) {
    reader_.SetPinRange(2000, 5000);
    reader_.SetPreload(1000, 1000);
  }

  bool Read() {
    if (read_size_ == 0)
      return true;
    unsigned char buffer[4096];
    CHECK_LE(read_size_, static_cast<int64_t>(sizeof(buffer)));
    CHECK_EQ(pos_, reader_.Tell());
    int64_t bytes_read = reader_.TryRead(buffer, read_size_);
    if (bytes_read) {
      for (int64_t i = 0; i < bytes_read; i++) {
        unsigned char expected = (pos_ * 15485863) >> 16;
        EXPECT_EQ(expected, buffer[i]) << " pos = " << pos_;
        pos_++;
      }
      CHECK_EQ(pos_, reader_.Tell());
      return true;
    }
    return false;
  }

  void StartRead() {
    CHECK_EQ(pos_, reader_.Tell());
    read_size_ = std::min(1 + rnd_->Rand() % (max_read_size_ - 1), end_ - pos_);
    if (!Read()) {
      reader_.Wait(read_size_,
                   base::Bind(&ReadHelper::WaitCB, base::Unretained(this)));
    }
  }

  void WaitCB() { CHECK(Read()); }

  void Seek() {
    pos_ = rnd_->Rand() % end_;
    reader_.Seek(pos_);
    CHECK_EQ(pos_, reader_.Tell());
  }

 private:
  int64_t pos_;
  int64_t end_;
  int64_t max_read_size_;
  int64_t read_size_;
  TestRandom* rnd_;
  MultiBufferReader reader_;
};

TEST_F(MultiBufferTest, RandomTest) {
  size_t file_size = 1000000;
  multibuffer_.SetFileSize(file_size);
  multibuffer_.SetMaxBlocksAfterDefer(10);
  std::vector<ReadHelper*> read_helpers;
  for (size_t i = 0; i < 20; i++) {
    read_helpers.push_back(
        new ReadHelper(file_size, 1000, &multibuffer_, &rnd_));
  }
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
      if (rnd_.Rand() & 1) {
        if (!writers.empty())
          Advance();
      } else {
        size_t j = rnd_.Rand() % read_helpers.size();
        if (rnd_.Rand() % 100 < 3)
          read_helpers[j]->Seek();
        read_helpers[j]->StartRead();
      }
    }
    multibuffer_.CheckLRUState();
  }
  multibuffer_.CheckPresentState();
  while (!read_helpers.empty()) {
    delete read_helpers.back();
    read_helpers.pop_back();
  }
}

TEST_F(MultiBufferTest, RandomTest_RangeSupported) {
  size_t file_size = 1000000;
  multibuffer_.SetFileSize(file_size);
  multibuffer_.SetMaxBlocksAfterDefer(10);
  std::vector<ReadHelper*> read_helpers;
  multibuffer_.SetRangeSupported(true);
  for (size_t i = 0; i < 20; i++) {
    read_helpers.push_back(
        new ReadHelper(file_size, 1000, &multibuffer_, &rnd_));
  }
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < 100; j++) {
      if (rnd_.Rand() & 1) {
        if (!writers.empty())
          Advance();
      } else {
        size_t j = rnd_.Rand() % read_helpers.size();
        if (rnd_.Rand() % 100 < 3)
          read_helpers[j]->Seek();
        read_helpers[j]->StartRead();
      }
    }
    multibuffer_.CheckLRUState();
  }
  multibuffer_.CheckPresentState();
  while (!read_helpers.empty()) {
    delete read_helpers.back();
    read_helpers.pop_back();
  }
}

}  // namespace media