Eagerly parse expected transitions in JSON.

src/json-parser.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * 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
@@ skipping 84 matching lines @@
     return false;
   }
 
   // A JSON string (production JSONString) is subset of valid JavaScript string
   // literals. The string must only be double-quoted (not single-quoted), and
   // the only allowed backslash-escapes are ", /, \, b, f, n, r, t and
   // four-digit hex escapes (uXXXX). Any other use of backslashes is invalid.
   Handle<String> ParseJsonString() {
     return ScanJsonString<false>();
   }
+
+  bool ParseJsonString(Handle<String> expected) {
+    int length = expected->length();
+    if (source_->length() - position_ - 1 > length) {
+      AssertNoAllocation no_gc;
+      String::FlatContent content = expected->GetFlatContent();
+      if (content.IsAscii()) {
+        ASSERT_EQ('"', c0_);
+        const uint8_t* input_chars = seq_source_->GetChars() + position_ + 1;
+        const uint8_t* expected_chars = content.ToOneByteVector().start();
+        for (int i = 0; i < length; i++) {
+          uint8_t c0 = input_chars[i];
+          if (c0 != expected_chars[i] ||
+              c0 == '"' || c0 < 0x20 || c0 == '\\') {

[Yang, 2013/04/09 15:47:00]

maybe you also need to check for 0x7f, which is also a control character?

[Toon Verwaest, 2013/04/09 16:47:59]

Irrelevant, as discussed offline.

+            return false;
+          }
+        }
+        if (input_chars[length] == '"') {
+          position_ = position_ + length + 1;
+          AdvanceSkipWhitespace();
+          return true;
+        }
+      }
+    }
+    return false;
+  }

[Yang, 2013/04/09 15:47:00]

I guess an empty line here would make sense.

[Toon Verwaest, 2013/04/09 16:47:59]

Done.

   Handle<String> ParseJsonInternalizedString() {
     return ScanJsonString<true>();
   }

[Yang, 2013/04/09 15:47:00]

empty line here as well.

[Toon Verwaest, 2013/04/09 16:47:59]

Done.

   template <bool is_internalized>
   Handle<String> ScanJsonString();
   // Creates a new string and copies prefix[start..end] into the beginning
   // of it. Then scans the rest of the string, adding characters after the
   // prefix. Called by ScanJsonString when reaching a '\' or non-ASCII char.
   template <typename StringType, typename SinkChar>
   Handle<String> SlowScanJsonString(Handle<String> prefix, int start, int end);
 
   // A JSON number (production JSONNumber) is a subset of the valid JavaScript
   // decimal number literals.
@@ skipping 169 matching lines @@
   return ReportUnexpectedCharacter();
 }
 
 
 // Parse a JSON object. Position must be right at '{'.
 template <bool seq_ascii>
 Handle<Object> JsonParser<seq_ascii>::ParseJsonObject() {
   HandleScope scope(isolate());
   Handle<JSObject> json_object =
       factory()->NewJSObject(object_constructor(), pretenure_);
+  Handle<Map> map(json_object->map());
+  ZoneScope zone_scope(zone(), DELETE_ON_EXIT);
+  ZoneList<Handle<Object> > properties(8, zone());

[Yang, 2013/04/09 15:47:00]

You could reuse one zone list through out the entire JSON parser, so that you
don't have to create new lists all the time. Just Clear() it after use.

[Toon Verwaest, 2013/04/09 16:47:59]

That's unfortunately not possible since objects are nested...

On 2013/04/09 15:47:00, Yang wrote:

   ASSERT_EQ(c0_, '{');
 
+  bool transitioning = true;
+
   AdvanceSkipWhitespace();
   if (c0_ != '}') {
     do {
       if (c0_ != '"') return ReportUnexpectedCharacter();
 
       int start_position = position_;
       Advance();
 
       uint32_t index = 0;
       if (c0_ >= '0' && c0_ <= '9') {
@@ skipping 23 matching lines @@
           continue;
         }
         // Not an index, fallback to the slow path.
       }
 
       position_ = start_position;
 #ifdef DEBUG
       c0_ = '"';
 #endif
 
-      Handle<String> key = ParseJsonInternalizedString();
-      if (key.is_null() || c0_ != ':') return ReportUnexpectedCharacter();
+      Handle<String> key;
+      Handle<Object> value;
 
-      AdvanceSkipWhitespace();
-      Handle<Object> value = ParseJsonValue();
-      if (value.is_null()) return ReportUnexpectedCharacter();
+      // Try to follow existing transitions as long as possible. Once we stop
+      // transitioning, no transition can be found anymore.
+      if (transitioning) {
+        // First check whether there is a single expected transition. If so, try
+        // to parse it first.
+        bool follow_expected = false;
+        if (seq_ascii) {
+          key = JSObject::ExpectedTransitionKey(map);
+          follow_expected = !key.is_null() && ParseJsonString(key);
+        }
+        // If the expected transition hits, follow it.
+        if (follow_expected) {
+          map = JSObject::ExpectedTransitionTarget(map);
+        } else {
+          // If the expected transition failed, parse an internal string and try

[Yang, 2013/04/09 15:47:00]

"internalized string"

[Toon Verwaest, 2013/04/09 16:47:59]

Done.

+          // to find a matching transition.
+          key = ParseJsonInternalizedString();
+          if (key.is_null()) return ReportUnexpectedCharacter();
 
-      if (JSObject::TryTransitionToField(json_object, key)) {
-        int index = json_object->LastAddedFieldIndex();
-        json_object->FastPropertyAtPut(index, *value);
+          Handle<Map> target = JSObject::FindTransitionToField(map, key);
+          // If a transition was found, follow it and continue.
+          if (!target.is_null()) {
+            map = target;
+          } else {
+            // If no transition was found, commit the intermediate state to the
+            // object and stop transitioning.
+            JSObject::TransitionToMap(json_object, map);
+            int length = properties.length();
+            for (int i = 0; i < length; i++) {
+              json_object->FastPropertyAtPut(i, *properties[i]);
+            }
+            transitioning = false;
+          }
+        }
+        if (c0_ != ':') return ReportUnexpectedCharacter();
+
+        AdvanceSkipWhitespace();
+        value = ParseJsonValue();
+        if (value.is_null()) return ReportUnexpectedCharacter();
+
+        properties.Add(value, zone());
+        if (transitioning) continue;
       } else {
-        JSObject::SetLocalPropertyIgnoreAttributes(
-            json_object, key, value, NONE);
+        key = ParseJsonInternalizedString();
+        if (key.is_null() || c0_ != ':') return ReportUnexpectedCharacter();
+
+        AdvanceSkipWhitespace();
+        value = ParseJsonValue();
+        if (value.is_null()) return ReportUnexpectedCharacter();
       }
+
+      JSObject::SetLocalPropertyIgnoreAttributes(
+          json_object, key, value, NONE);
     } while (MatchSkipWhiteSpace(','));
     if (c0_ != '}') {
       return ReportUnexpectedCharacter();
     }
+
+    // If we transitioned until the very end, transition the map now.
+    if (transitioning) {
+      JSObject::TransitionToMap(json_object, map);
+      int length = properties.length();
+      for (int i = 0; i < length; i++) {
+        json_object->FastPropertyAtPut(i, *properties[i]);
+      }
+    }
   }
   AdvanceSkipWhitespace();
   return scope.CloseAndEscape(json_object);
 }
 
 // Parse a JSON array. Position must be right at '['.
 template <bool seq_ascii>
 Handle<Object> JsonParser<seq_ascii>::ParseJsonArray() {
   HandleScope scope(isolate());
   ZoneScope zone_scope(zone(), DELETE_ON_EXIT);
@@ skipping 267 matching lines @@
     } while (c0 != '"');
     int length = position - position_;
     uint32_t hash = (length <= String::kMaxHashCalcLength)
         ? StringHasher::GetHashCore(running_hash) : length;
     Vector<const uint8_t> string_vector(
         seq_source_->GetChars() + position_, length);
     StringTable* string_table = isolate()->heap()->string_table();
     uint32_t capacity = string_table->Capacity();
     uint32_t entry = StringTable::FirstProbe(hash, capacity);
     uint32_t count = 1;
