json-parser.cc 40.6 KB
Newer Older
1 2 3 4
// Copyright 2016 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

Yang Guo's avatar
Yang Guo committed
5
#include "src/json/json-parser.h"
6

7
#include "src/common/message-template.h"
8
#include "src/debug/debug.h"
9
#include "src/numbers/conversions.h"
10
#include "src/numbers/hash-seed-inl.h"
11
#include "src/objects/field-type.h"
12
#include "src/objects/hash-table-inl.h"
13
#include "src/objects/objects-inl.h"
14
#include "src/objects/property-descriptor.h"
15 16
#include "src/strings/char-predicates-inl.h"
#include "src/strings/string-hasher.h"
17 18 19 20

namespace v8 {
namespace internal {

21 22
namespace {

23
constexpr JsonToken GetOneCharJsonToken(uint8_t c) {
24 25 26 27
  // clang-format off
  return
     c == '"' ? JsonToken::STRING :
     IsDecimalDigit(c) ?  JsonToken::NUMBER :
28
     c == '-' ? JsonToken::NUMBER :
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
     c == '[' ? JsonToken::LBRACK :
     c == '{' ? JsonToken::LBRACE :
     c == ']' ? JsonToken::RBRACK :
     c == '}' ? JsonToken::RBRACE :
     c == 't' ? JsonToken::TRUE_LITERAL :
     c == 'f' ? JsonToken::FALSE_LITERAL :
     c == 'n' ? JsonToken::NULL_LITERAL :
     c == ' ' ? JsonToken::WHITESPACE :
     c == '\t' ? JsonToken::WHITESPACE :
     c == '\r' ? JsonToken::WHITESPACE :
     c == '\n' ? JsonToken::WHITESPACE :
     c == ':' ? JsonToken::COLON :
     c == ',' ? JsonToken::COMMA :
     JsonToken::ILLEGAL;
  // clang-format on
}

// Table of one-character tokens, by character (0x00..0xFF only).
47 48
static const constexpr JsonToken one_char_json_tokens[256] = {
#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(N),
49 50
    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
51
#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(128 + N),
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
        INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
};

enum class EscapeKind : uint8_t {
  kIllegal,
  kSelf,
  kBackspace,
  kTab,
  kNewLine,
  kFormFeed,
  kCarriageReturn,
  kUnicode
};

67
using EscapeKindField = base::BitField8<EscapeKind, 0, 3>;
68 69
using MayTerminateStringField = EscapeKindField::Next<bool, 1>;
using NumberPartField = MayTerminateStringField::Next<bool, 1>;
70

71
constexpr bool MayTerminateJsonString(uint8_t flags) {
72 73 74 75 76 77 78 79 80 81 82
  return MayTerminateStringField::decode(flags);
}

constexpr EscapeKind GetEscapeKind(uint8_t flags) {
  return EscapeKindField::decode(flags);
}

constexpr bool IsNumberPart(uint8_t flags) {
  return NumberPartField::decode(flags);
}

83
constexpr uint8_t GetJsonScanFlags(uint8_t c) {
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
  // clang-format off
  return (c == 'b' ? EscapeKindField::encode(EscapeKind::kBackspace)
          : c == 't' ? EscapeKindField::encode(EscapeKind::kTab)
          : c == 'n' ? EscapeKindField::encode(EscapeKind::kNewLine)
          : c == 'f' ? EscapeKindField::encode(EscapeKind::kFormFeed)
          : c == 'r' ? EscapeKindField::encode(EscapeKind::kCarriageReturn)
          : c == 'u' ? EscapeKindField::encode(EscapeKind::kUnicode)
          : c == '"' ? EscapeKindField::encode(EscapeKind::kSelf)
          : c == '\\' ? EscapeKindField::encode(EscapeKind::kSelf)
          : c == '/' ? EscapeKindField::encode(EscapeKind::kSelf)
          : EscapeKindField::encode(EscapeKind::kIllegal)) |
         (c < 0x20 ? MayTerminateStringField::encode(true)
          : c == '"' ? MayTerminateStringField::encode(true)
          : c == '\\' ? MayTerminateStringField::encode(true)
          : MayTerminateStringField::encode(false)) |
         NumberPartField::encode(c == '.' ||
                                 c == 'e' ||
                                 c == 'E' ||
                                 IsDecimalDigit(c) ||
                                 c == '-' ||
                                 c == '+');
  // clang-format on
}

// Table of one-character scan flags, by character (0x00..0xFF only).
109 110
static const constexpr uint8_t character_json_scan_flags[256] = {
#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(N),
111 112
    INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
113
#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(128 + N),
114 115 116 117
        INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
#undef CALL_GET_SCAN_FLAGS
};

118 119
}  // namespace

120 121 122 123 124 125 126 127 128
MaybeHandle<Object> JsonParseInternalizer::Internalize(Isolate* isolate,
                                                       Handle<Object> object,
                                                       Handle<Object> reviver) {
  DCHECK(reviver->IsCallable());
  JsonParseInternalizer internalizer(isolate,
                                     Handle<JSReceiver>::cast(reviver));
  Handle<JSObject> holder =
      isolate->factory()->NewJSObject(isolate->object_function());
  Handle<String> name = isolate->factory()->empty_string();
129
  JSObject::AddProperty(isolate, holder, name, object, NONE);
130 131 132 133 134 135 136 137
  return internalizer.InternalizeJsonProperty(holder, name);
}

MaybeHandle<Object> JsonParseInternalizer::InternalizeJsonProperty(
    Handle<JSReceiver> holder, Handle<String> name) {
  HandleScope outer_scope(isolate_);
  Handle<Object> value;
  ASSIGN_RETURN_ON_EXCEPTION(
138 139
      isolate_, value, Object::GetPropertyOrElement(isolate_, holder, name),
      Object);
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
  if (value->IsJSReceiver()) {
    Handle<JSReceiver> object = Handle<JSReceiver>::cast(value);
    Maybe<bool> is_array = Object::IsArray(object);
    if (is_array.IsNothing()) return MaybeHandle<Object>();
    if (is_array.FromJust()) {
      Handle<Object> length_object;
      ASSIGN_RETURN_ON_EXCEPTION(
          isolate_, length_object,
          Object::GetLengthFromArrayLike(isolate_, object), Object);
      double length = length_object->Number();
      for (double i = 0; i < length; i++) {
        HandleScope inner_scope(isolate_);
        Handle<Object> index = isolate_->factory()->NewNumber(i);
        Handle<String> name = isolate_->factory()->NumberToString(index);
        if (!RecurseAndApply(object, name)) return MaybeHandle<Object>();
      }
    } else {
      Handle<FixedArray> contents;
      ASSIGN_RETURN_ON_EXCEPTION(
          isolate_, contents,
          KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,
                                  ENUMERABLE_STRINGS,
                                  GetKeysConversion::kConvertToString),
          Object);
      for (int i = 0; i < contents->length(); i++) {
        HandleScope inner_scope(isolate_);
        Handle<String> name(String::cast(contents->get(i)), isolate_);
        if (!RecurseAndApply(object, name)) return MaybeHandle<Object>();
      }
    }
  }
  Handle<Object> argv[] = {name, value};
  Handle<Object> result;
  ASSIGN_RETURN_ON_EXCEPTION(
      isolate_, result, Execution::Call(isolate_, reviver_, holder, 2, argv),
      Object);
  return outer_scope.CloseAndEscape(result);
}

bool JsonParseInternalizer::RecurseAndApply(Handle<JSReceiver> holder,
                                            Handle<String> name) {
181 182
  STACK_CHECK(isolate_, false);

183 184 185 186
  Handle<Object> result;
  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
      isolate_, result, InternalizeJsonProperty(holder, name), false);
  Maybe<bool> change_result = Nothing<bool>();
187
  if (result->IsUndefined(isolate_)) {
188 189
    change_result = JSReceiver::DeletePropertyOrElement(holder, name,
                                                        LanguageMode::kSloppy);
190 191 192 193 194 195 196
  } else {
    PropertyDescriptor desc;
    desc.set_value(result);
    desc.set_configurable(true);
    desc.set_enumerable(true);
    desc.set_writable(true);
    change_result = JSReceiver::DefineOwnProperty(isolate_, holder, name, &desc,
197
                                                  Just(kDontThrow));
198 199 200 201 202
  }
  MAYBE_RETURN(change_result, false);
  return true;
}

