// jalapenojson.h — single-header zero-copy parser.
//
// A document opens with a version line, then one or more schema lines, then
// its row count. The version line must say exactly the version this parser
// implements: one version of the format is in circulation, so there is no
// older layout to recognise and no version gate below this line.
//
// A type that is a number names a schema: the value is a nested list of rows
// of that schema. jj_parse does not descend into one -- it records the value as
// the bytes it is, costing nothing at parse time, exactly as it does for every
// other type. jj_sub() parses one when the caller asks for it, so no document
// can drive this parser off the stack, however deep its lists go.
//
// The format sets no limit on anything: not on rows, columns, schemas, the
// depth of nesting, a column's size or a value's length. Neither does this
// parser. What bounds a document here is the memory holding it, and a count or
// length is a ptrdiff_t, which is as large as any object can be.
//
// Every length in the input is validated against the end of the buffer before
// it is used, so a corrupt or hostile document makes jj_parse return an error
// instead of reading out of bounds. The parser never requires the buffer to be
// NUL-terminated: `len` is the only authority on where the input stops.
//
// Every column but a list column declares its size in bytes, so a value
// carries no length and the parser never scans for one. A schema with no list
// column therefore has a constant row length, and jj_parse builds no index at
// all for it: jj_field works the address out from the row number. That is the
// whole point of the format -- a document of any size costs one arithmetic
// step per value read, and nothing per value skipped.
//
// Exactly one '\n' follows the last column of each row. A sized value is raw
// bytes that may itself begin with a newline, so the separator is what says
// the row ended, and it is required rather than cosmetic.
//
// Usage:
//   jj_doc doc;
//   int rc = jj_parse(buf, len, &doc);      // buf must outlive doc (zero-copy)
//   if (rc != JJ_OK) { fprintf(stderr, "%s\n", jj_strerror(rc)); ... }
//   jj_field(&doc, r, c) -> jj_val* (ptr,len); ints via jj_int(jj_field(&doc,r,c))
//   jj_free(&doc);                          // safe after a failed parse too
//
// jj_parse mutates `buf`: column names are NUL-terminated in place.
#ifndef JALAPENOJSON_H
#define JALAPENOJSON_H
#include <limits.h>
#include <errno.h>
#include <float.h>
#include <math.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

// There is no column limit. The format does not define one, and Python and
// JavaScript never had one, so a fixed cap here meant they could write a
// document this parser refused to read. col_names/col_types grow instead. The
// input bounds the count on its own: a column costs at least 4 bytes ("#a:1"),
// so a header cannot declare more columns than it has room to spell.
#define JJ_COLS_INIT 8

// Nor is there a schema limit. A list column names its schema by number, and
// the number may run to as many digits as it needs, so the schema table grows
// the way the column arrays do. It used to be a fixed array of nine, because a
// reference was a single digit.
#define JJ_SCHEMAS_INIT 4

// The one version this parser writes and reads.
#define JJ_VERSION_MAJOR 0
#define JJ_VERSION_MINOR 6

// The break byte. A value shorter than its column is followed by one, and the
// value ends there: whatever the rest of the field holds is not part of it and
// is never looked at. A value that exactly fills its column carries none. So
// "Bo" and "Bo   " in the same s:5 column are different values, which is what
// a break byte buys over padding with spaces. No value may contain one, which
// costs nothing: no number, boolean, date or string grammar can hold a NUL.
//
// 'b' is the one type with no byte to reserve, since a b value may be any
// bytes at all, so a b column is not padded and every value in it is exactly
// the column's size.
#define JJ_BREAK '\0'
#define jj_is_padded(tag) ((tag) != 'b')

// How long the value in a padded field of `size` bytes at `p` is: up to its
// first break byte, or the whole field when it has none.
static inline ptrdiff_t jj__value_len(const char *p, ptrdiff_t size) {
    const char *brk = (const char *)memchr(p, JJ_BREAK, (size_t)size);
    return brk ? brk - p : size;
}

// A column's size has no upper bound in the format, and neither does a row.
// They used to stop at 9007199254740991, the largest whole number JavaScript
// holds exactly, so that the three implementations agreed on which documents
// exist. They agree without it: a size is a claim about bytes, and the only
// question a reader ever asks of it is whether the rows it describes fit in
// the document it holds.
//
// So a size, and the offsets and strides summed from sizes, are long long and
// held at JJ__BEYOND, the largest one, when they are larger than that. No
// object is larger than PTRDIFF_MAX bytes, which is at most that, so no
// document can hold a row that long, and holding the number at the cap gives
// the same answer to that question as holding the number itself would: a
// schema declaring such a column is a valid schema whose rows can never
// appear. A document with none of them reads, and col_sizes says what its
// header declared, exactly, on every target.
//
// They are long long rather than ptrdiff_t because a long long is 64 bits on
// every target, where a ptrdiff_t is 32 on wasm32, and two sizes that each fit
// in 32 bits can add up past it: that once wrapped and sent jj_field outside
// the buffer. Adding them here saturates, so nothing wraps anywhere.
#define JJ__BEYOND LLONG_MAX

static inline long long jj__add(long long a, long long b) {
    return a > JJ__BEYOND - b ? JJ__BEYOND : a + b;
}

// The number a run of ASCII digits at *pp spells, held at JJ__BEYOND when it
// is larger. Advances *pp past the digits; the caller has already seen that
// there is at least one.
static inline long long jj__digits(char **pp, const char *end) {
    char *p = *pp;
    long long w = 0;
    for (; p < end && *p >= '0' && *p <= '9'; p++)
        w = w > (JJ__BEYOND - (*p - '0')) / 10 ? JJ__BEYOND : w * 10 + (*p - '0');
    *pp = p;
    return w;
}

