[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

76 ↗

(On Diff #185127)

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?

100 ↗

(On Diff #185127)

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?

126 ↗

(On Diff #185127)

'Cannot'?

211–212 ↗

(On Diff #185127)

Should/could this be replaced with "cantFail"?

unittests/ADT/FallibleIteratorTest.cpp

22–23 ↗

(On Diff #185127)

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?

194 ↗

(On Diff #185127)

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)?

197 ↗

(On Diff #185127)

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

53 ↗

(On Diff #185127)

looks like the argument (Err) is missed here

[lhames]

include/llvm/ADT/fallible_iterator.h

76 ↗

(On Diff #185127)

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

100 ↗

(On Diff #185127)

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.

126 ↗

(On Diff #185127)

/s/can not/cannot/. :)

211–212 ↗

(On Diff #185127)

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

22–23 ↗

(On Diff #185127)

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.

194 ↗

(On Diff #185127)

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

197 ↗

(On Diff #185127)

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

[lhames]

unittests/ADT/FallibleIteratorTest.cpp

194 ↗

(On Diff #185127)

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

19 ↗

(On Diff #185127)

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

19 ↗

(On Diff #185127)

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.

53 ↗

(On Diff #185127)

It is. Thanks!

[dblaikie]

include/llvm/ADT/fallible_iterator.h

100 ↗

(On Diff #185127)

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

211–212 ↗

(On Diff #185127)

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

28 ↗

(On Diff #185167)

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?

34 ↗

(On Diff #185167)

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)

22–23 ↗

(On Diff #185127)

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.

[lhames]

unittests/ADT/FallibleIteratorTest.cpp

28 ↗

(On Diff #185167)

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

182 ↗

(On Diff #185228)

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))

282 ↗

(On Diff #185228)

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)

288–289 ↗

(On Diff #185228)

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

182 ↗

(On Diff #185228)

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

282 ↗

(On Diff #185228)

Done.

288–289 ↗

(On Diff #185228)

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.

llvm/trunk/docs/ProgrammersManual.rst

 ``Error::success()``, otherwise ``handleErrors`` will concatenate the remaining
 errors and return the resulting ``ErrorList``.
 
 Building fallible iterators and iterator ranges
 """""""""""""""""""""""""""""""""""""""""""""""
 
 The archive walking examples above retrieve archive members by index, however
 this requires considerable boiler-plate for iteration and error checking. We can
-clean this up by using ``Error`` with the "fallible iterator" pattern. The usual
-C++ iterator patterns do not allow for failure on increment, but we can
-incorporate support for it by having iterators hold an Error reference through
-which they can report failure. In this pattern, if an increment operation fails
-the failure is recorded via the Error reference and the iterator value is set to
-the end of the range in order to terminate the loop. This ensures that the
-dereference operation is safe anywhere that an ordinary iterator dereference
-would be safe (i.e. when the iterator is not equal to end). Where this pattern
-is followed (as in the ``llvm::object::Archive`` class) the result is much
-cleaner iteration idiom:
+clean this up by using the "fallible iterator" pattern, which supports the
+following natural iteration idiom for fallible containers like Archive:
 
 .. code-block:: c++
 
   Error Err;
   for (auto &Child : Ar->children(Err)) {
-    // Use Child - we only enter the loop when it's valid
+    // Use Child - only enter the loop when it's valid
+
+    // Allow early exit from the loop body, since we know that Err is success
+    // when we're inside the loop.
+    if (BailOutOn(Child))
+      return;
+
     ...
   }
   // Check Err after the loop to ensure it didn't break due to an error.
   if (Err)
     return Err;
 
+To enable this idiom, iterators over fallible containers are written in a
+natural style, with their ``++`` and ``--`` operators replaced with fallible
+``Error inc()`` and ``Error dec()`` functions. E.g.:
+
+.. code-block:: c++
+
+  class FallibleChildIterator {
+  public:
+    FallibleChildIterator(Archive &A, unsigned ChildIdx);
+    Archive::Child &operator*();
+    friend bool operator==(const ArchiveIterator &LHS,
+                           const ArchiveIterator &RHS);
+
+    // operator++/operator-- replaced with fallible increment / decrement:
+    Error inc() {
+      if (!A.childValid(ChildIdx + 1))
+        return make_error<BadArchiveMember>(...);
+      ++ChildIdx;
+      return Error::success();
+    }
+
+    Error dec() { ... }
+  };
+
+Instances of this kind of fallible iterator interface are then wrapped with the
+fallible_iterator utility which provides ``operator++`` and ``operator--``,
+returning any errors via a reference passed in to the wrapper at construction
+time. The fallible_iterator wrapper takes care of (a) jumping to the end of the
+range on error, and (b) marking the error as checked whenever an iterator is
+compared to ``end`` and found to be inequal (in particular: this marks the
+error as checked throughout the body of a range-based for loop), enabling early
+exit from the loop without redundant error checking.
+
+Instances of the fallible iterator interface (e.g. FallibleChildIterator above)
+are wrapped using the ``make_fallible_itr`` and ``make_fallible_end``
+functions. E.g.:
+
+.. code-block:: c++
+
+  class Archive {
+  public:
+    using child_iterator = fallible_iterator<FallibleChildIterator>;
+
+    child_iterator child_begin(Error &Err) {
+      return make_fallible_itr(FallibleChildIterator(*this, 0), Err);
+    }
+
+    child_iterator child_end() {
+      return make_fallible_end(FallibleChildIterator(*this, size()));
+    }
+
+    iterator_range<child_iterator> children(Error &Err) {
+      return make_range(child_begin(Err), child_end());
+    }
+  };
+
+Using the fallible_iterator utility allows for both natural construction of
+fallible iterators (using failing ``inc`` and ``dec`` operations) and
+relatively natural use of c++ iterator/loop idioms.
+
 .. _function_apis:
 
 More information on Error and its related utilities can be found in the
 Error.h header file.
 
 Passing functions and other callable objects
 --------------------------------------------
 

llvm/trunk/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(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 <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:
+  /// 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<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.
+  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<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

llvm/trunk/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)

llvm/trunk/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();

llvm/trunk/tools/llvm-objcopy/llvm-objcopy.cpp

return createStringError(object_error::invalid_file_type,
                              "Unsupported object file format");
 }
 
 static Error executeObjcopyOnArchive(const CopyConfig &Config,
                                      const Archive &Ar) {
   std::vector<NewArchiveMember> 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<std::unique_ptr<Binary>> ChildOrErr = Child.getAsBinary();
     if (!ChildOrErr)
       return createFileError(Ar.getFileName(), ChildOrErr.takeError());
     Binary *Bin = ChildOrErr->get();
 
     Expected<StringRef> ChildNameOrErr = Child.getName();
     if (!ChildNameOrErr)
       return createFileError(Ar.getFileName(), ChildNameOrErr.takeError());

llvm/trunk/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)

llvm/trunk/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;
+
+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<std::pair<Item, LinkValid>>;
+
+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<StringError>("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<StringError>("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<Item &> operator*() {
+    auto &I = FallibleCollectionWalker::operator*();
+    if (!I.isValid())
+      return make_error<StringError>("bad item", inconvertibleErrorCode());
+    return I;
+  }
+
+  Expected<const Item &> operator*() const {
+    const auto &I = FallibleCollectionWalker::operator*();
+    if (!I.isValid())
+      return make_error<StringError>("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<FallibleCollectionWalker>(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<FallibleCollectionWalker>(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<FallibleCollectionWalker>(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<FallibleCollectionWalker>(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<Item> V1 = *I;
+  EXPECT_THAT_ERROR(V1.takeError(), Succeeded());
+  ++I;
+  EXPECT_NE(I, E); // Implicitly check error.
+  Expected<Item> V2 = *I;
+  EXPECT_THAT_ERROR(V2.takeError(), Failed());
+  ++I;
+  EXPECT_NE(I, E); // Implicitly check error.
+  Expected<Item> V3 = *I;
+  EXPECT_THAT_ERROR(V3.takeError(), Succeeded());
+  ++I;
+  EXPECT_EQ(I, E);
+  cantFail(std::move(Err));
+}
+
+} // namespace