[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

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

538

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

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

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

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

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

[dblaikie]

include/llvm/ADT/STLExtras.h

241–243

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

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

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

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

317

Please use /// for function/class documentation.

325

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

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

245

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

245

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

251

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

[bryant]

Use already-present index_sequence/_of instead of NatList.

[bryant]

include/llvm/ADT/STLExtras.h

245

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

251

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

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

include/llvm/ADT/STLExtras.h

auto reverse(
     ContainerTy &&C,
     typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
     -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
                            llvm::make_reverse_iterator(std::begin(C)))) {
   return make_range(llvm::make_reverse_iterator(std::end(C)),
                     llvm::make_reverse_iterator(std::begin(C)));
 }
 
+namespace detail {
+template <unsigned N, unsigned... Ns> struct NatList {
+  using eval = typename NatList<N - 1, N - 1, Ns...>::eval;
+};
+
+template <unsigned... Ns> struct NatList<0, Ns...> {
+  using eval = NatList<Ns...>;
+};
+
+template <typename... Iters> class ZipFirst {
+public:
+  typedef typename NatList<sizeof...(Iters)>::eval nat_list;
+  typedef std::input_iterator_tag iterator_category;
+  typedef std::tuple<decltype(*std::declval<Iters>())...> value_type;
+  std::tuple<Iters...> iterators;
+
+private:
+  template <unsigned... Ns> value_type deres(NatList<Ns...>) {
+    return value_type(*std::get<Ns>(iterators)...);
+  }
+
+  template <unsigned... Ns> decltype(iterators) tup_inc(NatList<Ns...>) {
+    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
+  }
+
+public:
+  value_type operator*() { return deres(nat_list{}); }
+
+  void operator++() { iterators = tup_inc(nat_list{}); }
+
+  bool operator!=(const ZipFirst<Iters...> &other) const {
+    return std::get<0>(iterators) != std::get<0>(other.iterators);
+  }
+  ZipFirst(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
+};
+
+template <typename... Iters> class ZipShortest : public ZipFirst<Iters...> {
+  template <unsigned... Ns>
+  bool test(const ZipFirst<Iters...> &other, NatList<Ns...>) const {
+    std::array<bool, sizeof...(Iters)> conds = {
+        (std::get<Ns>(this->iterators) != std::get<Ns>(other.iterators))...};
+    return std::all_of(conds.begin(), conds.end(), [](bool a) { return a; });
+  }
+
+public:
+  bool operator!=(const ZipFirst<Iters...> &other) const {
+    return test(other, typename ZipFirst<Iters...>::nat_list{});
+  }
+  ZipShortest(Iters &&... ts)
+      : ZipFirst<Iters...>(std::forward<Iters>(ts)...) {}
+};
+
+template <template <typename...> class ItType, typename... Args> class Zippy {
+public:
+  typedef ItType<typename std::remove_reference<Args>::type::iterator...>
+      iterator;
+
+private:
+  typedef typename NatList<sizeof...(Args)>::eval nat_list;
+  std::tuple<Args...> ts;
+
+  template <unsigned... Ns> iterator begin_impl(NatList<Ns...>) {
+    return iterator(std::get<Ns>(ts).begin()...);
+  }
+  template <unsigned... Ns> iterator end_impl(NatList<Ns...>) {
+    return iterator(std::get<Ns>(ts).end()...);
+  }
+
+public:
+  iterator begin() { return begin_impl(nat_list{}); }
+  iterator end() { return end_impl(nat_list{}); }
+  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>
+Zippy<ZipShortest, T, U, Args...> zip(T &&t, U &&u, Args &&... args) {
+  return Zippy<ZipShortest, 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>
+Zippy<ZipFirst, T, U, Args...> zip_first(T &&t, U &&u, Args &&... args) {
+  return Zippy<ZipFirst, 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 {

 /// Wrapper function around std::transform to apply a function to a range and
 /// store the result elsewhere.
 template <typename R, class OutputIt, typename UnaryPredicate>
 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate &&P) {
   return std::transform(Range.begin(), Range.end(), d_first,
                         std::forward<UnaryPredicate>(P));
 }
 
+template <typename R, class OutputIt>
+OutputIt copy(R &&Range, OutputIt d_first) {
+  return std::copy(Range.begin(), Range.end(), d_first);
+}
+
+template <typename R, class OutputIt, typename UnaryPredicate>
+OutputIt copy_if(R &&Range, OutputIt d_first, UnaryPredicate &&P) {
+  return std::copy(Range.begin(), Range.end(), d_first,
+                   std::forward<UnaryPredicate>(P));
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 
 // Implement make_unique according to N3656.
 
 /// \brief Constructs a `new T()` with the given args and returns a
 ///        `unique_ptr<T>` which owns the object.