Reimplement a simpler version of JSON.stringify.

src/json-stringifier.h

Index: src/json-stringifier.h
diff --git a/src/json-stringifier.h b/src/json-stringifier.h
new file mode 100644
index 0000000000000000000000000000000000000000..1eef37a138aa211f7e9266629b371b2b5d1aa0cb
--- /dev/null
+++ b/src/json-stringifier.h
@@ -0,0 +1,595 @@
+// Copyright 2012 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
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_JSON_STRINGIFIER_H_
+#define V8_JSON_STRINGIFIER_H_
+
+#include "v8.h"
+#include "v8utils.h"
+#include "v8conversions.h"
+
+namespace v8 {
+namespace internal {
+
+class BasicJsonStringifier BASE_EMBEDDED {
+ public:
+  explicit BasicJsonStringifier(Isolate* isolate);
+
+  MaybeObject* Stringify(Handle<Object> object);
+
+ private:
+  static const int kPartLength = 8 * 1024;
+
+  enum Result { UNCHANGED, SUCCESS, BAILOUT, CIRCULAR };
+
+  template <bool is_ascii> void Extend();
+
+  void ChangeEncoding();
+
+  void ShrinkCurrentPart();
+
+  template <bool is_ascii, typename Char>
+  INLINE(void Append_(Char c));
+
+  template <bool is_ascii, typename Char>
+  INLINE(void AppendUnchecked_(Char c));
+
+  template <bool is_ascii, typename Char>
+  INLINE(void Append_(Char* chars));
+
+  template <bool is_ascii, typename Char>
+  INLINE(void Append_(const Char* chars));
+
+  template <bool is_ascii, typename Char>
+  INLINE(void AppendUnchecked_(const Char* chars));
+
+  INLINE(void Append(char c)) {
+    if (is_ascii_) {
+      Append_<true>(c);
+    } else {
+      Append_<false>(c);
+    }
+  }
+
+  INLINE(void Append(const char* chars)) {
+    if (is_ascii_) {
+      Append_<true>(chars);
+    } else {
+      Append_<false>(chars);
+    }
+  }
+
+  INLINE(Handle<Object> GetProperty(Handle<JSObject> object,
+                                    Handle<String> key));
+
+  INLINE(Result Serialize(Handle<Object> object)) {
+    return Serialize_<false>(object);
+  }
+
+  INLINE(Result SerializeDeferred(Handle<Object> object,
+                           bool deferred_comma,
+                           Handle<String> deferred_key)) {
+    ASSERT(!deferred_key.is_null());
+    return Serialize_<true>(object, deferred_comma, deferred_key);
+  }
+
+  template <bool deferred_key>
+  Result Serialize_(Handle<Object> object,
+                    bool comma = false,
+                    Handle<String> key = Handle<String>::null());
+
+  INLINE(void SerializeDeferredKey(bool deferred_comma,
+                                   Handle<String> deferred_key)) {
+    if (deferred_comma) Append(',');
+    SerializeString(deferred_key);
+    Append(':');
+  }
+
+  INLINE(Result SerializeSmi(Smi* object));
+
+  INLINE(Result SerializeDouble(double number));
+  INLINE(Result SerializeHeapNumber(Handle<HeapNumber> object)) {
+    return SerializeDouble(object->value());
+  }
+
+  Result SerializeArray(Handle<JSArray> object);
+  Result SerializeObject(Handle<JSObject> object);
+
+  void SerializeString(Handle<String> object);
+
+  template <bool is_ascii, typename Char>
+  INLINE(void SerializeString_(Vector<const Char> vector));
+
+  INLINE(Result StackPush(Handle<Object> object));
+  INLINE(void StackPop());
+
+  Isolate* isolate_;
+  Handle<String> accumulator_;
+  Handle<String> current_part_;
+  Handle<String> tojson_symbol_;
+  Handle<JSArray> stack_;
+  int current_index_;
+  bool is_ascii_;
+
+  static const int kJsonQuotesCharactersPerEntry = 8;
+  static const char* const JsonQuotes;
+};
+
+
+const char* const BasicJsonStringifier::JsonQuotes =
+    "\\u0000\0 \\u0001\0 \\u0002\0 \\u0003\0 "
+    "\\u0004\0 \\u0005\0 \\u0006\0 \\u0007\0 "
+    "\\b\0     \\t\0     \\n\0     \\u000b\0 "
+    "\\f\0     \\r\0     \\u000e\0 \\u000f\0 "
+    "\\u0010\0 \\u0011\0 \\u0012\0 \\u0013\0 "
+    "\\u0014\0 \\u0015\0 \\u0016\0 \\u0017\0 "
+    "\\u0018\0 \\u0019\0 \\u001a\0 \\u001b\0 "
+    "\\u001c\0 \\u001d\0 \\u001e\0 \\u001f\0 "
+    " \0      !\0      \\\"\0     #\0      "
+    "$\0      %\0      &\0      '\0      "
+    "(\0      )\0      *\0      +\0      "
+    ",\0      -\0      .\0      /\0      "
+    "0\0      1\0      2\0      3\0      "
+    "4\0      5\0      6\0      7\0      "
+    "8\0      9\0      :\0      ;\0      "
+    "<\0      =\0      >\0      ?\0      "
+    "@\0      A\0      B\0      C\0      "
+    "D\0      E\0      F\0      G\0      "
+    "H\0      I\0      J\0      K\0      "
+    "L\0      M\0      N\0      O\0      "
+    "P\0      Q\0      R\0      S\0      "
+    "T\0      U\0      V\0      W\0      "
+    "X\0      Y\0      Z\0      [\0      "
+    "\\\\\0     ]\0      ^\0      _\0      "
+    "`\0      a\0      b\0      c\0      "
+    "d\0      e\0      f\0      g\0      "
+    "h\0      i\0      j\0      k\0      "
+    "l\0      m\0      n\0      o\0      "
+    "p\0      q\0      r\0      s\0      "
+    "t\0      u\0      v\0      w\0      "
+    "x\0      y\0      z\0      {\0      "
+    "|\0      }\0      ~\0      \177\0      ";
+
+
+BasicJsonStringifier::BasicJsonStringifier(Isolate* isolate)
+    : isolate_(isolate), current_index_(0), is_ascii_(true) {
+  accumulator_ = isolate_->factory()->empty_string();
+  current_part_ =
+      isolate_->factory()->NewRawAsciiString(kPartLength);
+  tojson_symbol_ = isolate_->factory()->LookupAsciiSymbol("toJSON");
+  stack_ = isolate_->factory()->NewJSArray(8);
+}
+
+
+MaybeObject* BasicJsonStringifier::Stringify(Handle<Object> object) {
+  switch (Serialize(object)) {
+    case SUCCESS:
+      ShrinkCurrentPart();
+      return *isolate_->factory()->NewConsString(accumulator_, current_part_);
+    case BAILOUT:
+      return Smi::FromInt(0);
+    case UNCHANGED:
+      return isolate_->heap()->undefined_value();
+    case CIRCULAR:
+      return isolate_->Throw(*isolate_->factory()->NewTypeError(
+                 "circular_structure", HandleVector<Object>(NULL, 0)));
+    default:
+      UNREACHABLE();
+      return Smi::FromInt(0);
+  }
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::Append_(Char c) {
+  if (is_ascii) {
+    SeqAsciiString::cast(*current_part_)->SeqAsciiStringSet(
+        current_index_++, c);
+  } else {
+    SeqTwoByteString::cast(*current_part_)->SeqTwoByteStringSet(
+        current_index_++, c);
+  }
+  if (current_index_ == kPartLength) Extend<is_ascii>();
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::AppendUnchecked_(Char c) {
+  if (is_ascii) {
+    SeqAsciiString::cast(*current_part_)->SeqAsciiStringSet(
+        current_index_++, c);
+  } else {
+    SeqTwoByteString::cast(*current_part_)->SeqTwoByteStringSet(
+        current_index_++, c);
+  }
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::Append_(Char* chars) {
+  for ( ; *chars != '\0'; chars++) Append_<is_ascii>(*chars);
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::Append_(const Char* chars) {
+  for ( ; *chars != '\0'; chars++) Append_<is_ascii, Char>(*chars);
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::AppendUnchecked_(const Char* chars) {
+  for ( ; *chars != '\0'; chars++) AppendUnchecked_<is_ascii, Char>(*chars);
+}
+
+
+Handle<Object> BasicJsonStringifier::GetProperty(Handle<JSObject> object,
+                                                 Handle<String> key) {
+  LookupResult lookup(isolate_);
+  object->LookupRealNamedProperty(*key, &lookup);

[Toon Verwaest, 2012/10/17 17:52:50]

Don't you want LocalLookupRealNamedProperty instead, to avoid lookup in
prototypes (and an extra indirection)?

+  if (!lookup.IsProperty()) return isolate_->factory()->undefined_value();
+  Object* value;
+  switch (lookup.type()) {
+    case NORMAL:
+      value = lookup.holder()->GetNormalizedProperty(&lookup);
+      ASSERT(!value->IsTheHole() || lookup.IsReadOnly());

[Toon Verwaest, 2012/10/17 17:52:50]

Does it matter whether the property is readonly?
You assert it is not the hole, but at the same time handle it... Missing test?

+      return Handle<Object>(value->IsTheHole()
+                 ? isolate_->heap()->undefined_value() : value);
+    case FIELD:
+      value = lookup.holder()->FastPropertyAt(lookup.GetFieldIndex());
+      ASSERT(!value->IsTheHole() || lookup.IsReadOnly());
+      return Handle<Object>(value->IsTheHole()
+                 ? isolate_->heap()->undefined_value() : value);
+    case CONSTANT_FUNCTION:
+      return Handle<Object>(lookup.GetConstantFunction());
+    case CALLBACKS:
+    case HANDLER:
+    case INTERCEPTOR:
+      return Handle<Object>::null();
+    case TRANSITION:
+    case NONEXISTENT:
+      UNREACHABLE();
+      break;
+  }
+  return Handle<Object>::null();
+}
+
+
+BasicJsonStringifier::Result BasicJsonStringifier::StackPush(
+    Handle<Object> object) {
+  int length = Smi::cast(stack_->length())->value();
+  FixedArray* elements = FixedArray::cast(stack_->elements());
+  for (int i = 0; i < length; i++) {
+    if (elements->get(i) == *object) {
+      stack_ = Handle<JSArray>::null();

[Toon Verwaest, 2012/10/17 17:52:50]

Why is the stack_ set to null if we are going to throw an exception anyway?

+      return CIRCULAR;
+    }
+  }
+  stack_->EnsureSize(length + 1);
+  FixedArray::cast(stack_->elements())->set(length, *object);
+  stack_->set_length(Smi::FromInt(length + 1));
+  return SUCCESS;
+}
+
+
+void BasicJsonStringifier::StackPop() {
+  int length = Smi::cast(stack_->length())->value();
+  stack_->set_length(Smi::FromInt(length - 1));
+}
+
+
+template <bool deferred_key>
+BasicJsonStringifier::Result BasicJsonStringifier::Serialize_(
+    Handle<Object> object, bool comma, Handle<String> key) {
+  if (object->IsJSObject()) {
+    Handle<JSObject> jsobject = Handle<JSObject>::cast(object);
+    Handle<Object> toJson = GetProperty(jsobject, tojson_symbol_);
+    // We don't deal with custom toJSON functions.
+    if (toJson.is_null() || toJson->IsSpecFunction()) return BAILOUT;
+
+    if (object->IsJSFunction()) {
+      return UNCHANGED;
+    } else if (object->IsJSArray()) {
+      if (deferred_key) SerializeDeferredKey(comma, key);
+      return SerializeArray(Handle<JSArray>::cast(object));
+    } else if (object->IsJSValue()) {
+      // JSValue with a custom prototype.
+      if (object->GetPrototype()->IsJSReceiver()) return BAILOUT;
+      // Unpack value wrapper and fall through.
+      object = Handle<Object>(JSValue::cast(*object)->value());
+    } else {
+      if (deferred_key) SerializeDeferredKey(comma, key);
+      return SerializeObject(Handle<JSObject>::cast(object));
+    }
+  }
+
+  if (object->IsString()) {
+    if (deferred_key) SerializeDeferredKey(comma, key);
+    SerializeString(Handle<String>::cast(object));
+    return SUCCESS;
+  } else if (object->IsSmi()) {
+    if (deferred_key) SerializeDeferredKey(comma, key);
+    return SerializeSmi(Smi::cast(*object));
+  } else if (object->IsHeapNumber()) {
+    if (deferred_key) SerializeDeferredKey(comma, key);
+    return SerializeHeapNumber(Handle<HeapNumber>::cast(object));
+  } else if (object->IsOddball()) {
+    switch (Oddball::cast(*object)->kind()) {
+      case Oddball::kFalse:
+        if (deferred_key) SerializeDeferredKey(comma, key);
+        Append("false");
+        return SUCCESS;
+      case Oddball::kTrue:
+        if (deferred_key) SerializeDeferredKey(comma, key);
+        Append("true");
+        return SUCCESS;
+      case Oddball::kNull:
+        if (deferred_key) SerializeDeferredKey(comma, key);
+        Append("null");
+        return SUCCESS;
+    }
+  }
+
+  return UNCHANGED;
+}
+
+
+BasicJsonStringifier::Result BasicJsonStringifier::SerializeSmi(Smi* object) {
+  static const int kBufferSize = 100;
+  char chars[kBufferSize];
+  Vector<char> buffer(chars, kBufferSize);
+  Append(IntToCString(object->value(), buffer));
+  return SUCCESS;
+}
+
+
+BasicJsonStringifier::Result BasicJsonStringifier::SerializeDouble(
+    double number) {
+  if (isinf(number) || isnan(number)) {
+    Append("null");
+    return SUCCESS;
+  }
+  static const int kBufferSize = 100;
+  char chars[kBufferSize];
+  Vector<char> buffer(chars, kBufferSize);
+  Append(DoubleToCString(number, buffer));
+  return SUCCESS;
+}
+
+
+BasicJsonStringifier::Result BasicJsonStringifier::SerializeArray(
+    Handle<JSArray> object) {
+  if (StackPush(object) == CIRCULAR) return CIRCULAR;
+  int length = Smi::cast(object->length())->value();
+  Append('[');
+  switch (object->GetElementsKind()) {
+    case FAST_SMI_ELEMENTS: {
+      Handle<FixedArray> elements = Handle<FixedArray>(
+          FixedArray::cast(object->elements()));
+      for (int i = 0; i < length; i++) {
+        if (i > 0) Append(',');
+        SerializeSmi(Smi::cast(elements->get(i)));
+      }
+      break;
+    }
+    case FAST_HOLEY_SMI_ELEMENTS: {
+      Handle<FixedArray> elements = Handle<FixedArray>(
+          FixedArray::cast(object->elements()));
+      for (int i = 0; i < length; i++) {
+        if (i > 0) Append(',');
+        if (elements->is_the_hole(i)) {
+          Append("null");
+        } else {
+          SerializeSmi(Smi::cast(elements->get(i)));
+        }
+      }
+      break;
+    }
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
+    case FAST_DOUBLE_ELEMENTS: {
+      Handle<FixedDoubleArray> elements = Handle<FixedDoubleArray>(
+          FixedDoubleArray::cast(object->elements()));
+      for (int i = 0; i < length; i++) {
+        if (i > 0) Append(',');
+        SerializeDouble(elements->get_scalar(i));
+      }
+      break;
+    }
+    case FAST_HOLEY_ELEMENTS:
+    case FAST_ELEMENTS: {
+      Handle<FixedArray> elements = Handle<FixedArray>(
+          FixedArray::cast(object->elements()));
+      for (int i = 0; i < length; i++) {
+        if (i > 0) Append(',');
+        Result result = Serialize(Handle<Object>(elements->get(i)));
+        if (result == SUCCESS) continue;
+        if (result == UNCHANGED) {
+          Append("null");
+        } else {
+          return result;
+        }
+      }
+      break;
+    }
+    default:
+      return BAILOUT;
+  }
+  Append(']');
+  StackPop();
+  return SUCCESS;
+}
+
+
+BasicJsonStringifier::Result BasicJsonStringifier::SerializeObject(

[Toon Verwaest, 2012/10/17 17:52:50]

We should check for interceptors (and perhaps proxies) before serializing and
jump to the JavaScript code if so; rather than abandoning the entire
intermediate work. The same for arrays.

[Yang, 2012/10/18 12:27:33]

I'll do this in another CL.

+    Handle<JSObject> object) {
+  if (StackPush(object) == CIRCULAR) return CIRCULAR;
+  if (object->IsJSGlobalProxy()) return BAILOUT;
+  bool threw = false;
+  Handle<FixedArray> contents =
+      GetKeysInFixedArrayFor(object, LOCAL_ONLY, &threw);

[Toon Verwaest, 2012/10/17 17:52:50]

GetKeysInFixedArrayFor should probably be optimized a bit better. Currently it
copies around arrays...

More importantly: if we are just looping over fast properties without any
interceptors, we can just loop over the descriptors. The descriptors are not
only stored in order of addition (enumeration order), but also directly contain
the field index or constant function. This way we can directly get access to the
value without looking it up.

[Yang, 2012/10/18 12:27:33]

Ditto.

+  if (threw) return BAILOUT;
+  Append('{');
+  int length = contents->length();
+  bool comma = false;
+  for (int i = 0; i < length; i++) {
+    Object* key = contents->get(i);
+    Handle<String> key_handle;
+    Handle<Object> property;
+    if (key->IsString()) {
+      key_handle = Handle<String>(String::cast(key));
+      property = GetProperty(object, key_handle);
+    } else {
+      ASSERT(key->IsNumber());
+      key_handle = isolate_->factory()->NumberToString(Handle<Object>(key));
+      uint32_t index;
+      if (key->IsSmi()) {
+        property = Object::GetElement(object, Smi::cast(key)->value());
+      } else if (key_handle->AsArrayIndex(&index)) {
+        property = Object::GetElement(object, index);
+      } else {
+        property = GetProperty(object, key_handle);
+      }
+    }
+    if (property.is_null()) return BAILOUT;
+    Result result = SerializeDeferred(property, comma, key_handle);
+    if (!comma && result == SUCCESS) comma = true;
+    if (result >= BAILOUT) return result;
+  }
+  Append('}');
+  StackPop();
+  return SUCCESS;
+}
+
+
+void BasicJsonStringifier::ShrinkCurrentPart() {
+  ASSERT(current_index_ < kPartLength);
+  if (current_index_ == 0) {
+    current_part_ = isolate_->factory()->empty_string();
+    return;
+  }
+
+  int string_size, allocated_string_size;
+  if (is_ascii_) {
+    allocated_string_size = SeqAsciiString::SizeFor(kPartLength);
+    string_size = SeqAsciiString::SizeFor(current_index_);
+  } else {
+    allocated_string_size = SeqTwoByteString::SizeFor(kPartLength);
+    string_size = SeqTwoByteString::SizeFor(current_index_);
+  }
+
+  int delta = allocated_string_size - string_size;
+  current_part_->set_length(current_index_);
+
+  Address end_of_string = current_part_->address() + string_size;
+  isolate_->heap()->CreateFillerObjectAt(end_of_string, delta);

[Toon Verwaest, 2012/10/17 17:52:50]

Maybe add a comment saying that this relies on word-alignment of the
string_size.

+  if (Marking::IsBlack(Marking::MarkBitFrom(*current_part_))) {
+    MemoryChunk::IncrementLiveBytesFromMutator(
+        current_part_->address(), -delta);
+  }
+}
+
+
+template <bool is_ascii>
+void BasicJsonStringifier::Extend() {
+  accumulator_ =
+      isolate_->factory()->NewConsString(accumulator_, current_part_);
+  if (is_ascii) {
+    current_part_ =
+        isolate_->factory()->NewRawAsciiString(kPartLength);
+  } else {
+    current_part_ =
+        isolate_->factory()->NewRawTwoByteString(kPartLength);
+  }
+  current_index_ = 0;
+}
+
+
+void BasicJsonStringifier::ChangeEncoding() {
+  ShrinkCurrentPart();
+  accumulator_ = isolate_->factory()->NewConsString(accumulator_,
+                                                    current_part_);
+  current_part_ =
+      isolate_->factory()->NewRawTwoByteString(kPartLength);
+  current_index_ = 0;
+  is_ascii_ = false;
+}
+
+
+template <bool is_ascii, typename Char>
+void BasicJsonStringifier::SerializeString_(Vector<const Char> vector) {
+  int length = vector.length();
+  if (current_index_ + (length << 3) <= (kPartLength - 2)) {
+    AppendUnchecked_<is_ascii, char>('"');
+    for (int i = 0; i < length; i++) {
+      Char c = vector[i];
+      if ((c >= '#' && c <= '~' && c != '\\') ||
+          (!is_ascii && ((c & 0xFF80) != 0))) {
+        AppendUnchecked_<is_ascii, Char>(c);
+      } else {
+        AppendUnchecked_<is_ascii, char>(
+            &JsonQuotes[c * kJsonQuotesCharactersPerEntry]);
+      }
+    }
+    AppendUnchecked_<is_ascii, char>('"');
+  } else {
+    Append_<is_ascii, char>('"');
+    for (int i = 0; i < length; i++) {
+      Char c = vector[i];
+      if ((c >= '#' && c <= '~' && c != '\\') ||
+          (!is_ascii && ((c & 0xFF80) != 0))) {
+        Append_<is_ascii, Char>(c);
+      } else {
+        Append_<is_ascii, char>(&JsonQuotes[c * kJsonQuotesCharactersPerEntry]);
+      }
+    }
+    Append_<is_ascii, char>('"');
+  }
+}
+
+
+void BasicJsonStringifier::SerializeString(Handle<String> object) {
+  FlattenString(object);
+  String::FlatContent flat = object->GetFlatContent();
+  if (is_ascii_) {
+    if (flat.IsAscii()) {
+      SerializeString_<true, char>(flat.ToAsciiVector());
+    } else {
+      ChangeEncoding();
+      SerializeString(object);
+    }
+  } else {
+    if (flat.IsAscii()) {
+      SerializeString_<false, char>(flat.ToAsciiVector());
+    } else {
+      SerializeString_<false, uc16>(flat.ToUC16Vector());
+    }
+  }
+}
+
+} }  // namespace v8::internal
+
+#endif  // V8_JSON_STRINGIFIER_H_