src/json_parser.cc

// Copyright 2025 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "json_parser.h"

#include <errno.h>
#include <stdint.h>
#include <stdlib.h>

#include "json.h"

namespace {

int ParseHexDigit(char ch) {
  if (ch >= '0' && ch <= '9')
    return (ch - '0');
  if (ch >= 'A' && ch <= 'F')
    return 10 + (ch - 'A');
  if (ch >= 'a' && ch <= 'f')
    return 10 + (ch - 'a');
  return -1;
}

bool ParseHex4(const char* p, uint32_t* value) {
  int v = (ParseHexDigit(p[0]) << 12) | (ParseHexDigit(p[1]) << 8) |
          (ParseHexDigit(p[2]) << 4) | ParseHexDigit(p[3]);
  if (v < 0)
    return false;

  *value = static_cast<uint32_t>(v);
  return true;
}

bool IsUnicodeSurrogatePairStart(uint32_t cp) {
  return ((cp & 0xfc00) == 0xd800);
}

bool IsUnicodeSurrogatePairEnd(uint32_t cp) {
  return ((cp & 0xfc00) == 0xdc00);
}

// Result for ParseJsonEscape function. On failure, error will be true.
// Otherwise |len| will be the length of the escape sequence in chars,
// |single_char| will be non-0 for single-char escapes, or
// |unicode_cp| will be the unicode codepoint for unicode escapes.
struct JsonEscapeInfo {
  bool error = false;
  char len = 0;
  char single_char = '\0';
  uint32_t unicode_cp = 0;
};

JsonEscapeInfo ParseJsonEscape(const char* p, const char* limit) {
  JsonEscapeInfo info = { true };  // error set by default.

  if (p + 1 >= limit)  // trailing escape.
    return info;

  char single = '\0';
  switch (p[1]) {
  case 'b':
    single = '\b';
    break;
  case 'f':
    single = '\f';
    break;
  case 'n':
    single = '\n';
    break;
  case 'r':
    single = '\r';
    break;
  case 't':
    single = '\t';
    break;
  case '"':
    single = '"';
    break;
  case '\\':
    single = '\\';
    break;
  case 'u': {
    // Handle unicode quoting.
    uint32_t cp = 0;
    if (p + 6 > limit || !ParseHex4(p + 2, &cp) ||
        IsUnicodeSurrogatePairEnd(cp))
      return info;
    p += 6;
    info.len = 6;
    if (IsUnicodeSurrogatePairStart(cp)) {
      // Surrogate pair start must be followed by escape with surrogate pair
      // end.
      uint32_t cp2;
      if (p + 6 > limit || p[0] != '\\' || p[1] != 'u' ||
          !ParseHex4(p + 2, &cp2) || !IsUnicodeSurrogatePairEnd(cp2)) {
        return info;
      }
      cp = 0x100000 + ((static_cast<uint32_t>(cp) & 0x3ff) | (cp2 & 0x3ff));
      info.len = 12;
    }
    info.unicode_cp = cp;
    info.error = false;
    return info;
  }
  default:
    // Unsupported escape.
    return info;
  }
  // Fallback for single-char escapes.
  info.len = 2;
  info.single_char = single;
  info.error = false;
  return info;
}

}  // namespace

