# HG changeset patch # User jbe # Date 1407605956 -7200 # Node ID f7c1869b5b326df6c058254035a4f1daf1e517b3 # Parent b460ae08dd78b8587ec9b37d527d7950e4bf4ec6 Reimplemented json.export(...) function without recursion (incomplete yet) diff -r b460ae08dd78 -r f7c1869b5b32 libraries/json/json.c --- a/libraries/json/json.c Sat Aug 02 02:53:32 2014 +0200 +++ b/libraries/json/json.c Sat Aug 09 19:39:16 2014 +0200 @@ -6,16 +6,11 @@ // maximum number of nested JSON values (objects and arrays): // NOTE: json_import can store 2^32 / 3 levels on stack swap (using -// also negative indicies after integer wraparound), so -// 1024^3 = 1073741824 is a safe value. +// also negative indicies after integer wraparound), and +// json_export can store even more levels, so 1024^3 = +// 1073741824 is a safe value and allows practically unlimited +// levels for JSON documents <= 2 GiB. #define JSON_MAXDEPTH (1024*1024*1024) -// 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. -#if JSON_MAXDEPTH > 50 -#undef JSON_MAXDEPTH -#define JSON_MAXDEPTH 50 -#endif // generate dummy memory addresses that represents null values: char json_nullmark; @@ -1002,345 +997,312 @@ #define JSON_TABLETYPE_OBJECT 1 #define JSON_TABLETYPE_ARRAY 2 -// special Lua stack indicies for json_export_internal function: -#define json_export_internal_indentstring_idx 1 -#define json_export_internal_level_idx 2 -#define json_export_internal_value_idx 3 -#define json_export_internal_tmp_idx 4 +typedef struct { + int type; + int pos; + int count; + json_key_t keys[1]; // or more +} json_container_t; + +// special Lua stack indicies for json_export function: +#define json_export_value_idx 1 +#define json_export_indentstring_idx 2 +#define json_export_objectmt_idx 3 +#define json_export_arraymt_idx 4 +#define json_export_shadowtbl_idx 5 +#define json_export_stackswap_idx 6 +#define json_export_luacontainer_idx 7 +#define json_export_ccontainer_idx 8 -// encodes a JSON document (passed as third argument) -// optionally using indentation (indentation string passed as first argument) -// for a certain depth level (passed as second argument): -static int json_export_internal(lua_State *L) { +// encodes a JSON document (passed as first argument) +// optionally using indentation (indentation string passed as second argument) +static int json_export(lua_State *L) { + int pretty; // pretty printing on? (i.e. printing with indentation) + luaL_Buffer buf; // Lua buffer containing result string + lua_Number num; // number to encode + const char *str; // string to encode + size_t strlen; // length of string to encode + size_t strpos ; // position in string or position of current key + unsigned char c; // character to encode (unsigned!) + char hexcode[7]; // store for unicode hex escape sequence + // NOTE: 7 bytes due to backslash, character 'u', 4 hex digits, and terminating NULL byte + int tabletype; // table type: unknown, JSON object, or JSON array + size_t keycount = 0; // number of string keys in object + int level = 0; // current depth level + int i; // iteration variable for level dependent repetitions + int stackswapidx = 0; // elements in stack swap table + int containerkey = 0; // temporarily set to 1, if a container key is being encoded + json_container_t *container = NULL; // pointer to current C struct for container information +/* int level; // current depth level - int pretty; // pretty printing on? (i.e. printing with indentation) - int i; // iteration variable for level dependent repetitions: - lua_Number num; // number to encode - const char *str; // string to encode - size_t strlen; // length of string to encode - unsigned char c; // character to encode (unsigned!) - size_t pos = 0; // position in string or position of current key (initialized with zero!) - luaL_Buffer buf; // Lua buffer to create strings - char hexcode[7]; // store for unicode hex escape sequence - // NOTE: 7 bytes due to backslash, character 'u', 4 hex digits, and terminating NULL byte - int tabletype = JSON_TABLETYPE_UNKNOWN; // table type: unknown, JSON object, or JSON array int anyelement = 0; // set to 1 if at least one array element has been processed - size_t keycount = 0; // number of string keys in object json_key_t *keybuf = NULL; // temporary buffer to store (and sort) string keys of objects lua_Integer arrayidx; // index to iterate through arrays - // stack shall contain three function arguments: - lua_settop(L, json_export_internal_value_idx); - // if value to encode is the null-marker, then treat it the same as nil: - if (json_isnullmark(L, json_export_internal_value_idx)) { - lua_pop(L, 1); - lua_pushnil(L); +*/ + // stack shall contain two function arguments: + lua_settop(L, 2); + // use default indentation if indentation argument is (boolean) true: + if ( + lua_isboolean(L, json_export_indentstring_idx) && + lua_toboolean(L, json_export_indentstring_idx) + ) { + lua_pushliteral(L, " "); + lua_replace(L, json_export_indentstring_idx); } - // distinguish between different Lua types: - switch (lua_type(L, json_export_internal_value_idx)) { - // value to encode is nil: - case LUA_TNIL: - // return string "null": - lua_pushliteral(L, "null"); - return 1; - // value to encode is of type number: - case LUA_TNUMBER: - // convert value to double precision number: - num = lua_tonumber(L, json_export_internal_value_idx); - // throw error if number is not-a-number: - if (isnan(num)) return luaL_error(L, "JSON export not possible for NaN value"); - // throw error if number is positive or negative infinity: - if (isinf(num)) return luaL_error(L, "JSON export not possible for infinite numbers"); - // return Lua's string encoding of the number: - lua_tostring(L, json_export_internal_value_idx); - return 1; - // value to encode is of type boolean: - case LUA_TBOOLEAN: - // return string "true" or "false" according to boolean value: - if (lua_toboolean(L, json_export_internal_value_idx)) { - lua_pushliteral(L, "true"); - } else { - lua_pushliteral(L, "false"); + // set pretty variable to 1 if pretty printing (with indentation) is desired: + pretty = lua_toboolean(L, json_export_indentstring_idx); + // push objectmt onto stack position 3: + json_regfetch(L, objectmt); + // push arraymt onto stack position 4: + json_regfetch(L, arraymt); + // push shadowtbl onto stack position 5: + json_regfetch(L, shadowtbl); + // push table for stack swapping onto stack position 6: + lua_newtable(L); + // create placeholders on stack positions 7 through 8: + lua_settop(L, 9); + // create Lua string buffer: + luaL_buffinit(L, &buf); + // loop: + while (1) { + // if value to encode is the null-marker, then treat it the same as nil: + if (json_isnullmark(L, json_export_value_idx)) { + lua_pushnil(L); + lua_replace(L, json_export_value_idx); } - return 1; - // value to encode is of type string: - case LUA_TSTRING: - // quote, escape and return string: - str = lua_tolstring(L, 3, &strlen); - luaL_buffinit(L, &buf); - luaL_addchar(&buf, '"'); - while (pos < strlen) { - c = str[pos++]; - if (c == '"') luaL_addstring(&buf, "\\\""); - else if (c == '\\') luaL_addstring(&buf, "\\\\"); - else if (c == 127) luaL_addstring(&buf, "\\u007F"); - else if (c >= 32) luaL_addchar(&buf, c); - else if (c == '\b') luaL_addstring(&buf, "\\b"); - else if (c == '\f') luaL_addstring(&buf, "\\f"); - else if (c == '\n') luaL_addstring(&buf, "\\n"); - else if (c == '\r') luaL_addstring(&buf, "\\r"); - else if (c == '\t') luaL_addstring(&buf, "\\t"); - else if (c == '\v') luaL_addstring(&buf, "\\v"); - else { - sprintf(hexcode, "\\u%04X", c); - luaL_addstring(&buf, hexcode); - } - } - luaL_addchar(&buf, '"'); - luaL_pushresult(&buf); - return 1; - // value to encode is of type table (this includes JSON objects and JSON arrays): - case LUA_TTABLE: - // use table's metatable to try to determine type of table: - if (lua_getmetatable(L, json_export_internal_value_idx)) { - json_regfetch(L, objectmt); - if (lua_rawequal(L, -2, -1)) { - tabletype = JSON_TABLETYPE_OBJECT; - } else { - json_regfetch(L, arraymt); - if (lua_rawequal(L, -3, -1)) { - tabletype = JSON_TABLETYPE_ARRAY; - } else { - return luaL_error(L, "JSON export not possible for tables with nonsupported metatable"); - } - } - } - // replace table with its shadow table if existent, and reset stack: - json_regfetch(L, shadowtbl); - lua_pushvalue(L, json_export_internal_value_idx); - lua_rawget(L, -2); - if (!lua_isnil(L, -1)) lua_replace(L, json_export_internal_value_idx); - lua_settop(L, json_export_internal_value_idx); - // check if type of table is still undetermined: - if (tabletype == JSON_TABLETYPE_UNKNOWN) { - // if yes, iterate over all keys: - for (lua_pushnil(L); lua_next(L, json_export_internal_value_idx); lua_pop(L, 1)) { - switch (lua_type(L, -2)) { - case LUA_TSTRING: - // for string keys, - // increase keycount (may avoid another iteration): - keycount++; - // if type of table was unknown, then type of table is a JSON object now: - if (tabletype == JSON_TABLETYPE_UNKNOWN) tabletype = JSON_TABLETYPE_OBJECT; - // if type of table was a JSON array, then the type of table is ambiguous now - // and an error is thrown: - else if (tabletype == JSON_TABLETYPE_ARRAY) goto json_export_tabletype_error; - break; - case LUA_TNUMBER: - // for numeric keys, - // if type of table was unknown, then type of table is a JSON array now: - if (tabletype == JSON_TABLETYPE_UNKNOWN) tabletype = JSON_TABLETYPE_ARRAY; - // if type of table was a JSON object, then the type of table is ambiguous now - // and an error is thrown: - else if (tabletype == JSON_TABLETYPE_OBJECT) goto json_export_tabletype_error; - break; + // distinguish between different Lua types: + switch (lua_type(L, json_export_value_idx)) { + // value to encode is nil: + case LUA_TNIL: + // add string "null" to output buffer: + luaL_addstring(&buf, "null"); + break; + // value to encode is of type number: + case LUA_TNUMBER: + // convert value to double precision number: + num = lua_tonumber(L, json_export_value_idx); + // throw error if number is not-a-number: + if (isnan(num)) return luaL_error(L, "JSON export not possible for NaN value"); + // throw error if number is positive or negative infinity: + if (isinf(num)) return luaL_error(L, "JSON export not possible for infinite numbers"); + // add Lua's string encoding of the number to the output buffer: + lua_pushvalue(L, json_export_value_idx); + lua_tostring(L, -1); + luaL_addvalue(&buf); + break; + // value to encode is of type boolean: + case LUA_TBOOLEAN: + // add string "true" or "false" according to boolean value: + luaL_addstring(&buf, lua_toboolean(L, json_export_value_idx) ? "true" : "false"); + break; + // value to encode is of type string: + case LUA_TSTRING: + // add quoted and escaped string to output buffer: + str = lua_tolstring(L, json_export_value_idx, &strlen); + luaL_addchar(&buf, '"'); + strpos = 0; + while (strpos < strlen) { + c = str[strpos++]; + if (c == '"') luaL_addstring(&buf, "\\\""); + else if (c == '\\') luaL_addstring(&buf, "\\\\"); + else if (c == 127) luaL_addstring(&buf, "\\u007F"); + else if (c >= 32) luaL_addchar(&buf, c); + else if (c == '\b') luaL_addstring(&buf, "\\b"); + else if (c == '\f') luaL_addstring(&buf, "\\f"); + else if (c == '\n') luaL_addstring(&buf, "\\n"); + else if (c == '\r') luaL_addstring(&buf, "\\r"); + else if (c == '\t') luaL_addstring(&buf, "\\t"); + else if (c == '\v') luaL_addstring(&buf, "\\v"); + else { + sprintf(hexcode, "\\u%04X", c); + luaL_addstring(&buf, hexcode); } } - } - // set pretty variable to 1 if pretty printing (with indentation) is desired: - pretty = lua_toboolean(L, json_export_internal_indentstring_idx); - // set level variable to corresponding function argument increased by one: - level = lua_tointeger(L, json_export_internal_level_idx) + 1; - // throw error if there are more levels that could be imported by this library: - if (level > JSON_MAXDEPTH) { - return luaL_error(L, "More than %d nested JSON levels", JSON_MAXDEPTH); - } - // distinguish between JSON objects and JSON arrays: - switch (tabletype) { - // JSON object: - case JSON_TABLETYPE_OBJECT: - // calculate count of string keys unless it has been calculated before: - if (!keycount) { - for (lua_pushnil(L); lua_next(L, json_export_internal_value_idx); lua_pop(L, 1)) { - if (lua_type(L, -2) == LUA_TSTRING) keycount++; + luaL_addchar(&buf, '"'); + break; + // value to encode is of type table (this includes JSON objects and JSON arrays): + case LUA_TTABLE: + // use value as container: + lua_pushvalue(L, json_export_value_idx); + lua_replace(L, json_export_luacontainer_idx); + // use table's metatable to try to determine type of table: + tabletype = JSON_TABLETYPE_UNKNOWN; + if (lua_getmetatable(L, json_export_luacontainer_idx)) { + if (lua_rawequal(L, -1, json_export_objectmt_idx)) { + tabletype = JSON_TABLETYPE_OBJECT; + } else { + if (lua_rawequal(L, -1, json_export_arraymt_idx)) { + tabletype = JSON_TABLETYPE_ARRAY; + } else { + return luaL_error(L, "JSON export not possible for tables with nonsupported metatable"); + } + } + // reset stack (pop metatable from stack): + lua_pop(L, 1); + } + // replace table with its shadow table if existent, and reset stack: + lua_pushvalue(L, json_export_luacontainer_idx); + lua_rawget(L, json_export_shadowtbl_idx); + if (lua_isnil(L, -1)) lua_pop(L, 1); + else lua_replace(L, json_export_luacontainer_idx); + // check if type of table is still undetermined: + if (tabletype == JSON_TABLETYPE_UNKNOWN) { + // if yes, iterate over all keys: + for (lua_pushnil(L); lua_next(L, json_export_luacontainer_idx); lua_pop(L, 1)) { + switch (lua_type(L, -2)) { + case LUA_TSTRING: + // for string keys, + // increase keycount (may avoid another iteration): + keycount++; + // if type of table was unknown, then type of table is a JSON object now: + if (tabletype == JSON_TABLETYPE_UNKNOWN) tabletype = JSON_TABLETYPE_OBJECT; + // if type of table was a JSON array, then the type of table is ambiguous now + // and an error is thrown: + else if (tabletype == JSON_TABLETYPE_ARRAY) goto json_export_tabletype_error; + break; + case LUA_TNUMBER: + // for numeric keys, + // if type of table was unknown, then type of table is a JSON array now: + if (tabletype == JSON_TABLETYPE_UNKNOWN) tabletype = JSON_TABLETYPE_ARRAY; + // if type of table was a JSON object, then the type of table is ambiguous now + // and an error is thrown: + else if (tabletype == JSON_TABLETYPE_OBJECT) goto json_export_tabletype_error; + break; + } } } - // create a sorted list of all string keys in memory: - if (keycount) { - // allocate memory for string keys: - keybuf = calloc(keycount, sizeof(json_key_t)); - // check if memory allocation was successful: - if (!keybuf) { - // in case of memory exhaustion, try to collect garbage: - lua_gc(L, LUA_GCCOLLECT, 0); - // try to allocate memory again: - keybuf = calloc(keycount, sizeof(json_key_t)); - // throw error if memory allocation failed again: - if (!keybuf) { - return luaL_error(L, "Memory allocation failed in JSON library"); - } - } - // copy all string keys to the C array: - for (lua_pushnil(L); lua_next(L, json_export_internal_value_idx); lua_pop(L, 1)) { - if (lua_type(L, -2) == LUA_TSTRING) { - json_key_t *key = keybuf + (pos++); - key->data = lua_tolstring(L, -2, &key->length); - } - } - // sort C array using quicksort: - qsort(keybuf, keycount, sizeof(json_key_t), (void *)json_key_cmp); + // raise error if too many nested levels: + if (level >= JSON_MAXDEPTH) { + return luaL_error(L, "More than %d nested JSON levels", JSON_MAXDEPTH); } - // create Lua string buffer: - luaL_buffinit(L, &buf); - // add opening bracket to output buffer: - luaL_addchar(&buf, '{'); - // iterate through all (sorted) string keys: - for (pos=0; posdata, key->length); - if (lua_pcall(L, 3, 1, 0)) { - // free memory of sorted string keys on error: - if (keybuf) free(keybuf); - // rethrow error: - return lua_error(L); + // create a sorted list of all string keys in memory: + if (keycount) { + // allocate memory for C structure containing string keys and container iteration state: + container = lua_newuserdata(L, sizeof(json_container_t) + (keycount-1) * sizeof(json_key_t)); + // store reference on designated stack position: + lua_replace(L, json_export_ccontainer_idx); + // initialize C structure for container state: + container->type = JSON_TABLETYPE_OBJECT; + container->count = keycount; + container->pos = 0; + // copy all string keys to the C structure and reset container->pos again: + for (lua_pushnil(L); lua_next(L, json_export_luacontainer_idx); lua_pop(L, 1)) { + if (lua_type(L, -2) == LUA_TSTRING) { + json_key_t *key = &container->keys[container->pos++]; + key->data = lua_tolstring(L, -2, &key->length); + } + } + container->pos = 0; + // sort C array using quicksort: + qsort(container->keys, keycount, sizeof(json_key_t), (void *)json_key_cmp); } - // add encoded key to output buffer: - luaL_addvalue(&buf); - // add colon to output buffer: - luaL_addchar(&buf, ':'); - // handle indentation for pretty results: - if (pretty) luaL_addchar(&buf, ' '); - // recursive call to encode value: - lua_pushcfunction(L, json_export_internal); - lua_pushvalue(L, json_export_internal_indentstring_idx); - lua_pushinteger(L, level); - lua_pushlstring(L, key->data, key->length); - lua_rawget(L, json_export_internal_value_idx); - if (lua_pcall(L, 3, 1, 0)) { - // free memory of sorted string keys on error: - if (keybuf) free(keybuf); - // rethrow error: - return lua_error(L); + // add opening bracket to output buffer: + luaL_addchar(&buf, '{'); + break; + // JSON array: + case JSON_TABLETYPE_ARRAY: + container = lua_newuserdata(L, sizeof(json_container_t) - sizeof(json_key_t)); + lua_replace(L, json_export_ccontainer_idx); + container->type = JSON_TABLETYPE_ARRAY; + container->pos = 0; + // add opening bracket to output buffer: + luaL_addchar(&buf, '['); + break; + default: + // throw error if table type is unknown: + json_export_tabletype_error: + return luaL_error(L, "JSON export not possible for ambiguous table (cannot decide whether it is an object or array)"); + } + break; + default: + // all other datatypes are considered an error: + return luaL_error(L, "JSON export not possible for values of type \"%s\"", lua_typename(L, lua_type(L, json_export_value_idx))); + } + if (container) { + // add colon where necessary: + if (containerkey) luaL_addchar(&buf, ':'); + switch (container->type) { + case JSON_TABLETYPE_OBJECT: + if (container->pos < container->count) { + json_key_t *key; + key = &container->keys[container->pos]; + lua_pushlstring(L, key->data, key->length); + if (!containerkey) { + containerkey = 1; + } else { + lua_rawget(L, json_export_luacontainer_idx); + containerkey = 0; + container->pos++; + } + lua_replace(L, json_export_value_idx); + } else { + luaL_addchar(&buf, '}'); + goto json_export_close; } - // add encoded value to output buffer: - luaL_addvalue(&buf); - } - // decrement level variable for all following statements: - level--; - // free memory of sorted string keys: - if (keybuf) free(keybuf); - // handle indentation for pretty results: - if (pretty && keycount != 0) { - luaL_addchar(&buf, '\n'); - for (i=0; ipos); + lua_replace(L, json_export_value_idx); + if (lua_isnil(L, json_export_value_idx)) { + luaL_addchar(&buf, ']'); + goto json_export_close; + } + break; + json_export_close: + if (--level) { + lua_rawgeti(L, json_export_stackswap_idx, stackswapidx--); + lua_replace(L, json_export_ccontainer_idx); + container = lua_touserdata(L, json_export_ccontainer_idx); + lua_rawgeti(L, json_export_stackswap_idx, stackswapidx--); + lua_replace(L, json_export_luacontainer_idx); + } else { + // for pretty results, add final newline character if outermost container is processed: + if (pretty) luaL_addchar(&buf, '\n'); + luaL_pushresult(&buf); + return 1; } } - // add closing bracket to output buffer: - luaL_addchar(&buf, '}'); - // for pretty results, add final newline character if outermost container is processed: - if (pretty && level == 0) luaL_addchar(&buf, '\n'); - // convert and return buffer: - luaL_pushresult(&buf); - return 1; - // JSON array: - case JSON_TABLETYPE_ARRAY: - // reserve an extra element on the stack (needed because Lua buffer has unknown size on stack): - lua_settop(L, json_export_internal_tmp_idx); - // create Lua string buffer: - luaL_buffinit(L, &buf); - // add opening bracket to output buffer: - luaL_addchar(&buf, '['); - // iterate through integer keys: - for (arrayidx = 1; ; arrayidx++) { - // get value in array, and break if nil: - lua_rawgeti(L, json_export_internal_value_idx, arrayidx); - if (lua_isnil(L, -1)) { - lua_pop(L, 1); - break; - } - // store value below Lua string buffer on stack (to allow operation on string buffer): - lua_replace(L, json_export_internal_tmp_idx); - // - // add comma to output buffer unless we process the first element: - if (anyelement) luaL_addchar(&buf, ','); - // remember that we processed an element: - anyelement = 1; + /* + if (containerkey || container->type == JSON_TABLETYPE_ARRAY) { + // add comma where necessary: + if (container->pos > 1) luaL_addchar(&buf, ','); // handle indentation for pretty results: if (pretty) { - luaL_addchar(&buf, '\n'); - for (i=0; i