203 204 205
template <typename Char>
JsonParser<Char>::JsonParser(Isolate* isolate, Handle<String> source)
    : isolate_(isolate),
206
      hash_seed_(HashSeed(isolate)),
207
      object_constructor_(isolate_->object_function()),
208
      original_source_(source) {
209 210
  size_t start = 0;
  size_t length = source->length();
211 212
  if (source->IsSlicedString()) {
    SlicedString string = SlicedString::cast(*source);
213
    start = string.offset();
214 215 216 217 218 219
    String parent = string.parent();
    if (parent.IsThinString()) parent = ThinString::cast(parent).actual();
    source_ = handle(parent, isolate);
  } else {
    source_ = String::Flatten(isolate, source);
  }
220

221 222
  if (StringShape(*source_).IsExternal()) {
    chars_ =
223
        static_cast<const Char*>(SeqExternalString::cast(*source_).GetChars());
224
    chars_may_relocate_ = false;
225 226 227 228
  } else {
    DisallowHeapAllocation no_gc;
    isolate->heap()->AddGCEpilogueCallback(UpdatePointersCallback,
                                           v8::kGCTypeAll, this);
229
    chars_ = SeqString::cast(*source_).GetChars(no_gc);
230
    chars_may_relocate_ = true;
231
  }
232 233
  cursor_ = chars_ + start;
  end_ = cursor_ + length;
234 235
}

236 237 238 239 240 241 242 243
template <typename Char>
void JsonParser<Char>::ReportUnexpectedToken(JsonToken token) {
  // Some exception (for example stack overflow) is already pending.
  if (isolate_->has_pending_exception()) return;

  // Parse failed. Current character is the unexpected token.
  Factory* factory = this->factory();
  MessageTemplate message;
244 245 246 247 248
  int offset = original_source_->IsSlicedString()
                   ? SlicedString::cast(*original_source_).offset()
                   : 0;
  int pos = position() - offset;
  Handle<Object> arg1 = Handle<Smi>(Smi::FromInt(pos), isolate());
249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
  Handle<Object> arg2;

  switch (token) {
    case JsonToken::EOS:
      message = MessageTemplate::kJsonParseUnexpectedEOS;
      break;
    case JsonToken::NUMBER:
      message = MessageTemplate::kJsonParseUnexpectedTokenNumber;
      break;
    case JsonToken::STRING:
      message = MessageTemplate::kJsonParseUnexpectedTokenString;
      break;
    default:
      message = MessageTemplate::kJsonParseUnexpectedToken;
      arg2 = arg1;
      arg1 = factory->LookupSingleCharacterStringFromCode(*cursor_);
      break;
  }

  Handle<Script> script(factory->NewScript(original_source_));
  if (isolate()->NeedsSourcePositionsForProfiling()) {
270
    Script::InitLineEnds(isolate(), script);
271 272 273 274
  }
  // We should sent compile error event because we compile JSON object in
  // separated source file.
  isolate()->debug()->OnCompileError(script);
275
  MessageLocation location(script, pos, pos + 1);
276 277 278 279 280 281 282 283 284 285 286 287 288
  Handle<Object> error = factory->NewSyntaxError(message, arg1, arg2);
  isolate()->Throw(*error, &location);

  // Move the cursor to the end so we won't be able to proceed parsing.
  cursor_ = end_;
}

