Support rvalue references in enumerate range adapter.

[zturner]

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.

[dblaikie]

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 with suggestions.

[chandlerc]

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

169

80-columns?

[zturner]

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

[chandlerc]

include/llvm/ADT/STLExtras.h

635–636

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

636–640

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)

645–647

?

[zturner]

include/llvm/ADT/STLExtras.h

636–640

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)

[zturner]

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

[zturner]

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]

include/llvm/ADT/STLExtras.h

636–640

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

[zturner]

Removed some accidental code left in.

[zturner]

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.

[chandlerc]

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...

632–634

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

[zturner]

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]

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

[zturner]

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

[zturner]

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

[zturner]

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]

include/llvm/ADT/STLExtras.h

640–650

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]

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

[chandlerc]

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...

include/llvm/ADT/STLExtras.h

 #include <utility> // for std::pair
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
 namespace detail {
 
 template <typename RangeT>
-using IterOfRange = decltype(std::begin(std::declval<RangeT>()));
+using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
 
 } // End detail namespace
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <functional>
 //===----------------------------------------------------------------------===//
 
 template<class Ty>
 struct identity : public std::unary_function<Ty, Ty> {
   Ty &operator()(Ty &self) const {
template <typename T> struct deref {
   template <typename A, typename B>
   auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
     assert(lhs);
     assert(rhs);
     return func(*lhs, *rhs);
   }
 };
 
-namespace detail {
-template <typename I, typename V> class enumerator_impl {
-public:
-  template <typename X> struct result_pair {
-    result_pair(std::size_t Index, X Value) : Index(Index), Value(Value) {}
 
-    const std::size_t Index;
-    X Value;
-  };
 
-  struct iterator {
-    iterator(I Iter, std::size_t Index) : Iter(Iter), Index(Index) {}
+namespace detail {
+template <typename R> class enumerator_impl {
+public:
+  struct iterator
+      : public std::iterator<
+            std::forward_iterator_tag,
+            result_pair<
+                typename std::iterator_traits<IterOfRange<R>>::value_type>,
+            typename std::iterator_traits<IterOfRange<R>>::difference_type,
+            result_pair<typename std::iterator_traits<IterOfRange<R>>::pointer>,
+            result_pair<
+                typename std::iterator_traits<IterOfRange<R>>::reference>> {
+    typedef typename std::iterator_traits<iterator>::reference reference;
+    typedef typename std::iterator_traits<iterator>::pointer pointer;
+    typedef typename std::iterator_traits<iterator>::value_type value_type;
 
-    result_pair<const V> operator*() const {
-      return result_pair<const V>(Index, *Iter);
-    }
-    result_pair<V> operator*() { return result_pair<V>(Index, *Iter); }
+    iterator(IterOfRange<R> &&Iter, std::size_t Index)
+        : Iter(Iter), Index(Index) {}
+
+    reference operator*() const { return reference(Index, *Iter); }
 
     iterator &operator++() {
       ++Iter;
       ++Index;
       return *this;
     }
 
+    iterator &operator++(int) {
+      iterator Copy(*this);
+      ++(*this);
+      return Copy;
+    }
+
     bool operator!=(const iterator &RHS) const { return Iter != RHS.Iter; }
 
   private:
-    I Iter;
+    IterOfRange<R> Iter;
     std::size_t Index;
   };
 
-  enumerator_impl(I Begin, I End)
-      : Begin(std::move(Begin)), End(std::move(End)) {}
-
-  iterator begin() { return iterator(Begin, 0); }
-  iterator end() { return iterator(End, std::size_t(-1)); }
+public:
+  explicit enumerator_impl(R &&Range) : Range(std::forward<R>(Range)) {}
 
-  iterator begin() const { return iterator(Begin, 0); }
-  iterator end() const { return iterator(End, std::size_t(-1)); }
+  iterator begin() { return iterator(std::begin(Range), 0); }
+  iterator end() { return iterator(std::end(Range), std::size_t(-1)); }
 
 private:
-  I Begin;
-  I End;
+  R Range;
 };
-
-template <typename I>
-auto make_enumerator(I Begin, I End) -> enumerator_impl<I, decltype(*Begin)> {
-  return enumerator_impl<I, decltype(*Begin)>(std::move(Begin), std::move(End));
-}
 }
 
 /// Given an input range, returns a new range whose values are are pair (A,B)
 /// such that A is the 0-based index of the item in the sequence, and B is
 /// the value from the original sequence.  Example:
 ///
 /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
 /// for (auto X : enumerate(Items)) {
 ///   printf("Item %d - %c\n", X.Item, X.Value);
 /// }
 ///
 /// Output:
 ///   Item 0 - A
 ///   Item 1 - B
 ///   Item 2 - C
 ///   Item 3 - D
 ///
-template <typename R>
-auto enumerate(R &&Range)
-    -> decltype(detail::make_enumerator(std::begin(Range), std::end(Range))) {
-  return detail::make_enumerator(std::begin(Range), std::end(Range));
+template <typename R> detail::enumerator_impl<R> enumerate(R &&Range) {
+  return detail::enumerator_impl<R>(std::forward<R>(Range));
 }
 
 } // End llvm namespace
 
 #endif

unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, Rank) {
   // But going past 3 should work fine.
   EXPECT_EQ(4, f(rank<4>()));
 
   // And we can even go higher and just fall back to the last overload.
   EXPECT_EQ(4, f(rank<5>()));
   EXPECT_EQ(4, f(rank<6>()));
 }
 
-TEST(STLExtrasTest, Enumerate) {
+TEST(STLExtrasTest, EnumerateLValue) {
+  // Test that a simple LValue can be enumerated and gives correct results with
+  // multiple types, including the empty container.
   std::vector<char> foo = {'a', 'b', 'c'};
-
-  std::vector<std::pair<std::size_t, char>> results;
+  std::vector<std::pair<std::size_t, char>> CharResults;
 
   for (auto X : llvm::enumerate(foo)) {
-    results.push_back(std::make_pair(X.Index, X.Value));
+    CharResults.emplace_back(X.Index, X.Value);
   }
-  ASSERT_EQ(3u, results.size());
-  EXPECT_EQ(0u, results[0].first);
-  EXPECT_EQ('a', results[0].second);
-  EXPECT_EQ(1u, results[1].first);
-  EXPECT_EQ('b', results[1].second);
-  EXPECT_EQ(2u, results[2].first);
-  EXPECT_EQ('c', results[2].second);
-
-  results.clear();
-  const std::vector<int> bar = {'1', '2', '3'};
+  ASSERT_EQ(3u, CharResults.size());
+  EXPECT_EQ(std::make_pair(0u, 'a'), CharResults[0]);
+  EXPECT_EQ(std::make_pair(1u, 'b'), CharResults[1]);
+  EXPECT_EQ(std::make_pair(2u, 'c'), CharResults[2]);
+
+  // Test a const range of a different type.
+  std::vector<std::pair<std::size_t, int>> IntResults;
+  const std::vector<int> bar = {1, 2, 3};
   for (auto X : llvm::enumerate(bar)) {
-    results.push_back(std::make_pair(X.Index, X.Value));
+    IntResults.emplace_back(X.Index, X.Value);
   }
-  EXPECT_EQ(0u, results[0].first);
-  EXPECT_EQ('1', results[0].second);
-  EXPECT_EQ(1u, results[1].first);
-  EXPECT_EQ('2', results[1].second);
-  EXPECT_EQ(2u, results[2].first);
-  EXPECT_EQ('3', results[2].second);
+  ASSERT_EQ(3u, IntResults.size());
+  EXPECT_EQ(std::make_pair(0u, 1), IntResults[0]);
+  EXPECT_EQ(std::make_pair(1u, 2), IntResults[1]);
+  EXPECT_EQ(std::make_pair(2u, 3), IntResults[2]);
 
-  results.clear();
+  // Test an empty range.
+  IntResults.clear();
   const std::vector<int> baz;
   for (auto X : llvm::enumerate(baz)) {
-    results.push_back(std::make_pair(X.Index, X.Value));
+    IntResults.emplace_back(X.Index, X.Value);
   }
-  EXPECT_TRUE(baz.empty());
+  EXPECT_TRUE(IntResults.empty());
 }
 
-TEST(STLExtrasTest, EnumerateModify) {
+TEST(STLExtrasTest, EnumerateModifyLValue) {
+  // Test that you can modify the underlying entries of an lvalue range through
+  // the enumeration iterator.
   std::vector<char> foo = {'a', 'b', 'c'};
+  std::vector<std::pair<std::size_t, char>> CharResults;
 
   for (auto X : llvm::enumerate(foo)) {
     ++X.Value;
   }
-
   EXPECT_EQ('b', foo[0]);
   EXPECT_EQ('c', foo[1]);
   EXPECT_EQ('d', foo[2]);
 }
+
+TEST(STLExtrasTest, EnumerateRValueRef) {
+  // Test that an rvalue can be enumerated.
+  std::vector<std::pair<std::size_t, int>> Results;
+
+  auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
+
+  for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
+    Results.emplace_back(X.Index, X.Value);
+  }
+
+  ASSERT_EQ(3u, Results.size());
+  EXPECT_EQ(std::make_pair(0u, 1), Results[0]);
+  EXPECT_EQ(std::make_pair(1u, 2), Results[1]);
+  EXPECT_EQ(std::make_pair(2u, 3), Results[2]);
+}
+
+TEST(STLExtrasTest, EnumerateModifyRValue) {
+  // Test that when enumerating an rvalue, modification still works (even if
+  // this isn't terribly useful, it at least shows that we haven't snuck an
+  // extra const in there somewhere.
+  std::vector<std::pair<std::size_t, char>> Results;
+
+  for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
+    ++X.Value;
+    Results.emplace_back(X.Index, X.Value);
+  }
+
+  ASSERT_EQ(3u, Results.size());
+  EXPECT_EQ(std::make_pair(0u, '2'), Results[0]);
+  EXPECT_EQ(std::make_pair(1u, '3'), Results[1]);
+  EXPECT_EQ(std::make_pair(2u, '4'), Results[2]);
+}
+
+TEST(STLExtrasTest, EnumerateNested) {
+  std::vector<std::tuple<std::size_t, std::size_t, char>> Results;
+
+  for (auto X : enumerate(enumerate(std::vector<char>{'1', '2', '3'}))) {
+    Results.emplace_back(X.Index, X.Value.Index, X.Value.Value);
+  }
+
+  ASSERT_EQ(3u, Results.size());
+  EXPECT_EQ(std::make_tuple(0u, 0u, '1'), Results[0]);
+  EXPECT_EQ(std::make_tuple(1u, 1u, '2'), Results[1]);
+  EXPECT_EQ(std::make_tuple(2u, 2u, '3'), Results[2]);
+}
+
+template <bool B> struct CanMove {};
+template <> struct CanMove<false> {
+  CanMove(CanMove &&) = delete;
+
+  CanMove() = default;
+  CanMove(const CanMove &) = default;
+};
+
+template <bool B> struct CanCopy {};
+template <> struct CanCopy<false> {
+  CanCopy(const CanCopy &) = delete;
+
+  CanCopy() = default;
+  CanCopy(CanCopy &&) = default;
+};
+
+template <bool Moveable, bool Copyable>
+struct Range : CanMove<Moveable>, CanCopy<Copyable> {
+  explicit Range(int &C, int &M, int &D) : C(C), M(M), D(D) {}
+  Range(const Range &R) : CanCopy<Copyable>(R), C(R.C), M(R.M), D(R.D) { ++C; }
+  Range(Range &&R) : CanMove<Moveable>(std::move(R)), C(R.C), M(R.M), D(R.D) {
+    ++M;
+  }
+  ~Range() { ++D; }
+
+  int &C;
+  int &M;
+  int &D;
+
+  int *begin() { return nullptr; }
+  int *end() { return nullptr; }
+};
+
+TEST(STLExtrasTest, EnumerateLifetimeSemantics) {
+  // Test that when enumerating lvalues and rvalues, there are no surprise
+  // copies or moves.
+
+  // With an rvalue, it should not be destroyed until the end of the scope.
+  int Copies = 0;
+  int Moves = 0;
+  int Destructors = 0;
+  {
+    auto E1 = enumerate(Range<true, false>(Copies, Moves, Destructors));
+    // Doesn't compile.  rvalue ranges must be moveable.
+    // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
+    EXPECT_EQ(0, Copies);
+    EXPECT_EQ(1, Moves);
+    EXPECT_EQ(1, Destructors);
+  }
+  EXPECT_EQ(0, Copies);
+  EXPECT_EQ(1, Moves);
+  EXPECT_EQ(2, Destructors);
+
+  Copies = Moves = Destructors = 0;
+  // With an lvalue, it should not be destroyed even after the end of the scope.
+  // lvalue ranges need be neither copyable nor moveable.
+  Range<false, false> R(Copies, Moves, Destructors);
+  {
+    auto Enumerator = enumerate(R);
+    (void)Enumerator;
+    EXPECT_EQ(0, Copies);
+    EXPECT_EQ(0, Moves);
+    EXPECT_EQ(0, Destructors);
+  }
+  EXPECT_EQ(0, Copies);
+  EXPECT_EQ(0, Moves);
+  EXPECT_EQ(0, Destructors);
+}
 }