In this article, I'll walk you through a JSON validator in C that I wrote. A lot of popular programming languages have some way to parse a string of JSON. I wanted to come up with a way to bring JSON (as defined by RFC 8259 ) into CLIPS, but I wasn't quite pleased with existing JSON parsing libraries. This will be a "base" from which I write a JSON-to-CLIPS library next.
There are some really cool
JSON
parsers in C on GitHub, and I had fun writing a few
proof-of-concepts with
cJSON,
yajl,
and
jsmn.
cJSON was super simple to use, but it provided so many
options that I didn't want (including one to
allow
junk after a valid portion of the string) that I decided to look
elsewhere. yajl is a tried-and-true library developed by
Loid Hilaiel. It
provides a nice bring-your-own data structure approach, but I didn't
want the sort-of "framework" functionality that it provides.
jsmn really struct me as an awesome implementation.
However, like the other two, it initializes structs that I
don't need. On top of all of this, every one of those libraries uses
goto, which I'm personally not a fan of.
I decided to take jsmn's implementation and make it my own.
What I ended up with was a JSON validator that does not initialize
structs and only uses 1 int variable. I also wrote a test
suite to make sure changes I made over time did not introduce
regressions. While there is still room for improvement, I'm happy with
the effort, and I'll use this for a JSON-to-CLIPS implementation in the
coming weeks/months/whatevers. Now: on with the article!
First, the test suite setup.
test.c
loads in files from test/valid and
test/invalid in order to test both valid and invalid JSON
strings respectively. If it hits an error, it exits immediately. To add
a new valid or invalid case, add a file to those directories containing
the string in question. Here's what that looks like:
$ make test gcc -c validatejson.c gcc -o tests/test tests/test.c validatejson.o ./tests/test Test results: ================ PASS rm ./tests/test validatejson.o
Here's what it looks like when I add a valid json file to
the test/invalid directory:
$ echo "{}" > tests/invalid/foo.json
$ make test
gcc -c validatejson.c
gcc -o tests/test tests/test.c validatejson.o
./tests/test
Test results:
================
ERROR: {}
should be invalid!
rm ./tests/test validatejson.o
Here's what it looks like when I add an invalid json file
to the test/valid directory:
$ echo "}" > tests/valid/foo.json $ make test gcc -c validatejson.c gcc -o tests/test tests/test.c validatejson.o ./tests/test Test results: ================ ERROR: } should be valid! rm ./tests/test validatejson.o
I separated this out into two files: one file is meant to be included in
projects as a library, the other: a project that uses the aforementioned
library. This let me "dog food" my library. Take a look at
main.c.
This is a slightly more complex version of the example given in the
README.md
file. Here's its output:
$ make
gcc -c validatejson.c
gcc -o validatejson main.c validatejson.o
$ ./validatejson
USAGE
validatejson checks whether the argument passed is a valid string of JSON
Example:
validatejson '{ "foo": [ 1, 2, "Bar!" ] }'
$ ./validatejson '{ "foo": [ 1, 2, "Bar!" ] }'
PASS
$ ./validatejson '{ "foo": [ 1, 2, "Bar! ] }'
ERROR: { "foo": [ 1, 2, "Bar! ] } is invalid!
The main purpose of this binary is to demonstrate
usage
of the underlying function validateJSON which is
provided by the library:
#include <stdio.h> #include "validatejson.h" int main(int argc, char *argv[]) { if (argc == 1) { printf("USAGE\nvalidatejson checks whether the argument passed is a valid string of JSON\n\nExample:\n\tvalidatejson '{ \"foo\": [ 1, 2, \"Bar!\" ] }'\n"); return 0; } else if (argc == 2) { if (!validateJSON(argv[1])) { printf("ERROR: %s is invalid!\n", argv[1]); return -1; } printf("PASS\n"); return 0; } return -1; }
Let's have a look at the "entry" function: validateJSON:
bool validateJSON(const char *jsonString) { int cursor = 0; return validateJSONString(jsonString, &cursor, strlen(jsonString)); }
Super straightforward. Its main purpose is to store the context of our
cursor. This cursor will iterate over every
character in the passed string and determine if it's a valid character
at that point in the string according to
RFC
8259. We also pass in the calculated length of the
passed string. This provides defaults for our validator. If the
programmer wanted to start at a later character in a string, or if the
programmer wanted to limit the validation check to a certain number of
characters, they could pass their own into
validateJSONString:
bool validateJSONString(const char *jsonString, int *cursor, int length) { return validateJSONElement(jsonString, cursor, length) && ( (*cursor) == length || ++(*cursor) && skipWhitespace(jsonString, cursor, length) && (*cursor) == length ); }
This function is a convenient way of saying "the string must only contain one valid JSON element at the top level." We validate the first JSON element (as defined in the RFC), and then we make sure there is only whitespace trailing it.
Let's look at the next "layer:" validateJSONElement:
bool validateJSONElement(const char *jsonString, int *cursor, int length) { skipWhitespace(jsonString, cursor, length); switch (jsonString[*cursor]) { case '"': return validateString(jsonString, cursor, length); case '[': return validateArray(jsonString, cursor, length); case '{': return validateObject(jsonString, cursor, length); case 't': case 'f': case 'n': return validateBoolean(jsonString, cursor, length); case '-': (*cursor)++; default: return validateNumber(jsonString, cursor, length); } }
First thing first: since we're at the beginning of the string, we can
safely skip over whitespace. The next character we encounter must be a
string, an array, an object, a boolean, a null, or a number. strings
must start with a ", arrays must start with a
[, and objects start with a {. We check for
true, false and null in
validateBoolean, so we look for their starting characters
t, f, or n. Finally, numbers can
either begin with a - in the case of negatives or
0 through 9. By default, we'll go int to
validateNumber which will return false if the
cursor is not on a valid number:
bool validateNumber(const char *jsonString, int *cursor, int length) { return validateAtLeastOneInteger(jsonString, cursor, length) && validateFraction(jsonString, cursor, length) && validateExponent(jsonString, cursor, length) && ( jsonString[*cursor] == '}' || jsonString[*cursor] == ']' || jsonString[*cursor] == ',' || jsonString[*cursor] == ' ' || jsonString[*cursor] == '\t' || jsonString[*cursor] == '\r' || jsonString[*cursor] == '\n' || jsonString[*cursor] == '\0' ) && (*cursor)--; }
The first thing we're going to do is verify there is at least one integer:
bool validateAtLeastOneInteger(const char *jsonString, int *cursor, int length) { if ( jsonString[*cursor] < 48 || jsonString[*cursor] > 57 ) return false; do (*cursor)++; while ( *cursor < length && jsonString[*cursor] >= 48 && jsonString[*cursor] <= 57 ); return true; }
In C, we can check the int representation of a
char value. Conveniently, digits 0 through
9 are represented as ints 48 to
57, so we make sure the int the
cursor is on is between those two.
Once we've confirmed we're on an integer, we skip characters in the
string until we get to a non-integer. Using a do-while loop
lets us move the cursor forward once. This is nice since we've already
checked the character the current cursor is on.
The next non-integer character we should run into is a period
. to signify a fraction or an e/E
to signify an exponent. validateFraction and
validateExponent, which are called after we've hit a
non-integer character, will return with true if the
character we're on is not . or
e/E. This lets us "fall through" to the end of
our potential JSON number to make sure it "ends" properly:
bool validateFraction(const char *jsonString, int *cursor, int length) { return jsonString[*cursor] != '.' || (*cursor)++ && validateAtLeastOneInteger(jsonString, cursor, length); } bool validateExponent(const char *jsonString, int *cursor, int length) { return ( jsonString[*cursor] != 'e' && jsonString[*cursor] != 'E' ) || (*cursor)++ && ( ( jsonString[*cursor] == '-' || jsonString[*cursor] == '+' ) && (*cursor)++ || true ) && validateAtLeastOneInteger(jsonString, cursor, length); }
If we do find a . or e/E, we move
the cursor forward and begin validating that we have the proper
characters after this character in each function. For the fraction, we
make sure that we have at least one integer. For the exponent, we allow
an optional + or - sign. Then, we make sure we
have at least one integer.
validateNumber then checks for a character that signifies
the "end" of the number, then we move the cursor back one.
This is a potential place of improvement for our algorithm; we must ask
ourselves "how can we re-write this logic such that we only ever move
the cursor forward?" For now, I'm not sure. But that's ok: our current
approach works, and "perfect is the enemy of done."
Now that our cursor is on the end of a valid JSON number,
we can make sure that any "surrounding" JSON element is "closed" or
"continued" correctly. Control of our program will return to the "outer"
function calls, and validation will continue. If this string only
contains a number, we'll verify that there are no characters after the
JSON number.
The next "easy" validation to wrap our minds around is
validateBoolean since this checks for three specific series
of characters: true, false, or
null.
bool validateBoolean(const char *jsonString, int *cursor, int length) { return ( strncmp(jsonString + (*cursor), "true", 4) == 0 || strncmp(jsonString + (*cursor), "null", 4) == 0 ) && (*cursor = (*cursor) + 3) || strncmp(jsonString + (*cursor), "false", 5) == 0 && (*cursor = (*cursor) + 4); }
Given that the cursor is at the beginning of one of these
three specific words, we use strncmp (built into C's
string.h library) to check it and the following characters
for a match. strncmp returns 0 if we have a
match, so we just return the boolean value of a comparison check for
that integer. We also return (*cursor)++ which itself will
be an int. This is convenient because our
cursor will be an int greater than
0. This equates to true in C, while
0 itself equates to false. One gotcha: C will
return *cursor before it increments
*cursor, so if we ever need to return the value of
*cursor after it's been incremented, we'd need to
use ++(*cursor). That's why we do ++(*cursor)
in validateJSONString. This allows us to consider the case
of a single-digit number like 1. Since 1 would
be valid JSON, and our *cursor would be on index
0, our return statement would be false.
One last thing before we move on: (*cursor = (*cursor) + 4)
can be returned. It'll return the int which is the result
of (*cursor) + 4. It'll also set the value of
cursor. Convenient!
validateArray is next. By default, we'll allow for an empty
array []. Else, we'll make sure the following content is a
valid JSON element, then we'll make sure the array ends properly:
bool validateArray(const char *jsonString, int *cursor, int length) { (*cursor)++; skipWhitespace(jsonString, cursor, length); return jsonString[*cursor] == ']' || validateJSONElement(jsonString, cursor, length) && validateEndOfArray(jsonString, cursor, length); }
Note that we need to first advance the *cursor since the
only reason we're in this function is that we've determined we've hit
the start of an array with [ in
validateJSONElement.
Before we take a look at validateEndOfArray, let's have a
look at skipWhitespace:
bool skipWhitespace(const char *jsonString, int *cursor, int length) { while ( *cursor < length && ( validateCharAndAdvanceCursor(jsonString, cursor, ' ') || validateCharAndAdvanceCursor(jsonString, cursor, '\t') || validateCharAndAdvanceCursor(jsonString, cursor, '\r') || validateCharAndAdvanceCursor(jsonString, cursor, '\n') ) ); return true; }
This one has a funky-looking while loop. The
while will loop until the check returns false,
and this will only happen until your cursor is at the end of the string
or when the cursor is on a whitespace. Each
validateCharAndAdvanceCursor does exactly what you think it
should do:
bool validateCharAndAdvanceCursor(const char *jsonString, int *cursor, char c) { return jsonString[*cursor] == c && ++(*cursor); }
The while loop in skipWhitespace doesn't need
a body because all of the work is done by advancing the cursor in
validateCharAndAdvanceCursor.
Ok, as promised: here's validateEndOfArray:
bool validateEndOfArray(const char *jsonString, int *cursor, int length) { (*cursor)++; skipWhitespace(jsonString, cursor, length); return jsonString[*cursor] == ']' || validateCharAndAdvanceCursor(jsonString, cursor, ',') && validateJSONElement(jsonString, cursor, length) && validateEndOfArray(jsonString, cursor, length); }
Short and sweet. Either we end the array here with a ]
character, or we continue it with a ,. There's some
duplication here between validateArray and this function.
However, I believe it would require some re-organization of the control
flow of our program since the order of validations is context-dependent.
Simply: the only difference here is that , is a valid
character as it is at least the second JSON element in the array. I'm
sure there's some way to pass pointers to functions here, though it's
not immediately clear to me how that might work. Thus, we leave this
duplication for now.
validateObject and validateEndOfObject work
similarly:
bool validateEndOfObject(const char *jsonString, int *cursor, int length) { (*cursor)++; skipWhitespace(jsonString, cursor, length); return jsonString[*cursor] == '}' || validateCharAndAdvanceCursor(jsonString, cursor, ',') && skipWhitespace(jsonString, cursor, length) && jsonString[*cursor] == '"' && validateString(jsonString, cursor, length) && (*cursor)++ && skipWhitespace(jsonString, cursor, length) && validateCharAndAdvanceCursor(jsonString, cursor, ':') && validateJSONElement(jsonString, cursor, length) && validateEndOfObject(jsonString, cursor, length); } bool validateObject(const char *jsonString, int *cursor, int length) { (*cursor)++; skipWhitespace(jsonString, cursor, length); return jsonString[*cursor] == '}' || jsonString[*cursor] == '"' && validateString(jsonString, cursor, length) && (*cursor)++ && skipWhitespace(jsonString, cursor, length) && validateCharAndAdvanceCursor(jsonString, cursor, ':') && validateJSONElement(jsonString, cursor, length) && validateEndOfObject(jsonString, cursor, length); }
Just like in our array validation functions, the only difference between
these two is that we allow the possibility of a , and
following whitespace before validating a key/value pair in this object
in validateEndOfObject. In validateObject, we
skip these two checks because we assume it's the first key/value pair in
the object.
The last function we'll look at is validateString. Just a
fair warning: this one deviates from the other validation functions.
bool validateString(const char *jsonString, int *cursor, int length) { (*cursor)++; while ( *cursor < length && jsonString[*cursor] != '"' ) { if (jsonString[*cursor] == '\\') { (*cursor)++; if (jsonString[*cursor] == 'u') { if ((*cursor) + 4 > length) return false; // From https://github.com/zserge/jsmn/blob/25647e692c7906b96ffd2b05ca54c097948e879c/jsmn.h#L241-L251 for (int x = 0; x < 4; (*cursor)++ && x++) { int c = jsonString[(*cursor) + 1]; if (!( (c >= 48 && c <= 57) || /* 0-9 */ (c >= 65 && c <= 70) || /* A-F */ (c >= 97 && c <= 102) /* a-f */ )) return false; } } } (*cursor)++; } return jsonString[*cursor] == '"'; }
We immediately end once we find a " character. We
allow for characters to be escaped with \. There's a
special case accounted for when there is \u present. This
signifies a character represented by 4 hex digits.
In this article, I stepped you through a C implementation of a JSON validator. We talked about potential uses, tradeoffs in its design, and ways we could improve it. I'm going to use this as a reference for writing a JSON parser next. Thanks for reading!
- ryjo