# HG changeset patch
# User jbe
# Date 1406489126 -7200
# Node ID 209f8ce39c5a78f72a1837e7f98d8aca72549479
# Parent  453d8f8fbacec06593ee9002ecaac7727e48d7fd
Refactored JSON library to use shadow tables with null markers

diff -r 453d8f8fbace -r 209f8ce39c5a libraries/json/json.c
--- a/libraries/json/json.c	Sun Jul 27 15:03:21 2014 +0200
+++ b/libraries/json/json.c	Sun Jul 27 21:25:26 2014 +0200
@@ -3,9 +3,10 @@
 #include <stdlib.h>
 #include <string.h>
 
-#define JSON_UPVAL_TYPES lua_upvalueindex(1)
-#define JSON_UPVAL_NULLS lua_upvalueindex(2)
-#define JSON_UPVAL_METATABLE lua_upvalueindex(3)
+#define JSON_UPVAL_NULLMARK  lua_upvalueindex(1)
+#define JSON_UPVAL_SHADOWTBL lua_upvalueindex(2)
+#define JSON_UPVAL_TYPES     lua_upvalueindex(3)
+#define JSON_UPVAL_METATABLE lua_upvalueindex(4)
 
 #define JSON_STATE_VALUE 0
 #define JSON_STATE_OBJECT_KEY 1
@@ -26,7 +27,6 @@
   luaL_Buffer luabuf;
   char *cbuf;
   size_t writepos;
-  int aryidx;
   lua_settop(L, 1);
   str = lua_tostring(L, 1);
   total = strlen(str);
@@ -44,16 +44,16 @@
     if (mode != JSON_STATE_VALUE && mode != JSON_STATE_OBJECT_VALUE && mode != JSON_STATE_ARRAY_VALUE)
       goto json_import_syntax_error;
     pos++;
-    lua_newtable(L);  // the actual JSON object
+    lua_newtable(L);  // the external JSON object representation
     lua_pushvalue(L, JSON_UPVAL_METATABLE);
     lua_setmetatable(L, -2);
     lua_pushvalue(L, -1);
     lua_pushliteral(L, "object");
     lua_rawset(L, JSON_UPVAL_TYPES);
-    lua_newtable(L);  // stores set of NULL values
+    lua_newtable(L);  // the internal shadow table
     lua_pushvalue(L, -2);
     lua_pushvalue(L, -2);
-    lua_rawset(L, JSON_UPVAL_NULLS);
+    lua_rawset(L, JSON_UPVAL_SHADOWTBL);
     mode = JSON_STATE_OBJECT_KEY;
     level++;
     goto json_import_loop;
@@ -61,17 +61,17 @@
     if (mode != JSON_STATE_VALUE && mode != JSON_STATE_OBJECT_VALUE && mode != JSON_STATE_ARRAY_VALUE)
       goto json_import_syntax_error;
     pos++;
-    lua_newtable(L);  // the actual JSON array
+    lua_newtable(L);  // the external JSON array representation
     lua_pushvalue(L, JSON_UPVAL_METATABLE);
     lua_setmetatable(L, -2);
     lua_pushvalue(L, -1);
     lua_pushliteral(L, "array");
     lua_rawset(L, JSON_UPVAL_TYPES);
-    lua_newtable(L);  // stores set of NULL values
+    lua_newtable(L);  // the internal shadow table
     lua_pushvalue(L, -2);
     lua_pushvalue(L, -2);
-    lua_rawset(L, JSON_UPVAL_NULLS);
-    lua_pushinteger(L, 0);  // length of array (since it may contain nil's)
+    lua_rawset(L, JSON_UPVAL_SHADOWTBL);
+    lua_pushinteger(L, 0);  // magic integer to indicate an array
     mode = JSON_STATE_ARRAY_VALUE;
     level++;
     goto json_import_loop;
@@ -82,10 +82,10 @@
   case ']':
     if (mode != JSON_STATE_ARRAY_VALUE && mode != JSON_STATE_ARRAY_SEPARATOR)
       goto json_import_syntax_error;
-    lua_pop(L, 1);  // pop length information
+    lua_pop(L, 1);  // pop magic integer
   json_import_close:
     pos++;
