jstream.h

Go to the documentation of this file.

#ifndef JSTREAM_H_
#define JSTREAM_H_
 
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <string>
#include <string_view>
#include <vector>
#include <variant>
#include <assert.h>
 
// #include <charconv> // C++17
 
namespace jstream {
 
static inline std::vector<char> encode_json_string(std::string_view const &in)
{
    std::vector<char> ret;
    char const *ptr = in.data();
    char const *end = ptr + in.size();
    ret.reserve(end - ptr + 10);
    while (ptr < end) {
        int c = (unsigned char)*ptr;
        ptr++;
        switch (c) {
        case '\"': ret.push_back('\\'); ret.push_back('\"'); break;
        case '\\': ret.push_back('\\'); ret.push_back('\\'); break;
        case '\b': ret.push_back('\\'); ret.push_back('b'); break;
        case '\f': ret.push_back('\\'); ret.push_back('f'); break;
        case '\n': ret.push_back('\\'); ret.push_back('n'); break;
        case '\r': ret.push_back('\\'); ret.push_back('r'); break;
        case '\t': ret.push_back('\\'); ret.push_back('t'); break;
        default:
            if (c >= 0x20 && c < 0x7f) {
                ret.push_back(c);
            } else {
                uint32_t u = 0;
                if ((c & 0xe0) == 0xc0 && ptr < end) {
                    if ((ptr[0] & 0xc0) == 0x80) {
                        int d = (unsigned char)ptr[0];
                        u = ((c & 0x1f) << 6) | (d & 0x3f);
                    }
                } else if ((c & 0xf0) == 0xe0 && ptr + 1 < end) {
                    if ((ptr[0] & 0xc0) == 0x80 && (ptr[1] & 0xc0) == 0x80) {
                        int d = (unsigned char)ptr[0];
                        int e = (unsigned char)ptr[1];
                        u = ((c & 0x0f) << 12) | ((d & 0x3f) << 6) | (e & 0x3f);
                    }
                } else if ((c & 0xf8) == 0xf0 && ptr + 2 < end) {
                    if ((ptr[0] & 0xc0) == 0x80 && (ptr[1] & 0xc0) == 0x80 && (ptr[2] & 0xc0) == 0x80) {
                        int d = (unsigned char)ptr[0];
                        int e = (unsigned char)ptr[1];
                        int f = (unsigned char)ptr[2];
                        u = ((c & 0x0f) << 18) | ((d & 0x3f) << 12) | ((e & 0x3f) << 6) | (f & 0x3f);
                    }
                }
                if (u != 0) {
                    char tmp[20];
                    if (u >= 0x10000 && u < 0x110000) {
                        uint16_t h = (u - 0x10000) / 0x400 + 0xd800;
                        uint16_t l = (u - 0x10000) % 0x400 + 0xdc00;
                        sprintf(tmp, "\\u%04X\\u%04X", h, l);
                        ret.insert(ret.end(), tmp, tmp + 12);
                    } else {
                        sprintf(tmp, "\\u%04X", u);
                        ret.insert(ret.end(), tmp, tmp + 6);
                    }
                }
            }
        }
    }
    return ret;
}
 
class misc {
private:
    static double pow10_int(int exp)
    {
        // Pre‑computed powers for |exp| ≤ 16
        static const double tbl[] = {
            1e+00, 1e+01, 1e+02, 1e+03, 1e+04, 1e+05, 1e+06,
            1e+07, 1e+08, 1e+09, 1e+10, 1e+11, 1e+12, 1e+13,
            1e+14, 1e+15, 1e+16
        };
        if (exp >= 0 && exp < static_cast<int>(sizeof tbl / sizeof *tbl))
            return tbl[exp];
        if (exp <= 0 && exp > -static_cast<int>(sizeof tbl / sizeof *tbl))
            return 1.0 / tbl[-exp];
        // Rare case: delegate to libm
        return std::pow(10.0, exp);
    }
public:
    static double my_strtod(const char *nptr, char **endptr)
    {
        const char *s = nptr;
        bool sign = false;
        bool saw_digit = false;
        int frac_digits = 0;
        long exp_val = 0;
        bool exp_sign = false;
        double value = 0.0;
 
        // Skip leading white‑space
        while (std::isspace((unsigned char)*s)) ++s;
 
        // Parse optional sign
        if (*s == '+' || *s == '-') {
            if (*s == '-') sign = true;
            s++;
        }
 
        // Integer part
        while (std::isdigit((unsigned char)*s)) {
            saw_digit = true;
            value = value * 10.0 + (*s - '0');
            s++;
        }
 
        // Fractional part
        if (*s == '.') {
            s++;
            while (std::isdigit((unsigned char)*s)) {
                saw_digit = true;
                value = value * 10.0 + (*s - '0');
                s++;
                frac_digits++;
            }
        }
 
        // No digits at all -> conversion failure
        if (!saw_digit) {
            if (endptr) *endptr = const_cast<char *>(nptr);
            return 0.0;
        }
 
        // Exponent part
        if (*s == 'e' || *s == 'E') {
            s++;
            const char *exp_start = s;
            if (*s == '+' || *s == '-') {
                if (*s == '-') exp_sign = true;
                s++;
            }
            if (std::isdigit((unsigned char)*s)) {
                while (std::isdigit((unsigned char)*s)) {
                    exp_val = exp_val * 10 + (*s - '0');
                    s++;
                }
                if (exp_sign) {
                    exp_val = -exp_val;
                }
            } else {
                // Roll back if 'e' is not followed by a valid exponent
                s = exp_start - 1;
            }
        }
 
        // Scale by 10^(exponent − #fractional‑digits)
        int total_exp = exp_val - frac_digits;
        if (total_exp != 0) {
            value *= pow10_int(total_exp);
        }
 
        // Apply sign
        if (sign) {
            value = -value;
        }
 
        // Set errno on overflow/underflow
        if (!std::isfinite(value)) {
            // errno = ERANGE;
            value = sign ? -HUGE_VAL : HUGE_VAL;
        } else if (value == 0.0 && saw_digit && total_exp != 0) {
            // errno = ERANGE;  // underflow
        }
 
        // Report where parsing stopped
        if (endptr) *endptr = const_cast<char *>(s);
        return value;
    }
 
