Encode very sparse arrays as objects

Detect and encode very sparse arrays as objects. This prevents something
like:
	{ [1000000] = "nullfest" }
..from generating a huge array.

1 files changed, 14 insertions, 1 deletions

diff --git a/lua_cjson.c b/lua_cjson.c
index 203b3b8..b87aebf 100644
--- a/lua_cjson.c
+++ b/lua_cjson.c
@@ -22,7 +22,6 @@
  * - Option to encode non-printable characters? Only \" \\ are required
  * - Protect against cycles when encoding JSON from a data structure
  *   - Max depth? Notice cycles?
- * - Handle huge sparse arrays?
  */
 
 #include <assert.h>
@@ -36,6 +35,11 @@
 
 #include "strbuf.h"
 
+/* Encode very sparse arrays as objects */
+#ifndef VERY_SPARSE_ARRAY_RATIO
+#define VERY_SPARSE_ARRAY_RATIO 2
+#endif
+
 /* ===== ENCODING ===== */
 
 static void json_encode_exception(lua_State *l, strbuf_t *json,
@@ -113,8 +117,10 @@ static int lua_array_length(lua_State *l)
 {
     double k;
     int max;
+    int items;
 
     max = 0;
+    items = 0;
 
     lua_pushnil(l);
     /* table, startkey */
@@ -126,6 +132,7 @@ static int lua_array_length(lua_State *l)
             if (floor(k) == k && k >= 1) {
                 if (k > max)
                     max = k;
+                items++;
                 lua_pop(l, 1);
                 continue;
             }
@@ -136,6 +143,12 @@ static int lua_array_length(lua_State *l)
         return -1;
     }
 
+#ifdef VERY_SPARSE_ARRAY_RATIO
+    /* Encode very sparse arrays as objects */
+    if (max > items * VERY_SPARSE_ARRAY_RATIO)
+        return -1;
+#endif
+
     return max;
 }