Blink-compatible serialization of dictionary-like objects.

src/value-serializer.cc

Index: src/value-serializer.cc
diff --git a/src/value-serializer.cc b/src/value-serializer.cc
index 8358b66b66d9f79dfc9e885e05865b14e341bc44..8e74e91f9652100bc36b196ef9ea2c1c31114384 100644
--- a/src/value-serializer.cc
+++ b/src/value-serializer.cc
@@ -54,9 +54,18 @@ enum class SerializationTag : uint8_t {
   // byteLength:uint32_t, then raw data
   kUtf8String = 'S',
   kTwoByteString = 'c',
+  // Reference to a serialized object. objectID:uint32_t
+  kObjectReference = '^',
+  // Beginning of a JS object.
+  kBeginJSObject = 'o',
+  // End of a JS object. numProperties:uint32_t
+  kEndJSObject = '{',
 };
 
-ValueSerializer::ValueSerializer() {}
+ValueSerializer::ValueSerializer(Isolate* isolate)
+    : isolate_(isolate),
+      zone_(isolate->allocator()),
+      id_map_(isolate->heap(), &zone_) {}
 
 ValueSerializer::~ValueSerializer() {}
 
@@ -144,6 +153,8 @@ Maybe<bool> ValueSerializer::WriteObject(Handle<Object> object) {
       if (object->IsString()) {
         WriteString(Handle<String>::cast(object));
         return Just(true);
+      } else if (object->IsJSReceiver()) {
+        return WriteJSReceiver(Handle<JSReceiver>::cast(object));
       }
       UNIMPLEMENTED();
       return Nothing<bool>();
@@ -218,13 +229,82 @@ void ValueSerializer::WriteString(Handle<String> string) {
   }
 }
 
+Maybe<bool> ValueSerializer::WriteJSReceiver(Handle<JSReceiver> receiver) {
+  // If the object has already been serialized, just write its ID.
+  uint32_t* id_map_entry = id_map_.Get(receiver);
+  if (uint32_t id = *id_map_entry) {
+    WriteTag(SerializationTag::kObjectReference);
+    WriteVarint(id - 1);
+    return Just(true);
+  }
+
+  // Otherwise, allocate an ID for it.
+  uint32_t id = next_id_++;
+  *id_map_entry = id + 1;
+
+  // Eliminate callable and exotic objects, which should not be serialized.
+  auto instance_type = receiver->map()->instance_type();

[Camillo Bruni, 2016/08/16 11:26:57]

nit: we don't use the auto type in V8

[jbroman, 2016/08/16 18:16:29]

Done.

+  if (receiver->IsCallable() || instance_type <= LAST_SPECIAL_RECEIVER_TYPE)
+    return Nothing<bool>();

[Camillo Bruni, 2016/08/16 11:26:57]

nit: missing braces

+
+  // If we are at the end of the stack, abort. This function may recurse.
+  if (StackLimitCheck(isolate_).HasOverflowed()) return Nothing<bool>();
+
+  HandleScope scope(isolate_);
+  switch (instance_type) {
+    case JS_OBJECT_TYPE:
+    case JS_API_OBJECT_TYPE:
+      return WriteJSObject(Handle<JSObject>::cast(receiver));
+    default:
+      UNIMPLEMENTED();
+      break;
+  }
+  return Nothing<bool>();
+}
+
+Maybe<bool> ValueSerializer::WriteJSObject(Handle<JSObject> object) {
+  WriteTag(SerializationTag::kBeginJSObject);
+  Handle<FixedArray> keys;
+  if (!KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,

[Camillo Bruni, 2016/08/16 11:26:56]

I'm sure you already had a look at JsonStringifier::SerializeJSObject, I'd
presume you'll use the same structure having a FastVersion that bails out and
falls back to this Slow path.

[jbroman, 2016/08/16 18:16:29]

I've definitely considered it, though I figured I'd get things working first.
(Incidentally, I already expect a significant performance win even before
evaluating such fast paths.)

I'm not sure I understand the JSON implementation well enough to understand why
it works. It looks like it should behave in ways I don't want (w.r.t. things
messing with object structure during getters), but I haven't been able to
actually cause that to happen.

Is a new Map created whenever a JSObject's structure changes
(addition/removal/reconfiguration of properties)? There's no comment on i::Map,
but I'm having difficulty making sense of it otherwise.

[jbroman, 2016/08/16 18:22:13]

Ah, this is partially answered by your comment on my followup CL:
https://codereview.chromium.org/2248893003

+                               ENUMERABLE_STRINGS)
+           .ToHandle(&keys) ||
+      !WriteJSObjectProperties(object, keys).FromMaybe(false))
+    return Nothing<bool>();

[Camillo Bruni, 2016/08/16 11:26:57]

nit: missing braces

[jbroman, 2016/08/16 18:16:29]

Done.

