This is an archive of the discontinued LLVM Phabricator instance.

Support rvalue references in enumerate range adapter.
ClosedPublic

Authored by zturner on Sep 30 2016, 1:33 PM.

Details

Summary

@dblaikie pointed an issue wherein if you wrote a ranged-based for like this:

for (auto X : enumerate(std::vector<int>{1,2,3})) {
}

The vector would be destroyed since the range adapter stored the argument by reference. This patch adds a new template to stl extras called remove_rvalue_reference which is similar to std::remove_reference but only removes rvalue reference. This way, if it is constructed with an rvalue, it will copy the range, but if it is constructed with an lvalue, it will store by reference.

A test is added to verify that it works. The same test was confirmed to segfault before this patch.

Diff Detail

Event Timeline

zturner updated this revision to Diff 73128.Sep 30 2016, 1:33 PM
zturner retitled this revision from to Support rvalue references in enumerate range adapter..
zturner updated this object.
zturner added reviewers: chandlerc, dblaikie.
zturner added subscribers: llvm-commits, dblaikie.
dblaikie added inline comments.Sep 30 2016, 2:02 PM
include/llvm/ADT/STLExtras.h
680

So this is I think where it might be simpler than we're expecting.

If I change this line to:

R  Range;

all the tests still pass. It may be worth adding a test with a container type (a simple wrapper container) that tracks its lifetime with flags to ensure this is doing the right thing rather than invoking subtle UB - and/or potentially exposing R as a member of enumerator_impl and using static_asserts of is_same to test that the container type for an enumeration over an rvalue is the value type, and the container type for an enumeration over an lvalue is a reference type.

Something like:

struct Container {
  bool *Destroyed;
  Container(bool *Destroyed) : Destroyed(Destroyed) { } 
  /* begin and end, etc - could just have them both return nullptr */
  /* move ctor that just nulls out the Destroyed pointer */
  /* copy ops and move assign are implicitly disabled/removed by presence of a user declared move ctor */
  /* dtor that does: *Destroyed = true; */
};

bool Destroyed = false;
{
  auto Enumerator = enumerate(C(&Destroyed));
  /* check Destroyed == false */
}
/* check Destroyed == true */

also you could check that for an lvalue, no copy/move is required:

struct Container {
  Container();
  /* delete the move ctor and all the other move/copy ops will be implicitly deleted/not provided *(or delete them all if you want to be more explicit) */
  /* again, begin/end can just return nullptr */
};
Container c;
enumerate(c); // this should compile, even though the container is not copyable/movable

The reason I think this works is "reference collapsing". When you pass an rvalue reference to X a template argument "T &&" then T is deduced X (the value type), but if you pass an lvalue, T is deduced to "X&". That's my understanding, at least.

zturner updated this revision to Diff 73187.Sep 30 2016, 9:47 PM

Updated with suggestions.

chandlerc edited edge metadata.Sep 30 2016, 11:09 PM

Add a test showing mutation? Specifically that the range can be mutated even when a temporary is used, and that when an L-value is used the mutation mutates the underlying object rather than a copy (either of the element or the container).

unittests/ADT/STLExtrasTest.cpp
267

80-columns?

zturner updated this revision to Diff 73205.Oct 1 2016, 6:46 PM
zturner edited edge metadata.

This should address Chandler's concern. I had to fix the declval in the definition of iterator to allow modification of rvalues.

chandlerc added inline comments.Oct 1 2016, 8:08 PM
include/llvm/ADT/STLExtras.h
640–652

No need for public? This is a struct...

641–645

I don't really understand this comment or the remove_const below...

For example, does the remove_const cause this to allow mutation even when the range itself doesn't? That doesn't seem good...

(also, 80 columns)

650–652

?

zturner added inline comments.Oct 1 2016, 8:21 PM
include/llvm/ADT/STLExtras.h
641–645

The remove_const snuck in which I was tinkering around with things. I need to remove that. Thanks for pointing it out.

