AK: Make Vector capable of holding reference types

This commit makes it possible to instantiate `Vector<T&>` and use it
to store references to `T` in a vector.
All non-pointer observers are made to return the reference, and the
pointer observers simply yield the underlying pointer.
Note that the 'find_*' methods act on the values and not the pointers
that are stored in the vector.
This commit also makes errors in various vector methods much more
readable by directly using requires-clauses on them.
And finally, it should be noted that Vector cannot hold temporaries :^)

1 files changed, 149 insertions, 91 deletions

diff --git a/AK/Vector.h b/AK/Vector.h
index d3dd2a3466..a6fb9150fe 100644
--- a/AK/Vector.h
+++ b/AK/Vector.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2021, the SerenityOS developers.
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -30,18 +31,42 @@
 
 namespace AK {
 
+namespace Detail {
+
+template<typename StorageType, bool>
+struct CanBePlacedInsideVectorHelper;
+
+template<typename StorageType>
+struct CanBePlacedInsideVectorHelper<StorageType, true> {
+    template<typename U>
+    static constexpr bool value = requires(U&& u) { StorageType { &u }; };
+};
+
+template<typename StorageType>
+struct CanBePlacedInsideVectorHelper<StorageType, false> {
+    template<typename U>
+    static constexpr bool value = requires(U&& u) { StorageType(forward<U>(u)); };
+};
+}
+
 template<typename T, size_t inline_capacity>
-class Vector {
+requires(!IsRvalueReference<T>) class Vector {
+private:
+    static constexpr bool contains_reference = IsLvalueReference<T>;
+    using StorageType = Conditional<contains_reference, RawPtr<RemoveReference<T>>, T>;
+
+    template<typename U>
+    static constexpr bool CanBePlacedInsideVector = Detail::CanBePlacedInsideVectorHelper<StorageType, contains_reference>::template value<U>;
+
 public:
     using ValueType = T;
-
     Vector()
         : m_capacity(inline_capacity)
     {
     }
 
 #ifndef SERENITY_LIBC_BUILD
-    Vector(std::initializer_list<T> list)
+    Vector(std::initializer_list<T> list) requires(!IsLvalueReference<T>)
     {
         ensure_capacity(list.size());
         for (auto& item : list)
@@ -57,8 +82,8 @@ public:
         if constexpr (inline_capacity > 0) {
             if (!m_outline_buffer) {
                 for (size_t i = 0; i < m_size; ++i) {
-                    new (&inline_buffer()[i]) T(move(other.inline_buffer()[i]));
-                    other.inline_buffer()[i].~T();
+                    new (&inline_buffer()[i]) StorageType(move(other.inline_buffer()[i]));
+                    other.inline_buffer()[i].~StorageType();
                 }
             }
         }
@@ -70,7 +95,7 @@ public:
     Vector(Vector const& other)
     {
         ensure_capacity(other.size());
-        TypedTransfer<T>::copy(data(), other.data(), other.size());
+        TypedTransfer<StorageType>::copy(data(), other.data(), other.size());
         m_size = other.size();
     }
 
@@ -78,7 +103,7 @@ public:
     Vector(Vector<T, other_inline_capacity> const& other)
     {
         ensure_capacity(other.size());
-        TypedTransfer<T>::copy(data(), other.data(), other.size());
+        TypedTransfer<StorageType>::copy(data(), other.data(), other.size());
         m_size = other.size();
     }
 
@@ -87,24 +112,24 @@ public:
         clear();
     }
 
-    Span<T> span() { return { data(), size() }; }
-    Span<T const> span() const { return { data(), size() }; }
+    Span<StorageType> span() { return { data(), size() }; }
+    Span<StorageType const> span() const { return { data(), size() }; }
 
-    operator Span<T>() { return span(); }
-    operator Span<T const>() const { return span(); }
+    operator Span<StorageType>() { return span(); }
+    operator Span<StorageType const>() const { return span(); }
 
     bool is_empty() const { return size() == 0; }
     ALWAYS_INLINE size_t size() const { return m_size; }
     size_t capacity() const { return m_capacity; }
 
-    T* data()
+    StorageType* data()
     {
         if constexpr (inline_capacity > 0)
             return m_outline_buffer ? m_outline_buffer : inline_buffer();
         return m_outline_buffer;
     }
 
-    T const* data() const
+    StorageType const* data() const
     {
         if constexpr (inline_capacity > 0)
             return m_outline_buffer ? m_outline_buffer : inline_buffer();
@@ -114,13 +139,19 @@ public:
     ALWAYS_INLINE T const& at(size_t i) const
     {
         VERIFY(i < m_size);
-        return data()[i];
+        if constexpr (contains_reference)
+            return *data()[i];
+        else
+            return data()[i];
     }
 
     ALWAYS_INLINE T& at(size_t i)
     {
         VERIFY(i < m_size);
-        return data()[i];
+        if constexpr (contains_reference)
+            return *data()[i];
+        else
+            return data()[i];
     }
 
     ALWAYS_INLINE T const& operator[](size_t i) const { return at(i); }
@@ -159,7 +190,7 @@ public:
     {
         if (m_size != other.size())
             return false;
-        return TypedTransfer<T>::compare(data(), other.data(), size());
+        return TypedTransfer<StorageType>::compare(data(), other.data(), size());
     }
 
     bool contains_slow(T const& value) const
@@ -183,14 +214,14 @@ public:
     }
 
     template<typename U = T>
-    void insert(size_t index, U&& value)
+    void insert(size_t index, U&& value) requires(CanBePlacedInsideVector<U>)
     {
         auto did_allocate = try_insert<U>(index, forward<U>(value));
         VERIFY(did_allocate);
     }
 
     template<typename C, typename U = T>
-    void insert_before_matching(U&& value, C callback, size_t first_index = 0, size_t* inserted_index = nullptr)
+    void insert_before_matching(U&& value, C callback, size_t first_index = 0, size_t* inserted_index = nullptr) requires(CanBePlacedInsideVector<U>)
     {
         auto did_allocate = try_insert_before_matching(forward<U>(value), callback, first_index, inserted_index);
         VERIFY(did_allocate);
@@ -210,39 +241,46 @@ public:
 
     ALWAYS_INLINE void append(T&& value)
     {
-        auto did_allocate = try_append(move(value));
+        bool did_allocate;
+        if constexpr (contains_reference)
+            did_allocate = try_append(value);
+        else
+            did_allocate = try_append(move(value));
         VERIFY(did_allocate);
     }
 
-    ALWAYS_INLINE void append(T const& value)
+    ALWAYS_INLINE void append(T const& value) requires(!contains_reference)
     {
         auto did_allocate = try_append(T(value));
         VERIFY(did_allocate);
     }
 
-    void append(T const* values, size_t count)
+    void append(StorageType const* values, size_t count)
     {
         auto did_allocate = try_append(values, count);
         VERIFY(did_allocate);
     }
 
     template<typename U = T>
-    ALWAYS_INLINE void unchecked_append(U&& value)
+    ALWAYS_INLINE void unchecked_append(U&& value) requires(CanBePlacedInsideVector<U>)
     {
         VERIFY((size() + 1) <= capacity());
-        new (slot(m_size)) T(forward<U>(value));
+        if constexpr (contains_reference)
+            new (slot(m_size)) StorageType(&value);
+        else
+            new (slot(m_size)) StorageType(forward<U>(value));
         ++m_size;
     }
 
     template<class... Args>
-    void empend(Args&&... args)
+    void empend(Args&&... args) requires(!contains_reference)
     {
         auto did_allocate = try_empend(forward<Args>(args)...);
         VERIFY(did_allocate);
     }
 
     template<typename U = T>
-    void prepend(U&& value)
+    void prepend(U&& value) requires(CanBePlacedInsideVector<U>)
     {
         auto did_allocate = try_insert(0, forward<U>(value));
         VERIFY(did_allocate);
@@ -254,7 +292,7 @@ public:
         VERIFY(did_allocate);
     }
 
-    void prepend(T const* values, size_t count)
+    void prepend(StorageType const* values, size_t count)
     {
         auto did_allocate = try_prepend(values, count);
         VERIFY(did_allocate);
@@ -271,8 +309,8 @@ public:
             if constexpr (inline_capacity > 0) {
                 if (!m_outline_buffer) {
                     for (size_t i = 0; i < m_size; ++i) {
-                        new (&inline_buffer()[i]) T(move(other.inline_buffer()[i]));
-                        other.inline_buffer()[i].~T();
+                        new (&inline_buffer()[i]) StorageType(move(other.inline_buffer()[i]));
+                        other.inline_buffer()[i].~StorageType();
                     }
                 }
             }
@@ -288,7 +326,7 @@ public:
         if (this != &other) {
             clear();
             ensure_capacity(other.size());
-            TypedTransfer<T>::copy(data(), other.data(), other.size());
+            TypedTransfer<StorageType>::copy(data(), other.data(), other.size());
             m_size = other.size();
         }
         return *this;
@@ -299,7 +337,7 @@ public:
     {
         clear();
         ensure_capacity(other.size());
-        TypedTransfer<T>::copy(data(), other.data(), other.size());
+        TypedTransfer<StorageType>::copy(data(), other.data(), other.size());
         m_size = other.size();
         return *this;
     }
@@ -317,7 +355,7 @@ public:
     void clear_with_capacity()
     {
         for (size_t i = 0; i < m_size; ++i)
-            data()[i].~T();
+            data()[i].~StorageType();
         m_size = 0;
     }
 
@@ -325,13 +363,13 @@ public:
     {
         VERIFY(index < m_size);
 
-        if constexpr (Traits<T>::is_trivial()) {
-            TypedTransfer<T>::copy(slot(index), slot(index + 1), m_size - index - 1);
+        if constexpr (Traits<StorageType>::is_trivial()) {
+            TypedTransfer<StorageType>::copy(slot(index), slot(index + 1), m_size - index - 1);
         } else {
-            at(index).~T();
+            at(index).~StorageType();
             for (size_t i = index + 1; i < m_size; ++i) {
-                new (slot(i - 1)) T(move(at(i)));
-                at(i).~T();
+                new (slot(i - 1)) StorageType(move(at(i)));
+                at(i).~StorageType();
             }
         }
 
@@ -345,14 +383,14 @@ public:
         VERIFY(index + count > index);
         VERIFY(index + count <= m_size);
 
-        if constexpr (Traits<T>::is_trivial()) {
-            TypedTransfer<T>::copy(slot(index), slot(index + count), m_size - index - count);
+        if constexpr (Traits<StorageType>::is_trivial()) {
+            TypedTransfer<StorageType>::copy(slot(index), slot(index + count), m_size - index - count);
         } else {
             for (size_t i = index; i < index + count; i++)
-                at(i).~T();
+                at(i).~StorageType();
             for (size_t i = index + count; i < m_size; ++i) {
-                new (slot(i - count)) T(move(at(i)));
-                at(i).~T();
+                new (slot(i - count)) StorageType(move(at(i)));
+                at(i).~StorageType();
             }
         }
 
@@ -386,36 +424,46 @@ public:
     T take_last()
     {
         VERIFY(!is_empty());
-        T value = move(last());
-        last().~T();
+        auto value = move(raw_last());
+        if constexpr (!contains_reference)
+            last().~T();
         --m_size;
-        return value;
+        if constexpr (contains_reference)
+            return *value;
+        else
+            return value;
     }
 
     T take_first()
     {
         VERIFY(!is_empty());
-        T value = move(first());
+        auto value = move(raw_first());
         remove(0);
-        return value;
+        if constexpr (contains_reference)
+            return *value;
+        else
+            return value;
     }
 
     T take(size_t index)
     {
-        T value = move(at(index));
+        auto value = move(raw_at(index));
         remove(index);
-        return value;
+        if constexpr (contains_reference)
+            return *value;
+        else
+            return value;
     }
 
     T unstable_take(size_t index)
     {
         VERIFY(index < m_size);
-        swap(at(index), at(m_size - 1));
+        swap(raw_at(index), raw_at(m_size - 1));
         return take_last();
     }
 
     template<typename U = T>
-    [[nodiscard]] bool try_insert(size_t index, U&& value)
+    [[nodiscard]] bool try_insert(size_t index, U&& value) requires(CanBePlacedInsideVector<U>)
     {
         if (index > size())
             return false;
@@ -424,20 +472,23 @@ public:
         if (!try_grow_capacity(size() + 1))
             return false;
         ++m_size;
-        if constexpr (Traits<T>::is_trivial()) {
-            TypedTransfer<T>::move(slot(index + 1), slot(index), m_size - index - 1);
+        if constexpr (Traits<StorageType>::is_trivial()) {
+            TypedTransfer<StorageType>::move(slot(index + 1), slot(index), m_size - index - 1);
         } else {
             for (size_t i = size() - 1; i > index; --i) {
-                new (slot(i)) T(move(at(i - 1)));
-                at(i - 1).~T();
+                new (slot(i)) StorageType(move(at(i - 1)));
+                at(i - 1).~StorageType();
             }
         }
-        new (slot(index)) T(forward<U>(value));
+        if constexpr (contains_reference)
+            new (slot(index)) StorageType(&value);
+        else
+            new (slot(index)) StorageType(forward<U>(value));
         return true;
     }
 
     template<typename C, typename U = T>
-    [[nodiscard]] bool try_insert_before_matching(U&& value, C callback, size_t first_index = 0, size_t* inserted_index = nullptr)
+    [[nodiscard]] bool try_insert_before_matching(U&& value, C callback, size_t first_index = 0, size_t* inserted_index = nullptr) requires(CanBePlacedInsideVector<U>)
     {
         for (size_t i = first_index; i < size(); ++i) {
             if (callback(at(i))) {
@@ -465,7 +516,7 @@ public:
         Vector tmp = move(other);
         if (!try_grow_capacity(size() + other_size))
             return false;
-        TypedTransfer<T>::move(data() + m_size, tmp.data(), other_size);
+        TypedTransfer<StorageType>::move(data() + m_size, tmp.data(), other_size);
         m_size += other_size;
         return true;
     }
@@ -474,7 +525,7 @@ public:
     {
         if (!try_grow_capacity(size() + other.size()))
             return false;
-        TypedTransfer<T>::copy(data() + m_size, other.data(), other.size());
+        TypedTransfer<StorageType>::copy(data() + m_size, other.data(), other.size());
         m_size += other.m_size;
         return true;
     }
@@ -483,39 +534,42 @@ public:
     {
         if (!try_grow_capacity(size() + 1))
             return false;
-        new (slot(m_size)) T(move(value));
+        if constexpr (contains_reference)
+            new (slot(m_size)) StorageType(&value);
+        else
+            new (slot(m_size)) StorageType(move(value));
         ++m_size;
         return true;
     }
 
-    [[nodiscard]] ALWAYS_INLINE bool try_append(T const& value)
+    [[nodiscard]] ALWAYS_INLINE bool try_append(T const& value) requires(!contains_reference)
     {
         return try_append(T(value));
     }
 
-    [[nodiscard]] bool try_append(T const* values, size_t count)
+    [[nodiscard]] bool try_append(StorageType const* values, size_t count)
     {
         if (!count)
             return true;
         if (!try_grow_capacity(size() + count))
             return false;
-        TypedTransfer<T>::copy(slot(m_size), values, count);
+        TypedTransfer<StorageType>::copy(slot(m_size), values, count);
         m_size += count;
         return true;
     }
 
     template<class... Args>
-    [[nodiscard]] bool try_empend(Args&&... args)
+    [[nodiscard]] bool try_empend(Args&&... args) requires(!contains_reference)
     {
         if (!try_grow_capacity(m_size + 1))
             return false;
-        new (slot(m_size)) T { forward<Args>(args)... };
+        new (slot(m_size)) StorageType { forward<Args>(args)... };
         ++m_size;
         return true;
     }
 
     template<typename U = T>
-    [[nodiscard]] bool try_prepend(U&& value)
+    [[nodiscard]] bool try_prepend(U&& value) requires(CanBePlacedInsideVector<U>)
     {
         return try_insert(0, forward<U>(value));
     }
@@ -535,24 +589,24 @@ public:
             return false;
 
         for (size_t i = size() + other_size - 1; i >= other.size(); --i) {
-            new (slot(i)) T(move(at(i - other_size)));
-            at(i - other_size).~T();
+            new (slot(i)) StorageType(move(at(i - other_size)));
+            at(i - other_size).~StorageType();
         }
 
         Vector tmp = move(other);
-        TypedTransfer<T>::move(slot(0), tmp.data(), tmp.size());
+        TypedTransfer<StorageType>::move(slot(0), tmp.data(), tmp.size());
         m_size += other_size;
         return true;
     }
 
-    [[nodiscard]] bool try_prepend(T const* values, size_t count)
+    [[nodiscard]] bool try_prepend(StorageType const* values, size_t count)
     {
         if (!count)
             return true;
         if (!try_grow_capacity(size() + count))
             return false;
-        TypedTransfer<T>::move(slot(count), slot(0), m_size);
-        TypedTransfer<T>::copy(slot(0), values, count);
+        TypedTransfer<StorageType>::move(slot(count), slot(0), m_size);
+        TypedTransfer<StorageType>::copy(slot(0), values, count);
         m_size += count;
         return true;
     }
@@ -568,17 +622,17 @@ public:
     {
         if (m_capacity >= needed_capacity)
             return true;
-        size_t new_capacity = kmalloc_good_size(needed_capacity * sizeof(T)) / sizeof(T);
-        auto* new_buffer = (T*)kmalloc(new_capacity * sizeof(T));
+        size_t new_capacity = kmalloc_good_size(needed_capacity * sizeof(StorageType)) / sizeof(StorageType);
+        auto* new_buffer = (StorageType*)kmalloc(new_capacity * sizeof(StorageType));
         if (new_buffer == nullptr)
             return false;
 
-        if constexpr (Traits<T>::is_trivial()) {
-            TypedTransfer<T>::copy(new_buffer, data(), m_size);
+        if constexpr (Traits<StorageType>::is_trivial()) {
+            TypedTransfer<StorageType>::copy(new_buffer, data(), m_size);
         } else {
             for (size_t i = 0; i < m_size; ++i) {
-                new (&new_buffer[i]) T(move(at(i)));
-                at(i).~T();
+                new (&new_buffer[i]) StorageType(move(at(i)));
+                at(i).~StorageType();
             }
         }
         if (m_outline_buffer)
@@ -588,7 +642,7 @@ public:
         return true;
     }
 
-    [[nodiscard]] bool try_resize(size_t new_size, bool keep_capacity = false)
+    [[nodiscard]] bool try_resize(size_t new_size, bool keep_capacity = false) requires(!contains_reference)
     {
         if (new_size <= size()) {
             shrink(new_size, keep_capacity);
@@ -599,12 +653,12 @@ public:
             return false;
 
         for (size_t i = size(); i < new_size; ++i)
-            new (slot(i)) T {};
+            new (slot(i)) StorageType {};
         m_size = new_size;
         return true;
     }
 
-    [[nodiscard]] bool try_resize_and_keep_capacity(size_t new_size)
+    [[nodiscard]] bool try_resize_and_keep_capacity(size_t new_size) requires(!contains_reference)
     {
         return try_resize(new_size, true);
     }
@@ -636,17 +690,17 @@ public:
         }
 
         for (size_t i = new_size; i < size(); ++i)
-            at(i).~T();
+            at(i).~StorageType();
         m_size = new_size;
     }
 
-    void resize(size_t new_size, bool keep_capacity = false)
+    void resize(size_t new_size, bool keep_capacity = false) requires(!contains_reference)
     {
         auto did_allocate = try_resize(new_size, keep_capacity);
         VERIFY(did_allocate);
     }
 
-    void resize_and_keep_capacity(size_t new_size)
+    void resize_and_keep_capacity(size_t new_size) requires(!contains_reference)
     {
         auto did_allocate = try_resize_and_keep_capacity(new_size);
         VERIFY(did_allocate);
@@ -703,25 +757,29 @@ private:
         return max(static_cast<size_t>(4), capacity + (capacity / 4) + 4);
     }
 
-    T* slot(size_t i) { return &data()[i]; }
-    T const* slot(size_t i) const { return &data()[i]; }
+    StorageType* slot(size_t i) { return &data()[i]; }
+    StorageType const* slot(size_t i) const { return &data()[i]; }
 
-    T* inline_buffer()
+    StorageType* inline_buffer()
     {
         static_assert(inline_capacity > 0);
-        return reinterpret_cast<T*>(m_inline_buffer_storage);
+        return reinterpret_cast<StorageType*>(m_inline_buffer_storage);
     }
-    T const* inline_buffer() const
+    StorageType const* inline_buffer() const
     {
         static_assert(inline_capacity > 0);
-        return reinterpret_cast<T const*>(m_inline_buffer_storage);
+        return reinterpret_cast<StorageType const*>(m_inline_buffer_storage);
     }
 
+    StorageType& raw_last() { return raw_at(size() - 1); }
+    StorageType& raw_first() { return raw_at(0); }
+    StorageType& raw_at(size_t index) { return *slot(index); }
+
     size_t m_size { 0 };
     size_t m_capacity { 0 };
 
-    alignas(T) unsigned char m_inline_buffer_storage[sizeof(T) * inline_capacity];
-    T* m_outline_buffer { nullptr };
+    alignas(StorageType) unsigned char m_inline_buffer_storage[sizeof(StorageType) * inline_capacity];
+    StorageType* m_outline_buffer { nullptr };
 };
 
 }