-    lua_pop(L, 1);  // pop table that stores set of NULL values
+    lua_pop(L, 1);  // pop shadow table
     if (--level) {
       if (lua_type(L, -2) == LUA_TNUMBER) {
         mode = JSON_STATE_ARRAY_VALUE;
@@ -180,7 +180,7 @@
     lua_pushboolean(L, 0);
     pos += 5;
   } else if (!strncmp(str+pos, "null", 4)) {
-    lua_pushnil(L);
+    lua_pushvalue(L, JSON_UPVAL_NULLMARK);
     pos += 4;
   } else {
     goto json_import_syntax_error;
@@ -192,24 +192,11 @@
     mode = JSON_STATE_OBJECT_KEY_TERMINATOR;
     goto json_import_loop;
   case JSON_STATE_OBJECT_VALUE:
-    if (lua_isnil(L, -1)) {
-      lua_pushvalue(L, -2);
-      lua_pushboolean(L, 1);
-      lua_rawset(L, -5);
-    }
-    lua_rawset(L, -4);
+    lua_rawset(L, -3);
     mode = JSON_STATE_OBJECT_SEPARATOR;
     goto json_import_loop;
   case JSON_STATE_ARRAY_VALUE:
-    aryidx = lua_tointeger(L, -2) + 1;
-    if (lua_isnil(L, -1)) {
-      lua_pushinteger(L, aryidx);
-      lua_pushboolean(L, 1);
-      lua_rawset(L, -5);
-    }
-    lua_rawseti(L, -4, aryidx);
-    lua_pop(L, 1);
-    lua_pushinteger(L, aryidx);
+    lua_rawseti(L, -3, lua_rawlen(L, -3) + 1);
     mode = JSON_STATE_ARRAY_SEPARATOR;
     goto json_import_loop;
   case JSON_STATE_VALUE:
@@ -222,119 +209,135 @@
   return 2;
 }
 
-static int json_arylen(lua_State *L) {
-  int lower, middle;
-  int upper = 1;
-  lua_settop(L, 1);
+#define JSON_PATH_GET 1
+#define JSON_PATH_TYPE 2
+#define JSON_PATH_ISNULL 3
+
+static int json_path(lua_State *L, int mode) {
+  int argc;
+  int idx = 2;
+  argc = lua_gettop(L);
   lua_pushvalue(L, 1);
-  lua_rawget(L, JSON_UPVAL_NULLS);
-  if (lua_isnil(L, 2)) goto json_arylen_default;
-  lua_pushnil(L);
-  if (!lua_next(L, 2)) goto json_arylen_default;
-  lua_settop(L, 2);
-  while (1) {
-    lua_rawgeti(L, 1, upper);
+  while (idx <= argc) {
+    lua_pushvalue(L, -1);
+    lua_rawget(L, JSON_UPVAL_SHADOWTBL);
     if (lua_isnil(L, -1)) {
       lua_pop(L, 1);
-      lua_pushinteger(L, upper);
-      lua_rawget(L, 2);
+      if (lua_type(L, -1) == LUA_TTABLE) {
+        lua_pushvalue(L, idx++);
+        lua_gettable(L, -2);
+      } else {
+        lua_pushnil(L);
+      }
+    } else {
+      lua_replace(L, -2);
+      lua_pushvalue(L, idx++);
+      lua_rawget(L, -2);
     }
-    if (lua_isnil(L, -1)) break;
-    lua_pop(L, 1);
-    upper *= 2;
-    // TODO: avoid integer overflow!
+    if (lua_isnil(L, -1)) {
+      if (mode == JSON_PATH_ISNULL) lua_pushboolean(L, 0);
+      return 1;
+    }
+    lua_replace(L, -2);
   }
-  lua_pop(L, 1);
-  lower = upper / 2;
-  while (upper - lower > 1) {
-    middle = (lower + upper) / 2;
-    lua_rawgeti(L, 1, middle);
-    if (lua_isnil(L, -1)) {
-      lua_pop(L, 1);
-      lua_pushinteger(L, middle);
-      lua_rawget(L, 2);
+  switch (mode) {
+  case JSON_PATH_GET:
+    if (lua_rawequal(L, -1, JSON_UPVAL_NULLMARK)) lua_pushnil(L);
+    return 1;
+  case JSON_PATH_TYPE:
+    if (lua_rawequal(L, -1, JSON_UPVAL_NULLMARK)) {
+      lua_pushliteral(L, "null");
+      return 1;
     }
-    if (lua_isnil(L, -1)) upper = middle;
-    else lower = middle;
-    lua_pop(L, 1);
+    lua_pushvalue(L, -1);
+    lua_rawget(L, JSON_UPVAL_TYPES);
+    if (lua_isnil(L, -1)) lua_pushstring(L, lua_typename(L, lua_type(L, -2)));
+    return 1;
+  case JSON_PATH_ISNULL:
+    lua_pushboolean(L, lua_rawequal(L, -1, JSON_UPVAL_NULLMARK));
+    return 1;
   }
-  lua_pushinteger(L, lower);
-  return 1;
-json_arylen_default:
-  lua_pushinteger(L, lua_rawlen(L, 1));
+  return 0;
+}
+
+static int json_get(lua_State *L) {
+  return json_path(L, JSON_PATH_GET);
+}
+
+static int json_type(lua_State *L) {
+  return json_path(L, JSON_PATH_TYPE);
+}
+
+static int json_isnull(lua_State *L) {
+  return json_path(L, JSON_PATH_ISNULL);
+}
+
+static int json_len(lua_State *L) {
+  lua_settop(L, 1);
+  lua_pushvalue(L, 1);
+  lua_rawget(L, JSON_UPVAL_SHADOWTBL);
+  if (lua_isnil(L, -1)) lua_pop(L, 1);
+  lua_pushinteger(L, lua_rawlen(L, -1));
   return 1;
 }
 
-static int json_type(lua_State *L) {
-  if (lua_gettop(L) >= 2) {
-    lua_pushvalue(L, 1);
-    lua_rawget(L, JSON_UPVAL_NULLS);
-    lua_pushvalue(L, 2);
-    lua_rawget(L, -2);
-    if (lua_toboolean(L, -1)) {
-      lua_getmetatable(L, 1);
-      if (lua_rawequal(L, -1, JSON_UPVAL_METATABLE)) {
-        lua_pushliteral(L, "null");
-        return 1;
-      }
-    }
-    lua_settop(L, 2);
-    lua_rawget(L, 1);
-  } else {
-    lua_settop(L, 1);
-  }
-  lua_pushvalue(L, -1);
-  lua_rawget(L, JSON_UPVAL_TYPES);
-  if (lua_isnil(L, -1)) lua_pushstring(L, lua_typename(L, lua_type(L, -2)));
+static int json_index(lua_State *L) {
+  lua_settop(L, 2);
+  lua_pushvalue(L, 1);
+  lua_rawget(L, JSON_UPVAL_SHADOWTBL);
+  if (lua_isnil(L, -1)) return 1;
+  lua_pushvalue(L, 2);
+  lua_rawget(L, -2);
+  if (lua_rawequal(L, -1, JSON_UPVAL_NULLMARK)) lua_pushnil(L);
   return 1;
 }
 
-static int json_isnull(lua_State *L) {
-  lua_settop(L, 2);
-  lua_getmetatable(L, 1);
-  if (!lua_rawequal(L, -1, JSON_UPVAL_METATABLE)) goto json_isnull_false;
+static int json_newindex(lua_State *L) {
+  lua_settop(L, 3);
   lua_pushvalue(L, 1);
-  lua_rawget(L, JSON_UPVAL_NULLS);
-  if (lua_isnil(L, -1)) goto json_isnull_false;
-  lua_pushvalue(L, 2);
-  lua_rawget(L, -2);
-  if (!lua_isnil(L, -1)) return 1;
-json_isnull_false:
-  lua_pushboolean(L, 0);
+  lua_rawget(L, JSON_UPVAL_SHADOWTBL);
+  if (lua_isnil(L, -1)) return luaL_error(L, "Shadow table not found");
+  lua_replace(L, 1);
+  lua_rawset(L, 1);
   return 1;
 }
 
 static const struct luaL_Reg json_module_functions[] = {
   {"import", json_import},
+  {"get", json_get},
   {"type", json_type},
   {"isnull", json_isnull},
   {NULL, NULL}
 };
 
 static const struct luaL_Reg json_metatable_functions[] = {
-  {"__len", json_arylen},
+  {"__len", json_len},
+  {"__index", json_index},
+  {"__newindex", json_newindex},
   {NULL, NULL}
 };
 
 int luaopen_json(lua_State *L) {
   lua_settop(L, 0);
   lua_newtable(L);  // 1: library table on stack position
-  lua_newtable(L);  // 2: ephemeron table to store the type of the JSON object/array
-  lua_newtable(L);  // 3: ephemeron table to store a set of keys associated with JSON-null values
-  lua_newtable(L);  // 4: metatable for ephemeron tables
+  lua_newtable(L);  // 2: table used as JSON NULL value in internal shadow tables
+  lua_newtable(L);  // 3: ephemeron table to store shadow tables for each JSON object/array to allow NULL values returned as nil
+  lua_newtable(L);  // 4: ephemeron table to store the type of the JSON object/array
+  lua_newtable(L);  // 5: metatable for ephemeron tables
   lua_pushliteral(L, "__mode");
   lua_pushliteral(L, "k");
-  lua_rawset(L, 4);
-  lua_pushvalue(L, 4);  // 5: cloned metatable reference
-  lua_setmetatable(L, 2);
+  lua_rawset(L, 5);
+  lua_pushvalue(L, 5);  // 6: cloned metatable reference
   lua_setmetatable(L, 3);
-  lua_newtable(L);  // 4: metatable for JSON objects and JSON arrays
-  lua_pushvalue(L, 4);
+  lua_setmetatable(L, 4);
+  lua_newtable(L);  // 5: metatable for JSON objects and JSON arrays
+  lua_pushvalue(L, 5);
   lua_setfield(L, 1, "metatable");
   lua_pushvalue(L, 2);
   lua_pushvalue(L, 3);
   lua_pushvalue(L, 4);
-  luaL_setfuncs(L, json_metatable_functions, 3);
-  luaL_setfuncs(L, json_module_functions, 3);
+  lua_pushvalue(L, 5);
+  luaL_setfuncs(L, json_metatable_functions, 4);
+  luaL_setfuncs(L, json_module_functions, 4);
   return 1;
 }