aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Poznyakoff <gray@gnu.org>2019-05-23 13:08:08 +0300
committerSergey Poznyakoff <gray@gnu.org>2019-05-23 13:08:08 +0300
commitbd19f38853dad5a89abada6ee5e7a23c65173894 (patch)
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.
-rw-r--r--src/comp.c101
-rw-r--r--src/depmap.c38
-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, 215 insertions, 53 deletions
diff --git a/src/comp.c b/src/comp.c
index 17832ad..fcd0a14 100644
--- a/src/comp.c
+++ b/src/comp.c
@@ -125,7 +125,7 @@ component_lookup_index (const char *tag)
125 size_t i; 125 size_t i;
126 126
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;
130 return -1; 130 return -1;
131} 131}
@@ -388,24 +388,54 @@ list_str_cmp (const void *a, const void *b)
388 return safe_strcmp (a, b); 388 return safe_strcmp (a, b);
389} 389}
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)
397{
398 size_t i;
399
400 i = idx;
401 do
393 { 402 {
394 pies_depmap_pos_t pos;
395 size_t n; 403 size_t n;
404 pies_depmap_pos_t pos;
396 405
397 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag); 406 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag);
398 for (n = depmap_first (depmap, depmap_col, idx, &pos); 407 comp_array[i]->flags |= CF_REMOVE;
408 for (n = depmap_first (depmap, depmap_col, i, &pos);
399 n != (size_t)-1; 409 n != (size_t)-1;
400 n = depmap_next (depmap, pos)) 410 n = depmap_next (depmap, pos))
401 { 411 {
402 logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag); 412 if (n == i)
413 continue;
414 if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n))
415 break;
403 } 416 }
404 depmap_end (pos); 417 depmap_end (pos);
418
419 if (n == (size_t)-1)
420 break;
421 i = n;
422 }
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);
406} 425}
407 426
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)
410{ 440{
411 size_t i; 441 size_t i;
@@ -413,7 +443,7 @@ component_build_depmap (void)
413 443
414 free (depmap); 444 free (depmap);
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 {
418 struct component *comp = comp_array[i]; 448 struct component *comp = comp_array[i];
419 struct grecs_list_entry *ep; 449 struct grecs_list_entry *ep;
@@ -429,10 +459,8 @@ component_build_depmap (void)
429 _("component %s depends on %s, " 459 _("component %s depends on %s, "
430 "which is not declared"), 460 "which is not declared"),
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;
437 } 465 }
438 depmap_set (depmap, i, tgt); 466 depmap_set (depmap, i, tgt);
@@ -452,22 +480,30 @@ component_build_depmap (void)
452 } 480 }
453 depmap_set (depmap, tgt, i); 481 depmap_set (depmap, tgt, i);
454 } 482 }
483
484 i++;
455 } 485 }
456 486
457 dp = depmap_copy (depmap); 487 dp = depmap_copy (depmap);
458 depmap_tc (dp); 488 depmap_tc (dp);
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 {
462 logmsg (LOG_ERR, _("component %s depends on itself"), 492 logmsg (LOG_ERR, _("component %s depends on itself"),
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);
472} 508}
473 509
@@ -748,30 +784,21 @@ component_get (size_t n)
748} 784}
749 785
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
755 printf ("%s:\n", _("Dependency map")); 791 printf ("%s:\n", _("Dependency map"));
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 {
766 if (comp_array[i])
767 { 797 {
768 printf ("%2lu ", (unsigned long)k); 798 printf ("%2lu", (unsigned long)i);
769 for (j = 0; j < comp_count; j++) 799 for (j = 0; j < comp_count; j++)
770 if (comp_array[j]) 800 printf (" %c", depmap_isset (dpm, i, j) ? 'X' : ' ');
771 printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' ');
772 printf ("\n"); 801 printf ("\n");
773 k++;
774 }
775 } 802 }
776 printf ("\n%s:\n", _("Legend")); 803 printf ("\n%s:\n", _("Legend"));
777 for (i = 0; i < comp_count; i++) 804 for (i = 0; i < comp_count; i++)
@@ -779,6 +806,12 @@ components_dump_depmap (void)
779} 806}
780 807
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)
783{ 816{
784 pies_depmap_pos_t pos; 817 pies_depmap_pos_t pos;
diff --git a/src/depmap.c b/src/depmap.c
index 3ea5722..cb50548 100644
--- a/src/depmap.c
+++ b/src/depmap.c
@@ -81,9 +81,9 @@ TC (unsigned *R, int n)
81 81
82struct pies_depmap 82struct 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};
88 88
89pies_depmap_t 89pies_depmap_t
@@ -97,11 +97,18 @@ depmap_alloc (size_t count)
97 return dmap; 97 return dmap;
98} 98}
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
101depmap_copy (pies_depmap_t dpm) 108depmap_copy (pies_depmap_t dpm)
102{ 109{
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