common code for operation inlining

- add common code to make selecting the appropriate template function
  easier (vespa/vespalib/util/typify.h)
- enable detection of lambda functions matching all low-level
  operations. (lookup_op1, lookup_op2)
- add typifiers to decide which low-level operations should be inlined
  (TypifyOp1, TypifyOp2)
- integrate into dense_simple_join as a pilot customer

4 files changed, 231 insertions, 1 deletions

diff --git a/vespalib/CMakeLists.txt b/vespalib/CMakeLists.txt
index 2675bc16bf2..1ca9816a921 100644
--- a/vespalib/CMakeLists.txt
+++ b/vespalib/CMakeLists.txt
@@ -24,8 +24,8 @@ vespa_define_module(
     src/tests/assert
     src/tests/barrier
     src/tests/benchmark_timer
-    src/tests/btree
     src/tests/box
+    src/tests/btree
     src/tests/closure
     src/tests/component
     src/tests/compress
@@ -128,6 +128,7 @@ vespa_define_module(
     src/tests/tutorial/minimal
     src/tests/tutorial/simple
     src/tests/tutorial/threads
+    src/tests/typify
     src/tests/util/generationhandler
     src/tests/util/generationhandler_stress
     src/tests/util/md5
diff --git a/vespalib/src/tests/typify/CMakeLists.txt b/vespalib/src/tests/typify/CMakeLists.txt
new file mode 100644
index 00000000000..29e95af1988
--- /dev/null
+++ b/vespalib/src/tests/typify/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(vespalib_typify_test_app TEST
+    SOURCES
+    typify_test.cpp
+    DEPENDS
+    vespalib
+    gtest
+)
+vespa_add_test(NAME vespalib_typify_test_app COMMAND vespalib_typify_test_app)
diff --git a/vespalib/src/tests/typify/typify_test.cpp b/vespalib/src/tests/typify/typify_test.cpp
new file mode 100644
index 00000000000..4c3f1c512ca
--- /dev/null
+++ b/vespalib/src/tests/typify/typify_test.cpp
@@ -0,0 +1,124 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/util/typify.h>
+#include <vespa/vespalib/gtest/gtest.h>
+
+using namespace vespalib;
+
+struct A { static constexpr int value_from_type = 1; };
+struct B { static constexpr int value_from_type = 2; };
+
+struct MyIntA { int value; };
+struct MyIntB { int value; };
+struct MyIntC { int value; }; // no typifier for this type
+
+// MyIntA -> A or B
+struct TypifyMyIntA {
+    template <typename T> using Result = TypifyResultType<T>;
+    template <typename F> static decltype(auto) resolve(MyIntA value, F &&f) {
+        if (value.value == 1) {
+            return f(Result<A>());
+        } else if (value.value == 2) {
+            return f(Result<B>());
+        }
+        abort();
+    }
+};
+
+// MyIntB -> TypifyResultValue<int,1> or TypifyResultValue<int,2>
+struct TypifyMyIntB {
+    template <int VALUE> using Result = TypifyResultValue<int,VALUE>;
+    template <typename F> static decltype(auto) resolve(MyIntB value, F &&f) {
+        if (value.value == 1) {
+            return f(Result<1>());
+        } else if (value.value == 2) {
+            return f(Result<2>());
+        }
+        abort();
+    }
+};
+
+using TX = TypifyValue<TypifyBool, TypifyMyIntA, TypifyMyIntB>;
+
+//-----------------------------------------------------------------------------
+
+struct GetFromType {
+    template <typename T> static int invoke() { return T::value_from_type; }
+};
+
+TEST(TypifyTest, simple_type_typification_works) {
+    auto res1 = typify_invoke<1,TX,GetFromType>(MyIntA{1});
+    auto res2 = typify_invoke<1,TX,GetFromType>(MyIntA{2});
+    EXPECT_EQ(res1, 1);
+    EXPECT_EQ(res2, 2);
+}
+
+struct GetFromValue {
+    template <typename R> static int invoke() { return R::value; }
+};
+
+TEST(TypifyTest, simple_value_typification_works) {
+    auto res1 = typify_invoke<1,TX,GetFromValue>(MyIntB{1});
+    auto res2 = typify_invoke<1,TX,GetFromValue>(MyIntB{2});
+    EXPECT_EQ(res1, 1);
+    EXPECT_EQ(res2, 2);
+}
+
+struct MaybeSum {
+    template <typename F1, typename V1, typename F2, typename V2> static int invoke(MyIntC v3) {
+        int res = 0;
+        if (F1::value) {
+            res += V1::value_from_type;
+        }
+        if (F2::value) {
+            res += V2::value;
+        }
+        res += v3.value;
+        return res;
+    }
+};
+
+TEST(TypifyTest, complex_typification_works) {
+    auto res1 = typify_invoke<4,TX,MaybeSum>(false, MyIntA{2}, false, MyIntB{1}, MyIntC{4});
+    auto res2 = typify_invoke<4,TX,MaybeSum>(false, MyIntA{2},  true, MyIntB{1}, MyIntC{4});
+    auto res3 = typify_invoke<4,TX,MaybeSum>(true,  MyIntA{2}, false, MyIntB{1}, MyIntC{4});
+    auto res4 = typify_invoke<4,TX,MaybeSum>(true,  MyIntA{2},  true, MyIntB{1}, MyIntC{4});
+    EXPECT_EQ(res1, 4);
+    EXPECT_EQ(res2, 5);
+    EXPECT_EQ(res3, 6);
+    EXPECT_EQ(res4, 7);
+}
+
+struct Singleton {
+    virtual int get() const = 0;
+    virtual ~Singleton() {}
+};
+
+template <int A, int B>
+struct MySingleton : Singleton {
+    MySingleton() = default;
+    MySingleton(const MySingleton &) = delete;
+    MySingleton &operator=(const MySingleton &) = delete;
+    int get() const override { return A + B; }
+};
+
+struct GetSingleton {
+    template <typename A, typename B>
+    static const Singleton &invoke() {
+        static MySingleton<A::value, B::value> obj;
+        return obj;
+    }
+};
+
+TEST(TypifyTest, typify_invoke_can_return_object_reference) {
+    const Singleton &s1 = typify_invoke<2,TX,GetSingleton>(MyIntB{1}, MyIntB{1});
+    const Singleton &s2 = typify_invoke<2,TX,GetSingleton>(MyIntB{2}, MyIntB{2});
+    const Singleton &s3 = typify_invoke<2,TX,GetSingleton>(MyIntB{2}, MyIntB{2});
+    EXPECT_EQ(s1.get(), 2);
+    EXPECT_EQ(s2.get(), 4);
+    EXPECT_EQ(s3.get(), 4);
+    EXPECT_NE(&s1, &s2);
+    EXPECT_EQ(&s2, &s3);
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/vespalib/src/vespa/vespalib/util/typify.h b/vespalib/src/vespa/vespalib/util/typify.h
new file mode 100644
index 00000000000..0ee624a95b6
--- /dev/null
+++ b/vespalib/src/vespa/vespalib/util/typify.h
@@ -0,0 +1,96 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <stddef.h>
+#include <utility>
+
+namespace vespalib {
+
+//-----------------------------------------------------------------------------
+
+/**
+ * Typification result for values resolving into actual types.
+ **/
+template <typename T> struct TypifyResultType {
+    static constexpr bool is_type = true;
+    using type = T;
+};
+
+/**
+ * Typification result for values resolving into compile-time values
+ * which are also types as long as they are kept inside their result
+ * wrappers.
+ **/
+template <typename T, T VALUE> struct TypifyResultValue {
+    static constexpr bool is_type = false;
+    static constexpr T value = VALUE;
+};
+
+/**
+ * A Typifier is able to take a run-time value and resolve it into a
+ * type. The resolve result is passed to the specified function in the
+ * form of a thin result wrapper.
+ **/
+struct TypifyBool {
+    template <bool VALUE> using Result = TypifyResultValue<bool, VALUE>;
+    template <typename F> static decltype(auto) resolve(bool value, F &&f) {
+        if (value) {
+            return f(Result<true>());
+        } else {
+            return f(Result<false>());
+        }
+    }
+};
+
+//-----------------------------------------------------------------------------
+
+/**
+ * Template used to combine individual typifiers into a typifier able
+ * to resolve multiple types.
+ **/
+template <typename ...Ts> struct TypifyValue : Ts... { using Ts::resolve...; };
+
+//-----------------------------------------------------------------------------
+
+template <size_t N, typename Typify, typename Target, typename ...Rs> struct TypifyInvoke {
+    static decltype(auto) select() {
+        static_assert(sizeof...(Rs) == N);
+        return Target::template invoke<Rs...>();
+    }
+    template <typename T, typename ...Args> static decltype(auto) select(T &&value, Args &&...args) {
+        if constexpr (N == sizeof...(Rs)) {
+            return Target::template invoke<Rs...>(std::forward<T>(value), std::forward<Args>(args)...);
+        } else {
+            return Typify::resolve(value, [&](auto t)->decltype(auto)
+                                   {
+                                       using X = decltype(t);
+                                       if constexpr (X::is_type) {
+                                           return TypifyInvoke<N, Typify, Target, Rs..., typename X::type>::select(std::forward<Args>(args)...);
+                                       } else {
+                                           return TypifyInvoke<N, Typify, Target, Rs..., X>::select(std::forward<Args>(args)...);
+                                       }
+                                   });
+        }
+    }
+};
+
+/**
+ * Typify the N first parameters using Typify (typically an
+ * instantiation of the TypifyValue template) and forward the
+ * remaining parameters to the Target::invoke template function with
+ * the typification results from the N first parameters as template
+ * parameters. Note that typification results that are types are
+ * unwrapped before being used as template parameters while
+ * typification results that are compile-time values are kept in their
+ * wrappers when passed as template parameters. Please refer to the
+ * unit test for examples.
+ **/
+template <size_t N, typename Typify, typename Target, typename ...Args> decltype(auto) typify_invoke(Args && ...args) {
+    static_assert(N > 0);
+    return TypifyInvoke<N,Typify,Target>::select(std::forward<Args>(args)...);
+}
+
+//-----------------------------------------------------------------------------
+
+}