[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

1 files changed, 34 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/IteratorTest.cpp b/llvm/unittests/ADT/IteratorTest.cpp
index de0a6710789..902ddfb49f2 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<unsigned> pi{3, 1, 4, 1, 5, 9};
+  const vector<StringRef> e{"2", "7", "1", "8"};
+
+  {
+    // Check left range longer than right.
+    const vector<tuple<Optional<unsigned>, Optional<StringRef>>> 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<tuple<Optional<StringRef>, Optional<unsigned>>> 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<unsigned, 4> pi{3, 1, 4, 1, 5, 9};