From f57bfd3d9f2a9d659cfbab9bb196f8f183f669bf Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Wed, 5 Dec 2018 00:31:54 +0000 Subject: [PATCH] [ADT] Add zip_longest iterators. Like the already existing zip_shortest/zip_first iterators, zip_longest iterates over multiple iterators at once, but has as many iterations as the longest sequence. This means some iterators may reach the end before others do. zip_longest uses llvm::Optional's None value to mark a past-the-end value. zip_longest is not reverse-iteratable because the tuples iterated over would be different for different length sequences (IMHO for the same reason neither zip_shortest nor zip_first should be reverse-iteratable; one can still reverse the ranges individually if that's the expected behavior). In contrast to zip_shortest/zip_first, zip_longest tuples contain rvalues instead of references. This is because llvm::Optional cannot contain reference types and the value-initialized default does not have a memory location a reference could point to. The motivation for these iterators is to use C++ foreach to compare two lists of ordered attributes in D48100 (SemaOverload.cpp and ASTReaderDecl.cpp). Idea by @hfinkel. This re-commits r348301 which was reverted by r348303. The compilation error by gcc 5.4 was resolved using make_tuple in the in the initializer_list. The compileration error by msvc14 was resolved by splitting ZipLongestValueType (which already was a workaround for msvc15) into ZipLongestItemType and ZipLongestTupleType. Differential Revision: https://reviews.llvm.org/D48348 llvm-svn: 348323 --- llvm/include/llvm/ADT/STLExtras.h | 130 +++++++++++++++++++++++++++++++++++- llvm/unittests/ADT/IteratorTest.cpp | 34 ++++++++++ 2 files changed, 163 insertions(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h index ba31392..ae08472 100644 --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -508,9 +508,11 @@ make_early_inc_range(RangeT &&Range) { EarlyIncIteratorT(std::end(std::forward(Range)))); } -// forward declarations required by zip_shortest/zip_first +// forward declarations required by zip_shortest/zip_first/zip_longest template bool all_of(R &&range, UnaryPredicate P); +template +bool any_of(R &&range, UnaryPredicate P); template struct index_sequence; @@ -661,6 +663,132 @@ detail::zippy zip_first(T &&t, U &&u, std::forward(t), std::forward(u), std::forward(args)...); } +namespace detail { +template +static Iter next_or_end(const Iter &I, const Iter &End) { + if (I == End) + return End; + return std::next(I); +} + +template +static auto deref_or_none(const Iter &I, const Iter &End) + -> llvm::Optional::type>::type> { + if (I == End) + return None; + return *I; +} + +template struct ZipLongestItemType { + using type = + llvm::Optional())>::type>::type>; +}; + +template struct ZipLongestTupleType { + using type = std::tuple::type...>; +}; + +template +class zip_longest_iterator + : public iterator_facade_base< + zip_longest_iterator, + typename std::common_type< + std::forward_iterator_tag, + typename std::iterator_traits::iterator_category...>::type, + typename ZipLongestTupleType::type, + typename std::iterator_traits>::type>::difference_type, + typename ZipLongestTupleType::type *, + typename ZipLongestTupleType::type> { +public: + using value_type = typename ZipLongestTupleType::type; + +private: + std::tuple iterators; + std::tuple end_iterators; + + template + bool test(const zip_longest_iterator &other, + index_sequence) const { + return llvm::any_of( + std::initializer_list{std::get(this->iterators) != + std::get(other.iterators)...}, + identity{}); + } + + template value_type deref(index_sequence) const { + return value_type( + deref_or_none(std::get(iterators), std::get(end_iterators))...); + } + + template + decltype(iterators) tup_inc(index_sequence) const { + return std::tuple( + next_or_end(std::get(iterators), std::get(end_iterators))...); + } + +public: + zip_longest_iterator(std::pair... ts) + : iterators(std::forward(ts.first)...), + end_iterators(std::forward(ts.second)...) {} + + value_type operator*() { return deref(index_sequence_for{}); } + + value_type operator*() const { return deref(index_sequence_for{}); } + + zip_longest_iterator &operator++() { + iterators = tup_inc(index_sequence_for{}); + return *this; + } + + bool operator==(const zip_longest_iterator &other) const { + return !test(other, index_sequence_for{}); + } +}; + +template class zip_longest_range { +public: + using iterator = + zip_longest_iterator()))...>; + using iterator_category = typename iterator::iterator_category; + using value_type = typename iterator::value_type; + using difference_type = typename iterator::difference_type; + using pointer = typename iterator::pointer; + using reference = typename iterator::reference; + +private: + std::tuple ts; + + template iterator begin_impl(index_sequence) const { + return iterator(std::make_pair(adl_begin(std::get(ts)), + adl_end(std::get(ts)))...); + } + + template iterator end_impl(index_sequence) const { + return iterator(std::make_pair(adl_end(std::get(ts)), + adl_end(std::get(ts)))...); + } + +public: + zip_longest_range(Args &&... ts_) : ts(std::forward(ts_)...) {} + + iterator begin() const { return begin_impl(index_sequence_for{}); } + iterator end() const { return end_impl(index_sequence_for{}); } +}; +} // namespace detail + +/// Iterate over two or more iterators at the same time. Iteration continues +/// until all iterators reach the end. The llvm::Optional only contains a value +/// if the iterator has not reached the end. +template +detail::zip_longest_range zip_longest(T &&t, U &&u, + Args &&... args) { + return detail::zip_longest_range( + 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 diff --git a/llvm/unittests/ADT/IteratorTest.cpp b/llvm/unittests/ADT/IteratorTest.cpp index de0a671..902ddfb 100644 --- a/llvm/unittests/ADT/IteratorTest.cpp +++ b/llvm/unittests/ADT/IteratorTest.cpp @@ -328,6 +328,40 @@ TEST(ZipIteratorTest, ZipFirstBasic) { EXPECT_EQ(iters, 4u); } +TEST(ZipIteratorTest, ZipLongestBasic) { + using namespace std; + const vector pi{3, 1, 4, 1, 5, 9}; + const vector e{"2", "7", "1", "8"}; + + { + // Check left range longer than right. + const vector, Optional>> expected{ + make_tuple(3, StringRef("2")), make_tuple(1, StringRef("7")), + make_tuple(4, StringRef("1")), make_tuple(1, StringRef("8")), + make_tuple(5, None), make_tuple(9, None)}; + size_t iters = 0; + for (auto tup : zip_longest(pi, e)) { + EXPECT_EQ(tup, expected[iters]); + iters += 1; + } + EXPECT_EQ(iters, expected.size()); + } + + { + // Check right range longer than left. + const vector, Optional>> expected{ + make_tuple(StringRef("2"), 3), make_tuple(StringRef("7"), 1), + make_tuple(StringRef("1"), 4), make_tuple(StringRef("8"), 1), + make_tuple(None, 5), make_tuple(None, 9)}; + size_t iters = 0; + for (auto tup : zip_longest(e, pi)) { + EXPECT_EQ(tup, expected[iters]); + iters += 1; + } + EXPECT_EQ(iters, expected.size()); + } +} + TEST(ZipIteratorTest, Mutability) { using namespace std; const SmallVector pi{3, 1, 4, 1, 5, 9}; -- 2.7.4