// 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.

#include "src/json/json-parser.h"

#include <optional>

#include "src/base/small-vector.h"

#include "src/base/strings.h"

#include "src/builtins/builtins.h"

#include "src/common/assert-scope.h"

#include "src/common/globals.h"

#include "src/common/message-template.h"

#include "src/debug/debug.h"

#include "src/execution/frames-inl.h"

#include "src/heap/factory.h"

#include "src/numbers/conversions.h"

#include "src/numbers/hash-seed-inl.h"

#include "src/objects/elements-kind.h"

#include "src/objects/field-type.h"

#include "src/objects/hash-table-inl.h"

#include "src/objects/heap-object.h"

#include "src/objects/map-updater.h"

#include "src/objects/objects-inl.h"

#include "src/objects/property-descriptor.h"

#include "src/objects/property-details.h"

#include "src/roots/roots.h"

#include "src/strings/char-predicates-inl.h"

#include "src/strings/string-hasher.h"

#include "src/utils/boxed-float.h"

namespace v8 {

namespace internal {

namespace {

constexpr JsonToken GetOneCharJsonToken(uint8_t c) {

// clang-format off

return

c == '"' ? JsonToken::STRING :

IsDecimalDigit(c) ? JsonToken::NUMBER :

c == '-' ? JsonToken::NUMBER :

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).

static const constexpr JsonToken one_char_json_tokens[256] = {

#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(N),

INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)

#undef CALL_GET_SCAN_FLAGS

#define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(128 + N),

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

};

using EscapeKindField = base::BitField8<EscapeKind, 0, 3>;

using MayTerminateStringField = EscapeKindField::Next<bool, 1>;

using NumberPartField = MayTerminateStringField::Next<bool, 1>;

constexpr bool MayTerminateJsonString(uint8_t flags) {

return MayTerminateStringField::decode(flags);

}

constexpr EscapeKind GetEscapeKind(uint8_t flags) {

return EscapeKindField::decode(flags);

}

constexpr bool IsNumberPart(uint8_t flags) {

return NumberPartField::decode(flags);

}

constexpr uint8_t GetJsonScanFlags(uint8_t c) {

// 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).

static const constexpr uint8_t character_json_scan_flags[256] = {

#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(N),

INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)

#undef CALL_GET_SCAN_FLAGS

#define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(128 + N),

INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)

#undef CALL_GET_SCAN_FLAGS

};

#define EXPECT_RETURN_ON_ERROR(token, msg, ret) \

if (V8_UNLIKELY(!Expect<token>(msg))) { \

return ret; \

}

#define EXPECT_NEXT_RETURN_ON_ERROR(token, msg, ret) \

if (V8_UNLIKELY(!ExpectNext<token>(msg))) { \

return ret; \

}

} // namespace

MaybeHandle<Object> JsonParseInternalizer::Internalize(

Isolate* isolate, DirectHandle<Object> result, Handle<Object> reviver,

Handle<String> source, MaybeHandle<Object> val_node,

bool pass_context_argument) {

DCHECK(IsCallable(*reviver));

JsonParseInternalizer internalizer(isolate, Cast<JSReceiver>(reviver),

source);

DirectHandle<JSObject> holder =

isolate->factory()->NewJSObject(isolate->object_function());

DirectHandle<String> name = isolate->factory()->empty_string();

JSObject::AddProperty(isolate, holder, name, result, NONE);

if (pass_context_argument) {

// Three-argument reviver, so we add a context argument to each

// callback to the reviver, and that context object will normally

// have a source property.

return internalizer.InternalizeJsonProperty<kWithSource>(holder, name,

val_node, result);

} else {

// Faster two-argument reviver.

return internalizer.InternalizeJsonProperty<kWithoutContext>(

holder, name, val_node, DirectHandle<Object>());

}

}

template <JsonParseInternalizer::ReviverMode initial_reviver_mode>