    static std::string format_double(double val, bool allow_nan)
    {
        int precision = 15;
        bool trim_zeros = true;
        bool plus = false;
 
        if (std::isnan(val)) {
            if (allow_nan) {
                return "NaN";
            }
            return {};
        }
        if (std::isinf(val)) {
            if (allow_nan) {
                bool sign = std::signbit(val);
                if (sign) {
                    return "-Infinity";
                } else {
                    return "Infinity";
                }
            }
            return {};
        }
 
        char *ptr, *end;
 
        char *dot = nullptr;
 
        bool sign = val < 0;
        if (sign) {
            val = -val;
        }
 
        double intval = floor(val);
        val -= intval;
 
        int intlen = 0;
        if (intval == 0) {
            ptr = end = (char *)alloca(precision + 10) + 5;
        } else {
            double t = intval;
            do {
                t = floor(t / 10);
                intlen++;
            } while (t != 0);
            ptr = end = (char *)alloca(intlen + precision + 10) + intlen + 5;
        }
 
        if (precision > 0) {
            dot = end;
            *end++ = '.';
            double v = val;
            int e = 0;
            while (v > 0 && v < 1) {
                v *= 10;
                e++;
            }
            while (v >= 1) {
                v /= 10;
                e--;
            }
            double add = 0.5;
            for (int i = 0; i < precision - e; i++) {
                add /= 10;
            }
            v += add;
            double t = floor(v);
            intval += t;
            v -= t;
            int i = 0;
            int n = intlen;
            int r = std::min(e, precision);
            while (i < r) {
                *end++ = '0';
                if (n != 0) {
                    n++;
                }
                i++;
            }
            while (i < precision) {
                if (n < 16) {
                    v *= 10;
                    double m = floor(v);
                    v -= m;
                    *end++ = (char)m + '0';
                } else {
                    *end++ = '0';
                }
                n++;
                i++;
            }
        } else {
            intval += floor(val + 0.5);
        }
 
        intlen = 0;
        double t = intval;
        do {
            t = floor(t / 10);
            intlen++;
        } while (t != 0);
 
        if (intval == 0) {
            *--ptr = '0';
        } else {
            double t = intval;
            for (int i = 0; i < intlen; i++) {
                t /= 10;
                double u = floor(t);
                *--ptr = (char)((t - u) * 10 + 0.49) + '0';
                t = u;
            }
        }
 
        if (sign) {
            *--ptr = '-';
        } else if (plus) {
            *--ptr = '+';
        }
 
        if (trim_zeros && dot) {
            while (dot < end) {
                char c = end[-1];
                if (c == '.') {
                    end--;
                    break;
                }
                if (c != '0') {
                    break;
                }
                end--;
            }
        }
 
        return std::string(ptr, end - ptr);
    }
};
 
enum StateType {
    // Symbols
    None = 0,
    Null,
    False,
    True,
    // States
    Key = 100,
    Comma,
    StartObject,
    EndObject,
    StartArray,
    EndArray,
    String,
    Number,
};
 
class Reader {
public:
    struct Error {
        std::string what_;
        std::string what() const { return what_; }
    };
private:
    static std::string to_stdstr(std::vector<char> const &vec)
    {
        if (!vec.empty()) {
            char const *begin = &vec[0];
            char const *end = begin + vec.size();
            return std::string(begin, end);
        }
        return std::string();
    }
 
