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