non-recursive JavaScript JSON parser

Question

I have a very large JSON string that I need to parse with in-browser JavaScript. Right now, in a few browsers, I run out of stack space. Unfortunately, my JSON can contain user strings, so I can't use eval or otherwise let the browser parse it.

I've looked at a few of the standard JavaScript JSON parsers, and they are recursive. Wondering if anyone knows of any JSON parser that is safe and non-recursive. I'd be willing for it to have fewer features -- I just have a giant array of objects.

Alternatively, if someone knows of one that might be easy to modify, that would be a big help too.

EDIT: On closer inspection the stack overflow is thrown by eval() used inside the parser. So, it must be recursive.

Well, recursively-coded or not, parsing a deeply nested structure pretty much has to go through the same process. Are you sure the structure is really valid? How big is "very large"? — Pointy
– Pointy, Commented Aug 24, 2010 at 14:44
It's legal -- it's an array of a few thousand objects. When it gets to a certain size, eval() can't parse it (Well, IE can, but other browsers can't) — Lou Franco
– Lou Franco, Commented Aug 24, 2010 at 14:54
@Pointy yes it would go through the same process, but it doesn't need to use the stack, which could run out of space. Presumably, a non-recursive one builds up some other equivalent data-structure in the heap (which is larger, hopefully) — Lou Franco
– Lou Franco, Commented Aug 24, 2010 at 14:55

Lou Franco · Accepted Answer · 2010-08-24 14:42:37Z

5

If eval throws stackoverflow, you can use this

http://code.google.com/p/json-sans-eval/

A JSON parser that doesn't use eval() at all.

answered Aug 24, 2010 at 14:42

Lou Franco

89.3k14 gold badges137 silver badges199 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

drawnonward · Accepted Answer · 2011-09-04 07:14:56Z

I have written json parsers that are not recursive in several languages, but until now not in javascript. Instead of being recursive, this uses a local array named stack. In actionscript this was substantially faster and more memory efficient than recursion, and I assume javascript would be similar.

This implementation uses eval only for quoted strings with backslash escapes, as both an optimization and simplification. That could easily be replaced with the string handling from any other parser. The escape handling code is long and not related to recursion.

This implementation is not strict in (at least) the following ways. It treats 8 bit characters as whitespace. It allows leading "+" and "0" in numbers. It allows trailing "," in arrays and objects. It ignores input after the first result. So "[+09,]2" returns [9] and ignores "2".

