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