MaybeHandle<Object> JsonParseInternalizer::InternalizeJsonProperty(

DirectHandle<JSReceiver> holder, DirectHandle<String> name,

MaybeHandle<Object> val_node, DirectHandle<Object> snapshot) {

DCHECK_EQ(val_node.is_null(), snapshot.is_null());

DCHECK_NE(initial_reviver_mode == kWithSource, val_node.is_null());

DCHECK(IsCallable(*reviver_));

HandleScope outer_scope(isolate_);

Handle<Object> value;

ASSIGN_RETURN_ON_EXCEPTION(

isolate_, value, Object::GetPropertyOrElement(isolate_, holder, name));

// When reviver_mode == kWithSource, the source text is passed

// to the reviver if the reviver has not mucked with the originally parsed

// value.

ReviverMode reviver_mode;

if (initial_reviver_mode == kWithSource &&

!Object::SameValue(*value, *snapshot)) {

reviver_mode = NoSource(initial_reviver_mode);

} else {

reviver_mode = initial_reviver_mode;

}

if (IsJSReceiver(*value)) {

// Value is non-primitive, so we may have to recurse deeper.

Handle<JSReceiver> object = Cast<JSReceiver>(value);

Maybe<bool> is_array = Object::IsArray(object);

if (is_array.IsNothing()) return MaybeHandle<Object>();

if (is_array.FromJust()) {

DirectHandle<Object> length_object;

ASSIGN_RETURN_ON_EXCEPTION(

isolate_, length_object,

Object::GetLengthFromArrayLike(isolate_, object));

double length = Object::NumberValue(*length_object);

if (reviver_mode == kWithSource) {

auto val_nodes_and_snapshots =

Cast<FixedArray>(val_node.ToHandleChecked());

int snapshot_length = val_nodes_and_snapshots->length() / 2;

for (int i = 0; i < length; i++) {

HandleScope inner_scope(isolate_);

DirectHandle<Object> index = isolate_->factory()->NewNumber(i);

Handle<String> index_name =

isolate_->factory()->NumberToString(index);

// Even if the array pointer snapshot matched, it's possible the

// array had new elements added that are not in the snapshotted

// elements.

const bool rv =

i < snapshot_length

? RecurseAndApply<kWithSource>(

object, index_name,

handle(val_nodes_and_snapshots->get(i * 2), isolate_),

handle(val_nodes_and_snapshots->get(i * 2 + 1),

isolate_))

: RecurseAndApply<kWithoutSource>(

object, index_name, Handle<Object>(), Handle<Object>());

if (!rv) {

return MaybeHandle<Object>();

}

}

} else {

DCHECK(reviver_mode == kWithoutSource ||

reviver_mode == kWithoutContext);

for (int i = 0; i < length; i++) {

HandleScope inner_scope(isolate_);

DirectHandle<Object> index = isolate_->factory()->NewNumber(i);

Handle<String> index_name =

isolate_->factory()->NumberToString(index);

if (!RecurseAndApply<NoSource(initial_reviver_mode)>(

object, index_name, Handle<Object>(), Handle<Object>())) {

return MaybeHandle<Object>();

}

}

}

} else {

DCHECK(!is_array.FromJust()); // It's a non-primitive, non-array.

DirectHandle<FixedArray> contents;

ASSIGN_RETURN_ON_EXCEPTION(

isolate_, contents,

KeyAccumulator::GetKeys(isolate_, object, KeyCollectionMode::kOwnOnly,

ENUMERABLE_STRINGS,

GetKeysConversion::kConvertToString));

if (reviver_mode == kWithSource) {

auto val_nodes_and_snapshots =

Cast<ObjectTwoHashTable>(val_node.ToHandleChecked());

for (int i = 0; i < contents->length(); i++) {

HandleScope inner_scope(isolate_);

Handle<String> key_name(Cast<String>(contents->get(i)), isolate_);

auto property_val_node_and_snapshot =

val_nodes_and_snapshots->Lookup(isolate_, key_name);

Handle<Object> property_val_node(property_val_node_and_snapshot[0],

isolate_);

Handle<Object> property_snapshot(property_val_node_and_snapshot[1],

isolate_);

// Even if the object pointer snapshot matched, it's possible the

// object had new properties added that are not in the snapshotted

// contents.

const bool rv =

!IsTheHole(*property_snapshot)

? RecurseAndApply<kWithSource>(

object, key_name, property_val_node, property_snapshot)

: RecurseAndApply<kWithoutSource>(

object, key_name, Handle<Object>(), Handle<Object>());

if (!rv) {

return MaybeHandle<Object>();

}

}

} else {

DCHECK(reviver_mode == kWithoutSource ||

reviver_mode == kWithoutContext);

for (int i = 0; i < contents->length(); i++) {

HandleScope inner_scope(isolate_);

Handle<String> key_name(Cast<String>(contents->get(i)), isolate_);

if (!RecurseAndApply<NoSource(initial_reviver_mode)>(

object, key_name, Handle<Object>(), Handle<Object>())) {

return MaybeHandle<Object>();

}

}

}

}

}

// Done recursing.

if (reviver_mode == kWithoutContext) {

DirectHandle<Object> args[] = {name, value};

Handle<Object> result;

ASSIGN_RETURN_ON_EXCEPTION(

isolate_, result,

Execution::Call(isolate_, reviver_, holder, base::VectorOf(args)));

return outer_scope.CloseAndEscape(result);

}

DirectHandle<JSObject> context =

isolate_->factory()->NewJSObject(isolate_->object_function());

if (reviver_mode == kWithSource) {

auto val = val_node.ToHandleChecked();

if (IsString(*val)) {

JSReceiver::CreateDataProperty(isolate_, context,

isolate_->factory()->source_string(), val,

Just(kThrowOnError))

.Check();

}

}

DirectHandle<Object> args[] = {name, value, context};

Handle<Object> result;

ASSIGN_RETURN_ON_EXCEPTION(

isolate_, result,

Execution::Call(isolate_, reviver_, holder, base::VectorOf(args)));

return outer_scope.CloseAndEscape(result);

}

