json_parser.h

#include <cassert>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <string>
#include <vector>
#define noexcept throw()
#define snprintf _snprintf_s

#pragma once

#ifdef _MSC_VER
#if _MSC_VER <= 1800  // VS 2013
#ifndef noexcept
#endif

#ifndef snprintf
#endif
#endif
#endif

namespace json_parser {

enum JsonParse { STANDARD, COMMENTS };

class JsonValue;

class Json final {
 public:
  // Types
  enum Type { NUL, NUMBER, BOOL, STRING, ARRAY, OBJECT };

  // Array and object typedefs
  typedef std::vector<Json> array;
  typedef std::map<std::string, Json> object;

  // Constructors for the various types of JSON value.
  Json() noexcept;                 // NUL
  Json(std::nullptr_t) noexcept;   // NUL
  Json(double value);              // NUMBER
  Json(int64_t value);             // NUMBER
  Json(bool value);                // BOOL
  Json(const std::string &value);  // STRING
  Json(std::string &&value);       // STRING
  Json(const char *value);         // STRING
  Json(const array &values);       // ARRAY
  Json(array &&values);            // ARRAY
  Json(const object &values);      // OBJECT
  Json(object &&values);           // OBJECT

  // Implicit constructor: anything with a to_json() function.
  template <class T, class = decltype(&T::to_json)>
  Json(const T &t) : Json(t.to_json()) {}

  // Implicit constructor: map-like objects (std::map, std::unordered_map,
  // etc)
  template <
      class M,
      typename std::enable_if<
          std::is_constructible<std::string, typename M::key_type>::value &&
              std::is_constructible<Json, typename M::mapped_type>::value,
          int>::type = 0>
  Json(const M &m) : Json(object(begin(m), end(m))) {}

  // Implicit constructor: vector-like objects (std::list, std::vector,
  // std::set, etc)
  template <class V,
            typename std::enable_if<
                std::is_constructible<Json, typename V::value_type>::value,
                int>::type = 0>
  Json(const V &v) : Json(array(begin(v), end(v))) {}

  // This prevents Json(some_pointer) from accidentally producing a bool. Use
  // Json(bool(some_pointer)) if that behavior is desired.
  Json(void *) = delete;

  // Accessors
  Type type() const;

  bool is_null() const { return type() == NUL; }
  bool is_number() const { return type() == NUMBER; }
  bool is_bool() const { return type() == BOOL; }
  bool is_string() const { return type() == STRING; }
  bool is_array() const { return type() == ARRAY; }
  bool is_object() const { return type() == OBJECT; }

  // Return the enclosed value if this is a number, 0 otherwise. Note that
  // json_parser does not
  // distinguish between integer and non-integer numbers - number_value() and
  // int_value()
  // can both be applied to a NUMBER-typed object.
  double number_value() const;
  int64_t int_value() const;

  // Return the enclosed value if this is a boolean, false otherwise.
  bool bool_value() const;
  // Return the enclosed string if this is a string, "" otherwise.
  const std::string &string_value() const;
  // Return the enclosed std::vector if this is an array, or an empty vector
  // otherwise.
  const array &array_items() const;
  // Return the enclosed std::map if this is an object, or an empty map
  // otherwise.
  const object &object_items() const;

  // Return a reference to arr[i] if this is an array, Json() otherwise.
  const Json &operator[](size_t i) const;
  // Return a reference to obj[key] if this is an object, Json() otherwise.
  const Json &operator[](const std::string &key) const;

  // Serialize.
  void dump(std::string &out) const;
  std::string dump() const {
    std::string out;
    dump(out);
    return out;
  }

  // Parse. If parse fails, return Json() and assign an error message to err.
  static Json parse(const std::string &in, std::string &err,
                    JsonParse strategy = JsonParse::STANDARD);
  static Json parse(const char *in, std::string &err,
                    JsonParse strategy = JsonParse::STANDARD) {
    if (in) {
      return parse(std::string(in), err, strategy);
    } else {
      err = "null input";
      return nullptr;
    }
  }
  // Parse multiple objects, concatenated or separated by whitespace
  static std::vector<Json> parse_multi(
      const std::string &in, std::string::size_type &parser_stop_pos,
      std::string &err, JsonParse strategy = JsonParse::STANDARD);

