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_t< |
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. |
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. |
94 | static fallible_iterator end(Underlying I) { |
95 | return fallible_iterator(std::move(I), nullptr); |
96 | } |
97 | |
98 | /// Forward dereference to the underlying iterator. |
99 | decltype(auto) operator*() { return *I; } |
100 | |
101 | /// Forward const dereference to the underlying iterator. |
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 | enable_if_struct_deref_supported<T> 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 | enable_if_struct_deref_supported<const T> 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(Err: 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(Err: 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: |
195 | fallible_iterator(Underlying I, Error *Err) |
196 | : I(std::move(I)), ErrState(Err, false) {} |
197 | |
198 | Error *getErrPtr() const { return ErrState.getPointer(); } |
199 | |
200 | bool isEnd() const { return getErrPtr() == nullptr; } |
201 | |
202 | bool isValid() const { return !ErrState.getInt(); } |
203 | |
204 | void handleError(Error Err) { |
205 | *getErrPtr() = std::move(Err); |
206 | ErrState.setPointer(nullptr); |
207 | ErrState.setInt(true); |
208 | } |
209 | |
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> |
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> |
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>> |
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 | |