[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]

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.

[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]

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]

Update with fixes based on code review.

[chandlerc]

Updated and with answers below...

In D17870#367653, @llvm-commits wrote:

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]

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)

[chandlerc]

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]

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

llvm/trunk/include/llvm/ADT/Sequence.h

+//===- Sequence.h - Utility for producing sequences of values ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This routine provides some synthesis utilities to produce sequences of
+/// values. The names are intentionally kept very short as they tend to occur
+/// in common and widely used contexts.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_SEQ_H
+#define LLVM_ADT_SEQ_H
+
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
+
+namespace llvm {
+
+namespace detail {
+template <typename ValueT>
+class value_sequence_iterator
+    : public iterator_facade_base<value_sequence_iterator<ValueT>,
+                                  std::random_access_iterator_tag,
+                                  const ValueT> {
+  typedef typename value_sequence_iterator::iterator_facade_base BaseT;
+
+  ValueT Value;
+
+public:
+  typedef typename BaseT::difference_type difference_type;
+  typedef typename BaseT::reference reference;
+
+  value_sequence_iterator() = default;
+
+  template <typename U>
+  value_sequence_iterator(U &&Value) : Value(std::forward<U>(Value)) {}
+
+  value_sequence_iterator &operator+=(difference_type N) {
+    Value += N;
+    return *this;
+  }
+  value_sequence_iterator &operator-=(difference_type N) {
+    Value -= N;
+    return *this;
+  }
+  using BaseT::operator-;
+  difference_type operator-(const value_sequence_iterator &RHS) const {
+    return Value - RHS.Value;
+  }
+
+  bool operator==(const value_sequence_iterator &RHS) const {
+    return Value == RHS.Value;
+  }
+  bool operator<(const value_sequence_iterator &RHS) const {
+    return Value < RHS.Value;
+  }
+
+  reference operator*() const { return Value; }
+};
+} // End detail namespace.
+
+template <typename ValueT>
+iterator_range<detail::value_sequence_iterator<ValueT>> seq(ValueT Begin,
+                                                            ValueT End) {
+  return make_range(detail::value_sequence_iterator<ValueT>(Begin),
+                    detail::value_sequence_iterator<ValueT>(End));
+}
+
+}
+
+#endif

llvm/trunk/include/llvm/ADT/iterator.h

 protected:
   enum {
     IsRandomAccess =
         std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value,
     IsBidirectional =
         std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value,
   };
 
+  /// A proxy object for computing a reference via indirecting a copy of an
+  /// iterator. This is used in APIs which need to produce a reference via
+  /// indirection but for which the iterator object might be a temporary. The
+  /// proxy preserves the iterator internally and exposes the indirected
+  /// reference via a conversion operator.
+  class ReferenceProxy {
+    friend iterator_facade_base;
+
+    DerivedT I;
+
+    ReferenceProxy(DerivedT I) : I(std::move(I)) {}
+
+  public:
+    operator ReferenceT() const { return *I; }
+  };
+
 public:
   DerivedT operator+(DifferenceTypeT n) const {
     static_assert(
         IsRandomAccess,
         "The '+' operator is only defined for random access iterators.");
     DerivedT tmp = *static_cast<const DerivedT *>(this);
     tmp += n;
     return tmp;
static_assert(
         IsRandomAccess,
         "Relational operators are only defined for random access iterators.");
     return !static_cast<const DerivedT *>(this)->operator<(RHS);
   }
 
   PointerT operator->() const {
     return &static_cast<const DerivedT *>(this)->operator*();
   }
-  ReferenceT operator[](DifferenceTypeT n) const {
+  ReferenceProxy operator[](DifferenceTypeT n) const {
     static_assert(IsRandomAccess,
                   "Subscripting is only defined for random access iterators.");
-    return *static_cast<const DerivedT *>(this)->operator+(n);
+    return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
   }
 };
 
 /// \brief CRTP base class for adapting an iterator to a different type.
 ///
 /// This class can be used through CRTP to adapt one iterator into another.
 /// Typically this is done through providing in the derived class a custom \c
 /// operator* implementation. Other methods can be overridden as well.

llvm/trunk/unittests/ADT/CMakeLists.txt

set(ADTSources
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
+  SequenceTest.cpp
   SetVectorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StringMapTest.cpp

llvm/trunk/unittests/ADT/SequenceTest.cpp

+//===- SequenceTest.cpp - Unit tests for a sequence abstraciton -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Sequence.h"
+#include "gtest/gtest.h"
+
+#include <list>
+
+using namespace llvm;
+
+namespace {
+
+TEST(SequenceTest, Basic) {
+  int x = 0;
+  for (int i : seq(0, 10))
+    EXPECT_EQ(x++, i);
+  EXPECT_EQ(10, x);
+
+  auto my_seq = seq(0, 4);
+  EXPECT_EQ(4, my_seq.end() - my_seq.begin());
+  for (int i : {0, 1, 2, 3})
+    EXPECT_EQ(i, (int)my_seq.begin()[i]);
+
+  EXPECT_TRUE(my_seq.begin() < my_seq.end());
+
+  auto adjusted_begin = my_seq.begin() + 2;
+  auto adjusted_end = my_seq.end() - 2;
+  EXPECT_TRUE(adjusted_begin == adjusted_end);
+  EXPECT_EQ(2, *adjusted_begin);
+  EXPECT_EQ(2, *adjusted_end);
+}
+
+} // anonymous namespace