Enhance handling of circular references

It's now an error to try to add an object or array to itself. The
encoder checks for circular references and fails with an error status
if one is detected.

diff --git a/doc/apiref.rst b/doc/apiref.rst
index d6904eb..818ec51 100644 (file)
--- a/doc/apiref.rst
+++ b/doc/apiref.rst
@@ -159,6 +159,37 @@ will return a new or borrowed reference or steal a reference to its
 argument.
 
 
+Circular References
+-------------------
+
+A circular reference is created when an object or an array is,
+directly or indirectly, inserted inside itself. The direct case is
+simple::
+
+  json_t *obj = json_object();
+  json_object_set(obj, "foo", obj);
+
+Jansson will refuse to do this, and :cfunc:`json_object_set()` (and
+all the other such functions for objects and arrays) will return with
+an error status. The indirect case is the dangerous one::
+
+  json_t *arr1 = json_array(), *arr2 = json_array();
+  json_array_append(arr1, arr2);
+  json_array_append(arr2, arr1);
+
+In this example, the array ``arr2`` is contained in the array
+``arr1``, and vice versa. Jansson cannot check for this kind of
+indirect circular references without a performance hit, so it's up to
+the user to avoid them.
+
+If a circular reference is created, the memory consumed by the values
+cannot be freed by :cfunc:`json_decref()`. The reference counts never
+drops to zero because the values are keeping the circular reference to
+themselves. Moreover, trying to encode the values with any of the
+encoding functions will fail. The encoder detects circular references
+and returns an error status.
+
+
 True, False and Null
 ====================
 

diff --git a/src/dump.c b/src/dump.c
index 1ab1140..57de80c 100644 (file)
--- a/src/dump.c
+++ b/src/dump.c
@@ -11,6 +11,7 @@
 #include <string.h>
 
 #include <jansson.h>
+#include "jansson_private.h"
 #include "strbuffer.h"
 
 #define MAX_INTEGER_STR_LENGTH  100
@@ -157,7 +158,16 @@ static int do_dump(const json_t *json, unsigned long flags, int depth,
         case JSON_ARRAY:
         {
             int i;
-            int n = json_array_size(json);
+            int n;
+            json_array_t *array;
+
+            /* detect circular references */
+            array = json_to_array(json);
+            if(array->visited)
+                return -1;
+            array->visited = 1;
+
+            n = json_array_size(json);
 
             if(dump("[", 1, data))
                 return -1;
@@ -183,12 +193,23 @@ static int do_dump(const json_t *json, unsigned long flags, int depth,
                         return -1;
                 }
             }
+
+            array->visited = 0;
             return dump("]", 1, data);
         }
 
         case JSON_OBJECT:
         {
-            void *iter = json_object_iter((json_t *)json);
+            json_object_t *object;
+            void *iter;
+
+            /* detect circular references */
+            object = json_to_object(json);
+            if(object->visited)
+                return -1;
+            object->visited = 1;
+
+            iter = json_object_iter((json_t *)json);
 
             if(dump("{", 1, data))
                 return -1;
@@ -221,6 +242,8 @@ static int do_dump(const json_t *json, unsigned long flags, int depth,
 
                 iter = next;
             }
+
+            object->visited = 0;
             return dump("}", 1, data);
         }
 

diff --git a/src/jansson_private.h b/src/jansson_private.h
index ad8419a..317f05a 100644 (file)
--- a/src/jansson_private.h
+++ b/src/jansson_private.h
@@ -8,8 +8,48 @@
 #ifndef JANSSON_PRIVATE_H
 #define JANSSON_PRIVATE_H
 
+#include "jansson.h"
+#include "hashtable.h"
+
+#define container_of(ptr_, type_, member_)  \
+    ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
+
+typedef struct {
+    json_t json;
+    hashtable_t hashtable;
+    int visited;
+} json_object_t;
+
+typedef struct {
+    json_t json;
+    unsigned int size;
+    unsigned int entries;
+    json_t **table;
+    int visited;
+} json_array_t;
+
+typedef struct {
+    json_t json;
+    char *value;
+} json_string_t;
+
+typedef struct {
+    json_t json;
+    double value;
+} json_real_t;
+
+typedef struct {
+    json_t json;
+    int value;
+} json_integer_t;
+
+#define json_to_object(json_)  container_of(json_, json_object_t, json)
+#define json_to_array(json_)   container_of(json_, json_array_t, json)
+#define json_to_string(json_)  container_of(json_, json_string_t, json)
+#define json_to_real(json_)   container_of(json_, json_real_t, json)
+#define json_to_integer(json_) container_of(json_, json_integer_t, json)
+
 int json_object_set_nocheck(json_t *json, const char *key, json_t *value);
 json_t *json_string_nocheck(const char *value);
 
-
 #endif

diff --git a/src/value.c b/src/value.c
index 076e335..1982b90 100644 (file)
--- a/src/value.c
+++ b/src/value.c
@@ -15,41 +15,6 @@
 #include "utf.h"
 #include "util.h"
 
