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.

22 files changed, 774 insertions, 147 deletions

diff --git a/Libraries/LibJS/AST.cpp b/Libraries/LibJS/AST.cpp
index 7f8944c18a..8b713fe036 100644
--- a/Libraries/LibJS/AST.cpp
+++ b/Libraries/LibJS/AST.cpp
@@ -57,9 +57,8 @@ static void update_function_name(Value& value, const FlyString& name)
             function.set_name(name);
     } else if (object.is_array()) {
         auto& array = static_cast<Array&>(object);
-        for (size_t i = 0; i < array.elements().size(); ++i) {
-            update_function_name(array.elements()[i], name);
-        }
+        for (auto& entry : array.indexed_properties().values_unordered())
+            update_function_name(entry.value, name);
     }
 }
 
@@ -142,20 +141,22 @@ Value CallExpression::execute(Interpreter& interpreter) const
             return {};
         if (m_arguments[i].is_spread) {
             // FIXME: Support generic iterables
-            Vector<Value> iterables;
             if (value.is_string()) {
                 for (auto ch : value.as_string().string())
-                    iterables.append(Value(js_string(interpreter, String::format("%c", ch))));
+                    arguments.append(Value(js_string(interpreter, String::format("%c", ch))));
             } else if (value.is_object() && value.as_object().is_array()) {
-                iterables = static_cast<const Array&>(value.as_object()).elements();
+                auto& array = static_cast<Array&>(value.as_object());
+                for (auto& entry : array.indexed_properties()) {
+                    arguments.append(entry.value_and_attributes(&array).value);
+                    if (interpreter.exception())
+                        return {};
+                }
             } else if (value.is_object() && value.as_object().is_string_object()) {
                 for (auto ch : static_cast<const StringObject&>(value.as_object()).primitive_string().string())
-                    iterables.append(Value(js_string(interpreter, String::format("%c", ch))));
+                    arguments.append(Value(js_string(interpreter, String::format("%c", ch))));
             } else {
                 interpreter.throw_exception<TypeError>(String::format("%s is not iterable", value.to_string_without_side_effects().characters()));
             }
-            for (auto& value : iterables)
-                arguments.append(value);
         } else {
             arguments.append(value);
         }
