LibJS: Implement basic support for the "delete" operator

It turns out "delete" is actually a unary op :)
This patch implements deletion of object properties, it doesn't yet
work for casually deleting properties from the global object.

When deleting a property from an object, we switch that object to
having a unique shape, no longer sharing shapes with others.
Once an object has a unique shape, it no longer needs to care about
shape transitions.

9 files changed, 190 insertions, 8 deletions

diff --git a/Libraries/LibJS/AST.cpp b/Libraries/LibJS/AST.cpp
index 8c27bf549c..2633cb6da4 100644
--- a/Libraries/LibJS/AST.cpp
+++ b/Libraries/LibJS/AST.cpp
@@ -378,6 +378,21 @@ Value LogicalExpression::execute(Interpreter& interpreter) const
 
 Value UnaryExpression::execute(Interpreter& interpreter) const
 {
+    if (m_op == UnaryOp::Delete) {
+        if (!m_lhs->is_member_expression())
+            return Value(true);
+        auto object_value = static_cast<const MemberExpression&>(*m_lhs).object().execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        auto* object = object_value.to_object(interpreter.heap());
+        if (!object)
+            return {};
+        auto property_name = static_cast<const MemberExpression&>(*m_lhs).computed_property_name(interpreter);
+        if (!property_name.is_valid())
+            return {};
+        return object->delete_property(property_name);
+    }
+
     auto lhs_result = m_lhs->execute(interpreter);
     if (interpreter.exception())
         return {};
@@ -416,6 +431,8 @@ Value UnaryExpression::execute(Interpreter& interpreter) const
         }
     case UnaryOp::Void:
         return js_undefined();
+    case UnaryOp::Delete:
+        ASSERT_NOT_REACHED();
     }
 
     ASSERT_NOT_REACHED();
@@ -575,6 +592,9 @@ void UnaryExpression::dump(int indent) const
     case UnaryOp::Void:
         op_string = "void ";
         break;
+    case UnaryOp::Delete:
+        op_string = "delete ";
+        break;
     }
 
     print_indent(indent);
diff --git a/Libraries/LibJS/AST.h b/Libraries/LibJS/AST.h
index ba37df528a..bec3f2910a 100644
--- a/Libraries/LibJS/AST.h
+++ b/Libraries/LibJS/AST.h
@@ -400,6 +400,7 @@ enum class UnaryOp {
     Minus,
     Typeof,
     Void,
+    Delete,
 };
 
 class UnaryExpression : public Expression {
diff --git a/Libraries/LibJS/Parser.cpp b/Libraries/LibJS/Parser.cpp
index 7855501f30..caf0e7da75 100644
--- a/Libraries/LibJS/Parser.cpp
+++ b/Libraries/LibJS/Parser.cpp
@@ -187,6 +187,7 @@ Associativity Parser::operator_associativity(TokenType type) const
     case TokenType::ExclamationMarkEqualsEquals:
     case TokenType::Typeof:
     case TokenType::Void:
+    case TokenType::Delete:
     case TokenType::Ampersand:
     case TokenType::Caret:
     case TokenType::Pipe:
@@ -425,6 +426,9 @@ NonnullRefPtr<Expression> Parser::parse_unary_prefixed_expression()
     case TokenType::Void:
         consume();
         return create_ast_node<UnaryExpression>(UnaryOp::Void, parse_expression(precedence, associativity));
+    case TokenType::Delete:
+        consume();
+        return create_ast_node<UnaryExpression>(UnaryOp::Delete, parse_expression(precedence, associativity));
     default:
         m_parser_state.m_has_errors = true;
         expected("primary expression (missing switch case)");
@@ -1059,7 +1063,8 @@ bool Parser::match_unary_prefixed_expression() const
         || type == TokenType::Plus
         || type == TokenType::Minus
         || type == TokenType::Typeof
-        || type == TokenType::Void;
+        || type == TokenType::Void
+        || type == TokenType::Delete;
 }
 
 bool Parser::match_secondary_expression() const
@@ -1114,7 +1119,6 @@ bool Parser::match_statement() const
         || type == TokenType::Return
         || type == TokenType::Let
         || type == TokenType::Class
-        || type == TokenType::Delete
         || type == TokenType::Do
         || type == TokenType::If
         || type == TokenType::Throw
diff --git a/Libraries/LibJS/Runtime/Object.cpp b/Libraries/LibJS/Runtime/Object.cpp
index 0950660999..e0d757395e 100644
--- a/Libraries/LibJS/Runtime/Object.cpp
+++ b/Libraries/LibJS/Runtime/Object.cpp
@@ -71,6 +71,10 @@ void Object::set_prototype(Object* new_prototype)
 {
     if (prototype() == new_prototype)
         return;
+    if (shape().is_unique()) {
+        shape().set_prototype_without_transition(new_prototype);
+        return;
+    }
     m_shape = m_shape->create_prototype_transition(new_prototype);
 }
 
