9 files changed, 203 insertions, 28 deletions

diff --git a/include/plist/plist.h b/include/plist/plist.h
index 41af8ce..5ea30b8 100644
--- a/include/plist/plist.h
+++ b/include/plist/plist.h
@@ -144,6 +144,7 @@ extern "C"
         PLIST_ERR_PARSE        = -3,  /**< parsing of the input format failed */
         PLIST_ERR_NO_MEM       = -4,  /**< not enough memory to handle the operation */
         PLIST_ERR_IO           = -5,  /**< I/O error */
+        PLIST_ERR_CIRCULAR_REF = -6,  /**< circular reference detected */
         PLIST_ERR_UNKNOWN      = -255 /**< an unspecified error occurred */
     } plist_err_t;
 
diff --git a/src/bplist.c b/src/bplist.c
index b2d0e7c..ca2a556 100644
--- a/src/bplist.c
+++ b/src/bplist.c
@@ -244,8 +244,10 @@ struct bplist_data {
 #ifdef DEBUG
 static int plist_bin_debug = 0;
 #define PLIST_BIN_ERR(...) if (plist_bin_debug) { fprintf(stderr, "libplist[binparser] ERROR: " __VA_ARGS__); }
+#define PLIST_BIN_WRITE_ERR(...) if (plist_bin_debug) { fprintf(stderr, "libplist[binwriter] ERROR: " __VA_ARGS__); }
 #else
 #define PLIST_BIN_ERR(...)
+#define PLIST_BIN_WRITE_ERR(...)
 #endif
 
 void plist_bin_init(void)
@@ -997,35 +999,53 @@ struct serialize_s
 {
     ptrarray_t* objects;
     hashtable_t* ref_table;
+    hashtable_t* in_stack;
 };
 
-static void serialize_plist(node_t node, void* data)
+static plist_err_t serialize_plist(node_t node, void* data)
 {
     uint64_t *index_val = NULL;
     struct serialize_s *ser = (struct serialize_s *) data;
-    uint64_t current_index = ser->objects->len;
 
-    //first check that node is not yet in objects
+    // circular reference check: is node on current recursion stack?
+    if (hash_table_lookup(ser->in_stack, node)) {
+        PLIST_BIN_WRITE_ERR("circular reference detected\n");
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // first check that node is not yet in objects
     void* val = hash_table_lookup(ser->ref_table, node);
-    if (val)
-    {
-        //data is already in table
-        return;
+    if (val) {
+        // data is already in table
+        return PLIST_ERR_SUCCESS;
     }
-    //insert new ref
+
+    // mark as active
+    hash_table_insert(ser->in_stack, node, (void*)1);
+
+    // insert new ref
     index_val = (uint64_t *) malloc(sizeof(uint64_t));
     assert(index_val != NULL);
-    *index_val = current_index;
+    *index_val = ser->objects->len;
     hash_table_insert(ser->ref_table, node, index_val);
 
-    //now append current node to object array
+    // now append current node to object array
     ptr_array_add(ser->objects, node);
 
-    //now recurse on children
+    // now recurse on children
     node_t ch;
+    plist_err_t err = PLIST_ERR_SUCCESS;
     for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-        serialize_plist(ch, data);
+        err = serialize_plist(ch, data);
+        if (err != PLIST_ERR_SUCCESS) {
+            break;
+        }
     }
+
+    // leave recursion stack
+    hash_table_remove(ser->in_stack, node);
+
+    return err;
 }
 
 #define Log2(x) ((x) == 8 ? 3 : ((x) == 4 ? 2 : ((x) == 2 ? 1 : 0)))
@@ -1251,6 +1271,7 @@ plist_err_t plist_to_bin(plist_t plist, char **plist_bin, uint32_t * length)
 {
     ptrarray_t* objects = NULL;
     hashtable_t* ref_table = NULL;
+    hashtable_t* in_stack = NULL;
     struct serialize_s ser_s;
     uint8_t offset_size = 0;
     uint8_t ref_size = 0;
@@ -1280,11 +1301,28 @@ plist_err_t plist_to_bin(plist_t plist, char **plist_bin, uint32_t * length)
         ptr_array_free(objects);
         return PLIST_ERR_NO_MEM;
     }
+    //hashtable for circular reference detection
+    in_stack = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!in_stack) {
+        ptr_array_free(objects);
+        hash_table_destroy(ref_table);
+        return PLIST_ERR_NO_MEM;
+    }
 
     //serialize plist
     ser_s.objects = objects;
     ser_s.ref_table = ref_table;
-    serialize_plist((node_t)plist, &ser_s);
+    ser_s.in_stack = in_stack;
+    plist_err_t err = serialize_plist((node_t)plist, &ser_s);
+    if (err != PLIST_ERR_SUCCESS) {
+        ptr_array_free(objects);
+        hash_table_destroy(ref_table);
+        hash_table_destroy(in_stack);
+        return err;
+    }
+    //no longer needed
+    hash_table_destroy(in_stack);
+    ser_s.in_stack = NULL;
 
     //now stream to output buffer
     offset_size = 0;                    //unknown yet
diff --git a/src/jplist.c b/src/jplist.c
index 1c7a932..2e53400 100644
--- a/src/jplist.c
+++ b/src/jplist.c
@@ -38,6 +38,7 @@
 #include "plist.h"
 #include "strbuf.h"
 #include "jsmn.h"
+#include "hashtable.h"
 
 #ifdef DEBUG
 static int plist_json_debug = 0;
@@ -315,18 +316,27 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+        PLIST_JSON_WRITE_ERR("circular reference detected\n");
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         unsigned int n_children = node_n_children(node);
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            plist_err_t res = node_estimate_size(ch, size, depth + 1, prettify);
+            plist_err_t res = _node_estimate_size(ch, size, depth + 1, prettify, visited);
             if (res < 0) {
                 return res;
             }
@@ -402,6 +412,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, prettify, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 plist_err_t plist_to_json(plist_t plist, char **plist_json, uint32_t* length, int prettify)
 {
     uint64_t size = 0;
diff --git a/src/oplist.c b/src/oplist.c
index 277693f..680873c 100644
--- a/src/oplist.c
+++ b/src/oplist.c
@@ -37,6 +37,7 @@
 
 #include "plist.h"
 #include "strbuf.h"
+#include "hashtable.h"
 
 #ifdef DEBUG
 static int plist_ostep_debug = 0;
@@ -359,18 +360,27 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+        PLIST_OSTEP_WRITE_ERR("circular reference detected\n");
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         unsigned int n_children = node_n_children(node);
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            plist_err_t res = node_estimate_size(ch, size, depth + 1, prettify);
+            plist_err_t res = _node_estimate_size(ch, size, depth + 1, prettify, visited);
             if (res < 0) {
                 return res;
             }
@@ -446,6 +456,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, int prettify)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, prettify, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 plist_err_t plist_to_openstep(plist_t plist, char **openstep, uint32_t* length, int prettify)
 {
     uint64_t size = 0;
diff --git a/src/out-default.c b/src/out-default.c
index 266070b..09e64c3 100644
--- a/src/out-default.c
+++ b/src/out-default.c
@@ -38,6 +38,7 @@
 #include "plist.h"
 #include "strbuf.h"
 #include "time64.h"
+#include "hashtable.h"
 
 #define MAC_EPOCH 978307200
 
@@ -310,19 +311,30 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+#if DEBUG
+        fprintf(stderr, "libplist: ERROR: circular reference detected\n");
+#endif
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         unsigned int n_children = node_n_children(node);
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            plist_err_t res = node_estimate_size(ch, size, depth + 1, indent, partial_data);
-            if (res < 0) {
+            plist_err_t res = _node_estimate_size(ch, size, depth + 1, indent, partial_data, visited);
+            if (res != PLIST_ERR_SUCCESS) {
                 return res;
             }
         }
@@ -401,6 +413,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, int partial_data)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, indent, partial_data, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options)
 {
     uint8_t indent = 0;
diff --git a/src/out-limd.c b/src/out-limd.c
index 7d861f8..e281644 100644
--- a/src/out-limd.c
+++ b/src/out-limd.c
@@ -40,6 +40,7 @@
 #include "strbuf.h"
 #include "time64.h"
 #include "base64.h"
+#include "hashtable.h"
 
 #define MAC_EPOCH 978307200
 
@@ -278,19 +279,30 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+#if DEBUG
+        fprintf(stderr, "libplist: ERROR: circular reference detected\n");
+#endif
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         unsigned int n_children = node_n_children(node);
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            plist_err_t res = node_estimate_size(ch, size, depth + 1, indent);
-            if (res < 0) {
+            plist_err_t res = _node_estimate_size(ch, size, depth + 1, indent, visited);
+            if (res != PLIST_ERR_SUCCESS) {
                 return res;
             }
         }
@@ -359,6 +371,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth, uint32_t indent)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, indent, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options)
 {
     uint8_t indent = 0;
diff --git a/src/out-plutil.c b/src/out-plutil.c
index d85f22c..5354aa3 100644
--- a/src/out-plutil.c
+++ b/src/out-plutil.c
@@ -38,6 +38,7 @@
 #include "plist.h"
 #include "strbuf.h"
 #include "time64.h"
+#include "hashtable.h"
 
 #define MAC_EPOCH 978307200
 
@@ -304,19 +305,30 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+#if DEBUG
+        fprintf(stderr, "libplist: ERROR: circular reference detected\n");
+#endif
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         unsigned int n_children = node_n_children(node);
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            plist_err_t res = node_estimate_size(ch, size, depth + 1);
-            if (res < 0) {
+            plist_err_t res = _node_estimate_size(ch, size, depth + 1, visited);
+            if (res != PLIST_ERR_SUCCESS) {
                 return res;
             }
         }
@@ -388,6 +400,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 static plist_err_t _plist_write_to_strbuf(plist_t plist, strbuf_t *outbuf, plist_write_options_t options)
 {
     plist_err_t res = node_to_string((node_t)plist, &outbuf, 0);
diff --git a/src/plist.h b/src/plist.h
index a993e3a..3043fb7 100644
--- a/src/plist.h
+++ b/src/plist.h
@@ -81,4 +81,17 @@ extern plist_err_t plist_write_to_stream_default(plist_t plist, FILE *stream, pl
 extern plist_err_t plist_write_to_stream_limd(plist_t plist, FILE *stream, plist_write_options_t options);
 extern plist_err_t plist_write_to_stream_plutil(plist_t plist, FILE *stream, plist_write_options_t options);
 
+static inline unsigned int plist_node_ptr_hash(const void *ptr)
+{
+    uintptr_t h = (uintptr_t)ptr;
+    h ^= (h >> 16);
+    h *= 0x85ebca6b;
+    return (unsigned int)h;
+}
+
+static inline int plist_node_ptr_compare(const void *a, const void *b)
+{
+    return a == b;
+}
+
 #endif
diff --git a/src/xplist.c b/src/xplist.c
index dc5213b..c25c6b9 100644
--- a/src/xplist.c
+++ b/src/xplist.c
@@ -46,6 +46,7 @@
 #include "base64.h"
 #include "strbuf.h"
 #include "time64.h"
+#include "hashtable.h"
 
 #define XPLIST_KEY      "key"
 #define XPLIST_KEY_LEN 3
@@ -444,17 +445,29 @@ static int num_digits_u(uint64_t i)
     return n;
 }
 
-static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth)
+static plist_err_t _node_estimate_size(node_t node, uint64_t *size, uint32_t depth, hashtable_t *visited)
 {
     plist_data_t data;
     if (!node) {
         return PLIST_ERR_INVALID_ARG;
     }
+
+    if (hash_table_lookup(visited, node)) {
+        PLIST_XML_WRITE_ERR("circular reference detected\n");
+        return PLIST_ERR_CIRCULAR_REF;
+    }
+
+    // mark as visited
+    hash_table_insert(visited, node, (void*)1);
+
     data = plist_get_data(node);
     if (node->children) {
         node_t ch;
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-            node_estimate_size(ch, size, depth + 1);
+            plist_err_t err = _node_estimate_size(ch, size, depth + 1, visited);
+            if (err != PLIST_ERR_SUCCESS) {
+                return err;
+            }
         }
         switch (data->type) {
         case PLIST_DICT:
@@ -529,6 +542,15 @@ static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t dept
     return PLIST_ERR_SUCCESS;
 }
 
+static plist_err_t node_estimate_size(node_t node, uint64_t *size, uint32_t depth)
+{
+    hashtable_t *visited = hash_table_new(plist_node_ptr_hash, plist_node_ptr_compare, NULL);
+    if (!visited) return PLIST_ERR_NO_MEM;
+    plist_err_t err = _node_estimate_size(node, size, depth, visited);
+    hash_table_destroy(visited);
+    return err;
+}
+
 plist_err_t plist_to_xml(plist_t plist, char **plist_xml, uint32_t * length)
 {
     uint64_t size = 0;