[ADT] Zip range adapter

[bryant]

Summary

As discussed with jokereph over IRC a few weeks ago, this augments the STLExtras toolset with a zip iterator and range adapter. Zip comes in two varieties: zip, which will zip to the shortest of the input ranges, and zip_first, which limits its begin() == end() checks to just the first range.

[bryant]

clang-formatted to LLVM indentation style.

[dblaikie]

Generally lacking test coverage, and could consider using std::begin/std::end rather than member begin/end to make sure these algorithms work with arrays and other things without member begin/end.

include/llvm/ADT/STLExtras.h

238–259 ↗

(On Diff #67119)

These look like implementation details (& arguably ZipFirst/ZipShortest/Zippy are implementation details too) that should be hidden from the llvm namespace (either as local/nested types or in a 'detail' namespace, etc).

[bryant]

Use a more efficient method of generating the integer sequence. Encase NatList, Zippy, ZipFirst, ZipShortest in their own detail namespace.

[bryant]

In D23252#508788, @dblaikie wrote:

Generally lacking test coverage, and could consider using std::begin/std::end rather than member begin/end to make sure these algorithms work with arrays and other things without member begin/end.

I'd be happy to write tests for this, but where would they live, filesystem-wise? I would assume under test/*, but am unable to locate any tests of other STLExtra constructs.

Regarding using this with raw C arrays, I'm not sure that would be possible. From memory, C++11 compilers have special case handling for ranged-fors on raw arrays. You could certainly pass in initializer_list<T> into zip/zip_first, but then the initializer_list proxy would already have begin/end member functions.

[mehdi_amini]

In D23252#510783, @bryant wrote:

I'd be happy to write tests for this, but where would they live, filesystem-wise?

unittests/ADT.

[bryant]

Support zipping raw C arrays with std::{begin,end}.

[mehdi_amini]

include/llvm/ADT/STLExtras.h

537 ↗

(On Diff #67457)

Split into a separate patch for this addition (unless it is related to zip in a way that I missed)

[bryant]

Use detail:: namespace. Move out ranged copy/copy_if.

[bryant]

• When folding bools, replace std::array/std::all_of with a simple constexpr recursive function.
• Add basic unit test demonstrating rvalue input, mutability, and raw arrays.

[bryant]

accidentally deleted header.

[dblaikie]

include/llvm/ADT/STLExtras.h

301 ↗

(On Diff #67472)

This keeps a copy (or move) of all its arguments to allow for the rvalue case in a range-for loop? That would have surprising performance characteristics (implicit whole-container copies) for non-temporary parameters...

I think that gets into some pretty major design questions about the behavior here - and the major design problem/question with range proposals in general.

We might need to have a broader discussion about the design for anything like this - might be worth moving that part of the conversation to llvm-dev as I expect it'll be a bit more involved. But maybe here's OK & we can rope a few people in.

[dblaikie]

(might want to update the description to remove the mention of copy/copy_if now that they've been moved into a separate patch & make the title more specifically about zip range adapter, etc)

include/llvm/ADT/STLExtras.h

241–243 ↗

(On Diff #67472)

Recursive implementations only used in constexpr contexts are fine - but a recursive implementation used in a non-constexpr context may still be implemented recursively by the compiler & is usually best avoided. (this is a problem with constexpr currently - where the ideal implementation for constexpr is not the same as the ideal implementation for non-constexpr contexts)

& this isn't being called in a constexpr context, so I'm not sure of the value of flagging it as constexpr or designing it in a way that would be valid constexpr.

[bryant]

include/llvm/ADT/STLExtras.h

301 ↗

(On Diff #67472)

if by "non-temporary" you mean lvalue input, then no. the corresponding tuple member would be a reference. if it were a copy, the mutability demo in unit test wouldn't work. please correct me if i've misunderstood your question.

[bryant]

include/llvm/ADT/STLExtras.h

241–243 ↗

(On Diff #67472)

can you find a case where all_true is codegened into a recursive call?

[dblaikie]

include/llvm/ADT/STLExtras.h

241–243 ↗

(On Diff #67472)

Can't say I've tried, no. Fair point, though - just not exactly idiomatic (& admittedly variadic templates are on the fringes since they're not often used so idiom is still certainly evolving). Maybe Richard'll have some opinion here too. (or other people - don't mean to limit the review in any way)

301 ↗

(On Diff #67472)

Ah, indeed. You've not misunderstood - thanks for pointing out the test/explaining.

If that's all it takes to solve the temporary/non-temporary issue of range adapters, I'm really happy to hear it. But given my lack of understanding here I'm going to punt to Richard Smith, Chandler Carruth, on the C++ committee & who've been, at least somewhat (more than me, at least) aware of the goings on of range proposals, etc.

[george.burgess.iv]

Thanks for the patch!

Just a few drive-by comments. :)

include/llvm/ADT/STLExtras.h

241–243 ↗

(On Diff #67472)

I think constexpr makes some of the compilers we support unhappy; please use LLVM_CONSTEXPR instead.

(Also, FWIW,

template <typename... Bs> bool all_true(Bs... bools) {
  return all_of({bool(bools)...}, identity<bool>{});
}

would eliminate the potential recursion. Looks like this zip magic is declared above llvm::all_of, though.)

245 ↗

(On Diff #67472)

Is there a reason we can't just use std::index_sequence/std::make_index_sequence?

317 ↗

(On Diff #67472)

Please use /// for function/class documentation.

325 ↗

(On Diff #67472)

and here

unittests/Support/IteratorTest.cpp

101 ↗

(On Diff #67472)

Can we have one or more tests for zip_first, please? :)

[bryant]

include/llvm/ADT/STLExtras.h

241–243 ↗

(On Diff #67472)

this is good. i'm going to steal this, if you don't mind.

245 ↗

(On Diff #67472)

according to http://en.cppreference.com/w/cpp/utility/integer_sequence it's c++14, whereas i'm aiming for c++11.

[bryant]

• factor out mutability tests; test zip_first
• use triple slashes for fn doc comments
• replace potentially recursive fn with llvm::all_of

[bryant]

icmp echo request.

[zturner]

What is the status of this? I ended up writing my own zip implementation (see D25109) before it was pointed out to me that this already exists, but I see there has been no activity in some time.

It looks like this is waiting for comments from chandlerc@ and rsmith@?

include/llvm/ADT/STLExtras.h

251 ↗

(On Diff #67600)

For STL-like classes and functions, I believe we prefer to follow STL naming conventions. So I would imagine this should be zip_first

245 ↗

(On Diff #67472)

yes but we have llvm::integer_sequence in this very file. Can we use that instead?

[bryant]

Use already-present index_sequence/_of instead of NatList.

[bryant]

include/llvm/ADT/STLExtras.h

251 ↗

(On Diff #67600)

are you sure about this? Zippy/ZipFirst are auxiliary classes that aren't publicly accessible.

245 ↗

(On Diff #67472)

you're right, not sure how i missed this. fixed.

[bryant]

ping?

[mehdi_amini]

LGTM.

[bryant]

Increase lines of code by 12 with apply_tuple, as suggested by zturner.

[zturner]

If it increases code we shouldn't do it, I thought it would reduce lines of code because I thought I remembered that you had rolled something similar to apply on your own. Sorry for the bad suggestion :-/

[zturner]

Looks fine here too. Feel free to remove the apply() if you think it makes the code shorter or better.

[bryant]

The two main problems are that:

1. apply_tuple is defined at the bottom of the file which necessitates some very large forward decls.
2. I don't know of a direct way to invoke apply on a ctor without a wrapper func.

If the entire patch were moved to the bottom, then the clunky decls could be left out. However, zip would be separated from the rest of the iterator adapter definitions. Do you think this is a worthwhile adjustment?

[bryant]

• revert from using apply_tuple.
• follow stdlib naming conventions for the support classes in detail.

[bryant]

Nope.

llvm/trunk/include/llvm/ADT/STLExtras.h

make_filter_range(RangeT &&Range, PredicateT Pred) {
   using FilterIteratorT =
       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
   return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
                                     std::end(std::forward<RangeT>(Range)),
                                     std::move(Pred)),
                     FilterIteratorT(std::end(std::forward<RangeT>(Range))));
 }
 
+// forward declarations required by zip_shortest/zip_first
+template <typename R, class UnaryPredicate>
+bool all_of(R &&range, UnaryPredicate &&P);
+
+template <size_t... I> struct index_sequence;
+
+template <class... Ts> struct index_sequence_for;
+
+namespace detail {
+template <typename... Iters> class zip_first {
+public:
+  typedef std::input_iterator_tag iterator_category;
+  typedef std::tuple<decltype(*std::declval<Iters>())...> value_type;
+  std::tuple<Iters...> iterators;
+
+private:
+  template <size_t... Ns> value_type deres(index_sequence<Ns...>) {
+    return value_type(*std::get<Ns>(iterators)...);
+  }
+
+  template <size_t... Ns> decltype(iterators) tup_inc(index_sequence<Ns...>) {
+    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
+  }
+
+public:
+  value_type operator*() { return deres(index_sequence_for<Iters...>{}); }
+
+  void operator++() { iterators = tup_inc(index_sequence_for<Iters...>{}); }
+
+  bool operator!=(const zip_first<Iters...> &other) const {
+    return std::get<0>(iterators) != std::get<0>(other.iterators);
+  }
+  zip_first(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
+};
+
+template <typename... Iters> class zip_shortest : public zip_first<Iters...> {
+  template <size_t... Ns>
+  bool test(const zip_first<Iters...> &other, index_sequence<Ns...>) const {
+    return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
+                                              std::get<Ns>(other.iterators)...},
+                  identity<bool>{});
+  }
+
+public:
+  bool operator!=(const zip_first<Iters...> &other) const {
+    return test(other, index_sequence_for<Iters...>{});
+  }
+  zip_shortest(Iters &&... ts)
+      : zip_first<Iters...>(std::forward<Iters>(ts)...) {}
+};
+
+template <template <typename...> class ItType, typename... Args> class zippy {
+public:
+  typedef ItType<decltype(std::begin(std::declval<Args>()))...> iterator;
+
+private:
+  std::tuple<Args...> ts;
+
+  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
+    return iterator(std::begin(std::get<Ns>(ts))...);
+  }
+  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
+    return iterator(std::end(std::get<Ns>(ts))...);
+  }
+
+public:
+  iterator begin() { return begin_impl(index_sequence_for<Args...>{}); }
+  iterator end() { return end_impl(index_sequence_for<Args...>{}); }
+  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
+};
+} // End detail namespace
+
+/// zip iterator for two or more iteratable types.
+template <typename T, typename U, typename... Args>
+detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
+                                                       Args &&... args) {
+  return detail::zippy<detail::zip_shortest, T, U, Args...>(
+      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
+}
+
+/// zip iterator that, for the sake of efficiency, assumes the first iteratee to
+/// be the shortest.
+template <typename T, typename U, typename... Args>
+detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
+                                                          Args &&... args) {
+  return detail::zippy<detail::zip_first, T, U, Args...>(
+      std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <utility>
 //===----------------------------------------------------------------------===//
 
 /// \brief Function object to check whether the first component of a std::pair
 /// compares less than the first component of another std::pair.
 struct less_first {
   template <typename T> bool operator()(const T &lhs, const T &rhs) const {

llvm/trunk/unittests/ADT/IteratorTest.cpp

TEST(PointerIterator, Const) {
   const pointer_iterator<int *> Begin(std::begin(A));
   EXPECT_EQ(A, *Begin);
   EXPECT_EQ(A + 1, std::next(*Begin, 1));
   EXPECT_EQ(A + 2, std::next(*Begin, 2));
   EXPECT_EQ(A + 3, std::next(*Begin, 3));
   EXPECT_EQ(A + 4, std::next(*Begin, 4));
 }
 
+TEST(ZipIteratorTest, Basic) {
+  using namespace std;
+  const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
+  SmallVector<bool, 6> odd{1, 1, 0, 1, 1, 1};
+  const char message[] = "yynyyy\0";
+
+  for (auto tup : zip(pi, odd, message)) {
+    EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
+    EXPECT_EQ(get<0>(tup) & 0x01 ? 'y' : 'n', get<2>(tup));
+  }
+
+  // note the rvalue
+  for (auto tup : zip(pi, SmallVector<bool, 0>{1, 1, 0, 1, 1})) {
+    EXPECT_EQ(get<0>(tup) & 0x01, get<1>(tup));
+  }
+}
+
+TEST(ZipIteratorTest, ZipFirstBasic) {
+  using namespace std;
+  const SmallVector<unsigned, 6> pi{3, 1, 4, 1, 5, 9};
+  unsigned iters = 0;
+
+  for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
+    EXPECT_EQ(get<0>(tup), get<1>(tup) & 0x01);
+    iters += 1;
+  }
+
+  EXPECT_EQ(iters, 4u);
+}
+
+TEST(ZipIteratorTest, Mutability) {
+  using namespace std;
+  const SmallVector<unsigned, 4> pi{3, 1, 4, 1, 5, 9};
+  char message[] = "hello zip\0";
+
+  for (auto tup : zip(pi, message, message)) {
+    EXPECT_EQ(get<1>(tup), get<2>(tup));
+    get<2>(tup) = get<0>(tup) & 0x01 ? 'y' : 'n';
+  }
+
+  // note the rvalue
+  for (auto tup : zip(message, "yynyyyzip\0")) {
+    EXPECT_EQ(get<0>(tup), get<1>(tup));
+  }
+}
+
+TEST(ZipIteratorTest, ZipFirstMutability) {
+  using namespace std;
+  vector<unsigned> pi{3, 1, 4, 1, 5, 9};
+  unsigned iters = 0;
+
+  for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
+    get<1>(tup) = get<0>(tup);
+    iters += 1;
+  }
+
+  EXPECT_EQ(iters, 4u);
+
+  for (auto tup : zip_first(SmallVector<bool, 0>{1, 1, 0, 1}, pi)) {
+    EXPECT_EQ(get<0>(tup), get<1>(tup));
+  }
+}
+
 } // anonymous namespace