Non-recursive JSON parser

json.c

#include "json.h"

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
#include <stdalign.h>
#define ALIGNOF alignof
#elif defined(__GNUC__) || defined(__clang__)
#define ALIGNOF __alignof__
#elif defined(_MSC_VER)
#define ALIGNOF __alignof
#else
#include <stddef.h>
#define ALIGNOF(type_) offsetof(struct { char c; type_ member; }, member)
#endif

static const size_t JSON_ARENA_INITIAL = 0x1000;

static void *
JSONArena_alloc(JSONArena *arena, size_t size, size_t alignment) {
    JSONArenaChunk *chunk = arena->chunks;

    if (!chunk || (size > chunk->size - alignment) || (chunk->used > chunk->size - size - alignment)) {
        if (arena->next_size == 0) arena->next_size = JSON_ARENA_INITIAL;
        size_t next_size = arena->next_size;

        if (size > next_size) {
            next_size = size;
        } else if (next_size < SIZE_MAX / 2) {
            arena->next_size *= 2;
        }

        chunk = malloc(sizeof(JSONArenaChunk) + next_size);
        if (!chunk) {
            perror("malloc");
            exit(EXIT_FAILURE);
        }

        *chunk = (JSONArenaChunk) {
            .next = arena->chunks,
            .size = next_size,
            .used = 0
        };

        arena->chunks = chunk;
    }

    uintptr_t unaligned = (uintptr_t) (chunk->data + chunk->used);
    uintptr_t aligned = (unaligned + (alignment - 1)) & ~(alignment - 1);
    chunk->used += (aligned - unaligned) + size;
    return (void *) aligned;
}

#define JSONArena_INITIALIZER { .chunks = NULL, .next_size = 0 }
#define JSONArena_ALLOC(arena, type_) ((type_ *) JSONArena_alloc((arena), sizeof(type_), ALIGNOF(type_)))

JSONArena *
JSONArena_new(void) {
    JSONArena *arena = malloc(sizeof(JSONArena));
    if (!arena) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    *arena = (JSONArena) JSONArena_INITIALIZER;
    return arena;
}

void
JSONArena_free(JSONArena *arena) {
    JSONArenaChunk *chunk = arena->chunks;
    while (chunk) {
        JSONArenaChunk *next = chunk->next;
        free(chunk);
        chunk = next;
    }
    *arena = (JSONArena) JSONArena_INITIALIZER;
}

static JSONNull *
JSONNull_new(JSONArena *arena) {
    JSONNull *cast = JSONArena_ALLOC(arena, JSONNull);
    *cast = (JSONNull) { .base = { .type = kJSONTypeNull } };
    return cast;
}

static JSONTrue *
JSONTrue_new(JSONArena *arena) {
    JSONTrue *cast = JSONArena_ALLOC(arena, JSONTrue);
    *cast = (JSONTrue) { .base = { .type = kJSONTypeTrue } };
    return cast;
}

static JSONFalse *
JSONFalse_new(JSONArena *arena) {
    JSONFalse *cast = JSONArena_ALLOC(arena, JSONFalse);
    *cast = (JSONFalse) { .base = { .type = kJSONTypeFalse } };
    return cast;
}

static JSONNumber *
JSONNumber_new(JSONArena *arena, double value) {
    JSONNumber *cast = JSONArena_ALLOC(arena, JSONNumber);
    *cast = (JSONNumber) { .base = { .type = kJSONTypeNumber }, .value = value };
    return cast;
}

static JSONString *
JSONString_new(JSONArena *arena, const uint8_t *value, size_t length) {
    JSONString *cast = JSONArena_ALLOC(arena, JSONString);
    *cast = (JSONString) { .base = { .type = kJSONTypeString }, .value = value, .length = length };
    return cast;
}

static JSONArray *
JSONArray_new(JSONArena *arena) {
    JSONArray *cast = JSONArena_ALLOC(arena, JSONArray);
    *cast = (JSONArray) { .base = { .type = kJSONTypeArray }, .elements = NULL, .capa = 0, .size = 0 };
    return cast;
}

static JSONObject *
JSONObject_new(JSONArena *arena) {
    JSONObject *cast = JSONArena_ALLOC(arena, JSONObject);
    *cast = (JSONObject) { .base = { .type = kJSONTypeObject }, .elements = NULL, .capa = 0, .size = 0 };
    return cast;
}