    int scan_space(char const *begin, char const *end)
    {
        char const *ptr = begin;
        while (ptr < end) {
            if (std::isspace((unsigned char)*ptr)) {
                ptr++;
                continue;
            }
            if (d.allow_comment && *ptr == '/' && ptr + 1 < end) {
                if (ptr[1] == '/') {
                    ptr += 2;
                    while (ptr < end && *ptr != '\r' && *ptr != '\n') {
                        ptr++;
                    }
                    continue;
                }
                if (ptr[1] == '*') {
                    ptr += 2;
                    while (ptr + 1 < end) {
                        if (*ptr == '*' && ptr[1] == '/') {
                            ptr += 2;
                            break;
                        }
                        ptr++;
                    }
                    continue;
                }
            }
            break;
        }
        return ptr - begin;
    }
 
    int parse_symbol(char const *begin, char const *end, std::string *out)
    {
        char const *ptr = begin;
        ptr += scan_space(ptr, end);
        std::vector<char> vec;
        while (ptr < end) {
            if (!isalnum((unsigned char)*ptr) && *ptr != '_') break;
            vec.push_back(*ptr);
            ptr++;
        }
        if (ptr > begin && !vec.empty()) {
            *out = to_stdstr(vec);
            return ptr - begin;
        }
        out->clear();
        return 0;
    }
 
    int parse_number(char const *begin, char const *end, double *out)
    {
        *out = 0;
        char const *ptr = begin;
        ptr += scan_space(ptr, end);
 
        std::vector<char> vec;
 
        if (d.allow_hexadicimal) {
            char const *p = ptr;
            bool sign = false;
            if (p + 1 < end && *p == '-') {
                p++;
                sign = true;
            }
            if (p + 1 < end && *p == '0' && (p[1] == 'x' || p[1] == 'X')) {
                p += 2;
                while (p < end && isxdigit((unsigned char)*p)) {
                    vec.push_back(*p);
                    p++;
                }
                vec.push_back(0);
                long long v = strtoll(vec.data(), nullptr, 16);
                *out = sign ? -v : v;
                return p - begin;
            }
        }
 
        if (d.allow_special_constant) {
            char const *p = ptr;
            bool sign = false;
            if (p < end && *p == '-') {
                p++;
                sign = true;
            }
            while (p < end && isalpha((unsigned char)*p)) {
                vec.push_back(*p);
                p++;
            }
            vec.push_back(0);
            if (strcmp(vec.data(), "Infinity") == 0) {
                ptr = p;
                *out = sign ? -INFINITY : INFINITY;
            } else if (strcmp(vec.data(), "NaN") == 0) {
                ptr = p;
                *out = NAN;
            }
            if (ptr > begin) {
                return ptr - begin;
            }
        }
 
        while (ptr < end) {
            char c = *ptr;
            if (isdigit((unsigned char)c) || c == '.' || c == '+' || c == '-' || c == 'e' || c == 'E') {
                // thru
            } else {
                break;
            }
            vec.push_back(c);
            ptr++;
        }
        vec.push_back(0);
 
        // use my_strtod instead of strtod, because strtod is locale dependent
        // *out = strtod(vec.data(), nullptr);
        // std::from_chars(vec.data(), vec.data() + vec.size(), *out); // C++17
        *out = misc::my_strtod(vec.data(), nullptr);
 
        return ptr - begin;
    }
 
