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

#include "components/autofill/core/common/dense_set.h"

#include <algorithm>
#include <vector>

#include "base/logging.h"
#include "base/rand_util.h"
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/gtest/include/gtest/gtest.h"

using ::testing::ElementsAre;
using ::testing::Field;

namespace autofill {

namespace internal {

template <typename Word, size_t kNumWords>
void PrintTo(Bitset<Word, kNumWords> b, std::ostream* os) {
  for (size_t i = 0; i < kNumWords * 8; ++i) {
    *os << b.get_bit(i);
  }
}

namespace {

class BitUtilTestNameGenerator {
 public:
  template <typename T>
  static std::string GetName(int) {
    if constexpr (std::same_as<T, uint8_t>) {
      return "uint8_t";
    }
    if constexpr (std::same_as<T, uint16_t>) {
      return "uint16_t";
    }
    if constexpr (std::same_as<T, uint32_t>) {
      return "uint32_t";
    }
    if constexpr (std::same_as<T, uint64_t>) {
      return "uint64_t";
    }
  }
};

// Test fixture for the free functions for Bitset and DenseSet.
template <typename T>
class DenseSetTest_BitUtilTest : public testing::Test {};

using BitUtilTestParams = testing::Types<uint8_t, uint16_t, uint32_t, uint64_t>;

TYPED_TEST_SUITE(DenseSetTest_BitUtilTest,
                 BitUtilTestParams,
                 BitUtilTestNameGenerator);

// Tests that PreviousBitIndex() returns the index of the next one, starting
// from the given index, moving to the left.
TYPED_TEST(DenseSetTest_BitUtilTest, PreviousBitIndex) {
  using Word = TypeParam;
  constexpr int kNumBits = sizeof(Word) * 8;
  constexpr int kMaxIndex = kNumBits - 1;

  EXPECT_EQ(PreviousBitIndex(static_cast<uint8_t>(0b11010101), 5), 4);
  EXPECT_EQ(PreviousBitIndex(static_cast<uint8_t>(0b11010101), 4), 4);

  EXPECT_EQ(PreviousBitIndex(static_cast<Word>(0), 0), -1);
  EXPECT_EQ(PreviousBitIndex(static_cast<Word>(0), kMaxIndex), -1);

  for (int bit = 0; bit < kNumBits; ++bit) {
    const Word word = static_cast<Word>(1) << bit;

    // We do find the 1 if we begin the search to the right (including) of it.
    for (int index = bit; index < kNumBits; ++index) {
      SCOPED_TRACE(testing::Message()
                   << "Testing the index " << index << " of word (1 << " << bit
                   << ") = 0b1" << std::string(bit, '0'));
      EXPECT_EQ(PreviousBitIndex<Word>(word, index), bit);
    }

    // We do not find the 1 if we begin the search to the left (excluding) of
    // it.
    for (int index = 0; index < bit; ++index) {
      SCOPED_TRACE(testing::Message()
                   << "Testing the index " << index << " of word (1 << " << bit
                   << ") = 0b1" << std::string(bit, '0'));
      EXPECT_EQ(PreviousBitIndex<Word>(word, index), -1);
    }
  }
}

// Tests that NextBitIndex() returns the index of the next one, starting
// from the given index, moving to the right.
TYPED_TEST(DenseSetTest_BitUtilTest, NextBitIndex) {
  using Word = TypeParam;
  constexpr int kNumBits = sizeof(Word) * 8;
  constexpr int kMaxIndex = kNumBits - 1;

  EXPECT_EQ(NextBitIndex(static_cast<uint8_t>(0b10001011), 1), 1);
  EXPECT_EQ(NextBitIndex(static_cast<uint8_t>(0b10001011), 2), 3);

  EXPECT_EQ(NextBitIndex(static_cast<Word>(0), 0), kNumBits);
  EXPECT_EQ(NextBitIndex(static_cast<Word>(0), kMaxIndex), kNumBits);

  for (int bit = 0; bit < kNumBits; ++bit) {
    const Word word = static_cast<Word>(1) << bit;

    // We do find the 1 if we begin the search to the left (including) of it.
    for (int index = 0; index <= bit; ++index) {
      SCOPED_TRACE(testing::Message()
                   << "Testing the index " << index << " of word (1 << " << bit
                   << ") = 0b1" << std::string(bit, '0'));
      EXPECT_EQ(NextBitIndex<Word>(word, index), bit);
    }

    // We do not find the 1 if we begin the search to the right (excluding) of
    // it.
    for (int index = bit + 1; index < kNumBits; ++index) {
      SCOPED_TRACE(testing::Message()
                   << "Testing the index " << index << " of word (1 << " << bit
                   << ") = 0b1" << std::string(bit, '0'));
      EXPECT_EQ(NextBitIndex<Word>(word, index), kNumBits);
    }
  }
}

template <typename WordT, size_t kNumWordsT>
struct BitsetTestParam {
  using Word = WordT;
  static constexpr size_t kNumWords = kNumWordsT;
  static constexpr size_t kNumBits = kNumWords * sizeof(Word) * 8;
  using Bitset = Bitset<Word, kNumWords>;
};

class BitsetTestNameGenerator {
 public:
  template <typename T>
  static std::string GetName(int) {
    using Word = typename T::Word;
    constexpr size_t kNumWords = T::kNumWords;
    if constexpr (std::same_as<Word, uint8_t>) {
      if constexpr (kNumWords == 1) {
        return "uint8_tX1";
      }
      if constexpr (kNumWords == 2) {
        return "uint8_tX2";
      }
      if constexpr (kNumWords == 3) {
        return "uint8_tX3";
      }
    }
    if constexpr (std::same_as<Word, uint16_t>) {
      if constexpr (kNumWords == 1) {
        return "uint16_tX1";
      }
      if constexpr (kNumWords == 2) {
        return "uint16_tX2";
      }
      if constexpr (kNumWords == 3) {
        return "uint16_tX3";
      }
    }
    if constexpr (std::same_as<Word, uint32_t>) {
      if constexpr (kNumWords == 1) {
        return "uint32_tX1";
      }
      if constexpr (kNumWords == 2) {
        return "uint32_tX2";
      }
      if constexpr (kNumWords == 3) {
        return "uint32_tX3";
      }
    }
    if constexpr (std::same_as<Word, uint64_t>) {
      if constexpr (kNumWords == 1) {
        return "uint64_tX1";
      }
      if constexpr (kNumWords == 2) {
        return "uint64_tX2";
      }
      if constexpr (kNumWords == 3) {
        return "uint64_tX3";
      }
    }
  }
};

// Test fixture for Bitset<Word, kNumWords>.
template <typename T>
class DenseSetTest_BitsetTest : public testing::Test {};

using BitsetTestParams = testing::Types<BitsetTestParam<uint8_t, 1>,
                                        BitsetTestParam<uint8_t, 2>,
                                        BitsetTestParam<uint8_t, 3>,
                                        BitsetTestParam<uint16_t, 1>,
                                        BitsetTestParam<uint16_t, 2>,
                                        BitsetTestParam<uint16_t, 3>,
                                        BitsetTestParam<uint32_t, 1>,
                                        BitsetTestParam<uint32_t, 2>,
                                        BitsetTestParam<uint32_t, 3>,
                                        BitsetTestParam<uint64_t, 1>,
                                        BitsetTestParam<uint64_t, 2>,
                                        BitsetTestParam<uint64_t, 3>>;

TYPED_TEST_SUITE(DenseSetTest_BitsetTest,
                 BitsetTestParams,
                 BitsetTestNameGenerator);

// Test that Bitset::set_bit(), Bitset::get_bit(), and Bitset::num_set_bits()
// are plausible.
TYPED_TEST(DenseSetTest_BitsetTest, SetBit) {
  using Bitset = typename TypeParam::Bitset;
  constexpr size_t kNumBits = TypeParam::kNumBits;
  Bitset b;

  EXPECT_EQ(b.num_set_bits(), 0u);
  EXPECT_FALSE(b.get_bit(0));
  EXPECT_FALSE(b.get_bit(kNumBits - 1));

  b.set_bit(0);
  EXPECT_EQ(b.num_set_bits(), 1u);
  EXPECT_TRUE(b.get_bit(0));
  EXPECT_FALSE(b.get_bit(kNumBits - 1));

  b.set_bit(0);
  EXPECT_EQ(b.num_set_bits(), 1u);
  EXPECT_TRUE(b.get_bit(0));
  EXPECT_FALSE(b.get_bit(kNumBits - 1));

  b.set_bit(kNumBits - 1);
  EXPECT_EQ(b.num_set_bits(), 2u);
  EXPECT_TRUE(b.get_bit(0));
  EXPECT_TRUE(b.get_bit(kNumBits - 1));
}

// Test that Bitset::set_bit() also works at the word boundaries.
TYPED_TEST(DenseSetTest_BitsetTest, SetBitAtBoundary) {
  using Bitset = typename TypeParam::Bitset;
  constexpr size_t kNumBits = TypeParam::kNumBits;
  Bitset b;
  EXPECT_EQ(b.num_set_bits(), 0u);
  EXPECT_FALSE(b.get_bit(kNumBits / 2 - 1));
  EXPECT_FALSE(b.get_bit(kNumBits / 2));

  b.set_bit(kNumBits / 2 - 1u);
  EXPECT_EQ(b.num_set_bits(), 1u);
  EXPECT_TRUE(b.get_bit(kNumBits / 2 - 1));
  EXPECT_FALSE(b.get_bit(kNumBits / 2));

  b.set_bit(kNumBits / 2);
  EXPECT_EQ(b.num_set_bits(), 2u);
  EXPECT_TRUE(b.get_bit(kNumBits / 2 - 1));
  EXPECT_TRUE(b.get_bit(kNumBits / 2));
}

// Test that Bitset::unset_bit() clears bits.
TYPED_TEST(DenseSetTest_BitsetTest, UnsetBit) {
  using Bitset = typename TypeParam::Bitset;
  Bitset b;

  EXPECT_FALSE(b.get_bit(3));
  b.set_bit(3);
  EXPECT_TRUE(b.get_bit(3));
  b.unset_bit(3);
  EXPECT_FALSE(b.get_bit(3));
}

// Test that Bitset::previous_set_bit() is same or next smaller index at which
// a bit is set.
TYPED_TEST(DenseSetTest_BitsetTest, PreviousSetBit) {
  using Bitset = typename TypeParam::Bitset;
  constexpr size_t kNumBits = TypeParam::kNumBits;

  {
    Bitset b;
    b.set_bit(2);
    EXPECT_EQ(b.previous_set_bit(0), -1);
    EXPECT_EQ(b.previous_set_bit(1), -1);
    EXPECT_EQ(b.previous_set_bit(2), 2);
    EXPECT_EQ(b.previous_set_bit(3), 2);
    EXPECT_EQ(b.previous_set_bit(4), 2);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2 - 1), 2);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2), 2);
    EXPECT_EQ(b.previous_set_bit(kNumBits - 1), 2);
  }

  {
    Bitset b;
    b.set_bit(0);
    EXPECT_EQ(b.previous_set_bit(0), 0);
    EXPECT_EQ(b.previous_set_bit(1), 0);
    EXPECT_EQ(b.previous_set_bit(2), 0);
    EXPECT_EQ(b.previous_set_bit(3), 0);
    EXPECT_EQ(b.previous_set_bit(4), 0);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2 - 1), 0);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2), 0);
    EXPECT_EQ(b.previous_set_bit(kNumBits - 1), 0);
  }

  {
    Bitset b;
    b.set_bit(kNumBits - 1);
    EXPECT_EQ(b.previous_set_bit(0), -1);
    EXPECT_EQ(b.previous_set_bit(1), -1);
    EXPECT_EQ(b.previous_set_bit(2), -1);
    EXPECT_EQ(b.previous_set_bit(3), -1);
    EXPECT_EQ(b.previous_set_bit(4), -1);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2 - 1), -1);
    EXPECT_EQ(b.previous_set_bit(kNumBits / 2), -1);
    EXPECT_EQ(b.previous_set_bit(kNumBits - 1),
              base::checked_cast<int>(kNumBits) - 1);
  }
}

