You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2015/06/18 16:38:27 UTC
[2/3] incubator-tinkerpop git commit: Removed MatchStep and replaced
it with XMatchStep. Renamed XMatchStep,
MatchStep. All the tests are passing for OLTP and OLAP except one in OLAP that
makes sense why it doesnt pass, but the pattern should be caught b
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/MatchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/MatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/MatchStep.java
deleted file mode 100644
index db00d80..0000000
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/MatchStep.java
+++ /dev/null
@@ -1,596 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.tinkerpop.gremlin.process.traversal.step.map.match;
-
-import org.apache.tinkerpop.gremlin.process.traversal.Scope;
-import org.apache.tinkerpop.gremlin.process.traversal.Step;
-import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
-import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
-import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
-import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_S_SE_SL_Traverser;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
-import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
-import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
-import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.NoSuchElementException;
-import java.util.Set;
-import java.util.Stack;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-/**
- * @author Joshua Shinavier (http://fortytwo.net)
- */
-public final class MatchStep<S, E> extends AbstractStep<S, Map<String, E>> implements Scoping, TraversalParent {
-
- static final BiConsumer<String, Object> TRIVIAL_CONSUMER = (s, t) -> {
- };
-
- private static final String ANON_LABEL_PREFIX = "_";
-
- // optimize before processing each start object, by default
- private static final int DEFAULT_STARTS_PER_OPTIMIZE = 1;
-
- private final String startLabel;
- private final Map<String, List<TraversalWrapper<S, S>>> traversalsByStartAs;
- private final List<Traversal<?,?>> traversals = new ArrayList<>();
-
- private int startsPerOptimize = DEFAULT_STARTS_PER_OPTIMIZE;
- private int optimizeCounter = -1;
- private int anonLabelCounter = 0;
-
- private Enumerator<S> currentSolution;
- private int currentIndex;
-
- // initial value allows MatchStep to be used as a stand-alone query engine
- private Traverser.Admin<S> currentStart;
-
- public MatchStep(final Traversal.Admin traversal, final String startLabel, final Traversal... traversals) {
- super(traversal);
- this.startLabel = startLabel;
- this.traversalsByStartAs = new HashMap<>();
- this.currentStart = new B_O_S_SE_SL_Traverser<>(null, this, 1l); // TODO: bad? P?
- for (final Traversal tl : traversals) {
- addTraversalPrivate(tl);
- this.integrateChild(tl.asAdmin());
- this.traversals.add(tl);
- }
- checkSolvability();
- }
-
- @Override
- public Set<TraverserRequirement> getRequirements() {
- return this.getSelfAndChildRequirements();
- }
-
- @Override
- public Set<String> getScopeKeys() {
- final Set<String> keys = new HashSet<>();
- keys.add(this.startLabel);
- this.traversals.forEach(t -> {
- keys.addAll(t.asAdmin().getStartStep().getLabels());
- keys.addAll(t.asAdmin().getEndStep().getLabels());
- });
- return keys;
- }
-
- @Override
- public String toString() {
- return StringFactory.stepString(this, this.traversalsByStartAs);
- }
-
- /**
- * Adds an individual traversal to an already-constructed MatchStep.
- * The query must be solvable after addition (i.e. should not require the addition of
- * further traversals in order to be solvable)
- * This method should be called before the query is first executed.
- *
- * @param traversal the traversal to add
- */
- public void addTraversal(final Traversal<S, S> traversal) {
- addTraversalPrivate(traversal);
- this.traversals.add(traversal);
- this.integrateChild(traversal.asAdmin());
- checkSolvability();
- }
-
- public void setStartsPerOptimize(final int startsPerOptimize) {
- if (startsPerOptimize < 1) {
- throw new IllegalArgumentException();
- }
- this.startsPerOptimize = startsPerOptimize;
- }
-
- @Override
- protected Traverser<Map<String, E>> processNextStart() throws NoSuchElementException {
- final Map<String, E> map = new HashMap<>();
- final Traverser<Map<String, E>> result = this.currentStart.split(map, this);
- final BiConsumer<String, S> resultSetter = (name, value) -> map.put(name, (E) value);
-
- while (true) { // break out when the current solution is exhausted and there are no more starts
- if (null == this.currentSolution) {
- if (this.starts.hasNext()) {
- this.optimizeCounter = (this.optimizeCounter + 1) % this.startsPerOptimize;
- if (0 == this.optimizeCounter) {
- optimize();
- }
-
- this.currentStart = this.starts.next();
- this.currentSolution = solveFor(IteratorUtils.of(this.currentStart.get()));
- this.currentIndex = 0;
- } else {
- throw FastNoSuchElementException.instance();
- }
- }
-
- map.clear();
- if (this.currentSolution.visitSolution(this.currentIndex++, resultSetter)) {
- return result;
- } else {
- this.currentSolution = null;
- }
- }
- }
-
- /**
- * @return a description of the current state of this step, including the query plan and gathered statistics
- */
- public String summarize() {
- final StringBuilder sb = new StringBuilder("match \"")
- .append(this.startLabel)
- .append("\":\t")
- .append(findCost(this.startLabel))
- .append('\n');
- summarize(this.startLabel, sb, new HashSet<>(), 1);
- return sb.toString();
- }
-
- private void summarize(final String outLabel,
- final StringBuilder sb,
- final Set<String> visited,
- final int indent) {
- if (!visited.contains(outLabel)) {
- visited.add(outLabel);
- final List<TraversalWrapper<S, S>> outs = traversalsByStartAs.get(outLabel);
- if (null != outs) {
- for (final TraversalWrapper<S, S> w : outs) {
- for (int i = 0; i < indent; i++) sb.append('\t');
- sb.append(outLabel).append("->").append(w.endLabel).append(":\t");
- sb.append(findCost(w));
- sb.append('\t').append(w);
- sb.append('\n');
- summarize(w.endLabel, sb, visited, indent + 1);
- }
- }
- }
- }
-
- private void addTraversalPrivate(final Traversal<S, S> traversal) {
- final Step<S, ?> startStep = traversal.asAdmin().getStartStep();
- if (startStep.getLabels().isEmpty())
- throw new IllegalArgumentException("Match traversals must have their start step labeled with as(): " + traversal);
- if (startStep.getLabels().size() > 1)
- throw new IllegalArgumentException("Match traversals can not have multiple labels on the start step: " + traversal);
- final String startAs = traversal.asAdmin().getStartStep().getLabels().iterator().next();
- ///
- final Step<?, S> endStep = traversal.asAdmin().getEndStep();
- if (endStep.getLabels().size() > 1)
- throw new IllegalArgumentException("Match traversals can not have multiple labels on the end step: " + traversal);
-
- String endAs = endStep.getLabels().isEmpty() ? null : endStep.getLabels().iterator().next();
- checkAs(startAs);
- if (null == endAs) {
- endAs = createAnonymousAs();
- } else {
- checkAs(endAs);
- }
-
- final TraversalWrapper<S, S> wrapper = new TraversalWrapper<>(traversal, startAs, endAs);
- // index all wrapped traversals by their startLabel
- List<TraversalWrapper<S, S>> l2 = this.traversalsByStartAs.get(startAs);
- if (null == l2) {
- l2 = new LinkedList<>();
- this.traversalsByStartAs.put(startAs, l2);
- }
- l2.add(wrapper);
- }
-
- // given all the wrapped traversals, determine bad patterns in the set and throw exceptions if not solvable
- private void checkSolvability() {
- final Set<String> pathSet = new HashSet<>();
- final Stack<String> stack = new Stack<>();
- stack.push(this.startLabel);
- int countTraversals = 0;
- while (!stack.isEmpty()) {
- final String outAs = stack.peek();
- if (pathSet.contains(outAs)) {
- stack.pop();
- pathSet.remove(outAs);
- } else {
- pathSet.add(outAs);
- final List<TraversalWrapper<S, S>> l = traversalsByStartAs.get(outAs);
- if (null != l) {
- for (final TraversalWrapper<S, S> tw : l) {
- countTraversals++;
- if (pathSet.contains(tw.endLabel)) {
- throw new IllegalArgumentException("The provided traversal set contains a cycle due to '"
- + tw.endLabel + '\'');
- }
- stack.push(tw.endLabel);
- }
- }
- }
- }
-
- int totalTraversals = 0;
- for (List<TraversalWrapper<S, S>> l : this.traversalsByStartAs.values()) {
- totalTraversals += l.size();
- }
-
- if (countTraversals < totalTraversals) {
- throw new IllegalArgumentException("The provided traversal set contains unreachable as-label(s)");
- }
- }
-
- private static void checkAs(final String as) {
- // note: this won't happen so long as the anon prefix is the same as Traversal.UNDERSCORE
- if (isAnonymousAs(as)) {
- throw new IllegalArgumentException("The step named '" + as + "' uses reserved prefix '"
- + ANON_LABEL_PREFIX + '\'');
- }
- }
-
- private static boolean isAnonymousAs(final String as) {
- return as.startsWith(ANON_LABEL_PREFIX);
- }
-
- private String createAnonymousAs() {
- return ANON_LABEL_PREFIX + ++this.anonLabelCounter;
- }
-
- /**
- * Directly applies this match query to a sequence of inputs
- *
- * @param inputs a sequence of inputs
- * @return an enumerator over all solutions
- */
- public Enumerator<S> solveFor(final Iterator<S> inputs) {
- return solveFor(startLabel, inputs);
- }
-
- private Enumerator<S> solveFor(final String localStartAs,
- final Iterator<S> inputs) {
- List<TraversalWrapper<S, S>> outs = traversalsByStartAs.get(localStartAs);
- if (null == outs) {
- // no out-traversals from here; just enumerate the values bound to localStartAs
- return isAnonymousAs(localStartAs)
- ? new SimpleEnumerator<>(localStartAs, inputs)
- : new IteratorEnumerator<>(localStartAs, inputs);
- } else {
- // for each value bound to localStartAs, feed it into all out-traversals in parallel and join the results
- return new SerialEnumerator<>(localStartAs, inputs, o -> {
- Enumerator<S> result = null;
- Set<String> leftLabels = new HashSet<>();
-
- for (TraversalWrapper<S, S> w : outs) {
- TraversalUpdater<S, S> updater
- = new TraversalUpdater<>(w, IteratorUtils.of(o), currentStart, this.getId());
-
- Set<String> rightLabels = new HashSet<>();
- addVariables(w.endLabel, rightLabels);
- Enumerator<S> ie = solveFor(w.endLabel, updater);
- result = null == result ? ie : crossJoin(result, ie, leftLabels, rightLabels);
- leftLabels.addAll(rightLabels);
- }
-
- return result;
- });
- }
- }
-
- private static <T> Enumerator<T> crossJoin(final Enumerator<T> left,
- final Enumerator<T> right,
- final Set<String> leftLabels,
- final Set<String> rightLabels) {
- Set<String> shared = new HashSet<>();
- for (String s : rightLabels) {
- if (leftLabels.contains(s)) {
- shared.add(s);
- }
- }
-
- Enumerator<T> cj = new CrossJoinEnumerator<>(left, right);
- return shared.size() > 0 ? new InnerJoinEnumerator<>(cj, shared) : cj;
- }
-
- // recursively add all non-anonymous variables from a starting point in the query
- private void addVariables(final String localStartAs,
- final Set<String> variables) {
- if (!isAnonymousAs(localStartAs)) {
- variables.add(localStartAs);
- }
-
- List<TraversalWrapper<S, S>> outs = traversalsByStartAs.get(localStartAs);
- if (null != outs) {
- for (TraversalWrapper<S, S> w : outs) {
- String endAs = w.endLabel;
- if (!variables.contains(endAs)) {
- addVariables(endAs, variables);
- }
- }
- }
- }
-
- // applies a visitor, skipping anonymous variables
- static <T> void visit(final String name,
- final T value,
- final BiConsumer<String, T> visitor) {
- if (!isAnonymousAs(name)) {
- visitor.accept(name, value);
- }
- }
-
- /**
- * Computes and applies a new query plan based on gathered statistics about traversal inputs and outputs.
- */
- // note: optimize() is never called from within a solution iterator, as it changes the query plan
- public void optimize() {
- optimizeAt(startLabel);
- }
-
- private void optimizeAt(final String outAs) {
- List<TraversalWrapper<S, S>> outs = traversalsByStartAs.get(outAs);
- if (null != outs) {
- for (TraversalWrapper<S, S> t : outs) {
- optimizeAt(t.endLabel);
- updateOrderingFactor(t);
- }
- Collections.sort(outs);
- }
- }
-
- private double findCost(final TraversalWrapper<S, S> root) {
- double bf = root.findBranchFactor();
- return bf + findCost(root.endLabel, root.findBranchFactor());
- }
-
- private double findCost(final String outAs,
- final double branchFactor) {
- double bf = branchFactor;
-
- double cost = 0;
-
- List<TraversalWrapper<S, S>> outs = traversalsByStartAs.get(outAs);
- if (null != outs) {
- for (TraversalWrapper<S, S> child : outs) {
- cost += bf * findCost(child);
- bf *= child.findBranchFactor();
- }
- }
-
- return cost;
- }
-
- /**
- * @param outLabel the out-label of one or more traversals in the query
- * @return the expected cost, in the current query plan, of applying the branch of the query plan at
- * the given out-label to one start value
- */
- public double findCost(final String outLabel) {
- return findCost(outLabel, 1.0);
- }
-
- private void updateOrderingFactor(final TraversalWrapper<S, S> w) {
- w.orderingFactor = ((w.findBranchFactor() - 1) / findCost(w));
- }
-
- @Override
- public List<Traversal<?,?>> getLocalChildren() {
- return this.traversals;
- }
-
- @Override
- public Scope recommendNextScope() {
- return Scope.local;
- }
-
- @Override
- public void setScope(final Scope scope) {
-
- }
-
- @Override
- public Scope getScope() {
- return Scope.local;
- }
-
- /**
- * A wrapper for a traversal in a query which maintains statistics about the traversal as
- * it consumes inputs and produces outputs.
- * The "branch factor" of the traversal is an important factor in determining its place in the query plan.
- */
- // note: input and output counts are never "refreshed".
- // The position of a traversal in a query never changes, although its priority / likelihood of being executed does.
- // Priority in turn affects branch factor.
- // However, with sufficient inputs and optimizations,the branch factor is expected to converge on a stable value.
- public static class TraversalWrapper<A, B> implements Comparable<TraversalWrapper<A, B>> {
- private final Traversal<A, B> traversal;
- private final String startLabel, endLabel;
- private int totalInputs = 0;
- private int totalOutputs = 0;
- private double orderingFactor;
-
- public TraversalWrapper(final Traversal<A, B> traversal,
- final String startLabel,
- final String endLabel) {
- this.traversal = traversal;
- this.startLabel = startLabel;
- this.endLabel = endLabel;
- }
-
- public void incrementInputs() {
- this.totalInputs++;
- }
-
- public void incrementOutputs(int outputs) {
- this.totalOutputs += outputs;
- }
-
- // TODO: take variance into account, to avoid penalizing traversals for early encounters with super-inputs,
- // or simply for never having been tried
- public double findBranchFactor() {
- return 0 == this.totalInputs ? 1 : this.totalOutputs / ((double) this.totalInputs);
- }
-
- @Override
- public int compareTo(final TraversalWrapper<A, B> other) {
- return ((Double) this.orderingFactor).compareTo(other.orderingFactor);
- }
-
- public Traversal<A, B> getTraversal() {
- return this.traversal;
- }
-
- public void reset() {
- this.traversal.asAdmin().reset();
- }
-
- @Override
- public String toString() {
- return this.traversal.toString();
- //return "[" + this.startLabel + "->" + this.endLabel + "," + findBranchFactor() + ","
- // + this.totalInputs + "," + this.totalOutputs + "," + this.traversal + "]";
- }
- }
-
- /**
- * A helper object which wraps a traversal, submitting starts and counting results per start
- */
- public static class TraversalUpdater<A, B> implements Iterator<B> {
- private final TraversalWrapper<A, B> w;
- private int outputs = -1;
-
- public TraversalUpdater(final TraversalWrapper<A, B> w,
- final Iterator<A> inputs,
- final Traverser<A> start,
- final String as) {
- this.w = w;
-
- Iterator<A> seIter = new SideEffectIterator<>(inputs, ignored -> {
- // only increment traversal input and output counts once an input
- // has been completely processed by the traversal
- if (-1 != outputs) {
- w.incrementInputs();
- w.incrementOutputs(outputs);
- }
- outputs = 0;
- });
- Iterator<Traverser<A>> starts = new MapIterator<>(seIter,
- o -> {
- final Traverser.Admin<A> traverser = ((Traverser.Admin<A>) start).split();
- traverser.set((A) o);
- return traverser;
- });
-
- w.reset();
-
- // with the traversal "empty" and ready for re-use, add new starts
- w.traversal.asAdmin().addStarts(starts);
- }
-
- // note: may return true after first returning false (inheriting this behavior from e.g. DefaultTraversal)
- @Override
- public boolean hasNext() {
- return w.traversal.hasNext();
- }
-
- @Override
- public B next() {
- outputs++;
- B b = w.traversal.next();
-
- // immediately check hasNext(), possibly updating the traverser's statistics
- // even if we otherwise abandon the iterator
- w.traversal.hasNext();
-
- return b;
- }
- }
-
- // an iterator which executes a side-effect the first time hasNext() is called before a next()
- private static class SideEffectIterator<T> implements Iterator<T> {
- private final Consumer onHasNext;
- private final Iterator<T> baseIterator;
- private boolean ready = true;
-
- private SideEffectIterator(final Iterator<T> baseIterator,
- final Consumer onHasNext) {
- this.onHasNext = onHasNext;
- this.baseIterator = baseIterator;
- }
-
- @Override
- public boolean hasNext() {
- if (this.ready) {
- this.onHasNext.accept(null);
- this.ready = false;
- }
- return this.baseIterator.hasNext();
- }
-
- @Override
- public T next() {
- T value = this.baseIterator.next();
- this.ready = true;
- return value;
- }
- }
-
- private static class MapIterator<A, B> implements Iterator<B> {
- private final Function<A, B> map;
- private final Iterator<A> baseIterator;
-
- public MapIterator(final Iterator<A> baseIterator, final Function<A, B> map) {
- this.map = map;
- this.baseIterator = baseIterator;
- }
-
- @Override
- public boolean hasNext() {
- return this.baseIterator.hasNext();
- }
-
- @Override
- public B next() {
- return this.map.apply(this.baseIterator.next());
- }
- }
-}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SerialEnumerator.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SerialEnumerator.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SerialEnumerator.java
deleted file mode 100644
index e4f8bef..0000000
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SerialEnumerator.java
+++ /dev/null
@@ -1,119 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.tinkerpop.gremlin.process.traversal.step.map.match;
-
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-import java.util.function.BiConsumer;
-import java.util.function.Function;
-
-/**
- * An enumerator which consumes values from an iterator and maps each value to a secondary enumerator
- * (for example, a join)
- * Enumerated indices cover all solutions in the secondary enumerators,
- * in ascending order according to the value iterator and the enumerators' own indices.
- *
- * @author Joshua Shinavier (http://fortytwo.net)
- */
-public class SerialEnumerator<T> implements Enumerator<T> {
- private final String name;
- private Iterator<T> iterator;
- private final Function<T, Enumerator<T>> constructor;
- private final List<Enumerator<T>> memory = new ArrayList<>();
- private final List<T> values = new ArrayList<>();
-
- // TODO: this only assigned, not accessed until the efficient implementation of size() is restored
- private int completedEnumsSize = 0;
-
- public SerialEnumerator(final String name,
- final Iterator<T> iterator,
- final Function<T, Enumerator<T>> constructor) {
- this.name = name;
- this.iterator = iterator;
- this.constructor = constructor;
- }
-
- public int size() {
- // TODO: restore the more efficient implementation of size() while taking into account that
- // traversal iterators such as DefaultTraversal may return hasNext=true after first returning hasNext=false
- /*
- int size = completedEnumsSize;
- if (!sideEffects.isEmpty()) {
- size += sideEffects.get(sideEffects.size() - 1).size();
- }
- return size;
- */
-
- //*
- int size = 0;
- for (Enumerator<T> e : memory) size += e.size();
- return size;
- //*/
- }
-
- // note: *not* intended for random access; use binary search if this is ever needed
- public boolean visitSolution(final int index,
- final BiConsumer<String, T> visitor) {
- int totalSize = 0;
- int memIndex = 0;
- while (true) {
- if (memIndex < memory.size()) {
- Enumerator<T> e = memory.get(memIndex);
-
- if (e.visitSolution(index - totalSize, visitor)) {
- // additionally, bind the value stored in this enumerator
- MatchStep.visit(name, values.get(memIndex), visitor);
-
- return true;
- } else {
- totalSize += e.size();
- memIndex++;
- }
- } else {
- if (null == iterator) {
- return false;
- } else if (!iterator.hasNext()) {
- // free up memory as soon as possible
- iterator = null;
- return false;
- }
-
- if (!memory.isEmpty()) {
- int lastSize = memory.get(memIndex - 1).size();
-
- // first remove the head enumeration if it exists and is empty
- // (only the head will ever be empty, avoiding wasted space)
- if (0 == lastSize) {
- memIndex--;
- memory.remove(memIndex);
- values.remove(memIndex);
- } else {
- completedEnumsSize += lastSize;
- }
- }
-
- T value = iterator.next();
- values.add(value);
- Enumerator<T> e = constructor.apply(value);
- memory.add(memory.size(), e);
- }
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SimpleEnumerator.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SimpleEnumerator.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SimpleEnumerator.java
deleted file mode 100644
index eb5da9c..0000000
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/match/SimpleEnumerator.java
+++ /dev/null
@@ -1,66 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package org.apache.tinkerpop.gremlin.process.traversal.step.map.match;
-
-import java.util.Iterator;
-import java.util.function.BiConsumer;
-
-/**
- * An enumerator of at most one element
- *
- * @author Joshua Shinavier (http://fortytwo.net)
- */
-public class SimpleEnumerator<T> implements Enumerator<T> {
-
- private final String name;
- private Iterator<T> iterator;
- private T element;
-
- public SimpleEnumerator(final String name,
- final Iterator<T> iterator) {
- this.name = name;
- this.iterator = iterator;
- }
-
- @Override
- public int size() {
- return null == element ? 0 : 1;
- }
-
- @Override
- public boolean visitSolution(int index, BiConsumer<String, T> visitor) {
- if (0 != index) {
- return false;
- }
-
- if (null != iterator) {
- if (iterator.hasNext()) {
- element = iterator.next();
- }
- iterator = null;
- }
-
- if (null != element) {
- MatchStep.visit(name, element, visitor);
- return true;
- }
-
- return false;
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchWhereStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchWhereStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchWhereStrategy.java
index 3adee58..8774212 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchWhereStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchWhereStrategy.java
@@ -22,8 +22,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.filter.exp.XMatchStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.match.MatchStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
@@ -58,18 +57,18 @@ public final class MatchWhereStrategy extends AbstractTraversalStrategy<Traversa
@Override
public void apply(final Traversal.Admin<?, ?> traversal) {
- if (!TraversalHelper.hasStepOfClass(XMatchStep.class, traversal))
+ if (!TraversalHelper.hasStepOfClass(MatchStep.class, traversal))
return;
// pull out match(as("a").has().has()) to has().has().match() in order to allow vendors to leverages has-containers for index lookups
- TraversalHelper.getStepsOfClass(XMatchStep.class, traversal).forEach(matchStep -> {
+ TraversalHelper.getStepsOfClass(MatchStep.class, traversal).forEach(matchStep -> {
if (matchStep.getStartKey().isPresent()) {
- ((XMatchStep<?, ?>) matchStep).getGlobalChildren().stream().collect(Collectors.toList()).forEach(conjunction -> {
- if (conjunction.getStartStep() instanceof XMatchStep.XMatchStartStep) {
- ((XMatchStep<?, ?>.XMatchStartStep) conjunction.getStartStep()).getSelectKey().ifPresent(selectKey -> {
+ ((MatchStep<?, ?>) matchStep).getGlobalChildren().stream().collect(Collectors.toList()).forEach(conjunction -> {
+ if (conjunction.getStartStep() instanceof MatchStep.MatchStartStep) {
+ ((MatchStep.MatchStartStep) conjunction.getStartStep()).getSelectKey().ifPresent(selectKey -> {
if (selectKey.equals(matchStep.getStartKey().get()) && !conjunction.getSteps().stream()
- .filter(step -> !(step instanceof XMatchStep.XMatchStartStep) &&
- !(step instanceof XMatchStep.XMatchEndStep) &&
+ .filter(step -> !(step instanceof MatchStep.MatchStartStep) &&
+ !(step instanceof MatchStep.MatchEndStep) &&
!(step instanceof HasStep))
.findAny()
.isPresent() && !(matchStep.getPreviousStep() instanceof EmptyStep)) {
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
index a390e37..783b3eb 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/verification/ComputerVerificationStrategy.java
@@ -33,7 +33,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.DedupGlobalSte
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TailGlobalStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.OrderGlobalStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.match.MatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.GraphStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.InjectStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphStep;
@@ -58,7 +57,7 @@ public final class ComputerVerificationStrategy extends AbstractTraversalStrateg
private static final ComputerVerificationStrategy INSTANCE = new ComputerVerificationStrategy();
private static final Set<Class<?>> UNSUPPORTED_STEPS = new HashSet<>(Arrays.asList(
- InjectStep.class, MatchStep.class, Mutating.class, SubgraphStep.class
+ InjectStep.class, Mutating.class, SubgraphStep.class
));
private ComputerVerificationStrategy() {
@@ -94,7 +93,7 @@ public final class ComputerVerificationStrategy extends AbstractTraversalStrateg
if ((step instanceof ReducingBarrierStep || step instanceof SupplyingBarrierStep || step instanceof OrderGlobalStep || step instanceof RangeGlobalStep || step instanceof TailGlobalStep || step instanceof DedupGlobalStep) && (step != endStep || !(traversal.getParent() instanceof EmptyStep)))
throw new ComputerVerificationException("Global traversals on GraphComputer may not contain mid-traversal barriers: " + step, traversal);
- if(step instanceof DedupGlobalStep && !((DedupGlobalStep) step).getLocalChildren().isEmpty())
+ if (step instanceof DedupGlobalStep && !((DedupGlobalStep) step).getLocalChildren().isEmpty())
throw new ComputerVerificationException("Global traversals on GraphComputer may not contain by()-projecting de-duplication steps: " + step, traversal);
if (step instanceof TraversalParent) {
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
----------------------------------------------------------------------
diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
index 8d3be3d..f365c18 100644
--- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
+++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy
@@ -88,14 +88,14 @@ public abstract class GroovyMatchTest {
}
@Override
- public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_created_b__b_0created_aX() {
+ public Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_created_b__b_0created_aX() {
g.V().match('a',
__.as('a').out('created').as('b'),
__.as('b').in('created').as('a'))
}
@Override
- public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_knows_b__c_knows_bX() {
+ public Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_knows_b__c_knows_bX() {
return g.V().match('a', __.as('a').out('knows').as('b'),
__.as('c').out('knows').as('b'));
}
@@ -167,8 +167,8 @@ public abstract class GroovyMatchTest {
.select('a', 'c').by('name')
}
- /*@Override
- public Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_selectXnameX() {
+ @Override
+ public Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_select_byXnameX() {
g.V.match('a',
__.as('a').out('created').as('b'),
__.as('c').out('created').as('b')).select { it.value('name') }
@@ -179,7 +179,7 @@ public abstract class GroovyMatchTest {
g.V.out.out.match('a',
__.as('b').out('created').as('a'),
__.as('c').out('knows').as('b')).select('c').out('knows').name
- }*/
+ }
}
}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
index 9e64522..a209c92 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/AbstractGremlinProcessTest.java
@@ -75,7 +75,12 @@ public abstract class AbstractGremlinProcessTest extends AbstractGremlinTest {
public static <T> void checkResults(final List<T> expectedResults, final Traversal<?, T> traversal) {
final List<T> results = traversal.toList();
assertFalse(traversal.hasNext());
- assertEquals("Checking result size", expectedResults.size(), results.size());
+ if(expectedResults.size() != results.size()) {
+ System.err.println("Expected results: " + expectedResults);
+ System.err.println("Actual results: " + results);
+ assertEquals("Checking result size", expectedResults.size(), results.size());
+ }
+
for (T t : results) {
if (t instanceof Map) {
assertTrue("Checking map result existence: " + t, expectedResults.stream().filter(e -> e instanceof Map).filter(e -> checkMap((Map) e, (Map) t)).findAny().isPresent());
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/2f802634/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
index 5e4dd1a..d1c2945 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java
@@ -21,27 +21,26 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.LoadGraphWith;
import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest;
import org.apache.tinkerpop.gremlin.process.GremlinProcessRunner;
+import org.apache.tinkerpop.gremlin.process.IgnoreEngine;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.match.*;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.MapHelper;
-import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_S_SE_SL_Traverser;
import org.apache.tinkerpop.gremlin.structure.T;
import org.apache.tinkerpop.gremlin.structure.Vertex;
-import org.junit.Ignore;
import org.junit.Test;
import org.junit.runner.RunWith;
-import java.util.*;
-import java.util.function.BiConsumer;
-import java.util.function.Function;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.GRATEFUL;
import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN;
+import static org.apache.tinkerpop.gremlin.process.traversal.P.neq;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as;
import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out;
-import static org.apache.tinkerpop.gremlin.process.traversal.P.neq;
import static org.junit.Assert.*;
/**
@@ -75,11 +74,11 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public abstract Traversal<Vertex, String> get_g_V_out_out_matchXa_0created_b__b_0knows_cX_selectXcX_outXcreatedX_name();
- // contains a cycle
- public abstract Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_created_b__b_0created_aX();
+ //TODO: with Traversal.reverse()
+ public abstract Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_created_b__b_0created_aX();
// contains an unreachable label
- public abstract Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_knows_b__c_knows_bX();
+ public abstract Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_knows_b__c_knows_bX();
// nested match()
public abstract Traversal<Vertex, Map<String, String>> get_g_V_matchXa_knows_b__b_created_lop__b_matchXa1_created_b1__b1_0created_c1X_selectXc1X_cX_selectXnameX();
@@ -99,23 +98,24 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public abstract Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__b_0created_cX_whereXa_neq_cX_selectXa_c_nameX();
//TODO: with Traversal.reverse()
- //public abstract Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_selectXnameX();
+ public abstract Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_select_byXnameX();
//TODO: with Traversal.reverse()
- // public abstract Traversal<Vertex, String> get_g_V_out_out_hasXname_rippleX_matchXb_created_a__c_knows_bX_selectXcX_outXknowsX_name();
+ public abstract Traversal<Vertex, String> get_g_V_out_out_hasXname_rippleX_matchXb_created_a__c_knows_bX_selectXcX_outXknowsX_name();
@Test
@LoadGraphWith(MODERN)
public void g_V_matchXa_out_bX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_out_bX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "lop")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "vadas")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "josh")).put("b", convertToVertex(graph, "ripple")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "josh")).put("b", convertToVertex(graph, "lop")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "peter")).put("b", convertToVertex(graph, "lop")));
+ checkResults(makeMapList(2,
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"),
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "vadas"),
+ "a", convertToVertex(graph, "josh"), "b", convertToVertex(graph, "ripple"),
+ "a", convertToVertex(graph, "josh"), "b", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "peter"), "b", convertToVertex(graph, "lop")),
+ traversal);
}
@Test
@@ -146,9 +146,9 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public void g_V_matchXa_knows_b__b_created_cX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_knows_b__b_created_cX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "lop")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "ripple")));
+ checkResults(makeMapList(3,
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"), "c", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"), "c", convertToVertex(graph, "ripple")), traversal);
}
@Test
@@ -156,9 +156,9 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public void g_V_matchXa_knows_b__a_created_cX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_knows_b__a_created_cX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "vadas")).put("c", convertToVertex(graph, "lop")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "lop")));
+ checkResults(makeMapList(3,
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "vadas"), "c", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"), "c", convertToVertex(graph, "lop")), traversal);
}
@Test
@@ -166,9 +166,9 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public void g_V_matchXd_0knows_a__d_hasXname_vadasX__a_knows_b__b_created_cX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXd_0knows_a__d_hasXname_vadasX__a_knows_b__b_created_cX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>().put("d", convertToVertex(graph, "vadas")).put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "lop")),
- new Bindings<Vertex>().put("d", convertToVertex(graph, "vadas")).put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "ripple")));
+ checkResults(makeMapList(4,
+ "d", convertToVertex(graph, "vadas"), "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"), "c", convertToVertex(graph, "lop"),
+ "d", convertToVertex(graph, "vadas"), "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "josh"), "c", convertToVertex(graph, "ripple")), traversal);
}
@Test
@@ -177,21 +177,26 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
final Traversal<Vertex, Map<String, String>> traversal = get_g_V_matchXa_created_b__a_repeatXoutX_timesX2XX_selectXab_nameX();
printTraversalForm(traversal);
assertTrue(traversal.hasNext());
- assertResults(Function.identity(), traversal, new Bindings<String>().put("a", "marko").put("b", "lop"));
+ checkResults(makeMapList(2,
+ "a", "marko", "b", "lop"), traversal);
}
@Test
@LoadGraphWith(MODERN)
+ // TODO: DEBATABLE RESULTS
public void g_V_matchXa_created_lop_b__b_0created_29_cX_whereXc_repeatXoutX_timesX2XX_selectXnameX() throws Exception {
final List<Traversal<Vertex, Map<String, String>>> traversals = Arrays.asList(
- get_g_V_matchXa_created_lop_b__b_0created_29_c__c_repeatXoutX_timesX2XX_selectXnameX(),
- get_g_V_matchXa_created_lop_b__b_0created_29_cX_whereXc_repeatXoutX_timesX2XX_selectXnameX());
+ get_g_V_matchXa_created_lop_b__b_0created_29_c__c_repeatXoutX_timesX2XX_selectXnameX());
+ //get_g_V_matchXa_created_lop_b__b_0created_29_cX_whereXc_repeatXoutX_timesX2XX_selectXnameX()); // todo: predicate traversals are local traversals?
traversals.forEach(traversal -> {
printTraversalForm(traversal);
- assertResults(Function.identity(), traversal,
- new Bindings<String>().put("a", "marko").put("b", "lop").put("c", "marko"),
- new Bindings<String>().put("a", "josh").put("b", "lop").put("c", "marko"),
- new Bindings<String>().put("a", "peter").put("b", "lop").put("c", "marko"));
+ checkResults(makeMapList(3,
+ "a", "marko", "b", "lop", "c", "marko",
+ "a", "marko", "b", "lop", "c", "marko",
+ "a", "josh", "b", "lop", "c", "marko",
+ "a", "josh", "b", "lop", "c", "marko",
+ "a", "peter", "b", "lop", "c", "marko",
+ "a", "peter", "b", "lop", "c", "marko"), traversal);
});
}
@@ -205,16 +210,27 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
assertFalse(traversal.hasNext());
}
- @Test(expected = IllegalArgumentException.class)
+ @Test
@LoadGraphWith(MODERN)
public void g_V_matchXa_created_b__b_0created_aX() {
- get_g_V_matchXa_created_b__b_0created_aX();
+ final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_created_b__b_0created_aX();
+ printTraversalForm(traversal);
+ checkResults(makeMapList(2,
+ "a", convertToVertex(graph, "marko"), "b", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "josh"), "b", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "peter"), "b", convertToVertex(graph, "lop"),
+ "a", convertToVertex(graph, "josh"), "b", convertToVertex(graph, "ripple")),
+ traversal);
+
}
- @Test(expected = IllegalArgumentException.class)
+ // TODO: this test requires Traversal.reverse()
+ @Test(expected = IllegalStateException.class)
@LoadGraphWith(MODERN)
public void g_V_matchXa_knows_b__c_knows_bX() {
- get_g_V_matchXa_knows_b__c_knows_bX();
+ final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_knows_b__c_knows_bX();
+ printTraversalForm(traversal);
+ traversal.iterate();
}
@Test
@@ -222,69 +238,39 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public void g_V_matchXa_knows_b__b_created_lop__b_matchXa1_created_b1__b1_0created_c1X_selectXc1X_cX_selectXnameX() throws Exception {
final Traversal<Vertex, Map<String, String>> traversal = get_g_V_matchXa_knows_b__b_created_lop__b_matchXa1_created_b1__b1_0created_c1X_selectXc1X_cX_selectXnameX();
printTraversalForm(traversal);
- assertResults(Function.identity(), traversal,
- new Bindings<String>().put("a", "marko").put("b", "josh").put("c", "josh"),
- new Bindings<String>().put("a", "marko").put("b", "josh").put("c", "josh"), // expected duplicate: two paths to this solution
- new Bindings<String>().put("a", "marko").put("b", "josh").put("c", "marko"),
- new Bindings<String>().put("a", "marko").put("b", "josh").put("c", "peter"));
+ checkResults(makeMapList(3,
+ "a", "marko", "b", "josh", "c", "josh",
+ "a", "marko", "b", "josh", "c", "josh", // expected duplicate: two paths to this solution
+ "a", "marko", "b", "josh", "c", "marko",
+ "a", "marko", "b", "josh", "c", "peter"), traversal);
}
- /* TODO: this test requires Traversal.reverse()
- @Test
+ // TODO: this test requires Traversal.reverse()
+ @Test(expected = IllegalStateException.class)
@LoadGraphWith(MODERN)
public void g_V_matchXa_created_b__c_created_bX_selectXnameX() throws Exception {
- final Traversal<Vertex, Map<String, String>> traversal = get_g_V_matchXa_created_b__c_created_bX_selectXnameX();
+ final Traversal<Vertex, Map<String, String>> traversal = get_g_V_matchXa_created_b__c_created_bX_select_byXnameX();
printTraversalForm(traversal);
- assertTrue(traversal.hasNext());
- final Map<String, Long> countMap = new HashMap<>();
- int counter = 0;
- while (traversal.hasNext()) {
- counter++;
- final Map<String, String> bindings = traversal.next();
- // TODO: c is not being bound
- // assertEquals(3, bindings.size());
- assertEquals("lop", bindings.get("b"));
- MapHelper.incr(countMap, bindings.get("a") + ":" + bindings.get("c"), 1l);
- }
- // TODO: without 'c' binding, cant check results
- // assertEquals(Long.valueOf(1), countMap.get("marko:marko"));
- //assertEquals(Long.valueOf(1), countMap.get("marko:josh"));
- //assertEquals(Long.valueOf(1), countMap.get("marko:peter"));
- //assertEquals(Long.valueOf(1), countMap.get("josh:marko"));
- //assertEquals(Long.valueOf(1), countMap.get("josh:josh"));
- //assertEquals(Long.valueOf(1), countMap.get("josh:peter"));
- //assertEquals(Long.valueOf(1), countMap.get("peter:marko"));
- //assertEquals(Long.valueOf(1), countMap.get("peter:josh"));
- //assertEquals(Long.valueOf(1), countMap.get("peter:peter"));
- //assertEquals(countMap.size(), 9);
- //assertEquals(9, counter);
- assertFalse(traversal.hasNext());
+ traversal.iterate();
}
- */
- /* TODO: this test requires Traversal.reverse()
- @Test
+ // TODO: this test requires Traversal.reverse()
+ @Test(expected = IllegalStateException.class)
@LoadGraphWith(MODERN)
public void g_V_out_out_hasXname_rippleX_matchXb_created_a__c_knows_bX_selectXcX_outXknowsX_name() throws Exception {
- // TODO: Doesn't work, only bindings to 'a' in binding set.
final Traversal<Vertex, String> traversal = get_g_V_out_out_hasXname_rippleX_matchXb_created_a__c_knows_bX_selectXcX_outXknowsX_name();
printTraversalForm(traversal);
- assertTrue(traversal.hasNext());
- final List<String> results = traversal.toList();
- assertEquals(2, results.size());
- assertTrue(results.contains("josh"));
- assertTrue(results.contains("vadas"));
+ traversal.iterate();
}
- */
@Test
@LoadGraphWith(GRATEFUL)
public void g_V_matchXa_hasXname_GarciaX__a_0writtenBy_b__a_0sungBy_bX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_hasXname_GarciaX__a_0writtenBy_b__a_0sungBy_bX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>().put("a", convertToVertex(graph, "Garcia")).put("b", convertToVertex(graph, "CREAM PUFF WAR")),
- new Bindings<Vertex>().put("a", convertToVertex(graph, "Garcia")).put("b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT")));
+ checkResults(makeMapList(2,
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CREAM PUFF WAR"),
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT")), traversal);
}
@Test
@@ -292,348 +278,47 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
public void g_V_matchXa_0sungBy_b__a_0sungBy_c__b_writtenBy_d__c_writtenBy_e__d_hasXname_George_HarisonX__e_hasXname_Bob_MarleyXX() throws Exception {
final Traversal<Vertex, Map<String, Vertex>> traversal = get_g_V_matchXa_0sungBy_b__a_0sungBy_c__b_writtenBy_d__c_writtenBy_e__d_hasXname_George_HarisonX__e_hasXname_Bob_MarleyXX();
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Garcia"))
- .put("b", convertToVertex(graph, "I WANT TO TELL YOU"))
- .put("c", convertToVertex(graph, "STIR IT UP"))
- .put("d", convertToVertex(graph, "George_Harrison"))
- .put("e", convertToVertex(graph, "Bob_Marley")));
+ checkResults(makeMapList(5,
+ "a", convertToVertex(graph, "Garcia"),
+ "b", convertToVertex(graph, "I WANT TO TELL YOU"),
+ "c", convertToVertex(graph, "STIR IT UP"),
+ "d", convertToVertex(graph, "George_Harrison"),
+ "e", convertToVertex(graph, "Bob_Marley")), traversal);
}
@Test
@LoadGraphWith(MODERN)
public void g_V_matchXa_created_b__b_0created_cX_whereXa_neq_cX_selectXa_c_nameX() throws Exception {
final Traversal<Vertex, Map<String, String>> traversal = get_g_V_matchXa_created_b__b_0created_cX_whereXa_neq_cX_selectXa_c_nameX();
- assertResults(Function.identity(), traversal,
- new Bindings<String>().put("a", "marko").put("c", "josh"),
- new Bindings<String>().put("a", "marko").put("c", "peter"),
- new Bindings<String>().put("a", "josh").put("c", "marko"),
- new Bindings<String>().put("a", "josh").put("c", "peter"),
- new Bindings<String>().put("a", "peter").put("c", "marko"),
- new Bindings<String>().put("a", "peter").put("c", "josh"));
+ checkResults(makeMapList(2,
+ "a", "marko", "c", "josh",
+ "a", "marko", "c", "peter",
+ "a", "josh", "c", "marko",
+ "a", "josh", "c", "peter",
+ "a", "peter", "c", "marko",
+ "a", "peter", "c", "josh"), traversal);
}
@Test
- @Ignore
@LoadGraphWith(GRATEFUL)
public void g_V_matchXa_0sungBy_b__a_0writtenBy_c__b_writtenBy_d__c_sungBy_d__d_hasXname_GarciaXX() throws Exception {
final List<Traversal<Vertex, Map<String, Vertex>>> traversals = Arrays.asList(
- get_g_V_matchXa_0sungBy_b__a_0writtenBy_c__b_writtenBy_d__c_sungBy_d__d_hasXname_GarciaXX(),
- get_g_V_matchXa_0sungBy_b__a_0writtenBy_c__b_writtenBy_dX_whereXc_sungBy_dX_whereXd_hasXname_GarciaXX());
+ get_g_V_matchXa_0sungBy_b__a_0writtenBy_c__b_writtenBy_d__c_sungBy_d__d_hasXname_GarciaXX());
+ //get_g_V_matchXa_0sungBy_b__a_0writtenBy_c__b_writtenBy_dX_whereXc_sungBy_dX_whereXd_hasXname_GarciaXX()); // TODO: the where() is trying to get Garcia's name. Why is ComputerVerificationStrategy allowing this?
traversals.forEach(traversal -> {
printTraversalForm(traversal);
- assertResults(vertexToStr, traversal,
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Garcia"))
- .put("b", convertToVertex(graph, "CREAM PUFF WAR"))
- .put("c", convertToVertex(graph, "CREAM PUFF WAR"))
- .put("d", convertToVertex(graph, "Garcia")),
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Garcia"))
- .put("b", convertToVertex(graph, "CREAM PUFF WAR"))
- .put("c", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"))
- .put("d", convertToVertex(graph, "Garcia")),
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Garcia"))
- .put("b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"))
- .put("c", convertToVertex(graph, "CREAM PUFF WAR"))
- .put("d", convertToVertex(graph, "Garcia")),
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Garcia"))
- .put("b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"))
- .put("c", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"))
- .put("d", convertToVertex(graph, "Garcia")),
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Grateful_Dead"))
- .put("b", convertToVertex(graph, "CANT COME DOWN"))
- .put("c", convertToVertex(graph, "DOWN SO LONG"))
- .put("d", convertToVertex(graph, "Garcia")),
- new Bindings<Vertex>()
- .put("a", convertToVertex(graph, "Grateful_Dead"))
- .put("b", convertToVertex(graph, "THE ONLY TIME IS NOW"))
- .put("c", convertToVertex(graph, "DOWN SO LONG"))
- .put("d", convertToVertex(graph, "Garcia")));
+ checkResults(makeMapList(4,
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CREAM PUFF WAR"), "c", convertToVertex(graph, "CREAM PUFF WAR"), "d", convertToVertex(graph, "Garcia"),
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CREAM PUFF WAR"), "c", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"), "d", convertToVertex(graph, "Garcia"),
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"), "c", convertToVertex(graph, "CREAM PUFF WAR"), "d", convertToVertex(graph, "Garcia"),
+ "a", convertToVertex(graph, "Garcia"), "b", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"), "c", convertToVertex(graph, "CRYPTICAL ENVELOPMENT"), "d", convertToVertex(graph, "Garcia"),
+ "a", convertToVertex(graph, "Grateful_Dead"), "b", convertToVertex(graph, "CANT COME DOWN"), "c", convertToVertex(graph, "DOWN SO LONG"), "d", convertToVertex(graph, "Garcia"),
+ "a", convertToVertex(graph, "Grateful_Dead"), "b", convertToVertex(graph, "THE ONLY TIME IS NOW"), "c", convertToVertex(graph, "DOWN SO LONG"), "d", convertToVertex(graph, "Garcia")), traversal);
});
}
-
- /* TODO: is it necessary to implement each of these traversals three times?
- @Test
- @LoadGraphWith(MODERN)
- public void testTraversalUpdater() throws Exception {
- assertBranchFactor(
- 2.0,
- as("a").out("knows").as("b"),
- new SingleIterator<>(g.V(1)));
-
- assertBranchFactor(
- 0.0,
- as("a").out("foo").as("b"),
- new SingleIterator<>(g.V(1)));
-
- assertBranchFactor(
- 7.0,
- as("a").both().both().as("b"),
- new SingleIterator<>(g.V(1)));
-
- assertBranchFactor(
- 0.5,
- as("a").outV().has("name", "marko").as("b"),
- g.E());
- }
- */
-
- @Test
- @LoadGraphWith(MODERN)
- public void testOptimization() throws Exception {
- MatchStep<Object, Object> query;
- Iterator iter;
-
- query = new MatchStep<>(g.V().asAdmin(), "d",
- as("d").in("knows").as("a"),
- as("d").has("name", "vadas"),
- as("a").out("knows").as("b"),
- as("b").out("created").as("c"));
- iter = g.V();
- query.optimize();
- //System.out.println(query.summarize());
-
- // c costs nothing (no outgoing traversals)
- assertEquals(0.0, query.findCost("c"), 0);
- // b-created->c has a cost equal to its branch factor, 1.0
- // b has only one outgoing traversal, b-created->c, so its total cost is 1.0
- assertEquals(1.0, query.findCost("b"), 0);
- // the cost of a-knows->b is its branch factor (1.0) plus the branch factor times the cost of b-created->c (1.0), so 2.0
- // a has only one outgoing traversal, a-knows->b, so its total cost is 2.0
- assertEquals(2.0, query.findCost("a"), 0);
- // the cost of d<-knows-a is its branch factor (1.0) plus the branch factor times the cost of a-knows->b (2.0), so 3.0
- // the cost of d->has(name,vadas) is its branch factor (1.0)
- // the total cost of d is the cost of its first traversal times the branch factor of the first times the cost of the second,
- // or 3.0 + 1.0*1.0 = 4.0
- assertEquals(4.0, query.findCost("d"), 0);
-
- // apply the query to the graph, gathering non-trivial branch factors
- assertResults(query.solveFor(iter),
- new Bindings<>().put("d", convertToVertex(graph, "vadas")).put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "lop")),
- new Bindings<>().put("d", convertToVertex(graph, "vadas")).put("a", convertToVertex(graph, "marko")).put("b", convertToVertex(graph, "josh")).put("c", convertToVertex(graph, "ripple")));
- query.optimize();
- //System.out.println(query.summarize());
-
- // c still costs nothing (no outgoing traversals)
- assertEquals(0.0, query.findCost("c"), 0);
- // b-created->c still has a branch factor of 1.0, as we have put two items in (josh and vadas) and gotten two out (lop and ripple)
- // b has only one outgoing traversal, b-created->c, so its total cost is 1.0
- /* TODO: adjust and restore
- assertEquals(1.0, query.findCost("b"), 0);
- // a-knows->b now has a branch factor of 2.0 -- we put in marko and got out josh and vadas
- // the cost of a-knows->b is its branch factor (2.0) plus the branch factor times the cost of b-created->c (1.0), so 4.0
- // a has only one outgoing traversal, a-knows->b, so its total cost is 4.0
- assertEquals(4.0, query.findCost("a"), 0);
- // d<-knows-a has a branch factor of 1/6 -- we put in all six vertices and got out marko
- // we get out marko only once, because d-name->"vadas" is tried first and rules out all but one "d"
- // the cost of d<-knows-a is its branch factor (1/6) plus the branch factor times the cost of a-knows->b (4.0), so 5/6
- // since we optimized to put the has step first (it immediately eliminates most vertices),
- // the cost of d->has(name,vadas) is 1/6 -- we put in all six vertices and got out one
- // the total cost of d is the cost of its first traversal times the branch factor of the first times the cost of the second,
- // or 1/6 + 1/6*5/6 = 11/36
- */
- }
-
- // TODO: uncomment when query cycles are supported
- /*
- @Test
- @LoadGraphWith(MODERN)
- public void testCyclicPatterns() throws Exception {
- MatchStep<Object, Object> query;
- Iterator iter;
-
- iter = g.V();
- query = new MatchStep<>(g.V(), "a",
- as("a").out("uses").as("b"),
- as("b").out("dependsOn").as("c"),
- as("c").in("created").as("a"));
-
- assertResults(query.solve(iter),
- new Bindings<>().put("a", "v[1]").put("b", "v[10]").put("c", "v[11]"));
- }
- */
-
- @Test
- public void testIteratorEnumerator() throws Exception {
- IteratorEnumerator<String> ie;
- final Map<String, String> map = new HashMap<>();
- BiConsumer<String, String> visitor = map::put;
-
- ie = new IteratorEnumerator<>("a", new LinkedList<String>() {{
- add("foo");
- add("bar");
- }}.iterator());
- assertEquals(0, ie.size());
- assertTrue(ie.visitSolution(0, visitor));
- assertEquals(1, ie.size());
- assertEquals(1, map.size());
- assertEquals("foo", map.get("a"));
- map.clear();
- assertTrue(ie.visitSolution(1, visitor));
- assertEquals(2, ie.size());
- assertEquals(1, map.size());
- assertEquals("bar", map.get("a"));
- map.clear();
- assertFalse(ie.visitSolution(2, visitor));
- assertEquals(2, ie.size());
- assertEquals(0, map.size());
- // revisit previous solutions at random
- assertTrue(ie.visitSolution(1, visitor));
- assertEquals(2, ie.size());
- assertEquals(1, map.size());
- assertEquals("bar", map.get("a"));
-
- // empty enumerator
- ie = new IteratorEnumerator<>("a", new LinkedList<String>() {{
- }}.iterator());
- map.clear();
- assertEquals(0, ie.size());
- assertFalse(ie.visitSolution(0, visitor));
- assertEquals(0, ie.size());
- assertEquals(0, map.size());
- }
-
- @Test
- public void testCrossJoin() throws Exception {
- String[] a1 = new String[]{"a", "b", "c"};
- String[] a2 = new String[]{"1", "2", "3", "4"};
- String[] a3 = new String[]{"@", "#"};
-
- Enumerator<String> e1 = new IteratorEnumerator<>("letter", Arrays.asList(a1).iterator());
- Enumerator<String> e2 = new IteratorEnumerator<>("number", Arrays.asList(a2).iterator());
- Enumerator<String> e3 = new IteratorEnumerator<>("punc", Arrays.asList(a3).iterator());
-
- Enumerator<String> e1e2 = new CrossJoinEnumerator<>(e1, e2);
- Enumerator<String> e2e1 = new CrossJoinEnumerator<>(e2, e1);
- BiConsumer<String, String> visitor = (name, value) -> {
- System.out.println("\t" + name + ":\t" + value);
- };
- Enumerator<String> e1e2e3 = new CrossJoinEnumerator<>(e1e2, e3);
-
- Enumerator<String> result;
-
- result = e1e2;
- assertEquals(12, exhaust(result));
- assertEquals(12, result.size());
-
- result = e2e1;
- assertEquals(12, exhaust(result));
- assertEquals(12, result.size());
-
- result = e1e2e3;
- assertEquals(24, exhaust(result));
- assertEquals(24, result.size());
-
- /*
- int i = 0;
- while (result.visitSolution(i, visitor)) {
- System.out.println("solution #" + (i + 1) + "^^");
- i++;
- }
- */
- }
-
- /* TODO: uncomment when optimized cross-joins are available
- @Test
- public void testCrossJoinLaziness() throws Exception {
- List<Integer> value = new LinkedList<>();
- for (int j = 0; j < 1000; j++) {
- value.add(j);
- }
-
- int base = 3;
- List<Enumerator<Integer>> enums = new LinkedList<>();
- for (int k = 0; k < base; k++) {
- List<Integer> lNew = new LinkedList<>();
- lNew.addAll(value);
- Enumerator<Integer> ek = new IteratorEnumerator<>("" + (char) ('a' + k), lNew.iterator());
- enums.add(ek);
- }
-
- Enumerator<Integer> e = new NewCrossJoinEnumerator<>(enums);
-
- // we now have an enumerator of 5^3^10 elements
- EnumeratorIterator<Integer> iter = new EnumeratorIterator<>(e);
-
- int count = 0;
- // each binding set is unique
- Set<String> values = new HashSet<>();
- String s;
- s = iter.next().toString();
- values.add(s);
- assertEquals(++count, values.size());
- // begin at the head of all iterators
- assertEquals("{a=0, b=0, c=0, d=0, e=0, f=0, g=0, h=0, i=0, j=0}", s);
- int lim0 = (int) Math.pow(1, base);
- // first 2^10 results are binary (0's and 1's)
- int lim1 = (int) Math.pow(2, base);
- for (int i = lim0; i < lim1; i++) {
- s = iter.next().toString();
- System.out.println("" + i + ": " + count + ": " + s); System.out.flush();
- assertTrue(s.contains("1"));
- assertFalse(s.contains("2"));
- values.add(s);
- assertEquals(++count, values.size());
- }
- int lim2 = (int) Math.pow(3, base);
- for (int i = lim1; i < lim2; i++) {
- s = iter.next().toString();
- System.out.println("" + i + ": " + count + ": " + s); System.out.flush();
-
- if (!s.contains("2")) {
- findMissing(null, 0, base, "abcdefghij".getBytes(), values);
- }
-
-
- assertTrue(s.contains("2"));
- assertFalse(s.contains("3"));
- values.add(s);
- assertEquals(++count, values.size());
- }
- }
- */
-
- @Test
- public void testInnerJoin() throws Exception {
- String[] a1 = new String[]{"a", "b", "c"};
- String[] a2 = new String[]{"1", "2", "3", "4"};
- String[] a3 = new String[]{"2", "4", "6", "8", "10"};
-
- Enumerator<String> e1 = new IteratorEnumerator<>("letter", Arrays.asList(a1).iterator());
- Enumerator<String> e2 = new IteratorEnumerator<>("number", Arrays.asList(a2).iterator());
- Enumerator<String> e3 = new IteratorEnumerator<>("number", Arrays.asList(a3).iterator());
-
- Enumerator<String> e4 = new CrossJoinEnumerator<>(e1, e3);
- Enumerator<String> e5 = new CrossJoinEnumerator<>(e2, e4);
-
- // without AND semantics, we have all 60 combinations, including two "number" bindings per solution
- exhaust(e5);
- assertEquals(60, e5.size());
-
- // with AND semantics, we have only those six solutions for which a2 and a3 align
- Enumerator<String> join = new InnerJoinEnumerator<>(e5, new HashSet<String>() {{
- add("number");
- }});
- exhaust(join);
- assertEquals(6, join.size());
-
- assertResults(join,
- new Bindings<String>().put("letter", "a").put("number", "2"),
- new Bindings<String>().put("letter", "a").put("number", "4"),
- new Bindings<String>().put("letter", "b").put("number", "2"),
- new Bindings<String>().put("letter", "b").put("number", "4"),
- new Bindings<String>().put("letter", "c").put("number", "2"),
- new Bindings<String>().put("letter", "c").put("number", "4"));
- }
-
public static class Traversals extends MatchTest {
@Override
public Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_out_bX() {
@@ -699,14 +384,14 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
}
@Override
- public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_created_b__b_0created_aX() {
+ public Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_created_b__b_0created_aX() {
return g.V().match("a",
as("a").out("created").as("b"),
as("b").in("created").as("a"));
}
@Override
- public Traversal<Vertex, Map<String, Object>> get_g_V_matchXa_knows_b__c_knows_bX() {
+ public Traversal<Vertex, Map<String, Vertex>> get_g_V_matchXa_knows_b__c_knows_bX() {
return g.V().match("a", as("a").out("knows").as("b"),
as("c").out("knows").as("b"));
}
@@ -769,148 +454,19 @@ public abstract class MatchTest extends AbstractGremlinProcessTest {
.<String>select("a", "c").by("name");
}
- /*@Override
- public Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_selectXnameX() {
+ @Override
+ public Traversal<Vertex, Map<String, String>> get_g_V_matchXa_created_b__c_created_bX_select_byXnameX() {
return g.V().match("a",
as("a").out("created").as("b"),
- as("c").out("created").as("b")).select(v -> ((Vertex) v).value("name"));
+ as("c").out("created").as("b")).<String>select().by("name");
}
@Override
public Traversal<Vertex, String> get_g_V_out_out_hasXname_rippleX_matchXb_created_a__c_knows_bX_selectXcX_outXknowsX_name() {
return g.V().out().out().match("a",
as("b").out("created").as("a"),
- as("c").out("knows").as("b")).select("c").out("knows").value("name");
- }*/
-
- }
-
- private static final Function<Vertex, String> vertexToStr = v -> v.id().toString();
-
- private <S, E> void assertResults(final Function<E, String> toStringFunction,
- final Traversal<S, Map<String, E>> actual,
- final Bindings<E>... expected) {
- Comparator<Bindings<E>> comp = new Bindings.BindingsComparator<>(toStringFunction);
-
- List<Bindings<E>> actualList = toBindings(actual);
- List<Bindings<E>> expectedList = new LinkedList<>();
- Collections.addAll(expectedList, expected);
-
- if (expectedList.size() > actualList.size()) {
- fail("" + (expectedList.size() - actualList.size()) + " expected results not found, including " + expectedList.get(actualList.size()));
- } else if (actualList.size() > expectedList.size()) {
- fail("" + (actualList.size() - expectedList.size()) + " unexpected results, including " + actualList.get(expectedList.size()));
- }
-
- Collections.sort(actualList, comp);
- Collections.sort(expectedList, comp);
-
- for (int j = 0; j < actualList.size(); j++) {
- Bindings<E> a = actualList.get(j);
- Bindings<E> e = expectedList.get(j);
-
- if (0 != comp.compare(a, e)) {
- fail("unexpected result(s), including " + a);
- }
- }
- assertFalse(actual.hasNext());
- }
-
- private static final Function<Object, String> simpleToStringFunction = Object::toString;
-
- private <T> void assertResults(final Enumerator<T> actual,
- final Bindings<T>... expected) {
- Comparator<Bindings<T>> comp = new Bindings.BindingsComparator<>((Function<T, String>) simpleToStringFunction);
-
- List<Bindings<T>> actualList = toBindings(actual);
- List<Bindings<T>> expectedList = new LinkedList<>();
- Collections.addAll(expectedList, expected);
-
- Collections.sort(actualList, comp);
- Collections.sort(expectedList, comp);
-
- for (int j = 0; j < actualList.size(); j++) {
- if (j == expectedList.size()) {
- fail("" + (actualList.size() - expectedList.size()) + " unexpected results, including " + actualList.get(expectedList.size()));
- }
-
- Bindings<T> a = actualList.get(j);
- Bindings<T> e = expectedList.get(j);
-
- if (0 != comp.compare(a, e)) {
- fail("unexpected result(s), including " + a);
- }
- }
- if (expectedList.size() > actualList.size()) {
- fail("" + (expectedList.size() - actualList.size()) + " expected results not found, including " + expectedList.get(actualList.size()));
- }
- }
-
- private <S, E> List<Bindings<E>> toBindings(final Traversal<S, Map<String, E>> traversal) {
- List<Bindings<E>> result = new LinkedList<>();
- traversal.forEachRemaining(o -> {
- result.add(new Bindings<>(o));
- });
- return result;
- }
-
- private <T> List<Bindings<T>> toBindings(final Enumerator<T> enumerator) {
- List<Bindings<T>> bindingsList = new LinkedList<>();
- int i = 0;
- bindingsList.add(new Bindings<>());
- while (enumerator.visitSolution(i++, (name, value) -> {
- bindingsList.get(bindingsList.size() - 1).put(name, value);
- })) {
- bindingsList.add(new Bindings<>());
- }
- bindingsList.remove(bindingsList.size() - 1);
-
- return bindingsList;
- }
-
- private void assertBranchFactor(final double branchFactor,
- final Traversal t,
- final Iterator inputs) {
- Traverser start = new B_O_S_SE_SL_Traverser(null, null, 1l); // TODO bad? P?
- MatchStep.TraversalWrapper w = new MatchStep.TraversalWrapper(t, "a", "b");
- MatchStep.TraversalUpdater updater = new MatchStep.TraversalUpdater<>(w, inputs, start, "x");
- while (updater.hasNext()) {
- updater.next();
+ as("c").out("knows").as("b")).select("c").out("knows").values("name");
}
- assertEquals(branchFactor, w.findBranchFactor(), 0);
- }
- private <T> int exhaust(Enumerator<T> enumerator) {
- BiConsumer<String, T> visitor = (s, t) -> {
- };
- int i = 0;
- while (enumerator.visitSolution(i, visitor)) i++;
- return i;
- }
-
- private void findMissing(String s, final int i, final int n, final byte[] names, final Set<String> actual) {
- if (0 == i) {
- s = "{";
- } else {
- s += ", ";
- }
-
- s += (char) names[i];
- s += "=";
- String tmp = s;
- for (int j = 0; j < 3; j++) {
- s += j;
-
- if (n - 1 == i) {
- s += "}";
- if (!actual.contains(s)) {
- fail("not in set: " + s);
- }
- } else {
- findMissing(s, i + 1, n, names, actual);
- }
-
- s = tmp;
- }
}
}