    int parse_string(char const *begin, char const *end, std::string *out)
    {
        char const *ptr = begin;
        ptr += scan_space(ptr, end);
        if (*ptr == '\"') {
            ptr++;
            std::vector<char> vec;
            while (ptr < end) {
                if (*ptr == '\"') {
                    *out = to_stdstr(vec);
                    ptr++;
                    return ptr - begin;
                } else if (*ptr == '\\') {
                    ptr++;
                    if (ptr < end) {
                        auto push = [&](char c){ vec.push_back(c); ptr++;};
                        switch (*ptr) {
                        case 'b': push('\b'); break;
                        case 'n': push('\n'); break;
                        case 'r': push('\r'); break;
                        case 'f': push('\f'); break;
                        case 't': push('\t'); break;
                        case 'v': push('\v'); break;
                        case '\\':
                        case '\"':
                            push(*ptr);
                            break;
                        case 'u':
                            ptr++;
                            if (ptr + 3 < end) {
                                char tmp[5];
                                tmp[0] = ptr[0];
                                tmp[1] = ptr[1];
                                tmp[2] = ptr[2];
                                tmp[3] = ptr[3];
                                tmp[4] = 0;
                                ptr += 4;
                                uint32_t unicode = (uint32_t)strtol(tmp, nullptr, 16);
                                if (unicode >= 0xd800 && unicode < 0xdc00) {
                                    if (ptr + 5 < end && ptr[0] == '\\' && ptr[1] == 'u') {
                                        tmp[0] = ptr[2];
                                        tmp[1] = ptr[3];
                                        tmp[2] = ptr[4];
                                        tmp[3] = ptr[5];
                                        uint32_t surrogate = (uint32_t)strtol(tmp, nullptr, 16);
                                        if (surrogate >= 0xdc00 && surrogate < 0xe000) {
                                            ptr += 6;
                                            unicode = ((unicode - 0xd800) << 10) + (surrogate - 0xdc00) + 0x10000;
                                        }
                                    }
                                }
                                if (unicode < (1 << 7)) {
                                    vec.push_back(unicode & 0x7f);
                                } else if (unicode < (1 << 11)) {
                                    vec.push_back(((unicode >> 6) & 0x1f) | 0xc0);
                                    vec.push_back((unicode & 0x3f) | 0x80);
                                } else if (unicode < (1 << 16)) {
                                    vec.push_back(((unicode >> 12) & 0x0f) | 0xe0);
                                    vec.push_back(((unicode >> 6) & 0x3f) | 0x80);
                                    vec.push_back((unicode & 0x3f) | 0x80);
                                } else if (unicode < (1 << 21)) {
                                    vec.push_back(((unicode >> 18) & 0x07) | 0xf0);
                                    vec.push_back(((unicode >> 12) & 0x3f) | 0x80);
                                    vec.push_back(((unicode >> 6) & 0x3f) | 0x80);
                                    vec.push_back((unicode & 0x3f) | 0x80);
                                }
                            }
                            break;
                        default:
                            vec.push_back(*ptr);
                            ptr++;
                            break;
                        }
                    }
                } else {
                    vec.push_back(*ptr);
                    ptr++;
                }
            }
        }
        return 0;
    }
private:
    struct StateItem {
        StateType type = None;
        char const *ptr = nullptr;
        StateItem() = default;
        StateItem(StateType type, char const *ptr = nullptr)
            : type(type)
            , ptr(ptr)
        {
        }
    };
    struct ParserData {
        char const *begin = nullptr;
        char const *end = nullptr;
        char const *ptr = nullptr;
        std::vector<StateItem> states;
        bool hold = false;
        std::string key;
        std::string string;
        double number = 0;
        bool is_array = false;
        bool allow_comment = false;
        bool allow_ambiguous_comma = false;
        bool allow_unquoted_key = false;
        bool allow_hexadicimal = false;
        bool allow_special_constant = false;
        std::vector<std::string> depth;
        std::vector<int> depth_stack;
        StateItem last_state;
        std::vector<Error> errors;
    };
    ParserData d;
 
    void push_error(std::string const &what)
    {
        d.states.clear();
 
        Error err;
        err.what_ = what;
        d.errors.push_back(err);
    }
 
    void push_state(StateItem s)
    {
        if (state() == Key || state() == Comma || state() == EndObject) {
            d.states.pop_back();
        }
        d.states.push_back(s);
 
        if (isarray()) {
            d.key.clear();
        }
 
        switch (s.type) {
        case StartArray:
            d.is_array = true;
            break;
        case StartObject:
        case Key:
            d.is_array = false;
            break;
        }
    }
 
    bool pop_state()
    {
        bool f = false;
        if (!d.states.empty()) {
            d.last_state = d.states.back();
            d.states.pop_back();
            size_t i = d.states.size();
            while (i > 0) {
                i--;
                auto s = d.states[i];
                if (s.type == StartArray) {
                    d.is_array = true;
                    break;
                }
                if (s.type == StartObject || s.type == Key) {
                    d.is_array = false;
                    break;
                }
            }
            f = true;
            if (state() == Key) {
                d.states.pop_back();
            }
        }
        d.key.clear();
        return f;
    }
 
    void parse(char const *begin, char const *end)
    {
        reset();
        d = {};
        d.begin = begin;
        d.end = end;
        d.ptr = d.begin;
    }
 
    void parse(std::string_view const &sv)
    {
        parse(sv.data(), sv.data() + sv.size());
    }
 
    void parse(char const *ptr, int len = -1)
    {
        if (len < 0) {
            len = strlen(ptr);
        }
        parse(ptr, ptr + len);
    }
 
