1 package eu.fbk.rdfpro;
2
3 import java.util.ArrayList;
4 import java.util.Collections;
5 import java.util.HashMap;
6 import java.util.HashSet;
7 import java.util.List;
8 import java.util.Map;
9 import java.util.Set;
10 import java.util.concurrent.atomic.AtomicInteger;
11
12 import javax.annotation.Nullable;
13
14 import org.drools.core.spi.KnowledgeHelper;
15 import org.kie.api.KieServices;
16 import org.kie.api.builder.KieFileSystem;
17 import org.kie.api.builder.Message;
18 import org.kie.api.builder.Message.Level;
19 import org.kie.api.builder.ReleaseId;
20 import org.kie.api.builder.Results;
21 import org.kie.api.builder.model.KieBaseModel;
22 import org.kie.api.builder.model.KieModuleModel;
23 import org.kie.api.builder.model.KieSessionModel;
24 import org.kie.api.conf.EqualityBehaviorOption;
25 import org.kie.api.definition.type.Position;
26 import org.kie.api.runtime.KieContainer;
27 import org.kie.api.runtime.KieSession;
28 import org.openrdf.model.BNode;
29 import org.openrdf.model.Literal;
30 import org.openrdf.model.Resource;
31 import org.openrdf.model.Statement;
32 import org.openrdf.model.URI;
33 import org.openrdf.model.Value;
34 import org.openrdf.query.algebra.And;
35 import org.openrdf.query.algebra.EmptySet;
36 import org.openrdf.query.algebra.Exists;
37 import org.openrdf.query.algebra.Extension;
38 import org.openrdf.query.algebra.ExtensionElem;
39 import org.openrdf.query.algebra.Filter;
40 import org.openrdf.query.algebra.Join;
41 import org.openrdf.query.algebra.Not;
42 import org.openrdf.query.algebra.StatementPattern;
43 import org.openrdf.query.algebra.TupleExpr;
44 import org.openrdf.query.algebra.Union;
45 import org.openrdf.query.algebra.ValueExpr;
46 import org.openrdf.query.algebra.Var;
47 import org.openrdf.query.impl.ListBindingSet;
48 import org.openrdf.rio.RDFHandler;
49 import org.openrdf.rio.RDFHandlerException;
50 import org.slf4j.Logger;
51 import org.slf4j.LoggerFactory;
52
53 import eu.fbk.rdfpro.AbstractRDFHandlerWrapper;
54 import eu.fbk.rdfpro.Rule;
55 import eu.fbk.rdfpro.RuleEngine;
56 import eu.fbk.rdfpro.Ruleset;
57 import eu.fbk.rdfpro.util.Algebra;
58 import eu.fbk.rdfpro.util.Statements;
59
60 public class RuleEngineDrools extends RuleEngine {
61
62 private static final Logger LOGGER = LoggerFactory.getLogger(RuleEngineDrools.class);
63
64 private static final AtomicInteger COUNTER = new AtomicInteger(0);
65
66 private final KieContainer container;
67
68 private final Dictionary dictionary;
69
70 private final List<Quad> axioms;
71
72 private final List<Expression> expressions;
73
74 private final List<URI> ruleIDs;
75
76 public RuleEngineDrools(final Ruleset ruleset) {
77
78 super(ruleset);
79
80 final Translation t = new Translation(ruleset);
81
82 this.container = t.container;
83 this.dictionary = t.dictionary;
84 this.axioms = new ArrayList<>(t.axioms);
85 this.expressions = t.expressions;
86 this.ruleIDs = t.ruleIDs;
87 }
88
89 @Override
90 public String toString() {
91 return "DR rule engine";
92 }
93
94 @Override
95 protected RDFHandler doEval(final RDFHandler handler, final boolean deduplicate) {
96 return new Handler(handler);
97 }
98
99 public final class Handler extends AbstractRDFHandlerWrapper {
100
101 private final Dictionary dictionary;
102
103 private KieSession session;
104
105 private long timestamp;
106
107 private long initialSize;
108
109 private long[] activations;
110
111 Handler(final RDFHandler handler) {
112 super(handler);
113 this.dictionary = new Dictionary(RuleEngineDrools.this.dictionary);
114 this.session = null;
115 }
116
117 @Override
118 public void startRDF() throws RDFHandlerException {
119 super.startRDF();
120 this.timestamp = System.currentTimeMillis();
121 this.activations = new long[RuleEngineDrools.this.ruleIDs.size()];
122 this.session = RuleEngineDrools.this.container.newKieSession();
123 this.session.setGlobal("handler", this);
124 for (final Quad axiom : RuleEngineDrools.this.axioms) {
125 this.session.insert(axiom);
126 }
127 this.initialSize = this.session.getFactCount();
128 }
129
130 @Override
131 public synchronized void handleStatement(final Statement statement)
132 throws RDFHandlerException {
133 final long countBefore = this.session.getFactCount();
134 this.session.insert(Quad.encode(this.dictionary, statement));
135 final long countAfter = this.session.getFactCount();
136 if (countAfter > countBefore) {
137 this.handler.handleStatement(statement);
138 }
139 }
140
141 @Override
142 public void endRDF() throws RDFHandlerException {
143 this.session.fireAllRules();
144 if (LOGGER.isDebugEnabled()) {
145 final StringBuilder builder = new StringBuilder();
146 builder.append("Inference completed in ")
147 .append(System.currentTimeMillis() - this.timestamp).append(" ms, ")
148 .append(this.session.getFactCount() - this.initialSize)
149 .append(" quads total");
150 LOGGER.debug(builder.toString());
151 }
152 super.endRDF();
153 this.session.dispose();
154 this.session = null;
155 }
156
157 @Override
158 public void close() {
159 try {
160 if (this.session != null) {
161 this.session.dispose();
162 this.session = null;
163 }
164 } finally {
165 super.close();
166 }
167 }
168
169 public void triggered(final int ruleIndex) {
170 ++this.activations[ruleIndex];
171 }
172
173 public void insert(final KnowledgeHelper drools, final int subjectID,
174 final int predicateID, final int objectID, final int contextID)
175 throws RDFHandlerException {
176
177 if (!Dictionary.isResource(subjectID) || !Dictionary.isURI(predicateID)
178 || !Dictionary.isResource(contextID)) {
179 return;
180 }
181 final Quad quad = new Quad(subjectID, predicateID, objectID, contextID);
182 final long countBefore = this.session.getFactCount();
183 drools.insert(quad);
184 final long countAfter = this.session.getFactCount();
185 if (countAfter > countBefore) {
186 this.handler.handleStatement(quad.decode(this.dictionary));
187 }
188 }
189
190 public int eval(final int expressionIndex, final int... argIDs) {
191 return RuleEngineDrools.this.expressions.get(expressionIndex).evaluate(
192 this.dictionary, argIDs);
193 }
194
195 public boolean test(final int expressionIndex, final int... argIDs) {
196 try {
197 return ((Literal) RuleEngineDrools.this.expressions.get(expressionIndex).evaluate(
198 this.dictionary.decode(argIDs))).booleanValue();
199 } catch (final Throwable ex) {
200 return false;
201 }
202 }
203
204 }
205
206 public static final class Dictionary {
207
208 static final int SIZE = 4 * 1024 * 1024 - 1;
209
210 private final Value[] table;
211
212 public Dictionary() {
213 this.table = new Value[SIZE];
214 }
215
216 public Dictionary(final Dictionary source) {
217 this.table = source.table.clone();
218 }
219
220 public Value[] decode(final int... ids) {
221 final Value[] values = new Value[ids.length];
222 for (int i = 0; i < ids.length; ++i) {
223 values[i] = decode(ids[i]);
224 }
225 return values;
226 }
227
228 @Nullable
229 public Value decode(final int id) {
230 return this.table[id & 0x1FFFFFFF];
231 }
232
233 public int[] encode(final Value... values) {
234 final int[] ids = new int[values.length];
235 for (int i = 0; i < values.length; ++i) {
236 ids[i] = encode(values[i]);
237 }
238 return ids;
239 }
240
241 public int encode(@Nullable final Value value) {
242 if (value == null) {
243 return 0;
244 }
245 int id = (value.hashCode() & 0x7FFFFFFF) % SIZE;
246 if (id == 0) {
247 id = 1;
248 }
249 final int initialID = id;
250 while (true) {
251 final Value storedValue = this.table[id];
252 if (storedValue == null) {
253 this.table[id] = value;
254 break;
255 }
256 if (storedValue.equals(value)) {
257 break;
258 }
259 ++id;
260 if (id == SIZE) {
261 id = 1;
262 }
263 if (id == initialID) {
264 throw new Error("Dictionary full (capacity " + SIZE + ")");
265 }
266 }
267 if (value instanceof URI) {
268 return id;
269 } else if (value instanceof BNode) {
270 return id | 0x20000000;
271 } else {
272 return id | 0x40000000;
273 }
274 }
275
276 public static boolean isResource(final int id) {
277 return (id & 0x40000000) == 0;
278 }
279
280 public static boolean isURI(final int id) {
281 return (id & 0x60000000) == 0;
282 }
283
284 public static boolean isBNode(final int id) {
285 return (id & 0x60000000) == 0x20000000;
286 }
287
288 public static boolean isLiteral(final int id) {
289 return (id & 0x60000000) == 0x40000000;
290 }
291
292 }
293
294 public static final class Quad {
295
296 @Position(0)
297 private final int subjectID;
298
299 @Position(1)
300 private final int predicateID;
301
302 @Position(2)
303 private final int objectID;
304
305 @Position(3)
306 private final int contextID;
307
308 public Quad(final int subjectID, final int predicateID, final int objectID,
309 final int contextID) {
310 this.subjectID = subjectID;
311 this.predicateID = predicateID;
312 this.objectID = objectID;
313 this.contextID = contextID;
314 }
315
316 public int getSubjectID() {
317 return this.subjectID;
318 }
319
320 public int getPredicateID() {
321 return this.predicateID;
322 }
323
324 public int getObjectID() {
325 return this.objectID;
326 }
327
328 public int getContextID() {
329 return this.contextID;
330 }
331
332 @Override
333 public boolean equals(final Object object) {
334 if (object == this) {
335 return true;
336 }
337 if (!(object instanceof Quad)) {
338 return false;
339 }
340 final Quad other = (Quad) object;
341 return this.subjectID == other.subjectID && this.predicateID == other.predicateID
342 && this.objectID == other.objectID && this.contextID == other.contextID;
343 }
344
345 @Override
346 public int hashCode() {
347 return 7829 * this.subjectID + 1103 * this.predicateID + 137 * this.objectID
348 + this.contextID;
349 }
350
351 @Override
352 public String toString() {
353 final StringBuilder builder = new StringBuilder();
354 builder.append('(');
355 builder.append(this.subjectID);
356 builder.append(", ");
357 builder.append(this.predicateID);
358 builder.append(", ");
359 builder.append(this.objectID);
360 builder.append(", ");
361 builder.append(this.contextID);
362 builder.append(')');
363 return builder.toString();
364 }
365
366 public Statement decode(final Dictionary dictionary) {
367 return Statements.VALUE_FACTORY.createStatement(
368 (Resource) dictionary.decode(this.subjectID),
369 (URI) dictionary.decode(this.predicateID),
370 dictionary.decode(this.objectID),
371 (Resource) dictionary.decode(this.contextID));
372 }
373
374 public static Quad encode(final Dictionary dictionary, final Statement statement) {
375 return new Quad(
376 dictionary.encode(statement.getSubject()),
377 dictionary.encode(statement.getPredicate()),
378 dictionary.encode(statement.getObject()),
379 dictionary.encode(statement.getContext()));
380 }
381
382 public static Quad encode(final Dictionary dictionary, final Resource subject,
383 final URI predicate, final Value object, final Resource context) {
384 return new Quad(
385 dictionary.encode(subject),
386 dictionary.encode(predicate),
387 dictionary.encode(object),
388 dictionary.encode(context));
389 }
390
391 }
392
393 private static final class Translation {
394
395 private final StringBuilder builder;
396
397 public final Dictionary dictionary;
398
399 public final Set<Quad> axioms;
400
401 public final List<Expression> expressions;
402
403 public final List<URI> ruleIDs;
404
405 public KieContainer container;
406
407 public Translation(final Ruleset ruleset) {
408 this.dictionary = new Dictionary();
409 this.builder = new StringBuilder();
410 this.axioms = new HashSet<>();
411 this.expressions = new ArrayList<>();
412 this.ruleIDs = new ArrayList<>();
413 this.container = translate(ruleset);
414 }
415
416 private KieContainer translate(final Ruleset ruleset) {
417
418 this.builder.append("package eu.fbk.rdfpro.rules.drools;\n");
419 this.builder.append("import eu.fbk.rdfpro.RuleEngineDrools.Quad;\n");
420 this.builder.append("import eu.fbk.rdfpro.RuleEngineDrools.Handler;\n");
421 this.builder.append("import eu.fbk.rdfpro.RuleEngineDrools.Dictionary;\n");
422 this.builder.append("global Handler handler;\n");
423
424 for (final Rule rule : ruleset.getRules()) {
425
426
427 final int ruleIndex = this.ruleIDs.size();
428 this.ruleIDs.add(rule.getID());
429 this.builder.append("\nrule \"").append(rule.getID().getLocalName())
430 .append("\"\n");
431 this.builder.append("when\n");
432
433
434 final Map<String, Expression> extensionExprs = new HashMap<>();
435 final Set<String> matchedVars = new HashSet<>();
436 if (rule.getWhereExpr() != null) {
437 translate(Algebra.normalizeVars(rule.getWhereExpr()), Collections.emptySet(),
438 extensionExprs, matchedVars);
439 for (final String extensionVar : extensionExprs.keySet()) {
440 if (matchedVars.contains(extensionVar)) {
441 throw new IllegalArgumentException("Variable " + extensionVar
442 + " already used in body patterns");
443 }
444 }
445 }
446
447
448 this.builder.append("\nthen\n");
449 this.builder.append("handler.triggered(").append(ruleIndex).append(");\n");
450 if (rule.getInsertExpr() != null) {
451 for (final Map.Entry<String, Expression> entry : extensionExprs.entrySet()) {
452 final String var = entry.getKey();
453 final Expression expr = entry.getValue();
454 final int index = register(expr);
455 this.builder.append("int $").append(var).append(" = ")
456 .append(expr.toString("handler.eval(" + index + ", ", ");\n"));
457 }
458 for (final StatementPattern atom : Algebra.extractNodes(
459 Algebra.normalizeVars(rule.getInsertExpr()), StatementPattern.class,
460 null, null)) {
461 final List<Var> vars = atom.getVarList();
462 this.builder.append("handler.insert(drools, ");
463 for (int j = 0; j < 4; ++j) {
464 this.builder.append(j == 0 ? "" : ", ");
465 String name = null;
466 Value value = null;
467 if (j < vars.size()) {
468 final Var var = vars.get(j);
469 value = var.getValue();
470 name = var.getName();
471 }
472 if (name != null && value == null) {
473 this.builder.append("$").append(name);
474 } else {
475 this.builder.append(this.dictionary.encode(value));
476 }
477 }
478 this.builder.append(");\n");
479 }
480 }
481 this.builder.append("end\n");
482 }
483
484
485 final KieServices services = KieServices.Factory.get();
486 final KieFileSystem kfs = services.newKieFileSystem();
487
488
489 final String rulesetID = "ruleset" + COUNTER.getAndIncrement();
490 final KieModuleModel module = services.newKieModuleModel();
491 final KieBaseModel base = module.newKieBaseModel("kbase_" + rulesetID)
492 .setDefault(true).setEqualsBehavior(EqualityBehaviorOption.EQUALITY)
493 .addPackage("eu.fbk.rdfpro.rules.drools");
494 base.newKieSessionModel("session_" + rulesetID).setDefault(true)
495 .setType(KieSessionModel.KieSessionType.STATEFUL);
496 kfs.write("src/main/resources/META-INF/kmodule.xml", module.toXML());
497
498
499 final ReleaseId releaseId = services.newReleaseId("eu.fbk.rdfpro." + rulesetID,
500 rulesetID, "1.0");
501 kfs.writePomXML("<?xml version=\"1.0\"?>\n"
502 + "<project>\n"
503 + "<modelVersion>4.0.0</modelVersion>\n"
504 + "<groupId>" + releaseId.getGroupId() + "</groupId>\n"
505 + "<artifactId>" + releaseId.getArtifactId() + "</artifactId>\n"
506 + "<version>" + releaseId.getVersion() + "</version>\n"
507 + "<packaging>jar</packaging>\n"
508 + "</project>\n");
509
510
511 kfs.write("src/main/resources/eu/fbk/rdfpro/rules/drools/" + rulesetID + ".drl",
512 this.builder.toString());
513 LOGGER.trace("Generated DROOLS rules:\n" + this.builder);
514
515
516 final Results results = services.newKieBuilder(kfs).buildAll().getResults();
517 for (final Message message : results.getMessages(Level.INFO)) {
518 LOGGER.info("[DROOLS] {}", message);
519 }
520 for (final Message message : results.getMessages(Level.WARNING)) {
521 LOGGER.warn("[DROOLS] {}", message);
522 }
523 for (final Message message : results.getMessages(Level.ERROR)) {
524 LOGGER.error("[DROOLS] {}", message);
525 }
526 return services.newKieContainer(releaseId);
527 }
528
529 private void translate(final TupleExpr expr, final Set<Expression> conditionExprs,
530 final Map<String, Expression> extensionExprs, final Set<String> matchedVars) {
531
532 if (expr instanceof StatementPattern) {
533 final List<Var> vars = ((StatementPattern) expr).getVarList();
534 this.builder.append("Quad(");
535 for (int i = 0; i < vars.size(); ++i) {
536 this.builder.append(i == 0 ? "" : ", ");
537 if (vars.get(i).getValue() != null) {
538 this.builder.append(this.dictionary.encode(vars.get(i).getValue()));
539 } else {
540 this.builder.append('$').append(vars.get(i).getName());
541 matchedVars.add(vars.get(i).getName());
542 }
543 }
544 this.builder.append(';');
545 String separator = " ";
546 for (final Expression conditionExpr : conditionExprs) {
547 this.builder.append(separator).append(conditionExpr.toString(
548 "handler.test(" + register(conditionExpr) + ", ", ")"));
549 separator = ", ";
550 }
551 this.builder.append(")");
552
553 } else if (expr instanceof Join) {
554 final Join join = (Join) expr;
555 final Set<String> leftVars = Algebra.extractVariables(join.getLeftArg(), true);
556 final Set<Expression> leftConditionExprs = new HashSet<>();
557 final Set<Expression> rightConditionExprs = new HashSet<>();
558 for (final Expression conditionExpr : conditionExprs) {
559 if (leftVars.containsAll(conditionExpr.getVariables())) {
560 leftConditionExprs.add(conditionExpr);
561 } else {
562 rightConditionExprs.add(conditionExpr);
563 }
564 }
565 this.builder.append('(');
566 translate(join.getLeftArg(), leftConditionExprs, extensionExprs, matchedVars);
567 this.builder.append(" and ");
568 translate(join.getRightArg(), rightConditionExprs, extensionExprs, matchedVars);
569 this.builder.append(')');
570
571 } else if (expr instanceof Union) {
572 final Union union = (Union) expr;
573 this.builder.append('(');
574 translate(union.getLeftArg(), conditionExprs, extensionExprs, matchedVars);
575 this.builder.append(" or ");
576 translate(union.getRightArg(), conditionExprs, extensionExprs, matchedVars);
577 this.builder.append(')');
578
579 } else if (expr instanceof Extension) {
580 final Extension extension = (Extension) expr;
581 translate(extension.getArg(), conditionExprs, extensionExprs, matchedVars);
582 for (final ExtensionElem elem : extension.getElements()) {
583 if (elem.getExpr() instanceof Var
584 && elem.getName().equals(((Var) elem.getExpr()).getName())) {
585 continue;
586 }
587 if (extensionExprs.put(elem.getName(), new Expression(elem.getExpr())) != null) {
588 throw new IllegalArgumentException("Multiple bindings for variable "
589 + elem.getName());
590 }
591 }
592
593 } else if (expr instanceof Filter) {
594 final Filter filter = (Filter) expr;
595 final ValueExpr condition = filter.getCondition();
596 if (condition instanceof And) {
597 final ValueExpr leftCondition = ((And) condition).getLeftArg();
598 final ValueExpr rightCondition = ((And) condition).getRightArg();
599 translate(new Filter(new Filter(filter.getArg(), leftCondition),
600 rightCondition), conditionExprs, extensionExprs, matchedVars);
601 } else {
602 String existsOperator = null;
603 TupleExpr existsArg = null;
604 if (condition instanceof Exists) {
605 existsOperator = "exists";
606 existsArg = ((Exists) condition).getSubQuery();
607 } else if (condition instanceof Not
608 && ((Not) condition).getArg() instanceof Exists) {
609 existsOperator = "not";
610 existsArg = ((Exists) ((Not) condition).getArg()).getSubQuery();
611 }
612 if (existsOperator == null) {
613 final Set<Expression> newConditionExprs = new HashSet<>(conditionExprs);
614 newConditionExprs.add(new Expression(condition));
615 translate(filter.getArg(), newConditionExprs, extensionExprs, matchedVars);
616 } else {
617 final boolean emptyArg = filter.getArg() instanceof EmptySet;
618 if (!emptyArg) {
619 this.builder.append('(');
620 translate(filter.getArg(), conditionExprs, extensionExprs, matchedVars);
621 this.builder.append(" and ");
622 } else if (!conditionExprs.isEmpty()) {
623 throw new IllegalArgumentException("Unsupported body pattern: " + expr);
624 }
625 this.builder.append(existsOperator).append('(');
626 translate(existsArg, Collections.emptySet(), extensionExprs,
627 new HashSet<>());
628 this.builder.append(")").append(emptyArg ? "" : ")");
629 }
630 }
631
632 } else {
633 throw new IllegalArgumentException("Unsupported body pattern: " + expr);
634 }
635 }
636
637 private int register(final Expression expression) {
638 int index = this.expressions.indexOf(expression);
639 if (index < 0) {
640 index = this.expressions.size();
641 this.expressions.add(expression);
642 }
643 return index;
644 }
645
646 }
647
648 private static final class Expression {
649
650 private final ValueExpr expr;
651
652 private final List<String> variables;
653
654 public Expression(final ValueExpr expr) {
655 this.expr = expr;
656 this.variables = new ArrayList<>(Algebra.extractVariables(expr, false));
657 Collections.sort(this.variables);
658 }
659
660 public List<String> getVariables() {
661 return this.variables;
662 }
663
664 public Value evaluate(final Value... args) {
665 final ListBindingSet bindings = new ListBindingSet(this.variables, args);
666 return Algebra.evaluateValueExpr(this.expr, bindings);
667 }
668
669 public int evaluate(final Dictionary dictionary, final int... argIDs) {
670 return dictionary.encode(evaluate(dictionary.decode(argIDs)));
671 }
672
673 @Override
674 public boolean equals(final Object object) {
675 if (object == this) {
676 return true;
677 }
678 if (!(object instanceof Expression)) {
679 return false;
680 }
681 final Expression other = (Expression) object;
682 return this.expr.equals(other.expr);
683 }
684
685 @Override
686 public int hashCode() {
687 return this.expr.hashCode();
688 }
689
690 public String toString(final String prefix, final String suffix) {
691 final StringBuilder builder = new StringBuilder();
692 builder.append(prefix);
693 for (int i = 0; i < this.variables.size(); ++i) {
694 builder.append(i == 0 ? "" : ", ");
695 builder.append("$").append(this.variables.get(i));
696 }
697 builder.append(suffix);
698 return builder.toString();
699 }
700
701 @Override
702 public String toString() {
703 return toString("eval(", ")");
704 }
705
706 }
707
708 }