// Copyright 2020 the V8 project 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 "src/heap/cppgc/compactor.h"

#include "include/cppgc/allocation.h"
#include "include/cppgc/custom-space.h"
#include "include/cppgc/persistent.h"
#include "src/heap/cppgc/heap-object-header.h"
#include "src/heap/cppgc/heap-page.h"
#include "src/heap/cppgc/marker.h"
#include "src/heap/cppgc/stats-collector.h"
#include "test/unittests/heap/cppgc/tests.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace cppgc {

class CompactableCustomSpace : public CustomSpace<CompactableCustomSpace> {
 public:
  static constexpr size_t kSpaceIndex = 0;
  static constexpr bool kSupportsCompaction = true;
};

namespace internal {

namespace {

struct CompactableGCed : public GarbageCollected<CompactableGCed> {
 public:
  ~CompactableGCed() { ++g_destructor_callcount; }
  void Trace(Visitor* visitor) const {
    visitor->Trace(other);
    visitor->RegisterMovableReference(other.GetSlotForTesting());
  }
  static size_t g_destructor_callcount;
  Member<CompactableGCed> other;
  size_t id = 0;
};
// static
size_t CompactableGCed::g_destructor_callcount = 0;

template <int kNumObjects>
struct CompactableHolder
    : public GarbageCollected<CompactableHolder<kNumObjects>> {
 public:
  explicit CompactableHolder(cppgc::AllocationHandle& allocation_handle) {
    for (int i = 0; i < kNumObjects; ++i)
      objects[i] = MakeGarbageCollected<CompactableGCed>(allocation_handle);
  }

  void Trace(Visitor* visitor) const {
    for (int i = 0; i < kNumObjects; ++i) {
      visitor->Trace(objects[i]);
      visitor->RegisterMovableReference(objects[i].GetSlotForTesting());
    }
  }
  Member<CompactableGCed> objects[kNumObjects];
};

class CompactorTest : public testing::TestWithPlatform {
 public:
  CompactorTest() {
    Heap::HeapOptions options;
    options.custom_spaces.emplace_back(
        std::make_unique<CompactableCustomSpace>());
    heap_ = Heap::Create(platform_, std::move(options));
  }

  void StartCompaction() {
    compactor().EnableForNextGCForTesting();
    compactor().InitializeIfShouldCompact(
        GarbageCollector::Config::MarkingType::kIncremental,
        GarbageCollector::Config::StackState::kNoHeapPointers);
    EXPECT_TRUE(compactor().IsEnabledForTesting());
  }

  void CancelCompaction() {
    bool cancelled = compactor().CancelIfShouldNotCompact(
        GarbageCollector::Config::MarkingType::kAtomic,
        GarbageCollector::Config::StackState::kMayContainHeapPointers);
    EXPECT_TRUE(cancelled);
  }

  void FinishCompaction() { compactor().CompactSpacesIfEnabled(); }

  void StartGC() {
    CompactableGCed::g_destructor_callcount = 0u;
    StartCompaction();
    heap()->StartIncrementalGarbageCollection(
        GarbageCollector::Config::PreciseIncrementalConfig());
  }

  void EndGC() {
    heap()->marker()->FinishMarking(
        GarbageCollector::Config::StackState::kNoHeapPointers);
    FinishCompaction();
    // Sweeping also verifies the object start bitmap.
    const Sweeper::SweepingConfig sweeping_config{
        Sweeper::SweepingConfig::SweepingType::kAtomic,
        Sweeper::SweepingConfig::CompactableSpaceHandling::kIgnore};
    heap()->sweeper().Start(sweeping_config);
  }

  Heap* heap() { return Heap::From(heap_.get()); }
  cppgc::AllocationHandle& GetAllocationHandle() {
    return heap_->GetAllocationHandle();
  }
  Compactor& compactor() { return heap()->compactor(); }

 private:
  std::unique_ptr<cppgc::Heap> heap_;
};

}  // namespace

}  // namespace internal

template <>
struct SpaceTrait<internal::CompactableGCed> {
  using Space = CompactableCustomSpace;
};