  static inline std::vector<Json> parse_multi(
      const std::string &in, std::string &err,
      JsonParse strategy = JsonParse::STANDARD) {
    std::string::size_type parser_stop_pos;
    return parse_multi(in, parser_stop_pos, err, strategy);
  }

  bool operator==(const Json &rhs) const;
  bool operator<(const Json &rhs) const;
  bool operator!=(const Json &rhs) const { return !(*this == rhs); }
  bool operator<=(const Json &rhs) const { return !(rhs < *this); }
  bool operator>(const Json &rhs) const { return (rhs < *this); }
  bool operator>=(const Json &rhs) const { return !(*this < rhs); }

  /* has_shape(types, err)
   *
   * Return true if this is a JSON object and, for each item in types, has a
   * field of
   * the given type. If not, return false and set err to a descriptive
   * message.
   */
  typedef std::initializer_list<std::pair<std::string, Type>> shape;
  bool has_shape(const shape &types, std::string &err) const;

 private:
  std::shared_ptr<JsonValue> m_ptr;
};

// Internal class hierarchy - JsonValue objects are not exposed to users of
// this API.
class JsonValue {
 protected:
  friend class Json;
  friend class JsonInt;
  friend class JsonDouble;
  virtual Json::Type type() const = 0;
  virtual bool equals(const JsonValue *other) const = 0;
  virtual bool less(const JsonValue *other) const = 0;
  virtual void dump(std::string &out) const = 0;
  virtual double number_value() const;
  virtual int64_t int_value() const;
  virtual bool bool_value() const;
  virtual const std::string &string_value() const;
  virtual const Json::array &array_items() const;
  virtual const Json &operator[](size_t i) const;
  virtual const Json::object &object_items() const;
  virtual const Json &operator[](const std::string &key) const;
  virtual ~JsonValue() {}
};

static const int max_depth = 200;

using std::initializer_list;
using std::make_shared;
using std::map;
using std::move;
using std::string;
using std::vector;

/* Helper for representing null - just a do-nothing struct, plus comparison
 * operators so the helpers in JsonValue work. We can't use nullptr_t because
 * it may not be orderable.
 */
struct NullStruct {
  bool operator==(NullStruct) const { return true; }
  bool operator<(NullStruct) const { return false; }
};

/* * * * * * * * * * * * * * * * * * * *
 * Serialization
 */

static void dump(NullStruct, string &out) { out += "null"; }

static void dump(double value, string &out) {
  if (std::isfinite(value)) {
    char buf[32];
    snprintf(buf, sizeof buf, "%.17g", value);
    out += buf;
  } else {
    out += "null";
  }
}

static void dump(int64_t value, string &out) {
  char buf[32];
  snprintf(buf, sizeof buf, "%" PRId64, value);
  out += buf;
}

static void dump(bool value, string &out) { out += value ? "true" : "false"; }

static void dump(const string &value, string &out) {
  out += '"';
  for (size_t i = 0; i < value.length(); i++) {
    const char ch = value[i];
    if (ch == '\\') {
      out += "\\\\";
    } else if (ch == '"') {
      out += "\\\"";
    } else if (ch == '\b') {
      out += "\\b";
    } else if (ch == '\f') {
      out += "\\f";
    } else if (ch == '\n') {
      out += "\\n";
    } else if (ch == '\r') {
      out += "\\r";
    } else if (ch == '\t') {
      out += "\\t";
    } else if (static_cast<uint8_t>(ch) <= 0x1f) {
      char buf[8];
      snprintf(buf, sizeof buf, "\\u%04x", ch);
      out += buf;
    } else if (static_cast<uint8_t>(ch) == 0xe2 &&
               static_cast<uint8_t>(value[i + 1]) == 0x80 &&
               static_cast<uint8_t>(value[i + 2]) == 0xa8) {
      out += "\\u2028";
      i += 2;
    } else if (static_cast<uint8_t>(ch) == 0xe2 &&
               static_cast<uint8_t>(value[i + 1]) == 0x80 &&
               static_cast<uint8_t>(value[i + 2]) == 0xa9) {
      out += "\\u2029";
      i += 2;
    } else {
      out += ch;
    }
  }
  out += '"';
}

static void dump(const Json::array &values, string &out) {
  bool first = true;
  out += "[";
  for (const auto &value : values) {
    if (!first) out += ", ";
    value.dump(out);
    first = false;
  }
  out += "]";
}

static void dump(const Json::object &values, string &out) {
  bool first = true;
  out += "{";
  for (const auto &kv : values) {
    if (!first) out += ", ";
    dump(kv.first, out);
    out += ": ";
    kv.second.dump(out);
    first = false;
  }
  out += "}";
}

void Json::dump(string &out) const { m_ptr->dump(out); }

/* * * * * * * * * * * * * * * * * * * *
 * Value wrappers
 */

template <Json::Type tag, typename T>
class Value : public JsonValue {
 protected:
  // Constructors
  explicit Value(const T &value) : m_value(value) {}
  explicit Value(T &&value) : m_value(move(value)) {}

