2
\$\begingroup\$

Back in the day in addition to DOM and SAX parsers for XML another parser type was relatively popular -- pull parsers. Recently I was looking for a JSON parser and figured that most JSON C parsers are more akin to DOM parsers with their own toy object models. I personally see no need adopting such models in my projects. So I decided to write my own JSON pull parser in C.

Basically the pull parser returns raw tokens, it is the responsibility of the user application to convert the tokens to a suitable internal representation.

So far the parser has very simple interface. It does not even decode string escape sequences and does not convert number values to binary form. It just returns the pointers to value boundaries in the source buffer.

The parser is written with streaming scenario in mind. The input might be fed to the parser piece by piece. In case a value is split between two input pieces the parser concatenates the split parts within internal buffer.

I have plans to add functions that convert values copying from the raw JSON buffer to a user-provided target variables. But at the moment I focus on other things.

The code I got seems a little bit overcomplicated. Perhaps it checks for JSON format validity too pedantically. Perhaps it might be simplified. On other hand I'm interested if I failed to address any JSON peculiarities there. Also I'm interested in feature requests for the parser.

The source code is below, it is also available on GitHub:

json.h

/*
 * base/json.h - JSON pull parser.
 *
 * Copyright (C) 2015  Aleksey Demakov
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef BASE_JSON_H
#define BASE_JSON_H

#include "common.h"
#include "base/memory/arena.h"

typedef enum mm_json_token {

    /* Internal token of initial reader state. */
    MM_JSON_INITIAL = 0,

    /* Input data is incomplete. */
    MM_JSON_PARTIAL,

    /* Input data is invalid. */
    MM_JSON_ERROR,

    MM_JSON_START_DOCUMENT,
    MM_JSON_END_DOCUMENT,

    MM_JSON_START_OBJECT,
    MM_JSON_END_OBJECT,

    MM_JSON_START_ARRAY,
    MM_JSON_END_ARRAY,

    MM_JSON_NAME,

    MM_JSON_STRING,
    MM_JSON_NUMBER,
    MM_JSON_FALSE,
    MM_JSON_TRUE,
    MM_JSON_NULL,

} mm_json_token_t;

typedef enum mm_json_state {

    MM_JSON_STATE_VALUE,

    MM_JSON_STATE_SPACE,

    MM_JSON_STATE_ARRAY,
    MM_JSON_STATE_ARRAY_VALUE_SEP,

    MM_JSON_STATE_OBJECT,
    MM_JSON_STATE_OBJECT_NAME,
    MM_JSON_STATE_OBJECT_NAME_SEP,
    MM_JSON_STATE_OBJECT_VALUE_SEP,

} mm_json_state_t;

struct mm_json_reader
{
    mm_json_token_t token;
    mm_json_state_t state;

    /* A string or numeric value. */
    const char *value;
    const char *value_end;

    /* The current read position. */
    const char *ptr;
    const char *end;

    /* Input data buffer. */
    const char *input;
    const char *input_end;

    /* Internal data buffer. */
    char *buffer;
    char *buffer_end;
    size_t buffer_size;

    union
    {
        struct
        {
            bool fraction;
            bool exponent;
        } number;

        struct
        {
            bool escaped;
            bool highbit;
        } string;
    } extra;

    size_t stack_top;
    size_t stack_max;
    union
    {
        uintptr_t small_stack;
        uintptr_t *large_stack;
    };

    mm_arena_t arena;
};

void __attribute__((nonnull(1)))
mm_json_reader_prepare(struct mm_json_reader *reader, mm_arena_t arena);

void __attribute__((nonnull(1)))
mm_json_reader_cleanup(struct mm_json_reader *reader);

void __attribute__((nonnull(1, 2)))
mm_json_reader_feed(struct mm_json_reader *reader, const void *input, size_t input_size);

mm_json_token_t __attribute__((nonnull(1)))
mm_json_reader_next(struct mm_json_reader *reader);

#endif /* BASE_JSON_H */

json.c

/*
 * base/json.c - JSON pull parser.
 *
 * Copyright (C) 2015  Aleksey Demakov
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "base/json.h"

#include "base/log/debug.h"
#include "base/memory/memory.h"

#define MM_JSON_STACK_UNIT  (sizeof(uintptr_t) * 8)

/**********************************************************************
 * JSON reader initialization and termination.
 **********************************************************************/

void __attribute__((nonnull(1)))
mm_json_reader_prepare(struct mm_json_reader *reader, mm_arena_t arena)
{
    memset(reader, 0, sizeof(*reader));
    reader->stack_max = MM_JSON_STACK_UNIT;
    reader->arena = arena;
}

void __attribute__((nonnull(1)))
mm_json_reader_cleanup(struct mm_json_reader *reader)
{
    if (reader->buffer != NULL)
        mm_arena_free(reader->arena, reader->buffer);
    if (reader->stack_max > MM_JSON_STACK_UNIT)
        mm_arena_free(reader->arena, reader->large_stack);
}

/**********************************************************************
 * JSON reader stack maintenance.
 **********************************************************************/

