Revise dependency handling. Correctly display cyclic dependencies.

* src/comp.c (component_log_dep): Remove.
(report_cyclic_dependency): New function.
(comp_array_remove): New function.
(component_build_depmap): Remove erroneous components both from
the component table and dependency map.
(components_dump_depmap): Avoid trailing whitespace in the output.
* src/depmap.c (depmap_clear_all): Remove.
(depmap_remove): New function.
* src/pies.h (CF_REMOVE): New flag.
(depmap_clear_all): Remove prototype.
(depmap_remove): New prototype.

* tests/Makefile.am: Add new test.
* tests/atlocal.in (trimws): New function.
* tests/cyclic.at: New test.
* tests/testsuite.at: Include new test.

7 files changed, 222 insertions, 60 deletions

diff --git a/src/comp.c b/src/comp.c
index 17832ad..fcd0a14 100644
--- a/src/comp.c
+++ b/src/comp.c
@@ -127,3 +127,3 @@ component_lookup_index (const char *tag)
   for (i = 0; i < comp_count; i++)
-    if (comp_array[i] && strcmp (comp_array[i]->tag, tag) == 0)
+    if (strcmp (comp_array[i]->tag, tag) == 0)
       return i;
@@ -390,16 +390,35 @@ list_str_cmp (const void *a, const void *b)
 
+/* Report cyclic dependency starting at IDX.  Mark each element with
+   CF_REMOVE for subsequent removal.
+   DP is a transitive closure of depmap.
+*/
 static void
-component_log_dep (size_t idx)
+report_cyclic_dependency (pies_depmap_t dp, size_t idx)
 {
-  pies_depmap_pos_t pos;
-  size_t n;
+  size_t i;
   
-  logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag);
-  for (n = depmap_first (depmap, depmap_col, idx, &pos);
-       n != (size_t)-1;
-       n = depmap_next (depmap, pos))
+  i = idx;
+  do
     {
-      logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag);
+      size_t n;
+      pies_depmap_pos_t pos;
+      
+      logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag);
+      comp_array[i]->flags |= CF_REMOVE;
+      for (n = depmap_first (depmap, depmap_col, i, &pos);
+           n != (size_t)-1;
+           n = depmap_next (depmap, pos))
+        {
+          if (n == i)
+            continue;
+          if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n))
+            break;
+        }
+      depmap_end (pos);
+
+      if (n == (size_t)-1)
+        break;
+      i = n;
     }
-  depmap_end (pos);
+  while (i != idx);
   logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag);
@@ -408,2 +427,13 @@ component_log_dep (size_t idx)
 void
+comp_array_remove (size_t i)
+{
+  struct component *comp = comp_array[i];
+  if (i < comp_count - 1)
+    memmove (&comp_array[i], &comp_array[i+1],
+             (comp_count - i - 1) * sizeof comp_array[0]);
+  component_free (comp);
+  comp_count--;
+}
+
+void
 component_build_depmap (void)
@@ -415,3 +445,3 @@ component_build_depmap (void)
   depmap = depmap_alloc (comp_count);
-  for (i = 0; i < comp_count; i++)
+  for (i = 0; i < comp_count; )
     {
@@ -431,6 +461,4 @@ component_build_depmap (void)
                         comp->tag, tag);
-                component_free (comp);
-                comp_array[i] = NULL;
-                depmap_clear_all (depmap, depmap_row, i);
-                depmap_clear_all (depmap, depmap_col, i);
+                comp_array_remove (i);
+                depmap_remove (depmap, i);
                 continue;
@@ -454,2 +482,4 @@ component_build_depmap (void)
           }
+      
+      i++;
     }
@@ -459,3 +489,3 @@ component_build_depmap (void)
   for (i = 0; i < comp_count; i++)
-    if (depmap_isset (dp, i, i))
+    if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i))
       {
@@ -463,9 +493,15 @@ component_build_depmap (void)
                 comp_array[i]->tag);
-        component_log_dep (i);
-        component_free (comp_array[i]);
-        comp_array[i] = NULL;
-        depmap_clear_all (depmap, depmap_row, i);
-        depmap_clear_all (depmap, depmap_col, i);
-        continue;
+        report_cyclic_dependency (dp, i);
+      }
+
+  
+  for (i = 0; i < comp_count;)
+    if (comp_array[i]->flags & CF_REMOVE)
+      {
+        comp_array_remove (i);
+        depmap_remove (depmap, i);
       }
