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

#include "content/browser/indexed_db/instance/leveldb/tombstone_sweeper.h"

#include <memory>
#include <string>
#include <utility>

#include "base/files/scoped_temp_dir.h"
#include "base/no_destructor.h"
#include "base/strings/string_number_conversions.h"
#include "base/test/task_environment.h"
#include "components/services/storage/indexed_db/leveldb/mock_level_db.h"
#include "components/services/storage/indexed_db/scopes/leveldb_scopes.h"
#include "components/services/storage/indexed_db/scopes/varint_coding.h"
#include "components/services/storage/indexed_db/transactional_leveldb/transactional_leveldb_database.h"
#include "components/services/storage/indexed_db/transactional_leveldb/transactional_leveldb_factory.h"
#include "content/browser/indexed_db/instance/leveldb/backing_store.h"
#include "content/browser/indexed_db/instance/leveldb/indexed_db_leveldb_operations.h"
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/gtest/include/gtest/gtest.h"
#include "third_party/blink/public/common/indexeddb/indexeddb_key.h"
#include "third_party/blink/public/common/indexeddb/indexeddb_key_path.h"
#include "third_party/blink/public/common/indexeddb/indexeddb_metadata.h"
#include "third_party/leveldatabase/env_chromium.h"
#include "third_party/leveldatabase/leveldb_chrome.h"
#include "third_party/leveldatabase/src/include/leveldb/db.h"
#include "third_party/leveldatabase/src/include/leveldb/filter_policy.h"
#include "third_party/leveldatabase/src/include/leveldb/slice.h"

namespace content::indexed_db::level_db {

using blink::IndexedDBDatabaseMetadata;
using blink::IndexedDBIndexMetadata;
using blink::IndexedDBKey;
using blink::IndexedDBKeyPath;
using blink::IndexedDBObjectStoreMetadata;
using ::testing::_;
using ::testing::Eq;
using ::testing::Return;
using ::testing::StrictMock;

constexpr int kRoundIterations = 11;
constexpr int kMaxIterations = 100;

constexpr int64_t kDb1 = 1;
constexpr int64_t kDb2 = 1;
constexpr int64_t kOs1 = 3;
constexpr int64_t kOs2 = 5;
constexpr int64_t kOs3 = 8;
constexpr int64_t kOs4 = 9;
constexpr int64_t kIndex1 = 31;
constexpr int64_t kIndex2 = 32;
constexpr int64_t kIndex3 = 35;

MATCHER_P(SliceEq,
          str,
          std::string(negation ? "isn't" : "is") + " equal to " +
              base::HexEncode(str.data(), str.size())) {
  *result_listener << "which is " << base::HexEncode(arg.data(), arg.size());
  return std::string(arg.data(), arg.size()) == str;
}

leveldb_env::Options GetLevelDBOptions() {
  leveldb_env::Options options;
  options.comparator = indexed_db::GetDefaultLevelDBComparator();
  options.create_if_missing = true;
  options.write_buffer_size = 4 * 1024 * 1024;
  options.paranoid_checks = true;

  static base::NoDestructor<leveldb_env::ChromiumEnv> g_leveldb_env;
  options.env = g_leveldb_env.get();

  return options;
}

class LevelDbTombstoneSweeperTest : public testing::Test {
 public:
  LevelDbTombstoneSweeperTest() = default;
  ~LevelDbTombstoneSweeperTest() override = default;

