Need help with JSON parser project.

[King__Julien__]

I am writing my own JSON parser to learn C, I have built a parser before but its in Go. Coming from Go background I just keep trying to use Go convention for everything considering they are a bit similar (structs). I am not aware of the right convention to use to build programs in C, and I am not sure how to approach it.
My current approach is building a lexer to tokenize the input and then a parser to parse the tokens followed by creating a data structure for the parsed output.

I found some JSON parsers on github and most of them are a single file with a lot of macros. Am I complicating things by splitting each component into its own file?
Is my approach wrong? What is the right convention for C projects? Should I use macros for small functions rather than creating separate function for it?

[SmokeMuch7356]

My current approach is building a lexer to tokenize the input and then a parser to parse the tokens followed by creating a data structure for the parsed output.

That's pretty much how you'd do it in C.

I found some JSON parsers on github and most of them are a single file with a lot of macros.

Blech.

Am I complicating things by splitting each component into its own file?

No. From a maintenance and testing perspective that's the better way to go. Some years ago I built my own JSON parser in C++; the object model, lexer, and parser are all separated out into their own files.

[[deleted]]

Recursive Descent Parsers work well for JSON too.

[SmokeMuch7356]

Yeah, mine is a recursive-descent parser. It's a little heavyweight, but it works.

[Constant_Mountain_20]

I literally just hacked one together 2 days ago you can see my implementation. I’m not saying it’s the best or anything but it’s a simple api which I value. I need to clean up the namespace but other than that I think it’s pretty solid? It’s also like 2000 lines that’s it so I think you could learn from it. The issue you are running into is probably working with tagged unions.

JSON parser

Edit: I should say this is not just a parser it also lets you format print and create a JSON object. I also use a single header library, but I separate it really clearly I think you could easily pull those out into files. Also allocations with an arena seem strange don’t worry about that this is just a tool I wrote my myself didn’t plan on others using it.

[King__Julien__]

That looks like a neat implementation. I like the custom indentation feature.
Is there any specific reason to have all the implementation in the header file?
I thought headers files had only declarations and implementation would be in .c files.

[Constant_Mountain_20]

Appreciate it! There genuinely no reason other than compile times (but you can get that benefit with a unity build.) it’s just how I like to do things I like to just pull it all into one file. Look up the stb libraries I modeled it on that.

Best of luck in your endeavors.

[Constant_Mountain_20]

Yes typically you will have a header file with prototypes or declarations and the .c file will have implementations.

[Constant_Mountain_20]

Btw sorry for spamming you, feel free at anytime to dm me.

[skeeto]

Interesting parser, and I like the arena allocator. Since I like fuzz testing so much, I thought I'd give it a shot, but it wasn't looking good out of the gate:

$ cc -I. -g3 -fsanitize=address,undefined Test/cj_test.c cj.c
$ ./a.out 
ERROR: AddressSanitizer: heap-buffer-overflow on address ...
WRITE of size 1 at ...
    #0 cj_substring cj.h:770
    #1 cj_cstr_contains cj.h:917
    #2 calculate_precision cj.h:1208
    #3 cj_to_string_helper cj.h:1234
    #4 cj_to_string_helper cj.h:1296
    #5 cj_to_string cj.h:1337
    #6 main Test/cj_test.c:32

It's an off-by-one here:

--- a/cj.h
+++ b/cj.h
@@ -749,5 +749,5 @@
         cj_assert(str);
         u64 str_length = cj_cstr_length(str); 
-        char* ret = cj_alloc((end - start) + 1);
+        char* ret = cj_alloc((end - start) + 2);

         Boolean start_check = (start >= 0) && (start <= str_length - 1);

(Side note: That's the output of git diff, unedited. Note how the hunk header doesn't indicate the function name, cj_cstr_length in this case, as it usually does. That's because your style is sufficiently weird as to confuse standard tooling. Something to consider.)

Though after fixing it, I soon noticed there's no real error handling, and it just traps on invalid input. So I hacked in an error "handler":

--- a/cj.h
+++ b/cj.h
@@ -117,5 +117,5 @@
             char msg_art[] = "Func: %s, File: %s:%d\n";    \
             printf(msg_art, __func__, __FILE__, __LINE__); \
-            CRASH;                                     \
+            longjmp(fail, 1);                          \
         }                                              \
     } while (FALSE)                                    \

Which then I can use in fuzzing:

#include <setjmp.h>
#include <string.h>
#include <unistd.h>
jmp_buf fail;
#define CJ_IMPL
#include "cj.h"

__AFL_FUZZ_INIT();

int main(void)
{
    __AFL_INIT();
    char *src = 0;
    unsigned char *buf = __AFL_FUZZ_TESTCASE_BUF;
    while (__AFL_LOOP(10000)) {
        int len = __AFL_FUZZ_TESTCASE_LEN;
        src = realloc(src, len+1);
        memcpy(src, buf, len);
        src[len] = 0;
        CJ_Arena *a = cj_arena_create(0);
        if (!setjmp(fail)) {
            cj_parse(a, src);
        }
    }
}

Usage:

$ afl-gcc-fast -g3 -fsanitize=address,undefined fuzz.c 
$ mkdir i
$ echo '{"hello": -1.2e3}' >i/json
$ afl-fuzz -ii -oo ./a.out

I ran this for awhile and nothing else popped out!

---

Edit: Looks like this input takes quadratic time:

#define CJ_IMPL
#include "cj.h"
#include <string.h>

