parcel: a JSON parsing library in C

Question

I've created a JSON parsing library in C, and would like some feedback on it (feel free to submit a pull request on GitHub). Any and all suggestions are acceptable, but I would prefer if reviews were focused on making this more efficient.

My header file:

#ifndef _json_H_
#define _json_H_

/**
 * JSON type identifier. Basic types are:
 *  o Object
 *  o Array
 *  o String
 *  o Other primitive: number, boolean (true/false) or null
 */
typedef enum { JSON_PRIMITIVE, JSON_OBJECT, JSON_ARRAY, JSON_STRING } JsonType;

typedef enum
{
    JSON_ERROR_NOMEM = -1, // Not enough tokens were provided
    JSON_ERROR_INVAL = -2, // Invalid character inside JSON string
    JSON_ERROR_PART = -3, // The string is not a full JSON packet, more bytes expected
    JSON_SUCCESS = 0 // Everthing is fine
} JsonError;

/**
 * JSON token description.
 * @param       type    type (object, array, string etc.)
 * @param       start   start position in JSON data string
 * @param       end     end position in JSON data string
 */
typedef struct
{
    JsonType type;
    int start;
    int end;
    int size;
    #ifdef json_PARENT_LINKS
    int parent;
    #endif
} JsonToken;

/**
 * JSON parser. Contains an array of token blocks available. Also stores
 * the string being parsed now and current position in that string
 */
typedef struct
{
    unsigned int pos; /* offset in the JSON string */
    unsigned int toknext; /* next token to allocate */
    int toksuper; /* superior token node, e.g parent object or array */
} JsonParser;

/**
 * Create JSON parser over an array of tokens
 */
void json_initJsonParser(JsonParser *parser);

/**
 * Run JSON parser. It parses a JSON data string into and array of tokens, each describing
 * a single JSON object.
 */
JsonError json_parseJson(JsonParser *parser, const char *js, JsonToken *tokens, unsigned int tokenNum);

#endif /* _json_H_ */

My C source code:

/** 
 * @file json.c
 * @brief JSON Parser
 */

#include <stdlib.h>
#include "json.h"

/**
 * @fn static JsonToken *json_allocJsonToken(JsonParser *parser, JsonToken *tokens, size_t tokenNum)
 * @brief Allocates a fresh unused token from the token pull.
 * @param parser
 * @param tokens
 * @param tokenNum
 */
static JsonToken *json_allocJsonToken(JsonParser *parser, JsonToken *tokens, size_t tokenNum)
{
    if (parser->toknext >= tokenNum) return NULL;
    JsonToken *tok = &tokens[parser->toknext++];
    tok->start = tok->end = -1;
    tok->size = 0;
    #ifdef json_PARENT_LINKS
    tok->parent = -1;
    #endif
    return tok;
}

/**
 * @fn static void json_fillToken(JsonToken *token, JsonType type, int start, int end)
 * @brief Fills token type and boundaries.
 * @param token
 * @param type
 * @param start
 * @param end
 */
static void json_fillToken(JsonToken *token, JsonType type, int start, int end)
{
    token->type = type;
    token->start = start;
    token->end = end;
    token->size = 0;
}

/**
 * @fn static JsonError json_parsePrimitive(JsonParser *parser, const char *js, JsonToken *tokens, size_t num_tokens)
 * @brief Fills next available token with JSON primitive.
 * @param parser
 * @param js
 * @param tokens
 * @param num_tokens
 */
static JsonError json_parsePrimitive(JsonParser *parser, const char *js, JsonToken *tokens, size_t num_tokens)
{
    JsonToken *token;
    int start;

    start = parser->pos;

    for (; js[parser->pos] != '\0'; parser->pos++)
    {
        switch (js[parser->pos]) 
        {
            #ifndef json_STRICT
            /* In strict mode primitive must be followed by "," or "}" or "]" */
            case ':':
            #endif
            case '\t': 
            case '\r': 
            case '\n': 
            case ' ':
            case ',': 
            case ']': 
            case '}':
                goto found;
        }
        if (js[parser->pos] < 32 || js[parser->pos] >= 127)
        {
            parser->pos = start;
            return JSON_ERROR_INVAL;
        }
    }
    #ifdef json_STRICT
    /* In strict mode primitive must be followed by a comma/object/array */
    parser->pos = start;
    return JSON_ERROR_PART;
    #endif

    found:
    token = json_allocJsonToken(parser, tokens, num_tokens);
    if (!token)
    {
        parser->pos = start;
        return JSON_ERROR_NOMEM;
    }
    json_fillToken(token, JSON_PRIMITIVE, start, parser->pos);
    #ifdef json_PARENT_LINKS
    token->parent = parser->toksuper;
    #endif
    parser->pos--;
    return JSON_SUCCESS;
}