template <typename Char>
void JsonParser<Char>::ReportUnexpectedCharacter(uc32 c) {
  JsonToken token = JsonToken::ILLEGAL;
  if (c == kEndOfString) {
    token = JsonToken::EOS;
  } else if (c <= unibrow::Latin1::kMaxChar) {
289
    token = one_char_json_tokens[c];
290 291 292 293
  }
  return ReportUnexpectedToken(token);
}

294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
template <typename Char>
JsonParser<Char>::~JsonParser() {
  if (StringShape(*source_).IsExternal()) {
    // Check that the string shape hasn't changed. Otherwise our GC hooks are
    // broken.
    SeqExternalString::cast(*source_);
  } else {
    // Check that the string shape hasn't changed. Otherwise our GC hooks are
    // broken.
    SeqString::cast(*source_);
    isolate()->heap()->RemoveGCEpilogueCallback(UpdatePointersCallback, this);
  }
}

template <typename Char>
MaybeHandle<Object> JsonParser<Char>::ParseJson() {
310
  MaybeHandle<Object> result = ParseJsonValue();
311 312
  if (!Check(JsonToken::EOS)) ReportUnexpectedToken(peek());
  if (isolate_->has_pending_exception()) return MaybeHandle<Object>();
313 314 315
  return result;
}

316 317 318
MaybeHandle<Object> InternalizeJsonProperty(Handle<JSObject> holder,
                                            Handle<String> key);

319 320
template <typename Char>
void JsonParser<Char>::SkipWhitespace() {
321 322 323 324
  next_ = JsonToken::EOS;

  cursor_ = std::find_if(cursor_, end_, [this](Char c) {
    JsonToken current = V8_LIKELY(c <= unibrow::Latin1::kMaxChar)
325
                            ? one_char_json_tokens[c]
326 327 328 329 330
                            : JsonToken::ILLEGAL;
    bool result = current != JsonToken::WHITESPACE;
    if (result) next_ = current;
    return result;
  });
331 332
}

333 334 335 336 337 338 339 340 341 342 343
template <typename Char>
uc32 JsonParser<Char>::ScanUnicodeCharacter() {
  uc32 value = 0;
  for (int i = 0; i < 4; i++) {
    int digit = HexValue(NextCharacter());
    if (V8_UNLIKELY(digit < 0)) return -1;
    value = value * 16 + digit;
  }
  return value;
}

344
// Parse any JSON value.
345
template <typename Char>
346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
JsonString JsonParser<Char>::ScanJsonPropertyKey(JsonContinuation* cont) {
  {
    DisallowHeapAllocation no_gc;
    const Char* start = cursor_;
    uc32 first = CurrentCharacter();
    if (first == '\\' && NextCharacter() == 'u') first = ScanUnicodeCharacter();
    if (IsDecimalDigit(first)) {
      if (first == '0') {
        if (NextCharacter() == '"') {
          advance();
          // Record element information.
          cont->elements++;
          DCHECK_LE(0, cont->max_index);
          return JsonString(0);
        }
      } else {
        uint32_t index = first - '0';
        while (true) {
          cursor_ = std::find_if(cursor_ + 1, end_, [&index](Char c) {
365
            return !TryAddArrayIndexChar(&index, c);
366 367 368 369 370 371 372 373 374
          });

          if (CurrentCharacter() == '"') {
            advance();
            // Record element information.
            cont->elements++;
            cont->max_index = Max(cont->max_index, index);
            return JsonString(index);
          }
375

376
          if (CurrentCharacter() == '\\' && NextCharacter() == 'u') {
377
            if (TryAddArrayIndexChar(&index, ScanUnicodeCharacter())) continue;
378 379 380 381 382
          }

          break;
        }
      }
383
    }
384 385 386 387 388
    // Reset cursor_ to start if the key is not an index.
    cursor_ = start;
  }
  return ScanJsonString(true);
}
389

390 391 392 393 394 395 396
namespace {
Handle<Map> ParentOfDescriptorOwner(Isolate* isolate, Handle<Map> maybe_root,
                                    Handle<Map> source, int descriptor) {
  if (descriptor == 0) {
    DCHECK_EQ(0, maybe_root->NumberOfOwnDescriptors());
    return maybe_root;
  }
397 398
  return handle(source->FindFieldOwner(isolate, InternalIndex(descriptor - 1)),
                isolate);
399 400 401
}
}  // namespace

