[ADT] Add a generic concatenating iterator and range.

[chandlerc]

Summary

This allows both defining convenience iterator/range accessors on types
which walk across N different independent ranges within the object, and
more direct and simple usages with range based for loops such as shown
in the unittest. The same facilities are used for both. They end up
quite small and simple as it happens.

I've also switched an iterator on Module to use this. I would like to
add another convenience iterator that includes even more sequences as
part of it and seeing this one already present motivated me to actually
abstract it away and introduce a general utility.

[dblaikie]

Generally looks good - bunch of optional bits & pieces/thoughts.

include/llvm/ADT/STLExtras.h

455–456

Any particular tradeoff between doing this representation compared to std::tuple<std::pair<IterTs>...> (where the pairs contain begin/end)?

Maybe I'll understand as I read further.

460–461

should this be a \returns doxy comment to comment the return semantics more explicitly

521–522

If 'Ranges' is accepted by universal reference (or what's the preferred term these days?) should these begin/end call parameters be std::forward'd?
& ADL begin/end call?

532–534

Usually suggested that op overloads that can be non-members should be non-members (could still be friend) to allow equal implicit conversions on both operands. Perhaps not applicable here (can't think of any particular implicit ops that'd be asymmetric here - but might be good as a matter of course/consistency/etc.

573–574

Would it be better to have a single explicit arg before the variadic template arg - rather than static_assert? I suppose it's much of a muchness.

unittests/ADT/STLExtrasTest.cpp

257–269

What's the particular motivation for these data sets? (length 4, 2, 2 - vector, list, and SmallVector - seems like list's iterator's a strict subset of the others, so if it works for that, not sure adding the others adds lots of coverage & also not sure of the motivation for those lengths)

I guess there's no nice way to avoid creating a new data structure for the result? (I think GTest has some container comparison helpers, but I guess they don't work for arbitrary ranges?)

257–269

Worth testing the copy/non-copy/lifetime-extension semantics when a temporary is passed in to concat?

266

Might be nice (could be a separate change) to skip the explicit value type parameter when the subranges have an exact match.

[EricWF]

include/llvm/ADT/STLExtras.h

477

If I'm not mistaken this deduces to std::initializer_list<FuncType>, and we shouldn't use initializer_list outside of performing initialization.

This should be changed to deduce as an array type instead (or any other sequenced container).

521–522

Should this accept Ranges as rvalues at all? It seems like it might hide a lifetime bug.

If we do want to accept rvalues I'm not convinced we should forward them. Doing so might result it Range&& binding to begin(Range const&) instead of begin(Range&), and changing the constness of the returned iterator.

I agree we probably also want ADL here, but we'll need to bring in the generic array std::begin/std::end with using declarations.

573–574

You would need two explicit args because the third variadic pack can be empty.

include/llvm/IR/Module.h

595

You could break the line better using a using declaration instead. If only I knew @chandlerc's thoughts on manually editing whitespace...

[EricWF]

include/llvm/ADT/STLExtras.h

477

After double checking the standard I'm confident to say this code has UB; and should be fixed before committing.

[chandlerc]

Mostly addressed Dave's comments but still chasing a weird const issue...

[chandlerc]

Thanks for the review Dave and Eric! (Also, thanks for the help debugging and resolving issues on IRC Eric!)

I think everything is ship-shape, so I'm gonna land this and fight the build bots until it sticks. Shout if anything else catches your eye!

include/llvm/ADT/STLExtras.h

455–456

Nah, using a pair is much nicer. Half as many big tuple lookups.

I tried using iterator_range, but that's actually not a good fit because we're mutating things and doing other custom things.... But the pair seems nicer.

460–461

I'm not such a big fan of that doxygen these days. It doesn't seem to support lots of things I want, such as the fact that there are two statements about the return here...

That said, if you see a good way to restructure the comment, by all means?

477

Fixed by initializing an array instead of just 'auto'. Required massaging C++ harder than I'd like, but such is life.

521–522

Not really, because we can't move here as we need to access it twice. The reason for the forwarding reference is so that it can be either an L-value reference or an R-value reference pointing at a temporary iterator_range. We just need to look through it to the internal iterators.

521–522

Chatted with Eric on IRC about this - R-values are safe and intended. And we shouldn't forward when doing the begin thing for the reasons Eric lists.

Regarding ADL, I'm not convinced the complexity of doing it is worth the trouble particularly in an member init list. Anyways, we can add that if folks want it in the future.

532–534

This is just how the current iterator_facade_base works. If we want to change that we can, but it shouldn't be here.

573–574

I thought about this, and the static assert actually seemed more clear. You end up having to name the explicit template arguments and write a lot of boilerplate to handle them and error messages aren't clear *why* there are these explicit arguments. With the static assert it seemed more direct to me. Happy to consider follow-ups to go a different way though if there's a reason! =]

include/llvm/IR/Module.h

595

If we want to start moving everything to using declarations, maybe... but not this patch please. =D

unittests/ADT/STLExtrasTest.cpp

257–269

The particular data sets were chosen at random, but contained meaningfully different iterator types and categories. Nothing more or less.

