LibJS: Add a number-indexed property storage to all Objects

Objects can have both named and indexed properties. Previously we kept
all property names as strings. This patch separates named and indexed
properties and splits them between Object::m_storage and m_elements.

This allows us to do much faster array-style access using numeric
indices. It also makes the Array class much less special, since all
Objects now have number-indexed storage. :^)

5 files changed, 57 insertions, 49 deletions

diff --git a/Libraries/LibJS/Runtime/Array.cpp b/Libraries/LibJS/Runtime/Array.cpp
index 019697fe74..e779630c2c 100644
--- a/Libraries/LibJS/Runtime/Array.cpp
+++ b/Libraries/LibJS/Runtime/Array.cpp
@@ -43,52 +43,21 @@ Array::~Array()
 
 Value Array::shift()
 {
-    if (m_elements.size() == 0)
+    if (elements().size() == 0)
         return js_undefined();
-    return Value(m_elements.take_first());
+    return Value(elements().take_first());
 }
 
 Value Array::pop()
 {
-    if (m_elements.size() == 0)
+    if (elements().size() == 0)
         return js_undefined();
-    return Value(m_elements.take_last());
+    return Value(elements().take_last());
 }
 
 void Array::push(Value value)
 {
-    m_elements.append(value);
-}
-
-void Array::visit_children(Cell::Visitor& visitor)
-{
-    Object::visit_children(visitor);
-    for (auto& element : m_elements)
-        visitor.visit(element);
-}
-
-Optional<Value> Array::get_own_property(const Object& this_object, const FlyString& property_name) const
-{
-    bool ok;
-    i32 index = property_name.to_int(ok);
-    if (ok) {
-        if (index >= 0 && index < length())
-            return m_elements[index];
-    }
-    return Object::get_own_property(this_object, property_name);
-}
-
-bool Array::put_own_property(Object& this_object, const FlyString& property_name, Value value)
-{
-    bool ok;
-    i32 index = property_name.to_int(ok);
-    if (ok && index >= 0) {
-        if (index >= length())
-            m_elements.resize(index + 1);
-        m_elements[index] = value;
-        return true;
-    }
-    return Object::put_own_property(this_object, property_name, value);
+    elements().append(value);
 }
 
 Value Array::length_getter(Interpreter& interpreter)
diff --git a/Libraries/LibJS/Runtime/Array.h b/Libraries/LibJS/Runtime/Array.h
index 61c45644a0..10906e0256 100644
--- a/Libraries/LibJS/Runtime/Array.h
+++ b/Libraries/LibJS/Runtime/Array.h
@@ -35,9 +35,7 @@ public:
     Array();
     virtual ~Array() override;
 
-    i32 length() const { return static_cast<i32>(m_elements.size()); }
-    const Vector<Value>& elements() const { return m_elements; }
-    Vector<Value>& elements() { return m_elements; }
+    i32 length() const { return static_cast<i32>(elements().size()); }
 
     Value shift();
     Value pop();
@@ -45,15 +43,10 @@ public:
 
 private:
     virtual const char* class_name() const override { return "Array"; }
-    virtual void visit_children(Cell::Visitor&) override;
     virtual bool is_array() const override { return true; }
-    virtual Optional<Value> get_own_property(const Object& this_object, const FlyString& property_name) const override;
-    virtual bool put_own_property(Object& this_object, const FlyString& property_name, Value) override;
 
     static Value length_getter(Interpreter&);
     static void length_setter(Interpreter&, Value);
-
-    Vector<Value> m_elements;
 };
 
 }
diff --git a/Libraries/LibJS/Runtime/Object.cpp b/Libraries/LibJS/Runtime/Object.cpp
index 18185cc116..9751ddc0fd 100644
--- a/Libraries/LibJS/Runtime/Object.cpp
+++ b/Libraries/LibJS/Runtime/Object.cpp
@@ -119,8 +119,27 @@ bool Object::put_own_property(Object& this_object, const FlyString& property_nam
     return true;
 }
 
