diff options
author | Sergey Poznyakoff <gray@gnu.org> | 2020-10-18 22:20:16 +0300 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org> | 2020-10-18 22:20:16 +0300 |
commit | c26297063aa2dad0fecd28791a47a8bffcfc9925 (patch) | |
tree | 964990a4dd3c62bf0f25f248518b729403eb3c1a /src/comp.c | |
parent | a7f3e6adb0ffbe56d9b521522d22cf758ee6acb7 (diff) | |
download | pies-c26297063aa2dad0fecd28791a47a8bffcfc9925.tar.gz pies-c26297063aa2dad0fecd28791a47a8bffcfc9925.tar.bz2 |
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.
Diffstat (limited to 'src/comp.c')
-rw-r--r-- | src/comp.c | 80 |
1 files changed, 32 insertions, 48 deletions
@@ -403,44 +403,24 @@ list_str_cmp (const void *a, const void *b) | |||
403 | DP is a transitive closure of depmap. | 403 | DP is a transitive closure of depmap. |
404 | */ | 404 | */ |
405 | static void | 405 | static void |
406 | report_cyclic_dependency (pies_depmap_t dp, size_t idx) | 406 | report_cyclic_dependency (struct depmap_path *path) |
407 | { | 407 | { |
408 | size_t i; | 408 | struct depmap_path_elem *p; |
409 | 409 | for (p = path->head; p; p = p->next) | |
410 | i = idx; | ||
411 | do | ||
412 | { | 410 | { |
413 | size_t n; | 411 | logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[p->idx]->tag); |
414 | pies_depmap_pos_t pos; | 412 | comp_array[p->idx]->flags |= CF_REMOVE; |
415 | |||
416 | logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag); | ||
417 | comp_array[i]->flags |= CF_REMOVE; | ||
418 | for (n = depmap_first (depmap, depmap_col, i, &pos); | ||
419 | n != (size_t)-1; | ||
420 | n = depmap_next (depmap, pos)) | ||
421 | { | ||
422 | if (n == i) | ||
423 | continue; | ||
424 | if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n)) | ||
425 | break; | ||
426 | } | ||
427 | depmap_end (pos); | ||
428 | |||
429 | if (n == (size_t)-1) | ||
430 | break; | ||
431 | i = n; | ||
432 | } | 413 | } |
433 | while (i != idx); | 414 | logmsg_printf (LOG_NOTICE, "%s\n", comp_array[path->head->idx]->tag); |
434 | logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); | ||
435 | } | 415 | } |
436 | 416 | ||
437 | void | 417 | void |
438 | component_build_depmap (void) | 418 | component_build_depmap (void) |
439 | { | 419 | { |
440 | size_t i; | 420 | struct depmap_path *path; |
441 | pies_depmap_t dp; | 421 | int i; |
442 | 422 | ||
443 | free (depmap); | 423 | depmap_free (depmap); |
444 | depmap = depmap_alloc (comp_count); | 424 | depmap = depmap_alloc (comp_count); |
445 | for (i = 0; i < comp_count; ) | 425 | for (i = 0; i < comp_count; ) |
446 | { | 426 | { |
@@ -482,24 +462,22 @@ component_build_depmap (void) | |||
482 | i++; | 462 | i++; |
483 | } | 463 | } |
484 | 464 | ||
485 | dp = depmap_copy (depmap); | 465 | path = depmap_cycle_detect (depmap); |
486 | depmap_tc (dp); | 466 | if (path) |
487 | for (i = 0; i < comp_count; i++) | 467 | { |
488 | if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i)) | 468 | struct depmap_path *p; |
489 | { | 469 | |
490 | logmsg (LOG_ERR, _("component %s depends on itself"), | 470 | logmsg (LOG_ERR, "%s", _("cyclic dependencies detected:")); |
491 | comp_array[i]->tag); | 471 | for (p = path; p; p = p->next) |
492 | report_cyclic_dependency (dp, i); | 472 | report_cyclic_dependency (p); |
493 | } | 473 | depmap_path_free (path); |
494 | 474 | ||
495 | 475 | for (i = 0; i < comp_count;) | |
496 | for (i = 0; i < comp_count;) | 476 | if (comp_array[i]->flags & CF_REMOVE) |
497 | if (comp_array[i]->flags & CF_REMOVE) | 477 | comp_array_remove (i); |
498 | comp_array_remove (i); | 478 | else |
499 | else | 479 | i++; |
500 | i++; | 480 | } |
501 | |||
502 | free (dp); | ||
503 | } | 481 | } |
504 | 482 | ||
505 | void | 483 | void |
@@ -806,6 +784,12 @@ depmap_dump (pies_depmap_t dpm) | |||
806 | { | 784 | { |
807 | size_t i, j; | 785 | size_t i, j; |
808 | 786 | ||
787 | if (depmap_dim (dpm) == 0) | ||
788 | { | ||
789 | printf ("%s\n", _("No components defined")); | ||
790 | return; | ||
791 | } | ||
792 | |||
809 | printf ("%s:\n", _("Dependency map")); | 793 | printf ("%s:\n", _("Dependency map")); |
810 | printf (" "); | 794 | printf (" "); |
811 | for (i = 0; i < comp_count; i++) | 795 | for (i = 0; i < comp_count; i++) |