static void
mm_json_reader_stack_push(struct mm_json_reader *reader, bool is_object)
{
    if (reader->stack_top == reader->stack_max) {
        reader->stack_max *= 2;
        size_t nbytes = reader->stack_max / 8;
        if (reader->stack_top > MM_JSON_STACK_UNIT) {
            reader->large_stack = mm_arena_realloc(reader->arena,
                                                   reader->large_stack,
                                                   nbytes);
        } else {
            uintptr_t *large_stack = mm_arena_alloc(reader->arena, nbytes);
            large_stack[0] = reader->small_stack;
            reader->large_stack = large_stack;
        }
    }

    size_t bit = reader->stack_top++;
    if (reader->stack_max > MM_JSON_STACK_UNIT) {
        uintptr_t unit = bit / MM_JSON_STACK_UNIT;
        uintptr_t mask = (uintptr_t) 1 << (bit % MM_JSON_STACK_UNIT);
        if (is_object)
            reader->large_stack[unit] |= mask;
        else
            reader->large_stack[unit] &= ~mask;
    } else {
        uintptr_t mask = (uintptr_t) 1 << bit;
        if (is_object)
            reader->small_stack |= mask;
        else
            reader->small_stack &= ~mask;
    }
}

static bool
mm_json_reader_stack_get(struct mm_json_reader *reader)
{
    ASSERT(reader->stack_top > 0);
    size_t bit = reader->stack_top - 1;
    if (reader->stack_max > MM_JSON_STACK_UNIT) {
        uintptr_t unit = bit / MM_JSON_STACK_UNIT;
        uintptr_t mask = (uintptr_t) 1 << (bit % MM_JSON_STACK_UNIT);
        return (reader->large_stack[unit] & mask) != 0;
    } else {
        uintptr_t mask = (uintptr_t) 1 << bit;
        return (reader->small_stack & mask) != 0;
    }
}

static void
mm_json_reader_stack_pop(struct mm_json_reader *reader)
{
    ASSERT(reader->stack_top > 0);
    reader->stack_top--;
}

/**********************************************************************
 * JSON reader input buffer maintenance.
 **********************************************************************/

/*
 * Save some data from the input buffer in the internal buffer.
 * If the internal buffer contains any non-consumed data then
 * the input buffer data is appended to it.
 */
static void __attribute__((nonnull(1)))
mm_json_reader_save_input(struct mm_json_reader *reader, const char *input_limit)
{
    ASSERT(input_limit >= reader->input && input_limit <= reader->input_end);

    const char *input;
    size_t start_size;
    if (reader->end == reader->buffer_end) {
        ASSERT(reader->ptr >= reader->buffer && reader->ptr <= reader->buffer_end);
        input = reader->input;
        start_size = reader->end - reader->ptr;
    } else {
        ASSERT(reader->ptr >= reader->input && reader->ptr <= input_limit);
        input = reader->ptr;
        start_size = 0;
    }

    size_t input_size = input_limit - input;
    size_t total_size = start_size + input_size;
    if (total_size > reader->buffer_size) {
        char *buffer = mm_arena_alloc(reader->arena, total_size);
        if (start_size)
            memcpy(buffer, reader->ptr, start_size);
        if (reader->buffer)
            mm_arena_free(reader->arena, reader->buffer);
        reader->buffer = buffer;
    } else if (start_size && reader->ptr != reader->buffer) {
        memmove(reader->buffer, reader->ptr, start_size);
    }

    if (input_size)
        memcpy(reader->buffer + start_size, input, input_size);
    reader->buffer_end = reader->buffer + total_size;

    reader->ptr = reader->buffer;
    reader->end = reader->buffer_end;
}

/*
 * Make sure that the requested number of bytes are immediately available
 * in the current buffer. Consolidate the data in the internal buffer if
 * necessary.
 */
static inline const char *
mm_json_reader_check_size(struct mm_json_reader *reader, size_t n_min)
{
    size_t n = reader->end - reader->ptr;
    if (unlikely(n < n_min)) {
        if (reader->end == reader->input_end)
            return NULL;

        size_t m = reader->input_end - reader->input;
        if ((n + m) < n_min)
            return NULL;

        const char *value_end = reader->input + n_min - n;
        mm_json_reader_save_input(reader, value_end);
        reader->input = value_end;
    }

    return reader->ptr;
}

void __attribute__((nonnull(1, 2)))
mm_json_reader_feed(struct mm_json_reader *reader, const void *input, size_t input_size)
{
    const char *input_end = (const char *) input + input_size;

    if (reader->ptr == reader->input_end) {
        reader->ptr = input;
        reader->end = input_end;
    } else {
        mm_json_reader_save_input(reader, reader->input_end);
    }

    reader->input = input;
    reader->input_end = input_end;
}

/**********************************************************************
 * JSON reader literal scan routines.
 **********************************************************************/

#define Cx3(a, b, c)        ((a) | ((b) << 8) | ((c) << 16))
#define Cx4(a, b, c, d)     ((a) | ((b) << 8) | ((c) << 16) | ((d) << 24))