// Test that Bitset::previous_set_bit() is same or next greater index at which
// a bit is set.
TYPED_TEST(DenseSetTest_BitsetTest, NextSetBit) {
  using Bitset = typename TypeParam::Bitset;
  constexpr size_t kNumBits = TypeParam::kNumBits;

  {
    Bitset b;
    b.set_bit(2);
    EXPECT_EQ(b.next_set_bit(0), 2u);
    EXPECT_EQ(b.next_set_bit(1), 2u);
    EXPECT_EQ(b.next_set_bit(2), 2u);
    EXPECT_EQ(b.next_set_bit(3), kNumBits);
    EXPECT_EQ(b.next_set_bit(4), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2 - 1), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits - 1), kNumBits);
  }

  {
    Bitset b;
    b.set_bit(0);
    EXPECT_EQ(b.next_set_bit(0), 0u);
    EXPECT_EQ(b.next_set_bit(1), kNumBits);
    EXPECT_EQ(b.next_set_bit(2), kNumBits);
    EXPECT_EQ(b.next_set_bit(3), kNumBits);
    EXPECT_EQ(b.next_set_bit(4), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2 - 1), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2), kNumBits);
    EXPECT_EQ(b.next_set_bit(kNumBits - 1), kNumBits);
  }

  {
    Bitset b;
    b.set_bit(kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(0), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(1), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(2), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(3), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(4), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2 - 1), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(kNumBits / 2), kNumBits - 1);
    EXPECT_EQ(b.next_set_bit(kNumBits - 1), kNumBits - 1);
  }
}

