webmcp

annotate libraries/json/json.c @ 126:bccaa05aada7

find changesets by author, revision, files, or words in the commit message
Implemented efficient length operator for sparse JSON arrays (that may contain null values)
author jbe
date Sun Jul 27 03:54:39 2014 +0200 (2014-07-27)
parents e3e5bf890aad
children 83aced09adc7
rev   line source
jbe@121 1 #include <lua.h>
jbe@121 2 #include <lauxlib.h>
jbe@122 3 #include <stdlib.h>
jbe@121 4 #include <string.h>
jbe@121 5
jbe@126 6 #define JSON_UPVAL_NULLS lua_upvalueindex(1)
jbe@126 7 #define JSON_UPVAL_METATABLE lua_upvalueindex(2)
jbe@123 8
jbe@124 9 #define JSON_STATE_VALUE 0
jbe@124 10 #define JSON_STATE_OBJECT_KEY 1
jbe@124 11 #define JSON_STATE_OBJECT_KEY_TERMINATOR 2
jbe@124 12 #define JSON_STATE_OBJECT_VALUE 3
jbe@124 13 #define JSON_STATE_OBJECT_SEPARATOR 4
jbe@124 14 #define JSON_STATE_ARRAY_VALUE 5
jbe@124 15 #define JSON_STATE_ARRAY_SEPARATOR 6
jbe@124 16 #define JSON_STATE_END 7
jbe@121 17
jbe@121 18 static int json_import(lua_State *L) {
jbe@121 19 const char *str;
jbe@121 20 size_t total;
jbe@121 21 size_t pos = 0;
jbe@121 22 size_t level = 0;
jbe@124 23 int mode = JSON_STATE_VALUE;
jbe@121 24 char c;
jbe@121 25 luaL_Buffer luabuf;
jbe@121 26 char *cbuf;
jbe@121 27 size_t writepos;
jbe@121 28 int aryidx;
jbe@121 29 lua_settop(L, 1);
jbe@121 30 str = lua_tostring(L, 1);
jbe@121 31 total = strlen(str);
jbe@121 32 json_import_loop:
jbe@121 33 while (c = str[pos], c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == '\f') pos++;
jbe@121 34 switch (c) {
jbe@121 35 case 0:
jbe@124 36 if (mode == JSON_STATE_END) return 1;
jbe@121 37 json_import_unexpected_eof:
jbe@121 38 lua_pushnil(L);
jbe@121 39 if (level == 0) lua_pushliteral(L, "Empty string");
jbe@121 40 else lua_pushliteral(L, "Unexpected end of JSON document");
jbe@121 41 return 2;
jbe@121 42 case '{':
jbe@124 43 if (mode != JSON_STATE_VALUE && mode != JSON_STATE_OBJECT_VALUE && mode != JSON_STATE_ARRAY_VALUE)
jbe@121 44 goto json_import_syntax_error;
jbe@121 45 pos++;
jbe@125 46 lua_newtable(L); // the actual JSON object
jbe@125 47 lua_pushvalue(L, JSON_UPVAL_METATABLE);
jbe@125 48 lua_setmetatable(L, -2);
jbe@123 49 lua_newtable(L); // stores set of NULL values
jbe@123 50 lua_pushvalue(L, -2);
jbe@123 51 lua_pushvalue(L, -2);
jbe@123 52 lua_rawset(L, JSON_UPVAL_NULLS);
jbe@124 53 mode = JSON_STATE_OBJECT_KEY;
jbe@121 54 level++;
jbe@121 55 goto json_import_loop;
jbe@121 56 case '[':
jbe@124 57 if (mode != JSON_STATE_VALUE && mode != JSON_STATE_OBJECT_VALUE && mode != JSON_STATE_ARRAY_VALUE)
jbe@121 58 goto json_import_syntax_error;
jbe@121 59 pos++;
jbe@125 60 lua_newtable(L); // the actual JSON array
jbe@125 61 lua_pushvalue(L, JSON_UPVAL_METATABLE);
jbe@125 62 lua_setmetatable(L, -2);
jbe@123 63 lua_newtable(L); // stores set of NULL values
jbe@123 64 lua_pushvalue(L, -2);
jbe@123 65 lua_pushvalue(L, -2);
jbe@123 66 lua_rawset(L, JSON_UPVAL_NULLS);
jbe@121 67 lua_pushinteger(L, 0); // length of array (since it may contain nil's)
jbe@124 68 mode = JSON_STATE_ARRAY_VALUE;
jbe@121 69 level++;
jbe@121 70 goto json_import_loop;
jbe@121 71 case '}':
jbe@124 72 if (mode != JSON_STATE_OBJECT_KEY && mode != JSON_STATE_OBJECT_SEPARATOR)
jbe@121 73 goto json_import_syntax_error;
jbe@121 74 goto json_import_close;
jbe@121 75 case ']':
jbe@124 76 if (mode != JSON_STATE_ARRAY_VALUE && mode != JSON_STATE_ARRAY_SEPARATOR)
jbe@121 77 goto json_import_syntax_error;
jbe@126 78 lua_pop(L, 1); // pop length information
jbe@121 79 json_import_close:
jbe@121 80 pos++;
jbe@123 81 lua_pop(L, 1); // pop table that stores set of NULL values
jbe@121 82 if (--level) {
jbe@121 83 if (lua_type(L, -2) == LUA_TNUMBER) {
jbe@124 84 mode = JSON_STATE_ARRAY_VALUE;
jbe@121 85 } else {
jbe@124 86 mode = JSON_STATE_OBJECT_VALUE;
jbe@121 87 }
jbe@121 88 goto json_import_process_value;
jbe@121 89 } else {
jbe@124 90 mode = JSON_STATE_END;
jbe@121 91 }
jbe@121 92 goto json_import_loop;
jbe@121 93 case ':':
jbe@124 94 if (mode != JSON_STATE_OBJECT_KEY_TERMINATOR)
jbe@121 95 goto json_import_syntax_error;
jbe@121 96 pos++;
jbe@124 97 mode = JSON_STATE_OBJECT_VALUE;
jbe@121 98 goto json_import_loop;
jbe@121 99 case ',':
jbe@124 100 if (mode == JSON_STATE_OBJECT_SEPARATOR) {
jbe@124 101 mode = JSON_STATE_OBJECT_KEY;
jbe@124 102 } else if (mode == JSON_STATE_ARRAY_SEPARATOR) {
jbe@124 103 mode = JSON_STATE_ARRAY_VALUE;
jbe@121 104 } else {
jbe@121 105 goto json_import_syntax_error;
jbe@121 106 }
jbe@121 107 pos++;
jbe@121 108 goto json_import_loop;
jbe@121 109 case '"':
jbe@121 110 cbuf = luaL_buffinitsize(L, &luabuf, total-pos);
jbe@121 111 writepos = 0;
jbe@121 112 pos++;
jbe@121 113 while ((c = str[pos++]) != '"') {
jbe@121 114 if (c == 0) {
jbe@121 115 goto json_import_unexpected_eof;
jbe@121 116 } else if (c < 32 || c == 127) {
jbe@121 117 lua_pushnil(L);
jbe@121 118 lua_pushliteral(L, "Unexpected control character in JSON string");
jbe@121 119 return 2;
jbe@121 120 } else if (c == '\\') {
jbe@121 121 c = str[pos++];
jbe@121 122 switch (c) {
jbe@121 123 case 0:
jbe@121 124 goto json_import_unexpected_eof;
jbe@121 125 case '"':
jbe@121 126 case '/':
jbe@121 127 case '\\':
jbe@121 128 cbuf[writepos++] = c;
jbe@121 129 break;
jbe@121 130 case 'b':
jbe@121 131 cbuf[writepos++] = '\b';
jbe@121 132 break;
jbe@121 133 case 'f':
jbe@121 134 cbuf[writepos++] = '\f';
jbe@121 135 break;
jbe@121 136 case 'n':
jbe@121 137 cbuf[writepos++] = '\n';
jbe@121 138 break;
jbe@121 139 case 'r':
jbe@121 140 cbuf[writepos++] = '\r';
jbe@121 141 break;
jbe@121 142 case 't':
jbe@121 143 cbuf[writepos++] = '\t';
jbe@121 144 break;
jbe@121 145 case 'u':
jbe@121 146 lua_pushnil(L);
jbe@121 147 lua_pushliteral(L, "JSON unicode escape sequences are not implemented yet"); // TODO
jbe@121 148 return 2;
jbe@121 149 default:
jbe@121 150 lua_pushnil(L);
jbe@121 151 lua_pushliteral(L, "Unexpected string escape sequence in JSON document");
jbe@121 152 return 2;
jbe@121 153 }
jbe@121 154 } else {
jbe@121 155 cbuf[writepos++] = c;
jbe@121 156 }
jbe@121 157 }
jbe@121 158 if (!c) goto json_import_unexpected_eof;
jbe@121 159 luaL_pushresultsize(&luabuf, writepos);
jbe@121 160 goto json_import_process_value;
jbe@121 161 }
jbe@122 162 if (c == '-' || (c >= '0' && c <= '9')) {
jbe@122 163 char *endptr;
jbe@122 164 double numval;
jbe@122 165 numval = strtod(str+pos, &endptr);
jbe@122 166 if (endptr == str+pos) goto json_import_syntax_error;
jbe@122 167 pos += endptr - (str+pos);
jbe@122 168 lua_pushnumber(L, numval);
jbe@122 169 } else if (!strncmp(str+pos, "true", 4)) {
jbe@121 170 lua_pushboolean(L, 1);
jbe@121 171 pos += 4;
jbe@121 172 } else if (!strncmp(str+pos, "false", 5)) {
jbe@121 173 lua_pushboolean(L, 0);
jbe@121 174 pos += 5;
jbe@121 175 } else if (!strncmp(str+pos, "null", 4)) {
jbe@121 176 lua_pushnil(L);
jbe@121 177 pos += 4;
jbe@121 178 } else {
jbe@121 179 goto json_import_syntax_error;
jbe@121 180 }
jbe@121 181 json_import_process_value:
jbe@121 182 switch (mode) {
jbe@124 183 case JSON_STATE_OBJECT_KEY:
jbe@121 184 if (lua_type(L, -1) != LUA_TSTRING) goto json_import_syntax_error;
jbe@124 185 mode = JSON_STATE_OBJECT_KEY_TERMINATOR;
jbe@121 186 goto json_import_loop;
jbe@124 187 case JSON_STATE_OBJECT_VALUE:
jbe@123 188 if (lua_isnil(L, -1)) {
jbe@123 189 lua_pushvalue(L, -2);
jbe@123 190 lua_pushboolean(L, 1);
jbe@123 191 lua_rawset(L, -5);
jbe@123 192 }
jbe@123 193 lua_rawset(L, -4);
jbe@124 194 mode = JSON_STATE_OBJECT_SEPARATOR;
jbe@121 195 goto json_import_loop;
jbe@124 196 case JSON_STATE_ARRAY_VALUE:
jbe@121 197 aryidx = lua_tointeger(L, -2) + 1;
jbe@123 198 if (lua_isnil(L, -1)) {
jbe@123 199 lua_pushinteger(L, aryidx);
jbe@123 200 lua_pushboolean(L, 1);
jbe@123 201 lua_rawset(L, -5);
jbe@123 202 }
jbe@123 203 lua_rawseti(L, -4, aryidx);
jbe@121 204 lua_pop(L, 1);
jbe@121 205 lua_pushinteger(L, aryidx);
jbe@124 206 mode = JSON_STATE_ARRAY_SEPARATOR;
jbe@121 207 goto json_import_loop;
jbe@124 208 case JSON_STATE_VALUE:
jbe@124 209 mode = JSON_STATE_END;
jbe@121 210 goto json_import_loop;
jbe@121 211 }
jbe@121 212 json_import_syntax_error:
jbe@121 213 lua_pushnil(L);
jbe@121 214 lua_pushliteral(L, "Syntax error in JSON document");
jbe@121 215 return 2;
jbe@121 216 }
jbe@121 217
jbe@121 218 static int json_arylen(lua_State *L) {
jbe@126 219 int lower, middle;
jbe@126 220 int upper = 1;
jbe@126 221 // TODO: check input for valid array!
jbe@121 222 lua_settop(L, 1);
jbe@126 223 lua_pushvalue(L, 1);
jbe@126 224 lua_rawget(L, JSON_UPVAL_NULLS);
jbe@126 225 if (lua_isnil(L, -1)) goto json_arylen_default;
jbe@126 226 lua_pushnil(L);
jbe@126 227 if (!lua_next(L, -2)) goto json_arylen_default;
jbe@126 228 lua_pop(L, 2);
jbe@126 229 while (1) {
jbe@126 230 lua_rawgeti(L, 1, upper);
jbe@126 231 if (lua_isnil(L, -1)) {
jbe@126 232 // TODO: require metatable set?
jbe@126 233 lua_pop(L, 1);
jbe@126 234 lua_pushinteger(L, upper);
jbe@126 235 lua_rawget(L, 2);
jbe@126 236 }
jbe@126 237 if (lua_isnil(L, -1)) break;
jbe@126 238 lua_pop(L, 1);
jbe@126 239 upper *= 2;
jbe@126 240 // TODO: avoid integer overflow!
jbe@126 241 }
jbe@126 242 lua_pop(L, 1);
jbe@126 243 lower = upper / 2;
jbe@126 244 while (upper - lower > 1) {
jbe@126 245 middle = (lower + upper) / 2;
jbe@126 246 lua_rawgeti(L, 1, middle);
jbe@126 247 if (lua_isnil(L, -1)) {
jbe@126 248 // TODO: require metatable set?
jbe@126 249 lua_pop(L, 1);
jbe@126 250 lua_pushinteger(L, middle);
jbe@126 251 lua_rawget(L, 2);
jbe@126 252 }
jbe@126 253 if (lua_isnil(L, -1)) upper = middle;
jbe@126 254 else lower = middle;
jbe@126 255 lua_pop(L, 1);
jbe@126 256 }
jbe@126 257 lua_pushinteger(L, lower);
jbe@126 258 return 1;
jbe@126 259 json_arylen_default:
jbe@126 260 lua_pushinteger(L, lua_rawlen(L, 1));
jbe@123 261 return 1;
jbe@123 262 }
jbe@123 263
jbe@123 264 static int json_isnull(lua_State *L) {
jbe@126 265 // TODO: require metatable set?
jbe@123 266 lua_pushvalue(L, 1);
jbe@123 267 lua_rawget(L, JSON_UPVAL_NULLS);
jbe@123 268 if (lua_isnil(L, -1)) goto json_isnull_false;
jbe@123 269 lua_pushvalue(L, 2);
jbe@123 270 lua_rawget(L, -2);
jbe@123 271 if (!lua_isnil(L, -1)) return 1;
jbe@123 272 json_isnull_false:
jbe@123 273 lua_pushboolean(L, 0);
jbe@121 274 return 1;
jbe@121 275 }
jbe@121 276
jbe@121 277 static const struct luaL_Reg json_module_functions[] = {
jbe@121 278 {"import", json_import},
jbe@121 279 {"arylen", json_arylen},
jbe@123 280 {"isnull", json_isnull},
jbe@121 281 {NULL, NULL}
jbe@121 282 };
jbe@121 283
jbe@126 284 static const struct luaL_Reg json_metatable_functions[] = {
jbe@126 285 {"__len", json_arylen},
jbe@126 286 {NULL, NULL}
jbe@126 287 };
jbe@126 288
jbe@121 289 int luaopen_json(lua_State *L) {
jbe@126 290 lua_settop(L, 0);
jbe@126 291 lua_newtable(L); // 1: library table on stack position
jbe@126 292 lua_newtable(L); // 2: ephemeron table to store a set of keys associated with JSON-null values
jbe@126 293 lua_newtable(L); // 3: meta table for ephemeron table
jbe@121 294 lua_pushliteral(L, "__mode");
jbe@121 295 lua_pushliteral(L, "k");
jbe@126 296 lua_rawset(L, 3);
jbe@126 297 lua_setmetatable(L, 2);
jbe@126 298 lua_newtable(L); // 3: metatable for JSON objects and JSON arrays
jbe@126 299 lua_pushvalue(L, 3);
jbe@126 300 lua_setfield(L, 1, "metatable");
jbe@126 301 lua_pushvalue(L, 2);
jbe@126 302 lua_pushvalue(L, 3);
jbe@126 303 luaL_setfuncs(L, json_metatable_functions, 2);
jbe@126 304 luaL_setfuncs(L, json_module_functions, 2);
jbe@121 305 return 1;
jbe@121 306 }

Impressum / About Us