summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org>2019-05-23 10:08:08 (GMT)
committer Sergey Poznyakoff <gray@gnu.org>2019-05-23 10:08:08 (GMT)
commitbd19f38853dad5a89abada6ee5e7a23c65173894 (patch) (unidiff)
tree57b53cdceeb69db1bb51e8df48eb4f007c6ecb97
parent3ad426f88d274535d7e04e12add72534034ac075 (diff)
downloadpies-bd19f38853dad5a89abada6ee5e7a23c65173894.tar.gz
pies-bd19f38853dad5a89abada6ee5e7a23c65173894.tar.bz2
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.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--src/comp.c113
-rw-r--r--src/depmap.c40
-rw-r--r--src/pies.h6
-rw-r--r--tests/Makefile.am1
-rw-r--r--tests/atlocal.in6
-rw-r--r--tests/cyclic.at114
-rw-r--r--tests/testsuite.at2
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)
127 for (i = 0; i < comp_count; i++) 127 for (i = 0; i < comp_count; i++)
128 if (comp_array[i] && strcmp (comp_array[i]->tag, tag) == 0) 128 if (strcmp (comp_array[i]->tag, tag) == 0)
129 return i; 129 return i;
@@ -390,16 +390,35 @@ list_str_cmp (const void *a, const void *b)
390 390
391/* Report cyclic dependency starting at IDX. Mark each element with
392 CF_REMOVE for subsequent removal.
393 DP is a transitive closure of depmap.
394*/
391static void 395static void
392component_log_dep (size_t idx) 396report_cyclic_dependency (pies_depmap_t dp, size_t idx)
393{ 397{
394 pies_depmap_pos_t pos; 398 size_t i;
395 size_t n;
396 399
397 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag); 400 i = idx;
398 for (n = depmap_first (depmap, depmap_col, idx, &pos); 401 do
399 n != (size_t)-1;
400 n = depmap_next (depmap, pos))
401 { 402 {
402 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag); 403 size_t n;
404 pies_depmap_pos_t pos;
405
406 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag);
407 comp_array[i]->flags |= CF_REMOVE;
408 for (n = depmap_first (depmap, depmap_col, i, &pos);
409 n != (size_t)-1;
410 n = depmap_next (depmap, pos))
411 {
412 if (n == i)
413 continue;
414 if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n))
415 break;
416 }
417 depmap_end (pos);
418
419 if (n == (size_t)-1)
420 break;
421 i = n;
403 } 422 }
404 depmap_end (pos); 423 while (i != idx);
405 logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); 424 logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag);
@@ -408,2 +427,13 @@ component_log_dep (size_t idx)
408void 427void
428comp_array_remove (size_t i)
429{
430 struct component *comp = comp_array[i];
431 if (i < comp_count - 1)
432 memmove (&comp_array[i], &comp_array[i+1],
433 (comp_count - i - 1) * sizeof comp_array[0]);
434 component_free (comp);
435 comp_count--;
436}
437
438void
409component_build_depmap (void) 439component_build_depmap (void)
@@ -415,3 +445,3 @@ component_build_depmap (void)
415 depmap = depmap_alloc (comp_count); 445 depmap = depmap_alloc (comp_count);
416 for (i = 0; i < comp_count; i++) 446 for (i = 0; i < comp_count; )
417 { 447 {
@@ -431,6 +461,4 @@ component_build_depmap (void)
431 comp->tag, tag); 461 comp->tag, tag);
432 component_free (comp); 462 comp_array_remove (i);
433 comp_array[i] = NULL; 463 depmap_remove (depmap, i);
434 depmap_clear_all (depmap, depmap_row, i);
435 depmap_clear_all (depmap, depmap_col, i);
436 continue; 464 continue;
@@ -454,2 +482,4 @@ component_build_depmap (void)
454 } 482 }
483
484 i++;
455 } 485 }
@@ -459,3 +489,3 @@ component_build_depmap (void)
459 for (i = 0; i < comp_count; i++) 489 for (i = 0; i < comp_count; i++)
460 if (depmap_isset (dp, i, i)) 490 if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i))
461 { 491 {
@@ -463,9 +493,15 @@ component_build_depmap (void)
463 comp_array[i]->tag); 493 comp_array[i]->tag);
464 component_log_dep (i); 494 report_cyclic_dependency (dp, i);
465 component_free (comp_array[i]); 495 }
466 comp_array[i] = NULL; 496
467 depmap_clear_all (depmap, depmap_row, i); 497
468 depmap_clear_all (depmap, depmap_col, i); 498 for (i = 0; i < comp_count;)
469 continue; 499 if (comp_array[i]->flags & CF_REMOVE)
500 {
501 comp_array_remove (i);
502 depmap_remove (depmap, i);
470 } 503 }
504 else
505 i++;
506
471 free (dp); 507 free (dp);
@@ -750,5 +786,5 @@ component_get (size_t n)
750void 786void
751components_dump_depmap (void) 787depmap_dump (pies_depmap_t dpm)
752{ 788{
753 size_t i, j, k; 789 size_t i, j;
754 790
@@ -756,20 +792,11 @@ components_dump_depmap (void)
756 printf (" "); 792 printf (" ");
757 for (i = k = 0; i < comp_count; i++) 793 for (i = 0; i < comp_count; i++)
758 if (comp_array[i]) 794 printf (" %2lu", (unsigned long)i);
759 {
760 printf (" %2lu", (unsigned long)k);
761 k++;
762 }
763 printf ("\n"); 795 printf ("\n");
764 for (i = k = 0; i < comp_count; i++) 796 for (i = 0; i < comp_count; i++)
765 { 797 {
766 if (comp_array[i]) 798 printf ("%2lu", (unsigned long)i);
767 { 799 for (j = 0; j < comp_count; j++)
768 printf ("%2lu ", (unsigned long)k); 800 printf (" %c", depmap_isset (dpm, i, j) ? 'X' : ' ');
769 for (j = 0; j < comp_count; j++) 801 printf ("\n");
770 if (comp_array[j])
771 printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' ');
772 printf ("\n");
773 k++;
774 }
775 } 802 }
@@ -781,2 +808,8 @@ components_dump_depmap (void)
781void 808void
809components_dump_depmap (void)
810{
811 depmap_dump (depmap);
812}
813
814void
782component_trace (size_t idx, enum pies_depmap_direction dir) 815component_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
83{ 83{
84 size_t nrows; 84 size_t nrows; /* Number of rows (== number of mapped elements) */
85 size_t rowlen; 85 size_t rowlen; /* Length of a row in words */
86 unsigned r[1]; 86 unsigned r[1]; /* Data rows */
87}; 87};
@@ -99,2 +99,9 @@ depmap_alloc (size_t count)
99 99
100/* Return size of a depmap row in bytes */
101static inline size_t
102depmap_row_size (pies_depmap_t dpm)
103{
104 return dpm->rowlen * sizeof (unsigned);
105}
106
100pies_depmap_t 107pies_depmap_t
@@ -103,3 +110,3 @@ depmap_copy (pies_depmap_t dpm)
103 pies_depmap_t copy = depmap_alloc (dpm->nrows); 110 pies_depmap_t copy = depmap_alloc (dpm->nrows);
104 memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned)); 111 memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm));
105 return copy; 112 return copy;
@@ -176,19 +183,20 @@ depmap_end (pies_depmap_pos_t pos)
176 183
184/* Remove nth row and column from the map */
177void 185void
178depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, 186depmap_remove (pies_depmap_t dmap, size_t n)
179 size_t coord)
180{ 187{
181 size_t i; 188 if (n < dmap->nrows - 1)
182
183 switch (dir)
184 { 189 {
185 case depmap_row: 190 size_t i, j;
186 for (i = 0; i < dmap->nrows; i++) 191
187 depmap_clear (dmap, coord, i); 192 /* Remove nth row */
188 break; 193 memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1),
189 194 (dmap->nrows - n - 1) * depmap_row_size (dmap));
190 case depmap_col: 195 /* Renumber all columns j >= n: j = j - 1 */
191 for (i = 0; i < dmap->nrows; i++) 196 for (i = 0; i < dmap->nrows; i++)
192 depmap_clear (dmap, i, coord); 197 for (j = n; j < dmap->nrows - 1; j++)
198 (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear)
199 (dmap, i, j);
193 } 200 }
201 dmap->nrows--;
194} 202}
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
201 201
202#define CF_REMOVE 0x400 /* Marked for removal */
203
202#define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS)) 204#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);
376void depmap_clear (pies_depmap_t dmap, size_t row, size_t col); 378void depmap_clear (pies_depmap_t dmap, size_t row, size_t col);
377 379void depmap_remove (pies_depmap_t dmap, size_t n);
378void depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir,
379 size_t coord);
380 380
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 = \
43 control.at\ 43 control.at\
44 cyclic.at\
44 respawn.at\ 45 respawn.at\
diff --git a/tests/atlocal.in b/tests/atlocal.in
index 2ba1462..9069bbd 100644
--- a/tests/atlocal.in
+++ b/tests/atlocal.in
@@ -2,3 +2,3 @@
2# Configurable variable values for GNU Pies test suite. 2# Configurable variable values for GNU Pies test suite.
3# Copyright (C) 2016-2017 Sergey Poznyakoff 3# Copyright (C) 2016-2019 Sergey Poznyakoff
4 4
@@ -6 +6,5 @@ PATH=@abs_builddir@:@abs_top_builddir@/src:$srcdir:$PATH
6XFAILFILE=$abs_builddir/.badversion 6XFAILFILE=$abs_builddir/.badversion
7
8trimws() {
9 sed 's/[ ][ ]*$//'
10}
diff --git a/tests/cyclic.at b/tests/cyclic.at
new file mode 100644
index 0000000..27da22e
--- a/dev/null
+++ b/tests/cyclic.at
@@ -0,0 +1,114 @@
1# This file is part of GNU pies testsuite. -*- Autotest -*-
2# Copyright (C) 2019 Sergey Poznyakoff
3#
4# GNU pies is free software; you can redistribute it and/or modify
5# it under the terms of the GNU General Public License as published by
6# the Free Software Foundation; either version 3, or (at your option)
7# any later version.
8#
9# GNU pies is distributed in the hope that it will be useful,
10# but WITHOUT ANY WARRANTY; without even the implied warranty of
11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12# GNU General Public License for more details.
13#
14# You should have received a copy of the GNU General Public License
15# along with GNU pies. If not, see <http://www.gnu.org/licenses/>.
16
17AT_SETUP([Detecting cyclic dependencies])
18AT_CHECK([
19PIES_XFAIL_CHECK
20# The following matrices describe the test.conf configuration file below.
21#
22# Dependency matrix:
23# 0 1 2 3 4 5 6 7
24# 0 X X
25# 1 X
26# 2 X
27# 3 X
28# 4 X
29# 5
30# 6 X
31# 7
32#
33# Transitive closure:
34# 0 1 2 3 4 5 6 7
35# 0 X X X X X
36# 1 X
37# 2 X X X X X
38# 3 X X X X X
39# 4 X X X X X
40# 5
41# 6 X
42# 7
43#
44# Legend:
45# 0: a
46# 1: b
47# 2: c
48# 3: d
49# 4: e
50# 5: f
51# 6: g
52# 7: h
53
54AT_DATA([test.conf],
55[component a {
56 command "a";
57 prerequisites (b,d);
58}
59
60component b {
61 command "b";
62 prerequisites (b);
63}
64
65component c {
66 command "c";
67 prerequisites (e);
68}
69
70component d {
71 command "d";
72 prerequisites (c);
73}
74
75component e {
76 command "e";
77 prerequisites (a);
78}
79
80component f {
81 command "f";
82}
83
84component g {
85 command "g";
86 prerequisites (h);
87}
88
89component h {
90 command "h";
91}
92])
93
94pies --config-file test.conf --dump-depmap | trimws
95],
96[0],
97[Dependency map:
98 0 1 2
99 0
100 1 X
101 2
102
103Legend:
104 0: f
105 1: g
106 2: h
107],
108[pies: component a depends on itself
109pies: a -> d -> c -> e -> a
110pies: component b depends on itself
111pies: b -> b
112])
113
114AT_CLEANUP
diff --git a/tests/testsuite.at b/tests/testsuite.at
index 152b77f..7f4e7b8 100644
--- a/tests/testsuite.at
+++ b/tests/testsuite.at
@@ -60,2 +60,4 @@ m4_include([version.at])
60m4_include([control.at]) 60m4_include([control.at])
61AT_BANNER([Dependencies])
62m4_include([cyclic.at])
61AT_BANNER([Components]) 63AT_BANNER([Components])

Return to:

Send suggestions and report system problems to the System administrator.