blib/lib/Algorithm/ConstructDFA/XS.pm

filter: Statementstmt 94.6% 107 / 113 Branchbran 75.0% 27 / 36 Conditioncond 56.0% 14 / 25 MC/DCmcdc 6.2% 1 / 16 Subroutinesub 92.3% 12 / 13 Podpod 100% 1 / 1 totaltotal 79.4% 162 / 204 CC 35 SCAR 27.5
CC
35
Cov
85%
construct_dfa_xs
27.9
_construct_dfa_xs
11.0
__ANON__
3.0
CRAP 15.6
↑ Summary ConstructDFA.xs »
1 package Algorithm::ConstructDFA::XS;
2
3 5 ▶use 5.012000;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 5 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 5 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
6 5 ▶use Data::AutoBimap;
Subroutine BEGIN: called CC=1 SCAR=0.0
7 5 ▶use Storable;
Subroutine BEGIN: called CC=1 SCAR=0.0
8
9 5 require Exporter;
10
11 5 our @ISA = qw(Exporter);
12
13 5 our %EXPORT_TAGS = ( 'all' => [ qw(
14 construct_dfa_xs
15 ) ] );
16
17 5 our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
18
19 5 our @EXPORT = qw(
20 construct_dfa_xs
21 );
22
23 5 our $VERSION = '0.23';
24
25 5 require XSLoader;
26 5 XSLoader::load('Algorithm::ConstructDFA::XS', $VERSION);
27
28 86 ▶sub construct_dfa_xs {
Subroutine construct_dfa_xs: called CC=21 SCAR=33.3
Pod documented
29 86 my (%o) = @_;
30
31 86 ▶ die unless ref $o{is_nullable};
Branch: 1 branch
BranchTrueFalseTotal
unless ref $o{"is_nullable"} 0 86 86
32 86 ▶ die unless ref $o{is_accepting} or exists $o{final};
Branch: 1 branch
BranchTrueFalseTotal
unless ref $o{"is_accepting"} or exists $o{"final"} 0 86 86
Condition33%1/3
ref $o{"is_accepting"} or exists $o{"final"}
l!l&&r!l&&!r
8600
MC/DC0%0/2
ref $o{"is_accepting"} or exists $o{"final"}
ref $o{"is_accepting"} exists $o{"final"}
Truth table33%1/3
A or B
A= ref $o{"is_accepting"}B= exists $o{"final"}
ABresult
1X1
011
000
33 86 ▶ die unless ref $o{successors} or ref $o{edges_from};
Branch: 1 branch
BranchTrueFalseTotal
unless ref $o{"successors"} or ref $o{"edges_from"} 0 86 86
Condition66%2/3
ref $o{"successors"} or ref $o{"edges_from"}
l!l&&r!l&&!r
57290
MC/DC0%0/2
ref $o{"successors"} or ref $o{"edges_from"}
ref $o{"successors"} ref $o{"edges_from"}
Truth table66%2/3
A or B
A= ref $o{"successors"}B= ref $o{"edges_from"}
ABresult
1X1
011
000
34 86 ▶ die unless ref $o{get_label} or ref $o{edges_from};
Branch: 1 branch
BranchTrueFalseTotal
unless ref $o{"get_label"} or ref $o{"edges_from"} 0 86 86
Condition66%2/3
ref $o{"get_label"} or ref $o{"edges_from"}
l!l&&r!l&&!r
57290
MC/DC0%0/2
ref $o{"get_label"} or ref $o{"edges_from"}
ref $o{"get_label"} ref $o{"edges_from"}
Truth table66%2/3
A or B
A= ref $o{"get_label"}B= ref $o{"edges_from"}
ABresult
1X1
011
000
35 86 ▶ die unless exists $o{start} or exists $o{many_start};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $o{"start"} or exists $o{"many_start"} 0 86 86
Condition33%1/3
exists $o{"start"} or exists $o{"many_start"}
l!l&&r!l&&!r
8600
MC/DC0%0/2
exists $o{"start"} or exists $o{"many_start"}
exists $o{"start"} exists $o{"many_start"}
Truth table33%1/3
A or B
A= exists $o{"start"}B= exists $o{"many_start"}
ABresult
1X1
011
000
36 86 ▶ die if ref $o{is_accepting} and exists $o{final};
Branch: 1 branch
BranchTrueFalseTotal
if ref $o{"is_accepting"} and exists $o{"final"} 0 86 86
Condition33%1/3
ref $o{"is_accepting"} and exists $o{"final"}
!ll&&!rl&&r
0860
MC/DC0%0/2
ref $o{"is_accepting"} and exists $o{"final"}
ref $o{"is_accepting"} exists $o{"final"}
Truth table33%1/3
A and B
A= ref $o{"is_accepting"}B= exists $o{"final"}
ABresult
0X0
100
111
37 86 ▶ die if ref $o{successors} and exists $o{edges_from};
Branch: 1 branch
BranchTrueFalseTotal
if ref $o{"successors"} and exists $o{"edges_from"} 0 86 86
Condition66%2/3
ref $o{"successors"} and exists $o{"edges_from"}
!ll&&!rl&&r
29570
MC/DC0%0/2
ref $o{"successors"} and exists $o{"edges_from"}
ref $o{"successors"} exists $o{"edges_from"}
Truth table66%2/3
A and B
A= ref $o{"successors"}B= exists $o{"edges_from"}
ABresult
0X0
100
111
38 86 ▶ die if ref $o{get_label} and ref $o{edges_from};
Branch: 1 branch
BranchTrueFalseTotal
if ref $o{"get_label"} and ref $o{"edges_from"} 0 86 86
Condition66%2/3
ref $o{"get_label"} and ref $o{"edges_from"}
!ll&&!rl&&r
29570
MC/DC0%0/2
ref $o{"get_label"} and ref $o{"edges_from"}
ref $o{"get_label"} ref $o{"edges_from"}
Truth table66%2/3
A and B
A= ref $o{"get_label"}B= ref $o{"edges_from"}
ABresult
0X0
100
111
39
40 86 my $class = 'Algorithm::ConstructDFA::XS::Synth';
41
42 86 ▶ if (exists $o{edges_from}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $o{"edges_from"}) 29 57 86
43
44 29 my $old_accepting = $o{is_accepting};
45 198 ▶ $o{is_accepting} = sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
46 198 my @config = grep { ref $_ ne $class } @_;
47 198 return $old_accepting->(@config);
48 29 };
49
50 569 ▶ $o{get_label} = sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
51 569 my ($src) = @_;
52 569 ▶ return unless ref $src eq $class;
Branch: 1 branch
BranchTrueFalseTotal
unless ref $src eq $class 184 385 569
53 385 return (Storable::thaw($$src))->[1];
54 29 };
55
56 29 my $old_nullable = $o{is_nullable};
57 569 ▶ $o{is_nullable} = sub {
Subroutine __ANON__: called CC=2 SCAR=6.9
58 569 my ($src) = @_;
59
60 569 ▶ if (ref $src eq $class) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $src eq $class) 385 184 569
61 385 my $deref = $$src;
62 385 my $thawed = Storable::thaw $deref;
63 385 return not defined $thawed->[1];
64 }
65
66 184 $old_nullable->($src);
67 29 };
68
69 29 my $old_edges_from = $o{edges_from};
70
71 569 ▶ $o{successors} = sub {
Subroutine __ANON__: called CC=3 SCAR=11.0
72 569 my ($src) = @_;
73
74 569 ▶ if (ref $src eq $class) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $src eq $class) 385 184 569
75 385 return (Storable::thaw $$src)->[2];
76 }
77
78 184 my @successors;
79
80 184 for my $edge ($old_edges_from->($src)) {
81 385 my ($dst, $label) = @$edge;
82
83 # TODO: theoretically there could be name clashes between the
84 # artificial vertex created here and vertices in the original
85 # unwrapped input which can interfere with the bimaps mapping
86 # stringified vertices to numbers.
87 385 push @successors, bless \(Storable::freeze([$src, $label, $dst])),
88 $class;
89 }
90
91 184 return @successors;
92 29 };
93
94 }
95
96 86 ▶ if (exists $o{final}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $o{"final"}) 0 86 86
97 0 my %in_final = map { $_ => 1 } @{ $o{final} };
98 0 ▶ $o{is_accepting} = sub {
Subroutine __ANON__: not called CC=1 SCAR=6.9
99 0 grep { $in_final{$_} } @_
100 0 };
101 }
102
103 86 ▶ $o{many_start} //= [$o{start}];
Condition50%1/2
$o{"many_start"} //= [$o{"start"}]
l!l
086
MC/DC0%0/1
$o{"many_start"} //= [$o{"start"}]
$o{"many_start"}
Truth table50%1/2
A
A= $o{"many_start"}
Aresult
11
00
104
105 my $dfa = _construct_dfa_xs($o{many_start}, $o{get_label},
106 86 $o{is_nullable}, $o{successors}, $o{is_accepting});
107
108 86 ▶ if (exists $o{edges_from}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $o{"edges_from"}) 29 57 86
109 29 for (values %$dfa) {
110 $_->{Combines} = [ grep {
111 1086 ref $_ ne $class;
112 198 } @{ $_->{Combines} } ];
113 }
114 }
115
116 86 return $dfa;
117 }
118
119 86 ▶sub _construct_dfa_xs {
Subroutine _construct_dfa_xs: called CC=11 SCAR=24.0
120 86 my ($roots, $labelf, $nullablef, $successorsf, $acceptingf) = @_;
121
122 86 my @todo = map { @$_ } @$roots;
123 86 my %seen;
124 my @args;
125 86 my $sm = Data::AutoBimap->new;
126 86 my $rm = Data::AutoBimap->new;
127 86 my %is_start;
128
129 86 ▶ for (my $ix = 0; $ix < @$roots; ++$ix) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ix < @$roots) 86 86 172
130 86 for my $v (@{ $roots->[$ix] }) {
131 111 push @{ $is_start{$v} }, $ix + 1;
132 }
133 }
134
135 86 ▶ while (@todo) {
Branch: 1 branch
BranchTrueFalseTotal
if (@todo) 2196 86 2282
136 2196 my $c = pop @todo;
137
138 2196 ▶ next if $seen{$c}++;
Branch: 1 branch
BranchTrueFalseTotal
if $seen{$c}++ 984 1212 2196
139
140 1212 my $is_nullable = !!$nullablef->($c);
141 1212 my $label = $labelf->($c);
142 1212 ▶ my $label_x = defined $label ? $rm->s2n($label) : undef;
Branch: 1 branch
BranchTrueFalseTotal
defined $label ? : 939 273 1212
143
144 # [vertex, label, nullable, start, successors...]
145 1212 ▶ my @data = ($sm->s2n($c), $label_x, !!$is_nullable, $is_start{$c} // []);
Condition100%2/2
$is_start{$c} // []
l!l
1111101
MC/DC100%1/1
$is_start{$c} // []
$is_start{$c}
Truth table100%2/2
A
A= $is_start{$c}
Aresult
11
00
146
147 1212 for ($successorsf->($c)) {
148 2085 push @data, $sm->s2n($_);
149 2085 push @todo, $_;
150 }
151
152 1212 push @args, \@data;
153 }
154
155 868 ▶ my %h = _internal_construct_dfa_xs(sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
156 868 !!$acceptingf->(map { $sm->n2s($_) } @_)
157 86 }, \@args);
158
159 86 for (values %h) {
160 825 $_->{Combines} = [ map { $sm->n2s($_) } @{ $_->{Combines} } ];
161 }
162
163 86 for my $v (values %h) {
164 825 my $over = {};
165 825 $over->{ $rm->n2s($_) } = $v->{NextOver}{$_} for keys %{ $v->{NextOver} };
166 825 $v->{NextOver} = $over;
167 }
168
169 86 return \%h;
170 }
171
172 5 1;
173
174 __END__
↑ Summary ConstructDFA.xs »