| 1 | # -*- coding: utf-8 -*- | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | # This package is used to implement modified version of following algorithm: | ||||||||||||||||||||||||||||
| 4 | # | ||||||||||||||||||||||||||||
| 5 | # http://en.wikipedia.org/wiki/Topological_sorting#CITEREFCormenLeisersonRivestStein2001 | ||||||||||||||||||||||||||||
| 6 | # | ||||||||||||||||||||||||||||
| 7 | # Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; | ||||||||||||||||||||||||||||
| 8 | # Stein, Clifford (2001), | ||||||||||||||||||||||||||||
| 9 | # "Section 22.4: Topological sort", Introduction to Algorithms (2nd ed.), | ||||||||||||||||||||||||||||
| 10 | # MIT Press and McGraw-Hill, pp. 549–552, ISBN 0-262-03293-7. | ||||||||||||||||||||||||||||
| 11 | # | ||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||
| 13 | package YATT::Lite::Util::CycleDetector; | ||||||||||||||||||||||||||||
| 14 | 45 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 15 | 45 | ▶ | use warnings qw(FATAL all NONFATAL misc); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 16 | 45 | ▶ | use Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||||||
| 18 | 45 | ▶ | use Exporter qw/import/; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 19 | 45 | our @EXPORT_OK = qw/Visits/; | |||||||||||||||||||||||||||
| 20 | |||||||||||||||||||||||||||||
| 21 | sub Visits () {__PACKAGE__} | ||||||||||||||||||||||||||||
| 22 | 45 | ▶ | use YATT::Lite::MFields qw/nodes time/; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 23 | |||||||||||||||||||||||||||||
| 24 | use YATT::Lite::Types | ||||||||||||||||||||||||||||
| 25 | 45 | ▶ | ([Node => fields => [qw/fname discovered finished color parent/]]); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 26 | use YATT::Lite::Util::Enum | ||||||||||||||||||||||||||||
| 27 | 45 | ▶ | (NTYPE_ => [qw/WHITE GRAY BLACK/] | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 28 | 45 | , EDGE_ => [qw/TREE BACK FORW CROSS/]); | |||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||
| 30 | 160 | ▶ | sub start { | ||||||||||||||||||||||||||
|
Subroutine
start: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 31 | 160 | my ($pack, $fname) = @_; | |||||||||||||||||||||||||||
| 32 | 160 | my Visits $vis = bless {}, $pack; | |||||||||||||||||||||||||||
| 33 | 160 | $vis->{time} = 0; | |||||||||||||||||||||||||||
| 34 | 160 | $vis->ensure_make_node($fname); | |||||||||||||||||||||||||||
| 35 | 160 | $vis->visit_node($fname); | |||||||||||||||||||||||||||
| 36 | 160 | $vis; | |||||||||||||||||||||||||||
| 37 | } | ||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||
| 39 | 637 | ▶ | sub fname2id { | ||||||||||||||||||||||||||
|
Subroutine
fname2id: called CC=2 SCAR=7.2
Pod
undocumented
| |||||||||||||||||||||||||||||
| 40 | 637 | (my Visits $vis, my $fname) = @_; | |||||||||||||||||||||||||||
| 41 | 637 | my ($dev, $inode) = stat($fname); | |||||||||||||||||||||||||||
| 42 | 637 | ▶ | if (grep {$_ eq ''} $dev, $inode) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 43 | 0 | $fname; # Workaround | |||||||||||||||||||||||||||
| 44 | } else { | ||||||||||||||||||||||||||||
| 45 | 637 | join "_", $dev, $inode; | |||||||||||||||||||||||||||
| 46 | } | ||||||||||||||||||||||||||||
| 47 | } | ||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | 13 | ▶ | sub has_node { | ||||||||||||||||||||||||||
|
Subroutine
has_node: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 50 | 13 | (my Visits $vis, my $fname) = @_; | |||||||||||||||||||||||||||
| 51 | 13 | $vis->{nodes}{$vis->fname2id($fname)}; | |||||||||||||||||||||||||||
| 52 | } | ||||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | 202 | ▶ | sub ensure_make_node { | ||||||||||||||||||||||||||
|
Subroutine
ensure_make_node: called CC=3 SCAR=11.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 55 | 202 | (my Visits $vis, my @path) = @_; | |||||||||||||||||||||||||||
| 56 | 202 | foreach my $fname (@path) { | |||||||||||||||||||||||||||
| 57 | 202 | ▶ | next if $vis->{nodes}{$vis->fname2id($fname)}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 58 | 193 | $vis->make_node($fname); | |||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||
| 60 | 202 | @path; | |||||||||||||||||||||||||||
| 61 | } | ||||||||||||||||||||||||||||
| 62 | |||||||||||||||||||||||||||||
| 63 | 193 | ▶ | sub make_node { | ||||||||||||||||||||||||||
|
Subroutine
make_node: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 64 | 193 | (my Visits $vis, my ($fname)) = @_; | |||||||||||||||||||||||||||
| 65 | 193 | $vis->{nodes}{$vis->fname2id($fname)} = my Node $node = {}; | |||||||||||||||||||||||||||
| 66 | 193 | $node->{fname} = $fname; | |||||||||||||||||||||||||||
| 67 | 193 | $node->{color} = NTYPE_WHITE; | |||||||||||||||||||||||||||
| 68 | 193 | $node; | |||||||||||||||||||||||||||
| 69 | } | ||||||||||||||||||||||||||||
| 70 | |||||||||||||||||||||||||||||
| 71 | 178 | ▶ | sub visit_node { | ||||||||||||||||||||||||||
|
Subroutine
visit_node: called CC=3 SCAR=11.2
Pod
undocumented
| |||||||||||||||||||||||||||||
| 72 | 178 | (my Visits $vis, my ($fname, $parent)) = @_; | |||||||||||||||||||||||||||
| 73 | 178 | ▶ | my Node $node = $vis->{nodes}{$vis->fname2id($fname)} | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 74 | or croak "No such path in visits! $fname"; | ||||||||||||||||||||||||||||
| 75 | 178 | $node->{color} = NTYPE_GRAY; | |||||||||||||||||||||||||||
| 76 | 178 | $node->{discovered} = ++$vis->{time}; | |||||||||||||||||||||||||||
| 77 | 178 | ▶ | $node->{parent} = $vis->{nodes}{$vis->fname2id($parent)} if $parent; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 78 | 178 | $node; | |||||||||||||||||||||||||||
| 79 | } | ||||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | 32 | ▶ | sub finish_node { | ||||||||||||||||||||||||||
|
Subroutine
finish_node: called CC=2 SCAR=7.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 82 | 32 | (my Visits $vis, my $fname) = @_; | |||||||||||||||||||||||||||
| 83 | 32 | ▶ | my Node $node = $vis->{nodes}{$vis->fname2id($fname)} | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 84 | or croak "No such path in visits! $fname"; | ||||||||||||||||||||||||||||
| 85 | 32 | $node->{color} = NTYPE_BLACK; | |||||||||||||||||||||||||||
| 86 | 32 | $node->{finished} = ++$vis->{time}; | |||||||||||||||||||||||||||
| 87 | 32 | $node; | |||||||||||||||||||||||||||
| 88 | } | ||||||||||||||||||||||||||||
| 89 | |||||||||||||||||||||||||||||
| 90 | 19 | ▶ | sub check_cycle { | ||||||||||||||||||||||||||
|
Subroutine
check_cycle: called CC=4 SCAR=14.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 91 | 19 | (my Visits $vis, my ($to, $from)) = @_; | |||||||||||||||||||||||||||
| 92 | 19 | ▶ | my Node $dest = $vis->{nodes}{$vis->fname2id($to)} | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 93 | or croak "No such path in visits! $to"; | ||||||||||||||||||||||||||||
| 94 | 19 | ▶ | if ($dest->{color} == NTYPE_WHITE) { | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 95 | # tree edge | ||||||||||||||||||||||||||||
| 96 | 18 | $vis->visit_node($to); | |||||||||||||||||||||||||||
| 97 | } elsif ($dest->{color} == NTYPE_GRAY) { | ||||||||||||||||||||||||||||
| 98 | # back edge! | ||||||||||||||||||||||||||||
| 99 | 1 | return [$to, $vis->list_cycle($dest)] | |||||||||||||||||||||||||||
| 100 | } else { | ||||||||||||||||||||||||||||
| 101 | # forward or cross | ||||||||||||||||||||||||||||
| 102 | } | ||||||||||||||||||||||||||||
| 103 | 18 | return; | |||||||||||||||||||||||||||
| 104 | } | ||||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||
| 106 | 1 | ▶ | sub list_cycle { | ||||||||||||||||||||||||||
|
Subroutine
list_cycle: called CC=3 SCAR=13.5
Pod
undocumented
| |||||||||||||||||||||||||||||
| 107 | 1 | (my Visits $vis, my Node $node) = @_; | |||||||||||||||||||||||||||
| 108 | 1 | my @path; | |||||||||||||||||||||||||||
| 109 | 1 | ▶ | while ($node and $node->{parent}) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$node and $node->{"parent"}
MC/DC0%0/2
$node and $node->{"parent"}
$node
$node->{"parent"}
Truth table33%1/3
A and B
A= $nodeB= $node->{"parent"}
| |||||||||||||||||||||||||||||
| 110 | 0 | $node = $node->{parent}; | |||||||||||||||||||||||||||
| 111 | 0 | push @path, $node->{fname}; | |||||||||||||||||||||||||||
| 112 | } | ||||||||||||||||||||||||||||
| 113 | 1 | @path; | |||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | |||||||||||||||||||||||||||||
| 116 | 45 | 1; | |||||||||||||||||||||||||||