#define JSON_upcast(value_) (JSONValue *) (value_)
#define JSONNull_downcast(value_) ((JSONNull *) (value_))
#define JSONTrue_downcast(value_) ((JSONTrue *) (value_))
#define JSONFalse_downcast(value_) ((JSONFalse *) (value_))
#define JSONNumber_downcast(value_) ((JSONNumber *) (value_))
#define JSONString_downcast(value_) ((JSONString *) (value_))
#define JSONArray_downcast(value_) ((JSONArray *) (value_))
#define JSONObject_downcast(value_) ((JSONObject *) (value_))

static const uint8_t *
skip_whitespace(const uint8_t *source, const uint8_t *end) {
    while (source < end && (*source == ' ' || *source == '\t' || *source == '\n' || *source == '\r')) source++;
    return source;
}

// Parse a string value (source should point to the opening quote)
static JSONString *
parse_string(JSONArena *arena, const uint8_t **source, const uint8_t *end) {
    if (**source != '"') {
        return NULL;
    }
    (*source)++;

    const uint8_t *start = *source;
    while (*source < end) {
        uint8_t c = **source;
        if (c == '"') {
            size_t str_length = (size_t)(*source - start);
            (*source)++;
            return JSONString_new(arena, start, str_length);
        } else if (c == '\\') {
            (*source)++;
            if (*source >= end) {
                return NULL;
            }
            uint8_t esc = **source;
            if (esc == 'u') {
                // Validate unicode escape
                (*source)++;
                for (int i = 0; i < 4; i++) {
                    if (*source >= end || !isxdigit(**source)) {
                        return NULL;
                    }
                    (*source)++;
                }
                continue;
            } else if (esc == '"' || esc == '\\' || esc == '/' || esc == 'b' || esc == 'f' || esc == 'n' || esc == 'r' || esc == 't') {
                (*source)++;
            } else {
                return NULL;
            }
        } else if ((unsigned char)c < 0x20) {
            // Control characters are not allowed unescaped
            return NULL;
        } else {
            (*source)++;
        }
    }
    return NULL;  // Unterminated string
}

// Parse a number (source should point to first digit or minus sign)
static JSONNumber *
parse_number(JSONArena *arena, const uint8_t **source, const uint8_t *end) {
    const uint8_t *start = *source;

    // Optional minus
    if (**source == '-') {
        (*source)++;
    }

    // Integer part
    if (*source >= end) {
        return NULL;
    }

    if (**source == '0') {
        (*source)++;
        // After a leading 0, we can only have . or e/E (no other digits)
        if (*source < end && isdigit(**source)) {
            return NULL;  // Leading zeros not allowed
        }
    } else if (isdigit(**source)) {
        while (*source < end && isdigit(**source)) {
            (*source)++;
        }
    } else {
        return NULL;
    }

    // Fractional part
    if (*source < end && **source == '.') {
        (*source)++;
        if (*source >= end || !isdigit(**source)) {
            return NULL;
        }
        while (*source < end && isdigit(**source)) {
            (*source)++;
        }
    }

    // Exponent part
    if (*source < end && (**source == 'e' || **source == 'E')) {
        (*source)++;
        if (*source >= end) {
            return NULL;
        }
        if (**source == '+' || **source == '-') {
            (*source)++;
        }
        if (*source >= end || !isdigit(**source)) {
            return NULL;
        }
        while (*source < end && isdigit(**source)) {
            (*source)++;
        }
    }

    char *next;
    double value = strtod((const char *)start, &next);
    return JSONNumber_new(arena, value);
}

typedef enum {
    kParseStateValue,
    kParseStateArray,
    kParseStateObject,
    kParseStatePair
} ParseState;

typedef struct {
    ParseState state;
    union {
        JSONArray *array;
        JSONObject *object;
        JSONString *key;
    } data;
} ParseFrame;

static int
json_array_append(JSONArray *arr, JSONValue *value) {
    if (arr->size >= arr->capa) {
        size_t new_capa = arr->capa == 0 ? 10 : arr->capa * 2;
        JSONValue **new_elems = malloc(new_capa * sizeof(JSONValue *));
        if (!new_elems) {
            return 0;
        }
        if (arr->elements && arr->size > 0) {
            memcpy(new_elems, arr->elements, arr->size * sizeof(JSONValue *));
        }
        arr->elements = new_elems;
        arr->capa = new_capa;
    }

    arr->elements[arr->size++] = value;
    return 1;
}

static int
json_object_append(JSONArena *arena, JSONObject *obj, JSONString *key, JSONValue *value) {
    JSONPair *pair = JSONArena_ALLOC(arena, JSONPair);
    if (!pair) {
        return 0;
    }

    pair->key = JSON_upcast(key);
    pair->value = value;

    if (obj->size >= obj->capa) {
        size_t new_capa = obj->capa == 0 ? 10 : obj->capa * 2;
        JSONPair **new_elems = malloc(new_capa * sizeof(JSONPair *));
        if (!new_elems) {
            return 0;
        }
        if (obj->elements && obj->size > 0) {
            memcpy(new_elems, obj->elements, obj->size * sizeof(JSONPair *));
        }
        obj->elements = new_elems;
        obj->capa = new_capa;
    }

    obj->elements[obj->size++] = pair;
    return 1;
}

