Index: include/llvm/ADT/fallible_iterator.h =================================================================== --- /dev/null +++ include/llvm/ADT/fallible_iterator.h @@ -0,0 +1,243 @@ +//===--- fallible_iterator.h - Wrapper for fallible iterators ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_FALLIBLE_ITERATOR_H +#define LLVM_ADT_FALLIBLE_ITERATOR_H + +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/Error.h" + +#include + +namespace llvm { + +/// A wrapper class for fallible iterators. +/// +/// The fallible_iterator template wraps an underlying iterator-like class +/// whose increment and decrement operations are replaced with fallible versions +/// like: +/// +/// @code{.cpp} +/// Error inc(); +/// Error dec(); +/// @endcode +/// +/// It produces an interface that is (mostly) compatible with a traditional +/// c++ iterator, including ++ and -- operators that do not fail. +/// +/// Instances of the wrapper are constructed with an instance of the +/// underlying iterator and (for non-end iterators) a reference to an Error +/// instance. If the underlying increment/decrement operations fail, the Error +/// is returned via this reference, and the resulting iterator value set to an +/// end-of-range sentinel value. This enables the following loop idiom: +/// +/// @code{.cpp} +/// class Archive { // E.g. Potentially malformed on-disk archive +/// public: +/// fallible_iterator children_begin(Error &Err); +/// fallible_iterator children_end(); +/// iterator_range> +/// children(Error &Err) { +/// return make_range(children_begin(Err), children_end()); +/// //... +/// }; +/// +/// void walk(Archive &A) { +/// Error Err = Error::success(); +/// for (auto &C : A.children(Err)) { +/// // Loop body only entered when increment succeeds. +/// } +/// if (Err) { +/// // handle error. +/// } +/// } +/// @endcode +/// +/// The wrapper marks the referenced Error as unchecked after each increment +/// and/or decrement operation, and clears the unchecked flag when a non-end +/// value is compared against end (since, by the increment invariant, not being +/// an end value proves that there was no error, and is equivalent to checking +/// that the Error is success). This allows early exits from the loop body +/// without requiring redundant error checks. +template class fallible_iterator { +private: + template + using enable_if_struct_deref_supported = std::enable_if< + !std::is_void().operator->())>::value, + decltype(std::declval().operator->())>; + +public: + /// Construct a fallible iterator that *cannot* be used as an end-of-range + /// value. + /// + /// A value created by this method can be dereferenced, incremented, + /// decremented and compared, providing the underlying type supports it. + /// + /// The error that is passed in will be initially marked as checked, so if the + /// iterator is not used at all the Error need not be checked. + static fallible_iterator itr(Underlying I, Error &Err) { + (void)!!Err; + return fallible_iterator(std::move(I), &Err); + } + + /// Construct a fallible iteratro that can be used as an end-of-range value. + /// + /// A value created by this method can be dereferenced (if the underlying + /// value points at a valid value) and compared, but not incremented or + /// decremented. + static fallible_iterator end(Underlying I) { + return fallible_iterator(std::move(I), nullptr); + } + + /// Forward dereference to the underlying iterator. + auto operator*() -> decltype(*std::declval()) { return *I; } + + /// Forward const dereference to the underlying iterator. + auto operator*() const -> decltype(*std::declval()) { + return *I; + } + + /// Forward structure dereference to the underlying iterator (if the + /// underlying iterator supports it). + template + typename enable_if_struct_deref_supported::type operator->() { + return I.operator->(); + } + + /// Forward const structure dereference to the underlying iterator (if the + /// underlying iterator supports it). + template + typename enable_if_struct_deref_supported::type operator->() const { + return I.operator->(); + } + + /// Increment the fallible iterator. + /// + /// If the underlying 'inc' operation fails, this will set the Error value + /// and update this iterator value to point to end-of-range. + /// + /// The Error value is marked as needing checking, regardless of whether the + /// 'inc' operation succeeds or fails. + fallible_iterator &operator++() { + assert(getErrPtr() && "Cannot increment end iterator"); + if (auto Err = I.inc()) + handleError(std::move(Err)); + else + resetCheckedFlag(); + return *this; + } + + /// Decrement the fallible iterator. + /// + /// If the underlying 'dec' operation fails, this will set the Error value + /// and update this iterator value to point to end-of-range. + /// + /// The Error value is marked as needing checking, regardless of whether the + /// 'dec' operation succeeds or fails. + fallible_iterator &operator--() { + assert(getErrPtr() && "Cannot decrement end iterator"); + if (auto Err = I.dec()) + handleError(std::move(Err)); + else + resetCheckedFlag(); + return *this; + } + + /// Compare fallible iterators for equality. + /// + /// Returns true if both LHS and RHS are end-of-range values, or if both are + /// non-end-of-range values whose underlying iterator values compare equal. + /// + /// If this is a comparison between an end-of-range iterator and a + /// non-end-of-range iterator, then the Error (referenced by the + /// non-end-of-range value) is marked as checked: Since all + /// increment/decrement operations result in an end-of-range value, comparing + /// false against end-of-range is equivalent to checking that the Error value + /// is success. This flag management enables early returns from loop bodies + /// without redundant Error checks. + friend bool operator==(const fallible_iterator &LHS, + const fallible_iterator &RHS) { + // If both iterators are in the end state they compare + // equal, regardless of whether either is valid. + if (LHS.isEnd() && RHS.isEnd()) + return true; + + assert(LHS.isValid() && RHS.isValid() && + "Invalid iterators can only be compared against end"); + + bool Equal = LHS.I == RHS.I; + + // If the iterators differ and this is a comparison against end then mark + // the Error as checked. + if (!Equal) { + if (LHS.isEnd()) + (void)!!*RHS.getErrPtr(); + else + (void)!!*LHS.getErrPtr(); + } + + return Equal; + } + + /// Compare fallible iterators for inequality. + /// + /// See notes for operator==. + friend bool operator!=(const fallible_iterator &LHS, + const fallible_iterator &RHS) { + return !(LHS == RHS); + } + +private: + fallible_iterator(Underlying I, Error *Err) + : I(std::move(I)), ErrState(Err, false) {} + + Error *getErrPtr() const { return ErrState.getPointer(); } + + bool isEnd() const { return getErrPtr() == nullptr; } + + bool isValid() const { return !ErrState.getInt(); } + + void handleError(Error Err) { + *getErrPtr() = std::move(Err); + ErrState.setPointer(nullptr); + ErrState.setInt(true); + } + + void resetCheckedFlag() { + *getErrPtr() = Error::success(); + } + + Underlying I; + mutable PointerIntPair ErrState; +}; + +/// Convenience wrapper to make a fallible_iterator value from an instance +/// of an underlying iterator and an Error reference. +template +fallible_iterator make_fallible_itr(Underlying I, Error &Err) { + return fallible_iterator::itr(std::move(I), Err); +} + +/// Convenience wrapper to make a fallible_iterator end value from an instance +/// of an underlying iterator. +template +fallible_iterator make_fallible_end(Underlying E) { + return fallible_iterator::end(std::move(E)); +} + +template +iterator_range> +make_fallible_range(Underlying I, Underlying E, Error &Err) { + return make_range(make_fallible_itr(std::move(I), Err), + make_fallible_end(std::move(E))); +} + +} // end namespace llvm + +#endif // LLVM_ADT_FALLIBLE_ITERATOR_H Index: include/llvm/Object/Archive.h =================================================================== --- include/llvm/Object/Archive.h +++ include/llvm/Object/Archive.h @@ -15,6 +15,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/fallible_iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Object/Binary.h" #include "llvm/Support/Chrono.h" @@ -142,44 +143,38 @@ getAsBinary(LLVMContext *Context = nullptr) const; }; - class child_iterator { + class ChildFallibleIterator { Child C; - Error *E = nullptr; public: - child_iterator() : C(Child(nullptr, nullptr, nullptr)) {} - child_iterator(const Child &C, Error *E) : C(C), E(E) {} + ChildFallibleIterator() : C(Child(nullptr, nullptr, nullptr)) {} + ChildFallibleIterator(const Child &C) : C(C) {} const Child *operator->() const { return &C; } const Child &operator*() const { return C; } - bool operator==(const child_iterator &other) const { + bool operator==(const ChildFallibleIterator &other) const { // Ignore errors here: If an error occurred during increment then getNext // will have been set to child_end(), and the following comparison should // do the right thing. return C == other.C; } - bool operator!=(const child_iterator &other) const { + bool operator!=(const ChildFallibleIterator &other) const { return !(*this == other); } - // Code in loops with child_iterators must check for errors on each loop - // iteration. And if there is an error break out of the loop. - child_iterator &operator++() { // Preincrement - assert(E && "Can't increment iterator with no Error attached"); - ErrorAsOutParameter ErrAsOutParam(E); - if (auto ChildOrErr = C.getNext()) - C = *ChildOrErr; - else { - C = C.getParent()->child_end().C; - *E = ChildOrErr.takeError(); - E = nullptr; - } - return *this; + Error inc() { + auto NextChild = C.getNext(); + if (!NextChild) + return NextChild.takeError(); + C = std::move(*NextChild); + return Error::success(); } }; + using child_iterator = fallible_iterator; + class Symbol { const Archive *Parent; uint32_t SymbolIndex; Index: lib/Object/Archive.cpp =================================================================== --- lib/Object/Archive.cpp +++ lib/Object/Archive.cpp @@ -778,19 +778,18 @@ return child_end(); if (SkipInternal) - return child_iterator(Child(this, FirstRegularData, - FirstRegularStartOfFile), - &Err); + return child_iterator::itr( + Child(this, FirstRegularData, FirstRegularStartOfFile), Err); const char *Loc = Data.getBufferStart() + strlen(Magic); Child C(this, Loc, &Err); if (Err) return child_end(); - return child_iterator(C, &Err); + return child_iterator::itr(C, Err); } Archive::child_iterator Archive::child_end() const { - return child_iterator(Child(nullptr, nullptr, nullptr), nullptr); + return child_iterator::end(Child(nullptr, nullptr, nullptr)); } StringRef Archive::Symbol::getName() const { Index: tools/llvm-objcopy/llvm-objcopy.cpp =================================================================== --- tools/llvm-objcopy/llvm-objcopy.cpp +++ tools/llvm-objcopy/llvm-objcopy.cpp @@ -152,9 +152,6 @@ std::vector NewArchiveMembers; Error Err = Error::success(); for (const Archive::Child &Child : Ar.children(Err)) { - // FIXME: Archive::child_iterator requires that Err be checked *during* loop - // iteration, and hence does not allow early returns. - cantFail(std::move(Err)); Expected> ChildOrErr = Child.getAsBinary(); if (!ChildOrErr) return createFileError(Ar.getFileName(), ChildOrErr.takeError()); Index: unittests/ADT/CMakeLists.txt =================================================================== --- unittests/ADT/CMakeLists.txt +++ unittests/ADT/CMakeLists.txt @@ -18,6 +18,7 @@ DenseSetTest.cpp DepthFirstIteratorTest.cpp EquivalenceClassesTest.cpp + FallibleIteratorTest.cpp FoldingSet.cpp FunctionExtrasTest.cpp FunctionRefTest.cpp @@ -71,4 +72,6 @@ VariadicFunctionTest.cpp ) +target_link_libraries(ADTTests PRIVATE LLVMTestingSupport) + add_dependencies(ADTTests intrinsics_gen) Index: unittests/ADT/FallibleIteratorTest.cpp =================================================================== --- /dev/null +++ unittests/ADT/FallibleIteratorTest.cpp @@ -0,0 +1,291 @@ +//===- unittests/ADT/FallibleIteratorTest.cpp - fallible_iterator.h tests -===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/fallible_iterator.h" +#include "llvm/Testing/Support/Error.h" + +#include "gtest/gtest-spi.h" +#include "gtest/gtest.h" + +#include +#include + +using namespace llvm; + +namespace { + +using ItemValid = enum { ValidItem, InvalidItem }; +using LinkValid = enum { ValidLink, InvalidLink }; + +class Item { +public: + Item(ItemValid V) : V(V) {} + bool isValid() const { return V == ValidItem; } + +private: + ItemValid V; +}; + +// A utility to mock "bad collections". It supports both invalid items, +// where the dereference operator may return an Error, and bad links +// where the inc/dec operations may return an Error. +// Each element of the mock collection contains a pair of a (possibly broken) +// item and link. +using FallibleCollection = std::vector>; + +class FallibleCollectionWalker { +public: + FallibleCollectionWalker(FallibleCollection &C, unsigned Idx) + : C(C), Idx(Idx) {} + + Item &operator*() { return C[Idx].first; } + + const Item &operator*() const { return C[Idx].first; } + + Error inc() { + assert(Idx != C.size() && "Walking off end of (mock) collection"); + if (C[Idx].second == ValidLink) { + ++Idx; + return Error::success(); + } + return make_error("cant get next object in (mock) collection", + inconvertibleErrorCode()); + } + + Error dec() { + assert(Idx != 0 && "Walking off start of (mock) collection"); + --Idx; + if (C[Idx].second == ValidLink) + return Error::success(); + return make_error("cant get prev object in (mock) collection", + inconvertibleErrorCode()); + } + + friend bool operator==(const FallibleCollectionWalker &LHS, + const FallibleCollectionWalker &RHS) { + assert(&LHS.C == &RHS.C && "Comparing iterators across collectionss."); + return LHS.Idx == RHS.Idx; + } + +private: + FallibleCollection &C; + unsigned Idx; +}; + +class FallibleCollectionWalkerWithStructDeref + : public FallibleCollectionWalker { +public: + using FallibleCollectionWalker::FallibleCollectionWalker; + + Item *operator->() { return &this->operator*(); } + + const Item *operator->() const { return &this->operator*(); } +}; + +class FallibleCollectionWalkerWithFallibleDeref + : public FallibleCollectionWalker { +public: + using FallibleCollectionWalker::FallibleCollectionWalker; + + Expected operator*() { + auto &I = FallibleCollectionWalker::operator*(); + if (!I.isValid()) + return make_error("bad item", inconvertibleErrorCode()); + return I; + } + + Expected operator*() const { + const auto &I = FallibleCollectionWalker::operator*(); + if (!I.isValid()) + return make_error("bad item", inconvertibleErrorCode()); + return I; + } +}; + +TEST(FallibleIteratorTest, BasicSuccess) { + + // Check that a basic use-case involing successful iteration over a + // "FallibleCollection" works. + + FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}}); + + FallibleCollectionWalker begin(C, 0); + FallibleCollectionWalker end(C, 2); + + Error Err = Error::success(); + for (auto &Elem : + make_fallible_range(begin, end, Err)) + EXPECT_TRUE(Elem.isValid()); + cantFail(std::move(Err)); +} + +TEST(FallibleIteratorTest, BasicFailure) { + + // Check that a iteration failure (due to the InvalidLink state on element one + // of the fallible collection) breaks out of the loop and raises an Error. + + FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, InvalidLink}}); + + FallibleCollectionWalker begin(C, 0); + FallibleCollectionWalker end(C, 2); + + Error Err = Error::success(); + for (auto &Elem : + make_fallible_range(begin, end, Err)) + EXPECT_TRUE(Elem.isValid()); + + EXPECT_THAT_ERROR(std::move(Err), Failed()) << "Expected failure value"; +} + +TEST(FallibleIteratorTest, NoRedundantErrorCheckOnEarlyExit) { + + // Check that an early return from the loop body does not require a redundant + // check of Err. + + FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}}); + + FallibleCollectionWalker begin(C, 0); + FallibleCollectionWalker end(C, 2); + + Error Err = Error::success(); + for (auto &Elem : + make_fallible_range(begin, end, Err)) { + (void)Elem; + return; + } + // Err not checked, but should be ok because we exit from the loop + // body. +} + +#if LLVM_ENABLE_ABI_BREAKING_CHECKS +TEST(FallibleIteratorTest, RegularLoopExitRequiresErrorCheck) { + + // Check that Err must be checked after a normal (i.e. not early) loop exit + // by failing to check and expecting program death (due to the unchecked + // error). + + EXPECT_DEATH( + { + FallibleCollection C({{ValidItem, ValidLink}, {ValidItem, ValidLink}}); + + FallibleCollectionWalker begin(C, 0); + FallibleCollectionWalker end(C, 2); + + Error Err = Error::success(); + for (auto &Elem : + make_fallible_range(begin, end, Err)) + (void)Elem; + }, + "Program aborted due to an unhandled Error:") + << "Normal (i.e. not early) loop exit should require an error check"; +} +#endif + +TEST(FallibleIteratorTest, RawIncrementAndDecrementBehavior) { + + // Check the exact behavior of increment / decrement. + + FallibleCollection C({{ValidItem, ValidLink}, + {ValidItem, InvalidLink}, + {ValidItem, ValidLink}, + {ValidItem, InvalidLink}}); + + { + // One increment from begin succeeds. + Error Err = Error::success(); + auto I = make_fallible_itr(FallibleCollectionWalker(C, 0), Err); + ++I; + EXPECT_THAT_ERROR(std::move(Err), Succeeded()); + } + + { + // Two increments from begin fail. + Error Err = Error::success(); + auto I = make_fallible_itr(FallibleCollectionWalker(C, 0), Err); + ++I; + EXPECT_THAT_ERROR(std::move(Err), Succeeded()); + ++I; + EXPECT_THAT_ERROR(std::move(Err), Failed()) << "Expected failure value"; + } + + { + // One decement from element three succeeds. + Error Err = Error::success(); + auto I = make_fallible_itr(FallibleCollectionWalker(C, 3), Err); + --I; + EXPECT_THAT_ERROR(std::move(Err), Succeeded()); + } + + { + // One decement from element three succeeds. + Error Err = Error::success(); + auto I = make_fallible_itr(FallibleCollectionWalker(C, 3), Err); + --I; + EXPECT_THAT_ERROR(std::move(Err), Succeeded()); + --I; + EXPECT_THAT_ERROR(std::move(Err), Failed()); + } +} + +TEST(FallibleIteratorTest, CheckStructDerefOperatorSupport) { + // Check that the fallible_iterator wrapper forwards through to the + // underlying iterator's structure dereference operator if present. + + FallibleCollection C({{ValidItem, ValidLink}, + {ValidItem, ValidLink}, + {InvalidItem, InvalidLink}}); + + FallibleCollectionWalkerWithStructDeref begin(C, 0); + + { + Error Err = Error::success(); + auto I = make_fallible_itr(begin, Err); + EXPECT_TRUE(I->isValid()); + cantFail(std::move(Err)); + } + + { + Error Err = Error::success(); + const auto I = make_fallible_itr(begin, Err); + EXPECT_TRUE(I->isValid()); + cantFail(std::move(Err)); + } +} + +TEST(FallibleIteratorTest, CheckDerefToExpectedSupport) { + + // Check that the fallible_iterator wrapper forwards value types, in + // particular llvm::Expected, correctly. + + FallibleCollection C({{ValidItem, ValidLink}, + {InvalidItem, ValidLink}, + {ValidItem, ValidLink}}); + + FallibleCollectionWalkerWithFallibleDeref begin(C, 0); + FallibleCollectionWalkerWithFallibleDeref end(C, 3); + + Error Err = Error::success(); + auto I = make_fallible_itr(begin, Err); + auto E = make_fallible_end(end); + + Expected V1 = *I; + EXPECT_THAT_ERROR(V1.takeError(), Succeeded()); + ++I; + EXPECT_NE(I, E); // Implicitly check error. + Expected V2 = *I; + EXPECT_THAT_ERROR(V2.takeError(), Failed()); + ++I; + EXPECT_NE(I, E); // Implicitly check error. + Expected V3 = *I; + EXPECT_THAT_ERROR(V3.takeError(), Succeeded()); + ++I; + EXPECT_EQ(I, E); + cantFail(std::move(Err)); +} + +} // namespace