| 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
| |||||||||||||||||||||||||||||
| 32 | 86 | ▶ | die unless ref $o{is_accepting} or exists $o{final}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
ref $o{"is_accepting"} or exists $o{"final"}
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"}
| |||||||||||||||||||||||||||||
| 33 | 86 | ▶ | die unless ref $o{successors} or ref $o{edges_from}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
ref $o{"successors"} or ref $o{"edges_from"}
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"}
| |||||||||||||||||||||||||||||
| 34 | 86 | ▶ | die unless ref $o{get_label} or ref $o{edges_from}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
ref $o{"get_label"} or ref $o{"edges_from"}
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"}
| |||||||||||||||||||||||||||||
| 35 | 86 | ▶ | die unless exists $o{start} or exists $o{many_start}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
exists $o{"start"} or exists $o{"many_start"}
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"}
| |||||||||||||||||||||||||||||
| 36 | 86 | ▶ | die if ref $o{is_accepting} and exists $o{final}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
ref $o{"is_accepting"} and exists $o{"final"}
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"}
| |||||||||||||||||||||||||||||
| 37 | 86 | ▶ | die if ref $o{successors} and exists $o{edges_from}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
ref $o{"successors"} and exists $o{"edges_from"}
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"}
| |||||||||||||||||||||||||||||
| 38 | 86 | ▶ | die if ref $o{get_label} and ref $o{edges_from}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
ref $o{"get_label"} and ref $o{"edges_from"}
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"}
| |||||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||
| 40 | 86 | my $class = 'Algorithm::ConstructDFA::XS::Synth'; | |||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||
| 42 | 86 | ▶ | if (exists $o{edges_from}) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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"}]
MC/DC0%0/1
$o{"many_start"} //= [$o{"start"}]
$o{"many_start"}
Truth table50%1/2
A
A= $o{"many_start"}
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 136 | 2196 | my $c = pop @todo; | |||||||||||||||||||||||||||
| 137 | |||||||||||||||||||||||||||||
| 138 | 2196 | ▶ | next if $seen{$c}++; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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} // []
MC/DC100%1/1
$is_start{$c} // []
$is_start{$c}
Truth table100%2/2
A
A= $is_start{$c}
| |||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||