enum {
    JJ_OK = 0,
    JJ_ERR_ARGS,        // NULL buffer/doc, or negative len
    JJ_ERR_TRUNCATED,   // input ends in the middle of something
    JJ_ERR_BADNUM,      // expected an ASCII integer, found something else
    JJ_ERR_RANGE,       // an integer too large for what it counts
    JJ_ERR_NEGLEN,      // negative row count or value length
    JJ_ERR_HEADER,      // malformed header line
    JJ_ERR_TOO_MANY_COLS,  // no longer returned; kept so the codes stay stable
    JJ_ERR_BADSEP,      // missing '\n' where the format requires one
    JJ_ERR_OVERFLOW,    // n_rows * n_cols (or its allocation) overflows
    JJ_ERR_NOMEM,
    JJ_ERR_TRAILING,    // bytes left over after the last row
    JJ_ERR_VERSION,     // malformed version line, or one this parser cannot read
    JJ_ERR_TOO_MANY_SCHEMAS,  // no longer returned; kept so the codes stay stable
    JJ_ERR_SCHEMA_REF,  // a list names a schema the document does not declare
    JJ_ERR_DUPCOL,      // a schema declares the same column name twice
    JJ_ERR_SIZE,        // a column with no size, a size that is not a positive
                        // integer, or a size on a list column
    JJ_ERR_UTF8,        // text that is not UTF-8: a column name, or an s value
                        // read through jj_str_checked
    JJ_ERR_BADBOOL      // a y value that is neither 1 nor 0
};

typedef struct { char *ptr; ptrdiff_t len; } jj_val;

typedef struct {
    ptrdiff_t n_cols;
    char **col_names;   // n_cols pointers into buffer, NUL-terminated in-place
    char *col_types;    // n_cols type tags, JJ_LIST on a list column
    ptrdiff_t *col_schemas;  // n_cols: the schema a list column's rows use,
                        // counting from 1, and 0 on every other column
    long long *col_sizes;  // n_cols sizes in bytes; 0 only on a list column
    long long *col_offs;   // n_cols byte offsets of a column inside a row
    long long stride;   // bytes per row, separator included; 0 when a list
} jj_schema;            // column makes it vary. The arrays belong to the doc.

typedef struct {
    ptrdiff_t n_rows, n_cols;
    char **col_names;   // the schema THESE rows use: an alias into schemas[],
    char *col_types;    // or into the root doc's when jj_sub filled this one
    const ptrdiff_t *col_schemas;  // aliases too
    const long long *col_sizes;
    const long long *col_offs;
    long long stride;   // 0 when the schema holds a list column
    char *body;         // first byte of the first row, for the strided path
    jj_val *vals;       // flat [n_rows * n_cols], and NULL when stride != 0:
                        // a field is then arithmetic and nothing is stored.
    ptrdiff_t n_schemas;  // 0 in a doc jj_sub filled, which borrows the
    jj_schema *schemas;   // root's table. jj_free releases what is owned.
} jj_doc;

// The type col_types holds for a list column: its value is a nested list, read
// with jj_sub, and col_schemas says which schema its rows use. A document
// spells that type as the schema's number, which may run to any number of
// digits, so it cannot be kept in one byte; this byte stands for all of them.
// It is no letter, so no value type can ever arrive as it.
#define JJ_LIST '['
#define jj_is_list(tag) ((tag) == JJ_LIST)

// A column's type is one of these nine letters or a schema number, and
// nothing else is; there is no unknown type that a reader reads as something
// else.
//
// Saying so is what makes the three implementations agree about a header at
// all. Swept byte by byte they used to disagree about 132 of the 256 possible
// type bytes, because each one cuts a column out of the header line
// differently: this parser took whatever byte followed the colon, so it read a
// newline, a space and a second colon as types, while Python splits the line
// and JavaScript matches it with a regex and each of those three found a
// different column. Naming the legal types settles all of it in one rule, since
// every byte they disagreed about is neither a letter here nor a digit.
//
// A char may be signed, so a byte at or above 0x80 arrives negative here and
// matches nothing, which is the answer that band wants anyway.
#define jj_is_type(tag) \
    ((tag) == 'i' || (tag) == 'f' || (tag) == 's' || (tag) == 'b' || \
     (tag) == 'y' || (tag) == 'd' || (tag) == 't' || (tag) == 'n' || \
     (tag) == 'z')
#define jj_is_tag(tag) (jj_is_type(tag) || jj_is_list(tag))

static inline const char *jj_strerror(int rc) {
    switch (rc) {
        case JJ_OK:               return "ok";
        case JJ_ERR_ARGS:         return "invalid arguments";
        case JJ_ERR_TRUNCATED:    return "truncated input";
        case JJ_ERR_BADNUM:       return "expected an integer";
        case JJ_ERR_RANGE:        return "integer out of range";
        case JJ_ERR_NEGLEN:       return "negative length";
        case JJ_ERR_HEADER:       return "malformed header";
        case JJ_ERR_TOO_MANY_COLS:return "too many columns";   // no longer returned
        case JJ_ERR_BADSEP:       return "missing newline separator";
        case JJ_ERR_OVERFLOW:     return "size overflow";
        case JJ_ERR_NOMEM:        return "out of memory";
        case JJ_ERR_TRAILING:     return "bytes left over after the last row";
        case JJ_ERR_VERSION:      return "unreadable format version";
        case JJ_ERR_TOO_MANY_SCHEMAS: return "too many schemas";  // no longer returned
        case JJ_ERR_SCHEMA_REF:   return "a list names a schema that is not declared";
        case JJ_ERR_DUPCOL:       return "a schema declares the same column name twice";
        case JJ_ERR_SIZE:         return "a column with no size, a size that is not a positive integer, or a size on a list column";
        case JJ_ERR_UTF8:         return "text that is not valid UTF-8";
        case JJ_ERR_BADBOOL:      return "expected a boolean, 1 or 0";
        default:                  return "unknown error";
    }
}

