summaryrefslogtreecommitdiffabout
path: root/tests
authorSergey Poznyakoff <gray@gnu.org>2020-10-18 19:20:16 (GMT)
committer Sergey Poznyakoff <gray@gnu.org>2020-10-18 19:20:16 (GMT)
commitc26297063aa2dad0fecd28791a47a8bffcfc9925 (patch) (unidiff)
tree964990a4dd3c62bf0f25f248518b729403eb3c1a /tests
parenta7f3e6adb0ffbe56d9b521522d22cf758ee6acb7 (diff)
downloadpies-c26297063aa2dad0fecd28791a47a8bffcfc9925.tar.gz
pies-c26297063aa2dad0fecd28791a47a8bffcfc9925.tar.bz2
Fix cyclic dependecy detection and reporting.HEADmaster
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.
Diffstat (limited to 'tests') (more/less context) (ignore whitespace changes)
-rw-r--r--tests/cyclic.at33
1 files changed, 31 insertions, 2 deletions
diff --git a/tests/cyclic.at b/tests/cyclic.at
index 7c24acf..1cc542d 100644
--- a/tests/cyclic.at
+++ b/tests/cyclic.at
@@ -15,6 +15,7 @@
15# along with GNU pies. If not, see <http://www.gnu.org/licenses/>. 15# along with GNU pies. If not, see <http://www.gnu.org/licenses/>.
16 16
17AT_SETUP([Detecting cyclic dependencies]) 17AT_SETUP([Detecting cyclic dependencies])
18
18AT_CHECK([ 19AT_CHECK([
19PIES_XFAIL_CHECK 20PIES_XFAIL_CHECK
20# The following matrices describe the test.conf configuration file below. 21# The following matrices describe the test.conf configuration file below.
@@ -105,10 +106,38 @@ Legend:
105 1: g 106 1: g
106 2: h 107 2: h
107], 108],
108[pies: component a depends on itself 109[pies: cyclic dependencies detected:
109pies: a -> d -> c -> e -> a 110pies: a -> d -> c -> e -> a
110pies: component b depends on itself
111pies: b -> b 111pies: b -> b
112]) 112])
113 113
114AT_CHECK([
115AT_DATA([test.conf],[
116component a {
117 command "a";
118 prerequisites (b,c);
119}
120component b {
121 command "b";
122 prerequisites (c);
123}
124component c {
125 command "c";
126 prerequisites (d);
127}
128component d {
129 command "d";
130 prerequisites (a);
131}
132])
133pies --config-file test.conf --dump-depmap | trimws
134],
135[0],
136[No components defined
137],
138[pies: cyclic dependencies detected:
139pies: a -> c -> d -> a
140pies: a -> b -> c -> d -> a
141])
142
114AT_CLEANUP 143AT_CLEANUP

Return to:

Send suggestions and report system problems to the System administrator.