  void PopulateMultiDBMetdata() {
    // db1
    //   os1
    //   os2
    //     index1
    //     index2
    auto db1_ptr = std::make_unique<BackingStore::DatabaseMetadata>(u"db1");
    auto& db1 = *db1_ptr;
    db1.id = kDb1;
    db1.version = 1;
    db1.max_object_store_id = 29;
    db1.object_stores[kOs1] =
        IndexedDBObjectStoreMetadata(u"os1", kOs1, IndexedDBKeyPath(), false);
    db1.object_stores[kOs2] =
        IndexedDBObjectStoreMetadata(u"os2", kOs2, IndexedDBKeyPath(), false);
    auto& os2 = db1.object_stores[kOs2];
    os2.indexes[kIndex1] = IndexedDBIndexMetadata(
        u"index1", kIndex1, IndexedDBKeyPath(), true, false);
    os2.indexes[kIndex2] = IndexedDBIndexMetadata(
        u"index2", kIndex2, IndexedDBKeyPath(), true, false);
    metadata_.push_back(std::move(db1_ptr));
    // db2
    //   os3
    //     index3
    //   os4
    auto db2_ptr = std::make_unique<BackingStore::DatabaseMetadata>(u"db2");
    auto& db2 = *db2_ptr;
    db2.id = kDb2;
    db2.version = 1;
    db2.max_object_store_id = 29;
    db2.object_stores[kOs3] =
        IndexedDBObjectStoreMetadata(u"os3", kOs3, IndexedDBKeyPath(), false);
    db2.object_stores[kOs4] =
        IndexedDBObjectStoreMetadata(u"os4", kOs4, IndexedDBKeyPath(), false);
    auto& os3 = db2.object_stores[kOs3];
    os3.indexes[kIndex3] = IndexedDBIndexMetadata(
        u"index3", kIndex3, IndexedDBKeyPath(), true, false);
    metadata_.push_back(std::move(db2_ptr));
  }

  void PopulateSingleIndexDBMetadata() {
    // db1
    //   os1
    //     index1
    auto db1_ptr = std::make_unique<BackingStore::DatabaseMetadata>(u"db1");
    auto& db1 = *db1_ptr;
    db1.id = kDb1;
    db1.version = 1;
    db1.max_object_store_id = 29;
    db1.object_stores[kOs1] =
        IndexedDBObjectStoreMetadata(u"os1", kOs1, IndexedDBKeyPath(), false);
    auto& os2 = db1.object_stores[kOs1];
    os2.indexes[kIndex1] = IndexedDBIndexMetadata(
        u"index1", kIndex1, IndexedDBKeyPath(), true, false);
    metadata_.push_back(std::move(db1_ptr));
  }

  void SetupMockDB() {
    sweeper_ = std::make_unique<LevelDbTombstoneSweeper>(
        kRoundIterations, kMaxIterations, &mock_db_);
    sweeper_->SetStartSeedsForTesting(0, 0, 0);
  }

  void SetupRealDB() {
    leveldb_env::Options options = GetLevelDBOptions();
    std::unique_ptr<leveldb::Env> in_memory_env =
        leveldb_chrome::NewMemEnv("in-memory-testing-db", options.env);
    options.env = in_memory_env.get();

    std::unique_ptr<leveldb::DB> db;
    leveldb::Status s = leveldb_env::OpenDB(options, std::string(), &db);
    ASSERT_TRUE(s.ok());
    scoped_refptr<LevelDBState> level_db_state =
        LevelDBState::CreateForInMemoryDB(std::move(in_memory_env),
                                          options.comparator, std::move(db),
                                          "in-memory-testing-db");
    in_memory_db_ = DefaultTransactionalLevelDBFactory().CreateLevelDBDatabase(
        std::move(level_db_state), nullptr, nullptr,
        TransactionalLevelDBDatabase::kDefaultMaxOpenIteratorsPerDatabase);
    sweeper_ = std::make_unique<LevelDbTombstoneSweeper>(
        kRoundIterations, kMaxIterations, in_memory_db_->db());
    sweeper_->SetStartSeedsForTesting(0, 0, 0);
  }

  void ExpectIndexEntry(leveldb::MockIterator& iterator,
                        int64_t db,
                        int64_t os,
                        int64_t index,
                        const IndexedDBKey& index_key,
                        const IndexedDBKey& primary_key,
                        int index_version) {
    testing::InSequence sequence_enforcer;

    EXPECT_CALL(iterator, key())
        .WillOnce(Return(
            IndexDataKey::Encode(db, os, index, index_key, primary_key)));
    std::string value_str;
    EncodeVarInt(index_version, &value_str);
    EncodeIDBKey(primary_key, &value_str);
    EXPECT_CALL(iterator, value()).WillOnce(Return(value_str));
  }