@@ -113,8 +117,11 @@ void Object::put_own_property(Object& this_object, const FlyString& property_nam
 {
     auto metadata = shape().lookup(property_name);
     if (!metadata.has_value()) {
-        auto* new_shape = m_shape->create_put_transition(property_name, attributes);
-        set_shape(*new_shape);
+        if (m_shape->is_unique()) {
+            m_shape->add_property_to_unique_shape(property_name, attributes);
+        } else {
+            set_shape(*m_shape->create_put_transition(property_name, attributes));
+        }
         metadata = shape().lookup(property_name);
         ASSERT(metadata.has_value());
     }
@@ -126,8 +133,11 @@ void Object::put_own_property(Object& this_object, const FlyString& property_nam
     }
 
     if (mode == PutOwnPropertyMode::DefineProperty && attributes != metadata.value().attributes) {
-        auto* new_shape = m_shape->create_configure_transition(property_name, attributes);
-        set_shape(*new_shape);
+        if (m_shape->is_unique()) {
+            m_shape->reconfigure_property_in_unique_shape(property_name, attributes);
+        } else {
+            set_shape(*m_shape->create_configure_transition(property_name, attributes));
+        }
         metadata = shape().lookup(property_name);
 
         dbg() << "Reconfigured property " << property_name << ", new shape says offset is " << metadata.value().offset << " and my storage capacity is " << m_storage.size();
@@ -154,6 +164,39 @@ void Object::put_own_property(Object& this_object, const FlyString& property_nam
     }
 }
 
+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);
+    }
+    auto metadata = shape().lookup(property_name.as_string());
+    if (!metadata.has_value())
+        return Value(true);
+    if (!(metadata.value().attributes & Attribute::Configurable))
+        return Value(false);
+
+    size_t deleted_offset = metadata.value().offset;
+
+    ensure_shape_is_unique();
+
+    shape().remove_property_from_unique_shape(property_name.as_string(), deleted_offset);
+    m_storage.remove(deleted_offset);
+    return Value(true);
+}
+
+void Object::ensure_shape_is_unique()
+{
+    if (shape().is_unique())
+        return;
+
+    m_shape = m_shape->create_unique_clone();
+}
+
 Value Object::get_by_index(i32 property_index) const
 {
     if (property_index < 0)
diff --git a/Libraries/LibJS/Runtime/Object.h b/Libraries/LibJS/Runtime/Object.h
index 0b0ccc4fcc..5c945ea888 100644
--- a/Libraries/LibJS/Runtime/Object.h
+++ b/Libraries/LibJS/Runtime/Object.h
@@ -46,6 +46,8 @@ public:
     Shape& shape() { return *m_shape; }
     const Shape& shape() const { return *m_shape; }
 
+    Value delete_property(PropertyName);
+
     virtual Value get_by_index(i32 property_index) const;
     Value get(const FlyString& property_name) const;
     Value get(PropertyName) const;
@@ -102,6 +104,7 @@ public:
 
 private:
     void set_shape(Shape&);
+    void ensure_shape_is_unique();
 
     Shape* m_shape { nullptr };
     Vector<Value> m_storage;
diff --git a/Libraries/LibJS/Runtime/ObjectConstructor.cpp b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
index 34fea44646..1fcbe4e8e2 100644
--- a/Libraries/LibJS/Runtime/ObjectConstructor.cpp
+++ b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
@@ -75,8 +75,9 @@ Value ObjectConstructor::get_own_property_names(Interpreter& interpreter)
             result->elements().append(js_string(interpreter, String::number(i)));
     }
 
-    for (auto& it : object->shape().property_table())
+    for (auto& it : object->shape().property_table()) {
         result->elements().append(js_string(interpreter, it.key));
+    }
     return result;
 }
 
diff --git a/Libraries/LibJS/Runtime/Shape.cpp b/Libraries/LibJS/Runtime/Shape.cpp
index cbc7649c81..d03ad74a36 100644
--- a/Libraries/LibJS/Runtime/Shape.cpp
+++ b/Libraries/LibJS/Runtime/Shape.cpp
@@ -29,6 +29,17 @@
 
 namespace JS {
 
+Shape* Shape::create_unique_clone() const
+{
+    auto* new_shape = heap().allocate<Shape>();
+    new_shape->m_unique = true;
+    new_shape->m_prototype = m_prototype;
+    ensure_property_table();
+    new_shape->ensure_property_table();
+    (*new_shape->m_property_table) = *m_property_table;
+    return new_shape;
+}
+
 Shape* Shape::create_put_transition(const FlyString& property_name, u8 attributes)
 {
     TransitionKey key { property_name, attributes };
@@ -89,7 +100,10 @@ void Shape::visit_children(Cell::Visitor& visitor)
 
 Optional<PropertyMetadata> Shape::lookup(const FlyString& property_name) const
 {
-    return property_table().get(property_name);
+    auto property = property_table().get(property_name);
+    if (!property.has_value())
+        return {};
+    return property;
 }
 
 const HashMap<FlyString, PropertyMetadata>& Shape::property_table() const
@@ -134,4 +148,32 @@ void Shape::ensure_property_table() const
     }
 }
 