// Tests the comparison and bitwise operators of Bitset.
TYPED_TEST(DenseSetTest_BitsetTest, Operators) {
  using Bitset = typename TypeParam::Bitset;
  constexpr size_t kNumBits = TypeParam::kNumBits;

  Bitset b;
  b.set_bit(0);
  b.set_bit(1);
  b.set_bit(4);

  Bitset c;
  c.set_bit(4);
  c.set_bit(7);

  EXPECT_EQ(b, b);
  EXPECT_NE(b, c);

  EXPECT_EQ((b & c).num_set_bits(), 1u);
  EXPECT_TRUE((b & c).get_bit(4));
  {
    Bitset d = b;
    d &= c;
    EXPECT_EQ(b & c, d);
  }

  {
    Bitset d = b;
    d |= c;
    Bitset e;
    e.set_bit(0);
    e.set_bit(1);
    e.set_bit(4);
    e.set_bit(7);
    EXPECT_EQ(d, e);
  }

  EXPECT_EQ((~b).num_set_bits(), kNumBits - b.num_set_bits());
  {
    Bitset d;
    d = ~d;
    d.unset_bit(0);
    d.unset_bit(1);
    d.unset_bit(4);
    EXPECT_EQ(~b, d);
  }
  EXPECT_EQ(~~b, b);
}

// Tests that Bitset::data() returns a raw representation of the bitset.
TEST(DenseSetTest_BitsetTest_Data, Data) {
  Bitset<uint8_t, 3> b;
  b.set_bit(0 * 8 + 1);
  b.set_bit(1 * 8 + 2);
  b.set_bit(2 * 8 + 3);
  EXPECT_THAT(b.data(), ElementsAre(static_cast<uint8_t>(1 << 1),
                                    static_cast<uint8_t>(1 << 2),
                                    static_cast<uint8_t>(1 << 3)));
}

}  // namespace

}  // namespace internal

namespace {

// The default bounds are kMinValue and kMaxValue (inclusive).
TEST(DenseSetTest, ExampleUsage1) {
  enum class MyEnum {
    kFoo = -1,
    kBar = 0,
    kQux = 1,
    kMinValue = kFoo,
    kMaxValue = kQux
  };
  DenseSet<MyEnum> set;  // Bounds: [MyEnum::kMinValue, MyEnum::kMaxValue].
  set.insert(MyEnum::kFoo);
  set.insert(MyEnum::kBar);
  EXPECT_THAT(set, ElementsAre(MyEnum::kFoo, MyEnum::kBar));
  set.insert(MyEnum::kQux);
  EXPECT_THAT(set, ElementsAre(MyEnum::kFoo, MyEnum::kBar, MyEnum::kQux));
}

// If `kMinValue` is not defined, the fallback is `0`.
TEST(DenseSetTest, ExampleUsage2) {
  enum class MyEnum { kFoo, kBar, kQux, kMaxValue = kQux };
  DenseSet<MyEnum> set = DenseSet<MyEnum>::all();
  ASSERT_FALSE(set.empty());
  EXPECT_EQ(*set.begin(), MyEnum::kFoo);
  EXPECT_EQ(*set.rbegin(), MyEnum::kQux);
}

// Custom bounds can be specified in the traits.
TEST(DenseSetTest, ExampleUsage3) {
  enum MyEnum {
    kFoo = 0,
    kBar = 1,
    kQux = 2,
  };
  using MyEnumSet = DenseSet<MyEnum, EnumDenseSetTraits<MyEnum, kFoo, kQux>>;
  MyEnumSet set = MyEnumSet::all();
  EXPECT_THAT(set, ElementsAre(kFoo, kBar, kQux));
  set.erase(kBar);
  EXPECT_THAT(set, ElementsAre(kFoo, kQux));
}

// Used by DenseSetTest.ExampleUsage4.
enum class MyEnum4 { kFoo = 0, kQux = 2, kMaxValue = kQux };

}  // namespace

// Used by DenseSetTest.ExampleUsage4.
template <>
struct DenseSetTraits<MyEnum4>
    : public EnumDenseSetTraits<MyEnum4, MyEnum4(0), MyEnum4::kMaxValue> {
  static constexpr bool is_valid(MyEnum4 x) {
    return std::to_underlying(x) != 1;
  }
};

namespace {

// Invalid values can be excluded by specializing the traits:
TEST(DenseSetTest, ExampleUsage4) {
  DenseSet<MyEnum4> set = DenseSet<MyEnum4>::all();
  EXPECT_THAT(set, ElementsAre(MyEnum4::kFoo, MyEnum4::kQux));
}

// Used by DenseSetTest.ExampleUsage5.
struct MyStruct5 {
  int x = 0;  // Range -5 to 5.
};

}  // namespace

// Used by DenseSetTest.ExampleUsage5.
template <>
struct DenseSetTraits<MyStruct5> {
  using UnderlyingType = int;

  static constexpr MyStruct5 from_underlying(UnderlyingType x) {
    return {.x = x};
  }
  static constexpr UnderlyingType to_underlying(MyStruct5 s) { return s.x; }
  static constexpr bool is_valid(MyStruct5 x) { return true; }

  static constexpr MyStruct5 kMinValue = {.x = -5};
  static constexpr MyStruct5 kMaxValue = {.x = 5};
  static constexpr bool kPacked = false;
};

namespace {

// The value type does not need to be an enum -- it suffices if it has an
// integral representation:
TEST(DenseSetTest, ExampleUsage5) {
  DenseSet<MyStruct5> set;
  MyStruct5 s = {.x = 5};
  set.insert(s);
  EXPECT_THAT(set, ElementsAre(Field(&MyStruct5::x, 5)));
}

template <typename T, T kMinValue, T kMaxValue>
using IntDenseSet =
    DenseSet<T, IntegralDenseSetTraits<T, kMinValue, kMaxValue>>;

TEST(DenseSetTest, size_of) {
  static_assert(sizeof(IntDenseSet<size_t, 0, 1>) == 1u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 7>) == 1u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 8>) == 2u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 15>) == 2u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 16>) == 4u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 31>) == 4u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 32>) == 8u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 63>) == 8u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 64>) == 16u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 127>) == 16u);
  static_assert(sizeof(IntDenseSet<size_t, 0, 255>) == 32u);
}

TEST(DenseSetTest, initialization) {
  enum class T : size_t {
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5,
    kMaxValue = kFive,
  };
  DenseSet<T> s;
  EXPECT_TRUE(s.empty());
  EXPECT_EQ(s.size(), 0u);
  EXPECT_EQ(DenseSet<T>(s.begin(), s.end()), s);
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(DenseSet<T>(s.begin(), s.end()), s);
  EXPECT_EQ(DenseSet<T>(s.cbegin(), s.cend()), s);
  EXPECT_EQ(DenseSet<T>(s.rbegin(), s.rend()), s);
  EXPECT_EQ(DenseSet<T>(s.crbegin(), s.crend()), s);
  EXPECT_EQ(DenseSet<T>({T::kFour, T::kTwo, T::kOne}), s);
}

TEST(DenseSetTest, FromRange) {
  enum class E { kOne = 1, kTwo = 2, kThree = 3, kMaxValue = kThree };
  struct S {
    auto operator<=>(const S&) const = default;

    E e = E::kOne;
  };

  {
    std::vector<S> container = {S{.e = E::kTwo}, S{.e = E::kThree}};
    DenseSet s(container, &S::e);
    EXPECT_EQ(s, DenseSet({E::kTwo, E::kThree}));
  }

  {
    std::set<S> container = {S{.e = E::kOne}, S{.e = E::kThree}};
    DenseSet s(container, &S::e);
    EXPECT_EQ(s, DenseSet({E::kThree, E::kOne}));
  }
}

