LibJS: Object index properties have descriptors; Handle sparse indices

This patch adds an IndexedProperties object for storing indexed
properties within an Object. This accomplishes two goals: indexed
properties now have an associated descriptor, and objects now gracefully
handle sparse properties.

The IndexedProperties class is a wrapper around two other classes, one
for simple indexed properties storage, and one for general indexed
property storage. Simple indexed property storage is the common-case,
and is simply a vector of properties which all have attributes of
default_attributes (writable, enumerable, and configurable).

General indexed property storage is for a collection of indexed
properties where EITHER one or more properties have attributes other
than default_attributes OR there is a property with a large index (in
particular, large is '200' or higher).

Indexed properties are now treated relatively the same as storage within
the various Object methods. Additionally, there is a custom iterator
class for IndexedProperties which makes iteration easy. The iterator
skips empty values by default, but can be configured otherwise.
Likewise, it evaluates getters by default, but can be set not to.

1 files changed, 373 insertions, 0 deletions

diff --git a/Libraries/LibJS/Runtime/IndexedProperties.cpp b/Libraries/LibJS/Runtime/IndexedProperties.cpp
new file mode 100644
index 0000000000..5da0f570b6
--- /dev/null
+++ b/Libraries/LibJS/Runtime/IndexedProperties.cpp
@@ -0,0 +1,373 @@
+/*
+ * Copyright (c) 2020, Matthew Olsson <matthewcolsson@gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <LibJS/Runtime/Accessor.h>
+#include <LibJS/Runtime/IndexedProperties.h>
+
+namespace JS {
+
+SimpleIndexedPropertyStorage::SimpleIndexedPropertyStorage(Vector<Value>&& initial_values)
+    : m_array_size(initial_values.size())
+    , m_packed_elements(move(initial_values))
+{
+}
+
+bool SimpleIndexedPropertyStorage::has_index(u32 index) const
+{
+    return index < m_array_size && !m_packed_elements[index].is_empty();
+}
+
+Optional<ValueAndAttributes> SimpleIndexedPropertyStorage::get(u32 index) const
+{
+    if (index >= m_array_size)
+        return {};
+    return ValueAndAttributes { m_packed_elements[index], default_attributes };
+}
+
+void SimpleIndexedPropertyStorage::put(u32 index, Value value, u8 attributes)
+{
+    ASSERT(attributes == default_attributes);
+    ASSERT(index < SPARSE_ARRAY_THRESHOLD);
+
+    if (index >= m_array_size) {
+        m_array_size = index + 1;
+        if (index >= m_packed_elements.size())
+            m_packed_elements.resize(index + MIN_PACKED_RESIZE_AMOUNT >= SPARSE_ARRAY_THRESHOLD ? SPARSE_ARRAY_THRESHOLD : index + MIN_PACKED_RESIZE_AMOUNT);
+    }
+    m_packed_elements[index] = value;
+}
+
+void SimpleIndexedPropertyStorage::remove(u32 index)
+{
+    if (index < m_array_size)
+        m_packed_elements[index] = {};
+}
+
+void SimpleIndexedPropertyStorage::insert(u32 index, Value value, u8 attributes)
+{
+    ASSERT(attributes == default_attributes);
+    ASSERT(index < SPARSE_ARRAY_THRESHOLD);
+    m_array_size++;
+    ASSERT(m_array_size <= SPARSE_ARRAY_THRESHOLD);
+    m_packed_elements.insert(index, value);
+}
+
+ValueAndAttributes SimpleIndexedPropertyStorage::take_first()
+{
+    m_array_size--;
+    return { m_packed_elements.take_first(), default_attributes };
+}
+
+ValueAndAttributes SimpleIndexedPropertyStorage::take_last()
+{
+    m_array_size--;
+    auto last_element = m_packed_elements[m_array_size];
+    m_packed_elements[m_array_size] = {};
+    return { last_element, default_attributes };
+}
+
+void SimpleIndexedPropertyStorage::set_array_like_size(size_t new_size)
+{
+    ASSERT(new_size <= SPARSE_ARRAY_THRESHOLD);
+    m_array_size = new_size;
+    m_packed_elements.resize(new_size);
+}
+
+GenericIndexedPropertyStorage::GenericIndexedPropertyStorage(SimpleIndexedPropertyStorage&& storage)
+{
+    m_array_size = storage.array_like_size();
+    for (auto& element : move(storage.m_packed_elements))
+        m_packed_elements.append({ element, default_attributes });
+}
+
+bool GenericIndexedPropertyStorage::has_index(u32 index) const
+{
+    if (index < SPARSE_ARRAY_THRESHOLD)
+        return index < m_packed_elements.size() && !m_packed_elements[index].value.is_empty();
+    return m_sparse_elements.contains(index);
+}
+
+Optional<ValueAndAttributes> GenericIndexedPropertyStorage::get(u32 index) const
+{
+    if (index >= m_array_size)
+        return {};
+    if (index < SPARSE_ARRAY_THRESHOLD) {
+        if (index >= m_packed_elements.size())
+            return {};
+        return m_packed_elements[index];
+    }
+    return m_sparse_elements.get(index);
+}
+
+void GenericIndexedPropertyStorage::put(u32 index, Value value, u8 attributes)
+{
+    if (index >= m_array_size)
+        m_array_size = index + 1;
+    if (index < SPARSE_ARRAY_THRESHOLD) {
+        if (index >= m_packed_elements.size())
+            m_packed_elements.resize(index + MIN_PACKED_RESIZE_AMOUNT >= SPARSE_ARRAY_THRESHOLD ? SPARSE_ARRAY_THRESHOLD : index + MIN_PACKED_RESIZE_AMOUNT);
+        m_packed_elements[index] = { value, attributes };
+    } else {
+        m_sparse_elements.set(index, { value, attributes });
+    }
+}
+
+void GenericIndexedPropertyStorage::remove(u32 index)
+{
+    if (index >= m_array_size)
+        return;
+    if (index + 1 == m_array_size) {
+        take_last();
+        return;
+    }
+    if (index < SPARSE_ARRAY_THRESHOLD) {
+        if (index < m_packed_elements.size())
+            m_packed_elements[index] = {};
+    } else {
+        m_sparse_elements.remove(index);
+    }
+}
+
+void GenericIndexedPropertyStorage::insert(u32 index, Value value, u8 attributes)
+{
+    if (index >= m_array_size) {
+        put(index, value, attributes);
+        return;
+    }
+
+    m_array_size++;
+
+    if (!m_sparse_elements.is_empty()) {
+        HashMap<u32, ValueAndAttributes> new_sparse_elements;
+        for (auto& entry : m_sparse_elements)
+            new_sparse_elements.set(entry.key >= index ? entry.key + 1 : entry.key, entry.value);
+        m_sparse_elements = move(new_sparse_elements);
+    }
+
+    if (index < SPARSE_ARRAY_THRESHOLD) {
+        m_packed_elements.insert(index, { value, attributes });
+    } else {
+        m_sparse_elements.set(index, { value, attributes });
+    }
+}
+
+ValueAndAttributes GenericIndexedPropertyStorage::take_first()
+{
+    ASSERT(m_array_size > 0);
+    m_array_size--;
+
+    if (!m_sparse_elements.is_empty()) {
+        HashMap<u32, ValueAndAttributes> new_sparse_elements;
+        for (auto& entry : m_sparse_elements)
+            new_sparse_elements.set(entry.key - 1, entry.value);
+        m_sparse_elements = move(new_sparse_elements);
+    }
+
+    return m_packed_elements.take_first();
+}
+
+ValueAndAttributes GenericIndexedPropertyStorage::take_last()
+{
+    ASSERT(m_array_size > 0);
+    m_array_size--;
+
+    if (m_array_size <= SPARSE_ARRAY_THRESHOLD) {
+        auto last_element = m_packed_elements[m_array_size];
+        m_packed_elements[m_array_size] = {};
+        return last_element;
+    } else {
+        auto result = m_sparse_elements.get(m_array_size);
+        m_sparse_elements.remove(m_array_size);
+        ASSERT(result.has_value());
+        return result.value();
+    }
+}
+
+void GenericIndexedPropertyStorage::set_array_like_size(size_t new_size)
+{
+    if (new_size < SPARSE_ARRAY_THRESHOLD) {
+        m_packed_elements.resize(new_size);
+        m_sparse_elements.clear();
+    } else {
+        m_packed_elements.resize(SPARSE_ARRAY_THRESHOLD);
+
+        HashMap<u32, ValueAndAttributes> new_sparse_elements;
+        for (auto& entry : m_sparse_elements) {
+            if (entry.key < new_size)
+                new_sparse_elements.set(entry.key, entry.value);
+        }
+        m_sparse_elements = move(new_sparse_elements);
+    }
+}
+
+IndexedPropertyIterator::IndexedPropertyIterator(const IndexedProperties& indexed_properties, u32 staring_index, bool skip_empty)
+    : m_indexed_properties(indexed_properties)
+    , m_index(staring_index)
+    , m_skip_empty(skip_empty)
+{
+    while (m_skip_empty && m_index < m_indexed_properties.array_like_size()) {
+        if (m_indexed_properties.has_index(m_index))
+            break;
+        m_index++;
+    }
+}
+
+IndexedPropertyIterator& IndexedPropertyIterator::operator++()
+{
+    m_index++;
+
+    while (m_skip_empty && m_index < m_indexed_properties.array_like_size()) {
+        if (m_indexed_properties.has_index(m_index))
+            break;
+        m_index++;
+    };
+
+    return *this;
+}
+
+IndexedPropertyIterator& IndexedPropertyIterator::operator*()
+{
+    return *this;
+}
+
+bool IndexedPropertyIterator::operator!=(const IndexedPropertyIterator& other) const
+{
+    return m_index != other.m_index;
+}
+
+ValueAndAttributes IndexedPropertyIterator::value_and_attributes(Object* this_object, bool evaluate_accessors)
+{
+    if (m_index < m_indexed_properties.array_like_size())
+        return m_indexed_properties.get(this_object, m_index, evaluate_accessors).value();
+    return {};
+}
+
+Optional<ValueAndAttributes> IndexedProperties::get(Object* this_object, u32 index, bool evaluate_accessors) const
+{
+    auto result = m_storage->get(index);
+    if (!evaluate_accessors)
+        return result;
+    if (!result.has_value())
+        return {};
+    auto value = result.value();
+    if (value.value.is_accessor()) {
+        ASSERT(this_object);
+        auto& accessor = value.value.as_accessor();
+        return ValueAndAttributes { accessor.call_getter(this_object), value.attributes };
+    }
+    return result;
+}
+
+void IndexedProperties::put(Object* this_object, u32 index, Value value, u8 attributes, bool evaluate_accessors)
+{
+    if (m_storage->is_simple_storage() && (index >= SPARSE_ARRAY_THRESHOLD || attributes != default_attributes))
+        switch_to_generic_storage();
+    if (m_storage->is_simple_storage() || !evaluate_accessors) {
+        m_storage->put(index, value, attributes);
+        return;
+    }
+
+    auto value_here = m_storage->get(index);
+    if (value_here.has_value() && value_here.value().value.is_accessor()) {
+        ASSERT(this_object);
+        value_here.value().value.as_accessor().call_setter(this_object, value);
+    } else {
+        m_storage->put(index, value, attributes);
+    }
+}
+
+bool IndexedProperties::remove(u32 index)
+{
+    auto result = m_storage->get(index);
+    if (!result.has_value())
+        return true;
+    if (!(result.value().attributes & Attribute::Configurable))
+        return false;
+    m_storage->remove(index);
+    return true;
+}
+
+void IndexedProperties::insert(u32 index, Value value, u8 attributes)
+{
+    if (m_storage->is_simple_storage() && (index >= SPARSE_ARRAY_THRESHOLD || attributes != default_attributes || array_like_size() == SPARSE_ARRAY_THRESHOLD))
+        switch_to_generic_storage();
+    m_storage->insert(index, value, attributes);
+}
+
+ValueAndAttributes IndexedProperties::take_first(Object *this_object)
+{
+    auto first = m_storage->take_first();
+    if (first.value.is_accessor())
+        return { first.value.as_accessor().call_getter(this_object), first.attributes };
+    return first;
+}
+
+ValueAndAttributes IndexedProperties::take_last(Object *this_object)
+{
+    auto last = m_storage->take_last();
+    if (last.value.is_accessor())
+        return { last.value.as_accessor().call_getter(this_object), last.attributes };
+    return last;
+}
+
+void IndexedProperties::append_all(Object* this_object, const IndexedProperties& properties, bool evaluate_accessors)
+{
+    if (m_storage->is_simple_storage() && !properties.m_storage->is_simple_storage())
+        switch_to_generic_storage();
+
+    for (auto it = properties.begin(false); it != properties.end(); ++it) {
+        auto element = it.value_and_attributes(this_object, evaluate_accessors);
+        if (this_object && this_object->interpreter().exception())
+            return;
+        m_storage->put(m_storage->array_like_size(), element.value, element.attributes);
+    }
+}
+
+Vector<ValueAndAttributes> IndexedProperties::values_unordered() const
+{
+    if (m_storage->is_simple_storage()) {
+        auto elements = static_cast<const SimpleIndexedPropertyStorage&>(*m_storage).elements();
+        Vector<ValueAndAttributes> with_attributes;
+        for (auto& value : elements)
+            with_attributes.append({ value, default_attributes });
+        return with_attributes;
+    }
+
+    auto storage = static_cast<const GenericIndexedPropertyStorage&>(*m_storage);
+    auto values = storage.packed_elements();
+    values.ensure_capacity(values.size() + storage.sparse_elements().size());
+    for (auto& entry : storage.sparse_elements())
+        values.unchecked_append(entry.value);
+    return values;
+}
+
+void IndexedProperties::switch_to_generic_storage()
+{
+    auto storage = static_cast<const SimpleIndexedPropertyStorage&>(*m_storage);
+    m_storage = make<GenericIndexedPropertyStorage>(move(storage));
+}
+
+}