  // Get type tag
  Json::Type type() const override { return tag; }

  // Comparisons
  bool equals(const JsonValue *other) const override {
    return m_value == static_cast<const Value<tag, T> *>(other)->m_value;
  }
  bool less(const JsonValue *other) const override {
    return m_value < static_cast<const Value<tag, T> *>(other)->m_value;
  }

  const T m_value;
  void dump(string &out) const override { json_parser::dump(m_value, out); }
};

class JsonDouble final : public Value<Json::NUMBER, double> {
  double number_value() const override { return m_value; }
  int64_t int_value() const override { return static_cast<int64_t>(m_value); }
  bool equals(const JsonValue *other) const override {
    return m_value == other->number_value();
  }
  bool less(const JsonValue *other) const override {
    return m_value < other->number_value();
  }

 public:
  explicit JsonDouble(double value) : Value(value) {}
};

class JsonInt final : public Value<Json::NUMBER, int64_t> {
  double number_value() const override { return m_value; }
  int64_t int_value() const override { return m_value; }
  bool equals(const JsonValue *other) const override {
    return m_value == other->number_value();
  }
  bool less(const JsonValue *other) const override {
    return m_value < other->number_value();
  }

 public:
  explicit JsonInt(int value) : Value(value) {}
};

class JsonBoolean final : public Value<Json::BOOL, bool> {
  bool bool_value() const override { return m_value; }

 public:
  explicit JsonBoolean(bool value) : Value(value) {}
};

class JsonString final : public Value<Json::STRING, string> {
  const string &string_value() const override { return m_value; }

 public:
  explicit JsonString(const string &value) : Value(value) {}
  explicit JsonString(string &&value) : Value(move(value)) {}
};

class JsonArray final : public Value<Json::ARRAY, Json::array> {
  const Json::array &array_items() const override { return m_value; }
  const Json &operator[](size_t i) const override;

 public:
  explicit JsonArray(const Json::array &value) : Value(value) {}
  explicit JsonArray(Json::array &&value) : Value(move(value)) {}
};

class JsonObject final : public Value<Json::OBJECT, Json::object> {
  const Json::object &object_items() const override { return m_value; }
  const Json &operator[](const string &key) const override;