// What counts as a valid value for the numeric tags. The format defines this
// rather than leaving it to whatever each host language's parser happens to
// accept, because that is how the three implementations drifted apart: C and
// JavaScript read "12x" as 12 while Python rejected it, and Python read
// "1_000" as 1000 because Python integer literals allow underscores.
//
//   i   -?[0-9]+
//   f   -?[0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)?
//
// So: no leading "+", no surrounding whitespace, no underscores, no hex, no
// trailing junk, and no "inf"/"nan" -- the two encoders cannot even agree how
// to spell those (Python writes "inf", JavaScript writes "Infinity", and
// neither can read the other's), so a non-finite float is not representable.
static inline int jj__valid_num(const char *p, ptrdiff_t len, int is_float) {
    ptrdiff_t i = 0;
    if (len <= 0) return 0;
    if (p[i] == '-') i++;
    if (i == len || p[i] < '0' || p[i] > '9') return 0;
    while (i < len && p[i] >= '0' && p[i] <= '9') i++;
    if (!is_float) return i == len;

    if (i < len && p[i] == '.') {                  // fraction, at least one digit
        i++;
        if (i == len || p[i] < '0' || p[i] > '9') return 0;
        while (i < len && p[i] >= '0' && p[i] <= '9') i++;
    }
    if (i < len && (p[i] == 'e' || p[i] == 'E')) { // exponent, at least one digit
        i++;
        if (i < len && (p[i] == '+' || p[i] == '-')) i++;
        if (i == len || p[i] < '0' || p[i] > '9') return 0;
        while (i < len && p[i] >= '0' && p[i] <= '9') i++;
    }
    return i == len;
}

// Whether the len bytes at s are UTF-8: every character in its shortest form,
// no half of a surrogate pair, nothing past U+10FFFF. That is exactly what
// Python's decoder and JavaScript's fatal TextDecoder accept (the Unicode
// standard's table 3-7), so a column name or an s value all three read as text
// is the same text in each, and one that is not text is refused by all three.
static inline int jj__utf8(const char *s, ptrdiff_t len) {
    const unsigned char *p = (const unsigned char *)s, *end = p + len;
    while (p < end) {
        unsigned c = *p, lo = 0x80, hi = 0xBF;
        ptrdiff_t more, k;
        if (c < 0x80) { p++; continue; }
        if (c >= 0xC2 && c <= 0xDF) more = 1;
        else if (c >= 0xE0 && c <= 0xEF) {
            more = 2;
            if (c == 0xE0) lo = 0xA0;           // shorter as two bytes
            else if (c == 0xED) hi = 0x9F;      // U+D800-DFFF, surrogate halves
        } else if (c >= 0xF0 && c <= 0xF4) {
            more = 3;
            if (c == 0xF0) lo = 0x90;           // shorter as three bytes
            else if (c == 0xF4) hi = 0x8F;      // past U+10FFFF
        } else return 0;                        // a continuation byte, C0, C1, F5-FF
        if (end - p <= more || p[1] < lo || p[1] > hi) return 0;
        for (k = 2; k <= more; k++)
            if (p[k] < 0x80 || p[k] > 0xBF) return 0;
        p += more + 1;
    }
    return 1;
}

// A float read straight from its digits, when that is sure to give the answer
// strtod gives. It is when the digits, read as one whole number, fit in the 53
// bits of a double's significand and the power of ten that scales them is one a
// double holds exactly, which 10^22 is and 10^23 is not: the answer is then one
// correctly rounded multiplication or division of two exact doubles, which is
// the correctly rounded answer strtod gives (Clinger, 1990). That covers what
// the encoders write, which is 17 significant digits at most and mostly far
// fewer. Anything else returns 0 and is left to strtod. The grammar has
// already been checked.
//
// It holds only where a double is computed as a double. The x87's wider
// registers would round twice, so there this never answers.
#if defined(FLT_EVAL_METHOD) && FLT_EVAL_METHOD == 0
#define JJ__EXACT_DOUBLES 1
#else
#define JJ__EXACT_DOUBLES 0
#endif

static inline int jj__float_fast(const char *p, ptrdiff_t len, double *out) {
    static const double tens[] = {
        1e0,  1e1,  1e2,  1e3,  1e4,  1e5,  1e6,  1e7,  1e8,  1e9,  1e10, 1e11,
        1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22
    };
    unsigned long long w = 0;
    ptrdiff_t i = 0, digits = 0, scale = 0;
    long exponent = 0;
    int neg = 0, eneg = 0;
    double d;
    if (!JJ__EXACT_DOUBLES) return 0;
    if (p[i] == '-') { neg = 1; i++; }
    for (; i < len && p[i] >= '0' && p[i] <= '9'; i++, digits++)
        w = w * 10 + (unsigned)(p[i] - '0');
    if (i < len && p[i] == '.')
        for (i++; i < len && p[i] >= '0' && p[i] <= '9'; i++, digits++, scale--)
            w = w * 10 + (unsigned)(p[i] - '0');
    if (i < len) {                              // what is left is the exponent
        i++;
        if (p[i] == '-') { eneg = 1; i++; }
        else if (p[i] == '+') i++;
        for (; i < len; i++)                    // stops growing once far out of
            if (exponent < 1000) exponent = exponent * 10 + (p[i] - '0');  // range
    }
    scale += eneg ? -exponent : exponent;
    // Twenty digits could have wrapped w; nineteen cannot.
    if (digits > 19 || w > (1ULL << 53) || scale < -22 || scale > 22) return 0;
    d = (double)w;
    d = scale < 0 ? d / tens[-scale] : d * tens[scale];
    *out = neg ? -d : d;
    return 1;
}

