AK: JsonParser improvements

- Parsing invalid JSON no longer asserts
    Instead of asserting when coming across malformed JSON,
    JsonParser::parse now returns an Optional<JsonValue>.
- Disallow trailing commas in JSON objects and arrays
- No longer parse 'undefined', as that is a purely JS thing
- No longer allow non-whitespace after anything consumed by the initial
  parse() call. Examples of things that were valid and no longer are:
    - undefineddfz
    - {"foo": 1}abcd
    - [1,2,3]4
- JsonObject.for_each_member now iterates in original insertion order

6 files changed, 119 insertions, 73 deletions

diff --git a/AK/JsonObject.h b/AK/JsonObject.h
index 5b95005495..aa177da18d 100644
--- a/AK/JsonObject.h
+++ b/AK/JsonObject.h
@@ -41,26 +41,32 @@ public:
     ~JsonObject() {}
 
     JsonObject(const JsonObject& other)
-        : m_members(other.m_members)
+        : m_order(other.m_order)
+        , m_members(other.m_members)
     {
     }
 
     JsonObject(JsonObject&& other)
-        : m_members(move(other.m_members))
+        : m_order(move(other.m_order))
+        , m_members(move(other.m_members))
     {
     }
 
     JsonObject& operator=(const JsonObject& other)
     {
-        if (this != &other)
+        if (this != &other) {
             m_members = other.m_members;
+            m_order = other.m_order;
+        }
         return *this;
     }
 
     JsonObject& operator=(JsonObject&& other)
     {
-        if (this != &other)
+        if (this != &other) {
             m_members = move(other.m_members);
+            m_order = move(other.m_order);
+        }
         return *this;
     }
 
@@ -70,7 +76,7 @@ public:
     JsonValue get(const String& key) const
     {
         auto* value = get_ptr(key);
-        return value ? *value : JsonValue(JsonValue::Type::Undefined);
+        return value ? *value : JsonValue(JsonValue::Type::Null);
     }
 
     JsonValue get_or(const String& key, JsonValue alternative) const
@@ -94,14 +100,17 @@ public:
 
     void set(const String& key, JsonValue value)
     {
+        m_order.append(key);
         m_members.set(key, move(value));
     }
 
     template<typename Callback>
     void for_each_member(Callback callback) const
     {
-        for (auto& it : m_members)
-            callback(it.key, it.value);
+        for (size_t i = 0; i < m_order.size(); ++i) {
+            auto property = m_order[i];
+            callback(property, m_members.get(property).value());
+        }
     }
 
     template<typename Builder>
@@ -113,6 +122,7 @@ public:
     String to_string() const { return serialized<StringBuilder>(); }
 
 private:
+    Vector<String> m_order;
     HashMap<String, JsonValue> m_members;
 };
 
@@ -193,9 +203,6 @@ inline void JsonValue::serialize(Builder& builder) const
     case Type::UnsignedInt64:
         builder.appendf("%llu", as_u64());
         break;
-    case Type::Undefined:
-        builder.append("undefined");
-        break;
     case Type::Null:
         builder.append("null");
         break;
diff --git a/AK/JsonParser.cpp b/AK/JsonParser.cpp
index 7a883a8b3a..142c797a47 100644
--- a/AK/JsonParser.cpp
+++ b/AK/JsonParser.cpp
@@ -62,15 +62,16 @@ void JsonParser::consume_whitespace()
     consume_while([](char ch) { return is_whitespace(ch); });
 }
 
-void JsonParser::consume_specific(char expected_ch)
+bool JsonParser::consume_specific(char expected_ch)
 {
     char consumed_ch = consume();
-    ASSERT(consumed_ch == expected_ch);
+    return consumed_ch == expected_ch;
 }
 
 String JsonParser::consume_quoted_string()
 {
-    consume_specific('"');
+    if (!consume_specific('"'))
+        return {};
     Vector<char, 1024> buffer;
 
     for (;;) {
@@ -136,7 +137,8 @@ String JsonParser::consume_quoted_string()
             break;
         }
     }
-    consume_specific('"');
+    if (!consume_specific('"'))
+        return {};
 
     if (buffer.is_empty())
         return String::empty();
@@ -151,55 +153,78 @@ String JsonParser::consume_quoted_string()
     return last_string_starting_with_character;
 }
 
-JsonObject JsonParser::parse_object()
+Optional<JsonValue> JsonParser::parse_object()
 {
     JsonObject object;
-    consume_specific('{');
+    if (!consume_specific('{'))
+        return {};
     for (;;) {
         consume_whitespace();
         if (peek() == '}')
             break;
         consume_whitespace();
         auto name = consume_quoted_string();
+        if (name.is_null())
+            return {};
         consume_whitespace();
-        consume_specific(':');
+        if (!consume_specific(':'))
+            return {};
         consume_whitespace();
-        auto value = parse();
-        object.set(name, move(value));
+        auto value = parse_helper();
+        if (!value.has_value())
+            return {};
+        object.set(name, move(value.value()));
         consume_whitespace();
         if (peek() == '}')
             break;
-        consume_specific(',');
+        if (!consume_specific(','))
+            return {};
+        consume_whitespace();
+        if (peek() == '}')
+            return {};
     }
-    consume_specific('}');
+    if (!consume_specific('}'))
+        return {};
     return object;
 }
 