 public:
  explicit JsonObject(const Json::object &value) : Value(value) {}
  explicit JsonObject(Json::object &&value) : Value(move(value)) {}
};

class JsonNull final : public Value<Json::NUL, NullStruct> {
 public:
  JsonNull() : Value({}) {}
};

/* * * * * * * * * * * * * * * * * * * *
 * Static globals - static-init-safe
 */
struct Statics {
  const std::shared_ptr<JsonValue> null = make_shared<JsonNull>();
  const std::shared_ptr<JsonValue> t = make_shared<JsonBoolean>(true);
  const std::shared_ptr<JsonValue> f = make_shared<JsonBoolean>(false);
  const string empty_string;
  const vector<Json> empty_vector;
  const map<string, Json> empty_map;
  Statics() {}
};

static const Statics &statics() {
  static const Statics s{};
  return s;
}

static const Json &static_null() {
  // This has to be separate, not in Statics, because Json() accesses
  // statics().null.
  static const Json json_null;
  return json_null;
}

/* * * * * * * * * * * * * * * * * * * *
 * Constructors
 */

Json::Json() noexcept : m_ptr(statics().null) {}
Json::Json(std::nullptr_t) noexcept : m_ptr(statics().null) {}
Json::Json(double value) : m_ptr(make_shared<JsonDouble>(value)) {}
Json::Json(int64_t value) : m_ptr(make_shared<JsonInt>(value)) {}
Json::Json(bool value) : m_ptr(value ? statics().t : statics().f) {}
Json::Json(const string &value) : m_ptr(make_shared<JsonString>(value)) {}
Json::Json(string &&value) : m_ptr(make_shared<JsonString>(move(value))) {}
Json::Json(const char *value) : m_ptr(make_shared<JsonString>(value)) {}
Json::Json(const Json::array &values) : m_ptr(make_shared<JsonArray>(values)) {}
Json::Json(Json::array &&values)
    : m_ptr(make_shared<JsonArray>(move(values))) {}
Json::Json(const Json::object &values)
    : m_ptr(make_shared<JsonObject>(values)) {}
Json::Json(Json::object &&values)
    : m_ptr(make_shared<JsonObject>(move(values))) {}

/* * * * * * * * * * * * * * * * * * * *
 * Accessors
 */

Json::Type Json::type() const { return m_ptr->type(); }
double Json::number_value() const { return m_ptr->number_value(); }
int64_t Json::int_value() const { return m_ptr->int_value(); }
bool Json::bool_value() const { return m_ptr->bool_value(); }
const string &Json::string_value() const { return m_ptr->string_value(); }
const vector<Json> &Json::array_items() const { return m_ptr->array_items(); }
const map<string, Json> &Json::object_items() const {
  return m_ptr->object_items();
}
const Json &Json::operator[](size_t i) const { return (*m_ptr)[i]; }
const Json &Json::operator[](const string &key) const { return (*m_ptr)[key]; }

double JsonValue::number_value() const { return 0; }
int64_t JsonValue::int_value() const { return 0; }
bool JsonValue::bool_value() const { return false; }
const string &JsonValue::string_value() const { return statics().empty_string; }
const vector<Json> &JsonValue::array_items() const {
  return statics().empty_vector;
}
const map<string, Json> &JsonValue::object_items() const {
  return statics().empty_map;
}
const Json &JsonValue::operator[](size_t) const { return static_null(); }
const Json &JsonValue::operator[](const string &) const {
  return static_null();
}

const Json &JsonObject::operator[](const string &key) const {
  auto iter = m_value.find(key);
  return (iter == end(m_value)) ? static_null() : iter->second;
}
const Json &JsonArray::operator[](size_t i) const {
  if (i >= m_value.size())
    return static_null();
  else
    return m_value[i];
}

/* * * * * * * * * * * * * * * * * * * *
 * Comparison
 */

bool Json::operator==(const Json &other) const {
  if (m_ptr == other.m_ptr) return true;
  if (m_ptr->type() != other.m_ptr->type()) return false;

  return m_ptr->equals(other.m_ptr.get());
}

bool Json::operator<(const Json &other) const {
  if (m_ptr == other.m_ptr) return false;
  if (m_ptr->type() != other.m_ptr->type())
    return m_ptr->type() < other.m_ptr->type();

  return m_ptr->less(other.m_ptr.get());
}

/* * * * * * * * * * * * * * * * * * * *
 * Parsing
 */

/* esc(c)
 *
 * Format char c suitable for printing in an error message.
 */
static inline string esc(char c) {
  char buf[12];
  if (static_cast<uint8_t>(c) >= 0x20 && static_cast<uint8_t>(c) <= 0x7f) {
    snprintf(buf, sizeof buf, "'%c' (%d)", c, c);
  } else {
    snprintf(buf, sizeof buf, "(%d)", c);
  }
  return string(buf);
}

static inline bool in_range(long x, long lower, long upper) {
  return (x >= lower && x <= upper);
}

/* JsonParser
 *
 * Object that tracks all state of an in-progress parse.
 */
struct JsonParser final {
  /* State
   */
  const string &str;
  size_t i;
  string &err;
  bool failed;
  const JsonParse strategy;

