llvm/ADT/fallible_iterator.h

0001 //===--- fallible_iterator.h - Wrapper for fallible iterators ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_FALLIBLE_ITERATOR_H
0010 #define LLVM_ADT_FALLIBLE_ITERATOR_H
0011
0012 #include "llvm/ADT/PointerIntPair.h"
0013 #include "llvm/ADT/iterator_range.h"
0014 #include "llvm/Support/Error.h"
0015
0016 #include <type_traits>
0017
0018 namespace llvm {
0019
0020 /// A wrapper class for fallible iterators.
0021 ///
0022 ///   The fallible_iterator template wraps an underlying iterator-like class
0023 /// whose increment and decrement operations are replaced with fallible versions
0024 /// like:
0025 ///
0026 ///   @code{.cpp}
0027 ///   Error inc();
0028 ///   Error dec();
0029 ///   @endcode
0030 ///
0031 ///   It produces an interface that is (mostly) compatible with a traditional
0032 /// c++ iterator, including ++ and -- operators that do not fail.
0033 ///
0034 ///   Instances of the wrapper are constructed with an instance of the
0035 /// underlying iterator and (for non-end iterators) a reference to an Error
0036 /// instance. If the underlying increment/decrement operations fail, the Error
0037 /// is returned via this reference, and the resulting iterator value set to an
0038 /// end-of-range sentinel value. This enables the following loop idiom:
0039 ///
0040 ///   @code{.cpp}
0041 ///   class Archive { // E.g. Potentially malformed on-disk archive
0042 ///   public:
0043 ///     fallible_iterator<ArchiveChildItr> children_begin(Error &Err);
0044 ///     fallible_iterator<ArchiveChildItr> children_end();
0045 ///     iterator_range<fallible_iterator<ArchiveChildItr>>
0046 ///     children(Error &Err) {
0047 ///       return make_range(children_begin(Err), children_end());
0048 ///     //...
0049 ///   };
0050 ///
0051 ///   void walk(Archive &A) {
0052 ///     Error Err = Error::success();
0053 ///     for (auto &C : A.children(Err)) {
0054 ///       // Loop body only entered when increment succeeds.
0055 ///     }
0056 ///     if (Err) {
0057 ///       // handle error.
0058 ///     }
0059 ///   }
0060 ///   @endcode
0061 ///
0062 ///   The wrapper marks the referenced Error as unchecked after each increment
0063 /// and/or decrement operation, and clears the unchecked flag when a non-end
0064 /// value is compared against end (since, by the increment invariant, not being
0065 /// an end value proves that there was no error, and is equivalent to checking
0066 /// that the Error is success). This allows early exits from the loop body
0067 /// without requiring redundant error checks.
0068 template <typename Underlying> class fallible_iterator {
0069 private:
0070   template <typename T>
0071   using enable_if_struct_deref_supported = std::enable_if_t<
0072       !std::is_void<decltype(std::declval<T>().operator->())>::value,
0073       decltype(std::declval<T>().operator->())>;
0074
0075 public:
0076   /// Construct a fallible iterator that *cannot* be used as an end-of-range
0077   /// value.
0078   ///
0079   /// A value created by this method can be dereferenced, incremented,
0080   /// decremented and compared, providing the underlying type supports it.
0081   ///
0082   /// The error that is passed in will be initially marked as checked, so if the
0083   /// iterator is not used at all the Error need not be checked.
0084   static fallible_iterator itr(Underlying I, Error &Err) {
0085     (void)!!Err;
0086     return fallible_iterator(std::move(I), &Err);
0087   }
0088
0089   /// Construct a fallible iterator that can be used as an end-of-range value.
0090   ///
0091   /// A value created by this method can be dereferenced (if the underlying
0092   /// value points at a valid value) and compared, but not incremented or
0093   /// decremented.
0094   static fallible_iterator end(Underlying I) {
0095     return fallible_iterator(std::move(I), nullptr);
0096   }
0097
0098   /// Forward dereference to the underlying iterator.
0099   decltype(auto) operator*() { return *I; }
0100
0101   /// Forward const dereference to the underlying iterator.
0102   decltype(auto) operator*() const { return *I; }
0103
0104   /// Forward structure dereference to the underlying iterator (if the
0105   /// underlying iterator supports it).
0106   template <typename T = Underlying>
0107   enable_if_struct_deref_supported<T> operator->() {
0108     return I.operator->();
0109   }
0110
0111   /// Forward const structure dereference to the underlying iterator (if the
0112   /// underlying iterator supports it).
0113   template <typename T = Underlying>
0114   enable_if_struct_deref_supported<const T> operator->() const {
0115     return I.operator->();
0116   }
0117
0118   /// Increment the fallible iterator.
0119   ///
0120   /// If the underlying 'inc' operation fails, this will set the Error value
0121   /// and update this iterator value to point to end-of-range.
0122   ///
0123   /// The Error value is marked as needing checking, regardless of whether the
0124   /// 'inc' operation succeeds or fails.
0125   fallible_iterator &operator++() {
0126     assert(getErrPtr() && "Cannot increment end iterator");
0127     if (auto Err = I.inc())
0128       handleError(std::move(Err));
0129     else
0130       resetCheckedFlag();
0131     return *this;
0132   }
0133
0134   /// Decrement the fallible iterator.
0135   ///
0136   /// If the underlying 'dec' operation fails, this will set the Error value
0137   /// and update this iterator value to point to end-of-range.
0138   ///
0139   /// The Error value is marked as needing checking, regardless of whether the
0140   /// 'dec' operation succeeds or fails.
0141   fallible_iterator &operator--() {
0142     assert(getErrPtr() && "Cannot decrement end iterator");
0143     if (auto Err = I.dec())
0144       handleError(std::move(Err));
0145     else
0146       resetCheckedFlag();
0147     return *this;
0148   }
0149
0150   /// Compare fallible iterators for equality.
0151   ///
0152   /// Returns true if both LHS and RHS are end-of-range values, or if both are
0153   /// non-end-of-range values whose underlying iterator values compare equal.
0154   ///
0155   /// If this is a comparison between an end-of-range iterator and a
0156   /// non-end-of-range iterator, then the Error (referenced by the
0157   /// non-end-of-range value) is marked as checked: Since all
0158   /// increment/decrement operations result in an end-of-range value, comparing
0159   /// false against end-of-range is equivalent to checking that the Error value
0160   /// is success. This flag management enables early returns from loop bodies
0161   /// without redundant Error checks.
0162   friend bool operator==(const fallible_iterator &LHS,
0163                          const fallible_iterator &RHS) {
0164     // If both iterators are in the end state they compare
0165     // equal, regardless of whether either is valid.
0166     if (LHS.isEnd() && RHS.isEnd())
0167       return true;
0168
0169     assert(LHS.isValid() && RHS.isValid() &&
0170            "Invalid iterators can only be compared against end");
0171
0172     bool Equal = LHS.I == RHS.I;
0173
0174     // If the iterators differ and this is a comparison against end then mark
0175     // the Error as checked.
0176     if (!Equal) {
0177       if (LHS.isEnd())
0178         (void)!!*RHS.getErrPtr();
0179       else
0180         (void)!!*LHS.getErrPtr();
0181     }
0182
0183     return Equal;
0184   }
0185
0186   /// Compare fallible iterators for inequality.
0187   ///
0188   /// See notes for operator==.
0189   friend bool operator!=(const fallible_iterator &LHS,
0190                          const fallible_iterator &RHS) {
0191     return !(LHS == RHS);
0192   }
0193
0194 private:
0195   fallible_iterator(Underlying I, Error *Err)
0196       : I(std::move(I)), ErrState(Err, false) {}
0197
0198   Error *getErrPtr() const { return ErrState.getPointer(); }
0199
0200   bool isEnd() const { return getErrPtr() == nullptr; }
0201
0202   bool isValid() const { return !ErrState.getInt(); }
0203
0204   void handleError(Error Err) {
0205     *getErrPtr() = std::move(Err);
0206     ErrState.setPointer(nullptr);
0207     ErrState.setInt(true);
0208   }
0209
0210   void resetCheckedFlag() {
0211     *getErrPtr() = Error::success();
0212   }
0213
0214   Underlying I;
0215   mutable PointerIntPair<Error *, 1> ErrState;
0216 };
0217
0218 /// Convenience wrapper to make a fallible_iterator value from an instance
0219 /// of an underlying iterator and an Error reference.
0220 template <typename Underlying>
0221 fallible_iterator<Underlying> make_fallible_itr(Underlying I, Error &Err) {
0222   return fallible_iterator<Underlying>::itr(std::move(I), Err);
0223 }
0224
0225 /// Convenience wrapper to make a fallible_iterator end value from an instance
0226 /// of an underlying iterator.
0227 template <typename Underlying>
0228 fallible_iterator<Underlying> make_fallible_end(Underlying E) {
0229   return fallible_iterator<Underlying>::end(std::move(E));
0230 }
0231
0232 template <typename Underlying>
0233 iterator_range<fallible_iterator<Underlying>>
0234 make_fallible_range(Underlying I, Underlying E, Error &Err) {
0235   return make_range(make_fallible_itr(std::move(I), Err),
0236                     make_fallible_end(std::move(E)));
0237 }
0238
0239 } // end namespace llvm
0240
0241 #endif // LLVM_ADT_FALLIBLE_ITERATOR_H