static mm_json_token_t
mm_json_reader_scan_false(struct mm_json_reader *reader)
{
    const char *cp = mm_json_reader_check_size(reader, 5);
    if (unlikely(cp == NULL))
        return MM_JSON_PARTIAL;

    ASSERT(cp[0] == 'f');
    if (unlikely(Cx4(cp[1], cp[2], cp[3], cp[4]) != Cx4('a', 'l', 's', 'e')))
        return MM_JSON_ERROR;

    reader->ptr += 5;
    return MM_JSON_FALSE;
}

static mm_json_token_t
mm_json_reader_scan_true(struct mm_json_reader *reader)
{
    const char *cp = mm_json_reader_check_size(reader, 4);
    if (unlikely(cp == NULL))
        return MM_JSON_PARTIAL;

    ASSERT(cp[0] == 't');
    if (unlikely(Cx3(cp[1], cp[2], cp[3]) != Cx3('r', 'u', 'e')))
        return MM_JSON_ERROR;

    reader->ptr += 4;
    return MM_JSON_TRUE;
}

static mm_json_token_t
mm_json_reader_scan_null(struct mm_json_reader *reader)
{
    const char *cp = mm_json_reader_check_size(reader, 4);
    if (unlikely(cp == NULL))
        return MM_JSON_PARTIAL;

    ASSERT(cp[0] == 'n');
    if (unlikely(Cx3(cp[1], cp[2], cp[3]) != Cx3('u', 'l', 'l')))
        return MM_JSON_ERROR;

    reader->ptr += 4;
    return MM_JSON_NULL;
}

/**********************************************************************
 * JSON reader string scan routine.
 **********************************************************************/

typedef enum
{
    MM_JSON_SSTATE_NORMAL,
    MM_JSON_SSTATE_ESCAPE,
    MM_JSON_SSTATE_HEXNUM,

} mm_json_string_state_t;

typedef enum
{
    MM_JSON_SCTYPE_ERROR = 0,

    MM_JSON_SCTYPE_REGULAR,
    MM_JSON_SCTYPE_HIGHBIT,

    MM_JSON_SCTYPE_ESCAPE,
    MM_JSON_SCTYPE_ESC2CH,
    MM_JSON_SCTYPE_ESC6CH,
    MM_JSON_SCTYPE_HEXNUM,

    MM_JSON_SCTYPE_QUOTE,

} mm_json_string_ctype_t;

static uint8_t mm_json_string_table[][256] = {
#define C MM_JSON_SCTYPE_ERROR
#define R MM_JSON_SCTYPE_REGULAR
#define H MM_JSON_SCTYPE_HIGHBIT
#define E MM_JSON_SCTYPE_ESCAPE
#define Q MM_JSON_SCTYPE_QUOTE

    [MM_JSON_SSTATE_NORMAL] = {
        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
        C, C, C, C, C, C, C, C, C, C, C, C, C, C, C, C,
        R, R, Q, R, R, R, R, R, R, R, R, R, R, R, R, R,
        R, R, R, R, R, R, R, R, R, R, R, R, R, R, R, R,
        R, R, R, R, R, R, R, R, R, R, R, R, R, R, R, R,
        R, R, R, R, R, R, R, R, R, R, R, R, E, R, R, R,
        R, R, R, R, R, R, R, R, R, R, R, R, R, R, R, R,
        R, R, R, R, R, R, R, R, R, R, R, R, R, R, R, R,

        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
        H, H, H, H, H, H, H, H, H, H, H, H, H, H, H, H,
    },

#undef C
#undef R
#undef H
#undef E
#undef Q

    [MM_JSON_SSTATE_ESCAPE] = {
        ['b'] = MM_JSON_SCTYPE_ESC2CH, ['f'] = MM_JSON_SCTYPE_ESC2CH,
        ['n'] = MM_JSON_SCTYPE_ESC2CH, ['r'] = MM_JSON_SCTYPE_ESC2CH,
        ['t'] = MM_JSON_SCTYPE_ESC2CH, ['/'] = MM_JSON_SCTYPE_ESC2CH,
        ['"'] = MM_JSON_SCTYPE_ESC2CH, ['\\'] = MM_JSON_SCTYPE_ESC2CH,
        ['u'] = MM_JSON_SCTYPE_ESC6CH,
    },

    [MM_JSON_SSTATE_HEXNUM] = {
        ['0'] = MM_JSON_SCTYPE_HEXNUM, ['1'] = MM_JSON_SCTYPE_HEXNUM,
        ['2'] = MM_JSON_SCTYPE_HEXNUM, ['3'] = MM_JSON_SCTYPE_HEXNUM,
        ['4'] = MM_JSON_SCTYPE_HEXNUM, ['5'] = MM_JSON_SCTYPE_HEXNUM,
        ['6'] = MM_JSON_SCTYPE_HEXNUM, ['7'] = MM_JSON_SCTYPE_HEXNUM,
        ['8'] = MM_JSON_SCTYPE_HEXNUM, ['9'] = MM_JSON_SCTYPE_HEXNUM,
        ['a'] = MM_JSON_SCTYPE_HEXNUM, ['b'] = MM_JSON_SCTYPE_HEXNUM,
        ['c'] = MM_JSON_SCTYPE_HEXNUM, ['d'] = MM_JSON_SCTYPE_HEXNUM,
        ['e'] = MM_JSON_SCTYPE_HEXNUM, ['f'] = MM_JSON_SCTYPE_HEXNUM,
        ['A'] = MM_JSON_SCTYPE_HEXNUM, ['B'] = MM_JSON_SCTYPE_HEXNUM,
        ['C'] = MM_JSON_SCTYPE_HEXNUM, ['D'] = MM_JSON_SCTYPE_HEXNUM,
        ['E'] = MM_JSON_SCTYPE_HEXNUM, ['F'] = MM_JSON_SCTYPE_HEXNUM,
    },
};

