This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add a generic concatenating iterator and range.
ClosedPublic

Authored by chandlerc on Dec 24 2016, 3:19 AM.

Details

Summary

This allows both defining convenience iterator/range accessors on types
which walk across N different independent ranges within the object, and
more direct and simple usages with range based for loops such as shown
in the unittest. The same facilities are used for both. They end up
quite small and simple as it happens.

I've also switched an iterator on Module to use this. I would like to
add another convenience iterator that includes even more sequences as
part of it and seeing this one already present motivated me to actually
abstract it away and introduce a general utility.

Event Timeline

chandlerc updated this revision to Diff 82438.Dec 24 2016, 3:19 AM
chandlerc retitled this revision from to [ADT] Add a generic concatenating iterator and range..
chandlerc updated this object.
chandlerc added reviewers: dblaikie, mehdi_amini.
chandlerc added a subscriber: llvm-commits.
dblaikie accepted this revision.Dec 24 2016, 10:10 AM
dblaikie edited edge metadata.

Generally looks good - bunch of optional bits & pieces/thoughts.

include/llvm/ADT/STLExtras.h
455–456

Any particular tradeoff between doing this representation compared to std::tuple<std::pair<IterTs>...> (where the pairs contain begin/end)?

Maybe I'll understand as I read further.

460–461

should this be a \returns doxy comment to comment the return semantics more explicitly

521–522

If 'Ranges' is accepted by universal reference (or what's the preferred term these days?) should these begin/end call parameters be std::forward'd?
& ADL begin/end call?

532–534

Usually suggested that op overloads that can be non-members should be non-members (could still be friend) to allow equal implicit conversions on both operands. Perhaps not applicable here (can't think of any particular implicit ops that'd be asymmetric here - but might be good as a matter of course/consistency/etc.

573–574

Would it be better to have a single explicit arg before the variadic template arg - rather than static_assert? I suppose it's much of a muchness.

unittests/ADT/STLExtrasTest.cpp
257–269

What's the particular motivation for these data sets? (length 4, 2, 2 - vector, list, and SmallVector - seems like list's iterator's a strict subset of the others, so if it works for that, not sure adding the others adds lots of coverage & also not sure of the motivation for those lengths)

I guess there's no nice way to avoid creating a new data structure for the result? (I think GTest has some container comparison helpers, but I guess they don't work for arbitrary ranges?)

257–269

Worth testing the copy/non-copy/lifetime-extension semantics when a temporary is passed in to concat?

266

Might be nice (could be a separate change) to skip the explicit value type parameter when the subranges have an exact match.

This revision is now accepted and ready to land.Dec 24 2016, 10:10 AM
EricWF added a subscriber: EricWF.Dec 24 2016, 6:59 PM
EricWF added inline comments.
include/llvm/ADT/STLExtras.h
477

If I'm not mistaken this deduces to std::initializer_list<FuncType>, and we shouldn't use initializer_list outside of performing initialization.

This should be changed to deduce as an array type instead (or any other sequenced container).

521–522

Should this accept Ranges as rvalues at all? It seems like it might hide a lifetime bug.

If we do want to accept rvalues I'm not convinced we should forward them. Doing so might result it Range&& binding to begin(Range const&) instead of begin(Range&), and changing the constness of the returned iterator.

I agree we probably also want ADL here, but we'll need to bring in the generic array std::begin/std::end with using declarations.

573–574

You would need two explicit args because the third variadic pack can be empty.

include/llvm/IR/Module.h
595

You could break the line better using a using declaration instead. If only I knew @chandlerc's thoughts on manually editing whitespace...

EricWF requested changes to this revision.Dec 24 2016, 7:22 PM
EricWF added a reviewer: EricWF.
EricWF added inline comments.
include/llvm/ADT/STLExtras.h
477

After double checking the standard I'm confident to say this code has UB; and should be fixed before committing.

This revision now requires changes to proceed.Dec 24 2016, 7:22 PM
chandlerc updated this revision to Diff 82457.Dec 24 2016, 10:36 PM
chandlerc edited edge metadata.
chandlerc marked an inline comment as done.

Mostly addressed Dave's comments but still chasing a weird const issue...

Thanks for the review Dave and Eric! (Also, thanks for the help debugging and resolving issues on IRC Eric!)

I think everything is ship-shape, so I'm gonna land this and fight the build bots until it sticks. Shout if anything else catches your eye!

include/llvm/ADT/STLExtras.h
455–456

Nah, using a pair is much nicer. Half as many big tuple lookups.

I tried using iterator_range, but that's actually not a good fit because we're mutating things and doing other custom things.... But the pair seems nicer.

460–461

I'm not such a big fan of that doxygen these days. It doesn't seem to support lots of things I want, such as the fact that there are two statements about the return here...

That said, if you see a good way to restructure the comment, by all means?

477

Fixed by initializing an array instead of just 'auto'. Required massaging C++ harder than I'd like, but such is life.

521–522

Not really, because we can't move here as we need to access it twice. The reason for the forwarding reference is so that it can be either an L-value reference or an R-value reference pointing at a temporary iterator_range. We just need to look through it to the internal iterators.

521–522

Chatted with Eric on IRC about this - R-values are safe and intended. And we shouldn't forward when doing the begin thing for the reasons Eric lists.

Regarding ADL, I'm not convinced the complexity of doing it is worth the trouble particularly in an member init list. Anyways, we can add that if folks want it in the future.

532–534

This is just how the current iterator_facade_base works. If we want to change that we can, but it shouldn't be here.

573–574

I thought about this, and the static assert actually seemed more clear. You end up having to name the explicit template arguments and write a lot of boilerplate to handle them and error messages aren't clear *why* there are these explicit arguments. With the static assert it seemed more direct to me. Happy to consider follow-ups to go a different way though if there's a reason! =]

include/llvm/IR/Module.h
595

If we want to start moving everything to using declarations, maybe... but not this patch please. =D

unittests/ADT/STLExtrasTest.cpp
257–269

The particular data sets were chosen at random, but contained meaningfully different iterator types and categories. Nothing more or less.

Regarding temporary tests, yep, added. Thanks for suggesting, they found a bug where i was missing a & in the declval.

266

Yea, this does seem nice, but I'll leave it to a follow-up. I tried briefly and it added a lot of complexity. I probably just missed a good way to do it though.

This revision was automatically updated to reflect the committed changes.