# HG changeset patch
# User jbe
# Date 1406426079 -7200
# Node ID bccaa05aada7e40577d5fb02ffacb37881fe74b5
# Parent  e3e5bf890aad5ff7389e6915a5f70fb438dbd524
Implemented efficient length operator for sparse JSON arrays (that may contain null values)

diff -r e3e5bf890aad -r bccaa05aada7 libraries/json/json.c
--- a/libraries/json/json.c	Sun Jul 27 01:51:45 2014 +0200
+++ b/libraries/json/json.c	Sun Jul 27 03:54:39 2014 +0200
@@ -3,9 +3,8 @@
 #include <stdlib.h>
 #include <string.h>
 
-#define JSON_UPVAL_METATABLE lua_upvalueindex(1)
-#define JSON_UPVAL_NULLS lua_upvalueindex(2)
-#define JSON_UPVAL_ARYLEN lua_upvalueindex(3)
+#define JSON_UPVAL_NULLS lua_upvalueindex(1)
+#define JSON_UPVAL_METATABLE lua_upvalueindex(2)
 
 #define JSON_STATE_VALUE 0
 #define JSON_STATE_OBJECT_KEY 1
@@ -76,10 +75,7 @@
   case ']':
     if (mode != JSON_STATE_ARRAY_VALUE && mode != JSON_STATE_ARRAY_SEPARATOR)
       goto json_import_syntax_error;
-    lua_pushvalue(L, -2);  // use array table as key
-    lua_insert(L, -2);  // use length of array as value
-    lua_rawset(L, JSON_UPVAL_ARYLEN);  // store length in ephemeron table
-    // leaves array table on top of stack
+    lua_pop(L, 1);  // pop length information
   json_import_close:
     pos++;
     lua_pop(L, 1);  // pop table that stores set of NULL values
@@ -220,12 +216,53 @@
 }
 
 static int json_arylen(lua_State *L) {
+  int lower, middle;
+  int upper = 1;
+  // TODO: check input for valid array!
   lua_settop(L, 1);
-  lua_rawget(L, JSON_UPVAL_ARYLEN);
+  lua_pushvalue(L, 1);
+  lua_rawget(L, JSON_UPVAL_NULLS);
+  if (lua_isnil(L, -1)) goto json_arylen_default;
+  lua_pushnil(L);
+  if (!lua_next(L, -2)) goto json_arylen_default;
+  lua_pop(L, 2);
+  while (1) {
+    lua_rawgeti(L, 1, upper);
+    if (lua_isnil(L, -1)) {
+      // TODO: require metatable set?
+      lua_pop(L, 1);
+      lua_pushinteger(L, upper);
+      lua_rawget(L, 2);
+    }
+    if (lua_isnil(L, -1)) break;
+    lua_pop(L, 1);
+    upper *= 2;
+    // TODO: avoid integer overflow!
+  }
+  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)) {
+      // TODO: require metatable set?
+      lua_pop(L, 1);
+      lua_pushinteger(L, middle);
+      lua_rawget(L, 2);
+    }
+    if (lua_isnil(L, -1)) upper = middle;
+    else lower = middle;
+    lua_pop(L, 1);
+  }
+  lua_pushinteger(L, lower);
+  return 1;
+json_arylen_default:
+  lua_pushinteger(L, lua_rawlen(L, 1));
   return 1;
 }
 
 static int json_isnull(lua_State *L) {
+  // TODO: require metatable set?
   lua_pushvalue(L, 1);
   lua_rawget(L, JSON_UPVAL_NULLS);
   if (lua_isnil(L, -1)) goto json_isnull_false;
@@ -244,20 +281,26 @@
   {NULL, NULL}
 };
 
+static const struct luaL_Reg json_metatable_functions[] = {
+  {"__len", json_arylen},
+  {NULL, NULL}
+};
+
 int luaopen_json(lua_State *L) {
-  lua_newtable(L);  // library table
-  lua_newtable(L);  // metatable for JSON objects and JSON arrays
-  lua_pushvalue(L, -1);
-  lua_setfield(L, -3, "metatable");
-  lua_newtable(L);  // ephemeron table to store a set of keys associated with JSON-null values
-  lua_newtable(L);  // ephemeron table to store the length of arrays (that may contain nil's)
-  lua_newtable(L);  // meta table for ephemeron table
+  lua_settop(L, 0);
+  lua_newtable(L);  // 1: library table on stack position
+  lua_newtable(L);  // 2: ephemeron table to store a set of keys associated with JSON-null values
+  lua_newtable(L);  // 3: meta table for ephemeron table
   lua_pushliteral(L, "__mode");
   lua_pushliteral(L, "k");
-  lua_rawset(L, -3);
-  lua_pushvalue(L, -1);
-  lua_setmetatable(L, -3);
-  lua_setmetatable(L, -2);
-  luaL_setfuncs(L, json_module_functions, 3);
+  lua_rawset(L, 3);
+  lua_setmetatable(L, 2);
+  lua_newtable(L);  // 3: metatable for JSON objects and JSON arrays
+  lua_pushvalue(L, 3);
+  lua_setfield(L, 1, "metatable");
+  lua_pushvalue(L, 2);
+  lua_pushvalue(L, 3);
+  luaL_setfuncs(L, json_metatable_functions, 2);
+  luaL_setfuncs(L, json_module_functions, 2);
   return 1;
 }