402 403 404
template <typename Char>
Handle<Object> JsonParser<Char>::BuildJsonObject(
    const JsonContinuation& cont,
405
    const std::vector<JsonProperty>& property_stack, Handle<Map> feedback) {
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
  size_t start = cont.index;
  int length = static_cast<int>(property_stack.size() - start);
  int named_length = length - cont.elements;

  Handle<Map> initial_map = factory()->ObjectLiteralMapFromCache(
      isolate_->native_context(), named_length);

  Handle<Map> map = initial_map;

  Handle<FixedArrayBase> elements = factory()->empty_fixed_array();

  // First store the elements.
  if (cont.elements > 0) {
    // Store as dictionary elements if that would use less memory.
    if (ShouldConvertToSlowElements(cont.elements, cont.max_index + 1)) {
      Handle<NumberDictionary> elms =
          NumberDictionary::New(isolate_, cont.elements);
      for (int i = 0; i < length; i++) {
        const JsonProperty& property = property_stack[start + i];
        if (!property.string.is_index()) continue;
        uint32_t index = property.string.index();
        Handle<Object> value = property.value;
        elms = NumberDictionary::Set(isolate_, elms, index, value);
      }
      map = Map::AsElementsKind(isolate_, map, DICTIONARY_ELEMENTS);
      elements = elms;
    } else {
      Handle<FixedArray> elms =
          factory()->NewFixedArrayWithHoles(cont.max_index + 1);
      DisallowHeapAllocation no_gc;
      WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
      DCHECK_EQ(HOLEY_ELEMENTS, map->elements_kind());

      for (int i = 0; i < length; i++) {
        const JsonProperty& property = property_stack[start + i];
        if (!property.string.is_index()) continue;
        uint32_t index = property.string.index();
        Handle<Object> value = property.value;
        elms->set(static_cast<int>(index), *value, mode);
      }
      elements = elms;
447 448
    }
  }
449

450 451 452 453 454 455 456
  int feedback_descriptors =
      (feedback.is_null() ||
       feedback->elements_kind() != map->elements_kind() ||
       feedback->instance_size() != map->instance_size())
          ? 0
          : feedback->NumberOfOwnDescriptors();

457 458
  int i;
  int descriptor = 0;
459
  int new_mutable_double = 0;
460 461 462 463 464
  for (i = 0; i < length; i++) {
    const JsonProperty& property = property_stack[start + i];
    if (property.string.is_index()) continue;
    Handle<String> expected;
    Handle<Map> target;
465
    InternalIndex descriptor_index(descriptor);
466
    if (descriptor < feedback_descriptors) {
467 468 469
      expected = handle(String::cast(feedback->instance_descriptors().GetKey(
                            descriptor_index)),
                        isolate_);
470
    } else {
471 472 473 474 475 476 477 478 479 480
      DisallowHeapAllocation no_gc;
      TransitionsAccessor transitions(isolate(), *map, &no_gc);
      expected = transitions.ExpectedTransitionKey();
      if (!expected.is_null()) {
        // Directly read out the target while reading out the key, otherwise it
        // might die while building the string below.
        target = TransitionsAccessor(isolate(), *map, &no_gc)
                     .ExpectedTransitionTarget();
      }
    }
481

482
    Handle<String> key = MakeString(property.string, expected);
483 484 485 486 487 488 489 490 491 492 493 494
    if (key.is_identical_to(expected)) {
      if (descriptor < feedback_descriptors) target = feedback;
    } else {
      if (descriptor < feedback_descriptors) {
        map = ParentOfDescriptorOwner(isolate_, map, feedback, descriptor);
        feedback_descriptors = 0;
      }
      if (!TransitionsAccessor(isolate(), map)
               .FindTransitionToField(key)
               .ToHandle(&target)) {
        break;
      }
495 496 497 498
    }

    Handle<Object> value = property.value;

499
    PropertyDetails details =
500
        target->instance_descriptors().GetDetails(descriptor_index);
501 502 503
    Representation expected_representation = details.representation();

    if (!value->FitsRepresentation(expected_representation)) {
504
      Representation representation = value->OptimalRepresentation(isolate());
505
      representation = representation.generalize(expected_representation);
506 507 508 509
      if (!expected_representation.CanBeInPlaceChangedTo(representation)) {
        map = ParentOfDescriptorOwner(isolate_, map, target, descriptor);
        break;
      }
510 511
      Handle<FieldType> value_type =
          value->OptimalType(isolate(), representation);
512 513
      Map::GeneralizeField(isolate(), target, descriptor_index,
                           details.constness(), representation, value_type);
514 515
    } else if (expected_representation.IsHeapObject() &&
               !target->instance_descriptors()
516
                    .GetFieldType(descriptor_index)
517
                    .NowContains(value)) {
518 519
      Handle<FieldType> value_type =
          value->OptimalType(isolate(), expected_representation);
520 521 522
      Map::GeneralizeField(isolate(), target, descriptor_index,
                           details.constness(), expected_representation,
                           value_type);
523 524 525
    } else if (!FLAG_unbox_double_fields &&
               expected_representation.IsDouble() && value->IsSmi()) {
      new_mutable_double++;
526 527 528
    }

    DCHECK(target->instance_descriptors()
529
               .GetFieldType(descriptor_index)
530
               .NowContains(value));
531 532 533 534
    map = target;
    descriptor++;
  }

535 536 537 538 539 540 541
  // Fast path: Write all transitioned named properties.
  if (i == length && descriptor < feedback_descriptors) {
    map = ParentOfDescriptorOwner(isolate_, map, map, descriptor);
  }

  // Preallocate all mutable heap numbers so we don't need to allocate while
  // setting up the object. Otherwise verification of that object may fail.
542 543 544
  Handle<ByteArray> mutable_double_buffer;
  // Allocate enough space so we can double-align the payload.
  const int kMutableDoubleSize = sizeof(double) * 2;
545
  STATIC_ASSERT(HeapNumber::kSize <= kMutableDoubleSize);
546 547 548
  if (new_mutable_double > 0) {
    mutable_double_buffer =
        factory()->NewByteArray(kMutableDoubleSize * new_mutable_double);
549 550
  }

551 552 553 554 555
  Handle<JSObject> object = initial_map->is_dictionary_map()
                                ? factory()->NewSlowJSObjectFromMap(map)
                                : factory()->NewJSObjectFromMap(map);
  object->set_elements(*elements);

556 557 558 559
  {
    descriptor = 0;
    DisallowHeapAllocation no_gc;
    WriteBarrierMode mode = object->GetWriteBarrierMode(no_gc);
560 561 562 563 564 565
    Address mutable_double_address =
        mutable_double_buffer.is_null()
            ? 0
            : reinterpret_cast<Address>(
                  mutable_double_buffer->GetDataStartAddress());
    Address filler_address = mutable_double_address;
566 567 568 569 570 571
    if (kTaggedSize != kDoubleSize) {
      if (IsAligned(mutable_double_address, kDoubleAlignment)) {
        mutable_double_address += kTaggedSize;
      } else {
        filler_address += HeapNumber::kSize;
      }
572
    }
573 574 575
    for (int j = 0; j < i; j++) {
      const JsonProperty& property = property_stack[start + j];
      if (property.string.is_index()) continue;
576
      InternalIndex descriptor_index(descriptor);
577
      PropertyDetails details =
578
          map->instance_descriptors().GetDetails(descriptor_index);
579
      Object value = *property.value;
580
      FieldIndex index = FieldIndex::ForDescriptor(*map, descriptor_index);
581 582 583 584 585 586 587 588 589 590 591 592 593 594
      descriptor++;

      if (details.representation().IsDouble()) {
        if (object->IsUnboxedDoubleField(index)) {
          uint64_t bits;
          if (value.IsSmi()) {
            bits = bit_cast<uint64_t>(static_cast<double>(Smi::ToInt(value)));
          } else {
            DCHECK(value.IsHeapNumber());
            bits = HeapNumber::cast(value).value_as_bits();
          }
          object->RawFastDoublePropertyAsBitsAtPut(index, bits);
          continue;
        }
595

596
        if (value.IsSmi()) {
597 598 599 600 601 602 603 604
          if (kTaggedSize != kDoubleSize) {
            // Write alignment filler.
            HeapObject filler = HeapObject::FromAddress(filler_address);
            filler.set_map_after_allocation(
                *factory()->one_pointer_filler_map());
            filler_address += kMutableDoubleSize;
          }

605 606
          uint64_t bits =
              bit_cast<uint64_t>(static_cast<double>(Smi::ToInt(value)));
607 608 609 610
          // Allocate simple heapnumber with immortal map, with non-pointer
          // payload, so we can skip notifying object layout change.

          HeapObject hn = HeapObject::FromAddress(mutable_double_address);
611 612
          hn.set_map_after_allocation(*factory()->heap_number_map());
          HeapNumber::cast(hn).set_value_as_bits(bits);
613 614
          value = hn;
          mutable_double_address += kMutableDoubleSize;
615
        } else {
616
          DCHECK(value.IsHeapNumber());
617
          HeapObject::cast(value).synchronized_set_map(
618
              *factory()->heap_number_map());
619 620
        }
      }
621
      object->RawFastInobjectPropertyAtPut(index, value, mode);
622
    }
623
    // Make all mutable HeapNumbers alive.
624 625 626 627
    if (!mutable_double_buffer.is_null()) {
#ifdef DEBUG
      Address end =
          reinterpret_cast<Address>(mutable_double_buffer->GetDataEndAddress());
628 629 630 631 632 633 634
      if (kTaggedSize != kDoubleSize) {
        DCHECK_EQ(Min(filler_address, mutable_double_address), end);
        DCHECK_GE(filler_address, end);
        DCHECK_GE(mutable_double_address, end);
      } else {
        DCHECK_EQ(mutable_double_address, end);
      }
635 636 637
#endif
      mutable_double_buffer->set_length(0);
    }
638 639 640 641 642 643 644 645 646 647 648 649 650
  }

  // Slow path: define remaining named properties.
  for (; i < length; i++) {
    HandleScope scope(isolate_);
    const JsonProperty& property = property_stack[start + i];
    if (property.string.is_index()) continue;
    Handle<String> key = MakeString(property.string);
#ifdef DEBUG
    uint32_t index;
    DCHECK(!key->AsArrayIndex(&index));
#endif
    Handle<Object> value = property.value;
651
    LookupIterator it(isolate_, object, key, object, LookupIterator::OWN);
652
    JSObject::DefineOwnPropertyIgnoreAttributes(&it, value, NONE).Check();
653
  }
654 655

  return object;
656 657
}