static JSONValue *
parse(JSONArena *arena, const uint8_t **source, const uint8_t *end) {
    ParseFrame *stack = NULL;
    size_t stack_size = 0;
    size_t stack_cap = 0;
    JSONValue *result = NULL;

    // Push initial value frame
    stack_cap = 16;
    stack = malloc(stack_cap * sizeof(ParseFrame));
    if (!stack) {
        return NULL;
    }

    stack[stack_size++] = (ParseFrame){ .state = kParseStateValue };

    while (stack_size > 0) {
        ParseFrame *frame = &stack[stack_size - 1];

        switch (frame->state) {
            case kParseStateValue: {
                *source = skip_whitespace(*source, end);
                if (*source >= end) {
                    goto fail;
                }

                uint8_t c = **source;
                JSONValue *val = NULL;

                if (c == 'n') {
                    if (end - *source >= 4 && memcmp(*source, "null", 4) == 0) {
                        *source += 4;
                        val = JSON_upcast(JSONNull_new(arena));
                    } else {
                        goto fail;
                    }
                } else if (c == 't') {
                    if (end - *source >= 4 && memcmp(*source, "true", 4) == 0) {
                        *source += 4;
                        val = JSON_upcast(JSONTrue_new(arena));
                    } else {
                        goto fail;
                    }
                } else if (c == 'f') {
                    if (end - *source >= 5 && memcmp(*source, "false", 5) == 0) {
                        *source += 5;
                        val = JSON_upcast(JSONFalse_new(arena));
                    } else {
                        goto fail;
                    }
                } else if (c == '-' || isdigit(c)) {
                    JSONNumber *num = parse_number(arena, source, end);
                    if (!num) {
                        goto fail;
                    }
                    val = JSON_upcast(num);
                } else if (c == '"') {
                    JSONString *str = parse_string(arena, source, end);
                    if (!str) {
                        goto fail;
                    }
                    val = JSON_upcast(str);
                } else if (c == '[') {
                    *source += 1;
                    JSONArray *arr = JSONArray_new(arena);

                    *source = skip_whitespace(*source, end);
                    if (*source < end && **source == ']') {
                        *source += 1;
                        val = JSON_upcast(arr);
                    } else {
                        if (stack_size == stack_cap) {
                            size_t new_cap = stack_cap * 2;
                            ParseFrame *tmp = realloc(stack, new_cap * sizeof(ParseFrame));
                            if (!tmp) {
                                goto fail;
                            }
                            stack = tmp;
                            stack_cap = new_cap;
                        }
                        stack[stack_size - 1] = (ParseFrame){ .state = kParseStateArray, .data.array = arr };
                        stack[stack_size++] = (ParseFrame){ .state = kParseStateValue };
                        continue;
                    }
                } else if (c == '{') {
                    *source += 1;
                    JSONObject *obj = JSONObject_new(arena);

                    *source = skip_whitespace(*source, end);
                    if (*source < end && **source == '}') {
                        *source += 1;
                        val = JSON_upcast(obj);
                    } else {
                        if (stack_size == stack_cap) {
                            size_t new_cap = stack_cap * 2;
                            ParseFrame *tmp = realloc(stack, new_cap * sizeof(ParseFrame));
                            if (!tmp) {
                                goto fail;
                            }
                            stack = tmp;
                            stack_cap = new_cap;
                        }
                        stack[stack_size - 1] = (ParseFrame){ .state = kParseStateObject, .data.object = obj };
                        stack[stack_size++] = (ParseFrame){ .state = kParseStatePair, .data.key = NULL };
                        continue;
                    }
                } else {
                    goto fail;
                }

                // Pop value frame
                stack_size--;

                if (stack_size == 0) {
                    result = val;
                    goto done;
                }

                ParseFrame *parent = &stack[stack_size - 1];
                if (parent->state == kParseStateArray) {
                    if (!json_array_append(parent->data.array, val)) {
                        goto fail;
                    }
                } else if (parent->state == kParseStatePair) {
                    if (stack_size < 2) {
                        goto fail;
                    }
                    ParseFrame *object_frame = &stack[stack_size - 2];
                    if (object_frame->state != kParseStateObject) {
                        goto fail;
                    }

                    if (!json_object_append(arena, object_frame->data.object, parent->data.key, val)) {
                        goto fail;
                    }

                    // Remove the pair frame after use
                    stack_size--;
                } else {
                    goto fail;
                }

                break;
            }

            case kParseStateArray: {
                *source = skip_whitespace(*source, end);
                if (*source >= end) {
                    goto fail;
                }

                if (**source == ']') {
                    *source += 1;
                    JSONValue *arr_val = JSON_upcast(frame->data.array);
                    stack_size--;

                    if (stack_size == 0) {
                        result = arr_val;
                        goto done;
                    }

                    ParseFrame *parent = &stack[stack_size - 1];
                    if (parent->state == kParseStateArray) {
                        if (!json_array_append(parent->data.array, arr_val)) {
                            goto fail;
                        }
                    } else if (parent->state == kParseStatePair) {
                        if (stack_size < 2) {
                            goto fail;
                        }
                        ParseFrame *object_frame = &stack[stack_size - 2];
                        if (object_frame->state != kParseStateObject) {
                            goto fail;
                        }
                        if (!json_object_append(arena, object_frame->data.object, parent->data.key, arr_val)) {
                            goto fail;
                        }
                        stack_size--;
                    } else {
                        goto fail;
                    }

                    break;
                } else if (**source == ',') {
                    *source += 1;

                    if (stack_size == stack_cap) {
                        size_t new_cap = stack_cap * 2;
                        ParseFrame *tmp = realloc(stack, new_cap * sizeof(ParseFrame));
                        if (!tmp) {
                            goto fail;
                        }
                        stack = tmp;
                        stack_cap = new_cap;
                    }

                    stack[stack_size++] = (ParseFrame){ .state = kParseStateValue };
                    break;
                } else {
                    goto fail;
                }
            }

            case kParseStateObject: {
                *source = skip_whitespace(*source, end);
                if (*source >= end) {
                    goto fail;
                }

                if (**source == '}') {
                    *source += 1;
                    JSONValue *obj_val = JSON_upcast(frame->data.object);
                    stack_size--;

                    if (stack_size == 0) {
                        result = obj_val;
                        goto done;
                    }

                    ParseFrame *parent = &stack[stack_size - 1];
                    if (parent->state == kParseStateArray) {
                        if (!json_array_append(parent->data.array, obj_val)) {
                            goto fail;
                        }
                    } else if (parent->state == kParseStatePair) {
                        if (stack_size < 2) {
                            goto fail;
                        }
                        ParseFrame *object_frame = &stack[stack_size - 2];
                        if (object_frame->state != kParseStateObject) {
                            goto fail;
                        }
                        if (!json_object_append(arena, object_frame->data.object, parent->data.key, obj_val)) {
                            goto fail;
                        }
                        stack_size--;
                    } else {
                        goto fail;
                    }

                    break;
                } else if (**source == ',') {
                    *source += 1;

                    if (stack_size == stack_cap) {
                        size_t new_cap = stack_cap * 2;
                        ParseFrame *tmp = realloc(stack, new_cap * sizeof(ParseFrame));
                        if (!tmp) {
                            goto fail;
                        }
                        stack = tmp;
                        stack_cap = new_cap;
                    }

                    stack[stack_size++] = (ParseFrame){ .state = kParseStatePair, .data.key = NULL };
                    break;
                } else {
                    goto fail;
                }
            }

            case kParseStatePair: {
                *source = skip_whitespace(*source, end);
                if (*source >= end || **source != '"') {
                    goto fail;
                }

                JSONString *key = parse_string(arena, source, end);
                if (!key) {
                    goto fail;
                }

                *source = skip_whitespace(*source, end);
                if (*source >= end || **source != ':') {
                    goto fail;
                }
                *source += 1;

                frame->data.key = key;

                if (stack_size == stack_cap) {
                    size_t new_cap = stack_cap * 2;
                    ParseFrame *tmp = realloc(stack, new_cap * sizeof(ParseFrame));
                    if (!tmp) {
                        goto fail;
                    }
                    stack = tmp;
                    stack_cap = new_cap;
                }

                stack[stack_size++] = (ParseFrame){ .state = kParseStateValue };
                break;
            }
        }
    }

done:
    free(stack);
    return result;

fail:
    free(stack);
    return NULL;
}

JSONValue *
JSON_parse(JSONArena *arena, const uint8_t *source, size_t length) {
    const uint8_t *end = source + length;
    source = skip_whitespace(source, end);

    JSONValue *root = parse(arena, &source, end);
    if (!root) return NULL;

    source = skip_whitespace(source, end);
    if (source != end) return NULL;
    return root;
}