line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
# You may distribute under the terms of either the GNU General Public License |
2
|
|
|
|
|
|
|
# or the Artistic License (the same terms as Perl itself) |
3
|
|
|
|
|
|
|
# |
4
|
|
|
|
|
|
|
# (C) Paul Evans, 2020 -- leonerd@leonerd.org.uk |
5
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
|
package Devel::MAT::ToolBase::GraphWalker 0.51; |
7
|
|
|
|
|
|
|
|
8
|
5
|
|
|
5
|
|
64
|
use v5.14; |
|
5
|
|
|
|
|
15
|
|
9
|
5
|
|
|
5
|
|
33
|
use warnings; |
|
5
|
|
|
|
|
12
|
|
|
5
|
|
|
|
|
155
|
|
10
|
5
|
|
|
5
|
|
32
|
use base qw( Devel::MAT::Tool ); |
|
5
|
|
|
|
|
11
|
|
|
5
|
|
|
|
|
598
|
|
11
|
5
|
|
|
5
|
|
2545
|
use utf8; |
|
5
|
|
|
|
|
61
|
|
|
5
|
|
|
|
|
31
|
|
12
|
|
|
|
|
|
|
|
13
|
5
|
|
|
5
|
|
169
|
use List::Util qw( any pairs ); |
|
5
|
|
|
|
|
10
|
|
|
5
|
|
|
|
|
331
|
|
14
|
5
|
|
|
5
|
|
31
|
use List::UtilsBy qw( nsort_by ); |
|
5
|
|
|
|
|
10
|
|
|
5
|
|
|
|
|
2818
|
|
15
|
|
|
|
|
|
|
|
16
|
|
|
|
|
|
|
my %STRENGTH_ORDER = ( |
17
|
|
|
|
|
|
|
strong => 1, |
18
|
|
|
|
|
|
|
weak => 2, |
19
|
|
|
|
|
|
|
indirect => 3, |
20
|
|
|
|
|
|
|
inferred => 4, |
21
|
|
|
|
|
|
|
); |
22
|
|
|
|
|
|
|
|
23
|
|
|
|
|
|
|
my $next_id; |
24
|
|
|
|
|
|
|
my %id_for; |
25
|
|
|
|
|
|
|
my %seen; |
26
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
sub reset |
28
|
|
|
|
|
|
|
{ |
29
|
0
|
|
|
0
|
0
|
0
|
$next_id = "A"; |
30
|
0
|
|
|
|
|
0
|
undef %id_for; |
31
|
0
|
|
|
|
|
0
|
undef %seen; |
32
|
|
|
|
|
|
|
} |
33
|
|
|
|
|
|
|
|
34
|
|
|
|
|
|
|
sub walk_graph |
35
|
|
|
|
|
|
|
{ |
36
|
5
|
|
|
5
|
0
|
37
|
my $self = shift; |
37
|
5
|
|
|
|
|
11
|
my ( $node, @args ) = @_; |
38
|
|
|
|
|
|
|
|
39
|
5
|
|
|
|
|
12
|
my $addr = $node->addr; |
40
|
5
|
|
|
|
|
17
|
my @roots = $node->roots; |
41
|
5
|
|
|
|
|
18
|
my @edges = $node->edges_in; |
42
|
|
|
|
|
|
|
|
43
|
5
|
50
|
66
|
|
|
22
|
if( !@roots and !@edges ) { |
44
|
0
|
|
|
|
|
0
|
$self->on_walk_nothing( $node, @args ); |
45
|
0
|
|
|
|
|
0
|
return; |
46
|
|
|
|
|
|
|
} |
47
|
|
|
|
|
|
|
|
48
|
5
|
50
|
66
|
|
|
64
|
if( @roots == 1 and $roots[0] eq "EDEPTH" ) { |
49
|
0
|
|
|
|
|
0
|
$self->on_walk_EDEPTH( $node, @args ); |
50
|
0
|
|
|
|
|
0
|
return; |
51
|
|
|
|
|
|
|
} |
52
|
|
|
|
|
|
|
|
53
|
|
|
|
|
|
|
# Don't bother showing any non-root edges if we have a strong root |
54
|
5
|
100
|
|
3
|
|
56
|
@edges = () if any { $_->strength eq "strong" } @roots; |
|
3
|
|
|
|
|
10
|
|
55
|
|
|
|
|
|
|
|
56
|
5
|
50
|
66
|
|
|
50
|
if( @edges > 0 and $seen{$addr} ) { |
57
|
0
|
|
|
|
|
0
|
my $cyclic = $seen{$addr} == 1; |
58
|
0
|
|
|
|
|
0
|
my $id = $id_for{$addr}; |
59
|
|
|
|
|
|
|
|
60
|
0
|
|
|
|
|
0
|
$self->on_walk_again( $node, $cyclic, $id, @args ); |
61
|
0
|
|
|
|
|
0
|
return; |
62
|
|
|
|
|
|
|
} |
63
|
|
|
|
|
|
|
|
64
|
5
|
|
|
|
|
14
|
$seen{$addr}++; |
65
|
|
|
|
|
|
|
|
66
|
5
|
|
|
|
|
15
|
foreach my $idx ( 0 .. $#roots ) { |
67
|
3
|
|
|
|
|
7
|
my $root = $roots[$idx]; |
68
|
3
|
|
33
|
|
|
12
|
my $isfinal = $idx == $#roots && !@edges; |
69
|
|
|
|
|
|
|
|
70
|
3
|
|
|
|
|
12
|
$self->on_walk_root( $node, $root, $isfinal, @args ); |
71
|
|
|
|
|
|
|
} |
72
|
|
|
|
|
|
|
|
73
|
5
|
|
|
4
|
|
85
|
my @refs = nsort_by { $STRENGTH_ORDER{$_->[0]->strength} } pairs @edges; |
|
4
|
|
|
|
|
45
|
|
74
|
5
|
|
|
|
|
69
|
foreach my $idx ( 0 .. $#refs ) { |
75
|
4
|
|
|
|
|
6
|
my ( $ref, $refnode ) = @{ $refs[$idx] }; |
|
4
|
|
|
|
|
13
|
|
76
|
4
|
|
|
|
|
9
|
my $is_final = $idx == $#refs; |
77
|
|
|
|
|
|
|
|
78
|
4
|
|
|
|
|
10
|
my $ref_id; |
79
|
4
|
50
|
66
|
|
|
12
|
if( $refnode->edges_out > 1 and not $refnode->roots and not $id_for{$refnode->addr} ) { |
|
|
|
33
|
|
|
|
|
80
|
0
|
|
|
|
|
0
|
$ref_id = $id_for{$refnode->addr} = $next_id++; |
81
|
|
|
|
|
|
|
} |
82
|
|
|
|
|
|
|
|
83
|
4
|
|
|
|
|
14
|
my @subargs = |
84
|
|
|
|
|
|
|
$self->on_walk_ref( $node, $ref, $refnode->sv, $ref_id, $is_final, @args ); |
85
|
|
|
|
|
|
|
|
86
|
4
|
50
|
|
|
|
15
|
if( $refnode->addr == $addr ) { |
87
|
0
|
|
|
|
|
0
|
$self->on_walk_itself( $node, @subargs ); |
88
|
|
|
|
|
|
|
} |
89
|
|
|
|
|
|
|
else { |
90
|
4
|
|
|
|
|
22
|
$self->walk_graph( $refnode, @subargs ); |
91
|
|
|
|
|
|
|
} |
92
|
|
|
|
|
|
|
} |
93
|
|
|
|
|
|
|
|
94
|
5
|
|
|
|
|
28
|
$seen{$addr}++; |
95
|
|
|
|
|
|
|
} |
96
|
|
|
|
|
|
|
|
97
|
|
|
|
|
|
|
0x55AA; |