webmcp
changeset 181:c2e76617c26c
Support 715827883 nested levels in JSON parser
author | jbe |
---|---|
date | Sat Aug 02 02:38:18 2014 +0200 (2014-08-02) |
parents | 887b77f71e5e |
children | b460ae08dd78 |
files | libraries/json/json.c |
line diff
1.1 --- a/libraries/json/json.c Sat Aug 02 00:39:41 2014 +0200 1.2 +++ b/libraries/json/json.c Sat Aug 02 02:38:18 2014 +0200 1.3 @@ -5,14 +5,10 @@ 1.4 #include <math.h> 1.5 1.6 // maximum number of nested JSON values (objects and arrays): 1.7 -// NOTE: The Lua reference states that the stack may typically contain at least 1.8 -// "a few thousand elements". Since every nested level consumes 1.9 -// 3 elements on the Lua stack (the object/array, its shadow table, 1.10 -// a string key or a placeholder), we limit the number of nested levels 1.11 -// to 500. If a stack overflow would still happen in the import function, 1.12 -// this is detected nevertheless and an error is thrown (instead of 1.13 -// returning nil and an error string). 1.14 -#define JSON_MAXDEPTH 500 1.15 +// NOTE: json_import can store (2^31-1) / 3 levels on stack swap; 1.16 +// one additional level is kept on the Lua stack, resulting 1.17 +// in 715827883 possible nested levels. 1.18 +#define JSON_MAXDEPTH 715827883 1.19 // NOTE: As long as the function json_export_internal is implemented 1.20 // recursively, JSON_MAXDEPTH needs to be low (e.g. 50) to avoid C stack 1.21 // overflows. 1.22 @@ -195,6 +191,7 @@ 1.23 #define json_import_objectmt_idx 2 1.24 #define json_import_arraymt_idx 3 1.25 #define json_import_shadowtbl_idx 4 1.26 +#define json_import_stackswap_idx 5 1.27 1.28 // macros for hex decoding: 1.29 #define json_utf16_surrogate(x) ((x) >= 0xD800 && (x) <= 0xDFFF) 1.30 @@ -216,19 +213,20 @@ 1.31 1.32 // decodes a JSON document: 1.33 static int json_import(lua_State *L) { 1.34 - int i; // loop variable 1.35 - const char *str; // string to parse 1.36 - size_t total; // total length of string to parse 1.37 - size_t pos = 0; // current position in string to parse 1.38 - size_t level = 0; // nested levels of objects/arrays currently being processed 1.39 + int stackswapidx = 0; // elements in stack swap table 1.40 + int i; // loop variable 1.41 + const char *str; // string to parse 1.42 + size_t total; // total length of string to parse 1.43 + size_t pos = 0; // current position in string to parse 1.44 + size_t level = 0; // nested levels of objects/arrays currently being processed 1.45 int mode = JSON_STATE_VALUE; // state of parser (i.e. "what's expected next?") 1.46 - unsigned char c; // variable to store a single character to be processed (unsigned!) 1.47 - luaL_Buffer luabuf; // Lua buffer to decode JSON string values 1.48 - char *cbuf; // C buffer to decode JSON string values 1.49 - size_t outlen; // maximum length or write position of C buffer 1.50 - long codepoint; // decoded UTF-16 character or higher codepoint 1.51 - long utf16tail; // second decoded UTF-16 character (surrogate tail) 1.52 - size_t arraylen; // variable to temporarily store the array length 1.53 + unsigned char c; // variable to store a single character to be processed (unsigned!) 1.54 + luaL_Buffer luabuf; // Lua buffer to decode JSON string values 1.55 + char *cbuf; // C buffer to decode JSON string values 1.56 + size_t outlen; // maximum length or write position of C buffer 1.57 + long codepoint; // decoded UTF-16 character or higher codepoint 1.58 + long utf16tail; // second decoded UTF-16 character (surrogate tail) 1.59 + size_t arraylen; // variable to temporarily store the array length 1.60 // require string as argument and convert to C string with length information: 1.61 str = luaL_checklstring(L, 1, &total); 1.62 // if string contains a NULL byte, this is a syntax error 1.63 @@ -241,6 +239,9 @@ 1.64 json_regfetch(L, arraymt); 1.65 // push shadowtbl onto stack position 4: 1.66 json_regfetch(L, shadowtbl); 1.67 + // push table for stack swapping onto stack position 5: 1.68 + // (needed to avoid Lua stack overflows) 1.69 + lua_newtable(L); 1.70 // main loop of parser: 1.71 json_import_loop: 1.72 // skip whitespace and store next character in variable 'c': 1.73 @@ -269,18 +270,44 @@ 1.74 lua_pushliteral(L, "Unexpected end of JSON document"); 1.75 } 1.76 return 2; 1.77 - // new JSON object: 1.78 + // new JSON object or JSON array: 1.79 case '{': 1.80 - // if a JSON object is not expected here, then return an error: 1.81 + case '[': 1.82 + // if an encountered JSON object is not expected here, then return an error: 1.83 if ( 1.84 + c == '{' && 1.85 + mode != JSON_STATE_VALUE && 1.86 + mode != JSON_STATE_OBJECT_VALUE && 1.87 + mode != JSON_STATE_ARRAY_VALUE 1.88 + ) goto json_import_syntax_error; 1.89 + // if an encountered JSON array is not expected here, then return an error: 1.90 + if ( 1.91 + c == '[' && 1.92 mode != JSON_STATE_VALUE && 1.93 mode != JSON_STATE_OBJECT_VALUE && 1.94 mode != JSON_STATE_ARRAY_VALUE 1.95 ) goto json_import_syntax_error; 1.96 - // create JSON object on stack: 1.97 + // consume input character: 1.98 + pos++; 1.99 + // limit nested levels: 1.100 + if (level >= JSON_MAXDEPTH) { 1.101 + lua_pushnil(L); 1.102 + lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH); 1.103 + return 2; 1.104 + } 1.105 + // swap Lua stack entries for previous level to swap table: 1.106 + // (avoids depth limitations due to Lua stack size) 1.107 + if (level) { 1.108 + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); 1.109 + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); 1.110 + lua_rawseti(L, json_import_stackswap_idx, ++stackswapidx); 1.111 + } 1.112 + // increment level: 1.113 + level++; 1.114 + // create JSON object or JSON array on stack: 1.115 lua_newtable(L); 1.116 - // set metatable of JSON object: 1.117 - lua_pushvalue(L, json_import_objectmt_idx); 1.118 + // set metatable of JSON object or JSON array: 1.119 + lua_pushvalue(L, c == '{' ? json_import_objectmt_idx : json_import_arraymt_idx); 1.120 lua_setmetatable(L, -2); 1.121 // create internal shadow table on stack: 1.122 lua_newtable(L); 1.123 @@ -288,49 +315,18 @@ 1.124 lua_pushvalue(L, -2); 1.125 lua_pushvalue(L, -2); 1.126 lua_rawset(L, json_import_shadowtbl_idx); 1.127 - // expect object key (or end of object) to follow: 1.128 - mode = JSON_STATE_OBJECT_KEY; 1.129 - // jump to common code for opening JSON object and JSON array: 1.130 - goto json_import_open; 1.131 - // new JSON array: 1.132 - case '[': 1.133 - // if a JSON array is not expected here, then return an error: 1.134 - if ( 1.135 - mode != JSON_STATE_VALUE && 1.136 - mode != JSON_STATE_OBJECT_VALUE && 1.137 - mode != JSON_STATE_ARRAY_VALUE 1.138 - ) goto json_import_syntax_error; 1.139 - // create JSON array on stack: 1.140 - lua_newtable(L); 1.141 - // set metatable of JSON array: 1.142 - lua_pushvalue(L, json_import_arraymt_idx); 1.143 - lua_setmetatable(L, -2); 1.144 - // create internal shadow table on stack: 1.145 - lua_newtable(L); 1.146 - // register internal shadow table: 1.147 - lua_pushvalue(L, -2); 1.148 - lua_pushvalue(L, -2); 1.149 - lua_rawset(L, json_import_shadowtbl_idx); 1.150 - // add nil as key (needed to keep stack balance) and as magic to detect arrays: 1.151 - lua_pushnil(L); 1.152 - // expect array value (or end of array) to follow: 1.153 - mode = JSON_STATE_ARRAY_VALUE; 1.154 - // continue with common code for opening JSON object and JSON array: 1.155 - // common code for opening JSON object or JSON array: 1.156 - json_import_open: 1.157 - // limit nested levels: 1.158 - if (level >= JSON_MAXDEPTH) { 1.159 - lua_pushnil(L); 1.160 - lua_pushfstring(L, "More than %d nested JSON levels", JSON_MAXDEPTH); 1.161 - return 2; 1.162 + // distinguish between JSON objects and JSON arrays: 1.163 + if (c == '{') { 1.164 + // if JSON object, 1.165 + // expect object key (or end of object) to follow: 1.166 + mode = JSON_STATE_OBJECT_KEY; 1.167 + } else { 1.168 + // if JSON array, 1.169 + // expect array value (or end of array) to follow: 1.170 + mode = JSON_STATE_ARRAY_VALUE; 1.171 + // add nil as key (needed to keep stack balance) and as magic to detect arrays: 1.172 + if (c == '[') lua_pushnil(L); 1.173 } 1.174 - // additional buffer overflow protection: 1.175 - if (!lua_checkstack(L, LUA_MINSTACK)) 1.176 - return luaL_error(L, "Caught stack overflow in JSON import function (too many nested levels and stack size too small)"); 1.177 - // increment level: 1.178 - level++; 1.179 - // consume input character: 1.180 - pos++; 1.181 goto json_import_loop; 1.182 // end of JSON object: 1.183 case '}': 1.184 @@ -360,6 +356,13 @@ 1.185 // check if nested: 1.186 if (--level) { 1.187 // if nested, 1.188 + // restore previous stack elements from stack swap: 1.189 + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); 1.190 + lua_insert(L, -2); 1.191 + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); 1.192 + lua_insert(L, -2); 1.193 + lua_rawgeti(L, json_import_stackswap_idx, stackswapidx--); 1.194 + lua_insert(L, -2); 1.195 // check if outer(!) structure is an array or object: 1.196 if (lua_isnil(L, -2)) { 1.197 // select array value processing: