1 package eu.fbk.knowledgestore.server;
2
3 import java.io.IOException;
4 import java.util.LinkedHashMap;
5 import java.util.List;
6 import java.util.Map;
7 import java.util.concurrent.atomic.AtomicBoolean;
8 import java.util.regex.Matcher;
9 import java.util.regex.Pattern;
10
11 import javax.annotation.Nullable;
12
13 import com.google.common.base.Preconditions;
14
15 import org.openrdf.model.BNode;
16 import org.openrdf.model.URI;
17 import org.openrdf.model.Value;
18 import org.openrdf.query.BindingSet;
19 import org.openrdf.query.Dataset;
20 import org.openrdf.query.IncompatibleOperationException;
21 import org.openrdf.query.MalformedQueryException;
22 import org.openrdf.query.QueryEvaluationException;
23 import org.openrdf.query.algebra.ArbitraryLengthPath;
24 import org.openrdf.query.algebra.BinaryTupleOperator;
25 import org.openrdf.query.algebra.DescribeOperator;
26 import org.openrdf.query.algebra.Distinct;
27 import org.openrdf.query.algebra.Filter;
28 import org.openrdf.query.algebra.Group;
29 import org.openrdf.query.algebra.Order;
30 import org.openrdf.query.algebra.Projection;
31 import org.openrdf.query.algebra.Service;
32 import org.openrdf.query.algebra.Slice;
33 import org.openrdf.query.algebra.StatementPattern;
34 import org.openrdf.query.algebra.TupleExpr;
35 import org.openrdf.query.algebra.ZeroLengthPath;
36 import org.openrdf.query.algebra.evaluation.EvaluationStrategy;
37 import org.openrdf.query.algebra.evaluation.QueryBindingSet;
38 import org.openrdf.query.algebra.evaluation.impl.EvaluationStrategyImpl;
39 import org.openrdf.query.algebra.evaluation.iterator.DescribeIteration;
40 import org.openrdf.query.algebra.helpers.QueryModelVisitorBase;
41 import org.openrdf.query.impl.EmptyBindingSet;
42 import org.openrdf.query.parser.ParsedBooleanQuery;
43 import org.openrdf.query.parser.ParsedGraphQuery;
44 import org.openrdf.query.parser.ParsedQuery;
45 import org.openrdf.query.parser.ParsedTupleQuery;
46 import org.openrdf.query.parser.sparql.ASTVisitorBase;
47 import org.openrdf.query.parser.sparql.BaseDeclProcessor;
48 import org.openrdf.query.parser.sparql.BlankNodeVarProcessor;
49 import org.openrdf.query.parser.sparql.DatasetDeclProcessor;
50 import org.openrdf.query.parser.sparql.StringEscapesProcessor;
51 import org.openrdf.query.parser.sparql.TupleExprBuilder;
52 import org.openrdf.query.parser.sparql.WildcardProjectionProcessor;
53 import org.openrdf.query.parser.sparql.ast.ASTAskQuery;
54 import org.openrdf.query.parser.sparql.ast.ASTConstructQuery;
55 import org.openrdf.query.parser.sparql.ast.ASTDescribeQuery;
56 import org.openrdf.query.parser.sparql.ast.ASTIRI;
57 import org.openrdf.query.parser.sparql.ast.ASTOperationContainer;
58 import org.openrdf.query.parser.sparql.ast.ASTPrefixDecl;
59 import org.openrdf.query.parser.sparql.ast.ASTQName;
60 import org.openrdf.query.parser.sparql.ast.ASTQuery;
61 import org.openrdf.query.parser.sparql.ast.ASTQueryContainer;
62 import org.openrdf.query.parser.sparql.ast.ASTSelectQuery;
63 import org.openrdf.query.parser.sparql.ast.ASTServiceGraphPattern;
64 import org.openrdf.query.parser.sparql.ast.ParseException;
65 import org.openrdf.query.parser.sparql.ast.SyntaxTreeBuilder;
66 import org.openrdf.query.parser.sparql.ast.SyntaxTreeBuilderTreeConstants;
67 import org.openrdf.query.parser.sparql.ast.TokenMgrError;
68 import org.openrdf.query.parser.sparql.ast.VisitorException;
69
70 import info.aduna.iteration.CloseableIteration;
71 import info.aduna.iteration.ConvertingIteration;
72
73 import eu.fbk.knowledgestore.data.Data;
74 import eu.fbk.knowledgestore.triplestore.SelectQuery;
75 import eu.fbk.knowledgestore.triplestore.TripleTransaction;
76
77 final class SparqlHelper {
78
79 static ParsedQuery parse(final String queryStr, final String baseURI)
80 throws MalformedQueryException {
81 try {
82 final ASTQueryContainer qc = SyntaxTreeBuilder.parseQuery(queryStr);
83 StringEscapesProcessor.process(qc);
84 BaseDeclProcessor.process(qc, baseURI);
85 final Map<String, String> prefixes = parseHelper(qc);
86 WildcardProjectionProcessor.process(qc);
87 BlankNodeVarProcessor.process(qc);
88 if (qc.containsQuery()) {
89 TupleExpr tupleExpr;
90 final TupleExprBuilder tupleExprBuilder = new TupleExprBuilder(
91 Data.getValueFactory());
92 try {
93 tupleExpr = (TupleExpr) qc.jjtAccept(tupleExprBuilder, null);
94 } catch (final VisitorException e) {
95 throw new MalformedQueryException(e.getMessage(), e);
96 }
97 ParsedQuery query;
98 final ASTQuery queryNode = qc.getQuery();
99 if (queryNode instanceof ASTSelectQuery) {
100 query = new ParsedTupleQuery(queryStr, tupleExpr);
101 } else if (queryNode instanceof ASTConstructQuery) {
102 query = new ParsedGraphQuery(queryStr, tupleExpr, prefixes);
103 } else if (queryNode instanceof ASTAskQuery) {
104 query = new ParsedBooleanQuery(queryStr, tupleExpr);
105 } else if (queryNode instanceof ASTDescribeQuery) {
106 query = new ParsedGraphQuery(queryStr, tupleExpr, prefixes);
107 } else {
108 throw new RuntimeException("Unexpected query type: " + queryNode.getClass());
109 }
110 final Dataset dataset = DatasetDeclProcessor.process(qc);
111 if (dataset != null) {
112 query.setDataset(dataset);
113 }
114 return query;
115 } else {
116 throw new IncompatibleOperationException(
117 "supplied string is not a query operation");
118 }
119 } catch (final ParseException e) {
120 throw new MalformedQueryException(e.getMessage(), e);
121 } catch (final TokenMgrError e) {
122 throw new MalformedQueryException(e.getMessage(), e);
123 }
124 }
125
126 private static Map<String, String> parseHelper(final ASTOperationContainer qc)
127 throws MalformedQueryException {
128 final List<ASTPrefixDecl> prefixDeclList = qc.getPrefixDeclList();
129 final Map<String, String> prefixMap = new LinkedHashMap<String, String>();
130 for (final ASTPrefixDecl prefixDecl : prefixDeclList) {
131 final String prefix = prefixDecl.getPrefix();
132 final String iri = prefixDecl.getIRI().getValue();
133 if (prefixMap.containsKey(prefix)) {
134 throw new MalformedQueryException("Multiple prefix declarations for prefix '"
135 + prefix + "'");
136 }
137 prefixMap.put(prefix, iri);
138 }
139 final QNameProcessor visitor = new QNameProcessor(prefixMap);
140 try {
141 qc.jjtAccept(visitor, null);
142 } catch (final VisitorException e) {
143 throw new MalformedQueryException(e);
144 }
145 return prefixMap;
146 }
147
148 static CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
149 final TripleTransaction transaction, final TupleExpr expr,
150 @Nullable final Dataset dataset, @Nullable final BindingSet bindings,
151 @Nullable final Long timeout) throws QueryEvaluationException {
152
153 Preconditions.checkNotNull(transaction);
154
155 final AtomicBoolean delegate = new AtomicBoolean(false);
156 expr.visit(new QueryModelVisitorBase<RuntimeException>() {
157
158 @Override
159 public void meet(final StatementPattern node) throws RuntimeException {
160 delegate.set(true);
161 }
162
163 });
164
165 final EvaluationStrategy strategy = delegate.get() ? new DelegatingEvaluationStrategy(
166 transaction, dataset, timeout, false) : new LocalEvaluationStrategy(transaction,
167 dataset, timeout);
168
169 return strategy
170 .evaluate(expr, bindings != null ? bindings : EmptyBindingSet.getInstance());
171 }
172
173 private static Value skolemize(final Value value) {
174 return value instanceof BNode ? Data.getValueFactory().createURI("bnode:",
175 ((BNode) value).getID()) : value;
176 }
177
178 private static BindingSet skolemize(final BindingSet bindings) {
179 final QueryBindingSet result = new QueryBindingSet();
180 for (final String name : bindings.getBindingNames()) {
181 result.setBinding(name, skolemize(bindings.getValue(name)));
182 }
183 return result;
184 }
185
186 private static CloseableIteration<BindingSet, QueryEvaluationException> skolemize(
187 final CloseableIteration<BindingSet, QueryEvaluationException> iter) {
188 return new ConvertingIteration<BindingSet, BindingSet, QueryEvaluationException>(iter) {
189
190 @Override
191 protected BindingSet convert(final BindingSet bindings)
192 throws QueryEvaluationException {
193 return skolemize(bindings);
194 }
195
196 };
197 }
198
199 private static Value deskolemize(final Value value) {
200 if (value instanceof URI) {
201 final URI uri = (URI) value;
202 if (uri.getNamespace().equals("bnode:")) {
203 return Data.getValueFactory().createBNode(uri.getLocalName());
204 }
205 }
206 return value;
207 }
208
209 @Nullable
210 private static BindingSet deskolemize(@Nullable final BindingSet bindings) {
211 final QueryBindingSet result = new QueryBindingSet();
212 for (final String name : bindings.getBindingNames()) {
213 result.setBinding(name, deskolemize(bindings.getValue(name)));
214 }
215 return result;
216 }
217
218 private static CloseableIteration<BindingSet, QueryEvaluationException> deskolemize(
219 final CloseableIteration<BindingSet, QueryEvaluationException> iter) {
220 return new ConvertingIteration<BindingSet, BindingSet, QueryEvaluationException>(iter) {
221
222 @Override
223 protected BindingSet convert(final BindingSet bindings)
224 throws QueryEvaluationException {
225 return deskolemize(bindings);
226 }
227
228 };
229 }
230
231 private static final class LocalEvaluationStrategy extends EvaluationStrategyImpl {
232
233 private final TripleTransaction transaction;
234
235 @Nullable
236 private final Long timeout;
237
238 public LocalEvaluationStrategy(final TripleTransaction transaction, final Dataset dataset,
239 @Nullable final Long timeout) {
240 super(null, dataset, null);
241 this.transaction = Preconditions.checkNotNull(transaction);
242 this.timeout = timeout;
243 }
244
245 @Override
246 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
247 final DescribeOperator expr, final BindingSet bindings)
248 throws QueryEvaluationException {
249 return skolemize(new DescribeIteration(
250 deskolemize(evaluate(expr.getArg(), bindings)),
251 new DelegatingEvaluationStrategy(this.transaction, this.dataset, this.timeout,
252 true),
253 expr.getBindingNames(),
254 bindings));
255 }
256
257 }
258
259 private static final class DelegatingEvaluationStrategy extends EvaluationStrategyImpl {
260
261 private final TripleTransaction transaction;
262
263 @Nullable
264 private final Long timeout;
265
266 private final boolean skolemize;
267
268 public DelegatingEvaluationStrategy(final TripleTransaction transaction,
269 final Dataset dataset, @Nullable final Long timeout, final boolean skolemize) {
270 super(null, dataset, null);
271 this.transaction = transaction;
272 this.timeout = timeout;
273 this.skolemize = skolemize;
274 }
275
276 @Override
277 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
278 final DescribeOperator expr, final BindingSet bindings)
279 throws QueryEvaluationException {
280 return skolemize(new DescribeIteration(
281 deskolemize(evaluate(expr.getArg(), bindings)),
282 this.skolemize ? this : new DelegatingEvaluationStrategy(this.transaction,
283 this.dataset, this.timeout, true),
284 expr.getBindingNames(),
285 bindings));
286 }
287
288 @Override
289 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
290 final Projection expr, final BindingSet bindings) throws QueryEvaluationException {
291 return delegate(expr, bindings);
292 }
293
294 @Override
295 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
296 final BinaryTupleOperator expr, final BindingSet bindings)
297 throws QueryEvaluationException {
298 return delegate(expr, bindings);
299 }
300
301 @Override
302 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
303 final StatementPattern expr, final BindingSet bindings)
304 throws QueryEvaluationException {
305 return delegate(expr, bindings);
306 }
307
308 @Override
309 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
310 final Filter expr, final BindingSet bindings) throws QueryEvaluationException {
311 return delegate(expr, bindings);
312 }
313
314 @Override
315 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
316 final ZeroLengthPath expr, final BindingSet bindings)
317 throws QueryEvaluationException {
318 return delegate(expr, bindings);
319 }
320
321 @Override
322 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
323 final ArbitraryLengthPath expr, final BindingSet bindings)
324 throws QueryEvaluationException {
325 return delegate(expr, bindings);
326 }
327
328 @Override
329 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
330 final Service expr, final BindingSet bindings) throws QueryEvaluationException {
331 return delegate(expr, bindings);
332 }
333
334 @Override
335 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(final Slice expr,
336 final BindingSet bindings) throws QueryEvaluationException {
337 return delegate(expr, bindings);
338 }
339
340 @Override
341 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
342 final Distinct expr, final BindingSet bindings) throws QueryEvaluationException {
343 return delegate(expr, bindings);
344 }
345
346 @Override
347 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(final Group expr,
348 final BindingSet bindings) throws QueryEvaluationException {
349 return delegate(expr, bindings);
350 }
351
352 @Override
353 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(final Order expr,
354 final BindingSet bindings) throws QueryEvaluationException {
355 return delegate(expr, bindings);
356 }
357
358 private CloseableIteration<BindingSet, QueryEvaluationException> delegate(
359 final TupleExpr expr, final BindingSet bindings) throws QueryEvaluationException {
360
361 try {
362
363 final BindingSet actualBindings = this.skolemize ? skolemize(bindings) : bindings;
364
365
366 final SelectQuery query = SelectQuery.from(expr, this.dataset);
367
368
369 return this.transaction.query(query, actualBindings, this.timeout);
370
371 } catch (final IOException ex) {
372 throw new QueryEvaluationException(ex);
373 }
374 }
375
376 }
377
378 private static class QNameProcessor extends ASTVisitorBase {
379
380 private final Map<String, String> prefixMap;
381
382 public QNameProcessor(final Map<String, String> prefixMap) {
383 this.prefixMap = prefixMap;
384 }
385
386 @Override
387 public Object visit(final ASTServiceGraphPattern node, final Object data)
388 throws VisitorException {
389 node.setPrefixDeclarations(this.prefixMap);
390 return super.visit(node, data);
391 }
392
393 @Override
394 public Object visit(final ASTQName qnameNode, final Object data) throws VisitorException {
395 final String qname = qnameNode.getValue();
396 final int colonIdx = qname.indexOf(':');
397 assert colonIdx >= 0 : "colonIdx should be >= 0: " + colonIdx;
398 final String prefix = qname.substring(0, colonIdx);
399 String localName = qname.substring(colonIdx + 1);
400 String namespace = this.prefixMap.get(prefix);
401 if (namespace == null) {
402 namespace = Data.getNamespaceMap().get(prefix);
403 }
404 if (namespace == null) {
405 throw new VisitorException("QName '" + qname + "' uses an undefined prefix");
406 }
407 localName = processEscapesAndHex(localName);
408 final ASTIRI iriNode = new ASTIRI(SyntaxTreeBuilderTreeConstants.JJTIRI);
409 iriNode.setValue(namespace + localName);
410 qnameNode.jjtReplaceWith(iriNode);
411 return null;
412 }
413
414 private String processEscapesAndHex(final String localName) {
415 final StringBuffer unencoded = new StringBuffer();
416 final Pattern hexPattern = Pattern.compile("([^\\\\]|^)(%[A-F\\d][A-F\\d])",
417 Pattern.CASE_INSENSITIVE);
418 Matcher m = hexPattern.matcher(localName);
419 boolean result = m.find();
420 while (result) {
421 final String previousChar = m.group(1);
422 final String encoded = m.group(2);
423
424 final int codePoint = Integer.parseInt(encoded.substring(1), 16);
425 final String decoded = String.valueOf(Character.toChars(codePoint));
426
427 m.appendReplacement(unencoded, previousChar + decoded);
428 result = m.find();
429 }
430 m.appendTail(unencoded);
431 final StringBuffer unescaped = new StringBuffer();
432 final Pattern escapedCharPattern = Pattern
433 .compile("\\\\[_~\\.\\-!\\$\\&\\'\\(\\)\\*\\+\\,\\;\\=\\:\\/\\?#\\@\\%]");
434 m = escapedCharPattern.matcher(unencoded.toString());
435 result = m.find();
436 while (result) {
437 final String escaped = m.group();
438 m.appendReplacement(unescaped, escaped.substring(1));
439 result = m.find();
440 }
441 m.appendTail(unescaped);
442 return unescaped.toString();
443 }
444
445 }
446
447 }