// A value as a NUL-terminated string, for strtoll and strtod, which read
// until they meet one. A value points straight into the buffer and is followed
// by whatever the buffer holds next, so it is copied: into `small` when it
// fits, which is nearly always, and onto the heap when it does not. A spelling
// has no length limit -- leading zeros mean nothing, however many there are --
// so a long one is copied like a short one. NULL when the heap has no room.
// The caller frees the copy when it is not `small`.
static inline char *jj__terminated(const jj_val *v, char *small, size_t cap) {
    char *tmp = (size_t)v->len < cap ? small : (char *)malloc((size_t)v->len + 1);
    if (tmp) {
        memcpy(tmp, v->ptr, (size_t)v->len);
        tmp[v->len] = 0;
    }
    return tmp;
}

// Checked conversions. jj_int/jj_float below return 0 for anything they cannot
// read, which cannot be told apart from a real 0 -- Python and JavaScript raise
// on such a value, so a C caller that wants the same answer needs these. They
// validate at the point the value is materialized, exactly as the date
// accessors do, so jj_parse still reads a length and jumps the value and a
// numeric column costs nothing at parse time.
static inline int jj_int_checked(const jj_val *v, long long *out) {
    unsigned long long acc = 0;
    ptrdiff_t i;
    int neg;
    if (!v || !v->ptr || !out) return JJ_ERR_ARGS;
    if (!jj__valid_num(v->ptr, v->len, 0)) return JJ_ERR_BADNUM;
    neg = v->ptr[0] == '-';
    // Leading zeros are passed over rather than counted, so a value may carry
    // as many as its field has room for. What is left is read with no copy:
    // nineteen digits fit an unsigned long long whatever they are, and twenty
    // are past 2^63 whatever they are.
    for (i = neg; i < v->len - 1 && v->ptr[i] == '0'; i++) ;
    if (v->len - i > 19) return JJ_ERR_RANGE;
    for (; i < v->len; i++) acc = acc * 10 + (unsigned)(v->ptr[i] - '0');
    if (acc > (unsigned long long)LLONG_MAX + (unsigned)neg) return JJ_ERR_RANGE;
    // -2^63 has no positive twin in a long long, so it is not negated as one.
    *out = neg && acc ? -(long long)(acc - 1) - 1 : (long long)acc;
    return JJ_OK;
}

static inline int jj_float_checked(const jj_val *v, double *out) {
    char small[64], *tmp;
    double r;
    int err;
    if (!v || !v->ptr || !out) return JJ_ERR_ARGS;
    if (!jj__valid_num(v->ptr, v->len, 1)) return JJ_ERR_BADNUM;
    if (jj__float_fast(v->ptr, v->len, out)) return JJ_OK;
    if (!(tmp = jj__terminated(v, small, sizeof small))) return JJ_ERR_NOMEM;
    errno = 0;
    r = strtod(tmp, NULL);
    err = errno;
    if (tmp != small) free(tmp);
    // strtod reports ERANGE for underflow as well as for overflow, and an
    // underflow is not an error: 1e-400 naming zero, or 5e-324 naming the
    // smallest subnormal, is ordinary IEEE-754 behaviour and both other
    // implementations read them. Only a result that ran off the top is a value
    // this column cannot hold.
    if (err == ERANGE && (r >= HUGE_VAL || r <= -HUGE_VAL)) return JJ_ERR_RANGE;
    *out = r;
    return JJ_OK;
}

// An s value is text, and Python and JavaScript refuse one that is not UTF-8,
// so this answers the way they do: JJ_OK, or JJ_ERR_UTF8. jj_parse does not
// look. It hands an s value back as the bytes it is, because reading every
// value's bytes while parsing is the cost the sizes exist to avoid, so a
// caller reading a document it did not write calls this as it calls
// jj_int_checked. A b value is any bytes and has nothing to check.
static inline int jj_str_checked(const jj_val *v) {
    if (!v || !v->ptr || v->len < 0) return JJ_ERR_ARGS;
    return jj__utf8(v->ptr, v->len) ? JJ_OK : JJ_ERR_UTF8;
}

// A y value is 1 for true and 0 for false, one byte and nothing else: not "t",
// not "01", and not an empty field, which is not false either, because the
// format has no null. *out is 1 or 0, and JJ_ERR_BADBOOL says the value was
// neither. Like the others it is read when asked for, not by jj_parse.
static inline int jj_bool_checked(const jj_val *v, int *out) {
    if (!v || !v->ptr || !out) return JJ_ERR_ARGS;
    if (v->len != 1 || (v->ptr[0] != '0' && v->ptr[0] != '1')) return JJ_ERR_BADBOOL;
    *out = v->ptr[0] == '1';
    return JJ_OK;
}

// Values are not NUL-terminated (they point straight into the buffer and may
// contain any byte), so convert through a copy rather than letting
// strtoll/strtod scan past v->len.
//
// These stay lossy on purpose: they are the convenient form for data you have
// already validated, and they return 0 rather than reporting anything. Use
// jj_int_checked/jj_float_checked when the document is not yours.
static inline long long jj_int(const jj_val *v) {
    char small[64], *tmp;
    long long r;
    if (!v || !v->ptr || v->len < 0) return 0;
    if (!(tmp = jj__terminated(v, small, sizeof small))) return 0;
    r = strtoll(tmp, NULL, 10);
    if (tmp != small) free(tmp);
    return r;
}

static inline double jj_float(const jj_val *v) {
    char small[64], *tmp;
    double r;
    if (!v || !v->ptr || v->len < 0) return 0.0;
    if (!(tmp = jj__terminated(v, small, sizeof small))) return 0.0;
    r = strtod(tmp, NULL);
    if (tmp != small) free(tmp);
    return r;
}