-JsonArray JsonParser::parse_array()
+Optional<JsonValue> JsonParser::parse_array()
 {
     JsonArray array;
-    consume_specific('[');
+    if (!consume_specific('['))
+        return {};
     for (;;) {
         consume_whitespace();
         if (peek() == ']')
             break;
-        array.append(parse());
+        auto element = parse_helper();
+        if (!element.has_value())
+            return {};
+        array.append(element.value());
         consume_whitespace();
         if (peek() == ']')
             break;
-        consume_specific(',');
+        if (!consume_specific(','))
+            return {};
+        consume_whitespace();
+        if (peek() == ']')
+            return {};
     }
     consume_whitespace();
-    consume_specific(']');
+    if (!consume_specific(']'))
+        return {};
     return array;
 }
 
-JsonValue JsonParser::parse_string()
+Optional<JsonValue> JsonParser::parse_string()
 {
-    return consume_quoted_string();
+    auto result = consume_quoted_string();
+    if (result.is_null())
+        return {};
+    return JsonValue(result);
 }
 
-JsonValue JsonParser::parse_number()
+Optional<JsonValue> JsonParser::parse_number()
 {
     JsonValue value;
     Vector<char, 128> number_buffer;
@@ -235,7 +260,10 @@ JsonValue JsonParser::parse_number()
         if (to_signed_result.has_value()) {
             whole = to_signed_result.value();
         } else {
-            whole = number_string.to_int().value();
+            auto number = number_string.to_int();
+            if (!number.has_value())
+                return {};
+            whole = number.value();
         }
 
         int fraction = fraction_string.to_uint().value();
@@ -252,7 +280,10 @@ JsonValue JsonParser::parse_number()
         if (to_unsigned_result.has_value()) {
             value = JsonValue(to_unsigned_result.value());
         } else {
-            value = JsonValue(number_string.to_int().value());
+            auto number = number_string.to_int();
+            if (!number.has_value())
+                return {};
+            value = JsonValue(number.value());
         }
 #ifndef KERNEL
     }
@@ -261,37 +292,37 @@ JsonValue JsonParser::parse_number()
     return value;
 }
 
-void JsonParser::consume_string(const char* str)
+bool JsonParser::consume_string(const char* str)
 {
-    for (size_t i = 0, length = strlen(str); i < length; ++i)
-        consume_specific(str[i]);
+    for (size_t i = 0, length = strlen(str); i < length; ++i) {
+        if (!consume_specific(str[i]))
+            return false;
+    }
+    return true;
 }
 
-JsonValue JsonParser::parse_true()
+Optional<JsonValue> JsonParser::parse_true()
 {
-    consume_string("true");
+    if (!consume_string("true"))
+        return {};
     return JsonValue(true);
 }
 
-JsonValue JsonParser::parse_false()
+Optional<JsonValue> JsonParser::parse_false()
 {
-    consume_string("false");
+    if (!consume_string("false"))
+        return {};
     return JsonValue(false);
 }
 
-JsonValue JsonParser::parse_null()
+Optional<JsonValue> JsonParser::parse_null()
 {
-    consume_string("null");
+    if (!consume_string("null"))
+        return {};
     return JsonValue(JsonValue::Type::Null);
 }
 
-JsonValue JsonParser::parse_undefined()
-{
-    consume_string("undefined");
-    return JsonValue(JsonValue::Type::Undefined);
-}
-
-JsonValue JsonParser::parse()
+Optional<JsonValue> JsonParser::parse_helper()
 {
     consume_whitespace();
     auto type_hint = peek();
@@ -320,10 +351,19 @@ JsonValue JsonParser::parse()
         return parse_true();
     case 'n':
         return parse_null();
-    case 'u':
-        return parse_undefined();
     }
 
-    return JsonValue();
+    return {};
+}
+
+Optional<JsonValue> JsonParser::parse() {
+    auto result = parse_helper();
+    if (!result.has_value())
+        return {};
+    consume_whitespace();
+    if (m_index != m_input.length())
+        return {};
+    return result;
 }
+
 }
diff --git a/AK/JsonParser.h b/AK/JsonParser.h
index 3ff321424c..607bab8a6f 100644
--- a/AK/JsonParser.h
+++ b/AK/JsonParser.h
@@ -40,23 +40,24 @@ public:
     {
     }
 
-    JsonValue parse();
+    Optional<JsonValue> parse();
 
 private:
+    Optional<JsonValue> parse_helper();
+
     char peek() const;
     char consume();
     void consume_whitespace();
-    void consume_specific(char expected_ch);
-    void consume_string(const char*);
+    bool consume_specific(char expected_ch);
+    bool consume_string(const char*);
     String consume_quoted_string();