  /* fail(msg, err_ret = Json())
   *
   * Mark this parse as failed.
   */
  Json fail(string &&msg) { return fail(move(msg), Json()); }

  template <typename T>
  T fail(string &&msg, const T err_ret) {
    if (!failed) err = std::move(msg);
    failed = true;
    return err_ret;
  }

  /* consume_whitespace()
   *
   * Advance until the current character is non-whitespace.
   */
  void consume_whitespace() {
    while (str[i] == ' ' || str[i] == '\r' || str[i] == '\n' || str[i] == '\t')
      i++;
  }

  /* consume_comment()
   *
   * Advance comments (c-style inline and multiline).
   */
  bool consume_comment() {
    bool comment_found = false;
    if (str[i] == '/') {
      i++;
      if (i == str.size())
        return fail("unexpected end of input after start of comment", false);
      if (str[i] == '/') {  // inline comment
        i++;
        // advance until next line, or end of input
        while (i < str.size() && str[i] != '\n') {
          i++;
        }
        comment_found = true;
      } else if (str[i] == '*') {  // multiline comment
        i++;
        if (i > str.size() - 2)
          return fail("unexpected end of input inside multi-line comment",
                      false);
        // advance until closing tokens
        while (!(str[i] == '*' && str[i + 1] == '/')) {
          i++;
          if (i > str.size() - 2)
            return fail("unexpected end of input inside multi-line comment",
                        false);
        }
        i += 2;
        comment_found = true;
      } else
        return fail("malformed comment", false);
    }
    return comment_found;
  }

  /* consume_garbage()
   *
   * Advance until the current character is non-whitespace and non-comment.
   */
  void consume_garbage() {
    consume_whitespace();
    if (strategy == JsonParse::COMMENTS) {
      bool comment_found = false;
      do {
        comment_found = consume_comment();
        if (failed) return;
        consume_whitespace();
      } while (comment_found);
    }
  }

  /* get_next_token()
   *
   * Return the next non-whitespace character. If the end of the input is
   * reached,
   * flag an error and return 0.
   */
  char get_next_token() {
    consume_garbage();
    if (failed) return (char)0;
    if (i == str.size()) return fail("unexpected end of input", (char)0);

    return str[i++];
  }

  /* encode_utf8(pt, out)
   *
   * Encode pt as UTF-8 and add it to out.
   */
  void encode_utf8(long pt, string &out) {
    if (pt < 0) return;

    if (pt < 0x80) {
      out += static_cast<char>(pt);
    } else if (pt < 0x800) {
      out += static_cast<char>((pt >> 6) | 0xC0);
      out += static_cast<char>((pt & 0x3F) | 0x80);
    } else if (pt < 0x10000) {
      out += static_cast<char>((pt >> 12) | 0xE0);
      out += static_cast<char>(((pt >> 6) & 0x3F) | 0x80);
      out += static_cast<char>((pt & 0x3F) | 0x80);
    } else {
      out += static_cast<char>((pt >> 18) | 0xF0);
      out += static_cast<char>(((pt >> 12) & 0x3F) | 0x80);
      out += static_cast<char>(((pt >> 6) & 0x3F) | 0x80);
      out += static_cast<char>((pt & 0x3F) | 0x80);
    }
  }

