1 /* -*- Mode: c; c-basic-offset: 2 -*-
2 *
3 * rasqal_query_transform.c - Rasqal query transformations
4 *
5 * Copyright (C) 2004-2011, David Beckett http://www.dajobe.org/
6 * Copyright (C) 2004-2005, University of Bristol, UK http://www.bristol.ac.uk/
7 *
8 * This package is Free Software and part of Redland http://librdf.org/
9 *
10 * It is licensed under the following three licenses as alternatives:
11 * 1. GNU Lesser General Public License (LGPL) V2.1 or any newer version
12 * 2. GNU General Public License (GPL) V2 or any newer version
13 * 3. Apache License, V2.0 or any newer version
14 *
15 * You may not use this file except in compliance with at least one of
16 * the above three licenses.
17 *
18 * See LICENSE.html or LICENSE.txt at the top of this package for the
19 * complete terms and further detail along with the license texts for
20 * the licenses in COPYING.LIB, COPYING and LICENSE-2.0.txt respectively.
21 *
22 *
23 */
24
25 #ifdef HAVE_CONFIG_H
26 #include <rasqal_config.h>
27 #endif
28
29 #ifdef WIN32
30 #include <win32_rasqal_config.h>
31 #endif
32
33 #include <stdio.h>
34 #include <string.h>
35 #ifdef HAVE_STDLIB_H
36 #include <stdlib.h>
37 #endif
38 #include <stdarg.h>
39
40 #include "rasqal.h"
41 #include "rasqal_internal.h"
42
43
44 #if 0
45 #undef RASQAL_DEBUG
46 #define RASQAL_DEBUG 2
47 #endif
48
49 #define DEBUG_FH stderr
50
51 /* prototype for later */
52 static int rasqal_query_build_variables_use_map(rasqal_query* query, rasqal_projection* projection);
53 static int rasqal_query_graph_build_variables_use_map_binds(rasqal_graph_pattern* gp, unsigned short* vars_scope);
54 static void rasqal_query_expression_build_variables_use_map(unsigned short *use_map, rasqal_expression* e);
55 static void rasqal_query_let_build_variables_use_map(rasqal_query* query, unsigned short *use_map, rasqal_expression* e);
56 static int rasqal_query_let_build_variables_use_map_binds(rasqal_graph_pattern* gp, unsigned short* vars_scope);
57 static int rasqal_query_select_build_variables_use_map(rasqal_query* query, unsigned short *use_map, int width, rasqal_graph_pattern* gp);
58 static int rasqal_query_select_build_variables_use_map_binds(rasqal_query* query, unsigned short *use_map, int width, rasqal_graph_pattern* gp, unsigned short* vars_scope);
59 static int rasqal_query_union_build_variables_use_map_binds(rasqal_query* query, unsigned short *use_map, int width, rasqal_graph_pattern* gp, unsigned short* vars_scope);
60 static int rasqal_query_values_build_variables_use_map_binds(rasqal_query* query, unsigned short *use_map, int width, rasqal_graph_pattern* gp, unsigned short* vars_scope);
61
62
63 int
rasqal_query_expand_triple_qnames(rasqal_query * rq)64 rasqal_query_expand_triple_qnames(rasqal_query* rq)
65 {
66 int i;
67
68 if(!rq->triples)
69 return 0;
70
71 /* expand qnames in triples */
72 for(i = 0; i< raptor_sequence_size(rq->triples); i++) {
73 rasqal_triple* t = (rasqal_triple*)raptor_sequence_get_at(rq->triples, i);
74 if(rasqal_literal_expand_qname(rq, t->subject) ||
75 rasqal_literal_expand_qname(rq, t->predicate) ||
76 rasqal_literal_expand_qname(rq, t->object))
77 return 1;
78 }
79
80 return 0;
81 }
82
83
84 int
rasqal_sequence_has_qname(raptor_sequence * seq)85 rasqal_sequence_has_qname(raptor_sequence *seq)
86 {
87 int i;
88
89 if(!seq)
90 return 0;
91
92 /* expand qnames in triples */
93 for(i = 0; i< raptor_sequence_size(seq); i++) {
94 rasqal_triple* t = (rasqal_triple*)raptor_sequence_get_at(seq, i);
95 if(rasqal_literal_has_qname(t->subject) ||
96 rasqal_literal_has_qname(t->predicate) ||
97 rasqal_literal_has_qname(t->object))
98 return 1;
99 }
100
101 return 0;
102 }
103
104
105 static int
rasqal_graph_pattern_constraints_has_qname(rasqal_graph_pattern * gp)106 rasqal_graph_pattern_constraints_has_qname(rasqal_graph_pattern* gp)
107 {
108 int i;
109
110 /* check for qnames in sub graph patterns */
111 if(gp->graph_patterns) {
112 /* check for constraint qnames in rasqal_graph_patterns */
113 for(i = 0; i < raptor_sequence_size(gp->graph_patterns); i++) {
114 rasqal_graph_pattern *sgp;
115 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
116 if(rasqal_graph_pattern_constraints_has_qname(sgp))
117 return 1;
118 }
119 }
120
121 if(!gp->filter_expression)
122 return 0;
123
124 /* check for qnames in constraint expressions */
125 if(rasqal_expression_visit(gp->filter_expression,
126 rasqal_expression_has_qname, gp))
127 return 1;
128
129 return 0;
130 }
131
132
133 int
rasqal_query_constraints_has_qname(rasqal_query * rq)134 rasqal_query_constraints_has_qname(rasqal_query* rq)
135 {
136 if(!rq->query_graph_pattern)
137 return 0;
138
139 return rasqal_graph_pattern_constraints_has_qname(rq->query_graph_pattern);
140 }
141
142
143 int
rasqal_query_expand_graph_pattern_constraints_qnames(rasqal_query * rq,rasqal_graph_pattern * gp)144 rasqal_query_expand_graph_pattern_constraints_qnames(rasqal_query *rq,
145 rasqal_graph_pattern* gp)
146 {
147 int i;
148
149 /* expand qnames in sub graph patterns */
150 if(gp->graph_patterns) {
151 /* check for constraint qnames in rasqal_graph_patterns */
152 for(i = 0; i < raptor_sequence_size(gp->graph_patterns); i++) {
153 rasqal_graph_pattern *sgp;
154 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
155 if(rasqal_query_expand_graph_pattern_constraints_qnames(rq, sgp))
156 return 1;
157 }
158 }
159
160 if(!gp->filter_expression)
161 return 0;
162
163 /* expand qnames in constraint expressions */
164 if(rasqal_expression_visit(gp->filter_expression,
165 rasqal_expression_expand_qname, rq))
166 return 1;
167
168 return 0;
169 }
170
171
172 int
rasqal_query_expand_query_constraints_qnames(rasqal_query * rq)173 rasqal_query_expand_query_constraints_qnames(rasqal_query *rq)
174 {
175 return rasqal_query_expand_graph_pattern_constraints_qnames(rq,
176 rq->query_graph_pattern);
177 }
178
179
180 static int
rasqal_query_convert_blank_node_to_anonymous_variable(rasqal_query * rq,rasqal_literal * l)181 rasqal_query_convert_blank_node_to_anonymous_variable(rasqal_query *rq,
182 rasqal_literal *l)
183 {
184 rasqal_variable* v;
185
186 v = rasqal_variables_table_add2(rq->vars_table,
187 RASQAL_VARIABLE_TYPE_ANONYMOUS,
188 RASQAL_GOOD_CAST(unsigned char*, l->string),
189 l->string_len,
190 NULL);
191 /* rasqal_new_variable_typed took ownership of the l->string name.
192 * Set to NULL to prevent double delete. */
193 l->string = NULL;
194
195 if(!v)
196 return 1; /* error */
197
198 /* Convert the blank node literal into a variable literal */
199 l->type = RASQAL_LITERAL_VARIABLE;
200 l->value.variable = v;
201
202 return 0; /* success */
203 }
204
205
206 /**
207 * rasqal_query_build_anonymous_variables:
208 * @rq: query
209 *
210 * INTERNAL - Turn triple blank node parts into anonymous variables
211 *
212 * These are the blank nodes such as (Turtle/SPARQL):
213 * _:name or [] or [ prop value ] or ( collection of things )
214 *
215 * Return value: non-0 on failure
216 */
217 int
rasqal_query_build_anonymous_variables(rasqal_query * rq)218 rasqal_query_build_anonymous_variables(rasqal_query* rq)
219 {
220 int i;
221 int rc = 1;
222 raptor_sequence *s = rq->triples;
223
224 for(i = 0; i < raptor_sequence_size(s); i++) {
225 rasqal_triple* t = (rasqal_triple*)raptor_sequence_get_at(s, i);
226
227 if(t->subject->type == RASQAL_LITERAL_BLANK &&
228 rasqal_query_convert_blank_node_to_anonymous_variable(rq, t->subject))
229 goto done;
230
231 if(t->predicate->type == RASQAL_LITERAL_BLANK &&
232 rasqal_query_convert_blank_node_to_anonymous_variable(rq, t->predicate))
233 goto done;
234
235 if(t->object->type == RASQAL_LITERAL_BLANK &&
236 rasqal_query_convert_blank_node_to_anonymous_variable(rq, t->object))
237 goto done;
238 }
239
240 rc = 0;
241
242 done:
243 return rc;
244 }
245
246
247 /**
248 * rasqal_query_expand_wildcards:
249 * @rq: query
250 *
251 * INTERNAL - expand SPARQL SELECT * to a full list of select variables
252 *
253 * Return value: non-0 on failure
254 */
255 int
rasqal_query_expand_wildcards(rasqal_query * rq,rasqal_projection * projection)256 rasqal_query_expand_wildcards(rasqal_query* rq, rasqal_projection* projection)
257 {
258 int i;
259 int size;
260
261 if(rq->verb != RASQAL_QUERY_VERB_SELECT ||
262 !projection || !projection->wildcard)
263 return 0;
264
265 /* If 'SELECT *' was given, make the selects be a list of all variables */
266 size = rasqal_variables_table_get_named_variables_count(rq->vars_table);
267 for(i = 0; i < size; i++) {
268 rasqal_variable* v = rasqal_variables_table_get(rq->vars_table, i);
269
270 rasqal_query_add_variable(rq, v);
271 }
272
273 return 0;
274 }
275
276
277 /**
278 * rasqal_query_remove_duplicate_select_vars:
279 * @rq: query
280 *
281 * INTERNAL - remove duplicate variables in SELECT sequence and warn
282 *
283 * The order of the select variables is preserved.
284 *
285 * Return value: non-0 on failure
286 */
287 int
rasqal_query_remove_duplicate_select_vars(rasqal_query * rq,rasqal_projection * projection)288 rasqal_query_remove_duplicate_select_vars(rasqal_query* rq,
289 rasqal_projection* projection)
290 {
291 int i;
292 int modified = 0;
293 int size;
294 raptor_sequence* seq;
295 raptor_sequence* new_seq;
296
297 if(!projection)
298 return 1;
299
300 seq = projection->variables;
301 if(!seq)
302 return 0;
303
304 size = raptor_sequence_size(seq);
305 if(!size)
306 return 0;
307
308 new_seq = raptor_new_sequence((raptor_data_free_handler)rasqal_free_variable,
309 (raptor_data_print_handler)rasqal_variable_print);
310 if(!new_seq)
311 return 1;
312
313 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
314 RASQAL_DEBUG1("bound variables before deduping: ");
315 raptor_sequence_print(seq, DEBUG_FH);
316 fputs("\n", DEBUG_FH);
317 #endif
318
319 for(i = 0; i < size; i++) {
320 int j;
321 rasqal_variable *v;
322 int warned = 0;
323
324 v = (rasqal_variable*)raptor_sequence_get_at(seq, i);
325 if(!v)
326 continue;
327
328 for(j = 0; j < i; j++) {
329 rasqal_variable *v2;
330 v2 = (rasqal_variable*)raptor_sequence_get_at(seq, j);
331
332 if(v == v2) {
333 if(!warned) {
334 rasqal_log_warning_simple(rq->world,
335 RASQAL_WARNING_LEVEL_DUPLICATE_VARIABLE,
336 &rq->locator,
337 "Variable %s duplicated in SELECT.",
338 v->name);
339 warned = 1;
340 }
341 }
342 }
343 if(!warned) {
344 v = rasqal_new_variable_from_variable(v);
345 raptor_sequence_push(new_seq, v);
346 modified = 1;
347 }
348 }
349
350 if(modified) {
351 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
352 RASQAL_DEBUG1("bound variables after deduping: ");
353 raptor_sequence_print(new_seq, DEBUG_FH);
354 fputs("\n", DEBUG_FH);
355 #endif
356 raptor_free_sequence(projection->variables);
357 projection->variables = new_seq;
358 } else
359 raptor_free_sequence(new_seq);
360
361 return 0;
362 }
363
364
365 /**
366 * rasqal_query_build_variable_agg_use:
367 * @query: the query
368 *
369 * INTERNAL - calculate the usage of variables across all parts of the query
370 *
371 * Return value: array of variable usage info or NULL on failure
372 */
373 static unsigned short*
rasqal_query_build_variable_agg_use(rasqal_query * query)374 rasqal_query_build_variable_agg_use(rasqal_query* query)
375 {
376 int width;
377 int height;
378 unsigned short* agg_row;
379 int row_index;
380
381 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
382 height = RASQAL_VAR_USE_MAP_OFFSET_LAST + 1 + query->graph_pattern_count;
383
384 agg_row = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width), sizeof(unsigned short));
385 if(!agg_row)
386 return NULL;
387
388 for(row_index = 0; row_index < height; row_index++) {
389 unsigned short *row;
390 int i;
391
392 row = &query->variables_use_map[row_index * width];
393
394 for(i = 0; i < width; i++)
395 agg_row[i] |= row[i];
396 }
397
398 return agg_row;
399 }
400
401
402
403 /**
404 * rasqal_query_check_unused_variables:
405 * @query: the #rasqal_query to check
406 *
407 * INTERNAL - warn variables that are selected but not bound in a triple
408 *
409 * FIXME: Fails to handle variables bound in LET
410 *
411 * Return value: non-0 on failure
412 */
413 static int
rasqal_query_check_unused_variables(rasqal_query * query)414 rasqal_query_check_unused_variables(rasqal_query* query)
415 {
416 int i;
417 int size;
418
419 /* check only for named variables since only they can
420 * appear in SELECT $vars
421 */
422 size = rasqal_variables_table_get_named_variables_count(query->vars_table);
423 for(i = 0; i < size; i++) {
424 rasqal_variable *v;
425
426 v = rasqal_variables_table_get(query->vars_table, i);
427
428 if(!rasqal_query_variable_is_bound(query, v)) {
429 rasqal_log_warning_simple(query->world,
430 RASQAL_WARNING_LEVEL_UNUSED_SELECTED_VARIABLE,
431 &query->locator,
432 "Variable %s was selected but is unused in the query",
433 v->name);
434 }
435 }
436
437 return 0;
438 }
439
440
441 /**
442 * rasqal_query_merge_triple_patterns:
443 * @query: query (not used here)
444 * @gp: current graph pattern
445 * @data: visit data (not used here)
446 *
447 * INTERNAL - Join triple patterns in adjacent basic graph patterns into
448 * single basic graph pattern.
449 *
450 * For group graph pattern move all triples
451 * from { { a } { b } { c } D... }
452 * to { a b c D... }
453 * if the types of a, b, c are all BASIC GPs (just triples)
454 * D... is anything else
455 *
456 */
457 static int
rasqal_query_merge_triple_patterns(rasqal_query * query,rasqal_graph_pattern * gp,void * data)458 rasqal_query_merge_triple_patterns(rasqal_query* query,
459 rasqal_graph_pattern* gp,
460 void* data)
461 {
462 int* modified = (int*)data;
463 int checking;
464 int offset;
465
466 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
467 printf("rasqal_query_merge_triple_patterns: Checking graph pattern #%d:\n ", gp->gp_index);
468 rasqal_graph_pattern_print(gp, stdout);
469 fputs("\n", stdout);
470 RASQAL_DEBUG3("Columns %d to %d\n", gp->start_column, gp->end_column);
471 #endif
472
473 if(!gp->graph_patterns) {
474 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
475 RASQAL_DEBUG2("Ending graph patterns %d - no sub-graph patterns\n", gp->gp_index);
476 #endif
477 return 0;
478 }
479
480 if(gp->op != RASQAL_GRAPH_PATTERN_OPERATOR_GROUP) {
481 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
482 RASQAL_DEBUG3("Ending graph patterns %d - operator %s\n", gp->gp_index,
483 rasqal_graph_pattern_operator_as_string(gp->op));
484 #endif
485 return 0;
486 }
487
488
489 checking = 1;
490 offset = 0;
491 while(checking) {
492 int bgp_count;
493 rasqal_graph_pattern *dest_bgp;
494 raptor_sequence *seq;
495 int i, j;
496 int first = 0, last = 0;
497 int size = raptor_sequence_size(gp->graph_patterns);
498
499 /* find first basic graph pattern starting at offset */
500 for(i= offset; i < size; i++) {
501 rasqal_graph_pattern *sgp;
502
503 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
504
505 if(sgp->op == RASQAL_GRAPH_PATTERN_OPERATOR_BASIC) {
506 first = i;
507 break;
508 }
509 }
510
511 /* None found */
512 if(i >= size)
513 break;
514
515 /* Next time, start after this BGP */
516 offset = i+1;
517
518 /* count basic graph patterns */
519 bgp_count = 0;
520 dest_bgp = NULL; /* destination graph pattern */
521 for(j = i; j < size; j++) {
522 rasqal_graph_pattern *sgp;
523
524 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, j);
525
526 if(sgp->op == RASQAL_GRAPH_PATTERN_OPERATOR_BASIC) {
527 bgp_count++;
528
529 if(!dest_bgp)
530 dest_bgp = sgp;
531
532 last = j;
533 } else
534 break;
535 }
536
537
538 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
539 RASQAL_DEBUG3("Found sequence of %d basic sub-graph patterns in %d\n", bgp_count, gp->gp_index);
540 #endif
541 if(bgp_count < 2)
542 continue;
543
544 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
545 RASQAL_DEBUG3("OK to merge %d basic sub-graph patterns of %d\n", bgp_count, gp->gp_index);
546
547 RASQAL_DEBUG3("Initial columns %d to %d\n", gp->start_column, gp->end_column);
548 #endif
549
550 seq = raptor_new_sequence((raptor_data_free_handler)rasqal_free_graph_pattern, (raptor_data_print_handler)rasqal_graph_pattern_print);
551 if(!seq)
552 return 1;
553
554 for(i = 0; raptor_sequence_size(gp->graph_patterns) > 0; i++) {
555 rasqal_graph_pattern *sgp;
556
557 sgp = (rasqal_graph_pattern*)raptor_sequence_unshift(gp->graph_patterns);
558
559 if(i >= first && i <= last) {
560 if(sgp != dest_bgp) {
561 if(rasqal_graph_patterns_join(dest_bgp, sgp)) {
562 RASQAL_DEBUG1("Cannot join graph patterns\n");
563 *modified = -1; /* error flag */
564 }
565 rasqal_free_graph_pattern(sgp);
566 } else
567 raptor_sequence_push(seq, sgp);
568 } else
569 raptor_sequence_push(seq, sgp);
570 }
571 raptor_free_sequence(gp->graph_patterns);
572 gp->graph_patterns = seq;
573
574 if(!*modified)
575 *modified = 1;
576
577 } /* end while checking */
578
579
580 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
581 RASQAL_DEBUG3("Ending columns %d to %d\n", gp->start_column, gp->end_column);
582
583 RASQAL_DEBUG2("Ending graph pattern #%d\n ", gp->gp_index);
584 rasqal_graph_pattern_print(gp, stdout);
585 fputs("\n\n", stdout);
586 #endif
587
588 return 0;
589 }
590
591
592 /**
593 * rasqal_graph_pattern_move_constraints:
594 * @dest_gp: destination graph pattern
595 * @src_gp: src graph pattern
596 *
597 * INTERNAL - copy all constraints from @src_gp graph pattern to @src_gp graph pattern
598 *
599 * Return value: non-0 on error
600 */
601 int
rasqal_graph_pattern_move_constraints(rasqal_graph_pattern * dest_gp,rasqal_graph_pattern * src_gp)602 rasqal_graph_pattern_move_constraints(rasqal_graph_pattern* dest_gp,
603 rasqal_graph_pattern* src_gp)
604 {
605 int rc = 0;
606 rasqal_expression* fs = NULL;
607 rasqal_expression* e;
608
609 if(!src_gp->filter_expression)
610 return 0; /* no constraints is not an error */
611
612 e = rasqal_new_expression_from_expression(src_gp->filter_expression);
613 fs = dest_gp->filter_expression;
614 if(fs)
615 e = rasqal_new_2op_expression(e->world, RASQAL_EXPR_AND, fs, e);
616
617 dest_gp->filter_expression = e;
618
619 return rc;
620 }
621
622
623 /**
624 * rasqal_query_remove_empty_group_graph_patterns:
625 * @query: query (not used here)
626 * @gp: current graph pattern
627 * @data: visit data (not used here)
628 *
629 * INTERNAL - Remove empty group graph patterns
630 *
631 * Return value: non-0 on failure
632 */
633 static int
rasqal_query_remove_empty_group_graph_patterns(rasqal_query * query,rasqal_graph_pattern * gp,void * data)634 rasqal_query_remove_empty_group_graph_patterns(rasqal_query* query,
635 rasqal_graph_pattern* gp,
636 void* data)
637 {
638 int i;
639 int saw_empty_gp = 0;
640 raptor_sequence *seq;
641 int* modified = (int*)data;
642
643 if(!gp->graph_patterns)
644 return 0;
645
646 if(gp->op != RASQAL_GRAPH_PATTERN_OPERATOR_GROUP)
647 return 0;
648
649 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
650 printf("rasqal_query_remove_empty_group_graph_patterns: Checking graph pattern #%d:\n ", gp->gp_index);
651 rasqal_graph_pattern_print(gp, stdout);
652 fputs("\n", stdout);
653 #endif
654
655 for(i = 0; i < raptor_sequence_size(gp->graph_patterns); i++) {
656 rasqal_graph_pattern *sgp;
657
658 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
659
660 if(sgp->graph_patterns && !raptor_sequence_size(sgp->graph_patterns)) {
661 /* One is enough to know we need to rewrite */
662 saw_empty_gp = 1;
663 break;
664 }
665 }
666
667 if(!saw_empty_gp) {
668 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
669 RASQAL_DEBUG2("Ending graph patterns %d - saw no empty groups\n", gp->gp_index);
670 #endif
671 return 0;
672 }
673
674 seq = raptor_new_sequence((raptor_data_free_handler)rasqal_free_graph_pattern, (raptor_data_print_handler)rasqal_graph_pattern_print);
675 if(!seq) {
676 RASQAL_DEBUG1("Cannot create new gp sequence\n");
677 *modified = -1;
678 return 1;
679 }
680
681 while(raptor_sequence_size(gp->graph_patterns) > 0) {
682 rasqal_graph_pattern *sgp;
683
684 sgp = (rasqal_graph_pattern*)raptor_sequence_unshift(gp->graph_patterns);
685
686 if(sgp->graph_patterns && !raptor_sequence_size(sgp->graph_patterns)) {
687 rasqal_graph_pattern_move_constraints(gp, sgp);
688 rasqal_free_graph_pattern(sgp);
689 continue;
690 }
691
692 raptor_sequence_push(seq, sgp);
693 }
694 raptor_free_sequence(gp->graph_patterns);
695 gp->graph_patterns = seq;
696
697 if(!*modified)
698 *modified = 1;
699
700 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
701 RASQAL_DEBUG2("Ending graph pattern #%d\n ", gp->gp_index);
702 rasqal_graph_pattern_print(gp, stdout);
703 fputs("\n\n", stdout);
704 #endif
705
706 return 0;
707 }
708
709
710 /**
711 * rasqal_query_merge_graph_patterns:
712 * @query: query (not used here)
713 * @gp: current graph pattern
714 * @data: pointer to int modified flag
715 *
716 * INTERNAL - Merge graph patterns where possible
717 *
718 * When size = 1 (never for UNION)
719 * GROUP { A } -> A
720 * OPTIONAL { A } -> OPTIONAL { A }
721 *
722 * When size > 1
723 * GROUP { BASIC{2,} } -> merge-BASIC
724 * OPTIONAL { BASIC{2,} } -> OPTIONAL { merge-BASIC }
725 *
726 * Never merged: UNION
727 */
728 int
rasqal_query_merge_graph_patterns(rasqal_query * query,rasqal_graph_pattern * gp,void * data)729 rasqal_query_merge_graph_patterns(rasqal_query* query,
730 rasqal_graph_pattern* gp,
731 void* data)
732 {
733 rasqal_graph_pattern_operator op;
734 int merge_gp_ok = 0;
735 int all_gp_op_same = 0;
736 int i;
737 int size;
738 int* modified = (int*)data;
739
740 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
741 printf("rasqal_query_merge_graph_patterns: Checking graph pattern #%d:\n ",
742 gp->gp_index);
743 rasqal_graph_pattern_print(gp, stdout);
744 fputs("\n", stdout);
745 RASQAL_DEBUG3("Columns %d to %d\n", gp->start_column, gp->end_column);
746 #endif
747
748 if(!gp->graph_patterns) {
749 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
750 RASQAL_DEBUG3("Ending graph pattern #%d - operator %s: no sub-graph patterns\n", gp->gp_index,
751 rasqal_graph_pattern_operator_as_string(gp->op));
752 #endif
753 return 0;
754 }
755
756 if(gp->op != RASQAL_GRAPH_PATTERN_OPERATOR_GROUP) {
757 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
758 RASQAL_DEBUG3("Ending graph patterns %d - operator %s: not GROUP\n", gp->gp_index,
759 rasqal_graph_pattern_operator_as_string(gp->op));
760 #endif
761 return 0;
762 }
763
764 size = raptor_sequence_size(gp->graph_patterns);
765 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
766 RASQAL_DEBUG3("Doing %d sub-graph patterns of %d\n", size, gp->gp_index);
767 #endif
768 op = RASQAL_GRAPH_PATTERN_OPERATOR_UNKNOWN;
769 all_gp_op_same = 1;
770
771 for(i = 0; i < size; i++) {
772 rasqal_graph_pattern *sgp;
773
774 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
775
776 if(op == RASQAL_GRAPH_PATTERN_OPERATOR_UNKNOWN) {
777 op = sgp->op;
778 } else {
779 if(op != sgp->op) {
780 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
781 RASQAL_DEBUG4("Sub-graph pattern #%d is %s different from first %s, cannot merge\n",
782 i, rasqal_graph_pattern_operator_as_string(sgp->op),
783 rasqal_graph_pattern_operator_as_string(op));
784 #endif
785 all_gp_op_same = 0;
786 }
787 }
788 }
789
790 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
791 RASQAL_DEBUG2("Sub-graph patterns of %d done\n", gp->gp_index);
792 #endif
793
794 if(!all_gp_op_same) {
795 merge_gp_ok = 0;
796 goto merge_check_done;
797 }
798
799 if(size == 1) {
800 /* Never merge a FILTER to an outer GROUP since you lose
801 * knowledge about variable scope
802 */
803 merge_gp_ok = (op != RASQAL_GRAPH_PATTERN_OPERATOR_FILTER);
804 goto merge_check_done;
805 }
806
807
808 /* if size > 1 check if ALL sub-graph patterns are basic graph
809 * patterns and either:
810 * 1) a single triple
811 * 2) a single constraint
812 */
813 for(i = 0; i < size; i++) {
814 rasqal_graph_pattern *sgp;
815
816 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
817
818 if(sgp->op != RASQAL_GRAPH_PATTERN_OPERATOR_BASIC) {
819 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
820 RASQAL_DEBUG3("Found %s sub-graph pattern #%d\n",
821 rasqal_graph_pattern_operator_as_string(sgp->op),
822 sgp->gp_index);
823 #endif
824 merge_gp_ok = 0;
825 break;
826 }
827
828 /* not ok if there are >1 triples */
829 if(sgp->triples && (sgp->end_column-sgp->start_column+1) > 1) {
830 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
831 RASQAL_DEBUG2("Found >1 triples in sub-graph pattern #%d\n", sgp->gp_index);
832 #endif
833 merge_gp_ok = 0;
834 break;
835 }
836
837 /* not ok if there are triples and constraints */
838 if(sgp->triples && sgp->filter_expression) {
839 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
840 RASQAL_DEBUG2("Found triples and constraints in sub-graph pattern #%d\n", sgp->gp_index);
841 #endif
842 merge_gp_ok = 0;
843 break;
844 }
845
846 /* was at least 1 OK sub graph-pattern */
847 merge_gp_ok = 1;
848 }
849
850 merge_check_done:
851
852 if(merge_gp_ok) {
853 raptor_sequence *seq;
854
855 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
856 RASQAL_DEBUG2("OK to merge sub-graph patterns of %d\n", gp->gp_index);
857
858 RASQAL_DEBUG3("Initial columns %d to %d\n", gp->start_column, gp->end_column);
859 #endif
860
861 /* Pretend dest is an empty basic graph pattern */
862 seq = gp->graph_patterns;
863 gp->graph_patterns = NULL;
864 gp->op = op;
865
866 while(raptor_sequence_size(seq) > 0) {
867 rasqal_graph_pattern *sgp;
868
869 sgp = (rasqal_graph_pattern*)raptor_sequence_unshift(seq);
870
871 /* fake this so that the join happens */
872 sgp->op = gp->op;
873 if(rasqal_graph_patterns_join(gp, sgp)) {
874 RASQAL_DEBUG1("Cannot join graph patterns\n");
875 *modified = -1; /* error flag */
876 }
877
878 rasqal_free_graph_pattern(sgp);
879 }
880
881 /* If result is 'basic' but contains graph patterns, turn it into a group */
882 if(gp->graph_patterns && gp->op == RASQAL_GRAPH_PATTERN_OPERATOR_BASIC)
883 gp->op = RASQAL_GRAPH_PATTERN_OPERATOR_GROUP;
884
885 /* Delete any evidence of sub graph patterns */
886 raptor_free_sequence(seq);
887
888 if(!*modified)
889 *modified = 1;
890
891 } else {
892 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
893 RASQAL_DEBUG2("NOT OK to merge sub-graph patterns of %d\n", gp->gp_index);
894 #endif
895 }
896
897 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
898 if(merge_gp_ok) {
899 RASQAL_DEBUG2("Ending graph pattern #%d\n ", gp->gp_index);
900 rasqal_graph_pattern_print(gp, stdout);
901 fputs("\n\n", stdout);
902 }
903 #endif
904
905 return 0;
906 }
907
908
909 /**
910 * rasqal_query_filter_variable_scope:
911 * @query: query
912 * @gp: current graph pattern
913 * @data: pointer to int modified flag
914 *
915 * Replace a FILTER in a GROUP refering to out-of-scope var with FALSE
916 *
917 * For each variable in a FILTER expression, if there is one defined
918 * outside the GROUP, the FILTER is always FALSE - so set it thus and
919 * the tree of GP is modified
920 *
921 * Return value: 0
922 */
923 static int
rasqal_query_filter_variable_scope(rasqal_query * query,rasqal_graph_pattern * gp,void * data)924 rasqal_query_filter_variable_scope(rasqal_query* query,
925 rasqal_graph_pattern* gp,
926 void* data)
927 {
928 int vari;
929 int* modified = (int*)data;
930 rasqal_graph_pattern *qgp;
931 int size;
932
933 /* Scan up from FILTER GPs */
934 if(gp->op != RASQAL_GRAPH_PATTERN_OPERATOR_FILTER)
935 return 0;
936
937 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
938 RASQAL_DEBUG2("Checking FILTER graph pattern #%d:\n ", gp->gp_index);
939 rasqal_graph_pattern_print(gp, stderr);
940 fputs("\n", stderr);
941 #endif
942
943 qgp = rasqal_query_get_query_graph_pattern(query);
944
945 size = rasqal_variables_table_get_named_variables_count(query->vars_table);
946
947 for(vari = 0; vari < size; vari++) {
948 rasqal_variable* v = rasqal_variables_table_get(query->vars_table, vari);
949 int var_in_scope = 2;
950 rasqal_graph_pattern *sgp;
951
952 if(!rasqal_expression_mentions_variable(gp->filter_expression, v))
953 continue;
954 RASQAL_DEBUG3("FILTER GP #%d expression mentions %s\n",
955 gp->gp_index, v->name);
956
957 sgp = gp;
958 while(1) {
959 int bound_here;
960
961 sgp = rasqal_graph_pattern_get_parent(query, sgp, qgp);
962 if(!sgp)
963 break;
964
965 bound_here = rasqal_graph_pattern_variable_bound_below(sgp, v);
966 RASQAL_DEBUG4("Checking parent GP #%d op %s - bound below: %d\n",
967 sgp->gp_index,
968 rasqal_graph_pattern_operator_as_string(sgp->op),
969 bound_here);
970
971 if(sgp->op == RASQAL_GRAPH_PATTERN_OPERATOR_OPTIONAL) {
972 /* Collapse OPTIONAL { GROUP } */
973 var_in_scope++;
974 }
975
976 if(sgp->op == RASQAL_GRAPH_PATTERN_OPERATOR_GROUP) {
977 var_in_scope--;
978 if(bound_here) {
979 /* It was defined in first GROUP so life is good - done */
980 if(var_in_scope == 1)
981 break;
982
983 /* It was defined in an outer GROUP so this is bad */
984 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
985 RASQAL_DEBUG3("FILTER Variable %s defined in GROUP GP #%d and now out of scope\n", v->name, sgp->gp_index);
986 #endif
987 var_in_scope = 0;
988 break;
989 }
990 }
991 }
992
993 if(!var_in_scope) {
994 rasqal_literal* l;
995
996 l = rasqal_new_boolean_literal(query->world, 0);
997 /* In-situ conversion of filter_expression to a literal expression */
998 rasqal_expression_convert_to_literal(gp->filter_expression, l);
999 *modified = 1;
1000
1001 RASQAL_DEBUG2("FILTER Variable %s was defined outside FILTER's parent group\n", v->name);
1002 break;
1003 }
1004
1005 }
1006
1007 return 0;
1008 }
1009
1010
1011 struct folding_state {
1012 rasqal_query* query;
1013 int changes;
1014 int failed;
1015 };
1016
1017
1018 static int
rasqal_expression_foreach_fold(void * user_data,rasqal_expression * e)1019 rasqal_expression_foreach_fold(void *user_data, rasqal_expression *e)
1020 {
1021 struct folding_state *st = (struct folding_state*)user_data;
1022 rasqal_query* query;
1023 rasqal_literal* l;
1024 int error = 0;
1025
1026 /* skip if already a literal or this expression tree is not constant */
1027 if(e->op == RASQAL_EXPR_LITERAL || !rasqal_expression_is_constant(e))
1028 return 0;
1029
1030 #ifdef RASQAL_DEBUG
1031 RASQAL_DEBUG2("folding expression %p: ", e);
1032 rasqal_expression_print(e, DEBUG_FH);
1033 fprintf(DEBUG_FH, "\n");
1034 #endif
1035
1036 query = st->query;
1037 l = rasqal_expression_evaluate2(e, query->eval_context, &error);
1038 if(error) {
1039 st->failed++;
1040 return 1;
1041 }
1042
1043 /* In-situ conversion of 'e' to a literal expression */
1044 rasqal_expression_convert_to_literal(e, l);
1045
1046 #ifdef RASQAL_DEBUG
1047 RASQAL_DEBUG1("folded expression now: ");
1048 rasqal_expression_print(e, DEBUG_FH);
1049 fputc('\n', DEBUG_FH);
1050 #endif
1051
1052 /* change made */
1053 st->changes++;
1054
1055 return 0;
1056 }
1057
1058
1059 static int
rasqal_query_expression_fold(rasqal_query * rq,rasqal_expression * e)1060 rasqal_query_expression_fold(rasqal_query* rq, rasqal_expression* e)
1061 {
1062 struct folding_state st;
1063
1064 st.query = rq;
1065 while(1) {
1066 st.changes = 0;
1067 st.failed = 0;
1068 rasqal_expression_visit(e, rasqal_expression_foreach_fold,
1069 (void*)&st);
1070 if(!st.changes || st.failed)
1071 break;
1072 }
1073
1074 return st.failed;
1075 }
1076
1077
1078 static int
rasqal_graph_pattern_fold_expressions(rasqal_query * rq,rasqal_graph_pattern * gp)1079 rasqal_graph_pattern_fold_expressions(rasqal_query* rq,
1080 rasqal_graph_pattern* gp)
1081 {
1082 if(!gp)
1083 return 1;
1084
1085 /* fold expressions in sub graph patterns */
1086 if(gp->graph_patterns) {
1087 int i;
1088
1089 for(i = 0; i < raptor_sequence_size(gp->graph_patterns); i++) {
1090 rasqal_graph_pattern *sgp;
1091
1092 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
1093
1094 if(rasqal_graph_pattern_fold_expressions(rq, sgp))
1095 return 1;
1096 }
1097 }
1098
1099 if(gp->filter_expression)
1100 return rasqal_query_expression_fold(rq, gp->filter_expression);
1101
1102 return 0;
1103 }
1104
1105
1106 static int
rasqal_query_fold_expressions(rasqal_query * rq)1107 rasqal_query_fold_expressions(rasqal_query* rq)
1108 {
1109 rasqal_graph_pattern *gp = rq->query_graph_pattern;
1110 int order_size;
1111 raptor_sequence *order_seq = rasqal_query_get_order_conditions_sequence(rq);
1112
1113 if(gp)
1114 rasqal_graph_pattern_fold_expressions(rq, gp);
1115
1116 if(!order_seq)
1117 return 0;
1118
1119 order_size = raptor_sequence_size(order_seq);
1120 if(order_size) {
1121 int i;
1122
1123 for(i = 0; i < order_size; i++) {
1124 rasqal_expression* e;
1125
1126 e = (rasqal_expression*)raptor_sequence_get_at(order_seq, i);
1127 rasqal_query_expression_fold(rq, e);
1128 }
1129 }
1130
1131 return 0;
1132 }
1133
1134
1135 static int
rasqal_query_prepare_count_graph_pattern(rasqal_query * query,rasqal_graph_pattern * gp,void * data)1136 rasqal_query_prepare_count_graph_pattern(rasqal_query* query,
1137 rasqal_graph_pattern* gp,
1138 void* data)
1139 {
1140 raptor_sequence* seq = (raptor_sequence*)data;
1141
1142 if(raptor_sequence_push(seq, gp)) {
1143 query->failed = 1;
1144 return 1;
1145 }
1146 gp->gp_index = (query->graph_pattern_count++);
1147 return 0;
1148 }
1149
1150
1151 /**
1152 * rasqal_query_enumerate_graph_patterns:
1153 * @query: query object
1154 *
1155 * INTERNAL - Label all graph patterns in query graph patterns with an index 0..
1156 *
1157 * Used for the size of the graph pattern execution data array.
1158 * Used to allocate in rasqal_query_build_variables_use_map()
1159 * and rasqal_query_build_variable_agg_use() and used in
1160 * rasqal_query_print_variables_use_map() and
1161 * rasqal_query_variable_is_bound().
1162 *
1163 * Return value: non-0 on failure
1164 */
1165 static int
rasqal_query_enumerate_graph_patterns(rasqal_query * query)1166 rasqal_query_enumerate_graph_patterns(rasqal_query *query)
1167 {
1168 query->graph_pattern_count = 0;
1169
1170 if(query->graph_patterns_sequence)
1171 raptor_free_sequence(query->graph_patterns_sequence);
1172
1173 /* This sequence stores shared pointers to the graph patterns it
1174 * finds, indexed by the gp_index
1175 */
1176 query->graph_patterns_sequence = raptor_new_sequence(NULL, NULL);
1177 if(!query->graph_patterns_sequence)
1178 return 1;
1179
1180 return rasqal_query_graph_pattern_visit2(query,
1181 rasqal_query_prepare_count_graph_pattern,
1182 query->graph_patterns_sequence);
1183 }
1184
1185
1186 /**
1187 * rasqal_query_build_variables_use:
1188 * @query: query
1189 *
1190 * INTERNAL - build structures recording variable use in the query
1191 *
1192 * Should be called if the query variable usage is modified such as
1193 * a variable added during query planning.
1194 *
1195 * Return value: non-0 on failure
1196 */
1197 int
rasqal_query_build_variables_use(rasqal_query * query,rasqal_projection * projection)1198 rasqal_query_build_variables_use(rasqal_query* query,
1199 rasqal_projection* projection)
1200 {
1201 int rc;
1202
1203 /* create query->variables_use_map that marks where a variable is
1204 * mentioned, bound or used in a graph pattern.
1205 */
1206 rc = rasqal_query_build_variables_use_map(query, projection);
1207 if(rc)
1208 return rc;
1209
1210 if(1) {
1211 unsigned short* agg_row;
1212 int i;
1213 int errors = 0;
1214
1215 agg_row = rasqal_query_build_variable_agg_use(query);
1216 if(!agg_row)
1217 return 1;
1218
1219 for(i = 0; 1; i++) {
1220 rasqal_variable* v = rasqal_variables_table_get(query->vars_table, i);
1221 if(!v)
1222 break;
1223
1224 if( (agg_row[i] & RASQAL_VAR_USE_BOUND_HERE) &&
1225 !(agg_row[i] & RASQAL_VAR_USE_MENTIONED_HERE)) {
1226 rasqal_log_warning_simple(query->world,
1227 RASQAL_WARNING_LEVEL_VARIABLE_UNUSED,
1228 &query->locator,
1229 "Variable %s was bound but is unused in the query",
1230 v->name);
1231 } else if(!(agg_row[i] & RASQAL_VAR_USE_BOUND_HERE) &&
1232 (agg_row[i] & RASQAL_VAR_USE_MENTIONED_HERE)) {
1233 rasqal_log_warning_simple(query->world,
1234 RASQAL_WARNING_LEVEL_SELECTED_NEVER_BOUND,
1235 &query->locator,
1236 "Variable %s was used but is not bound in the query",
1237 v->name);
1238 } else if(!(agg_row[i] & RASQAL_VAR_USE_BOUND_HERE) &&
1239 !(agg_row[i] & RASQAL_VAR_USE_MENTIONED_HERE)) {
1240 rasqal_log_error_simple(query->world,
1241 RAPTOR_LOG_LEVEL_ERROR,
1242 &query->locator,
1243 "Variable %s was not bound and not used in the query (where is it from?)",
1244 v->name);
1245 errors++;
1246 }
1247 }
1248
1249 RASQAL_FREE(shortarray, agg_row);
1250
1251 if(errors)
1252 return 1;
1253 }
1254
1255
1256
1257 return rc;
1258 }
1259
1260
1261 /**
1262 * rasqal_query_prepare_common:
1263 * @query: query
1264 *
1265 * INTERNAL - initialise the remainder of the query structures
1266 *
1267 * Does not do any execution prepration - this is once-only stuff.
1268 *
1269 * NOTE: The caller is responsible for ensuring this is called at
1270 * most once. This is currently enforced by rasqal_query_prepare()
1271 * using the query->prepared flag when it calls the query factory
1272 * prepare method which does the query string parsing and ends by
1273 * calling this function.
1274 *
1275 * Return value: non-0 on failure
1276 */
1277 int
rasqal_query_prepare_common(rasqal_query * query)1278 rasqal_query_prepare_common(rasqal_query *query)
1279 {
1280 int rc = 1;
1281 rasqal_projection* projection;
1282
1283 if(!query->triples)
1284 goto done;
1285
1286 /* turn SELECT $a, $a into SELECT $a - editing the projection */
1287 projection = rasqal_query_get_projection(query);
1288 if(projection) {
1289 if(rasqal_query_remove_duplicate_select_vars(query, projection))
1290 goto done;
1291 }
1292
1293 rasqal_query_fold_expressions(query);
1294
1295 if(query->query_graph_pattern) {
1296 /* This query prepare processing requires a query graph pattern.
1297 * Not the case for a legal query like 'DESCRIBE <uri>'
1298 */
1299
1300 int modified;
1301
1302 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1303 fputs("Initial query graph pattern:\n ", DEBUG_FH);
1304 rasqal_graph_pattern_print(query->query_graph_pattern, DEBUG_FH);
1305 fputs("\n", DEBUG_FH);
1306 #endif
1307
1308 do {
1309 modified = 0;
1310
1311 rc = rasqal_query_graph_pattern_visit2(query,
1312 rasqal_query_merge_triple_patterns,
1313 &modified);
1314 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1315 fprintf(DEBUG_FH, "modified=%d after merge triples, query graph pattern now:\n ", modified);
1316 rasqal_graph_pattern_print(query->query_graph_pattern, DEBUG_FH);
1317 fputs("\n", DEBUG_FH);
1318 #endif
1319 if(rc) {
1320 modified = rc;
1321 break;
1322 }
1323
1324 rc = rasqal_query_graph_pattern_visit2(query,
1325 rasqal_query_remove_empty_group_graph_patterns,
1326 &modified);
1327
1328 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1329 fprintf(DEBUG_FH, "modified=%d after remove empty groups, query graph pattern now:\n ", modified);
1330 rasqal_graph_pattern_print(query->query_graph_pattern, DEBUG_FH);
1331 fputs("\n", DEBUG_FH);
1332 #endif
1333 if(rc) {
1334 modified = rc;
1335 break;
1336 }
1337
1338 rc = rasqal_query_graph_pattern_visit2(query,
1339 rasqal_query_merge_graph_patterns,
1340 &modified);
1341
1342 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1343 fprintf(DEBUG_FH, "modified=%d after merge graph patterns, query graph pattern now:\n ", modified);
1344 rasqal_graph_pattern_print(query->query_graph_pattern, DEBUG_FH);
1345 fputs("\n", DEBUG_FH);
1346 #endif
1347 if(rc) {
1348 modified = rc;
1349 break;
1350 }
1351
1352 } while(modified > 0);
1353
1354 rc = modified; /* error if modified<0, success if modified==0 */
1355 if(rc)
1356 goto done;
1357
1358 rc = rasqal_query_enumerate_graph_patterns(query);
1359 if(rc)
1360 goto done;
1361
1362 rc = rasqal_query_build_variables_use(query, projection);
1363 if(rc)
1364 goto done;
1365
1366 /* Turn FILTERs that refer to out-of-scope variables into FALSE */
1367 (void)rasqal_query_graph_pattern_visit2(query,
1368 rasqal_query_filter_variable_scope,
1369 &modified);
1370 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1371 fprintf(DEBUG_FH, "modified=%d after filter variable scope, query graph pattern now:\n ", modified);
1372 rasqal_graph_pattern_print(query->query_graph_pattern, DEBUG_FH);
1373 fputs("\n", DEBUG_FH);
1374 #endif
1375
1376 /* warn if any of the selected named variables are not in a triple */
1377 rc = rasqal_query_check_unused_variables(query);
1378 if(rc)
1379 goto done;
1380
1381 }
1382
1383
1384 rc = 0;
1385
1386 done:
1387 return rc;
1388 }
1389
1390
1391 /**
1392 * rasqal_graph_patterns_join:
1393 * @dest_gp: destination graph pattern
1394 * @src_gp: src graph pattern
1395 *
1396 * INTERNAL - merge @src_gp graph pattern into @dest_gp graph pattern
1397 *
1398 * Return value: non-0 on error
1399 */
1400 int
rasqal_graph_patterns_join(rasqal_graph_pattern * dest_gp,rasqal_graph_pattern * src_gp)1401 rasqal_graph_patterns_join(rasqal_graph_pattern *dest_gp,
1402 rasqal_graph_pattern *src_gp)
1403 {
1404 int rc;
1405
1406 if(!src_gp || !dest_gp)
1407 return 0;
1408
1409 if(src_gp->op != dest_gp->op) {
1410 RASQAL_DEBUG3("Source operator %s != Destination operator %s, ending\n",
1411 rasqal_graph_pattern_operator_as_string(src_gp->op),
1412 rasqal_graph_pattern_operator_as_string(dest_gp->op));
1413 return 1;
1414 }
1415
1416 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1417 RASQAL_DEBUG2("Joining graph pattern #%d\n ", src_gp->gp_index);
1418 rasqal_graph_pattern_print(src_gp, DEBUG_FH);
1419 fprintf(DEBUG_FH, "\nto graph pattern #%d\n ", dest_gp->gp_index);
1420 rasqal_graph_pattern_print(dest_gp, DEBUG_FH);
1421 fprintf(DEBUG_FH, "\nboth of operator %s\n",
1422 rasqal_graph_pattern_operator_as_string(src_gp->op));
1423 #endif
1424
1425
1426 if(src_gp->graph_patterns) {
1427 if(!dest_gp->graph_patterns) {
1428 dest_gp->graph_patterns = raptor_new_sequence((raptor_data_free_handler)rasqal_free_graph_pattern,
1429 (raptor_data_print_handler)rasqal_graph_pattern_print);
1430 if(!dest_gp->graph_patterns)
1431 return -1;
1432 }
1433
1434 rc = raptor_sequence_join(dest_gp->graph_patterns, src_gp->graph_patterns);
1435 if(rc)
1436 return rc;
1437 }
1438
1439 if(src_gp->triples) {
1440 int start_c = src_gp->start_column;
1441 int end_c = src_gp->end_column;
1442
1443 /* if this is our first triple, save a free/alloc */
1444 dest_gp->triples = src_gp->triples;
1445 src_gp->triples = NULL;
1446
1447 if((dest_gp->start_column < 0) || start_c < dest_gp->start_column)
1448 dest_gp->start_column = start_c;
1449 if((dest_gp->end_column < 0) || end_c > dest_gp->end_column)
1450 dest_gp->end_column = end_c;
1451
1452 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1453 RASQAL_DEBUG3("Moved triples from columns %d to %d\n", start_c, end_c);
1454 RASQAL_DEBUG3("Columns now %d to %d\n", dest_gp->start_column, dest_gp->end_column);
1455 #endif
1456 }
1457
1458 rc = rasqal_graph_pattern_move_constraints(dest_gp, src_gp);
1459
1460 if(src_gp->origin) {
1461 dest_gp->origin = src_gp->origin;
1462 src_gp->origin = NULL;
1463 }
1464
1465 if(src_gp->var) {
1466 dest_gp->var = src_gp->var;
1467 src_gp->var = NULL;
1468 }
1469
1470 if(src_gp->projection) {
1471 dest_gp->projection = src_gp->projection;
1472 src_gp->projection = NULL;
1473 }
1474
1475 if(src_gp->modifier) {
1476 dest_gp->modifier = src_gp->modifier;
1477 src_gp->modifier = NULL;
1478 }
1479
1480 if(src_gp->bindings) {
1481 dest_gp->bindings = src_gp->bindings;
1482 src_gp->bindings = NULL;
1483 }
1484
1485 dest_gp->silent = src_gp->silent;
1486
1487 #if defined(RASQAL_DEBUG) && RASQAL_DEBUG > 1
1488 RASQAL_DEBUG2("Result graph pattern #%d\n ", dest_gp->gp_index);
1489 rasqal_graph_pattern_print(dest_gp, stdout);
1490 fputs("\n", stdout);
1491 #endif
1492
1493 return rc;
1494 }
1495
1496
1497 /**
1498 * rasqal_query_triples_build_variables_use_map_row:
1499 * @triples: triples sequence to use
1500 * @use_map_row: 1D array of size num. variables to write
1501 * @start_column: first column in triples array
1502 * @end_column: last column in triples array
1503 *
1504 * INTERNAL - Mark variables mentioned in a sequence of triples
1505 *
1506 **/
1507 static int
rasqal_query_triples_build_variables_use_map_row(raptor_sequence * triples,unsigned short * use_map_row,int start_column,int end_column)1508 rasqal_query_triples_build_variables_use_map_row(raptor_sequence *triples,
1509 unsigned short *use_map_row,
1510 int start_column,
1511 int end_column)
1512 {
1513 int rc = 0;
1514 int col;
1515
1516 for(col = start_column; col <= end_column; col++) {
1517 rasqal_triple *t;
1518 rasqal_variable *v;
1519
1520 t = (rasqal_triple*)raptor_sequence_get_at(triples, col);
1521
1522 if((v = rasqal_literal_as_variable(t->subject))) {
1523 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
1524 }
1525
1526 if((v = rasqal_literal_as_variable(t->predicate))) {
1527 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
1528 }
1529
1530 if((v = rasqal_literal_as_variable(t->object))) {
1531 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
1532 }
1533
1534 if(t->origin) {
1535 if((v = rasqal_literal_as_variable(t->origin))) {
1536 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
1537 }
1538 }
1539
1540 }
1541
1542 return rc;
1543 }
1544
1545
1546 /**
1547 * rasqal_query_graph_build_variables_use_map:
1548 * @use_map_row: 1D array of size num. variables to write
1549 * @literal: graph origin literal
1550 *
1551 * INTERNAL - Mark variables mentioned in a GRAPH graph pattern
1552 *
1553 **/
1554 static int
rasqal_query_graph_build_variables_use_map(unsigned short * use_map_row,rasqal_literal * origin)1555 rasqal_query_graph_build_variables_use_map(unsigned short *use_map_row,
1556 rasqal_literal *origin)
1557 {
1558 rasqal_variable* v = rasqal_literal_as_variable(origin);
1559
1560 if(v)
1561 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
1562
1563 return 0;
1564 }
1565
1566
1567
1568 /**
1569 * rasqal_query_graph_pattern_build_variables_use_map:
1570 * @query: the #rasqal_query to find the variables in
1571 * @use_map: 2D array of (num. variables x num. GPs) to write
1572 * @width: width of array (num. variables)
1573 * @gp: graph pattern to use
1574 *
1575 * INTERNAL - Mark where variables are used (mentioned) in a graph_pattern tree walk
1576 *
1577 **/
1578 static int
rasqal_query_graph_pattern_build_variables_use_map(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp)1579 rasqal_query_graph_pattern_build_variables_use_map(rasqal_query* query,
1580 unsigned short *use_map,
1581 int width,
1582 rasqal_graph_pattern *gp)
1583 {
1584 int offset;
1585
1586 if(gp->graph_patterns) {
1587 int i;
1588
1589 for(i = 0; i < raptor_sequence_size(gp->graph_patterns); i++) {
1590 rasqal_graph_pattern *sgp;
1591 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
1592 if(rasqal_query_graph_pattern_build_variables_use_map(query, use_map,
1593 width, sgp))
1594 return 1;
1595 }
1596 }
1597
1598
1599 /* write to the 1D array for this GP */
1600 offset = (gp->gp_index + RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) * width;
1601 switch(gp->op) {
1602 case RASQAL_GRAPH_PATTERN_OPERATOR_BASIC:
1603 /* BGP (part 1) - everything is a mention */
1604 rasqal_query_triples_build_variables_use_map_row(query->triples,
1605 &use_map[offset],
1606 gp->start_column,
1607 gp->end_column);
1608 break;
1609
1610 case RASQAL_GRAPH_PATTERN_OPERATOR_GRAPH:
1611 /* Mentions the graph variable */
1612 rasqal_query_graph_build_variables_use_map(&use_map[offset],
1613 gp->origin);
1614 break;
1615
1616 case RASQAL_GRAPH_PATTERN_OPERATOR_FILTER:
1617 /* Only mentions */
1618 rasqal_query_expression_build_variables_use_map(&use_map[offset],
1619 gp->filter_expression);
1620 break;
1621
1622 case RASQAL_GRAPH_PATTERN_OPERATOR_LET:
1623 /* Mentions in expression */
1624 rasqal_query_let_build_variables_use_map(query, &use_map[offset],
1625 gp->filter_expression);
1626 break;
1627
1628 case RASQAL_GRAPH_PATTERN_OPERATOR_SELECT:
1629 rasqal_query_select_build_variables_use_map(query, &use_map[offset],
1630 width, gp);
1631 break;
1632
1633 case RASQAL_GRAPH_PATTERN_OPERATOR_OPTIONAL:
1634 case RASQAL_GRAPH_PATTERN_OPERATOR_UNION:
1635 case RASQAL_GRAPH_PATTERN_OPERATOR_GROUP:
1636 case RASQAL_GRAPH_PATTERN_OPERATOR_SERVICE:
1637 case RASQAL_GRAPH_PATTERN_OPERATOR_MINUS:
1638 case RASQAL_GRAPH_PATTERN_OPERATOR_VALUES:
1639 case RASQAL_GRAPH_PATTERN_OPERATOR_UNKNOWN:
1640 break;
1641 }
1642
1643 return 0;
1644 }
1645
1646
1647 /**
1648 * rasqal_graph_pattern_mentions_variable:
1649 * @gp: graph pattern
1650 * @v: variable
1651 *
1652 * INTERNAL - test if a variable is bound in a graph pattern directly
1653 *
1654 * Return value: non-0 if variable is bound in the given graph pattern
1655 */
1656 static int
rasqal_graph_pattern_mentions_variable(rasqal_graph_pattern * gp,rasqal_variable * v)1657 rasqal_graph_pattern_mentions_variable(rasqal_graph_pattern* gp,
1658 rasqal_variable* v)
1659 {
1660 rasqal_query* query = gp->query;
1661 int width;
1662 int gp_offset;
1663 unsigned short *row;
1664
1665 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
1666 gp_offset = (gp->gp_index + RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) * width;
1667 row = &query->variables_use_map[gp_offset];
1668
1669 return (row[v->offset] & RASQAL_VAR_USE_MENTIONED_HERE);
1670 }
1671
1672
1673 /**
1674 * rasqal_graph_pattern_tree_mentions_variable:
1675 * @query: query
1676 * @gp: graph pattern
1677 * @v: variable
1678 *
1679 * INTERNAL - test if a variable is mentioned in a graph pattern tree
1680 *
1681 * Return value: non-0 if variable is mentioned in GP tree
1682 */
1683 static int
rasqal_graph_pattern_tree_mentions_variable(rasqal_graph_pattern * gp,rasqal_variable * v)1684 rasqal_graph_pattern_tree_mentions_variable(rasqal_graph_pattern* gp,
1685 rasqal_variable* v)
1686 {
1687 if(gp->graph_patterns) {
1688 int size = raptor_sequence_size(gp->graph_patterns);
1689 int i;
1690
1691 for(i = 0; i < size; i++) {
1692 rasqal_graph_pattern *sgp;
1693 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
1694 if(rasqal_graph_pattern_tree_mentions_variable(sgp, v))
1695 return 1;
1696 }
1697 }
1698
1699 return rasqal_graph_pattern_mentions_variable(gp, v);
1700 }
1701
1702
1703
1704 /**
1705 * rasqal_graph_pattern_promote_variable_mention_to_bind:
1706 * @gp: graph pattern
1707 * @v: variable
1708 * @vars_scope: variable in scope array
1709 *
1710 * INTERNAL - Promote a variable from a mention to a bind - for a basic graph pattenr
1711 *
1712 * Return value: non-0 on failure
1713 */
1714 static int
rasqal_graph_pattern_promote_variable_mention_to_bind(rasqal_graph_pattern * gp,rasqal_variable * v,unsigned short * vars_scope)1715 rasqal_graph_pattern_promote_variable_mention_to_bind(rasqal_graph_pattern* gp,
1716 rasqal_variable* v,
1717 unsigned short* vars_scope)
1718 {
1719 rasqal_query* query = gp->query;
1720 int width;
1721 int gp_offset;
1722 unsigned short* row;
1723
1724 /* If already bound, do nothing - not an error */
1725 if(vars_scope[v->offset])
1726 return 0;
1727
1728 RASQAL_DEBUG3("Converting variable %s from mention to bound in GP #%d\n",
1729 v->name, gp->gp_index);
1730
1731 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
1732 gp_offset = (gp->gp_index + RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) * width;
1733 row = &query->variables_use_map[gp_offset];
1734
1735 /* new variable - bind it */
1736 row[v->offset] |= RASQAL_VAR_USE_BOUND_HERE;
1737
1738 vars_scope[v->offset] = 1;
1739
1740 return 0;
1741 }
1742
1743
1744 /**
1745 * rasqal_query_triples_build_variables_use_map_binds:
1746 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
1747 * @width: width of array (num. variables)
1748 * @gp: graph pattern to use
1749 * @vars_scope: variables bound in current scope
1750 *
1751 * INTERNAL - Mark variables bound in a BASIC graph pattern (triple pattern)
1752 *
1753 **/
1754 static int
rasqal_query_triples_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp,unsigned short * vars_scope)1755 rasqal_query_triples_build_variables_use_map_binds(rasqal_query* query,
1756 unsigned short *use_map,
1757 int width,
1758 rasqal_graph_pattern* gp,
1759 unsigned short* vars_scope)
1760 {
1761 int start_column = gp->start_column;
1762 int end_column = gp->end_column;
1763 int col;
1764 int gp_offset;
1765 unsigned short* gp_use_map_row;
1766 int var_index;
1767
1768 gp_offset = (gp->gp_index + RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) * width;
1769 gp_use_map_row = &query->variables_use_map[gp_offset];
1770
1771 /* Scan all triples and mark per-triple use/bind and for entire BGP use*/
1772 for(col = start_column; col <= end_column; col++) {
1773 rasqal_triple *t;
1774 rasqal_variable *v;
1775 unsigned short* triple_row = &query->triples_use_map[col * width];
1776
1777 t = (rasqal_triple*)raptor_sequence_get_at(gp->triples, col);
1778
1779 if((v = rasqal_literal_as_variable(t->subject))) {
1780 if(!vars_scope[v->offset]) {
1781 /* v needs binding in this triple as SUBJECT */
1782 triple_row[v->offset] |= RASQAL_TRIPLES_BOUND_SUBJECT;
1783 } else
1784 triple_row[v->offset] |= RASQAL_TRIPLES_USE_SUBJECT;
1785 }
1786
1787 if((v = rasqal_literal_as_variable(t->predicate))) {
1788 if(!vars_scope[v->offset]) {
1789 /* v needs binding in this triple as PREDICATE */
1790 triple_row[v->offset] |= RASQAL_TRIPLES_BOUND_PREDICATE;
1791 } else
1792 triple_row[v->offset] |= RASQAL_TRIPLES_USE_PREDICATE;
1793 }
1794
1795 if((v = rasqal_literal_as_variable(t->object))) {
1796 if(!vars_scope[v->offset]) {
1797 /* v needs binding in this triple as OBJECT */
1798 triple_row[v->offset] |= RASQAL_TRIPLES_BOUND_OBJECT;
1799 } else
1800 triple_row[v->offset] |= RASQAL_TRIPLES_USE_OBJECT;
1801 }
1802
1803 if(t->origin) {
1804 if((v = rasqal_literal_as_variable(t->origin))) {
1805 if(!vars_scope[v->offset]) {
1806 /* v needs binding in this triple as GRAPH */
1807 triple_row[v->offset] |= RASQAL_TRIPLES_BOUND_GRAPH;
1808 } else
1809 triple_row[v->offset] |= RASQAL_TRIPLES_USE_GRAPH;
1810 }
1811 }
1812
1813
1814 /* Promote first use of a variable into a bind. */
1815 if((v = rasqal_literal_as_variable(t->subject)) &&
1816 triple_row[v->offset] & RASQAL_TRIPLES_BOUND_SUBJECT) {
1817 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
1818 }
1819
1820 if((v = rasqal_literal_as_variable(t->predicate)) &&
1821 triple_row[v->offset] & RASQAL_TRIPLES_BOUND_PREDICATE) {
1822 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
1823 }
1824
1825 if((v = rasqal_literal_as_variable(t->object)) &&
1826 triple_row[v->offset] & RASQAL_TRIPLES_BOUND_OBJECT) {
1827 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
1828 }
1829
1830 if(t->origin) {
1831 if((v = rasqal_literal_as_variable(t->origin)) &&
1832 triple_row[v->offset] & RASQAL_TRIPLES_BOUND_GRAPH) {
1833 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
1834 }
1835 }
1836
1837 }
1838
1839 /* Scan all triples for USEs of variables and update BGP mentioned bits */
1840 for(var_index = 0; var_index < width; var_index++) {
1841 int mentioned = 0;
1842
1843 for(col = start_column; col <= end_column; col++) {
1844 unsigned short* triple_row = &query->triples_use_map[col * width];
1845
1846 if(triple_row[var_index] & RASQAL_TRIPLES_USE_MASK) {
1847 mentioned = 1;
1848 break;
1849 }
1850 }
1851
1852 if(mentioned)
1853 gp_use_map_row[var_index] |= RASQAL_VAR_USE_MENTIONED_HERE;
1854 else
1855 gp_use_map_row[var_index] = RASQAL_GOOD_CAST(unsigned short, gp_use_map_row[var_index] & ~RASQAL_VAR_USE_MENTIONED_HERE);
1856
1857 }
1858
1859 return 0;
1860 }
1861
1862
1863 #ifdef RASQAL_DEBUG
1864 static void
rasqal_query_dump_vars_scope(rasqal_query * query,int width,unsigned short * vars_scope)1865 rasqal_query_dump_vars_scope(rasqal_query* query, int width, unsigned short *vars_scope)
1866 {
1867 int j;
1868
1869 for(j = 0; j < width; j++) {
1870 rasqal_variable* v = rasqal_variables_table_get(query->vars_table, j);
1871 fprintf(DEBUG_FH, "%8s ", v->name);
1872 }
1873 fputs("\n ", DEBUG_FH);
1874 for(j = 0; j < width; j++) {
1875 fprintf(DEBUG_FH, "%8d ", vars_scope[j]);
1876 }
1877 fputc('\n', DEBUG_FH);
1878 }
1879 #endif
1880
1881
1882 /**
1883 * rasqal_query_graph_pattern_build_variables_use_map_binds:
1884 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
1885 * @width: width of array (num. variables)
1886 * @gp: graph pattern to use
1887 * @vars_scope: variables bound in current scope
1888 *
1889 * INTERNAL - Calculate which GPs bind variables in a graph_pattern tree walk
1890 *
1891 * Return value: non-0 on failure
1892 **/
1893 static int
rasqal_query_graph_pattern_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp,unsigned short * vars_scope)1894 rasqal_query_graph_pattern_build_variables_use_map_binds(rasqal_query* query,
1895 unsigned short *use_map,
1896 int width,
1897 rasqal_graph_pattern *gp,
1898 unsigned short *vars_scope)
1899 {
1900 int rc = 0;
1901
1902 /* This a query in-order walk so SELECT ... AS ?var, BIND .. AS
1903 * ?var and GRAPH ?var come before any sub-graph patterns
1904 */
1905
1906 switch(gp->op) {
1907 case RASQAL_GRAPH_PATTERN_OPERATOR_BASIC:
1908 rc = rasqal_query_triples_build_variables_use_map_binds(query,
1909 use_map,
1910 width,
1911 gp, vars_scope);
1912 break;
1913
1914 case RASQAL_GRAPH_PATTERN_OPERATOR_GRAPH:
1915 rc = rasqal_query_graph_build_variables_use_map_binds(gp, vars_scope);
1916 break;
1917
1918 case RASQAL_GRAPH_PATTERN_OPERATOR_FILTER:
1919 /* Only mentions */
1920 break;
1921
1922 case RASQAL_GRAPH_PATTERN_OPERATOR_LET:
1923 rc = rasqal_query_let_build_variables_use_map_binds(gp, vars_scope);
1924 break;
1925
1926 case RASQAL_GRAPH_PATTERN_OPERATOR_SELECT:
1927 rc = rasqal_query_select_build_variables_use_map_binds(query,
1928 use_map,
1929 width,
1930 gp, vars_scope);
1931 break;
1932
1933 case RASQAL_GRAPH_PATTERN_OPERATOR_UNION:
1934 case RASQAL_GRAPH_PATTERN_OPERATOR_GROUP:
1935 case RASQAL_GRAPH_PATTERN_OPERATOR_OPTIONAL:
1936 rc = rasqal_query_union_build_variables_use_map_binds(query,
1937 use_map,
1938 width,
1939 gp, vars_scope);
1940 break;
1941
1942 case RASQAL_GRAPH_PATTERN_OPERATOR_VALUES:
1943 rc = rasqal_query_values_build_variables_use_map_binds(query,
1944 use_map, width,
1945 gp,
1946 vars_scope);
1947 break;
1948
1949 case RASQAL_GRAPH_PATTERN_OPERATOR_SERVICE:
1950 case RASQAL_GRAPH_PATTERN_OPERATOR_MINUS:
1951 case RASQAL_GRAPH_PATTERN_OPERATOR_UNKNOWN:
1952 break;
1953 }
1954
1955 #ifdef RASQAL_DEBUG
1956 RASQAL_DEBUG3("vars_scope after %s graph pattern #%d verb is now:\n ",
1957 rasqal_graph_pattern_operator_as_string(gp->op), gp->gp_index);
1958 rasqal_query_dump_vars_scope(query, width, vars_scope);
1959 #endif
1960
1961 /* Bind sub-graph patterns but not sub-SELECT gp twice */
1962 if(gp->op != RASQAL_GRAPH_PATTERN_OPERATOR_SELECT && gp->graph_patterns) {
1963 int gp_size = raptor_sequence_size(gp->graph_patterns);
1964 int i;
1965
1966 /* recursively call binds */
1967 for(i = 0; i < gp_size; i++) {
1968 rasqal_graph_pattern *sgp;
1969
1970 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns, i);
1971 RASQAL_DEBUG2("checking vars_scope for SGP #%d\n", sgp->gp_index);
1972
1973 rc = rasqal_query_graph_pattern_build_variables_use_map_binds(query,
1974 use_map,
1975 width, sgp,
1976 vars_scope);
1977 if(rc)
1978 goto done;
1979
1980 #ifdef RASQAL_DEBUG
1981 RASQAL_DEBUG2("vars_scope after SGP #%d is now:\n ", sgp->gp_index);
1982 rasqal_query_dump_vars_scope(query, width, vars_scope);
1983 #endif
1984 }
1985 }
1986
1987
1988 done:
1989 return rc;
1990 }
1991
1992
1993 /**
1994 * rasqal_query_build_variables_use_map_binds:
1995 * @query: the #rasqal_query to find the variables in
1996 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
1997 * @width: width of array (num. variables)
1998 * @gp: graph pattern to use
1999 *
2000 * INTERNAL - Calculate which GPs bind variables in a graph_pattern tree walk
2001 *
2002 * Return value: non-0 on failure
2003 **/
2004 static int
rasqal_query_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp)2005 rasqal_query_build_variables_use_map_binds(rasqal_query* query,
2006 unsigned short *use_map,
2007 int width,
2008 rasqal_graph_pattern *gp)
2009 {
2010 int rc;
2011 unsigned short* vars_scope;
2012 raptor_sequence* seq;
2013
2014 vars_scope = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width), sizeof(unsigned short));
2015 if(!vars_scope)
2016 return 1;
2017
2018 rc = rasqal_query_graph_pattern_build_variables_use_map_binds(query,
2019 use_map,
2020 width,
2021 gp,
2022 vars_scope);
2023
2024 /* Record variable binding for GROUP BY expressions (SPARQL 1.1) */
2025 seq = rasqal_query_get_group_conditions_sequence(query);
2026 if(seq) {
2027 int size = raptor_sequence_size(seq);
2028 int i;
2029 unsigned short *use_map_row;
2030
2031 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_GROUP_BY * width];
2032
2033 /* sequence of rasqal_expression of operation RASQAL_EXPR_LITERAL
2034 * containing a variable literal, with the variable having
2035 * ->expression set to the expression
2036 */
2037 for(i = 0; i < size; i++) {
2038 rasqal_expression *e;
2039 rasqal_literal *l;
2040
2041 e = (rasqal_expression*)raptor_sequence_get_at(seq, i);
2042
2043 l = e->literal;
2044 if(l) {
2045 rasqal_variable* v = l->value.variable;
2046 if(v && v->expression) {
2047 use_map_row[v->offset] |= RASQAL_VAR_USE_BOUND_HERE;
2048
2049 vars_scope[v->offset] = 1;
2050 }
2051 }
2052 }
2053 }
2054
2055 RASQAL_FREE(intarray, vars_scope);
2056
2057 return rc;
2058 }
2059
2060
2061 #ifdef RASQAL_DEBUG
2062 static const char* const use_map_offset_labels[RASQAL_VAR_USE_MAP_OFFSET_LAST + 1] = {
2063 "Verbs",
2064 "GROUP BY",
2065 "HAVING",
2066 "ORDER BY",
2067 "VALUES"
2068 };
2069
2070
2071 #define N_MAP_FLAGS_LABELS 8
2072 static const char* const use_map_flags_labels[N_MAP_FLAGS_LABELS + 1] = {
2073 " ",
2074 " I",
2075 " M ",
2076 " I",
2077 "B ",
2078 "B I",
2079 "BM ",
2080 "B I",
2081 "???"
2082 };
2083
2084
2085 static void
rasqal_query_print_variables_use_map(FILE * fh,rasqal_query * query)2086 rasqal_query_print_variables_use_map(FILE* fh, rasqal_query* query)
2087 {
2088 int width;
2089 int height;
2090 int i;
2091 int row_index;
2092
2093 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
2094 height = (RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) + query->graph_pattern_count;
2095
2096 fprintf(fh, "Query GP variables-use map (B=bound, M=mentioned, U=used):\n");
2097 fputs("GP# Type ", fh);
2098
2099 for(i = 0; i < width; i++) {
2100 rasqal_variable* v = rasqal_variables_table_get(query->vars_table, i);
2101 fprintf(fh, "%-12s ", v->name);
2102 }
2103
2104 fputc('\n', fh);
2105
2106 for(row_index = 0; row_index < height; row_index++) {
2107 unsigned short *row = &query->variables_use_map[row_index * width];
2108 int gp_index = row_index - (RASQAL_VAR_USE_MAP_OFFSET_LAST + 1);
2109
2110 if(gp_index < 0)
2111 fprintf(fh, "-- %-8s ", use_map_offset_labels[row_index]);
2112 else {
2113 rasqal_graph_pattern* gp;
2114 gp = (rasqal_graph_pattern*)raptor_sequence_get_at(query->graph_patterns_sequence, gp_index);
2115 fprintf(fh, "%-2d %-8s ", gp_index,
2116 rasqal_graph_pattern_operator_as_string(gp->op));
2117 }
2118
2119 for(i = 0; i < width; i++) {
2120 int flag_index = row[i];
2121
2122 /* Turn unknown flags into "???" */
2123 if(flag_index > N_MAP_FLAGS_LABELS - 1)
2124 flag_index = N_MAP_FLAGS_LABELS;
2125 fprintf(fh, "%-12s ", use_map_flags_labels[flag_index]);
2126
2127 }
2128 fputc('\n', fh);
2129 }
2130 }
2131
2132
2133 static const char bit_label[9] = "spogSPOG";
2134
2135 static void
rasqal_query_print_triples_use_map(FILE * fh,rasqal_query * query)2136 rasqal_query_print_triples_use_map(FILE* fh, rasqal_query* query)
2137 {
2138 int width;
2139 int height;
2140 int i;
2141 int column;
2142
2143 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
2144 height = raptor_sequence_size(query->triples);
2145
2146 fprintf(fh,
2147 "Query triples variables-use map (mentioned: spog, bound: SPOG):\n");
2148
2149 fputs("Triple# ", fh);
2150 for(i = 0; i < width; i++) {
2151 rasqal_variable* v = rasqal_variables_table_get(query->vars_table, i);
2152 fprintf(fh, "%-12s ", v->name);
2153 }
2154 fputc('\n', fh);
2155
2156 for(column = 0; column < height; column++) {
2157 unsigned short *row = &query->triples_use_map[column * width];
2158 rasqal_triple* t;
2159
2160 fprintf(fh, "%-7d ", column);
2161 for(i = 0; i < width; i++) {
2162 int flag = row[i];
2163 char label[14] = " ";
2164 int bit;
2165
2166 /* bit 0: RASQAL_TRIPLES_USE_SUBJECT
2167 * to
2168 * bit 7: RASQAL_TRIPLES_BOUND_GRAPH
2169 */
2170 for(bit = 0; bit < 8; bit++) {
2171 if(flag & (1 << bit))
2172 label[(bit & 3)] = bit_label[bit];
2173 }
2174 fputs(label, fh);
2175 }
2176 fputc(' ', fh);
2177 t = (rasqal_triple*)raptor_sequence_get_at(query->triples, column);
2178 rasqal_triple_print(t, fh);
2179 fputc('\n', fh);
2180 }
2181 }
2182 #endif
2183
2184
2185 /* for use with rasqal_expression_visit and user_data=rasqal_query */
2186 static int
rasqal_query_expression_build_variables_use_map_row(unsigned short * use_map_row,rasqal_expression * e)2187 rasqal_query_expression_build_variables_use_map_row(unsigned short *use_map_row,
2188 rasqal_expression *e)
2189 {
2190 if(e->literal) {
2191 rasqal_variable* v;
2192
2193 v = rasqal_literal_as_variable(e->literal);
2194
2195 if(v)
2196 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
2197 }
2198
2199 return 0;
2200 }
2201
2202
2203 /*
2204 * rasqal_query_build_variables_sequence_use_map_row:
2205 * @use_map_row: row to write to
2206 * @vars_seq: sequence of variables
2207 * @bind: force bind; otherwise binds only if var has an expression
2208 *
2209 * INTERNAL: Mark variables seen / bound in a sequence of variables (with optional expression)
2210 *
2211 * Return value: non-0 on failure
2212 */
2213 static int
rasqal_query_build_variables_sequence_use_map_row(unsigned short * use_map_row,raptor_sequence * vars_seq,int bind)2214 rasqal_query_build_variables_sequence_use_map_row(unsigned short* use_map_row,
2215 raptor_sequence *vars_seq,
2216 int bind)
2217 {
2218 int rc = 0;
2219 int idx;
2220
2221 for(idx = 0; 1; idx++) {
2222 rasqal_variable* v;
2223 int flags = RASQAL_VAR_USE_MENTIONED_HERE;
2224
2225 v = (rasqal_variable*)raptor_sequence_get_at(vars_seq, idx);
2226 if(!v)
2227 break;
2228
2229 if(bind)
2230 flags |= RASQAL_VAR_USE_BOUND_HERE;
2231 else {
2232 rasqal_expression *e;
2233 e = v->expression;
2234 if(e) {
2235 rasqal_query_expression_build_variables_use_map(use_map_row, e);
2236 flags |= RASQAL_VAR_USE_BOUND_HERE;
2237 }
2238 }
2239
2240 use_map_row[v->offset] = RASQAL_GOOD_CAST(unsigned short, use_map_row[v->offset] | flags);
2241 }
2242
2243 return rc;
2244 }
2245
2246
2247 /*
2248 * Mark variables seen in a sequence of literals
2249 */
2250 static int
rasqal_query_build_literals_sequence_use_map_row(unsigned short * use_map_row,raptor_sequence * lits_seq)2251 rasqal_query_build_literals_sequence_use_map_row(unsigned short* use_map_row,
2252 raptor_sequence *lits_seq)
2253 {
2254 int idx;
2255
2256 for(idx = 0; 1; idx++) {
2257 rasqal_literal* l;
2258 rasqal_variable* v;
2259
2260 l = (rasqal_literal*)raptor_sequence_get_at(lits_seq, idx);
2261 if(!l)
2262 break;
2263
2264 v = rasqal_literal_as_variable(l);
2265 if(v)
2266 use_map_row[v->offset] |= RASQAL_VAR_USE_MENTIONED_HERE;
2267 }
2268
2269 return 0;
2270 }
2271
2272
2273 /*
2274 * Mark variables seen in a sequence of expressions
2275 */
2276 static int
rasqal_query_build_expressions_sequence_use_map_row(unsigned short * use_map_row,raptor_sequence * exprs_seq)2277 rasqal_query_build_expressions_sequence_use_map_row(unsigned short* use_map_row,
2278 raptor_sequence *exprs_seq)
2279 {
2280 int rc = 0;
2281 int idx;
2282
2283 for(idx = 0; 1; idx++) {
2284 rasqal_expression *e;
2285
2286 e = (rasqal_expression*)raptor_sequence_get_at(exprs_seq, idx);
2287 if(!e)
2288 break;
2289
2290 rasqal_query_expression_build_variables_use_map(use_map_row, e);
2291 }
2292
2293 return rc;
2294 }
2295
2296
2297 /**
2298 * rasqal_query_build_variables_use_map:
2299 * @query: the #rasqal_query to find the variables in
2300 *
2301 * INTERNAL - Record where variables are mentioned in query structures
2302 *
2303 * Need to walk query components that may mention or bind variables
2304 * and record their variable use:
2305 * 1) Query verbs: ASK SELECT CONSTRUCT DESCRIBE (SPARQL 1.0)
2306 * 1a) SELECT project-expressions (SPARQL 1.1)
2307 * 2) GROUP BY expr/var (SPARQL 1.1 TBD)
2308 * 3) HAVING expr (SPARQL 1.1 TBD)
2309 * 4) ORDER list-of-expr (SPARQL 1.0)
2310 *
2311 * Constructs a 2D array of
2312 * width: number of variables
2313 * height: (number of graph patterns + #RASQAL_VAR_USE_MAP_OFFSET_LAST+1)
2314 * where each row records how a variable is bound/used in a GP or query
2315 * structure.
2316 *
2317 * The first #RASQAL_VAR_USE_MAP_OFFSET_LAST+1 rows are used for the
2318 * query structures above defined by the #rasqal_var_use_map_offset
2319 * enum. Example: row 0 (#RASQAL_VAR_USE_MAP_OFFSET_VERBS) is used
2320 * to record variable use for the query verbs - item 1) in the list
2321 * above.
2322 *
2323 * Graph pattern rows are recorded at row
2324 * <GP ID> + #RASQAL_VAR_USE_MAP_OFFSET_LAST + 1
2325 *
2326 * Return value: non-0 on failure
2327 **/
2328 static int
rasqal_query_build_variables_use_map(rasqal_query * query,rasqal_projection * projection)2329 rasqal_query_build_variables_use_map(rasqal_query* query,
2330 rasqal_projection* projection)
2331 {
2332 int width;
2333 int height;
2334 int rc = 0;
2335 unsigned short *use_map;
2336 raptor_sequence* seq;
2337 unsigned short *use_map_row;
2338
2339 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
2340 height = RASQAL_VAR_USE_MAP_OFFSET_LAST + 1 + query->graph_pattern_count;
2341
2342 use_map = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width * height),
2343 sizeof(unsigned short));
2344 if(!use_map)
2345 return 1;
2346
2347 if(query->variables_use_map)
2348 RASQAL_FREE(shortarray, query->variables_use_map);
2349
2350 query->variables_use_map = use_map;
2351
2352 height = raptor_sequence_size(query->triples);
2353 use_map = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width * height),
2354 sizeof(unsigned short));
2355 if(!use_map) {
2356 RASQAL_FREE(shortarray, query->variables_use_map);
2357 query->variables_use_map = NULL;
2358 return 1;
2359 }
2360
2361 if(query->triples_use_map)
2362 RASQAL_FREE(shortarray, query->triples_use_map);
2363
2364 query->triples_use_map = use_map;
2365
2366 use_map = query->variables_use_map;
2367 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_VERBS * width];
2368
2369 /* record variable use for 1) Query verbs */
2370 switch(query->verb) {
2371 case RASQAL_QUERY_VERB_SELECT:
2372 /* This also handles 1a) select/project expressions */
2373 if(projection && projection->variables)
2374 rc = rasqal_query_build_variables_sequence_use_map_row(use_map_row,
2375 projection->variables, 0);
2376 break;
2377
2378 case RASQAL_QUERY_VERB_DESCRIBE:
2379 /* This is a list of rasqal_literal not rasqal_variable */
2380 rc = rasqal_query_build_literals_sequence_use_map_row(use_map_row,
2381 query->describes);
2382 break;
2383
2384 case RASQAL_QUERY_VERB_CONSTRUCT:
2385 if(1) {
2386 int last_column = raptor_sequence_size(query->constructs)-1;
2387
2388 rc = rasqal_query_triples_build_variables_use_map_row(query->constructs,
2389 use_map_row,
2390 0,
2391 last_column);
2392 }
2393 break;
2394
2395 case RASQAL_QUERY_VERB_DELETE:
2396 case RASQAL_QUERY_VERB_INSERT:
2397 case RASQAL_QUERY_VERB_UPDATE:
2398 /* FIXME - should mark the verbs using triple patterns as using vars */
2399 break;
2400
2401 case RASQAL_QUERY_VERB_UNKNOWN:
2402 case RASQAL_QUERY_VERB_ASK:
2403 default:
2404 break;
2405 }
2406
2407 if(rc)
2408 goto done;
2409
2410
2411 /* Record variable use for 2) GROUP BY expressions (SPARQL 1.1) */
2412 seq = rasqal_query_get_group_conditions_sequence(query);
2413 if(seq) {
2414 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_GROUP_BY * width];
2415 rc = rasqal_query_build_expressions_sequence_use_map_row(use_map_row, seq);
2416 if(rc)
2417 goto done;
2418 }
2419
2420
2421 /* Record variable use for 3) HAVING expr (SPARQL 1.1) */
2422 seq = rasqal_query_get_having_conditions_sequence(query);
2423 if(seq) {
2424 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_HAVING * width];
2425 rc = rasqal_query_build_expressions_sequence_use_map_row(use_map_row, seq);
2426 if(rc)
2427 goto done;
2428 }
2429
2430 /* record variable use for 4) ORDER list-of-expr (SPARQL 1.0) */
2431 seq = rasqal_query_get_order_conditions_sequence(query);
2432 if(seq) {
2433 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_ORDER_BY * width];
2434 rc = rasqal_query_build_expressions_sequence_use_map_row(use_map_row, seq);
2435 if(rc)
2436 goto done;
2437 }
2438
2439
2440 /* record variable use for 5) VALUES (SPARQL 1.1) */
2441 if(query->bindings) {
2442 use_map_row = &use_map[RASQAL_VAR_USE_MAP_OFFSET_VALUES * width];
2443 rc = rasqal_query_build_variables_sequence_use_map_row(use_map_row,
2444 query->bindings->variables, 1);
2445 if(rc)
2446 goto done;
2447 }
2448
2449
2450 /* record variable use for graph patterns */
2451 rc = rasqal_query_graph_pattern_build_variables_use_map(query,
2452 use_map,
2453 width,
2454 query->query_graph_pattern);
2455 if(rc)
2456 goto done;
2457
2458 #ifdef RASQAL_DEBUG
2459 RASQAL_DEBUG1("variables use map after mentions: ");
2460 rasqal_query_print_variables_use_map(DEBUG_FH, query);
2461 fputs("\n", DEBUG_FH);
2462 #endif
2463
2464 /* calculate which GPs bind variables for all query graph patterns
2465 * reading from the use_map
2466 */
2467 rc = rasqal_query_build_variables_use_map_binds(query, use_map, width,
2468 query->query_graph_pattern);
2469 if(rc)
2470 goto done;
2471
2472 #ifdef RASQAL_DEBUG
2473 RASQAL_DEBUG1("use map after binds and mentions: ");
2474 rasqal_query_print_variables_use_map(DEBUG_FH, query);
2475 fputs("\n", DEBUG_FH);
2476
2477 RASQAL_DEBUG1("triples use map after binds and mentions: ");
2478 rasqal_query_print_triples_use_map(DEBUG_FH, query);
2479 fputs("\n", DEBUG_FH);
2480 #endif
2481
2482 done:
2483 return rc;
2484 }
2485
2486
2487 /**
2488 * rasqal_query_graph_build_variables_use_map_binds:
2489 * @gp: the #rasqal_graph_pattern GRAPH pattern
2490 * @vars_scope: variable scope array
2491 *
2492 * INTERNAL - Mark variables bound in a GRAPH graph pattern
2493 *
2494 **/
2495 static int
rasqal_query_graph_build_variables_use_map_binds(rasqal_graph_pattern * gp,unsigned short * vars_scope)2496 rasqal_query_graph_build_variables_use_map_binds(rasqal_graph_pattern* gp,
2497 unsigned short* vars_scope)
2498 {
2499 rasqal_variable *v;
2500
2501 v = rasqal_literal_as_variable(gp->origin);
2502
2503 if(v)
2504 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
2505
2506 return 0;
2507 }
2508
2509
2510
2511 /**
2512 * rasqal_query_expression_build_variables_use_map:
2513 * @use_map_row: 1D array of size num. variables to write
2514 * @e: filter expression to use
2515 *
2516 * INTERNAL - Mark variables mentioned in an expression
2517 *
2518 **/
2519 static void
rasqal_query_expression_build_variables_use_map(unsigned short * use_map_row,rasqal_expression * e)2520 rasqal_query_expression_build_variables_use_map(unsigned short *use_map_row,
2521 rasqal_expression* e)
2522 {
2523 rasqal_expression_visit(e,
2524 (rasqal_expression_visit_fn)rasqal_query_expression_build_variables_use_map_row,
2525 use_map_row);
2526 }
2527
2528
2529 /**
2530 * rasqal_query_let_build_variables_use_map:
2531 * @query: the #rasqal_query to find the variables in
2532 * @use_map_row: 1D array of size num. variables to write
2533 * @e: let expression to use
2534 *
2535 * INTERNAL - Mark variables mentioned in a LET graph pattern
2536 *
2537 **/
2538 static void
rasqal_query_let_build_variables_use_map(rasqal_query * query,unsigned short * use_map_row,rasqal_expression * e)2539 rasqal_query_let_build_variables_use_map(rasqal_query* query,
2540 unsigned short *use_map_row,
2541 rasqal_expression* e)
2542 {
2543 rasqal_expression_visit(e,
2544 (rasqal_expression_visit_fn)rasqal_query_expression_build_variables_use_map_row,
2545 use_map_row);
2546 }
2547
2548
2549 /**
2550 * rasqal_query_let_build_variables_use_map_binds:
2551 * @gp: the #rasqal_graph_pattern LET graph pattern
2552 * @vars_scope: variable scope array
2553 *
2554 * INTERNAL - Mark variables bound in a LET graph pattern
2555 *
2556 **/
2557 static int
rasqal_query_let_build_variables_use_map_binds(rasqal_graph_pattern * gp,unsigned short * vars_scope)2558 rasqal_query_let_build_variables_use_map_binds(rasqal_graph_pattern* gp,
2559 unsigned short* vars_scope)
2560 {
2561 rasqal_variable* v = gp->var;
2562
2563 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
2564
2565 return 0;
2566 }
2567
2568
2569
2570 /**
2571 * rasqal_query_select_build_variables_use_map:
2572 * @query: the #rasqal_query to find the variables in
2573 * @use_map_row: 1D array of size num. variables to write
2574 * @width: width of array (num. variables)
2575 * @gp: the SELECT graph pattern
2576 *
2577 * INTERNAL - Mark variables mentioned in a sub-SELECT graph pattern
2578 *
2579 **/
2580 static int
rasqal_query_select_build_variables_use_map(rasqal_query * query,unsigned short * use_map_row,int width,rasqal_graph_pattern * gp)2581 rasqal_query_select_build_variables_use_map(rasqal_query* query,
2582 unsigned short *use_map_row,
2583 int width,
2584 rasqal_graph_pattern* gp)
2585 {
2586 int rc = 0;
2587 raptor_sequence* seq;
2588
2589 /* mention any variables in the projection */
2590 seq = rasqal_projection_get_variables_sequence(gp->projection);
2591
2592 if(!seq && gp->graph_patterns) {
2593 int var_index;
2594 int gp_size;
2595
2596 seq = raptor_new_sequence((raptor_data_free_handler)rasqal_free_variable,
2597 (raptor_data_print_handler)rasqal_variable_print);
2598
2599 gp_size = raptor_sequence_size(gp->graph_patterns);
2600
2601 /* No variables; must be SELECT * so form it from all mentioned
2602 * variables in the sub graph patterns
2603 */
2604 for(var_index = 0; var_index < width; var_index++) {
2605 rasqal_variable *v;
2606 int gp_index;
2607
2608 v = rasqal_variables_table_get(query->vars_table, var_index);
2609
2610 for(gp_index = 0; gp_index < gp_size; gp_index++) {
2611 rasqal_graph_pattern *sgp;
2612
2613 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(gp->graph_patterns,
2614 gp_index);
2615 if(rasqal_graph_pattern_tree_mentions_variable(sgp, v)) {
2616 raptor_sequence_push(seq, rasqal_new_variable_from_variable(v));
2617
2618 /* if any sub-GP mentions the variable we can end the SGP loop */
2619 break;
2620 }
2621 }
2622 }
2623
2624 /* FIXME: uses internal knowledge of projection structure */
2625 gp->projection->variables = seq;
2626 }
2627
2628 rc = rasqal_query_build_variables_sequence_use_map_row(use_map_row, seq, 0);
2629 if(rc)
2630 return rc;
2631
2632 if(gp->bindings) {
2633 rc = rasqal_query_build_variables_sequence_use_map_row(use_map_row,
2634 gp->bindings->variables, 1);
2635 if(rc)
2636 return rc;
2637 }
2638
2639 return rc;
2640 }
2641
2642
2643 /**
2644 * rasqal_query_select_build_variables_use_map_binds:
2645 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
2646 * @width: width of array (num. variables)
2647 * @gp: graph pattern to use
2648 * @vars_scope: variables bound in current scope
2649 *
2650 * INTERNAL - Mark variables bound in a sub-SELECT graph pattern
2651 *
2652 **/
2653 static int
rasqal_query_select_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp,unsigned short * vars_scope)2654 rasqal_query_select_build_variables_use_map_binds(rasqal_query* query,
2655 unsigned short *use_map,
2656 int width,
2657 rasqal_graph_pattern* gp,
2658 unsigned short* vars_scope)
2659 {
2660 unsigned short* inner_vars_scope;
2661 raptor_sequence* seq;
2662 int size;
2663 int i;
2664
2665 inner_vars_scope = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width),
2666 sizeof(unsigned short));
2667 if(!inner_vars_scope)
2668 return 1;
2669
2670 seq = gp->graph_patterns;
2671 size = raptor_sequence_size(seq);
2672 for(i = 0; i < size; i++) {
2673 rasqal_graph_pattern *sgp;
2674
2675 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(seq, i);
2676
2677 rasqal_query_graph_pattern_build_variables_use_map_binds(query,
2678 use_map, width,
2679 sgp,
2680 inner_vars_scope);
2681 }
2682
2683 RASQAL_FREE(intarray, inner_vars_scope);
2684 inner_vars_scope = NULL;
2685
2686 /* Mark as binding in the OUTER scope all variables that were bound
2687 * in the INNER SELECT projection
2688 */
2689 seq = rasqal_projection_get_variables_sequence(gp->projection);
2690 size = raptor_sequence_size(seq);
2691 for(i = 0; i < size; i++) {
2692 rasqal_variable * v;
2693
2694 v = (rasqal_variable*)raptor_sequence_get_at(seq, i);
2695
2696 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
2697 }
2698
2699 return 0;
2700 }
2701
2702
2703 /**
2704 * rasqal_query_union_build_variables_use_map_binds:
2705 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
2706 * @width: width of array (num. variables)
2707 * @gp: graph pattern to use
2708 * @vars_scope: variables bound in current scope
2709 *
2710 * INTERNAL - Mark variables bound in a UNION sub-graph patterns
2711 *
2712 **/
2713 static int
rasqal_query_union_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp,unsigned short * vars_scope)2714 rasqal_query_union_build_variables_use_map_binds(rasqal_query* query,
2715 unsigned short *use_map,
2716 int width,
2717 rasqal_graph_pattern* gp,
2718 unsigned short* vars_scope)
2719 {
2720 unsigned short* inner_vars_scope;
2721 raptor_sequence* seq;
2722 int gp_size;
2723 int i;
2724 int rc = 0;
2725
2726 seq = gp->graph_patterns;
2727 gp_size = raptor_sequence_size(seq);
2728
2729 inner_vars_scope = RASQAL_CALLOC(unsigned short*, RASQAL_GOOD_CAST(size_t, width),
2730 sizeof(unsigned short));
2731 if(!inner_vars_scope)
2732 return 1;
2733
2734 for(i = 0; i < gp_size; i++) {
2735 rasqal_graph_pattern *sgp;
2736
2737 /* UNION starts with a copy of all scoped outer variables */
2738 memcpy(inner_vars_scope, vars_scope, RASQAL_GOOD_CAST(size_t,
2739 RASQAL_GOOD_CAST(size_t, width) * sizeof(unsigned short)));
2740
2741 sgp = (rasqal_graph_pattern*)raptor_sequence_get_at(seq, i);
2742
2743 rc = rasqal_query_graph_pattern_build_variables_use_map_binds(query,
2744 use_map,
2745 width,
2746 sgp,
2747 inner_vars_scope);
2748 if(rc)
2749 goto done;
2750
2751 }
2752
2753 done:
2754 RASQAL_FREE(intarray, inner_vars_scope);
2755
2756 return rc;
2757 }
2758
2759
2760 /**
2761 * rasqal_query_values_build_variables_use_map_binds:
2762 * @use_map: 2D array of (num. variables x num. GPs) to READ and WRITE
2763 * @width: width of array (num. variables)
2764 * @gp: graph pattern to use
2765 * @vars_scope: variables bound in current scope
2766 *
2767 * INTERNAL - Mark variables bound in a VALUES sub-graph patterns
2768 *
2769 **/
2770 static int
rasqal_query_values_build_variables_use_map_binds(rasqal_query * query,unsigned short * use_map,int width,rasqal_graph_pattern * gp,unsigned short * vars_scope)2771 rasqal_query_values_build_variables_use_map_binds(rasqal_query* query,
2772 unsigned short *use_map,
2773 int width,
2774 rasqal_graph_pattern* gp,
2775 unsigned short* vars_scope)
2776 {
2777 raptor_sequence* seq;
2778 int size;
2779 int i;
2780 int rc = 0;
2781
2782 seq = gp->bindings->variables;
2783 size = raptor_sequence_size(seq);
2784
2785 for(i = 0; i < size; i++) {
2786 rasqal_variable * v;
2787 v = (rasqal_variable*)raptor_sequence_get_at(seq, i);
2788
2789 rasqal_graph_pattern_promote_variable_mention_to_bind(gp, v, vars_scope);
2790 }
2791
2792 return rc;
2793 }
2794
2795
2796 /*
2797 * rasqal_query_variable_is_bound:
2798 * @gp: #rasqal_graph_pattern object
2799 * @variable: variable
2800 *
2801 * INTERNAL - Test if a variable is bound in the given GP
2802 *
2803 * Return value: non-0 if bound
2804 */
2805 int
rasqal_query_variable_is_bound(rasqal_query * query,rasqal_variable * v)2806 rasqal_query_variable_is_bound(rasqal_query* query, rasqal_variable* v)
2807 {
2808 unsigned short *use_map = query->variables_use_map;
2809 int width;
2810 int height;
2811 int row_index;
2812
2813 width = rasqal_variables_table_get_total_variables_count(query->vars_table);
2814 height = (RASQAL_VAR_USE_MAP_OFFSET_LAST + 1) + query->graph_pattern_count;
2815
2816 for(row_index = 0; row_index < height; row_index++) {
2817 unsigned short *row = &use_map[row_index * width];
2818 if(row[v->offset])
2819 return 1;
2820 }
2821
2822 return 0;
2823 }
2824