658
template <typename Char>
659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
Handle<Object> JsonParser<Char>::BuildJsonArray(
    const JsonContinuation& cont,
    const std::vector<Handle<Object>>& element_stack) {
  size_t start = cont.index;
  int length = static_cast<int>(element_stack.size() - start);

  ElementsKind kind = PACKED_SMI_ELEMENTS;
  for (size_t i = start; i < element_stack.size(); i++) {
    Object value = *element_stack[i];
    if (value.IsHeapObject()) {
      if (HeapObject::cast(value).IsHeapNumber()) {
        kind = PACKED_DOUBLE_ELEMENTS;
      } else {
        kind = PACKED_ELEMENTS;
        break;
      }
675
    }
676
  }
677

678 679 680 681 682
  Handle<JSArray> array = factory()->NewJSArray(kind, length, length);
  if (kind == PACKED_DOUBLE_ELEMENTS) {
    DisallowHeapAllocation no_gc;
    FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
    for (int i = 0; i < length; i++) {
683
      elements.set(i, element_stack[start + i]->Number());
684 685 686 687 688 689 690 691
    }
  } else {
    DisallowHeapAllocation no_gc;
    FixedArray elements = FixedArray::cast(array->elements());
    WriteBarrierMode mode = kind == PACKED_SMI_ELEMENTS
                                ? SKIP_WRITE_BARRIER
                                : elements.GetWriteBarrierMode(no_gc);
    for (int i = 0; i < length; i++) {
692
      elements.set(i, *element_stack[start + i], mode);
693 694 695
    }
  }
  return array;
696 697
}

