libcnary: Define error codes and add cycle, depth, and parent guards

3 files changed, 164 insertions, 67 deletions

diff --git a/libcnary/include/node.h b/libcnary/include/node.h
index 123241a..5b3ae37 100644
--- a/libcnary/include/node.h
+++ b/libcnary/include/node.h
@@ -29,6 +29,18 @@
 
 #define NODE_TYPE 1;
 
+#ifndef NODE_MAX_DEPTH
+#define NODE_MAX_DEPTH 512
+#endif
+
+#define NODE_ERR_SUCCESS       0
+#define NODE_ERR_INVALID_ARG  -1
+#define NODE_ERR_NO_MEM       -2
+#define NODE_ERR_PARENT       -3
+#define NODE_ERR_CIRCULAR_REF -4
+#define NODE_ERR_MAX_DEPTH    -5
+#define NODE_ERR_NOT_FOUND    -6
+
 // This class implements the abstract iterator class
 typedef struct node* node_t;
 struct node {
diff --git a/libcnary/node.c b/libcnary/node.c
index 8d3708b..9457548 100644
--- a/libcnary/node.c
+++ b/libcnary/node.c
@@ -61,12 +61,11 @@ node_t node_create(node_t parent, void* data)
         node->children = NULL;
 
         // Pass NULL to create a root node
-        if(parent != NULL) {
+        if (parent != NULL) {
                 // This is a child node so attach it to it's parent
                 error = node_attach(parent, node);
-                if(error < 0) {
+                if (error < 0) {
                         // Unable to attach nodes
-                        printf("ERROR: %d \"Unable to attach nodes\"\n", error);
                         node_destroy(node);
                         return NULL;
                 }
@@ -75,15 +74,86 @@ node_t node_create(node_t parent, void* data)
         return node;
 }
 
+static int node_depth_from_root(node_t n)
+{
+        int d = 0;
+        while (n && n->parent) {
+                d++;
+                n = n->parent;
+                if (d > NODE_MAX_DEPTH) return d; // early out
+        }
+        return d;
+}
+
+static int node_subtree_max_depth(node_t root)
+{
+        if (!root) return 0;
+
+        typedef struct { node_t n; int depth; } frame_t;
+        size_t cap = 64, sp = 0;
+        frame_t *st = (frame_t*)malloc(cap * sizeof(*st));
+        if (!st) return NODE_MAX_DEPTH + 1;
+
+        st[sp++] = (frame_t){ root, 0 };
+        int maxd = 0;
+
+        while (sp) {
+                frame_t f = st[--sp];
+                if (f.depth > maxd) maxd = f.depth;
+                if (maxd > NODE_MAX_DEPTH) break;
+
+                if (!f.n->children) continue;
+
+                for (node_t ch = node_first_child(f.n); ch; ch = node_next_sibling(ch)) {
+                        if (sp == cap) {
+                                cap *= 2;
+                                frame_t *tmp = (frame_t*)realloc(st, cap * sizeof(*st));
+                                if (!tmp) { maxd = NODE_MAX_DEPTH + 1; goto out; }
+                                st = tmp;
+                        }
+                        st[sp++] = (frame_t){ ch, f.depth + 1 };
+                }
+        }
+
+out:
+        free(st);
+        return maxd;
+}
+
+static int would_create_cycle(node_t parent, node_t child)
+{
+        // if parent is anywhere in child's ancestor chain => cycle
+        for (node_t p = parent; p; p = p->parent) {
+                if (p == child) return 1;
+        }
+        return 0;
+}
+
 int node_attach(node_t parent, node_t child)
 {
-        if (!parent || !child) return -1;
-        child->parent = parent;
-        if(!parent->children) {
+        if (!parent || !child) return NODE_ERR_INVALID_ARG;
+
+        // already parented?
+        if (child->parent) return NODE_ERR_PARENT;
+
+        // self/cycle guard
+        if (parent == child) return NODE_ERR_CIRCULAR_REF;
+        if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF;
+
+        // depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH
+        int pd = node_depth_from_root(parent);
+        int cd = node_subtree_max_depth(child);
+        if (pd + 1 + cd > NODE_MAX_DEPTH) {
+                return NODE_ERR_MAX_DEPTH;
+        }
+
+        if (!parent->children) {
                 parent->children = node_list_create();
+                if (!parent->children) return NODE_ERR_NO_MEM;
         }
         int res = node_list_add(parent->children, child);
         if (res == 0) {
+                child->parent = parent;
                 parent->count++;
         }
         return res;
@@ -91,7 +161,7 @@ int node_attach(node_t parent, node_t child)
 
 int node_detach(node_t parent, node_t child)
 {
-        if (!parent || !child) return -1;
+        if (!parent || !child) return NODE_ERR_INVALID_ARG;
         int node_index = node_list_remove(parent->children, child);
         if (node_index >= 0) {
                 parent->count--;
@@ -101,13 +171,29 @@ int node_detach(node_t parent, node_t child)
 
 int node_insert(node_t parent, unsigned int node_index, node_t child)
 {
-        if (!parent || !child) return -1;
-        child->parent = parent;
-        if(!parent->children) {
+        if (!parent || !child) return NODE_ERR_INVALID_ARG;
+
+        // already parented?
+        if (child->parent) return NODE_ERR_PARENT;
+
+        // self/cycle guard
+        if (parent == child) return NODE_ERR_CIRCULAR_REF;
+        if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF;
+
+        // depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH
+        int pd = node_depth_from_root(parent);
+        int cd = node_subtree_max_depth(child);
+        if (pd + 1 + cd > NODE_MAX_DEPTH) {
+                return NODE_ERR_MAX_DEPTH;
+        }
+
+        if (!parent->children) {
                 parent->children = node_list_create();
+                if (!parent->children) return NODE_ERR_NO_MEM;
         }
         int res = node_list_insert(parent->children, node_index, child);
         if (res == 0) {
+                child->parent = parent;
                 parent->count++;
         }
         return res;
@@ -186,7 +272,7 @@ node_t node_next_sibling(node_t node)
 
 int node_child_position(node_t parent, node_t child)
 {
-        if (!parent || !parent->children || !parent->children->begin || !child) return -1;
+        if (!parent || !parent->children || !parent->children->begin || !child) return NODE_ERR_INVALID_ARG;
         int node_index = 0;
         int found = 0;
         node_t ch;
@@ -198,7 +284,7 @@ int node_child_position(node_t parent, node_t child)
                 node_index++;
         }
         if (!found) {
-                return -1;
+                return NODE_ERR_NOT_FOUND;
         }
         return node_index;
 }
@@ -211,10 +297,18 @@ node_t node_copy_deep(node_t node, copy_func_t copy_func)
                 data = copy_func(node->data);
         }
         node_t copy = node_create(NULL, data);
+        if (!copy) return NULL;
         node_t ch;
         for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
                 node_t cc = node_copy_deep(ch, copy_func);
-                node_attach(copy, cc);
+                if (!cc) {
+                        node_destroy(copy);
+                        return NULL;
+                }
+                if (node_attach(copy, cc) < 0) {
+                        node_destroy(copy);
+                        return NULL;
+                }
         }
         return copy;
 }
diff --git a/libcnary/node_list.c b/libcnary/node_list.c
index f6c2c70..218c81d 100644
--- a/libcnary/node_list.c
+++ b/libcnary/node_list.c
@@ -49,7 +49,7 @@ node_list_t node_list_create()
 
 int node_list_add(node_list_t list, node_t node)
 {
-        if (!list || !node) return -1;
+        if (!list || !node) return NODE_ERR_INVALID_ARG;
 
         // Find the last element in the list
         node_t last = list->end;
@@ -72,89 +72,80 @@ int node_list_add(node_list_t list, node_t node)
 
         // Increment our node count for this list
         list->count++;
-        return 0;
+        return NODE_ERR_SUCCESS;
 }
 
 int node_list_insert(node_list_t list, unsigned int node_index, node_t node)
 {
-        if (!list || !node) return -1;
-        if (node_index >= list->count) {
+        if (!list || !node) return NODE_ERR_INVALID_ARG;
+        if (node_index > list->count) return NODE_ERR_INVALID_ARG;
+        if (node_index == list->count) {
                 return node_list_add(list, node);
         }
 
         // Get the first element in the list
         node_t cur = list->begin;
-
-        unsigned int pos = 0;
         node_t prev = NULL;
 
-        if (node_index > 0) {
-                while (pos < node_index) {
-                        prev = cur;
-                        cur = cur->next;
-                        pos++;
-                }
+        for (unsigned int pos = 0; pos < node_index; pos++) {
+                if (!cur) return NODE_ERR_INVALID_ARG;
+                prev = cur;
+                cur = cur->next;
         }
 
+        // insert node before cur
+        node->prev = prev;
+        node->next = cur;
+
         if (prev) {
-                // Set previous node
-                node->prev = prev;
-                // Set next node of our new node to next node of the previous node
-                node->next = prev->next;
-                // Set next node of previous node to our new node
                 prev->next = node;
         } else {
-                node->prev = NULL;
-                // get old first element in list
-                node->next = list->begin;
-                // set new node as first element in list
                 list->begin = node;
         }
 
-        if (node->next == NULL) {
-                // Set the lists prev to the new last element
-                list->end = node;
+        if (cur) {
+                cur->prev = node;
         } else {
-                // set prev of the new next element to our node
-                node->next->prev = node;
+                // should not happen with bounds above, but keeps things consistent
+                list->end = node;
         }
 
         // Increment our node count for this list
         list->count++;
-        return 0;
+        return NODE_ERR_SUCCESS;
 }
 
+// Returns removed index (>=0) on success, or NODE_ERR_* (<0) on failure.
 int node_list_remove(node_list_t list, node_t node)
 {
-        if (!list || !node) return -1;
-        if (list->count == 0) return -1;
+        if (!list || !node) return NODE_ERR_INVALID_ARG;
+        if (list->count == 0) return NODE_ERR_NOT_FOUND;
 
         int node_index = 0;
-        node_t n;
-        for (n = list->begin; n; n = n->next) {
-                if (node == n) {
-                        node_t newnode = node->next;
-                        if (node->prev) {
-                                node->prev->next = newnode;
-                                if (newnode) {
-                                        newnode->prev = node->prev;
-                                } else {
-                                        // last element in the list
-                                        list->end = node->prev;
-                                }
-                        } else {
-                                // we just removed the first element
-                                if (newnode) {
-                                        newnode->prev = NULL;
-                                } else {
-                                        list->end = NULL;
-                                }
-                                list->begin = newnode;
-                        }
-                        list->count--;
-                        return node_index;
+        for (node_t n = list->begin; n; n = n->next, node_index++) {
+                if (node != n) continue;
+
+                node_t newnode = node->next;
+                if (node->prev) {
+                        node->prev->next = newnode;
+                } else {
+                        // we just removed the first element
+                        list->begin = newnode;
                 }
-                node_index++;
+
+                if (newnode) {
+                        newnode->prev = node->prev;
+                } else {
+                        // we removed the last element, set new end
+                        list->end = node->prev;
+                }
+
+                // fully detach node from list
+                node->prev = NULL;
+                node->next = NULL;
+
+                list->count--;
+                return node_index;
         }
-        return -1;
+        return NODE_ERR_NOT_FOUND;
 }