This is an archive of the discontinued LLVM Phabricator instance.

BitVector: use iterator_facade
AbandonedPublic

Authored by thegameg on May 22 2017, 1:32 PM.

Details

Summary

As pointed out by @dblaikie, the BitVector iterator introduced in r303227 could use iterator_facade_base to provide some default behaviors for iterators, like It++ and !=.

For that, we need to update the constraints on iterator_facade_base to support iterators with an operator-> returning a value, and not a const T&.

Diff Detail

Event Timeline

thegameg created this revision.May 22 2017, 1:32 PM
dblaikie accepted this revision.May 22 2017, 4:51 PM
dblaikie added inline comments.
include/llvm/ADT/iterator.h
170–174

What brought you to adding these static_asserts? Not that they're bad, just curious.

This revision is now accepted and ready to land.May 22 2017, 4:51 PM
dblaikie requested changes to this revision.May 22 2017, 4:54 PM
dblaikie added inline comments.
include/llvm/ADT/iterator.h
45–49

Actually, I see your leading comment and this change now.

I'm not sure if this change is valid/necessary. I /think/ op* is meant to return something convertible to the reference type of the iterator, even for a forward iterator. (& you should be able to take its address and use that so long as you don't modify the iterator).

ie: I /think/ this should be valid for all forward iterators:

auto &x = *my_iterator;
func(x);

but for the bit iterator you've added, that would be invalid - reference to temporary, etc.

I /think/ you have to return a (const, in this case) unsigned& from the op* and you should be fine & not need these changes)

This revision now requires changes to proceed.May 22 2017, 4:54 PM
thegameg added inline comments.May 22 2017, 5:09 PM
include/llvm/ADT/iterator.h
45–49

I'm not sure I understand how that would work, since find_first / find_next return an int, but we actually want the operator* to return an unsigned. We could return a const int&, but as @MatzeB pointed out here, it makes much more sense to return an unsigned.

thegameg added inline comments.May 22 2017, 5:26 PM
include/llvm/ADT/iterator.h
45–49

And this gets even more dangerous since the reference would be bound to the lifetime of the iterator, not the container.

dblaikie added inline comments.May 22 2017, 6:05 PM
include/llvm/ADT/iterator.h
45–49

The usual way to do this (& other iterators have this sort of thing - consider, say, what the implementation of std::istream_iterator might look like) is to have a member of the value type fo the iterator, in the iterator - and, yes, it'd only be valid while the iterator hasn't been mutated (ie: you can take a reference to the element returned from iterator's op*, but you can't increment the iterator and continue to use the reference).

This, I think, is how most forward iterators are implemented. But I'm not 100% sure if it's necessary, just that it seems to be the norm in my experience.

thegameg abandoned this revision.Jan 9 2018, 3:36 AM