static mm_json_token_t
mm_json_reader_scan_string(struct mm_json_reader *reader, mm_json_token_t token)
{
    const char *cp = reader->ptr;
    const char *ep = reader->end;
    ASSERT(cp[0] == '"');

    reader->extra.string.escaped = false;
    reader->extra.string.highbit = false;

    bool split = false;
    unsigned count = 0;
    mm_json_string_state_t state = MM_JSON_SSTATE_NORMAL;
    for (;;) {
        if (++cp == ep) {
            if (cp == reader->input_end)
                return MM_JSON_PARTIAL;

            cp = reader->input;
            ep = reader->input_end;
            if (unlikely(cp == ep))
                return MM_JSON_PARTIAL;

            split = true;
        }

        uint8_t c = *cp;
        switch (mm_json_string_table[state][c]) {
            case MM_JSON_SCTYPE_ERROR:
                return MM_JSON_ERROR;

            case MM_JSON_SCTYPE_REGULAR:
                break;

            case MM_JSON_SCTYPE_HIGHBIT:
                reader->extra.string.highbit = true;
                break;

            case MM_JSON_SCTYPE_ESCAPE:
                reader->extra.string.escaped = true;
                state = MM_JSON_SSTATE_ESCAPE;
                break;

            case MM_JSON_SCTYPE_ESC2CH:
                state = MM_JSON_SSTATE_NORMAL;
                break;

            case MM_JSON_SCTYPE_ESC6CH:
                state = MM_JSON_SSTATE_HEXNUM;
                break;

            case MM_JSON_SCTYPE_HEXNUM:
                if (count++ == 3) {
                    count = 0;
                    state = MM_JSON_SSTATE_NORMAL;
                }
                break;

            case MM_JSON_SCTYPE_QUOTE:
                if (unlikely(split)) {
                    mm_json_reader_save_input(reader, cp);
                    reader->input = cp;

                    reader->value = reader->buffer;
                    reader->value_end = reader->buffer_end;
                } else {
                    reader->value = reader->ptr;
                    reader->value_end = cp;
                }
                reader->ptr = cp + 1;
                return token;
        }
    }
}

/**********************************************************************
 * JSON reader number scan routine.
 **********************************************************************/

typedef enum
{
    MM_JSON_NSTATE_START,
    MM_JSON_NSTATE_FIRST,
    MM_JSON_NSTATE_NEXT,
    MM_JSON_NSTATE_ONLY,

    MM_JSON_NSTATE_FFIRST,
    MM_JSON_NSTATE_FNEXT,

    MM_JSON_NSTATE_ESTART,
    MM_JSON_NSTATE_EFIRST,
    MM_JSON_NSTATE_ENEXT,

} mm_json_number_state_t;

typedef enum
{
    MM_JSON_NCTYPE_ERROR = 0,

    MM_JSON_NCTYPE_MINUS,
    MM_JSON_NCTYPE_ZERO,
    MM_JSON_NCTYPE_FIRST,
    MM_JSON_NCTYPE_NEXT,

    MM_JSON_NCTYPE_POINT,
    MM_JSON_NCTYPE_FFIRST,

    MM_JSON_NCTYPE_E,
    MM_JSON_NCTYPE_ESIGN,
    MM_JSON_NCTYPE_EFIRST,

    MM_JSON_NCTYPE_DELIM,

} mm_json_number_ctype_t;

