AK: Add a Variant<Ts...> implementation

Also adds an AK::Empty struct, because 'empty' variants are useful, but
this implementation leaves that to the user (i.e. a variant cannot
actually be empty, but it can contain an instance of Empty - i.e. a
byte).
Note that this is more of a constrained Any type, but they basically do
the same things anyway :^)

3 files changed, 397 insertions, 0 deletions

diff --git a/AK/Tests/CMakeLists.txt b/AK/Tests/CMakeLists.txt
index 07fea34753..ff0d6b0119 100644
--- a/AK/Tests/CMakeLists.txt
+++ b/AK/Tests/CMakeLists.txt
@@ -56,6 +56,7 @@ set(AK_TEST_SOURCES
     TestTypedTransfer.cpp
     TestURL.cpp
     TestUtf8.cpp
+    TestVariant.cpp
     TestVector.cpp
     TestWeakPtr.cpp
 )
diff --git a/AK/Tests/TestVariant.cpp b/AK/Tests/TestVariant.cpp
new file mode 100644
index 0000000000..769cde605a
--- /dev/null
+++ b/AK/Tests/TestVariant.cpp
@@ -0,0 +1,112 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenity.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestSuite.h>
+
+#include <AK/Variant.h>
+
+TEST_CASE(basic)
+{
+    Variant<int, String> the_value { 42 };
+    EXPECT(the_value.has<int>());
+    EXPECT_EQ(the_value.get<int>(), 42);
+    the_value = String("42");
+    EXPECT(the_value.has<String>());
+    EXPECT_EQ(the_value.get<String>(), "42");
+}
+
+TEST_CASE(visit)
+{
+    bool correct = false;
+    Variant<int, String, float> the_value { 42.0f };
+    the_value.visit(
+        [&](const int&) { correct = false; },
+        [&](const String&) { correct = false; },
+        [&](const float&) { correct = true; });
+    EXPECT(correct);
+}
+
+TEST_CASE(destructor)
+{
+    struct DestructionChecker {
+        explicit DestructionChecker(bool& was_destroyed)
+            : m_was_destroyed(was_destroyed)
+        {
+        }
+
+        ~DestructionChecker()
+        {
+            m_was_destroyed = true;
+        }
+        bool& m_was_destroyed;
+    };
+
+    bool was_destroyed = false;
+    {
+        Variant<DestructionChecker> test_variant { DestructionChecker { was_destroyed } };
+    }
+    EXPECT(was_destroyed);
+}
+
+TEST_CASE(move_moves)
+{
+    struct NoCopy {
+        AK_MAKE_NONCOPYABLE(NoCopy);
+
+    public:
+        NoCopy() = default;
+        NoCopy(NoCopy&&) = default;
+    };
+
+    Variant<NoCopy, int> first_variant { 42 };
+    // Should not fail to compile
+    first_variant = NoCopy {};
+
+    Variant<NoCopy, int> second_variant = move(first_variant);
+    EXPECT(second_variant.has<NoCopy>());
+}
+
+TEST_CASE(downcast)
+{
+    Variant<i8, i16, i32, i64> one_integer_to_rule_them_all { static_cast<i32>(42) };
+    auto fake_integer = one_integer_to_rule_them_all.downcast<i8, i32>();
+    EXPECT(fake_integer.has<i32>());
+    EXPECT(one_integer_to_rule_them_all.has<i32>());
+    EXPECT_EQ(fake_integer.get<i32>(), 42);
+    EXPECT_EQ(one_integer_to_rule_them_all.get<i32>(), 42);
+
+    fake_integer = static_cast<i8>(60);
+    one_integer_to_rule_them_all = fake_integer.downcast<i8, i16>().downcast<i8, i32, float>().downcast<i8, i16, i32, i64>();
+    EXPECT(fake_integer.has<i8>());
+    EXPECT(one_integer_to_rule_them_all.has<i8>());
+    EXPECT_EQ(fake_integer.get<i8>(), 60);
+    EXPECT_EQ(one_integer_to_rule_them_all.get<i8>(), 60);
+}
+
+TEST_CASE(moved_from_state)
+{
+    // Note: This test requires that Vector's moved-from state be consistent
+    //       it need not be in a specific state (though as it is currently implemented,
+    //       a moved-from vector is the same as a newly-created vector)
+    //       This test does not make assumptions about the state itself, but rather that
+    //       it remains consistent when done on different instances.
+    //       Should this assumption be broken, we should probably switch to defining a local
+    //       class that has fixed semantics, but I doubt the moved-from state of Vector will
+    //       change any time soon :P
+    Vector<i32> bunch_of_values { 1, 2, 3, 4, 5, 6, 7, 8 };
+    Variant<Vector<i32>, Empty> optionally_a_bunch_of_values { Vector<i32> { 1, 2, 3, 4, 5, 6, 7, 8 } };
+
+    {
+        [[maybe_unused]] auto devnull_0 = move(bunch_of_values);
+        [[maybe_unused]] auto devnull_1 = move(optionally_a_bunch_of_values);
+    }
+
+    // The moved-from state should be the same in both cases, and the variant should still contain a moved-from vector.
+    // Note: Use after move is intentional.
+    EXPECT(optionally_a_bunch_of_values.has<Vector<i32>>());
+    auto same_contents = __builtin_memcmp(&bunch_of_values, &optionally_a_bunch_of_values.get<Vector<i32>>(), sizeof(bunch_of_values)) == 0;
+    EXPECT(same_contents);
+}
diff --git a/AK/Variant.h b/AK/Variant.h
new file mode 100644
index 0000000000..87d3089c73
--- /dev/null
+++ b/AK/Variant.h
@@ -0,0 +1,284 @@
+/*
+ * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+#include <AK/Array.h>
+#include <AK/BitCast.h>
+#include <AK/StdLibExtras.h>
+#include <typeinfo>
+
+namespace AK::Detail {
+
+template<typename... Ts>
+struct Variant;
+
+template<typename F, typename... Ts>
+struct Variant<F, Ts...> {
+    static void delete_(const std::type_info& id, void* data)
+    {
+        if (id == typeid(F))
+            bit_cast<F*>(data)->~F();
+        else
+            Variant<Ts...>::delete_(id, data);
+    }
+
+    static void move_(const std::type_info& old_id, void* old_data, void* new_data)
+    {
+        if (old_id == typeid(F))
+            new (new_data) F(move(*bit_cast<F*>(old_data)));
+        else
+            Variant<Ts...>::move_(old_id, old_data, new_data);
+    }
+
+    static void copy_(const std::type_info& old_id, const void* old_data, void* new_data)
+    {
+        if (old_id == typeid(F))
+            new (new_data) F(*bit_cast<F*>(old_data));
+        else
+            Variant<Ts...>::copy_(old_id, old_data, new_data);
+    }
+
+    template<typename Visitor>
+    static void visit_(const std::type_info& id, void* data, Visitor&& visitor)
+    {
+        if (id == typeid(F))
+            visitor(*bit_cast<F*>(data));
+        else
+            Variant<Ts...>::visit_(id, data, forward<Visitor>(visitor));
+    }
+
+    template<typename Visitor>
+    static void visit_(const std::type_info& id, const void* data, Visitor&& visitor)
+    {
+        if (id == typeid(F))
+            visitor(*bit_cast<const F*>(data));
+        else
+            Variant<Ts...>::visit_(id, data, forward<Visitor>(visitor));
+    }
+};
+
+template<>
+struct Variant<> {
+    static void delete_(const std::type_info&, void*) { }
+    static void move_(const std::type_info&, void*, void*) { }
+    static void copy_(const std::type_info&, const void*, void*) { }
+    template<typename Visitor>
+    static void visit_(const std::type_info&, void*, Visitor&&) { }
+    template<typename Visitor>
+    static void visit_(const std::type_info&, const void*, Visitor&&) { }
+};
+
+struct VariantNoClearTag {
+    explicit VariantNoClearTag() = default;
+};
+
+template<typename T, typename Base>
+struct VariantConstructors {
+    VariantConstructors(T&& t)
+    {
+        internal_cast().template set<T>(forward<T>(t), VariantNoClearTag {});
+    }
+
+    VariantConstructors() { }
+
+    Base& operator=(const T& value)
+    {
+        Base variant { value };
+        internal_cast() = move(variant);
+        return internal_cast();
+    }
+
+    Base& operator=(T&& value)
+    {
+        Base variant { move(value) };
+        internal_cast() = move(variant);
+        return internal_cast();
+    }
+
+private:
+    [[nodiscard]] Base& internal_cast()
+    {
+        // Warning: Internal type shenanigans - VariantsConstrutors<T, Base> <- Base
+        //          Not the other way around, so be _really_ careful not to cause issues.
+        return *reinterpret_cast<Base*>(this);
+    }
+};
+
+}
+
+namespace AK {
+
+struct Empty {
+};
+
+template<typename... Ts>
+struct Variant
+    : public Detail::VariantConstructors<Ts, Variant<Ts...>>... {
+
+    template<typename... NewTs>
+    friend struct Variant;
+
+    Variant(const Variant& old)
+        : Detail::VariantConstructors<Ts, Variant<Ts...>>()...
+        , m_type_info(old.m_type_info)
+    {
+        Helper::copy_(*old.m_type_info, old.m_data, m_data);
+    }
+
+    // Note: A moved-from variant emulates the state of the object it contains
+    //       so if a variant containing an int is moved from, it will still contain that int
+    //       and if a variant with a nontrivial move ctor is moved from, it may or may not be valid
+    //       but it will still contain the "moved-from" state of the object it previously contained.
+    Variant(Variant&& old)
+        : Detail::VariantConstructors<Ts, Variant<Ts...>>()...
+        , m_type_info(old.m_type_info)
+    {
+        Helper::move_(*old.m_type_info, old.m_data, m_data);
+    }
+
+    ~Variant()
+    {
+        Helper::delete_(*m_type_info, m_data);
+    }
+
+    Variant& operator=(const Variant& other)
+    {
+        m_type_info = other.m_type_info;
+        Helper::copy_(*other.m_type_info, other.m_data, m_data);
+        return *this;
+    }
+
+    Variant& operator=(Variant&& other)
+    {
+        m_type_info = other.m_type_info;
+        Helper::move_(*other.m_type_info, other.m_data, m_data);
+        return *this;
+    }
+
+    using Detail::VariantConstructors<Ts, Variant<Ts...>>::VariantConstructors...;
+
+    template<typename T>
+    void set(T&& t)
+    {
+        Helper::delete_(*m_type_info, m_data);
+        new (m_data) T(forward<T>(t));
+        m_type_info = &typeid(T);
+    }
+
+    template<typename T>
+    void set(T&& t, Detail::VariantNoClearTag)
+    {
+        new (m_data) T(forward<T>(t));
+        m_type_info = &typeid(T);
+    }
+
+    template<typename T>
+    T* get_pointer()
+    {
+        if (typeid(T) == *m_type_info)
+            return reinterpret_cast<T*>(m_data);
+        return nullptr;
+    }
+
+    template<typename T>
+    T& get()
+    {
+        VERIFY(typeid(T) == *m_type_info);
+        return *reinterpret_cast<T*>(m_data);
+    }
+
+    template<typename T>
+    const T* get_pointer() const
+    {
+        if (typeid(T) == *m_type_info)
+            return reinterpret_cast<const T*>(m_data);
+        return nullptr;
+    }
+
+    template<typename T>
+    const T& get() const
+    {
+        VERIFY(typeid(T) == *m_type_info);
+        return *reinterpret_cast<const T*>(m_data);
+    }
+
+    template<typename T>
+    [[nodiscard]] bool has() const
+    {
+        return typeid(T) == *m_type_info;
+    }
+
+    template<typename... Fs>
+    void visit(Fs&&... functions)
+    {
+        Visitor<Fs...> visitor { forward<Fs>(functions)... };
+        Helper::visit_(*m_type_info, m_data, visitor);
+    }
+
+    template<typename... Fs>
+    void visit(Fs&&... functions) const
+    {
+        Visitor<Fs...> visitor { forward<Fs>(functions)... };
+        Helper::visit_(*m_type_info, m_data, visitor);
+    }
+
+    template<typename... NewTs>
+    Variant<NewTs...> downcast() &&
+    {
+        VERIFY(covers<NewTs...>());
+        Variant<NewTs...> instance { m_type_info };
+        Helper::move_(*m_type_info, m_data, instance.m_data);
+        return instance;
+    }
+
+    template<typename... NewTs>
+    Variant<NewTs...> downcast() &
+    {
+        VERIFY(covers<NewTs...>());
+        Variant<NewTs...> instance { m_type_info };
+        Helper::copy_(*m_type_info, m_data, instance.m_data);
+        return instance;
+    }
+
+private:
+    static constexpr auto data_size = integer_sequence_generate_array<size_t>(0, IntegerSequence<size_t, sizeof(Ts)...>()).max();
+    static constexpr auto data_alignment = integer_sequence_generate_array<size_t>(0, IntegerSequence<size_t, alignof(Ts)...>()).max();
+    using Helper = Detail::Variant<Ts...>;
+
+    template<typename... NewTs>
+    bool covers() const
+    {
+        return ((typeid(NewTs) == *m_type_info) || ...);
+    }
+
+    explicit Variant(const std::type_info* type_info)
+        : Detail::VariantConstructors<Ts, Variant<Ts...>>()...
+        , m_type_info(type_info)
+    {
+    }
+
+    template<typename... Fs>
+    struct Visitor : Fs... {
+        Visitor(Fs&&... args)
+            : Fs(args)...
+        {
+        }
+
+        using Fs::operator()...;
+    };
+
+    alignas(data_alignment) u8 m_data[data_size];
+    // Note: Make sure not to default-initialize!
+    //       VariantConstructors::VariantConstructors(T) will set this to the correct value
+    //       So default-constructing to anything will leave the first initialization with that value instead of the correct one.
+    const std::type_info* m_type_info;
+};
+
+}
+
+using AK::Empty;
+using AK::Variant;