namespace {

static bool IsDecimal(char ch) {
  return (ch >= '0' && ch <= '9');  // std:digit() is locale-dependent and slow.
}

static bool IsJsonWhitespace(char ch) {
  return (ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n');
};

bool SetMissingKeyError(JsonParser& parser, StringPiece key) {
  return parser.SetErrorFormat("Missing required key '%.*s'",
                               static_cast<int>(key.size()), key.begin());
}

}  // namespace

JsonParser::JsonParser(StringPiece input)
    : p_(input.begin()), end_(input.end()) {}

void JsonParser::Reset(StringPiece input) {
  p_ = input.begin();
  end_ = input.end();
  token_type_ = kNone;
  token_ = {};
  error_.clear();
}

JsonParser::TokenType JsonParser::PeekTokenType() {
  EnsureToken();
  return token_type_;
}

bool JsonParser::SetError(std::string error) {
  error_ = std::move(error);
  token_type_ = kParsingError;
  return false;
}

bool JsonParser::SetErrorFormat(const char* fmt, ...) {
  va_list args;
  va_start(args, fmt);
  SetError(StringFormat(fmt, args));
  va_end(args);
  return false;
}

bool JsonParser::SetExpectedError(const char* expected) {
  return SetErrorFormat("expected %s, got %s", expected,
                        ToString(token_type_).c_str());
}

StringPiece JsonParser::PeekToken() {
  EnsureToken();
  return token_;
}

void JsonParser::SkipToken() {
  if (token_type_ == kNone)
    ParseToken();
  token_type_ = kNone;
  // The next PeekToken() will parse the next token.
}

std::string JsonParser::ToString(JsonParser::TokenType type) {
  StringPiece result;
  switch (type) {
  case kNone:
    result = "NONE";
    break;
  case kEndOfInput:
    result = "END_OF_INPUT";
    break;
  case kParsingError:
    result = "PARSING_ERROR";
    break;
  case kObjectStart:
    result = "OBJECT_START";
    break;
  case kObjectEnd:
    result = "OBJECT_END";
    break;
  case kArrayStart:
    result = "ARRAY_START";
    break;
  case kArrayEnd:
    result = "ARRAY_END";
    break;
  case kComma:
    result = "COMMA";
    break;
  case kColon:
    result = "COLON";
    break;
  case kString:
    result = "STRING";
    break;
  case kTrue:
    result = "TRUE";
    break;
  case kFalse:
    result = "FALSE";
    break;
  case kNull:
    result = "NULL";
    break;
  case kNumber:
    result = "NUMBER";
    break;
  default:
    return StringFormat("UNKNOWN(%d)", type);
  }
  return result.AsString();
}

// Return true if the next token matches the start of a JSON value.
bool JsonParser::PeekValueStart() {
  EnsureToken();
  switch (token_type_) {
  case kEndOfInput:
  case kParsingError:
  case kArrayEnd:
  case kObjectEnd:
    return false;
  default:
    return true;
  }
}

bool JsonParser::ExpectValueStartNoSkip() {
  if (!PeekValueStart()) {
    error_ = "expected JSON value";
    return false;
  }
  return true;
}

bool JsonParser::ExpectNumber(StringPiece* str_value) {
  EnsureToken();
  if (token_type_ != kNumber) {
    return SetExpectedError("number");
  }
  *str_value = token_;
  SkipToken();
  return true;
}

bool JsonParser::ExpectInteger(int64_t* int_value) {
  StringPiece number;
  if (!ExpectNumber(&number))
    return false;

  std::string number_str = number.AsString();
  errno = 0;
  char* end = nullptr;
  int64_t value = strtoll(number_str.c_str(), &end, 10);
  if (errno != 0 || end != &number_str.back() + 1) {
    error_ = StringFormat("Number is not an integer: %s", number_str.c_str());
    return false;
  }
  *int_value = value;
  return true;
}

bool JsonParser::ExpectDouble(double* float_value) {
  StringPiece number;
  if (!ExpectNumber(&number))
    return false;

  std::string number_str = number.AsString();
  errno = 0;
  char* end = nullptr;
  double value = strtod(number_str.c_str(), &end);
  if (errno != 0 || end != &number_str.back() + 1) {
    error_ =
        StringFormat("Number is not floating point: %s", number_str.c_str());
    return false;
  }
  *float_value = value;
  return true;
}

bool JsonParser::ExpectBoolean(bool* flag_value) {
  EnsureToken();
  if (token_type_ == kTrue || token_type_ == kFalse) {
    *flag_value = (token_type_ == kTrue);
    SkipToken();
    return true;
  }
  return SetExpectedError("boolean");
}

bool JsonParser::SkipOptionalArrayEnd() {
  if (PeekTokenType() != kArrayEnd)
    return false;
  SkipToken();
  return true;
}

bool JsonParser::CheckOptionalArrayComma() {
  EnsureToken();
  if (token_type_ == kComma) {
    SkipToken();
    return true;
  } else if (token_type_ == kArrayEnd) {
    return true;
  }
  return SetExpectedError("comma or array end");
}

bool JsonParser::SkipOptionalObjectEnd() {
  if (PeekTokenType() != kObjectEnd)
    return false;

  SkipToken();
  return true;
}

bool JsonParser::CheckOptionalObjectComma() {
  EnsureToken();
  if (token_type_ == kComma) {
    SkipToken();
    return true;
  } else if (token_type_ == kObjectEnd) {
    return true;
  }
  return SetExpectedError("comma or object end");
}

bool JsonParser::ExpectEncodedString(StringPiece* encoded_str) {
  EnsureToken();
  if (token_type_ != kString) {
    return SetExpectedError("string");
  }
  *encoded_str = token_;
  SkipToken();
  return true;
}

bool JsonParser::ExpectString(std::string* str) {
  StringPiece encoded;
  if (!ExpectEncodedString(&encoded))
    return false;
  *str = JsonParser::DecodeString(encoded);
  return true;
}

bool JsonParser::ExpectStringList(std::vector<std::string>* str_list) {
  str_list->clear();
  JsonParser::ArrayIterator it(*this);
  while (it.HasItem()) {
    StringPiece encoded;
    if (!ExpectEncodedString(&encoded)) {
      break;
    }
    str_list->push_back(JsonParser::DecodeString(encoded));
  }
  return IsOk();
}

bool JsonParser::ParseJsonValue(JsonParser::ValueInfo* info) {
  EnsureToken();
  switch (token_type_) {
  case kEndOfInput:
    return SetExpectedError("JSON value");
  case kParsingError:
    error_ = "malformed JSON input";
    return false;
  case kArrayStart: {
    const char* start = token_.str_;
    SkipToken();
    while (!SkipOptionalArrayEnd()) {
      if (PeekTokenType() == kArrayEnd)
        break;
      if (!SkipJsonValue())
        return false;
      if (!CheckOptionalArrayComma())
        return false;
    }
    if (info) {
      info->type = kArrayStart;
      info->value = StringPiece(start, p_ - start);
    }
    return true;
  }
  case kObjectStart: {
    const char* start = token_.str_;
    SkipToken();
    while (!SkipOptionalObjectEnd()) {
      if (PeekTokenType() == kObjectEnd)
        break;
      StringPiece key;
      if (!ExpectObjectKeyAndColon(&key))
        return false;
      if (!SkipJsonValue())
        return false;
      if (!CheckOptionalObjectComma())
        return false;
    }
    if (info) {
      info->type = kObjectStart;
      info->value = StringPiece(start, p_ - start);
    }
    return true;
  }
  case kString:
  case kTrue:
  case kFalse:
  case kNumber:
  case kNull:
    if (info) {
      info->type = token_type_;
      info->value = token_;
    }
    SkipToken();
    return true;
  default:
    // Anything else is an unexpected token for a value.
    return SetExpectedError("JSON value");
  }
}

bool JsonParser::SkipJsonValue() {
  return ParseJsonValue(nullptr);
}

JsonParser::ArrayIterator::ArrayIterator(JsonParser& parser) : parser_(parser) {
  parser_.ExpectArrayStart();
}

bool JsonParser::ArrayIterator::HasItem() {
  if (parser_.HasError())
    return false;
  TokenType token = parser_.PeekTokenType();
  if (token == kArrayEnd) {
    parser_.SkipToken();
    return false;
  }
  if (expect_comma_ && !parser_.ExpectComma()) {
    return false;
  }
  expect_comma_ = true;
  if (!parser_.ExpectValueStartNoSkip()) {
    return false;
  }
  return true;
}

JsonParser::ObjectIterator::ObjectIterator(JsonParser& parser)
    : parser_(parser) {
  parser_.ExpectObjectStart();
}

bool JsonParser::ObjectIterator::HasKeyValue() {
  if (parser_.HasError())
    return false;

  TokenType token = parser_.PeekTokenType();
  if (token == kObjectEnd) {
    parser_.SkipToken();
    return false;
  }
  if (expect_comma_ && !parser_.ExpectComma()) {
    return false;
  }
  expect_comma_ = true;
  if (!parser_.ExpectObjectKeyAndColon(&key_)) {
    return false;
  }
  return true;
}

bool JsonParser::ExpectTokenType(TokenType token_type, const char* error_msg) {
  EnsureToken();
  if (token_type_ != token_type) {
    error_ = error_msg;
    return false;
  }
  SkipToken();
  return true;
}

bool JsonParser::IsJsonNumber(const char* start, const char* limit,
                              const char** end_ptr) {
  const char* p = start;
  // Required 0, or [1-9][0-9]*
  if (p >= limit || !IsDecimal(p[0]))
    return false;
  p++;
  if (p[-1] != '0') {
    while (p <= limit && IsDecimal(p[0]))
      p++;
  }
  // Optional dot followed by [0-9]+
  if (p + 2 < limit && p[0] == '.' && IsDecimal(p[1])) {
    p += 2;
    while (p < limit && IsDecimal(p[0]))
      p++;
  }
  // Optional [eE][+-]?[0-9]+
  if (p < limit && (p[0] == 'e' || p[0] == 'E')) {
    const char* q = p + 1;
    if (q < limit && (q[0] == '+' || q[0] == '-'))
      q++;
    if (q < limit && IsDecimal(q[0])) {
      p = q + 1;
      while (p < limit && IsDecimal(p[0]))
        p++;
    }
  }
  *end_ptr = p;
  return true;
}

void JsonParser::ParseToken() {
  token_ = StringPiece(p_, 0);
  if (HasError()) {
    token_type_ = kParsingError;
    return;
  }
  // Skip whitespace.
  while (p_ < end_ && IsJsonWhitespace(*p_))
    p_++;
  if (p_ == end_) {
    token_type_ = kEndOfInput;
    return;
  }
  switch (*p_) {
  case '{':
    token_type_ = kObjectStart;
    break;
  case '}':
    token_type_ = kObjectEnd;
    break;
  case '[':
    token_type_ = kArrayStart;
    break;
  case ']':
    token_type_ = kArrayEnd;
    break;
  case ',':
    token_type_ = kComma;
    break;
  case ':':
    token_type_ = kColon;
    break;
  case '"': {
    JsonInputStringInfo info = ParseJsonInputString(p_, end_);
    if (info.error)
      goto MALFORMED_INPUT;
    token_type_ = kString;
    token_ = StringPiece(info.start, info.end - info.start);
    p_ = info.end + 1;  // Skip over closing quote.
    return;
  }
  case 'f':
    if (p_ + 5 > end_ || memcmp(p_ + 1, "alse", 4) != 0)
      goto MALFORMED_INPUT;
    token_type_ = kFalse;
    token_ = StringPiece(p_, 5u);
    p_ += 5;
    return;
  case 't':
    if (p_ + 4 > end_ || memcmp(p_ + 1, "rue", 3) != 0)
      goto MALFORMED_INPUT;
    token_type_ = kTrue;
    token_ = StringPiece(p_, 4u);
    p_ += 4;
    return;
  case 'n':
    if (p_ + 4 > end_ || memcmp(p_ + 1, "ull", 3) != 0)
      goto MALFORMED_INPUT;
    token_type_ = kNull;
    token_ = StringPiece(p_, 4u);
    p_ += 4;
    return;
  default:
    const char* number_end = nullptr;
    if (!IsJsonNumber(p_, end_, &number_end))
      goto MALFORMED_INPUT;
    token_type_ = kNumber;
    token_ = StringPiece(p_, number_end - p_);
    p_ = number_end;
    return;
  }
  // Common code for single character tokens.
  token_ = StringPiece(p_, 1);
  p_ += 1;
  return;

MALFORMED_INPUT:
  token_type_ = kParsingError;
  token_ = StringPiece();
  error_ = "malformed input";
  return;
}

bool JsonParser::KeyValueMap::Get(StringPiece key,
                                  JsonParser::ValueInfo* vi) const {
  auto it = this->find(key);
  if (it == end())
    return false;
  *vi = it->second;
  return true;
}

bool JsonParser::KeyValueMap::GetRequired(StringPiece key,
                                          JsonParser::ValueInfo* vi,
                                          JsonParser& parser) const {
  if (Get(key, vi))
    return true;
  return SetMissingKeyError(parser, key);
}

bool JsonParser::KeyValueMap::GetRequiredExpected(StringPiece key,
                                                  TokenType expected_type,
                                                  JsonParser::ValueInfo* vi,
                                                  JsonParser& parser) const {
  if (!Get(key, vi))
    return SetMissingKeyError(parser, key);
  if (vi->type != expected_type) {
    return parser.SetErrorFormat("Invalid type for key '%.*s', expected %s",
                                 static_cast<int>(key.size()), key.begin(),
                                 parser.ToString(expected_type).c_str());
  }
  return true;
}

bool JsonParser::KeyValueMap::GetOptionalTyped(StringPiece key,
                                               TokenType expected_type,
                                               StringPiece* value,
                                               JsonParser& parser) const {
  JsonParser::ValueInfo vi;
  if (!Get(key, &vi)) {
    *value = {};
  } else if (vi.type == expected_type) {
    *value = vi.value;
  } else {
    return parser.SetErrorFormat("Invalid type for key '%.*s', expected %s",
                                 static_cast<int>(key.size()), key.begin(),
                                 parser.ToString(expected_type).c_str());
  }
  return true;
}

bool JsonParser::KeyValueMap::GetRequiredInteger(StringPiece key,
                                                 int64_t* value,
                                                 JsonParser& parser) const {
  JsonParser::ValueInfo vi;
  if (!GetRequiredExpected(key, JsonParser::kNumber, &vi, parser))
    return false;
  std::string number = vi.value.AsString();
  char* end = nullptr;
  errno = 0;
  long long v = strtoll(number.c_str(), &end, 10);
  if (end != &number.back() + 1) {
    return parser.SetErrorFormat("Integer number expected, got '%s'",
                                 number.c_str());
  }
  if (errno == ERANGE)
    return parser.SetErrorFormat("Integer number is too large: '%s'",
                                 number.c_str());
  *value = static_cast<int64_t>(v);
  return true;
}

bool JsonParser::KeyValueMap::GetRequiredString(StringPiece key,
                                                std::string* value,
                                                JsonParser& parser) const {
  JsonParser::ValueInfo vi;
  if (!GetRequiredExpected(key, JsonParser::kString, &vi, parser))
    return false;
  *value = JsonParser::DecodeString(vi.value);
  return true;
}

bool JsonParser::KeyValueMap::GetRequiredStringList(
    StringPiece key, std::vector<std::string>* value,
    JsonParser& parser) const {
  value->clear();
  JsonParser::ValueInfo vi;
  if (!GetRequiredExpected(key, JsonParser::kArrayStart, &vi, parser))
    return false;
  JsonParser list_parser(vi.value);
  JsonParser::ArrayIterator it(list_parser);
  while (it.HasItem()) {
    StringPiece encoded;
    if (!list_parser.ExpectEncodedString(&encoded)) {
      break;
    }
    value->push_back(JsonParser::DecodeString(encoded));
  }
  if (list_parser.HasError())
    return parser.SetError(list_parser.TakeError());

  return true;
}

bool JsonParser::KeyValueMap::GetOptionalOrEmptyString(
    StringPiece key, std::string* value, JsonParser& parser) const {
  StringPiece encoded_value;
  if (!GetOptionalTyped(key, JsonParser::kString, &encoded_value, parser))
    return false;
  if (encoded_value.empty()) {
    value->clear();
  } else {
    *value = JsonParser::DecodeString(encoded_value);
  }
  return true;
}

bool JsonParser::ParseObject(JsonParser::KeyValueMap* kv_map) {
  kv_map->clear();
  JsonParser::ObjectIterator it(*this);
  while (it.HasKeyValue()) {
    StringPiece key = it.key();
    ValueInfo vi;
    if (!ParseJsonValue(&vi))
      break;
    auto ret = kv_map->emplace(key, vi);
    if (!ret.second) {
      ret.first->second = vi;
    }
  }
  return IsOk();
}

JsonParser::JsonInputStringInfo JsonParser::ParseJsonInputString(
    const char* start, const char* limit) {
  JsonInputStringInfo result = { start, limit, true };

  if (start > limit || *start != '"')
    return result;

  const char* p = start + 1;
  result.start = p;
  auto* next_quote = static_cast<const char*>(::memchr(p, '"', limit - p));
  if (!next_quote)  // Missing closing quote from input.
    return result;

  // If there are no escape sequences, return quickly.
  if (!::memchr(p, '\\', next_quote - p)) {
    result.end = next_quote;
    result.error = false;
    return result;
  }

  // Parse the string looking for escape sequences to find the real closing
  // quote.
  while (true) {
    if (p == limit) {  // Missing closing quote.
      return result;
    }
    if (*p == '"') {  // closing quote.
      result.end = p;
      result.error = false;
      return result;
    }
    if (*p != '\\') {  // non-escaped character.
      p++;
      continue;
    }
    JsonEscapeInfo info = ParseJsonEscape(p, limit);
    if (!info.error) {
      p += info.len;
      continue;
    }
    result.end = p;
    return result;
  }
}

std::string JsonParser::DecodeString(StringPiece str) {
  const char* start = str.begin();
  size_t len = str.size();
  const char* limit = start + len;

  if (start >= limit)
    return {};

  std::string result;
  result.reserve(len);

  while (start < limit) {
    auto* escape =
        static_cast<const char*>(::memchr(start, '\\', limit - start));
    if (!escape) {
      result.append(start, limit - start);
      break;
    }
    if (escape > start)
      result.append(start, escape - start);

    JsonEscapeInfo info = ParseJsonEscape(escape, limit);
    if (info.error)
      break;  // stop at invalid escapes.
    if (info.single_char) {
      result.push_back(info.single_char);
    } else {
      // Write Unicode codepoint as UTF-8.
      uint32_t cp = info.unicode_cp;
      if (cp < 0x80) {
        result.push_back(static_cast<char>(cp));
      } else if (cp < 0x800) {
        result.push_back(static_cast<char>(0xc0 | ((cp >> 6) & 0x1f)));
        result.push_back(static_cast<char>(0x80 | (cp & 0x3f)));
      } else if (cp < 0x10000) {
        result.push_back(static_cast<char>(0xe0 | ((cp >> 12) & 0x1f)));
        result.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3f)));
        result.push_back(static_cast<char>(0x80 | (cp & 0x3f)));
      } else if (cp < 0x1fffff) {
        result.push_back(static_cast<char>(0xf0 | ((cp >> 18) & 0x07)));
        result.push_back(static_cast<char>(0x80 | ((cp >> 12) & 0x3f)));
        result.push_back(static_cast<char>(0x80 | ((cp >> 6) & 0x3f)));
        result.push_back(static_cast<char>(0x80 | (cp & 0x3f)));
      }
    }
    start = escape + info.len;
  }
  return result;
}