@@ -361,8 +362,10 @@ Value ForInStatement::execute(Interpreter& interpreter) const
     auto* object = rhs_result.to_object(interpreter);
     while (object) {
         auto property_names = object->get_own_properties(*object, Object::GetOwnPropertyMode::Key, Attribute::Enumerable);
-        for (auto& property_name : static_cast<Array&>(property_names.as_object()).elements()) {
-            interpreter.set_variable(variable_name, property_name);
+        for (auto& property_name : property_names.as_object().indexed_properties()) {
+            interpreter.set_variable(variable_name, property_name.value_and_attributes(object).value);
+            if (interpreter.exception())
+                return {};
             last_value = interpreter.run(*m_body);
             if (interpreter.exception())
                 return {};
@@ -406,9 +409,13 @@ Value ForOfStatement::execute(Interpreter& interpreter) const
     size_t index = 0;
     auto next = [&]() -> Optional<Value> {
         if (rhs_result.is_array()) {
-            auto array_elements = static_cast<Array*>(&rhs_result.as_object())->elements();
-            if (index < array_elements.size())
-                return Value(array_elements.at(index));
+            auto& array_elements = rhs_result.as_object().indexed_properties();
+            if (index < array_elements.array_like_size()) {
+                auto result = array_elements.get(&rhs_result.as_object(), index);
+                if (interpreter.exception())
+                    return {};
+                return result.value().value;
+            }
         } else if (rhs_result.is_string()) {
             auto string = rhs_result.as_string().string();
             if (index < string.length())
@@ -1277,12 +1284,10 @@ Value ObjectExpression::execute(Interpreter& interpreter) const
         if (property.type() == ObjectProperty::Type::Spread) {
             if (key_result.is_array()) {
                 auto& array_to_spread = static_cast<Array&>(key_result.as_object());
-                auto& elements = array_to_spread.elements();
-
-                for (size_t i = 0; i < elements.size(); ++i) {
-                    auto element = elements.at(i);
-                    if (!element.is_empty())
-                        object->define_property(i, element);
+                for (auto& entry : array_to_spread.indexed_properties()) {
+                    object->indexed_properties().append(entry.value_and_attributes(&array_to_spread).value);
+                    if (interpreter.exception())
+                        return {};
                 }
             } else if (key_result.is_object()) {
                 auto& obj_to_spread = key_result.as_object();
@@ -1441,30 +1446,29 @@ Value ArrayExpression::execute(Interpreter& interpreter) const
                 // FIXME: Support arbitrary iterables
                 if (value.is_array()) {
                     auto& array_to_spread = static_cast<Array&>(value.as_object());
-                    for (auto& it : array_to_spread.elements()) {
-                        if (it.is_empty()) {
-                            array->elements().append(js_undefined());
-                        } else {
-                            array->elements().append(it);
-                        }
+                    for (auto& entry : array_to_spread.indexed_properties()) {
+                        array->indexed_properties().append(entry.value_and_attributes(&array_to_spread).value);
+                        if (interpreter.exception())
+                            return {};
                     }
                     continue;
                 }
                 if (value.is_string() || (value.is_object() && value.as_object().is_string_object())) {
                     String string_to_spread;
-                    if (value.is_string())
+                    if (value.is_string()) {
                         string_to_spread = value.as_string().string();
-                    else
+                    } else {
                         string_to_spread = static_cast<const StringObject&>(value.as_object()).primitive_string().string();
+                    }
                     for (size_t i = 0; i < string_to_spread.length(); ++i)
-                        array->elements().append(js_string(interpreter, string_to_spread.substring(i, 1)));
+                        array->indexed_properties().append(js_string(interpreter, string_to_spread.substring(i, 1)));
                     continue;
                 }
                 interpreter.throw_exception<TypeError>(String::format("%s is not iterable", value.to_string_without_side_effects().characters()));
                 return {};
             }
         }
-        array->elements().append(value);
+        array->indexed_properties().append(value);
     }
     return array;
 }
@@ -1524,10 +1528,11 @@ Value TaggedTemplateLiteral::execute(Interpreter& interpreter) const
             return {};
         // tag`${foo}`             -> "", foo, ""                -> tag(["", ""], foo)
         // tag`foo${bar}baz${qux}` -> "foo", bar, "baz", qux, "" -> tag(["foo", "baz", ""], bar, qux)
-        if (i % 2 == 0)
-            strings->elements().append(value);
-        else
+        if (i % 2 == 0) {
+            strings->indexed_properties().append(value);
+        } else {
             arguments.append(value);
+        }
     }
 
     auto* raw_strings = Array::create(interpreter.global_object());
@@ -1535,7 +1540,7 @@ Value TaggedTemplateLiteral::execute(Interpreter& interpreter) const
         auto value = raw_string.execute(interpreter);
         if (interpreter.exception())
             return {};
-        raw_strings->elements().append(value);
+        raw_strings->indexed_properties().append(value);
     }
     strings->define_property("raw", raw_strings, 0);
 
diff --git a/Libraries/LibJS/CMakeLists.txt b/Libraries/LibJS/CMakeLists.txt
index f47cf3dbb8..b9795afd79 100644
--- a/Libraries/LibJS/CMakeLists.txt
+++ b/Libraries/LibJS/CMakeLists.txt
@@ -28,6 +28,7 @@ set(SOURCES
     Runtime/Function.cpp
     Runtime/FunctionPrototype.cpp
     Runtime/GlobalObject.cpp
+    Runtime/IndexedProperties.cpp
     Runtime/LexicalEnvironment.cpp
     Runtime/MarkedValueList.cpp
     Runtime/MathObject.cpp
diff --git a/Libraries/LibJS/MarkupGenerator.cpp b/Libraries/LibJS/MarkupGenerator.cpp
index 001bf3971a..9db68b2077 100644
--- a/Libraries/LibJS/MarkupGenerator.cpp
+++ b/Libraries/LibJS/MarkupGenerator.cpp
@@ -116,10 +116,13 @@ void MarkupGenerator::value_to_html(Value value, StringBuilder& output_html, Has
 void MarkupGenerator::array_to_html(const Array& array, StringBuilder& html_output, HashTable<Object*>& seen_objects)
 {
     html_output.append(wrap_string_in_style("[ ", StyleType::Punctuation));
-    for (size_t i = 0; i < array.elements().size(); ++i) {
-        value_to_html(array.elements()[i], html_output, seen_objects);
-        if (i != array.elements().size() - 1)
+    bool first = true;
+    for (auto it = array.indexed_properties().begin(false); it != array.indexed_properties().end(); ++it) {
+        if (!first)
             html_output.append(wrap_string_in_style(", ", StyleType::Punctuation));
+        first = false;
+        // FIXME: Exception check
+        value_to_html(it.value_and_attributes(const_cast<Array*>(&array)).value, html_output, seen_objects);
     }
     html_output.append(wrap_string_in_style(" ]", StyleType::Punctuation));
 }
@@ -127,18 +130,18 @@ void MarkupGenerator::array_to_html(const Array& array, StringBuilder& html_outp
 void MarkupGenerator::object_to_html(const Object& object, StringBuilder& html_output, HashTable<Object*>& seen_objects)
 {
     html_output.append(wrap_string_in_style("{ ", StyleType::Punctuation));
-
-    for (size_t i = 0; i < object.elements().size(); ++i) {
-        if (object.elements()[i].is_empty())
-            continue;
-        html_output.append(wrap_string_in_style(String::format("%zu", i), StyleType::Number));
-        html_output.append(wrap_string_in_style(": ", StyleType::Punctuation));
-        value_to_html(object.elements()[i], html_output, seen_objects);
-        if (i != object.elements().size() - 1)
+    bool first = true;
+    for (auto& entry : object.indexed_properties()) {
+        if (!first)
             html_output.append(wrap_string_in_style(", ", StyleType::Punctuation));
+        first = false;
+        html_output.append(wrap_string_in_style(String::number(entry.index()), StyleType::Number));
+        html_output.append(wrap_string_in_style(": ", StyleType::Punctuation));
+        // FIXME: Exception check
+        value_to_html(entry.value_and_attributes(const_cast<Object*>(&object)).value, html_output, seen_objects);
     }
 
-    if (!object.elements().is_empty() && object.shape().property_count())
+    if (!object.indexed_properties().is_empty() && object.shape().property_count())
         html_output.append(wrap_string_in_style(", ", StyleType::Punctuation));
 
     size_t index = 0;
diff --git a/Libraries/LibJS/Runtime/Accessor.h b/Libraries/LibJS/Runtime/Accessor.h
index 9f7fd9451a..82ade250a2 100644
--- a/Libraries/LibJS/Runtime/Accessor.h
+++ b/Libraries/LibJS/Runtime/Accessor.h
@@ -27,7 +27,9 @@
 
 #pragma once
 
+#include <LibJS/Interpreter.h>
 #include <LibJS/Runtime/Function.h>
+#include <LibJS/Runtime/MarkedValueList.h>
 
 namespace JS {
 
diff --git a/Libraries/LibJS/Runtime/Array.cpp b/Libraries/LibJS/Runtime/Array.cpp
index 38d78cb161..8c28966236 100644
--- a/Libraries/LibJS/Runtime/Array.cpp
+++ b/Libraries/LibJS/Runtime/Array.cpp
@@ -66,7 +66,7 @@ Value Array::length_getter(Interpreter& interpreter)
     auto* array = array_from(interpreter);
     if (!array)
         return {};
-    return Value(array->length());
+    return Value(static_cast<i32>(array->indexed_properties().array_like_size()));
 }
 
 void Array::length_setter(Interpreter& interpreter, Value value)
@@ -81,7 +81,7 @@ void Array::length_setter(Interpreter& interpreter, Value value)
         interpreter.throw_exception<RangeError>("Invalid array length");
         return;
     }
-    array->elements().resize(length.as_double());
+    array->indexed_properties().set_array_like_size(length.as_double());
 }
 
 }
diff --git a/Libraries/LibJS/Runtime/Array.h b/Libraries/LibJS/Runtime/Array.h
index 6b580b2889..a45ac0e9eb 100644
--- a/Libraries/LibJS/Runtime/Array.h
+++ b/Libraries/LibJS/Runtime/Array.h
@@ -39,8 +39,6 @@ public:
     explicit Array(Object& prototype);
     virtual ~Array() override;
 
-    i32 length() const { return static_cast<i32>(elements().size()); }
-
 private:
     virtual const char* class_name() const override { return "Array"; }
     virtual bool is_array() const override { return true; }
diff --git a/Libraries/LibJS/Runtime/ArrayConstructor.cpp b/Libraries/LibJS/Runtime/ArrayConstructor.cpp
index 3af09146b3..800a386836 100644
--- a/Libraries/LibJS/Runtime/ArrayConstructor.cpp
+++ b/Libraries/LibJS/Runtime/ArrayConstructor.cpp
@@ -63,13 +63,13 @@ Value ArrayConstructor::call(Interpreter& interpreter)
             return {};
         }
         auto* array = Array::create(interpreter.global_object());
-        array->elements().resize(array_length_value.as_i32());
+        array->indexed_properties().set_array_like_size(array_length_value.as_i32());
         return array;
     }
 
     auto* array = Array::create(interpreter.global_object());
     for (size_t i = 0; i < interpreter.argument_count(); ++i)
-        array->elements().append(interpreter.argument(i));
+        array->indexed_properties().append(interpreter.argument(i));
     return array;
 }
 
@@ -91,7 +91,7 @@ Value ArrayConstructor::of(Interpreter& interpreter)
 {
     auto* array = Array::create(interpreter.global_object());
     for (size_t i = 0; i < interpreter.argument_count(); ++i)
-        array->elements().append(interpreter.argument(i));
+        array->indexed_properties().append(interpreter.argument(i));
     return array;
 }
 
diff --git a/Libraries/LibJS/Runtime/ArrayPrototype.cpp b/Libraries/LibJS/Runtime/ArrayPrototype.cpp
index 1c8a95035c..bbe6a929aa 100644
--- a/Libraries/LibJS/Runtime/ArrayPrototype.cpp
+++ b/Libraries/LibJS/Runtime/ArrayPrototype.cpp
@@ -143,7 +143,7 @@ Value ArrayPrototype::filter(Interpreter& interpreter)
     auto* new_array = Array::create(interpreter.global_object());
     for_each_item(interpreter, "filter", [&](auto, auto value, auto callback_result) {
         if (callback_result.to_boolean())
-            new_array->elements().append(value);
+            new_array->indexed_properties().append(value);
         return IterationDecision::Continue;
     });
     return Value(new_array);
@@ -166,9 +166,9 @@ Value ArrayPrototype::map(Interpreter& interpreter)
     if (interpreter.exception())
         return {};
     auto* new_array = Array::create(interpreter.global_object());
-    new_array->elements().resize(initial_length);
+    new_array->indexed_properties().set_array_like_size(initial_length);
     for_each_item(interpreter, "map", [&](auto index, auto, auto callback_result) {
-        new_array->elements()[index] = callback_result;
+        new_array->put(index, callback_result);
         return IterationDecision::Continue;
     });
     return Value(new_array);
@@ -182,8 +182,8 @@ Value ArrayPrototype::push(Interpreter& interpreter)
     if (this_object->is_array()) {
         auto* array = static_cast<Array*>(this_object);
         for (size_t i = 0; i < interpreter.argument_count(); ++i)
-            array->elements().append(interpreter.argument(i));
-        return Value(array->length());
+            array->indexed_properties().append(interpreter.argument(i));
+        return Value(static_cast<i32>(array->indexed_properties().array_like_size()));
     }
     auto length = get_length(interpreter, *this_object);
     if (interpreter.exception())
@@ -207,8 +207,8 @@ Value ArrayPrototype::unshift(Interpreter& interpreter)
     if (!array)
         return {};
     for (size_t i = 0; i < interpreter.argument_count(); ++i)
-        array->elements().insert(i, interpreter.argument(i));
-    return Value(array->length());
+        array->indexed_properties().insert(i, interpreter.argument(i));
+    return Value(static_cast<i32>(array->indexed_properties().array_like_size()));
 }
 
 Value ArrayPrototype::pop(Interpreter& interpreter)
@@ -218,9 +218,9 @@ Value ArrayPrototype::pop(Interpreter& interpreter)
         return {};
     if (this_object->is_array()) {
         auto* array = static_cast<Array*>(this_object);
-        if (array->elements().is_empty())
+        if (array->indexed_properties().is_empty())
             return js_undefined();
-        return array->elements().take_last().value_or(js_undefined());
+        return array->indexed_properties().take_last(array).value.value_or(js_undefined());
     }
     auto length = get_length(interpreter, *this_object);
     if (length == 0) {
@@ -243,9 +243,12 @@ Value ArrayPrototype::shift(Interpreter& interpreter)
     auto* array = array_from(interpreter);
     if (!array)
         return {};
-    if (array->elements().is_empty())
+    if (array->indexed_properties().is_empty())
         return js_undefined();
-    return array->elements().take_first().value_or(js_undefined());
+    auto result = array->indexed_properties().take_first(array);
+    if (interpreter.exception())
+        return {};
+    return result.value.value_or(js_undefined());
 }
 
 Value ArrayPrototype::to_string(Interpreter& interpreter)
@@ -299,15 +302,19 @@ Value ArrayPrototype::concat(Interpreter& interpreter)
         return {};
 
     auto* new_array = Array::create(interpreter.global_object());
-    new_array->elements().append(array->elements());
+    new_array->indexed_properties().append_all(array, array->indexed_properties());
+    if (interpreter.exception())
+        return {};
 
     for (size_t i = 0; i < interpreter.argument_count(); ++i) {
         auto argument = interpreter.argument(i);
         if (argument.is_array()) {
             auto& argument_object = argument.as_object();
-            new_array->elements().append(argument_object.elements());
+            new_array->indexed_properties().append_all(&argument_object, argument_object.indexed_properties());
+            if (interpreter.exception())
+                return {};
         } else {
-            new_array->elements().append(argument);
+            new_array->indexed_properties().append(argument);
         }
     }
 
@@ -322,11 +329,13 @@ Value ArrayPrototype::slice(Interpreter& interpreter)
 
     auto* new_array = Array::create(interpreter.global_object());
     if (interpreter.argument_count() == 0) {
-        new_array->elements().append(array->elements());
+        new_array->indexed_properties().append_all(array, array->indexed_properties());
+        if (interpreter.exception())
+            return {};
         return new_array;
     }
 
-    ssize_t array_size = static_cast<ssize_t>(array->elements().size());
+    ssize_t array_size = static_cast<ssize_t>(array->indexed_properties().array_like_size());
     auto start_slice = interpreter.argument(0).to_i32(interpreter);
     if (interpreter.exception())
         return {};
@@ -348,10 +357,10 @@ Value ArrayPrototype::slice(Interpreter& interpreter)
             end_slice = array_size;
     }
 
-    size_t array_capacity = start_slice + array_size - end_slice;
-    new_array->elements().ensure_capacity(array_capacity);
     for (ssize_t i = start_slice; i < end_slice; ++i) {
-        new_array->elements().append(array->elements().at(i));
+        new_array->indexed_properties().append(array->get(i));
+        if (interpreter.exception())
+            return {};
     }
 
     return new_array;
@@ -512,16 +521,20 @@ Value ArrayPrototype::reverse(Interpreter& interpreter)
     if (!array)
         return {};
 
-    if (array->elements().size() == 0)
+    if (array->indexed_properties().is_empty())
         return array;
 
     Vector<Value> array_reverse;
-    array_reverse.ensure_capacity(array->elements().size());
+    auto size = array->indexed_properties().array_like_size();
+    array_reverse.ensure_capacity(size);
 
-    for (ssize_t i = array->elements().size() - 1; i >= 0; --i)
-        array_reverse.append(array->elements().at(i));
+    for (ssize_t i = size - 1; i >= 0; --i) {
+        array_reverse.append(array->get(i));
+        if (interpreter.exception())
+            return {};
+    }
 
-    array->elements() = move(array_reverse);
+    array->set_indexed_property_elements(move(array_reverse));
 
     return array;
 }
