# HG changeset patch # User jbe # Date 1406939898 -7200 # Node ID c2e76617c26cf586106112a9c0310e0018438dc5 # Parent 887b77f71e5e99e5c5d8dad6adbeca33f45a558a Support 715827883 nested levels in JSON parser diff -r 887b77f71e5e -r c2e76617c26c libraries/json/json.c --- a/libraries/json/json.c Sat Aug 02 00:39:41 2014 +0200 +++ b/libraries/json/json.c Sat Aug 02 02:38:18 2014 +0200 @@ -5,14 +5,10 @@ #include // maximum number of nested JSON values (objects and arrays): -// NOTE: The Lua reference states that the stack may typically contain at least -// "a few thousand elements". Since every nested level consumes -// 3 elements on the Lua stack (the object/array, its shadow table, -// a string key or a placeholder), we limit the number of nested levels -// to 500. If a stack overflow would still happen in the import function, -// this is detected nevertheless and an error is thrown (instead of -// returning nil and an error string). -#define JSON_MAXDEPTH 500 +// NOTE: json_import can store (2^31-1) / 3 levels on stack swap; +// one additional level is kept on the Lua stack, resulting +// in 715827883 possible nested levels. +#define JSON_MAXDEPTH 715827883 // NOTE: As long as the function json_export_internal is implemented // recursively, JSON_MAXDEPTH needs to be low (e.g. 50) to avoid C stack // overflows. @@ -195,6 +191,7 @@ #define json_import_objectmt_idx 2 #define json_import_arraymt_idx 3 #define json_import_shadowtbl_idx 4 +#define json_import_stackswap_idx 5 // macros for hex decoding: #define json_utf16_surrogate(x) ((x) >= 0xD800 && (x) <= 0xDFFF) @@ -216,19 +213,20 @@ // decodes a JSON document: static int json_import(lua_State *L) { - int i; // loop variable - const char *str; // string to parse - size_t total; // total length of string to parse - size_t pos = 0; // current position in string to parse - size_t level = 0; // nested levels of objects/arrays currently being processed + int stackswapidx = 0; // elements in stack swap table + int i; // loop variable + const char *str; // string to parse + size_t total; // total length of string to parse + size_t pos = 0; // current position in string to parse + size_t level = 0; // nested levels of objects/arrays currently being processed int mode = JSON_STATE_VALUE; // state of parser (i.e. "what's expected next?") - unsigned char c; // variable to store a single character to be processed (unsigned!) - luaL_Buffer luabuf; // Lua buffer to decode JSON string values - char *cbuf; // C buffer to decode JSON string values - size_t outlen; // maximum length or write position of C buffer - long codepoint; // decoded UTF-16 character or higher codepoint - long utf16tail; // second decoded UTF-16 character (surrogate tail) - size_t arraylen; // variable to temporarily store the array length + unsigned char c; // variable to store a single character to be processed (unsigned!) + luaL_Buffer luabuf; // Lua buffer to decode JSON string values + char *cbuf; // C buffer to decode JSON string values + size_t outlen; // maximum length or write position of C buffer + long codepoint; // decoded UTF-16 character or higher codepoint + long utf16tail; // second decoded UTF-16 character (surrogate tail) + size_t arraylen; // variable to temporarily store the array length // require string as argument and convert to C string with length information: str = luaL_checklstring(L, 1, &total); // if string contains a NULL byte, this is a syntax error @@ -241,6 +239,9 @@ json_regfetch(L, arraymt); // push shadowtbl onto stack position 4: json_regfetch(L, shadowtbl); + // push table for stack swapping onto stack position 5: + // (needed to avoid Lua stack overflows) + lua_newtable(L); // main loop of parser: json_import_loop: // skip whitespace and store next character in variable 'c': @@ -269,18 +270,44 @@ lua_pushliteral(L, "Unexpected end of JSON document"); } return 2; - // new JSON object: + // new JSON object or JSON array: case '{': - // if a JSON object is not expected here, then return an error: + case '[': + // if an encountered JSON object is not expected here, then return an error: if ( + c == '{' && + mode != JSON_STATE_VALUE && + mode != JSON_STATE_OBJECT_VALUE && + mode != JSON_STATE_ARRAY_VALUE + ) goto json_import_syntax_error; + // if an encountered JSON array is not expected here, then return an error: + if ( + c == '[' && mode != JSON_STATE_VALUE && mode != JSON_STATE_OBJECT_VALUE && mode != JSON_STATE_ARRAY_VALUE ) goto json_import_syntax_error; - // create JSON object on stack: + // consume input character: + pos++; + // limit nested levels: + if (level >= JSON_MAXDEPTH) { + lua_pushnil(L); + lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH); + return 2; + } + // swap Lua stack entries for previous level to swap table: + // (avoids depth limitations due to Lua stack size) + if (level) { + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); + } + // increment level: + level++; + // create JSON object or JSON array on stack: lua_newtable(L); - // set metatable of JSON object: - lua_pushvalue(L, json_import_objectmt_idx); + // set metatable of JSON object or JSON array: + lua_pushvalue(L, c == '{' ? json_import_objectmt_idx : json_import_arraymt_idx); lua_setmetatable(L, -2); // create internal shadow table on stack: lua_newtable(L); @@ -288,49 +315,18 @@ lua_pushvalue(L, -2); lua_pushvalue(L, -2); lua_rawset(L, json_import_shadowtbl_idx); - // expect object key (or end of object) to follow: - mode = JSON_STATE_OBJECT_KEY; - // jump to common code for opening JSON object and JSON array: - goto json_import_open; - // new JSON array: - case '[': - // if a JSON array is not expected here, then return an error: - if ( - mode != JSON_STATE_VALUE && - mode != JSON_STATE_OBJECT_VALUE && - mode != JSON_STATE_ARRAY_VALUE - ) goto json_import_syntax_error; - // create JSON array on stack: - lua_newtable(L); - // set metatable of JSON array: - lua_pushvalue(L, json_import_arraymt_idx); - lua_setmetatable(L, -2); - // create internal shadow table on stack: - lua_newtable(L); - // register internal shadow table: - lua_pushvalue(L, -2); - lua_pushvalue(L, -2); - lua_rawset(L, json_import_shadowtbl_idx); - // add nil as key (needed to keep stack balance) and as magic to detect arrays: - lua_pushnil(L); - // expect array value (or end of array) to follow: - mode = JSON_STATE_ARRAY_VALUE; - // continue with common code for opening JSON object and JSON array: - // common code for opening JSON object or JSON array: - json_import_open: - // limit nested levels: - if (level >= JSON_MAXDEPTH) { - lua_pushnil(L); - lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH); - return 2; + // distinguish between JSON objects and JSON arrays: + if (c == '{') { + // if JSON object, + // expect object key (or end of object) to follow: + mode = JSON_STATE_OBJECT_KEY; + } else { + // if JSON array, + // expect array value (or end of array) to follow: + mode = JSON_STATE_ARRAY_VALUE; + // add nil as key (needed to keep stack balance) and as magic to detect arrays: + if (c == '[') lua_pushnil(L); } - // additional buffer overflow protection: - if (!lua_checkstack(L, LUA_MINSTACK)) - return luaL_error(L, "Caught stack overflow in JSON import function (too many nested levels and stack size too small)"); - // increment level: - level++; - // consume input character: - pos++; goto json_import_loop; // end of JSON object: case '}': @@ -360,6 +356,13 @@ // check if nested: if (--level) { // if nested, + // restore previous stack elements from stack swap: + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); + lua_insert(L, -2); + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); + lua_insert(L, -2); + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); + lua_insert(L, -2); // check if outer(!) structure is an array or object: if (lua_isnil(L, -2)) { // select array value processing: