llvm/unittests/ADT/SequenceTest.cpp

   1 //===- SequenceTest.cpp - Unit tests for a sequence abstraciton -----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/Sequence.h"
  10 #include "llvm/ADT/STLExtras.h"
  11 #include "gmock/gmock.h"
  12 #include "gtest/gtest.h"
  13
  14 #include <algorithm>
  15 #include <numeric>
  16
  17 using namespace llvm;
  18
  19 using testing::ElementsAre;
  20 using testing::IsEmpty;
  21
  22 namespace {
  23
  24 using detail::canTypeFitValue;
  25 using detail::CheckedInt;
  26
  27 using IntegralTypes = testing::Types<uint8_t,   // 0
  28                                      uint16_t,  // 1
  29                                      uint32_t,  // 2
  30                                      uint64_t,  // 3
  31                                      uintmax_t, // 4
  32                                      int8_t,    // 5
  33                                      int16_t,   // 6
  34                                      int32_t,   // 7
  35                                      int64_t,   // 8
  36                                      intmax_t   // 9
  37                                      >;
  38
  39 template <class T> class StrongIntTest : public testing::Test {};
  40 TYPED_TEST_SUITE(StrongIntTest, IntegralTypes, );
  41 TYPED_TEST(StrongIntTest, Operations) {
  42   using T = TypeParam;
  43   auto Max = std::numeric_limits<T>::max();
  44   auto Min = std::numeric_limits<T>::min();
  45
  46   // We bail out for types that are not entirely representable within intmax_t.
  47   if (!canTypeFitValue<intmax_t>(Max) || !canTypeFitValue<intmax_t>(Min))
  48     return;
  49
  50   // All representable values convert back and forth.
  51   EXPECT_EQ(CheckedInt::from(Min).template to<T>(), Min);
  52   EXPECT_EQ(CheckedInt::from(Max).template to<T>(), Max);
  53
  54   // Addition -2, -1, 0, 1, 2.
  55   const T Expected = Max / 2;
  56   const CheckedInt Actual = CheckedInt::from(Expected);
  57   EXPECT_EQ((Actual + -2).template to<T>(), Expected - 2);
  58   EXPECT_EQ((Actual + -1).template to<T>(), Expected - 1);
  59   EXPECT_EQ((Actual + 0).template to<T>(), Expected);
  60   EXPECT_EQ((Actual + 1).template to<T>(), Expected + 1);
  61   EXPECT_EQ((Actual + 2).template to<T>(), Expected + 2);
  62
  63   // EQ/NEQ
  64   EXPECT_EQ(Actual, Actual);
  65   EXPECT_NE(Actual, Actual + 1);
  66
  67   // Difference
  68   EXPECT_EQ(Actual - Actual, 0);
  69   EXPECT_EQ((Actual + 1) - Actual, 1);
  70   EXPECT_EQ(Actual - (Actual + 2), -2);
  71 }
  72
  73 #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
  74 TEST(StrongIntDeathTest, OutOfBounds) {
  75   // Values above 'INTMAX_MAX' are not representable.
  76   EXPECT_DEATH(CheckedInt::from<uintmax_t>(INTMAX_MAX + 1ULL), "Out of bounds");
  77   EXPECT_DEATH(CheckedInt::from<uintmax_t>(UINTMAX_MAX), "Out of bounds");
  78   // Casting to narrower type asserts when out of bounds.
  79   EXPECT_DEATH(CheckedInt::from(-1).to<uint8_t>(), "Out of bounds");
  80   EXPECT_DEATH(CheckedInt::from(256).to<uint8_t>(), "Out of bounds");
  81   // Operations leading to intmax_t overflow assert.
  82   EXPECT_DEATH(CheckedInt::from(INTMAX_MAX) + 1, "Out of bounds");
  83   EXPECT_DEATH(CheckedInt::from(INTMAX_MIN) + -1, "Out of bounds");
  84   EXPECT_DEATH(CheckedInt::from(INTMAX_MIN) - CheckedInt::from(INTMAX_MAX),
  85                "Out of bounds");
  86 }
  87 #endif
  88
  89 TEST(SafeIntIteratorTest, Operations) {
  90   detail::SafeIntIterator<int, false> Forward(0);
  91   detail::SafeIntIterator<int, true> Reverse(0);
  92
  93   const auto SetToZero = [&]() {
  94     Forward = detail::SafeIntIterator<int, false>(0);
  95     Reverse = detail::SafeIntIterator<int, true>(0);
  96   };
  97
  98   // Equality / Comparisons
  99   SetToZero();
 100   EXPECT_EQ(Forward, Forward);
 101   EXPECT_LT(Forward - 1, Forward);
 102   EXPECT_LE(Forward, Forward);
 103   EXPECT_LE(Forward - 1, Forward);
 104   EXPECT_GT(Forward + 1, Forward);
 105   EXPECT_GE(Forward, Forward);
 106   EXPECT_GE(Forward + 1, Forward);
 107
 108   EXPECT_EQ(Reverse, Reverse);
 109   EXPECT_LT(Reverse - 1, Reverse);
 110   EXPECT_LE(Reverse, Reverse);
 111   EXPECT_LE(Reverse - 1, Reverse);
 112   EXPECT_GT(Reverse + 1, Reverse);
 113   EXPECT_GE(Reverse, Reverse);
 114   EXPECT_GE(Reverse + 1, Reverse);
 115
 116   // Dereference
 117   SetToZero();
 118   EXPECT_EQ(*Forward, 0);
 119   EXPECT_EQ(*Reverse, 0);
 120
 121   // Indexing
 122   SetToZero();
 123   EXPECT_EQ(Forward[2], 2);
 124   EXPECT_EQ(Reverse[2], -2);
 125
 126   // Pre-increment
 127   SetToZero();
 128   ++Forward;
 129   EXPECT_EQ(*Forward, 1);
 130   ++Reverse;
 131   EXPECT_EQ(*Reverse, -1);
 132
 133   // Pre-decrement
 134   SetToZero();
 135   --Forward;
 136   EXPECT_EQ(*Forward, -1);
 137   --Reverse;
 138   EXPECT_EQ(*Reverse, 1);
 139
 140   // Post-increment
 141   SetToZero();
 142   EXPECT_EQ(*(Forward++), 0);
 143   EXPECT_EQ(*Forward, 1);
 144   EXPECT_EQ(*(Reverse++), 0);
 145   EXPECT_EQ(*Reverse, -1);
 146
 147   // Post-decrement
 148   SetToZero();
 149   EXPECT_EQ(*(Forward--), 0);
 150   EXPECT_EQ(*Forward, -1);
 151   EXPECT_EQ(*(Reverse--), 0);
 152   EXPECT_EQ(*Reverse, 1);
 153
 154   // Compound assignment operators
 155   SetToZero();
 156   Forward += 1;
 157   EXPECT_EQ(*Forward, 1);
 158   Reverse += 1;
 159   EXPECT_EQ(*Reverse, -1);
 160   SetToZero();
 161   Forward -= 2;
 162   EXPECT_EQ(*Forward, -2);
 163   Reverse -= 2;
 164   EXPECT_EQ(*Reverse, 2);
 165
 166   // Arithmetic
 167   SetToZero();
 168   EXPECT_EQ(*(Forward + 3), 3);
 169   EXPECT_EQ(*(Reverse + 3), -3);
 170   SetToZero();
 171   EXPECT_EQ(*(Forward - 4), -4);
 172   EXPECT_EQ(*(Reverse - 4), 4);
 173
 174   // Difference
 175   SetToZero();
 176   EXPECT_EQ(Forward - Forward, 0);
 177   EXPECT_EQ(Reverse - Reverse, 0);
 178   EXPECT_EQ((Forward + 1) - Forward, 1);
 179   EXPECT_EQ(Forward - (Forward + 1), -1);
 180   EXPECT_EQ((Reverse + 1) - Reverse, 1);
 181   EXPECT_EQ(Reverse - (Reverse + 1), -1);
 182 }
 183
 184 TEST(SequenceTest, Iteration) {
 185   EXPECT_THAT(seq(5), ElementsAre(0, 1, 2, 3, 4));
 186
 187   EXPECT_THAT(seq(-4, 5), ElementsAre(-4, -3, -2, -1, 0, 1, 2, 3, 4));
 188   EXPECT_THAT(reverse(seq(-4, 5)), ElementsAre(4, 3, 2, 1, 0, -1, -2, -3, -4));
 189
 190   EXPECT_THAT(seq_inclusive(-4, 5),
 191               ElementsAre(-4, -3, -2, -1, 0, 1, 2, 3, 4, 5));
 192   EXPECT_THAT(reverse(seq_inclusive(-4, 5)),
 193               ElementsAre(5, 4, 3, 2, 1, 0, -1, -2, -3, -4));
 194 }
 195
 196 TEST(SequenceTest, Distance) {
 197   const auto Forward = seq(0, 10);
 198   EXPECT_EQ(std::distance(Forward.begin(), Forward.end()), 10);
 199   EXPECT_EQ(std::distance(Forward.rbegin(), Forward.rend()), 10);
 200 }
 201
 202 TEST(SequenceTest, Dereference) {
 203   const auto Forward = seq(0, 10).begin();
 204   EXPECT_EQ(Forward[0], 0);
 205   EXPECT_EQ(Forward[2], 2);
 206   const auto Backward = seq(0, 10).rbegin();
 207   EXPECT_EQ(Backward[0], 9);
 208   EXPECT_EQ(Backward[2], 7);
 209 }
 210
 211 enum UntypedEnum { A = 3 };
 212 enum TypedEnum : uint32_t { B = 3 };
 213
 214 namespace X {
 215 enum class ScopedEnum : uint16_t { C = 3 };
 216 } // namespace X
 217
 218 struct S {
 219   enum NestedEnum { D = 4 };
 220   enum NestedEnum2 { E = 5 };
 221
 222 private:
 223   enum NestedEnum3 { F = 6 };
 224   friend struct llvm::enum_iteration_traits<NestedEnum3>;
 225
 226 public:
 227   static auto getNestedEnum3() { return NestedEnum3::F; }
 228 };
 229
 230 } // namespace
 231
 232 namespace llvm {
 233
 234 template <> struct enum_iteration_traits<UntypedEnum> {
 235   static constexpr bool is_iterable = true;
 236 };
 237
 238 template <> struct enum_iteration_traits<TypedEnum> {
 239   static constexpr bool is_iterable = true;
 240 };
 241
 242 template <> struct enum_iteration_traits<X::ScopedEnum> {
 243   static constexpr bool is_iterable = true;
 244 };
 245
 246 template <> struct enum_iteration_traits<S::NestedEnum> {
 247   static constexpr bool is_iterable = true;
 248 };
 249
 250 template <> struct enum_iteration_traits<S::NestedEnum3> {
 251   static constexpr bool is_iterable = true;
 252 };
 253
 254 } // namespace llvm
 255
 256 namespace {
 257
 258 TEST(StrongIntTest, Enums) {
 259   EXPECT_EQ(CheckedInt::from(A).to<UntypedEnum>(), A);
 260   EXPECT_EQ(CheckedInt::from(B).to<TypedEnum>(), B);
 261   EXPECT_EQ(CheckedInt::from(X::ScopedEnum::C).to<X::ScopedEnum>(),
 262             X::ScopedEnum::C);
 263 }
 264
 265 TEST(SequenceTest, IterableEnums) {
 266   EXPECT_THAT(enum_seq(UntypedEnum::A, UntypedEnum::A), IsEmpty());
 267   EXPECT_THAT(enum_seq_inclusive(UntypedEnum::A, UntypedEnum::A),
 268               ElementsAre(UntypedEnum::A));
 269
 270   EXPECT_THAT(enum_seq(TypedEnum::B, TypedEnum::B), IsEmpty());
 271   EXPECT_THAT(enum_seq_inclusive(TypedEnum::B, TypedEnum::B),
 272               ElementsAre(TypedEnum::B));
 273
 274   EXPECT_THAT(enum_seq(X::ScopedEnum::C, X::ScopedEnum::C), IsEmpty());
 275   EXPECT_THAT(enum_seq_inclusive(X::ScopedEnum::C, X::ScopedEnum::C),
 276               ElementsAre(X::ScopedEnum::C));
 277
 278   EXPECT_THAT(enum_seq_inclusive(S::NestedEnum::D, S::NestedEnum::D),
 279               ElementsAre(S::NestedEnum::D));
 280   EXPECT_THAT(enum_seq_inclusive(S::getNestedEnum3(), S::getNestedEnum3()),
 281               ElementsAre(S::getNestedEnum3()));
 282 }
 283
 284 TEST(SequenceTest, NonIterableEnums) {
 285   EXPECT_THAT(enum_seq(S::NestedEnum2::E, S::NestedEnum2::E,
 286                        force_iteration_on_noniterable_enum),
 287               IsEmpty());
 288   EXPECT_THAT(enum_seq_inclusive(S::NestedEnum2::E, S::NestedEnum2::E,
 289                                  force_iteration_on_noniterable_enum),
 290               ElementsAre(S::NestedEnum2::E));
 291
 292   // Check that this also works with enums marked as iterable.
 293   EXPECT_THAT(enum_seq(UntypedEnum::A, UntypedEnum::A,
 294                        force_iteration_on_noniterable_enum),
 295               IsEmpty());
 296   EXPECT_THAT(enum_seq_inclusive(UntypedEnum::A, UntypedEnum::A,
 297                                  force_iteration_on_noniterable_enum),
 298               ElementsAre(UntypedEnum::A));
 299 }
 300
 301 // Reproducer for https://github.com/llvm/llvm-project/issues/61122
 302 TEST(SequenceTest, CorrectReferenceType) {
 303   std::vector<int> vals = {1, 2, 3};
 304   detail::SafeIntIterator<int, false> begin(4);
 305   detail::SafeIntIterator<int, false> end(6);
 306   vals.insert(vals.end(), begin, end);
 307   EXPECT_THAT(vals, ElementsAre(1, 2, 3, 4, 5));
 308 }
 309
 310 } // namespace