[ADT] Add a fallible_iterator wrapper.
A fallible iterator is one whose increment or decrement operations may fail.
This would usually be supported by replacing the ++ and -- operators 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. It also marks the Error as checked any time an iterator is
compared with a known end value and found to be inequal, allowing early exit
from loops without redundant error checking*.
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 (SomeCondition)
return;
}
if (Err)
// Handle error.
* Since failure causes a fallible iterator to jump to end, testing that a
fallible iterator is not an end value implicitly verifies that the error is a
success value, and so is equivalent to an error check.
Reviewers: dblaikie, rupprecht
Subscribers: mgorny, dexonsmith, kristina, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D57618
llvm-svn: 353237
diff --git a/llvm/docs/ProgrammersManual.rst b/llvm/docs/ProgrammersManual.rst
index e2cb14b..2f89d9b 100644
--- a/llvm/docs/ProgrammersManual.rst
+++ b/llvm/docs/ProgrammersManual.rst
@@ -935,28 +935,86 @@
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