// 1 for a y value that is 1, and 0 for anything else, a bad value included.
static inline int jj_bool(const jj_val *v) {
    return v && v->ptr && v->len == 1 && v->ptr[0] == '1';
}

// Bounded ASCII integer scan over [*pp, end). Advances *pp past the digits. A
// count or a length past PTRDIFF_MAX is refused, because no document could
// hold that many of anything: it is the size of the largest object there is.
static inline int jj__num(char **pp, const char *end, ptrdiff_t *out) {
    char *p = *pp;
    int neg = 0;
    size_t acc = 0;
    // '-' is read so that a negative row count or length can be reported as
    // JJ_ERR_NEGLEN rather than as a stray character. '+' is not: no encoder
    // writes one, Python and JavaScript both refuse it, and rule 9 already
    // rules it out for a value, so accepting it here made C the only reader
    // that would take the document.
    if (p < end && *p == '-') { neg = 1; p++; }
    if (p == end) return JJ_ERR_TRUNCATED;
    if (*p < '0' || *p > '9') return JJ_ERR_BADNUM;
    while (p < end && *p >= '0' && *p <= '9') {
        size_t d = (size_t)(*p - '0');
        if (acc > (size_t)PTRDIFF_MAX / 10 ||
            (acc == (size_t)PTRDIFF_MAX / 10 && d > (size_t)PTRDIFF_MAX % 10))
            return JJ_ERR_RANGE;
        acc = acc * 10 + d;
        p++;
    }
    *pp = p;
    *out = neg ? -(ptrdiff_t)acc : (ptrdiff_t)acc;
    return JJ_OK;
}

// Consume one mandatory '\n'.
static inline int jj__newline(char **pp, const char *end) {
    if (*pp == end) return JJ_ERR_TRUNCATED;
    if (**pp != '\n') return JJ_ERR_BADSEP;
    (*pp)++;
    return JJ_OK;
}

// Release the arrays a doc owns. A doc jj_sub filled owns only vals: its
// column arrays and schema table belong to the root doc it was read from.
static inline void jj_free(jj_doc *doc) {
    ptrdiff_t i;
    if (!doc) return;
    free(doc->vals);
    for (i = 0; i < doc->n_schemas; i++) {
        free(doc->schemas[i].col_names);
        free(doc->schemas[i].col_types);
        free(doc->schemas[i].col_schemas);
        free(doc->schemas[i].col_sizes);
        free(doc->schemas[i].col_offs);
    }
    free(doc->schemas);
    doc->schemas = NULL;
    doc->vals = NULL;
    doc->col_names = NULL;     // an alias, never freed here
    doc->col_types = NULL;
    doc->col_schemas = NULL;
    doc->col_sizes = NULL;
    doc->col_offs = NULL;
    doc->stride = 0;
    doc->body = NULL;
    doc->n_rows = doc->n_cols = doc->n_schemas = 0;
}