template <JsonParseInternalizer::ReviverMode reviver_mode>

bool JsonParseInternalizer::RecurseAndApply(Handle<JSReceiver> holder,

Handle<String> name,

Handle<Object> val_node,

Handle<Object> snapshot) {

STACK_CHECK(isolate_, false);

DCHECK(IsCallable(*reviver_));

DirectHandle<Object> result;

ASSIGN_RETURN_ON_EXCEPTION_VALUE(

isolate_, result,

InternalizeJsonProperty<reviver_mode>(holder, name, val_node, snapshot),

false);

Maybe<bool> change_result = Nothing<bool>();

if (IsUndefined(*result, isolate_)) {

change_result = JSReceiver::DeletePropertyOrElement(isolate_, holder, name,

LanguageMode::kSloppy);

} else {

PropertyDescriptor desc;

desc.set_value(Cast<JSAny>(result));

desc.set_configurable(true);

desc.set_enumerable(true);

desc.set_writable(true);

change_result = JSReceiver::DefineOwnProperty(isolate_, holder, name, &desc,

Just(kDontThrow));

}

MAYBE_RETURN(change_result, false);

return true;

}

template <typename Char>

JsonParser<Char>::JsonParser(Isolate* isolate, Handle<String> source,

std::optional<ScriptDetails> script_details)

: isolate_(isolate),

object_constructor_(isolate_->object_function()),

original_source_(source),

script_details_(script_details),

parsed_val_node_() {

size_t start = 0;

size_t length = source->length();

PtrComprCageBase cage_base(isolate);

if (IsSlicedString(*source, cage_base)) {

Tagged<SlicedString> string = Cast<SlicedString>(*source);

start = string->offset();

Tagged<String> parent = string->parent();

if (IsThinString(parent, cage_base))

parent = Cast<ThinString>(parent)->actual();

source_ = handle(parent, isolate);

} else {

source_ = String::Flatten(isolate, source);

}

if (StringShape(*source_).IsExternal()) {

chars_ =

static_cast<const Char*>(Cast<SeqExternalString>(*source_)->GetChars());

chars_may_relocate_ = false;

} else {

DisallowGarbageCollection no_gc;

isolate->main_thread_local_heap()->AddGCEpilogueCallback(

UpdatePointersCallback, this);

chars_ = Cast<SeqString>(*source_)->GetChars(no_gc);

chars_may_relocate_ = true;

}

cursor_ = chars_ + start;

end_ = cursor_ + length;

}

template <typename Char>