static uint8_t mm_json_number_table[][256] = {

    [MM_JSON_NSTATE_START] = {
        ['-'] = MM_JSON_NCTYPE_MINUS,

        ['0'] = MM_JSON_NCTYPE_ZERO, ['1'] = MM_JSON_NCTYPE_FIRST,
        ['2'] = MM_JSON_NCTYPE_FIRST, ['3'] = MM_JSON_NCTYPE_FIRST,
        ['4'] = MM_JSON_NCTYPE_FIRST, ['5'] = MM_JSON_NCTYPE_FIRST,
        ['6'] = MM_JSON_NCTYPE_FIRST, ['7'] = MM_JSON_NCTYPE_FIRST,
        ['8'] = MM_JSON_NCTYPE_FIRST, ['9'] = MM_JSON_NCTYPE_FIRST,
    },

    [MM_JSON_NSTATE_FIRST] = {
        ['0'] = MM_JSON_NCTYPE_ZERO, ['1'] = MM_JSON_NCTYPE_FIRST,
        ['2'] = MM_JSON_NCTYPE_FIRST, ['3'] = MM_JSON_NCTYPE_FIRST,
        ['4'] = MM_JSON_NCTYPE_FIRST, ['5'] = MM_JSON_NCTYPE_FIRST,
        ['6'] = MM_JSON_NCTYPE_FIRST, ['7'] = MM_JSON_NCTYPE_FIRST,
        ['8'] = MM_JSON_NCTYPE_FIRST, ['9'] = MM_JSON_NCTYPE_FIRST,
    },

    [MM_JSON_NSTATE_NEXT] = {
        ['0'] = MM_JSON_NCTYPE_NEXT, ['1'] = MM_JSON_NCTYPE_NEXT,
        ['2'] = MM_JSON_NCTYPE_NEXT, ['3'] = MM_JSON_NCTYPE_NEXT,
        ['4'] = MM_JSON_NCTYPE_NEXT, ['5'] = MM_JSON_NCTYPE_NEXT,
        ['6'] = MM_JSON_NCTYPE_NEXT, ['7'] = MM_JSON_NCTYPE_NEXT,
        ['8'] = MM_JSON_NCTYPE_NEXT, ['9'] = MM_JSON_NCTYPE_NEXT,

        ['.'] = MM_JSON_NCTYPE_POINT,
        ['e'] = MM_JSON_NCTYPE_E, ['E'] = MM_JSON_NCTYPE_E,

        [' '] = MM_JSON_NCTYPE_DELIM, ['\t'] = MM_JSON_NCTYPE_DELIM,
        ['\r'] = MM_JSON_NCTYPE_DELIM, ['\n'] = MM_JSON_NCTYPE_DELIM,
        [']'] = MM_JSON_NCTYPE_DELIM, ['}'] = MM_JSON_NCTYPE_DELIM,
        [','] = MM_JSON_NCTYPE_DELIM,
    },

    [MM_JSON_NSTATE_ONLY] = {
        ['.'] = MM_JSON_NCTYPE_POINT,
        ['e'] = MM_JSON_NCTYPE_E, ['E'] = MM_JSON_NCTYPE_E,

        [' '] = MM_JSON_NCTYPE_DELIM, ['\t'] = MM_JSON_NCTYPE_DELIM,
        ['\r'] = MM_JSON_NCTYPE_DELIM, ['\n'] = MM_JSON_NCTYPE_DELIM,
        [']'] = MM_JSON_NCTYPE_DELIM, ['}'] = MM_JSON_NCTYPE_DELIM,
        [','] = MM_JSON_NCTYPE_DELIM,
    },

    [MM_JSON_NSTATE_FFIRST] = {
        ['0'] = MM_JSON_NCTYPE_FFIRST, ['1'] = MM_JSON_NCTYPE_FFIRST,
        ['2'] = MM_JSON_NCTYPE_FFIRST, ['3'] = MM_JSON_NCTYPE_FFIRST,
        ['4'] = MM_JSON_NCTYPE_FFIRST, ['5'] = MM_JSON_NCTYPE_FFIRST,
        ['6'] = MM_JSON_NCTYPE_FFIRST, ['7'] = MM_JSON_NCTYPE_FFIRST,
        ['8'] = MM_JSON_NCTYPE_FFIRST, ['9'] = MM_JSON_NCTYPE_FFIRST,
    },

    [MM_JSON_NSTATE_FNEXT] = {
        ['0'] = MM_JSON_NCTYPE_NEXT, ['1'] = MM_JSON_NCTYPE_NEXT,
        ['2'] = MM_JSON_NCTYPE_NEXT, ['3'] = MM_JSON_NCTYPE_NEXT,
        ['4'] = MM_JSON_NCTYPE_NEXT, ['5'] = MM_JSON_NCTYPE_NEXT,
        ['6'] = MM_JSON_NCTYPE_NEXT, ['7'] = MM_JSON_NCTYPE_NEXT,
        ['8'] = MM_JSON_NCTYPE_NEXT, ['9'] = MM_JSON_NCTYPE_NEXT,

        ['e'] = MM_JSON_NCTYPE_E, ['E'] = MM_JSON_NCTYPE_E,

        [' '] = MM_JSON_NCTYPE_DELIM, ['\t'] = MM_JSON_NCTYPE_DELIM,
        ['\r'] = MM_JSON_NCTYPE_DELIM, ['\n'] = MM_JSON_NCTYPE_DELIM,
        [']'] = MM_JSON_NCTYPE_DELIM, ['}'] = MM_JSON_NCTYPE_DELIM,
        [','] = MM_JSON_NCTYPE_DELIM,
    },

    [MM_JSON_NSTATE_ESTART] = {
        ['-'] = MM_JSON_NCTYPE_ESIGN, ['+'] = MM_JSON_NCTYPE_ESIGN,

        ['0'] = MM_JSON_NCTYPE_EFIRST, ['1'] = MM_JSON_NCTYPE_EFIRST,
        ['2'] = MM_JSON_NCTYPE_EFIRST, ['3'] = MM_JSON_NCTYPE_EFIRST,
        ['4'] = MM_JSON_NCTYPE_EFIRST, ['5'] = MM_JSON_NCTYPE_EFIRST,
        ['6'] = MM_JSON_NCTYPE_EFIRST, ['7'] = MM_JSON_NCTYPE_EFIRST,
        ['8'] = MM_JSON_NCTYPE_EFIRST, ['9'] = MM_JSON_NCTYPE_EFIRST,
    },

    [MM_JSON_NSTATE_EFIRST] = {
        ['0'] = MM_JSON_NCTYPE_EFIRST, ['1'] = MM_JSON_NCTYPE_EFIRST,
        ['2'] = MM_JSON_NCTYPE_EFIRST, ['3'] = MM_JSON_NCTYPE_EFIRST,
        ['4'] = MM_JSON_NCTYPE_EFIRST, ['5'] = MM_JSON_NCTYPE_EFIRST,
        ['6'] = MM_JSON_NCTYPE_EFIRST, ['7'] = MM_JSON_NCTYPE_EFIRST,
        ['8'] = MM_JSON_NCTYPE_EFIRST, ['9'] = MM_JSON_NCTYPE_EFIRST,
    },

    [MM_JSON_NSTATE_ENEXT] = {
        ['0'] = MM_JSON_NCTYPE_NEXT, ['1'] = MM_JSON_NCTYPE_NEXT,
        ['2'] = MM_JSON_NCTYPE_NEXT, ['3'] = MM_JSON_NCTYPE_NEXT,
        ['4'] = MM_JSON_NCTYPE_NEXT, ['5'] = MM_JSON_NCTYPE_NEXT,
        ['6'] = MM_JSON_NCTYPE_NEXT, ['7'] = MM_JSON_NCTYPE_NEXT,
        ['8'] = MM_JSON_NCTYPE_NEXT, ['9'] = MM_JSON_NCTYPE_NEXT,

        [' '] = MM_JSON_NCTYPE_DELIM, ['\t'] = MM_JSON_NCTYPE_DELIM,
        ['\r'] = MM_JSON_NCTYPE_DELIM, ['\n'] = MM_JSON_NCTYPE_DELIM,
        [']'] = MM_JSON_NCTYPE_DELIM, ['}'] = MM_JSON_NCTYPE_DELIM,
        [','] = MM_JSON_NCTYPE_DELIM,
    },
};