// Read one header line, "#name:t:size #name:2 ...\n", NUL-terminating names in
// place and growing the schema's arrays as it goes. Leaves *pp on the line's
// '\n', which the caller consumes. On failure the arrays allocated so far stay
// on the schema, for the caller's jj_free to release.
//
// Every column carries a size but a list column, which carries a length in
// each row instead. Once the line is read the column offsets and the row
// stride fall out of the sizes, and they are what makes a field arithmetic.
static inline int jj__header(char **pp, const char *end, jj_schema *s) {
    char *p = *pp;
    ptrdiff_t col_cap = 0, i, j;
    while (p < end && *p == '#') {
        char *name;
        if (s->n_cols == col_cap) {
            ptrdiff_t ncap = col_cap ? col_cap * 2 : JJ_COLS_INIT;
            char **nn;
            char *nt;
            // Bounded by the input, so a header cannot ask for more than it
            // has bytes to describe; this only guards the doubling itself.
            if ((size_t)ncap > SIZE_MAX / sizeof(long long)) return JJ_ERR_OVERFLOW;
            nn = (char **)realloc(s->col_names, sizeof(char *) * (size_t)ncap);
            if (!nn) return JJ_ERR_NOMEM;
            s->col_names = nn;
            nt = (char *)realloc(s->col_types, (size_t)ncap);
            if (!nt) return JJ_ERR_NOMEM;
            s->col_types = nt;
            {
                ptrdiff_t *nr = (ptrdiff_t *)realloc(s->col_schemas,
                                                     sizeof(ptrdiff_t) * (size_t)ncap);
                long long *nw;
                if (!nr) return JJ_ERR_NOMEM;
                s->col_schemas = nr;
                nw = (long long *)realloc(s->col_sizes, sizeof(long long) * (size_t)ncap);
                if (!nw) return JJ_ERR_NOMEM;
                s->col_sizes = nw;
                nw = (long long *)realloc(s->col_offs, sizeof(long long) * (size_t)ncap);
                if (!nw) return JJ_ERR_NOMEM;
                s->col_offs = nw;
            }
            col_cap = ncap;
        }
        p++;
        name = p;
        // A NUL ends the scan too, so a name containing one falls into the
        // check below. col_names[] hands names back as C strings, so a name
        // with a NUL in it would silently truncate -- two different columns
        // could arrive as the same empty string, and a lookup by name would
        // match the wrong one. Python and JS keep such a name intact, so
        // accepting it here would also put the three implementations out of
        // step. Rejecting it is the only option that keeps them agreeing.
        while (p < end && *p != ':' && *p != ' ' && *p != '\n' && *p != '\0') p++;
        if (p == end) return JJ_ERR_TRUNCATED;
        if (*p != ':' || p == name) return JJ_ERR_HEADER;   // names are non-empty
        // A name is text, and Python and JavaScript read it as text, so a name
        // that is not UTF-8 is refused here as they refuse it. Checked now,
        // not on request as a value is: a header is read once and is short.
        if (!jj__utf8(name, p - name)) return JJ_ERR_UTF8;
        *p++ = 0;
        if (p == end) return JJ_ERR_TRUNCATED;
        s->col_names[s->n_cols] = name;
        s->col_sizes[s->n_cols] = 0;
        s->col_schemas[s->n_cols] = 0;
        if (*p >= '0' && *p <= '9') {
            // A list column. Its type is the number of the schema its rows
            // use, in as many digits as that takes, so a document may declare
            // as many schemas as it needs. Whether the schema exists is asked
            // once the whole table is in, since a reference may point forward;
            // a number larger than any document could hold schemas for is held
            // at PTRDIFF_MAX, where no table reaches, and refused there with
            // the rest. Held, not cast: on a 32-bit target a cast would wrap
            // 4294967297 round to schema 1.
            long long n = jj__digits(&p, end);
            s->col_types[s->n_cols] = JJ_LIST;
            s->col_schemas[s->n_cols] = n > PTRDIFF_MAX ? PTRDIFF_MAX : (ptrdiff_t)n;
        } else {
            // A type outside the set is a malformed document, not a column
            // whose values happen to read back as strings. JJ_LIST stands for
            // a number, so the byte itself is not a type either.
            s->col_types[s->n_cols] = *p++;
            if (!jj_is_type(s->col_types[s->n_cols])) return JJ_ERR_HEADER;
        }
        s->n_cols++;
        if (p == end) return JJ_ERR_TRUNCATED;
        {
            char tag = s->col_types[s->n_cols - 1];
            if (*p == ':') {
                long long w;
                p++;
                if (p == end || *p < '0' || *p > '9') return JJ_ERR_SIZE;
                // As large as it likes: see JJ__BEYOND.
                w = jj__digits(&p, end);
                if (p == end) return JJ_ERR_TRUNCATED;
                // A nested list is as long as its own contents, so a size on
                // one would be a promise about something different in every
                // row. It is the one column that carries a length instead.
                if (w < 1 || jj_is_list(tag)) return JJ_ERR_SIZE;
                s->col_sizes[s->n_cols - 1] = w;
            } else if (!jj_is_list(tag)) {
                // Every other column declares its size. Without one there is
                // nothing to say where the value ends, and no row has a
                // constant length any more.
                return JJ_ERR_SIZE;
            }
        }
        if (*p == ' ') p++;                                 // more columns follow
        else if (*p != '\n') return JJ_ERR_HEADER;
    }
    if (s->n_cols == 0) return JJ_ERR_HEADER;
    // Where each column starts inside a row, and how long a row is. A list
    // column has no size, so everything after it moves with the data and the
    // schema has no stride: its rows are walked instead. Random access is a
    // property of a schema, not of the format.
    {
        long long off = 0;
        int listy = 0;
        for (i = 0; i < s->n_cols; i++) {
            s->col_offs[i] = off;
            if (jj_is_list(s->col_types[i])) { listy = 1; break; }
            off = jj__add(off, s->col_sizes[i]);     // saturates; never wraps
        }
        s->stride = listy ? 0 : jj__add(off, 1);    // + the row's separator
    }
    // A name declared twice is refused rather than resolved. Values here are
    // positional, so this parser would keep both columns, while Python and
    // JavaScript hand a row back keyed by name and the second one overwrites
    // the first. That is a parser differential: the same bytes meaning
    // different things to different readers. Picking a winner would make them
    // agree by discarding data; refusing the document makes them agree by
    // making it invalid, which is what this format already does rather than
    // tolerate a divergence.
    //
    // Quadratic in the column count, which is a header parsed once and almost
    // always a handful of columns. At the thousand-column end it is half a
    // million string compares against a document that is already far larger.
    for (i = 1; i < s->n_cols; i++)
        for (j = 0; j < i; j++)
            if (strcmp(s->col_names[i], s->col_names[j]) == 0)
                return JJ_ERR_DUPCOL;
    *pp = p;
    return JJ_OK;
}

// The first '\n' at or after p, or end when the line is unterminated.
static inline const char *jj__eol(const char *p, const char *end) {
    while (p < end && *p != '\n') p++;
    return p;
}

// The version line, "<major>.<minor>". One version of the format exists, so
// this takes that one and refuses everything else -- a document from the
// future because it cannot know what it says, and one from the past because
// there is no past.
static inline int jj__version(char **pp, const char *eol) {
    char *p = *pp;
    ptrdiff_t major, minor;
    if (jj__num(&p, eol, &major) != JJ_OK) return JJ_ERR_VERSION;
    if (p == eol || *p != '.') return JJ_ERR_VERSION;
    p++;
    if (jj__num(&p, eol, &minor) != JJ_OK) return JJ_ERR_VERSION;
    if (p != eol) return JJ_ERR_VERSION;        // trailing junk on the line
    if (major != JJ_VERSION_MAJOR || minor != JJ_VERSION_MINOR)
        return JJ_ERR_VERSION;
    *pp = p + 1;                                 // past the line's '\n'
    return JJ_OK;
}