function parseJSON( inJSON ) {
    var result;
    var parent;
    var string;

    var depth = 0;
    var stack = new Array();
    var state = 0;

    var began , place = 0 , limit = inJSON.length;
    var letter;

    while ( place < limit ) {
        letter = inJSON.charCodeAt( place++ );

        if ( letter <= 0x20 || letter >= 0x7F ) {   //  whitespace or control
        } else if ( letter === 0x22 ) {             //  " string
            var slash = 0;
            var plain = true;

            began = place - 1;
            while ( place < limit ) {
                letter = inJSON.charCodeAt( place++ );

                if ( slash !== 0 ) {
                    slash = 0;
                } else if ( letter === 0x5C ) {     //  \ escape
                    slash = 1;
                    plain = false;
                } else if ( letter === 0x22 ) {     //  " string
                    if ( plain ) {
                        result = inJSON.substring( began + 1 , place - 1 );
                    } else {
                        string = inJSON.substring( began , place );
                        result = eval( string );    //  eval to unescape
                    }

                    break;
                }
            }
        } else if ( letter === 0x7B ) {             //  { object
            stack[depth++] = state;
            stack[depth++] = parent;
            parent = new Object();
            result = undefined;
            state = letter;
        } else if ( letter === 0x7D ) {             //  } object
            if ( state === 0x3A ) {
                parent[stack[--depth]] = result;
                state = stack[--depth];
            }

            if ( state === 0x7B ) {
                result = parent;
                parent = stack[--depth];
                state = stack[--depth];
            } else {
                //  error got } expected state {
                result = undefined;
                break;
            }
        } else if ( letter === 0x5B ) {             //  [ array
            stack[depth++] = state;
            stack[depth++] = parent;
            parent = new Array();
            result = undefined;
            state = letter;
        } else if ( letter === 0x5D ) {             //  ] array
            if ( state === 0x5B ) {
                if ( undefined !== result ) parent.push( result );

                result = parent;
                parent = stack[--depth];
                state = stack[--depth];
            } else {
                //  error got ] expected state [
                result = undefined;
                break;
            }
        } else if ( letter === 0x2C ) {             //  , delimiter
            if ( undefined === result ) {
                //  error got , expected previous value
                break;
            } else if ( state === 0x3A ) {
                parent[stack[--depth]] = result;
                state = stack[--depth];
                result = undefined;
            } else if ( state === 0x5B ) {
                parent.push( result );
                result = undefined;
            } else {
                //  error got , expected state [ or :
                result = undefined;
                break;
            }
        } else if ( letter === 0x3A ) {             //  : assignment
            if ( state === 0x7B ) {
                //  could verify result is string
                stack[depth++] = state;
                stack[depth++] = result;
                state = letter;
                result = undefined;
            } else {
                //  error got : expected state {
                result = undefined;
                break;
            }
        } else {
            if ( ( letter >= 0x30 && letter <= 0x39 ) || letter === 0x2B || letter === 0x2D || letter === 0x2E ) {
                var             exponent = -2;
                var             real = ( letter === 0x2E );
                var             digits = ( letter >= 0x30 && letter <= 0x39 ) ? 1 : 0;

                began = place - 1;
                while ( place < limit ) {
                    letter = inJSON.charCodeAt( place++ );

                    if ( letter >= 0x30 && letter <= 0x39 ) {           //  digit
                        digits += 1;
                    } else if ( letter === 0x2E ) {                     //  .
                        if ( real ) break;
                        else real = true;
                    } else if ( letter === 0x45 || letter === 0x65 ) {  //  e E
                        if ( exponent > began || 0 === digits ) break;
                        else exponent = place - 1;
                        real = true;
                    } else if ( letter === 0x2B || letter === 0x2D ) {  //  + -
                        if ( place != exponent + 2 ) break;
                    } else {
                        break;
                    }
                }

                place -= 1;
                string = inJSON.substring( began , place );

                if ( 0 === digits ) break;  //  error expected digits
                if ( real ) result = parseFloat( string );
                else result = parseInt( string , 10 );
            } else if ( letter === 0x6E && 'ull' === inJSON.substr( place , 3 ) ) {
                result = null;
                place += 3;
            } else if ( letter === 0x74 && 'rue' === inJSON.substr( place , 3 ) ) {
                result = true;
                place += 3;
            } else if ( letter === 0x66 && 'alse' === inJSON.substr( place , 4 ) ) {
                result = false;
                place += 4;
            } else {
                //  error unrecognized literal
                result = undefined;
                break;
            }
        }

        if ( 0 === depth ) break;
    }

    return result;
}

Ramon Araujo · Accepted Answer · 2010-08-24 14:44:32Z

1

I recommend you to divide JSON string in chunks, and bring them on demand. May be using AJAX too, you can have a recipe that just fit your needs. Using a "divide and conquer" mechanism, I think you can still use common JSON parsing methods.

Hope that helps,

answered Aug 24, 2010 at 14:44

Ramon Araujo

1,74823 silver badges31 bronze badges

1 Comment

Lou Franco Over a year ago

We considered that, but it's difficult given other constraints. We need to send the response all at once. To delimit it so that a split() would work requires another escaping pass. We might still go this way, but hoping to find a better parser.

Nakedible · Accepted Answer · 2010-08-24 14:31:50Z

0

JSON parsing in browser is usually done with just eval, but preceding the eval with a regular expression "lint", that is supposed to make it safe to evaluate the JSON.

There is an example on this on wikipedia:

http://en.wikipedia.org/wiki/JSON#Security_issues

answered Aug 24, 2010 at 14:31

Nakedible

4,1987 gold badges37 silver badges42 bronze badges

2 Comments

Lou Franco Over a year ago

right, I see now that eval is being called after checking for safety, and then it throws a stack overflow (because it's internally recursive and the JSON string is large)

Lou Franco Over a year ago

Thanks -- your suggestion helped me see the real problem was in eval().

Collectives™ on Stack Overflow

non-recursive JavaScript JSON parser

4 Answers 4

Comments

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related