-    JsonArray parse_array();
-    JsonObject parse_object();
-    JsonValue parse_number();
-    JsonValue parse_string();
-    JsonValue parse_false();
-    JsonValue parse_true();
-    JsonValue parse_null();
-    JsonValue parse_undefined();
+    Optional<JsonValue> parse_array();
+    Optional<JsonValue> parse_object();
+    Optional<JsonValue> parse_number();
+    Optional<JsonValue> parse_string();
+    Optional<JsonValue> parse_false();
+    Optional<JsonValue> parse_true();
+    Optional<JsonValue> parse_null();
 
     template<typename C>
     void consume_while(C);
diff --git a/AK/JsonValue.cpp b/AK/JsonValue.cpp
index 76e65f3f15..8a1bc99f04 100644
--- a/AK/JsonValue.cpp
+++ b/AK/JsonValue.cpp
@@ -75,7 +75,7 @@ void JsonValue::copy_from(const JsonValue& other)
 
 JsonValue::JsonValue(JsonValue&& other)
 {
-    m_type = exchange(other.m_type, Type::Undefined);
+    m_type = exchange(other.m_type, Type::Null);
     m_value.as_string = exchange(other.m_value.as_string, nullptr);
 }
 
@@ -83,7 +83,7 @@ JsonValue& JsonValue::operator=(JsonValue&& other)
 {
     if (this != &other) {
         clear();
-        m_type = exchange(other.m_type, Type::Undefined);
+        m_type = exchange(other.m_type, Type::Null);
         m_value.as_string = exchange(other.m_value.as_string, nullptr);
     }
     return *this;
@@ -247,11 +247,11 @@ void JsonValue::clear()
     default:
         break;
     }
-    m_type = Type::Undefined;
+    m_type = Type::Null;
     m_value.as_string = nullptr;
 }
 
-JsonValue JsonValue::from_string(const StringView& input)
+Optional<JsonValue> JsonValue::from_string(const StringView& input)
 {
     return JsonParser(input).parse();
 }
diff --git a/AK/JsonValue.h b/AK/JsonValue.h
index 5ff6b4be99..7d3eef87f9 100644
--- a/AK/JsonValue.h
+++ b/AK/JsonValue.h
@@ -37,7 +37,6 @@ namespace AK {
 class JsonValue {
 public:
     enum class Type {
-        Undefined,
         Null,
         Int32,
         UnsignedInt32,
@@ -52,7 +51,7 @@ public:
         Object,
     };
 
-    static JsonValue from_string(const StringView&);
+    static Optional<JsonValue> from_string(const StringView&);
 
     explicit JsonValue(Type = Type::Null);
     ~JsonValue() { clear(); }
@@ -188,7 +187,6 @@ public:
     }
 
     bool is_null() const { return m_type == Type::Null; }
-    bool is_undefined() const { return m_type == Type::Undefined; }
     bool is_bool() const { return m_type == Type::Bool; }
     bool is_string() const { return m_type == Type::String; }
     bool is_i32() const { return m_type == Type::Int32; }
@@ -246,7 +244,7 @@ private:
     void clear();
     void copy_from(const JsonValue&);
 
-    Type m_type { Type::Undefined };
+    Type m_type { Type::Null };
 
     union {
         StringImpl* as_string { nullptr };
diff --git a/AK/Tests/TestJSON.cpp b/AK/Tests/TestJSON.cpp
index c8e787d4d4..87dca32879 100644
--- a/AK/Tests/TestJSON.cpp
+++ b/AK/Tests/TestJSON.cpp
@@ -48,7 +48,7 @@ TEST_CASE(load_form)
 
     fclose(fp);
 
-    JsonValue form_json = JsonValue::from_string(builder.to_string());
+    JsonValue form_json = JsonValue::from_string(builder.to_string()).value();
 
     EXPECT(form_json.is_object());
 
@@ -87,14 +87,14 @@ BENCHMARK_CASE(load_4chan_catalog)
     auto json_string = builder.to_string();
 
     for (int i = 0; i < 10; ++i) {
-        JsonValue form_json = JsonValue::from_string(json_string);
+        JsonValue form_json = JsonValue::from_string(json_string).value();
         EXPECT(form_json.is_array());
     }
 }
 
 TEST_CASE(json_empty_string)
 {
-    auto json = JsonValue::from_string("\"\"");
+    auto json = JsonValue::from_string("\"\"").value();
     EXPECT_EQ(json.type(), JsonValue::Type::String);
     EXPECT_EQ(json.as_string().is_null(), false);
     EXPECT_EQ(json.as_string().is_empty(), true);
@@ -102,7 +102,7 @@ TEST_CASE(json_empty_string)
 
 TEST_CASE(json_utf8_character)
 {
-    auto json = JsonValue::from_string("\"\xc3\x84\"");
+    auto json = JsonValue::from_string("\"\xc3\x84\"").value();
     EXPECT_EQ(json.type(), JsonValue::Type::String);
     EXPECT_EQ(json.as_string().is_null(), false);
     EXPECT_EQ(json.as_string().length(), size_t { 2 });