@@ -691,7 +704,7 @@ Value ArrayPrototype::splice(Interpreter& interpreter)
         if (interpreter.exception())
             return {};
 
-        removed_elements->elements().append(value);
+        removed_elements->indexed_properties().append(value);
     }
 
     if (insert_count < actual_delete_count) {
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));
+}
+
+}
diff --git a/Libraries/LibJS/Runtime/IndexedProperties.h b/Libraries/LibJS/Runtime/IndexedProperties.h
new file mode 100644
index 0000000000..9456a9dafe
--- /dev/null
+++ b/Libraries/LibJS/Runtime/IndexedProperties.h
@@ -0,0 +1,175 @@
+/*
+ * 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.
+ */
+
+#pragma once
+
+#include <AK/NonnullOwnPtr.h>
+#include <LibJS/Runtime/Shape.h>
+#include <LibJS/Runtime/Value.h>
+
+namespace JS {
+
+const u32 SPARSE_ARRAY_THRESHOLD = 200;
+const u32 MIN_PACKED_RESIZE_AMOUNT = 20;
+
+struct ValueAndAttributes {
+    Value value;
+    u8 attributes { default_attributes };
+};
+
+class IndexedProperties;
+class IndexedPropertyIterator;
+class GenericIndexedPropertyStorage;
+
+class IndexedPropertyStorage {
+public:
+    virtual ~IndexedPropertyStorage() {};
+
+    virtual bool has_index(u32 index) const = 0;
+    virtual Optional<ValueAndAttributes> get(u32 index) const = 0;
+    virtual void put(u32 index, Value value, u8 attributes = default_attributes) = 0;
+    virtual void remove(u32 index) = 0;
+
+    virtual void insert(u32 index, Value value, u8 attributes = default_attributes) = 0;
+    virtual ValueAndAttributes take_first() = 0;
+    virtual ValueAndAttributes take_last() = 0;
+
+    virtual size_t size() const = 0;
+    virtual size_t array_like_size() const = 0;
+    virtual void set_array_like_size(size_t new_size) = 0;
+
+    virtual bool is_simple_storage() const { return false; }
+};
+
+class SimpleIndexedPropertyStorage final : public IndexedPropertyStorage {
+public:
+    SimpleIndexedPropertyStorage() = default;
+    explicit SimpleIndexedPropertyStorage(Vector<Value>&& initial_values);
+
+    virtual bool has_index(u32 index) const override;
+    virtual Optional<ValueAndAttributes> get(u32 index) const override;
+    virtual void put(u32 index, Value value, u8 attributes = default_attributes) override;
+    virtual void remove(u32 index) override;
+
+    virtual void insert(u32 index, Value value, u8 attributes = default_attributes) override;
+    virtual ValueAndAttributes take_first() override;
+    virtual ValueAndAttributes take_last() override;
+
+    virtual size_t size() const override { return m_packed_elements.size(); }
+    virtual size_t array_like_size() const override { return m_array_size; }
+    virtual void set_array_like_size(size_t new_size) override;
+
+    virtual bool is_simple_storage() const override { return true; }
+    Vector<Value> elements() const { return m_packed_elements; }
+
+private:
+    friend GenericIndexedPropertyStorage;
+
+    size_t m_array_size { 0 };
+    Vector<Value> m_packed_elements;
+};
+
+class GenericIndexedPropertyStorage final : public IndexedPropertyStorage {
+public:
+    explicit GenericIndexedPropertyStorage(SimpleIndexedPropertyStorage&&);
+
+    virtual bool has_index(u32 index) const override;
+    virtual Optional<ValueAndAttributes> get(u32 index) const override;
+    virtual void put(u32 index, Value value, u8 attributes = default_attributes) override;
+    virtual void remove(u32 index) override;
+
+    virtual void insert(u32 index, Value value, u8 attributes = default_attributes) override;
+    virtual ValueAndAttributes take_first() override;
+    virtual ValueAndAttributes take_last() override;
+
+    virtual size_t size() const override { return m_packed_elements.size() + m_sparse_elements.size(); }
+    virtual size_t array_like_size() const override { return m_array_size; }
+    virtual void set_array_like_size(size_t new_size) override;
+
+    Vector<ValueAndAttributes> packed_elements() const { return m_packed_elements; }
+    HashMap<u32, ValueAndAttributes> sparse_elements() const { return m_sparse_elements; }
+
+private:
+    size_t m_array_size { 0 };
+    Vector<ValueAndAttributes> m_packed_elements;
+    HashMap<u32, ValueAndAttributes> m_sparse_elements;
+};
+
+class IndexedPropertyIterator {
+public:
+    IndexedPropertyIterator(const IndexedProperties&, u32 starting_index, bool skip_empty);
+
+    IndexedPropertyIterator& operator++();
+    IndexedPropertyIterator& operator*();
+    bool operator!=(const IndexedPropertyIterator&) const;
+
+    u32 index() const { return m_index; };
+    ValueAndAttributes value_and_attributes(Object* this_object, bool evaluate_accessors = true);
+
+private:
+    const IndexedProperties& m_indexed_properties;
+    u32 m_index;
+    bool m_skip_empty;
+};
+
+class IndexedProperties {
+public:
+    IndexedProperties() = default;
+
+    IndexedProperties(Vector<Value>&& values)
+        : m_storage(make<SimpleIndexedPropertyStorage>(move(values)))
+    {
+    }
+
+    bool has_index(u32 index) const { return m_storage->has_index(index); }
+    Optional<ValueAndAttributes> get(Object* this_object, u32 index, bool evaluate_accessors = true) const;
+    void put(Object* this_object, u32 index, Value value, u8 attributes = default_attributes, bool evaluate_accessors = true);
+    bool remove(u32 index);
+
+    void insert(u32 index, Value value, u8 attributes = default_attributes);
+    ValueAndAttributes take_first(Object* this_object);
+    ValueAndAttributes take_last(Object* this_object);
+
+    void append(Value value, u8 attributes = default_attributes) { put(nullptr, array_like_size(), value, attributes, false); }
+    void append_all(Object* this_object, const IndexedProperties& properties, bool evaluate_accessors = true);
+
+    IndexedPropertyIterator begin(bool skip_empty = true) const { return IndexedPropertyIterator(*this, 0, skip_empty); };
+    IndexedPropertyIterator end() const { return IndexedPropertyIterator(*this, array_like_size(), false); };
+
+    size_t size() const { return m_storage->size(); }
+    bool is_empty() const { return size() == 0; }
+    size_t array_like_size() const { return m_storage->array_like_size(); }
+    void set_array_like_size(size_t new_size) { m_storage->set_array_like_size(new_size); };
+
+    Vector<ValueAndAttributes> values_unordered() const;
+
+private:
+    void switch_to_generic_storage();
+
+    NonnullOwnPtr<IndexedPropertyStorage> m_storage { make<SimpleIndexedPropertyStorage>() };
+};
+
+}
diff --git a/Libraries/LibJS/Runtime/Object.cpp b/Libraries/LibJS/Runtime/Object.cpp
index 8e4043cbb8..bab44c3b88 100644
--- a/Libraries/LibJS/Runtime/Object.cpp
+++ b/Libraries/LibJS/Runtime/Object.cpp
@@ -94,9 +94,10 @@ Value Object::get_own_property(const Object& this_object, PropertyName property_
     Value value_here;
 
     if (property_name.is_number()) {
-        if (static_cast<size_t>(property_name.as_number()) >= m_elements.size())
+        auto existing_property = m_indexed_properties.get(nullptr, property_name.as_number(), false);
+        if (!existing_property.has_value())
             return {};
-        value_here = m_elements[property_name.as_number()];
+        value_here = existing_property.value().value;
     } else {
         auto metadata = shape().lookup(property_name.as_string());
         if (!metadata.has_value())
@@ -145,19 +146,20 @@ Value Object::get_own_properties(const Object& this_object, GetOwnPropertyMode k
     }
 
     size_t property_index = 0;
-    for (size_t i = 0; i < m_elements.size(); ++i) {
-        if (m_elements.at(i).is_empty())
-            continue;
-
+    for (auto& entry : m_indexed_properties) {
         if (kind == GetOwnPropertyMode::Key) {
-            properties_array->put_by_index(property_index, js_string(interpreter(), String::number(i)));
+            properties_array->define_property(property_index, js_string(interpreter(), String::number(entry.index())));
         } else if (kind == GetOwnPropertyMode::Value) {
-            properties_array->put_by_index(property_index, m_elements.at(i));
+            properties_array->define_property(property_index, entry.value_and_attributes(const_cast<Object*>(&this_object)).value);
+            if (interpreter().exception())
+                return {};
         } else {
             auto* entry_array = Array::create(interpreter().global_object());
-            entry_array->put_by_index(0, js_string(interpreter(), String::number(i)));
-            entry_array->put_by_index(1, m_elements.at(i));
-            properties_array->put_by_index(property_index, entry_array);
+            entry_array->define_property(0, js_string(interpreter(), String::number(entry.index())));
+            entry_array->define_property(1, entry.value_and_attributes(const_cast<Object*>(&this_object)).value);
+            if (interpreter().exception())
+                return {};
+            properties_array->define_property(property_index, entry_array);
         }
 
         ++property_index;
@@ -168,14 +170,18 @@ Value Object::get_own_properties(const Object& this_object, GetOwnPropertyMode k
             size_t offset = it.value.offset + property_index;
 
             if (kind == GetOwnPropertyMode::Key) {
-                properties_array->put_by_index(offset, js_string(interpreter(), it.key));
+                properties_array->define_property(offset, js_string(interpreter(), it.key));
             } else if (kind == GetOwnPropertyMode::Value) {
-                properties_array->put_by_index(offset, this_object.get(it.key));
+                properties_array->define_property(offset, this_object.get(it.key));
+                if (interpreter().exception())
+                    return {};
             } else {
                 auto* entry_array = Array::create(interpreter().global_object());
-                entry_array->put_by_index(0, js_string(interpreter(), it.key));
-                entry_array->put_by_index(1, this_object.get(it.key));
-                properties_array->put_by_index(offset, entry_array);
+                entry_array->define_property(0, js_string(interpreter(), it.key));
+                entry_array->define_property(1, this_object.get(it.key));
+                if (interpreter().exception())
+                    return {};
+                properties_array->define_property(offset, entry_array);
             }
         }
     }
@@ -189,9 +195,11 @@ Value Object::get_own_property_descriptor(PropertyName property_name) const
     u8 attributes;
 
     if (property_name.is_number()) {
-        if (static_cast<size_t>(property_name.as_number()) >= m_elements.size())
-            return {};
-        value = m_elements[property_name.as_number()];
+        auto existing_value = m_indexed_properties.get(nullptr, property_name.as_number(), false);
+        if (!existing_value.has_value())
+            return js_undefined();
+        value = existing_value.value().value;
+        attributes = existing_value.value().attributes;
         attributes = default_attributes;
     } else {
         auto metadata = shape().lookup(property_name.as_string());
@@ -381,9 +389,9 @@ bool Object::put_own_property_by_index(Object& this_object, u32 property_index,
             attributes |= Attribute::HasSet;
     }
 
-    auto new_property = property_index >= m_elements.size();
-    auto existing_property = new_property ? Value() : m_elements[property_index];
-    auto existing_attributes = default_attributes;
+    auto existing_property = m_indexed_properties.get(nullptr, property_index, false);
+    auto new_property = !existing_property.has_value();
+    auto existing_attributes = new_property ? 0 : existing_property.value().attributes;
 
     if (!new_property && mode == PutOwnPropertyMode::DefineProperty && !(existing_attributes & Attribute::Configurable) && attributes != existing_attributes) {
         dbg() << "Disallow reconfig of non-configurable property";
@@ -392,7 +400,7 @@ bool Object::put_own_property_by_index(Object& this_object, u32 property_index,
         return false;
     }
 
-    auto value_here = existing_property;
+    auto value_here = new_property ? Value() : existing_property.value().value;
     if (!new_property && mode == PutOwnPropertyMode::Put && !value_here.is_accessor() && !(existing_attributes & Attribute::Writable)) {
         dbg() << "Disallow write to non-writable property";
         return false;
@@ -409,9 +417,7 @@ bool Object::put_own_property_by_index(Object& this_object, u32 property_index,
         native_property.set(interpreter, value);
         interpreter.pop_call_frame();
     } else {
-        if (new_property)
-            m_elements.resize(property_index + 1);
-        m_elements[property_index] = value;
+        m_indexed_properties.put(&this_object, property_index, value, attributes, mode == PutOwnPropertyMode::Put);
     }
     return true;
 }
@@ -419,13 +425,8 @@ bool Object::put_own_property_by_index(Object& this_object, u32 property_index,
 Value Object::delete_property(PropertyName property_name)
 {
     ASSERT(property_name.is_valid());
-    if (property_name.is_number()) {
-        if (property_name.as_number() < static_cast<i32>(elements().size())) {
-            elements()[property_name.as_number()] = {};
-            return Value(true);
-        }
-        return Value(true);
-    }
+    if (property_name.is_number())
+        return Value(m_indexed_properties.remove(property_name.as_number()));
     auto metadata = shape().lookup(property_name.as_string());
     if (!metadata.has_value())
         return Value(true);
@@ -459,11 +460,13 @@ Value Object::get_by_index(u32 property_index) const
                 return js_string(heap(), string.substring(property_index, 1));
             return js_undefined();
         }
-        if (static_cast<size_t>(property_index) < object->m_elements.size()) {
-            auto value = object->m_elements[property_index];
-            if (value.is_empty())
+        if (static_cast<size_t>(property_index) < object->m_indexed_properties.array_like_size()) {
+            auto result = object->m_indexed_properties.get(const_cast<Object*>(this), property_index);
+            if (interpreter().exception())
                 return {};
-            return value;
+            if (result.has_value() && !result.value().value.is_empty())
+                return result.value().value;
+            return {};
         }
         object = object->prototype();
     }
@@ -494,12 +497,31 @@ Value Object::get(PropertyName property_name) const
 bool Object::put_by_index(u32 property_index, Value value)
 {
     ASSERT(!value.is_empty());
-    // FIXME: Implement some kind of sparse storage for arrays with huge indices.
-    // Also: Take attributes into account here
-    if (static_cast<size_t>(property_index) >= m_elements.size())
-        m_elements.resize(property_index + 1);
-    m_elements[property_index] = value;
-    return true;
+
+    // If there's a setter in the prototype chain, we go to the setter.
+    // Otherwise, it goes in the own property storage.
+    Object* object = this;
+    while (object) {
+        auto existing_value = object->m_indexed_properties.get(nullptr, property_index, false);
+        if (existing_value.has_value()) {
+            auto value_here = existing_value.value();
+            if (value_here.value.is_accessor()) {
+                value_here.value.as_accessor().call_setter(object, value);
+                return true;
+            }
+            if (value_here.value.is_object() && value_here.value.as_object().is_native_property()) {
+                auto& native_property = static_cast<NativeProperty&>(value_here.value.as_object());
+                auto& interpreter = const_cast<Object*>(this)->interpreter();
+                auto& call_frame = interpreter.push_call_frame();
+                call_frame.this_value = this;
+                native_property.set(interpreter, value);
+                interpreter.pop_call_frame();
+                return true;
+            }
+        }
+        object = object->prototype();
+    }
+    return put_own_property_by_index(*this, property_index, value, default_attributes, PutOwnPropertyMode::Put);
 }
 
 bool Object::put(PropertyName property_name, Value value)
@@ -562,8 +584,8 @@ void Object::visit_children(Cell::Visitor& visitor)
     for (auto& value : m_storage)
         visitor.visit(value);
 
-    for (auto& value : m_elements)
-        visitor.visit(value);
+    for (auto& value : m_indexed_properties.values_unordered())
+        visitor.visit(value.value);
 }
 
 bool Object::has_property(PropertyName property_name) const
@@ -582,9 +604,7 @@ bool Object::has_own_property(PropertyName property_name) const
     auto has_indexed_property = [&](u32 index) -> bool {
         if (is_string_object())
             return index < static_cast<const StringObject*>(this)->primitive_string().string().length();
-        if (static_cast<size_t>(index) >= m_elements.size())
-            return false;
-        return !m_elements[index].is_empty();
+        return m_indexed_properties.has_index(index);
     };
 
     if (property_name.is_number())
diff --git a/Libraries/LibJS/Runtime/Object.h b/Libraries/LibJS/Runtime/Object.h
index 752d186c62..ad334a2d8a 100644
--- a/Libraries/LibJS/Runtime/Object.h
+++ b/Libraries/LibJS/Runtime/Object.h
@@ -30,6 +30,7 @@
 #include <AK/String.h>
 #include <LibJS/Forward.h>
 #include <LibJS/Runtime/Cell.h>
+#include <LibJS/Runtime/IndexedProperties.h>
 #include <LibJS/Runtime/PrimitiveString.h>
 #include <LibJS/Runtime/PropertyName.h>
 #include <LibJS/Runtime/Shape.h>
@@ -37,8 +38,6 @@
 
 namespace JS {
 
-const u8 default_attributes = Attribute::Configurable | Attribute::Writable | Attribute::Enumerable;
-
 class Object : public Cell {
 public:
     static Object* create_empty(Interpreter&, GlobalObject&);
@@ -110,8 +109,9 @@ public:
 
     Value get_direct(size_t index) const { return m_storage[index]; }
 
-    const Vector<Value>& elements() const { return m_elements; }
-    Vector<Value>& elements() { return m_elements; }
+    const IndexedProperties& indexed_properties() const { return m_indexed_properties; }
+    IndexedProperties& indexed_properties() { return m_indexed_properties; }
+    void set_indexed_property_elements(Vector<Value>&& values) { m_indexed_properties = IndexedProperties(move(values)); }
 
 private:
     virtual Value get_by_index(u32 property_index) const;
@@ -124,7 +124,7 @@ private:
 
     Shape* m_shape { nullptr };
     Vector<Value> m_storage;
-    Vector<Value> m_elements;
+    IndexedProperties m_indexed_properties;
 };
 
 }
diff --git a/Libraries/LibJS/Runtime/ObjectConstructor.cpp b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
index e9f9459f5b..828e0db2ea 100644
--- a/Libraries/LibJS/Runtime/ObjectConstructor.cpp
+++ b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
@@ -75,14 +75,11 @@ Value ObjectConstructor::get_own_property_names(Interpreter& interpreter)
     if (interpreter.exception())
         return {};
     auto* result = Array::create(interpreter.global_object());
-    for (size_t i = 0; i < object->elements().size(); ++i) {
-        if (!object->elements()[i].is_empty())
-            result->elements().append(js_string(interpreter, String::number(i)));
-    }
-
-    for (auto& it : object->shape().property_table_ordered()) {
-        result->elements().append(js_string(interpreter, it.key));
-    }
+    for (auto& entry : object->indexed_properties())
+        result->indexed_properties().append(js_string(interpreter, String::number(entry.index())));
+    for (auto& it : object->shape().property_table_ordered())
+        result->indexed_properties().append(js_string(interpreter, it.key));
+
     return result;
 }
 
diff --git a/Libraries/LibJS/Runtime/ScriptFunction.cpp b/Libraries/LibJS/Runtime/ScriptFunction.cpp
index 4d8e0a4597..1b6aa3ef3b 100644
--- a/Libraries/LibJS/Runtime/ScriptFunction.cpp
+++ b/Libraries/LibJS/Runtime/ScriptFunction.cpp
@@ -104,7 +104,7 @@ Value ScriptFunction::call(Interpreter& interpreter)
         if (parameter.is_rest) {
             auto* array = Array::create(interpreter.global_object());
             for (size_t rest_index = i; rest_index < argument_values.size(); ++rest_index)
-                array->elements().append(argument_values[rest_index]);
+                array->indexed_properties().append(argument_values[rest_index]);
             value = Value(array);
         } else {
             if (i < argument_values.size() && !argument_values[i].is_undefined()) {
diff --git a/Libraries/LibJS/Runtime/Shape.h b/Libraries/LibJS/Runtime/Shape.h
index e3d5305dca..ac19d775c7 100644
--- a/Libraries/LibJS/Runtime/Shape.h
+++ b/Libraries/LibJS/Runtime/Shape.h
@@ -45,6 +45,8 @@ struct Attribute {
     };
 };
 
+const u8 default_attributes = Attribute::Configurable | Attribute::Writable | Attribute::Enumerable;
+
 struct PropertyMetadata {
     size_t offset { 0 };
     u8 attributes { 0 };
diff --git a/Libraries/LibJS/Runtime/StringConstructor.cpp b/Libraries/LibJS/Runtime/StringConstructor.cpp
index a4f5a12ca3..fd24023a74 100644
--- a/Libraries/LibJS/Runtime/StringConstructor.cpp
+++ b/Libraries/LibJS/Runtime/StringConstructor.cpp
@@ -83,14 +83,20 @@ Value StringConstructor::raw(Interpreter& interpreter)
     if (!raw.is_array())
         return js_string(interpreter, "");
 
-    auto& raw_array_elements = static_cast<Array*>(raw.to_object(interpreter))->elements();
+    auto* array = static_cast<Array*>(raw.to_object(interpreter));
+    auto& raw_array_elements = array->indexed_properties();
     StringBuilder builder;
 
-    for (size_t i = 0; i < raw_array_elements.size(); ++i) {
-        builder.append(raw_array_elements.at(i).to_string(interpreter));
+    for (size_t i = 0; i < raw_array_elements.array_like_size(); ++i) {
+        auto result = raw_array_elements.get(array, i);
         if (interpreter.exception())
             return {};
-        if (i + 1 < interpreter.argument_count() && i < raw_array_elements.size() - 1) {
+        if (!result.has_value())
+            continue;
+        builder.append(result.value().value.to_string(interpreter));
+        if (interpreter.exception())
+            return {};
+        if (i + 1 < interpreter.argument_count() && i < raw_array_elements.array_like_size() - 1) {
             builder.append(interpreter.argument(i + 1).to_string(interpreter));
             if (interpreter.exception())
                 return {};
diff --git a/Libraries/LibJS/Tests/Array.js b/Libraries/LibJS/Tests/Array.js
index c103025bb0..a96388a006 100644
--- a/Libraries/LibJS/Tests/Array.js
+++ b/Libraries/LibJS/Tests/Array.js
@@ -29,6 +29,10 @@ try {
     assert(a[0][1] === 2);
     assert(a[0][2] === 3);
 
+    a = new Array(1, 2, 3);
+    Object.defineProperty(a, 3, { get() { return 10; } });
+    assert(a.toString() === "1,2,3,10");
+
     [-1, -100, -0.1, 0.1, 1.23, Infinity, -Infinity, NaN].forEach(value => {
         assertThrowsError(() => {
             new Array(value);
diff --git a/Libraries/LibJS/Tests/Array.of.js b/Libraries/LibJS/Tests/Array.of.js
index 1fb4200847..49b1561d88 100644
--- a/Libraries/LibJS/Tests/Array.of.js
+++ b/Libraries/LibJS/Tests/Array.of.js
@@ -31,6 +31,15 @@ try {
     assert(a[0][1] === 2);
     assert(a[0][2] === 3);
 
+    let t = [1, 2, 3];
+    Object.defineProperty(t, 3, { get() { return 4; } });
+    a = Array.of(...t);
+    assert(a.length === 4);
+    assert(a[0] === 1);
+    assert(a[1] === 2);
+    assert(a[2] === 3);
+    assert(a[3] === 4);
+
     console.log("PASS");
 } catch (e) {
     console.log("FAIL: " + e);
diff --git a/Libraries/LibJS/Tests/Object.defineProperty.js b/Libraries/LibJS/Tests/Object.defineProperty.js
index 846b62ddfa..db12bb38bb 100644
--- a/Libraries/LibJS/Tests/Object.defineProperty.js
+++ b/Libraries/LibJS/Tests/Object.defineProperty.js
@@ -7,6 +7,8 @@ try {
     assert(o.foo === 1);
     o.foo = 2;
     assert(o.foo === 1);
+    Object.defineProperty(o, 2, { get() { return 10; } });
+    assert(o[2] === 10);
 
     var d = Object.getOwnPropertyDescriptor(o, "foo");
     assert(d.configurable === false);
diff --git a/Libraries/LibJS/Tests/array-basic.js b/Libraries/LibJS/Tests/array-basic.js
index b39bcda134..57e0b5d624 100644
--- a/Libraries/LibJS/Tests/array-basic.js
+++ b/Libraries/LibJS/Tests/array-basic.js
@@ -40,6 +40,23 @@ try {
     assert(a[4] === undefined);
     assert(a[5] === 3);
 
+    a = [1,,2,,,3,];
+    Object.defineProperty(a, 1, {
+        get() {
+            return this.secret_prop;
+        },
+        set(value) {
+            this.secret_prop = value;
+        },
+    });
+    assert(a.length === 6);
+    assert(a.toString() === "1,,2,,,3");
+    assert(a.secret_prop === undefined);
+    a[1] = 20;
+    assert(a.length === 6);
+    assert(a.toString() === "1,20,2,,,3");
+    assert(a.secret_prop === 20);
+
     console.log("PASS");
 } catch (e) {
     console.log("FAIL: " + e);
diff --git a/Libraries/LibWeb/Bindings/DocumentWrapper.cpp b/Libraries/LibWeb/Bindings/DocumentWrapper.cpp
index d9bf59f45d..ced42bac05 100644
--- a/Libraries/LibWeb/Bindings/DocumentWrapper.cpp
+++ b/Libraries/LibWeb/Bindings/DocumentWrapper.cpp
@@ -119,7 +119,7 @@ JS::Value DocumentWrapper::query_selector_all(JS::Interpreter& interpreter)
     // FIXME: This should be a static NodeList, not a plain JS::Array.
     auto* node_list = JS::Array::create(interpreter.global_object());
     for (auto& element : elements) {
-        node_list->elements().append(wrap(interpreter.heap(), element));
+        node_list->indexed_properties().append(wrap(interpreter.heap(), element));
     }
     return node_list;
 }
diff --git a/Libraries/LibWeb/Bindings/NavigatorObject.cpp b/Libraries/LibWeb/Bindings/NavigatorObject.cpp
index 54d6077b06..6d018e69d5 100644
--- a/Libraries/LibWeb/Bindings/NavigatorObject.cpp
+++ b/Libraries/LibWeb/Bindings/NavigatorObject.cpp
@@ -38,12 +38,12 @@ NavigatorObject::NavigatorObject()
     : Object(interpreter().global_object().object_prototype())
 {
     auto* languages = JS::Array::create(interpreter().global_object());
-    languages->elements().append(js_string(heap(), "en-US"));
+    languages->indexed_properties().append(js_string(heap(), "en-US"));
 
     define_property("appCodeName", js_string(heap(), "Mozilla"));
     define_property("appName", js_string(heap(), "Netscape"));
     define_property("appVersion", js_string(heap(), "4.0"));
-    define_property("language", languages->elements().first());
+    define_property("language", languages->get(0));
     define_property("languages", languages);
     define_property("platform", js_string(heap(), "SerenityOS"));
     define_property("product", js_string(heap(), "Gecko"));