From 2ee659846b7ffa5791775465975b93e47ea81a4e Mon Sep 17 00:00:00 2001 From: misomosi Date: Sun, 21 Jun 2026 17:38:33 -0400 Subject: [PATCH] Port JSON parser from miso's github --- dumb-json-parser/.gitignore | 41 +++ dumb-json-parser/LICENSE | 24 ++ dumb-json-parser/README.md | 2 + dumb-json-parser/main.c | 548 ++++++++++++++++++++++++++++++++++++ 4 files changed, 615 insertions(+) create mode 100644 dumb-json-parser/.gitignore create mode 100644 dumb-json-parser/LICENSE create mode 100644 dumb-json-parser/README.md create mode 100644 dumb-json-parser/main.c diff --git a/dumb-json-parser/.gitignore b/dumb-json-parser/.gitignore new file mode 100644 index 0000000..d4fb281 --- /dev/null +++ b/dumb-json-parser/.gitignore @@ -0,0 +1,41 @@ +# Prerequisites +*.d + +# Compiled Object files +*.slo +*.lo +*.o +*.obj + +# Precompiled Headers +*.gch +*.pch + +# Linker files +*.ilk + +# Debugger Files +*.pdb + +# Compiled Dynamic libraries +*.so +*.dylib +*.dll + +# Fortran module files +*.mod +*.smod + +# Compiled Static libraries +*.lai +*.la +*.a +*.lib + +# Executables +*.exe +*.out +*.app + +# debug information files +*.dwo diff --git a/dumb-json-parser/LICENSE b/dumb-json-parser/LICENSE new file mode 100644 index 0000000..fdddb29 --- /dev/null +++ b/dumb-json-parser/LICENSE @@ -0,0 +1,24 @@ +This is free and unencumbered software released into the public domain. + +Anyone is free to copy, modify, publish, use, compile, sell, or +distribute this software, either in source code form or as a compiled +binary, for any purpose, commercial or non-commercial, and by any +means. + +In jurisdictions that recognize copyright laws, the author or authors +of this software dedicate any and all copyright interest in the +software to the public domain. We make this dedication for the benefit +of the public at large and to the detriment of our heirs and +successors. We intend this dedication to be an overt act of +relinquishment in perpetuity of all present and future rights to this +software under copyright law. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +OTHER DEALINGS IN THE SOFTWARE. + +For more information, please refer to diff --git a/dumb-json-parser/README.md b/dumb-json-parser/README.md new file mode 100644 index 0000000..05bff92 --- /dev/null +++ b/dumb-json-parser/README.md @@ -0,0 +1,2 @@ +# dumb-json-parser +A really dumb, private JSON parser I wrote in C to prove I could do it KEKW diff --git a/dumb-json-parser/main.c b/dumb-json-parser/main.c new file mode 100644 index 0000000..4c2600a --- /dev/null +++ b/dumb-json-parser/main.c @@ -0,0 +1,548 @@ +#include +#include +#include +#include +#include +#include + +struct json_value; +struct json_object_list; +struct json_array_list; +struct json_string { + const char *val; + size_t len; +}; + +union json_value_raw { + struct json_string str; + struct json_object_list *obj; + struct json_array_list *arr; + double num; +}; + +enum json_tag { + JSON_ERR, + JSON_TRUE, + JSON_FALSE, + JSON_NULL, + JSON_NUM, + JSON_STR, + JSON_OBJ, + JSON_ARR, +}; + +struct json_value { + int tag; + union json_value_raw raw; +}; + +struct json_object_list { + struct json_object_list *next; + struct json_string key; + struct json_value val; +}; + +struct json_array_list { + struct json_array_list *next; + struct json_value val; +}; + + +// Forward declarations +static struct json_value json_parse(const char **p_json, size_t *p_json_len, void **p_mem, size_t *p_cap, size_t *p_len); + +static void *mem_grow(void **p_mem, size_t *p_cap, size_t *p_len, size_t sz, size_t align) +{ + if (!p_mem || !p_cap || !p_len || (align & (align - 1))) + return (void *)0; + char *mem_base = *p_mem; + size_t cap = *p_cap, len = *p_len; + + size_t len_new = ((len + (align - 1)) & ~(align - 1)); + if (len_new < len) + return (void *)0; + size_t mem_ret_offset = len_new; + + len_new += sz; + if (len_new < len) + return (void *)0; + + // We don't realloc the memory because that would move it + // Instead, establish a max memory limit and fail if not met + if (len_new > cap) + return (void *)0; + *p_len = len_new; + return &mem_base[mem_ret_offset]; +} + +// Most JSON uses ASCII for tokenization instead of code points, so +// this is (thankfully) rarely used. We only use it in the string parsing +// because most code points are acceptable in a JSON string +static int json_codepoint_next(const char **p_json, size_t *p_json_len) +{ + if (!p_json || !p_json_len) + return -1; + const unsigned char *json = (const unsigned char *)*p_json; + size_t json_len = *p_json_len; + if (json_len < 1) + return -1; + + // Find number of bytes in the code point and check that format is correct + unsigned int codepoint = json[0]; + size_t nbytes = 1; + while (nbytes < 5 && nbytes < json_len && (json[nbytes] & 0xc0) == 0x80) + nbytes++; + unsigned int mask = 0x80; + unsigned int expect = 0x00; + if (nbytes > 1) { + mask = (1 << 8) - (1 << (7 - nbytes)); + expect = mask - (1 << (8 - nbytes)); + } + if (nbytes == 5 || (codepoint & mask) != expect) + return -1; + + // Now get the value of the codepoint and check it against the max UTF codepoint + codepoint = (codepoint & ~mask) << 6 * (nbytes - 1); + for (size_t i = 1; i < nbytes; i++) + codepoint |= (json[i] & 0x3f) << 6 * (nbytes - 1 - i); + + // Reject overlong encodings and non-existant codepoints + unsigned int overlong_check = 0; + switch (nbytes) + { + case 2: overlong_check = 0x80u; break; + case 3: overlong_check = 0x800u; break; + case 4: overlong_check = 0x10000u; break; + default: break; + } + if (codepoint > 0x10ffffu || codepoint < overlong_check) + codepoint = -1; + *p_json_len = json_len - nbytes; + *p_json += nbytes; + return codepoint; +} + +static int json_codepoint_emit(int codepoint, void **p_mem, size_t *p_cap, size_t *p_len) +{ + if (codepoint < 0 || codepoint > 0x10ffff) + return -1; + + int nbytes = 0; + if (codepoint < 0x80) + nbytes = 1; + else if (codepoint < 0x800) + nbytes = 2; + else if (codepoint < 0x10000) + nbytes = 3; + else + nbytes = 4; + + unsigned char *mem = mem_grow(p_mem, p_cap, p_len, nbytes, 1); + if (!mem) + return -1; + for (int i = nbytes - 1; i > 0; i--) { + mem[i] = (codepoint & 0x3f) | 0xc0; + codepoint >>= 6; + } + unsigned int mask = 0xff; + if (nbytes != 1) + mask = (1 << (7 - nbytes)) - 1; + mem[0] = (codepoint & mask) | ~(mask << 1 | 1); + return codepoint; +} + +static void json_parse_whitespace(const char **p_json, size_t *p_json_len) +{ + if (!p_json || !p_json_len) + return; + + // For some reason, in the official JSON spec, vertical tabs + // do not count as white space. For completeness sake, be strict + const char *json = *p_json; + size_t json_len = *p_json_len; + size_t i = 0; + for (; i < json_len; i++) + if (!isspace(json[i]) || json[i] == '\v') + break; + *p_json = json + i; + *p_json_len = json_len - i; +} + +static struct json_value json_parse_number(const char **p_json, size_t *p_json_len) +{ + struct json_value v = {JSON_ERR}; + size_t i = 0; + + if (!p_json || !p_json_len) + return v; + + const char *json = *p_json; + size_t json_len = *p_json_len; + if (i >= json_len) + return v; + + // There can be a negative sign, and there must be at least one digit + char digit = json[i]; + if (digit == '-') { + i++; + if (i >= json_len) + return v; + else + digit = json[i]; + } + if (!isdigit(digit)) + return v; + + // If the digit is 0, then this must be the only digit + // Otherwise, keep parsing digits + if (digit != '0') { + while (i < json_len && isdigit(digit = json[i])) + i++; + } + + // If there's a dot, then it's a fraction and any non-empty string of digits follow + if (digit == '.') { + i++; + if (i >= json_len || !isdigit(digit = json[i])) + return v; + i++; + while (i < json_len && isdigit(digit = json[i])) + i++; + } + // If there's an e, then it's an exponent and a sign with any non-empty string of digits follows + if (digit == 'e' || digit == 'E') { + i++; + if (i >= json_len) + return v; + digit = json[i]; + if (digit == '-' || digit == '+') { + i++; + if (i >= json_len) + return v; + else + digit = json[i]; + } + while (i < json_len && isdigit(digit = json[i])) + i++; + } + // Now we want to parse the result via strtod + // which, unfortunately, needs a null-terminated string :( + char *nullterm = malloc(i + 1); + if (nullterm) { + memcpy(nullterm, json, i); + nullterm[i] = 0; + errno = 0; + v.raw.num = strtod(nullterm, 0); + + free(nullterm); + if (!errno) { + v.tag = JSON_NUM; + *p_json += i; + *p_json_len -= i; + } + } + return v; +} + +static struct json_value json_parse_string(const char **p_json, size_t *p_json_len, void **p_mem, size_t *p_cap, size_t *p_len) +{ + struct json_value v = {JSON_ERR}; + + if (!p_json || !p_json_len || !p_mem || !p_cap || !p_len) + return v; + + const char *json = *p_json; + size_t json_len = *p_json_len; + + // We don't want the changes to json and json len to persist if this function fails + int codepoint = json_codepoint_next(&json, &json_len); + if (codepoint != '"') + return v; + + size_t mark = *p_len; + while ((codepoint = json_codepoint_next(&json, &json_len)) != '"') { + // Control characters not directly allowed, must be escaped + if (iscntrl(codepoint) || codepoint < 0) + return v; + + if (codepoint == '\\') { + if (json_len == 0) + return v; + codepoint = *json++; + json_len--; + + switch (codepoint) { + case '"': codepoint = '"'; break; + case '\\': codepoint = '\\'; break; + case '/': codepoint = '/'; break; + case 'b': codepoint = '\b'; break; + case 'f': codepoint = '\f'; break; + case 'n': codepoint = '\n'; break; + case 'r': codepoint = '\r'; break; + case 't': codepoint = '\t'; break; + case 'u': + if (json_len < 4) + return v; + codepoint = 0; + for (size_t i = 0; i < 4; i++) { + int digit = 0; + char c = tolower(json[i]); + if (c >= '0' && c <= '9') + digit = (c - '0'); + else if (c >= 'a' && c <= 'f') + digit = (c - 'a' + 10); + else + return v; + codepoint <<= 4; + codepoint |= digit; + } + json += 4; + json_len -= 4; + break; + default: + return v; + } + } + if (json_codepoint_emit(codepoint, p_mem, p_cap, p_len) < 0) + return v; + } + v.tag = JSON_STR; + v.raw.str.val = &((const char *)*p_mem)[mark]; + v.raw.str.len = *p_len - mark; + *p_json_len = json_len; + *p_json = json; + return v; +} + +static struct json_value json_parse_keyword(const char **p_json, size_t *p_json_len) +{ + struct json_value v = {JSON_ERR}; + if (!p_json || !p_json_len) + return v; + const char *json = *p_json; + size_t json_len = *p_json_len; + if (json_len >= 5) { + json_len -= 5; + if (!memcmp("false", json, 5)) + v.tag = JSON_FALSE; + else + json_len += 5; + } else if (json_len >= 4) { + json_len -= 4; + if (!memcmp("null", json, 4)) + v.tag = JSON_NULL; + else if (!memcmp("true", json, 4)) + v.tag = JSON_TRUE; + else + json_len += 4; + } + return v; +} + +static struct json_value json_parse_array(const char **p_json, size_t *p_json_len, void **p_mem, size_t *p_cap, size_t *p_len) +{ + struct json_value v = {JSON_ERR}; + + if (!p_json || !p_json_len || !p_cap || !p_len || !p_mem) + return v; + + const char *json = *p_json; + size_t json_len = *p_json_len; + if (json_len < 1 || *json != '[') + return v; + json++; + json_len--; + + json_parse_whitespace(&json, &json_len); + if (json_len > 0 && *json == ']') { + *p_json = json + 1; + *p_json_len = json_len - 1; + v.tag = JSON_ARR; + return v; + } + + struct json_array_list **p_next = &v.raw.arr; + do { + struct json_value element = json_parse(&json, &json_len, p_mem, p_cap, p_len); + if (element.tag == JSON_ERR) + return element; + struct json_array_list *node = mem_grow(p_mem, p_cap, p_len, sizeof(*node), sizeof(void *)); + if (!node) + return v; + node->val = element; + node->next = (struct json_array_list *)0; + *p_next = node; + p_next = &node->next; + + char c = json_len ? *json++ : 0; + json_len--; + switch (c) { + case ',': break; + case ']': + *p_json = json; + *p_json_len = json_len; + v.tag = JSON_ARR; + // fallthrough + default: + return v; + } + } while(1); + return v; +} + +static struct json_value json_parse_object(const char **p_json, size_t *p_json_len, void **p_mem, size_t *p_cap, size_t *p_len) +{ + struct json_value v = {JSON_ERR}; + + if (!p_json || !p_json_len || !p_cap || !p_len || !p_mem) + return v; + + const char *json = *p_json; + size_t json_len = *p_json_len; + if (json_len < 1 || *json != '{') + return v; + json++; + json_len--; + + json_parse_whitespace(&json, &json_len); + if (json_len > 0 && *json == '}') { + *p_json = json + 1; + *p_json_len = json_len - 1; + v.tag = JSON_OBJ; + return v; + } + + struct json_object_list **p_next = &v.raw.obj; + do { + json_parse_whitespace(&json, &json_len); + struct json_value key = json_parse_string(&json, &json_len, p_mem, p_cap, p_len); + json_parse_whitespace(&json, &json_len); + if (key.tag == JSON_ERR) + return key; + + if (json_len == 0 || *json != ':') + return v; + json++; + json_len--; + + struct json_value element = json_parse(&json, &json_len, p_mem, p_cap, p_len); + if (element.tag == JSON_ERR) + return element; + struct json_object_list *node = mem_grow(p_mem, p_cap, p_len, sizeof(*node), sizeof(void *)); + if (!node) + return v; + node->key = key.raw.str; + node->val = element; + node->next = (struct json_object_list *)0; + *p_next = node; + p_next = &node->next; + + json_parse_whitespace(&json, &json_len); + if (json_len < 1) + return v; + + char c = *json++; + json_len--; + switch (c) { + case ',': break; + case '}': + *p_json = json; + *p_json_len = json_len; + v.tag = JSON_OBJ; + // fallthrough + default: + return v; + } + } while(1); + return v; +} + +// Parse a JSON value and return the memory for the value to free later +// NOTE: We don't realloc memory anymore, no freeing to be done +static struct json_value json_parse(const char **p_json, size_t *p_json_len, void **p_mem, size_t *p_cap, size_t *p_len) +{ + struct json_value v = {JSON_ERR}; + + if (!p_json || !p_json_len || !p_cap || !p_len || !p_mem) + return v; + json_parse_whitespace(p_json, p_json_len); + if (!*p_json_len) + return v; + + switch (**p_json) { + case '"': + v = json_parse_string(p_json, p_json_len, p_mem, p_cap, p_len); break; + case '-': + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + v = json_parse_number(p_json, p_json_len); break; + case '[': + v = json_parse_array(p_json, p_json_len, p_mem, p_cap, p_len); break; + case '{': + v = json_parse_object(p_json, p_json_len, p_mem, p_cap, p_len); break; + default: + v = json_parse_keyword(p_json, p_json_len); break; + } + // White space can be after the value and this is acceptable + // If it is an error, don't clean up memory, still let user clean it up + if (v.tag != JSON_ERR) + json_parse_whitespace(p_json, p_json_len); + return v; +} + +static void json_dump(struct json_value val) { + switch (val.tag) { + case JSON_ERR: printf("Parsing failed. KEKW!"); break; + case JSON_NUM: printf("%lf", val.raw.num); break; + case JSON_STR: printf("\"%.*s\"", (int)val.raw.str.len, val.raw.str.val); break; + case JSON_TRUE: printf("true"); break; + case JSON_NULL: printf("null"); break; + case JSON_FALSE: printf("false"); break; + case JSON_ARR: + putc('[', stdout); + for (struct json_array_list *node = val.raw.arr; node; node = node->next) { + json_dump(node->val); + if (node->next) + putc(',', stdout); + } + putc(']', stdout); + break; + case JSON_OBJ: + putc('{', stdout); + for (struct json_object_list *node = val.raw.obj; node; node = node->next) { + json_dump((struct json_value){JSON_STR,{node->key}}); + putc(':', stdout); + json_dump(node->val); + if (node->next) + putc(',', stdout); + } + putc('}', stdout); + break; + default: break; + } +} + +size_t mem_reserve[(1 << 28) / sizeof(size_t)]; +int main(int argc, char **argv) +{ + void *mem = mem_reserve; + size_t cap = sizeof(mem_reserve), len = 0; + if (argc < 2) { + fprintf(stderr, "%s \n", argv[0]); + return 1; + } + const char *json = argv[1]; + size_t json_len = strlen(json); + struct json_value val = json_parse(&json, &json_len, &mem, &cap, &len); + json_dump(val); + putc('\n', stdout); + return 0; +} -- 2.49.1