[ADT] Add a fallible_iterator wrapper.

[lhames]

Summary

A fallible iterator is one whose increment or decrement operations may fail.
This would usually be supported by replacing the usually iterator increment
and decrement operations (++ / --) with methods that return error:

class MyFallibleIterator {
public:
  // ...
  Error inc();
  Errro dec();
  // ...
};

The downside of this style is that it no longer conforms to the C++ iterator
concept, and can not make use of standard algorithms and features such as
range-based for loops.

The fallible_iterator wrapper takes an iterator written in the style above
and adapts it to (mostly) conform with the C++ iterator concept. It does this
by providing standard ++ and -- operator implementations, returning any errors
generated via a side channel (an Error reference passed into the wrapper at
construction time), and immediately jumping the iterator to a known 'end'
value upon error.

Usage looks like:

MyFallibleIterator I = ..., E = ...;

Error Err = Error::success();
for (auto &Elem : make_fallible_range(I, E, Err)) {
  // Loop body is only entered when safe.
  // Early exits from loop body permitted without checking Err.
}
if (Err)
  // Handle error.

[lhames]

• Fix a missing header, rename make_fallible_iter to make_fallible_itr, and update Archive::child_iterator to use the fallible_iterator wrapper.

[lhames]

• Remove the cantFail added in r352888, since fallible_iterator makes it unneccessary.

[lhames]

Assuming this looks good to everyone, I will also update the programmers manual documentation for fallible iterators. I wanted to get this into a final form before re-writing the docs though.

[dblaikie]

include/llvm/ADT/fallible_iterator.h

77

I think you can use "fallible_iterator" without template parameters throughout the class (this would ues the injected class name), probably means you don't need this alias here?

101

Not sure if the "const Underlying" is correct here.

Iterator const tends not to be deep, I think? So, for instance a "const std::vector<int>::iterator" is not the same as a "std::vector<int>::const_iterator" - the former cannot be assigned to, but its dereference probably still returns non-const reference. Whereas the latter can be assigned, incremented, etc, but still has a const reference return from op*. Does that make sense?

All in all, I think you only need the member-const op* (because op* doesn't modify the iterator, only the thing it is iterating over). And it should probably use const in the declval, I think?

127

'Cannot'?

212–213

Should/could this be replaced with "cantFail"?

unittests/ADT/FallibleIteratorTest.cpp

23–24

I'm a bit surprised to find linker terminology in this test case that's orthogonal to linkers, object files, etc. Do you find they improve readability/framing?

195

Might be better as an explicit EXPECT_THAT_ERROR(Succeeded) - if there was a bug that caused this Error to be in a fail state, the test would fail rather indirectly later on inside the fallible iterator implementationg where it does "cantFail' (or the moral equivalent)?

198

What's this line for? (it looks to me like the EXPECT_THAT_ERROR on the previous line should have validated the Error state & so there should be no other need to do any Error handling after that?)

[alexander-shaposhnikov]

include/llvm/ADT/fallible_iterator.h

54

looks like the argument (Err) is missed here

[lhames]

include/llvm/ADT/fallible_iterator.h

77

Yep. This is a hangover from when the type name was longer. It can be removed.

101

You're approaching this from a very different angle to me. I just think of these operators as forwarding: There's a const and a non-const version, and they do whatever the const and non-const version of the underlying iterator do. The wrapper is being as minimalist as possible in the assumptions it places on the Underlying type.

127

/s/can not/cannot/. :)

212–213

I don't think Error's move constructor ever guaranteed that a moved-from error was assignable. It *probably* is, but I'd have to check and formalize this.

Instead here I have forced a check and then written to the error.

unittests/ADT/FallibleIteratorTest.cpp

23–24

I may be biased, but they definitely do for me. Archive iteration was the original motivating use case for the fallible_iterator pattern, and has the advantage of including both kinds of iterator fail: increment/decrement failures (if the archive header is bad), and dereference failures (if an archive member is malformed). Only the former is tested so far in this test case, but I plan to add a dereference failure test too, to verify the forwarding nature of the dereference operators.

195

Yep. This is another instance of moved-from-Errors-aren't-assignable/reusable. I could use two errors though.

198

Yep -- this is redundant. Good catch. I'll remove it.

[lhames]

unittests/ADT/FallibleIteratorTest.cpp

195

Nope, wait: This is returning via the error reference. It has to be a check, until/unless I define moved-from Errors to be checked Error success values. Thinking about it though, that should be the case, so I can just document that in Error's move constructor.

[alexander-shaposhnikov]

include/llvm/ADT/fallible_iterator.h

20

general comment: @lhames , have you considered using CRTP instead of introducing this wrapper/ forwarding etc ?

[lhames]

• Address several review feedback comments.

[lhames]

include/llvm/ADT/fallible_iterator.h

20

I didn't. I approached the design like this:

What does a natural fallible iterator API look like? I think it looks like:

class MyFallibleIterator {
public:

  // The usual iterator operations
  MyFallibleIterator(...);
  reference_type operator*();
  const reference_type operator*() const;

  // operator++ / operator-- replaced with inc/dec, which return Error.
  Error inc();
  Error dec();
};

This makes the implementation of inc/dec easy, and feels (relatively) natural to use in a raw loop where you're doing non-trivial stepping. E.g.:

auto FI = MyFallibleIterator(...);
auto FE = MyFallibelIterator(...);

while (FI != FE) {
  auto A = *FI;
  if (auto Err = FI.inc())
    return Err;
  auto B = *FI;
  doSomethingWithAdjacentValues(A, B);
}

The (mild) problem with CRTP is that you would have to pass an Error in to the constructor for this 'natural' API, even though it doesn't use it. For that reason I am inclined to stick with the wrapper design as is.

54

It is. Thanks!

[dblaikie]

include/llvm/ADT/fallible_iterator.h

101

Fair enough - I'd probably be inclined to err on the side of simpler until the functionality was needed, but whatever suits.

212–213

I'd guess there's probably already a fair bit of code that relies on a moved-from Error being assignable.

unittests/ADT/FallibleIteratorTest.cpp

23–24

For me it implies some context I don't have or don't have readily at hand when I read the test - and so I kind of glaze over when I come to this wondering what object/archive context I should have to understand this test, where it doesn't seem like I should need any.

s/Archive/FallibleSequence/
s/ArchiveWalker/FallibleSequenceWalker/

Seems to me like it'd be clearer to a reader coming into this code - well, it'd be clearer to me at least.

29

Having another concept of validity here seems confusing, to me at least - if this needs an arbitrary member function to call to test -> on the iterator, perhaps it could have some other name - so it's not likely to confuse the validity/error checking that's central to this testing?

35

I'd probably put the "do not iterate this object" bit, inside the Object rather than pairing it up. But up to you. (I understand how this maps to the original context, but it doesn't seem necessary to me here, in a standalone setting)

[lhames]

unittests/ADT/FallibleIteratorTest.cpp

29

I was going to have the dereference operator for ArchiveWalker return an Expected<Object> based on this state in some future tests, but it’s probably enough to test that a move only value type can be propagated through the dereference operator. I will do that instead and rename the types as you suggested.

[lhames]

• Rename test classes and remove fixture, add test for deref-returns-expected.

[dblaikie]

Looks good to me - some optional points on test coverage, etc.

unittests/ADT/FallibleIteratorTest.cpp

183

Shouldn't this work without the invalid item? An error check should be required after the loop even if the error is success, right?