Regarding temporary tests, yep, added. Thanks for suggesting, they found a bug where i was missing a & in the declval.

266

Yea, this does seem nice, but I'll leave it to a follow-up. I tried briefly and it added a lot of complexity. I probably just missed a good way to do it though.

include/llvm/ADT/STLExtras.h

 #include <memory>
 #include <tuple>
 #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"
+#include "llvm/Support/ErrorHandling.h"
 
 namespace llvm {
 
 // Only used by compiler if both template types are the same.  Useful when
 // using SFINAE to test for the existence of member functions.
 template <typename T, T> struct SameType;
 
 namespace detail {

 /// 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)...);
 }
 
+/// Iterator wrapper that concatenates sequences together.
+///
+/// This can concatenate different iterators, even with different types, into
+/// a single iterator provided the value types of all the concatenated
+/// iterators expose `reference` and `pointer` types that can be converted to
+/// `ValueT &` and `ValueT *` respectively. It doesn't support more
+/// interesting/customized pointer or reference types.
+///
+/// Currently this only supports forward or higher iterator categories as
+/// inputs and always exposes a forward iterator interface.
+template <typename ValueT, typename... IterTs>
+class concat_iterator
+    : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
+                                  std::forward_iterator_tag, ValueT> {
+  typedef typename concat_iterator::iterator_facade_base BaseT;
+
+  /// We store both the current and end iterators for each concatenated
+  /// sequence in a tuple of pairs.
+  ///
+  /// Note that something like iterator_range seems nice at first here, but the
+  /// range properties are of little benefit and end up getting in the way
+  /// because we need to do mutation on the current iterators.
+  std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
+
+  /// Attempts to increment a specific iterator.
+  ///
+  /// Returns true if it was able to increment the iterator. Returns false if
+  /// the iterator is already at the end iterator.
+  template <size_t Index> bool incrementHelper() {
+    auto &IterPair = std::get<Index>(IterPairs);
+    if (IterPair.first == IterPair.second)
+      return false;
+
+    ++IterPair.first;
+    return true;
+  }
+
+  /// Increments the first non-end iterator.
+  ///
+  /// It is an error to call this with all iterators at the end.
+  template <size_t... Ns> void increment(index_sequence<Ns...>) {
+    // Build a sequence of functions to increment each iterator if possible.
+    auto IncrementHelperFns = {&concat_iterator::incrementHelper<Ns>...};
+
+    // Loop over them, and stop as soon as we succeed at incrementing one.
+    for (auto &IncrementHelperFn : IncrementHelperFns)
+      if ((this->*IncrementHelperFn)())
+        return;
+
+    llvm_unreachable("Attempted to increment an end concat iterator!");
+  }
+
+  /// Returns null if the specified iterator is at the end. Otherwise,
+  /// dereferences the iterator and returns the address of the resulting
+  /// reference.
+  template <size_t Index> ValueT *getHelper() const {
+    auto &IterPair = std::get<Index>(IterPairs);
+    if (IterPair.first == IterPair.second)
+      return nullptr;
+
+    return &*IterPair.first;
+  }
+
+  /// Finds the first non-end iterator, dereferences, and returns the resulting
+  /// reference.
+  ///
+  /// It is an error to call this with all iterators at the end.
+  template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
+    // Build a sequence of functions to get from iterator if possible.
+    auto GetHelperFns = {&concat_iterator::getHelper<Ns>...};
+
+    // Loop over them, and return the first result we find.
+    for (auto &GetHelperFn : GetHelperFns)
+      if (ValueT *P = (this->*GetHelperFn)())
+        return *P;
+
+    llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
+  }
+
+public:
+  /// Constructs an iterator from a squence of ranges.
+  ///
+  /// We need the full range to know how to switch between each of the
+  /// iterators.
+  template <typename... RangeTs>
+  explicit concat_iterator(RangeTs &&... Ranges)
+      : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
+
+  using BaseT::operator++;
+  concat_iterator &operator++() {
+    increment(index_sequence_for<IterTs...>());
+    return *this;
+  }
+
+  ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
+
+  bool operator==(const concat_iterator &RHS) const {
+    return IterPairs == RHS.IterPairs;
+  }
+};
+
+namespace detail {
+/// Helper to store a sequence of ranges being concatenated and access them.
+///
+/// This is designed to facilitate providing actual storage when temporaries
+/// are passed into the constructor such that we can use it as part of range
+/// based for loops.
+template <typename ValueT, typename... RangeTs> class concat_range {
+public:
+  typedef concat_iterator<ValueT,
+                          decltype(std::begin(std::declval<RangeTs>()))...>
+      iterator;
+
+private:
+  std::tuple<RangeTs...> Ranges;
+
+  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
+    return iterator(std::get<Ns>(Ranges)...);
+  }
+  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
+    return iterator(make_range(std::end(std::get<Ns>(Ranges)),
+                               std::end(std::get<Ns>(Ranges)))...);
+  }
+
+public:
+  iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
+  iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
+  concat_range(RangeTs &&... Ranges)
+      : Ranges(std::forward<RangeTs>(Ranges)...) {}
+};
+}
+
+/// Concatenated range across two or more ranges.
+///
+/// The desired value type must be explicitly specified.
+template <typename ValueT, typename... RangeTs>
+detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
+  static_assert(sizeof...(RangeTs) > 1,
+                "Need more than one range to concatenate!");
+  return detail::concat_range<ValueT, RangeTs...>(
+      std::forward<RangeTs>(Ranges)...);
+}
+
 //===----------------------------------------------------------------------===//
 //     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 {

