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
18namespace 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.
68template <typename Underlying> class fallible_iterator {
69private:
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
75public:
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 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
194private:
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.
220template <typename Underlying>
221fallible_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.
227template <typename Underlying>
228fallible_iterator<Underlying> make_fallible_end(Underlying E) {
229 return fallible_iterator<Underlying>::end(std::move(E));
230}
231
232template <typename Underlying>
233iterator_range<fallible_iterator<Underlying>>
234make_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