+  WriteTag(SerializationTag::kEndJSObject);
+  WriteVarint<uint32_t>(keys->length());
+  return Just(true);
+}
+
+Maybe<bool> ValueSerializer::WriteJSObjectProperties(Handle<JSObject> object,
+                                                     Handle<FixedArray> keys) {
+  int length = keys->length();
+  for (int i = 0; i < length; i++) {
+    Handle<Object> key(keys->get(i), isolate_);
+    if (!WriteObject(key).FromMaybe(false)) return Nothing<bool>();

[Camillo Bruni, 2016/08/16 11:26:57]

I don't know the details of the post message serialization format, but here you
differ from the the JSON.stringify way of skipping properties that are set to
undefined.

So probably this is fine :)

[jbroman, 2016/08/16 18:16:29]

The structured clone algorithm reproduces properties with value "undefined" on
the other side (unlike JSON, which doesn't have a representation of undefined).
https://html.spec.whatwg.org/multipage/infrastructure.html#structuredclone

+    bool success;
+    LookupIterator it = LookupIterator::PropertyOrElement(
+        isolate_, object, key, &success, LookupIterator::OWN);
+    DCHECK(success);
+    Handle<Object> value;
+    if (!Object::GetProperty(&it).ToHandle(&value) ||
+        !WriteObject(value).FromMaybe(false))
+      return Nothing<bool>();
+  }
+  return Just(true);
+}
+
 ValueDeserializer::ValueDeserializer(Isolate* isolate,
                                      Vector<const uint8_t> data)
     : isolate_(isolate),
       position_(data.start()),
-      end_(data.start() + data.length()) {}
+      end_(data.start() + data.length()),
+      id_map_(Handle<SeededNumberDictionary>::cast(
+          isolate->global_handles()->Create(
+              *SeededNumberDictionary::New(isolate, 0)))) {}
 