bool JsonParser<Char>::IsSpecialString() {

// The special cases are undefined, NaN, Infinity, and {} being passed to the

// parse method

int offset = IsSlicedString(*original_source_)

? Cast<SlicedString>(*original_source_)->offset()

: 0;

size_t length = original_source_->length();

#define CASES(V) \

V("[object Object]") \

V("undefined") \

V("Infinity") \

V("NaN")

switch (length) {

#define CASE(n) \

case arraysize(n) - 1: \

return CompareCharsEqual(chars_ + offset, n, arraysize(n) - 1);

CASES(CASE)

default:

return false;

}

#undef CASE

#undef CASES

}

template <typename Char>

MessageTemplate JsonParser<Char>::GetErrorMessageWithEllipses(

DirectHandle<Object>& arg, DirectHandle<Object>& arg2, int pos) {

MessageTemplate message;

Factory* factory = this->factory();

arg = factory->LookupSingleCharacterStringFromCode(*cursor_);

int origin_source_length = original_source_->length();

// Only provide context for strings with at least

// kMinOriginalSourceLengthForContext characters in length.

if (origin_source_length >= kMinOriginalSourceLengthForContext) {

int substring_start = 0;

int substring_end = origin_source_length;

if (pos < kMaxContextCharacters) {

message =

MessageTemplate::kJsonParseUnexpectedTokenStartStringWithContext;

// Output the string followed by ellipses.

substring_end = pos + kMaxContextCharacters;

} else if (pos >= kMaxContextCharacters &&

pos < origin_source_length - kMaxContextCharacters) {

message =

MessageTemplate::kJsonParseUnexpectedTokenSurroundStringWithContext;

// Add context before and after position of bad token surrounded by

// ellipses.

substring_start = pos - kMaxContextCharacters;

substring_end = pos + kMaxContextCharacters;

} else {

message = MessageTemplate::kJsonParseUnexpectedTokenEndStringWithContext;

// Add ellipses followed by some context before bad token.

substring_start = pos - kMaxContextCharacters;

}

arg2 =

factory->NewSubString(original_source_, substring_start, substring_end);

} else {

arg2 = original_source_;

// Output the entire string without ellipses but provide the token which

// was unexpected.

message = MessageTemplate::kJsonParseUnexpectedTokenShortString;

}

return message;

}

template <typename Char>

MessageTemplate JsonParser<Char>::LookUpErrorMessageForJsonToken(

JsonToken token, DirectHandle<Object>& arg, DirectHandle<Object>& arg2,

int pos) {

MessageTemplate message;

switch (token) {

case JsonToken::EOS:

message = MessageTemplate::kJsonParseUnexpectedEOS;

break;

case JsonToken::NUMBER:

message = MessageTemplate::kJsonParseUnexpectedTokenNumber;

break;

case JsonToken::STRING:

message = MessageTemplate::kJsonParseUnexpectedTokenString;

break;

default:

// Output entire string without ellipses and don't provide the token

// that was unexpected because it makes the error messages more confusing

if (IsSpecialString()) {

arg = original_source_;

message = MessageTemplate::kJsonParseShortString;

} else {

message = GetErrorMessageWithEllipses(arg, arg2, pos);

}

}

return message;

}

template <typename Char>

void JsonParser<Char>::CalculateFileLocation(DirectHandle<Object>& line,

DirectHandle<Object>& column) {

// JSON allows only \r and \n as line terminators.

// (See https://www.json.org/json-en.html - "whitespace")

int line_number = 1;

const Char* start =

chars_ + (IsSlicedString(*original_source_)

? Cast<SlicedString>(*original_source_)->offset()

: 0);

const Char* last_line_break = start;

const Char* cursor = start;

const Char* end = cursor_; // cursor_ points to the position of the error.

for (; cursor < end; ++cursor) {

if (*cursor == '\r' && cursor < end - 1 && cursor[1] == '\n') {

// \r\n counts as a single line terminator, as of

// https://tc39.es/ecma262/#sec-line-terminators. JSON itself does not

// have a notion of lines or line terminators.

++cursor;

}

if (*cursor == '\r' || *cursor == '\n') {

++line_number;

last_line_break = cursor + 1;

}

}

int column_number = 1 + static_cast<int>(cursor - last_line_break);

line = direct_handle(Smi::FromInt(line_number), isolate());

column = direct_handle(Smi::FromInt(column_number), isolate());

}

template <typename Char>