TEST(DenseSetTest, initializer_list) {
  // The largest value so that DenseSet offers a constexpr constructor.
  constexpr uint64_t kMaxValueForConstexpr = 63;

  // Each of the below blocks is a copy that only varies in `kMax` and whether
  // or not the `set` is `constexpr`.

  {
    constexpr uint64_t kMax = 10;
    constexpr IntDenseSet<uint64_t, 0, kMax> set{0, 1, kMax - 2, kMax - 1,
                                                 kMax};
    EXPECT_THAT(std::vector<uint64_t>(set.begin(), set.end()),
                ElementsAre(0, 1, kMax - 2, kMax - 1, kMax));
  }

  {
    constexpr uint64_t kMax = kMaxValueForConstexpr;
    constexpr IntDenseSet<uint64_t, 0, kMax> set{0, 1, kMax - 2, kMax - 1,
                                                 kMax};
    EXPECT_THAT(std::vector<uint64_t>(set.begin(), set.end()),
                ElementsAre(0, 1, kMax - 2, kMax - 1, kMax));
  }

  {
    constexpr uint64_t kMax = kMaxValueForConstexpr + 1;
    IntDenseSet<uint64_t, 0, kMax> set{0, 1, kMax - 2, kMax - 1, kMax};
    EXPECT_THAT(std::vector<uint64_t>(set.begin(), set.end()),
                ElementsAre(0, 1, kMax - 2, kMax - 1, kMax));
  }

  {
    constexpr uint64_t kMax = kMaxValueForConstexpr + 2;
    IntDenseSet<uint64_t, 0, kMax> set{0, 1, kMax - 2, kMax - 1, kMax};
    EXPECT_THAT(std::vector<uint64_t>(set.begin(), set.end()),
                ElementsAre(0, 1, kMax - 2, kMax - 1, kMax));
  }

  {
    constexpr uint64_t kMax = kMaxValueForConstexpr + 100;
    IntDenseSet<uint64_t, 0, kMax> set{0, 1, kMax - 2, kMax - 1, kMax};
    EXPECT_THAT(std::vector<uint64_t>(set.begin(), set.end()),
                ElementsAre(0, 1, kMax - 2, kMax - 1, kMax));
  }
}

