Attean/BindingEqualityTest.pm

filter: Statementstmt 75.6% 180 / 238 Branchbran 56.9% 33 / 58 Conditioncond 100% 2 / 2 MC/DCmcdc 100% 1 / 1 Subroutinesub 82.1% 23 / 28 Podpod 60.0% 3 / 5 totaltotal 72.8% 242 / 332 CC 52 SCAR 26.3
CC
52
Cov
72%
_statement_blank_irisets
56.0
_find_mapping
22.6
__ANON__
20.0
CRAP 13.9
« Attean/API/QueryPlanner.pm ↑ Summary Attean/TreeRewriter.pm »
1 50 ▶use v5.14;
Subroutine BEGIN: called CC=1 SCAR=0.0
2 50 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
3  
4 =head1 NAME
5  
6 Attean::BindingEqualityTest - Test for equality of binding sets with bnode isomorphism
7  
8 =head1 VERSION
9  
10 This document describes Attean::BindingEqualityTest version 0.040
11  
12 =head1 SYNOPSIS
13  
14 use v5.14;
15 use Attean;
16 my $test = Attean::BindingEqualityTest->new();
17 if ($test->equals($iter_a, $iter_b)) {
18 say "Iterators contain equivalent bindings";
19 }
20  
21 =head1 DESCRIPTION
22  
23 ...
24  
25 =head1 METHODS
26  
27 =over 4
28  
29 =cut
30  
31 50 package Attean::BindingEqualityTest::_Iter {
32 0 ▶ sub new {
Subroutine new: not called CC=1 SCAR=6.9
33 0 my $class = shift;
34 0 my @iters = @_;
35 0 my @values = $class->_materialize([], @iters);
36 0 return bless(\@values, $class);
37 }
38
39 0 ▶ sub _materialize {
Subroutine _materialize: not called CC=3 SCAR=24.8
40 0 my $class = shift;
41 0 my $v = shift;
42 0 my @iters = @_;
43 0 ▶ if (scalar(@iters)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @iters) { } 0 0 0
44 0 my $i = shift(@iters);
45 0 my @values;
46 0 ▶ while (my $vv = $i->next) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $vv = $i->next) 0 0 0
47 0 my $prefix = [@$v, @$vv];
48 0 push(@values, $class->_materialize($prefix, @iters));
49 }
50 0 return @values;
51 } else {
52 0 return $v;
53 }
54 }
55
56 0 ▶ sub next {
Subroutine next: not called CC=1 SCAR=6.9
57 0 my $self = shift;
58 0 return shift(@$self);
59 }
60 }
61  
62 50 package Attean::BindingEqualityTest 0.040 {
63 50 ▶ use v5.14;
Subroutine BEGIN: called CC=1 SCAR=0.0
64 50 ▶ use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
65 50 ▶ use Moo;
Subroutine BEGIN: called CC=1 SCAR=0.0
66 50 ▶ use Types::Standard qw(CodeRef ConsumerOf Str);
Subroutine BEGIN: called CC=1 SCAR=0.0
67 50 ▶ use Data::Dumper;
Subroutine BEGIN: called CC=1 SCAR=0.0
68 50 ▶ use Algorithm::Combinatorics qw(permutations);
Subroutine BEGIN: called CC=1 SCAR=0.0
69 50 ▶ use Scalar::Util qw(blessed);
Subroutine BEGIN: called CC=1 SCAR=0.0
70 50 ▶ use List::Util qw(shuffle);
Subroutine BEGIN: called CC=1 SCAR=0.0
71 50 ▶ use Attean::RDF;
Subroutine BEGIN: called CC=1 SCAR=0.0
72 50 ▶ use Digest::MD5 qw(md5_hex);
Subroutine BEGIN: called CC=1 SCAR=0.0
73 50 ▶ use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
74
75 50 with 'MooX::Log::Any';
76
77 50 has error => (is => 'rw', isa => Str, init_arg => undef);
78
79 28 ▶ sub _coerce {
Subroutine _coerce: called CC=3 SCAR=13.3
80 28 my $o = shift;
81 28 ▶ if ($o->does('Attean::API::Model')) {
Branch: 2 branches
BranchTrueFalseTotal
if ($o->does('Attean::API::Model')) { } 0 28 28
elsif ($o->does('Attean::API::Iterator')) { } 28 0 28
82 0 return $o->get_quads;
83 } elsif ($o->does('Attean::API::Iterator')) {
84 28 return $o;
85 }
86 0 return;
87 }
88  
89 =item C<< equals ( $graph1, $graph2 ) >>
90  
91 Returns true if the invocant and $graph represent two equal RDF graphs (e.g.
92 there exists a bijection between the RDF statements of the invocant and $graph).
93  
94 =cut
95  
96 10 ▶ sub equals {
Subroutine equals: called CC=2 SCAR=6.9
Pod documented
97 10 my $self = shift;
98 10 $self->error('');
99 10 ▶ return $self->_check_equality(@_) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$self->_check_equality(@_) ? : 5 5 10
100 }
101  
102 10 ▶ sub _check_equality {
Subroutine _check_equality: called CC=7 SCAR=19.5
103 10 my $self = shift;
104 10 my ($a, $b) = map { _coerce($_) } @_;
105
106 10 my @graphs = ($a, $b);
107 10 my ($ba, $nba) = $self->split_blank_statements($a);
108 10 my ($bb, $nbb) = $self->split_blank_statements($b);
109 10 ▶ if (scalar(@$nba) != scalar(@$nbb)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$nba != scalar @$nbb) 1 9 10
110 1 my $nbac = scalar(@$nba);
111 1 my $nbbc = scalar(@$nbb);
112
113 # warn "====================================================\n";
114 # warn "BindingEqualityTest count of non-blank statements didn't match:\n";
115 # warn "-------- a\n";
116 # foreach my $t (@$nba) {
117 # warn $t->as_string . "\n";
118 # }
119 # warn "-------- b\n";
120 # foreach my $t (@$nbb) {
121 # warn $t->as_string . "\n";
122 # }
123 1 $self->error("count of non-blank statements didn't match ($nbac != $nbbc)");
124 1 return 0;
125 }
126 9 my $bac = scalar(@$ba);
127 9 my $bbc = scalar(@$bb);
128 9 ▶ if ($bac != $bbc) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bac != $bbc) 1 8 9
129 1 $self->error("count of blank statements didn't match ($bac != $bbc)");
130 1 return 0;
131 }
132
133 8 my $mapper = Attean::TermMap->canonicalization_map;
134 8 for ($nba, $nbb) {
135 16 @$_ = sort map { $_->apply_map($mapper)->as_string } @$_;
136 }
137
138 8 foreach my $i (0 .. $#{ $nba }) {
139 5 ▶ unless ($nba->[$i] eq $nbb->[$i]) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($nba->[$i] eq $nbb->[$i]) 2 3 5
140 # warn "====================================================\n";
141 # warn "BindingEqualityTest non-blank statements didn't match:\n";
142 # warn "-------- a\n";
143 # foreach my $t (@$nba) {
144 # warn $t . "\n";
145 # }
146 # warn "-------- b\n";
147 # foreach my $t (@$nbb) {
148 # warn $t . "\n";
149 # }
150 2 ▶ unless ($self->error) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->error) 2 0 2
151 2 $self->error("non-blank triples don't match:\n" . Dumper($nba->[$i], $nbb->[$i]));
152 }
153 2 return 0;
154 }
155 }
156
157 6 return _find_mapping($self, $ba, $bb, 1);
158 }
159  
160 =item C<< is_subgraph_of ( $graph1, $graph2 ) >>
161  
162 Returns true if the invocant is a subgraph of $graph. (i.e. there exists an
163 injection of RDF statements from the invocant to $graph.)
164  
165 =cut
166  
167 1 ▶ sub is_subgraph_of {
Subroutine is_subgraph_of: called CC=2 SCAR=7.1
Pod documented
168 1 my $self = shift;
169 1 $self->error('');
170 1 ▶ return $self->_check_subgraph(@_) ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$self->_check_subgraph(@_) ? : 1 0 1
171 }
172  
173 =item C<< injection_map ( $graph1, $graph2 ) >>
174  
175 If the invocant is a subgraph of $graph, returns a mapping of blank node
176 identifiers from the invocant graph to $graph as a hashref. Otherwise
177 returns false. The solution is not always unique; where there exist multiple
178 solutions, the solution returned is arbitrary.
179  
180 =cut
181  
182 3 ▶ sub injection_map {
Subroutine injection_map: called CC=2 SCAR=7.4
Pod documented
183 3 my $self = shift;
184 3 $self->error('');
185 3 my $map = $self->_check_subgraph(@_);
186 3 ▶ return $map if $map;
Branch: 1 branch
BranchTrueFalseTotal
if $map 3 0 3
187 0 return;
188 }
189  
190 4 ▶ sub _check_subgraph {
Subroutine _check_subgraph: called CC=5 SCAR=18.0
191 4 my $self = shift;
192 4 my ($a, $b) = map { _coerce($_) } @_;
193
194 4 my @graphs = ($a, $b);
195 4 my ($ba, $nba) = $self->split_blank_statements($a);
196 4 my ($bb, $nbb) = $self->split_blank_statements($b);
197
198 4 ▶ if (scalar(@$nba) > scalar(@$nbb)) {
Branch: 2 branches
BranchTrueFalseTotal
if (scalar @$nba > scalar @$nbb) { } 0 4 4
elsif (scalar @$ba > scalar @$bb) { } 0 4 4
199 0 $self->error("invocant had too many blank node statements to be a subgraph of argument");
200 0 return 0;
201 } elsif (scalar(@$ba) > scalar(@$bb)) {
202 0 $self->error("invocant had too many non-blank node statements to be a subgraph of argument");
203 0 return 0;
204 }
205  
206 4 my %NBB = map { $_->as_string => 1 } @$nbb;
207
208 4 foreach my $st (@$nba) {
209 1 ▶ unless ($NBB{ $st->as_string }) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($NBB{$st->as_string}) 0 1 1
210 0 return 0;
211 }
212 }
213
214 4 return _find_mapping($self, $ba, $bb);
215 }
216  
217 0 ▶ sub _statement_blank_irisets {
Subroutine _statement_blank_irisets: not called CC=7 SCAR=40.3
218 0 my $self = shift;
219 0 my @st = @_;
220 0 my %blank_ids_b_iris;
221 0 foreach my $st (@st) {
222 0 my @iris = map { $_->value } grep { $_->does('Attean::API::IRI') } $st->values;
223 0 ▶ unless (scalar(@iris)) {
Branch: 1 branch
BranchTrueFalseTotal
unless (scalar @iris) 0 0 0
224 0 push(@iris, '_');
225 }
226 0 foreach my $n (grep { $_->does('Attean::API::Blank') } $st->values) {
227 0 foreach my $i (@iris) {
228 0 $blank_ids_b_iris{$n->value}{$i}++;
229 }
230 }
231 }
232
233 0 my %iri_blanks;
234 0 foreach my $bid (sort keys %blank_ids_b_iris) {
235 0 my $d = Digest::MD5->new();
236 0 foreach my $iri (sort keys %{ $blank_ids_b_iris{$bid} }) {
237 0 $d->add($iri);
238 }
239 0 $iri_blanks{$d->hexdigest}{$bid}++;
240 }
241 0 return \%iri_blanks;
242 }
243
244 10 ▶ sub _find_mapping {
Subroutine _find_mapping: called CC=19 SCAR=31.2
245 10 my $self = shift;
246 10 my $ba = shift;
247 10 my $bb = shift;
248 10 ▶ my $equal = shift || 0;
Condition100%2/2
shift() || 0
l!l
64
MC/DC100%1/1
shift() || 0
shift()
Truth table100%2/2
A
A= shift()
Aresult
11
00
249  
250 # warn "########### _find_mapping:\n";
251 # warn "============ A\n";
252 # foreach my $t (@$ba) {
253 # warn $t->as_string . "\n";
254 # }
255 # warn "============ B\n";
256 # foreach my $t (@$bb) {
257 # warn $t->as_string . "\n";
258 # }
259  
260 10 ▶ if (scalar(@$ba) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$ba == 0) 2 8 10
261 2 return {};
262 }
263
264 8 my %blank_ids_a;
265 8 foreach my $st (@$ba) {
266 14 foreach my $n ($st->blanks) {
267 18 $blank_ids_a{ $n->value }++;
268 }
269 }
270  
271 8 my %blank_ids_b;
272 8 foreach my $st (@$bb) {
273 16 foreach my $n ($st->blanks) {
274 21 $blank_ids_b{ $n->value }++;
275 }
276 }
277
278
279 8 my (@ka, @kb);
280 8 my $kbp;
281 # if ($equal) {
282 # # if we're testing for equality, and not just finding an injection mapping,
283 # # we can avoid unnecessary work by restricting mappings to those where each
284 # # permutation only maps blank nodes to other blank nodes that appear in
285 # # similar bindings (in this case they appear with all the same IRIs)
286 # my $ba_iri_blanks = $self->_statement_blank_irisets(@$ba);
287 #
288 # my $bb_iri_blanks = $self->_statement_blank_irisets(@$bb);
289 #
290 # my $ba_keys = join('|', sort keys %$ba_iri_blanks);
291 # my $bb_keys = join('|', sort keys %$bb_iri_blanks);
292 # unless ($ba_keys eq $bb_keys) {
293 # $self->error("didn't find blank node mapping\n");
294 # return 0;
295 # }
296 #
297 # my @iters;
298 # foreach my $k (sort keys %$ba_iri_blanks) {
299 # unless (scalar(@{[keys %{ $ba_iri_blanks->{$k} }]}) == scalar(@{[keys %{ $bb_iri_blanks->{$k} }]})) {
300 # $self->error("didn't find blank node mapping\n");
301 # return 0;
302 # }
303 # push(@ka, keys %{ $ba_iri_blanks->{$k} });
304 # push(@kb, keys %{ $bb_iri_blanks->{$k} });
305 # my $i = permutations([keys %{ $bb_iri_blanks->{$k} }]);
306 # push(@iters, $i);
307 # }
308 #
309 # if (scalar(@iters) == 1) {
310 # $kbp = shift(@iters);
311 # } else {
312 # $kbp = Attean::BindingEqualityTest::_Iter->new(@iters);
313 # }
314 # } else {
315 8 @ka = keys %blank_ids_a;
316 8 @kb = keys %blank_ids_b;
317 8 $kbp = permutations( [shuffle @kb] );
318 # }
319
320
321 8 my $canon_map = Attean::TermMap->canonicalization_map;
322 8 my @canon_ba;
323 8 foreach my $st (@$ba) {
324 14 push(@canon_ba, $st->apply_map($canon_map));
325 }
326 8 $ba = \@canon_ba;
327
328 8 my %bb_master;
329 8 foreach my $bb_item (@$bb) {
330 16 my $k = $bb_item->apply_map($canon_map)->as_string;
331 16 $bb_master{ $k }++;
332 }
333 # my %bb_master = map { $_->apply_map($canon_map)->as_string => 1 } @$bb;
334
335 8 my $count = 0;
336 8 my %blank_node_cache;
337 8 foreach my $b (@ka) {
338 14 $blank_node_cache{$b} = Attean::Blank->new($b);
339 }
340 8 foreach my $b (@kb) {
341 15 $blank_node_cache{$b} = Attean::Blank->new($b);
342 }
343
344 8 my ($ba_counts, $should_use) = $self->count_bindings_by_blank($ba);
345 8 my ($bb_counts) = $self->count_bindings_by_blank($bb);
346 8 ▶ my $quick_check_permutation = sub { return 1; };
Subroutine __ANON__: called CC=1 SCAR=0.0
347 8 ▶ if ($should_use) {
Branch: 1 branch
BranchTrueFalseTotal
if ($should_use) 0 8 8
348 0 ▶ $quick_check_permutation = sub {
Subroutine __ANON__: not called CC=4 SCAR=30.0
349 # TODO: quickly rule-out permutations that will not lead to valid solutions
350 0 my $mapping = shift;
351 0 my %mapping_str;
352 0 @mapping_str{ @ka } = @$mapping;
353 0 ▶ if (scalar(@$mapping) > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$mapping > 1) 0 0 0
354 0 foreach my $k (keys %mapping_str) {
355 0 my $a_count = $ba_counts->{ $k };
356 0 my $b_count = $bb_counts->{ $mapping_str{ $k } };
357 0 ▶ unless ($a_count == $b_count) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($a_count == $b_count) 0 0 0
358 # Early rejection of this mapping, because the number of statements this blank node
359 # appears in differs between the lhs and rhs bindings.
360 0 return 0;
361 }
362 }
363 }
364 0 return 1;
365 0 };
366 }
367
368 8 ▶ MAPPING: while (my $mapping = $kbp->next) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $mapping = $kbp->next) 13 1 14
369 13 ▶ next unless $quick_check_permutation->($mapping);
Branch: 1 branch
BranchTrueFalseTotal
unless &$quick_check_permutation($mapping) 0 13 13
370 13 $count++;
371 13 my %mapping_str;
372 13 @mapping_str{ @ka } = @$mapping;
373 my %mapping = map {
374 13 ▶ die unless exists $blank_node_cache{$_};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $blank_node_cache{$_} 0 23 23
375 23 ▶ die unless exists $blank_node_cache{ $mapping_str{$_} };
Branch: 1 branch
BranchTrueFalseTotal
unless exists $blank_node_cache{$mapping_str{$_}} 0 23 23
376 23 $blank_node_cache{$_}->as_string => $blank_node_cache{ $mapping_str{$_} }
377 } (keys %mapping_str);
378 13 my $mapper = Attean::TermMap->rewrite_map(\%mapping);
379 # $self->log->trace("trying mapping: " . Dumper($mapping));
380
381 13 my %bb = %bb_master;
382 13 foreach my $st (@$ba) {
383 21 my $mapped_st = $st->apply_map($mapper)->as_string;
384 # $self->log->trace("checking for '$mapped_st' in " . Dumper(\%bb));
385 21 ▶ if ($bb{ $mapped_st }) {
Branch: 1 branch
BranchTrueFalseTotal
if ($bb{$mapped_st}) { } 15 6 21
386 # $self->log->trace("Found mapping for binding: " . Dumper($mapped_st));
387 15 ▶ if (--$bb{ $mapped_st } == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (--$bb{$mapped_st} == 0) 15 0 15
388 15 delete $bb{ $mapped_st };
389 }
390 } else {
391 # $self->log->trace("No mapping found for binding: " . Dumper($mapped_st));
392 6 next MAPPING;
393 }
394 }
395 # warn "FOUND MAPPING after $count attempts.\n";
396 7 $self->error("found mapping: " . Dumper(\%mapping_str));
397 7 return \%mapping_str;
398 }
399
400 # warn "didn't find blank node mapping:\n";
401 1 $self->error("didn't find blank node mapping\n");
402 1 return 0;
403 }
404  
405 16 ▶ sub count_bindings_by_blank {
Subroutine count_bindings_by_blank: called CC=5 SCAR=16.1
Pod undocumented
406 16 my $self = shift;
407 16 my $bindings = shift;
408 16 my %bindings;
409 16 foreach my $st (@$bindings) {
410 30 ▶ if ($st->has_blanks) {
Branch: 1 branch
BranchTrueFalseTotal
if ($st->has_blanks) 30 0 30
411 30 foreach my $n ($st->blanks) {
412 39 push( @{ $bindings{ $n->value } }, $st );
413 }
414 }
415 }
416 16 my %counts;
417 16 foreach my $k (keys %bindings) {
418 29 $counts{ $k } = scalar(@{ $bindings{ $k } });
419 }
420 16 my %distinct_counts = map { $_ => 1 } (values %counts);
421 16 my @distinct_counts = keys %distinct_counts;
422 16 my $should_use = (scalar(@distinct_counts) > 1);
423 16 return (\%counts, $should_use);
424 }
425 =item C<< split_blank_statements( $iter ) >>
426  
427 Returns two array refs containing bindings from C<< $iter >>, with bindings
428 containing blank nodes and bindings without any blank nodes, respectively.
429  
430 =cut
431  
432 28 ▶ sub split_blank_statements {
Subroutine split_blank_statements: called CC=4 SCAR=13.9
Pod undocumented
433 28 my $self = shift;
434 28 my $iter = shift;
435 28 my (@blanks, @nonblanks);
436 28 ▶ while (my $st = $iter->next) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $st = $iter->next) 55 28 83
437 55 ▶ unless ($st->does('Attean::API::Binding')) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($st->does("Attean::API::Binding")) 0 55 55
438 0 die "Unexpected non-binding value found in BindingEqualityTest: " . $st->as_string;
439 }
440 55 ▶ if ($st->has_blanks) {
Branch: 1 branch
BranchTrueFalseTotal
if ($st->has_blanks) { } 39 16 55
441 39 push(@blanks, $st);
442 } else {
443 16 push(@nonblanks, $st);
444 }
445 }
446 28 return (\@blanks, \@nonblanks);
447 }
448  
449 }
450  
451 50 1;
452  
453 __END__
« Attean/API/QueryPlanner.pm ↑ Summary Attean/TreeRewriter.pm »