namespace internal {

TEST_F(CompactorTest, NothingToCompact) {
  StartCompaction();
  FinishCompaction();
}

TEST_F(CompactorTest, CancelledNothingToCompact) {
  StartCompaction();
  CancelCompaction();
}

TEST_F(CompactorTest, NonEmptySpaceAllLive) {
  static constexpr int kNumObjects = 10;
  Persistent<CompactableHolder<kNumObjects>> holder =
      MakeGarbageCollected<CompactableHolder<kNumObjects>>(
          GetAllocationHandle(), GetAllocationHandle());
  CompactableGCed* references[kNumObjects] = {nullptr};
  for (int i = 0; i < kNumObjects; ++i) {
    references[i] = holder->objects[i];
  }
  StartGC();
  EndGC();
  EXPECT_EQ(0u, CompactableGCed::g_destructor_callcount);
  for (int i = 0; i < kNumObjects; ++i) {
    EXPECT_EQ(holder->objects[i], references[i]);
  }
}

TEST_F(CompactorTest, NonEmptySpaceAllDead) {
  static constexpr int kNumObjects = 10;
  Persistent<CompactableHolder<kNumObjects>> holder =
      MakeGarbageCollected<CompactableHolder<kNumObjects>>(
          GetAllocationHandle(), GetAllocationHandle());
  CompactableGCed::g_destructor_callcount = 0u;
  StartGC();
  for (int i = 0; i < kNumObjects; ++i) {
    holder->objects[i] = nullptr;
  }
  EndGC();
  EXPECT_EQ(10u, CompactableGCed::g_destructor_callcount);
}

TEST_F(CompactorTest, NonEmptySpaceHalfLive) {
  static constexpr int kNumObjects = 10;
  Persistent<CompactableHolder<kNumObjects>> holder =
      MakeGarbageCollected<CompactableHolder<kNumObjects>>(
          GetAllocationHandle(), GetAllocationHandle());
  CompactableGCed* references[kNumObjects] = {nullptr};
  for (int i = 0; i < kNumObjects; ++i) {
    references[i] = holder->objects[i];
  }
  StartGC();
  for (int i = 0; i < kNumObjects; i += 2) {
    holder->objects[i] = nullptr;
  }
  EndGC();
  // Half of object were destroyed.
  EXPECT_EQ(5u, CompactableGCed::g_destructor_callcount);
  // Remaining objects are compacted.
  for (int i = 1; i < kNumObjects; i += 2) {
    EXPECT_EQ(holder->objects[i], references[i / 2]);
  }
}

TEST_F(CompactorTest, CompactAcrossPages) {
  Persistent<CompactableHolder<1>> holder =
      MakeGarbageCollected<CompactableHolder<1>>(GetAllocationHandle(),
                                                 GetAllocationHandle());
  CompactableGCed* reference = holder->objects[0];
  static constexpr size_t kObjectsPerPage =
      kPageSize / (sizeof(CompactableGCed) + sizeof(HeapObjectHeader));
  for (size_t i = 0; i < kObjectsPerPage; ++i) {
    holder->objects[0] =
        MakeGarbageCollected<CompactableGCed>(GetAllocationHandle());
  }
  // Last allocated object should be on a new page.
  EXPECT_NE(reference, holder->objects[0]);
  EXPECT_NE(BasePage::FromInnerAddress(heap(), reference),
            BasePage::FromInnerAddress(heap(), holder->objects[0].Get()));
  StartGC();
  EndGC();
  // Half of object were destroyed.
  EXPECT_EQ(kObjectsPerPage, CompactableGCed::g_destructor_callcount);
  EXPECT_EQ(reference, holder->objects[0]);
}

TEST_F(CompactorTest, InteriorSlotToPreviousObject) {
  static constexpr int kNumObjects = 3;
  Persistent<CompactableHolder<kNumObjects>> holder =
      MakeGarbageCollected<CompactableHolder<kNumObjects>>(
          GetAllocationHandle(), GetAllocationHandle());
  CompactableGCed* references[kNumObjects] = {nullptr};
  for (int i = 0; i < kNumObjects; ++i) {
    references[i] = holder->objects[i];
  }
  holder->objects[2]->other = holder->objects[1];
  holder->objects[1] = nullptr;
  holder->objects[0] = nullptr;
  StartGC();
  EndGC();
  EXPECT_EQ(1u, CompactableGCed::g_destructor_callcount);
  EXPECT_EQ(references[1], holder->objects[2]);
  EXPECT_EQ(references[0], holder->objects[2]->other);
}

TEST_F(CompactorTest, InteriorSlotToNextObject) {
  static constexpr int kNumObjects = 3;
  Persistent<CompactableHolder<kNumObjects>> holder =
      MakeGarbageCollected<CompactableHolder<kNumObjects>>(
          GetAllocationHandle(), GetAllocationHandle());
  CompactableGCed* references[kNumObjects] = {nullptr};
  for (int i = 0; i < kNumObjects; ++i) {
    references[i] = holder->objects[i];
  }
  holder->objects[1]->other = holder->objects[2];
  holder->objects[2] = nullptr;
  holder->objects[0] = nullptr;
  StartGC();
  EndGC();
  EXPECT_EQ(1u, CompactableGCed::g_destructor_callcount);
  EXPECT_EQ(references[0], holder->objects[1]);
  EXPECT_EQ(references[1], holder->objects[1]->other);
}

}  // namespace internal
}  // namespace cppgc