+    Handle<String> result;
     while (true) {
       Object* element = string_table->KeyAt(entry);
       if (element == isolate()->heap()->undefined_value()) {
         // Lookup failure.
+        result = factory()->InternalizeOneByteString(
+            seq_source_, position_, length);
         break;
       }
       if (element != isolate()->heap()->the_hole_value() &&
           String::cast(element)->IsOneByteEqualTo(string_vector)) {
-        // Lookup success, update the current position.
-        position_ = position;
-        // Advance past the last '"'.
-        AdvanceSkipWhitespace();
-        return Handle<String>(String::cast(element), isolate());
+        result = Handle<String>(String::cast(element), isolate());
+#ifdef DEBUG
+        uint32_t hash_field =
+            (hash << String::kHashShift) | String::kIsNotArrayIndexMask;
+        ASSERT_EQ(static_cast<int>(result->Hash()),
+                  static_cast<int>(hash_field >> String::kHashShift));
+#endif
+        break;
       }
       entry = StringTable::NextProbe(entry, count++, capacity);
     }
+    position_ = position;
+    // Advance past the last '"'.
+    AdvanceSkipWhitespace();
+    return result;
   }
 
   int beg_pos = position_;
   // Fast case for ASCII only without escape characters.
   do {
     // Check for control character (0x00-0x1f) or unterminated string (<0).
     if (c0_ < 0x20) return Handle<String>::null();
     if (c0_ != '\\') {
       if (seq_ascii || c0_ <= String::kMaxOneByteCharCode) {
         Advance();
       } else {
         return SlowScanJsonString<SeqTwoByteString, uc16>(source_,
                                                           beg_pos,
                                                           position_);
       }
     } else {
       return SlowScanJsonString<SeqOneByteString, uint8_t>(source_,
                                                            beg_pos,
                                                            position_);
     }
   } while (c0_ != '"');
   int length = position_ - beg_pos;
-  Handle<String> result;
-  if (seq_ascii && is_internalized) {
-    result = factory()->InternalizeOneByteString(seq_source_, beg_pos, length);
-  } else {
-    result = factory()->NewRawOneByteString(length, pretenure_);
-    uint8_t* dest = SeqOneByteString::cast(*result)->GetChars();
-    String::WriteToFlat(*source_, dest, beg_pos, position_);
-  }
+  Handle<String> result = factory()->NewRawOneByteString(length, pretenure_);
+  uint8_t* dest = SeqOneByteString::cast(*result)->GetChars();
+  String::WriteToFlat(*source_, dest, beg_pos, position_);
+
   ASSERT_EQ('"', c0_);
   // Advance past the last '"'.
   AdvanceSkipWhitespace();
   return result;
 }
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSON_PARSER_H_