xref: /third_party/node/deps/v8/src/json/json-parser.cc (revision 1cb0ef41) 
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-parser.h"
6
7#include "src/base/strings.h"
8#include "src/common/globals.h"
9#include "src/common/message-template.h"
10#include "src/debug/debug.h"
11#include "src/execution/frames-inl.h"
12#include "src/numbers/conversions.h"
13#include "src/numbers/hash-seed-inl.h"
14#include "src/objects/field-type.h"
15#include "src/objects/hash-table-inl.h"
16#include "src/objects/map-updater.h"
17#include "src/objects/objects-inl.h"
18#include "src/objects/property-descriptor.h"
19#include "src/strings/char-predicates-inl.h"
20#include "src/strings/string-hasher.h"
21
22namespace v8 {
23namespace internal {
24
25namespace {
26
27constexpr JsonToken GetOneCharJsonToken(uint8_t c) {
28  // clang-format off
29  return
30     c == '"' ? JsonToken::STRING :
31     IsDecimalDigit(c) ?  JsonToken::NUMBER :
32     c == '-' ? JsonToken::NUMBER :
33     c == '[' ? JsonToken::LBRACK :
34     c == '{' ? JsonToken::LBRACE :
35     c == ']' ? JsonToken::RBRACK :
36     c == '}' ? JsonToken::RBRACE :
37     c == 't' ? JsonToken::TRUE_LITERAL :
38     c == 'f' ? JsonToken::FALSE_LITERAL :
39     c == 'n' ? JsonToken::NULL_LITERAL :
40     c == ' ' ? JsonToken::WHITESPACE :
41     c == '\t' ? JsonToken::WHITESPACE :
42     c == '\r' ? JsonToken::WHITESPACE :
43     c == '\n' ? JsonToken::WHITESPACE :
44     c == ':' ? JsonToken::COLON :
45     c == ',' ? JsonToken::COMMA :
46     JsonToken::ILLEGAL;
47  // clang-format on
48}
49
50// Table of one-character tokens, by character (0x00..0xFF only).
51static const constexpr JsonToken one_char_json_tokens[256] = {
52#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(N),
53    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
54#undef CALL_GET_SCAN_FLAGS
55#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(128 + N),
56        INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
57#undef CALL_GET_SCAN_FLAGS
58};
59
60enum class EscapeKind : uint8_t {
61  kIllegal,
62  kSelf,
63  kBackspace,
64  kTab,
65  kNewLine,
66  kFormFeed,
67  kCarriageReturn,
68  kUnicode
69};
70
71using EscapeKindField = base::BitField8<EscapeKind, 0, 3>;
72using MayTerminateStringField = EscapeKindField::Next<bool, 1>;
73using NumberPartField = MayTerminateStringField::Next<bool, 1>;
74
75constexpr bool MayTerminateJsonString(uint8_t flags) {
76  return MayTerminateStringField::decode(flags);
77}
78
79constexpr EscapeKind GetEscapeKind(uint8_t flags) {
80  return EscapeKindField::decode(flags);
81}
82
83constexpr bool IsNumberPart(uint8_t flags) {
84  return NumberPartField::decode(flags);
85}
86
87constexpr uint8_t GetJsonScanFlags(uint8_t c) {
88  // clang-format off
89  return (c == 'b' ? EscapeKindField::encode(EscapeKind::kBackspace)
90          : c == 't' ? EscapeKindField::encode(EscapeKind::kTab)
91          : c == 'n' ? EscapeKindField::encode(EscapeKind::kNewLine)
92          : c == 'f' ? EscapeKindField::encode(EscapeKind::kFormFeed)
93          : c == 'r' ? EscapeKindField::encode(EscapeKind::kCarriageReturn)
94          : c == 'u' ? EscapeKindField::encode(EscapeKind::kUnicode)
95          : c == '"' ? EscapeKindField::encode(EscapeKind::kSelf)
96          : c == '\\' ? EscapeKindField::encode(EscapeKind::kSelf)
97          : c == '/' ? EscapeKindField::encode(EscapeKind::kSelf)
98          : EscapeKindField::encode(EscapeKind::kIllegal)) |
99         (c < 0x20 ? MayTerminateStringField::encode(true)
100          : c == '"' ? MayTerminateStringField::encode(true)
101          : c == '\\' ? MayTerminateStringField::encode(true)
102          : MayTerminateStringField::encode(false)) |
103         NumberPartField::encode(c == '.' ||
104                                 c == 'e' ||
105                                 c == 'E' ||
106                                 IsDecimalDigit(c) ||
107                                 c == '-' ||
108                                 c == '+');
109  // clang-format on
110}
111
112// Table of one-character scan flags, by character (0x00..0xFF only).
113static const constexpr uint8_t character_json_scan_flags[256] = {
114#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(N),
115    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
116#undef CALL_GET_SCAN_FLAGS
117#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(128 + N),
118        INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
119#undef CALL_GET_SCAN_FLAGS
120};
121
122}  // namespace
123
124MaybeHandle<Object> JsonParseInternalizer::Internalize(Isolate* isolate,
125                                                       Handle<Object> object,
126                                                       Handle<Object> reviver) {
127  DCHECK(reviver->IsCallable());
128  JsonParseInternalizer internalizer(isolate,
129                                     Handle<JSReceiver>::cast(reviver));
130  Handle<JSObject> holder =
131      isolate->factory()->NewJSObject(isolate->object_function());
132  Handle<String> name = isolate->factory()->empty_string();
133  JSObject::AddProperty(isolate, holder, name, object, NONE);
134  return internalizer.InternalizeJsonProperty(holder, name);
135}
136
137MaybeHandle<Object> JsonParseInternalizer::InternalizeJsonProperty(
138    Handle<JSReceiver> holder, Handle<String> name) {
139  HandleScope outer_scope(isolate_);
140  Handle<Object> value;
141  ASSIGN_RETURN_ON_EXCEPTION(
142      isolate_, value, Object::GetPropertyOrElement(isolate_, holder, name),
143      Object);
144  if (value->IsJSReceiver()) {
145    Handle<JSReceiver> object = Handle<JSReceiver>::cast(value);
146    Maybe<bool> is_array = Object::IsArray(object);
147    if (is_array.IsNothing()) return MaybeHandle<Object>();
148    if (is_array.FromJust()) {
149      Handle<Object> length_object;
150      ASSIGN_RETURN_ON_EXCEPTION(
151          isolate_, length_object,
152          Object::GetLengthFromArrayLike(isolate_, object), Object);
153      double length = length_object->Number();
154      for (double i = 0; i < length; i++) {
155        HandleScope inner_scope(isolate_);
156        Handle<Object> index = isolate_->factory()->NewNumber(i);
157        Handle<String> index_name = isolate_->factory()->NumberToString(index);
158        if (!RecurseAndApply(object, index_name)) return MaybeHandle<Object>();
159      }
160    } else {
161      Handle<FixedArray> contents;
162      ASSIGN_RETURN_ON_EXCEPTION(
163          isolate_, contents,
164          KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,
165                                  ENUMERABLE_STRINGS,
166                                  GetKeysConversion::kConvertToString),
167          Object);
168      for (int i = 0; i < contents->length(); i++) {
169        HandleScope inner_scope(isolate_);
170        Handle<String> key_name(String::cast(contents->get(i)), isolate_);
171        if (!RecurseAndApply(object, key_name)) return MaybeHandle<Object>();
172      }
173    }
174  }
175  Handle<Object> argv[] = {name, value};
176  Handle<Object> result;
177  ASSIGN_RETURN_ON_EXCEPTION(
178      isolate_, result, Execution::Call(isolate_, reviver_, holder, 2, argv),
179      Object);
180  return outer_scope.CloseAndEscape(result);
181}
182
183bool JsonParseInternalizer::RecurseAndApply(Handle<JSReceiver> holder,
184                                            Handle<String> name) {
185  STACK_CHECK(isolate_, false);
186
187  Handle<Object> result;
188  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
189      isolate_, result, InternalizeJsonProperty(holder, name), false);
190  Maybe<bool> change_result = Nothing<bool>();
191  if (result->IsUndefined(isolate_)) {
192    change_result = JSReceiver::DeletePropertyOrElement(holder, name,
193                                                        LanguageMode::kSloppy);
194  } else {
195    PropertyDescriptor desc;
196    desc.set_value(result);
197    desc.set_configurable(true);
198    desc.set_enumerable(true);
199    desc.set_writable(true);
200    change_result = JSReceiver::DefineOwnProperty(isolate_, holder, name, &desc,
201                                                  Just(kDontThrow));
202  }
203  MAYBE_RETURN(change_result, false);
204  return true;
205}
206
207template <typename Char>
208JsonParser<Char>::JsonParser(Isolate* isolate, Handle<String> source)
209    : isolate_(isolate),
210      hash_seed_(HashSeed(isolate)),
211      object_constructor_(isolate_->object_function()),
212      original_source_(source) {
213  size_t start = 0;
214  size_t length = source->length();
215  PtrComprCageBase cage_base(isolate);
216  if (source->IsSlicedString(cage_base)) {
217    SlicedString string = SlicedString::cast(*source);
218    start = string.offset();
219    String parent = string.parent(cage_base);
220    if (parent.IsThinString(cage_base))
221      parent = ThinString::cast(parent).actual(cage_base);
222    source_ = handle(parent, isolate);
223  } else {
224    source_ = String::Flatten(isolate, source);
225  }
226
227  if (StringShape(*source_, cage_base).IsExternal()) {
228    chars_ = static_cast<const Char*>(
229        SeqExternalString::cast(*source_).GetChars(cage_base));
230    chars_may_relocate_ = false;
231  } else {
232    DisallowGarbageCollection no_gc;
233    isolate->main_thread_local_heap()->AddGCEpilogueCallback(
234        UpdatePointersCallback, this);
235    chars_ = SeqString::cast(*source_).GetChars(no_gc);
236    chars_may_relocate_ = true;
237  }
238  cursor_ = chars_ + start;
239  end_ = cursor_ + length;
240}
241
242template <typename Char>
243void JsonParser<Char>::ReportUnexpectedToken(JsonToken token) {
244  // Some exception (for example stack overflow) is already pending.
245  if (isolate_->has_pending_exception()) return;
246
247  // Parse failed. Current character is the unexpected token.
248  Factory* factory = this->factory();
249  MessageTemplate message;
250  int offset = original_source_->IsSlicedString()
251                   ? SlicedString::cast(*original_source_).offset()
252                   : 0;
253  int pos = position() - offset;
254  Handle<Object> arg1 = Handle<Smi>(Smi::FromInt(pos), isolate());
255  Handle<Object> arg2;
256
257  switch (token) {
258    case JsonToken::EOS:
259      message = MessageTemplate::kJsonParseUnexpectedEOS;
260      break;
261    case JsonToken::NUMBER:
262      message = MessageTemplate::kJsonParseUnexpectedTokenNumber;
263      break;
264    case JsonToken::STRING:
265      message = MessageTemplate::kJsonParseUnexpectedTokenString;
266      break;
267    default:
268      message = MessageTemplate::kJsonParseUnexpectedToken;
269      arg2 = arg1;
270      arg1 = factory->LookupSingleCharacterStringFromCode(*cursor_);
271      break;
272  }
273
274  Handle<Script> script(factory->NewScript(original_source_));
275  if (isolate()->NeedsSourcePositionsForProfiling()) {
276    Script::InitLineEnds(isolate(), script);
277  }
278
279  StackTraceFrameIterator it(isolate_);
280  if (!it.done() && it.is_javascript()) {
281    FrameSummary summary = it.GetTopValidFrame();
282    script->set_eval_from_shared(summary.AsJavaScript().function()->shared());
283    if (summary.script()->IsScript()) {
284      script->set_origin_options(
285          Script::cast(*summary.script()).origin_options());
286    }
287  }
288
289  // We should sent compile error event because we compile JSON object in
290  // separated source file.
291  isolate()->debug()->OnCompileError(script);
292  MessageLocation location(script, pos, pos + 1);
293  isolate()->ThrowAt(factory->NewSyntaxError(message, arg1, arg2), &location);
294
295  // Move the cursor to the end so we won't be able to proceed parsing.
296  cursor_ = end_;
297}
298
299template <typename Char>
300void JsonParser<Char>::ReportUnexpectedCharacter(base::uc32 c) {
301  JsonToken token = JsonToken::ILLEGAL;
302  if (c == kEndOfString) {
303    token = JsonToken::EOS;
304  } else if (c <= unibrow::Latin1::kMaxChar) {
305    token = one_char_json_tokens[c];
306  }
307  return ReportUnexpectedToken(token);
308}
309
310template <typename Char>
311JsonParser<Char>::~JsonParser() {
312  if (StringShape(*source_).IsExternal()) {
313    // Check that the string shape hasn't changed. Otherwise our GC hooks are
314    // broken.
315    SeqExternalString::cast(*source_);
316  } else {
317    // Check that the string shape hasn't changed. Otherwise our GC hooks are
318    // broken.
319    SeqString::cast(*source_);
320    isolate()->main_thread_local_heap()->RemoveGCEpilogueCallback(
321        UpdatePointersCallback, this);
322  }
323}
324
325template <typename Char>
326MaybeHandle<Object> JsonParser<Char>::ParseJson() {
327  MaybeHandle<Object> result = ParseJsonValue();
328  if (!Check(JsonToken::EOS)) ReportUnexpectedToken(peek());
329  if (isolate_->has_pending_exception()) return MaybeHandle<Object>();
330  return result;
331}
332
333MaybeHandle<Object> InternalizeJsonProperty(Handle<JSObject> holder,
334                                            Handle<String> key);
335
336template <typename Char>
337void JsonParser<Char>::SkipWhitespace() {
338  next_ = JsonToken::EOS;
339
340  cursor_ = std::find_if(cursor_, end_, [this](Char c) {
341    JsonToken current = V8_LIKELY(c <= unibrow::Latin1::kMaxChar)
342                            ? one_char_json_tokens[c]
343                            : JsonToken::ILLEGAL;
344    bool result = current != JsonToken::WHITESPACE;
345    if (result) next_ = current;
346    return result;
347  });
348}
349
350template <typename Char>
351base::uc32 JsonParser<Char>::ScanUnicodeCharacter() {
352  base::uc32 value = 0;
353  for (int i = 0; i < 4; i++) {
354    int digit = base::HexValue(NextCharacter());
355    if (V8_UNLIKELY(digit < 0)) return kInvalidUnicodeCharacter;
356    value = value * 16 + digit;
357  }
358  return value;
359}
360
361// Parse any JSON value.
362template <typename Char>
363JsonString JsonParser<Char>::ScanJsonPropertyKey(JsonContinuation* cont) {
364  {
365    DisallowGarbageCollection no_gc;
366    const Char* start = cursor_;
367    base::uc32 first = CurrentCharacter();
368    if (first == '\\' && NextCharacter() == 'u') first = ScanUnicodeCharacter();
369    if (IsDecimalDigit(first)) {
370      if (first == '0') {
371        if (NextCharacter() == '"') {
372          advance();
373          // Record element information.
374          cont->elements++;
375          DCHECK_LE(0, cont->max_index);
376          return JsonString(0);
377        }
378      } else {
379        uint32_t index = first - '0';
380        while (true) {
381          cursor_ = std::find_if(cursor_ + 1, end_, [&index](Char c) {
382            return !TryAddArrayIndexChar(&index, c);
383          });
384
385          if (CurrentCharacter() == '"') {
386            advance();
387            // Record element information.
388            cont->elements++;
389            cont->max_index = std::max(cont->max_index, index);
390            return JsonString(index);
391          }
392
393          if (CurrentCharacter() == '\\' && NextCharacter() == 'u') {
394            if (TryAddArrayIndexChar(&index, ScanUnicodeCharacter())) continue;
395          }
396
397          break;
398        }
399      }
400    }
401    // Reset cursor_ to start if the key is not an index.
402    cursor_ = start;
403  }
404  return ScanJsonString(true);
405}
406
407namespace {
408Handle<Map> ParentOfDescriptorOwner(Isolate* isolate, Handle<Map> maybe_root,
409                                    Handle<Map> source, int descriptor) {
410  if (descriptor == 0) {
411    DCHECK_EQ(0, maybe_root->NumberOfOwnDescriptors());
412    return maybe_root;
413  }
414  return handle(source->FindFieldOwner(isolate, InternalIndex(descriptor - 1)),
415                isolate);
416}
417}  // namespace
418
419template <typename Char>
420Handle<Object> JsonParser<Char>::BuildJsonObject(
421    const JsonContinuation& cont,
422    const SmallVector<JsonProperty>& property_stack, Handle<Map> feedback) {
423  size_t start = cont.index;
424  int length = static_cast<int>(property_stack.size() - start);
425  int named_length = length - cont.elements;
426
427  Handle<Map> initial_map = factory()->ObjectLiteralMapFromCache(
428      isolate_->native_context(), named_length);
429
430  Handle<Map> map = initial_map;
431
432  Handle<FixedArrayBase> elements = factory()->empty_fixed_array();
433
434  // First store the elements.
435  if (cont.elements > 0) {
436    // Store as dictionary elements if that would use less memory.
437    if (ShouldConvertToSlowElements(cont.elements, cont.max_index + 1)) {
438      Handle<NumberDictionary> elms =
439          NumberDictionary::New(isolate_, cont.elements);
440      for (int i = 0; i < length; i++) {
441        const JsonProperty& property = property_stack[start + i];
442        if (!property.string.is_index()) continue;
443        uint32_t index = property.string.index();
444        Handle<Object> value = property.value;
445        elms = NumberDictionary::Set(isolate_, elms, index, value);
446      }
447      map = Map::AsElementsKind(isolate_, map, DICTIONARY_ELEMENTS);
448      elements = elms;
449    } else {
450      Handle<FixedArray> elms =
451          factory()->NewFixedArrayWithHoles(cont.max_index + 1);
452      DisallowGarbageCollection no_gc;
453      WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
454      DCHECK_EQ(HOLEY_ELEMENTS, map->elements_kind());
455
456      for (int i = 0; i < length; i++) {
457        const JsonProperty& property = property_stack[start + i];
458        if (!property.string.is_index()) continue;
459        uint32_t index = property.string.index();
460        Handle<Object> value = property.value;
461        elms->set(static_cast<int>(index), *value, mode);
462      }
463      elements = elms;
464    }
465  }
466
467  int feedback_descriptors =
468      (feedback.is_null() ||
469       feedback->elements_kind() != map->elements_kind() ||
470       feedback->instance_size() != map->instance_size())
471          ? 0
472          : feedback->NumberOfOwnDescriptors();
473
474  int i;
475  int descriptor = 0;
476  int new_mutable_double = 0;
477  for (i = 0; i < length; i++) {
478    const JsonProperty& property = property_stack[start + i];
479    if (property.string.is_index()) continue;
480    Handle<String> expected;
481    Handle<Map> target;
482    InternalIndex descriptor_index(descriptor);
483    if (descriptor < feedback_descriptors) {
484      expected =
485          handle(String::cast(feedback->instance_descriptors(isolate_).GetKey(
486                     descriptor_index)),
487                 isolate_);
488    } else {
489      TransitionsAccessor transitions(isolate(), *map);
490      expected = transitions.ExpectedTransitionKey();
491      if (!expected.is_null()) {
492        // Directly read out the target while reading out the key, otherwise it
493        // might die while building the string below.
494        target =
495            TransitionsAccessor(isolate(), *map).ExpectedTransitionTarget();
496      }
497    }
498
499    Handle<String> key = MakeString(property.string, expected);
500    if (key.is_identical_to(expected)) {
501      if (descriptor < feedback_descriptors) target = feedback;
502    } else {
503      if (descriptor < feedback_descriptors) {
504        map = ParentOfDescriptorOwner(isolate_, map, feedback, descriptor);
505        feedback_descriptors = 0;
506      }
507      if (!TransitionsAccessor(isolate(), *map)
508               .FindTransitionToField(key)
509               .ToHandle(&target)) {
510        break;
511      }
512    }
513
514    Handle<Object> value = property.value;
515
516    PropertyDetails details =
517        target->instance_descriptors(isolate_).GetDetails(descriptor_index);
518    Representation expected_representation = details.representation();
519
520    if (!value->FitsRepresentation(expected_representation)) {
521      Representation representation = value->OptimalRepresentation(isolate());
522      representation = representation.generalize(expected_representation);
523      if (!expected_representation.CanBeInPlaceChangedTo(representation)) {
524        map = ParentOfDescriptorOwner(isolate_, map, target, descriptor);
525        break;
526      }
527      Handle<FieldType> value_type =
528          value->OptimalType(isolate(), representation);
529      MapUpdater::GeneralizeField(isolate(), target, descriptor_index,
530                                  details.constness(), representation,
531                                  value_type);
532    } else if (expected_representation.IsHeapObject() &&
533               !target->instance_descriptors(isolate())
534                    .GetFieldType(descriptor_index)
535                    .NowContains(value)) {
536      Handle<FieldType> value_type =
537          value->OptimalType(isolate(), expected_representation);
538      MapUpdater::GeneralizeField(isolate(), target, descriptor_index,
539                                  details.constness(), expected_representation,
540                                  value_type);
541    } else if (expected_representation.IsDouble() && value->IsSmi()) {
542      new_mutable_double++;
543    }
544
545    DCHECK(target->instance_descriptors(isolate())
546               .GetFieldType(descriptor_index)
547               .NowContains(value));
548    map = target;
549    descriptor++;
550  }
551
552  // Fast path: Write all transitioned named properties.
553  if (i == length && descriptor < feedback_descriptors) {
554    map = ParentOfDescriptorOwner(isolate_, map, map, descriptor);
555  }
556
557  // Preallocate all mutable heap numbers so we don't need to allocate while
558  // setting up the object. Otherwise verification of that object may fail.
559  Handle<ByteArray> mutable_double_buffer;
560  // Allocate enough space so we can double-align the payload.
561  const int kMutableDoubleSize = sizeof(double) * 2;
562  STATIC_ASSERT(HeapNumber::kSize <= kMutableDoubleSize);
563  if (new_mutable_double > 0) {
564    mutable_double_buffer =
565        factory()->NewByteArray(kMutableDoubleSize * new_mutable_double);
566  }
567
568  Handle<JSObject> object = initial_map->is_dictionary_map()
569                                ? factory()->NewSlowJSObjectFromMap(map)
570                                : factory()->NewJSObjectFromMap(map);
571  object->set_elements(*elements);
572
573  {
574    descriptor = 0;
575    DisallowGarbageCollection no_gc;
576    WriteBarrierMode mode = object->GetWriteBarrierMode(no_gc);
577    Address mutable_double_address =
578        mutable_double_buffer.is_null()
579            ? 0
580            : reinterpret_cast<Address>(
581                  mutable_double_buffer->GetDataStartAddress());
582    Address filler_address = mutable_double_address;
583    if (kTaggedSize != kDoubleSize) {
584      if (IsAligned(mutable_double_address, kDoubleAlignment)) {
585        mutable_double_address += kTaggedSize;
586      } else {
587        filler_address += HeapNumber::kSize;
588      }
589    }
590    for (int j = 0; j < i; j++) {
591      const JsonProperty& property = property_stack[start + j];
592      if (property.string.is_index()) continue;
593      InternalIndex descriptor_index(descriptor);
594      PropertyDetails details =
595          map->instance_descriptors(isolate()).GetDetails(descriptor_index);
596      Object value = *property.value;
597      FieldIndex index = FieldIndex::ForDescriptor(*map, descriptor_index);
598      descriptor++;
599
600      if (details.representation().IsDouble()) {
601        if (value.IsSmi()) {
602          if (kTaggedSize != kDoubleSize) {
603            // Write alignment filler.
604            HeapObject filler = HeapObject::FromAddress(filler_address);
605            filler.set_map_after_allocation(
606                *factory()->one_pointer_filler_map());
607            filler_address += kMutableDoubleSize;
608          }
609
610          uint64_t bits =
611              bit_cast<uint64_t>(static_cast<double>(Smi::ToInt(value)));
612          // Allocate simple heapnumber with immortal map, with non-pointer
613          // payload, so we can skip notifying object layout change.
614
615          HeapObject hn = HeapObject::FromAddress(mutable_double_address);
616          hn.set_map_after_allocation(*factory()->heap_number_map());
617          HeapNumber::cast(hn).set_value_as_bits(bits, kRelaxedStore);
618          value = hn;
619          mutable_double_address += kMutableDoubleSize;
620        } else {
621          DCHECK(value.IsHeapNumber());
622          HeapObject::cast(value).set_map(*factory()->heap_number_map(),
623                                          kReleaseStore);
624        }
625      }
626      object->RawFastInobjectPropertyAtPut(index, value, mode);
627    }
628    // Make all mutable HeapNumbers alive.
629    if (!mutable_double_buffer.is_null()) {
630#ifdef DEBUG
631      Address end =
632          reinterpret_cast<Address>(mutable_double_buffer->GetDataEndAddress());
633      if (kTaggedSize != kDoubleSize) {
634        DCHECK_EQ(std::min(filler_address, mutable_double_address), end);
635        DCHECK_GE(filler_address, end);
636        DCHECK_GE(mutable_double_address, end);
637      } else {
638        DCHECK_EQ(mutable_double_address, end);
639      }
640#endif
641      // Before setting the length of mutable_double_buffer back to zero, we
642      // must ensure that the sweeper is not running or has already swept the
643      // object's page. Otherwise the GC can add the contents of
644      // mutable_double_buffer to the free list.
645      isolate()->heap()->EnsureSweepingCompleted(*mutable_double_buffer);
646      mutable_double_buffer->set_length(0);
647    }
648  }
649
650  // Slow path: define remaining named properties.
651  for (; i < length; i++) {
652    HandleScope scope(isolate_);
653    const JsonProperty& property = property_stack[start + i];
654    if (property.string.is_index()) continue;
655    Handle<String> key = MakeString(property.string);
656#ifdef DEBUG
657    uint32_t index;
658    DCHECK(!key->AsArrayIndex(&index));
659#endif
660    Handle<Object> value = property.value;
661    LookupIterator it(isolate_, object, key, object, LookupIterator::OWN);
662    JSObject::DefineOwnPropertyIgnoreAttributes(&it, value, NONE).Check();
663  }
664
665  return object;
666}
667
668template <typename Char>
669Handle<Object> JsonParser<Char>::BuildJsonArray(
670    const JsonContinuation& cont,
671    const SmallVector<Handle<Object>>& element_stack) {
672  size_t start = cont.index;
673  int length = static_cast<int>(element_stack.size() - start);
674
675  ElementsKind kind = PACKED_SMI_ELEMENTS;
676  for (size_t i = start; i < element_stack.size(); i++) {
677    Object value = *element_stack[i];
678    if (value.IsHeapObject()) {
679      if (HeapObject::cast(value).IsHeapNumber()) {
680        kind = PACKED_DOUBLE_ELEMENTS;
681      } else {
682        kind = PACKED_ELEMENTS;
683        break;
684      }
685    }
686  }
687
688  Handle<JSArray> array = factory()->NewJSArray(kind, length, length);
689  if (kind == PACKED_DOUBLE_ELEMENTS) {
690    DisallowGarbageCollection no_gc;
691    FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
692    for (int i = 0; i < length; i++) {
693      elements.set(i, element_stack[start + i]->Number());
694    }
695  } else {
696    DisallowGarbageCollection no_gc;
697    FixedArray elements = FixedArray::cast(array->elements());
698    WriteBarrierMode mode = kind == PACKED_SMI_ELEMENTS
699                                ? SKIP_WRITE_BARRIER
700                                : elements.GetWriteBarrierMode(no_gc);
701    for (int i = 0; i < length; i++) {
702      elements.set(i, *element_stack[start + i], mode);
703    }
704  }
705  return array;
706}
707
708// Parse any JSON value.
709template <typename Char>
710MaybeHandle<Object> JsonParser<Char>::ParseJsonValue() {
711  std::vector<JsonContinuation> cont_stack;
712  SmallVector<JsonProperty> property_stack;
713  SmallVector<Handle<Object>> element_stack;
714
715  cont_stack.reserve(16);
716
717  JsonContinuation cont(isolate_, JsonContinuation::kReturn, 0);
718
719  Handle<Object> value;
720  while (true) {
721    // Produce a json value.
722    //
723    // Iterate until a value is produced. Starting but not immediately finishing
724    // objects and arrays will cause the loop to continue until a first member
725    // is completed.
726    while (true) {
727      SkipWhitespace();
728      // The switch is immediately followed by 'break' so we can use 'break' to
729      // break out of the loop, and 'continue' to continue the loop.
730      switch (peek()) {
731        case JsonToken::STRING:
732          Consume(JsonToken::STRING);
733          value = MakeString(ScanJsonString(false));
734          break;
735
736        case JsonToken::NUMBER:
737          value = ParseJsonNumber();
738          break;
739
740        case JsonToken::LBRACE: {
741          Consume(JsonToken::LBRACE);
742          if (Check(JsonToken::RBRACE)) {
743            // TODO(verwaest): Directly use the map instead.
744            value = factory()->NewJSObject(object_constructor_);
745            break;
746          }
747
748          // Start parsing an object with properties.
749          cont_stack.emplace_back(std::move(cont));
750          cont = JsonContinuation(isolate_, JsonContinuation::kObjectProperty,
751                                  property_stack.size());
752
753          // Parse the property key.
754          ExpectNext(JsonToken::STRING);
755          property_stack.emplace_back(ScanJsonPropertyKey(&cont));
756
757          ExpectNext(JsonToken::COLON);
758
759          // Continue to start producing the first property value.
760          continue;
761        }
762
763        case JsonToken::LBRACK:
764          Consume(JsonToken::LBRACK);
765          if (Check(JsonToken::RBRACK)) {
766            value = factory()->NewJSArray(0, PACKED_SMI_ELEMENTS);
767            break;
768          }
769
770          // Start parsing an array with elements.
771          cont_stack.emplace_back(std::move(cont));
772          cont = JsonContinuation(isolate_, JsonContinuation::kArrayElement,
773                                  element_stack.size());
774
775          // Continue to start producing the first array element.
776          continue;
777
778        case JsonToken::TRUE_LITERAL:
779          ScanLiteral("true");
780          value = factory()->true_value();
781          break;
782
783        case JsonToken::FALSE_LITERAL:
784          ScanLiteral("false");
785          value = factory()->false_value();
786          break;
787
788        case JsonToken::NULL_LITERAL:
789          ScanLiteral("null");
790          value = factory()->null_value();
791          break;
792
793        case JsonToken::COLON:
794        case JsonToken::COMMA:
795        case JsonToken::ILLEGAL:
796        case JsonToken::RBRACE:
797        case JsonToken::RBRACK:
798        case JsonToken::EOS:
799          ReportUnexpectedCharacter(CurrentCharacter());
800          // Pop the continuation stack to correctly tear down handle scopes.
801          while (!cont_stack.empty()) {
802            cont = std::move(cont_stack.back());
803            cont_stack.pop_back();
804          }
805          return MaybeHandle<Object>();
806
807        case JsonToken::WHITESPACE:
808          UNREACHABLE();
809      }
810
811      // Done producing a value, consume it.
812      break;
813    }
814
815    // Consume a produced json value.
816    //
817    // Iterate as long as values are produced (arrays or object literals are
818    // finished).
819    while (true) {
820      // The switch is immediately followed by 'break' so we can use 'break' to
821      // break out of the loop, and 'continue' to continue the loop.
822      switch (cont.type()) {
823        case JsonContinuation::kReturn:
824          return cont.scope.CloseAndEscape(value);
825
826        case JsonContinuation::kObjectProperty: {
827          // Store the previous property value into its property info.
828          property_stack.back().value = value;
829
830          if (V8_LIKELY(Check(JsonToken::COMMA))) {
831            // Parse the property key.
832            ExpectNext(JsonToken::STRING);
833
834            property_stack.emplace_back(ScanJsonPropertyKey(&cont));
835            ExpectNext(JsonToken::COLON);
836
837            // Break to start producing the subsequent property value.
838            break;
839          }
840
841          Handle<Map> feedback;
842          if (cont_stack.size() > 0 &&
843              cont_stack.back().type() == JsonContinuation::kArrayElement &&
844              cont_stack.back().index < element_stack.size() &&
845              element_stack.back()->IsJSObject()) {
846            Map maybe_feedback = JSObject::cast(*element_stack.back()).map();
847            // Don't consume feedback from objects with a map that's detached
848            // from the transition tree.
849            if (!maybe_feedback.IsDetached(isolate_)) {
850              feedback = handle(maybe_feedback, isolate_);
851              if (feedback->is_deprecated()) {
852                feedback = Map::Update(isolate_, feedback);
853              }
854            }
855          }
856          value = BuildJsonObject(cont, property_stack, feedback);
857          property_stack.resize_no_init(cont.index);
858          Expect(JsonToken::RBRACE);
859
860          // Return the object.
861          value = cont.scope.CloseAndEscape(value);
862          // Pop the continuation.
863          cont = std::move(cont_stack.back());
864          cont_stack.pop_back();
865          // Consume to produced object.
866          continue;
867        }
868
869        case JsonContinuation::kArrayElement: {
870          // Store the previous element on the stack.
871          element_stack.emplace_back(value);
872          // Break to start producing the subsequent element value.
873          if (V8_LIKELY(Check(JsonToken::COMMA))) break;
874
875          value = BuildJsonArray(cont, element_stack);
876          element_stack.resize_no_init(cont.index);
877          Expect(JsonToken::RBRACK);
878
879          // Return the array.
880          value = cont.scope.CloseAndEscape(value);
881          // Pop the continuation.
882          cont = std::move(cont_stack.back());
883          cont_stack.pop_back();
884          // Consume the produced array.
885          continue;
886        }
887      }
888
889      // Done consuming a value. Produce next value.
890      break;
891    }
892  }
893}
894
895template <typename Char>
896void JsonParser<Char>::AdvanceToNonDecimal() {
897  cursor_ =
898      std::find_if(cursor_, end_, [](Char c) { return !IsDecimalDigit(c); });
899}
900
901template <typename Char>
902Handle<Object> JsonParser<Char>::ParseJsonNumber() {
903  double number;
904  int sign = 1;
905
906  {
907    const Char* start = cursor_;
908    DisallowGarbageCollection no_gc;
909
910    base::uc32 c = *cursor_;
911    if (c == '-') {
912      sign = -1;
913      c = NextCharacter();
914    }
915
916    if (c == '0') {
917      // Prefix zero is only allowed if it's the only digit before
918      // a decimal point or exponent.
919      c = NextCharacter();
920      if (base::IsInRange(c, 0,
921                          static_cast<int32_t>(unibrow::Latin1::kMaxChar)) &&
922          IsNumberPart(character_json_scan_flags[c])) {
923        if (V8_UNLIKELY(IsDecimalDigit(c))) {
924          AllowGarbageCollection allow_before_exception;
925          ReportUnexpectedToken(JsonToken::NUMBER);
926          return handle(Smi::FromInt(0), isolate_);
927        }
928      } else if (sign > 0) {
929        return handle(Smi::FromInt(0), isolate_);
930      }
931    } else {
932      const Char* smi_start = cursor_;
933      AdvanceToNonDecimal();
934      if (V8_UNLIKELY(smi_start == cursor_)) {
935        AllowGarbageCollection allow_before_exception;
936        ReportUnexpectedCharacter(CurrentCharacter());
937        return handle(Smi::FromInt(0), isolate_);
938      }
939      c = CurrentCharacter();
940      STATIC_ASSERT(Smi::IsValid(-999999999));
941      STATIC_ASSERT(Smi::IsValid(999999999));
942      const int kMaxSmiLength = 9;
943      if ((cursor_ - smi_start) <= kMaxSmiLength &&
944          (!base::IsInRange(c, 0,
945                            static_cast<int32_t>(unibrow::Latin1::kMaxChar)) ||
946           !IsNumberPart(character_json_scan_flags[c]))) {
947        // Smi.
948        int32_t i = 0;
949        for (; smi_start != cursor_; smi_start++) {
950          DCHECK(IsDecimalDigit(*smi_start));
951          i = (i * 10) + ((*smi_start) - '0');
952        }
953        // TODO(verwaest): Cache?
954        return handle(Smi::FromInt(i * sign), isolate_);
955      }
956    }
957
958    if (CurrentCharacter() == '.') {
959      c = NextCharacter();
960      if (!IsDecimalDigit(c)) {
961        AllowGarbageCollection allow_before_exception;
962        ReportUnexpectedCharacter(c);
963        return handle(Smi::FromInt(0), isolate_);
964      }
965      AdvanceToNonDecimal();
966    }
967
968    if (AsciiAlphaToLower(CurrentCharacter()) == 'e') {
969      c = NextCharacter();
970      if (c == '-' || c == '+') c = NextCharacter();
971      if (!IsDecimalDigit(c)) {
972        AllowGarbageCollection allow_before_exception;
973        ReportUnexpectedCharacter(c);
974        return handle(Smi::FromInt(0), isolate_);
975      }
976      AdvanceToNonDecimal();
977    }
978
979    base::Vector<const Char> chars(start, cursor_ - start);
980    number =
981        StringToDouble(chars,
982                       NO_CONVERSION_FLAGS,  // Hex, octal or trailing junk.
983                       std::numeric_limits<double>::quiet_NaN());
984
985    DCHECK(!std::isnan(number));
986  }
987
988  return factory()->NewNumber(number);
989}
990
991namespace {
992
993template <typename Char>
994bool Matches(const base::Vector<const Char>& chars, Handle<String> string) {
995  DCHECK(!string.is_null());
996  return string->IsEqualTo(chars);
997}
998
999}  // namespace
1000
1001template <typename Char>
1002template <typename SinkSeqString>
1003Handle<String> JsonParser<Char>::DecodeString(
1004    const JsonString& string, Handle<SinkSeqString> intermediate,
1005    Handle<String> hint) {
1006  using SinkChar = typename SinkSeqString::Char;
1007  {
1008    DisallowGarbageCollection no_gc;
1009    SinkChar* dest = intermediate->GetChars(no_gc);
1010    if (!string.has_escape()) {
1011      DCHECK(!string.internalize());
1012      CopyChars(dest, chars_ + string.start(), string.length());
1013      return intermediate;
1014    }
1015    DecodeString(dest, string.start(), string.length());
1016
1017    if (!string.internalize()) return intermediate;
1018
1019    base::Vector<const SinkChar> data(dest, string.length());
1020    if (!hint.is_null() && Matches(data, hint)) return hint;
1021  }
1022
1023  return factory()->InternalizeString(intermediate, 0, string.length());
1024}
1025
1026template <typename Char>
1027Handle<String> JsonParser<Char>::MakeString(const JsonString& string,
1028                                            Handle<String> hint) {
1029  if (string.length() == 0) return factory()->empty_string();
1030
1031  if (string.internalize() && !string.has_escape()) {
1032    if (!hint.is_null()) {
1033      base::Vector<const Char> data(chars_ + string.start(), string.length());
1034      if (Matches(data, hint)) return hint;
1035    }
1036    if (chars_may_relocate_) {
1037      return factory()->InternalizeString(Handle<SeqString>::cast(source_),
1038                                          string.start(), string.length(),
1039                                          string.needs_conversion());
1040    }
1041    base::Vector<const Char> chars(chars_ + string.start(), string.length());
1042    return factory()->InternalizeString(chars, string.needs_conversion());
1043  }
1044
1045  if (sizeof(Char) == 1 ? V8_LIKELY(!string.needs_conversion())
1046                        : string.needs_conversion()) {
1047    Handle<SeqOneByteString> intermediate =
1048        factory()->NewRawOneByteString(string.length()).ToHandleChecked();
1049    return DecodeString(string, intermediate, hint);
1050  }
1051
1052  Handle<SeqTwoByteString> intermediate =
1053      factory()->NewRawTwoByteString(string.length()).ToHandleChecked();
1054  return DecodeString(string, intermediate, hint);
1055}
1056
1057template <typename Char>
1058template <typename SinkChar>
1059void JsonParser<Char>::DecodeString(SinkChar* sink, int start, int length) {
1060  SinkChar* sink_start = sink;
1061  const Char* cursor = chars_ + start;
1062  while (true) {
1063    const Char* end = cursor + length - (sink - sink_start);
1064    cursor = std::find_if(cursor, end, [&sink](Char c) {
1065      if (c == '\\') return true;
1066      *sink++ = c;
1067      return false;
1068    });
1069
1070    if (cursor == end) return;
1071
1072    cursor++;
1073
1074    switch (GetEscapeKind(character_json_scan_flags[*cursor])) {
1075      case EscapeKind::kSelf:
1076        *sink++ = *cursor;
1077        break;
1078
1079      case EscapeKind::kBackspace:
1080        *sink++ = '\x08';
1081        break;
1082
1083      case EscapeKind::kTab:
1084        *sink++ = '\x09';
1085        break;
1086
1087      case EscapeKind::kNewLine:
1088        *sink++ = '\x0A';
1089        break;
1090
1091      case EscapeKind::kFormFeed:
1092        *sink++ = '\x0C';
1093        break;
1094
1095      case EscapeKind::kCarriageReturn:
1096        *sink++ = '\x0D';
1097        break;
1098
1099      case EscapeKind::kUnicode: {
1100        base::uc32 value = 0;
1101        for (int i = 0; i < 4; i++) {
1102          value = value * 16 + base::HexValue(*++cursor);
1103        }
1104        if (value <=
1105            static_cast<base::uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
1106          *sink++ = value;
1107        } else {
1108          *sink++ = unibrow::Utf16::LeadSurrogate(value);
1109          *sink++ = unibrow::Utf16::TrailSurrogate(value);
1110        }
1111        break;
1112      }
1113
1114      case EscapeKind::kIllegal:
1115        UNREACHABLE();
1116    }
1117    cursor++;
1118  }
1119}
1120
1121template <typename Char>
1122JsonString JsonParser<Char>::ScanJsonString(bool needs_internalization) {
1123  DisallowGarbageCollection no_gc;
1124  int start = position();
1125  int offset = start;
1126  bool has_escape = false;
1127  base::uc32 bits = 0;
1128
1129  while (true) {
1130    cursor_ = std::find_if(cursor_, end_, [&bits](Char c) {
1131      if (sizeof(Char) == 2 && V8_UNLIKELY(c > unibrow::Latin1::kMaxChar)) {
1132        bits |= c;
1133        return false;
1134      }
1135      return MayTerminateJsonString(character_json_scan_flags[c]);
1136    });
1137
1138    if (V8_UNLIKELY(is_at_end())) {
1139      AllowGarbageCollection allow_before_exception;
1140      ReportUnexpectedCharacter(kEndOfString);
1141      break;
1142    }
1143
1144    if (*cursor_ == '"') {
1145      int end = position();
1146      advance();
1147      int length = end - offset;
1148      bool convert = sizeof(Char) == 1 ? bits > unibrow::Latin1::kMaxChar
1149                                       : bits <= unibrow::Latin1::kMaxChar;
1150      return JsonString(start, length, convert, needs_internalization,
1151                        has_escape);
1152    }
1153
1154    if (*cursor_ == '\\') {
1155      has_escape = true;
1156      base::uc32 c = NextCharacter();
1157      if (V8_UNLIKELY(!base::IsInRange(
1158              c, 0, static_cast<int32_t>(unibrow::Latin1::kMaxChar)))) {
1159        AllowGarbageCollection allow_before_exception;
1160        ReportUnexpectedCharacter(c);
1161        break;
1162      }
1163
1164      switch (GetEscapeKind(character_json_scan_flags[c])) {
1165        case EscapeKind::kSelf:
1166        case EscapeKind::kBackspace:
1167        case EscapeKind::kTab:
1168        case EscapeKind::kNewLine:
1169        case EscapeKind::kFormFeed:
1170        case EscapeKind::kCarriageReturn:
1171          offset += 1;
1172          break;
1173
1174        case EscapeKind::kUnicode: {
1175          base::uc32 value = ScanUnicodeCharacter();
1176          if (value == kInvalidUnicodeCharacter) {
1177            AllowGarbageCollection allow_before_exception;
1178            ReportUnexpectedCharacter(CurrentCharacter());
1179            return JsonString();
1180          }
1181          bits |= value;
1182          // \uXXXX results in either 1 or 2 Utf16 characters, depending on
1183          // whether the decoded value requires a surrogate pair.
1184          offset += 5 - (value > static_cast<base::uc32>(
1185                                     unibrow::Utf16::kMaxNonSurrogateCharCode));
1186          break;
1187        }
1188
1189        case EscapeKind::kIllegal:
1190          AllowGarbageCollection allow_before_exception;
1191          ReportUnexpectedCharacter(c);
1192          return JsonString();
1193      }
1194
1195      advance();
1196      continue;
1197    }
1198
1199    DCHECK_LT(*cursor_, 0x20);
1200    AllowGarbageCollection allow_before_exception;
1201    ReportUnexpectedCharacter(*cursor_);
1202    break;
1203  }
1204
1205  return JsonString();
1206}
1207
1208// Explicit instantiation.
1209template class JsonParser<uint8_t>;
1210template class JsonParser<uint16_t>;
1211
1212}  // namespace internal
1213}  // namespace v8
1214