698
// Parse any JSON value.
699
template <typename Char>
700 701 702 703
MaybeHandle<Object> JsonParser<Char>::ParseJsonValue() {
  std::vector<JsonContinuation> cont_stack;
  std::vector<JsonProperty> property_stack;
  std::vector<Handle<Object>> element_stack;
704

705 706 707
  cont_stack.reserve(16);
  property_stack.reserve(16);
  element_stack.reserve(16);
708

709
  JsonContinuation cont(isolate_, JsonContinuation::kReturn, 0);
710

711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730
  Handle<Object> value;
  while (true) {
    // Produce a json value.
    //
    // Iterate until a value is produced. Starting but not immediately finishing
    // objects and arrays will cause the loop to continue until a first member
    // is completed.
    while (true) {
      SkipWhitespace();
      // The switch is immediately followed by 'break' so we can use 'break' to
      // break out of the loop, and 'continue' to continue the loop.
      switch (peek()) {
        case JsonToken::STRING:
          Consume(JsonToken::STRING);
          value = MakeString(ScanJsonString(false));
          break;

        case JsonToken::NUMBER:
          value = ParseJsonNumber();
          break;
731

732 733 734 735 736 737
        case JsonToken::LBRACE: {
          Consume(JsonToken::LBRACE);
          if (Check(JsonToken::RBRACE)) {
            // TODO(verwaest): Directly use the map instead.
            value = factory()->NewJSObject(object_constructor_);
            break;
738 739
          }

740 741 742 743
          // Start parsing an object with properties.
          cont_stack.emplace_back(std::move(cont));
          cont = JsonContinuation(isolate_, JsonContinuation::kObjectProperty,
                                  property_stack.size());
744

745 746 747
          // Parse the property key.
          ExpectNext(JsonToken::STRING);
          property_stack.emplace_back(ScanJsonPropertyKey(&cont));
748

749
          ExpectNext(JsonToken::COLON);
750

751
          // Continue to start producing the first property value.
752
          continue;
753
        }
754

755 756 757 758 759 760
        case JsonToken::LBRACK:
          Consume(JsonToken::LBRACK);
          if (Check(JsonToken::RBRACK)) {
            value = factory()->NewJSArray(0, PACKED_SMI_ELEMENTS);
            break;
          }
761

762 763 764 765
          // Start parsing an array with elements.
          cont_stack.emplace_back(std::move(cont));
          cont = JsonContinuation(isolate_, JsonContinuation::kArrayElement,
                                  element_stack.size());
766

767 768
          // Continue to start producing the first array element.
          continue;
769

770 771 772 773
        case JsonToken::TRUE_LITERAL:
          ScanLiteral("true");
          value = factory()->true_value();
          break;
774

775 776 777 778
        case JsonToken::FALSE_LITERAL:
          ScanLiteral("false");
          value = factory()->false_value();
          break;
779

780 781 782 783
        case JsonToken::NULL_LITERAL:
          ScanLiteral("null");
          value = factory()->null_value();
          break;
784

785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804
        case JsonToken::COLON:
        case JsonToken::COMMA:
        case JsonToken::ILLEGAL:
        case JsonToken::RBRACE:
        case JsonToken::RBRACK:
        case JsonToken::EOS:
          ReportUnexpectedCharacter(CurrentCharacter());
          // Pop the continuation stack to correctly tear down handle scopes.
          while (!cont_stack.empty()) {
            cont = std::move(cont_stack.back());
            cont_stack.pop_back();
          }
          return MaybeHandle<Object>();

        case JsonToken::WHITESPACE:
          UNREACHABLE();
      }

      // Done producing a value, consume it.
      break;
805 806
    }

807 808 809 810 811 812 813 814 815 816
    // Consume a produced json value.
    //
    // Iterate as long as values are produced (arrays or object literals are
    // finished).
    while (true) {
      // The switch is immediately followed by 'break' so we can use 'break' to
      // break out of the loop, and 'continue' to continue the loop.
      switch (cont.type()) {
        case JsonContinuation::kReturn:
          return cont.scope.CloseAndEscape(value);
817

818 819 820
        case JsonContinuation::kObjectProperty: {
          // Store the previous property value into its property info.
          property_stack.back().value = value;
821

822 823 824
          if (V8_LIKELY(Check(JsonToken::COMMA))) {
            // Parse the property key.
            ExpectNext(JsonToken::STRING);
825

826 827
            property_stack.emplace_back(ScanJsonPropertyKey(&cont));
            ExpectNext(JsonToken::COLON);
828

829 830 831 832
            // Break to start producing the subsequent property value.
            break;
          }

833 834 835 836 837
          Handle<Map> feedback;
          if (cont_stack.size() > 0 &&
              cont_stack.back().type() == JsonContinuation::kArrayElement &&
              cont_stack.back().index < element_stack.size() &&
              element_stack.back()->IsJSObject()) {
838 839 840 841 842
            Map maybe_feedback = JSObject::cast(*element_stack.back()).map();
            // Don't consume feedback from objects with a map that's detached
            // from the transition tree.
            if (!maybe_feedback.GetBackPointer().IsUndefined(isolate_)) {
              feedback = handle(maybe_feedback, isolate_);
843 844 845
              if (feedback->is_deprecated()) {
                feedback = Map::Update(isolate_, feedback);
              }
846
            }
847 848
          }
          value = BuildJsonObject(cont, property_stack, feedback);
849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878
          property_stack.resize(cont.index);
          Expect(JsonToken::RBRACE);

          // Return the object.
          value = cont.scope.CloseAndEscape(value);
          // Pop the continuation.
          cont = std::move(cont_stack.back());
          cont_stack.pop_back();
          // Consume to produced object.
          continue;
        }

        case JsonContinuation::kArrayElement: {
          // Store the previous element on the stack.
          element_stack.emplace_back(value);
          // Break to start producing the subsequent element value.
          if (V8_LIKELY(Check(JsonToken::COMMA))) break;

          value = BuildJsonArray(cont, element_stack);
          element_stack.resize(cont.index);
          Expect(JsonToken::RBRACK);

          // Return the array.
          value = cont.scope.CloseAndEscape(value);
          // Pop the continuation.
          cont = std::move(cont_stack.back());
          cont_stack.pop_back();
          // Consume the produced array.
          continue;
        }
879
      }
880 881

      // Done consuming a value. Produce next value.
882 883
      break;
    }
884 885 886
  }
}