// Everything before the first value: the version line and the schema table.
// Failures leave the doc for jj_free, because a schema may already be
// allocated.
static inline int jj__preamble(char **pp, const char *end, jj_doc *doc) {
    char *p = *pp;
    const char *eol = jj__eol(p, end);
    ptrdiff_t cap = 0, i, c;
    int rc;

    if (eol == end) return JJ_ERR_TRUNCATED;
    if ((rc = jj__version(&p, eol)) != JJ_OK) return rc;

    while (p < end && *p == '#') {
        jj_schema *s;
        if (doc->n_schemas == cap) {
            // Bounded by the input like the column arrays: a schema line
            // costs at least five bytes ("#a:1\n").
            ptrdiff_t ncap = cap ? cap * 2 : JJ_SCHEMAS_INIT;
            jj_schema *grown;
            if ((size_t)ncap > SIZE_MAX / sizeof(jj_schema)) return JJ_ERR_OVERFLOW;
            grown = (jj_schema *)realloc(doc->schemas, sizeof(jj_schema) * (size_t)ncap);
            if (!grown) return JJ_ERR_NOMEM;
            doc->schemas = grown;
            cap = ncap;
        }
        // Blanked and counted before it is filled, so that a header that fails
        // partway is still released by jj_free rather than leaked, and so that
        // jj_free only ever releases what jj__header allocated.
        s = &doc->schemas[doc->n_schemas++];
        s->n_cols = 0;
        s->col_names = NULL;
        s->col_types = NULL;
        s->col_schemas = NULL;
        s->col_sizes = NULL;
        s->col_offs = NULL;
        s->stride = 0;
        if ((rc = jj__header(&p, end, s)) != JJ_OK) return rc;
        if ((rc = jj__newline(&p, end)) != JJ_OK) return rc;
    }
    if (doc->n_schemas == 0) return JJ_ERR_HEADER;

    // A list names its schema by number. References may point forward, so they
    // are checked once the whole table is in rather than as each line is read.
    // Schemas count from 1, so 0 names none.
    for (i = 0; i < doc->n_schemas; i++)
        for (c = 0; c < doc->schemas[i].n_cols; c++) {
            ptrdiff_t n = doc->schemas[i].col_schemas[c];
            if (jj_is_list(doc->schemas[i].col_types[c]) && (n < 1 || n > doc->n_schemas))
                return JJ_ERR_SCHEMA_REF;
        }

    if ((rc = jj__num(&p, end, &doc->n_rows)) != JJ_OK) return rc;
    if (doc->n_rows < 0) return JJ_ERR_NEGLEN;
    if ((rc = jj__newline(&p, end)) != JJ_OK) return rc;
    *pp = p;
    return JJ_OK;
}

// A schema with no list column has a constant row length, so its rows need no
// index at all: jj_parse checks that the document is exactly n_rows strides
// long and that every row ends with its separator, and jj_field works the rest
// out by arithmetic. Nothing is allocated and no value is looked at, so a
// document of any size costs the same per value read and nothing per value
// skipped. This is what the fixed sizes are for.
static inline int jj__rows_strided(char *p, const char *end, jj_doc *doc) {
    ptrdiff_t r;
    long long span, avail = end - p;

    // stride is at least 2 (one column of at least one byte, plus the
    // separator), so the division cannot divide by zero and the product below
    // cannot overflow once it holds. A stride held at JJ__BEYOND is longer
    // than any document, so it passes here only when there are no rows.
    if (doc->n_rows > avail / doc->stride) return JJ_ERR_TRUNCATED;
    span = doc->n_rows * doc->stride;
    // A well-formed document ends where its last row ends. Leftover bytes mean
    // the row count did not describe this document.
    if (span != avail) return JJ_ERR_TRAILING;

    // One byte read per row rather than per value. A sized value is raw bytes
    // that may itself begin with a newline, so this separator is the only
    // thing that says the row ended, and a document missing one is refused
    // here rather than read as a row of shifted values.
    for (r = 0; r < doc->n_rows; r++)
        if (p[r * doc->stride + doc->stride - 1] != '\n') return JJ_ERR_BADSEP;

    doc->body = p;
    return JJ_OK;
}

// A schema holding a list column has no constant row length, because a list is
// as long as its own contents. Its rows are walked once and recorded, which is
// what an index is for. Sized columns are still stepped over by their size; a
// list column is the only one that carries a length.
static inline int jj__rows_walked(char *p, const char *end, jj_doc *doc) {
    ptrdiff_t total, i, c;
    long long row_min = 0;
    jj_val *v;
    int rc;

    if (doc->n_rows > PTRDIFF_MAX / doc->n_cols) return JJ_ERR_OVERFLOW;
    total = doc->n_rows * doc->n_cols;
    if ((size_t)total > SIZE_MAX / sizeof(jj_val)) return JJ_ERR_OVERFLOW;
    // The smallest a row can be: a sized value costs its size, a list costs at
    // least 2 bytes ("0\n" and no rows), and every row spends one more on its
    // separator. A row count larger than the buffer can hold is rejected
    // before anything is allocated. The sum saturates as a stride does, so a
    // schema whose columns add up past any document still reads when it has
    // no rows.
    for (c = 0; c < doc->n_cols; c++)
        row_min = jj__add(row_min, doc->col_sizes[c] ? doc->col_sizes[c] : 2);
    row_min = jj__add(row_min, 1);
    if (doc->n_rows > (end - p) / row_min) return JJ_ERR_TRUNCATED;

    doc->vals = malloc(sizeof(jj_val) * (size_t)(total ? total : 1));
    if (!doc->vals) return JJ_ERR_NOMEM;

    v = doc->vals;
    for (i = 0; i < total; i++, v++) {
        long long vlen, size;
        c = i % doc->n_cols;
        size = doc->col_sizes[c];
        if (size) {
            vlen = size;                       // the header already said how long
        } else {
            ptrdiff_t n;
            if ((rc = jj__num(&p, end, &n)) != JJ_OK) return rc;
            if (n < 0) return JJ_ERR_NEGLEN;
            if ((rc = jj__newline(&p, end)) != JJ_OK) return rc;  // ends the length
            vlen = n;
        }
        // Need vlen value bytes. end - p is at least 0 and fits in a
        // ptrdiff_t, so once this holds vlen fits in one too, whatever a size
        // could be.
        if (vlen > end - p) return JJ_ERR_TRUNCATED;
        v->ptr = p;
        v->len = (ptrdiff_t)vlen;
        p += vlen;                             // value bytes are never scanned
        if (size && jj_is_padded(doc->col_types[c])) {
            // The one place a value is looked at while parsing. Ending it here
            // keeps v->len meaning the value in every implementation; the scan
            // stops at the break byte, so the rest of the field is never read.
            v->len = jj__value_len(v->ptr, v->len);
        }
        if (c == doc->n_cols - 1) {
            if (p == end || *p != '\n') return JJ_ERR_BADSEP;
            p++;
        }
    }
    if (p != end) return JJ_ERR_TRAILING;
    return JJ_OK;
}