-ValueDeserializer::~ValueDeserializer() {}
+ValueDeserializer::~ValueDeserializer() {
+  GlobalHandles::Destroy(Handle<Object>::cast(id_map_).location());

[jbroman, 2016/08/15 22:27:06]

This seems to be how such handles are currently managed in v8::internal, though
an internal handle equivalent to v8::Global would naturally be more convenient
than explicitly writing the create/destroy invocations.

[Camillo Bruni, 2016/08/16 11:26:56]

If I see this correctly, I think you can get rid of the GlobalHandle if you make
sure that you have an outer HandleScope. From what I've seen is that many API
helper methods create one and then call into an internal V8 method.

[jbroman, 2016/08/16 18:16:28]

I couldn't figure out how to do this. We might need to enlarge the dictionary
during some deep recursive call, and if I understand correctly, the handle that
will be allocated then will be part of the current (deeper) HandleScope. I'd
need to lift it (potentially up several levels) to a HandleScope that will
survive until ~ValueDeserializer.

The two ways I could think of to do that were to use a global handle, or to hold
a handle on a heap object which itself contains a reference to the current
dictionary (adding another level of indirection). I didn't see any code doing
the latter, so I did the former.

What's the right way to do this?

[Jakob Kummerow, 2016/08/17 13:00:14]

I think your understanding is correct, and GlobalHandles are indeed the way to
solve this.

+}
 
 Maybe<bool> ValueDeserializer::ReadHeader() {
   if (position_ < end_ &&
@@ -236,6 +316,17 @@ Maybe<bool> ValueDeserializer::ReadHeader() {
   return Just(true);
 }
 
+Maybe<SerializationTag> ValueDeserializer::PeekTag() const {
+  const uint8_t* peek_position = position_;
+  SerializationTag tag;
+  do {
+    if (peek_position >= end_) return Nothing<SerializationTag>();
+    tag = static_cast<SerializationTag>(*peek_position);
+    peek_position++;
+  } while (tag == SerializationTag::kPadding);
+  return Just(tag);
+}
+
 Maybe<SerializationTag> ValueDeserializer::ReadTag() {
   SerializationTag tag;
   do {
@@ -337,6 +428,13 @@ MaybeHandle<Object> ValueDeserializer::ReadObject() {
       return ReadUtf8String();
     case SerializationTag::kTwoByteString:
       return ReadTwoByteString();
+    case SerializationTag::kObjectReference: {
+      uint32_t id;
+      if (!ReadVarint<uint32_t>().To(&id)) return MaybeHandle<Object>();
+      return GetObjectWithID(id);
+    }
+    case SerializationTag::kBeginJSObject:
+      return ReadJSObject();
     default:
       return MaybeHandle<Object>();
   }
@@ -377,5 +475,91 @@ MaybeHandle<String> ValueDeserializer::ReadTwoByteString() {
   return string;
 }
 
+MaybeHandle<JSObject> ValueDeserializer::ReadJSObject() {
+  return ReadJSReceiver<JSObject>([this](uint32_t id) -> MaybeHandle<JSObject> {

[Camillo Bruni, 2016/08/16 11:26:56]

nit: I think V8 is not too fond of functors (call us old fashioned), could you
rewrite this more explicitly (I think I'd be fine with some more duplication
here). I consulted with jkummerow who's going to take over and he's not too fond
of it either ;). Feel free to convince us though!

[jbroman, 2016/08/16 18:16:28]

My only reservation is making sure that all JSReceivers do this properly. There
are a few cases that will need to need the same boilerplate: object, host
object, array, map, set, regexp, date, and the various JSValue wrappers. That
said, the boilerplate isn't too bad and about half of those are leaves for which
it's OK to skip the HandleScope and StackLimitCheck, so I'll just go ahead and
inline it.

+    Handle<JSObject> object =
+        isolate_->factory()->NewJSObject(isolate_->object_function());
+    AddObjectWithID(id, object);
+
+    uint32_t num_properties;
+    uint32_t expected_num_properties;
+    if (!ReadJSObjectProperties(object, SerializationTag::kEndJSObject)
+             .To(&num_properties) ||
+        !ReadVarint<uint32_t>().To(&expected_num_properties) ||
+        num_properties != expected_num_properties)
+      return MaybeHandle<JSObject>();

[Camillo Bruni, 2016/08/16 11:26:57]

nit: missing braces

[jbroman, 2016/08/16 18:16:29]

Done.

+
+    return object;
+  });
+}
+
+template <typename T, typename Functor>
+MaybeHandle<T> ValueDeserializer::ReadJSReceiver(const Functor& functor) {
+  // If we are at the end of the stack, abort. This function may recurse.
+  if (StackLimitCheck(isolate_).HasOverflowed()) return MaybeHandle<T>();
+
+  uint32_t id = next_id_++;
+  HandleScope scope(isolate_);
+  Handle<T> handle;
+  if (!functor(id).ToHandle(&handle)) return MaybeHandle<T>();
+  DCHECK(HasObjectWithID(id));
+  return scope.CloseAndEscape(handle);
+}
+
+Maybe<uint32_t> ValueDeserializer::ReadJSObjectProperties(
+    Handle<JSObject> object, SerializationTag end_tag) {
+  for (uint32_t num_properties = 0;; num_properties++) {
+    SerializationTag tag;
+    if (!PeekTag().To(&tag)) return Nothing<uint32_t>();
+    if (tag == end_tag) {
+      SerializationTag consumed_tag = ReadTag().ToChecked();
+      (void)consumed_tag;
+      DCHECK(tag == consumed_tag);
+      return Just(num_properties);
+    }
+
+    Handle<Object> key;
+    if (!ReadObject().ToHandle(&key)) return Nothing<uint32_t>();
+    Handle<Object> value;
+    if (!ReadObject().ToHandle(&value)) return Nothing<uint32_t>();
+
+    bool success;
+    LookupIterator it = LookupIterator::PropertyOrElement(
+        isolate_, object, key, &success, LookupIterator::OWN);
+    if (!success ||
+        JSObject::DefineOwnPropertyIgnoreAttributes(&it, value, NONE).is_null())
+      return Nothing<uint32_t>();
+  }
+}
+
+bool ValueDeserializer::HasObjectWithID(uint32_t id) {
+  return id_map_->Has(isolate_, id);
+}
+
+MaybeHandle<JSReceiver> ValueDeserializer::GetObjectWithID(uint32_t id) {
+  int index = id_map_->FindEntry(isolate_, id);
+  if (index == SeededNumberDictionary::kNotFound)
+    return MaybeHandle<JSReceiver>();

[Camillo Bruni, 2016/08/16 11:26:57]

nit: missing braces

[jbroman, 2016/08/16 18:16:29]

Done.

The other cases you've pointed out had multi-line conditions, but this makes me
wonder what the condition is that you're looking for braces in.

https://github.com/v8/v8/wiki/Cpp%20Style%20Guide just points to the Chromium
and Google style guides, both of which allow braces to be omitted if the body is
one line. Can you point me where I can find the style rules I'm unaware of?

+  Object* value = id_map_->ValueAt(index);
+  DCHECK(value->IsJSReceiver());
+  return Handle<JSReceiver>(JSReceiver::cast(value), isolate_);
+}
+
+void ValueDeserializer::AddObjectWithID(uint32_t id,
+                                        Handle<JSReceiver> object) {
+  DCHECK(!HasObjectWithID(id));
+  const bool used_as_prototype = false;
+  Handle<SeededNumberDictionary> new_dictionary =
+      SeededNumberDictionary::AtNumberPut(id_map_, id, object,
+                                          used_as_prototype);
+
+  // If the dictionary was reallocated, update the global handle.
+  if (!new_dictionary.is_identical_to(id_map_)) {
+    GlobalHandles::Destroy(Handle<Object>::cast(id_map_).location());
+    id_map_ = Handle<SeededNumberDictionary>::cast(
+        isolate_->global_handles()->Create(*new_dictionary));
+  }

[Camillo Bruni, 2016/08/16 11:26:57]

nit: I'd drop the global handle (as I outlined above), they are quite costly in
comparison to normal handles anyway.

[jbroman, 2016/08/16 18:16:29]

Replied above. Happy to eliminate it if there's a better solution, but just
using plain handles here with no other changes doesn't work -- it results in
accessing a handle outside its HandleScope. (That could possibly be resolved by
making sure not to create inner HandleScopes, but deep recursion could lead to
many open handles in that case.)

+}
+
 }  // namespace internal
 }  // namespace v8