887
template <typename Char>
888 889 890 891 892 893
void JsonParser<Char>::AdvanceToNonDecimal() {
  cursor_ =
      std::find_if(cursor_, end_, [](Char c) { return !IsDecimalDigit(c); });
}

template <typename Char>
894
Handle<Object> JsonParser<Char>::ParseJsonNumber() {
895
  double number;
896
  int sign = 1;
897 898

  {
899
    const Char* start = cursor_;
900
    DisallowHeapAllocation no_gc;
901

902 903 904 905 906 907 908
    uc32 c = *cursor_;
    if (c == '-') {
      sign = -1;
      c = NextCharacter();
    }

    if (c == '0') {
909 910
      // Prefix zero is only allowed if it's the only digit before
      // a decimal point or exponent.
911
      c = NextCharacter();
912 913
      if (base::IsInRange(c, 0,
                          static_cast<int32_t>(unibrow::Latin1::kMaxChar)) &&
914
          IsNumberPart(character_json_scan_flags[c])) {
915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935
        if (V8_UNLIKELY(IsDecimalDigit(c))) {
          AllowHeapAllocation allow_before_exception;
          ReportUnexpectedToken(JsonToken::NUMBER);
          return handle(Smi::FromInt(0), isolate_);
        }
      } else if (sign > 0) {
        return handle(Smi::FromInt(0), isolate_);
      }
    } else {
      const Char* smi_start = cursor_;
      AdvanceToNonDecimal();
      if (V8_UNLIKELY(smi_start == cursor_)) {
        AllowHeapAllocation allow_before_exception;
        ReportUnexpectedCharacter(CurrentCharacter());
        return handle(Smi::FromInt(0), isolate_);
      }
      uc32 c = CurrentCharacter();
      STATIC_ASSERT(Smi::IsValid(-999999999));
      STATIC_ASSERT(Smi::IsValid(999999999));
      const int kMaxSmiLength = 9;
      if ((cursor_ - smi_start) <= kMaxSmiLength &&
936 937
          (!base::IsInRange(c, 0,
                            static_cast<int32_t>(unibrow::Latin1::kMaxChar)) ||
938
           !IsNumberPart(character_json_scan_flags[c]))) {
939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
        // Smi.
        int32_t i = 0;
        for (; smi_start != cursor_; smi_start++) {
          DCHECK(IsDecimalDigit(*smi_start));
          i = (i * 10) + ((*smi_start) - '0');
        }
        // TODO(verwaest): Cache?
        return handle(Smi::FromInt(i * sign), isolate_);
      }
    }

    if (CurrentCharacter() == '.') {
      uc32 c = NextCharacter();
      if (!IsDecimalDigit(c)) {
        AllowHeapAllocation allow_before_exception;
        ReportUnexpectedCharacter(c);
        return handle(Smi::FromInt(0), isolate_);
      }
      AdvanceToNonDecimal();
    }

    if (AsciiAlphaToLower(CurrentCharacter()) == 'e') {
      uc32 c = NextCharacter();
      if (c == '-' || c == '+') c = NextCharacter();
      if (!IsDecimalDigit(c)) {
        AllowHeapAllocation allow_before_exception;
        ReportUnexpectedCharacter(c);
        return handle(Smi::FromInt(0), isolate_);
      }
      AdvanceToNonDecimal();
    }

971
    Vector<const Char> chars(start, cursor_ - start);
972
    number = StringToDouble(chars,
973 974
                            NO_FLAGS,  // Hex, octal or trailing junk.
                            std::numeric_limits<double>::quiet_NaN());
975

976
    DCHECK(!std::isnan(number));
977
  }
978

979
  return factory()->NewNumber(number);
980 981
}

982
namespace {
983

984 985
template <typename Char>
bool Matches(const Vector<const Char>& chars, Handle<String> string) {
986
  DCHECK(!string.is_null());
987

988
  if (chars.length() != string->length()) return false;
989

990
  DisallowHeapAllocation no_gc;
991 992 993 994 995
  if (string->IsOneByteRepresentation()) {
    const uint8_t* string_data = string->GetChars<uint8_t>(no_gc);
    return CompareChars(chars.begin(), string_data, chars.length()) == 0;
  }
  const uint16_t* string_data = string->GetChars<uint16_t>(no_gc);
996
  return CompareChars(chars.begin(), string_data, chars.length()) == 0;
997 998
}

999
}  // namespace
1000 1001