static inline int jj__rows(char *p, const char *end, jj_doc *doc) {
    if (doc->n_cols <= 0) return JJ_ERR_HEADER;
    if (doc->n_rows < 0) return JJ_ERR_NEGLEN;
    return doc->stride ? jj__rows_strided(p, end, doc)
                       : jj__rows_walked(p, end, doc);
}

// Point a doc's column arrays at one of the schemas in `table`. The arrays are
// borrowed, not copied: `table`'s owner must outlive this doc, exactly as the
// buffer must.
static inline void jj__use_schema(jj_doc *doc, const jj_schema *s) {
    doc->n_cols = s->n_cols;
    doc->col_names = s->col_names;
    doc->col_types = s->col_types;
    doc->col_schemas = s->col_schemas;
    doc->col_sizes = s->col_sizes;
    doc->col_offs = s->col_offs;
    doc->stride = s->stride;
}

// Row r, column c. In a schema with a stride this is pure arithmetic over the
// buffer: no index was built and none is needed. In one holding a list column
// it reads the index jj__rows_walked recorded. Either way the value means the
// same thing, ending at its break byte.
static inline jj_val jj__field(const jj_doc *doc, ptrdiff_t r, ptrdiff_t c) {
    jj_val v;
    if (doc->stride) {
        v.ptr = doc->body + r * doc->stride + doc->col_offs[c];
        // A field lies inside the document, so its size fits in a ptrdiff_t,
        // as every value's length does.
        v.len = (ptrdiff_t)doc->col_sizes[c];
        // Ended here rather than at parse time, so a value nobody reads costs
        // nothing at all.
        if (jj_is_padded(doc->col_types[c]))
            v.len = jj__value_len(v.ptr, v.len);
        return v;
    }
    return doc->vals[r * doc->n_cols + c];
}

// field accessor: row r, column c. A one-element compound literal, so this
// still hands back a jj_val* that lives to the end of the enclosing block and
// every caller reads it as it always did, while a strided document stores no
// jj_val anywhere for it to point at.
#define jj_field(doc, r, c) ((jj_val[]){ jj__field((doc), (r), (c)) })

static inline void jj__blank(jj_doc *doc) {
    doc->n_rows = doc->n_cols = doc->n_schemas = 0;
    doc->vals = NULL;
    doc->col_names = NULL;
    doc->col_types = NULL;
    doc->col_schemas = NULL;
    doc->col_sizes = NULL;
    doc->col_offs = NULL;
    doc->stride = 0;
    doc->body = NULL;
    doc->schemas = NULL;
}

static inline int jj_parse(char *buf, ptrdiff_t len, jj_doc *doc) {
    char *p = buf;
    int rc;

    if (!doc) return JJ_ERR_ARGS;
    jj__blank(doc);
    if (!buf || len < 0) return JJ_ERR_ARGS;

    if ((rc = jj__preamble(&p, buf + len, doc)) != JJ_OK) goto fail;

    // The top-level rows use schema 1; the whole table stays on the doc so that
    // jj_sub can resolve a nested list's schema at any depth.
    jj__use_schema(doc, &doc->schemas[0]);

    if ((rc = jj__rows(p, buf + len, doc)) != JJ_OK) goto fail;
    return JJ_OK;

fail:
    jj_free(doc);
    return rc;
}

// Parse one nested list. `root` is the document jj_parse filled, `schema` the
// number of the schema the list's rows use -- col_schemas[c] for the column it
// sits in -- and `v` the value. `out` is filled like any other jj_doc and
// released with jj_free; it points into the same buffer and borrows the root's
// schema table, so both must outlive it. Its own columns may hold further
// lists, read the same way and always against `root`.
static inline int jj_sub(const jj_doc *root, ptrdiff_t schema, const jj_val *v,
                         jj_doc *out) {
    char *p;
    const char *end;
    int rc;

    if (!out) return JJ_ERR_ARGS;
    jj__blank(out);
    if (!root || !v || !v->ptr) return JJ_ERR_ARGS;
    if (schema < 1 || schema > root->n_schemas) return JJ_ERR_SCHEMA_REF;

    // A nested list carries its own row count and then its values, with no
    // header: the schema it uses is the one its column names. Every length in
    // it is checked against the value's end, not the document's.
    p = v->ptr;
    end = v->ptr + v->len;
    if ((rc = jj__num(&p, end, &out->n_rows)) != JJ_OK) goto fail;
    if (out->n_rows < 0) { rc = JJ_ERR_NEGLEN; goto fail; }
    if ((rc = jj__newline(&p, end)) != JJ_OK) goto fail;

    jj__use_schema(out, &root->schemas[schema - 1]);  // borrowed: n_schemas stays 0

    if ((rc = jj__rows(p, end, out)) != JJ_OK) goto fail;
    return JJ_OK;

fail:
    jj_free(out);
    return rc;
}

#endif