/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/fallible_iterator.h
Line | Count | Source (jump to first uncovered line) |
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. |
84 | 1.52k | static fallible_iterator itr(Underlying I, Error &Err) { |
85 | 1.52k | (void)!!Err; |
86 | 1.52k | return fallible_iterator(std::move(I), &Err); |
87 | 1.52k | } |
88 | | |
89 | | /// Construct a fallible iteratro 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 | 1.53k | static fallible_iterator end(Underlying I) { |
95 | 1.53k | return fallible_iterator(std::move(I), nullptr); |
96 | 1.53k | } |
97 | | |
98 | | /// Forward dereference to the underlying iterator. |
99 | 3.67k | auto operator*() -> decltype(*std::declval<Underlying>()) { return *I; } |
100 | | |
101 | | /// Forward const dereference to the underlying iterator. |
102 | | auto operator*() const -> decltype(*std::declval<const Underlying>()) { |
103 | | return *I; |
104 | | } |
105 | | |
106 | | /// Forward structure dereference to the underlying iterator (if the |
107 | | /// underlying iterator supports it). |
108 | | template <typename T = Underlying> |
109 | | typename enable_if_struct_deref_supported<T>::type operator->() { |
110 | | return I.operator->(); |
111 | | } |
112 | | |
113 | | /// Forward const structure dereference to the underlying iterator (if the |
114 | | /// underlying iterator supports it). |
115 | | template <typename T = Underlying> |
116 | | typename enable_if_struct_deref_supported<const T>::type operator->() const { |
117 | | return I.operator->(); |
118 | | } |
119 | | |
120 | | /// Increment the fallible iterator. |
121 | | /// |
122 | | /// If the underlying 'inc' operation fails, this will set the Error value |
123 | | /// and update this iterator value to point to end-of-range. |
124 | | /// |
125 | | /// The Error value is marked as needing checking, regardless of whether the |
126 | | /// 'inc' operation succeeds or fails. |
127 | 2.76k | fallible_iterator &operator++() { |
128 | 2.76k | assert(getErrPtr() && "Cannot increment end iterator"); |
129 | 2.76k | if (auto Err = I.inc()) |
130 | 4 | handleError(std::move(Err)); |
131 | 2.76k | else |
132 | 2.76k | resetCheckedFlag(); |
133 | 2.76k | return *this; |
134 | 2.76k | } |
135 | | |
136 | | /// Decrement the fallible iterator. |
137 | | /// |
138 | | /// If the underlying 'dec' operation fails, this will set the Error value |
139 | | /// and update this iterator value to point to end-of-range. |
140 | | /// |
141 | | /// The Error value is marked as needing checking, regardless of whether the |
142 | | /// 'dec' operation succeeds or fails. |
143 | | fallible_iterator &operator--() { |
144 | | assert(getErrPtr() && "Cannot decrement end iterator"); |
145 | | if (auto Err = I.dec()) |
146 | | handleError(std::move(Err)); |
147 | | else |
148 | | resetCheckedFlag(); |
149 | | return *this; |
150 | | } |
151 | | |
152 | | /// Compare fallible iterators for equality. |
153 | | /// |
154 | | /// Returns true if both LHS and RHS are end-of-range values, or if both are |
155 | | /// non-end-of-range values whose underlying iterator values compare equal. |
156 | | /// |
157 | | /// If this is a comparison between an end-of-range iterator and a |
158 | | /// non-end-of-range iterator, then the Error (referenced by the |
159 | | /// non-end-of-range value) is marked as checked: Since all |
160 | | /// increment/decrement operations result in an end-of-range value, comparing |
161 | | /// false against end-of-range is equivalent to checking that the Error value |
162 | | /// is success. This flag management enables early returns from loop bodies |
163 | | /// without redundant Error checks. |
164 | | friend bool operator==(const fallible_iterator &LHS, |
165 | 3.64k | const fallible_iterator &RHS) { |
166 | 3.64k | // If both iterators are in the end state they compare |
167 | 3.64k | // equal, regardless of whether either is valid. |
168 | 3.64k | if (LHS.isEnd() && RHS.isEnd()7 ) |
169 | 7 | return true; |
170 | 3.64k | |
171 | 3.64k | assert(LHS.isValid() && RHS.isValid() && |
172 | 3.64k | "Invalid iterators can only be compared against end"); |
173 | 3.64k | |
174 | 3.64k | bool Equal = LHS.I == RHS.I; |
175 | 3.64k | |
176 | 3.64k | // If the iterators differ and this is a comparison against end then mark |
177 | 3.64k | // the Error as checked. |
178 | 3.64k | if (!Equal) { |
179 | 3.03k | if (LHS.isEnd()) |
180 | 0 | (void)!!*RHS.getErrPtr(); |
181 | 3.03k | else |
182 | 3.03k | (void)!!*LHS.getErrPtr(); |
183 | 3.03k | } |
184 | 3.64k | |
185 | 3.64k | return Equal; |
186 | 3.64k | } |
187 | | |
188 | | /// Compare fallible iterators for inequality. |
189 | | /// |
190 | | /// See notes for operator==. |
191 | | friend bool operator!=(const fallible_iterator &LHS, |
192 | 2.17k | const fallible_iterator &RHS) { |
193 | 2.17k | return !(LHS == RHS); |
194 | 2.17k | } |
195 | | |
196 | | private: |
197 | | fallible_iterator(Underlying I, Error *Err) |
198 | 3.05k | : I(std::move(I)), ErrState(Err, false) {} |
199 | | |
200 | 12.4k | Error *getErrPtr() const { return ErrState.getPointer(); } |
201 | | |
202 | 6.68k | bool isEnd() const { return getErrPtr() == nullptr; } |
203 | | |
204 | | bool isValid() const { return !ErrState.getInt(); } |
205 | | |
206 | 4 | void handleError(Error Err) { |
207 | 4 | *getErrPtr() = std::move(Err); |
208 | 4 | ErrState.setPointer(nullptr); |
209 | 4 | ErrState.setInt(true); |
210 | 4 | } |
211 | | |
212 | 2.76k | void resetCheckedFlag() { |
213 | 2.76k | *getErrPtr() = Error::success(); |
214 | 2.76k | } |
215 | | |
216 | | Underlying I; |
217 | | mutable PointerIntPair<Error *, 1> ErrState; |
218 | | }; |
219 | | |
220 | | /// Convenience wrapper to make a fallible_iterator value from an instance |
221 | | /// of an underlying iterator and an Error reference. |
222 | | template <typename Underlying> |
223 | | fallible_iterator<Underlying> make_fallible_itr(Underlying I, Error &Err) { |
224 | | return fallible_iterator<Underlying>::itr(std::move(I), Err); |
225 | | } |
226 | | |
227 | | /// Convenience wrapper to make a fallible_iterator end value from an instance |
228 | | /// of an underlying iterator. |
229 | | template <typename Underlying> |
230 | | fallible_iterator<Underlying> make_fallible_end(Underlying E) { |
231 | | return fallible_iterator<Underlying>::end(std::move(E)); |
232 | | } |
233 | | |
234 | | template <typename Underlying> |
235 | | iterator_range<fallible_iterator<Underlying>> |
236 | | make_fallible_range(Underlying I, Underlying E, Error &Err) { |
237 | | return make_range(make_fallible_itr(std::move(I), Err), |
238 | | make_fallible_end(std::move(E))); |
239 | | } |
240 | | |
241 | | } // end namespace llvm |
242 | | |
243 | | #endif // LLVM_ADT_FALLIBLE_ITERATOR_H |