    bool _internal_next()
    {
        while (d.ptr < d.end) {
            {
                auto n = scan_space(d.ptr, d.end);;
                if (n > 0) {
                    d.ptr += n;
                    continue;
                }
            }
            if (*d.ptr == '}') {
                d.ptr++;
                d.string.clear();
                std::string key;
                if (!d.depth.empty()) {
                    key = d.depth.back();
                    auto n = key.size();
                    if (n > 0) {
                        if (key[n - 1] == '{') {
                            key = key.substr(0, n - 1);
                        }
                    }
                    d.depth.pop_back();
                }
                while (1) {
                    bool f = (state() == StartObject);
                    if (!pop_state()) break;
                    if (f) {
                        push_state(EndObject);
                        d.key = key;
                        return true;
                    }
                }
            }
            if (*d.ptr == ']') {
                d.ptr++;
                d.string.clear();
                std::string key;
                if (!d.depth.empty()) {
                    key = d.depth.back();
                    auto n = key.size();
                    if (n > 0) {
                        if (key[n - 1] == '[') {
                            key = key.substr(0, n - 1);
                        }
                    }
                    d.depth.pop_back();
                }
                while (1) {
                    bool f = (state() == StartArray);
                    if (!pop_state()) break;
                    if (f) {
                        push_state(EndArray);
                        d.key = key;
                        return true;
                    }
                }
            }
            if (*d.ptr == ',') {
                d.ptr++;
                if (state() == Key) {
                    push_state(Null);
                    return true;
                }
                d.ptr += scan_space(d.ptr, d.end);
                if (isobject() || isvalue()) {
                    pop_state();
                }
                push_state(Comma);
                if (d.allow_ambiguous_comma) {
                    continue;
                } else {
                    // if not allow_ambiguous_comma, fall through
                }
            }
            if (*d.ptr == '{') {
                char const *p = d.ptr++;
                if (state() != Key) {
                    d.key.clear();
                    d.string.clear();
                }
                d.depth.push_back(d.key + '{');
                push_state({StartObject, p});
                return true;
            }
            if (*d.ptr == '[') {
                char const *p = d.ptr++;
                if (state() != Key) {
                    d.key.clear();
                    d.string.clear();
                }
                d.depth.push_back(d.key + '[');
                push_state({StartArray, p});
                return true;
            }
            if (*d.ptr == '\"') {
                switch (state()) {
                case None:
                case StartObject:
                case StartArray:
                case Key:
                case Comma:
                    // thru
                    break;
                default:
                    if (d.allow_ambiguous_comma) {
                        break; // consider as a virtual comma is exists
                    }
                    push_error("unexpected double quote");
                    return false;
                }
 
                auto n = parse_string(d.ptr, d.end, &d.string);
                if (n > 0) {
                    if (isarray()) {
                        d.ptr += n;
                        push_state(String);
                        return true;
                    }
                    if (state() == Key) {
                        d.ptr += n;
                        push_state(String);
                        return true;
                    }
                    n += scan_space(d.ptr + n, d.end);
                    if (d.ptr[n] == ':') {
                        d.ptr += n + 1;
                        d.key = d.string;
                        push_state(Key);
                        return true;
                    }
                }
            }
            if (state() == Key || isarray()) {
                auto n = parse_number(d.ptr, d.end, &d.number);
                if (n > 0) {
                    d.string.assign(d.ptr, n);
                    d.ptr += n;
                    push_state(Number);
                    return true;
                }
                if (isalpha((unsigned char)*d.ptr)) {
                    auto n = parse_symbol(d.ptr, d.end, &d.string);
                    if (n > 0) {
                        if (state() == Key || state() == Comma || state() == StartArray) {
                            d.ptr += n;
                            if (d.string == "false") {
                                push_state(False);
                                return true;
                            }
                            if (d.string == "true") {
                                push_state(True);
                                return true;
                            }
                            if (d.string == "null") {
                                push_state(Null);
                                return true;
                            }
                        }
                    }
                }
            } else if (d.allow_unquoted_key) {
                auto n = parse_symbol(d.ptr, d.end, &d.string);
                if (n > 0) {
                    n += scan_space(d.ptr + n, d.end);
                    if (d.ptr[n] == ':') {
                        d.ptr += n + 1;
                        d.key = d.string;
                        push_state(Key);
                        return true;
                    }
                }
            }
            push_error("syntax error");
            break;
        }
        return false;
    }
public:
    Reader(std::string_view const &sv)
    {
        parse(sv);
    }
    Reader(char const *begin, char const *end)
    {
        parse(begin, end);
    }
    Reader(char const *ptr, int len = -1)
    {
        parse(ptr, len);
    }
    void allow_comment(bool allow)
    {
        d.allow_comment = allow;
    }
    void allow_ambiguous_comma(bool allow)
    {
        d.allow_ambiguous_comma = allow;
    }
    void allow_unquoted_key(bool allow)
    {
        d.allow_unquoted_key = allow;
    }
    void allow_hexadicimal(bool allow)
    {
        d.allow_hexadicimal = allow;
    }
    void allow_special_constant(bool allow)
    {
        d.allow_special_constant = allow;
    }
    void reset()
    {
        d.errors.clear();
    }
    void hold()
    {
        d.hold = true;
    }
    void nest()
    {
        d.depth_stack.push_back(depth());
    }
    bool next()
    {
        if (d.hold) {
            d.hold = false;
            return true;
        }
        if (_internal_next()) {
            if (d.depth_stack.empty()) return true;
            if (this->depth() >= d.depth_stack.back()) {
                return true;
            }
            d.depth_stack.pop_back();
            hold();
        }
        return false;
    }
 