static mm_json_token_t
mm_json_reader_scan_number(struct mm_json_reader *reader)
{
    const char *cp = reader->ptr;
    const char *ep = reader->end;
    ASSERT(cp[0] == '-' || cp[0] >= '0' && cp[0] <= '9');

    reader->extra.number.fraction = false;
    reader->extra.number.exponent = false;

    bool split = false;
    mm_json_number_state_t state = MM_JSON_NSTATE_START;
    for (;;) {
        uint8_t c = *cp;
        switch (mm_json_number_table[state][c]) {
            case MM_JSON_NCTYPE_ERROR:
                return MM_JSON_ERROR;

            case MM_JSON_NCTYPE_MINUS:
                state = MM_JSON_NSTATE_FIRST;
                break;

            case MM_JSON_NCTYPE_ZERO:
                state = MM_JSON_NSTATE_ONLY;
                break;

            case MM_JSON_NCTYPE_FIRST:
                state = MM_JSON_NSTATE_NEXT;
                break;

            case MM_JSON_NCTYPE_POINT:
                state = MM_JSON_NSTATE_FFIRST;
                break;

            case MM_JSON_NCTYPE_FFIRST:
                state = MM_JSON_NSTATE_FNEXT;
                break;

            case MM_JSON_NCTYPE_E:
                state = MM_JSON_NSTATE_ESTART;
                break;

            case MM_JSON_NCTYPE_ESIGN:
                state = MM_JSON_NSTATE_EFIRST;
                break;

            case MM_JSON_NCTYPE_EFIRST:
                state = MM_JSON_NSTATE_ENEXT;
                break;

            case MM_JSON_NCTYPE_NEXT:
                break;

            case MM_JSON_NCTYPE_DELIM:
                if (unlikely(split)) {
                    mm_json_reader_save_input(reader, cp);
                    reader->input = cp;
                    reader->value = reader->buffer;
                    reader->value_end = reader->buffer_end;
                } else {
                    reader->value = reader->ptr;
                    reader->value_end = cp;
                }
                reader->ptr = cp;
                return MM_JSON_NUMBER;
        }

        if (++cp == ep) {
            if (cp == reader->input_end)
                return MM_JSON_PARTIAL;

            cp = reader->input;
            ep = reader->input_end;
            if (unlikely(cp == ep))
                return MM_JSON_PARTIAL;

            split = true;
        }
    }
}

/**********************************************************************
 * JSON reader main parser.
 **********************************************************************/

typedef enum
{
    MM_JSON_CTYPE_ERROR = 0,

    MM_JSON_CTYPE_SPACE,

    MM_JSON_CTYPE_OBJECT,
    MM_JSON_CTYPE_OBJECT_VALUE,
    MM_JSON_CTYPE_OBJECT_NEXT,
    MM_JSON_CTYPE_OBJECT_END,

    MM_JSON_CTYPE_ARRAY,
    MM_JSON_CTYPE_ARRAY_NEXT,
    MM_JSON_CTYPE_ARRAY_END,

    MM_JSON_CTYPE_FALSE,
    MM_JSON_CTYPE_TRUE,
    MM_JSON_CTYPE_NULL,

    MM_JSON_CTYPE_NAME,
    MM_JSON_CTYPE_STRING,
    MM_JSON_CTYPE_NUMBER,

} mm_json_ctype_t;

