LibJS: Support array holes, encoded as empty JS::Value

This patch adds a new kind of JS::Value, the empty value.
It's what you get when you do JSValue() (or most commonly, {} in C++.)

An empty Value signifies the absence of a value, and should never be
visible to JavaScript itself. As of right now, it's used for array
holes and as a return value when an exception has been thrown and we
just want to unwind.

This patch is a bit of a mess as I had to fix a whole bunch of code
that was relying on JSValue() being undefined, etc.

7 files changed, 96 insertions, 31 deletions

diff --git a/Libraries/LibJS/AST.cpp b/Libraries/LibJS/AST.cpp
index cbab937bec..bb6eb6f8d0 100644
--- a/Libraries/LibJS/AST.cpp
+++ b/Libraries/LibJS/AST.cpp
@@ -49,7 +49,7 @@ Value FunctionDeclaration::execute(Interpreter& interpreter) const
 {
     auto* function = interpreter.heap().allocate<ScriptFunction>(body(), parameters());
     interpreter.set_variable(name(), function);
-    return {};
+    return js_undefined();
 }
 
 Value FunctionExpression::execute(Interpreter& interpreter) const
@@ -66,7 +66,7 @@ CallExpression::ThisAndCallee CallExpression::compute_this_and_callee(Interprete
 {
     if (is_new_expression()) {
         // Computing |this| is irrelevant for "new" expression.
-        return { {}, m_callee->execute(interpreter) };
+        return { js_undefined(), m_callee->execute(interpreter) };
     }
 
     if (m_callee->is_member_expression()) {
@@ -77,7 +77,7 @@ CallExpression::ThisAndCallee CallExpression::compute_this_and_callee(Interprete
         auto* this_value = object_value.to_object(interpreter.heap());
         if (interpreter.exception())
             return {};
-        auto callee = this_value->get(member_expression.computed_property_name(interpreter)).value_or({});
+        auto callee = this_value->get(member_expression.computed_property_name(interpreter)).value_or(js_undefined());
         return { this_value, callee };
     }
     return { &interpreter.global_object(), m_callee->execute(interpreter) };
@@ -89,6 +89,8 @@ Value CallExpression::execute(Interpreter& interpreter) const
     if (interpreter.exception())
         return {};
 
+    ASSERT(!callee.is_empty());
+
     if (is_new_expression()) {
         if (!callee.is_object()
             || !callee.as_object().is_function()
@@ -130,6 +132,9 @@ Value CallExpression::execute(Interpreter& interpreter) const
         result = function.call(interpreter);
     }
 
+    if (interpreter.exception())
+        return {};
+
     interpreter.pop_call_frame();
 
     if (is_new_expression()) {
@@ -161,7 +166,7 @@ Value IfStatement::execute(Interpreter& interpreter) const
     if (m_alternate)
         return interpreter.run(*m_alternate);
 
-    return {};
+    return js_undefined();
 }
 
 Value WhileStatement::execute(Interpreter& interpreter) const
@@ -228,7 +233,7 @@ Value ForStatement::execute(Interpreter& interpreter) const
                     interpreter.stop_unwind();
                     break;
                 } else {
-                    return {};
+                    return js_undefined();
                 }
             }
             if (m_update) {
@@ -249,7 +254,7 @@ Value ForStatement::execute(Interpreter& interpreter) const
                     interpreter.stop_unwind();
                     break;
                 } else {
-                    return {};
+                    return js_undefined();
                 }
             }
             if (m_update) {
@@ -352,6 +357,8 @@ Value LogicalExpression::execute(Interpreter& interpreter) const
 Value UnaryExpression::execute(Interpreter& interpreter) const
 {
     auto lhs_result = m_lhs->execute(interpreter);
+    if (interpreter.exception())
+        return {};
     switch (m_op) {
     case UnaryOp::BitwiseNot:
         return bitwise_not(lhs_result);
@@ -363,6 +370,9 @@ Value UnaryExpression::execute(Interpreter& interpreter) const
         return unary_minus(lhs_result);
     case UnaryOp::Typeof:
         switch (lhs_result.type()) {
+        case Value::Type::Empty:
+            ASSERT_NOT_REACHED();
+            return {};
         case Value::Type::Undefined:
             return js_string(interpreter, "undefined");
         case Value::Type::Null:
@@ -528,7 +538,8 @@ void UnaryExpression::dump(int indent) const
 
 void CallExpression::dump(int indent) const
 {
-    ASTNode::dump(indent);
+    print_indent(indent);
+    printf("CallExpression %s\n", is_new_expression() ? "[new]" : "");
     m_callee->dump(indent + 1);
     for (auto& argument : m_arguments)
         argument.dump(indent + 1);
@@ -655,20 +666,33 @@ Value AssignmentExpression::execute(Interpreter& interpreter) const
     if (interpreter.exception())
         return {};
 
+    Value lhs_result;
     switch (m_op) {
     case AssignmentOp::Assignment:
         break;
     case AssignmentOp::AdditionAssignment:
-        rhs_result = add(m_lhs->execute(interpreter), rhs_result);
+        lhs_result = m_lhs->execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        rhs_result = add(lhs_result, rhs_result);
         break;
     case AssignmentOp::SubtractionAssignment:
-        rhs_result = sub(m_lhs->execute(interpreter), rhs_result);
+        lhs_result = m_lhs->execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        rhs_result = sub(lhs_result, rhs_result);
         break;
     case AssignmentOp::MultiplicationAssignment:
-        rhs_result = mul(m_lhs->execute(interpreter), rhs_result);
+        lhs_result = m_lhs->execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        rhs_result = mul(lhs_result, rhs_result);
         break;
     case AssignmentOp::DivisionAssignment:
-        rhs_result = div(m_lhs->execute(interpreter), rhs_result);
+        lhs_result = m_lhs->execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        rhs_result = div(lhs_result, rhs_result);
         break;
     }
     if (interpreter.exception())
@@ -678,7 +702,10 @@ Value AssignmentExpression::execute(Interpreter& interpreter) const
         auto name = static_cast<const Identifier&>(*m_lhs).string();
         interpreter.set_variable(name, rhs_result);
     } else if (m_lhs->is_member_expression()) {
-        if (auto* object = static_cast<const MemberExpression&>(*m_lhs).object().execute(interpreter).to_object(interpreter.heap())) {
+        auto object_value = static_cast<const MemberExpression&>(*m_lhs).object().execute(interpreter);
+        if (interpreter.exception())
+            return {};
+        if (auto* object = object_value.to_object(interpreter.heap())) {
             auto property_name = static_cast<const MemberExpression&>(*m_lhs).computed_property_name(interpreter);
             object->put(property_name, rhs_result);
         }
@@ -779,7 +806,7 @@ Value VariableDeclaration::execute(Interpreter& interpreter) const
             interpreter.set_variable(declarator.id().string(), initalizer_result, true);
         }
     }
-    return {};
+    return js_undefined();
 }
 
 Value VariableDeclarator::execute(Interpreter&) const
@@ -862,6 +889,9 @@ PropertyName MemberExpression::computed_property_name(Interpreter& interpreter)
         return PropertyName(static_cast<const Identifier&>(*m_property).string());
     }
     auto index = m_property->execute(interpreter);
+    if (interpreter.exception())
+        return {};
+    ASSERT(!index.is_empty());
     // FIXME: What about non-integer numbers tho.
     if (index.is_number())
         return PropertyName(index.to_i32());
@@ -870,11 +900,17 @@ PropertyName MemberExpression::computed_property_name(Interpreter& interpreter)
 
 Value MemberExpression::execute(Interpreter& interpreter) const
 {
-    auto* object_result = m_object->execute(interpreter).to_object(interpreter.heap());
+    auto object_value = m_object->execute(interpreter);
+    if (interpreter.exception())
+        return {};
+    auto* object_result = object_value.to_object(interpreter.heap());
     if (interpreter.exception())
         return {};
     auto result = object_result->get(computed_property_name(interpreter));
-    return result.value_or({});
+    if (result.has_value()) {
+        ASSERT(!result.value().is_empty());
+    }
+    return result.value_or(js_undefined());
 }
 
 Value StringLiteral::execute(Interpreter& interpreter) const
@@ -967,7 +1003,7 @@ Value TryStatement::execute(Interpreter& interpreter) const
     if (m_finalizer)
         m_finalizer->execute(interpreter);
 
-    return {};
+    return js_undefined();
 }
 
 Value CatchClause::execute(Interpreter&) const
@@ -1017,7 +1053,7 @@ Value SwitchStatement::execute(Interpreter& interpreter) const
         }
     }
 