    StateType state() const
    {
        return d.states.empty() ? None : d.states.back().type;
    }
 
    bool has_error() const
    {
        return !d.errors.empty();
    }
 
    std::vector<Error> const &errors() const
    {
        return d.errors;
    }
 
    bool is_start_object() const
    {
        return state() == StartObject;
    }
 
    bool is_end_object() const
    {
        return state() == EndObject;
    }
 
    bool is_start_array() const
    {
        return state() == StartArray;
    }
 
    bool is_end_array() const
    {
        return state() == EndArray;
    }
 
    bool isobject() const
    {
        switch (state()) {
        case StartObject:
        case StartArray:
            return true;
        case EndObject:
        case EndArray:
            if (d.states.size() > 1) {
                auto s = d.states[d.states.size() - 2];
                switch (s.type) {
                case StartObject:
                case StartArray:
                    return true;
                }
            }
            break;
        }
        return false;
    }
 
    bool isvalue() const
    {
        switch (state()) {
        case String:
        case Number:
        case Null:
        case False:
        case True:
            return true;
        }
        return false;
    }
 
    std::string key() const
    {
        return d.key;
    }
 
    std::string string() const
    {
        return d.string;
    }
 
    StateType symbol() const
    {
        StateType s = state();
 
        switch (s) {
        case Null:
        case False:
        case True:
            return s;
        }
        return None;
    }
 
    bool isnull() const
    {
        return symbol() == Null;
    }
 
    bool isfalse() const
    {
        return symbol() == False;
    }
 
    bool istrue() const
    {
        return symbol() == True;
    }
 
    bool isnumber() const
    {
        return state() == Number;
    }
 
    bool isstring() const
    {
        return state() == String;
    }
 
    double number() const
    {
        return d.number;
    }
 
    bool isarray() const
    {
        return d.is_array;
    }
 
    int depth() const
    {
        return d.depth.size();
    }
 
    std::string path() const
    {
        std::string path;
        for (std::string const &s : d.depth) {
            path += s;
        }
        if (state() == jstream::StartObject || state() == jstream::StartArray) {
            return path;
        }
        return path + d.key;
    }
 
    std::string_view raw()
    {
        if (d.last_state.ptr) {
            size_t n = d.ptr - d.last_state.ptr;
            return std::string_view(d.last_state.ptr, n);
        }
        return {};
    }
 
    bool match(char const *path, std::vector<std::string> *vals = nullptr, bool clear = true) const
    {
        if (vals && clear) {
            vals->clear();
        }
        if (!isobject() && !isarray() && !isvalue()) return false;
        size_t i;
        for (i = 0; i < d.depth.size(); i++) {
            std::string const &s = d.depth[i];
            if (s.empty()) break;
            if (path[0] == '*' && path[1] == '*' && path[2] == 0) {
                return true;
            }
            if (path[0] == '*' && s.c_str()[s.size() - 1] == '{') {
                if (path[1] == 0) {
                    if (state() == StartObject) {
                        if (i + 1 == d.depth.size()) {
                            if (vals) {
                                std::string t;
                                while (i < d.depth.size()) {
                                    t += d.depth[i];
                                    i++;
                                }
                                if (isvalue()) {
                                    t += d.key;
                                }
                                vals->push_back(t);
                            }
                            return true;
                        }
                    }
                    return false;
                } else if (path[1] == '{') {
                    path += 2;
                    continue;
                }
            }
            if (strncmp(path, s.c_str(), s.size()) != 0) return false;
            path += s.size();
        }
        if (path[0] == '*' && path[1] == '*' && path[2] == 0) {
            return true;
        }
        if (path[0] == '*') {
            if (path[1] == 0 && i == d.depth.size() && (isvalue() || state() == EndObject || state() == EndArray)) {
                if (vals) {
                    std::string t;
                    if (isvalue()) {
                        t = d.key;
                    }
                    vals->push_back(t);
                }
                return true;
            }
            return false;
        }
        if (path == d.key) {
            if (vals && isvalue()) {
                vals->push_back(string());
            }
            return true;
        }
        return false;
    }
 
