1 //===--- fallible_iterator.h - Wrapper for fallible iterators ---*- C++ -*-===//
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 #ifndef LLVM_ADT_FALLIBLE_ITERATOR_H
10 #define LLVM_ADT_FALLIBLE_ITERATOR_H
11
12 #include "llvm/ADT/PointerIntPair.h"
13 #include "llvm/ADT/iterator_range.h"
14 #include "llvm/Support/Error.h"
15
16 #include <type_traits>
17
18 namespace llvm {
19
20 /// A wrapper class for fallible iterators.
21 ///
22 /// The fallible_iterator template wraps an underlying iterator-like class
23 /// whose increment and decrement operations are replaced with fallible versions
24 /// like:
25 ///
26 /// @code{.cpp}
27 /// Error inc();
28 /// Error dec();
29 /// @endcode
30 ///
31 /// It produces an interface that is (mostly) compatible with a traditional
32 /// c++ iterator, including ++ and -- operators that do not fail.
33 ///
34 /// Instances of the wrapper are constructed with an instance of the
35 /// underlying iterator and (for non-end iterators) a reference to an Error
36 /// instance. If the underlying increment/decrement operations fail, the Error
37 /// is returned via this reference, and the resulting iterator value set to an
38 /// end-of-range sentinel value. This enables the following loop idiom:
39 ///
40 /// @code{.cpp}
41 /// class Archive { // E.g. Potentially malformed on-disk archive
42 /// public:
43 /// fallible_iterator<ArchiveChildItr> children_begin(Error &Err);
44 /// fallible_iterator<ArchiveChildItr> children_end();
45 /// iterator_range<fallible_iterator<ArchiveChildItr>>
46 /// children(Error &Err) {
47 /// return make_range(children_begin(Err), children_end());
48 /// //...
49 /// };
50 ///
51 /// void walk(Archive &A) {
52 /// Error Err = Error::success();
53 /// for (auto &C : A.children(Err)) {
54 /// // Loop body only entered when increment succeeds.
55 /// }
56 /// if (Err) {
57 /// // handle error.
58 /// }
59 /// }
60 /// @endcode
61 ///
62 /// The wrapper marks the referenced Error as unchecked after each increment
63 /// and/or decrement operation, and clears the unchecked flag when a non-end
64 /// value is compared against end (since, by the increment invariant, not being
65 /// an end value proves that there was no error, and is equivalent to checking
66 /// that the Error is success). This allows early exits from the loop body
67 /// without requiring redundant error checks.
68 template <typename Underlying> class fallible_iterator {
69 private:
70 template <typename T>
71 using enable_if_struct_deref_supported = std::enable_if<
72 !std::is_void<decltype(std::declval<T>().operator->())>::value,
73 decltype(std::declval<T>().operator->())>;
74
75 public:
76 /// Construct a fallible iterator that *cannot* be used as an end-of-range
77 /// value.
78 ///
79 /// A value created by this method can be dereferenced, incremented,
80 /// decremented and compared, providing the underlying type supports it.
81 ///
82 /// The error that is passed in will be initially marked as checked, so if the
83 /// iterator is not used at all the Error need not be checked.
itr(Underlying I,Error & Err)84 static fallible_iterator itr(Underlying I, Error &Err) {
85 (void)!!Err;
86 return fallible_iterator(std::move(I), &Err);
87 }
88
89 /// Construct a fallible iterator that can be used as an end-of-range value.
90 ///
91 /// A value created by this method can be dereferenced (if the underlying
92 /// value points at a valid value) and compared, but not incremented or
93 /// decremented.
end(Underlying I)94 static fallible_iterator end(Underlying I) {
95 return fallible_iterator(std::move(I), nullptr);
96 }
97
98 /// Forward dereference to the underlying iterator.
decltype(auto)99 decltype(auto) operator*() { return *I; }
100
101 /// Forward const dereference to the underlying iterator.
decltype(auto)102 decltype(auto) operator*() const { return *I; }
103
104 /// Forward structure dereference to the underlying iterator (if the
105 /// underlying iterator supports it).
106 template <typename T = Underlying>
107 typename enable_if_struct_deref_supported<T>::type operator->() {
108 return I.operator->();
109 }
110
111 /// Forward const structure dereference to the underlying iterator (if the
112 /// underlying iterator supports it).
113 template <typename T = Underlying>
114 typename enable_if_struct_deref_supported<const T>::type operator->() const {
115 return I.operator->();
116 }
117
118 /// Increment the fallible iterator.
119 ///
120 /// If the underlying 'inc' operation fails, this will set the Error value
121 /// and update this iterator value to point to end-of-range.
122 ///
123 /// The Error value is marked as needing checking, regardless of whether the
124 /// 'inc' operation succeeds or fails.
125 fallible_iterator &operator++() {
126 assert(getErrPtr() && "Cannot increment end iterator");
127 if (auto Err = I.inc())
128 handleError(std::move(Err));
129 else
130 resetCheckedFlag();
131 return *this;
132 }
133
134 /// Decrement the fallible iterator.
135 ///
136 /// If the underlying 'dec' operation fails, this will set the Error value
137 /// and update this iterator value to point to end-of-range.
138 ///
139 /// The Error value is marked as needing checking, regardless of whether the
140 /// 'dec' operation succeeds or fails.
141 fallible_iterator &operator--() {
142 assert(getErrPtr() && "Cannot decrement end iterator");
143 if (auto Err = I.dec())
144 handleError(std::move(Err));
145 else
146 resetCheckedFlag();
147 return *this;
148 }
149
150 /// Compare fallible iterators for equality.
151 ///
152 /// Returns true if both LHS and RHS are end-of-range values, or if both are
153 /// non-end-of-range values whose underlying iterator values compare equal.
154 ///
155 /// If this is a comparison between an end-of-range iterator and a
156 /// non-end-of-range iterator, then the Error (referenced by the
157 /// non-end-of-range value) is marked as checked: Since all
158 /// increment/decrement operations result in an end-of-range value, comparing
159 /// false against end-of-range is equivalent to checking that the Error value
160 /// is success. This flag management enables early returns from loop bodies
161 /// without redundant Error checks.
162 friend bool operator==(const fallible_iterator &LHS,
163 const fallible_iterator &RHS) {
164 // If both iterators are in the end state they compare
165 // equal, regardless of whether either is valid.
166 if (LHS.isEnd() && RHS.isEnd())
167 return true;
168
169 assert(LHS.isValid() && RHS.isValid() &&
170 "Invalid iterators can only be compared against end");
171
172 bool Equal = LHS.I == RHS.I;
173
174 // If the iterators differ and this is a comparison against end then mark
175 // the Error as checked.
176 if (!Equal) {
177 if (LHS.isEnd())
178 (void)!!*RHS.getErrPtr();
179 else
180 (void)!!*LHS.getErrPtr();
181 }
182
183 return Equal;
184 }
185
186 /// Compare fallible iterators for inequality.
187 ///
188 /// See notes for operator==.
189 friend bool operator!=(const fallible_iterator &LHS,
190 const fallible_iterator &RHS) {
191 return !(LHS == RHS);
192 }
193
194 private:
fallible_iterator(Underlying I,Error * Err)195 fallible_iterator(Underlying I, Error *Err)
196 : I(std::move(I)), ErrState(Err, false) {}
197
getErrPtr()198 Error *getErrPtr() const { return ErrState.getPointer(); }
199
isEnd()200 bool isEnd() const { return getErrPtr() == nullptr; }
201
isValid()202 bool isValid() const { return !ErrState.getInt(); }
203
handleError(Error Err)204 void handleError(Error Err) {
205 *getErrPtr() = std::move(Err);
206 ErrState.setPointer(nullptr);
207 ErrState.setInt(true);
208 }
209
resetCheckedFlag()210 void resetCheckedFlag() {
211 *getErrPtr() = Error::success();
212 }
213
214 Underlying I;
215 mutable PointerIntPair<Error *, 1> ErrState;
216 };
217
218 /// Convenience wrapper to make a fallible_iterator value from an instance
219 /// of an underlying iterator and an Error reference.
220 template <typename Underlying>
make_fallible_itr(Underlying I,Error & Err)221 fallible_iterator<Underlying> make_fallible_itr(Underlying I, Error &Err) {
222 return fallible_iterator<Underlying>::itr(std::move(I), Err);
223 }
224
225 /// Convenience wrapper to make a fallible_iterator end value from an instance
226 /// of an underlying iterator.
227 template <typename Underlying>
make_fallible_end(Underlying E)228 fallible_iterator<Underlying> make_fallible_end(Underlying E) {
229 return fallible_iterator<Underlying>::end(std::move(E));
230 }
231
232 template <typename Underlying>
233 iterator_range<fallible_iterator<Underlying>>
make_fallible_range(Underlying I,Underlying E,Error & Err)234 make_fallible_range(Underlying I, Underlying E, Error &Err) {
235 return make_range(make_fallible_itr(std::move(I), Err),
236 make_fallible_end(std::move(E)));
237 }
238
239 } // end namespace llvm
240
241 #endif // LLVM_ADT_FALLIBLE_ITERATOR_H
242