  /* parse_string()
   *
   * Parse a string, starting at the current position.
   */
  string parse_string() {
    string out;
    long last_escaped_codepoint = -1;
    while (true) {
      if (i == str.size()) return fail("unexpected end of input in string", "");

      char ch = str[i++];

      if (ch == '"') {
        encode_utf8(last_escaped_codepoint, out);
        return out;
      }

      if (in_range(ch, 0, 0x1f))
        return fail("unescaped " + esc(ch) + " in string", "");

      // The usual case: non-escaped characters
      if (ch != '\\') {
        encode_utf8(last_escaped_codepoint, out);
        last_escaped_codepoint = -1;
        out += ch;
        continue;
      }

      // Handle escapes
      if (i == str.size()) return fail("unexpected end of input in string", "");

      ch = str[i++];

      if (ch == 'u') {
        // Extract 4-byte escape sequence
        string esc = str.substr(i, 4);
        // Explicitly check length of the substring. The following loop
        // relies on std::string returning the terminating NUL when
        // accessing str[length]. Checking here reduces brittleness.
        if (esc.length() < 4) {
          return fail("bad \\u escape: " + esc, "");
        }
        for (size_t j = 0; j < 4; j++) {
          if (!in_range(esc[j], 'a', 'f') && !in_range(esc[j], 'A', 'F') &&
              !in_range(esc[j], '0', '9'))
            return fail("bad \\u escape: " + esc, "");
        }

        long codepoint = strtol(esc.data(), nullptr, 16);

        // JSON specifies that characters outside the BMP shall be encoded as
        // a pair
        // of 4-hex-digit \u escapes encoding their surrogate pair components.
        // Check
        // whether we're in the middle of such a beast: the previous codepoint
        // was an
        // escaped lead (high) surrogate, and this is a trail (low) surrogate.
        if (in_range(last_escaped_codepoint, 0xD800, 0xDBFF) &&
            in_range(codepoint, 0xDC00, 0xDFFF)) {
          // Reassemble the two surrogate pairs into one astral-plane
          // character, per
          // the UTF-16 algorithm.
          encode_utf8((((last_escaped_codepoint - 0xD800) << 10) |
                       (codepoint - 0xDC00)) +
                          0x10000,
                      out);
          last_escaped_codepoint = -1;
        } else {
          encode_utf8(last_escaped_codepoint, out);
          last_escaped_codepoint = codepoint;
        }

        i += 4;
        continue;
      }

      encode_utf8(last_escaped_codepoint, out);
      last_escaped_codepoint = -1;

      if (ch == 'b') {
        out += '\b';
      } else if (ch == 'f') {
        out += '\f';
      } else if (ch == 'n') {
        out += '\n';
      } else if (ch == 'r') {
        out += '\r';
      } else if (ch == 't') {
        out += '\t';
      } else if (ch == '"' || ch == '\\' || ch == '/') {
        out += ch;
      } else {
        return fail("invalid escape character " + esc(ch), "");
      }
    }
  }

  /* parse_number()
   *
   * Parse a double.
   */
  Json parse_number() {
    size_t start_pos = i;

    if (str[i] == '-') i++;

    // Integer part
    if (str[i] == '0') {
      i++;
      if (in_range(str[i], '0', '9'))
        return fail("leading 0s not permitted in numbers");
    } else if (in_range(str[i], '1', '9')) {
      i++;
      while (in_range(str[i], '0', '9')) i++;
    } else {
      return fail("invalid " + esc(str[i]) + " in number");
    }

    if (str[i] != '.' && str[i] != 'e' && str[i] != 'E' &&
        (i - start_pos) <=
            static_cast<size_t>(std::numeric_limits<int64_t>::digits10)) {
      return static_cast<int64_t>(std::atoll(str.c_str() + start_pos));
    }

    // Decimal part
    if (str[i] == '.') {
      i++;
      if (!in_range(str[i], '0', '9'))
        return fail("at least one digit required in fractional part");

      while (in_range(str[i], '0', '9')) i++;
    }

    // Exponent part
    if (str[i] == 'e' || str[i] == 'E') {
      i++;

      if (str[i] == '+' || str[i] == '-') i++;

      if (!in_range(str[i], '0', '9'))
        return fail("at least one digit required in exponent");

      while (in_range(str[i], '0', '9')) i++;
    }

    return std::strtod(str.c_str() + start_pos, nullptr);
  }

