This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add a fallible_iterator wrapper.
ClosedPublic

Authored by lhames on Feb 1 2019, 2:07 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

lhames created this revision.Feb 1 2019, 2:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 1 2019, 2:07 PM
lhames updated this revision to Diff 185113.Feb 4 2019, 11:44 AM
  • Fix a missing header, rename make_fallible_iter to make_fallible_itr, and update Archive::child_iterator to use the fallible_iterator wrapper.
lhames updated this revision to Diff 185127.Feb 4 2019, 12:37 PM
  • Remove the cantFail added in r352888, since fallible_iterator makes it unneccessary.

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 added inline comments.Feb 4 2019, 1:45 PM
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?)

include/llvm/ADT/fallible_iterator.h
53 ↗(On Diff #185127)

looks like the argument (Err) is missed here

lhames marked 7 inline comments as done.Feb 4 2019, 2:42 PM
lhames added inline comments.
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 marked an inline comment as done.Feb 4 2019, 2:49 PM
lhames added inline comments.
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.

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 updated this revision to Diff 185167.Feb 4 2019, 2:56 PM
lhames marked an inline comment as done.
  • Address several review feedback comments.
lhames marked an inline comment as done.Feb 4 2019, 3:12 PM
lhames added inline comments.
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 added inline comments.Feb 4 2019, 3:41 PM
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 marked an inline comment as done.Feb 4 2019, 5:19 PM
lhames added inline comments.
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 updated this revision to Diff 185228.Feb 4 2019, 8:41 PM
  • Rename test classes and remove fixture, add test for deref-returns-expected.
dblaikie accepted this revision.Feb 4 2019, 9:01 PM

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

This revision is now accepted and ready to land.Feb 4 2019, 9:01 PM
rupprecht requested changes to this revision.Feb 5 2019, 10:52 AM
rupprecht added inline comments.
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.

This revision now requires changes to proceed.Feb 5 2019, 10:52 AM
lhames updated this revision to Diff 185378.Feb 5 2019, 12:41 PM
lhames marked 2 inline comments as done.
  • Require iterator checks on each increment, rename some test vars.
lhames updated this revision to Diff 185380.Feb 5 2019, 12:53 PM
lhames marked an inline comment as done.
  • Remove unused collection elements.
lhames marked 2 inline comments as done.Feb 5 2019, 12:56 PM
lhames added inline comments.
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 accepted this revision.Feb 5 2019, 1:48 PM
rupprecht marked an inline comment as done.
rupprecht added inline comments.
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!

This revision is now accepted and ready to land.Feb 5 2019, 1:48 PM
This revision was automatically updated to reflect the committed changes.
lhames added a comment.Feb 5 2019, 3:28 PM

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