Attean/QueryPlanner.pm

filter: Statementstmt 56.6% 376 / 664 Branchbran 38.0% 83 / 218 Conditioncond 22.9% 11 / 48 MC/DCmcdc 10.3% 3 / 29 Subroutinesub 89.1% 33 / 37 Podpod 90.9% 10 / 11 totaltotal 51.2% 516 / 1007 CC 160 SCAR 72.4
CC
160
Cov
51%
plans_for_algebra
2416.3
simplify_path
90.0
_package
20.0
CRAP 1387.2
« Attean/SimpleQueryEvaluator.pm ↑ Summary Test/Attean/W3CManifestTestSuite.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::QueryPlanner - Query planner
7  
8 =head1 VERSION
9  
10 This document describes Attean::QueryPlanner version 0.040
11  
12 =head1 SYNOPSIS
13  
14 use v5.14;
15 use Attean;
16 my $planner = Attean::QueryPlanner->new();
17 my $default_graphs = [ Attean::IRI->new('http://example.org/') ];
18 my $plan = $planner->plan_for_algebra( $algebra, $model, $default_graphs );
19 my $iter = $plan->evaluate($model);
20 while (my $result = $iter->next()) {
21 say $result->as_string;
22 }
23  
24 =head1 DESCRIPTION
25  
26 The Attean::QueryPlanner class is a base class implementing common behavior for
27 query planners. Subclasses will need to consume or compose the
28 L<Attean::API::JoinPlanner> role.
29  
30 Trivial sub-classes may consume L<Attean::API::NaiveJoinPlanner>, while more
31 complex planners may choose to implement complex join planning (e.g.
32 L<Attean::IDPQueryPlanner>).
33  
34 =head1 ATTRIBUTES
35  
36 =over 4
37  
38 =cut
39  
40 50 ▶use Attean::Algebra;
Subroutine BEGIN: called CC=1 SCAR=0.0
41 50 ▶use Attean::Plan;
Subroutine BEGIN: called CC=1 SCAR=0.0
42 50 ▶use Attean::Expression;
Subroutine BEGIN: called CC=1 SCAR=0.0
43  
44 50 package Attean::QueryPlanner 0.040 {
45 50 ▶ use Moo;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 50 ▶ use Encode qw(encode);
Subroutine BEGIN: called CC=1 SCAR=0.0
47 50 ▶ use Attean::RDF;
Subroutine BEGIN: called CC=1 SCAR=0.0
48 50 ▶ use Scalar::Util qw(blessed reftype);
Subroutine BEGIN: called CC=1 SCAR=0.0
49 50 ▶ use List::Util qw(reduce);
Subroutine BEGIN: called CC=1 SCAR=0.0
50 50 ▶ use List::Util qw(all any);
Subroutine BEGIN: called CC=1 SCAR=0.0
51 50 ▶ use Types::Standard qw(Int ConsumerOf InstanceOf);
Subroutine BEGIN: called CC=1 SCAR=0.0
52 50 ▶ use URI::Escape;
Subroutine BEGIN: called CC=1 SCAR=0.0
53 50 ▶ use Algorithm::Combinatorics qw(subsets);
Subroutine BEGIN: called CC=1 SCAR=0.0
54 50 ▶ use List::Util qw(min);
Subroutine BEGIN: called CC=1 SCAR=0.0
55 50 ▶ use Math::Cartesian::Product;
Subroutine BEGIN: called CC=1 SCAR=0.0
56 50 ▶ use namespace::clean;
Subroutine BEGIN: called CC=1 SCAR=0.0
57  
58 50 with 'Attean::API::QueryPlanner', 'MooX::Log::Any';
59 50 has 'counter' => (is => 'rw', isa => Int, default => 0);
60 50 has 'table_threshold' => (is => 'rw', isa => Int, default => 10);
61  
62 =back
63  
64 =head1 METHODS
65  
66 =over 4
67  
68 =item C<< new_temporary( $type ) >>
69  
70 Returns a new unique (in the context of the query planner) ID string that may
71 be used for things like fresh (temporary) variables. The C<< $type >> string is
72 used in the generated name to aid in identifying different uses for the names.
73  
74 =cut
75  
76 15 ▶ sub new_temporary {
Subroutine new_temporary: called CC=1 SCAR=0.0
Pod documented
77 15 my $self = shift;
78 15 my $type = shift;
79 15 my $c = $self->counter;
80 15 $self->counter($c+1);
81 15 return sprintf('.%s-%d', $type, $c);
82 }
83  
84 =item C<< plan_for_algebra( $algebra, $model, \@active_graphs, \@default_graphs ) >>
85  
86 Returns the first plan returned from C<< plans_for_algebra >>.
87  
88 =cut
89  
90 26 ▶ sub plan_for_algebra {
Subroutine plan_for_algebra: called CC=1 SCAR=0.0
Pod documented
91 26 my $self = shift;
92 26 my @plans = $self->plans_for_algebra(@_);
93 25 return shift(@plans);
94 }
95
96 =item C<< plans_for_algebra( $algebra, $model, \@active_graphs, \@default_graphs ) >>
97  
98 Returns L<Attean::API::Plan> objects representing alternate query plans for
99 evaluating the query C<< $algebra >> against the C<< $model >>, using
100 the supplied C<< $active_graph >>.
101  
102 =cut
103  
104 134 ▶ sub plans_for_algebra {
Subroutine plans_for_algebra: called CC=112 SCAR=77.9
Pod documented
105 134 my $self = shift;
106 134 my $algebra = shift;
107 134 my $model = shift;
108 134 my $active_graphs = shift;
109 134 my $default_graphs = shift;
110 134 my %args = @_;
111
112 134 ▶ if ($model->does('Attean::API::CostPlanner')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($model->does("Attean::API::CostPlanner")) 134 0 134
113 134 my @plans = $model->plans_for_algebra($algebra, $self, $active_graphs, $default_graphs, %args);
114 134 ▶ if (@plans) {
Branch: 1 branch
BranchTrueFalseTotal
if (@plans) { } 2 132 134
115 2 return @plans; # trust that the model knows better than us what plans are best
116 } else {
117 132 $self->log->info("*** Model did not provide plans: $model");
118 }
119 }
120
121 132 ▶ Carp::confess "No algebra passed for evaluation" unless ($algebra);
Branch: 1 branch
BranchTrueFalseTotal
unless $algebra 0 132 132
122
123 # TODO: propagate interesting orders
124 132 my $interesting = [];
125
126 132 my @children = @{ $algebra->children };
127 132 my ($child) = $children[0];
128 132 ▶ if ($algebra->isa('Attean::Algebra::Query') or $algebra->isa('Attean::Algebra::Update')) {
Branch: 27 branches
BranchTrueFalseTotal
if ($algebra->isa('Attean::Algebra::Query') or $algebra->isa('Attean::Algebra::Update')) { } 8 124 132
elsif ($algebra->isa('Attean::Algebra::BGP')) { } 69 55 124
elsif ($algebra->isa('Attean::Algebra::Join')) { } 11 44 55
elsif ($algebra->isa('Attean::Algebra::Distinct') or $algebra->isa('Attean::Algebra::Reduced')) { } 6 38 44
elsif ($algebra->isa('Attean::Algebra::Filter')) { } 6 32 38
elsif ($algebra->isa('Attean::Algebra::OrderBy')) { } 3 29 32
elsif ($algebra->isa('Attean::Algebra::LeftJoin')) { } 0 29 29
elsif ($algebra->isa('Attean::Algebra::Minus')) { } 0 29 29
elsif ($algebra->isa('Attean::Algebra::Project')) { } 8 21 29
elsif ($algebra->isa('Attean::Algebra::Graph')) { } 10 11 21
elsif ($algebra->isa('Attean::Algebra::Table')) { } 0 11 11
elsif ($algebra->isa('Attean::Algebra::Service')) { } 4 7 11
elsif ($algebra->isa('Attean::Algebra::Slice')) { } 0 7 7
elsif ($algebra->isa('Attean::Algebra::Union')) { } 0 7 7
elsif ($algebra->isa('Attean::Algebra::Extend')) { } 1 6 7
elsif ($algebra->isa('Attean::Algebra::Group')) { } 1 5 6
elsif ($algebra->isa('Attean::Algebra::Ask')) { } 4 1 5
elsif ($algebra->isa('Attean::Algebra::Path')) { } 0 1 1
elsif ($algebra->isa('Attean::Algebra::Construct')) { } 0 1 1
elsif ($algebra->isa('Attean::Algebra::Describe')) { } 1 0 1
elsif ($algebra->isa('Attean::Algebra::Clear')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Add')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Modify')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Load')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Create')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Sequence')) { } 0 0 0
elsif ($algebra->isa('Attean::Algebra::Unfold')) { } 0 0 0
Condition66%2/3
$algebra->isa("Attean::Algebra::Query") or $algebra->isa("Attean::Algebra::Update")
l!l&&r!l&&!r
80124
MC/DC50%1/2
$algebra->isa("Attean::Algebra::Query") or $algebra->isa("Attean::Algebra::Update")
$algebra->isa("Attean::Algebra::Query") $algebra->isa("Attean::Algebra::Update")
Truth table66%2/3
A or B
A= $algebra->isa("Attean::Algebra::Query")B= $algebra->isa("Attean::Algebra::Update")
ABresult
1X1
011
000
129  
130 8 my @active_graphs = @$active_graphs;
131 8 my @default_graphs = @$default_graphs;
132
133 8 ▶ if ($algebra->can('dataset')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($algebra->can("dataset")) 8 0 8
134 8 my $dataset = $algebra->dataset;
135 8 ▶ my @default = @{ $dataset->{'default'} || [] };
Condition50%1/2
$dataset->{'default'} || []
l!l
08
MC/DC0%0/1
$dataset->{'default'} || []
$dataset->{'default'}
Truth table50%1/2
A
A= $dataset->{'default'}
Aresult
11
00
136 8 my $named = $dataset->{'named'};
137 8 ▶ my @named = (ref($named) eq 'ARRAY') ? @$named : (values %{ $named || {} });
Branch: 1 branch
BranchTrueFalseTotal
ref $named eq 'ARRAY' ? : 0 8 8
Condition50%1/2
$named || {}
l!l
08
MC/DC0%0/1
$named || {}
$named
Truth table50%1/2
A
A= $named
Aresult
11
00
138
139 8 ▶ if (scalar(@default) or scalar(@named)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @default or scalar @named) 0 8 8
Condition50%1/2
scalar @default or scalar @named
l!l
08
MC/DC0%0/1
scalar @default or scalar @named
scalar @default
Truth table50%1/2
A
A= scalar @default
Aresult
11
00
140 # change the available named graphs
141 # change the active graph(s)
142 0 @active_graphs = @default;
143 0 @default_graphs = @default;
144 0 $args{ available_graphs } = [@named];
145 }
146 }
147  
148 8 return $self->plans_for_algebra($algebra->child, $model, \@active_graphs, \@default_graphs, %args);
149 } elsif ($algebra->isa('Attean::Algebra::BGP')) {
150 69 my $triples = $algebra->triples;
151 69 my @triples = @$triples;
152 69 my %blanks;
153 69 $self->replace_blanks_with_variables(\%blanks, \@triples);
154 69 my $bgp = Attean::Algebra::BGP->new( triples => \@triples );
155 my @plans = $self->bgp_join_plans($bgp, $model, $active_graphs, $default_graphs, $interesting, map {
156 69 [$self->access_plans($model, $active_graphs, $_)]
157 } @triples);
158 68 return @plans;
159 } elsif ($algebra->isa('Attean::Algebra::Join')) {
160 return $self->group_join_plans($model, $active_graphs, $default_graphs, $interesting, map {
161 11 [$self->plans_for_algebra($_, $model, $active_graphs, $default_graphs, %args)]
162 } @children);
163 ▶ } elsif ($algebra->isa('Attean::Algebra::Distinct') or $algebra->isa('Attean::Algebra::Reduced')) {
Condition66%2/3
$algebra->isa("Attean::Algebra::Distinct") or $algebra->isa("Attean::Algebra::Reduced")
l!l&&r!l&&!r
6038
MC/DC50%1/2
$algebra->isa("Attean::Algebra::Distinct") or $algebra->isa("Attean::Algebra::Reduced")
$algebra->isa("Attean::Algebra::Distinct") $algebra->isa("Attean::Algebra::Reduced")
Truth table66%2/3
A or B
A= $algebra->isa("Attean::Algebra::Distinct")B= $algebra->isa("Attean::Algebra::Reduced")
ABresult
1X1
011
000
164 6 my @plans = $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
165 6 my @dist;
166 6 foreach my $p (@plans) {
167 38 ▶ if ($p->distinct) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p->distinct) { } 12 26 38
168 12 push(@dist, $p);
169 } else {
170 26 my @vars = @{ $p->in_scope_variables };
171 26 my $cmps = $p->ordered;
172 26 ▶ if ($self->_comparators_are_stable_and_cover_vars($cmps, @vars)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_comparators_are_stable_and_cover_vars($cmps, @vars)) { } 0 26 26
173 # the plan has a stable ordering which covers all the variables, so we can just uniq the iterator
174 0 push(@dist, Attean::Plan::Unique->new(children => [$p], distinct => 1, ordered => $p->ordered));
175 } else {
176 # TODO: if the plan isn't distinct, but is ordered, we can use a batched implementation
177 26 push(@dist, Attean::Plan::HashDistinct->new(children => [$p], distinct => 1, ordered => $p->ordered));
178 }
179 }
180 }
181 6 return @dist;
182 } elsif ($algebra->isa('Attean::Algebra::Filter')) {
183 # TODO: simple range relation filters can be handled differently if that filter operates on a variable that is part of the ordering
184 6 my $expr = $algebra->expression;
185 6 my $w = Attean::TreeRewriter->new(types => ['Attean::API::DirectedAcyclicGraph']);
186 12 ▶ $w->register_pre_handler(sub {
Subroutine __ANON__: called CC=3 SCAR=17.9
187 12 my ($t, $parent, $thunk) = @_;
188 12 ▶ if ($t->isa('Attean::ExistsExpression')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($t->isa("Attean::ExistsExpression")) 0 12 12
189 0 my $pattern = $t->pattern;
190 0 my $plan = $self->plan_for_algebra($pattern, $model, $active_graphs, $default_graphs, @_);
191 0 ▶ unless ($plan->does('Attean::API::BindingSubstitutionPlan')) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($plan->does("Attean::API::BindingSubstitutionPlan")) 0 0 0
192 0 die 'Exists plan does not consume Attean::API::BindingSubstitutionPlan: ' . $plan->as_string;
193 }
194 0 my $new = Attean::ExistsPlanExpression->new(
195 plan => $plan,
196 );
197 0 return (1, 0, $new);
198 }
199 12 return (0, 1, $t);
200 6 });
201 6 my ($changed, $rewritten) = $w->rewrite($expr, {});
202 6 ▶ if ($changed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($changed) 0 6 6
203 0 $expr = $rewritten;
204 }
205
206 6 my $var = $self->new_temporary('filter');
207 6 my %exprs = ($var => $expr);
208
209 6 my @plans;
210 6 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args)) {
211 6 my $distinct = $plan->distinct;
212 6 my $ordered = $plan->ordered;
213 6 ▶ if ($expr->isa('Attean::ValueExpression') and $expr->value->does('Attean::API::Variable')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($expr->isa('Attean::ValueExpression') and $expr->value->does('Attean::API::Variable')) { } 3 3 6
Condition66%2/3
$expr->isa("Attean::ValueExpression") and $expr->value->does("Attean::API::Variable")
!ll&&!rl&&r
303
MC/DC50%1/2
$expr->isa("Attean::ValueExpression") and $expr->value->does("Attean::API::Variable")
$expr->isa("Attean::ValueExpression") $expr->value->does("Attean::API::Variable")
Truth table66%2/3
A and B
A= $expr->isa("Attean::ValueExpression")B= $expr->value->does("Attean::API::Variable")
ABresult
0X0
100
111
214 3 my $filtered = Attean::Plan::EBVFilter->new(children => [$plan], variable => $expr->value->value, distinct => $distinct, ordered => $ordered);
215 3 push(@plans, $filtered);
216 } else {
217 3 my @vars = ($var);
218 3 my @inscope = ($var, @{ $plan->in_scope_variables });
219 3 my @pvars = map { Attean::Variable->new($_) } @{ $plan->in_scope_variables };
220 3 my $extend = Attean::Plan::Extend->new(children => [$plan], expressions => \%exprs, distinct => 0, ordered => $ordered, active_graphs => $active_graphs);
221 3 my $filtered = Attean::Plan::EBVFilter->new(children => [$extend], variable => $var, distinct => 0, ordered => $ordered);
222 3 my $proj = $self->new_projection($filtered, $distinct, @{ $plan->in_scope_variables });
223 3 push(@plans, $proj);
224 }
225 }
226 6 return @plans;
227 } elsif ($algebra->isa('Attean::Algebra::OrderBy')) {
228 # TODO: no-op if already ordered
229 3 my @cmps = @{ $algebra->comparators };
230 3 my ($exprs, $ascending, $svars) = $self->_order_by($algebra);
231 3 my @plans;
232 3 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, interesting_order => $algebra->comparators, %args)) {
233 3 my $distinct = $plan->distinct;
234  
235 3 ▶ if (scalar(@cmps) == 1 and $cmps[0]->expression->isa('Attean::ValueExpression') and $cmps[0]->expression->value->does('Attean::API::Variable')) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @cmps == 1 and $cmps[0]->expression->isa('Attean::ValueExpression') and $cmps[0]->expression->value->does('Attean::API::Variable')) { } 3 0 3
Condition33%2/6
scalar @cmps == 1 and $cmps[0]->expression->isa("Attean::ValueExpression") and $cmps[0]->expression->value->does("Attean::API::Variable")
!ll&&!rl&&r
003
scalar @cmps == 1 and $cmps[0]->expression->isa("Attean::ValueExpression")
!ll&&!rl&&r
003
MC/DC0%0/3
scalar @cmps == 1 and $cmps[0]->expression->isa("Attean::ValueExpression") and $cmps[0]->expression->value->does("Attean::API::Variable")
scalar @cmps == 1 $cmps[0]->expression->isa("Attean::ValueExpression") $cmps[0]->expression->value->does("Attean::API::Variable")
Truth table25%1/4
A and B and C
A= scalar @cmps == 1B= $cmps[0]->expression->isa("Attean::ValueExpression")C= $cmps[0]->expression->value->does("Attean::API::Variable")
ABCresult
0XX0
10X0
1100
1111
236 # TODO: extend this to handle more than one comparator, so long as they are *all* just variables (and not complex expressions)
237 # If we're sorting by just a variable name, don't bother creating new variables for the sort expressions, use the underlying variable directy
238 3 my @vars = @{ $plan->in_scope_variables };
239 3 my @pvars = map { Attean::Variable->new($_) } @{ $plan->in_scope_variables };
240 3 my $var = $cmps[0]->expression->value->value;
241 3 my $ascending = { $var => $cmps[0]->ascending };
242 3 my $ordered = Attean::Plan::OrderBy->new(children => [$plan], variables => [$var], ascending => $ascending, distinct => $distinct, ordered => \@cmps);
243 3 push(@plans, $ordered);
244 } else {
245 0 my @vars = (@{ $plan->in_scope_variables }, keys %$exprs);
246 0 my @pvars = map { Attean::Variable->new($_) } @{ $plan->in_scope_variables };
247 0 my $extend = Attean::Plan::Extend->new(children => [$plan], expressions => $exprs, distinct => 0, ordered => $plan->ordered, active_graphs => $active_graphs);
248 0 my $ordered = Attean::Plan::OrderBy->new(children => [$extend], variables => $svars, ascending => $ascending, distinct => 0, ordered => \@cmps);
249 0 my $proj = $self->new_projection($ordered, $distinct, @{ $plan->in_scope_variables });
250 0 push(@plans, $proj);
251 }
252 }
253
254 3 return @plans;
255 } elsif ($algebra->isa('Attean::Algebra::LeftJoin')) {
256 0 my $l = [$self->plans_for_algebra($children[0], $model, $active_graphs, $default_graphs, %args)];
257 0 my $r = [$self->plans_for_algebra($children[1], $model, $active_graphs, $default_graphs, %args)];
258 0 return $self->join_plans($model, $active_graphs, $default_graphs, $l, $r, 'left', $algebra->expression);
259 } elsif ($algebra->isa('Attean::Algebra::Minus')) {
260 0 my $l = [$self->plans_for_algebra($children[0], $model, $active_graphs, $default_graphs, %args)];
261 0 my $r = [$self->plans_for_algebra($children[1], $model, $active_graphs, $default_graphs, %args)];
262 0 return $self->join_plans($model, $active_graphs, $default_graphs, $l, $r, 'minus');
263 } elsif ($algebra->isa('Attean::Algebra::Project')) {
264 8 my $vars = $algebra->variables;
265 8 my @vars = map { $_->value } @{ $vars };
266 8 my $vars_key = join(' ', sort @vars);
267 8 my $distinct = 0;
268 my @plans = map {
269 8 ▶ ($vars_key eq join(' ', sort @{ $_->in_scope_variables }))
Branch: 1 branch
BranchTrueFalseTotal
$vars_key eq join(' ', sort(@{$_->in_scope_variables;})) ? : 7 7 14
270 ? $_ # no-op if plan is already properly-projected
271 : $self->new_projection($_, $distinct, @vars)
272 } $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
273 8 return @plans;
274 } elsif ($algebra->isa('Attean::Algebra::Graph')) {
275 10 my $graph = $algebra->graph;
276 10 ▶ if ($graph->does('Attean::API::Term')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($graph->does('Attean::API::Term')) { } 5 5 10
277 5 ▶ if (my $available = $args{available_graphs}) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $available = $args{"available_graphs"}) 2 3 5
278 # the list of available graphs has been restricted, and this
279 # graph is not available so return an empty table plan.
280 2 ▶ unless (any { $_->equals($graph) } @$available) {
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
BranchTrueFalseTotal
unless (&any(sub { $_->equals($graph); } , @$available)) 1 1 2
281 1 my $plan = Attean::Plan::Table->new( variables => [], rows => [], distinct => 0, ordered => [] );
282 1 return $plan;
283 }
284 }
285 4 return $self->plans_for_algebra($child, $model, [$graph], $default_graphs, %args);
286 } else {
287 5 my $gvar = $graph->value;
288 5 my $graphs = $model->get_graphs;
289
290 5 my @plans;
291 5 my %vars = map { $_ => 1 } $child->in_scope_variables;
292 5 $vars{ $gvar }++;
293 5 my @vars = keys %vars;
294
295 5 my %available;
296 5 ▶ if (my $available = $args{available_graphs}) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $available = $args{"available_graphs"}) 2 3 5
297 2 foreach my $a (@$available) {
298 4 $available{ $a->value }++;
299 }
300 2 ▶ $graphs = $graphs->grep(sub { $available{ $_->value } });
Subroutine __ANON__: called CC=1 SCAR=0.0
301 }
302
303 5 my @branches;
304 # ignore default graphs unless they are listed as available named graphs
305 5 my %ignore = map { $_->value => 1 } grep { not exists $available{ $_->value} } @$default_graphs;
306 5 ▶ while (my $graph = $graphs->next) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $graph = $graphs->next) 3 5 8
307 3 ▶ next if $ignore{ $graph->value };
Branch: 1 branch
BranchTrueFalseTotal
if $ignore{$graph->value} 0 3 3
308 3 my %exprs = ($gvar => Attean::ValueExpression->new(value => $graph));
309 # TODO: rewrite $child pattern here to replace any occurrences of the variable $gvar to $graph
310 my @plans = map {
311 3 Attean::Plan::Extend->new(children => [$_], expressions => \%exprs, distinct => 0, ordered => $_->ordered, active_graphs => $active_graphs);
312 } $self->plans_for_algebra($child, $model, [$graph], $default_graphs, %args);
313 3 push(@branches, \@plans);
314 }
315
316 5 ▶ if (scalar(@branches) == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @branches == 1) { } 1 4 5
317 1 @plans = @{ shift(@branches) };
318 } else {
319 4 ▶ cartesian { push(@plans, Attean::Plan::Union->new(children => [@_], distinct => 0, ordered => [])) } @branches;
Subroutine __ANON__: called CC=1 SCAR=0.0
320 }
321 5 return @plans;
322 }
323 } elsif ($algebra->isa('Attean::Algebra::Table')) {
324 0 my $rows = $algebra->rows;
325 0 my $vars = $algebra->variables;
326 0 my @vars = map { $_->value } @{ $vars };
327
328 0 ▶ if (scalar(@$rows) < $self->table_threshold) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @$rows < $self->table_threshold) { } 0 0 0
329 0 return Attean::Plan::Table->new( variables => $vars, rows => $rows, distinct => 0, ordered => [] );
330 } else {
331 0 my $iter = Attean::ListIterator->new(
332 item_type => 'Attean::API::Result',
333 variables => \@vars,
334 values => $rows
335 );
336 0 return Attean::Plan::Iterator->new( iterator => $iter, distinct => 0, ordered => [] );
337 }
338 } elsif ($algebra->isa('Attean::Algebra::Service')) {
339 4 my $endpoint = $algebra->endpoint;
340 4 my $silent = $algebra->silent;
341 4 my $sparql = sprintf('SELECT * WHERE { %s }', $child->as_sparql);
342 4 my @vars = $child->in_scope_variables;
343 4 my $plan = Attean::Plan::Service->new(
344 request_signer => $self->request_signer,
345 endpoint => $endpoint,
346 silent => $silent,
347 sparql => $sparql,
348 distinct => 0,
349 in_scope_variables => \@vars,
350 ordered => []
351 );
352 4 return $plan;
353 } elsif ($algebra->isa('Attean::Algebra::Slice')) {
354 0 my $limit = $algebra->limit;
355 0 my $offset = $algebra->offset;
356 0 my @plans;
357 0 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args)) {
358 0 my $vars = $plan->in_scope_variables;
359 0 push(@plans, Attean::Plan::Slice->new(children => [$plan], limit => $limit, offset => $offset, distinct => $plan->distinct, ordered => $plan->ordered));
360 }
361 0 return @plans;
362 } elsif ($algebra->isa('Attean::Algebra::Union')) {
363 # TODO: if both branches are similarly ordered, we can use Attean::Plan::Merge to keep the resulting plan ordered
364 0 my @vars = keys %{ { map { map { $_ => 1 } $_->in_scope_variables } @children } };
365 0 my @plansets = map { [$self->plans_for_algebra($_, $model, $active_graphs, $default_graphs, %args)] } @children;
366  
367 0 my @plans;
368 0 ▶ cartesian {
Subroutine __ANON__: not called CC=1 SCAR=6.9
369 0 push(@plans, Attean::Plan::Union->new(children => \@_, distinct => 0, ordered => []))
370 0 } @plansets;
371 0 return @plans;
372 } elsif ($algebra->isa('Attean::Algebra::Extend')) {
373 1 my $var = $algebra->variable->value;
374 1 my $expr = $algebra->expression;
375 1 my %exprs = ($var => $expr);
376 1 my @vars = $algebra->in_scope_variables;
377  
378 1 my @plans;
379 1 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args)) {
380 4 my $extend = Attean::Plan::Extend->new(children => [$plan], expressions => \%exprs, distinct => 0, ordered => $plan->ordered, active_graphs => $active_graphs);
381 4 push(@plans, $extend);
382 }
383 1 return @plans;
384 } elsif ($algebra->isa('Attean::Algebra::Group')) {
385 1 my $aggs = $algebra->aggregates;
386 1 my $groups = $algebra->groupby;
387 1 my %exprs;
388 1 foreach my $expr (@$aggs) {
389 1 my $var = $expr->variable->value;
390 1 $exprs{$var} = $expr;
391 }
392 1 my @plans;
393 1 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args)) {
394 4 my $extend = Attean::Plan::Aggregate->new(children => [$plan], aggregates => \%exprs, groups => $groups, distinct => 0, ordered => [], active_graphs => $active_graphs);
395 4 push(@plans, $extend);
396 }
397 1 return @plans;
398 } elsif ($algebra->isa('Attean::Algebra::Ask')) {
399 4 my @plans;
400 4 foreach my $plan ($self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args)) {
401 4 return Attean::Plan::Exists->new(children => [$plan], distinct => 1, ordered => []);
402 }
403 0 return @plans;
404 } elsif ($algebra->isa('Attean::Algebra::Path')) {
405 0 my $s = $algebra->subject;
406 0 my $path = $algebra->path;
407 0 my $o = $algebra->object;
408
409 0 my @algebra = $self->simplify_path($s, $path, $o);
410
411 0 my @join;
412 0 ▶ if (scalar(@algebra)) {
Branch: 3 branches
BranchTrueFalseTotal
if (scalar @algebra) { } 0 0 0
elsif ($path->isa('Attean::Algebra::ZeroOrMorePath') or $path->isa('Attean::Algebra::OneOrMorePath')) { } 0 0 0
elsif ($path->isa('Attean::Algebra::ZeroOrOnePath')) { } 0 0 0
413 0 my @triples;
414 0 ▶ while (my $pa = shift(@algebra)) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $pa = shift @algebra) 0 0 0
415 0 ▶ if ($pa->isa('Attean::TriplePattern')) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pa->isa('Attean::TriplePattern')) { } 0 0 0
416 0 push(@triples, $pa);
417 } else {
418 0 ▶ if (scalar(@triples)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @triples) 0 0 0
419 0 push(@join, Attean::Algebra::BGP->new( triples => [@triples] ));
420 0 @triples = ();
421 }
422 0 push(@join, $pa);
423 }
424 }
425 0 ▶ if (scalar(@triples)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @triples) 0 0 0
426 0 push(@join, Attean::Algebra::BGP->new( triples => [@triples] ));
427 }
428
429 0 my @vars = $algebra->in_scope_variables;
430
431 my @joins = $self->group_join_plans($model, $active_graphs, $default_graphs, $interesting, map {
432 0 [$self->plans_for_algebra($_, $model, $active_graphs, $default_graphs, %args)]
433 } @join);
434
435 0 my @plans;
436 0 foreach my $j (@joins) {
437 0 push(@plans, Attean::Plan::Project->new(children => [$j], variables => [map { Attean::Variable->new($_) } @vars], distinct => 0, ordered => []));
438 }
439 0 return @plans;
440
441 ▶ } elsif ($path->isa('Attean::Algebra::ZeroOrMorePath') or $path->isa('Attean::Algebra::OneOrMorePath')) {
Condition0%0/3
$path->isa("Attean::Algebra::ZeroOrMorePath") or $path->isa("Attean::Algebra::OneOrMorePath")
l!l&&r!l&&!r
000
MC/DC0%0/2
$path->isa("Attean::Algebra::ZeroOrMorePath") or $path->isa("Attean::Algebra::OneOrMorePath")
$path->isa("Attean::Algebra::ZeroOrMorePath") $path->isa("Attean::Algebra::OneOrMorePath")
Truth table0%0/3
A or B
A= $path->isa("Attean::Algebra::ZeroOrMorePath")B= $path->isa("Attean::Algebra::OneOrMorePath")
ABresult
1X1
011
000
442 0 ▶ my $skip = $path->isa('Attean::Algebra::OneOrMorePath') ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$path->isa('Attean::Algebra::OneOrMorePath') ? : 0 0 0
443 0 my $begin = Attean::Variable->new(value => $self->new_temporary('pp'));
444 0 my $end = Attean::Variable->new(value => $self->new_temporary('pp'));
445 0 my $s_var = $s->does('Attean::API::Variable');
446 0 my $o_var = $o->does('Attean::API::Variable');
447
448 0 my $child = $path->children->[0];
449 0 my $a;
450 0 ▶ if ($s_var and not($o_var)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($s_var and not $o_var) { } 0 0 0
Condition0%0/3
$s_var and not $o_var
!ll&&!rl&&r
000
MC/DC0%0/2
$s_var and not $o_var
$s_var not $o_var
Truth table0%0/3
A and not(B)
A= $s_varB= not $o_var
ABresult
0X0
100
111
451 0 my $inv = Attean::Algebra::InversePath->new( children => [$child] );
452 0 $a = Attean::Algebra::Path->new( subject => $begin, path => $inv, object => $end );
453 0 ($s, $o) = ($o, $s);
454 } else {
455 0 $a = Attean::Algebra::Path->new( subject => $begin, path => $child, object => $end );
456 }
457 0 my @cplans = $self->plans_for_algebra($a, $model, $active_graphs, $default_graphs, %args);
458 0 my @plans;
459 0 foreach my $cplan (@cplans) {
460 0 my $plan = Attean::Plan::ALPPath->new(
461 subject => $s,
462 children => [$cplan],
463 object => $o,
464 graph => $active_graphs,
465 skip => $skip,
466 step_begin => $begin,
467 step_end => $end,
468 distinct => 0,
469 ordered => []
470 );
471 0 push(@plans, $plan);
472 }
473 0 return @plans;
474 } elsif ($path->isa('Attean::Algebra::ZeroOrOnePath')) {
475 0 my $a = Attean::Algebra::Path->new( subject => $s, path => $path->children->[0], object => $o );
476 0 my @children = $self->plans_for_algebra($a, $model, $active_graphs, $default_graphs, %args);
477 0 my @plans;
478 0 foreach my $plan (@children) {
479 0 push(@plans, Attean::Plan::ZeroOrOnePath->new(
480 subject => $s,
481 children => [$plan],
482 object => $o,
483 graph => $active_graphs,
484 distinct => 0,
485 ordered => []
486 ));
487 }
488 0 return @plans;
489 } else {
490 0 die "Cannot simplify property path $path: " . $algebra->as_string;
491 }
492 } elsif ($algebra->isa('Attean::Algebra::Construct')) {
493 0 my @children = $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
494 0 my @plans;
495 0 foreach my $plan (@children) {
496 0 push(@plans, Attean::Plan::Construct->new(triples => $algebra->triples, children => [$plan], distinct => 0, ordered => []));
497 }
498 0 return @plans;
499 } elsif ($algebra->isa('Attean::Algebra::Describe')) {
500 1 my @children = $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
501 1 my @plans;
502 1 foreach my $plan (@children) {
503 1 push(@plans, Attean::Plan::Describe->new(terms => $algebra->terms, graph => $active_graphs, children => [$plan], distinct => 0, ordered => []));
504 }
505 1 return @plans;
506 } elsif ($algebra->isa('Attean::Algebra::Clear')) {
507 0 ▶ my $plan_class = $algebra->drop ? 'Attean::Plan::Drop' : 'Attean::Plan::Clear';
Branch: 1 branch
BranchTrueFalseTotal
$algebra->drop ? : 0 0 0
508 0 my $target = $algebra->target;
509 0 ▶ if ($target eq 'GRAPH') {
Branch: 1 branch
BranchTrueFalseTotal
if ($target eq 'GRAPH') { } 0 0 0
510 0 return Attean::Plan::Clear->new(graphs => [$algebra->graph]);
511 } else {
512 0 my %default = map { $_->value => 1 } @$active_graphs;
513 0 my $graphs = $model->get_graphs;
514 0 my @graphs;
515 0 ▶ while (my $graph = $graphs->next) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $graph = $graphs->next) 0 0 0
516 0 ▶ if ($target eq 'ALL') {
Branch: 1 branch
BranchTrueFalseTotal
if ($target eq 'ALL') { } 0 0 0
517 0 push(@graphs, $graph);
518 } else {
519 0 ▶ if ($target eq 'DEFAULT' and $default{ $graph->value }) {
Branch: 2 branches
BranchTrueFalseTotal
if ($target eq 'DEFAULT' and $default{$graph->value}) { } 0 0 0
elsif ($target eq 'NAMED' and not $default{$graph->value}) { } 0 0 0
Condition0%0/3
$target eq "DEFAULT" and $default{$graph->value}
!ll&&!rl&&r
000
MC/DC0%0/2
$target eq "DEFAULT" and $default{$graph->value}
$target eq "DEFAULT" $default{$graph->value}
Truth table0%0/3
A and B
A= $target eq "DEFAULT"B= $default{$graph->value}
ABresult
0X0
100
111
520 0 push(@graphs, $graph);
521 ▶ } elsif ($target eq 'NAMED' and not $default{ $graph->value }) {
Condition0%0/3
$target eq "NAMED" and not $default{$graph->value}
!ll&&!rl&&r
000
MC/DC0%0/2
$target eq "NAMED" and not $default{$graph->value}
$target eq "NAMED" not $default{$graph->value}
Truth table0%0/3
A and not(B)
A= $target eq "NAMED"B= not $default{$graph->value}
ABresult
0X0
100
111
522 0 push(@graphs, $graph);
523 }
524 }
525 }
526 0 return $plan_class->new(graphs => \@graphs);
527 }
528 } elsif ($algebra->isa('Attean::Algebra::Add')) {
529 0 my $triple = triplepattern(variable('s'), variable('p'), variable('o'));
530 0 my $child;
531 0 my $default_source = 0;
532 0 ▶ if (my $from = $algebra->source) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $from = $algebra->source) { } 0 0 0
533 0 ($child) = $self->access_plans( $model, $active_graphs, $triple->as_quad_pattern($from) );
534 } else {
535 0 $default_source++;
536 0 my $bgp = Attean::Algebra::BGP->new( triples => [$triple] );
537 0 ($child) = $self->plans_for_algebra($bgp, $model, $active_graphs, $default_graphs, %args);
538 }
539
540 0 my $dest;
541 0 my $default_dest = 0;
542 0 ▶ if (my $g = $algebra->destination) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $g = $algebra->destination) { } 0 0 0
543 0 $dest = $triple->as_quad_pattern($g);
544 } else {
545 0 $default_dest++;
546 0 $dest = $triple->as_quad_pattern($default_graphs->[0]);
547 }
548  
549  
550 0 my @plans;
551 0 my $run_update = 1;
552 0 ▶ if ($default_dest and $default_source) {
Branch: 3 branches
BranchTrueFalseTotal
if ($default_dest and $default_source) { } 0 0 0
elsif ($default_dest or $default_source) { } 0 0 0
elsif ($algebra->source->equals($algebra->destination)) { } 0 0 0
Condition0%0/3
$default_dest and $default_source
!ll&&!rl&&r
000
MC/DC0%0/2
$default_dest and $default_source
$default_dest $default_source
Truth table0%0/3
A and B
A= $default_destB= $default_source
ABresult
0X0
100
111
553 0 $run_update = 0;
554 ▶ } elsif ($default_dest or $default_source) {
Condition0%0/3
$default_dest or $default_source
l!l&&r!l&&!r
000
MC/DC0%0/2
$default_dest or $default_source
$default_dest $default_source
Truth table0%0/3
A or B
A= $default_destB= $default_source
ABresult
1X1
011
000
555 #
556 } elsif ($algebra->source->equals($algebra->destination)) {
557 0 $run_update = 0;
558 }
559
560 0 ▶ if ($run_update) {
Branch: 1 branch
BranchTrueFalseTotal
if ($run_update) 0 0 0
561 0 ▶ if ($algebra->drop_destination) {
Branch: 1 branch
BranchTrueFalseTotal
if ($algebra->drop_destination) 0 0 0
562 0 ▶ my @graphs = $algebra->has_destination ? $algebra->destination : @$default_graphs;
Branch: 1 branch
BranchTrueFalseTotal
$algebra->has_destination ? : 0 0 0
563 0 unshift(@plans, Attean::Plan::Clear->new(graphs => [@graphs]));
564 }
565
566 0 push(@plans, Attean::Plan::TripleTemplateToModelQuadMethod->new(
567 graph => $default_graphs->[0],
568 order => ['add_quad'],
569 patterns => {'add_quad' => [$dest]},
570 children => [$child],
571 ));
572
573 0 ▶ if ($algebra->drop_source) {
Branch: 1 branch
BranchTrueFalseTotal
if ($algebra->drop_source) 0 0 0
574 0 ▶ my @graphs = $algebra->has_source ? $algebra->source : @$default_graphs;
Branch: 1 branch
BranchTrueFalseTotal
$algebra->has_source ? : 0 0 0
575 0 push(@plans, Attean::Plan::Clear->new(graphs => [@graphs]));
576 }
577 }
578 0 ▶ my $plan = (scalar(@plans) == 1) ? shift(@plans) : Attean::Plan::Sequence->new( children => \@plans );
Branch: 1 branch
BranchTrueFalseTotal
scalar @plans == 1 ? : 0 0 0
579 0 return $plan;
580 } elsif ($algebra->isa('Attean::Algebra::Modify')) {
581 0 ▶ unless ($child) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($child) 0 0 0
582 # This is an INSERT/DELETE DATA algebra with ground data and no pattern
583 0 $child = Attean::Algebra::BGP->new( triples => [] );
584 }
585
586 0 my $dataset = $algebra->dataset;
587 0 ▶ my @default = @{ $dataset->{default} || [] };
Condition0%0/2
$dataset->{'default'} || []
l!l
00
MC/DC0%0/1
$dataset->{'default'} || []
$dataset->{'default'}
Truth table0%0/2
A
A= $dataset->{'default'}
Aresult
11
00
588 0 ▶ my @named = values %{ $dataset->{named} || {} };
Condition0%0/2
$dataset->{'named'} || {}
l!l
00
MC/DC0%0/1
$dataset->{'named'} || {}
$dataset->{'named'}
Truth table0%0/2
A
A= $dataset->{'named'}
Aresult
11
00
589
590 0 my @active_graphs = @$active_graphs;
591 0 my @default_graphs = @$default_graphs;
592
593 0 ▶ if (scalar(@default) or scalar(@named)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @default or scalar @named) { } 0 0 0
Condition0%0/2
scalar @default or scalar @named
l!l
00
MC/DC0%0/1
scalar @default or scalar @named
scalar @default
Truth table0%0/2
A
A= scalar @default
Aresult
11
00
594 # change the available named graphs
595 # change the active graph(s)
596 0 @active_graphs = @default;
597 0 @default_graphs = @default;
598 0 $args{ available_graphs } = [@named];
599 } else {
600 # no custom dataset
601 }
602
603 0 my @children = $self->plans_for_algebra($child, $model, \@active_graphs, \@default_graphs, %args);
604 0 $algebra->materialize;
605 0 my $i = $algebra->insert;
606 0 my $d = $algebra->delete;
607 0 my %patterns;
608 my @order;
609 0 ▶ if ($d->size) {
Branch: 1 branch
BranchTrueFalseTotal
if ($d->size) 0 0 0
610 0 push(@order, 'remove_quad');
611 0 $patterns{ 'remove_quad' } = [$d->elements];
612 }
613 0 ▶ if ($i->size) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i->size) 0 0 0
614 0 push(@order, 'add_quad');
615 0 $patterns{ 'add_quad' } = [$i->elements];
616 }
617 return map {
618 0 Attean::Plan::TripleTemplateToModelQuadMethod->new(
619 graph => $default_graphs->[0],
620 order => \@order,
621 patterns => \%patterns,
622 children => [$_],
623 )
624 } @children;
625 } elsif ($algebra->isa('Attean::Algebra::Load')) {
626 0 my $pattern = triplepattern(variable('subject'), variable('predicate'), variable('object'));
627 0 my $load = Attean::Plan::Load->new( url => $algebra->url->value, silent => $algebra->silent );
628 0 ▶ my $graph = $algebra->has_graph ? $algebra->graph : $default_graphs->[0];
Branch: 1 branch
BranchTrueFalseTotal
$algebra->has_graph ? : 0 0 0
629 0 my $plan = Attean::Plan::TripleTemplateToModelQuadMethod->new(
630 graph => $graph,
631 order => ['add_quad'],
632 patterns => {'add_quad' => [$pattern]},
633 children => [$load],
634 );
635 0 return $plan;
636 } elsif ($algebra->isa('Attean::Algebra::Create')) {
637 0 return Attean::Plan::Sequence->new( children => [] );
638 } elsif ($algebra->isa('Attean::Algebra::Sequence')) {
639 0 my @plans;
640 0 foreach my $child (@{ $algebra->children }) {
641 0 my ($plan) = $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
642 0 push(@plans, $plan);
643 }
644 0 return Attean::Plan::Sequence->new( children => \@plans );
645 } elsif ($algebra->isa('Attean::Algebra::Unfold')) {
646 0 my @plans = $self->plans_for_algebra($child, $model, $active_graphs, $default_graphs, %args);
647 0 my @unfold;
648 0 foreach my $p (@plans) {
649 0 push(@unfold, Attean::Plan::Unfold->new( children => [$p], expression => $algebra->expression, variables => $algebra->variables, active_graphs => $active_graphs ));
650 }
651 0 return @unfold;
652 }
653 0 die "Unimplemented algebra evaluation for: " . $algebra->as_string;
654 }
655
656 69 ▶ sub replace_blanks_with_variables {
Subroutine replace_blanks_with_variables: called CC=8 SCAR=21.7
Pod undocumented
657 69 my $self = shift;
658 69 my $blanks = shift;
659 69 my $triples = shift;
660 69 my $any_changed = 0;
661 69 foreach my $i (0 .. $#{ $triples }) {
662 100 my $t = $triples->[$i];
663 100 my @nodes = $t->values;
664 100 my $changed = 0;
665 100 foreach (@nodes) {
666 300 ▶ if ($_->does('Attean::API::Blank')) {
Branch: 2 branches
BranchTrueFalseTotal
if ($_->does('Attean::API::Blank')) { } 6 294 300
elsif ($_->does('Attean::API::TriplePattern')) { } 0 294 294
667 6 $changed++;
668 6 my $id = $_->value;
669 6 ▶ unless (exists $blanks->{$id}) {
Branch: 1 branch
BranchTrueFalseTotal
unless (exists $blanks->{$id}) 6 0 6
670 6 $blanks->{$id} = Attean::Variable->new(value => $self->new_temporary('blank'));
671 }
672 6 $_ = $blanks->{$id};
673 } elsif ($_->does('Attean::API::TriplePattern')) {
674 0 my $tt = [$_];
675 0 my $changed = $self->replace_blanks_with_variables($blanks, $tt);
676 0 ▶ if ($changed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($changed) 0 0 0
677 0 $_ = $tt->[0];
678 }
679 }
680 }
681
682 100 ▶ if ($changed) {
Branch: 1 branch
BranchTrueFalseTotal
if ($changed) 6 94 100
683 6 $any_changed++;
684 6 my $new = Attean::TriplePattern->new(@nodes);
685 6 $triples->[$i] = $new;
686 }
687 }
688 69 return $any_changed;
689 }
690
691 # sub plans_for_unbounded_path {
692 # my $self = shift;
693 # my $algebra = shift;
694 # my $model = shift;
695 # my $active_graphs = shift;
696 # my $default_graphs = shift;
697 # my %args = @_;
698 #
699 # my $s = $algebra->subject;
700 # my $path = $algebra->path;
701 # my $o = $algebra->object;
702 #
703 # return Attean::Plan::ALPPath->new(distinct => 0, ordered => []);
704 # }
705
706 0 ▶ sub _package {
Subroutine _package: not called CC=4 SCAR=30.0
707 0 my $self = shift;
708 0 my @args = @_;
709
710 0 my @bgptriples = map { @{ $_->triples } } grep { $_->isa('Attean::Algebra::BGP') } @args;
711 0 my @triples = grep { $_->isa('Attean::TriplePattern') } @args;
712 0 ▶ my @rest = grep { not $_->isa('Attean::Algebra::BGP') and not $_->isa('Attean::TriplePattern') } @args;
Condition0%0/3
$_->isa('Attean::Algebra::BGP') || $_->isa('Attean::TriplePattern')
l!l&&r!l&&!r
000
MC/DC0%0/2
$_->isa('Attean::Algebra::BGP') || $_->isa('Attean::TriplePattern')
$_->isa('Attean::Algebra::BGP') $_->isa('Attean::TriplePattern')
Truth table0%0/3
A || B
A= $_->isa('Attean::Algebra::BGP')B= $_->isa('Attean::TriplePattern')
ABresult
1X1
011
000
713 0 ▶ if (scalar(@rest) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @rest == 0) { } 0 0 0
714 0 return Attean::Algebra::BGP->new( triples => [@bgptriples, @triples] );
715 } else {
716 0 my $p = Attean::Algebra::BGP->new( triples => [@bgptriples, @triples] );
717 0 ▶ while (scalar(@rest) > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @rest > 0) 0 0 0
718 0 $p = Attean::Algebra::Join->new( children => [$p, shift(@rest)] );
719 }
720 0 return $p;
721 }
722 }
723
724 =item C<< simplify_path( $subject, $path, $object ) >>
725  
726 Return a simplified L<Attean::API::Algebra> object corresponding to the given
727 property path.
728  
729 =cut
730  
731 0 ▶ sub simplify_path {
Subroutine simplify_path: not called CC=9 SCAR=45.0
Pod documented
732 0 my $self = shift;
733 0 my $s = shift;
734 0 my $path = shift;
735 0 my $o = shift;
736 0 ▶ if ($path->isa('Attean::Algebra::SequencePath')) {
Branch: 5 branches
BranchTrueFalseTotal
if ($path->isa('Attean::Algebra::SequencePath')) { } 0 0 0
elsif ($path->isa('Attean::Algebra::InversePath')) { } 0 0 0
elsif ($path->isa('Attean::Algebra::PredicatePath')) { } 0 0 0
elsif ($path->isa('Attean::Algebra::AlternativePath')) { } 0 0 0
elsif ($path->isa('Attean::Algebra::NegatedPropertySet')) { } 0 0 0
737 0 my $jvar = Attean::Variable->new(value => $self->new_temporary('pp'));
738 0 my ($lhs, $rhs) = @{ $path->children };
739 0 my @paths;
740 0 push(@paths, $self->simplify_path($s, $lhs, $jvar));
741 0 push(@paths, $self->simplify_path($jvar, $rhs, $o));
742 0 return $self->_package(@paths);
743 } elsif ($path->isa('Attean::Algebra::InversePath')) {
744 0 my ($ipath) = @{ $path->children };
745 0 return $self->simplify_path($o, $ipath, $s);
746 } elsif ($path->isa('Attean::Algebra::PredicatePath')) {
747 0 my $pred = $path->predicate;
748 0 return Attean::TriplePattern->new($s, $pred, $o);
749 } elsif ($path->isa('Attean::Algebra::AlternativePath')) {
750 0 my ($l, $r) = @{ $path->children };
751 0 my $la = $self->_package($self->simplify_path($s, $l, $o));
752 0 my $ra = $self->_package($self->simplify_path($s, $r, $o));
753 0 return Attean::Algebra::Union->new( children => [$la, $ra] );
754 } elsif ($path->isa('Attean::Algebra::NegatedPropertySet')) {
755 0 my @branches;
756
757 0 my @preds = @{ $path->predicates };
758 0 ▶ if (scalar(@preds)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @preds) 0 0 0
759 0 my $pvar = Attean::Variable->new(value => $self->new_temporary('nps'));
760 0 my $pvar_e = Attean::ValueExpression->new( value => $pvar );
761 0 my $t = Attean::TriplePattern->new($s, $pvar, $o);
762 0 my @vals = map { Attean::ValueExpression->new( value => $_ ) } @preds;
763 0 my $expr = Attean::FunctionExpression->new( children => [$pvar_e, @vals], operator => 'notin' );
764 0 my $bgp = Attean::Algebra::BGP->new( triples => [$t] );
765 0 my $f_fwd = Attean::Algebra::Filter->new( children => [$bgp], expression => $expr );
766 0 push(@branches, $f_fwd);
767 }
768  
769 0 my @rev = @{ $path->reversed };
770 0 ▶ if (scalar(@rev)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @rev) 0 0 0
771 0 my $pvar = Attean::Variable->new(value => $self->new_temporary('nps_rev'));
772 0 my $pvar_e = Attean::ValueExpression->new( value => $pvar );
773 0 my $t = Attean::TriplePattern->new($o, $pvar, $s);
774 0 my @vals = map { Attean::ValueExpression->new( value => $_ ) } @rev;
775 0 my $expr = Attean::FunctionExpression->new( children => [$pvar_e, @vals], operator => 'notin' );
776 0 my $bgp = Attean::Algebra::BGP->new( triples => [$t] );
777 0 my $f_rev = Attean::Algebra::Filter->new( children => [$bgp], expression => $expr );
778 0 push(@branches, $f_rev);
779 }
780  
781 0 ▶ if (scalar(@branches) == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @branches == 1) { } 0 0 0
782 0 return shift(@branches);
783 } else {
784 0 return Attean::Algebra::Union->new( children => \@branches );
785 }
786 } else {
787 0 return;
788 }
789 }
790
791 =item C<< new_projection( $plan, $distinct, @variable_names ) >>
792  
793 Return a new L<< Attean::Plan::Project >> plan over C<< $plan >>, projecting
794 the named variables. C<< $disctinct >> should be true if the caller can
795 guarantee that the resulting plan will produce distinct results, false otherwise.
796  
797 This method takes care of computing plan metadata such as the resulting ordering.
798  
799 =cut
800  
801 10 ▶ sub new_projection {
Subroutine new_projection: called CC=4 SCAR=15.4
Pod documented
802 10 my $self = shift;
803 10 my $plan = shift;
804 10 my $distinct = shift;
805 10 my @vars = @_;
806 10 my $order = $plan->ordered;
807 10 my @pvars = map { Attean::Variable->new($_) } @vars;
808
809 10 my %pvars = map { $_ => 1 } @vars;
810 10 my @porder;
811 10 CMP: foreach my $cmp (@{ $order }) {
812 0 my @cmpvars = $self->_comparator_referenced_variables($cmp);
813 0 foreach my $v (@cmpvars) {
814 0 ▶ unless ($pvars{ $v }) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($pvars{$v}) 0 0 0
815 # projection is dropping a variable used in this comparator
816 # so we lose any remaining ordering that the sub-plan had.
817 0 last CMP;
818 }
819 }
820
821 # all the variables used by this comparator are available after
822 # projection, so the resulting plan will continue to be ordered
823 # by this comparator
824 0 push(@porder, $cmp);
825 }
826
827 10 return Attean::Plan::Project->new(children => [$plan], variables => \@pvars, distinct => $distinct, ordered => \@porder);
828 }
829  
830 =item C<< bgp_join_plans( $bgp, $model, \@active_graphs, \@default_graphs, \@interesting_order, \@plansA, \@plansB, ... ) >>
831  
832 Returns a list of alternative plans for the join of a set of triples.
833 The arguments C<@plansA>, C<@plansB>, etc. represent alternative plans for each
834 triple participating in the join.
835  
836 =cut
837  
838 69 ▶ sub bgp_join_plans {
Subroutine bgp_join_plans: called CC=8 SCAR=20.8
Pod documented
839 69 my $self = shift;
840 69 my $bgp = shift;
841 69 my $model = shift;
842 69 my $active = shift;
843 69 my $default = shift;
844 69 my $interesting = shift;
845 69 my @triples = @_;
846
847 69 ▶ if (scalar(@triples)) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @triples) { } 62 7 69
848 62 my @plans = $self->joins_for_plan_alternatives($model, $active, $default, $interesting, @triples);
849 61 my @triples = @{ $bgp->triples };
850
851 # If the BGP does not contain any blanks, then the results are
852 # guaranteed to be distinct. Otherwise, we have to assume they're
853 # not distinct.
854 61 my $distinct = 1;
855 61 LOOP: foreach my $t (@triples) {
856 97 foreach my $b ($t->values_consuming_role('Attean::API::Blank')) {
857 0 $distinct = 0;
858 0 last LOOP;
859 }
860 97 foreach my $b ($t->values_consuming_role('Attean::API::Variable')) {
861 141 ▶ if ($b->value =~ /^[.]/) {
Branch: 1 branch
BranchTrueFalseTotal
if ($b->value =~ /^[.]/u) 6 135 141
862 # variable names starting with a dot represent placeholders introduced during query planning (with C<new_temporary>)
863 # they are not projectable, and so may cause an otherwise distinct result to become non-distinct
864 6 $distinct = 0;
865 6 last LOOP;
866 }
867 }
868 }
869
870 # Set the distinct flag on each of the top-level join plans that
871 # represents the entire BGP. (Sub-plans won't ever be marked as
872 # distinct, but that shouldn't matter to the rest of the planning
873 # process.)
874 61 ▶ if ($distinct) {
Branch: 1 branch
BranchTrueFalseTotal
if ($distinct) 55 6 61
875 55 foreach my $p (@plans) {
876 119 $p->distinct(1);
877 }
878 }
879  
880 61 return @plans;
881 } else {
882 # The empty BGP is a special case -- it results in a single join-identity result
883 7 my $r = Attean::Result->new( bindings => {} );
884 7 my $plan = Attean::Plan::Table->new( rows => [$r], variables => [], distinct => 1, ordered => [] );
885 7 return $plan;
886 }
887 }
888  
889 =item C<< group_join_plans( $model, \@active_graphs, \@default_graphs, \@interesting_order, \@plansA, \@plansB, ... ) >>
890  
891 Returns a list of alternative plans for the join of a set of sub-plans.
892 The arguments C<@plansA>, C<@plansB>, etc. represent alternative plans for each
893 sub-plan participating in the join.
894  
895 =cut
896  
897 11 ▶ sub group_join_plans {
Subroutine group_join_plans: called CC=1 SCAR=0.0
Pod documented
898 11 my $self = shift;
899 11 return $self->joins_for_plan_alternatives(@_);
900 }
901
902 =item C<< joins_for_plan_alternatives( $model, \@active_graphs, \@default_graphs, $interesting, \@plan_A, \@plan_B, ... ) >>
903  
904 Returns a list of alternative plans that may all be used to produce results
905 matching the join of C<< plan_A >>, C< plan_B >>, etc. Each plan array here
906 (e.g. C<< @plan_A >>) should contain equivalent plans.
907  
908 =cut
909  
910 1 ▶ sub joins_for_plan_alternatives {
Subroutine joins_for_plan_alternatives: called CC=1 SCAR=0.0
Pod documented
911 1 my $self = shift;
912 1 my $model = shift;
913 1 my $active_graphs = shift;
914 1 my $default_graphs = shift;
915 1 my $interesting = shift;
916 1 my @args = @_; # each $args[$i] here is an array reference containing alternate plans for element $i
917 1 die "This query planner does not seem to consume a Attean::API::JoinPlanner role (which is necessary for query planning)";
918 }
919
920 =item C<< access_plans( $model, $active_graphs, $pattern ) >>
921  
922 Returns a list of alternative L<Attean::API::Plan> objects that may be used to
923 produce results matching the L<Attean::API::TripleOrQuadPattern> $pattern in
924 the context of C<< $active_graphs >>.
925  
926 =cut
927  
928 # $pattern is a Attean::API::TripleOrQuadPattern object
929 # Return a Attean::API::Plan object that represents the evaluation of $pattern.
930 # e.g. different plans might represent different ways of producing the matches (table scan, index match, etc.)
931 100 ▶ sub access_plans {
Subroutine access_plans: called CC=4 SCAR=13.9
Pod documented
932 100 my $self = shift;
933 100 my $model = shift;
934 100 my $active_graphs = shift;
935 100 my $pattern = shift;
936 100 my @vars = map { $_->value } $pattern->values_consuming_role('Attean::API::Variable');
937 100 my %vars;
938 100 my $dup = 0;
939 100 foreach my $v (@vars) {
940 144 ▶ $dup++ if ($vars{$v}++);
Branch: 1 branch
BranchTrueFalseTotal
if $vars{$v}++ 0 144 144
941 }
942
943 100 my $distinct = 0; # TODO: is this pattern distinct? does it have blank nodes?
944
945 100 my @nodes = $pattern->values;
946 100 ▶ unless ($nodes[3]) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($nodes[3]) 100 0 100
947 100 $nodes[3] = $active_graphs;
948 }
949 100 my $plan = Attean::Plan::Quad->new(
950 subject => $nodes[0],
951 predicate => $nodes[1],
952 object => $nodes[2],
953 graph => $nodes[3],
954 values => \@nodes,
955 distinct => $distinct,
956 ordered => [],
957 );
958 100 return $plan;
959 }
960
961 =item C<< join_plans( $model, \@active_graphs, \@default_graphs, \@plan_left, \@plan_right, $type [, $expr] ) >>
962  
963 Returns a list of alternative plans for the join of one plan from C<< @plan_left >>
964 and one plan from C<< @plan_right >>. The join C<< $type >> must be one of
965 C<< 'inner' >>, C<< 'left' >>, or C<< 'minus' >>, indicating the join algorithm
966 to be used. If C<< $type >> is C<< 'left' >>, then the optional C<< $expr >>
967 may be used to supply a filter expression that should be used by the SPARQL
968 left-join algorithm.
969  
970 =cut
971  
972 # $lhs and $rhs are both Attean::API::Plan objects
973 # Return a Attean::API::Plan object that represents the evaluation of $lhs ⋈ $rhs.
974 # The $left and $minus flags indicate the type of the join to be performed (⟕ and ▷, respectively).
975 # e.g. different plans might represent different join algorithms (nested loop join, hash join, etc.) or different orderings ($lhs ⋈ $rhs or $rhs ⋈ $lhs)
976 263 ▶ sub join_plans {
Subroutine join_plans: called CC=10 SCAR=23.7
Pod documented
977 263 my $self = shift;
978 263 my $model = shift;
979 263 my $active_graphs = shift;
980 263 my $default_graphs = shift;
981 263 my $lplans = shift;
982 263 my $rplans = shift;
983 263 my $type = shift;
984 263 my $left = ($type eq 'left');
985 263 my $minus = ($type eq 'minus');
986 263 my $expr = shift;
987
988 263 my @plans;
989 263 ▶ Carp::confess unless (reftype($lplans) eq 'ARRAY');
Branch: 1 branch
BranchTrueFalseTotal
unless builtin::reftype($lplans) eq "ARRAY" 0 263 263
990 263 foreach my $lhs (@{ $lplans }) {
991 353 foreach my $rhs (@{ $rplans }) {
992 366 my @vars = (@{ $lhs->in_scope_variables }, @{ $rhs->in_scope_variables });
993 366 my %vars;
994 my %join_vars;
995 366 foreach my $v (@vars) {
996 1308 ▶ if ($vars{$v}++) {
Branch: 1 branch
BranchTrueFalseTotal
if ($vars{$v}++) 363 945 1308
997 363 $join_vars{$v}++;
998 }
999 }
1000 366 my @join_vars = keys %join_vars;
1001
1002 366 ▶ if ($left) {
Branch: 2 branches
BranchTrueFalseTotal
if ($left) { } 0 366 366
elsif ($minus) { } 0 366 366
1003 0 ▶ if (scalar(@join_vars) > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @join_vars > 0) 0 0 0
1004 0 push(@plans, Attean::Plan::HashJoin->new(children => [$lhs, $rhs], left => 1, expression => $expr, join_variables => \@join_vars, distinct => 0, ordered => []));
1005 }
1006 0 push(@plans, Attean::Plan::NestedLoopJoin->new(children => [$lhs, $rhs], left => 1, expression => $expr, join_variables => \@join_vars, distinct => 0, ordered => $lhs->ordered));
1007 } elsif ($minus) {
1008 # we can't use a hash join for MINUS queries, because of the definition of MINUS having a special case for compatible results that have disjoint domains
1009 0 push(@plans, Attean::Plan::NestedLoopJoin->new(children => [$lhs, $rhs], anti => 1, join_variables => \@join_vars, distinct => 0, ordered => $lhs->ordered));
1010 } else {
1011 366 ▶ if (scalar(@join_vars) > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar @join_vars > 0) 311 55 366
1012 # if there's shared variables (hopefully), we can also use a hash join
1013 311 push(@plans, Attean::Plan::HashJoin->new(children => [$lhs, $rhs], join_variables => \@join_vars, distinct => 0, ordered => []));
1014 311 push(@plans, Attean::Plan::HashJoin->new(children => [$rhs, $lhs], join_variables => \@join_vars, distinct => 0, ordered => []));
1015 # } else {
1016 # warn "No join vars for $lhs ⋈ $rhs";
1017 }
1018  
1019 # nested loop joins work in all cases
1020 366 push(@plans, Attean::Plan::NestedLoopJoin->new(children => [$lhs, $rhs], join_variables => \@join_vars, distinct => 0, ordered => $lhs->ordered));
1021 366 push(@plans, Attean::Plan::NestedLoopJoin->new(children => [$rhs, $lhs], join_variables => \@join_vars, distinct => 0, ordered => $rhs->ordered));
1022 }
1023 }
1024 }
1025
1026 263 return @plans;
1027 }
1028
1029
1030 0 ▶ sub _comparator_referenced_variables {
Subroutine _comparator_referenced_variables: not called CC=3 SCAR=24.8
1031 0 my $self = shift;
1032 0 my %vars;
1033 0 ▶ while (my $c = shift) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $c = shift()) 0 0 0
1034 0 my $expr = $c->expression;
1035 0 foreach my $v ($expr->in_scope_variables) {
1036 0 $vars{$v}++;
1037 }
1038 }
1039 0 return keys %vars;
1040 }
1041
1042 26 ▶ sub _comparators_are_stable_and_cover_vars {
Subroutine _comparators_are_stable_and_cover_vars: called CC=4 SCAR=15.9
1043 26 my $self = shift;
1044 26 my $cmps = shift;
1045 26 my @vars = @_;
1046 26 my %unseen = map { $_ => 1 } @vars;
1047 26 foreach my $c (@$cmps) {
1048 0 ▶ return 0 unless ($c->expression->is_stable);
Branch: 1 branch
BranchTrueFalseTotal
unless $c->expression->is_stable 0 0 0
1049 0 foreach my $v ($self->_comparator_referenced_variables($c)) {
1050 0 delete $unseen{$v};
1051 }
1052 }
1053 26 my @keys = keys %unseen;
1054 26 return (scalar(@keys) == 0);
1055 }
1056
1057 3 ▶ sub _order_by {
Subroutine _order_by: called CC=2 SCAR=6.9
1058 3 my $self = shift;
1059 3 my $algebra = shift;
1060 3 my ($exprs, $ascending, $svars);
1061 3 my @cmps = @{ $algebra->comparators };
1062 3 my %ascending;
1063 my %exprs;
1064 3 my @svars;
1065 3 foreach my $i (0 .. $#cmps) {
1066 3 my $var = $self->new_temporary('order');
1067 3 my $cmp = $cmps[$i];
1068 3 push(@svars, $var);
1069 3 $ascending{$var} = $cmp->ascending;
1070 3 $exprs{$var} = $cmp->expression;
1071 }
1072 3 return (\%exprs, \%ascending, \@svars);
1073 }
1074 }
1075  
1076 50 1;
1077  
1078 __END__
« Attean/SimpleQueryEvaluator.pm ↑ Summary Test/Attean/W3CManifestTestSuite.pm »