1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/json/json-stringifier.h"
6
7#include "src/base/strings.h"
8#include "src/common/message-template.h"
9#include "src/numbers/conversions.h"
10#include "src/objects/heap-number-inl.h"
11#include "src/objects/js-array-inl.h"
12#include "src/objects/lookup.h"
13#include "src/objects/objects-inl.h"
14#include "src/objects/oddball-inl.h"
15#include "src/objects/ordered-hash-table.h"
16#include "src/objects/smi.h"
17#include "src/strings/string-builder-inl.h"
18#include "src/utils/utils.h"
19
20namespace v8 {
21namespace internal {
22
23class JsonStringifier {
24 public:
25  explicit JsonStringifier(Isolate* isolate);
26
27  ~JsonStringifier() { DeleteArray(gap_); }
28
29  V8_WARN_UNUSED_RESULT MaybeHandle<Object> Stringify(Handle<Object> object,
30                                                      Handle<Object> replacer,
31                                                      Handle<Object> gap);
32
33 private:
34  enum Result { UNCHANGED, SUCCESS, EXCEPTION };
35
36  bool InitializeReplacer(Handle<Object> replacer);
37  bool InitializeGap(Handle<Object> gap);
38
39  V8_WARN_UNUSED_RESULT MaybeHandle<Object> ApplyToJsonFunction(
40      Handle<Object> object, Handle<Object> key);
41  V8_WARN_UNUSED_RESULT MaybeHandle<Object> ApplyReplacerFunction(
42      Handle<Object> value, Handle<Object> key, Handle<Object> initial_holder);
43
44  // Entry point to serialize the object.
45  V8_INLINE Result SerializeObject(Handle<Object> obj) {
46    return Serialize_<false>(obj, false, factory()->empty_string());
47  }
48
49  // Serialize an array element.
50  // The index may serve as argument for the toJSON function.
51  V8_INLINE Result SerializeElement(Isolate* isolate, Handle<Object> object,
52                                    int i) {
53    return Serialize_<false>(object, false,
54                             Handle<Object>(Smi::FromInt(i), isolate));
55  }
56
57  // Serialize a object property.
58  // The key may or may not be serialized depending on the property.
59  // The key may also serve as argument for the toJSON function.
60  V8_INLINE Result SerializeProperty(Handle<Object> object, bool deferred_comma,
61                                     Handle<String> deferred_key) {
62    DCHECK(!deferred_key.is_null());
63    return Serialize_<true>(object, deferred_comma, deferred_key);
64  }
65
66  template <bool deferred_string_key>
67  Result Serialize_(Handle<Object> object, bool comma, Handle<Object> key);
68
69  V8_INLINE void SerializeDeferredKey(bool deferred_comma,
70                                      Handle<Object> deferred_key);
71
72  Result SerializeSmi(Smi object);
73
74  Result SerializeDouble(double number);
75  V8_INLINE Result SerializeHeapNumber(Handle<HeapNumber> object) {
76    return SerializeDouble(object->value());
77  }
78
79  Result SerializeJSPrimitiveWrapper(Handle<JSPrimitiveWrapper> object,
80                                     Handle<Object> key);
81
82  V8_INLINE Result SerializeJSArray(Handle<JSArray> object, Handle<Object> key);
83  V8_INLINE Result SerializeJSObject(Handle<JSObject> object,
84                                     Handle<Object> key);
85
86  Result SerializeJSProxy(Handle<JSProxy> object, Handle<Object> key);
87  Result SerializeJSReceiverSlow(Handle<JSReceiver> object);
88  Result SerializeArrayLikeSlow(Handle<JSReceiver> object, uint32_t start,
89                                uint32_t length);
90
91  void SerializeString(Handle<String> object);
92
93  template <typename SrcChar, typename DestChar>
94  V8_INLINE static void SerializeStringUnchecked_(
95      base::Vector<const SrcChar> src,
96      IncrementalStringBuilder::NoExtend<DestChar>* dest);
97
98  template <typename SrcChar, typename DestChar>
99  V8_INLINE void SerializeString_(Handle<String> string);
100
101  template <typename Char>
102  V8_INLINE static bool DoNotEscape(Char c);
103
104  V8_INLINE void NewLine();
105  V8_NOINLINE void NewLineOutline();
106  V8_INLINE void Indent() { indent_++; }
107  V8_INLINE void Unindent() { indent_--; }
108  V8_INLINE void Separator(bool first);
109
110  Handle<JSReceiver> CurrentHolder(Handle<Object> value,
111                                   Handle<Object> inital_holder);
112
113  Result StackPush(Handle<Object> object, Handle<Object> key);
114  void StackPop();
115
116  // Uses the current stack_ to provide a detailed error message of
117  // the objects involved in the circular structure.
118  Handle<String> ConstructCircularStructureErrorMessage(Handle<Object> last_key,
119                                                        size_t start_index);
120  // The prefix and postfix count do NOT include the starting and
121  // closing lines of the error message.
122  static const int kCircularErrorMessagePrefixCount = 2;
123  static const int kCircularErrorMessagePostfixCount = 1;
124
125  Factory* factory() { return isolate_->factory(); }
126
127  Isolate* isolate_;
128  IncrementalStringBuilder builder_;
129  Handle<String> tojson_string_;
130  Handle<FixedArray> property_list_;
131  Handle<JSReceiver> replacer_function_;
132  base::uc16* gap_;
133  int indent_;
134
135  using KeyObject = std::pair<Handle<Object>, Handle<Object>>;
136  std::vector<KeyObject> stack_;
137
138  static const int kJsonEscapeTableEntrySize = 8;
139  static const char* const JsonEscapeTable;
140};
141
142MaybeHandle<Object> JsonStringify(Isolate* isolate, Handle<Object> object,
143                                  Handle<Object> replacer, Handle<Object> gap) {
144  JsonStringifier stringifier(isolate);
145  return stringifier.Stringify(object, replacer, gap);
146}
147
148// Translation table to escape Latin1 characters.
149// Table entries start at a multiple of 8 and are null-terminated.
150const char* const JsonStringifier::JsonEscapeTable =
151    "\\u0000\0 \\u0001\0 \\u0002\0 \\u0003\0 "
152    "\\u0004\0 \\u0005\0 \\u0006\0 \\u0007\0 "
153    "\\b\0     \\t\0     \\n\0     \\u000b\0 "
154    "\\f\0     \\r\0     \\u000e\0 \\u000f\0 "
155    "\\u0010\0 \\u0011\0 \\u0012\0 \\u0013\0 "
156    "\\u0014\0 \\u0015\0 \\u0016\0 \\u0017\0 "
157    "\\u0018\0 \\u0019\0 \\u001a\0 \\u001b\0 "
158    "\\u001c\0 \\u001d\0 \\u001e\0 \\u001f\0 "
159    " \0      !\0      \\\"\0     #\0      "
160    "$\0      %\0      &\0      '\0      "
161    "(\0      )\0      *\0      +\0      "
162    ",\0      -\0      .\0      /\0      "
163    "0\0      1\0      2\0      3\0      "
164    "4\0      5\0      6\0      7\0      "
165    "8\0      9\0      :\0      ;\0      "
166    "<\0      =\0      >\0      ?\0      "
167    "@\0      A\0      B\0      C\0      "
168    "D\0      E\0      F\0      G\0      "
169    "H\0      I\0      J\0      K\0      "
170    "L\0      M\0      N\0      O\0      "
171    "P\0      Q\0      R\0      S\0      "
172    "T\0      U\0      V\0      W\0      "
173    "X\0      Y\0      Z\0      [\0      "
174    "\\\\\0     ]\0      ^\0      _\0      "
175    "`\0      a\0      b\0      c\0      "
176    "d\0      e\0      f\0      g\0      "
177    "h\0      i\0      j\0      k\0      "
178    "l\0      m\0      n\0      o\0      "
179    "p\0      q\0      r\0      s\0      "
180    "t\0      u\0      v\0      w\0      "
181    "x\0      y\0      z\0      {\0      "
182    "|\0      }\0      ~\0      \x7F\0      "
183    "\x80\0      \x81\0      \x82\0      \x83\0      "
184    "\x84\0      \x85\0      \x86\0      \x87\0      "
185    "\x88\0      \x89\0      \x8A\0      \x8B\0      "
186    "\x8C\0      \x8D\0      \x8E\0      \x8F\0      "
187    "\x90\0      \x91\0      \x92\0      \x93\0      "
188    "\x94\0      \x95\0      \x96\0      \x97\0      "
189    "\x98\0      \x99\0      \x9A\0      \x9B\0      "
190    "\x9C\0      \x9D\0      \x9E\0      \x9F\0      "
191    "\xA0\0      \xA1\0      \xA2\0      \xA3\0      "
192    "\xA4\0      \xA5\0      \xA6\0      \xA7\0      "
193    "\xA8\0      \xA9\0      \xAA\0      \xAB\0      "
194    "\xAC\0      \xAD\0      \xAE\0      \xAF\0      "
195    "\xB0\0      \xB1\0      \xB2\0      \xB3\0      "
196    "\xB4\0      \xB5\0      \xB6\0      \xB7\0      "
197    "\xB8\0      \xB9\0      \xBA\0      \xBB\0      "
198    "\xBC\0      \xBD\0      \xBE\0      \xBF\0      "
199    "\xC0\0      \xC1\0      \xC2\0      \xC3\0      "
200    "\xC4\0      \xC5\0      \xC6\0      \xC7\0      "
201    "\xC8\0      \xC9\0      \xCA\0      \xCB\0      "
202    "\xCC\0      \xCD\0      \xCE\0      \xCF\0      "
203    "\xD0\0      \xD1\0      \xD2\0      \xD3\0      "
204    "\xD4\0      \xD5\0      \xD6\0      \xD7\0      "
205    "\xD8\0      \xD9\0      \xDA\0      \xDB\0      "
206    "\xDC\0      \xDD\0      \xDE\0      \xDF\0      "
207    "\xE0\0      \xE1\0      \xE2\0      \xE3\0      "
208    "\xE4\0      \xE5\0      \xE6\0      \xE7\0      "
209    "\xE8\0      \xE9\0      \xEA\0      \xEB\0      "
210    "\xEC\0      \xED\0      \xEE\0      \xEF\0      "
211    "\xF0\0      \xF1\0      \xF2\0      \xF3\0      "
212    "\xF4\0      \xF5\0      \xF6\0      \xF7\0      "
213    "\xF8\0      \xF9\0      \xFA\0      \xFB\0      "
214    "\xFC\0      \xFD\0      \xFE\0      \xFF\0      ";
215
216JsonStringifier::JsonStringifier(Isolate* isolate)
217    : isolate_(isolate),
218      builder_(isolate),
219      gap_(nullptr),
220      indent_(0),
221      stack_() {
222  tojson_string_ = factory()->toJSON_string();
223}
224
225MaybeHandle<Object> JsonStringifier::Stringify(Handle<Object> object,
226                                               Handle<Object> replacer,
227                                               Handle<Object> gap) {
228  if (!InitializeReplacer(replacer)) return MaybeHandle<Object>();
229  if (!gap->IsUndefined(isolate_) && !InitializeGap(gap)) {
230    return MaybeHandle<Object>();
231  }
232  Result result = SerializeObject(object);
233  if (result == UNCHANGED) return factory()->undefined_value();
234  if (result == SUCCESS) return builder_.Finish();
235  DCHECK(result == EXCEPTION);
236  return MaybeHandle<Object>();
237}
238
239bool JsonStringifier::InitializeReplacer(Handle<Object> replacer) {
240  DCHECK(property_list_.is_null());
241  DCHECK(replacer_function_.is_null());
242  Maybe<bool> is_array = Object::IsArray(replacer);
243  if (is_array.IsNothing()) return false;
244  if (is_array.FromJust()) {
245    HandleScope handle_scope(isolate_);
246    Handle<OrderedHashSet> set = factory()->NewOrderedHashSet();
247    Handle<Object> length_obj;
248    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
249        isolate_, length_obj,
250        Object::GetLengthFromArrayLike(isolate_,
251                                       Handle<JSReceiver>::cast(replacer)),
252        false);
253    uint32_t length;
254    if (!length_obj->ToUint32(&length)) length = kMaxUInt32;
255    for (uint32_t i = 0; i < length; i++) {
256      Handle<Object> element;
257      Handle<String> key;
258      ASSIGN_RETURN_ON_EXCEPTION_VALUE(
259          isolate_, element, Object::GetElement(isolate_, replacer, i), false);
260      if (element->IsNumber() || element->IsString()) {
261        ASSIGN_RETURN_ON_EXCEPTION_VALUE(
262            isolate_, key, Object::ToString(isolate_, element), false);
263      } else if (element->IsJSPrimitiveWrapper()) {
264        Handle<Object> value(Handle<JSPrimitiveWrapper>::cast(element)->value(),
265                             isolate_);
266        if (value->IsNumber() || value->IsString()) {
267          ASSIGN_RETURN_ON_EXCEPTION_VALUE(
268              isolate_, key, Object::ToString(isolate_, element), false);
269        }
270      }
271      if (key.is_null()) continue;
272      // Object keys are internalized, so do it here.
273      key = factory()->InternalizeString(key);
274      MaybeHandle<OrderedHashSet> set_candidate =
275          OrderedHashSet::Add(isolate_, set, key);
276      if (!set_candidate.ToHandle(&set)) {
277        return false;
278      }
279    }
280    property_list_ = OrderedHashSet::ConvertToKeysArray(
281        isolate_, set, GetKeysConversion::kKeepNumbers);
282    property_list_ = handle_scope.CloseAndEscape(property_list_);
283  } else if (replacer->IsCallable()) {
284    replacer_function_ = Handle<JSReceiver>::cast(replacer);
285  }
286  return true;
287}
288
289bool JsonStringifier::InitializeGap(Handle<Object> gap) {
290  DCHECK_NULL(gap_);
291  HandleScope scope(isolate_);
292  if (gap->IsJSPrimitiveWrapper()) {
293    Handle<Object> value(Handle<JSPrimitiveWrapper>::cast(gap)->value(),
294                         isolate_);
295    if (value->IsString()) {
296      ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate_, gap,
297                                       Object::ToString(isolate_, gap), false);
298    } else if (value->IsNumber()) {
299      ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate_, gap,
300                                       Object::ToNumber(isolate_, gap), false);
301    }
302  }
303
304  if (gap->IsString()) {
305    Handle<String> gap_string = Handle<String>::cast(gap);
306    if (gap_string->length() > 0) {
307      int gap_length = std::min(gap_string->length(), 10);
308      gap_ = NewArray<base::uc16>(gap_length + 1);
309      String::WriteToFlat(*gap_string, gap_, 0, gap_length);
310      for (int i = 0; i < gap_length; i++) {
311        if (gap_[i] > String::kMaxOneByteCharCode) {
312          builder_.ChangeEncoding();
313          break;
314        }
315      }
316      gap_[gap_length] = '\0';
317    }
318  } else if (gap->IsNumber()) {
319    double value = std::min(gap->Number(), 10.0);
320    if (value > 0) {
321      int gap_length = DoubleToInt32(value);
322      gap_ = NewArray<base::uc16>(gap_length + 1);
323      for (int i = 0; i < gap_length; i++) gap_[i] = ' ';
324      gap_[gap_length] = '\0';
325    }
326  }
327  return true;
328}
329
330MaybeHandle<Object> JsonStringifier::ApplyToJsonFunction(Handle<Object> object,
331                                                         Handle<Object> key) {
332  HandleScope scope(isolate_);
333
334  // Retrieve toJSON function. The LookupIterator automatically handles
335  // the ToObject() equivalent ("GetRoot") if {object} is a BigInt.
336  Handle<Object> fun;
337  LookupIterator it(isolate_, object, tojson_string_,
338                    LookupIterator::PROTOTYPE_CHAIN_SKIP_INTERCEPTOR);
339  ASSIGN_RETURN_ON_EXCEPTION(isolate_, fun, Object::GetProperty(&it), Object);
340  if (!fun->IsCallable()) return object;
341
342  // Call toJSON function.
343  if (key->IsSmi()) key = factory()->NumberToString(key);
344  Handle<Object> argv[] = {key};
345  ASSIGN_RETURN_ON_EXCEPTION(isolate_, object,
346                             Execution::Call(isolate_, fun, object, 1, argv),
347                             Object);
348  return scope.CloseAndEscape(object);
349}
350
351MaybeHandle<Object> JsonStringifier::ApplyReplacerFunction(
352    Handle<Object> value, Handle<Object> key, Handle<Object> initial_holder) {
353  HandleScope scope(isolate_);
354  if (key->IsSmi()) key = factory()->NumberToString(key);
355  Handle<Object> argv[] = {key, value};
356  Handle<JSReceiver> holder = CurrentHolder(value, initial_holder);
357  ASSIGN_RETURN_ON_EXCEPTION(
358      isolate_, value,
359      Execution::Call(isolate_, replacer_function_, holder, 2, argv), Object);
360  return scope.CloseAndEscape(value);
361}
362
363Handle<JSReceiver> JsonStringifier::CurrentHolder(
364    Handle<Object> value, Handle<Object> initial_holder) {
365  if (stack_.empty()) {
366    Handle<JSObject> holder =
367        factory()->NewJSObject(isolate_->object_function());
368    JSObject::AddProperty(isolate_, holder, factory()->empty_string(),
369                          initial_holder, NONE);
370    return holder;
371  } else {
372    return Handle<JSReceiver>(JSReceiver::cast(*stack_.back().second),
373                              isolate_);
374  }
375}
376
377JsonStringifier::Result JsonStringifier::StackPush(Handle<Object> object,
378                                                   Handle<Object> key) {
379  StackLimitCheck check(isolate_);
380  if (check.HasOverflowed()) {
381    isolate_->StackOverflow();
382    return EXCEPTION;
383  }
384
385  {
386    DisallowGarbageCollection no_gc;
387    Object raw_obj = *object;
388    size_t size = stack_.size();
389    for (size_t i = 0; i < size; ++i) {
390      if (*stack_[i].second == raw_obj) {
391        AllowGarbageCollection allow_to_return_error;
392        Handle<String> circle_description =
393            ConstructCircularStructureErrorMessage(key, i);
394        Handle<Object> error = factory()->NewTypeError(
395            MessageTemplate::kCircularStructure, circle_description);
396        isolate_->Throw(*error);
397        return EXCEPTION;
398      }
399    }
400  }
401  stack_.emplace_back(key, object);
402  return SUCCESS;
403}
404
405void JsonStringifier::StackPop() { stack_.pop_back(); }
406
407class CircularStructureMessageBuilder {
408 public:
409  explicit CircularStructureMessageBuilder(Isolate* isolate)
410      : builder_(isolate) {}
411
412  void AppendStartLine(Handle<Object> start_object) {
413    builder_.AppendCString(kStartPrefix);
414    builder_.AppendCStringLiteral("starting at object with constructor ");
415    AppendConstructorName(start_object);
416  }
417
418  void AppendNormalLine(Handle<Object> key, Handle<Object> object) {
419    builder_.AppendCString(kLinePrefix);
420    AppendKey(key);
421    builder_.AppendCStringLiteral(" -> object with constructor ");
422    AppendConstructorName(object);
423  }
424
425  void AppendClosingLine(Handle<Object> closing_key) {
426    builder_.AppendCString(kEndPrefix);
427    AppendKey(closing_key);
428    builder_.AppendCStringLiteral(" closes the circle");
429  }
430
431  void AppendEllipsis() {
432    builder_.AppendCString(kLinePrefix);
433    builder_.AppendCStringLiteral("...");
434  }
435
436  MaybeHandle<String> Finish() { return builder_.Finish(); }
437
438 private:
439  void AppendConstructorName(Handle<Object> object) {
440    builder_.AppendCharacter('\'');
441    Handle<String> constructor_name = JSReceiver::GetConstructorName(
442        builder_.isolate(), Handle<JSReceiver>::cast(object));
443    builder_.AppendString(constructor_name);
444    builder_.AppendCharacter('\'');
445  }
446
447  // A key can either be a string, the empty string or a Smi.
448  void AppendKey(Handle<Object> key) {
449    if (key->IsSmi()) {
450      builder_.AppendCStringLiteral("index ");
451      AppendSmi(Smi::cast(*key));
452      return;
453    }
454
455    CHECK(key->IsString());
456    Handle<String> key_as_string = Handle<String>::cast(key);
457    if (key_as_string->length() == 0) {
458      builder_.AppendCStringLiteral("<anonymous>");
459    } else {
460      builder_.AppendCStringLiteral("property '");
461      builder_.AppendString(key_as_string);
462      builder_.AppendCharacter('\'');
463    }
464  }
465
466  void AppendSmi(Smi smi) {
467    static const int kBufferSize = 100;
468    char chars[kBufferSize];
469    base::Vector<char> buffer(chars, kBufferSize);
470    builder_.AppendCString(IntToCString(smi.value(), buffer));
471  }
472
473  IncrementalStringBuilder builder_;
474  static constexpr const char* kStartPrefix = "\n    --> ";
475  static constexpr const char* kEndPrefix = "\n    --- ";
476  static constexpr const char* kLinePrefix = "\n    |     ";
477};
478
479Handle<String> JsonStringifier::ConstructCircularStructureErrorMessage(
480    Handle<Object> last_key, size_t start_index) {
481  DCHECK(start_index < stack_.size());
482  CircularStructureMessageBuilder builder(isolate_);
483
484  // We track the index to be printed next for better readability.
485  size_t index = start_index;
486  const size_t stack_size = stack_.size();
487
488  builder.AppendStartLine(stack_[index++].second);
489
490  // Append a maximum of kCircularErrorMessagePrefixCount normal lines.
491  const size_t prefix_end =
492      std::min(stack_size, index + kCircularErrorMessagePrefixCount);
493  for (; index < prefix_end; ++index) {
494    builder.AppendNormalLine(stack_[index].first, stack_[index].second);
495  }
496
497  // If the circle consists of too many objects, we skip them and just
498  // print an ellipsis.
499  if (stack_size > index + kCircularErrorMessagePostfixCount) {
500    builder.AppendEllipsis();
501  }
502
503  // Since we calculate the postfix lines from the back of the stack,
504  // we have to ensure that lines are not printed twice.
505  index = std::max(index, stack_size - kCircularErrorMessagePostfixCount);
506  for (; index < stack_size; ++index) {
507    builder.AppendNormalLine(stack_[index].first, stack_[index].second);
508  }
509
510  builder.AppendClosingLine(last_key);
511
512  Handle<String> result;
513  ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate_, result, builder.Finish(),
514                                   factory()->empty_string());
515  return result;
516}
517
518template <bool deferred_string_key>
519JsonStringifier::Result JsonStringifier::Serialize_(Handle<Object> object,
520                                                    bool comma,
521                                                    Handle<Object> key) {
522  StackLimitCheck interrupt_check(isolate_);
523  if (interrupt_check.InterruptRequested() &&
524      isolate_->stack_guard()->HandleInterrupts().IsException(isolate_)) {
525    return EXCEPTION;
526  }
527
528  Handle<Object> initial_value = object;
529  PtrComprCageBase cage_base(isolate_);
530  if (!object->IsSmi()) {
531    InstanceType instance_type =
532        HeapObject::cast(*object).map(cage_base).instance_type();
533    if (InstanceTypeChecker::IsJSReceiver(instance_type) ||
534        InstanceTypeChecker::IsBigInt(instance_type)) {
535      ASSIGN_RETURN_ON_EXCEPTION_VALUE(
536          isolate_, object, ApplyToJsonFunction(object, key), EXCEPTION);
537    }
538  }
539  if (!replacer_function_.is_null()) {
540    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
541        isolate_, object, ApplyReplacerFunction(object, key, initial_value),
542        EXCEPTION);
543  }
544
545  if (object->IsSmi()) {
546    if (deferred_string_key) SerializeDeferredKey(comma, key);
547    return SerializeSmi(Smi::cast(*object));
548  }
549
550  InstanceType instance_type =
551      HeapObject::cast(*object).map(cage_base).instance_type();
552  switch (instance_type) {
553    case HEAP_NUMBER_TYPE:
554      if (deferred_string_key) SerializeDeferredKey(comma, key);
555      return SerializeHeapNumber(Handle<HeapNumber>::cast(object));
556    case BIGINT_TYPE:
557      isolate_->Throw(
558          *factory()->NewTypeError(MessageTemplate::kBigIntSerializeJSON));
559      return EXCEPTION;
560    case ODDBALL_TYPE:
561      switch (Oddball::cast(*object).kind()) {
562        case Oddball::kFalse:
563          if (deferred_string_key) SerializeDeferredKey(comma, key);
564          builder_.AppendCStringLiteral("false");
565          return SUCCESS;
566        case Oddball::kTrue:
567          if (deferred_string_key) SerializeDeferredKey(comma, key);
568          builder_.AppendCStringLiteral("true");
569          return SUCCESS;
570        case Oddball::kNull:
571          if (deferred_string_key) SerializeDeferredKey(comma, key);
572          builder_.AppendCStringLiteral("null");
573          return SUCCESS;
574        default:
575          return UNCHANGED;
576      }
577    case JS_ARRAY_TYPE:
578      if (deferred_string_key) SerializeDeferredKey(comma, key);
579      return SerializeJSArray(Handle<JSArray>::cast(object), key);
580    case JS_PRIMITIVE_WRAPPER_TYPE:
581      if (deferred_string_key) SerializeDeferredKey(comma, key);
582      return SerializeJSPrimitiveWrapper(
583          Handle<JSPrimitiveWrapper>::cast(object), key);
584    case SYMBOL_TYPE:
585      return UNCHANGED;
586    default:
587      if (InstanceTypeChecker::IsString(instance_type)) {
588        if (deferred_string_key) SerializeDeferredKey(comma, key);
589        SerializeString(Handle<String>::cast(object));
590        return SUCCESS;
591      } else {
592        DCHECK(object->IsJSReceiver());
593        if (HeapObject::cast(*object).IsCallable(cage_base)) return UNCHANGED;
594        // Go to slow path for global proxy and objects requiring access checks.
595        if (deferred_string_key) SerializeDeferredKey(comma, key);
596        if (InstanceTypeChecker::IsJSProxy(instance_type)) {
597          return SerializeJSProxy(Handle<JSProxy>::cast(object), key);
598        }
599        return SerializeJSObject(Handle<JSObject>::cast(object), key);
600      }
601  }
602
603  UNREACHABLE();
604}
605
606JsonStringifier::Result JsonStringifier::SerializeJSPrimitiveWrapper(
607    Handle<JSPrimitiveWrapper> object, Handle<Object> key) {
608  Object raw = object->value();
609  if (raw.IsString()) {
610    Handle<Object> value;
611    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
612        isolate_, value, Object::ToString(isolate_, object), EXCEPTION);
613    SerializeString(Handle<String>::cast(value));
614  } else if (raw.IsNumber()) {
615    Handle<Object> value;
616    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
617        isolate_, value, Object::ToNumber(isolate_, object), EXCEPTION);
618    if (value->IsSmi()) return SerializeSmi(Smi::cast(*value));
619    SerializeHeapNumber(Handle<HeapNumber>::cast(value));
620  } else if (raw.IsBigInt()) {
621    isolate_->Throw(
622        *factory()->NewTypeError(MessageTemplate::kBigIntSerializeJSON));
623    return EXCEPTION;
624  } else if (raw.IsBoolean()) {
625    if (raw.IsTrue(isolate_)) {
626      builder_.AppendCStringLiteral("true");
627    } else {
628      builder_.AppendCStringLiteral("false");
629    }
630  } else {
631    // ES6 24.3.2.1 step 10.c, serialize as an ordinary JSObject.
632    return SerializeJSObject(object, key);
633  }
634  return SUCCESS;
635}
636
637JsonStringifier::Result JsonStringifier::SerializeSmi(Smi object) {
638  static const int kBufferSize = 100;
639  char chars[kBufferSize];
640  base::Vector<char> buffer(chars, kBufferSize);
641  builder_.AppendCString(IntToCString(object.value(), buffer));
642  return SUCCESS;
643}
644
645JsonStringifier::Result JsonStringifier::SerializeDouble(double number) {
646  if (std::isinf(number) || std::isnan(number)) {
647    builder_.AppendCStringLiteral("null");
648    return SUCCESS;
649  }
650  static const int kBufferSize = 100;
651  char chars[kBufferSize];
652  base::Vector<char> buffer(chars, kBufferSize);
653  builder_.AppendCString(DoubleToCString(number, buffer));
654  return SUCCESS;
655}
656
657JsonStringifier::Result JsonStringifier::SerializeJSArray(
658    Handle<JSArray> object, Handle<Object> key) {
659  uint32_t length = 0;
660  CHECK(object->length().ToArrayLength(&length));
661  DCHECK(!object->IsAccessCheckNeeded());
662  if (length == 0) {
663    builder_.AppendCStringLiteral("[]");
664    return SUCCESS;
665  }
666
667  PtrComprCageBase cage_base(isolate_);
668  Result stack_push = StackPush(object, key);
669  if (stack_push != SUCCESS) return stack_push;
670
671  builder_.AppendCharacter('[');
672  Indent();
673  uint32_t i = 0;
674  if (replacer_function_.is_null()) {
675    StackLimitCheck interrupt_check(isolate_);
676    const uint32_t kInterruptLength = 4000;
677    uint32_t limit = std::min(length, kInterruptLength);
678    const uint32_t kMaxAllowedFastPackedLength =
679        std::numeric_limits<uint32_t>::max() - kInterruptLength;
680    STATIC_ASSERT(FixedArray::kMaxLength < kMaxAllowedFastPackedLength);
681    switch (object->GetElementsKind(cage_base)) {
682      case PACKED_SMI_ELEMENTS: {
683        Handle<FixedArray> elements(
684            FixedArray::cast(object->elements(cage_base)), isolate_);
685        while (true) {
686          for (; i < limit; i++) {
687            Separator(i == 0);
688            SerializeSmi(Smi::cast(elements->get(cage_base, i)));
689          }
690          if (i >= length) break;
691          DCHECK_LT(limit, kMaxAllowedFastPackedLength);
692          limit = std::min(length, limit + kInterruptLength);
693          if (interrupt_check.InterruptRequested() &&
694              isolate_->stack_guard()->HandleInterrupts().IsException(
695                  isolate_)) {
696            return EXCEPTION;
697          }
698        }
699        break;
700      }
701      case PACKED_DOUBLE_ELEMENTS: {
702        Handle<FixedDoubleArray> elements(
703            FixedDoubleArray::cast(object->elements(cage_base)), isolate_);
704        while (true) {
705          for (; i < limit; i++) {
706            Separator(i == 0);
707            SerializeDouble(elements->get_scalar(i));
708          }
709          if (i >= length) break;
710          DCHECK_LT(limit, kMaxAllowedFastPackedLength);
711          limit = std::min(length, limit + kInterruptLength);
712          if (interrupt_check.InterruptRequested() &&
713              isolate_->stack_guard()->HandleInterrupts().IsException(
714                  isolate_)) {
715            return EXCEPTION;
716          }
717        }
718        break;
719      }
720      case PACKED_ELEMENTS: {
721        HandleScope handle_scope(isolate_);
722        Handle<Object> old_length(object->length(), isolate_);
723        for (i = 0; i < length; i++) {
724          if (object->length() != *old_length ||
725              object->GetElementsKind(cage_base) != PACKED_ELEMENTS) {
726            // Fall back to slow path.
727            break;
728          }
729          Separator(i == 0);
730          Result result = SerializeElement(
731              isolate_,
732              handle(FixedArray::cast(object->elements()).get(cage_base, i),
733                     isolate_),
734              i);
735          if (result == UNCHANGED) {
736            builder_.AppendCStringLiteral("null");
737          } else if (result != SUCCESS) {
738            return result;
739          }
740        }
741        break;
742      }
743      default:
744        break;
745    }
746  }
747  if (i < length) {
748    // Slow path for non-fast elements and fall-back in edge case.
749    Result result = SerializeArrayLikeSlow(object, i, length);
750    if (result != SUCCESS) return result;
751  }
752  Unindent();
753  NewLine();
754  builder_.AppendCharacter(']');
755  StackPop();
756  return SUCCESS;
757}
758
759JsonStringifier::Result JsonStringifier::SerializeArrayLikeSlow(
760    Handle<JSReceiver> object, uint32_t start, uint32_t length) {
761  // We need to write out at least two characters per array element.
762  static const int kMaxSerializableArrayLength = String::kMaxLength / 2;
763  if (length > kMaxSerializableArrayLength) {
764    isolate_->Throw(*isolate_->factory()->NewInvalidStringLengthError());
765    return EXCEPTION;
766  }
767  HandleScope handle_scope(isolate_);
768  for (uint32_t i = start; i < length; i++) {
769    Separator(i == 0);
770    Handle<Object> element;
771    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
772        isolate_, element, JSReceiver::GetElement(isolate_, object, i),
773        EXCEPTION);
774    Result result = SerializeElement(isolate_, element, i);
775    if (result == SUCCESS) continue;
776    if (result == UNCHANGED) {
777      // Detect overflow sooner for large sparse arrays.
778      if (builder_.HasOverflowed()) return EXCEPTION;
779      builder_.AppendCStringLiteral("null");
780    } else {
781      return result;
782    }
783  }
784  return SUCCESS;
785}
786
787namespace {
788V8_INLINE bool CanFastSerializeJSObject(PtrComprCageBase cage_base,
789                                        JSObject raw_object, Isolate* isolate) {
790  DisallowGarbageCollection no_gc;
791  if (raw_object.map(cage_base).IsCustomElementsReceiverMap()) return false;
792  if (!raw_object.HasFastProperties(cage_base)) return false;
793  auto roots = ReadOnlyRoots(isolate);
794  auto elements = raw_object.elements(cage_base);
795  return elements == roots.empty_fixed_array() ||
796         elements == roots.empty_slow_element_dictionary();
797}
798}  // namespace
799
800JsonStringifier::Result JsonStringifier::SerializeJSObject(
801    Handle<JSObject> object, Handle<Object> key) {
802  PtrComprCageBase cage_base(isolate_);
803  HandleScope handle_scope(isolate_);
804
805  if (!property_list_.is_null() ||
806      !CanFastSerializeJSObject(cage_base, *object, isolate_)) {
807    Result stack_push = StackPush(object, key);
808    if (stack_push != SUCCESS) return stack_push;
809    Result result = SerializeJSReceiverSlow(object);
810    if (result != SUCCESS) return result;
811    StackPop();
812    return SUCCESS;
813  }
814
815  DCHECK(!object->IsJSGlobalProxy());
816  DCHECK(!object->HasIndexedInterceptor());
817  DCHECK(!object->HasNamedInterceptor());
818
819  Handle<Map> map(object->map(cage_base), isolate_);
820  if (map->NumberOfOwnDescriptors() == 0) {
821    builder_.AppendCStringLiteral("{}");
822    return SUCCESS;
823  }
824
825  Result stack_push = StackPush(object, key);
826  if (stack_push != SUCCESS) return stack_push;
827  builder_.AppendCharacter('{');
828  Indent();
829  bool comma = false;
830  for (InternalIndex i : map->IterateOwnDescriptors()) {
831    Handle<String> key_name;
832    PropertyDetails details = PropertyDetails::Empty();
833    {
834      DisallowGarbageCollection no_gc;
835      DescriptorArray descriptors = map->instance_descriptors(cage_base);
836      Name name = descriptors.GetKey(i);
837      // TODO(rossberg): Should this throw?
838      if (!name.IsString(cage_base)) continue;
839      key_name = handle(String::cast(name), isolate_);
840      details = descriptors.GetDetails(i);
841    }
842    if (details.IsDontEnum()) continue;
843    Handle<Object> property;
844    if (details.location() == PropertyLocation::kField &&
845        *map == object->map(cage_base)) {
846      DCHECK_EQ(PropertyKind::kData, details.kind());
847      FieldIndex field_index = FieldIndex::ForDescriptor(*map, i);
848      property = JSObject::FastPropertyAt(
849          isolate_, object, details.representation(), field_index);
850    } else {
851      ASSIGN_RETURN_ON_EXCEPTION_VALUE(
852          isolate_, property,
853          Object::GetPropertyOrElement(isolate_, object, key_name), EXCEPTION);
854    }
855    Result result = SerializeProperty(property, comma, key_name);
856    if (!comma && result == SUCCESS) comma = true;
857    if (result == EXCEPTION) return result;
858  }
859  Unindent();
860  if (comma) NewLine();
861  builder_.AppendCharacter('}');
862  StackPop();
863  return SUCCESS;
864}
865
866JsonStringifier::Result JsonStringifier::SerializeJSReceiverSlow(
867    Handle<JSReceiver> object) {
868  Handle<FixedArray> contents = property_list_;
869  if (contents.is_null()) {
870    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
871        isolate_, contents,
872        KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,
873                                ENUMERABLE_STRINGS,
874                                GetKeysConversion::kConvertToString),
875        EXCEPTION);
876  }
877  builder_.AppendCharacter('{');
878  Indent();
879  bool comma = false;
880  for (int i = 0; i < contents->length(); i++) {
881    Handle<String> key(String::cast(contents->get(i)), isolate_);
882    Handle<Object> property;
883    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
884        isolate_, property, Object::GetPropertyOrElement(isolate_, object, key),
885        EXCEPTION);
886    Result result = SerializeProperty(property, comma, key);
887    if (!comma && result == SUCCESS) comma = true;
888    if (result == EXCEPTION) return result;
889  }
890  Unindent();
891  if (comma) NewLine();
892  builder_.AppendCharacter('}');
893  return SUCCESS;
894}
895
896JsonStringifier::Result JsonStringifier::SerializeJSProxy(
897    Handle<JSProxy> object, Handle<Object> key) {
898  HandleScope scope(isolate_);
899  Result stack_push = StackPush(object, key);
900  if (stack_push != SUCCESS) return stack_push;
901  Maybe<bool> is_array = Object::IsArray(object);
902  if (is_array.IsNothing()) return EXCEPTION;
903  if (is_array.FromJust()) {
904    Handle<Object> length_object;
905    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
906        isolate_, length_object,
907        Object::GetLengthFromArrayLike(isolate_,
908                                       Handle<JSReceiver>::cast(object)),
909        EXCEPTION);
910    uint32_t length;
911    if (!length_object->ToUint32(&length)) {
912      // Technically, we need to be able to handle lengths outside the
913      // uint32_t range. However, we would run into string size overflow
914      // if we tried to stringify such an array.
915      isolate_->Throw(*isolate_->factory()->NewInvalidStringLengthError());
916      return EXCEPTION;
917    }
918    builder_.AppendCharacter('[');
919    Indent();
920    Result result = SerializeArrayLikeSlow(object, 0, length);
921    if (result != SUCCESS) return result;
922    Unindent();
923    if (length > 0) NewLine();
924    builder_.AppendCharacter(']');
925  } else {
926    Result result = SerializeJSReceiverSlow(object);
927    if (result != SUCCESS) return result;
928  }
929  StackPop();
930  return SUCCESS;
931}
932
933template <typename SrcChar, typename DestChar>
934void JsonStringifier::SerializeStringUnchecked_(
935    base::Vector<const SrcChar> src,
936    IncrementalStringBuilder::NoExtend<DestChar>* dest) {
937  // Assert that base::uc16 character is not truncated down to 8 bit.
938  // The <base::uc16, char> version of this method must not be called.
939  DCHECK(sizeof(DestChar) >= sizeof(SrcChar));
940  for (int i = 0; i < src.length(); i++) {
941    SrcChar c = src[i];
942    if (DoNotEscape(c)) {
943      dest->Append(c);
944    } else if (sizeof(SrcChar) != 1 &&
945               base::IsInRange(c, static_cast<SrcChar>(0xD800),
946                               static_cast<SrcChar>(0xDFFF))) {
947      // The current character is a surrogate.
948      if (c <= 0xDBFF) {
949        // The current character is a leading surrogate.
950        if (i + 1 < src.length()) {
951          // There is a next character.
952          SrcChar next = src[i + 1];
953          if (base::IsInRange(next, static_cast<SrcChar>(0xDC00),
954                              static_cast<SrcChar>(0xDFFF))) {
955            // The next character is a trailing surrogate, meaning this is a
956            // surrogate pair.
957            dest->Append(c);
958            dest->Append(next);
959            i++;
960          } else {
961            // The next character is not a trailing surrogate. Thus, the
962            // current character is a lone leading surrogate.
963            dest->AppendCString("\\u");
964            char* const hex = DoubleToRadixCString(c, 16);
965            dest->AppendCString(hex);
966            DeleteArray(hex);
967          }
968        } else {
969          // There is no next character. Thus, the current character is a lone
970          // leading surrogate.
971          dest->AppendCString("\\u");
972          char* const hex = DoubleToRadixCString(c, 16);
973          dest->AppendCString(hex);
974          DeleteArray(hex);
975        }
976      } else {
977        // The current character is a lone trailing surrogate. (If it had been
978        // preceded by a leading surrogate, we would've ended up in the other
979        // branch earlier on, and the current character would've been handled
980        // as part of the surrogate pair already.)
981        dest->AppendCString("\\u");
982        char* const hex = DoubleToRadixCString(c, 16);
983        dest->AppendCString(hex);
984        DeleteArray(hex);
985      }
986    } else {
987      dest->AppendCString(&JsonEscapeTable[c * kJsonEscapeTableEntrySize]);
988    }
989  }
990}
991
992template <typename SrcChar, typename DestChar>
993void JsonStringifier::SerializeString_(Handle<String> string) {
994  int length = string->length();
995  builder_.Append<uint8_t, DestChar>('"');
996  // We might be able to fit the whole escaped string in the current string
997  // part, or we might need to allocate.
998  if (int worst_case_length = builder_.EscapedLengthIfCurrentPartFits(length)) {
999    DisallowGarbageCollection no_gc;
1000    base::Vector<const SrcChar> vector = string->GetCharVector<SrcChar>(no_gc);
1001    IncrementalStringBuilder::NoExtendBuilder<DestChar> no_extend(
1002        &builder_, worst_case_length, no_gc);
1003    SerializeStringUnchecked_(vector, &no_extend);
1004  } else {
1005    FlatStringReader reader(isolate_, string);
1006    for (int i = 0; i < reader.length(); i++) {
1007      SrcChar c = reader.Get<SrcChar>(i);
1008      if (DoNotEscape(c)) {
1009        builder_.Append<SrcChar, DestChar>(c);
1010      } else if (sizeof(SrcChar) != 1 &&
1011                 base::IsInRange(c, static_cast<SrcChar>(0xD800),
1012                                 static_cast<SrcChar>(0xDFFF))) {
1013        // The current character is a surrogate.
1014        if (c <= 0xDBFF) {
1015          // The current character is a leading surrogate.
1016          if (i + 1 < reader.length()) {
1017            // There is a next character.
1018            SrcChar next = reader.Get<SrcChar>(i + 1);
1019            if (base::IsInRange(next, static_cast<SrcChar>(0xDC00),
1020                                static_cast<SrcChar>(0xDFFF))) {
1021              // The next character is a trailing surrogate, meaning this is a
1022              // surrogate pair.
1023              builder_.Append<SrcChar, DestChar>(c);
1024              builder_.Append<SrcChar, DestChar>(next);
1025              i++;
1026            } else {
1027              // The next character is not a trailing surrogate. Thus, the
1028              // current character is a lone leading surrogate.
1029              builder_.AppendCStringLiteral("\\u");
1030              char* const hex = DoubleToRadixCString(c, 16);
1031              builder_.AppendCString(hex);
1032              DeleteArray(hex);
1033            }
1034          } else {
1035            // There is no next character. Thus, the current character is a
1036            // lone leading surrogate.
1037            builder_.AppendCStringLiteral("\\u");
1038            char* const hex = DoubleToRadixCString(c, 16);
1039            builder_.AppendCString(hex);
1040            DeleteArray(hex);
1041          }
1042        } else {
1043          // The current character is a lone trailing surrogate. (If it had
1044          // been preceded by a leading surrogate, we would've ended up in the
1045          // other branch earlier on, and the current character would've been
1046          // handled as part of the surrogate pair already.)
1047          builder_.AppendCStringLiteral("\\u");
1048          char* const hex = DoubleToRadixCString(c, 16);
1049          builder_.AppendCString(hex);
1050          DeleteArray(hex);
1051        }
1052      } else {
1053        builder_.AppendCString(&JsonEscapeTable[c * kJsonEscapeTableEntrySize]);
1054      }
1055    }
1056  }
1057  builder_.Append<uint8_t, DestChar>('"');
1058}
1059
1060template <>
1061bool JsonStringifier::DoNotEscape(uint8_t c) {
1062  // https://tc39.github.io/ecma262/#table-json-single-character-escapes
1063  return base::IsInRange(c, static_cast<uint8_t>(0x23),
1064                         static_cast<uint8_t>(0x7E)) &&
1065         c != 0x5C;
1066}
1067
1068template <>
1069bool JsonStringifier::DoNotEscape(uint16_t c) {
1070  // https://tc39.github.io/ecma262/#table-json-single-character-escapes
1071  return c >= 0x23 && c != 0x5C && c != 0x7F && (c < 0xD800 || c > 0xDFFF);
1072}
1073
1074void JsonStringifier::NewLine() {
1075  if (gap_ == nullptr) return;
1076  NewLineOutline();
1077}
1078
1079void JsonStringifier::NewLineOutline() {
1080  builder_.AppendCharacter('\n');
1081  for (int i = 0; i < indent_; i++) builder_.AppendCString(gap_);
1082}
1083
1084void JsonStringifier::Separator(bool first) {
1085  if (!first) builder_.AppendCharacter(',');
1086  NewLine();
1087}
1088
1089void JsonStringifier::SerializeDeferredKey(bool deferred_comma,
1090                                           Handle<Object> deferred_key) {
1091  Separator(!deferred_comma);
1092  SerializeString(Handle<String>::cast(deferred_key));
1093  builder_.AppendCharacter(':');
1094  if (gap_ != nullptr) builder_.AppendCharacter(' ');
1095}
1096
1097void JsonStringifier::SerializeString(Handle<String> object) {
1098  object = String::Flatten(isolate_, object);
1099  if (builder_.CurrentEncoding() == String::ONE_BYTE_ENCODING) {
1100    if (String::IsOneByteRepresentationUnderneath(*object)) {
1101      SerializeString_<uint8_t, uint8_t>(object);
1102    } else {
1103      builder_.ChangeEncoding();
1104      SerializeString(object);
1105    }
1106  } else {
1107    if (String::IsOneByteRepresentationUnderneath(*object)) {
1108      SerializeString_<uint8_t, base::uc16>(object);
1109    } else {
1110      SerializeString_<base::uc16, base::uc16>(object);
1111    }
1112  }
1113}
1114
1115}  // namespace internal
1116}  // namespace v8
1117