dgraph: add dgraph_check and CCAN_DGRAPH_DEBUG

This is good form for datastructures, so caller can track weird bugs.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c
index 9a6f66245dbe9ff533353ee308d56422dfe6134e..eb5a62d2c7a3d52223c61fc7aa221d30e33d242f 100644 (file)
--- a/ccan/dgraph/dgraph.c
+++ b/ccan/dgraph/dgraph.c
@@ -1,6 +1,7 @@
 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
 #include <ccan/dgraph/dgraph.h>
 #include <stdlib.h>
+#include <stdio.h>
 
 void dgraph_init_node(struct dgraph_node *n)
 {
@@ -22,6 +23,7 @@ void dgraph_clear_node(struct dgraph_node *n)
        struct dgraph_edge *e;
        unsigned int i;
 
+       (void)dgraph_debug(n);
        for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
                while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
                        assert(e->n[i] == n);
@@ -33,6 +35,9 @@ void dgraph_clear_node(struct dgraph_node *n)
 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
 {
        struct dgraph_edge *e = malloc(sizeof(*e));
+
+       (void)dgraph_debug(from);
+       (void)dgraph_debug(to);
        e->n[DGRAPH_FROM] = from;
        e->n[DGRAPH_TO] = to;
        tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
@@ -43,6 +48,8 @@ bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
 {
        struct dgraph_edge *e, *next;
 
+       (void)dgraph_debug(from);
+       (void)dgraph_debug(to);
        dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
                if (e->n[DGRAPH_TO] == to) {
                        free_edge(e);
@@ -59,22 +66,110 @@ static bool traverse_depth_first(struct dgraph_node *n,
 {
        struct dgraph_edge *e, *next;
 
-       dgraph_for_each_edge_safe(n, e, next, dir) {
+       /* dgraph_for_each_edge_safe, without dgraph_debug() */
+       tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
                if (!traverse_depth_first(e->n[!dir], dir, fn, data))
                        return false;
        }
        return fn(n, (void *)data);
 }
 
-void dgraph_traverse(struct dgraph_node *n,
+void dgraph_traverse(const struct dgraph_node *n,
                     enum dgraph_dir dir,
                     bool (*fn)(struct dgraph_node *, void *),
                     const void *data)
 {
        struct dgraph_edge *e, *next;
 
-       dgraph_for_each_edge_safe(n, e, next, dir) {
+       /* dgraph_for_each_edge_safe, without dgraph_debug() */
+       tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
                if (!traverse_depth_first(e->n[!dir], dir, fn, data))
                        break;
        }
 }
+
+struct check_info {
+       const struct dgraph_node *ret;
+       const char *abortstr;
+};
+
+static bool find_backedge(const struct dgraph_node *from,
+                         const struct dgraph_node *to,
+                         enum dgraph_dir dir)
+{
+       struct dgraph_edge *e;
+
+       tlist_for_each(&from->edge[dir], e, list[dir]) {
+               if (e->n[!dir] == to)
+                       return true;
+       }
+       return false;
+}
+
+static bool dgraph_check_node(struct dgraph_node *n, void *info_)
+{
+       struct check_info *info = info_;
+       unsigned int dir;
+       struct dgraph_edge *e;
+
+       for (dir = DGRAPH_FROM; dir <= DGRAPH_TO; dir++) {
+               /* First, check edges list. */
+               if (!tlist_check(&n->edge[dir], info->abortstr)) {
+                       info->ret = NULL;
+                       return false;
+               }
+
+               /* dgraph_for_each_edge() without check! */
+               tlist_for_each(&n->edge[dir], e, list[dir]) {
+                       if (e->n[dir] == n) {
+                               if (find_backedge(e->n[!dir], n, !dir))
+                                       continue;
+                               if (info->abortstr) {
+                                       fprintf(stderr,
+                                               "%s: node %p %s edge doesnt"
+                                               " point back to %p\n",
+                                               info->abortstr, e->n[!dir],
+                                               !dir == DGRAPH_FROM
+                                               ? "DGRAPH_FROM" : "DGRAPH_TO",
+                                               n);
+                                       abort();
+                               }
+                               info->ret = NULL;
+                               return false;
+                       }
+
+                       if (info->abortstr) {
+                               fprintf(stderr,
+                                       "%s: node %p %s edge %p points"
+                                       " to %p\n",
+                                       info->abortstr, n,
+                                       dir == DGRAPH_FROM
+                                       ? "DGRAPH_FROM" : "DGRAPH_TO",
+                                       e, e->n[dir]);
+                               abort();
+                       }
+                       info->ret = NULL;
+                       return false;
+               }
+       }
+
+       return true;
+}
+
+struct dgraph_node *dgraph_check(const struct dgraph_node *n,
+                                const char *abortstr)
+{
+       struct check_info info;
+
+       /* This gets set to NULL by dgraph_check_node on failure. */
+       info.ret = n;
+       info.abortstr = abortstr;
+
+       dgraph_check_node((struct dgraph_node *)info.ret, &info);
+
+       if (info.ret)
+               dgraph_traverse(n, DGRAPH_FROM, dgraph_check_node, &info);
+       if (info.ret)
+               dgraph_traverse(n, DGRAPH_TO, dgraph_check_node, &info);
+       return (void *)info.ret;
+}

diff --git a/ccan/dgraph/dgraph.h b/ccan/dgraph/dgraph.h
index dd1723fb19074f168a685b7572f8057b5953d111..6c82798c0a551dbf63057ed770cbb47f031f7096 100644 (file)
--- a/ccan/dgraph/dgraph.h
+++ b/ccan/dgraph/dgraph.h
@@ -40,28 +40,46 @@ void dgraph_clear_node(struct dgraph_node *n);
 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to);
 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to);
 
+#ifdef CCAN_DGRAPH_DEBUG
+#define dgraph_debug(n) dgraph_check((n), __func__)
+#else
+#define dgraph_debug(n) (n)
+#endif
+
 /* You can dgraph_clear_node() the node you're on safely. */
 #define dgraph_traverse_from(n, fn, arg)                               \
-       dgraph_traverse((n), DGRAPH_FROM,                               \
+       dgraph_traverse(dgraph_debug(n), DGRAPH_FROM,                   \
                        typesafe_cb_preargs(bool, void *, (fn), (arg),  \
                                            struct dgraph_node *),      \
                        (arg))
 
 #define dgraph_traverse_to(n, fn, arg)                                 \
-       dgraph_traverse((n), DGRAPH_TO,                                 \
+       dgraph_traverse(dgraph_debug(n), DGRAPH_TO,                     \
                        typesafe_cb_preargs(bool, void *, (fn), (arg),  \
                                            struct dgraph_node *),      \
                        (arg))
 
-void dgraph_traverse(struct dgraph_node *n,
+void dgraph_traverse(const struct dgraph_node *n,
                     enum dgraph_dir dir,
                     bool (*fn)(struct dgraph_node *from, void *data),
                     const void *data);
 
 #define dgraph_for_each_edge(n, i, dir)                \
-       tlist_for_each(&(n)->edge[dir], i, list[dir])
+       tlist_for_each(&dgraph_debug(n)->edge[dir], i, list[dir])
 
 #define dgraph_for_each_edge_safe(n, i, next, dir)             \
-       tlist_for_each_safe(&(n)->edge[dir], i, next, list[dir])
+       tlist_for_each_safe(&dgraph_debug(n)->edge[dir], i, next, list[dir])
 
+/**
+ * dgraph_check - check a graph for consistency
+ * @n: the dgraph_node to check.
+ * @abortstr: the string to print on aborting, or NULL.
+ *
+ * Returns @n if the list is consistent, NULL if not (it can never
+ * return NULL if @abortstr is set).
+ *
+ * See also: tlist_check()
+ */
+struct dgraph_node *dgraph_check(const struct dgraph_node *n,
+                                const char *abortstr);
 #endif /* CCAN_DGRAPH_H */

diff --git a/ccan/dgraph/test/run-debug.c b/ccan/dgraph/test/run-debug.c
new file mode 100644 (file)
index 0000000..d9d3265
--- /dev/null
+++ b/ccan/dgraph/test/run-debug.c
@@ -0,0 +1,135 @@
+#define CCAN_DGRAPH_DEBUG 1
+#include <ccan/dgraph/dgraph.h>
+/* Include the C files directly. */
+#include <ccan/dgraph/dgraph.c>
+#include <ccan/tap/tap.h>
+
+static bool count_nodes(struct dgraph_node *n, unsigned int *count)
+{
+       (*count)++;
+       return true;
+}
+
+static bool stop_traverse(struct dgraph_node *n, unsigned int *count)
+{
+       if (--(*count) == 0)
+               return false;
+       return true;
+}
+
+int main(void)
+{
+       struct dgraph_node n1, n2, n3;
+       unsigned int count = 0;
+
+       /* This is how many tests you plan to run */
+       plan_tests(42);
+
+       dgraph_init_node(&n1);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+
+       dgraph_init_node(&n2);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       dgraph_add_edge(&n1, &n2);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 1);
+
+       dgraph_init_node(&n3);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+       dgraph_add_edge(&n2, &n3);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 2);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 2);
+
+       /* Check stopping traverse. */
+       count = 1;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 0);
+       count = 2;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 0);
+       count = 3;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 1);
+
+       dgraph_clear_node(&n1);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 1);
+
+       ok1(dgraph_del_edge(&n2, &n3));
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 0);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+
+       ok1(!dgraph_del_edge(&n2, &n3));
+       dgraph_clear_node(&n2);
+
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}