/**
 * @fn static JsonError json_parseString(JsonParser *parser, const char *js, JsonToken *tokens, size_t num_tokens)
 * @brief Fills next token with JSON string.
 * @param parser
 * @param js 
 * @param tokens
 * @param num_tokens
 */
static JsonError json_parseString(JsonParser *parser, const char *js, JsonToken *tokens, size_t num_tokens)
{
    JsonToken *token;
    int start = parser->pos;

    parser->pos++;

    /* Skip starting quote */
    for (; js[parser->pos] != '\0'; parser->pos++)
    {
        char c = js[parser->pos];

        /* Quote: end of string */
        if (c == '\"')
        {
            token = json_allocJsonToken(parser, tokens, num_tokens);
            if (!token)
            {
                parser->pos = start;
                return JSON_ERROR_NOMEM;
            }
            json_fillToken(token, JSON_STRING, start+1, parser->pos);
            #ifdef json_PARENT_LINKS
            token->parent = parser->toksuper;
            #endif
            return JSON_SUCCESS;
        }

        /* Backslash: Quoted symbol expected */
        if (c == '\\')
        {
            parser->pos++;
            switch (js[parser->pos])
            {
                /* Allowed escaped symbols */
                case '\"': 
                case '/': 
                case '\\': 
                case 'b':
                case 'f': 
                case 'r': 
                case 'n': 
                case 't':
                    break;
                /* Allows escaped symbol \uXXXX */
                case 'u':
                    /// \todo handle JSON unescaped symbol \\uXXXX
                    break;
                /* Unexpected symbol */
                default:
                    parser->pos = start;
                    return JSON_ERROR_INVAL;
            }
        }
    }
    parser->pos = start;
    return JSON_ERROR_PART;
}

/**
 * @fn JsonError json_parseJson(JsonParser *parser, const char *js, JsonToken *tokens, unsigned int num_tokens) 
 * @brief Parse JSON string and fill tokens.
 * @param parser
 * @param js
 * @param tokens
 * @param num_tokens
 */
JsonError json_parseJson(JsonParser *parser, const char *js, JsonToken *tokens, unsigned int num_tokens) 
{
    JsonError r;
    int i;
    JsonToken *token;

    for (; js[parser->pos] != '\0'; parser->pos++)
    {
        char c;
        JsonType type;

        c = js[parser->pos];
        switch (c)
        {
            case '{':
            case '[':
                token = json_allocJsonToken(parser, tokens, num_tokens);
                if (!token) return JSON_ERROR_NOMEM;
                if (parser->toksuper != -1)
                {
                    tokens[parser->toksuper].size++;
                    #ifdef json_PARENT_LINKS
                    token->parent = parser->toksuper;
                    #endif
                }
                token->type = (c == '{' ? JSON_OBJECT : JSON_ARRAY);
                token->start = parser->pos;
                parser->toksuper = parser->toknext - 1;
                break;
            case '}':
            case ']':
                type = (c == '}' ? JSON_OBJECT : JSON_ARRAY);
                #ifdef json_PARENT_LINKS
                if (parser->toknext < 1) return JSON_ERROR_INVAL;
                token = &tokens[parser->toknext - 1];
                for (;;)
                {
                    if (token->start != -1 && token->end == -1)
                    {
                        if (token->type != type) return JSON_ERROR_INVAL;
                        token->end = parser->pos + 1;
                        parser->toksuper = token->parent;
                        break;
                    }
                    if (token->parent == -1) break;
                    token = &tokens[token->parent];
                }
                #else
                for (i = parser->toknext - 1; i >= 0; i--)
                {
                    token = &tokens[i];
                    if (token->start != -1 && token->end == -1)
                    {
                        if (token->type != type) return JSON_ERROR_INVAL;
                        parser->toksuper = -1;
                        token->end = parser->pos + 1;
                        break;
                    }
                }
                /* Error if unmatched closing bracket */
                if (i == -1) return JSON_ERROR_INVAL;
                for (; i >= 0; i--)
                {
                    token = &tokens[i];
                    if (token->start != -1 && token->end == -1)
                    {
                        parser->toksuper = i;
                        break;
                    }
                }
                #endif
                break;
            case '\"':
                r = json_parseString(parser, js, tokens, num_tokens);
                if (r < 0) return r;
                if (parser->toksuper != -1) tokens[parser->toksuper].size++;
                break;
            case '\t':
            case '\r':
            case '\n':
            case ':':
            case ',':
            case ' ': 
                break;
            #ifdef json_STRICT
            /* In strict mode primitives are: numbers and booleans */
            case '-':
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
            case 't':
            case 'f':
            case 'n':
            #else
            /* In non-strict mode every unquoted value is a primitive */
            default:
            #endif
                r = json_parsePrimitive(parser, js, tokens, num_tokens);
                if (r < 0) return r;
                if (parser->toksuper != -1) tokens[parser->toksuper].size++;
                break;

            #ifdef json_STRICT
            /* Unexpected char in strict mode */
            default:
                return JSON_ERROR_INVAL;
            #endif

        }
    }

    for (i = parser->toknext - 1; i >= 0; i--)
    {
        /* Unmatched opened object or array */
        if (tokens[i].start != -1 && tokens[i].end == -1) return JSON_ERROR_PART;
    }

    return JSON_SUCCESS;
}

/**
 * @fn void json_initJsonParser(JsonParser *parser)
 * @brief Creates a new parser based over a given buffer with an array of tokens available.
 * @param parser
 */
void json_initJsonParser(JsonParser *parser)
{
    parser->pos = 0;
    parser->toknext = 0;
    parser->toksuper = -1;
}

Answer 1

What you did well

1. As far as I can tell, the code produces correct output when given correct input.
2. The functions feel like a coherent library, with consistent function names and logical order of parameters.
3. You use a caller-owns-everything memory management policy, which works well for C.

What you could improve on

1. The name json_initJsonParser() is a bit redundant. json_initParser() should suffice.
2. I don't think that #ifdef json_PARENT_LINKS is a good idea. A user could easily compile the library without support for parent links, yet compile the application with json_PARENT_LINKS defined, leading to nasty bugs. Why not always enable support parent links? It would be pretty difficult to make sense of the parser output without it.
3. I think that #ifdef json_STRICT would be better as a runtime option rather than a compile-time option. If the user wants to have both modes available, there's no reasonable way to do so.
4. JSON primitives may be numbers, true, false, or null. You accept illegal primitives such as truthy.
5. json_allocJsonToken() doesn't "allocate" memory in the sense that I expect. Also, two of the three calls to json_allocJsonToken() are followed by json_fillToken(), so you might as well combine the two functions. Filling in dummy values first is senseless.
6. In the JsonParser structure, toknext and toksuper should be the same data type. It's weird that one is unsigned and the other is signed. I recommend just using int for both, or possibly ssize_t.

7. It is not obvious that the way to extract the results is to use a loop like

   for (int i = 0; i < parser.toknext; i++) {
       //              ^^^^^^^^^^^^^^
   }
   

   Please feel free to add some generous comments with usage examples in the header file.

Answer 2

I think the code looks pretty tidy. Not sure if you can get a huge speed up - you are effectively tokenizing a string by storing the meta data of the tokens (start/end positions and type). This alleviates the pain of having to copy the data and dealing with the associated memory allocation issue.

A few remarks:

1. You could consider changing the token to store a const char * start and a size_t length instead where start points to the first char of the token in the input. This way you can work on the data of the token without having to also pass around a reference to the original string.

2. You have documentation for your methods but you don't really document the parameters - what they are for, what their invariants are etc.

3. For general use the interface is probably too inconvenient - you pretty much need to know how many tokens to expect before parsing (or do the old parse - fail - double memory - try again dance) which could be hard to keep track of. As a user I might know what kind of object I want to parse but I'd be hard pressed to know exactly up front how many json tokens I'd need.

4. goto is generally frowned upon. While you use it in a fairly straight forward way that's easy to follow I'm almost certain that rewriting the code with a gotValidToken token flag to terminate the loop instead could potentially increase readability. The goto forces you to jump around while reading the code.