    bool match_start_object(char const *path) const
    {
        return state() == StartObject && match(path);
    }
 
    bool match_end_object(char const *path) const
    {
        return state() == EndObject && match(path);
    }
 
    bool match_start_array(char const *path) const
    {
        return state() == StartArray && match(path);
    }
 
    bool match_end_array(char const *path) const
    {
        return state() == EndArray && match(path);
    }
};
 
class Writer {
protected:
    void print(char const *p, int n)
    {
        if (output_fn) {
            output_fn(p, n);
        } else {
            for (size_t i = 0; i < n; i++) {
                putchar(p[i]);
            }
        }
    }
 
    void print(char c)
    {
        print(&c, 1);
    }
 
    void print(char const *p)
    {
        print(p, strlen(p));
    }
 
    void print(std::string const &s)
    {
        print(s.c_str(), s.size());
    }
private:
    std::vector<int> stack;
    std::function<void (char const *p, int n)> output_fn;
 
    bool enable_indent_ = true;
    bool enable_newline_ = true;
    bool allow_nan_ = false;
 
    void print_newline()
    {
        if (!enable_newline_) return;
 
        print('\n');
    }
 
    void print_indent()
    {
        if (!enable_indent_) return;
 
        size_t n = stack.size() - 1;
        for (size_t i = 0; i < n; i++) {
            print(' ');
            print(' ');
        }
    }
 
    bool print_number(double v)
    {
        std::string s = misc::format_double(v, allow_nan_);
        if (s.empty()) {
            print("null");
            return false;
        }
        print(s);
        return true;
    }
 
    void print_string(std::string const &s)
    {
        std::vector<char> buf = encode_json_string(s);
 
        print('\"');
        if (!buf.empty()) {
            print(buf.data(), buf.size());
        }
        print('\"');
    }
 
    bool print_value(std::string const &name, std::function<bool ()> const &fn)
    {
        print_name(name);
 
        bool ok = fn();
 
        if (!stack.empty()) stack.back()++;
 
        return ok;
    }
 
    void print_object(std::string const &name = {}, std::function<void ()> const &fn = {})
    {
        print_name(name);
        print('{');
        stack.push_back(0);
        if (fn) {
            fn();
            end_object();
        }
    }
 
    void print_array(std::string const &name = {}, std::function<void ()> const &fn = {})
    {
        print_name(name);
        print('[');
        stack.push_back(0);
        if (fn) {
            fn();
            end_array();
        }
    }
 
    void end_block()
    {
        print_newline();
        if (!stack.empty()) {
            stack.pop_back();
            if (!stack.empty()) stack.back()++;
        }
        print_indent();
    }
public:
    Writer(std::function<void (char const *p, int n)> fn = {})
    {
        output_fn = fn;
        stack.push_back(0);
    }
 
    ~Writer()
    {
        if (!stack.empty() && stack.front() > 0) {
            print_newline();
        }
    }
 
    void enable_indent(bool enabled)
    {
        enable_indent_ = enabled;
    }
 
    void enable_newline(bool enabled)
    {
        enable_newline_ = enabled;
    }
 
    void allow_nan(bool allow)
    {
        allow_nan_ = allow;
    }
 
    void print_name(std::string const &name)
    {
        if (!stack.empty()) {
            if (stack.back() > 0) {
                print(',');
            }
        }
        if (stack.size() > 1) {
            print_newline();
        }
        print_indent();
        if (!name.empty()) {
            print_string(name);
            print(':');
            if (enable_indent_) {
                print(' ');
            }
        }
    }
 
    void start_object(std::string const &name = {})
    {
        print_object(name);
    }
 
    void end_object()
    {
        end_block();
        print('}');
    }
 
    void object(std::string const &name, std::function<void ()> const &fn)
    {
        print_object(name, fn);
    }
 
    void start_array(std::string const &name = {})
    {
        print_array(name, {});
    }
 
    void end_array()
    {
        end_block();
        print(']');
    }
 
    void array(std::string const &name, std::function<void ()> const &fn)
    {
        print_array(name, fn);
    }
 
    bool number(std::string const &name, double v)
    {
        return print_value(name, [&](){
            return print_number(v);
        });
    }
 
    void number(double v)
    {
        number({}, v);
    }
 
    void string(std::string const &name, std::string const &s)
    {
        print_value(name, [&](){
            print_string(s);
            return true;
        });
    }
 
    void string(std::string const &s)
    {
        string({}, s);
    }
 
