1   /*
2    * RDFpro - An extensible tool for building stream-oriented RDF processing libraries.
3    * 
4    * Written in 2015 by Francesco Corcoglioniti with support by Alessio Palmero Aprosio and Marco
5    * Rospocher. Contact info on http://rdfpro.fbk.eu/
6    * 
7    * To the extent possible under law, the authors have dedicated all copyright and related and
8    * neighboring rights to this software to the public domain worldwide. This software is
9    * distributed without any warranty.
10   * 
11   * You should have received a copy of the CC0 Public Domain Dedication along with this software.
12   * If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
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             // was: final Map<String, String> prefixes = parseHelper(qc, namespaces);
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); // [FC] changed
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         // Apply defaults where necessary
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         // Add a dummy query root node to help with the optimization
329         expr = expr.clone();
330         if (!(expr instanceof QueryRoot)) {
331             expr = new QueryRoot(expr);
332         }
333 
334         // Replace constant values in the query with corresponding values in the model
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         // Optimize the query
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         // Start the query, returning a CloseableIteration over its results
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) { // [FC] added lookup of default namespace
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 }