Merge pull request #11664 from vespa-engine/havardpe/overload

Havardpe/overload

7 files changed, 255 insertions, 0 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index 14c14fe85ca..9339cdacea0 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -78,6 +78,7 @@ vespa_define_module(
     src/tests/net/tls/transport_options
     src/tests/objects/nbostream
     src/tests/optimized
+    src/tests/overload
     src/tests/portal
     src/tests/portal/handle_manager
     src/tests/portal/http_request
@@ -130,6 +131,7 @@ vespa_define_module(
     src/tests/util/md5
     src/tests/util/rcuvector
     src/tests/valgrind
+    src/tests/visit_ranges
     src/tests/websocket
     src/tests/zcurve
 
diff --git a/vespalib/src/tests/overload/CMakeLists.txt b/vespalib/src/tests/overload/CMakeLists.txt
new file mode 100644
index 00000000000..67aa6230225
--- /dev/null
+++ b/vespalib/src/tests/overload/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_overload_test_app TEST
+    SOURCES
+    overload_test.cpp
+    DEPENDS
+    vespalib
+    gtest
+)
+vespa_add_test(NAME vespalib_overload_test_app COMMAND vespalib_overload_test_app)
diff --git a/vespalib/src/tests/overload/overload_test.cpp b/vespalib/src/tests/overload/overload_test.cpp
new file mode 100644
index 00000000000..ceae29ac02f
--- /dev/null
+++ b/vespalib/src/tests/overload/overload_test.cpp
@@ -0,0 +1,19 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/overload.h>
+#include <vespa/vespalib/gtest/gtest.h>
+#include <variant>
+#include <string>
+
+using namespace vespalib;
+
+TEST(OverloadTest, visit_with_overload_works) {
+    std::variant<std::string,int> a = 10;
+    std::variant<std::string,int> b = "foo";
+    std::visit(overload{[](int v){ EXPECT_EQ(v,10); },
+                        [](const std::string &){ FAIL() << "invalid visit"; }}, a);
+    std::visit(overload{[](int){ FAIL() << "invalid visit"; },
+                        [](const std::string &v){ EXPECT_EQ(v, "foo"); }}, b);
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/tests/visit_ranges/CMakeLists.txt b/vespalib/src/tests/visit_ranges/CMakeLists.txt
new file mode 100644
index 00000000000..de94b2ebb1e
--- /dev/null
+++ b/vespalib/src/tests/visit_ranges/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_visit_ranges_test_app TEST
+    SOURCES
+    visit_ranges_test.cpp
+    DEPENDS
+    vespalib
+    gtest
+)
+vespa_add_test(NAME vespalib_visit_ranges_test_app COMMAND vespalib_visit_ranges_test_app)
diff --git a/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp b/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp
new file mode 100644
index 00000000000..cb1ac9bd9c3
--- /dev/null
+++ b/vespalib/src/tests/visit_ranges/visit_ranges_test.cpp
@@ -0,0 +1,120 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/overload.h>
+#include <vespa/vespalib/util/visit_ranges.h>
+#include <vespa/vespalib/gtest/gtest.h>
+#include <variant>
+#include <string>
+
+using namespace vespalib;
+
+TEST(VisitRangeExample, set_intersection) {
+    std::vector<int> first({1,3,7});
+    std::vector<int> second({2,3,8});
+    std::vector<int> result;
+    vespalib::visit_ranges(overload{[](visit_ranges_either, int) {},
+                                    [&result](visit_ranges_both, int x, int) { result.push_back(x); }},
+                           first.begin(), first.end(), second.begin(), second.end());
+    EXPECT_EQ(result, std::vector<int>({3}));
+}
+
+TEST(VisitRangeExample, set_subtraction) {
+    std::vector<int> first({1,3,7});
+    std::vector<int> second({2,3,8});
+    std::vector<int> result;
+    vespalib::visit_ranges(overload{[&result](visit_ranges_first, int a) { result.push_back(a); },
+                                    [](visit_ranges_second, int) {},
+                                    [](visit_ranges_both, int, int) {}},
+                           first.begin(), first.end(), second.begin(), second.end());
+    EXPECT_EQ(result, std::vector<int>({1,7}));
+}
+
+TEST(VisitRangesTest, empty_ranges_can_be_visited) {
+    std::vector<int> a;
+    std::vector<int> b;
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int) {
+                           c.push_back(42);
+                       },
+                       [&c](visit_ranges_both, int, int) {
+                           c.push_back(42);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({}));
+}
+
+TEST(VisitRangesTest, simple_merge_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x);
+                           c.push_back(y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,2,3,3,7,8}));
+}
+
+TEST(VisitRangesTest, simple_union_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int) {
+                           c.push_back(x);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,2,3,7,8}));
+}
+
+TEST(VisitRangesTest, asymmetric_merge_can_be_implemented) {
+    std::vector<int> a({1,3,7});
+    std::vector<int> b({2,3,8});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_first, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_second, int) {},
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x * y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end());
+    EXPECT_EQ(c, std::vector<int>({1,9,7}));
+}
+
+TEST(VisitRangesTest, comparator_can_be_specified) {
+    std::vector<int> a({7,3,1});
+    std::vector<int> b({8,3,2});
+    std::vector<int> c;
+    auto visitor = overload
+                   {
+                       [&c](visit_ranges_either, int x) {
+                           c.push_back(x);
+                       },
+                       [&c](visit_ranges_both, int x, int y) {
+                           c.push_back(x);
+                           c.push_back(y);
+                       }
+                   };
+    vespalib::visit_ranges(visitor, a.begin(), a.end(), b.begin(), b.end(), std::greater<>());
+    EXPECT_EQ(c, std::vector<int>({8,7,3,3,2,1}));
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/overload.h b/vespalib/src/vespa/vespalib/util/overload.h
new file mode 100644
index 00000000000..d5af9dee2d3
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/overload.h
@@ -0,0 +1,15 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+namespace vespalib {
+
+/**
+ * Simple overload lambda composition class. To be replaced by
+ * standard overload functionality when available. (C++20)
+ **/
+
+template<class... Ts> struct overload : Ts... { using Ts::operator()...; };
+template<class... Ts> overload(Ts...) -> overload<Ts...>;
+
+}
diff --git a/vespalib/src/vespa/vespalib/util/visit_ranges.h b/vespalib/src/vespa/vespalib/util/visit_ranges.h
new file mode 100644
index 00000000000..9cf1112fe0d
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/visit_ranges.h
@@ -0,0 +1,81 @@
+// Copyright 2020 Oath Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <functional>
+
+namespace vespalib {
+
+struct visit_ranges_either {};
+struct visit_ranges_first : visit_ranges_either {};
+struct visit_ranges_second : visit_ranges_either {};
+struct visit_ranges_both {};
+
+/**
+ * Visit elements from two distinct ranges in the order defined by the
+ * given comparator. The comparator must define a strict-weak ordering
+ * across all elements from both ranges and each range must already be
+ * sorted according to the comparator before calling this
+ * function. Pairs of elements from the two ranges (one from each)
+ * that are equal according to the comparator will be visited by a
+ * single callback. The different cases ('from the first range', 'from
+ * the second range' and 'from both ranges') are indicated by using
+ * tagged dispatch in the visitation callback.
+ *
+ * An example treating both inputs equally:
+ * <pre>
+ *   TEST(VisitRangeExample, set_intersection) {
+ *       std::vector<int> first({1,3,7});
+ *       std::vector<int> second({2,3,8});
+ *       std::vector<int> result;
+ *       vespalib::visit_ranges(overload{[](visit_ranges_either, int) {},
+ *                                       [&result](visit_ranges_both, int x, int) { result.push_back(x); }},
+ *                              first.begin(), first.end(), second.begin(), second.end());
+ *       EXPECT_EQ(result, std::vector<int>({3}));
+ *   }
+ * </pre>
+ *
+ * An example treating the inputs differently:
+ * <pre>
+ *   TEST(VisitRangeExample, set_subtraction) {
+ *       std::vector<int> first({1,3,7});
+ *       std::vector<int> second({2,3,8});
+ *       std::vector<int> result;
+ *       vespalib::visit_ranges(overload{[&result](visit_ranges_first, int a) { result.push_back(a); },
+ *                                       [](visit_ranges_second, int) {},
+ *                                       [](visit_ranges_both, int, int) {}},
+ *                              first.begin(), first.end(), second.begin(), second.end());
+ *       EXPECT_EQ(result, std::vector<int>({1,7}));
+ *   }
+ * </pre>
+ *
+ * The intention of this function is to simplify the implementation of
+ * merge-like operations.
+ **/
+
+template <typename V, typename ItA, typename ItB, typename Cmp = std::less<> >
+void visit_ranges(V &&visitor, ItA pos_a, ItA end_a, ItB pos_b, ItB end_b, Cmp cmp = Cmp()) {
+    while ((pos_a != end_a) && (pos_b != end_b)) {
+        if (cmp(*pos_a, *pos_b)) {
+            visitor(visit_ranges_first(), *pos_a);
+            ++pos_a;
+        } else if (cmp(*pos_b, *pos_a)) {
+            visitor(visit_ranges_second(), *pos_b);
+            ++pos_b;
+        } else {
+            visitor(visit_ranges_both(), *pos_a, *pos_b);
+            ++pos_a;
+            ++pos_b;
+        }
+    }
+    while (pos_a != end_a) {
+        visitor(visit_ranges_first(), *pos_a);
+        ++pos_a;
+    }
+    while (pos_b != end_b) {
+        visitor(visit_ranges_second(), *pos_b);
+        ++pos_b;
+    }
+}
+
+}