blib/lib/YATT/Lite/Util/CycleDetector.pm

filter: Statementstmt 95.7% 67 / 70 Branchbran 61.1% 11 / 18 Conditioncond 33.3% 1 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 100% 16 / 16 Podpod 0.0% 0 / 9 totaltotal 80.5% 95 / 118 CC 12 SCAR 8.7
CC
12
Cov
87%
check_cycle
4.1
list_cycle
3.8
visit_node
3.1
CRAP 2.4
« blib/lib/YATT/Lite/CLI/GenPerl.pm ↑ Summary blib/lib/YATT/Lite/RegexpNames.pm »
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
BranchTrueFalseTotal
if (grep {$_ eq '';} $dev, $inode) { } 0 637 637
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
BranchTrueFalseTotal
if $vis->{"nodes"}{$vis->fname2id($fname)} 9 193 202
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
BranchTrueFalseTotal
my YATT::Lite::Util::CycleDetector::Node $node = $vis->{"nodes"}{$vis->fname2id($fname)} or croak("No such path in visits! $fname") 178 0 178
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
BranchTrueFalseTotal
if $parent 0 178 178
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
BranchTrueFalseTotal
my YATT::Lite::Util::CycleDetector::Node $node = $vis->{"nodes"}{$vis->fname2id($fname)} or croak("No such path in visits! $fname") 32 0 32
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
BranchTrueFalseTotal
my YATT::Lite::Util::CycleDetector::Node $dest = $vis->{"nodes"}{$vis->fname2id($to)} or croak("No such path in visits! $to") 19 0 19
93 or croak "No such path in visits! $to";
94 19 ▶ if ($dest->{color} == NTYPE_WHITE) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dest->{'color'} == 0) { } 18 1 19
elsif ($dest->{'color'} == 1) { } 1 0 1
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
BranchTrueFalseTotal
if ($node and $node->{"parent"}) 0 1 1
Condition33%1/3
$node and $node->{"parent"}
!ll&&!rl&&r
010
MC/DC0%0/2
$node and $node->{"parent"}
$node $node->{"parent"}
Truth table33%1/3
A and B
A= $nodeB= $node->{"parent"}
ABresult
0X0
100
111
110 0 $node = $node->{parent};
111 0 push @path, $node->{fname};
112 }
113 1 @path;
114 }
115  
116 45 1;
« blib/lib/YATT/Lite/CLI/GenPerl.pm ↑ Summary blib/lib/YATT/Lite/RegexpNames.pm »