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   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 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   static fallible_iterator end(Underlying I) {
95     return fallible_iterator(std::move(I), nullptr);
96   }
97 
98   /// Forward dereference to the underlying iterator.
99   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   fallible_iterator &operator++() {
128     assert(getErrPtr() && "Cannot increment end iterator");
129     if (auto Err = I.inc())
130       handleError(std::move(Err));
131     else
132       resetCheckedFlag();
133     return *this;
134   }
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                          const fallible_iterator &RHS) {
166     // If both iterators are in the end state they compare
167     // equal, regardless of whether either is valid.
168     if (LHS.isEnd() && RHS.isEnd())
169       return true;
170 
171     assert(LHS.isValid() && RHS.isValid() &&
172            "Invalid iterators can only be compared against end");
173 
174     bool Equal = LHS.I == RHS.I;
175 
176     // If the iterators differ and this is a comparison against end then mark
177     // the Error as checked.
178     if (!Equal) {
179       if (LHS.isEnd())
180         (void)!!*RHS.getErrPtr();
181       else
182         (void)!!*LHS.getErrPtr();
183     }
184 
185     return Equal;
186   }
187 
188   /// Compare fallible iterators for inequality.
189   ///
190   /// See notes for operator==.
191   friend bool operator!=(const fallible_iterator &LHS,
192                          const fallible_iterator &RHS) {
193     return !(LHS == RHS);
194   }
195 
196 private:
197   fallible_iterator(Underlying I, Error *Err)
198       : I(std::move(I)), ErrState(Err, false) {}
199 
200   Error *getErrPtr() const { return ErrState.getPointer(); }
201 
202   bool isEnd() const { return getErrPtr() == nullptr; }
203 
204   bool isValid() const { return !ErrState.getInt(); }
205 
206   void handleError(Error Err) {
207     *getErrPtr() = std::move(Err);
208     ErrState.setPointer(nullptr);
209     ErrState.setInt(true);
210   }
211 
212   void resetCheckedFlag() {
213     *getErrPtr() = Error::success();
214   }
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
244