Correct me if I'm wrong here, but at least the conclusion I came to when trying to get this working was this:

  1. std::declval<R>() returns an R&&
  2. std::begin(R&&) will select the overload of std::begin() that accepts a const Container&, because the result of std::declval<R>() is an rvalue, so it can't bind to the overload of std::begin() that accepts a Container&.
  3. As a result, std::begin() returns a const_iterator.
  4. This means I is typedefed to std::vector<T>::const_iterator, which will obviously not work for mutation. (vector just an example since that's what i used in the tests, replace with arbitrary R).

By writing std::declval<R&>() you're forcing it to return an rvalue, so we get a non-const iterator (unless of course R is itself a const type)

Also I'm using clang-format. I will double check the columns but I'm not sure why they wouldn't be 80

I double checked the columns. I'm not going over 80 anywhere. What are you seeing? A few of my lines are exactly 80 columns, which means that the "cursor" would be on the 81st. Is that throwing off the tool you're using? Phab doesn't even show me columns so I'm not sure how you're viewing them.

zturner added inline comments.Oct 1 2016, 8:26 PM
include/llvm/ADT/STLExtras.h
641–645

The last sentence should say "By writing std::declval<R&>() you're forcing it to return an lvalue"

zturner updated this revision to Diff 73207.Oct 1 2016, 8:34 PM

Removed some accidental code left in.

zturner updated this revision to Diff 73356.Oct 3 2016, 3:26 PM

Updated with the proper fix for lvalue / rvalue-ness. Confirmed with rsmith@ that this was in fact the right incantation. A side benefit of this is that we were already trying to do this same thing earlier in the file, but we had gotten it wrong there too. So I fixed it there and re-used the top-level typedef.

This entire system really needs a bunch of work to fully interoperate well with iterators. I don't want to sign you up for all of it so I'm trying to suggest minimal changes below. Hopefully they don't cause too many problems. Not sure where to draw the line here without yak shaving this into the next century. I'll probably sign myself up to fix some of this now that I'm neck deep.... Anyways, lemme know if the below changes work.

include/llvm/ADT/STLExtras.h
35–40

Put these as members of enumerate_impl so that they can directly use R? I would alse name them IteratorT and ValueT.

But I don't know that you want to define ValueT this way. Instead, I would use std::iterator_traits<IteratorT>::value_type and std::iterator_traits<IteratorT>::reference which seem like the more formal way to extract this information.

However, this may in turn show that you can't actually nest these yet. But if you want to fix that, I think it will need a much more invasive change. I wouldn't worry with that unless you really want to...

639–640

Just accept this by-value, no need for r-value reference here.

zturner added inline comments.Oct 4 2016, 9:21 AM
include/llvm/ADT/STLExtras.h
35–40

As mentioned, make_filter_range also uses IterOfRange. In fact, there was a bug in it before, so putting it here both fixes an existing bug in make_filter_range and hopefully ensures that nobody will make this same mistake again. I only put ValueOfRange here as well since IterOfRange was already here.

In response to your second point, I tried it out and it doesn't quite work. In order for this to work I will need to typedef reference inside of enumerator_impl::iterator. That might seem obvious, but a cursory glance at the standard does not seem to require that range-for-iterators support iterator_traits. So it would be nice to be able to use enumerate (and any other range-adaptors we might invent) with iterators that don't have full support for iterator_traits.

zturner updated this revision to Diff 73494.Oct 4 2016, 9:24 AM

Fixed the superfluous std::move. Will wait to see your comments on the iterator_traits before changing the definition of ValueOfRange.

zturner updated this revision to Diff 73499.Oct 4 2016, 9:46 AM

Actually David convinced me of the usefulness of supporting iterator. This should do the trick, and it still works with nested enumeration.

zturner updated this revision to Diff 73506.Oct 4 2016, 10:30 AM

Sigh... Dependent base class rule. Had to make this really ugly by typedefing the base so I could explicitly pull in value_type

zturner updated this revision to Diff 73543.Oct 4 2016, 1:18 PM

Fixes some more issues with my last patch. I think this is as far as I can go but let me know if there's anything else critical missing.

chandlerc added inline comments.Oct 4 2016, 3:56 PM
include/llvm/ADT/STLExtras.h
657–667

Deriving from std::iterator isn't really what you want to do...

What may not be obvious is that in these three typedefs "iterator" refers to the injected class name of the std::iterator base class. You could equivalently write those three typedefs as:

typedef typename iterator::reference reference;

And so on...

But I don't think you want to try to inherit from std::iterator or typedef any of these things. Your type isn't a forward iterator. It is either an input or output iterator depending on the constness, and it has a few extra features. This will be really hard to model as-is...

I would just make a private typedef for your result type using std::iterator_traits<IterOfRange<R>>, and give up nesting enumerates until we completely overhaul how all of this code deals with ranges and iterators. Is there a reason you can't do that?

zturner updated this revision to Diff 73573.Oct 4 2016, 4:07 PM

Ok, let's try this a 22nd time :)

chandlerc accepted this revision.Oct 4 2016, 4:34 PM
chandlerc edited edge metadata.

LGTM. Sorry this ended up as such a mess. Small nit below, but feel free to submit.

include/llvm/ADT/STLExtras.h
629–634

I suspect this should still be in the detail namespace, and potentially still in the enumerator_impl class? Not sure when it floated out...

This revision is now accepted and ready to land.Oct 4 2016, 4:34 PM
This revision was automatically updated to reflect the committed changes.