From 1e976309c1774cd4d28ee70b41865c7b4875eb8f Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 25 Dec 2016 23:41:14 +0000 Subject: [PATCH] [ADT] Add a generic concatenating iterator and range (take 2). This recommits r290512 that was reverted when MSVC failed to compile it. Since then I've played with various approaches using rextester.com (where I was able to reproduce the failure) and think that I have a solution thanks in part to the help of Dave Blaikie! It seems MSVC just has a defective `decltype` in this version. Manually writing out the type seems to do the trick, even though it is .... quite complicated. Original commit message: 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. Differential Revision: https://reviews.llvm.org/D28093 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@290528 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/STLExtras.h | 146 ++++++++++++++++++++++++++++++++ include/llvm/IR/Module.h | 70 ++++----------- unittests/ADT/STLExtrasTest.cpp | 23 +++++ 3 files changed, 184 insertions(+), 55 deletions(-) diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index 4435b46f462..09483823f4b 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -31,6 +31,7 @@ #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -435,6 +436,151 @@ detail::zippy zip_first(T &&t, U &&u, std::forward(t), std::forward(u), std::forward(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 +class concat_iterator + : public iterator_facade_base, + 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...> 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 bool incrementHelper() { + auto &IterPair = std::get(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 void increment(index_sequence) { + // Build a sequence of functions to increment each iterator if possible. + bool (concat_iterator::*IncrementHelperFns[])() = { + &concat_iterator::incrementHelper...}; + + // 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 ValueT *getHelper() const { + auto &IterPair = std::get(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 ValueT &get(index_sequence) const { + // Build a sequence of functions to get from iterator if possible. + ValueT *(concat_iterator::*GetHelperFns[])() const = { + &concat_iterator::getHelper...}; + + // 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 + explicit concat_iterator(RangeTs &&... Ranges) + : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {} + + using BaseT::operator++; + concat_iterator &operator++() { + increment(index_sequence_for()); + return *this; + } + + ValueT &operator*() const { return get(index_sequence_for()); } + + 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 class concat_range { +public: + typedef concat_iterator()))...> + iterator; + +private: + std::tuple Ranges; + + template iterator begin_impl(index_sequence) { + return iterator(std::get(Ranges)...); + } + template iterator end_impl(index_sequence) { + return iterator(make_range(std::end(std::get(Ranges)), + std::end(std::get(Ranges)))...); + } + +public: + iterator begin() { return begin_impl(index_sequence_for{}); } + iterator end() { return end_impl(index_sequence_for{}); } + concat_range(RangeTs &&... Ranges) + : Ranges(std::forward(Ranges)...) {} +}; +} + +/// Concatenated range across two or more ranges. +/// +/// The desired value type must be explicitly specified. +template +detail::concat_range concat(RangeTs &&... Ranges) { + static_assert(sizeof...(RangeTs) > 1, + "Need more than one range to concatenate!"); + return detail::concat_range( + std::forward(Ranges)...); +} + //===----------------------------------------------------------------------===// // Extra additions to //===----------------------------------------------------------------------===// diff --git a/include/llvm/IR/Module.h b/include/llvm/IR/Module.h index 507a5ea4174..0f7a3ed47d4 100644 --- a/include/llvm/IR/Module.h +++ b/include/llvm/IR/Module.h @@ -590,69 +590,29 @@ public: /// @name Convenience iterators /// @{ - template class global_object_iterator_t { - friend Module; - - typename std::conditional::type - function_i, - function_e; - typename std::conditional::type global_i; - - typedef - typename std::conditional::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()) {} - - public: - global_object_iterator_t &operator++() { - if (function_i != function_e) - ++function_i; - else - ++global_i; - return *this; - } - - typename std::conditional::type & - operator*() const { - if (function_i != function_e) - return *function_i; - else - return *global_i; - } - - 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 global_object_iterator; - typedef global_object_iterator_t + typedef concat_iterator + global_object_iterator; + typedef concat_iterator const_global_object_iterator; - global_object_iterator global_object_begin() { - return global_object_iterator(*this); + iterator_range global_objects() { + return concat(functions(), globals()); } - global_object_iterator global_object_end() { - return global_object_iterator(*this, 0); + iterator_range global_objects() const { + return concat(functions(), globals()); } - const_global_object_iterator global_object_begin() const { - return const_global_object_iterator(*this); - } - const_global_object_iterator global_object_end() const { - return const_global_object_iterator(*this, 0); + global_object_iterator global_object_begin() { + return global_objects().begin(); } + global_object_iterator global_object_end() { return global_objects().end(); } - iterator_range global_objects() { - return make_range(global_object_begin(), global_object_end()); + const_global_object_iterator global_object_begin() const { + return global_objects().begin(); } - iterator_range global_objects() const { - return make_range(global_object_begin(), global_object_end()); + const_global_object_iterator global_object_end() const { + return global_objects().end(); } /// @} diff --git a/unittests/ADT/STLExtrasTest.cpp b/unittests/ADT/STLExtrasTest.cpp index 76881296db6..d3bef6a2e05 100644 --- a/unittests/ADT/STLExtrasTest.cpp +++ b/unittests/ADT/STLExtrasTest.cpp @@ -10,6 +10,7 @@ #include "llvm/ADT/STLExtras.h" #include "gtest/gtest.h" +#include #include using namespace llvm; @@ -253,4 +254,26 @@ TEST(STLExtrasTest, CountAdaptor) { EXPECT_EQ(1, count(v, 3)); EXPECT_EQ(1, count(v, 4)); } + +TEST(STLExtrasTest, ConcatRange) { + std::vector Expected = {1, 2, 3, 4, 5, 6, 7, 8}; + std::vector Test; + + std::vector V1234 = {1, 2, 3, 4}; + std::list L56 = {5, 6}; + SmallVector SV78 = {7, 8}; + + // Use concat across different sized ranges of different types with different + // iterators. + for (int &i : concat(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(std::vector(V1234), L56, std::move(SV78))) + Test.push_back(i); + EXPECT_EQ(Expected, Test); +} } -- 2.49.0