  void ExpectIndexAndExistsEntries(leveldb::MockIterator& iterator,
                                   int64_t db,
                                   int64_t os,
                                   int64_t index,
                                   const IndexedDBKey& index_key,
                                   const IndexedDBKey& primary_key,
                                   int index_version,
                                   int exists_version) {
    ExpectIndexEntry(iterator, db, os, index, index_key, primary_key,
                     index_version);

    testing::InSequence sequence_enforcer;

    std::string encoded_primary_key;
    EncodeIDBKey(primary_key, &encoded_primary_key);

    std::string exists_value;
    EncodeVarInt(exists_version, &exists_value);
    EXPECT_CALL(
        mock_db_,
        Get(_, SliceEq(ExistsEntryKey::Encode(db, os, encoded_primary_key)), _))
        .WillOnce(testing::DoAll(testing::SetArgPointee<2>(exists_value),
                                 Return(leveldb::Status::OK())));
  }

 protected:
  std::unique_ptr<TransactionalLevelDBDatabase> in_memory_db_;
  leveldb::MockLevelDB mock_db_;

  std::vector<std::unique_ptr<IndexedDBDatabaseMetadata>> metadata_;

  std::unique_ptr<LevelDbTombstoneSweeper> sweeper_;

 private:
  base::test::TaskEnvironment task_environment_;
};

TEST_F(LevelDbTombstoneSweeperTest, EmptyDB) {
  SetupMockDB();
  sweeper_->SetMetadata(&metadata_);
  EXPECT_TRUE(sweeper_->RunRound());
}

TEST_F(LevelDbTombstoneSweeperTest, NoTombstonesComplexDB) {
  SetupMockDB();
  PopulateMultiDBMetdata();
  sweeper_->SetMetadata(&metadata_);

  // We'll have one index entry per index, and simulate reaching the end.
  leveldb::MockIterator* first_mock_iterator = new leveldb::MockIterator();
  leveldb::MockIterator* second_mock_iterator = new leveldb::MockIterator();
  leveldb::MockIterator* third_mock_iterator = new leveldb::MockIterator();
  EXPECT_CALL(mock_db_, NewIterator(testing::_))
      .WillOnce(testing::Return(first_mock_iterator))
      .WillOnce(testing::Return(second_mock_iterator))
      .WillOnce(testing::Return(third_mock_iterator));
  // First index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*first_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex1))));
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *first_mock_iterator, kDb1, kOs2, kIndex1,
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(20, blink::mojom::IDBKeyType::Number), 1, 1);
    EXPECT_CALL(*first_mock_iterator, Next());
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    // Return the beginning of the second index, which should cause us to error
    // & go restart our index seek.
    ExpectIndexEntry(*first_mock_iterator, kDb1, kOs2, kIndex2,
                     IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
                     IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1);
  }

  // Second index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*second_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex2))));
    EXPECT_CALL(*second_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *second_mock_iterator, kDb1, kOs2, kIndex2,
        IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1, 1);
    EXPECT_CALL(*second_mock_iterator, Next());
    // Return next key, which should make it error
    EXPECT_CALL(*second_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexEntry(*second_mock_iterator, kDb2, kOs3, kIndex3,
                     IndexedDBKey(1501, blink::mojom::IDBKeyType::Number),
                     IndexedDBKey(15123, blink::mojom::IDBKeyType::Number), 12);
  }

  // Third index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*third_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb2, kOs3, kIndex3))));
    EXPECT_CALL(*third_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *third_mock_iterator, kDb2, kOs3, kIndex3,
        IndexedDBKey(1501, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(15123, blink::mojom::IDBKeyType::Number), 12, 12);
    EXPECT_CALL(*third_mock_iterator, Next());
    // Return next key, which should make it error
    EXPECT_CALL(*third_mock_iterator, Valid()).WillOnce(Return(false));
    EXPECT_CALL(*third_mock_iterator, status())
        .WillOnce(Return(leveldb::Status::OK()));
    EXPECT_CALL(*third_mock_iterator, Valid()).WillOnce(Return(false));
  }
  ASSERT_TRUE(sweeper_->RunRound());
}