void JsonParser<Char>::ReportUnexpectedToken(

JsonToken token, std::optional<MessageTemplate> errorMessage) {

// Some exception (for example stack overflow) was already thrown.

if (isolate_->has_exception()) return;

// Parse failed. Current character is the unexpected token.

Factory* factory = this->factory();

int offset = IsSlicedString(*original_source_)

? Cast<SlicedString>(*original_source_)->offset()

: 0;

int pos = position() - offset;

DirectHandle<Object> arg(Smi::FromInt(pos), isolate());

DirectHandle<Object> arg2;

DirectHandle<Object> arg3;

CalculateFileLocation(arg2, arg3);

MessageTemplate message =

errorMessage ? errorMessage.value()

: LookUpErrorMessageForJsonToken(token, arg, arg2, pos);

Handle<Script> script(factory->NewScript(original_source_));

DCHECK_IMPLIES(isolate_->NeedsSourcePositions(), script->has_line_ends());

if (script_details_.has_value()) {

const ScriptDetails& details = script_details_.value();

script->set_origin_options(details.origin_options);

{

DisallowGarbageCollection no_gc;

SetScriptFieldsFromDetails(isolate_, *script, details, &no_gc);

}

} else {

DebuggableStackFrameIterator it(isolate_);

if (!it.done() && it.is_javascript()) {

FrameSummary summary = it.GetTopValidFrame();

script->set_eval_from_shared(summary.AsJavaScript().function()->shared());

if (IsScript(*summary.script())) {

script->set_origin_options(

Cast<Script>(*summary.script())->origin_options());

}

}

}

// We should sent compile error event because we compile JSON object in

// separated source file.

isolate()->debug()->OnCompileError(script);

MessageLocation location(script, pos, pos + 1);

isolate()->ThrowAt(factory->NewSyntaxError(message, arg, arg2, arg3),

&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(base::uc32 c) {

JsonToken token = JsonToken::ILLEGAL;

if (c == kEndOfString) {

token = JsonToken::EOS;

} else if (c <= unibrow::Latin1::kMaxChar) {

token = one_char_json_tokens[c];

}

return ReportUnexpectedToken(token);

}

template <typename Char>

JsonParser<Char>::~JsonParser() {

if (chars_may_relocate_) {

// Check that the string shape hasn't changed. Otherwise our GC hooks are

// broken.

Cast<SeqString>(*source_);

isolate()->main_thread_local_heap()->RemoveGCEpilogueCallback(

UpdatePointersCallback, this);

} else {

// Check that the string shape hasn't changed. Otherwise our GC hooks are

// broken.

Cast<SeqExternalString>(*source_);

}

}

template <typename Char>

MaybeHandle<Object> JsonParser<Char>::ParseJson(bool should_track_json_source) {

Handle<Object> result;

if (V8_UNLIKELY(should_track_json_source)) {

ASSIGN_RETURN_ON_EXCEPTION(isolate(), result, ParseJsonValue<true>());

} else {

ASSIGN_RETURN_ON_EXCEPTION(isolate(), result, ParseJsonValueRecursive());

}

EXPECT_NEXT_RETURN_ON_ERROR(

JsonToken::EOS,

MessageTemplate::kJsonParseUnexpectedNonWhiteSpaceCharacter, {});

if (isolate_->has_exception()) {

return MaybeHandle<Object>();

}

return result;

}

MaybeDirectHandle<Object> InternalizeJsonProperty(Handle<JSObject> holder,

Handle<String> key);

namespace {

template <typename Char>

JsonToken GetTokenForCharacter(Char c) {

return V8_LIKELY(c <= unibrow::Latin1::kMaxChar) ? one_char_json_tokens[c]

: JsonToken::ILLEGAL;

}

} // namespace

template <typename Char>

JsonToken JsonParser<Char>::peek() const {

// Check that the next token was scanned before using peek().

DCHECK_IMPLIES(!is_at_end(),

GetTokenForCharacter(CurrentCharacter()) == next_);

return next_;

}

template <typename Char>

void JsonParser<Char>::GetNextNonWhitespaceToken() {

JsonToken local_next = JsonToken::EOS;

cursor_ = std::find_if(cursor_, end_, [&](Char c) {

JsonToken current = GetTokenForCharacter(c);

bool result = current != JsonToken::WHITESPACE;

if (V8_LIKELY(result)) local_next = current;

return result;

});

next_ = local_next;

}

template <typename Char>

base::uc32 JsonParser<Char>::ScanUnicodeCharacter() {

base::uc32 value = 0;

for (int i = 0; i < 4; i++) {

int digit = base::HexValue(NextCharacter());

if (V8_UNLIKELY(digit < 0)) return kInvalidUnicodeCharacter;

value = value * 16 + digit;

}

return value;

}

// Parse any JSON value.

template <typename Char>

JsonString JsonParser<Char>::ScanJsonPropertyKey(JsonContinuation* cont) {

{

DisallowGarbageCollection no_gc;

const Char* start = cursor_;

base::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) {

return !IsDecimalDigit(c) || !TryAddArrayIndexChar(&index, c);

});

if (CurrentCharacter() == '"') {

advance();

// Record element information.

cont->elements++;

cont->max_index = std::max(cont->max_index, index);

return JsonString(index);

}

if (CurrentCharacter() == '\\' && NextCharacter() == 'u') {

base::uc32 c = ScanUnicodeCharacter();

if (IsDecimalDigit(c) && TryAddArrayIndexChar(&index, c)) continue;

}

break;

}

}

}

