1 //===- unittests/ADT/FallibleIteratorTest.cpp - fallible_iterator.h tests -===//
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/fallible_iterator.h"
10 #include "llvm/Testing/Support/Error.h"
11 
12 #include "gtest/gtest-spi.h"
13 #include "gtest/gtest.h"
14 
15 #include <utility>
16 #include <vector>
17 
18 using namespace llvm;
19 
20 namespace {
21 
22 using ItemValid = enum { ValidItem, InvalidItem };
23 using LinkValid = enum { ValidLink, InvalidLink };
24 
25 class Item {
26 public:
27   Item(ItemValid V) : V(V) {}
28   bool isValid() const { return V == ValidItem; }
29 
30 private:
31   ItemValid V;
32 };
33 
34 // A utility to mock "bad collections". It supports both invalid items,
35 // where the dereference operator may return an Error, and bad links
36 // where the inc/dec operations may return an Error.
37 // Each element of the mock collection contains a pair of a (possibly broken)
38 // item and link.
39 using FallibleCollection = std::vector<std::pair<Item, LinkValid>>;
40 
41 class FallibleCollectionWalker {
42 public:
43   FallibleCollectionWalker(FallibleCollection &C, unsigned Idx)
44       : C(C), Idx(Idx) {}
45 
46   Item &operator*() { return C[Idx].first; }
47 
48   const Item &operator*() const { return C[Idx].first; }
49 
50   Error inc() {
51     assert(Idx != C.size() && "Walking off end of (mock) collection");
52     if (C[Idx].second == ValidLink) {
53       ++Idx;
54       return Error::success();
55     }
56     return make_error<StringError>("cant get next object in (mock) collection",
57                                    inconvertibleErrorCode());
58   }
59 
60   Error dec() {
61     assert(Idx != 0 && "Walking off start of (mock) collection");
62     --Idx;
63     if (C[Idx].second == ValidLink)
64       return Error::success();
65     return make_error<StringError>("cant get prev object in (mock) collection",
66                                    inconvertibleErrorCode());
67   }
68 
69   friend bool operator==(const FallibleCollectionWalker &LHS,
70                          const FallibleCollectionWalker &RHS) {
71     assert(&LHS.C == &RHS.C && "Comparing iterators across collectionss.");
72     return LHS.Idx == RHS.Idx;
73   }
74 
75 private:
76   FallibleCollection &C;
77   unsigned Idx;
78 };
79 
80 class FallibleCollectionWalkerWithStructDeref
81     : public FallibleCollectionWalker {
82 public:
83   using FallibleCollectionWalker::FallibleCollectionWalker;
84 
85   Item *operator->() { return &this->operator*(); }
86 
87   const Item *operator->() const { return &this->operator*(); }
88 };
89 
90 class FallibleCollectionWalkerWithFallibleDeref
91     : public FallibleCollectionWalker {
92 public:
93   using FallibleCollectionWalker::FallibleCollectionWalker;
94 
95   Expected<Item &> operator*() {
96     auto &I = FallibleCollectionWalker::operator*();
97     if (!I.isValid())
98       return make_error<StringError>("bad item", inconvertibleErrorCode());
99     return I;
100   }
101 
102   Expected<const Item &> operator*() const {
103     const auto &I = FallibleCollectionWalker::operator*();
104     if (!I.isValid())
105       return make_error<StringError>("bad item", inconvertibleErrorCode());
106     return I;
107   }
108 };
109 
110 TEST(FallibleIteratorTest, BasicSuccess) {
111 
112   // Check that a basic use-case involing successful iteration over a
113   // "FallibleCollection" works.
114 
115   FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}});
116 
117   FallibleCollectionWalker begin(C, 0);
118   FallibleCollectionWalker end(C, 2);
119 
120   Error Err = Error::success();
121   for (auto &Elem :
122        make_fallible_range<FallibleCollectionWalker>(begin, end, Err))
123     EXPECT_TRUE(Elem.isValid());
124   cantFail(std::move(Err));
125 }
126 
127 TEST(FallibleIteratorTest, BasicFailure) {
128 
129   // Check that a iteration failure (due to the InvalidLink state on element one
130   // of the fallible collection) breaks out of the loop and raises an Error.
131 
132   FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, InvalidLink}});
133 
134   FallibleCollectionWalker begin(C, 0);
135   FallibleCollectionWalker end(C, 2);
136 
137   Error Err = Error::success();
138   for (auto &Elem :
139        make_fallible_range<FallibleCollectionWalker>(begin, end, Err))
140     EXPECT_TRUE(Elem.isValid());
141 
142   EXPECT_THAT_ERROR(std::move(Err), Failed()) << "Expected failure value";
143 }
144 
145 TEST(FallibleIteratorTest, NoRedundantErrorCheckOnEarlyExit) {
146 
147   // Check that an early return from the loop body does not require a redundant
148   // check of Err.
149 
150   FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}});
151 
152   FallibleCollectionWalker begin(C, 0);
153   FallibleCollectionWalker end(C, 2);
154 
155   Error Err = Error::success();
156   for (auto &Elem :
157        make_fallible_range<FallibleCollectionWalker>(begin, end, Err)) {
158     (void)Elem;
159     return;
160   }
161   // Err not checked, but should be ok because we exit from the loop
162   // body.
163 }
164 
165 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
166 TEST(FallibleIteratorTest, RegularLoopExitRequiresErrorCheck) {
167 
168   // Check that Err must be checked after a normal (i.e. not early) loop exit
169   // by failing to check and expecting program death (due to the unchecked
170   // error).
171 
172   EXPECT_DEATH(
173       {
174         FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}});
175 
176         FallibleCollectionWalker begin(C, 0);
177         FallibleCollectionWalker end(C, 2);
178 
179         Error Err = Error::success();
180         for (auto &Elem :
181              make_fallible_range<FallibleCollectionWalker>(begin, end, Err))
182           (void)Elem;
183       },
184       "Program aborted due to an unhandled Error:")
185       << "Normal (i.e. not early) loop exit should require an error check";
186 }
187 #endif
188 
189 TEST(FallibleIteratorTest, RawIncrementAndDecrementBehavior) {
190 
191   // Check the exact behavior of increment / decrement.
192 
193   FallibleCollection C({{ValidItem, ValidLink},
194                         {ValidItem, InvalidLink},
195                         {ValidItem, ValidLink},
196                         {ValidItem, InvalidLink}});
197 
198   {
199     // One increment from begin succeeds.
200     Error Err = Error::success();
201     auto I = make_fallible_itr(FallibleCollectionWalker(C, 0), Err);
202     ++I;
203     EXPECT_THAT_ERROR(std::move(Err), Succeeded());
204   }
205 
206   {
207     // Two increments from begin fail.
208     Error Err = Error::success();
209     auto I = make_fallible_itr(FallibleCollectionWalker(C, 0), Err);
210     ++I;
211     EXPECT_THAT_ERROR(std::move(Err), Succeeded());
212     ++I;
213     EXPECT_THAT_ERROR(std::move(Err), Failed()) << "Expected failure value";
214   }
215 
216   {
217     // One decement from element three succeeds.
218     Error Err = Error::success();
219     auto I = make_fallible_itr(FallibleCollectionWalker(C, 3), Err);
220     --I;
221     EXPECT_THAT_ERROR(std::move(Err), Succeeded());
222   }
223 
224   {
225     // One decement from element three succeeds.
226     Error Err = Error::success();
227     auto I = make_fallible_itr(FallibleCollectionWalker(C, 3), Err);
228     --I;
229     EXPECT_THAT_ERROR(std::move(Err), Succeeded());
230     --I;
231     EXPECT_THAT_ERROR(std::move(Err), Failed());
232   }
233 }
234 
235 TEST(FallibleIteratorTest, CheckStructDerefOperatorSupport) {
236   // Check that the fallible_iterator wrapper forwards through to the
237   // underlying iterator's structure dereference operator if present.
238 
239   FallibleCollection C({{ValidItem, ValidLink},
240                         {ValidItem, ValidLink},
241                         {InvalidItem, InvalidLink}});
242 
243   FallibleCollectionWalkerWithStructDeref begin(C, 0);
244 
245   {
246     Error Err = Error::success();
247     auto I = make_fallible_itr(begin, Err);
248     EXPECT_TRUE(I->isValid());
249     cantFail(std::move(Err));
250   }
251 
252   {
253     Error Err = Error::success();
254     const auto I = make_fallible_itr(begin, Err);
255     EXPECT_TRUE(I->isValid());
256     cantFail(std::move(Err));
257   }
258 }
259 
260 TEST(FallibleIteratorTest, CheckDerefToExpectedSupport) {
261 
262   // Check that the fallible_iterator wrapper forwards value types, in
263   // particular llvm::Expected, correctly.
264 
265   FallibleCollection C({{ValidItem, ValidLink},
266                         {InvalidItem, ValidLink},
267                         {ValidItem, ValidLink}});
268 
269   FallibleCollectionWalkerWithFallibleDeref begin(C, 0);
270   FallibleCollectionWalkerWithFallibleDeref end(C, 3);
271 
272   Error Err = Error::success();
273   auto I = make_fallible_itr(begin, Err);
274   auto E = make_fallible_end(end);
275 
276   Expected<Item> V1 = *I;
277   EXPECT_THAT_ERROR(V1.takeError(), Succeeded());
278   ++I;
279   EXPECT_NE(I, E); // Implicitly check error.
280   Expected<Item> V2 = *I;
281   EXPECT_THAT_ERROR(V2.takeError(), Failed());
282   ++I;
283   EXPECT_NE(I, E); // Implicitly check error.
284   Expected<Item> V3 = *I;
285   EXPECT_THAT_ERROR(V3.takeError(), Succeeded());
286   ++I;
287   EXPECT_EQ(I, E);
288   cantFail(std::move(Err));
289 }
290 
291 } // namespace
292