    void symbol(std::string const &name, StateType v)
    {
        print_value(name, [&](){
            switch (v) {
            case False:
                print("false");
                break;
            case True:
                print("true");
                break;
            default:
                print("null");
            }
            return true;
        });
    }
 
    void boolean(std::string const &name, bool b)
    {
        symbol(name, b ? True : False);
    }
 
    void null()
    {
        symbol({}, Null);
    }
};
 
typedef std::nullptr_t null_t;
constexpr std::nullptr_t null = nullptr;
 
struct Array;
struct KeyValue;
typedef std::vector<KeyValue> _Object;
typedef std::variant<null_t, bool, double, std::string, _Object, Array> Variant;
struct Array {
    std::vector<Variant> a;
    size_t size() const
    {
        return a.size();
    }
    bool empty() const
    {
        return a.empty();
    }
    Variant &operator[](size_t i)
    {
        return a[i];
    }
    Variant const &operator[](size_t i) const
    {
        return a[i];
    }
    template <typename T> T &get(size_t i)
    {
        assert(i < a.size());
        return std::get<T>(a[i]);
    }
    template <typename T> T const &get(size_t i) const
    {
        assert(i < a.size());
        return std::get<T>(a[i]);
    }
    void push_back(Variant const &v)
    {
        a.push_back(v);
    }
    Array &operator += (Variant const &v)
    {
        push_back(v);
        return *this;
    }
};
struct KeyValue {
    std::string key;
    Variant value;
    KeyValue() = default;
    KeyValue(std::string const &k, Variant const &v)
        : key(k), value(v)
    {
    }
};
struct VariantRef {
    Variant *var;
    VariantRef(Variant &v)
        : var(&v)
    {
    }
    void operator = (Variant const &v)
    {
        *var = v;
    }
    operator Variant &()
    {
        return *var;
    }
};
struct Object {
    _Object *p;
    Object() : p(nullptr)
    {
    }
    Object(_Object &o)
        : p(&o)
    {
    }
    Object(Variant &v)
    {
        if (!std::holds_alternative<_Object>(v)) {
            v = _Object();
        }
        p = &std::get<_Object>(v);
    }
    size_t size() const
    {
        return p ? p->size() : 0;
    }
    bool empty() const
    {
        return size() == 0;
    }
    Variant *find(std::string const &key)
    {
        if (p) {
            for (auto &kv : *p) {
                if (kv.key == key) {
                    return &kv.value;
                }
            }
        }
        return nullptr;
    }
    Variant const *find(std::string const &key) const
    {
        return const_cast<Object *>(this)->find(key);
    }
    Variant &value(std::string const &key)
    {
        Variant *v = find(key);
        assert(v);
        return *v;
    }
    Variant const &value(std::string const &key) const
    {
        return const_cast<Object *>(this)->value(key);
    }
    template <typename T> T const &get(std::string const &key) const
    {
        Variant const *v = find(key);
        assert(v);
        return std::get<T>(*v);
    }
    VariantRef operator [] (std::string const &key)
    {
        p->emplace_back(key, Variant());
        return p->back().value;
    }
};
 
static inline bool is_null(Variant const &v)
{
    return std::holds_alternative<null_t>(v);
}
static inline bool is_boolean(Variant const &v)
{
    return std::holds_alternative<bool>(v);
}
static inline bool is_number(Variant const &v)
{
    return std::holds_alternative<double>(v);
}
static inline bool is_string(Variant const &v)
{
    return std::holds_alternative<std::string>(v);
}
static inline bool is_object(Variant const &v)
{
    return std::holds_alternative<_Object>(v);
}
static inline bool is_array(Variant const &v)
{
    return std::holds_alternative<Array>(v);
}
static inline bool is_nan(Variant const &v)
{
    return std::holds_alternative<double>(v) && std::isnan(std::get<double>(v));
}
static inline bool is_infinite(Variant const &v)
{
    return std::holds_alternative<double>(v) && std::isinf(std::get<double>(v));
}
static inline Array &arr(Array &a)
{
    return a;
}
static inline Array &arr(Variant &v)
{
    if (!std::holds_alternative<Array>(v)) {
        v = Array();
    }
    return std::get<Array>(v);
}
static inline Object obj(Variant &v)
{
    if (!std::holds_alternative<_Object>(v)) {
        v = _Object();
    }
    return Object(std::get<_Object>(v));
}
 
static inline Variant var(jstream::Reader const &reader)
{
    if (reader.isnull()) {
        return null;
    } else if (reader.isfalse()) {
        return false;
    } else if (reader.istrue()) {
        return true;
    } else if (reader.isnumber()) {
        return reader.number();
    } else if (reader.isstring()) {
        return reader.string();
    }
    return null;
}
 
using std::get;
 
} // namespace jstream
 
#endif // JSTREAM_H_