Page MenuHomePhabricator

[ADT] Add an 'llvm::seq' function which produces an iterator range over a sequence of values. It increments through the values in the half-open range: [Begin, End), producing those values when indirecting the iterator. It should support integers...
ClosedPublic

Authored by chandlerc on Mar 3 2016, 2:47 PM.

Details

Summary

..., iterators, and any other type providing these basic arithmetic operations.

This came up in the C++ standards committee meeting, and it seemed like
a useful construct that LLVM might want as well, and I wanted to
understand how easily we could solve it. I suspect this can be used to
write simpler counting loops even in LLVM along the lines of:

for (int i : seq(0, v.size())) {
  ...
};

As part of this, I had to fix the lack of a proxy object returned from
the operator[] in our iterator facade.

Diff Detail

Repository
rL LLVM

Event Timeline

chandlerc updated this revision to Diff 49779.Mar 3 2016, 2:47 PM
chandlerc retitled this revision from to [ADT] Add an 'llvm::seq' function which produces an iterator range over a sequence of values. It increments through the values in the half-open range: [Begin, End), producing those values when indirecting the iterator. It should support integers....
chandlerc updated this object.
chandlerc added reviewers: hfinkel, dexonsmith.
chandlerc added a subscriber: llvm-commits.

Hi Chandler

Haven’t looked at the code yet, but I like the idea and the use of it you gave.

Seems like most integer cases are going to start at 0. Could we have a seq(n) to handle [0, n) ranges?

Cheers,
Pete

dblaikie added inline comments.
include/llvm/ADT/Sequence.h
41 ↗(On Diff #49779)

that should be forward<U>, I think?

include/llvm/ADT/iterator.h
139 ↗(On Diff #49779)

Not entirely following here, so I might be completely in the weeds, but is this any better than simply returning by value? (I suppose this implementation supports both cases where the value isn't copyable/must be referenced and where the iterator/value is transient and must be copied, then?)

unittests/ADT/SequenceTest.cpp
21 ↗(On Diff #49779)

Test with a type that supports unary ++/-- but not binary +/- (you mention this in comments in the implementation about why we can't implement unary ++/-- in terms of binary +/-)?

Possibly test that a sequence iterator over such a non-random-access sequence is itself, not random access (so we don't get quiet O(N) binary +/-)?

chandlerc updated this revision to Diff 49801.Mar 3 2016, 11:45 PM
chandlerc marked 2 inline comments as done.

Update with fixes based on code review.

Updated and with answers below...

Hi Chandler

Haven’t looked at the code yet, but I like the idea and the use of it you gave.

Seems like most integer cases are going to start at 0. Could we have a seq(n) to handle [0, n) ranges?

We could, but I'm inclined to write the '0, '. It's pretty short, and I'm a bit hesitant to add too many overloads with different arity unless there is a significant inconvenience.

include/llvm/ADT/iterator.h
139 ↗(On Diff #49779)

The spec says convertible to a reference. In part, if the iterator is mutable, you're required to be able to write through the reference. =/

unittests/ADT/SequenceTest.cpp
21 ↗(On Diff #49779)

Bleh, the non-random-access thing just doesn't work. I have to choose a tag for the iterator category, and that ends up dictating everything. I've removed the code trying to support non-random-access stuff.

In order to make that work if we ever want too, we'd need to build a type function to select a iterator category based on what operators are supported.... But that seems like *waaay* too much complexity at this juncture. For now, I've reduced it to the simple form.

dblaikie accepted this revision.Mar 4 2016, 2:46 PM
dblaikie added a reviewer: dblaikie.

Looks good.

(I'd +1 Pete's comment, for a seq(t) -> seq(T(), t) helper but that can be added in follow up/when needed)

This revision is now accepted and ready to land.Mar 4 2016, 2:46 PM

What do you think Justin? I think not having to remember to make an end variable is nice, and I'd like to start somewhere on building up more range stuff, and this seems like a reasonable place to start...

sanjoy added a subscriber: sanjoy.Apr 6 2016, 10:58 PM

Hi Chandler,

This is great! With this and map_iterator, writing iterators for semi-complex data structures will become a lot more scalable, since I can write them as maps of Foo::getElementAtIndex(i) over seq(0, elementCount). E.g. this is how easy it is to implement a range for operand bundles with this change: (rough code) https://ghostbin.com/paste/srpq7

This revision was automatically updated to reflect the committed changes.