template <typename Char>
1002
template <typename SinkSeqString>
1003
Handle<String> JsonParser<Char>::DecodeString(
1004
    const JsonString& string, Handle<SinkSeqString> intermediate,
1005
    Handle<String> hint) {
1006
  using SinkChar = typename SinkSeqString::Char;
1007
  {
1008
    DisallowHeapAllocation no_gc;
1009
    SinkChar* dest = intermediate->GetChars(no_gc);
1010 1011
    if (!string.has_escape()) {
      DCHECK(!string.internalize());
1012
      CopyChars(dest, chars_ + string.start(), string.length());
1013
      return intermediate;
1014
    }
1015 1016 1017
    DecodeString(dest, string.start(), string.length());

    if (!string.internalize()) return intermediate;
1018 1019

    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 1026
}

template <typename Char>
1027 1028 1029 1030 1031 1032 1033 1034 1035 1036
Handle<String> JsonParser<Char>::MakeString(const JsonString& string,
                                            Handle<String> hint) {
  if (string.length() == 0) return factory()->empty_string();

  if (string.internalize() && !string.has_escape()) {
    if (!hint.is_null()) {
      Vector<const Char> data(chars_ + string.start(), string.length());
      if (Matches(data, hint)) return hint;
    }
    if (chars_may_relocate_) {
1037
      return factory()->InternalizeString(Handle<SeqString>::cast(source_),
1038 1039
                                          string.start(), string.length(),
                                          string.needs_conversion());
1040 1041
    }
    Vector<const Char> chars(chars_ + string.start(), string.length());
1042
    return factory()->InternalizeString(chars, string.needs_conversion());
1043 1044
  }

1045 1046
  if (sizeof(Char) == 1 ? V8_LIKELY(!string.needs_conversion())
                        : string.needs_conversion()) {
1047 1048
    Handle<SeqOneByteString> intermediate =
        factory()->NewRawOneByteString(string.length()).ToHandleChecked();
1049
    return DecodeString(string, intermediate, hint);
1050 1051 1052 1053
  }

  Handle<SeqTwoByteString> intermediate =
      factory()->NewRawTwoByteString(string.length()).ToHandleChecked();
1054
  return DecodeString(string, intermediate, hint);
1055 1056 1057
}

template <typename Char>
1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068
template <typename SinkChar>
void JsonParser<Char>::DecodeString(SinkChar* sink, int start, int length) {
  SinkChar* sink_start = sink;
  const Char* cursor = chars_ + start;
  while (true) {
    const Char* end = cursor + length - (sink - sink_start);
    cursor = std::find_if(cursor, end, [&sink](Char c) {
      if (c == '\\') return true;
      *sink++ = c;
      return false;
    });
1069

1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
    if (cursor == end) return;

    cursor++;

    switch (GetEscapeKind(character_json_scan_flags[*cursor])) {
      case EscapeKind::kSelf:
        *sink++ = *cursor;
        break;

      case EscapeKind::kBackspace:
        *sink++ = '\x08';
        break;

      case EscapeKind::kTab:
        *sink++ = '\x09';
        break;

      case EscapeKind::kNewLine:
        *sink++ = '\x0A';
        break;

      case EscapeKind::kFormFeed:
        *sink++ = '\x0C';
        break;

      case EscapeKind::kCarriageReturn:
        *sink++ = '\x0D';
        break;

      case EscapeKind::kUnicode: {
        uc32 value = 0;
        for (int i = 0; i < 4; i++) {
          value = value * 16 + HexValue(*++cursor);
        }
        if (value <=
            static_cast<uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
          *sink++ = value;
1107
        } else {
1108 1109
          *sink++ = unibrow::Utf16::LeadSurrogate(value);
          *sink++ = unibrow::Utf16::TrailSurrogate(value);
1110
        }
1111
        break;
1112
      }
1113

1114 1115
      case EscapeKind::kIllegal:
        UNREACHABLE();
1116
    }
1117
    cursor++;
1118
  }
1119 1120 1121 1122 1123 1124 1125 1126 1127
}

template <typename Char>
JsonString JsonParser<Char>::ScanJsonString(bool needs_internalization) {
  DisallowHeapAllocation no_gc;
  int start = position();
  int offset = start;
  bool has_escape = false;
  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 1139 1140 1141 1142
    if (V8_UNLIKELY(is_at_end())) {
      AllowHeapAllocation allow_before_exception;
      ReportUnexpectedCharacter(kEndOfString);
      break;
    }
1143 1144

    if (*cursor_ == '"') {
1145
      int end = position();
1146
      advance();
1147 1148 1149 1150 1151
      int length = end - offset;
      bool convert = sizeof(Char) == 1 ? bits > unibrow::Latin1::kMaxChar
                                       : bits <= unibrow::Latin1::kMaxChar;
      return JsonString(start, length, convert, needs_internalization,
                        has_escape);
1152
    }
1153 1154

    if (*cursor_ == '\\') {
1155
      has_escape = true;
1156
      uc32 c = NextCharacter();
1157
      if (V8_UNLIKELY(!base::IsInRange(
1158
              c, 0, static_cast<int32_t>(unibrow::Latin1::kMaxChar)))) {
1159
        AllowHeapAllocation allow_before_exception;
1160
        ReportUnexpectedCharacter(c);
1161
        break;
1162
      }
1163

1164
      switch (GetEscapeKind(character_json_scan_flags[c])) {
1165 1166 1167 1168 1169 1170
        case EscapeKind::kSelf:
        case EscapeKind::kBackspace:
        case EscapeKind::kTab:
        case EscapeKind::kNewLine:
        case EscapeKind::kFormFeed:
        case EscapeKind::kCarriageReturn:
1171
          offset += 1;
1172 1173 1174
          break;

        case EscapeKind::kUnicode: {
1175 1176 1177 1178 1179
          uc32 value = ScanUnicodeCharacter();
          if (value == -1) {
            AllowHeapAllocation allow_before_exception;
            ReportUnexpectedCharacter(CurrentCharacter());
            return JsonString();
1180
          }
1181 1182 1183 1184 1185
          bits |= value;
          // \uXXXX results in either 1 or 2 Utf16 characters, depending on
          // whether the decoded value requires a surrogate pair.
          offset += 5 - (value > static_cast<uc32>(
                                     unibrow::Utf16::kMaxNonSurrogateCharCode));
1186 1187
          break;
        }
1188

1189
        case EscapeKind::kIllegal:
1190
          AllowHeapAllocation allow_before_exception;
1191
          ReportUnexpectedCharacter(c);
1192
          return JsonString();
1193
      }
1194

1195 1196 1197
      advance();
      continue;
    }
1198

1199
    DCHECK_LT(*cursor_, 0x20);
1200
    AllowHeapAllocation allow_before_exception;
1201
    ReportUnexpectedCharacter(*cursor_);
1202
    break;
1203 1204
  }

1205
  return JsonString();
1206 1207
}

1208
// Explicit instantiation.
1209 1210
template class JsonParser<uint8_t>;
template class JsonParser<uint16_t>;
1211 1212 1213

}  // namespace internal
}  // namespace v8