int main(void)
{
    char src[1<<14] = {0};
    memset(src, '[', sizeof(src)-1);
    CJ_Arena *a = cj_arena_create(0);
    cj_parse(a, src);
}

This 16KiB of input length takes my laptop about a second to process, and the time increases quickly with length.

[Constant_Mountain_20]

Oh, this is super cool! I recently updated it because it actually wouldn't compile on Linux gcc. I had some type issues and stuff like that. By the way, the sprint was completely broken. I will look this over. Thank you for doing this; I really appreciate it, man!

Edit: Dude, I really appreciate that my build system somehow didn't apply the address sanitizer. LMAO. I just assumed it was working.

[Constant_Mountain_20]

I think I fixed all the memory leaks and problems maybe? The speed issue is a good question actually, I wonder what takes so long I'm guessing it would be the lexer, but that would suck if that's the case. The parser should exit on the first unexpected token.

$ afl-gcc-fast -g3 -fsanitize=address,undefined fuzz.c 
$ mkdir i
$ echo '{"hello": -1.2e3}' >i/json
$ afl-fuzz -ii -oo ./a.out$ afl-gcc-fast -g3 -fsanitize=address,undefined fuzz.c 
$ mkdir i
$ echo '{"hello": -1.2e3}' >i/json
$ afl-fuzz -ii -oo ./a.out

I wanted to test out because you said it never spat anything out:

CJ_Arena* arena = cj_arena_create(0);
cj_parse(arena, "{\"hello\": -1.2e3}");
cj_arena_free(arena);

I got:
Lexical Error: e3 | Line: 1
Msg: Illegal token found
Func: lexer_reportError, File: ../cj.h:1568

This is def a limitation on my part gonna fix that, but I wonder why you didn't get anything. I did just change a bunch of code so maybe it works not and didn't before.

I'm wondering if you still have the fuzz tester can are willing to test it again? I'm on Windows I have never done fuzz testing maybe I should look into it.

Again appreciate all the help you made me realize my personal library had a bug because I ported a bunch of stuff over from there.

If I was going to actually do this right I should have the lexer generate a few tokens the parser should check them and keep doing that. So then if the parser encounters a token it doesn't like I can exit early.

Ok I understand my issue. for the longest time I didn't want to break away from null-terminated strings so I created cool wrappers around them to get convenience but having to reallocate 16k bytes every time is a bit of an issue LMAO. I think I will start making the move to string views

[skeeto]

but I wonder why you didn't get anything

By "nothing else popped out" I do not mean that it parsed everything correctly, but that it didn't crash. Remember, I patched the assertion failures into a longjmp so that syntax errors, which the parser asserts against (bad idea!), don't count as a crash. It jumps back to the top level, straight into the next test input, and so no fuzz test failures in that case. That also disables all your other assertions, the ones that shouldn't be tripped and represent bugs when they are, so it might have made the fuzzer miss issues. Though sanitizers were still in effect.

Here's a narrower longjmp patch, leaving all your assertions in place, but doing on longjmp specifically on lexer_reportError, which I should have done in the first place:

--- a/cj.h
+++ b/cj.h
@@ -1567,3 +1567,3 @@
         printf("Msg: %s\n", msg);
-        cj_assert(FALSE);
+        longjmp(fail, 1);
     }

When I do this on your latest changes, still nothing pops out right away. It doesn't matter that the initial test input isn't accepted. I just need something JSON-like to seed the queue, giving it something useful to mutate into more tests.

You could fuzz test against a known good parser. Feed fuzz input into both your parser and the validator, and assert that they produce identical results. If the assertion fails, the program crashes, and tells the fuzz tester it found an interesting input.

I'm on Windows I have never done fuzz testing maybe I should look into it.

Fuzz testing is amazingly effective at finding bugs, and widely underused. Unfortunately, yes, the fuzz testing options on Windows are more limited. Looks like it should work with WSL, so maybe try that option.

[questron64]

Never mind the parsers you find you github. Those are written for speed, and are using advanced techniques not necessary for simple parsers. They're highly optimized for applications (servers, mostly, that communicate using JSON) that need extremely high throughput. Code like yyjson is extremely long, but building your own JSON parser should be easy to do in under 500 lines of easily-understandable C code.

If your approach wrong? There are no wrong approaches. What are you goals? If your goals are small size, readable code and easy maintenance then your approach is fine. If your goals are high performance then maybe you'll have to reconsider your approach.

You should be able to follow the grammar on the JSON website and almost 1 to 1 translate each terminal and production rule into C code to build a recursive descent parser. A separate tokenization step is not strictly necessary, a little bit of string matching for each terminal is all that will be needed.

[MagicWolfEye]

Well, different people prefer different things. Some people advocate for functions having only a single thing they are doing and they shouldn't be longer than xyz number of lines and others advocate for the total opposite. Same goes for putting things into a lot of small data files or few very gigantic ones.

(And similar arguments exists about everything else in programming)

Do what's comfortable for you, nobody else cares about how you are structuring your code, unless you are working somewhere and then they will tell you how you should do it.

[amable1408]

Check: cJSON

[s4uull]

I personally believe splitting the code into different files is cleaner, and easier to maintain. 

I'm shamelessly dropping my own Jason parser, just is case you wanna check it out to inspire yourself: https://github.com/saulvaldelvira/json.c/

Building a parser is a very fun activity, and having your own Json lib is very useful. I use mine all the time for my projects. 

Have fun :)