+    else
+      i++;
+  
   free (dp);
@@ -750,5 +786,5 @@ component_get (size_t n)
 void
-components_dump_depmap (void)
+depmap_dump (pies_depmap_t dpm)
 {
-  size_t i, j, k;
+  size_t i, j;
 
@@ -756,20 +792,11 @@ components_dump_depmap (void)
   printf ("  ");
-  for (i = k = 0; i < comp_count; i++)
-    if (comp_array[i])
-      {
-        printf (" %2lu", (unsigned long)k);
-        k++;
-      }
+  for (i = 0; i < comp_count; i++)
+    printf (" %2lu", (unsigned long)i);
   printf ("\n");
-  for (i = k = 0; i < comp_count; i++)
+  for (i = 0; i < comp_count; i++)
     {
-      if (comp_array[i])
-        {
-          printf ("%2lu ", (unsigned long)k);
-          for (j = 0; j < comp_count; j++)
-            if (comp_array[j])
-              printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' ');
-          printf ("\n");
-          k++;
-       }
+      printf ("%2lu", (unsigned long)i);
+      for (j = 0; j < comp_count; j++)
+        printf ("  %c", depmap_isset (dpm, i, j) ? 'X' : ' ');
+      printf ("\n");
     }
@@ -781,2 +808,8 @@ components_dump_depmap (void)
 void
+components_dump_depmap (void)
+{
+  depmap_dump (depmap);
+}
+
+void
 component_trace (size_t idx, enum pies_depmap_direction dir)
diff --git a/src/depmap.c b/src/depmap.c
index 3ea5722..cb50548 100644
--- a/src/depmap.c
+++ b/src/depmap.c
@@ -83,5 +83,5 @@ struct pies_depmap
 {
-  size_t nrows;
-  size_t rowlen;
-  unsigned r[1];
+  size_t nrows;         /* Number of rows (== number of mapped elements) */
+  size_t rowlen;        /* Length of a row in words */
+  unsigned r[1];        /* Data rows */
 };
@@ -99,2 +99,9 @@ depmap_alloc (size_t count)
 
+/* Return size of a depmap row in bytes */
+static inline size_t
+depmap_row_size (pies_depmap_t dpm)
+{
+  return dpm->rowlen * sizeof (unsigned);
+}   
+
 pies_depmap_t
@@ -103,3 +110,3 @@ depmap_copy (pies_depmap_t dpm)
   pies_depmap_t copy = depmap_alloc (dpm->nrows);
-  memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned));
+  memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm));
   return copy;
@@ -176,19 +183,20 @@ depmap_end (pies_depmap_pos_t pos)
 
+/* Remove nth row and column from the map */
 void
-depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir,
-                  size_t coord)
+depmap_remove (pies_depmap_t dmap, size_t n)
 {
-  size_t i;
-  
-  switch (dir)
+  if (n < dmap->nrows - 1)
     {
-    case depmap_row:
-      for (i = 0; i < dmap->nrows; i++)
-        depmap_clear (dmap, coord, i);
-      break;
-
-    case depmap_col:
+      size_t i, j;
+      
+      /* Remove nth row */
+      memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1),
+               (dmap->nrows - n - 1) * depmap_row_size (dmap));
+      /* Renumber all columns j >= n: j = j - 1 */
       for (i = 0; i < dmap->nrows; i++)
-        depmap_clear (dmap, i, coord);
+        for (j = n; j < dmap->nrows - 1; j++)
+          (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear)
+            (dmap, i, j);
     }
+  dmap->nrows--;
 }
diff --git a/src/pies.h b/src/pies.h
index 70d972a..e7e5d71 100644
--- a/src/pies.h
+++ b/src/pies.h
@@ -201,2 +201,4 @@ enum pies_comp_mode
 
+#define CF_REMOVE      0x400 /* Marked for removal */
+
 #define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS))
@@ -376,5 +378,3 @@ int depmap_isset (pies_depmap_t dmap, size_t row, size_t col);
 void depmap_clear (pies_depmap_t dmap, size_t row, size_t col);
-
-void depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir,
-                       size_t coord);
+void depmap_remove (pies_depmap_t dmap, size_t n);
 
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 5ef3796..6c387cb 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -43,2 +43,3 @@ TESTSUITE_AT = \
  control.at\