TEST_F(LevelDbTombstoneSweeperTest, AllTombstonesComplexDB) {
  SetupMockDB();
  PopulateMultiDBMetdata();
  sweeper_->SetMetadata(&metadata_);

  // We'll have one index entry per index, and simulate reaching the end.
  leveldb::MockIterator* first_mock_iterator = new leveldb::MockIterator();
  leveldb::MockIterator* second_mock_iterator = new leveldb::MockIterator();
  leveldb::MockIterator* third_mock_iterator = new leveldb::MockIterator();
  EXPECT_CALL(mock_db_, NewIterator(testing::_))
      .WillOnce(testing::Return(first_mock_iterator))
      .WillOnce(testing::Return(second_mock_iterator))
      .WillOnce(testing::Return(third_mock_iterator));
  // First index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*first_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex1))));
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *first_mock_iterator, kDb1, kOs2, kIndex1,
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(20, blink::mojom::IDBKeyType::Number), 1, 2);
    EXPECT_CALL(*first_mock_iterator, Next());
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    // Return the beginning of the second index, which should cause us to error
    // & go restart our index seek.
    ExpectIndexEntry(*first_mock_iterator, kDb1, kOs2, kIndex2,
                     IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
                     IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1);
  }

  // Second index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*second_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex2))));
    EXPECT_CALL(*second_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *second_mock_iterator, kDb1, kOs2, kIndex2,
        IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1, 2);
    EXPECT_CALL(*second_mock_iterator, Next());
    // Return next key, which should make it error
    EXPECT_CALL(*second_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexEntry(*second_mock_iterator, kDb2, kOs3, kIndex3,
                     IndexedDBKey(1501, blink::mojom::IDBKeyType::Number),
                     IndexedDBKey(15123, blink::mojom::IDBKeyType::Number), 12);
  }

  // Third index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*third_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb2, kOs3, kIndex3))));
    EXPECT_CALL(*third_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *third_mock_iterator, kDb2, kOs3, kIndex3,
        IndexedDBKey(1501, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(15123, blink::mojom::IDBKeyType::Number), 12, 13);
    EXPECT_CALL(*third_mock_iterator, Next());
    // Return next key, which should make it error
    EXPECT_CALL(*third_mock_iterator, Valid()).WillOnce(Return(false));
    EXPECT_CALL(*third_mock_iterator, status())
        .WillOnce(Return(leveldb::Status::OK()));
    EXPECT_CALL(*third_mock_iterator, Valid()).WillOnce(Return(false));
  }

  EXPECT_CALL(mock_db_, Write(_, _));

  ASSERT_TRUE(sweeper_->RunRound());
}

TEST_F(LevelDbTombstoneSweeperTest, SimpleRealDBNoTombstones) {
  PopulateSingleIndexDBMetadata();
  SetupRealDB();
  sweeper_->SetMetadata(&metadata_);

  for (int i = 0; i < kRoundIterations; i++) {
    auto index_key = IndexedDBKey(i, blink::mojom::IDBKeyType::Number);
    auto primary_key = IndexedDBKey(i + 1, blink::mojom::IDBKeyType::Number);
    std::string value_str;
    EncodeVarInt(1, &value_str);
    EncodeIDBKey(primary_key, &value_str);
    in_memory_db_->Put(
        IndexDataKey::Encode(kDb1, kOs1, kIndex1, index_key, primary_key),
        &value_str);

    std::string exists_value;
    std::string encoded_primary_key;
    EncodeIDBKey(primary_key, &encoded_primary_key);
    EncodeVarInt(1, &exists_value);
    in_memory_db_->Put(ExistsEntryKey::Encode(kDb1, kOs1, encoded_primary_key),
                       &exists_value);
  }

  ASSERT_FALSE(sweeper_->RunRound());
  EXPECT_TRUE(sweeper_->RunRound());
}