TEST(DenseSetTest, all_non_enum) {
  constexpr IntDenseSet<int, 0, 10> set = IntDenseSet<int, 0, 10>::all();
  EXPECT_EQ(set.size(), 11u);
  EXPECT_THAT(std::vector<int>(set.begin(), set.end()),
              ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
}

TEST(DenseSetTest, all_enum) {
  enum class T {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kMaxValue = kTwo,
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kMaxValue>;

  constexpr DenseSet<T, Traits> set = DenseSet<T, Traits>::all();
  // `set` will contain all values from -1 to 2, including 0 even if 0 doesn't
  // correspond to any value of `T`.
  EXPECT_EQ(set.size(), 4u);
  EXPECT_THAT(std::vector<T>(set.begin(), set.end()),
              ElementsAre(T::kMinusOne, static_cast<T>(0), T::kOne, T::kTwo));
}

TEST(DenseSetTest, data) {
  {
    constexpr IntDenseSet<uint64_t, 0, 23> set{0, 1, 2, 3, 4, 20, 23};
    EXPECT_THAT(
        set.data(),
        ElementsAre((1ULL << 0) | (1ULL << 1) | (1ULL << 2) | (1ULL << 3) |
                    (1ULL << 4) | (1ULL << 20) | (1ULL << 23)));
  }
  {
    constexpr IntDenseSet<uint64_t, 0, 31> set{0, 1, 2, 3, 4, 20, 31};
    EXPECT_THAT(
        set.data(),
        ElementsAre((1ULL << 0) | (1ULL << 1) | (1ULL << 2) | (1ULL << 3) |
                    (1ULL << 4) | (1ULL << 20) | (1ULL << 31)));
  }
  {
    constexpr IntDenseSet<uint64_t, 0, 63> set{0, 1, 63};
    EXPECT_THAT(set.data(),
                ElementsAre((1ULL << 0) | (1ULL << 1) | (1ULL << 63)));
  }
}

TEST(DenseSetTest, iterators_begin_end) {
  enum class T : int {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5,
    kMaxValue = kFive,
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kMaxValue>;

  DenseSet<T, Traits> s;
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(std::distance(s.begin(), s.end()), 3);

  {
    auto it = s.begin();
    auto x1 = *it++;
    auto x2 = *it++;
    auto x3 = *it++;
    EXPECT_EQ(it, s.end());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  {
    auto it = s.begin();
    auto x1 = *it;
    auto x2 = *++it;
    auto x3 = *++it;
    EXPECT_NE(it, s.end());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  EXPECT_THAT(s, ElementsAre(T::kOne, T::kTwo, T::kFour));
}

TEST(DenseSetTest, iterators_begin_end_reverse) {
  enum class T : int8_t {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5,
    kMaxValue = kFive
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kMaxValue>;

  DenseSet<T, Traits> s;
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);
  EXPECT_EQ(s.size(), 3u);

  {
    auto it = s.end();
    it--;
    auto x3 = *it--;
    auto x2 = *it--;
    auto x1 = *it;
    EXPECT_EQ(it, s.begin());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  {
    auto it = s.end();
    auto x3 = *--it;
    auto x2 = *--it;
    auto x1 = *--it;
    EXPECT_EQ(it, s.begin());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }
}

TEST(DenseSetTest, iterators_rbegin_rend) {
  enum class T {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5,
    kMaxValue = kFive
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kMaxValue>;

  DenseSet<T, Traits> s;
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(std::distance(s.rbegin(), s.rend()), 3);

  {
    auto it = s.rbegin();
    auto x3 = *it++;
    auto x2 = *it++;
    auto x1 = *it++;
    EXPECT_EQ(it, s.rend());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  {
    auto it = s.rbegin();
    auto x3 = *it;
    auto x2 = *++it;
    auto x1 = *++it;
    EXPECT_NE(it, s.rend());
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  EXPECT_THAT(std::vector<T>(s.rbegin(), s.rend()),
              ElementsAre(T::kFour, T::kTwo, T::kOne));
}

TEST(DenseSetTest, lookup) {
  enum class T {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5,
    kMaxValue = kFive
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kMaxValue>;

  DenseSet<T, Traits> s;
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);

  EXPECT_FALSE(s.contains(static_cast<T>(0)));
  EXPECT_TRUE(s.contains(T::kOne));
  EXPECT_TRUE(s.contains(T::kTwo));
  EXPECT_FALSE(s.contains(T::kThree));
  EXPECT_TRUE(s.contains(T::kFour));
  EXPECT_FALSE(s.contains(T::kFive));

  EXPECT_EQ(s.contains(static_cast<T>(0)), 0u);
  EXPECT_EQ(s.contains(T::kOne), 1u);
  EXPECT_EQ(s.contains(T::kTwo), 1u);
  EXPECT_EQ(s.contains(T::kThree), 0u);
  EXPECT_EQ(s.contains(T::kFour), 1u);
  EXPECT_EQ(s.contains(T::kFive), 0u);

  EXPECT_EQ(s.find(static_cast<T>(0)), s.end());
  EXPECT_NE(s.find(T::kOne), s.end());
  EXPECT_NE(s.find(T::kTwo), s.end());
  EXPECT_EQ(s.find(T::kThree), s.end());
  EXPECT_NE(s.find(T::kFour), s.end());
  EXPECT_EQ(s.find(T::kFive), s.end());

  EXPECT_EQ(*s.find(T::kOne), T::kOne);
  EXPECT_EQ(*s.find(T::kTwo), T::kTwo);
  EXPECT_EQ(*s.find(T::kFour), T::kFour);

  EXPECT_NE(s.find(static_cast<T>(0)), s.lower_bound(static_cast<T>(0)));
  EXPECT_EQ(s.find(T::kOne), s.lower_bound(T::kOne));
  EXPECT_EQ(s.find(T::kTwo), s.lower_bound(T::kTwo));
  EXPECT_NE(s.find(T::kThree), s.lower_bound(T::kThree));
  EXPECT_EQ(s.find(T::kFour), s.lower_bound(T::kFour));
  EXPECT_EQ(s.find(T::kFive), s.lower_bound(T::kFive));

  DenseSet<T, Traits> t;
  EXPECT_TRUE(t.empty());
  EXPECT_TRUE(t.contains_none({}));
  EXPECT_FALSE(t.contains_any({}));
  EXPECT_TRUE(t.contains_all({}));

  t.insert_all(s);
  EXPECT_EQ(s, t);
  EXPECT_FALSE(s.contains_none(t));
  EXPECT_TRUE(s.contains_any(t));
  EXPECT_TRUE(s.contains_all(t));
  EXPECT_TRUE(s.contains_none({}));
  EXPECT_FALSE(s.contains_any({}));
  EXPECT_TRUE(s.contains_all({}));

  t.erase(t.begin());
  EXPECT_FALSE(s.contains_none(t));
  EXPECT_TRUE(s.contains_any(t));
  EXPECT_TRUE(s.contains_all(t));
  EXPECT_FALSE(t.contains_none(s));
  EXPECT_FALSE(t.contains_all(s));
  EXPECT_TRUE(t.contains_any(s));
  EXPECT_TRUE(s.contains_none({}));
  EXPECT_FALSE(s.contains_any({}));
  EXPECT_TRUE(s.contains_all({}));
}

TEST(DenseSetTest, iterators_lower_upper_bound) {
  enum class T {
    kMinusOne = -1,
    kOne = 1,
    kTwo = 2,
    kThree = 3,
    kFour = 4,
    kFive = 5
  };
  using Traits = EnumDenseSetTraits<T, T::kMinusOne, T::kFive>;

  DenseSet<T, Traits> s;
  s.insert(T::kTwo);
  s.insert(T::kFour);
  s.insert(T::kOne);
  EXPECT_EQ(s.size(), 3u);

  EXPECT_EQ(s.lower_bound(static_cast<T>(0)), s.begin());
  EXPECT_EQ(s.lower_bound(T::kOne), s.begin());

  EXPECT_EQ(s.upper_bound(T::kFour), s.end());
  EXPECT_EQ(s.upper_bound(T::kFive), s.end());

  {
    auto it = s.lower_bound(static_cast<T>(0));
    auto jt = s.upper_bound(static_cast<T>(0));
    EXPECT_EQ(it, jt);
  }

  {
    auto it = s.lower_bound(T::kOne);
    auto jt = s.upper_bound(T::kOne);
    auto x1 = *it++;
    EXPECT_EQ(it, jt);
    EXPECT_EQ(x1, T::kOne);
  }

  {
    auto it = s.lower_bound(T::kFour);
    auto jt = s.upper_bound(T::kFour);
    auto x3 = *it++;
    EXPECT_EQ(it, jt);
    EXPECT_EQ(x3, T::kFour);
  }

  {
    auto it = s.lower_bound(T::kFive);
    auto jt = s.upper_bound(T::kFive);
    EXPECT_EQ(it, jt);
  }

  {
    auto it = s.lower_bound(T::kOne);
    auto jt = s.upper_bound(T::kFive);
    auto x1 = *it++;
    auto x2 = *it++;
    auto x3 = *it++;
    EXPECT_EQ(it, jt);
    EXPECT_EQ(x1, T::kOne);
    EXPECT_EQ(x2, T::kTwo);
    EXPECT_EQ(x3, T::kFour);
  }

  {
    auto it = s.lower_bound(T::kThree);
    auto jt = s.upper_bound(T::kFour);
    auto x3 = *it++;
    EXPECT_EQ(jt, s.end());
    EXPECT_EQ(it, jt);
    EXPECT_EQ(x3, T::kFour);
  }

  EXPECT_EQ(static_cast<size_t>(std::distance(s.begin(), s.end())), s.size());
  EXPECT_EQ(std::next(std::next(std::next(s.begin()))), s.end());
}

TEST(DenseSetTest, max_size) {
  const int kOne = 1;
  const int kTwo = 2;
  // const int kThree = 3;
  const int kFour = 4;
  // const int kFive = 5;
  const int kMaxValue = 5;

  IntDenseSet<int, 0, kMaxValue> s;
  EXPECT_TRUE(s.empty());
  EXPECT_EQ(s.size(), 0u);
  EXPECT_EQ(s.max_size(), 6u);
  s.insert(kTwo);
  EXPECT_FALSE(s.empty());
  EXPECT_EQ(s.size(), 1u);
  s.insert(kFour);
  EXPECT_FALSE(s.empty());
  EXPECT_EQ(s.size(), 2u);
  s.insert(kOne);
  EXPECT_FALSE(s.empty());
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(s.max_size(), 6u);
}

TEST(DenseSetTest, modifiers) {
  const uint64_t kOne = 1;
  const uint64_t kTwo = 2;
  const uint64_t kThree = 3;
  const uint64_t kFour = 4;
  // const uint64_t kFive = 5;
  const uint64_t kMaxValue = 5;

  IntDenseSet<uint64_t, 0, kMaxValue> s;
  s.insert(kTwo);
  s.insert(kFour);
  s.insert(kOne);
  EXPECT_EQ(s.size(), 3u);

  auto EXPECT_INSERTION = [](auto& set, auto value, bool took_place) {
    auto it = set.insert(value);
    EXPECT_EQ(it, std::make_pair(set.find(value), took_place));
  };

  IntDenseSet<uint64_t, 0, kMaxValue> t;
  EXPECT_NE(s, t);
  EXPECT_INSERTION(t, kTwo, true);
  EXPECT_INSERTION(t, kTwo, false);
  EXPECT_INSERTION(t, kFour, true);
  EXPECT_INSERTION(t, kFour, false);
  EXPECT_INSERTION(t, kOne, true);
  EXPECT_INSERTION(t, kOne, false);
  EXPECT_EQ(s, t);
  EXPECT_EQ(t.size(), 3u);

  EXPECT_INSERTION(t, kThree, true);
  EXPECT_INSERTION(t, kThree, false);
  EXPECT_EQ(t.erase(kThree), 1u);
  EXPECT_EQ(t.erase(kThree), 0u);
  EXPECT_EQ(s, t);
  EXPECT_EQ(t.size(), 3u);

  EXPECT_EQ(s.erase(kOne), 1u);
  EXPECT_EQ(t.erase(kFour), 1u);
  EXPECT_NE(s, t);
  EXPECT_EQ(s.size(), 2u);
  EXPECT_EQ(t.size(), 2u);

  EXPECT_INSERTION(s, kOne, true);
  EXPECT_INSERTION(t, kFour, true);
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(t.size(), 3u);

  EXPECT_EQ(s.erase(s.find(kOne)), s.find(kTwo));
  EXPECT_EQ(t.erase(t.lower_bound(kOne), t.upper_bound(kOne)), t.find(kTwo));
  EXPECT_FALSE(s.contains(kOne));
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 2u);
  EXPECT_EQ(t.size(), 2u);

  EXPECT_INSERTION(s, kOne, true);
  EXPECT_INSERTION(t, kOne, true);
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(t.size(), 3u);

  EXPECT_EQ(s.erase(s.find(kTwo), s.end()), s.end());
  EXPECT_EQ(t.erase(t.lower_bound(kTwo), t.upper_bound(kFour)), t.end());
  EXPECT_TRUE(s.contains(kOne));
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 1u);
  EXPECT_EQ(t.size(), 1u);

  EXPECT_INSERTION(s, kTwo, true);
  EXPECT_INSERTION(t, kTwo, true);
  EXPECT_INSERTION(s, kFour, true);
  EXPECT_INSERTION(t, kFour, true);
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(t.size(), 3u);

  s.clear();
  EXPECT_EQ(s, decltype(s){});
  EXPECT_TRUE(s.empty());

  s.insert(kThree);
  s.insert_all(t);
  EXPECT_EQ(s.size(), 4u);
  EXPECT_EQ(t.size(), 3u);
  EXPECT_NE(s, t);
  EXPECT_FALSE(s.contains_none(t));
  EXPECT_TRUE(s.contains_any(t));
  EXPECT_TRUE(s.contains_all(t));
  EXPECT_TRUE(s.contains(kThree));
  EXPECT_FALSE(t.contains_none(s));
  EXPECT_TRUE(t.contains_any(s));
  EXPECT_FALSE(t.contains_all(s));

  s.erase_all(t);
  EXPECT_EQ(s.size(), 1u);
  EXPECT_TRUE(s.contains(kThree));
  EXPECT_TRUE(s.contains_none(t));
  EXPECT_FALSE(s.contains_any(t));
  EXPECT_FALSE(s.contains_all(t));

  s.insert_all(t);
  s.erase(kThree);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(s, t);

  s.erase_all(t);
  EXPECT_TRUE(s.empty());

  EXPECT_INSERTION(s, *t.begin(), true);
  EXPECT_TRUE(s.contains(kOne));
  EXPECT_INSERTION(s, *std::next(t.begin()), true);
  EXPECT_TRUE(s.contains(kTwo));
  EXPECT_INSERTION(s, *std::prev(t.end()), true);
  EXPECT_TRUE(s.contains(kFour));
  EXPECT_EQ(s, t);
  EXPECT_EQ(s.size(), 3u);
  EXPECT_EQ(t.size(), 3u);
}

TEST(DenseSetTest, intersect) {
  constexpr uint64_t kMaxValue = 5;
  IntDenseSet<uint64_t, 0, kMaxValue> s = {1, 3, 4};
  IntDenseSet<uint64_t, 0, kMaxValue> t = {1, 2, 4};
  s.intersect(t);
  // Expect that only 1 and 4 remain.
  t.erase(2);
  EXPECT_EQ(s, t);
}

TEST(DenseSetTest, std_set) {
  constexpr uint64_t kMaxValue = 50;
  IntDenseSet<uint64_t, 0, kMaxValue> dense_set;
  std::set<uint64_t> std_set;

  auto expect_equivalence = [&] {
    EXPECT_EQ(dense_set.empty(), std_set.empty());
    EXPECT_EQ(dense_set.size(), std_set.size());
    EXPECT_TRUE(std::ranges::equal(dense_set, std_set));
  };

  auto random_insert = [&] {
    expect_equivalence();
    uint64_t value = base::RandUint64() % kMaxValue;
    auto p = dense_set.insert(value);
    auto q = std_set.insert(value);
    EXPECT_EQ(p.second, q.second);
    EXPECT_EQ(p.first == dense_set.end(), q.first == std_set.end());
    EXPECT_TRUE(!p.second || p.first == dense_set.find(value));
    EXPECT_TRUE(!q.second || q.first == std_set.find(value));
  };

  auto random_erase = [&] {
    expect_equivalence();
    uint64_t value = base::RandUint64() % kMaxValue;
    EXPECT_EQ(dense_set.erase(value), std_set.erase(value));
  };

  auto random_erase_iterator = [&] {
    expect_equivalence();
    uint64_t value = base::RandUint64() % kMaxValue;
    auto it = dense_set.find(value);
    auto jt = std_set.find(value);
    EXPECT_EQ(it == dense_set.end(), jt == std_set.end());
    if (it == dense_set.end() || jt == std_set.end())
      return;
    auto succ_it = dense_set.erase(it);
    auto succ_jt = std_set.erase(jt);
    EXPECT_EQ(succ_it == dense_set.end(), succ_jt == std_set.end());
    EXPECT_TRUE(succ_it == dense_set.upper_bound(value));
    EXPECT_TRUE(succ_jt == std_set.upper_bound(value));
    EXPECT_TRUE(succ_it == dense_set.end() || *succ_it == *succ_jt);
  };

  auto random_erase_range = [&] {
    expect_equivalence();
    uint64_t min_value = base::RandUint64() % kMaxValue;
    uint64_t max_value = base::RandUint64() % kMaxValue;
    min_value = std::min(min_value, max_value);
    max_value = std::max(min_value, max_value);
    dense_set.erase(dense_set.lower_bound(min_value),
                    dense_set.upper_bound(max_value));
    std_set.erase(std_set.lower_bound(min_value),
                  std_set.upper_bound(max_value));
  };

  for (uint64_t i = 0; i < kMaxValue; ++i) {
    random_insert();
  }

  for (uint64_t i = 0; i < kMaxValue / 2; ++i) {
    random_erase();
  }

  expect_equivalence();
  dense_set.clear();
  std_set.clear();
  expect_equivalence();

  for (uint64_t i = 0; i < kMaxValue; ++i) {
    random_insert();
  }

  for (uint64_t i = 0; i < kMaxValue; ++i) {
    random_erase_iterator();
  }

  expect_equivalence();
  dense_set.clear();
  std_set.clear();
  expect_equivalence();

  for (uint64_t i = 0; i < kMaxValue; ++i) {
    random_insert();
  }

  for (uint64_t i = 0; i < kMaxValue; ++i) {
    random_erase_range();
  }

  expect_equivalence();
}

TEST(DenseSetTest, Intersection) {
  constexpr uint64_t kMaxValue = 5;
  IntDenseSet<uint64_t, 0, kMaxValue> s = {1, 3, 4};
  IntDenseSet<uint64_t, 0, kMaxValue> t = {1, 2, 4};
  IntDenseSet<uint64_t, 0, kMaxValue> u = {1, 4, 5};
  IntDenseSet<uint64_t, 0, kMaxValue> set_intersection = Intersection(s, t, u);
  IntDenseSet<uint64_t, 0, kMaxValue> expectation = {1, 4};
  EXPECT_EQ(set_intersection, expectation);
}

TEST(DenseSetTest, Union) {
  constexpr uint64_t kMaxValue = 5;
  IntDenseSet<uint64_t, 0, kMaxValue> s = {1, 3, 4};
  IntDenseSet<uint64_t, 0, kMaxValue> t = {1, 2, 4};
  IntDenseSet<uint64_t, 0, kMaxValue> u = {1, 5};
  IntDenseSet<uint64_t, 0, kMaxValue> set_union = Union(s, t, u);
  IntDenseSet<uint64_t, 0, kMaxValue> expectation = {1, 2, 3, 4, 5};
  EXPECT_EQ(set_union, expectation);
}

}  // namespace
}  // namespace autofill