Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[6814] branches/BIGDATA_RELEASE_1_2_0
|
From: <mrp...@us...> - 2013-01-22 18:28:03
|
Revision: 6814
http://bigdata.svn.sourceforge.net/bigdata/?rev=6814&view=rev
Author: mrpersonick
Date: 2013-01-22 18:27:52 +0000 (Tue, 22 Jan 2013)
Log Message:
-----------
SPARQL 1.1 property paths
Modified Paths:
--------------
branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/BOpUtility.java
branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/Var.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysis.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysisBase.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/VarNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpUtility.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTJoinOrderByTypeOptimizer.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTWildcardProjectionOptimizer.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/DefaultOptimizerList.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/java/com/bigdata/rdf/sail/sparql/GroupGraphPattern.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/java/com/bigdata/rdf/sail/sparql/TriplePatternExprBuilder.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/test/com/bigdata/rdf/sail/tck/BigdataSparqlTest.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/test/org/openrdf/query/parser/sparql/SPARQLASTQueryTest.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/test/org/openrdf/query/parser/sparql/SPARQLQueryTest.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-sails/src/test/org/openrdf/query/parser/sparql/SPARQLUpdateTest.java
Added Paths:
-----------
branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/
branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ArbitraryLengthPathOp.java
branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ZeroLengthPathOp.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PathNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PropertyPathNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PropertyPathUnionNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ZeroLengthPathNode.java
branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTPropertyPathOptimizer.java
Modified: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/BOpUtility.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2013-01-21 13:50:22 UTC (rev 6813)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/BOpUtility.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -1245,7 +1245,7 @@
// copy accepted binding sets to the default sink.
sink.add(tmp);
- nout += chunk.length;
+ nout += tmp.length;
if (sink2 != null) {
Modified: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/Var.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/Var.java 2013-01-21 13:50:22 UTC (rev 6813)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/Var.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -37,6 +37,20 @@
private static final long serialVersionUID = -7100443208125002485L;
+ private boolean anonymous = false;
+
+ public void setAnonymous(boolean anonymous) {
+
+ this.anonymous = anonymous;
+
+ }
+
+ public boolean isAnonymous() {
+
+ return anonymous;
+
+ }
+
final private String name;
final public boolean isVar() {
Added: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ArbitraryLengthPathOp.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ArbitraryLengthPathOp.java (rev 0)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ArbitraryLengthPathOp.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -0,0 +1,896 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2010. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on Aug 18, 2010
+ */
+
+package com.bigdata.bop.paths;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.Callable;
+import java.util.concurrent.FutureTask;
+
+import org.apache.log4j.Logger;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.BOpContext;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstant;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.IVariableOrConstant;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.PipelineOp;
+import com.bigdata.bop.bindingSet.EmptyBindingSet;
+import com.bigdata.bop.engine.AbstractRunningQuery;
+import com.bigdata.bop.engine.IRunningQuery;
+import com.bigdata.bop.engine.QueryEngine;
+import com.bigdata.striterator.ICloseableIterator;
+
+/**
+ * Pipeline join incoming bindings against a special kind of subquery that
+ * represents an arbitrary length path between a single input variable and a
+ * single output variable. Continue this in rounds, using the output of the
+ * previous round as the input of the next round. This has the effect of
+ * producing the transitive closure of the subquery operation.
+ * <p>
+ * The basic idea behind this operator is to run a series of rounds until the
+ * solutions produced by each round reach a fixed point. Regardless of the the
+ * actual schematics of the arbitrary length path (whether there are constants
+ * or variables on the left and right side), we use two transitivity variables
+ * to keep the operator moving. Depending on the schematics of the arbitrary
+ * length path, we can run on forward (left side is input) or reverse (right
+ * side is input). For each intermediate solution, the binding for the
+ * transitivity variable on the output side is re-mapped to input for the next
+ * round.
+ * <p>
+ * This operator does not use internal parallelism, but it is thread-safe and
+ * multiple instances of this operator may be run in parallel by the query
+ * engine for parallel evaluation of different binding set chunks flowing
+ * through the pipeline. However, there are much more efficient query plan
+ * patterns for most use cases. E.g., (a) creating a hash index with all source
+ * solutions, (b) flooding a sub-section of the query plan with the source
+ * solutions from the hash index; and (c) hash joining the solutions from the
+ * sub-section of the query plan back against the hash index to reunite the
+ * solutions from the subquery with those in the parent context.
+ *
+ * @author <a href="mailto:mpe...@us...">Mike Personick</a>
+ */
+public class ArbitraryLengthPathOp extends PipelineOp {
+
+ private static final Logger log = Logger.getLogger(ArbitraryLengthPathOp.class);
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ public interface Annotations extends com.bigdata.bop.PipelineOp.Annotations {
+
+ /**
+ * The subquery representing the path between left and right.
+ */
+ String SUBQUERY = Annotations.class.getName() + ".subquery";
+
+ /**
+ * The left term - can be a variable or a constant.
+ */
+ String LEFT_TERM = Annotations.class.getName() + ".leftTerm";
+
+ /**
+ * The right term - can be a variable or a constant.
+ */
+ String RIGHT_TERM = Annotations.class.getName() + ".rightTerm";
+
+ /**
+ * The left transitivity variable.
+ */
+ String TRANSITIVITY_VAR_LEFT = Annotations.class.getName() + ".transitivityVarLeft";
+
+ /**
+ * The right transitivity variable.
+ */
+ String TRANSITIVITY_VAR_RIGHT = Annotations.class.getName() + ".transitivityVarRight";
+
+ /**
+ * The lower bound on the number of rounds to run. Can be zero (0) or
+ * one (1). A lower bound of zero is a special kind of path - the
+ * Zero Length Path. A zero length path connects a vertex to itself
+ * (in graph parlance). In the context of arbitrary length paths it
+ * means we bind the input onto the output regardless of whether they
+ * are actually connected via the path or not.
+ */
+ String LOWER_BOUND = Annotations.class.getName() + ".lowerBound";
+
+ /**
+ * The upper bound on the number of rounds to run.
+ */
+ String UPPER_BOUND = Annotations.class.getName() + ".upperBound";
+
+ /**
+ * Variables to dop in between rounds. This should be set to the
+ * internal variables produced by the path subquery. Each run of the
+ * subquery should be run "fresh", that is without its produced bindings
+ * already set.
+ */
+ String VARS_TO_DROP = Annotations.class.getName() + ".varsToDrop";
+
+ }
+
+ /**
+ * Deep copy constructor.
+ */
+ public ArbitraryLengthPathOp(final ArbitraryLengthPathOp op) {
+ super(op);
+ }
+
+ /**
+ * Shallow copy constructor.
+ *
+ * @param args
+ * @param annotations
+ */
+ public ArbitraryLengthPathOp(final BOp[] args,
+ final Map<String, Object> annotations) {
+
+ super(args, annotations);
+
+ getRequiredProperty(Annotations.SUBQUERY);
+
+ getRequiredProperty(Annotations.LEFT_TERM);
+
+ getRequiredProperty(Annotations.RIGHT_TERM);
+
+ getRequiredProperty(Annotations.TRANSITIVITY_VAR_LEFT);
+
+ getRequiredProperty(Annotations.TRANSITIVITY_VAR_RIGHT);
+
+ getRequiredProperty(Annotations.LOWER_BOUND);
+
+ getRequiredProperty(Annotations.UPPER_BOUND);
+
+ getRequiredProperty(Annotations.VARS_TO_DROP);
+
+ }
+
+ public ArbitraryLengthPathOp(final BOp[] args, NV... annotations) {
+
+ this(args, NV.asMap(annotations));
+
+ }
+
+ public FutureTask<Void> eval(final BOpContext<IBindingSet> context) {
+
+ return new FutureTask<Void>(new ArbitraryLengthPathTask(this, context));
+
+ }
+
+ private static class ArbitraryLengthPathTask implements Callable<Void> {
+
+ private final BOpContext<IBindingSet> context;
+ private final PipelineOp subquery;
+ private final Gearing forwardGearing, reverseGearing;
+ private final long lowerBound, upperBound;
+ private IVariable<?>[] varsToDrop;
+
+ public ArbitraryLengthPathTask(final ArbitraryLengthPathOp controllerOp,
+ final BOpContext<IBindingSet> context) {
+
+ if (controllerOp == null)
+ throw new IllegalArgumentException();
+
+ if (context == null)
+ throw new IllegalArgumentException();
+
+ this.context = context;
+
+ this.subquery = (PipelineOp) controllerOp
+ .getRequiredProperty(Annotations.SUBQUERY);
+
+ final IVariableOrConstant<?> leftTerm = (IVariableOrConstant<?>) controllerOp
+ .getProperty(Annotations.LEFT_TERM);
+
+ final IVariable<?> leftVar = leftTerm.isVar() ? (IVariable<?>) leftTerm : null;
+
+ final IConstant<?> leftConst = leftTerm.isConstant() ? (IConstant<?>) leftTerm : null;
+
+ final IVariableOrConstant<?> rightTerm = (IVariableOrConstant<?>) controllerOp
+ .getProperty(Annotations.RIGHT_TERM);
+
+ final IVariable<?> rightVar = rightTerm.isVar() ? (IVariable<?>) rightTerm : null;
+
+ final IConstant<?> rightConst = rightTerm.isConstant() ? (IConstant<?>) rightTerm : null;
+
+ final IVariable<?> tVarLeft = (IVariable<?>) controllerOp
+ .getProperty(Annotations.TRANSITIVITY_VAR_LEFT);
+
+ final IVariable<?> tVarRight = (IVariable<?>) controllerOp
+ .getProperty(Annotations.TRANSITIVITY_VAR_RIGHT);
+
+ this.forwardGearing = new Gearing(
+ leftVar, rightVar, leftConst, rightConst, tVarLeft, tVarRight);
+
+ this.reverseGearing = forwardGearing.reverse();
+
+ this.lowerBound = (Long) controllerOp
+ .getProperty(Annotations.LOWER_BOUND);
+
+ this.upperBound = (Long) controllerOp
+ .getProperty(Annotations.UPPER_BOUND);
+
+ this.varsToDrop = (IVariable<?>[]) controllerOp
+ .getProperty(Annotations.VARS_TO_DROP);
+
+ }
+
+ public Void call() throws Exception {
+
+ try {
+
+ final ICloseableIterator<IBindingSet[]> sitr = context
+ .getSource();
+
+ if (!sitr.hasNext()) {
+
+ processChunk(new IBindingSet[0]);
+
+ } else {
+
+ while (sitr.hasNext()) {
+
+ final IBindingSet[] chunk = sitr.next();
+
+ processChunk(chunk);
+
+ }
+
+ }
+
+ // Now that we know the subqueries ran Ok, flush the sink.
+ context.getSink().flush();
+
+ // Done.
+ return null;
+
+ } finally {
+
+ context.getSource().close();
+
+ context.getSink().close();
+
+ if (context.getSink2() != null)
+ context.getSink2().close();
+
+ }
+
+ }
+
+ @SuppressWarnings("unchecked")
+ private void processChunk(final IBindingSet[] chunkIn) throws Exception {
+
+ final Map<SolutionKey, IBindingSet> solutionsOut =
+ new LinkedHashMap<SolutionKey, IBindingSet>();
+
+ final QueryEngine queryEngine = this.context
+ .getRunningQuery().getQueryEngine();
+
+ /*
+ * The input to each round of transitive chaining.
+ */
+ final Set<IBindingSet> nextRoundInput = new LinkedHashSet<IBindingSet>();
+
+ /*
+ * Decide based on the schematics of the path and the
+ * incoming data whether to run in forward or reverse gear.
+ *
+ * TODO Break the incoming chunk into two chunks - one to be run
+ * in forward gear and one to be run in reverse. This is an
+ * extremely unlikely scenario.
+ */
+ final Gearing gearing = chooseGearing(chunkIn);
+
+ if (log.isDebugEnabled()) {
+ log.debug("gearing: " + gearing);
+ }
+
+ for (IBindingSet parentSolutionIn : chunkIn) {
+
+ if (log.isDebugEnabled())
+ log.debug("parent solution in: " + parentSolutionIn);
+
+ IBindingSet childSolutionIn = parentSolutionIn.clone();
+
+ /*
+ * The seed is either a constant on the input side of
+ * the property path or a bound value for the property
+ * path's input variable from the incoming binding set.
+ */
+ final IConstant<?> seed = gearing.inConst != null ?
+ gearing.inConst : childSolutionIn.get(gearing.inVar);
+
+ if (log.isDebugEnabled())
+ log.debug("seed: " + seed);
+
+ if (seed != null) {
+
+ childSolutionIn.set(gearing.tVarIn, seed);
+
+ /*
+ * Dirty hack for zero length paths. Add a zero length
+ * path from the seed to itself. By handling this here
+ * (instead of in a separate operator) we get the
+ * cardinality right. Except in the case on nested
+ * arbitrary length paths, we are getting too few solutions
+ * from that (over-filtering). See the todo below. Again,
+ * this seems to be a very esoteric problem stemming from
+ * an unlikely scenario. Not going to fix it for now.
+ *
+ * TODO Add a binding for the bop id for the
+ * subquery that generated this solution and use
+ * that as part of the solution key somehow? This
+ * would allow duplicates from nested paths to
+ * remain in the outbound solutions, which seems to
+ * be the problem with the TCK query:
+ *
+ * :a (:p*)* ?y
+ */
+ if (lowerBound == 0 && gearing.outVar != null &&
+ !childSolutionIn.isBound(gearing.outVar)) {
+
+ final IBindingSet bs = parentSolutionIn.clone();
+
+ /*
+ * Setting the outVar seems to produce duplicates
+ * when we do chunk at a time.
+ */
+// bs.set(gearing.outVar, seed);
+
+ bs.set(gearing.tVarIn, seed);
+
+ bs.set(gearing.tVarOut, seed);
+
+ solutionsOut.put(newSolutionKey(gearing, bs), bs);
+
+ if (log.isDebugEnabled()) {
+ log.debug("added a zero length path: " + bs);
+ }
+
+ }
+
+ }
+
+ nextRoundInput.add(childSolutionIn);
+
+ }
+
+ if (log.isDebugEnabled()) {
+ for (IBindingSet childSolutionIn : nextRoundInput)
+ log.debug("first round input: " + childSolutionIn);
+ }
+
+ for (int i = 0; i < upperBound; i++) {
+
+ long sizeBefore = solutionsOut.size();
+
+ // The subquery
+ IRunningQuery runningSubquery = null;
+ // The iterator draining the subquery
+ ICloseableIterator<IBindingSet[]> subquerySolutionItr = null;
+
+ try {
+
+ runningSubquery = queryEngine.eval(subquery,
+ nextRoundInput.toArray(new IBindingSet[nextRoundInput.size()]));
+
+ long count = 0L;
+ try {
+
+ // Declare the child query to the parent.
+ ((AbstractRunningQuery) context.getRunningQuery())
+ .addChild(runningSubquery);
+
+ // clear the input set to make room for the next round
+ nextRoundInput.clear();
+
+ // Iterator visiting the subquery solutions.
+ subquerySolutionItr = runningSubquery.iterator();
+
+ while (subquerySolutionItr.hasNext()) {
+
+ final IBindingSet[] chunk = subquerySolutionItr.next();
+
+ for (IBindingSet bs : chunk) {
+
+ count++;
+
+ if (log.isDebugEnabled()) {
+ log.debug("round " + i + " solution: " + bs);
+ }
+
+ if (gearing.inVar != null && !bs.isBound(gearing.inVar)) {
+
+ /*
+ * Must be the first round. The first
+ * round when there are no incoming
+ * binding (from the parent or previous
+ * rounds) is the only time the inVar
+ * won't be set.
+ */
+ bs.set(gearing.inVar, bs.get(gearing.tVarIn));
+
+ if (log.isDebugEnabled()) {
+ log.debug("adding binding for inVar: " + bs);
+ }
+
+ }
+
+ // drop the intermediate variables
+ dropVars(bs);
+
+// solutionsOut.add(solution);
+ solutionsOut.put(newSolutionKey(gearing, bs), bs);
+
+ /*
+ * Remap the solution as input to the next round.
+ */
+ final IBindingSet input = bs.clone();
+
+ input.set(gearing.tVarIn, bs.get(gearing.tVarOut));
+
+ input.clear(gearing.tVarOut);
+
+ nextRoundInput.add(input);
+
+ if (log.isDebugEnabled()) {
+ log.debug("remapped as input for next round: " + input);
+ }
+
+ }
+
+ }
+
+ // finished with the iterator
+ subquerySolutionItr.close();
+
+ // wait for the subquery to halt / test for errors.
+ runningSubquery.get();
+
+ if (log.isDebugEnabled()) {
+ log.debug("done with round " + i +
+ ", count=" + count +
+ ", totalBefore=" + sizeBefore +
+ ", totalAfter=" + solutionsOut.size() +
+ ", totalNew=" + (solutionsOut.size() - sizeBefore));
+ }
+
+ // we've reached fixed point
+ if (solutionsOut.size() == sizeBefore) {
+
+ break;
+
+ }
+
+ } catch (InterruptedException ex) {
+
+ // this thread was interrupted, so cancel the subquery.
+ runningSubquery
+ .cancel(true/* mayInterruptIfRunning */);
+
+ // rethrow the exception.
+ throw ex;
+
+ }
+
+ } catch (Throwable t) {
+
+ if (runningSubquery == null
+ || runningSubquery.getCause() != null) {
+ /*
+ * If things fail before we start the subquery, or if a
+ * subquery fails (due to abnormal termination), then
+ * propagate the error to the parent and rethrow the
+ * first cause error out of the subquery.
+ *
+ * Note: IHaltable#getCause() considers exceptions
+ * triggered by an interrupt to be normal termination.
+ * Such exceptions are NOT propagated here and WILL NOT
+ * cause the parent query to terminate.
+ */
+ throw new RuntimeException(ArbitraryLengthPathTask.this.context
+ .getRunningQuery().halt(
+ runningSubquery == null ? t
+ : runningSubquery.getCause()));
+ }
+
+// return runningSubquery;
+
+ } finally {
+
+ try {
+
+ // ensure subquery is halted.
+ if (runningSubquery != null)
+ runningSubquery
+ .cancel(true/* mayInterruptIfRunning */);
+
+ } finally {
+
+ // ensure the subquery solution iterator is closed.
+ if (subquerySolutionItr != null)
+ subquerySolutionItr.close();
+
+ }
+
+ }
+
+ } // fixed point for loop
+
+ /*
+ * Do some final filtering and then send the solutions
+ * down the pipeline.
+ */
+ final Iterator<Map.Entry<SolutionKey, IBindingSet>> it =
+ solutionsOut.entrySet().iterator();
+
+ while (it.hasNext()) {
+
+ final Map.Entry<SolutionKey, IBindingSet> entry = it.next();
+
+ final IBindingSet bs = entry.getValue();
+
+ if (log.isDebugEnabled()) {
+ log.debug("considering possible solution: " + bs);
+ }
+
+ if (gearing.outConst != null) {
+
+ /*
+ * Handle the case where there is a constant on the
+ * output side of the subquery. Make sure the
+ * solution's transitive output variable matches.
+ */
+ if (!bs.get(gearing.tVarOut).equals(gearing.outConst)) {
+
+ if (log.isDebugEnabled()) {
+ log.debug("transitive output does not match output const, dropping");
+ }
+
+ it.remove();
+
+ continue;
+
+ }
+
+ } else { // outVar != null
+
+ /*
+ * Handle the case where the gearing.outVar was bound
+ * coming in. Again, make sure it matches the
+ * transitive output variable.
+ */
+ if (bs.isBound(gearing.outVar)) {
+
+ if (!bs.get(gearing.tVarOut).equals(bs.get(gearing.outVar))) {
+
+ if (log.isDebugEnabled()) {
+ log.debug("transitive output does not match incoming binding for output var, dropping");
+ }
+
+ it.remove();
+
+ continue;
+
+ }
+
+ } else {
+
+ /*
+ * Handle the normal case - when we simply
+ * need to copy the transitive output over to
+ * the real output.
+ */
+ bs.set(gearing.outVar, bs.get(gearing.tVarOut));
+
+ }
+
+ }
+
+ if (log.isDebugEnabled()) {
+ log.debug("solution accepted");
+ }
+
+ /*
+ * Should we drop the intermediate variables now?
+ */
+ bs.clear(gearing.tVarIn);
+ bs.clear(gearing.tVarOut);
+
+ }
+
+ final IBindingSet[] chunkOut =
+ solutionsOut.values().toArray(
+ new IBindingSet[solutionsOut.size()]);
+
+ if (log.isDebugEnabled()) {
+ log.debug("final output to sink:\n" + Arrays.toString(chunkOut));
+ }
+
+ // copy accepted binding sets to the default sink.
+ context.getSink().add(chunkOut);
+
+ // done.
+// return runningSubquery;
+
+ } // processChunk method
+
+ /**
+ * Choose forward or reverse gear based on the scematics of the operator
+ * and the incoming binding sets.
+ */
+ private Gearing chooseGearing(final IBindingSet[] bsets) {
+
+ /*
+ * By just taking the first binding set we are assuming that all
+ * the binding sets in this chunk are best served by the same
+ * gearing.
+ *
+ * TODO Challenge this assumption?
+ */
+ final IBindingSet bs = (bsets != null && bsets.length > 0) ?
+ bsets[0] : EmptyBindingSet.INSTANCE;
+
+ if (forwardGearing.inConst != null) {
+
+ if (log.isDebugEnabled())
+ log.debug("forward gear");
+
+ // <X> (p/p)* ?o or <X> (p/p)* <Y>
+ return forwardGearing;
+
+ } else if (forwardGearing.outConst != null) {
+
+ if (log.isDebugEnabled())
+ log.debug("reverse gear");
+
+ // ?s (p/p)* <Y>
+ return reverseGearing;
+
+ } else {
+
+ if (bs.isBound(forwardGearing.inVar)) {
+
+ if (log.isDebugEnabled())
+ log.debug("forward gear");
+
+ // ?s (p/p)* ?o and ?s is bound in incoming binding set
+ return forwardGearing;
+
+ } else if (bs.isBound(forwardGearing.outVar)) {
+
+ if (log.isDebugEnabled())
+ log.debug("reverse gear");
+
+ // ?s (p/p)* ?o and ?o is bound in incoming binding set
+ return reverseGearing;
+
+ } else {
+
+ if (log.isDebugEnabled())
+ log.debug("forward gear");
+
+ // ?s (p/p)* ?o and neither ?s nor ?o are bound in incoming binding set
+ return forwardGearing;
+
+ }
+
+ }
+
+ }
+
+ /**
+ * Drop vars bound by nested paths that are not meant to be external
+ * output.
+ */
+ private void dropVars(final IBindingSet bs) {
+
+ if (varsToDrop != null) {
+
+ for (IVariable<?> v : varsToDrop) {
+
+ bs.clear(v);
+
+ }
+
+ }
+
+ }
+
+ /**
+ * Need to filter the duplicates per the spec:
+ *
+ * "Such connectivity matching does not introduce duplicates
+ * (it does not incorporate any count of the number of ways
+ * the connection can be made) even if the repeated path
+ * itself would otherwise result in duplicates.
+ *
+ * The graph matched may include cycles. Connectivity
+ * matching is defined so that matching cycles does not lead
+ * to undefined or infinite results."
+ *
+ * We handle this by keeping the solutions in a Map with a solution
+ * key that keeps duplicates from getting in.
+ */
+ private SolutionKey newSolutionKey(final Gearing gearing, final IBindingSet bs) {
+
+ if (gearing.inVar != null && gearing.outVar != null) {
+ return new SolutionKey(new IConstant<?>[] {
+ bs.get(gearing.inVar), bs.get(gearing.outVar), bs.get(gearing.tVarOut)
+ });
+ } else if (gearing.inVar != null) {
+ return new SolutionKey(new IConstant<?>[] {
+ bs.get(gearing.inVar), bs.get(gearing.tVarOut)
+ });
+ } else if (gearing.outVar != null) {
+ return new SolutionKey(new IConstant<?>[] {
+ bs.get(gearing.outVar), bs.get(gearing.tVarOut)
+ });
+ } else {
+ return new SolutionKey(new IConstant<?>[] {
+ bs.get(gearing.tVarOut)
+ });
+ }
+
+ }
+
+ /**
+ * This operator can work in forward or reverse gear. In forward gear,
+ * the left side of the path is the input and the right side is output.
+ * In reverse it's the opposite. Each side, input and output, will
+ * have one term, either a variable or a constant. Although there are
+ * two variables for each side, only one can be non-null. The
+ * transitivity variables must always be non-null;
+ */
+ private final static class Gearing {
+
+ private final IVariable<?> inVar, outVar;
+ private final IConstant<?> inConst, outConst;
+ private final IVariable<?> tVarIn, tVarOut;
+
+ public Gearing(
+ final IVariable<?> inVar, final IVariable<?> outVar,
+ final IConstant<?> inConst, final IConstant<?> outConst,
+ final IVariable<?> tVarIn, final IVariable<?> tVarOut) {
+
+ if ((inVar == null && inConst == null) ||
+ (inVar != null && inConst != null)) {
+ throw new IllegalArgumentException();
+ }
+
+ if ((outVar == null && outConst == null) ||
+ (outVar != null && outConst != null)) {
+ throw new IllegalArgumentException();
+ }
+
+ if (tVarIn == null || tVarOut == null) {
+ throw new IllegalArgumentException();
+ }
+
+ this.inVar = inVar;
+
+ this.outVar = outVar;
+
+ this.inConst = inConst;
+
+ this.outConst = outConst;
+
+ this.tVarIn = tVarIn;
+
+ this.tVarOut = tVarOut;
+
+ }
+
+ public Gearing reverse() {
+
+ return new Gearing(
+ this.outVar, this.inVar,
+ this.outConst, this.inConst,
+ this.tVarOut, this.tVarIn);
+
+ }
+
+ public String toString() {
+
+ final StringBuilder sb = new StringBuilder();
+
+ sb.append(getClass().getSimpleName()).append(" [");
+ sb.append("inVar=").append(inVar);
+ sb.append(", outVar=").append(outVar);
+ sb.append(", inConst=").append(inConst);
+ sb.append(", outConst=").append(outConst);
+ sb.append(", tVarIn=").append(suffix(tVarIn, 8));
+ sb.append(", tVarOut=").append(suffix(tVarOut, 8));
+ sb.append("]");
+
+ return sb.toString();
+
+ }
+
+ public String suffix(final Object o, final int len) {
+
+ final String s = o.toString();
+
+ return s.substring(s.length()-len, s.length());
+
+ }
+
+ }
+
+ /**
+ * Lifted directly from the JVMDistinctBindingSetsOp.
+ */
+ private final static class SolutionKey {
+
+ private final int hash;
+
+ private final IConstant<?>[] vals;
+
+ public SolutionKey(final IConstant<?>[] vals) {
+ this.vals = vals;
+ this.hash = java.util.Arrays.hashCode(vals);
+ }
+
+ public int hashCode() {
+ return hash;
+ }
+
+ public boolean equals(final Object o) {
+ if (this == o)
+ return true;
+ if (!(o instanceof SolutionKey)) {
+ return false;
+ }
+ final SolutionKey t = (SolutionKey) o;
+ if (vals.length != t.vals.length)
+ return false;
+ for (int i = 0; i < vals.length; i++) {
+ // @todo verify that this allows for nulls with a unit test.
+ if (vals[i] == t.vals[i])
+ continue;
+ if (vals[i] == null)
+ return false;
+ if (!vals[i].equals(t.vals[i]))
+ return false;
+ }
+ return true;
+ }
+
+ }
+
+ } // ArbitraryLengthPathTask
+
+}
Property changes on: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ArbitraryLengthPathOp.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ZeroLengthPathOp.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ZeroLengthPathOp.java (rev 0)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ZeroLengthPathOp.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -0,0 +1,282 @@
+/**
+
+Copyright (C) SYSTAP, LLC 2006-2010. All rights reserved.
+
+Contact:
+ SYSTAP, LLC
+ 4501 Tower Road
+ Greensboro, NC 27410
+ lic...@bi...
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; version 2 of the License.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+/*
+ * Created on Aug 25, 2010
+ */
+
+package com.bigdata.bop.paths;
+
+import java.util.Map;
+import java.util.concurrent.Callable;
+import java.util.concurrent.FutureTask;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.BOpContext;
+import com.bigdata.bop.IBindingSet;
+import com.bigdata.bop.IConstant;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.IVariableOrConstant;
+import com.bigdata.bop.NV;
+import com.bigdata.bop.PipelineOp;
+import com.bigdata.relation.accesspath.IBlockingBuffer;
+import com.bigdata.striterator.ICloseableIterator;
+
+/**
+ * An attempt to solve the zero length path problem with its own operator.
+ *
+ * @deprecated Does not work. Leads to cardinality problems.
+ */
+public class ZeroLengthPathOp extends PipelineOp {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ public interface Annotations extends PipelineOp.Annotations {
+
+ /**
+ * The left side of the zero-length path.
+ */
+ String LEFT_TERM = Annotations.class.getName() + ".leftTerm";
+
+ /**
+ * The right side of the zero-length path.
+ */
+ String RIGHT_TERM = Annotations.class.getName() + ".rightTerm";
+
+ }
+
+ /**
+ * Deep copy constructor.
+ *
+ * @param op
+ */
+ public ZeroLengthPathOp(ZeroLengthPathOp op) {
+ super(op);
+ }
+
+ /**
+ * Shallow copy constructor.
+ *
+ * @param args
+ * @param annotations
+ */
+ public ZeroLengthPathOp(BOp[] args, Map<String, Object> annotations) {
+ super(args, annotations);
+ }
+
+ public ZeroLengthPathOp(final BOp[] args, NV... annotations) {
+
+ this(args, NV.asMap(annotations));
+
+ }
+
+ public FutureTask<Void> eval(final BOpContext<IBindingSet> context) {
+
+ return new FutureTask<Void>(new ZeroLengthPathTask(this, context));
+
+ }
+
+ static private class ZeroLengthPathTask implements Callable<Void> {
+
+ private final BOpContext<IBindingSet> context;
+
+ private final IVariable<?> leftVar, rightVar;
+
+ private final IConstant<?> leftConst, rightConst;
+
+ ZeroLengthPathTask(final ZeroLengthPathOp op,
+ final BOpContext<IBindingSet> context) {
+
+ this.context = context;
+
+ final IVariableOrConstant<?> leftTerm = (IVariableOrConstant<?>) op
+ .getProperty(Annotations.LEFT_TERM);
+
+ this.leftVar = leftTerm.isVar() ? (IVariable<?>) leftTerm : null;
+
+ this.leftConst = leftTerm.isConstant() ? (IConstant<?>) leftTerm : null;
+
+ final IVariableOrConstant<?> rightTerm = (IVariableOrConstant<?>) op
+ .getProperty(Annotations.RIGHT_TERM);
+
+ this.rightVar = rightTerm.isVar() ? (IVariable<?>) rightTerm : null;
+
+ this.rightConst = rightTerm.isConstant() ? (IConstant<?>) rightTerm : null;
+
+ if (leftConst != null && rightConst != null) {
+
+ throw new IllegalArgumentException("must be a variable on at least one side");
+
+ }
+
+ }
+
+ public Void call() throws Exception {
+
+ // source.
+ final ICloseableIterator<IBindingSet[]> source = context
+ .getSource();
+
+ // default sink
+ final IBlockingBuffer<IBindingSet[]> sink = context.getSink();
+
+ try {
+
+ while (source.hasNext()) {
+
+ final IBindingSet[] chunk = source.next();
+
+ final IBindingSet[] chunkOut = processChunk(chunk);
+
+ sink.add(chunkOut);
+
+ }
+
+ // flush the sink.
+ sink.flush();
+
+ // Done.
+ return null;
+
+ } finally {
+
+ sink.close();
+
+ source.close();
+
+ }
+
+ }
+
+ @SuppressWarnings("unchecked")
+ private IBindingSet[] processChunk(final IBindingSet[] chunk) {
+
+ final IBindingSet[] chunkOut = new IBindingSet[chunk.length];
+
+ int j = 0;
+ for (int i = 0; i < chunk.length; i++) {
+
+ final IBindingSet bs = chunk[i].clone();
+
+ final Gearing gearing = getGearing(bs);
+
+ if (gearing == null) {
+
+ // neither side of the zero-length path is bound
+ return new IBindingSet[0];
+
+ }
+
+ // first check to see if the variable side is already bound
+ if (bs.isBound(gearing.var)) {
+
+ /*
+ * If it has a value that is not equals to the constant
+ * side then we filter out the solution (by not adding it
+ * to chunkOut).
+ */
+
+ if (!bs.get(gearing.var).equals(gearing.constant)) {
+
+ continue;
+
+ }
+
+ } else {
+
+ // create a zero length path
+ bs.set(gearing.var, gearing.constant);
+
+ }
+
+ chunkOut[j++] = bs;
+
+ }
+
+ if (j != chunk.length) {
+
+ final IBindingSet[] tmp = new IBindingSet[j];
+
+ System.arraycopy(chunkOut, 0, tmp, 0, j);
+
+ return tmp;
+
+ } else {
+
+ return chunkOut;
+
+ }
+
+ }
+
+ private Gearing getGearing(final IBindingSet bs) {
+
+ if (leftConst != null) {
+
+ return new Gearing(rightVar, leftConst);
+
+ } else if (rightConst != null) {
+
+ return new Gearing(leftVar, rightConst);
+
+ } else { // both left and right are vars
+
+ if (bs.isBound(this.leftVar)) {
+
+ return new Gearing(this.rightVar, bs.get(this.leftVar));
+
+ } else if (bs.isBound(this.rightVar)) {
+
+ return new Gearing(this.leftVar, bs.get(this.rightVar));
+
+ } else {
+
+ return null;
+
+ }
+
+ }
+
+ }
+
+ private class Gearing {
+
+ final public IVariable<?> var;
+
+ final public IConstant<?> constant;
+
+ public Gearing(final IVariable<?> var, final IConstant<?> constant) {
+
+ this.var = var;
+ this.constant = constant;
+
+ }
+
+ }
+
+ } // class ZeroLengthPathTask
+
+}
Property changes on: branches/BIGDATA_RELEASE_1_2_0/bigdata/src/java/com/bigdata/bop/paths/ZeroLengthPathOp.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java (rev 0)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -0,0 +1,210 @@
+package com.bigdata.rdf.sparql.ast;
+
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.Constant;
+import com.bigdata.bop.IVariable;
+import com.bigdata.bop.NV;
+import com.bigdata.rdf.sparql.ast.PathNode.PathMod;
+
+/**
+ * A special kind of AST node that represents the SPARQL 1.1 arbitrary length
+ * path operator. This node has a single child arg - a JoinGroupNode consisting
+ * of other operators (the path) that must be run to fixed point. This node also
+ * has several annotations that define the schematics (the left and right sides
+ * and the lower and upper bounds) of the arbitrary length path.
+ */
+public class ArbitraryLengthPathNode
+ extends GroupMemberNodeBase<ArbitraryLengthPathNode>
+ implements IBindingProducerNode {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ interface Annotations extends GroupNodeBase.Annotations {
+
+ /**
+ * The left term - can be a variable or a constant.
+ */
+ String LEFT_TERM = Annotations.class.getName() + ".leftTerm";
+
+ /**
+ * The right term - can be a variable or a constant.
+ */
+ String RIGHT_TERM = Annotations.class.getName() + ".rightTerm";
+
+ /**
+ * The left transitivity variable.
+ */
+ String TRANSITIVITY_VAR_LEFT = Annotations.class.getName() + ".transitivityVarLeft";
+
+ /**
+ * The right transitivity variable.
+ */
+ String TRANSITIVITY_VAR_RIGHT = Annotations.class.getName() + ".transitivityVarRight";
+
+ /**
+ * The lower bound on the number of rounds to run. Can be zero (0) or
+ * one (1). A lower bound of zero is a special kind of path - the
+ * Zero Length Path. A zero length path connects a vertex to itself
+ * (in graph parlance). In the context of arbitrary length paths it
+ * means we bind the input onto the output regardless of whether they
+ * are actually connected via the path or not.
+ */
+ String LOWER_BOUND = Annotations.class.getName() + ".lowerBound";
+
+ /**
+ * The upper bound on the number of rounds to run.
+ */
+ String UPPER_BOUND = Annotations.class.getName() + ".upperBound";
+
+ }
+
+ /**
+ * Required deep copy constructor.
+ */
+ public ArbitraryLengthPathNode(ArbitraryLengthPathNode op) {
+
+ super(op);
+
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public ArbitraryLengthPathNode(BOp[] args, Map<String, Object> anns) {
+
+ super(args, anns);
+
+ }
+
+ /**
+ * Fully construct an arbitrary length path node with all required
+ * annotations.
+ */
+ public ArbitraryLengthPathNode(final TermNode left, final TermNode right,
+ final VarNode transitivityVarLeft, final VarNode transitivityVarRight,
+ final PathMod mod) {
+ this(new BOp[] { new JoinGroupNode() }, NV.asMap(
+ new NV(Annotations.LEFT_TERM, left),
+ new NV(Annotations.RIGHT_TERM, right),
+ new NV(Annotations.TRANSITIVITY_VAR_LEFT, transitivityVarLeft),
+ new NV(Annotations.TRANSITIVITY_VAR_RIGHT, transitivityVarRight),
+ new NV(Annotations.LOWER_BOUND, mod == PathMod.ONE_OR_MORE ? 1L : 0L),
+ new NV(Annotations.UPPER_BOUND, mod == PathMod.ZERO_OR_ONE ? 1L : Long.MAX_VALUE)
+ ));
+ }
+
+ /**
+ * Returns the left term.
+ */
+ public TermNode left() {
+ return (TermNode) super.getRequiredProperty(Annotations.LEFT_TERM);
+ }
+
+ /**
+ * Returns the right term.
+ */
+ public TermNode right() {
+ return (TermNode) super.getRequiredProperty(Annotations.RIGHT_TERM);
+ }
+
+ /**
+ * Return the left transitivity var.
+ */
+ public VarNode tVarLeft() {
+ return (VarNode) super.getRequiredProperty(Annotations.TRANSITIVITY_VAR_LEFT);
+ }
+
+ /**
+ * Return the right transitivity var.
+ */
+ public VarNode tVarRight() {
+ return (VarNode) super.getRequiredProperty(Annotations.TRANSITIVITY_VAR_RIGHT);
+ }
+
+ /**
+ * Return the lower bound.
+ */
+ public long lowerBound() {
+ return (Long) super.getRequiredProperty(Annotations.LOWER_BOUND);
+ }
+
+ /**
+ * Return the upper bound.
+ */
+ public long upperBound() {
+ return (Long) super.getRequiredProperty(Annotations.UPPER_BOUND);
+ }
+
+ /**
+ * Return the subgroup.
+ */
+ public JoinGroupNode subgroup() {
+ return (JoinGroupNode) get(0);
+ }
+
+ /**
+ * Return the variables bound by the path - i.e. what this node will
+ * attempt to bind when run.
+ */
+ public Set<IVariable<?>> getProducedBindings() {
+
+ final Set<IVariable<?>> producedBindings = new LinkedHashSet<IVariable<?>>();
+
+ addProducedBindings(left(), producedBindings);
+ addProducedBindings(right(), producedBindings);
+
+ return producedBindings;
+
+ }
+
+ /**
+ * This handles the special case where we've wrapped a Var with a Constant
+ * because we know it's bound, perhaps by the exogenous bindings. If we
+ * don't handle this case then we get the join vars wrong.
+ *
+ * @see StaticAnalysis._getJoinVars
+ */
+ private void addProducedBindings(final TermNode t, final Set<IVariable<?>> producedBindings) {
+
+ if (t instanceof VarNode) {
+
+ producedBindings.add(((VarNode) t).getValueExpression());
+
+ } else if (t instanceof ConstantNode) {
+
+ final ConstantNode cNode = (ConstantNode) t;
+ final Constant<?> c = (Constant<?>) cNode.getValueExpression();
+ final IVariable<?> var = c.getVar();
+ if (var != null) {
+ producedBindings.add(var);
+ }
+
+ }
+
+ }
+
+ @Override
+ public String toString(int indent) {
+
+ final String s = indent(indent);
+
+ final StringBuilder sb = new StringBuilder();
+ sb.append("\n");
+ sb.append(s).append(getClass().getSimpleName());
+ sb.append("(left=").append(left()).append(", right=").append(right()).append(") {");
+ sb.append(subgroup().toString(indent+1));
+ sb.append("\n").append(s).append("}");
+
+ return sb.toString();
+
+ }
+
+
+}
Property changes on: branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PathNode.java
===================================================================
--- branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PathNode.java (rev 0)
+++ branches/BIGDATA_RELEASE_1_2_0/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/PathNode.java 2013-01-22 18:27:52 UTC (rev 6814)
@@ -0,0 +1,359 @@
+package com.bigdata.rdf.sparql.ast;
+
+import java.util.Map;
+
+import com.bigdata.bop.BOp;
+import com.bigdata.bop.NV;
+
+/**
+ * AST Node used to represent a property path.
+ *
+ * See http://www.w3.org/TR/sparql11-query/#rTriplesSameSubjectPath for details.
+ *
+ * This class corresponds to "VerbPath".
+ *
+ * A VerbPath (PathNode) has one Path.
+ * VerbPath ::= Path
+ *
+ * A Path has one PathAlternative.
+ * Path ::= PathAlt
+ *
+ * A PathAlternative has one or more PathSequences.
+ * PathAlternative ::= PathSequence ( '|' PathSequence )*
+ *
+ * A PathSequence has one or more PathEltOrInverses.
+ * PathSequence ::= PathEltOrInverse ( '/' PathEltOrInverse )*
+ *
+ * A PathEltOrInverse has one PathElt and a boolean flag for inverse ('^').
+ * PathEltOrInverse ::= PathElt | '^' PathElt
+ *
+ * A PathElt has a PathPrimary and an optional PathMod.
+ * PathElt ::= PathPrimary PathMod?
+ *
+ * A PathPrimary has either an iri, a PathNegatedPropertySet, or a nested Path.
+ * PathPrimary ::= iri | '!' PathNegatedPropertySet | '(' Path ')'
+ *
+ * A PathMod is one from the enumeration '?', '*', or '+'. '?' means zero or
+ * one (simple optional), '+' means one or more (fixed point), and '*' means
+ * zero or more (optional fixed point).
+ * PathMod ::= '?' | '*' | '+'
+ *
+ * A PathNegatedPropertySet is zero or more PathOneInPropertySets.
+ * PathNegatedPropertySet ::= PathOneInPropertySet |
+ * '(' (PathOneInPropertySet ( '|' PathOneInPropertySet )* )? ')'
+ *
+ * A PathOneInPropertySet is an iri and a boolean flag for inverse ('^').
+ * PathOneInPropertySet ::= iri | '^' iri
+ *
+ * This model is actually flattened a bit by Sesame, so I followed Sesame's
+ * model instead of the grammar. In Sesame's model, the top level is
+ * PathAlternative, which contains one or more PathSequences. Each
+ * PathSequence contains one or more PathElt. Each PathElt has two modifiers -
+ * the PathMod (for arbitrary length and zero length paths) and the inverse
+ * modifier. It also has the actual element - one of either a TermNode,
+ * a nested path (a PathAlternative), a NegatedPropertySet, or a zero
+ * length path.
+ *
+ * @author mikepersonick
+ */
+public class PathNode extends ASTBase {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = -4396141823074067307L;
+
+ /**
+ * Required deep copy constructor.
+ */
+ public PathNode(PathNode op) {
+ super(op);
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public PathNode(final BOp[] args, final Map<String, Object> anns) {
+ super(args, anns);
+ }
+
+ public PathNode(final PathAlternative arg) {
+ this(new BOp[] { arg }, BOp.NOANNS);
+ }
+
+ /**
+ * The root of the property path is always a PathAlternative.
+ */
+ public PathAlternative getPathAlternative() {
+ return (PathAlternative) get(0);
+ }
+
+ /**
+ * Used to signify an OR (UNION) of multiple possible subpaths.
+ */
+ public static class PathAlternative extends ASTBase {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ */
+ public PathAlternative(PathAlternative op) {
+ super(op);
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public PathAlternative(final BOp[] args, final Map<String, Object> anns) {
+ super(args, anns);
+ }
+
+ public PathAlternative(final PathSequence... args) {
+ this(args, BOp.NOANNS);
+
+ if (args == null || args.length == 0)
+ throw new IllegalArgumentException("one or more args required");
+ }
+
+ }
+
+ /**
+ * A sequence of paths (JOINS).
+ */
+ public static class PathSequence extends ASTBase {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ */
+ public PathSequence(PathSequence op) {
+ super(op);
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public PathSequence(final BOp[] args, final Map<String, Object> anns) {
+ super(args, anns);
+ }
+
+ public PathSequence(final PathElt... args) {
+ this(args, BOp.NOANNS);
+
+ if (args == null || args.length == 0)
+ throw new IllegalArgumentException("one or more args required");
+ }
+
+ }
+
+ /**
+ * A specific path element. Can be a nested path (a PathAlternative).
+ */
+ public static class PathElt extends ASTBase {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ interface Annotations extends ASTBase.Annotations {
+
+ /**
+ * The inverse modifier '^'.
+ */
+ String INVERSE = Annotations.class.getName() + ".inverse";
+
+ /**
+ * The cardinality modifiers '?', '*', and '+'.
+ */
+ String MOD = Annotations.class.getName() + ".mod";
+
+ }
+
+ /**
+ * Required deep copy constructor.
+ */
+ public PathElt(PathElt op) {
+ super(op);
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public PathElt(final BOp[] args, final Map<String, Object> anns) {
+ super(args, anns);
+ }
+
+ /**
+ * @see {@link #PathNode(BOp, boolean, PathMod)}.
+ */
+ public PathElt(final BOp arg) {
+ this(arg, false);
+ }
+
+ /**
+ * @see {@link #PathNode(BOp, boolean, PathMod)}.
+ */
+ public PathElt(final BOp arg, final boolean inverse) {
+ this(arg, inverse, null);
+ }
+
+ /**
+ * @see {@link #PathNode(BOp, boolean, PathMod)}.
+ */
+ public PathElt(final BOp arg, final PathMod mod) {
+ this(arg, false, mod);
+ }
+
+ /**
+ * @param arg Must be one of the following types:
+ * <ul>
+ * <li>{@link ConstantNode}</li>
+ * <li>{@link PathAlternative}</li>
+ * <li>{@link PathNegatedPropertySet}</li>
+ * <li>{@link ZeroLengthPathNode}</li>
+ * <ul>
+ */
+ public PathElt(final BOp arg, final boolean inverse, final PathMod mod) {
+ this(new BOp[] { arg }, NV.asMap(
+ new NV(Annotations.INVERSE, inverse),
+ new NV(Annotations.MOD, mod)));
+
+ if (!(arg instanceof ConstantNode ||
+ arg instanceof PathAlternative ||
+ arg instanceof PathNegatedPropertySet ||
+ arg instanceof ZeroLengthPathNode)) {
+ throw new IllegalArgumentException();
+ }
+ }
+
+ public boolean inverse() {
+ return (Boolean) super.getRequiredProperty(Annotations.INVERSE);
+ }
+
+ public void setInverse(final boolean inverse) {
+ super.setProperty(Annotations.INVERSE, inverse);
+ }
+
+ public PathMod getMod() {
+ return (PathMod) super.getProperty(Annotations.MOD);
+ }
+
+ public void setMod(final PathMod mod) {
+ super.setProperty(Annotations.MOD, mod);
+ }
+
+ public boolean isIRI() {
+ return get(0) instanceof ConstantNode;
+ }
+
+ public boolean isNestedPath() {
+ return get(0) instanceof PathAlternative;
+ }
+
+ public boolean isNegatedPropertySet() {
+ return get(0) instanceof PathNegatedPropertySet;
+ }
+
+ public boolean isZeroLengthPath() {
+ return get(0) instanceof ZeroLengthPathNode;
+ }
+
+ }
+
+ public static enum PathMod {
+
+ ZERO_OR_ONE("?"),
+
+ ZERO_OR_MORE("*"),
+
+ ONE_OR_MORE("+");
+
+ final String mod;
+ PathMod(final String mod) {
+ this.mod = mod;
+ }
+
+ public String toString() {
+ return mod;
+ }
+
+ }
+
+ public static class PathNegatedPropertySet extends ASTBase {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ /**
+ * Required deep copy constructor.
+ */
+ public PathNegatedPropertySet(PathNegatedPropertySet op) {
+ super(op);
+ }
+
+ /**
+ * Required shallow copy constructor.
+ */
+ public PathNegatedPropertySet(final BOp[] args, final Map<String, Object> anns) {
+ super(args, anns);
+ }
+
+ public PathNegatedPropertySet(fin...
[truncated message content] |
