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