static uint8_t mm_json_text_table[][256] = {

    [MM_JSON_STATE_SPACE] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,
    },

    [MM_JSON_STATE_VALUE] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        ['{'] = MM_JSON_CTYPE_OBJECT,
        ['['] = MM_JSON_CTYPE_ARRAY,

        ['f'] = MM_JSON_CTYPE_FALSE, ['t'] = MM_JSON_CTYPE_TRUE,
        ['n'] = MM_JSON_CTYPE_NULL,

        ['"'] = MM_JSON_CTYPE_STRING,

        ['-'] = MM_JSON_CTYPE_NUMBER,
        ['0'] = MM_JSON_CTYPE_NUMBER, ['1'] = MM_JSON_CTYPE_NUMBER,
        ['2'] = MM_JSON_CTYPE_NUMBER, ['3'] = MM_JSON_CTYPE_NUMBER,
        ['4'] = MM_JSON_CTYPE_NUMBER, ['5'] = MM_JSON_CTYPE_NUMBER,
        ['6'] = MM_JSON_CTYPE_NUMBER, ['7'] = MM_JSON_CTYPE_NUMBER,
        ['8'] = MM_JSON_CTYPE_NUMBER, ['9'] = MM_JSON_CTYPE_NUMBER,
    },

    [MM_JSON_STATE_OBJECT] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        ['"'] = MM_JSON_CTYPE_NAME,

        ['}'] = MM_JSON_CTYPE_OBJECT_END,
    },
    [MM_JSON_STATE_OBJECT_NAME] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        ['"'] = MM_JSON_CTYPE_NAME,
    },
    [MM_JSON_STATE_OBJECT_NAME_SEP] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        [':'] = MM_JSON_CTYPE_OBJECT_VALUE,
    },
    [MM_JSON_STATE_OBJECT_VALUE_SEP] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        [','] = MM_JSON_CTYPE_OBJECT_NEXT,

        ['}'] = MM_JSON_CTYPE_OBJECT_END,
    },

    [MM_JSON_STATE_ARRAY] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        ['{'] = MM_JSON_CTYPE_OBJECT,
        ['['] = MM_JSON_CTYPE_ARRAY,

        ['f'] = MM_JSON_CTYPE_FALSE,
        ['t'] = MM_JSON_CTYPE_TRUE,
        ['n'] = MM_JSON_CTYPE_NULL,

        ['"'] = MM_JSON_CTYPE_STRING,

        ['-'] = MM_JSON_CTYPE_NUMBER,
        ['0'] = MM_JSON_CTYPE_NUMBER, ['1'] = MM_JSON_CTYPE_NUMBER,
        ['2'] = MM_JSON_CTYPE_NUMBER, ['3'] = MM_JSON_CTYPE_NUMBER,
        ['4'] = MM_JSON_CTYPE_NUMBER, ['5'] = MM_JSON_CTYPE_NUMBER,
        ['6'] = MM_JSON_CTYPE_NUMBER, ['7'] = MM_JSON_CTYPE_NUMBER,
        ['8'] = MM_JSON_CTYPE_NUMBER, ['9'] = MM_JSON_CTYPE_NUMBER,

        [']'] = MM_JSON_CTYPE_ARRAY_END,
    },
    [MM_JSON_STATE_ARRAY_VALUE_SEP] = {
        [' '] = MM_JSON_CTYPE_SPACE, ['\t'] = MM_JSON_CTYPE_SPACE,
        ['\r'] = MM_JSON_CTYPE_SPACE, ['\n'] = MM_JSON_CTYPE_SPACE,

        [','] = MM_JSON_CTYPE_ARRAY_NEXT,

        [']'] = MM_JSON_CTYPE_ARRAY_END,
    },
};

