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