-    return {};
+    return js_undefined();
 }
 
 Value SwitchCase::execute(Interpreter& interpreter) const
@@ -1029,13 +1065,13 @@ Value SwitchCase::execute(Interpreter& interpreter) const
 Value BreakStatement::execute(Interpreter& interpreter) const
 {
     interpreter.unwind(ScopeType::Breakable);
-    return {};
+    return js_undefined();
 }
 
 Value ContinueStatement::execute(Interpreter& interpreter) const
 {
     interpreter.unwind(ScopeType::Continuable);
-    return {};
+    return js_undefined();
 }
 
 void SwitchStatement::dump(int indent) const
diff --git a/Libraries/LibJS/Interpreter.cpp b/Libraries/LibJS/Interpreter.cpp
index e7fb481abb..b8dbad53c3 100644
--- a/Libraries/LibJS/Interpreter.cpp
+++ b/Libraries/LibJS/Interpreter.cpp
@@ -69,7 +69,7 @@ Value Interpreter::run(const Statement& statement, ArgumentVector arguments, Sco
     auto& block = static_cast<const ScopeNode&>(statement);
     enter_scope(block, move(arguments), scope_type);
 
-    m_last_value = {};
+    m_last_value = js_undefined();
     for (auto& node : block.children()) {
         m_last_value = node.execute(*this);
         if (m_unwind_until != ScopeType::None)
diff --git a/Libraries/LibJS/Runtime/Object.cpp b/Libraries/LibJS/Runtime/Object.cpp
index e0bbbe3190..da570ee785 100644
--- a/Libraries/LibJS/Runtime/Object.cpp
+++ b/Libraries/LibJS/Runtime/Object.cpp
@@ -77,6 +77,7 @@ Optional<Value> Object::get_own_property(const Object& this_object, const FlyStr
         return {};
 
     auto value_here = m_storage[metadata.value().offset];
+    ASSERT(!value_here.is_empty());
     if (value_here.is_object() && value_here.as_object().is_native_property()) {
         auto& native_property = static_cast<const NativeProperty&>(value_here.as_object());
         auto& interpreter = const_cast<Object*>(this)->interpreter();
@@ -126,8 +127,12 @@ Optional<Value> Object::get_by_index(i32 property_index) const
 
     const Object* object = this;
     while (object) {
-        if (static_cast<size_t>(property_index) < object->m_elements.size())
-            return object->m_elements[property_index];
+        if (static_cast<size_t>(property_index) < object->m_elements.size()) {
+            auto value = object->m_elements[property_index];
+            if (value.is_empty())
+                return {};
+            return value;
+        }
         object = object->prototype();
     }
     return {};
@@ -159,6 +164,7 @@ Optional<Value> Object::get(PropertyName property_name) const
 
 void Object::put_by_index(i32 property_index, Value value)
 {
+    ASSERT(!value.is_empty());
     if (property_index < 0)
         return put(String::number(property_index), value);
     // FIXME: Implement some kind of sparse storage for arrays with huge indices.
@@ -169,6 +175,7 @@ void Object::put_by_index(i32 property_index, Value value)
 
 void Object::put(const FlyString& property_name, Value value)
 {
+    ASSERT(!value.is_empty());
     bool ok;
     i32 property_index = property_name.to_int(ok);
     if (ok && property_index >= 0)
@@ -231,8 +238,11 @@ 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();
+    if (ok && property_index >= 0) {
+        if (static_cast<size_t>(property_index) >= m_elements.size())
+            return false;
+        return !m_elements[property_index].is_empty();
+    }
     return shape().lookup(property_name).has_value();
 }
 
diff --git a/Libraries/LibJS/Runtime/ObjectConstructor.cpp b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
index f56ae2f161..bef6ceff1e 100644
--- a/Libraries/LibJS/Runtime/ObjectConstructor.cpp
+++ b/Libraries/LibJS/Runtime/ObjectConstructor.cpp
@@ -64,8 +64,10 @@ Value ObjectConstructor::get_own_property_names(Interpreter& interpreter)
     if (interpreter.exception())
         return {};
     auto* result = interpreter.heap().allocate<Array>();
-    for (size_t i = 0; i < object->elements().size(); ++i)
-        result->push(js_string(interpreter, String::number(i)));
+    for (size_t i = 0; i < object->elements().size(); ++i) {
+        if (!object->elements()[i].is_empty())
+            result->push(js_string(interpreter, String::number(i)));
+    }
 
     for (auto& it : object->shape().property_table())
         result->push(js_string(interpreter, it.key));
diff --git a/Libraries/LibJS/Runtime/PropertyName.h b/Libraries/LibJS/Runtime/PropertyName.h
index 6965cb5bdf..49542c81c5 100644
--- a/Libraries/LibJS/Runtime/PropertyName.h
+++ b/Libraries/LibJS/Runtime/PropertyName.h
@@ -33,10 +33,13 @@ namespace JS {
 class PropertyName {
 public:
     enum class Type {
+        Invalid,
         Number,
         String,
     };
 
+    PropertyName() {}
+
     explicit PropertyName(i32 index)
         : m_type(Type::Number)
         , m_number(index)
@@ -50,6 +53,7 @@ public:
     {
     }
 
+    bool is_valid() const { return m_type != Type::Invalid; }
     bool is_number() const { return m_type == Type::Number; }
     bool is_string() const { return m_type == Type::String; }
 
@@ -57,7 +61,7 @@ public:
     const FlyString& as_string() const { return m_string; }
 
 private:
-    Type m_type;
+    Type m_type { Type::Invalid };
     FlyString m_string;
     i32 m_number { 0 };
 };
diff --git a/Libraries/LibJS/Runtime/Value.cpp b/Libraries/LibJS/Runtime/Value.cpp
index ea0594245f..cf85045799 100644
--- a/Libraries/LibJS/Runtime/Value.cpp
+++ b/Libraries/LibJS/Runtime/Value.cpp
@@ -39,6 +39,14 @@
 
 namespace JS {
 
+Value::Value()
+    : m_type(Type::Empty)
+{
+ //   dbg() << "Create empty value";
+   // dump_backtrace();
+}
+
+
 bool Value::is_array() const
 {
     return is_object() && as_object().is_array();
@@ -119,6 +127,9 @@ Object* Value::to_object(Heap& heap) const
 Value Value::to_number() const
 {
     switch (m_type) {
+    case Type::Empty:
+        ASSERT_NOT_REACHED();
+        return {};
     case Type::Boolean:
         return Value(m_value.as_bool ? 1 : 0);
     case Type::Number:
@@ -280,6 +291,9 @@ Value typed_eq(Value lhs, Value rhs)
         return Value(false);
 
     switch (lhs.type()) {
+    case Value::Type::Empty:
+        ASSERT_NOT_REACHED();
+        return {};
     case Value::Type::Undefined:
         return Value(true);
     case Value::Type::Null:
diff --git a/Libraries/LibJS/Runtime/Value.h b/Libraries/LibJS/Runtime/Value.h
index b6d30c80f1..f6240c316f 100644
--- a/Libraries/LibJS/Runtime/Value.h
+++ b/Libraries/LibJS/Runtime/Value.h
@@ -36,6 +36,7 @@ namespace JS {
 class Value {
 public:
     enum class Type {
+        Empty,
         Undefined,
         Null,
         Number,
@@ -44,6 +45,7 @@ public:
         Boolean,
     };
 
+    bool is_empty() const { return m_type == Type::Empty; }
     bool is_undefined() const { return m_type == Type::Undefined; }
     bool is_null() const { return m_type == Type::Null; }
     bool is_number() const { return m_type == Type::Number; }
@@ -56,10 +58,7 @@ public:
     bool is_nan() const { return is_number() && __builtin_isnan(as_double()); }
     bool is_infinity() const { return is_number() && __builtin_isinf(as_double()); }
 
-    Value()
-        : m_type(Type::Undefined)
-    {
-    }
+    Value();
 
     explicit Value(bool value)
         : m_type(Type::Boolean)