1
2
3
4
5
6
7
8
9
10
11
12
13
14 package eu.fbk.rdfpro.util;
15
16 import java.util.ArrayList;
17 import java.util.Arrays;
18 import java.util.HashMap;
19 import java.util.HashSet;
20 import java.util.Iterator;
21 import java.util.LinkedHashMap;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.Objects;
25 import java.util.Set;
26 import java.util.concurrent.atomic.AtomicBoolean;
27 import java.util.concurrent.atomic.AtomicReference;
28 import java.util.function.Function;
29 import java.util.function.Predicate;
30 import java.util.function.ToDoubleFunction;
31 import java.util.regex.Matcher;
32 import java.util.regex.Pattern;
33
34 import javax.annotation.Nullable;
35
36 import org.openrdf.model.Resource;
37 import org.openrdf.model.Statement;
38 import org.openrdf.model.URI;
39 import org.openrdf.model.Value;
40 import org.openrdf.model.ValueFactory;
41 import org.openrdf.query.Binding;
42 import org.openrdf.query.BindingSet;
43 import org.openrdf.query.Dataset;
44 import org.openrdf.query.IncompatibleOperationException;
45 import org.openrdf.query.MalformedQueryException;
46 import org.openrdf.query.QueryEvaluationException;
47 import org.openrdf.query.algebra.And;
48 import org.openrdf.query.algebra.Extension;
49 import org.openrdf.query.algebra.ExtensionElem;
50 import org.openrdf.query.algebra.Filter;
51 import org.openrdf.query.algebra.Join;
52 import org.openrdf.query.algebra.Projection;
53 import org.openrdf.query.algebra.QueryModelNode;
54 import org.openrdf.query.algebra.QueryRoot;
55 import org.openrdf.query.algebra.SameTerm;
56 import org.openrdf.query.algebra.StatementPattern;
57 import org.openrdf.query.algebra.TupleExpr;
58 import org.openrdf.query.algebra.UnaryTupleOperator;
59 import org.openrdf.query.algebra.ValueConstant;
60 import org.openrdf.query.algebra.ValueExpr;
61 import org.openrdf.query.algebra.Var;
62 import org.openrdf.query.algebra.evaluation.EvaluationStrategy;
63 import org.openrdf.query.algebra.evaluation.TripleSource;
64 import org.openrdf.query.algebra.evaluation.federation.FederatedServiceResolver;
65 import org.openrdf.query.algebra.evaluation.federation.FederatedServiceResolverImpl;
66 import org.openrdf.query.algebra.evaluation.impl.BindingAssigner;
67 import org.openrdf.query.algebra.evaluation.impl.CompareOptimizer;
68 import org.openrdf.query.algebra.evaluation.impl.ConjunctiveConstraintSplitter;
69 import org.openrdf.query.algebra.evaluation.impl.ConstantOptimizer;
70 import org.openrdf.query.algebra.evaluation.impl.DisjunctiveConstraintOptimizer;
71 import org.openrdf.query.algebra.evaluation.impl.EvaluationStatistics;
72 import org.openrdf.query.algebra.evaluation.impl.EvaluationStrategyImpl;
73 import org.openrdf.query.algebra.evaluation.impl.FilterOptimizer;
74 import org.openrdf.query.algebra.evaluation.impl.IterativeEvaluationOptimizer;
75 import org.openrdf.query.algebra.evaluation.impl.OrderLimitOptimizer;
76 import org.openrdf.query.algebra.evaluation.impl.QueryJoinOptimizer;
77 import org.openrdf.query.algebra.evaluation.impl.QueryModelNormalizer;
78 import org.openrdf.query.algebra.evaluation.impl.SameTermFilterOptimizer;
79 import org.openrdf.query.algebra.helpers.QueryModelVisitorBase;
80 import org.openrdf.query.impl.EmptyBindingSet;
81 import org.openrdf.query.parser.ParsedBooleanQuery;
82 import org.openrdf.query.parser.ParsedGraphQuery;
83 import org.openrdf.query.parser.ParsedQuery;
84 import org.openrdf.query.parser.ParsedTupleQuery;
85 import org.openrdf.query.parser.sparql.ASTVisitorBase;
86 import org.openrdf.query.parser.sparql.BaseDeclProcessor;
87 import org.openrdf.query.parser.sparql.BlankNodeVarProcessor;
88 import org.openrdf.query.parser.sparql.DatasetDeclProcessor;
89 import org.openrdf.query.parser.sparql.StringEscapesProcessor;
90 import org.openrdf.query.parser.sparql.TupleExprBuilder;
91 import org.openrdf.query.parser.sparql.WildcardProjectionProcessor;
92 import org.openrdf.query.parser.sparql.ast.ASTAskQuery;
93 import org.openrdf.query.parser.sparql.ast.ASTConstructQuery;
94 import org.openrdf.query.parser.sparql.ast.ASTDescribeQuery;
95 import org.openrdf.query.parser.sparql.ast.ASTIRI;
96 import org.openrdf.query.parser.sparql.ast.ASTPrefixDecl;
97 import org.openrdf.query.parser.sparql.ast.ASTQName;
98 import org.openrdf.query.parser.sparql.ast.ASTQuery;
99 import org.openrdf.query.parser.sparql.ast.ASTQueryContainer;
100 import org.openrdf.query.parser.sparql.ast.ASTSelectQuery;
101 import org.openrdf.query.parser.sparql.ast.ASTServiceGraphPattern;
102 import org.openrdf.query.parser.sparql.ast.ParseException;
103 import org.openrdf.query.parser.sparql.ast.SyntaxTreeBuilder;
104 import org.openrdf.query.parser.sparql.ast.SyntaxTreeBuilderTreeConstants;
105 import org.openrdf.query.parser.sparql.ast.TokenMgrError;
106 import org.openrdf.query.parser.sparql.ast.VisitorException;
107 import org.slf4j.Logger;
108 import org.slf4j.LoggerFactory;
109
110 import info.aduna.iteration.CloseableIteration;
111 import info.aduna.iteration.EmptyIteration;
112
113 public final class Algebra {
114
115 private static final Logger LOGGER = LoggerFactory.getLogger(Algebra.class);
116
117 private static final EvaluationStatistics DEFAULT_EVALUATION_STATISTICS = new EvaluationStatistics();
118
119 private static final FederatedServiceResolverImpl FEDERATED_SERVICE_RESOLVER =
120 new FederatedServiceResolverImpl();
121
122 private static final TripleSource EMPTY_TRIPLE_SOURCE = new TripleSource() {
123
124 @Override
125 public ValueFactory getValueFactory() {
126 return Statements.VALUE_FACTORY;
127 }
128
129 @Override
130 public CloseableIteration<? extends Statement, QueryEvaluationException> getStatements(
131 final Resource subj, final URI pred, final Value obj, final Resource... contexts)
132 throws QueryEvaluationException {
133 return new EmptyIteration<Statement, QueryEvaluationException>();
134 }
135
136 };
137
138 private static final EvaluationStrategy EMPTY_EVALUATION_STRATEGY = new EvaluationStrategyImpl(
139 EMPTY_TRIPLE_SOURCE, FEDERATED_SERVICE_RESOLVER);
140
141 static {
142 Runtime.getRuntime().addShutdownHook(new Thread() {
143
144 @Override
145 public void run() {
146 FEDERATED_SERVICE_RESOLVER.shutDown();
147 }
148
149 });
150 }
151
152 public static FederatedServiceResolver getFederatedServiceResolver() {
153 return FEDERATED_SERVICE_RESOLVER;
154 }
155
156 public static TripleSource getEmptyTripleSource() {
157 return EMPTY_TRIPLE_SOURCE;
158 }
159
160 public static EvaluationStrategy getEvaluationStrategy(
161 @Nullable final TripleSource tripleSource, @Nullable final Dataset dataset) {
162
163 if (tripleSource != null) {
164 return new EvaluationStrategyImpl(tripleSource, dataset, FEDERATED_SERVICE_RESOLVER);
165 } else if (dataset != null) {
166 return new EvaluationStrategyImpl(EMPTY_TRIPLE_SOURCE, dataset,
167 FEDERATED_SERVICE_RESOLVER);
168 } else {
169 return EMPTY_EVALUATION_STRATEGY;
170 }
171 }
172
173 public static EvaluationStatistics getEvaluationStatistics(
174 @Nullable final ToDoubleFunction<StatementPattern> estimator) {
175
176 return estimator == null ? DEFAULT_EVALUATION_STATISTICS : new EvaluationStatistics() {
177
178 @Override
179 protected CardinalityCalculator createCardinalityCalculator() {
180 return new CardinalityCalculator() {
181
182 @Override
183 public final double getCardinality(final StatementPattern pattern) {
184 final double estimate = estimator.applyAsDouble(pattern);
185 return estimate >= 0.0 ? estimate : super.getCardinality(pattern);
186 }
187
188 };
189 }
190
191 };
192 }
193
194 public static TupleExpr parseTupleExpr(final String string, @Nullable final String baseURI,
195 @Nullable final Map<String, String> namespaces) throws MalformedQueryException {
196
197 Objects.requireNonNull(string);
198 final TupleExpr expr = ((Projection) parseQuery("SELECT *\nWHERE {\n" + string + "\n}",
199 baseURI, namespaces).getTupleExpr()).getArg();
200 expr.setParentNode(null);
201 return expr;
202 }
203
204 public static ValueExpr parseValueExpr(final String string, @Nullable final String baseURI,
205 @Nullable final Map<String, String> namespaces) throws MalformedQueryException {
206
207 Objects.requireNonNull(string);
208 final TupleExpr expr = parseQuery("SELECT ((" + string + ") AS ?dummy) WHERE {}", baseURI,
209 namespaces).getTupleExpr();
210 return ((Extension) ((Projection) expr).getArg()).getElements().get(0).getExpr();
211 }
212
213 public static ParsedQuery parseQuery(final String string, @Nullable final String baseURI,
214 @Nullable final Map<String, String> namespaces) throws MalformedQueryException {
215 try {
216 final ASTQueryContainer qc = SyntaxTreeBuilder.parseQuery(string);
217 StringEscapesProcessor.process(qc);
218 BaseDeclProcessor.process(qc, baseURI);
219
220
221 final List<ASTPrefixDecl> prefixDeclList = qc.getPrefixDeclList();
222 final Map<String, String> prefixes = new LinkedHashMap<String, String>();
223 for (final ASTPrefixDecl prefixDecl : prefixDeclList) {
224 final String prefix = prefixDecl.getPrefix();
225 final String iri = prefixDecl.getIRI().getValue();
226 if (prefixes.containsKey(prefix)) {
227 throw new MalformedQueryException("Multiple prefix declarations for prefix '"
228 + prefix + "'");
229 }
230 prefixes.put(prefix, iri);
231 }
232 if (namespaces != null) {
233 final QNameProcessor visitor = new QNameProcessor(namespaces, prefixes);
234 try {
235 qc.jjtAccept(visitor, null);
236 } catch (final VisitorException e) {
237 throw new MalformedQueryException(e);
238 }
239 }
240
241 WildcardProjectionProcessor.process(qc);
242 BlankNodeVarProcessor.process(qc);
243 if (qc.containsQuery()) {
244 TupleExpr tupleExpr;
245 final TupleExprBuilder tupleExprBuilder = new TupleExprBuilder(
246 Statements.VALUE_FACTORY);
247 try {
248 tupleExpr = (TupleExpr) qc.jjtAccept(tupleExprBuilder, null);
249 } catch (final VisitorException e) {
250 throw new MalformedQueryException(e.getMessage(), e);
251 }
252 ParsedQuery query;
253 final ASTQuery queryNode = qc.getQuery();
254 if (queryNode instanceof ASTSelectQuery) {
255 query = new ParsedTupleQuery(string, tupleExpr);
256 } else if (queryNode instanceof ASTConstructQuery) {
257 query = new ParsedGraphQuery(string, tupleExpr, prefixes);
258 } else if (queryNode instanceof ASTAskQuery) {
259 query = new ParsedBooleanQuery(string, tupleExpr);
260 } else if (queryNode instanceof ASTDescribeQuery) {
261 query = new ParsedGraphQuery(string, tupleExpr, prefixes);
262 } else {
263 throw new RuntimeException("Unexpected query type: " + queryNode.getClass());
264 }
265 final Dataset dataset = DatasetDeclProcessor.process(qc);
266 if (dataset != null) {
267 query.setDataset(dataset);
268 }
269 return query;
270 } else {
271 throw new IncompatibleOperationException(
272 "supplied string is not a query operation");
273 }
274 } catch (final ParseException e) {
275 throw new MalformedQueryException(e.getMessage(), e);
276 } catch (final TokenMgrError e) {
277 throw new MalformedQueryException(e.getMessage(), e);
278 }
279 }
280
281 public static Value evaluateValueExpr(final ValueExpr expr, final BindingSet bindings) {
282 try {
283 return EMPTY_EVALUATION_STRATEGY.evaluate(expr, bindings);
284 } catch (final QueryEvaluationException ex) {
285 throw new IllegalArgumentException("Error evaluating value expr:\n" + expr
286 + "\nbindings: " + bindings, ex);
287 }
288 }
289
290 @SuppressWarnings("unchecked")
291 @Nullable
292 public static <T extends QueryModelNode> T normalize(@Nullable T expr,
293 final Function<Value, Value> normalizer) {
294 if (expr != null) {
295 expr = (T) expr.clone();
296 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
297
298 @Override
299 public void meet(final Var node) throws RuntimeException {
300 if (node.hasValue()) {
301 node.setValue(normalizer.apply(node.getValue()));
302 }
303 }
304
305 @Override
306 public void meet(final ValueConstant node) throws RuntimeException {
307 node.setValue(normalizer.apply(node.getValue()));
308 }
309
310 });
311 }
312 return expr;
313 }
314
315 public static Iterator<BindingSet> evaluateTupleExpr(TupleExpr expr,
316 @Nullable final Dataset dataset, @Nullable BindingSet bindings,
317 @Nullable EvaluationStrategy evaluationStrategy,
318 @Nullable EvaluationStatistics evaluationStatistics,
319 @Nullable final Function<Value, Value> valueNormalizer) {
320
321
322 bindings = bindings != null ? bindings : EmptyBindingSet.getInstance();
323 evaluationStrategy = evaluationStrategy != null ? evaluationStrategy
324 : Algebra.getEvaluationStrategy(null, dataset);
325 evaluationStatistics = evaluationStatistics != null ? evaluationStatistics
326 : Algebra.getEvaluationStatistics(null);
327
328
329 expr = expr.clone();
330 if (!(expr instanceof QueryRoot)) {
331 expr = new QueryRoot(expr);
332 }
333
334
335 if (valueNormalizer != null) {
336 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
337
338 @Override
339 public void meet(final Var node) throws RuntimeException {
340 if (node.hasValue()) {
341 node.setValue(valueNormalizer.apply(node.getValue()));
342 }
343 }
344
345 @Override
346 public void meet(final ValueConstant node) throws RuntimeException {
347 node.setValue(valueNormalizer.apply(node.getValue()));
348 }
349
350 });
351 }
352
353
354 LOGGER.trace("Query before optimization:\n{}", expr);
355 new BindingAssigner().optimize(expr, dataset, bindings);
356 new ConstantOptimizer(evaluationStrategy).optimize(expr, dataset, bindings);
357 new CompareOptimizer().optimize(expr, dataset, bindings);
358 new ConjunctiveConstraintSplitter().optimize(expr, dataset, bindings);
359 new DisjunctiveConstraintOptimizer().optimize(expr, dataset, bindings);
360 new SameTermFilterOptimizer().optimize(expr, dataset, bindings);
361 new QueryModelNormalizer().optimize(expr, dataset, bindings);
362 new QueryJoinOptimizer(evaluationStatistics).optimize(expr, dataset, bindings);
363 new IterativeEvaluationOptimizer().optimize(expr, dataset, bindings);
364 new FilterOptimizer().optimize(expr, dataset, bindings);
365 new OrderLimitOptimizer().optimize(expr, dataset, bindings);
366 LOGGER.trace("Query after optimization:\n{}", expr);
367
368
369 try {
370 return eu.fbk.rdfpro.util.Iterators.forIteration(evaluationStrategy.evaluate(expr,
371 EmptyBindingSet.getInstance()));
372 } catch (final QueryEvaluationException ex) {
373 throw new RuntimeException(ex);
374 }
375 }
376
377 public static boolean isBGP(final TupleExpr expr) {
378 final AtomicBoolean bgp = new AtomicBoolean(true);
379 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
380
381 @Override
382 protected void meetNode(final QueryModelNode node) throws RuntimeException {
383 if (!bgp.get()) {
384 return;
385 } else if (node instanceof StatementPattern || node instanceof Join
386 || node instanceof Var) {
387 super.meetNode(node);
388 } else {
389 bgp.set(false);
390 return;
391 }
392 }
393
394 });
395 return bgp.get();
396 }
397
398 public static <T> List<T> extractNodes(@Nullable final QueryModelNode expr,
399 final Class<T> clazz, @Nullable final Predicate<? super T> matchPredicate,
400 @Nullable final Predicate<QueryModelNode> recursePredicate) {
401 final List<T> result = new ArrayList<>();
402 if (expr != null) {
403 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
404
405 @SuppressWarnings("unchecked")
406 @Override
407 protected void meetNode(final QueryModelNode node) throws RuntimeException {
408 if (clazz.isInstance(node)
409 && (matchPredicate == null || matchPredicate.test((T) node))) {
410 result.add((T) node);
411 }
412 if (recursePredicate == null || recursePredicate.test(node)) {
413 super.meetNode(node);
414 }
415 }
416
417 });
418 }
419 return result;
420 }
421
422 public static Set<String> extractVariables(@Nullable final QueryModelNode expr,
423 final boolean onlyOutputVars) {
424 final Set<String> set = new HashSet<>();
425 if (expr != null) {
426 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
427
428 @Override
429 public void meet(final Var var) throws RuntimeException {
430 if (!var.hasValue()) {
431 final String name = var.getName();
432 final int index = name.indexOf('-');
433 set.add(index < 0 ? name : name.substring(0, index));
434 }
435 }
436
437 });
438 if (onlyOutputVars && expr instanceof TupleExpr) {
439 set.retainAll(((TupleExpr) expr).getBindingNames());
440 }
441 }
442 return set;
443 }
444
445 public static void internStrings(@Nullable final QueryModelNode expr) {
446 if (expr != null) {
447 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
448
449 @Override
450 public void meet(final Var var) throws RuntimeException {
451 var.setName(var.getName().intern());
452 }
453
454 });
455 }
456 }
457
458 @Nullable
459 public static <T extends QueryModelNode> T rewrite(@Nullable final T node,
460 @Nullable final Map<String, Var> substitutions) {
461 if (node == null || substitutions == null) {
462 return null;
463 }
464 @SuppressWarnings("unchecked")
465 final T result = (T) node.clone();
466 result.visit(new QueryModelVisitorBase<RuntimeException>() {
467
468 @Override
469 public void meet(final Var var) throws RuntimeException {
470 if (!var.hasValue()) {
471 final Var replacement = substitutions.get(var.getName());
472 if (replacement != null) {
473 var.setName(replacement.getName());
474 var.setValue(replacement.getValue());
475 var.setAnonymous(replacement.isAnonymous());
476 }
477 }
478 }
479
480 });
481 return result;
482 }
483
484 @Nullable
485 public static <T extends QueryModelNode> T rewrite(@Nullable final T node,
486 @Nullable final BindingSet bindings) {
487
488 if (node == null || bindings == null) {
489 return node;
490 }
491
492 @SuppressWarnings("unchecked")
493 final T result = (T) node.clone();
494 result.setParentNode(null);
495
496 result.visit(new QueryModelVisitorBase<RuntimeException>() {
497
498 @Override
499 public void meet(final Var var) {
500 final Binding binding = bindings.getBinding(var.getName());
501 if (binding != null) {
502 if (var.getParentNode() instanceof StatementPattern) {
503 var.setValue(binding.getValue());
504 var.setName("_const-" + var.getName());
505 } else {
506 replaceNode(result, var, new ValueConstant(binding.getValue()));
507 }
508 }
509 }
510
511 });
512 return result;
513 }
514
515 @Nullable
516 public static TupleExpr normalizeVars(@Nullable TupleExpr expr) {
517
518 if (expr == null) {
519 return null;
520 }
521
522 expr = expr.clone();
523 expr.setParentNode(null);
524
525 final Map<String, String> replacements = new HashMap<>();
526 final List<Filter> filtersToDrop = new ArrayList<>();
527 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
528
529 @Override
530 public void meet(final SameTerm same) throws RuntimeException {
531 if (same.getParentNode() instanceof Filter && same.getLeftArg() instanceof Var
532 && same.getRightArg() instanceof Var) {
533 final Var leftVar = (Var) same.getLeftArg();
534 final Var rightVar = (Var) same.getRightArg();
535 if (leftVar.isAnonymous() || rightVar.isAnonymous()) {
536 if (!rightVar.isAnonymous()) {
537 replacements.put(leftVar.getName(), rightVar.getName());
538 } else {
539 replacements.put(rightVar.getName(), leftVar.getName());
540 }
541 filtersToDrop.add((Filter) same.getParentNode());
542 }
543 }
544 }
545
546 });
547 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
548
549 @Override
550 public void meet(final Var var) throws RuntimeException {
551 if (!var.hasValue()) {
552 final String newName = replacements.get(var.getName());
553 if (newName != null) {
554 var.setName(newName);
555 } else if (var.getName().startsWith("_const-")) {
556 if (var.getParentNode() instanceof StatementPattern) {
557 for (final Var var2 : ((StatementPattern) var.getParentNode())
558 .getVarList()) {
559 if (var2.hasValue() && var.getName().startsWith(var2.getName())) {
560 var.setValue(var2.getValue());
561 }
562 }
563 }
564 } else if (var.getName().startsWith("-anon-")) {
565 var.setName(var.getName().replace('-', '_'));
566 } else {
567 final int index = var.getName().indexOf('-');
568 if (index >= 0) {
569 var.setName(var.getName().substring(0, index));
570 }
571 }
572 }
573 }
574
575 });
576 for (final Filter filter : filtersToDrop) {
577 expr = (TupleExpr) replaceNode(expr, filter, filter.getArg());
578 }
579 return expr;
580 }
581
582 public static TupleExpr rewriteGraph(final TupleExpr expr, final Var graphVar) {
583
584 if (expr == null) {
585 return null;
586 }
587
588 final TupleExpr result = expr.clone();
589 result.setParentNode(null);
590
591 result.visit(new QueryModelVisitorBase<RuntimeException>() {
592
593 @Override
594 public void meet(final StatementPattern pattern) throws RuntimeException {
595 pattern.setContextVar(graphVar);
596 }
597
598 });
599 return result;
600 }
601
602 public static QueryModelNode replaceNode(final QueryModelNode root,
603 final QueryModelNode current, final QueryModelNode replacement) {
604 final QueryModelNode parent = current.getParentNode();
605 if (parent == null) {
606 replacement.setParentNode(null);
607 return replacement;
608 } else {
609 parent.replaceChildNode(current, replacement);
610 current.setParentNode(null);
611 return root;
612 }
613 }
614
615 @Nullable
616 public static TupleExpr explodeFilters(@Nullable TupleExpr expr) {
617
618 if (expr == null) {
619 return null;
620 }
621
622 expr = expr.clone();
623 expr.setParentNode(null);
624
625 final List<Filter> filters = extractNodes(expr, Filter.class, (final Filter filter) -> {
626 return filter.getCondition() instanceof And;
627 }, null);
628
629 if (filters.isEmpty()) {
630 return expr;
631 }
632
633 for (final Filter filter : filters) {
634 TupleExpr arg = filter.getArg();
635 for (final ValueExpr condition : extractNodes(filter.getCondition(), ValueExpr.class,
636 e -> !(e instanceof And), e -> e instanceof And)) {
637 arg = new Filter(arg, condition);
638 }
639 expr = (TupleExpr) replaceNode(expr, filter, arg);
640 }
641
642 return expr;
643 }
644
645 @Nullable
646 public static TupleExpr pushFilters(@Nullable TupleExpr expr) {
647
648 if (expr == null) {
649 return null;
650 }
651
652 expr = expr.clone();
653 expr.setParentNode(null);
654
655 boolean dirty = true;
656 while (dirty) {
657 dirty = false;
658 for (final Filter filter : extractNodes(expr, Filter.class, null, null)) {
659
660 TupleExpr arg = filter.getArg();
661 while (arg instanceof Filter) {
662 arg = ((Filter) arg).getArg();
663 }
664
665 if (arg instanceof Join) {
666 final ValueExpr condition = filter.getCondition();
667 final Set<String> filterVars = extractVariables(condition, false);
668 final Join join = (Join) arg;
669 boolean rewritten = false;
670 if (join.getLeftArg().getAssuredBindingNames().containsAll(filterVars)) {
671 join.setLeftArg(new Filter(join.getLeftArg(), condition.clone()));
672 rewritten = true;
673 }
674 if (join.getRightArg().getAssuredBindingNames().containsAll(filterVars)) {
675 join.setRightArg(new Filter(join.getRightArg(), condition.clone()));
676 rewritten = true;
677 }
678 if (rewritten) {
679 expr = (TupleExpr) replaceNode(expr, filter, filter.getArg());
680 dirty = true;
681 }
682 } else if (arg instanceof Extension) {
683 final Extension ext = (Extension) arg;
684 final TupleExpr extArg = ext.getArg();
685 final Set<String> vars = extArg.getBindingNames();
686 boolean canMove = true;
687 for (TupleExpr e = filter; e instanceof Filter; e = ((Filter) e).getArg()) {
688 canMove = canMove
689 && vars.containsAll(Algebra.extractVariables(
690 ((Filter) e).getCondition(), false));
691 }
692 if (canMove) {
693 final Filter lastFilter = (Filter) ext.getParentNode();
694 expr = (TupleExpr) replaceNode(expr, filter, ext);
695 lastFilter.setArg(extArg);
696 ext.setArg(filter);
697 }
698 }
699 }
700 }
701
702 return expr;
703 }
704
705 @Nullable
706 public static TupleExpr pushExtensions(@Nullable TupleExpr expr) {
707
708 if (expr == null) {
709 return null;
710 }
711
712 expr = expr.clone();
713 expr.setParentNode(null);
714
715 boolean dirty = true;
716 while (dirty) {
717 dirty = false;
718 for (final Extension extension : extractNodes(expr, Extension.class, null, null)) {
719
720 TupleExpr arg = extension.getArg();
721 while (arg instanceof Extension) {
722 arg = ((Filter) arg).getArg();
723 }
724
725 if (arg instanceof Join) {
726 final Join join = (Join) arg;
727 for (final ExtensionElem elem : new ArrayList<>(extension.getElements())) {
728 final Set<String> elemVars = extractVariables(elem.getExpr(), false);
729 Extension newArg = null;
730 if (join.getLeftArg().getAssuredBindingNames().containsAll(elemVars)) {
731 newArg = join.getLeftArg() instanceof Extension ? (Extension) join
732 .getLeftArg() : new Extension(join.getLeftArg());
733 join.setLeftArg(newArg);
734 } else if (join.getRightArg().getAssuredBindingNames().contains(elemVars)) {
735 newArg = join.getRightArg() instanceof Extension ? (Extension) join
736 .getRightArg() : new Extension(join.getRightArg());
737 join.setRightArg(newArg);
738 }
739 if (newArg != null) {
740 newArg.addElement(elem.clone());
741 extension.getElements().remove(elem);
742 dirty = true;
743 }
744 }
745 if (extension.getElements().isEmpty()) {
746 expr = (TupleExpr) replaceNode(expr, extension, extension.getArg());
747 }
748 }
749 }
750 }
751
752 return expr;
753 }
754
755 public static TupleExpr[] splitTupleExpr(final TupleExpr expr, final Set<URI> vocabulary,
756 final int partition) {
757
758 return splitTupleExpr(expr, new Predicate<StatementPattern>() {
759
760 @Override
761 public boolean test(final StatementPattern pattern) {
762 for (final Var var : pattern.getVarList()) {
763 if (vocabulary.contains(var.getValue())) {
764 return true;
765 }
766 }
767 return false;
768 }
769
770 }, partition);
771 }
772
773 public static TupleExpr[] splitTupleExpr(@Nullable final TupleExpr expr,
774 final Predicate<StatementPattern> predicate, final int partition) {
775
776 if (expr == null) {
777 return new TupleExpr[] { null, null };
778 }
779
780 final TupleExpr clonedExpr = expr.clone();
781 clonedExpr.setParentNode(null);
782
783 final AtomicReference<TupleExpr> unsplittable = new AtomicReference<>(null);
784 try {
785 final List<TupleExpr> matching = new ArrayList<>();
786 final List<TupleExpr> nonMatching = new ArrayList<>();
787 clonedExpr.visit(new QueryModelVisitorBase<RuntimeException>() {
788
789 private int flag = 0;
790
791 private boolean top = true;
792
793 @Override
794 protected void meetNode(final QueryModelNode node) throws RuntimeException {
795 if (node instanceof TupleExpr) {
796
797 int flag;
798 if (node instanceof StatementPattern) {
799 flag = predicate.test((StatementPattern) node) ? 1 : 2;
800 this.flag = this.flag | flag;
801
802 } else {
803 final int oldFlag = this.flag;
804 final boolean oldTop = this.top;
805 this.flag = 0;
806 this.top &= node instanceof Join;
807 node.visitChildren(this);
808 flag = this.flag;
809 this.flag = oldFlag | this.flag;
810 this.top = oldTop;
811 }
812
813 if (this.top && !(node instanceof Join)) {
814 if (flag == 1) {
815 matching.add((TupleExpr) node);
816 } else if (flag == 2) {
817 nonMatching.add((TupleExpr) node);
818 } else {
819 unsplittable.set((TupleExpr) node);
820 throw new IllegalArgumentException("Cannot split:\n" + expr);
821 }
822 }
823 }
824 }
825
826 });
827
828 final TupleExpr[] result = new TupleExpr[2];
829 final List<List<TupleExpr>> exprs = Arrays.asList(matching, nonMatching);
830 for (int i = 0; i < 2; ++i) {
831 for (final TupleExpr e : exprs.get(i)) {
832 final TupleExpr clone = e.clone();
833 result[i] = result[i] == null ? clone : new Join(result[i], clone);
834 }
835 }
836 return result;
837
838 } catch (final RuntimeException ex) {
839 final TupleExpr e = unsplittable.get();
840 if ((e instanceof Filter || e instanceof Extension)
841 && (partition == 0 || partition == 1)) {
842 final TupleExpr expr2 = (TupleExpr) replaceNode(clonedExpr, e,
843 ((UnaryTupleOperator) e).getArg());
844 final TupleExpr[] result = splitTupleExpr(expr2, predicate, partition);
845 boolean fixed = false;
846 if (e instanceof Filter) {
847 final ValueExpr condition = ((Filter) e).getCondition();
848 final Set<String> vars = extractVariables(condition, false);
849 for (int i = 0; i < 2; ++i) {
850 if (result[i].getAssuredBindingNames().containsAll(vars)) {
851 result[i] = new Filter(result[i], condition);
852 fixed = true;
853 }
854 }
855 if (!fixed && (partition == 1 || partition == 2)) {
856 result[partition] = new Filter(result[partition], condition);
857 fixed = true;
858 }
859 } else {
860 final List<ExtensionElem> elems = ((Extension) e).getElements();
861 final Set<String> vars = new HashSet<>();
862 for (final ExtensionElem elem : elems) {
863 vars.addAll(extractVariables(elem, false));
864 }
865 for (int i = 0; i < 2; ++i) {
866 if (i == partition || result[i].getAssuredBindingNames().containsAll(vars)) {
867 result[i] = new Extension(result[i], elems);
868 fixed = true;
869 break;
870 }
871 }
872 if (!fixed && (partition == 1 || partition == 2)) {
873 result[partition] = new Extension(result[partition], elems);
874 fixed = true;
875 }
876 }
877 if (fixed) {
878 return result;
879 }
880 }
881 throw ex;
882 }
883 }
884
885 public static String renderQuery(final TupleExpr expr, @Nullable final Dataset dataset,
886 @Nullable final Map<String, String> prefixes, final boolean forceSelect) {
887 return new SPARQLRenderer(prefixes, forceSelect).render(expr, dataset);
888 }
889
890 public static String renderExpr(final TupleExpr expr,
891 @Nullable final Map<String, String> prefixes) {
892 return new SPARQLRenderer(prefixes, false).renderTupleExpr(expr);
893 }
894
895 public static String format(final TupleExpr expr) {
896 return expr == null ? "null" : renderExpr(expr, Namespaces.DEFAULT.prefixMap())
897 .replaceAll("[\n\r\t ]+", " ");
898 }
899
900 private static class QNameProcessor extends ASTVisitorBase {
901
902 private final Map<String, String> namespacesOut;
903
904 private final Map<String, String> namespacesIn;
905
906 public QNameProcessor(final Map<String, String> namespacesIn,
907 final Map<String, String> namespacesOut) {
908 this.namespacesOut = namespacesOut;
909 this.namespacesIn = namespacesIn;
910 }
911
912 @Override
913 public Object visit(final ASTServiceGraphPattern node, final Object data)
914 throws VisitorException {
915 node.setPrefixDeclarations(this.namespacesOut);
916 return super.visit(node, data);
917 }
918
919 @Override
920 public Object visit(final ASTQName qnameNode, final Object data) throws VisitorException {
921 final String qname = qnameNode.getValue();
922 final int colonIdx = qname.indexOf(':');
923 assert colonIdx >= 0 : "colonIdx should be >= 0: " + colonIdx;
924 final String prefix = qname.substring(0, colonIdx);
925 String localName = qname.substring(colonIdx + 1);
926 String namespace = this.namespacesOut.get(prefix);
927 if (namespace == null) {
928 namespace = this.namespacesIn.get(prefix);
929 }
930 if (namespace == null) {
931 throw new VisitorException("QName '" + qname + "' uses an undefined prefix");
932 }
933 localName = processEscapesAndHex(localName);
934 final ASTIRI iriNode = new ASTIRI(SyntaxTreeBuilderTreeConstants.JJTIRI);
935 iriNode.setValue(namespace + localName);
936 qnameNode.jjtReplaceWith(iriNode);
937 return null;
938 }
939
940 private String processEscapesAndHex(final String localName) {
941 final StringBuffer unencoded = new StringBuffer();
942 final Pattern hexPattern = Pattern.compile("([^\\\\]|^)(%[A-F\\d][A-F\\d])",
943 Pattern.CASE_INSENSITIVE);
944 Matcher m = hexPattern.matcher(localName);
945 boolean result = m.find();
946 while (result) {
947 final String previousChar = m.group(1);
948 final String encoded = m.group(2);
949
950 final int codePoint = Integer.parseInt(encoded.substring(1), 16);
951 final String decoded = String.valueOf(Character.toChars(codePoint));
952
953 m.appendReplacement(unencoded, previousChar + decoded);
954 result = m.find();
955 }
956 m.appendTail(unencoded);
957 final StringBuffer unescaped = new StringBuffer();
958 final Pattern escapedCharPattern = Pattern
959 .compile("\\\\[_~\\.\\-!\\$\\&\\'\\(\\)\\*\\+\\,\\;\\=\\:\\/\\?#\\@\\%]");
960 m = escapedCharPattern.matcher(unencoded.toString());
961 result = m.find();
962 while (result) {
963 final String escaped = m.group();
964 m.appendReplacement(unescaped, escaped.substring(1));
965 result = m.find();
966 }
967 m.appendTail(unescaped);
968 return unescaped.toString();
969 }
970
971 }
972
973 }