// Reset cursor_ to start if the key is not an index.

cursor_ = start;

}

return ScanJsonString(true);

}

class FoldedMutableHeapNumberAllocation {

public:

// TODO(leszeks): If allocation alignment is ever enabled, we'll need to add

// padding fillers between heap numbers.

static_assert(!USE_ALLOCATION_ALIGNMENT_HEAP_NUMBER_BOOL);

FoldedMutableHeapNumberAllocation(Isolate* isolate, int count) {

if (count == 0) return;

int size = count * sizeof(HeapNumber);

raw_bytes_ = isolate->factory()->NewByteArray(size);

}

Handle<ByteArray> raw_bytes() const { return raw_bytes_; }

private:

Handle<ByteArray> raw_bytes_ = {};

};

class FoldedMutableHeapNumberAllocator {

public:

FoldedMutableHeapNumberAllocator(

Isolate* isolate, FoldedMutableHeapNumberAllocation* allocation,

DisallowGarbageCollection& no_gc)

: isolate_(isolate), roots_(isolate) {

if (allocation->raw_bytes().is_null()) return;

raw_bytes_ = allocation->raw_bytes();

mutable_double_address_ =

reinterpret_cast<Address>(allocation->raw_bytes()->begin());

}

~FoldedMutableHeapNumberAllocator() {

// Make all mutable HeapNumbers alive.

if (mutable_double_address_ == 0) {

DCHECK(raw_bytes_.is_null());

return;

}

DCHECK_EQ(mutable_double_address_,

reinterpret_cast<Address>(raw_bytes_->end()));

// Before setting the length of mutable_double_buffer back to zero, we

// must ensure that the sweeper is not running or has already swept the

// object's page. Otherwise the GC can add the contents of

// mutable_double_buffer to the free list.

isolate_->heap()->EnsureSweepingCompletedForObject(*raw_bytes_);

raw_bytes_->set_length(0);

}

Tagged<HeapNumber> AllocateNext(ReadOnlyRoots roots, Float64 value) {

DCHECK_GE(mutable_double_address_,

reinterpret_cast<Address>(raw_bytes_->begin()));

Tagged<HeapObject> hn = HeapObject::FromAddress(mutable_double_address_);

hn->set_map_after_allocation(isolate_, roots.heap_number_map());

Cast<HeapNumber>(hn)->set_value_as_bits(value.get_bits());

mutable_double_address_ +=

ALIGN_TO_ALLOCATION_ALIGNMENT(sizeof(HeapNumber));

DCHECK_LE(mutable_double_address_,

reinterpret_cast<Address>(raw_bytes_->end()));

return Cast<HeapNumber>(hn);

}

private:

Isolate* isolate_;

ReadOnlyRoots roots_;

Handle<ByteArray> raw_bytes_ = {};

Address mutable_double_address_ = 0;

};

// JSDataObjectBuilder is a helper for efficiently building a data object,

// similar (in semantics and efficiency) to a JS object literal, based on

// key/value pairs.

//

// The JSDataObjectBuilder works by first trying to find the right map for the