include/llvm/IR/Module.h

/// @{
   iterator_range<const_ifunc_iterator> ifuncs() const {
     return make_range(ifunc_begin(), ifunc_end());
   }
 
 /// @}
 /// @name Convenience iterators
 /// @{
 
-  template <bool IsConst> class global_object_iterator_t {
-    friend Module;
-
-    typename std::conditional<IsConst, const_iterator, iterator>::type
-        function_i,
-        function_e;
-    typename std::conditional<IsConst, const_global_iterator,
-                              global_iterator>::type global_i;
-
-    typedef
-        typename std::conditional<IsConst, const Module, Module>::type ModuleTy;
-
-    global_object_iterator_t(ModuleTy &M)
-        : function_i(M.begin()), function_e(M.end()),
-          global_i(M.global_begin()) {}
-    global_object_iterator_t(ModuleTy &M, int)
-        : function_i(M.end()), function_e(M.end()), global_i(M.global_end()) {}
+  typedef concat_iterator<GlobalObject, iterator, global_iterator>
+      global_object_iterator;
+  typedef concat_iterator<const GlobalObject, const_iterator,
+                          const_global_iterator>
+      const_global_object_iterator;
 
-  public:
-    global_object_iterator_t &operator++() {
-      if (function_i != function_e)
-        ++function_i;
-      else
-        ++global_i;
-      return *this;
-    }
-
-    typename std::conditional<IsConst, const GlobalObject, GlobalObject>::type &
-    operator*() const {
-      if (function_i != function_e)
-        return *function_i;
-      else
-        return *global_i;
-    }
+  iterator_range<global_object_iterator> global_objects() {
+    return concat<GlobalObject>(functions(), globals());
+  iterator_range<const_global_object_iterator> global_objects() const {
+    return concat<const GlobalObject>(functions(), globals());
 
-    bool operator!=(const global_object_iterator_t &other) const {
-      return function_i != other.function_i || global_i != other.global_i;
-    }
-  };
-
-  typedef global_object_iterator_t</*IsConst=*/false> global_object_iterator;
-  typedef global_object_iterator_t</*IsConst=*/true>
-      const_global_object_iterator;
-
   global_object_iterator global_object_begin() {
-    return global_object_iterator(*this);
+    return global_objects().begin();
   }
   global_object_iterator global_object_end() {
-    return global_object_iterator(*this, 0);
+    return global_objects().end();
   }
 
   const_global_object_iterator global_object_begin() const {
-    return const_global_object_iterator(*this);
+    return global_objects().begin();
   }
   const_global_object_iterator global_object_end() const {
-    return const_global_object_iterator(*this, 0);
-  }
-
-  iterator_range<global_object_iterator> global_objects() {
-    return make_range(global_object_begin(), global_object_end());
-  }
-  iterator_range<const_global_object_iterator> global_objects() const {
-    return make_range(global_object_begin(), global_object_end());
+    return global_objects().end();
   }
 
   /// @}
   /// @name Named Metadata Iteration
   /// @{
 
   named_metadata_iterator named_metadata_begin() { return NamedMDList.begin(); }
   const_named_metadata_iterator named_metadata_begin() const {

unittests/ADT/STLExtrasTest.cpp

 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/STLExtras.h"
 #include "gtest/gtest.h"
 
+#include <list>
 #include <vector>
 
 using namespace llvm;
 
 namespace {
 
 int f(rank<0>) { return 0; }
 int f(rank<1>) { return 1; }
TEST(STLExtrasTest, CountAdaptor) {
   v.push_back(2);
   v.push_back(1);
 
   EXPECT_EQ(3, count(v, 1));
   EXPECT_EQ(2, count(v, 2));
   EXPECT_EQ(1, count(v, 3));
   EXPECT_EQ(1, count(v, 4));
 }
+
+TEST(STLExtrasTest, ConcatRange) {
+  std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
+  std::vector<int> Test;
+
+  std::vector<int> V1234 = {1, 2, 3, 4};
+  std::list<int> L56 = {5, 6};
+  SmallVector<int, 2> SV78 = {7, 8};
+
+  // Use concat across different sized ranges of different types with different
+  // iterators.
+  for (int &i : concat<int>(V1234, L56, SV78))
+    Test.push_back(i);
+  EXPECT_EQ(Expected, Test);
+
+  // Use concat between a temporary, an L-value, and an R-value to make sure
+  // complex lifetimes work well.
+  Test.clear();
+  for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))
+    Test.push_back(i);
+  EXPECT_EQ(Expected, Test);
+}
 }