1351278Sdim//===--- fallible_iterator.h - Wrapper for fallible iterators ---*- C++ -*-===// 2351278Sdim// 3351278Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351278Sdim// See https://llvm.org/LICENSE.txt for license information. 5351278Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351278Sdim// 7351278Sdim//===----------------------------------------------------------------------===// 8351278Sdim 9351278Sdim#ifndef LLVM_ADT_FALLIBLE_ITERATOR_H 10351278Sdim#define LLVM_ADT_FALLIBLE_ITERATOR_H 11351278Sdim 12351278Sdim#include "llvm/ADT/PointerIntPair.h" 13351278Sdim#include "llvm/ADT/iterator_range.h" 14351278Sdim#include "llvm/Support/Error.h" 15351278Sdim 16351278Sdim#include <type_traits> 17351278Sdim 18351278Sdimnamespace llvm { 19351278Sdim 20351278Sdim/// A wrapper class for fallible iterators. 21351278Sdim/// 22351278Sdim/// The fallible_iterator template wraps an underlying iterator-like class 23351278Sdim/// whose increment and decrement operations are replaced with fallible versions 24351278Sdim/// like: 25351278Sdim/// 26351278Sdim/// @code{.cpp} 27351278Sdim/// Error inc(); 28351278Sdim/// Error dec(); 29351278Sdim/// @endcode 30351278Sdim/// 31351278Sdim/// It produces an interface that is (mostly) compatible with a traditional 32351278Sdim/// c++ iterator, including ++ and -- operators that do not fail. 33351278Sdim/// 34351278Sdim/// Instances of the wrapper are constructed with an instance of the 35351278Sdim/// underlying iterator and (for non-end iterators) a reference to an Error 36351278Sdim/// instance. If the underlying increment/decrement operations fail, the Error 37351278Sdim/// is returned via this reference, and the resulting iterator value set to an 38351278Sdim/// end-of-range sentinel value. This enables the following loop idiom: 39351278Sdim/// 40351278Sdim/// @code{.cpp} 41351278Sdim/// class Archive { // E.g. Potentially malformed on-disk archive 42351278Sdim/// public: 43351278Sdim/// fallible_iterator<ArchiveChildItr> children_begin(Error &Err); 44351278Sdim/// fallible_iterator<ArchiveChildItr> children_end(); 45351278Sdim/// iterator_range<fallible_iterator<ArchiveChildItr>> 46351278Sdim/// children(Error &Err) { 47351278Sdim/// return make_range(children_begin(Err), children_end()); 48351278Sdim/// //... 49351278Sdim/// }; 50351278Sdim/// 51351278Sdim/// void walk(Archive &A) { 52351278Sdim/// Error Err = Error::success(); 53351278Sdim/// for (auto &C : A.children(Err)) { 54351278Sdim/// // Loop body only entered when increment succeeds. 55351278Sdim/// } 56351278Sdim/// if (Err) { 57351278Sdim/// // handle error. 58351278Sdim/// } 59351278Sdim/// } 60351278Sdim/// @endcode 61351278Sdim/// 62351278Sdim/// The wrapper marks the referenced Error as unchecked after each increment 63351278Sdim/// and/or decrement operation, and clears the unchecked flag when a non-end 64351278Sdim/// value is compared against end (since, by the increment invariant, not being 65351278Sdim/// an end value proves that there was no error, and is equivalent to checking 66351278Sdim/// that the Error is success). This allows early exits from the loop body 67351278Sdim/// without requiring redundant error checks. 68351278Sdimtemplate <typename Underlying> class fallible_iterator { 69351278Sdimprivate: 70351278Sdim template <typename T> 71351278Sdim using enable_if_struct_deref_supported = std::enable_if< 72351278Sdim !std::is_void<decltype(std::declval<T>().operator->())>::value, 73351278Sdim decltype(std::declval<T>().operator->())>; 74351278Sdim 75351278Sdimpublic: 76351278Sdim /// Construct a fallible iterator that *cannot* be used as an end-of-range 77351278Sdim /// value. 78351278Sdim /// 79351278Sdim /// A value created by this method can be dereferenced, incremented, 80351278Sdim /// decremented and compared, providing the underlying type supports it. 81351278Sdim /// 82351278Sdim /// The error that is passed in will be initially marked as checked, so if the 83351278Sdim /// iterator is not used at all the Error need not be checked. 84351278Sdim static fallible_iterator itr(Underlying I, Error &Err) { 85351278Sdim (void)!!Err; 86351278Sdim return fallible_iterator(std::move(I), &Err); 87351278Sdim } 88351278Sdim 89351278Sdim /// Construct a fallible iteratro that can be used as an end-of-range value. 90351278Sdim /// 91351278Sdim /// A value created by this method can be dereferenced (if the underlying 92351278Sdim /// value points at a valid value) and compared, but not incremented or 93351278Sdim /// decremented. 94351278Sdim static fallible_iterator end(Underlying I) { 95351278Sdim return fallible_iterator(std::move(I), nullptr); 96351278Sdim } 97351278Sdim 98351278Sdim /// Forward dereference to the underlying iterator. 99351278Sdim auto operator*() -> decltype(*std::declval<Underlying>()) { return *I; } 100351278Sdim 101351278Sdim /// Forward const dereference to the underlying iterator. 102351278Sdim auto operator*() const -> decltype(*std::declval<const Underlying>()) { 103351278Sdim return *I; 104351278Sdim } 105351278Sdim 106351278Sdim /// Forward structure dereference to the underlying iterator (if the 107351278Sdim /// underlying iterator supports it). 108351278Sdim template <typename T = Underlying> 109351278Sdim typename enable_if_struct_deref_supported<T>::type operator->() { 110351278Sdim return I.operator->(); 111351278Sdim } 112351278Sdim 113351278Sdim /// Forward const structure dereference to the underlying iterator (if the 114351278Sdim /// underlying iterator supports it). 115351278Sdim template <typename T = Underlying> 116351278Sdim typename enable_if_struct_deref_supported<const T>::type operator->() const { 117351278Sdim return I.operator->(); 118351278Sdim } 119351278Sdim 120351278Sdim /// Increment the fallible iterator. 121351278Sdim /// 122351278Sdim /// If the underlying 'inc' operation fails, this will set the Error value 123351278Sdim /// and update this iterator value to point to end-of-range. 124351278Sdim /// 125351278Sdim /// The Error value is marked as needing checking, regardless of whether the 126351278Sdim /// 'inc' operation succeeds or fails. 127351278Sdim fallible_iterator &operator++() { 128351278Sdim assert(getErrPtr() && "Cannot increment end iterator"); 129351278Sdim if (auto Err = I.inc()) 130351278Sdim handleError(std::move(Err)); 131351278Sdim else 132351278Sdim resetCheckedFlag(); 133351278Sdim return *this; 134351278Sdim } 135351278Sdim 136351278Sdim /// Decrement the fallible iterator. 137351278Sdim /// 138351278Sdim /// If the underlying 'dec' operation fails, this will set the Error value 139351278Sdim /// and update this iterator value to point to end-of-range. 140351278Sdim /// 141351278Sdim /// The Error value is marked as needing checking, regardless of whether the 142351278Sdim /// 'dec' operation succeeds or fails. 143351278Sdim fallible_iterator &operator--() { 144351278Sdim assert(getErrPtr() && "Cannot decrement end iterator"); 145351278Sdim if (auto Err = I.dec()) 146351278Sdim handleError(std::move(Err)); 147351278Sdim else 148351278Sdim resetCheckedFlag(); 149351278Sdim return *this; 150351278Sdim } 151351278Sdim 152351278Sdim /// Compare fallible iterators for equality. 153351278Sdim /// 154351278Sdim /// Returns true if both LHS and RHS are end-of-range values, or if both are 155351278Sdim /// non-end-of-range values whose underlying iterator values compare equal. 156351278Sdim /// 157351278Sdim /// If this is a comparison between an end-of-range iterator and a 158351278Sdim /// non-end-of-range iterator, then the Error (referenced by the 159351278Sdim /// non-end-of-range value) is marked as checked: Since all 160351278Sdim /// increment/decrement operations result in an end-of-range value, comparing 161351278Sdim /// false against end-of-range is equivalent to checking that the Error value 162351278Sdim /// is success. This flag management enables early returns from loop bodies 163351278Sdim /// without redundant Error checks. 164351278Sdim friend bool operator==(const fallible_iterator &LHS, 165351278Sdim const fallible_iterator &RHS) { 166351278Sdim // If both iterators are in the end state they compare 167351278Sdim // equal, regardless of whether either is valid. 168351278Sdim if (LHS.isEnd() && RHS.isEnd()) 169351278Sdim return true; 170351278Sdim 171351278Sdim assert(LHS.isValid() && RHS.isValid() && 172351278Sdim "Invalid iterators can only be compared against end"); 173351278Sdim 174351278Sdim bool Equal = LHS.I == RHS.I; 175351278Sdim 176351278Sdim // If the iterators differ and this is a comparison against end then mark 177351278Sdim // the Error as checked. 178351278Sdim if (!Equal) { 179351278Sdim if (LHS.isEnd()) 180351278Sdim (void)!!*RHS.getErrPtr(); 181351278Sdim else 182351278Sdim (void)!!*LHS.getErrPtr(); 183351278Sdim } 184351278Sdim 185351278Sdim return Equal; 186351278Sdim } 187351278Sdim 188351278Sdim /// Compare fallible iterators for inequality. 189351278Sdim /// 190351278Sdim /// See notes for operator==. 191351278Sdim friend bool operator!=(const fallible_iterator &LHS, 192351278Sdim const fallible_iterator &RHS) { 193351278Sdim return !(LHS == RHS); 194351278Sdim } 195351278Sdim 196351278Sdimprivate: 197351278Sdim fallible_iterator(Underlying I, Error *Err) 198351278Sdim : I(std::move(I)), ErrState(Err, false) {} 199351278Sdim 200351278Sdim Error *getErrPtr() const { return ErrState.getPointer(); } 201351278Sdim 202351278Sdim bool isEnd() const { return getErrPtr() == nullptr; } 203351278Sdim 204351278Sdim bool isValid() const { return !ErrState.getInt(); } 205351278Sdim 206351278Sdim void handleError(Error Err) { 207351278Sdim *getErrPtr() = std::move(Err); 208351278Sdim ErrState.setPointer(nullptr); 209351278Sdim ErrState.setInt(true); 210351278Sdim } 211351278Sdim 212351278Sdim void resetCheckedFlag() { 213351278Sdim *getErrPtr() = Error::success(); 214351278Sdim } 215351278Sdim 216351278Sdim Underlying I; 217351278Sdim mutable PointerIntPair<Error *, 1> ErrState; 218351278Sdim}; 219351278Sdim 220351278Sdim/// Convenience wrapper to make a fallible_iterator value from an instance 221351278Sdim/// of an underlying iterator and an Error reference. 222351278Sdimtemplate <typename Underlying> 223351278Sdimfallible_iterator<Underlying> make_fallible_itr(Underlying I, Error &Err) { 224351278Sdim return fallible_iterator<Underlying>::itr(std::move(I), Err); 225351278Sdim} 226351278Sdim 227351278Sdim/// Convenience wrapper to make a fallible_iterator end value from an instance 228351278Sdim/// of an underlying iterator. 229351278Sdimtemplate <typename Underlying> 230351278Sdimfallible_iterator<Underlying> make_fallible_end(Underlying E) { 231351278Sdim return fallible_iterator<Underlying>::end(std::move(E)); 232351278Sdim} 233351278Sdim 234351278Sdimtemplate <typename Underlying> 235351278Sdimiterator_range<fallible_iterator<Underlying>> 236351278Sdimmake_fallible_range(Underlying I, Underlying E, Error &Err) { 237351278Sdim return make_range(make_fallible_itr(std::move(I), Err), 238351278Sdim make_fallible_end(std::move(E))); 239351278Sdim} 240351278Sdim 241351278Sdim} // end namespace llvm 242351278Sdim 243351278Sdim#endif // LLVM_ADT_FALLIBLE_ITERATOR_H 244