-#define container_of(ptr_, type_, member_)  \
-    ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
-
-typedef struct {
-    json_t json;
-    hashtable_t hashtable;
-} json_object_t;
-
-typedef struct {
-    json_t json;
-    unsigned int size;
-    unsigned int entries;
-    json_t **table;
-} json_array_t;
-
-typedef struct {
-    json_t json;
-    char *value;
-} json_string_t;
-
-typedef struct {
-    json_t json;
-    double value;
-} json_real_t;
-
-typedef struct {
-    json_t json;
-    int value;
-} json_integer_t;
-
-#define json_to_object(json_)  container_of(json_, json_object_t, json)
-#define json_to_array(json_)   container_of(json_, json_array_t, json)
-#define json_to_string(json_)  container_of(json_, json_string_t, json)
-#define json_to_real(json_)   container_of(json_, json_real_t, json)
-#define json_to_integer(json_) container_of(json_, json_integer_t, json)
 
 static inline void json_init(json_t *json, json_type type)
 {
@@ -98,6 +63,9 @@ json_t *json_object(void)
         free(object);
         return NULL;
     }
+
+    object->visited = 0;
+
     return &object->json;
 }
 
@@ -136,7 +104,7 @@ int json_object_set_new_nocheck(json_t *json, const char *key, json_t *value)
     if(!key || !value)
         return -1;
 
-    if(!json_is_object(json))
+    if(!json_is_object(json) || json == value)
     {
         json_decref(value);
         return -1;
@@ -273,6 +241,8 @@ json_t *json_array(void)
         return NULL;
     }
 
+    array->visited = 0;
+
     return &array->json;
 }
 
@@ -315,7 +285,7 @@ int json_array_set_new(json_t *json, unsigned int index, json_t *value)
     if(!value)
         return -1;
 
-    if(!json_is_array(json))
+    if(!json_is_array(json) || json == value)
     {
         json_decref(value);
         return -1;
@@ -383,7 +353,7 @@ int json_array_append_new(json_t *json, json_t *value)
     if(!value)
         return -1;
 
-    if(!json_is_array(json))
+    if(!json_is_array(json) || json == value)
     {
         json_decref(value);
         return -1;
@@ -409,7 +379,7 @@ int json_array_insert_new(json_t *json, unsigned int index, json_t *value)
     if(!value)
         return -1;
 
-    if(!json_is_array(json)) {
+    if(!json_is_array(json) || json == value) {
         json_decref(value);
         return -1;
     }

diff --git a/test/testprogs/test_array.c b/test/testprogs/test_array.c
index 53f6f3d..d077fa8 100644 (file)
--- a/test/testprogs/test_array.c
+++ b/test/testprogs/test_array.c
@@ -340,6 +340,52 @@ static void test_extend(void)
     json_decref(array2);
 }
 
+static void test_circular()
+{
+    json_t *array1, *array2;
+
+    /* the simple cases are checked */
+
+    array1 = json_array();
+    if(!array1)
+        fail("unable to create array");
+
+    if(json_array_append(array1, array1) == 0)
+        fail("able to append self");
+
+    if(json_array_insert(array1, 0, array1) == 0)
+        fail("able to insert self");
+
+    if(json_array_append_new(array1, json_true()))
+        fail("failed to append true");
+
+    if(json_array_set(array1, 0, array1) == 0)
+        fail("able to set self");
+
+    json_decref(array1);
+
+
+    /* create circular references */
+
+    array1 = json_array();
+    array2 = json_array();
+    if(!array1 || !array2)
+        fail("unable to create array");
+
+    if(json_array_append(array1, array2) ||
+       json_array_append(array2, array1))
+        fail("unable to append");
+
+    /* circularity is detected when dumping */
+    if(json_dumps(array1, 0) != NULL)
+        fail("able to dump circulars");
+
+    /* decref twice to deal with the circular references */
+    json_decref(array1);
+    json_decref(array2);
+    json_decref(array1);
+}
+
 
 int main()
 {
@@ -348,6 +394,7 @@ int main()
     test_remove();
     test_clear();
     test_extend();
+    test_circular();
 
     return 0;
 }

diff --git a/test/testprogs/test_object.c b/test/testprogs/test_object.c
index 3be49e5..657a9c6 100644 (file)
--- a/test/testprogs/test_object.c
+++ b/test/testprogs/test_object.c
@@ -139,6 +139,34 @@ static void test_update()
     json_decref(object);
 }
 
+static void test_circular()
+{
+    json_t *object1, *object2;
+
+    object1 = json_object();
+    object2 = json_object();
+    if(!object1 || !object2)
+        fail("unable to create object");
+
+    /* the simple case is checked */
+    if(json_object_set(object1, "a", object1) == 0)
+        fail("able to set self");
+
+    /* create circular references */
+    if(json_object_set(object1, "a", object2) ||
+       json_object_set(object2, "a", object1))
+        fail("unable to set value");
+
+    /* circularity is detected when dumping */
+    if(json_dumps(object1, 0) != NULL)
+        fail("able to dump circulars");
+
+    /* decref twice to deal with the circular references */
+    json_decref(object1);
+    json_decref(object2);
+    json_decref(object1);
+}
+
 static void test_misc()
 {
     json_t *object, *string, *other_string, *value;
@@ -264,6 +292,7 @@ int main()
     test_misc();
     test_clear();
     test_update();
+    test_circular();
 
     return 0;
 }