TEST_F(LevelDbTombstoneSweeperTest, SimpleRealDBWithTombstones) {
  PopulateSingleIndexDBMetadata();
  SetupRealDB();
  sweeper_->SetMetadata(&metadata_);

  for (int i = 0; i < kRoundIterations + 1; i++) {
    auto index_key = IndexedDBKey(i, blink::mojom::IDBKeyType::Number);
    auto primary_key = IndexedDBKey(i + 1, blink::mojom::IDBKeyType::Number);
    std::string value_str;
    EncodeVarInt(1, &value_str);
    EncodeIDBKey(primary_key, &value_str);
    in_memory_db_->Put(
        IndexDataKey::Encode(kDb1, kOs1, kIndex1, index_key, primary_key),
        &value_str);

    std::string exists_value;
    std::string encoded_primary_key;
    EncodeIDBKey(primary_key, &encoded_primary_key);
    bool tombstone = i % 2 != 0;
    EncodeVarInt(tombstone ? 2 : 1, &exists_value);
    in_memory_db_->Put(ExistsEntryKey::Encode(kDb1, kOs1, encoded_primary_key),
                       &exists_value);
  }

  ASSERT_FALSE(sweeper_->RunRound());
  EXPECT_TRUE(sweeper_->RunRound());

  for (int i = 0; i < kRoundIterations + 1; i++) {
    if (i % 2 == 1) {
      std::string out;
      bool found = false;
      auto index_key = IndexedDBKey(i, blink::mojom::IDBKeyType::Number);
      auto primary_key = IndexedDBKey(i + 1, blink::mojom::IDBKeyType::Number);
      EXPECT_TRUE(in_memory_db_
                      ->Get(IndexDataKey::Encode(kDb1, kOs1, kIndex1, index_key,
                                                 primary_key),
                            &out, &found)
                      .ok());
      EXPECT_TRUE(!found);
    }
  }
}

TEST_F(LevelDbTombstoneSweeperTest, LevelDBError) {
  SetupMockDB();
  PopulateMultiDBMetdata();
  sweeper_->SetMetadata(&metadata_);

  // We'll have one index entry per index, and simulate reaching the end.
  leveldb::MockIterator* first_mock_iterator = new leveldb::MockIterator();
  leveldb::MockIterator* second_mock_iterator = new leveldb::MockIterator();
  EXPECT_CALL(mock_db_, NewIterator(testing::_))
      .WillOnce(testing::Return(first_mock_iterator))
      .WillOnce(testing::Return(second_mock_iterator));
  // First index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*first_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex1))));
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *first_mock_iterator, kDb1, kOs2, kIndex1,
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(20, blink::mojom::IDBKeyType::Number), 1, 1);
    EXPECT_CALL(*first_mock_iterator, Next());
    EXPECT_CALL(*first_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    // Return the beginning of the second index, which should cause us to error
    // & go restart our index seek.
    ExpectIndexEntry(*first_mock_iterator, kDb1, kOs2, kIndex2,
                     IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
                     IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1);
  }

  // Second index.
  {
    testing::InSequence sequence_enforcer;
    EXPECT_CALL(*second_mock_iterator,
                Seek(SliceEq(IndexDataKey::EncodeMinKey(kDb1, kOs2, kIndex2))));
    EXPECT_CALL(*second_mock_iterator, Valid())
        .Times(2)
        .WillRepeatedly(Return(true));
    ExpectIndexAndExistsEntries(
        *second_mock_iterator, kDb1, kOs2, kIndex2,
        IndexedDBKey(30, blink::mojom::IDBKeyType::Number),
        IndexedDBKey(10, blink::mojom::IDBKeyType::Number), 1, 1);
    EXPECT_CALL(*second_mock_iterator, Next());
    // Return read error.
    EXPECT_CALL(*second_mock_iterator, Valid()).WillOnce(Return(false));
    EXPECT_CALL(*second_mock_iterator, status())
        .WillOnce(Return(leveldb::Status::Corruption("Test error")));
  }

  ASSERT_TRUE(sweeper_->RunRound());
}

}  // namespace content::indexed_db::level_db