mm_json_token_t __attribute__((nonnull(1)))
mm_json_reader_next(struct mm_json_reader *reader)
{
    switch (reader->token) {
        case MM_JSON_INITIAL:
            return (reader->token = MM_JSON_START_DOCUMENT);

        case MM_JSON_PARTIAL:
            // Just take up where we left off.
            break;

        case MM_JSON_ERROR:
            // Once an error, always an error.
            return reader->token;

        case MM_JSON_START_DOCUMENT:
            reader->state = MM_JSON_STATE_VALUE;
            break;

        case MM_JSON_START_OBJECT:
            reader->state = MM_JSON_STATE_OBJECT;
            break;

        case MM_JSON_START_ARRAY:
            reader->state = MM_JSON_STATE_ARRAY;
            break;

        case MM_JSON_NAME:
            reader->state = MM_JSON_STATE_OBJECT_NAME_SEP;
            break;

        case MM_JSON_STRING:
        case MM_JSON_NUMBER:
        case MM_JSON_FALSE:
        case MM_JSON_TRUE:
        case MM_JSON_NULL:
        case MM_JSON_END_OBJECT:
        case MM_JSON_END_ARRAY:
            if (reader->stack_top == 0)
                return (reader->token = MM_JSON_END_DOCUMENT);
            if (mm_json_reader_stack_get(reader))
                reader->state = MM_JSON_STATE_OBJECT_VALUE_SEP;
            else
                reader->state = MM_JSON_STATE_ARRAY_VALUE_SEP;
            break;

        case MM_JSON_END_DOCUMENT:
            reader->state = MM_JSON_STATE_SPACE;
            break;

        default:
            ABORT();
    }

    for (;;) {
        if (reader->ptr == reader->end) {
            if (reader->ptr == reader->input_end)
                return (reader->token = MM_JSON_PARTIAL);

            reader->ptr = reader->input;
            reader->end = reader->input_end;
            if (unlikely(reader->ptr == reader->end))
                return (reader->token = MM_JSON_PARTIAL);
        }

        uint8_t c = *reader->ptr;
        switch (mm_json_text_table[reader->state][c]) {
            case MM_JSON_CTYPE_ERROR:
                return (reader->token = MM_JSON_ERROR);

            case MM_JSON_CTYPE_SPACE:
                reader->ptr++;
                break;

            case MM_JSON_CTYPE_ARRAY:
                reader->ptr++;
                mm_json_reader_stack_push(reader, false);
                return (reader->token = MM_JSON_START_ARRAY);

            case MM_JSON_CTYPE_ARRAY_NEXT:
                reader->ptr++;
                reader->state = MM_JSON_STATE_VALUE;
                break;

            case MM_JSON_CTYPE_ARRAY_END:
                reader->ptr++;
                mm_json_reader_stack_pop(reader);
                return (reader->token = MM_JSON_END_ARRAY);

            case MM_JSON_CTYPE_OBJECT:
                reader->ptr++;
                mm_json_reader_stack_push(reader, true);
                return (reader->token = MM_JSON_START_OBJECT);

            case MM_JSON_CTYPE_OBJECT_VALUE:
                reader->ptr++;
                reader->state = MM_JSON_STATE_VALUE;
                break;

            case MM_JSON_CTYPE_OBJECT_NEXT:
                reader->ptr++;
                reader->state = MM_JSON_STATE_OBJECT_NAME;
                break;

            case MM_JSON_CTYPE_OBJECT_END:
                reader->ptr++;
                mm_json_reader_stack_pop(reader);
                return (reader->token = MM_JSON_END_OBJECT);

            case MM_JSON_CTYPE_FALSE:
                return (reader->token = mm_json_reader_scan_false(reader));

            case MM_JSON_CTYPE_TRUE:
                return (reader->token = mm_json_reader_scan_true(reader));

            case MM_JSON_CTYPE_NULL:
                return (reader->token = mm_json_reader_scan_null(reader));

            case MM_JSON_CTYPE_NAME:
                return (reader->token = mm_json_reader_scan_string(reader,
                                                                   MM_JSON_NAME));

            case MM_JSON_CTYPE_STRING:
                return (reader->token = mm_json_reader_scan_string(reader,
                                                                   MM_JSON_STRING));

            case MM_JSON_CTYPE_NUMBER:
                return (reader->token = mm_json_reader_scan_number(reader));
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ __attribute__((nonnull(1))) is certainly not standard C \$\endgroup\$ – chux Oct 30 '15 at 3:05
  • \$\begingroup\$ Having #define __attribute__(x) in common.h will magically make it standard C. \$\endgroup\$ – Aleksey Demakov Oct 30 '15 at 7:00
  • \$\begingroup\$ Note: By posting code here you have also released under creative commons (see bottom of page). \$\endgroup\$ – Martin York Nov 2 '15 at 21:19
  • \$\begingroup\$ @LokiAstari That's okay. The GPL still applies to the parent project, but if there is any interest from the public I'm considering spinning off the the json code in a separate repo with a permissive license such as CC. \$\endgroup\$ – Aleksey Demakov Nov 3 '15 at 8:47
1
\$\begingroup\$
  1. Your initialization-function could just return the new reader by value. Thus, there is one argument less which must not be NULL, and it should be equally efficient.

  2. Shouldn't you guard against a NULL arena-allocator?

  3. Unless you are sure you will commonly stay with a stack having at most one element throughout a readers lifetime, get rid of the special case for that.
    It complicates the rest of your code and reduces performance.

  4. Your cleanup-function should probably just unconditionally free the memory.
    Doing those pre-checks is a pessimization, because the overwhelmingly common case gets slower (mind the minimal-stack-optimization handle under point 2).

Well, for so much code I found few things to criticize. Seems you wrote good code...

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for review. The stack is used to store single bit entities therefore it could handle nesting levels of up to 64 (on a 64-bit CPU) without stack allocation. I expect this to be the most common case, so the CPU branch predictor should make it fast while still saving on pointer dereferences (but I didn't actually benchmark it). The stack allocation case is a fallback to handle crazy levels of nesting. This could be simplified 1) by rejecting to accept that deep nesting 2) by removing proper array/object nesting checks thus removing the stack itself. \$\endgroup\$ – Aleksey Demakov Nov 3 '15 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.