cannam@150: /* Copyright (c) 2013 Dropbox, Inc.
cannam@150:  *
cannam@150:  * Permission is hereby granted, free of charge, to any person obtaining a copy
cannam@150:  * of this software and associated documentation files (the "Software"), to deal
cannam@150:  * in the Software without restriction, including without limitation the rights
cannam@150:  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
cannam@150:  * copies of the Software, and to permit persons to whom the Software is
cannam@150:  * furnished to do so, subject to the following conditions:
cannam@150:  *
cannam@150:  * The above copyright notice and this permission notice shall be included in
cannam@150:  * all copies or substantial portions of the Software.
cannam@150:  *
cannam@150:  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
cannam@150:  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
cannam@150:  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
cannam@150:  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
cannam@150:  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
cannam@150:  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
cannam@150:  * THE SOFTWARE.
cannam@150:  */
cannam@150: 
cannam@150: #include "json11.hpp"
cannam@150: #include <cassert>
cannam@150: #include <cmath>
cannam@150: #include <cstdlib>
cannam@150: #include <cstdio>
cannam@150: #include <limits>
cannam@150: 
cannam@150: namespace json11 {
cannam@150: 
cannam@150: static const int max_depth = 200;
cannam@150: 
cannam@150: using std::string;
cannam@150: using std::vector;
cannam@150: using std::map;
cannam@150: using std::make_shared;
cannam@150: using std::initializer_list;
cannam@150: using std::move;
cannam@150: 
cannam@242: /* Helper for representing null - just a do-nothing struct, plus comparison
cannam@242:  * operators so the helpers in JsonValue work. We can't use nullptr_t because
cannam@242:  * it may not be orderable.
cannam@242:  */
cannam@242: struct NullStruct {
cannam@242:     bool operator==(NullStruct) const { return true; }
cannam@242:     bool operator<(NullStruct) const { return false; }
cannam@242: };
cannam@242: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Serialization
cannam@150:  */
cannam@150: 
cannam@242: static void dump(NullStruct, string &out) {
cannam@150:     out += "null";
cannam@150: }
cannam@150: 
cannam@150: static void dump(double value, string &out) {
cannam@150:     if (std::isfinite(value)) {
cannam@150:         char buf[32];
cannam@150:         snprintf(buf, sizeof buf, "%.17g", value);
cannam@150:         out += buf;
cannam@150:     } else {
cannam@150:         out += "null";
cannam@150:     }
cannam@150: }
cannam@150: 
cannam@150: static void dump(int value, string &out) {
cannam@150:     char buf[32];
cannam@150:     snprintf(buf, sizeof buf, "%d", value);
cannam@150:     out += buf;
cannam@150: }
cannam@150: 
cannam@150: static void dump(bool value, string &out) {
cannam@150:     out += value ? "true" : "false";
cannam@150: }
cannam@150: 
cannam@150: static void dump(const string &value, string &out) {
cannam@150:     out += '"';
cannam@150:     for (size_t i = 0; i < value.length(); i++) {
cannam@150:         const char ch = value[i];
cannam@150:         if (ch == '\\') {
cannam@150:             out += "\\\\";
cannam@150:         } else if (ch == '"') {
cannam@150:             out += "\\\"";
cannam@150:         } else if (ch == '\b') {
cannam@150:             out += "\\b";
cannam@150:         } else if (ch == '\f') {
cannam@150:             out += "\\f";
cannam@150:         } else if (ch == '\n') {
cannam@150:             out += "\\n";
cannam@150:         } else if (ch == '\r') {
cannam@150:             out += "\\r";
cannam@150:         } else if (ch == '\t') {
cannam@150:             out += "\\t";
cannam@150:         } else if (static_cast<uint8_t>(ch) <= 0x1f) {
cannam@150:             char buf[8];
cannam@150:             snprintf(buf, sizeof buf, "\\u%04x", ch);
cannam@150:             out += buf;
cannam@150:         } else if (static_cast<uint8_t>(ch) == 0xe2 && static_cast<uint8_t>(value[i+1]) == 0x80
cannam@150:                    && static_cast<uint8_t>(value[i+2]) == 0xa8) {
cannam@150:             out += "\\u2028";
cannam@150:             i += 2;
cannam@150:         } else if (static_cast<uint8_t>(ch) == 0xe2 && static_cast<uint8_t>(value[i+1]) == 0x80
cannam@150:                    && static_cast<uint8_t>(value[i+2]) == 0xa9) {
cannam@150:             out += "\\u2029";
cannam@150:             i += 2;
cannam@150:         } else {
cannam@150:             out += ch;
cannam@150:         }
cannam@150:     }
cannam@150:     out += '"';
cannam@150: }
cannam@150: 
cannam@150: static void dump(const Json::array &values, string &out) {
cannam@150:     bool first = true;
cannam@150:     out += "[";
cannam@150:     for (const auto &value : values) {
cannam@150:         if (!first)
cannam@150:             out += ", ";
cannam@150:         value.dump(out);
cannam@150:         first = false;
cannam@150:     }
cannam@150:     out += "]";
cannam@150: }
cannam@150: 
cannam@150: static void dump(const Json::object &values, string &out) {
cannam@150:     bool first = true;
cannam@150:     out += "{";
cannam@150:     for (const auto &kv : values) {
cannam@150:         if (!first)
cannam@150:             out += ", ";
cannam@150:         dump(kv.first, out);
cannam@150:         out += ": ";
cannam@150:         kv.second.dump(out);
cannam@150:         first = false;
cannam@150:     }
cannam@150:     out += "}";
cannam@150: }
cannam@150: 
cannam@150: void Json::dump(string &out) const {
cannam@150:     m_ptr->dump(out);
cannam@150: }
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Value wrappers
cannam@150:  */
cannam@150: 
cannam@150: template <Json::Type tag, typename T>
cannam@150: class Value : public JsonValue {
cannam@150: protected:
cannam@150: 
cannam@150:     // Constructors
cannam@150:     explicit Value(const T &value) : m_value(value) {}
cannam@150:     explicit Value(T &&value)      : m_value(move(value)) {}
cannam@150: 
cannam@150:     // Get type tag
cannam@150:     Json::Type type() const override {
cannam@150:         return tag;
cannam@150:     }
cannam@150: 
cannam@150:     // Comparisons
cannam@150:     bool equals(const JsonValue * other) const override {
cannam@150:         return m_value == static_cast<const Value<tag, T> *>(other)->m_value;
cannam@150:     }
cannam@150:     bool less(const JsonValue * other) const override {
cannam@150:         return m_value < static_cast<const Value<tag, T> *>(other)->m_value;
cannam@150:     }
cannam@150: 
cannam@150:     const T m_value;
cannam@150:     void dump(string &out) const override { json11::dump(m_value, out); }
cannam@150: };
cannam@150: 
cannam@150: class JsonDouble final : public Value<Json::NUMBER, double> {
cannam@150:     double number_value() const override { return m_value; }
cannam@150:     int int_value() const override { return static_cast<int>(m_value); }
cannam@150:     bool equals(const JsonValue * other) const override { return m_value == other->number_value(); }
cannam@150:     bool less(const JsonValue * other)   const override { return m_value <  other->number_value(); }
cannam@150: public:
cannam@150:     explicit JsonDouble(double value) : Value(value) {}
cannam@150: };
cannam@150: 
cannam@150: class JsonInt final : public Value<Json::NUMBER, int> {
cannam@150:     double number_value() const override { return m_value; }
cannam@150:     int int_value() const override { return m_value; }
cannam@150:     bool equals(const JsonValue * other) const override { return m_value == other->number_value(); }
cannam@150:     bool less(const JsonValue * other)   const override { return m_value <  other->number_value(); }
cannam@150: public:
cannam@150:     explicit JsonInt(int value) : Value(value) {}
cannam@150: };
cannam@150: 
cannam@150: class JsonBoolean final : public Value<Json::BOOL, bool> {
cannam@150:     bool bool_value() const override { return m_value; }
cannam@150: public:
cannam@150:     explicit JsonBoolean(bool value) : Value(value) {}
cannam@150: };
cannam@150: 
cannam@150: class JsonString final : public Value<Json::STRING, string> {
cannam@150:     const string &string_value() const override { return m_value; }
cannam@150: public:
cannam@150:     explicit JsonString(const string &value) : Value(value) {}
cannam@150:     explicit JsonString(string &&value)      : Value(move(value)) {}
cannam@150: };
cannam@150: 
cannam@150: class JsonArray final : public Value<Json::ARRAY, Json::array> {
cannam@150:     const Json::array &array_items() const override { return m_value; }
cannam@150:     const Json & operator[](size_t i) const override;
cannam@150: public:
cannam@150:     explicit JsonArray(const Json::array &value) : Value(value) {}
cannam@150:     explicit JsonArray(Json::array &&value)      : Value(move(value)) {}
cannam@150: };
cannam@150: 
cannam@150: class JsonObject final : public Value<Json::OBJECT, Json::object> {
cannam@150:     const Json::object &object_items() const override { return m_value; }
cannam@150:     const Json & operator[](const string &key) const override;
cannam@150: public:
cannam@150:     explicit JsonObject(const Json::object &value) : Value(value) {}
cannam@150:     explicit JsonObject(Json::object &&value)      : Value(move(value)) {}
cannam@150: };
cannam@150: 
cannam@242: class JsonNull final : public Value<Json::NUL, NullStruct> {
cannam@150: public:
cannam@242:     JsonNull() : Value({}) {}
cannam@150: };
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Static globals - static-init-safe
cannam@150:  */
cannam@150: struct Statics {
cannam@150:     const std::shared_ptr<JsonValue> null = make_shared<JsonNull>();
cannam@150:     const std::shared_ptr<JsonValue> t = make_shared<JsonBoolean>(true);
cannam@150:     const std::shared_ptr<JsonValue> f = make_shared<JsonBoolean>(false);
cannam@150:     const string empty_string;
cannam@150:     const vector<Json> empty_vector;
cannam@150:     const map<string, Json> empty_map;
cannam@150:     Statics() {}
cannam@150: };
cannam@150: 
cannam@150: static const Statics & statics() {
cannam@150:     static const Statics s {};
cannam@150:     return s;
cannam@150: }
cannam@150: 
cannam@150: static const Json & static_null() {
cannam@150:     // This has to be separate, not in Statics, because Json() accesses statics().null.
cannam@150:     static const Json json_null;
cannam@150:     return json_null;
cannam@150: }
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Constructors
cannam@150:  */
cannam@150: 
cannam@150: Json::Json() noexcept                  : m_ptr(statics().null) {}
cannam@150: Json::Json(std::nullptr_t) noexcept    : m_ptr(statics().null) {}
cannam@150: Json::Json(double value)               : m_ptr(make_shared<JsonDouble>(value)) {}
cannam@150: Json::Json(int value)                  : m_ptr(make_shared<JsonInt>(value)) {}
cannam@150: Json::Json(bool value)                 : m_ptr(value ? statics().t : statics().f) {}
cannam@150: Json::Json(const string &value)        : m_ptr(make_shared<JsonString>(value)) {}
cannam@150: Json::Json(string &&value)             : m_ptr(make_shared<JsonString>(move(value))) {}
cannam@150: Json::Json(const char * value)         : m_ptr(make_shared<JsonString>(value)) {}
cannam@150: Json::Json(const Json::array &values)  : m_ptr(make_shared<JsonArray>(values)) {}
cannam@150: Json::Json(Json::array &&values)       : m_ptr(make_shared<JsonArray>(move(values))) {}
cannam@150: Json::Json(const Json::object &values) : m_ptr(make_shared<JsonObject>(values)) {}
cannam@150: Json::Json(Json::object &&values)      : m_ptr(make_shared<JsonObject>(move(values))) {}
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Accessors
cannam@150:  */
cannam@150: 
cannam@150: Json::Type Json::type()                           const { return m_ptr->type();         }
cannam@150: double Json::number_value()                       const { return m_ptr->number_value(); }
cannam@150: int Json::int_value()                             const { return m_ptr->int_value();    }
cannam@150: bool Json::bool_value()                           const { return m_ptr->bool_value();   }
cannam@150: const string & Json::string_value()               const { return m_ptr->string_value(); }
cannam@150: const vector<Json> & Json::array_items()          const { return m_ptr->array_items();  }
cannam@150: const map<string, Json> & Json::object_items()    const { return m_ptr->object_items(); }
cannam@150: const Json & Json::operator[] (size_t i)          const { return (*m_ptr)[i];           }
cannam@150: const Json & Json::operator[] (const string &key) const { return (*m_ptr)[key];         }
cannam@150: 
cannam@150: double                    JsonValue::number_value()              const { return 0; }
cannam@150: int                       JsonValue::int_value()                 const { return 0; }
cannam@150: bool                      JsonValue::bool_value()                const { return false; }
cannam@150: const string &            JsonValue::string_value()              const { return statics().empty_string; }
cannam@150: const vector<Json> &      JsonValue::array_items()               const { return statics().empty_vector; }
cannam@150: const map<string, Json> & JsonValue::object_items()              const { return statics().empty_map; }
cannam@150: const Json &              JsonValue::operator[] (size_t)         const { return static_null(); }
cannam@150: const Json &              JsonValue::operator[] (const string &) const { return static_null(); }
cannam@150: 
cannam@150: const Json & JsonObject::operator[] (const string &key) const {
cannam@150:     auto iter = m_value.find(key);
cannam@150:     return (iter == m_value.end()) ? static_null() : iter->second;
cannam@150: }
cannam@150: const Json & JsonArray::operator[] (size_t i) const {
cannam@150:     if (i >= m_value.size()) return static_null();
cannam@150:     else return m_value[i];
cannam@150: }
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Comparison
cannam@150:  */
cannam@150: 
cannam@150: bool Json::operator== (const Json &other) const {
cannam@242:     if (m_ptr == other.m_ptr)
cannam@242:         return true;
cannam@150:     if (m_ptr->type() != other.m_ptr->type())
cannam@150:         return false;
cannam@150: 
cannam@150:     return m_ptr->equals(other.m_ptr.get());
cannam@150: }
cannam@150: 
cannam@150: bool Json::operator< (const Json &other) const {
cannam@242:     if (m_ptr == other.m_ptr)
cannam@242:         return false;
cannam@150:     if (m_ptr->type() != other.m_ptr->type())
cannam@150:         return m_ptr->type() < other.m_ptr->type();
cannam@150: 
cannam@150:     return m_ptr->less(other.m_ptr.get());
cannam@150: }
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Parsing
cannam@150:  */
cannam@150: 
cannam@150: /* esc(c)
cannam@150:  *
cannam@150:  * Format char c suitable for printing in an error message.
cannam@150:  */
cannam@150: static inline string esc(char c) {
cannam@150:     char buf[12];
cannam@150:     if (static_cast<uint8_t>(c) >= 0x20 && static_cast<uint8_t>(c) <= 0x7f) {
cannam@150:         snprintf(buf, sizeof buf, "'%c' (%d)", c, c);
cannam@150:     } else {
cannam@150:         snprintf(buf, sizeof buf, "(%d)", c);
cannam@150:     }
cannam@150:     return string(buf);
cannam@150: }
cannam@150: 
cannam@150: static inline bool in_range(long x, long lower, long upper) {
cannam@150:     return (x >= lower && x <= upper);
cannam@150: }
cannam@150: 
cannam@242: namespace {
cannam@150: /* JsonParser
cannam@150:  *
cannam@150:  * Object that tracks all state of an in-progress parse.
cannam@150:  */
cannam@242: struct JsonParser final {
cannam@150: 
cannam@150:     /* State
cannam@150:      */
cannam@150:     const string &str;
cannam@150:     size_t i;
cannam@150:     string &err;
cannam@150:     bool failed;
cannam@150:     const JsonParse strategy;
cannam@150: 
cannam@150:     /* fail(msg, err_ret = Json())
cannam@150:      *
cannam@150:      * Mark this parse as failed.
cannam@150:      */
cannam@150:     Json fail(string &&msg) {
cannam@150:         return fail(move(msg), Json());
cannam@150:     }
cannam@150: 
cannam@150:     template <typename T>
cannam@150:     T fail(string &&msg, const T err_ret) {
cannam@150:         if (!failed)
cannam@150:             err = std::move(msg);
cannam@150:         failed = true;
cannam@150:         return err_ret;
cannam@150:     }
cannam@150: 
cannam@150:     /* consume_whitespace()
cannam@150:      *
cannam@150:      * Advance until the current character is non-whitespace.
cannam@150:      */
cannam@150:     void consume_whitespace() {
cannam@150:         while (str[i] == ' ' || str[i] == '\r' || str[i] == '\n' || str[i] == '\t')
cannam@150:             i++;
cannam@150:     }
cannam@150: 
cannam@150:     /* consume_comment()
cannam@150:      *
cannam@150:      * Advance comments (c-style inline and multiline).
cannam@150:      */
cannam@150:     bool consume_comment() {
cannam@150:       bool comment_found = false;
cannam@150:       if (str[i] == '/') {
cannam@150:         i++;
cannam@150:         if (i == str.size())
cannam@242:           return fail("unexpected end of input after start of comment", false);
cannam@150:         if (str[i] == '/') { // inline comment
cannam@150:           i++;
cannam@242:           // advance until next line, or end of input
cannam@242:           while (i < str.size() && str[i] != '\n') {
cannam@150:             i++;
cannam@150:           }
cannam@150:           comment_found = true;
cannam@150:         }
cannam@150:         else if (str[i] == '*') { // multiline comment
cannam@150:           i++;
cannam@150:           if (i > str.size()-2)
cannam@242:             return fail("unexpected end of input inside multi-line comment", false);
cannam@150:           // advance until closing tokens
cannam@150:           while (!(str[i] == '*' && str[i+1] == '/')) {
cannam@150:             i++;
cannam@150:             if (i > str.size()-2)
cannam@150:               return fail(
cannam@242:                 "unexpected end of input inside multi-line comment", false);
cannam@150:           }
cannam@150:           i += 2;
cannam@150:           comment_found = true;
cannam@150:         }
cannam@150:         else
cannam@242:           return fail("malformed comment", false);
cannam@150:       }
cannam@150:       return comment_found;
cannam@150:     }
cannam@150: 
cannam@150:     /* consume_garbage()
cannam@150:      *
cannam@150:      * Advance until the current character is non-whitespace and non-comment.
cannam@150:      */
cannam@150:     void consume_garbage() {
cannam@150:       consume_whitespace();
cannam@150:       if(strategy == JsonParse::COMMENTS) {
cannam@150:         bool comment_found = false;
cannam@150:         do {
cannam@150:           comment_found = consume_comment();
cannam@242:           if (failed) return;
cannam@150:           consume_whitespace();
cannam@150:         }
cannam@150:         while(comment_found);
cannam@150:       }
cannam@150:     }
cannam@150: 
cannam@150:     /* get_next_token()
cannam@150:      *
cannam@150:      * Return the next non-whitespace character. If the end of the input is reached,
cannam@150:      * flag an error and return 0.
cannam@150:      */
cannam@150:     char get_next_token() {
cannam@150:         consume_garbage();
cannam@242:         if (failed) return (char)0;
cannam@150:         if (i == str.size())
cannam@242:             return fail("unexpected end of input", (char)0);
cannam@150: 
cannam@150:         return str[i++];
cannam@150:     }
cannam@150: 
cannam@150:     /* encode_utf8(pt, out)
cannam@150:      *
cannam@150:      * Encode pt as UTF-8 and add it to out.
cannam@150:      */
cannam@150:     void encode_utf8(long pt, string & out) {
cannam@150:         if (pt < 0)
cannam@150:             return;
cannam@150: 
cannam@150:         if (pt < 0x80) {
cannam@150:             out += static_cast<char>(pt);
cannam@150:         } else if (pt < 0x800) {
cannam@150:             out += static_cast<char>((pt >> 6) | 0xC0);
cannam@150:             out += static_cast<char>((pt & 0x3F) | 0x80);
cannam@150:         } else if (pt < 0x10000) {
cannam@150:             out += static_cast<char>((pt >> 12) | 0xE0);
cannam@150:             out += static_cast<char>(((pt >> 6) & 0x3F) | 0x80);
cannam@150:             out += static_cast<char>((pt & 0x3F) | 0x80);
cannam@150:         } else {
cannam@150:             out += static_cast<char>((pt >> 18) | 0xF0);
cannam@150:             out += static_cast<char>(((pt >> 12) & 0x3F) | 0x80);
cannam@150:             out += static_cast<char>(((pt >> 6) & 0x3F) | 0x80);
cannam@150:             out += static_cast<char>((pt & 0x3F) | 0x80);
cannam@150:         }
cannam@150:     }
cannam@150: 
cannam@150:     /* parse_string()
cannam@150:      *
cannam@150:      * Parse a string, starting at the current position.
cannam@150:      */
cannam@150:     string parse_string() {
cannam@150:         string out;
cannam@150:         long last_escaped_codepoint = -1;
cannam@150:         while (true) {
cannam@150:             if (i == str.size())
cannam@150:                 return fail("unexpected end of input in string", "");
cannam@150: 
cannam@150:             char ch = str[i++];
cannam@150: 
cannam@150:             if (ch == '"') {
cannam@150:                 encode_utf8(last_escaped_codepoint, out);
cannam@150:                 return out;
cannam@150:             }
cannam@150: 
cannam@150:             if (in_range(ch, 0, 0x1f))
cannam@150:                 return fail("unescaped " + esc(ch) + " in string", "");
cannam@150: 
cannam@150:             // The usual case: non-escaped characters
cannam@150:             if (ch != '\\') {
cannam@150:                 encode_utf8(last_escaped_codepoint, out);
cannam@150:                 last_escaped_codepoint = -1;
cannam@150:                 out += ch;
cannam@150:                 continue;
cannam@150:             }
cannam@150: 
cannam@150:             // Handle escapes
cannam@150:             if (i == str.size())
cannam@150:                 return fail("unexpected end of input in string", "");
cannam@150: 
cannam@150:             ch = str[i++];
cannam@150: 
cannam@150:             if (ch == 'u') {
cannam@150:                 // Extract 4-byte escape sequence
cannam@150:                 string esc = str.substr(i, 4);
cannam@150:                 // Explicitly check length of the substring. The following loop
cannam@150:                 // relies on std::string returning the terminating NUL when
cannam@150:                 // accessing str[length]. Checking here reduces brittleness.
cannam@150:                 if (esc.length() < 4) {
cannam@150:                     return fail("bad \\u escape: " + esc, "");
cannam@150:                 }
cannam@242:                 for (size_t j = 0; j < 4; j++) {
cannam@150:                     if (!in_range(esc[j], 'a', 'f') && !in_range(esc[j], 'A', 'F')
cannam@150:                             && !in_range(esc[j], '0', '9'))
cannam@150:                         return fail("bad \\u escape: " + esc, "");
cannam@150:                 }
cannam@150: 
cannam@150:                 long codepoint = strtol(esc.data(), nullptr, 16);
cannam@150: 
cannam@150:                 // JSON specifies that characters outside the BMP shall be encoded as a pair
cannam@150:                 // of 4-hex-digit \u escapes encoding their surrogate pair components. Check
cannam@150:                 // whether we're in the middle of such a beast: the previous codepoint was an
cannam@150:                 // escaped lead (high) surrogate, and this is a trail (low) surrogate.
cannam@150:                 if (in_range(last_escaped_codepoint, 0xD800, 0xDBFF)
cannam@150:                         && in_range(codepoint, 0xDC00, 0xDFFF)) {
cannam@150:                     // Reassemble the two surrogate pairs into one astral-plane character, per
cannam@150:                     // the UTF-16 algorithm.
cannam@150:                     encode_utf8((((last_escaped_codepoint - 0xD800) << 10)
cannam@150:                                  | (codepoint - 0xDC00)) + 0x10000, out);
cannam@150:                     last_escaped_codepoint = -1;
cannam@150:                 } else {
cannam@150:                     encode_utf8(last_escaped_codepoint, out);
cannam@150:                     last_escaped_codepoint = codepoint;
cannam@150:                 }
cannam@150: 
cannam@150:                 i += 4;
cannam@150:                 continue;
cannam@150:             }
cannam@150: 
cannam@150:             encode_utf8(last_escaped_codepoint, out);
cannam@150:             last_escaped_codepoint = -1;
cannam@150: 
cannam@150:             if (ch == 'b') {
cannam@150:                 out += '\b';
cannam@150:             } else if (ch == 'f') {
cannam@150:                 out += '\f';
cannam@150:             } else if (ch == 'n') {
cannam@150:                 out += '\n';
cannam@150:             } else if (ch == 'r') {
cannam@150:                 out += '\r';
cannam@150:             } else if (ch == 't') {
cannam@150:                 out += '\t';
cannam@150:             } else if (ch == '"' || ch == '\\' || ch == '/') {
cannam@150:                 out += ch;
cannam@150:             } else {
cannam@150:                 return fail("invalid escape character " + esc(ch), "");
cannam@150:             }
cannam@150:         }
cannam@150:     }
cannam@150: 
cannam@150:     /* parse_number()
cannam@150:      *
cannam@150:      * Parse a double.
cannam@150:      */
cannam@150:     Json parse_number() {
cannam@150:         size_t start_pos = i;
cannam@150: 
cannam@150:         if (str[i] == '-')
cannam@150:             i++;
cannam@150: 
cannam@150:         // Integer part
cannam@150:         if (str[i] == '0') {
cannam@150:             i++;
cannam@150:             if (in_range(str[i], '0', '9'))
cannam@150:                 return fail("leading 0s not permitted in numbers");
cannam@150:         } else if (in_range(str[i], '1', '9')) {
cannam@150:             i++;
cannam@150:             while (in_range(str[i], '0', '9'))
cannam@150:                 i++;
cannam@150:         } else {
cannam@150:             return fail("invalid " + esc(str[i]) + " in number");
cannam@150:         }
cannam@150: 
cannam@150:         if (str[i] != '.' && str[i] != 'e' && str[i] != 'E'
cannam@150:                 && (i - start_pos) <= static_cast<size_t>(std::numeric_limits<int>::digits10)) {
cannam@150:             return std::atoi(str.c_str() + start_pos);
cannam@150:         }
cannam@150: 
cannam@150:         // Decimal part
cannam@150:         if (str[i] == '.') {
cannam@150:             i++;
cannam@150:             if (!in_range(str[i], '0', '9'))
cannam@150:                 return fail("at least one digit required in fractional part");
cannam@150: 
cannam@150:             while (in_range(str[i], '0', '9'))
cannam@150:                 i++;
cannam@150:         }
cannam@150: 
cannam@150:         // Exponent part
cannam@150:         if (str[i] == 'e' || str[i] == 'E') {
cannam@150:             i++;
cannam@150: 
cannam@150:             if (str[i] == '+' || str[i] == '-')
cannam@150:                 i++;
cannam@150: 
cannam@150:             if (!in_range(str[i], '0', '9'))
cannam@150:                 return fail("at least one digit required in exponent");
cannam@150: 
cannam@150:             while (in_range(str[i], '0', '9'))
cannam@150:                 i++;
cannam@150:         }
cannam@150: 
cannam@150:         return std::strtod(str.c_str() + start_pos, nullptr);
cannam@150:     }
cannam@150: 
cannam@150:     /* expect(str, res)
cannam@150:      *
cannam@150:      * Expect that 'str' starts at the character that was just read. If it does, advance
cannam@150:      * the input and return res. If not, flag an error.
cannam@150:      */
cannam@150:     Json expect(const string &expected, Json res) {
cannam@150:         assert(i != 0);
cannam@150:         i--;
cannam@150:         if (str.compare(i, expected.length(), expected) == 0) {
cannam@150:             i += expected.length();
cannam@150:             return res;
cannam@150:         } else {
cannam@150:             return fail("parse error: expected " + expected + ", got " + str.substr(i, expected.length()));
cannam@150:         }
cannam@150:     }
cannam@150: 
cannam@150:     /* parse_json()
cannam@150:      *
cannam@150:      * Parse a JSON object.
cannam@150:      */
cannam@150:     Json parse_json(int depth) {
cannam@150:         if (depth > max_depth) {
cannam@150:             return fail("exceeded maximum nesting depth");
cannam@150:         }
cannam@150: 
cannam@150:         char ch = get_next_token();
cannam@150:         if (failed)
cannam@150:             return Json();
cannam@150: 
cannam@150:         if (ch == '-' || (ch >= '0' && ch <= '9')) {
cannam@150:             i--;
cannam@150:             return parse_number();
cannam@150:         }
cannam@150: 
cannam@150:         if (ch == 't')
cannam@150:             return expect("true", true);
cannam@150: 
cannam@150:         if (ch == 'f')
cannam@150:             return expect("false", false);
cannam@150: 
cannam@150:         if (ch == 'n')
cannam@150:             return expect("null", Json());
cannam@150: 
cannam@150:         if (ch == '"')
cannam@150:             return parse_string();
cannam@150: 
cannam@150:         if (ch == '{') {
cannam@150:             map<string, Json> data;
cannam@150:             ch = get_next_token();
cannam@150:             if (ch == '}')
cannam@150:                 return data;
cannam@150: 
cannam@150:             while (1) {
cannam@150:                 if (ch != '"')
cannam@150:                     return fail("expected '\"' in object, got " + esc(ch));
cannam@150: 
cannam@150:                 string key = parse_string();
cannam@150:                 if (failed)
cannam@150:                     return Json();
cannam@150: 
cannam@150:                 ch = get_next_token();
cannam@150:                 if (ch != ':')
cannam@150:                     return fail("expected ':' in object, got " + esc(ch));
cannam@150: 
cannam@150:                 data[std::move(key)] = parse_json(depth + 1);
cannam@150:                 if (failed)
cannam@150:                     return Json();
cannam@150: 
cannam@150:                 ch = get_next_token();
cannam@150:                 if (ch == '}')
cannam@150:                     break;
cannam@150:                 if (ch != ',')
cannam@150:                     return fail("expected ',' in object, got " + esc(ch));
cannam@150: 
cannam@150:                 ch = get_next_token();
cannam@150:             }
cannam@150:             return data;
cannam@150:         }
cannam@150: 
cannam@150:         if (ch == '[') {
cannam@150:             vector<Json> data;
cannam@150:             ch = get_next_token();
cannam@150:             if (ch == ']')
cannam@150:                 return data;
cannam@150: 
cannam@150:             while (1) {
cannam@150:                 i--;
cannam@150:                 data.push_back(parse_json(depth + 1));
cannam@150:                 if (failed)
cannam@150:                     return Json();
cannam@150: 
cannam@150:                 ch = get_next_token();
cannam@150:                 if (ch == ']')
cannam@150:                     break;
cannam@150:                 if (ch != ',')
cannam@150:                     return fail("expected ',' in list, got " + esc(ch));
cannam@150: 
cannam@150:                 ch = get_next_token();
cannam@150:                 (void)ch;
cannam@150:             }
cannam@150:             return data;
cannam@150:         }
cannam@150: 
cannam@150:         return fail("expected value, got " + esc(ch));
cannam@150:     }
cannam@150: };
cannam@242: }//namespace {
cannam@150: 
cannam@150: Json Json::parse(const string &in, string &err, JsonParse strategy) {
cannam@150:     JsonParser parser { in, 0, err, false, strategy };
cannam@150:     Json result = parser.parse_json(0);
cannam@150: 
cannam@150:     // Check for any trailing garbage
cannam@150:     parser.consume_garbage();
cannam@242:     if (parser.failed)
cannam@242:         return Json();
cannam@150:     if (parser.i != in.size())
cannam@150:         return parser.fail("unexpected trailing " + esc(in[parser.i]));
cannam@150: 
cannam@150:     return result;
cannam@150: }
cannam@150: 
cannam@150: // Documented in json11.hpp
cannam@150: vector<Json> Json::parse_multi(const string &in,
cannam@242:                                std::string::size_type &parser_stop_pos,
cannam@150:                                string &err,
cannam@150:                                JsonParse strategy) {
cannam@150:     JsonParser parser { in, 0, err, false, strategy };
cannam@242:     parser_stop_pos = 0;
cannam@150:     vector<Json> json_vec;
cannam@150:     while (parser.i != in.size() && !parser.failed) {
cannam@150:         json_vec.push_back(parser.parse_json(0));
cannam@242:         if (parser.failed)
cannam@242:             break;
cannam@242: 
cannam@150:         // Check for another object
cannam@150:         parser.consume_garbage();
cannam@242:         if (parser.failed)
cannam@242:             break;
cannam@242:         parser_stop_pos = parser.i;
cannam@150:     }
cannam@150:     return json_vec;
cannam@150: }
cannam@150: 
cannam@150: /* * * * * * * * * * * * * * * * * * * *
cannam@150:  * Shape-checking
cannam@150:  */
cannam@150: 
cannam@150: bool Json::has_shape(const shape & types, string & err) const {
cannam@150:     if (!is_object()) {
cannam@150:         err = "expected JSON object, got " + dump();
cannam@150:         return false;
cannam@150:     }
cannam@150: 
cannam@150:     for (auto & item : types) {
cannam@150:         if ((*this)[item.first].type() != item.second) {
cannam@150:             err = "bad type for " + item.first + " in " + dump();
cannam@150:             return false;
cannam@150:         }
cannam@150:     }
cannam@150: 
cannam@150:     return true;
cannam@150: }
cannam@150: 
cannam@150: } // namespace json11