// object, and then letting the caller stamp out the object fields linearly.

// There are several fast paths that can be fallen out of; if the builder bails

// out, then it's still possible to stamp out the object partially based on the

// last map found, and then continue with slow object setup afterward.

//

// The maps start from the object literal cache (to try to share maps with

// equivalent object literals in JS code). From there, when adding properties,

// there are several fast paths that the builder follows:

//

// 1. At construction, it can be passed an expected final map for the object

// (e.g. cached from previous runs, or assumed from surrounding objects).

// If given, then we first check whether the property matches the

// entry in the DescriptorArray of the final map; if yes, then we don't

// need to do any map transitions.

// 2. When given a property key, it looks for whether there is exactly one

// transition away from the current map ("ExpectedTransition").

// The expected key is passed as a hint to the current property key

// getter, for e.g. faster internalized string materialization.

// 3. Otherwise, it searches for whether there is any transition in the

// current map that matches the key.

// 4. For all of the above, it checks whether the field representation of the

// found map matches the representation of the value. If it doesn't, it

// migrates the map, potentially deprecating it too.

// 5. If there is no transition, it tries to allocate a new map transition,

// bailing out if this fails.

class JSDataObjectBuilder {

public:

// HeapNumberMode determines whether incoming HeapNumber values will be

// guaranteed to be uniquely owned by this object, and therefore can be used

// directly as mutable HeapNumbers for double representation fields.

enum HeapNumberMode {

kNormalHeapNumbers,

kHeapNumbersGuaranteedUniquelyOwned

};

JSDataObjectBuilder(Isolate* isolate, ElementsKind elements_kind,

int expected_named_properties,

DirectHandle<Map> expected_final_map,

HeapNumberMode heap_number_mode)

: isolate_(isolate),

elements_kind_(elements_kind),

expected_property_count_(expected_named_properties),

heap_number_mode_(heap_number_mode),

expected_final_map_(expected_final_map) {

if (!TryInitializeMapFromExpectedFinalMap()) {

InitializeMapFromZero();

}

}

// Builds and returns an object whose properties are based on a property

// iterator.

//

// Expects an iterator of the form:

//

// struct Iterator {

// void Advance();

// bool Done();

//

// // Get the key of the current property, optionally returning the hinted

// // expected key if applicable.

// Handle<String> GetKey(Handle<String> expected_key_hint);

//

// // Get the value of the current property. `will_revisit_value` is true

// // if this value will need to be revisited later via RevisitValues().

// Handle<Object> GetValue(bool will_revisit_value);

//

// // Return an iterator over the values that were already visited by

// // GetValue. Might require caching those values if necessary.

// ValueIterator RevisitValues();

// }

template <typename PropertyIterator>

Handle<JSObject> BuildFromIterator(

PropertyIterator&& it, MaybeHandle<FixedArrayBase> maybe_elements = {}) {

Handle<String> failed_property_add_key;

for (; !it.Done(); it.Advance()) {

Handle<String> property_key;

if (!TryAddFastPropertyForValue(

it.GetKeyChars(),

[&](Handle<String> expected_key) {

return property_key = it.GetKey(expected_key);

},

[&]() { return it.GetValue(true); })) {

failed_property_add_key = property_key;

break;

}

}

DirectHandle<FixedArrayBase> elements;

if (!maybe_elements.ToHandle(&elements)) {

elements = isolate_->factory()->empty_fixed_array();

}

CreateAndInitialiseObject(it.RevisitValues(), elements);

// Slow path: define remaining named properties.

for (; !it.Done(); it.Advance()) {

DirectHandle<String> key;

if (!failed_property_add_key.is_null()) {

key = std::exchange(failed_property_add_key, {});

} else {

key = it.GetKey({});

}

#ifdef DEBUG

uint32_t index;

DCHECK(!key->AsArrayIndex(&index));

#endif

Handle<Object> value = it.GetValue(false);

AddSlowProperty(key, value);

}

return object();

}

template <typename Char, typename GetKeyFunction, typename GetValueFunction>

V8_INLINE bool TryAddFastPropertyForValue(base::Vector<const Char> key_chars,

GetKeyFunction&& get_key,

GetValueFunction&& get_value) {

// The fast path is only valid as long as we haven't allocated an object

// yet.

DCHECK(object_.is_null());

Handle<String> key;

bool existing_map_found =

TryFastTransitionToPropertyKey(key_chars, get_key, &key);

// Unconditionally get the value after getting the transition result.

DirectHandle<Object> value = get_value();

if (existing_map_found) {

// We found a map with a field for our value -- now make sure that field

// is compatible with our value.

if (!TryGeneralizeFieldToValue(value)) {

// TODO(leszeks): Try to stay on the fast path if we just deprecate

// here.

return false;

}

AdvanceToNextProperty();

return true;

}

// Try to stay on a semi-fast path (being able to stamp out the object

// fields after creating the correct map) by manually creating the next

// map here.

Tagged<DescriptorArray> descriptors = map_->instance_descriptors(isolate_);

InternalIndex descriptor_number =

descriptors->SearchWithCache(isolate_, *key, *map_);

if (descriptor_number.is_found()) {

// Duplicate property, we need to bail out of even the semi-fast path

// because we can no longer stamp out values linearly.

return false;

}

if (!TransitionsAccessor::CanHaveMoreTransitions(isolate_, map_)) {

return false;

}

Representation representation =

Object::OptimalRepresentation(*value, isolate_);

DirectHandle<FieldType> type =

Object::OptimalType(*value, isolate_, representation);

MaybeHandle<Map> maybe_map = Map::CopyWithField(

isolate_, map_, key, type, NONE, PropertyConstness::kConst,

representation, INSERT_TRANSITION);

Handle<Map> next_map;

if (!maybe_map.ToHandle(&next_map)) return false;

if (next_map->is_dictionary_map()) return false;

map_ = next_map;

if (representation.IsDouble()) {

RegisterFieldNeedsFreshHeapNumber(value);

}

AdvanceToNextProperty();

return true;

}

template <typename ValueIterator>

V8_INLINE void CreateAndInitialiseObject(

ValueIterator value_it, DirectHandle<FixedArrayBase> elements) {

// We've created a map for the first `i` property stack values (which might

// be all of them). We need to write these properties to a newly allocated

// object.

DCHECK(object_.is_null());

if (current_property_index_ < property_count_in_expected_final_map_) {

// If we were on the expected map fast path all the way, but never reached

// the expected final map itself, then finalize the map by rewinding to

// the one whose property is the actual current property index.

//

// TODO(leszeks): Do we actually want to use the final map fast path when

// we know that the current map _can't_ reach the final map? Will we even

// hit this case given that we check for matching instance size?

RewindExpectedFinalMapFastPathToBeforeCurrent();

}

if (map_->is_dictionary_map()) {

// It's only safe to emit a dictionary map when we've not set up any

// properties, as the caller assumes it can set up the first N properties

// as fast data properties.

DCHECK_EQ(current_property_index_, 0);

Handle<JSObject> object = isolate_->factory()->NewSlowJSObjectFromMap(

map_, expected_property_count_);

object->set_elements(*elements);

object_ = object;

return;

}

// The map should have as many own descriptors as the number of properties

// we've created so far...

DCHECK_EQ(current_property_index_, map_->NumberOfOwnDescriptors());

// ... and all of those properties should be in-object data properties.

DCHECK_EQ(current_property_index_,

map_->GetInObjectProperties() - map_->UnusedInObjectProperties());

// Create a folded mutable HeapNumber allocation area before allocating the

// object -- this ensures that there is no allocation between the object

// allocation and its initial fields being initialised, where the verifier

// would see invalid double field state.

FoldedMutableHeapNumberAllocation hn_allocation(isolate_,

extra_heap_numbers_needed_);

// Allocate the object then immediately start a no_gc scope -- again, this

// is so the verifier doesn't see invalid double field state.

Handle<JSObject> object = isolate_->factory()->NewJSObjectFromMap(

map_, AllocationType::kYoung, DirectHandle<AllocationSite>::null(),

NewJSObjectType::kNoEmbedderFieldsAndNoApiWrapper);

DisallowGarbageCollection no_gc;

Tagged<JSObject> raw_object = *object;

raw_object->set_elements(*elements);

Tagged<DescriptorArray> descriptors =

raw_object->map()->instance_descriptors();

FoldedMutableHeapNumberAllocator hn_allocator(isolate_, &hn_allocation,