  /* expect(str, result)
   *
   * Expect that 'str' starts at the character that was just read. If it does,
   * advance
   * the input and return result. If not, flag an error.
   */
  Json expect(const string &expected, Json result) {
    assert(i != 0);
    i--;
    if (str.compare(i, expected.length(), expected) == 0) {
      i += expected.length();
      return result;
    } else {
      return fail("parse error: expected " + expected + ", got " +
                  str.substr(i, expected.length()));
    }
  }

  /* parse_json()
   *
   * Parse a JSON object.
   */
  Json parse_json(int depth) {
    if (depth > max_depth) {
      return fail("exceeded maximum nesting depth");
    }

    char ch = get_next_token();
    if (failed) return Json();

    if (ch == '-' || (ch >= '0' && ch <= '9')) {
      i--;
      return parse_number();
    }

    if (ch == 't') return expect("true", true);

    if (ch == 'f') return expect("false", false);

    if (ch == 'n') return expect("null", Json());

    if (ch == '"') return parse_string();

    if (ch == '{') {
      map<string, Json> data;
      ch = get_next_token();
      if (ch == '}') return data;

      while (1) {
        if (ch != '"') return fail("expected '\"' in object, got " + esc(ch));

        string key = parse_string();
        if (failed) return Json();

        ch = get_next_token();
        if (ch != ':') return fail("expected ':' in object, got " + esc(ch));

        data[std::move(key)] = parse_json(depth + 1);
        if (failed) return Json();

        ch = get_next_token();
        if (ch == '}') break;
        if (ch != ',') return fail("expected ',' in object, got " + esc(ch));

        ch = get_next_token();
      }
      return data;
    }

    if (ch == '[') {
      vector<Json> data;
      ch = get_next_token();
      if (ch == ']') return data;

      while (1) {
        i--;
        data.push_back(parse_json(depth + 1));
        if (failed) return Json();

        ch = get_next_token();
        if (ch == ']') break;
        if (ch != ',') return fail("expected ',' in list, got " + esc(ch));

        ch = get_next_token();
        (void)ch;
      }
      return data;
    }

    return fail("expected value, got " + esc(ch));
  }
};

Json Json::parse(const string &in, string &err, JsonParse strategy) {
  JsonParser parser{in, 0, err, false, strategy};
  Json result = parser.parse_json(0);

  // Check for any trailing garbage
  parser.consume_garbage();
  if (parser.failed) return Json();
  if (parser.i != in.size())
    return parser.fail("unexpected trailing " + esc(in[parser.i]));

  return result;
}

// Documented in json_parser.hpp
vector<Json> Json::parse_multi(const string &in,
                               std::string::size_type &parser_stop_pos,
                               string &err, JsonParse strategy) {
  JsonParser parser{in, 0, err, false, strategy};
  parser_stop_pos = 0;
  vector<Json> json_vec;
  while (parser.i != in.size() && !parser.failed) {
    json_vec.push_back(parser.parse_json(0));
    if (parser.failed) break;

    // Check for another object
    parser.consume_garbage();
    if (parser.failed) break;
    parser_stop_pos = parser.i;
  }
  return json_vec;
}

/* * * * * * * * * * * * * * * * * * * *
 * Shape-checking
 */

bool Json::has_shape(const shape &types, string &err) const {
  if (!is_object()) {
    err = "expected JSON object, got " + dump();
    return false;
  }

  for (auto &item : types) {
    if ((*this)[item.first].type() != item.second) {
      err = "bad type for " + item.first + " in " + dump();
      return false;
    }
  }

  return true;
}

}  // namespace json_parser