(perhaps test both cases? But testing the positive case seems more "interesting" (since it's the lesser requirement, but still a requirement))

283

I'd personally consider writing out the type here - it's a bit of a distance from the FallibleDeref definition, and Expected<Item>'s "interesting" enough, I think, though I suppose the Expected's the only bit that's important here)

289–290

Should the Error have any reliable state at this point? (I guess it sort of has to by virtue of "return" being valid - so it can't be in an error state - but it's also not in an "unchecked" state (well, I guess it is because no iterator end comparison has been performed))

Not a sure thing in any case, but I'd probably test for inequality with end here, rather than that the Error is in any particular state.

(wonder if we should sure up the iterator to require this - that an iterator be compared to end before it's incremented (it's in the "unchecked" state and comparison with end is how you "check" it - incrementing could discard the unchecked state, technically speaking)? That might be a bit too stringent though - or perhaps that's already the case & these error comparisons are equivalent to comparison with end, and one or the other is needed?)

[rupprecht]

tools/llvm-objcopy/llvm-objcopy.cpp

176 ↗

(On Diff #185127)

When I remove this Error check at trunk, I can get 6 tests to fail:

$ ninja check-llvm-tools-llvm-objcopy
...
Program aborted due to an unhandled Error:
Error value was Success. (Note: Success values must still be checked prior to being destroyed).
...
Failing Tests (6):
    LLVM :: tools/llvm-objcopy/ELF/basic-archive-copy.test
    LLVM :: tools/llvm-objcopy/ELF/deterministic-archive.test
    LLVM :: tools/llvm-objcopy/ELF/strip-all.test
    LLVM :: tools/llvm-objcopy/ELF/strip-debug.test
    LLVM :: tools/llvm-objcopy/ELF/strip-preserve-atime.test
    LLVM :: tools/llvm-objcopy/ELF/strip-preserve-mtime.test

But when I patch in this change and then remove this line, I no longer get an error that Err is unchecked. So, I think something needs to reset Error so that it is unchecked at the end of normal loop iteration.

[lhames]

• Require iterator checks on each increment, rename some test vars.

[lhames]

• Remove unused collection elements.

[lhames]

tools/llvm-objcopy/llvm-objcopy.cpp

176 ↗

(On Diff #185127)

I was not able to reproduce that. Can you try again with the latest patch? Is this happening on a debug or release branch?

unittests/ADT/FallibleIteratorTest.cpp

183

I have removed that item: the loop only ranges over the first two.

283

Done.

289–290

wonder if we should sure up the iterator to require this - that an iterator be compared to end before it's incremented

Good call. It is the moral equivalent to requiring that an Error be checked before being assigned to. I've updated the patch to require that.

[rupprecht]

tools/llvm-objcopy/llvm-objcopy.cpp

176 ↗

(On Diff #185127)

I'm using a debug build w/ assertions enabled.

I tested with the latest version of the patch, and I'm getting the expected test failures now when I remove this error check, so LGTM. Thanks!

[lhames]

Committed. I updated the language in the fallible iterators section of the programmers manual too. Feed back on that is very welcome too.

include/llvm/ADT/fallible_iterator.h

+//===--- 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 <type_traits>
+
+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<ArchiveChildItr> children_begin(Error &Err);
+///     fallible_iterator<ArchiveChildItr> children_end();
+///     iterator_range<fallible_iterator<ArchiveChildItr>>
+///     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 <typename Underlying> class fallible_iterator {
+private:
+  template <typename T>
+  using enable_if_struct_deref_supported = std::enable_if<
+      !std::is_void<decltype(std::declval<T>().operator->())>::value,
+      decltype(std::declval<T>().operator->())>;
+
+public:
+  using this_fallible_iterator = fallible_iterator<Underlying>;
+
+  /// 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<Underlying>()) { return *I; }
+
+  /// Forward const dereference to the underlying iterator.
+  auto operator*() const -> decltype(*std::declval<const Underlying>()) {
+    return *I;
+  }
+
+  /// Forward structure dereference to the underlying iterator (if the
+  /// underlying iterator supports it).
+  template <typename T = Underlying>
+  typename enable_if_struct_deref_supported<T>::type operator->() {
+    return I.operator->();
+  }
+
+  /// Forward const structure dereference to the underlying iterator (if the
+  /// underlying iterator supports it).
+  template <typename T = Underlying>
+  typename enable_if_struct_deref_supported<const T>::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<Error *, 1> ErrState;
+};
+
+/// Convenience wrapper to make a fallible_iterator value from an instance
+/// of an underlying iterator and an Error reference.
+template <typename Underlying>
+fallible_iterator<Underlying> make_fallible_itr(Underlying I, Error &Err) {
+  return fallible_iterator<Underlying>::itr(std::move(I), Err);
+}
+
+/// Convenience wrapper to make a fallible_iterator end value from an instance
+/// of an underlying iterator.
+template <typename Underlying>
+fallible_iterator<Underlying> make_fallible_end(Underlying E) {
+  return fallible_iterator<Underlying>::end(std::move(E));
+}
+
+template <typename Underlying>
+iterator_range<fallible_iterator<Underlying>>
+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

include/llvm/Object/Archive.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_OBJECT_ARCHIVE_H
 #define LLVM_OBJECT_ARCHIVE_H
 
 #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"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <algorithm>
 #include <cassert>
public:
     uint64_t getChildOffset() const;
 
     Expected<MemoryBufferRef> getMemoryBufferRef() const;
 
     Expected<std::unique_ptr<Binary>>
     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<ChildFallibleIterator>;
+
   class Symbol {
     const Archive *Parent;
     uint32_t SymbolIndex;
     uint32_t StringIndex; // Extra index to the string.
 
   public:
     Symbol(const Archive *p, uint32_t symi, uint32_t stri)
       : Parent(p)

lib/Object/Archive.cpp

 }
 
 Archive::child_iterator Archive::child_begin(Error &Err,
                                              bool SkipInternal) const {
   if (isEmpty())
     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 {
   return Parent->getSymbolTable().begin() + StringIndex;
 }
 
 Expected<Archive::Child> Archive::Symbol::getMember() const {
   const char *Buf = Parent->getSymbolTable().begin();

unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   EquivalenceClassesTest.cpp
+  FallibleIteratorTest.cpp
   FoldingSet.cpp
   FunctionExtrasTest.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp
   IListIteratorTest.cpp
   IListNodeBaseTest.cpp
   IListNodeTest.cpp
add_llvm_unittest(ADTTests
   StringRefTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   VariadicFunctionTest.cpp
   )
 
+target_link_libraries(ADTTests PRIVATE LLVMTestingSupport)
+
 add_dependencies(ADTTests intrinsics_gen)

unittests/ADT/FallibleIteratorTest.cpp

+//===- 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 <utility>
+#include <vector>
+
+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<std::pair<Object, LinkValid>>;
+
+  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<StringError>("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<StringError>("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<ArchiveWalker>(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<ArchiveWalker>(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<ArchiveWalker>(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<ArchiveWalker>(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