// 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/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),
          type_(type),
          index(static_cast<uint32_t>(index)),
          max_index(0),
          elements(0) {}

    Type type() const { return static_cast<Type>(type_); }
    void set_type(Type type) { type_ = static_cast<uint8_t>(type); }

    HandleScope scope;
    // Unfortunately GCC doesn't like packing Type in two bits.
    uint32_t type_ : 2;
    uint32_t index : 30;
    uint32_t max_index;
    uint32_t elements;
  };

  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) {
    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);
  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;
    const Char* chars = Cast<SeqString>(source_)->GetChars(no_gc);
    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_;
};

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