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;
15  
16  import java.io.IOException;
17  import java.io.Reader;
18  import java.util.ArrayList;
19  import java.util.Arrays;
20  import java.util.Collection;
21  import java.util.Collections;
22  import java.util.HashMap;
23  import java.util.HashSet;
24  import java.util.Iterator;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.Objects;
28  import java.util.Set;
29  import java.util.TreeSet;
30  import java.util.UUID;
31  import java.util.concurrent.atomic.AtomicBoolean;
32  import java.util.concurrent.atomic.AtomicInteger;
33  import java.util.concurrent.atomic.AtomicLong;
34  import java.util.concurrent.atomic.AtomicReference;
35  import java.util.function.Function;
36  import java.util.function.Supplier;
37  
38  import javax.annotation.Nullable;
39  
40  import com.google.common.base.Preconditions;
41  import com.google.common.collect.ImmutableList;
42  import com.google.common.collect.ImmutableSet;
43  import com.google.common.collect.Ordering;
44  import com.google.common.io.CharStreams;
45  import com.google.common.io.LineProcessor;
46  
47  import org.openrdf.model.BNode;
48  import org.openrdf.model.Literal;
49  import org.openrdf.model.Model;
50  import org.openrdf.model.Namespace;
51  import org.openrdf.model.Resource;
52  import org.openrdf.model.Statement;
53  import org.openrdf.model.URI;
54  import org.openrdf.model.Value;
55  import org.openrdf.model.ValueFactory;
56  import org.openrdf.model.impl.ContextStatementImpl;
57  import org.openrdf.model.vocabulary.RDF;
58  import org.openrdf.model.vocabulary.SESAME;
59  import org.openrdf.query.BindingSet;
60  import org.openrdf.query.QueryEvaluationException;
61  import org.openrdf.query.algebra.Compare;
62  import org.openrdf.query.algebra.Compare.CompareOp;
63  import org.openrdf.query.algebra.Exists;
64  import org.openrdf.query.algebra.Extension;
65  import org.openrdf.query.algebra.ExtensionElem;
66  import org.openrdf.query.algebra.Filter;
67  import org.openrdf.query.algebra.FunctionCall;
68  import org.openrdf.query.algebra.Join;
69  import org.openrdf.query.algebra.QueryModelNode;
70  import org.openrdf.query.algebra.StatementPattern;
71  import org.openrdf.query.algebra.TupleExpr;
72  import org.openrdf.query.algebra.ValueExpr;
73  import org.openrdf.query.algebra.Var;
74  import org.openrdf.query.algebra.evaluation.EvaluationStrategy;
75  import org.openrdf.query.algebra.evaluation.TripleSource;
76  import org.openrdf.query.algebra.evaluation.impl.EvaluationStatistics;
77  import org.openrdf.query.algebra.evaluation.impl.EvaluationStrategyImpl;
78  import org.openrdf.query.algebra.helpers.QueryModelVisitorBase;
79  import org.openrdf.query.impl.EmptyBindingSet;
80  import org.openrdf.rio.RDFHandler;
81  import org.openrdf.rio.RDFHandlerException;
82  import org.slf4j.Logger;
83  import org.slf4j.LoggerFactory;
84  
85  import info.aduna.iteration.CloseableIteration;
86  
87  import eu.fbk.rdfpro.util.Algebra;
88  import eu.fbk.rdfpro.util.Environment;
89  import eu.fbk.rdfpro.util.IO;
90  import eu.fbk.rdfpro.util.Namespaces;
91  import eu.fbk.rdfpro.util.QuadModel;
92  import eu.fbk.rdfpro.util.Statements;
93  import eu.fbk.rdfpro.util.Tracker;
94  import eu.fbk.rdfpro.vocab.RR;
95  
96  /**
97   * Rule definition.
98   */
99  public final class Rule implements Comparable<Rule> {
100 
101     private static final Logger LOGGER = LoggerFactory.getLogger(Rule.class);
102 
103     private static final AtomicLong ID_COUNTER = new AtomicLong(0L);
104 
105     private static final AtomicInteger DLOG_RULE_COUNTER = new AtomicInteger(0);
106 
107     private final URI id;
108 
109     private final boolean fixpoint;
110 
111     private final int phase;
112 
113     @Nullable
114     private final TupleExpr deleteExpr;
115 
116     @Nullable
117     private final TupleExpr insertExpr;
118 
119     @Nullable
120     private final TupleExpr whereExpr;
121 
122     @Nullable
123     private transient List<String> commonVariables;
124 
125     @Nullable
126     private transient Set<StatementPattern> deletePatterns;
127 
128     @Nullable
129     private transient Set<StatementPattern> insertPatterns;
130 
131     @Nullable
132     private transient Set<StatementPattern> wherePatterns;
133 
134     @Nullable
135     private transient Collector collector;
136 
137     private transient byte simple; // 0 = not computed, 1 = true, -1 = false
138 
139     private transient byte streamable; // 0 = not computed, 1 = true, -1 = false
140 
141     private transient byte safe; // 0 = not computed, 1 = true, -1 = false
142 
143     private transient byte specific; // 0 = not computed, 1 = true, -1 = false
144 
145     /**
146      * Creates a new rule.
147      *
148      * @param id
149      *            the rule ID, not null
150      * @param fixpoint
151      *            true, if the rule should be evaluated with a fixpoint semantics
152      * @param phase
153      *            the evaluation phase associated to this rule (defaults to zero)
154      * @param deleteExpr
155      *            the optional DELETE expression; if present, must be a BGP
156      * @param insertExpr
157      *            the optional INSERT expression; if present, must be a BGP
158      * @param whereExpr
159      *            the optional WHERE expression (absent in case of rules asserting axiomatic
160      *            quads)
161      */
162     public Rule(final URI id, final boolean fixpoint, final int phase,
163             @Nullable final TupleExpr deleteExpr, @Nullable final TupleExpr insertExpr,
164             @Nullable final TupleExpr whereExpr) {
165 
166         Objects.requireNonNull(id, "No rule ID specified");
167 
168         this.id = id;
169         this.fixpoint = fixpoint;
170         this.phase = phase;
171         this.deleteExpr = Algebra.normalizeVars(deleteExpr);
172         this.insertExpr = Algebra.normalizeVars(insertExpr);
173         this.whereExpr = Algebra.pushFilters(whereExpr);
174         this.commonVariables = null;
175         this.simple = 0;
176         this.safe = 0;
177 
178         Algebra.internStrings(this.deleteExpr);
179         Algebra.internStrings(this.insertExpr);
180         Algebra.internStrings(this.whereExpr);
181 
182         Preconditions.checkArgument(this.deleteExpr == null || Algebra.isBGP(this.deleteExpr));
183         Preconditions.checkArgument(this.insertExpr == null || Algebra.isBGP(this.insertExpr));
184     }
185 
186     /**
187      * Returns the rule ID.
188      *
189      * @return the rule ID
190      */
191     public URI getID() {
192         return this.id;
193     }
194 
195     /**
196      * Returns true if the rule must be evaluated using a fixpoint semantics
197      *
198      * @return true, for fixpoint rules
199      */
200     public boolean isFixpoint() {
201         return this.fixpoint;
202     }
203 
204     /**
205      * Returns the evaluation phase this rule is associated to. Evaluation phases with lower index
206      * are executed first.
207      *
208      * @return an integer (possibly negative) identifying the evaluation phase.
209      */
210     public int getPhase() {
211         return this.phase;
212     }
213 
214     /**
215      * Returns the optional DELETE expression
216      *
217      * @return the DELETE expression if present, null otherwise
218      */
219     @Nullable
220     public TupleExpr getDeleteExpr() {
221         return this.deleteExpr;
222     }
223 
224     /**
225      * Returns the optional INSERT expression
226      *
227      * @return the INSERT expression if present, null otherwise
228      */
229     @Nullable
230     public TupleExpr getInsertExpr() {
231         return this.insertExpr;
232     }
233 
234     /**
235      * Returns the optional WHERE expression.
236      *
237      * @return the WHERE expression if present; null otherwise
238      */
239     @Nullable
240     public TupleExpr getWhereExpr() {
241         return this.whereExpr;
242     }
243 
244     /**
245      * Returns the statement patterns in the DELETE expression, if any.
246      *
247      * @return a non-null set with the statement patterns in the DELETE expression
248      */
249     public Set<StatementPattern> getDeletePatterns() {
250         if (this.deletePatterns == null) {
251             this.deletePatterns = this.deleteExpr == null ? ImmutableSet.of() : ImmutableSet
252                     .copyOf(Algebra.extractNodes(this.deleteExpr, StatementPattern.class, null,
253                             null));
254         }
255         return this.deletePatterns;
256     }
257 
258     /**
259      * Returns the statement patterns in the INSERT expression, if any.
260      *
261      * @return a non-null set with the statement patterns in the INSERT expression
262      */
263     public Set<StatementPattern> getInsertPatterns() {
264         if (this.insertPatterns == null) {
265             this.insertPatterns = this.insertExpr == null ? ImmutableSet.of() : ImmutableSet
266                     .copyOf(Algebra.extractNodes(this.insertExpr, StatementPattern.class, null,
267                             null));
268         }
269         return this.insertPatterns;
270     }
271 
272     /**
273      * Returns the statement patterns in the WHERE expression, if any.
274      *
275      * @return a non-null set with the statement patterns in the WHERE expression
276      */
277     public Set<StatementPattern> getWherePatterns() {
278         if (this.wherePatterns == null) {
279             this.wherePatterns = this.whereExpr == null ? ImmutableSet.of() : ImmutableSet
280                     .copyOf(Algebra.extractNodes(this.whereExpr, StatementPattern.class, null,
281                             null));
282         }
283         return this.wherePatterns;
284     }
285 
286     /**
287      * Returns a sorted list with the variables returned by the WHERE expression that are
288      * referenced either in the DELETE or in the INSERT expressions.
289      *
290      * @return a sorted list of common variables between the WHERE expression and the DELETE and
291      *         INSERT expressions
292      */
293     public List<String> getCommonVariables() {
294         if (this.commonVariables == null) {
295             if (this.deleteExpr == null && this.insertExpr == null || this.whereExpr == null) {
296                 this.commonVariables = ImmutableList.of();
297             } else {
298                 final Set<String> vars = new HashSet<>();
299                 if (this.deleteExpr != null) {
300                     vars.addAll(Algebra.extractVariables(this.deleteExpr, true));
301                 }
302                 if (this.insertExpr != null) {
303                     vars.addAll(Algebra.extractVariables(this.insertExpr, true));
304                 }
305                 vars.retainAll(Algebra.extractVariables(this.whereExpr, true));
306                 this.commonVariables = Ordering.natural().immutableSortedCopy(vars);
307             }
308         }
309         return this.commonVariables;
310     }
311 
312     /**
313      * Returns true if the rule is safe, i.e., if all the variables referenced in the DELETE and
314      * INSERT expressions are present in the bindings produced by the WHERE expression. Only safe
315      * rules can be evaluated. Non-safe rules are however allowed as they can be transformed into
316      * safe rules through variable binding (by calling method
317      * {@link #rewriteVariables(BindingSet)}).
318      *
319      * @return true, if the rule is safe
320      */
321     public boolean isSafe() {
322         if (this.safe == 0) {
323             if (this.deleteExpr == null && this.insertExpr == null) {
324                 this.safe = 1;
325             } else {
326                 final Set<String> vars = new HashSet<>();
327                 if (this.deleteExpr != null) {
328                     vars.addAll(Algebra.extractVariables(this.deleteExpr, true));
329                 }
330                 if (this.insertExpr != null) {
331                     vars.addAll(Algebra.extractVariables(this.insertExpr, true));
332                 }
333                 if (this.whereExpr != null) {
334                     vars.removeAll(Algebra.extractVariables(this.whereExpr, true));
335                 }
336                 this.safe = (byte) (vars.isEmpty() ? 1 : -1);
337             }
338         }
339         return this.safe == 1;
340     }
341 
342     /**
343      * Returns true if the rule is simple, i.e., if the WHERE expression consists only of BGPs,
344      * FILTERs (without the EXISTS construct) and outer level BINDs. Simple rules can be evaluated
345      * more efficiently.
346      *
347      * @return true, if the rule is simple
348      */
349     public boolean isSimple() {
350         if (this.simple == 0) {
351             final AtomicBoolean simple = new AtomicBoolean(true);
352             if (this.whereExpr != null) {
353                 this.whereExpr.visit(new QueryModelVisitorBase<RuntimeException>() {
354 
355                     @Override
356                     protected void meetNode(final QueryModelNode node) throws RuntimeException {
357                         if (!simple.get()) {
358                             return;
359                         } else if (node instanceof StatementPattern || node instanceof Join
360                                 || node instanceof Filter || node instanceof ValueExpr
361                                 && !(node instanceof Exists) || node instanceof ExtensionElem) {
362                             super.meetNode(node);
363                         } else if (node instanceof Extension) {
364                             for (QueryModelNode n = node.getParentNode(); n != null; n = n
365                                     .getParentNode()) {
366                                 if (!(n instanceof Extension)) {
367                                     simple.set(false);
368                                     return;
369                                 }
370                             }
371                             super.meetNode(node);
372                         } else {
373                             simple.set(false);
374                             return;
375                         }
376                     }
377 
378                 });
379             }
380             this.simple = (byte) (simple.get() ? 1 : -1);
381         }
382         return this.simple == 1;
383     }
384 
385     /**
386      * Returns true if the rule can be evaluated in a streaming way. A rule is streamable if: (i)
387      * it is simple (see {@link #isSimple()}); (ii) its where part contains at most one statement
388      * pattern; and (iii) the delete part is missing or it contains exactly the statement pattern
389      * of the where part (which must be non empty).
390      *
391      * @return true, if the rule is streamable
392      */
393     public boolean isStreamable() {
394         if (!isSimple()) {
395             return false;
396         }
397         if (this.streamable == 0) {
398             boolean streamable = false;
399             final Set<StatementPattern> wherePatterns = getWherePatterns();
400             if (wherePatterns.size() <= 1) {
401                 if (this.deleteExpr == null) {
402                     streamable = true;
403                 } else if (wherePatterns.size() == 1) {
404                     final List<StatementPattern> deletePatterns = Algebra.extractNodes(
405                             this.deleteExpr, StatementPattern.class, null, null);
406                     if (deletePatterns.size() == 1 && wherePatterns.containsAll(deletePatterns)) {
407                         streamable = true;
408                     }
409                 }
410             }
411             this.streamable = (byte) (streamable ? 1 : -1);
412         }
413         return this.streamable == 1;
414     }
415 
416     /**
417      * Returns true if the rule matches only specific types of statements. A rule is specific if
418      * its where part is null or it does not contain a statement pattern that could match any
419      * statement. Specific rules might be evaluated only on a subset of statements (the ones that
420      * could be matched) obtaining the same results.
421      *
422      * @return true, if the rule is specific
423      */
424     public boolean isSpecific() {
425         if (this.specific == 0) {
426             boolean specific = true;
427             for (final StatementPattern pattern : getWherePatterns()) {
428                 if (!pattern.getSubjectVar().hasValue()
429                         && !pattern.getPredicateVar().hasValue()
430                         && !pattern.getObjectVar().hasValue()
431                         && (pattern.getContextVar() == null || !pattern.getContextVar().hasValue())) {
432                     specific = false;
433                     break;
434                 }
435             }
436             this.specific = (byte) (specific ? 1 : -1);
437         }
438         return this.specific == 1;
439     }
440 
441     /**
442      * Returns true if the rule may be activated given the dataset statistics supplied. Note that
443      * false positive answers may be returned, i.e, if the result is true it is not guaranteed
444      * that the rule will fire, whereas if the result is false the rule is guaranteed not to fire
445      * (under the assumption that statistics returned by {@code statisitcs} are 0.0 only if no
446      * triple is returned for a certain statement pattern).
447      *
448      * @param statistics
449      *            the statistics object
450      * @return true, if the rule might fire given the supplied statistics
451      */
452     public boolean mightActivate(final EvaluationStatistics statistics) {
453         if (isSimple() && !getWherePatterns().isEmpty()) {
454             for (final StatementPattern pattern : getWherePatterns()) {
455                 if (statistics.getCardinality(pattern) == 0.0) {
456                     return false;
457                 }
458             }
459         }
460         return true;
461     }
462 
463     /**
464      * Rewrites the rule according to the GLOBAL graph inference mode, using the global graph URI
465      * specified. The returned rule: (i) has a new ID generated based on the ID of this rule; (ii)
466      * matches quads in any graph in the WHERE part; (iii) insert quads in the specified global
467      * graph; and (iv) deletes quads from any graph.
468      *
469      * @param globalGraph
470      *            the URI of the global graph where to insert new quads; if null, quads will be
471      *            inserted in the default graph {@code sesame:nil}
472      * @return the rewritten rule
473      */
474     public Rule rewriteGlobalGM(@Nullable final URI globalGraph) {
475         final Var graphVar = globalGraph != null ? newConstVar(globalGraph) : null;
476         final TupleExpr newDeleteExpr = Algebra.rewriteGraph(this.deleteExpr, null);
477         final TupleExpr newInsertExpr = Algebra.rewriteGraph(this.insertExpr, graphVar);
478         final TupleExpr newWhereExpr = Algebra.rewriteGraph(this.whereExpr, null);
479         return new Rule(newID(this.id.stringValue()), this.fixpoint, this.phase, newDeleteExpr,
480                 newInsertExpr, newWhereExpr);
481     }
482 
483     /**
484      * Rewrites the rule according to the SEPARATE graph inference mode. The returned rule: (i)
485      * has a new ID generated based on the ID of this rule; and (ii) operates on a per-graph
486      * basis, i.e., for each graph, the WHERE clause is applied and its results are used to
487      * evaluate the DELETE and INSERT clauses on the very same graph.
488      *
489      * @return the rewritten rule
490      */
491     public Rule rewriteSeparateGM() {
492 
493         // Extract all the variables used in the rule
494         final Set<String> vars = new HashSet<String>();
495         vars.addAll(Algebra.extractVariables(this.deleteExpr, false));
496         vars.addAll(Algebra.extractVariables(this.insertExpr, false));
497         vars.addAll(Algebra.extractVariables(this.whereExpr, false));
498 
499         // Select a fresh graph variable
500         String graphVarName = "g";
501         int index = 0;
502         while (vars.contains(graphVarName)) {
503             graphVarName = "g" + index++;
504         }
505         final Var graphVar = new Var(graphVarName);
506 
507         // Generate the where expr if missing
508         TupleExpr whereExpr = this.whereExpr;
509         if (whereExpr == null) {
510             whereExpr = new StatementPattern(new Var("s"), new Var("p"), new Var("o"),
511                     graphVar.clone());
512         }
513 
514         // Rewrite the rule
515         final TupleExpr newDeleteExpr = Algebra.rewriteGraph(this.deleteExpr, graphVar);
516         final TupleExpr newInsertExpr = Algebra.rewriteGraph(this.insertExpr, graphVar);
517         final TupleExpr newWhereExpr = Algebra.rewriteGraph(whereExpr, graphVar);
518         return new Rule(newID(this.id.stringValue()), this.fixpoint, this.phase, newDeleteExpr,
519                 newInsertExpr, newWhereExpr);
520     }
521 
522     /**
523      * Rewrites the rule according to the STAR graph inference mode, using the global graph URI
524      * supplied. The returned rule: (i) has a new ID generated based on the ID of this rule; (ii)
525      * operates on a per-graph basis similarly to {@link #rewriteSeparateGM()}, however
526      * 'importing' (as far as matching in the WHERE clause is concerned) also quads in the global
527      * graph; and (iii) in case the WHERE clause is missing or a match is found on quads in the
528      * global graph, deletions and insertions are performed on the global graph itself (this can
529      * be useful to setup the global graph 'before' applying rules on the other graphs)
530      *
531      * @param globalGraph
532      *            the URI of the global graph whose quads are 'imported' in other graphs; if null,
533      *            the default graph {@code sesame:nil} will be used
534      * @return the rewritten rule
535      */
536     public Rule rewriteStarGM(@Nullable final URI globalGraph) {
537 
538         // Extract all the variables used in the rule
539         final Set<String> vars = new HashSet<String>();
540         vars.addAll(Algebra.extractVariables(this.deleteExpr, false));
541         vars.addAll(Algebra.extractVariables(this.insertExpr, false));
542         vars.addAll(Algebra.extractVariables(this.whereExpr, false));
543 
544         // Select a variable prefix never used in the rule
545         String candidatePrefix = "g";
546         outer: while (true) {
547             for (final String var : vars) {
548                 if (var.startsWith(candidatePrefix)) {
549                     candidatePrefix = "_" + candidatePrefix;
550                     continue outer;
551                 }
552             }
553             break;
554         }
555         final String prefix = candidatePrefix;
556 
557         // Rewrite the rule
558         final URI global = globalGraph != null ? globalGraph : SESAME.NIL;
559         TupleExpr newDeleteExpr = this.deleteExpr;
560         TupleExpr newInsertExpr = this.insertExpr;
561         TupleExpr newWhereExpr = this.whereExpr;
562         if (this.whereExpr == null) {
563             newDeleteExpr = Algebra.rewriteGraph(newDeleteExpr, newConstVar(global));
564             newInsertExpr = Algebra.rewriteGraph(newInsertExpr, newConstVar(global));
565         } else {
566             final AtomicInteger counter = new AtomicInteger(0);
567             final List<ValueExpr> filterGraphVars = new ArrayList<>();
568             final List<ValueExpr> bindGraphVars = new ArrayList<>();
569             filterGraphVars.add(newConstVar(global));
570             bindGraphVars.add(newConstVar(global));
571             newDeleteExpr = Algebra.rewriteGraph(newDeleteExpr, new Var(prefix));
572             newInsertExpr = Algebra.rewriteGraph(newInsertExpr, new Var(prefix));
573             newWhereExpr = newWhereExpr.clone();
574             newWhereExpr.visit(new QueryModelVisitorBase<RuntimeException>() {
575 
576                 @Override
577                 public void meet(final StatementPattern pattern) throws RuntimeException {
578                     final Var graphVar = new Var(prefix + counter.getAndIncrement());
579                     pattern.setContextVar(graphVar);
580                     filterGraphVars.add(graphVar.clone());
581                     bindGraphVars.add(graphVar.clone());
582                 }
583 
584             });
585             newWhereExpr = new Filter(newWhereExpr, new Compare(new FunctionCall(
586                     RR.STAR_SELECT_GRAPH.stringValue(), filterGraphVars), new Var("_const-"
587                     + UUID.randomUUID(), RDF.NIL), CompareOp.NE));
588             newWhereExpr = new Extension(newWhereExpr, new ExtensionElem(new FunctionCall(
589                     RR.STAR_SELECT_GRAPH.stringValue(), bindGraphVars), prefix));
590         }
591         return new Rule(newID(this.id.stringValue()), this.fixpoint, this.phase, newDeleteExpr,
592                 newInsertExpr, newWhereExpr);
593     }
594 
595     /**
596      * Rewrites the rule by replacing selected variables with constant values as dictated by the
597      * supplied bindings. In case the rewriting is unnecessary this rule is returned unchanged;
598      * otherwise, a new, rewritten rule with a different ID (based on the ID of this rule) is
599      * produced.
600      *
601      * @param bindings
602      *            the variable = value bindings to use for the rewriting; if null or empty, no
603      *            rewriting will take place
604      * @return either the rewritten rule of this rule, if rewriting is unnecessary
605      */
606     public Rule rewriteVariables(@Nullable final BindingSet bindings) {
607         if (bindings == null || bindings.size() == 0) {
608             return this;
609         }
610         final TupleExpr newDeleteExpr = Algebra.rewrite(this.deleteExpr, bindings);
611         final TupleExpr newInsertExpr = Algebra.rewrite(this.insertExpr, bindings);
612         final TupleExpr newWhereExpr = Algebra.rewrite(this.whereExpr, bindings);
613         return new Rule(newID(this.id.stringValue()), this.fixpoint, this.phase, newDeleteExpr,
614                 newInsertExpr, newWhereExpr);
615     }
616 
617     /**
618      * Merges rules with the same WHERE expression, priority and fixpoint flag. A merged rule,
619      * with a fresh ID, is produced for each cluster of rules having the same values of these
620      * attributes. The DELETE and INSERT expressions of the merged rule are obtained by
621      * concatenating the DELETE and INSERT expressions of the rules in the cluster.
622      *
623      * @param rules
624      *            the rules to merge
625      * @return a list with the merged rules
626      */
627     public static List<Rule> mergeSameWhereExpr(final Iterable<Rule> rules) {
628 
629         // Group together rules with the same fixpoint, phase and WHERE expression
630         final Map<List<Object>, List<Rule>> clusters = new HashMap<>();
631         for (final Rule rule : rules) {
632             final List<Object> key = Arrays.asList(rule.fixpoint, rule.phase, rule.whereExpr);
633             List<Rule> cluster = clusters.get(key);
634             if (cluster == null) {
635                 cluster = new ArrayList<>();
636                 clusters.put(key, cluster);
637             }
638             cluster.add(rule);
639         }
640 
641         // Create a merged rule for each cluster obtained before
642         final List<Rule> mergedRules = new ArrayList<>();
643         for (final List<Rule> cluster : clusters.values()) {
644             final Rule first = cluster.get(0);
645             final String namespace = first.getID().getNamespace();
646             final Set<String> names = new TreeSet<>();
647             TupleExpr newDeleteExpr = null;
648             TupleExpr newInsertExpr = null;
649             for (int i = 0; i < cluster.size(); ++i) {
650                 final Rule rule = cluster.get(i);
651                 final String s = rule.getID().getLocalName();
652                 final int index = s.indexOf("__");
653                 names.add(index < 0 ? s : s.substring(0, index));
654                 newDeleteExpr = newDeleteExpr == null ? rule.deleteExpr //
655                         : new Join(newDeleteExpr, rule.deleteExpr);
656                 newInsertExpr = newInsertExpr == null ? rule.insertExpr //
657                         : new Join(newInsertExpr, rule.insertExpr);
658             }
659             final URI id = newID(namespace + String.join("_", names));
660             mergedRules.add(new Rule(id, first.fixpoint, first.phase, newDeleteExpr,
661                     newInsertExpr, first.whereExpr));
662         }
663         return mergedRules;
664     }
665 
666     public void evaluate(final QuadModel model, @Nullable final QuadModel deltaModel,
667             @Nullable final StatementPattern deltaPattern,
668             @Nullable final Supplier<RDFHandler> deleteSink,
669             @Nullable final Supplier<RDFHandler> insertSink) {
670 
671         new Evaluation(this, model, deltaModel, deltaPattern, deleteSink, insertSink).run();
672     }
673 
674     public static int evaluate(final Iterable<Rule> rules, final QuadModel model,
675             @Nullable final QuadModel deltaModel, @Nullable final Supplier<RDFHandler> deleteSink,
676             @Nullable final Supplier<RDFHandler> insertSink) {
677 
678         // Evaluate all rules in parallel, collecting produced quads in the two buffers
679         final List<Evaluation> tasks = new ArrayList<>();
680         for (final Rule rule : rules) {
681             if (deltaModel == null || rule.getWhereExpr() == null) {
682                 final Evaluation task = new Evaluation(rule, model, null, null, deleteSink,
683                         insertSink);
684                 if (task.isActivable()) {
685                     tasks.add(task);
686                 }
687             } else {
688                 for (final StatementPattern pattern : rule.getWherePatterns()) {
689                     final Evaluation task = new Evaluation(rule, model, deltaModel, pattern,
690                             deleteSink, insertSink);
691                     if (task.isActivable()) {
692                         tasks.add(task);
693                     }
694                 }
695             }
696         }
697         if (!tasks.isEmpty()) {
698             Collections.sort(tasks);
699             final Tracker tracker = new Tracker(LOGGER, null, null, "%d/" + tasks.size()
700                     + " rule variants evaluated");
701             for (final Evaluation task : tasks) {
702                 task.setTracker(tracker);
703             }
704             tracker.start();
705             try {
706                 Environment.run(tasks);
707             } finally {
708                 tracker.end();
709             }
710         }
711         return tasks.size();
712     }
713 
714     /**
715      * {@inheritDoc} Rules with the same ID are equal. Otherwise, rules are sorted by phase (lower
716      * phase index comes first), fixpoint flag (false = no fixpoint comes first) and finally ID.
717      * This sorting is compatible with the order of execution of rules.
718      */
719     @Override
720     public int compareTo(final Rule other) {
721         final int idResult = Statements.valueComparator().compare(this.id, other.id);
722         if (idResult == 0) {
723             return 0; // Required for compatibility with equals
724         }
725         int result = this.phase - other.phase;
726         if (result == 0) {
727             result = this.fixpoint ? other.fixpoint ? 0 : 1 : other.fixpoint ? -1 : 0;
728             if (result == 0) {
729                 result = idResult;
730             }
731         }
732         return result;
733     }
734 
735     /**
736      * {@inheritDoc} Two rules are equal if they have the same ID.
737      */
738     @Override
739     public boolean equals(final Object object) {
740         if (object == this) {
741             return true;
742         }
743         if (!(object instanceof Rule)) {
744             return false;
745         }
746         final Rule other = (Rule) object;
747         return this.id.equals(other.id);
748     }
749 
750     /**
751      * {@inheritDoc} The returned hash code depends exclusively on the rule ID.
752      */
753     @Override
754     public int hashCode() {
755         return this.id.hashCode();
756     }
757 
758     /**
759      * {@inheritDoc} The returned string has the form
760      * {@code ID (phase: N, fixpoint): DELETE ... INSERT ... WHERE ...}, where the
761      * {@code fixpoint}, {@code DELETE ...}, {@code INSERT ...} and {@code WHERE ...} may be
762      * present or absent based on the properties of the rule.
763      */
764     @Override
765     public String toString() {
766         try {
767             final StringBuilder builder = new StringBuilder();
768             builder.append(this.id instanceof BNode ? ((BNode) this.id).getID() : this.id
769                     .getLocalName());
770             builder.append(" (phase ").append(this.phase)
771                     .append(this.fixpoint ? ", fixpoint):" : "):");
772             if (this.deleteExpr != null) {
773                 builder.append(" DELETE ");
774                 builder.append(Algebra.renderExpr(this.deleteExpr, Namespaces.DEFAULT.prefixMap())
775                         .replaceAll("[\n\r\t ]+", " "));
776             }
777             if (this.insertExpr != null) {
778                 builder.append(" INSERT ");
779                 builder.append(Algebra.renderExpr(this.insertExpr, Namespaces.DEFAULT.prefixMap())
780                         .replaceAll("[\n\r\t ]+", " "));
781             }
782             if (this.whereExpr != null) {
783                 builder.append(" WHERE ");
784                 builder.append(Algebra.renderExpr(this.whereExpr, Namespaces.DEFAULT.prefixMap())
785                         .replaceAll("[\n\r\t ]+", " "));
786             }
787             return builder.toString();
788         } catch (final Exception ex) {
789             throw new RuntimeException(ex);
790         }
791     }
792 
793     /**
794      * Emits the RDF serialization of the rule. Emitted triples are placed in the default graph.
795      *
796      * @param output
797      *            the collection where to add emitted RDF statements, not null
798      * @return the supplied collection
799      */
800     public <T extends Collection<? super Statement>> T toRDF(final T output) {
801 
802         final ValueFactory vf = Statements.VALUE_FACTORY;
803         output.add(vf.createStatement(this.id, RDF.TYPE, RR.RULE));
804         output.add(vf.createStatement(this.id, RDF.TYPE, this.fixpoint ? RR.FIXPOINT_RULE
805                 : RR.NON_FIXPOINT_RULE));
806         if (this.phase != 0) {
807             output.add(vf.createStatement(this.id, RR.PHASE, vf.createLiteral(this.phase)));
808         }
809         try {
810             if (this.deleteExpr != null) {
811                 output.add(vf.createStatement(this.id, RR.DELETE,
812                         vf.createLiteral(Algebra.renderExpr(this.deleteExpr, null))));
813             }
814             if (this.insertExpr != null) {
815                 output.add(vf.createStatement(this.id, RR.INSERT,
816                         vf.createLiteral(Algebra.renderExpr(this.insertExpr, null))));
817             }
818             if (this.whereExpr != null) {
819                 output.add(vf.createStatement(this.id, RR.WHERE,
820                         vf.createLiteral(Algebra.renderExpr(this.whereExpr, null))));
821             }
822         } catch (final Exception ex) {
823             throw new RuntimeException(ex);
824         }
825         return output;
826     }
827 
828     public static List<Rule> fromDLOG(final Reader reader) throws IOException {
829 
830         return CharStreams.readLines(reader, new LineProcessor<List<Rule>>() {
831 
832             private final Map<String, String> namespaceMap = new HashMap<>();
833 
834             @Nullable
835             private Namespaces namespaces = null;
836 
837             private final List<Rule> rules = new ArrayList<>();
838 
839             private int varCounter = 0;
840 
841             @Override
842             public List<Rule> getResult() {
843                 return this.rules;
844             }
845 
846             @Override
847             public boolean processLine(final String line) throws IOException {
848                 try {
849                     if (line.startsWith("PREFIX ") || line.startsWith("prefix ")) {
850                         this.namespaces = null;
851                         final String[] tokens = line.split("\\s+");
852                         final String prefix = tokens[1].substring(0, tokens[1].length() - 1);
853                         final String namespace = ((URI) Statements.parseValue(tokens[2]))
854                                 .toString();
855                         this.namespaceMap.put(prefix, namespace);
856                     } else {
857                         final int index = line.indexOf(":-");
858                         if (index >= 0) {
859                             this.namespaces = this.namespaces != null ? this.namespaces
860                                     : Namespaces.forURIMap(this.namespaceMap);
861                             final TupleExpr head = processAtoms(line.substring(0, index));
862                             final TupleExpr body = processAtoms(line.substring(index + 2));
863                             this.rules.add(new Rule(Statements.VALUE_FACTORY.createURI("rule:"
864                                     + DLOG_RULE_COUNTER.incrementAndGet()), true, 0, null, head,
865                                     body));
866                         }
867                     }
868                     return true;
869                 } catch (final Throwable ex) {
870                     throw new IllegalArgumentException("Could not parse line: " + line, ex);
871                 }
872             }
873 
874             private TupleExpr processAtoms(final String string) {
875                 TupleExpr expr = null;
876                 for (String atomToken : string.split("\\)\\s*[,.]?")) {
877                     atomToken = atomToken.trim();
878                     final int index1 = atomToken.indexOf('(');
879                     final Var rel = constant(atomToken.substring(0, index1).trim());
880                     final List<Var> vars = new ArrayList<>();
881                     for (String termToken : atomToken.substring(index1 + 1).split("\\s*\\,\\s*")) {
882                         termToken = termToken.trim();
883                         if (termToken.startsWith("?")) {
884                             vars.add(new Var(termToken.substring(1)));
885                         } else {
886                             vars.add(constant(termToken));
887                         }
888                     }
889                     final StatementPattern pattern = vars.size() == 1 ? new StatementPattern(vars
890                             .get(0), constant(RDF.TYPE), rel) : new StatementPattern(vars.get(0),
891                             rel, vars.get(1));
892                     expr = expr == null ? pattern : new Join(expr, pattern);
893                 }
894                 return expr;
895             }
896 
897             private Var constant(final String string) {
898                 if ("<int$false>".equals(string)) {
899                     return constant(Statements.VALUE_FACTORY.createURI("sesame:false"));
900                 }
901                 return constant(Statements.parseValue(string, this.namespaces));
902             }
903 
904             private Var constant(final Value value) {
905                 return new Var("__v" + (++this.varCounter), value);
906             }
907 
908         });
909     }
910 
911     /**
912      * Parses all the rules contained in the supplied RDF statements.
913      *
914      * @param model
915      *            the RDF statements, not null
916      * @return an unsorted list containing the parsed rules
917      */
918     public static List<Rule> fromRDF(final Iterable<Statement> model) {
919 
920         // Load namespaces from model metadata, reusing default prefix/ns mappings
921         final Map<String, String> namespaces = new HashMap<>(Namespaces.DEFAULT.uriMap());
922         if (model instanceof Model) {
923             for (final Namespace namespace : ((Model) model).getNamespaces()) {
924                 namespaces.put(namespace.getPrefix(), namespace.getName());
925             }
926         }
927         for (final Statement stmt : model) {
928             if (stmt.getSubject() instanceof URI && stmt.getObject() instanceof Literal
929                     && stmt.getPredicate().equals(RR.PREFIX_PROPERTY)) {
930                 namespaces.put(stmt.getObject().stringValue(), stmt.getSubject().stringValue());
931             }
932         }
933 
934         // Use a 5-fields Object[] record to collect the attributes of each rule.
935         // fields: 0 = fixpoint, 1 = phase, 2 = delete expr, 3 = insert expr, 4 = where expr
936         final Map<URI, Object[]> records = new HashMap<>();
937 
938         // Scan the statements, extracting rule properties and populating the records map
939         for (final Statement stmt : model) {
940             try {
941                 if (stmt.getSubject() instanceof URI) {
942 
943                     // Extract relevant statement components
944                     final URI subj = (URI) stmt.getSubject();
945                     final URI pred = stmt.getPredicate();
946                     final Value obj = stmt.getObject();
947 
948                     // Identify field and value (if any) of corresponding Object[] record
949                     int field = -1;
950                     Object value = null;
951                     if (pred.equals(RDF.TYPE)) {
952                         field = 0;
953                         if (obj.equals(RR.FIXPOINT_RULE)) {
954                             value = true;
955                         } else if (obj.equals(RR.NON_FIXPOINT_RULE)) {
956                             value = false;
957                         }
958                     } else if (pred.equals(RR.PHASE)) {
959                         field = 1;
960                         value = ((Literal) obj).intValue();
961                     } else if (pred.equals(RR.DELETE)) {
962                         field = 2;
963                     } else if (pred.equals(RR.INSERT) || pred.equals(RR.HEAD)) {
964                         field = 3;
965                     } else if (pred.equals(RR.WHERE) || pred.equals(RR.BODY)) {
966                         field = 4;
967                     }
968                     if (field == 2 || field == 3 || field == 4) {
969                         value = Algebra.parseTupleExpr(stmt.getObject().stringValue(), null,
970                                 namespaces);
971                     }
972 
973                     // Update Object[] records if the statement is about a rule
974                     if (value != null) {
975                         Object[] record = records.get(subj);
976                         if (record == null) {
977                             record = new Object[] { true, 0, null, null, null };
978                             records.put(subj, record);
979                         }
980                         record[field] = value;
981                     }
982                 }
983             } catch (final Throwable ex) {
984                 throw new IllegalArgumentException("Invalid rule attribute in statement: " + stmt,
985                         ex);
986             }
987         }
988 
989         // Generate the rules from parsed heads and bodies
990         final List<Rule> rules = new ArrayList<>();
991         for (final Map.Entry<URI, Object[]> entry : records.entrySet()) {
992             final URI id = entry.getKey();
993             final Object[] record = entry.getValue();
994             rules.add(new Rule(id, (Boolean) record[0], (Integer) record[1],
995                     (TupleExpr) record[2], (TupleExpr) record[3], (TupleExpr) record[4]));
996         }
997         return rules;
998     }
999 
1000     static URI newID(final String baseID) {
1001         final int index = baseID.indexOf("__");
1002         final String base = index < 0 ? baseID : baseID.substring(0, index);
1003         return Statements.VALUE_FACTORY.createURI(base + "__" + ID_COUNTER.incrementAndGet());
1004     }
1005 
1006     static Var newConstVar(final Value value) {
1007         return new Var("_const-" + UUID.randomUUID(), value);
1008     }
1009 
1010     Collector getCollector() {
1011         if (this.collector == null) {
1012             this.collector = Collector.create(this);
1013         }
1014         return this.collector;
1015     }
1016 
1017     private static final class Evaluation implements Runnable, Comparable<Evaluation> {
1018 
1019         private final Rule rule;
1020 
1021         private final QuadModel model;
1022 
1023         @Nullable
1024         private final QuadModel deltaModel;
1025 
1026         @Nullable
1027         private final StatementPattern deltaPattern;
1028 
1029         @Nullable
1030         private final Supplier<RDFHandler> deleteSink;
1031 
1032         @Nullable
1033         private final Supplier<RDFHandler> insertSink;
1034 
1035         @Nullable
1036         private Tracker tracker;
1037 
1038         private final EvaluationStatistics statistics;
1039 
1040         private final double cardinality;
1041 
1042         Evaluation(final Rule rule, final QuadModel model, @Nullable final QuadModel deltaModel,
1043                 @Nullable final StatementPattern deltaPattern,
1044                 @Nullable final Supplier<RDFHandler> deleteSink,
1045                 @Nullable final Supplier<RDFHandler> insertSink) {
1046 
1047             this.rule = rule;
1048             this.deleteSink = deleteSink;
1049             this.insertSink = insertSink;
1050             this.model = model;
1051             this.deltaModel = deltaModel;
1052             this.deltaPattern = deltaPattern;
1053             this.statistics = deltaModel == null ? model.getEvaluationStatistics()
1054                     : newSemiNaiveEvaluationStatistics();
1055             this.cardinality = rule.whereExpr == null ? 1.0 : this.statistics
1056                     .getCardinality(rule.whereExpr);
1057         }
1058 
1059         boolean isActivable() {
1060             return this.cardinality != 0.0;
1061         }
1062 
1063         void setTracker(@Nullable final Tracker tracker) {
1064             this.tracker = tracker;
1065         }
1066 
1067         @Override
1068         public int compareTo(final Evaluation other) {
1069             return -Double.compare(this.cardinality, other.cardinality);
1070         }
1071 
1072         @Override
1073         public void run() {
1074 
1075             // Retrieve current thread
1076             final Thread thread = Thread.currentThread();
1077             final String threadName = thread.getName();
1078 
1079             try {
1080                 // Update thread name (for diagnostic purposes)
1081                 thread.setName(thread.getName() + " [" + this.rule.toString() + "]");
1082 
1083                 // Take a timestamp to measure rule evaluation time
1084                 final long ts = System.currentTimeMillis();
1085 
1086                 // Define counter for # activations
1087                 int numActivations = 0;
1088 
1089                 // Start evaluating the rule
1090                 Iterator<BindingSet> iterator;
1091                 if (this.cardinality == 0.0) {
1092                     iterator = Collections.emptyIterator();
1093                 } else if (this.rule.getWhereExpr() == null) {
1094                     iterator = Collections.singleton(EmptyBindingSet.getInstance()).iterator();
1095                 } else if (this.deltaModel == null) {
1096                     iterator = this.model.evaluate(this.rule.getWhereExpr(), null, null);
1097                 } else {
1098                     iterator = Algebra.evaluateTupleExpr(this.rule.getWhereExpr(), null, null,
1099                             newSemiNaiveEvaluationStrategy(), this.statistics,
1100                             this.model.getValueNormalizer());
1101                 }
1102 
1103                 try {
1104                     // Proceed only if there is some query result to process
1105                     if (iterator.hasNext()) {
1106 
1107                         // Acquire a collector, normalizing its constants so to use the same Value
1108                         // objects in the model
1109                         final Collector collector = this.rule.getCollector().normalize(
1110                                 this.model.getValueNormalizer());
1111 
1112                         // Allocate the delete handler, if possible
1113                         RDFHandler deleteHandler = null;
1114                         if (this.deleteSink != null && this.rule.getDeleteExpr() != null) {
1115                             deleteHandler = this.deleteSink.get();
1116                             deleteHandler.startRDF();
1117                         }
1118 
1119                         // Allocate the insert handler, if possible
1120                         RDFHandler insertHandler = null;
1121                         if (this.insertSink != null && this.rule.getInsertExpr() != null) {
1122                             insertHandler = this.insertSink.get();
1123                             insertHandler.startRDF();
1124                         }
1125 
1126                         // Scan the bindings returned by the WHERE part, using the collector to
1127                         // compute deleted/inserted quads
1128                         while (iterator.hasNext()) {
1129                             ++numActivations;
1130                             final BindingSet bindings = iterator.next();
1131                             collector.collect(bindings, this.model, deleteHandler, insertHandler);
1132                         }
1133 
1134                         // Signal completion to the delete handler, if any
1135                         if (deleteHandler != null) {
1136                             deleteHandler.endRDF();
1137                         }
1138 
1139                         // Signal completion to the insert handler, if any
1140                         if (insertHandler != null) {
1141                             insertHandler.endRDF();
1142                         }
1143                     }
1144                 } catch (final RDFHandlerException ex) {
1145                     // Wrap and propagate
1146                     throw new RuntimeException(ex);
1147 
1148                 } finally {
1149                     // Ensure to close the iterator (if it needs to be closed)
1150                     IO.closeQuietly(iterator);
1151 
1152                 }
1153 
1154                 // Log relevant rule evaluation statistics
1155                 if (LOGGER.isTraceEnabled()) {
1156                     final String patternString = this.deltaPattern == null ? ""
1157                             : " (delta pattern " + Algebra.format(this.deltaPattern) + ")";
1158                     LOGGER.trace("Rule {}{} evaluated in {} ms with {} activations", this.rule
1159                             .getID().getLocalName(), patternString, System.currentTimeMillis()
1160                             - ts, numActivations);
1161                 }
1162 
1163             } finally {
1164                 // Restore original thread name
1165                 thread.setName(threadName);
1166                 if (this.tracker != null) {
1167                     this.tracker.increment();
1168                 }
1169             }
1170         }
1171 
1172         private EvaluationStrategy newSemiNaiveEvaluationStrategy() {
1173 
1174             final AtomicReference<TripleSource> selectedSource = new AtomicReference<>();
1175 
1176             final TripleSource baseSource = this.model.getTripleSource();
1177             final TripleSource deltaSource = this.deltaModel.getTripleSource();
1178             final TripleSource semiNaiveSource = new TripleSource() {
1179 
1180                 @Override
1181                 public CloseableIteration<? extends Statement, QueryEvaluationException> getStatements(
1182                         final Resource subj, final URI pred, final Value obj,
1183                         final Resource... contexts) throws QueryEvaluationException {
1184                     return selectedSource.get().getStatements(subj, pred, obj, contexts);
1185                 }
1186 
1187                 @Override
1188                 public ValueFactory getValueFactory() {
1189                     return baseSource.getValueFactory();
1190                 }
1191 
1192             };
1193 
1194             return new EvaluationStrategyImpl(semiNaiveSource, null,
1195                     Algebra.getFederatedServiceResolver()) {
1196 
1197                 @Nullable
1198                 private StatementPattern normalizedDeltaPattern = null;
1199 
1200                 @Override
1201                 public CloseableIteration<BindingSet, QueryEvaluationException> evaluate(
1202                         final StatementPattern pattern, final BindingSet bindings)
1203                         throws QueryEvaluationException {
1204 
1205                     if (this.normalizedDeltaPattern == null) {
1206                         if (pattern.equals(Evaluation.this.deltaPattern)) {
1207                             this.normalizedDeltaPattern = pattern;
1208                         }
1209                     }
1210                     if (this.normalizedDeltaPattern == pattern) {
1211                         selectedSource.set(deltaSource);
1212                     } else {
1213                         selectedSource.set(baseSource);
1214                     }
1215                     return super.evaluate(pattern, bindings);
1216                 }
1217 
1218             };
1219         }
1220 
1221         private EvaluationStatistics newSemiNaiveEvaluationStatistics() {
1222 
1223             return new EvaluationStatistics() {
1224 
1225                 @Override
1226                 protected CardinalityCalculator createCardinalityCalculator() {
1227                     return new CardinalityCalculator() {
1228 
1229                         @Override
1230                         public final double getCardinality(final StatementPattern pattern) {
1231                             if (pattern.equals(Evaluation.this.deltaPattern)) {
1232                                 return Evaluation.this.deltaModel.getEvaluationStatistics()
1233                                         .getCardinality(pattern);
1234                             } else {
1235                                 return Evaluation.this.model.getEvaluationStatistics()
1236                                         .getCardinality(pattern);
1237                             }
1238                         }
1239 
1240                     };
1241                 }
1242 
1243             };
1244         }
1245 
1246     }
1247 
1248     private static final class Collector {
1249 
1250         private static final int[] EMPTY_INDEXES = new int[0];
1251 
1252         private static final String[] EMPTY_VARS = new String[0];
1253 
1254         private static final Value[] EMPTY_CONSTANTS = new Value[0];
1255 
1256         private transient final int[] deleteIndexes;
1257 
1258         private transient final int[] insertIndexes;
1259 
1260         private transient final String[] commonVars;
1261 
1262         private transient final Value[] constants;
1263 
1264         static Collector create(final Rule rule) {
1265 
1266             // Retrieve the list of variables common to the WHERE and DELETE/INSERT expressions
1267             final List<String> commonVars = rule.getCommonVariables();
1268             final String[] commonVarsArray = commonVars.isEmpty() ? EMPTY_VARS : commonVars
1269                     .toArray(new String[commonVars.size()]);
1270 
1271             // Compute the mappings (indexes+constants) required for translating bindings to quads
1272             final List<Value> constants = new ArrayList<>();
1273             final int[] deleteIndexes = createHelper(rule.getDeleteExpr(), commonVars, constants);
1274             final int[] insertIndexes = createHelper(rule.getInsertExpr(), commonVars, constants);
1275             final Value[] constantsArray = constants.isEmpty() ? EMPTY_CONSTANTS : constants
1276                     .toArray(new Value[constants.size()]);
1277 
1278             // Log results
1279             if (LOGGER.isTraceEnabled()) {
1280                 final StringBuilder builder = new StringBuilder();
1281                 for (final Value constant : constants) {
1282                     builder.append(builder.length() == 0 ? "[" : ", ");
1283                     builder.append(Statements.formatValue(constant, Namespaces.DEFAULT));
1284                 }
1285                 builder.append("]");
1286                 LOGGER.trace("Collector for rule {}: vars={}, constants={}, delete indexes={}, "
1287                         + "insert indexes={}", rule.getID().getLocalName(), commonVars, builder,
1288                         deleteIndexes, insertIndexes);
1289             }
1290 
1291             // Instantiate a collector with the data structures computed above
1292             return new Collector(deleteIndexes, insertIndexes, commonVarsArray, constantsArray);
1293         }
1294 
1295         private static int[] createHelper(@Nullable final TupleExpr expr,
1296                 final List<String> commonVars, final List<Value> constants) {
1297 
1298             // Return an empty index array if there is no expression (-> no mapping necessary)
1299             if (expr == null) {
1300                 return EMPTY_INDEXES;
1301             }
1302 
1303             // Otherwise, extracts all the statement patterns in the expression
1304             final List<StatementPattern> patterns = Algebra.extractNodes(expr,
1305                     StatementPattern.class, null, null);
1306 
1307             // Build an index array with 4 slots for each pattern. Each slot contains either: the
1308             // index (i + 1) of the variable in commonVars correspon+ding to that quad component,
1309             // or the index -(i+1) of the constant in 'constants' corresponding to that component,
1310             // or 0 to denote the default context constant (sesame:nil)
1311             final int[] indexes = new int[4 * patterns.size()];
1312             for (int i = 0; i < patterns.size(); ++i) {
1313                 final List<Var> patternVars = patterns.get(i).getVarList();
1314                 for (int j = 0; j < patternVars.size(); ++j) {
1315                     final Var var = patternVars.get(j);
1316                     if (var.getValue() != null) {
1317                         int index = constants.indexOf(var.getValue());
1318                         if (index < 0) {
1319                             index = constants.size();
1320                             constants.add(var.getValue());
1321                         }
1322                         indexes[i * 4 + j] = -index - 1;
1323                     } else {
1324                         final int index = commonVars.indexOf(var.getName());
1325                         if (index < 0) {
1326                             throw new Error("Var " + var.getName() + " not among common vars "
1327                                     + commonVars);
1328                         }
1329                         indexes[i * 4 + j] = index + 1;
1330                     }
1331                 }
1332             }
1333             return indexes;
1334         }
1335 
1336         private Collector(final int[] deleteIndexes, final int[] insertIndexes,
1337                 final String[] commonVars, final Value[] constants) {
1338 
1339             // Store all the supplied parameters
1340             this.deleteIndexes = deleteIndexes;
1341             this.insertIndexes = insertIndexes;
1342             this.commonVars = commonVars;
1343             this.constants = constants;
1344         }
1345 
1346         private Value resolve(final int index, final Value[] commonValues) {
1347             return index > 0 ? commonValues[index - 1] : index == 0 ? null
1348                     : this.constants[-index - 1];
1349         }
1350 
1351         void collect(final BindingSet bindings, @Nullable final QuadModel model,
1352                 @Nullable final RDFHandler deleteHandler, @Nullable final RDFHandler insertHandler) {
1353 
1354             // Transform the var=value bindings map to a value array, using the same variable
1355             // order of commonVars
1356             final Value[] commonValues = new Value[this.commonVars.length];
1357             for (int i = 0; i < commonValues.length; ++i) {
1358                 commonValues[i] = bindings.getValue(this.commonVars[i]);
1359             }
1360 
1361             try {
1362                 // Generate and send to the delete handler the quads that need to be removed. In
1363                 // case
1364                 // of quads in the default context, we need to explode them including all the
1365                 // quads
1366                 // with same SPO and different context (due to SESAME semantics 'default context =
1367                 // merge of all other contexts').
1368                 if (deleteHandler != null) {
1369                     for (int i = 0; i < this.deleteIndexes.length; i += 4) {
1370                         final Value subj = resolve(this.deleteIndexes[i], commonValues);
1371                         final Value pred = resolve(this.deleteIndexes[i + 1], commonValues);
1372                         final Value obj = resolve(this.deleteIndexes[i + 2], commonValues);
1373                         final Value ctx = resolve(this.deleteIndexes[i + 3], commonValues);
1374                         if (subj instanceof Resource && pred instanceof URI
1375                                 && obj instanceof Value) {
1376                             if (ctx instanceof Resource || model == null) {
1377                                 deleteHandler.handleStatement(new ContextStatementImpl(
1378                                         (Resource) subj, (URI) pred, obj, (Resource) ctx));
1379                             } else if (ctx == null) {
1380                                 for (final Statement stmt : model.filter((Resource) subj,
1381                                         (URI) pred, obj)) {
1382                                     deleteHandler.handleStatement(new ContextStatementImpl(
1383                                             (Resource) subj, (URI) pred, obj, stmt.getContext()));
1384                                 }
1385                             }
1386                         }
1387                     }
1388                 }
1389 
1390                 // Generate and send to the insert handler the quads that need to be inserted
1391                 if (insertHandler != null) {
1392                     for (int i = 0; i < this.insertIndexes.length; i += 4) {
1393                         final Value subj = resolve(this.insertIndexes[i], commonValues);
1394                         final Value pred = resolve(this.insertIndexes[i + 1], commonValues);
1395                         final Value obj = resolve(this.insertIndexes[i + 2], commonValues);
1396                         final Value ctx = resolve(this.insertIndexes[i + 3], commonValues);
1397                         if (subj instanceof Resource && pred instanceof URI
1398                                 && obj instanceof Value
1399                                 && (ctx == null || ctx instanceof Resource)) {
1400                             insertHandler.handleStatement(new ContextStatementImpl(
1401                                     (Resource) subj, (URI) pred, obj, (Resource) ctx));
1402                         }
1403                     }
1404                 }
1405 
1406             } catch (final RDFHandlerException ex) {
1407                 // Wrap and propagate
1408                 throw new RuntimeException(ex);
1409             }
1410         }
1411 
1412         Collector normalize(final Function<Value, Value> normalizer) {
1413 
1414             // Replace each Value constant in the constants array with the corresponding Value
1415             // instance already stored in the quad model, if any. This may enable using identity
1416             // comparison of values instead of string comparison (faster!)
1417             int numReplacements = 0;
1418             final Value[] normalizedConstants = new Value[this.constants.length];
1419             for (int i = 0; i < this.constants.length; ++i) {
1420                 normalizedConstants[i] = normalizer.apply(this.constants[i]);
1421                 numReplacements += normalizedConstants[i] == this.constants[i] ? 0 : 1;
1422             }
1423             LOGGER.trace("{} constant values replaced during collector normalization",
1424                     numReplacements);
1425 
1426             // Return the collector with the same parameters except the normalized constant array
1427             return new Collector(this.deleteIndexes, this.insertIndexes, this.commonVars,
1428                     normalizedConstants);
1429         }
1430 
1431     }
1432 
1433 }