+Optional<Value> Object::get_by_index(i32 property_index) const
+{
+    if (property_index < 0)
+        return get(String::number(property_index));
+
+    const Object* object = this;
+    while (object) {
+        if (static_cast<size_t>(property_index) < object->m_elements.size())
+            return object->m_elements[property_index];
+        object = object->prototype();
+    }
+    return {};
+}
+
 Optional<Value> Object::get(const FlyString& property_name) const
 {
+    bool ok;
+    i32 property_index = property_name.to_int(ok);
+    if (ok && property_index >= 0)
+        return get_by_index(property_index);
+
     const Object* object = this;
     while (object) {
         auto value = object->get_own_property(*this, property_name);
@@ -131,8 +150,23 @@ Optional<Value> Object::get(const FlyString& property_name) const
     return {};
 }
 
+void Object::put_by_index(i32 property_index, Value value)
+{
+    if (property_index < 0)
+        return put(String::number(property_index), value);
+    // FIXME: Implement some kind of sparse storage for arrays with huge indices.
+    if (static_cast<size_t>(property_index) >= m_elements.size())
+        m_elements.resize(property_index + 1);
+    m_elements[property_index] = value;
+}
+
 void Object::put(const FlyString& property_name, Value value)
 {
+    bool ok;
+    i32 property_index = property_name.to_int(ok);
+    if (ok && property_index >= 0)
+        return put_by_index(property_index, value);
+
     // 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;
@@ -174,10 +208,17 @@ void Object::visit_children(Cell::Visitor& visitor)
 
     for (auto& value : m_storage)
         visitor.visit(value);
+
+    for (auto& value : m_elements)
+        visitor.visit(value);
 }
 
 bool Object::has_own_property(const FlyString& property_name) const
 {
+    bool ok;
+    i32 property_index = property_name.to_int(ok);
+    if (ok && property_index >= 0)
+        return static_cast<size_t>(property_index) < m_elements.size();
     return shape().lookup(property_name).has_value();
 }
 
diff --git a/Libraries/LibJS/Runtime/Object.h b/Libraries/LibJS/Runtime/Object.h
index f47b35ac72..529fdb92cc 100644
--- a/Libraries/LibJS/Runtime/Object.h
+++ b/Libraries/LibJS/Runtime/Object.h
@@ -43,7 +43,10 @@ public:
     Shape& shape() { return *m_shape; }
     const Shape& shape() const { return *m_shape; }
 
+    Optional<Value> get_by_index(i32 property_index) const;
     Optional<Value> get(const FlyString& property_name) const;
+
+    void put_by_index(i32 property_index, Value);
     void put(const FlyString& property_name, Value);
 
     virtual Optional<Value> get_own_property(const Object& this_object, const FlyString& property_name) const;
@@ -81,11 +84,15 @@ 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; }
+
 private:
     void set_shape(Shape&);
 
     Shape* m_shape { nullptr };
     Vector<Value> m_storage;
+    Vector<Value> m_elements;
 };
 
 }
diff --git a/Libraries/LibJS/Runtime/ObjectConstructor.cpp b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
index 41376b5cbc..f56ae2f161 100644
--- a/Libraries/LibJS/Runtime/ObjectConstructor.cpp
+++ b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
@@ -64,11 +64,9 @@ Value ObjectConstructor::get_own_property_names(Interpreter& interpreter)
     if (interpreter.exception())
         return {};
     auto* result = interpreter.heap().allocate<Array>();
-    if (object->is_array()) {
-        auto* array = static_cast<const Array*>(object);
-        for (i32 i = 0; i < array->length(); ++i)
-            result->push(js_string(interpreter, String::number(i)));
-    }
+    for (size_t i = 0; i < object->elements().size(); ++i)
+        result->push(js_string(interpreter, String::number(i)));
+
     for (auto& it : object->shape().property_table())
         result->push(js_string(interpreter, it.key));
     return result;