Fix cyclic dependecy detection and reporting.

Use modified Floyd-Warshall algorithm for cyclic dependecy detection.
The computed next vertex indices are used when reporting the cycles
found.

This fixes dead loops that occurred in earlier versions when trying to
report cycles.  One of inputs that caused such behavior is used as a
new test in cyclic.at.

* src/depmap.c: Rewrite using modified Floyd-Warshall algorithm.
(depmap_cycle_detect,depmap_path_free): New functions.
* src/comp.c (report_cyclic_dependency): Take struct depmap_path *
as argument.
(component_build_depmap): Use depmap_cycle_detect to detect cyclic
dependencies.
(depmap_dump): Special handling for zero-sized depmap.
* tests/cyclic.at: Add new test.
* src/pies.h (depmap_dim, depmap_free)
(depmap_cycle_detect,depmap_path_free): New protos.
* NEWS: Document changes.

1 files changed, 19 insertions, 0 deletions

diff --git a/src/pies.h b/src/pies.h
index 1a03702..d397f88 100644
--- a/src/pies.h
+++ b/src/pies.h
@@ -392,6 +392,8 @@ enum pies_depmap_direction
 
 pies_depmap_t depmap_alloc (size_t count);
 pies_depmap_t depmap_copy (pies_depmap_t dpm);
+size_t depmap_dim (struct pies_depmap *dmap);
+void depmap_free (pies_depmap_t dmap);
 void depmap_set (pies_depmap_t dmap, size_t row, size_t col);
 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);
@@ -403,6 +405,23 @@ size_t depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir,
 size_t depmap_next (pies_depmap_t dmap, pies_depmap_pos_t pos);
 void depmap_end (pies_depmap_pos_t pos);
 
+
+struct depmap_path_elem
+{
+  int idx;
+  struct depmap_path_elem *next;
+};
+
+struct depmap_path
+{
+  size_t len;
+  struct depmap_path_elem *head, *tail;
+  struct depmap_path *next;
+};
+
+void depmap_path_free (struct depmap_path *path);
+struct depmap_path *depmap_cycle_detect (pies_depmap_t dmap);
+
 int assert_grecs_value_type (grecs_locus_t *locus,
 			     const grecs_value_t *value, int type);