diff --git a/ccan/dgraph/test/run.c b/ccan/dgraph/test/run.c
index b868c18a3d6351f87adc8591e177de31c801a9ad..0253ac2409e54fde47db7aeca3256aaabab67ca8 100644 (file)
--- a/ccan/dgraph/test/run.c
+++ b/ccan/dgraph/test/run.c
@@ -22,9 +22,10 @@ int main(void)
        unsigned int count = 0;
 
        /* This is how many tests you plan to run */
-       plan_tests(25);
+       plan_tests(42);
 
        dgraph_init_node(&n1);
+       ok1(dgraph_check(&n1, NULL) == &n1);
        count = 0;
        dgraph_traverse_from(&n1, count_nodes, &count);
        ok1(count == 0);
@@ -33,7 +34,10 @@ int main(void)
        ok1(count == 0);
 
        dgraph_init_node(&n2);
+       ok1(dgraph_check(&n2, NULL) == &n2);
        dgraph_add_edge(&n1, &n2);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
        count = 0;
        dgraph_traverse_from(&n1, count_nodes, &count);
        ok1(count == 1);
@@ -48,7 +52,11 @@ int main(void)
        ok1(count == 1);
 
        dgraph_init_node(&n3);
+       ok1(dgraph_check(&n3, NULL) == &n3);
        dgraph_add_edge(&n2, &n3);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
        count = 0;
        dgraph_traverse_from(&n1, count_nodes, &count);
        ok1(count == 2);
@@ -80,6 +88,9 @@ int main(void)
        ok1(count == 1);
 
        dgraph_clear_node(&n1);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
 
        count = 0;
        dgraph_traverse_from(&n2, count_nodes, &count);
@@ -107,10 +118,17 @@ int main(void)
        count = 0;
        dgraph_traverse_to(&n3, count_nodes, &count);
        ok1(count == 0);
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
 
        ok1(!dgraph_del_edge(&n2, &n3));
        dgraph_clear_node(&n2);
 
+       ok1(dgraph_check(&n1, NULL) == &n1);
+       ok1(dgraph_check(&n2, NULL) == &n2);
+       ok1(dgraph_check(&n3, NULL) == &n3);
+
        /* This exits depending on whether all tests passed */
        return exit_status();
 }