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