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()) { +/// // 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: + using this_fallible_iterator = fallible_iterator; + + /// Construct a fallible iterator that *can not* 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. + static this_fallible_iterator itr(Underlying I, Error &Err) { + return this_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 this_fallible_iterator end(Underlying I) { + return this_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. + this_fallible_iterator &operator++() { + assert(getErrPtr() && "Can not 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. + this_fallible_iterator &operator--() { + assert(getErrPtr() && "Can not 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 this_fallible_iterator &LHS, + const this_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 this_fallible_iterator &LHS, + const this_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() { + (void)!!*getErrPtr(); + assert(!*getErrPtr() && "Incrementing failure value"); + *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,241 @@ +//===- 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; + +class FallibleIteratorTest : public testing::Test { +public: + using ObjectValid = enum { ValidObject, InvalidObject }; + using LinkValid = enum { ValidLink, InvalidLink }; + + class Object { + public: + Object(ObjectValid V) : V(V) {} + bool isValid() const { return V == ValidObject; } + + private: + ObjectValid V; + }; + + using Archive = std::vector>; + + class ArchiveWalker { + public: + ArchiveWalker(Archive &A, unsigned Idx) : A(A), Idx(Idx) {} + + Object &operator*() { return A[Idx].first; } + + const Object &operator*() const { return A[Idx].first; } + + Error inc() { + assert(Idx != A.size() && "Walking off end of (fake) archive"); + if (A[Idx].second == ValidLink) { + ++Idx; + return Error::success(); + } + return make_error("cant get next object in (fake) archive", + inconvertibleErrorCode()); + } + + Error dec() { + assert(Idx != 0 && "Walking off start of (fake) archive"); + --Idx; + if (A[Idx].second == ValidLink) + return Error::success(); + return make_error("cant get prev object in (fake) archiev", + inconvertibleErrorCode()); + } + + friend bool operator==(const ArchiveWalker &LHS, const ArchiveWalker &RHS) { + assert(&LHS.A == &RHS.A && "Comparing iterators across archives."); + return LHS.Idx == RHS.Idx; + } + + friend bool operator!=(const ArchiveWalker &LHS, const ArchiveWalker &RHS) { + return !(LHS == RHS); + } + + private: + Archive &A; + unsigned Idx; + }; + + class ArchiveWalkerWithDeref : public ArchiveWalker { + public: + using ArchiveWalker::ArchiveWalker; + + Object *operator->() { return &this->operator*(); } + + const Object *operator->() const { return &this->operator*(); } + }; +}; + +namespace { + +TEST_F(FallibleIteratorTest, BasicSuccess) { + + // Check that a basic use-case involing successful iteration over a dummy + // "Archive" works. + + Archive A({{ValidObject, ValidLink}, + {ValidObject, ValidLink}, + {InvalidObject, InvalidLink}}); + + ArchiveWalker begin(A, 0); + ArchiveWalker end(A, 2); + + Error Err = Error::success(); + for (auto &Elem : make_fallible_range(begin, end, Err)) + EXPECT_TRUE(Elem.isValid()); + cantFail(std::move(Err)); +} + +TEST_F(FallibleIteratorTest, BasicFailure) { + + // Check that a iteration failure (due to the InvalidLink state on element one + // of the dummy archive) breaks out of the loop and raises an Error. + + Archive A({{ValidObject, ValidLink}, + {ValidObject, InvalidLink}, + {InvalidObject, InvalidLink}}); + + ArchiveWalker begin(A, 0); + ArchiveWalker end(A, 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_F(FallibleIteratorTest, NoRedundantErrorCheckOnEarlyExit) { + + // Check that an early return from the loop body does not require a redundant + // check of Err. + + Archive A({{ValidObject, ValidLink}, + {ValidObject, ValidLink}, + {InvalidObject, InvalidLink}}); + + ArchiveWalker begin(A, 0); + ArchiveWalker end(A, 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_F(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( + { + Archive A({{ValidObject, ValidLink}, + {ValidObject, ValidLink}, + {InvalidObject, InvalidLink}}); + + ArchiveWalker begin(A, 0); + ArchiveWalker end(A, 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_F(FallibleIteratorTest, RawIncrementAndDecrementBehavior) { + + // Check the exact behavior of increment / decrement. + + Archive A({{ValidObject, ValidLink}, + {ValidObject, InvalidLink}, + {ValidObject, ValidLink}, + {ValidObject, InvalidLink}}); + + { + // One increment from begin succeeds. + Error Err = Error::success(); + auto I = make_fallible_itr(ArchiveWalker(A, 0), Err); + ++I; + EXPECT_THAT_ERROR(std::move(Err), Succeeded()); + } + + { + // Two increments from begin fail. + Error Err = Error::success(); + auto I = make_fallible_itr(ArchiveWalker(A, 0), Err); + ++I; + (void)!!Err; // Manualy reset the checked flag. + ++I; + EXPECT_THAT_ERROR(std::move(Err), Failed()) << "Expected failure value"; + cantFail(std::move(Err)); + } + + { + // One decement from element three succeeds. + Error Err = Error::success(); + auto I = make_fallible_itr(ArchiveWalker(A, 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(ArchiveWalker(A, 3), Err); + --I; + (void)!!Err; // Manually reset the checked flag. + --I; + EXPECT_THAT_ERROR(std::move(Err), Failed()); + } +} + +TEST_F(FallibleIteratorTest, CheckDerefOperatorSupport) { + Archive A({{ValidObject, ValidLink}, + {ValidObject, ValidLink}, + {InvalidObject, InvalidLink}}); + + ArchiveWalkerWithDeref begin(A, 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)); + } +} + +} // namespace