+void Shape::add_property_to_unique_shape(const FlyString& property_name, u8 attributes)
+{
+    ASSERT(is_unique());
+    ASSERT(m_property_table);
+    ASSERT(!m_property_table->contains(property_name));
+    m_property_table->set(property_name, { m_property_table->size(), attributes });
+}
+
+void Shape::reconfigure_property_in_unique_shape(const FlyString& property_name, u8 attributes)
+{
+    ASSERT(is_unique());
+    ASSERT(m_property_table);
+    ASSERT(m_property_table->contains(property_name));
+    m_property_table->set(property_name, { m_property_table->size(), attributes });
+}
+
+void Shape::remove_property_from_unique_shape(const FlyString& property_name, size_t offset)
+{
+    ASSERT(is_unique());
+    ASSERT(m_property_table);
+    m_property_table->remove(property_name);
+    for (auto& it : *m_property_table) {
+        ASSERT(it.value.offset != offset);
+        if (it.value.offset > offset)
+            --it.value.offset;
+    }
+}
+
 }
diff --git a/Libraries/LibJS/Runtime/Shape.h b/Libraries/LibJS/Runtime/Shape.h
index 70c75fef78..26c8eb574b 100644
--- a/Libraries/LibJS/Runtime/Shape.h
+++ b/Libraries/LibJS/Runtime/Shape.h
@@ -78,6 +78,9 @@ public:
     Shape* create_configure_transition(const FlyString& name, u8 attributes);
     Shape* create_prototype_transition(Object* new_prototype);
 
+    bool is_unique() const { return m_unique; }
+    Shape* create_unique_clone() const;
+
     Object* prototype() { return m_prototype; }
     const Object* prototype() const { return m_prototype; }
 
@@ -87,6 +90,10 @@ public:
 
     void set_prototype_without_transition(Object* new_prototype) { m_prototype = new_prototype; }
 
+    void remove_property_from_unique_shape(const FlyString&, size_t offset);
+    void add_property_to_unique_shape(const FlyString&, u8 attributes);
+    void reconfigure_property_in_unique_shape(const FlyString& property_name, u8 attributes);
+
 private:
     virtual const char* class_name() const override { return "Shape"; }
     virtual void visit_children(Visitor&) override;
@@ -99,6 +106,7 @@ private:
     Shape* m_previous { nullptr };
     FlyString m_property_name;
     u8 m_attributes { 0 };
+    bool m_unique { false };
     Object* m_prototype { nullptr };
     TransitionType m_transition_type { TransitionType::Invalid };
 };
diff --git a/Libraries/LibJS/Tests/delete-basic.js b/Libraries/LibJS/Tests/delete-basic.js
new file mode 100644
index 0000000000..eda9741b6b
--- /dev/null
+++ b/Libraries/LibJS/Tests/delete-basic.js
@@ -0,0 +1,60 @@
+load("test-common.js");
+
+try {
+    o = {};
+    o.x = 1;
+    o.y = 2;
+    o.z = 3;
+    assert(Object.getOwnPropertyNames(o).length === 3);
+
+    assert(delete o.x === true);
+    assert(o.hasOwnProperty('x') === false);
+    assert(o.hasOwnProperty('y') === true);
+    assert(o.hasOwnProperty('z') === true);
+    assert(Object.getOwnPropertyNames(o).length === 2);
+
+    assert(delete o.y === true);
+    assert(o.hasOwnProperty('x') === false);
+    assert(o.hasOwnProperty('y') === false);
+    assert(o.hasOwnProperty('z') === true);
+    assert(Object.getOwnPropertyNames(o).length === 1);
+
+    assert(delete o.z === true);
+    assert(o.hasOwnProperty('x') === false);
+    assert(o.hasOwnProperty('y') === false);
+    assert(o.hasOwnProperty('z') === false);
+    assert(Object.getOwnPropertyNames(o).length === 0);
+
+    a = [ 3, 5, 7 ];
+
+    assert(Object.getOwnPropertyNames(a).length === 4);
+
+    assert(delete a[0] === true);
+    assert(a.hasOwnProperty(0) === false);
+    assert(a.hasOwnProperty(1) === true);
+    assert(a.hasOwnProperty(2) === true);
+    assert(Object.getOwnPropertyNames(a).length === 3);
+
+    assert(delete a[1] === true);
+    assert(a.hasOwnProperty(0) === false);
+    assert(a.hasOwnProperty(1) === false);
+    assert(a.hasOwnProperty(2) === true);
+    assert(Object.getOwnPropertyNames(a).length === 2);
+
+    assert(delete a[2] === true);
+    assert(a.hasOwnProperty(0) === false);
+    assert(a.hasOwnProperty(1) === false);
+    assert(a.hasOwnProperty(2) === false);
+    assert(Object.getOwnPropertyNames(a).length === 1);
+
+    q = {};
+    Object.defineProperty(q, "foo", { value: 1, writable: false, enumerable: false });
+    assert(q.foo === 1);
+
+    assert(delete q.foo === false);
+    assert(q.hasOwnProperty('foo') === true);
+
+    console.log("PASS");
+} catch (e) {
+    console.log("FAIL: " + e);
+}