// Copyright 2011 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.
#ifndef V8_JSON_JSON_PARSER_H_
#define V8_JSON_JSON_PARSER_H_
#include <optional>
#include "include/v8-callbacks.h"
#include "src/base/bit-field.h"
#include "src/base/macros.h"
#include "src/base/small-vector.h"
#include "src/base/strings.h"
#include "src/codegen/script-details.h"
#include "src/common/high-allocation-throughput-scope.h"
#include "src/execution/isolate.h"
#include "src/heap/factory.h"
#include "src/objects/descriptor-array.h"
#include "src/objects/objects.h"
#include "src/objects/string.h"
#include "src/roots/roots.h"
namespace v8 {
namespace internal {
enum ParseElementResult { kElementFound, kElementNotFound };
class JsonString final {
public:
JsonString()
: start_(0),
length_(0),
needs_conversion_(false),
internalize_(false),
has_escape_(false),
is_index_(false) {}
explicit JsonString(uint32_t index)
: index_(index),
length_(0),
needs_conversion_(false),
internalize_(false),
has_escape_(false),
is_index_(true) {}
JsonString(uint32_t start, uint32_t length, bool needs_conversion,
bool internalize, bool has_escape)
: start_(start),
length_(length),
needs_conversion_(needs_conversion),
internalize_(internalize),
has_escape_(has_escape),
is_index_(false) {}
bool internalize() const {
DCHECK(!is_index_);
return internalize_;
}
bool needs_conversion() const {
DCHECK(!is_index_);
return needs_conversion_;
}
bool has_escape() const {
DCHECK(!is_index_);
return has_escape_;
}
uint32_t start() const {
DCHECK(!is_index_);
return start_;
}
uint32_t length() const {
DCHECK(!is_index_);
return length_;
}
uint32_t index() const {
DCHECK(is_index_);
return index_;
}
bool is_index() const { return is_index_; }
private:
union {
const uint32_t start_;
const uint32_t index_;
};
const uint32_t length_;
const bool needs_conversion_ : 1;
const bool internalize_ : 1;
const bool has_escape_ : 1;
const bool is_index_ : 1;
};
struct JsonProperty {
JsonProperty() { UNREACHABLE(); }
explicit JsonProperty(const JsonString& string) : string(string) {}
JsonProperty(const JsonString& string, Handle<Object> value)
: string(string), value(value) {}
JsonString string;
Handle<Object> value;
};
class JsonParseInternalizer {
public:
static MaybeHandle<Object> Internalize(Isolate* isolate,
DirectHandle<Object> result,
Handle<Object> reviver,
Handle<String> source,
MaybeHandle<Object> val_node,
bool pass_context_argument);
private:
JsonParseInternalizer(Isolate* isolate, Handle<JSReceiver> reviver,
Handle<String> source)
: isolate_(isolate), reviver_(reviver), source_(source) {}
enum ReviverMode {
kWithoutContext, // Two-arg reviver callback, no context argument.
kWithoutSource, // Three-arg reviver callback, context argument has no
// source property.
kWithSource, // Three-arg reviver callback, context object has source
// property.
};
static constexpr ReviverMode NoSource(ReviverMode old_mode) {
if (old_mode == kWithSource) return kWithoutSource;
return old_mode;
}
template <ReviverMode reviver_mode>
MaybeHandle<Object> InternalizeJsonProperty(DirectHandle<JSReceiver> holder,
DirectHandle<String> key,
MaybeHandle<Object> val_node,
DirectHandle<Object> snapshot);
template <ReviverMode reviver_mode>
bool RecurseAndApply(Handle<JSReceiver> holder, Handle<String> name,
Handle<Object> val_node, Handle<Object> snapshot);
Isolate* isolate_;
Handle<JSReceiver> reviver_;
Handle<String> source_;
};
enum class JsonToken : uint8_t {
NUMBER,
STRING,
LBRACE,
RBRACE,
LBRACK,
RBRACK,
TRUE_LITERAL,
FALSE_LITERAL,
NULL_LITERAL,
WHITESPACE,
COLON,
COMMA,
ILLEGAL,
EOS
};
template <JsonToken token, JsonToken... tokens>
concept JsonTokenIsOneOf = ((token == tokens) || ...);
template <JsonToken token>
concept JsonTokenIsCharacter =
JsonTokenIsOneOf<token, JsonToken::STRING, JsonToken::LBRACE,
JsonToken::RBRACE, JsonToken::LBRACK, JsonToken::RBRACK,
JsonToken::TRUE_LITERAL, JsonToken::FALSE_LITERAL,
JsonToken::NULL_LITERAL, JsonToken::COLON,
JsonToken::COMMA>;
constexpr uint8_t JsonTokenToCharacter(JsonToken token) {
switch (token) {
case JsonToken::STRING:
return '"';
case JsonToken::LBRACE:
return '{';
case JsonToken::RBRACE:
return '}';
case JsonToken::LBRACK:
return '[';
case JsonToken::RBRACK:
return ']';
case JsonToken::TRUE_LITERAL:
return 't';
case JsonToken::FALSE_LITERAL:
return 'f';
case JsonToken::NULL_LITERAL:
return 'n';
case JsonToken::COLON:
return ':';
case JsonToken::COMMA:
return ',';
default:
CONSTEXPR_UNREACHABLE();
}
}
// A json parser.
template <typename Char>
class JsonParser final {
public:
using SeqString = typename CharTraits<Char>::String;
using SeqExternalString = typename CharTraits<Char>::ExternalString;
V8_WARN_UNUSED_RESULT static bool CheckRawJson(Isolate* isolate,
Handle<String> source) {
return JsonParser(isolate, source, std::nullopt).ParseRawJson();
}
V8_WARN_UNUSED_RESULT static MaybeHandle<Object> Parse(
Isolate* isolate, Handle<String> source, Handle<Object> reviver,
std::optional<ScriptDetails> script_details);
static constexpr base::uc32 kEndOfString = static_cast<base::uc32>(-1);
static constexpr base::uc32 kInvalidUnicodeCharacter =
static_cast<base::uc32>(-1);
private:
class NamedPropertyIterator;
template <typename T>
using SmallVector = base::SmallVector<T, 16>;
struct JsonContinuation {
enum Type : uint8_t { kReturn, kObjectProperty, kArrayElement };
JsonContinuation(Isolate* isolate, Type type, size_t index)
: scope(isolate),
max_index(0),
elements(0),
fast_keys_matched(false),
type_and_index_(TypeField::encode(type) | IndexField::encode(index)) {
}
Type type() const { return TypeField::decode(type_and_index_); }
void set_type(Type type) {
type_and_index_ = TypeField::update(type_and_index_, type);
}
size_t index() const { return IndexField::decode(type_and_index_); }
HandleScope scope;
uint32_t max_index;
uint32_t elements;
// True if ParseJsonObjectProperties<FastIterableState::kJsonFast> matched
// all property keys against the feedback map in exact sequence with no
// trailing properties. Used by BuildJsonObject for direct layout
// allocation.
bool fast_keys_matched;
private:
using TypeField = base::BitField<Type, 0, 2>;
using IndexField = TypeField::template Next<size_t, 30>;
uint32_t type_and_index_;
};
JsonParser(Isolate* isolate, Handle<String> source,
std::optional<ScriptDetails> script_details);
~JsonParser();
// Parse a string containing a single JSON value. If
// collect_source_strings is true then we also build the data structures
// for the reviver callback. This includes both the source strings for
// primitive values, and also the val_nodes for non-primitive objects, used
// for detecting whether the user has changed the deserialized 'this'
// object that was implicitly passed to the reviver key-value callback.
MaybeHandle<Object> ParseJson(bool collect_source_strings);
bool ParseRawJson();
void advance() { ++cursor_; }
base::uc32 CurrentCharacter() const {
if (V8_UNLIKELY(is_at_end())) return kEndOfString;
return *cursor_;
}
base::uc32 NextCharacter() {
advance();
return CurrentCharacter();
}
void AdvanceToNonDecimal();
V8_INLINE JsonToken peek() const;
void Consume(JsonToken token) {
DCHECK_EQ(peek(), token);
advance();
}
template <JsonToken token>
V8_INLINE bool IsNextToken() {
if constexpr (token == JsonToken::EOS) {
return is_at_end();
} else if constexpr (JsonTokenIsCharacter<token>) {
constexpr Char expected_char = JsonTokenToCharacter(token);
return V8_LIKELY(expected_char == CurrentCharacter());
} else {
return false;
}
}
template <JsonToken token>
V8_WARN_UNUSED_RESULT bool Check() {
if (V8_LIKELY(IsNextToken<token>())) {
advance();
return true;
}
GetNextNonWhitespaceToken();
if (peek() == token) {
advance();
return true;
}
return false;
}
template <JsonToken token>
V8_WARN_UNUSED_RESULT bool Expect(
std::optional<MessageTemplate> errorMessage = std::nullopt) {
if (V8_LIKELY(peek() == token)) {
advance();
return true;
}
ReportUnexpectedToken(peek(), errorMessage);
return false;
}
template <JsonToken token>
V8_WARN_UNUSED_RESULT bool ExpectNext(
std::optional<MessageTemplate> errorMessage) {
if (Check<token>()) {
return true;
}
ReportUnexpectedToken(peek(), errorMessage);
return false;
}
template <size_t N>
void ScanLiteral(const char (&s)[N]) {
DCHECK(!is_at_end());
// There's at least 1 character, we always consume a character and compare
// the next character. The first character was compared before we jumped
// to ScanLiteral.
static_assert(N > 2);
size_t remaining = remaining_chars();
if (V8_LIKELY(remaining >= N - 1 &&
CompareCharsEqual(s + 1, cursor_ + 1, N - 2))) {
cursor_ += N - 1;
return;
}
cursor_++;
for (size_t i = 0; i < std::min(N - 2, remaining - 1); i++) {
if (*(s + 1 + i) != *cursor_) {
ReportUnexpectedCharacter(*cursor_);
return;
}
cursor_++;
}
DCHECK(is_at_end());
ReportUnexpectedToken(JsonToken::EOS);
}
// The JSON lexical grammar is specified in the ECMAScript 5 standard,
// section 15.12.1.1. The only allowed whitespace characters between tokens
// are tab, carriage-return, newline and space.
void GetNextNonWhitespaceToken();
// A JSON string (production JSONString) is subset of valid JavaScript string
// literals. The string must only be double-quoted (not single-quoted), and
// the only allowed backslash-escapes are ", /, \, b, f, n, r, t and
// four-digit hex escapes (uXXXX). Any other use of backslashes is invalid.
JsonString ScanJsonString(bool needs_internalization);
JsonString ScanJsonPropertyKey(JsonContinuation* cont);
base::uc32 ScanUnicodeCharacter();
base::Vector<const Char> GetKeyChars(JsonString key) {
// For escaped keys the source range starting at `key.start()` holds the raw
// (undecoded) characters while `key.length()` is the decoded length, so the
// bytes here do not represent the actual decoded key. Return an empty
// vector to signal that the byte-compare transition fast path must be
// skipped (see JSDataObjectBuilder::TryFastTransitionToPropertyKey).
if (key.has_escape()) return base::Vector<const Char>();
return base::Vector<const Char>(chars_ + key.start(), key.length());
}
Handle<String> MakeString(const JsonString& string,
Handle<String> hint = Handle<String>());
template <typename SinkChar>
void DecodeString(SinkChar* sink, uint32_t start, uint32_t length);
template <typename SinkSeqString>
Handle<String> DecodeString(const JsonString& string,
Handle<SinkSeqString> intermediate,
Handle<String> hint);
// A JSON number (production JSONNumber) is a subset of the valid JavaScript
// decimal number literals.
// It includes an optional minus sign, must have at least one
// digit before and after a decimal point, may not have prefixed zeros (unless
// the integer part is zero), and may include an exponent part (e.g., "e-10").
// Hexadecimal and octal numbers are not allowed.
Handle<Object> ParseJsonNumber();
// Parses a number either as a double or a Smi. Returns true if it was a
// double, false if it was a Smi.
bool ParseJsonNumberAsDoubleOrSmi(double* result_double, int* result_smi);
// Parse a single JSON value from input (grammar production JSONValue).
// A JSON value is either a (double-quoted) string literal, a number literal,
// one of "true", "false", or "null", or an object or array literal.
template <bool should_track_json_source>
MaybeHandle<Object> ParseJsonValue();
V8_INLINE MaybeHandle<Object> ParseJsonValueRecursive(
Handle<Map> feedback = {});
MaybeHandle<Object> ParseJsonArray();
MaybeHandle<Object> ParseJsonObject(Handle<Map> feedback);
template <DescriptorArray::FastIterableState fast_iterable_state>
V8_INLINE bool ParseJsonObjectProperties(JsonContinuation* cont,
MessageTemplate first_token_msg,
Handle<DescriptorArray> descriptors,
uint16_t nof_descriptors);
V8_INLINE bool ParseJsonPropertyValue(const JsonString& key);
V8_INLINE bool FastKeyMatch(const uint8_t* key_chars, uint32_t key_length);
V8_INLINE bool FastKeyMatch(const uint8_t* key_chars, uint32_t key_length,
JsonString scanned_key);
template <bool should_track_json_source>
Handle<JSObject> BuildJsonObject(const JsonContinuation& cont,
DirectHandle<Map> feedback);
Handle<Object> BuildJsonArray(size_t start);
static const int kMaxContextCharacters = 10;
static const int kMinOriginalSourceLengthForContext =
(kMaxContextCharacters * 2) + 1;
// Mark that a parsing error has happened at the current character.
void ReportUnexpectedCharacter(base::uc32 c);
bool IsSpecialString();
MessageTemplate GetErrorMessageWithEllipses(DirectHandle<Object>& arg,
DirectHandle<Object>& arg2,
int pos);
MessageTemplate LookUpErrorMessageForJsonToken(JsonToken token,
DirectHandle<Object>& arg,
DirectHandle<Object>& arg2,
int pos);
// Calculate line and column based on the current cursor position.
// Both values start at 1.
void CalculateFileLocation(DirectHandle<Object>& line,
DirectHandle<Object>& column);
// Mark that a parsing error has happened at the current token.
void ReportUnexpectedToken(
JsonToken token,
std::optional<MessageTemplate> errorMessage = std::nullopt);
inline Isolate* isolate() { return isolate_; }
inline Factory* factory() { return isolate_->factory(); }
inline ReadOnlyRoots roots() { return ReadOnlyRoots(isolate_); }
inline DirectHandle<JSFunction> object_constructor() {
return object_constructor_;
}
static const int kInitialSpecialStringLength = 32;
static void UpdatePointersCallback(void* parser) {
reinterpret_cast<JsonParser<Char>*>(parser)->UpdatePointers();
}
void UpdatePointers() {
DisallowGarbageCollection no_gc;
// Keeping the `GetChars()` result is safe because we update the pointer in
// the GCEpilogueCallback.
START_IGNORE_LIFETIME_SAFETY_WARNINGS();
const Char* chars = Cast<SeqString>(source_)->GetChars(no_gc);
END_IGNORE_LIFETIME_SAFETY_WARNINGS();
if (chars_ != chars) {
size_t position = cursor_ - chars_;
size_t length = end_ - chars_;
chars_ = chars;
cursor_ = chars_ + position;
end_ = chars_ + length;
}
}
private:
static const bool kIsOneByte = sizeof(Char) == 1;
bool is_at_end() const {
DCHECK_LE(cursor_, end_);
return cursor_ == end_;
}
size_t remaining_chars() const { return end_ - cursor_; }
uint32_t position() const { return static_cast<uint32_t>(cursor_ - chars_); }
Isolate* isolate_;
JsonToken next_;
// Indicates whether the bytes underneath source_ can relocate during GC.
bool chars_may_relocate_;
Handle<JSFunction> object_constructor_;
const Handle<String> original_source_;
Handle<String> source_;
// Script details for error reporting. When provided, error Script
// objects will use this information instead of inferring from the
// stack frame.
std::optional<ScriptDetails> script_details_;
// The parsed value's source to be passed to the reviver, if the reviver is
// callable.
MaybeHandle<Object> parsed_val_node_;
SmallVector<Handle<Object>> element_stack_;
SmallVector<JsonProperty> property_stack_;
SmallVector<double> double_elements_;
SmallVector<int> smi_elements_;
// Cached pointer to the raw chars in source. In case source is on-heap, we
// register an UpdatePointers callback. For this reason, chars_, cursor_ and
// end_ should never be locally cached across a possible allocation. The scope
// in which we cache chars has to be guarded by a DisallowGarbageCollection
// scope.
const Char* cursor_;
const Char* end_;
const Char* chars_;
// Remaining budget for heuristic internalization of non-key, short one-byte
// strings.
uint32_t remaining_heuristic_internalizations_;
};
// Explicit instantiation declarations.
extern template class JsonParser<uint8_t>;
extern template class JsonParser<uint16_t>;
} // namespace internal
} // namespace v8
#endif // V8_JSON_JSON_PARSER_H_