This is an automated email from the ASF dual-hosted git repository.
lyndonb pushed a commit to branch TINKERPOP-3002
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
The following commit(s) were added to refs/heads/TINKERPOP-3002 by this push:
new 00c6f5eac9 TINKERPOP-3002 initial commit with test that reproduces
issue and switch to TraverSet that fixes this. This is not a long term solution
because it effectively forces everything to be eager, which is also not
correct. It should toggle between eager and lazy behavior as is appropriate
with the barriers present. To do this we must use IteratorUtils.mappings, which
will come next commit.
00c6f5eac9 is described below
commit 00c6f5eac9153ff1908e5e90f8acd56012cc2fa8
Author: lyndon <[email protected]>
AuthorDate: Thu Oct 12 20:07:10 2023 -0700
TINKERPOP-3002 initial commit with test that reproduces issue and switch to
TraverSet that fixes this. This is not a long term solution because it
effectively forces everything to be eager, which is also not correct. It should
toggle between eager and lazy behavior as is appropriate with the barriers
present. To do this we must use IteratorUtils.mappings, which will come next
commit.
---
.../process/traversal/step/branch/RepeatStep.java | 74 +++++++++++------
.../process/traversal/util/TraversalUtil.java | 32 ++++++++
.../structure/TinkerGraphRepeatBarrierTest.java | 94 ++++++++++++++++++++++
3 files changed, 177 insertions(+), 23 deletions(-)
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/RepeatStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/RepeatStep.java
index 955dacbcb0..0f2757ab43 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/RepeatStep.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/RepeatStep.java
@@ -24,6 +24,8 @@ import
org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import
org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareStep;
import
org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
+import
org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import
org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils;
@@ -113,14 +115,22 @@ public final class RepeatStep<S> extends
ComputerAwareStep<S, S> implements Trav
return list;
}
- public final boolean doUntil(final Traverser.Admin<S> traverser, boolean
utilFirst) {
- return utilFirst == this.untilFirst && null != this.untilTraversal &&
TraversalUtil.test(traverser, this.untilTraversal);
+ public final boolean doUntil(final Traverser.Admin<S> traverser, boolean
untilFirst) {
+ return untilFirst == this.untilFirst && null != this.untilTraversal &&
TraversalUtil.test(traverser, this.untilTraversal);
+ }
+
+ public final boolean doUntil(final TraverserSet<S> traverserSet, boolean
untilFirst) {
+ return untilFirst == this.untilFirst && null != this.untilTraversal &&
TraversalUtil.test(traverserSet, this.untilTraversal);
}
public final boolean doEmit(final Traverser.Admin<S> traverser, boolean
emitFirst) {
return emitFirst == this.emitFirst && null != this.emitTraversal &&
TraversalUtil.test(traverser, this.emitTraversal);
}
+ public final boolean doEmit(final TraverserSet<S> traverserSet, boolean
emitFirst) {
+ return emitFirst == this.emitFirst && null != this.emitTraversal &&
TraversalUtil.test(traverserSet, this.emitTraversal);
+ }
+
@Override
public String toString() {
if (this.untilFirst && this.emitFirst)
@@ -196,17 +206,26 @@ public final class RepeatStep<S> extends
ComputerAwareStep<S, S> implements Trav
if (this.repeatTraversal.getEndStep().hasNext()) {
return this.repeatTraversal.getEndStep();
} else {
- final Traverser.Admin<S> start = this.starts.next();
- start.initialiseLoops(this.getId(), this.loopName);
- if (doUntil(start, true)) {
- start.resetLoops();
- return IteratorUtils.of(start);
+ TraverserSet<S> traverserSet = new TraverserSet<>();
+ do {
+ Traverser.Admin<S> start = starts.next();
+ start.initialiseLoops(this.getId(), this.loopName);
+ traverserSet.add(start);
+ } while ((starts.hasNext()));
+
+ if (doUntil(traverserSet, true)) {
+ traverserSet.forEach(Traverser.Admin::resetLoops);
+ return traverserSet.iterator();
}
- this.repeatTraversal.addStart(start);
- if (doEmit(start, true)) {
- final Traverser.Admin<S> emitSplit = start.split();
- emitSplit.resetLoops();
- return IteratorUtils.of(emitSplit);
+ this.repeatTraversal.addStarts(traverserSet.iterator());
+ if (doEmit(traverserSet, true)) {
+ TraverserSet<S> emitSet = new TraverserSet<>();
+ traverserSet.forEach(traverser -> {
+ Traverser.Admin<S> emitSplit = traverser.split();
+ emitSplit.resetLoops();
+ emitSet.add(emitSplit);
+ });
+ return emitSet.iterator();
}
}
}
@@ -293,20 +312,29 @@ public final class RepeatStep<S> extends
ComputerAwareStep<S, S> implements Trav
protected Iterator<Traverser.Admin<S>> standardAlgorithm() throws
NoSuchElementException {
final RepeatStep<S> repeatStep = (RepeatStep<S>)
this.getTraversal().getParent();
while (true) {
- final Traverser.Admin<S> start = this.starts.next();
- start.incrLoops();
- if (repeatStep.doUntil(start, false)) {
- start.resetLoops();
- return IteratorUtils.of(start);
+ TraverserSet<S> traverserSet = new TraverserSet<>();
+ do {
+ Traverser.Admin<S> start = starts.next();
+ start.incrLoops();
+ traverserSet.add(start);
+ } while ((starts.hasNext()));
+
+ if (repeatStep.doUntil(traverserSet, false)) {
+ traverserSet.forEach(Traverser.Admin::resetLoops);
+ return traverserSet.iterator();
} else {
if (!repeatStep.untilFirst && !repeatStep.emitFirst)
- repeatStep.repeatTraversal.addStart(start);
+
repeatStep.repeatTraversal.addStarts(traverserSet.iterator());
else
- repeatStep.addStart(start);
- if (repeatStep.doEmit(start, false)) {
- final Traverser.Admin<S> emitSplit = start.split();
- emitSplit.resetLoops();
- return IteratorUtils.of(emitSplit);
+ repeatStep.addStarts(traverserSet.iterator());
+ if (repeatStep.doEmit(traverserSet, false)) {
+ TraverserSet<S> emitSet = new TraverserSet<>();
+ traverserSet.forEach(traverser -> {
+ final Traverser.Admin<S> emitSplit =
traverser.split();
+ emitSplit.resetLoops();
+ emitSet.add(emitSplit);
+ });
+ return emitSet.iterator();
}
}
}
diff --git
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalUtil.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalUtil.java
index 1acb54743b..2f908bab36 100644
---
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalUtil.java
+++
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalUtil.java
@@ -21,6 +21,7 @@ package org.apache.tinkerpop.gremlin.process.traversal.util;
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.traverser.util.TraverserSet;
import org.apache.tinkerpop.gremlin.structure.util.CloseableIterator;
import java.util.Iterator;
@@ -136,6 +137,21 @@ public final class TraversalUtil {
}
}
+ public static <S, E> boolean test(final TraverserSet<S> traverserSet,
final Traversal.Admin<S, E> traversal) {
+ prepare(traverserSet, traversal);
+
+ boolean val = false;
+ while (traversal.hasNext()) {
+ val = true;
+ traversal.next();
+ }
+
+ //Close the traversal to release any underlying resources.
+ CloseableIterator.closeIterator(traversal);
+
+ return val;
+ }
+
public static <S, E> boolean test(final Traverser.Admin<S> traverser,
final Traversal.Admin<S, E> traversal) {
prepare(traverser, traversal);
final boolean val = traversal.hasNext(); // filter
@@ -186,4 +202,20 @@ public final class TraversalUtil {
traversal.addStart(split);
return split;
}
+
+ public static <S, E> TraverserSet<S> prepare(final TraverserSet<S>
traverserSet, final Traversal.Admin<S, E> traversal) {
+ final TraverserSet<S> traverserSetClone = new TraverserSet<>();
+ final TraverserSet<S> traverserSetClone2 = new TraverserSet<>();
+ while (!traverserSet.isEmpty()) {
+ Traverser.Admin<S> split = traverserSet.remove().split();
+ traverserSetClone2.add(split);
+ split.setSideEffects(traversal.getSideEffects());
+ split.setBulk(1L);
+ traversal.reset();
+ traverserSetClone.add(split);
+ }
+ traversal.addStarts(traverserSetClone.iterator());
+ traverserSet.addAll(traverserSetClone2);
+ return traverserSetClone;
+ }
}
diff --git
a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphRepeatBarrierTest.java
b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphRepeatBarrierTest.java
new file mode 100644
index 0000000000..a6f67c9f00
--- /dev/null
+++
b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphRepeatBarrierTest.java
@@ -0,0 +1,94 @@
+/*
+ * 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.tinkergraph.structure;
+
+import org.apache.tinkerpop.gremlin.process.traversal.P;
+import
org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import
org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RepeatUnrollStrategy;
+import
org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.function.Consumer;
+
+public class TinkerGraphRepeatBarrierTest {
+
+ @Test
+ public void test() {
+ final TinkerGraph tg = TinkerGraph.open();
+ final GraphTraversalSource g = tg.traversal();
+
+ // Create structure:
+ // root-branch1->[leaf_1, leaf_2, leaf_3]
+ // leaf_1-branch2->[leaf2_1, leaf2_2, leaf2_3]
+ // leaf_2-branch2->[leaf2_4, leaf2_5, leaf2_6]
+ // leaf_3-branch2->[leaf2_7, leaf2_8, leaf2_9]
+ g.addV("root").as("root").
+ addE("branch1").to(__.addV("leaf1_1").as("leaf1_1").
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_1"))).
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_2"))).
+
sideEffect(__.addE("branch2").to(__.addV("leaf2_3"))).select("leaf1_1")).
+ select("root").
+ addE("branch1x").to(__.addV("leaf1_2").as("leaf1_2").
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_4"))).
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_5"))).
+
sideEffect(__.addE("branch2").to(__.addV("leaf2_6"))).select("leaf1_2")).
+ select("root").
+ addE("branch1xx").to(__.addV("leaf1_3").as("leaf1_3").
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_7"))).
+ sideEffect(__.addE("branch2").to(__.addV("leaf2_8"))).
+
sideEffect(__.addE("branch2").to(__.addV("leaf2_9"))).select("leaf1_3")).iterate();
+
+ final BarrierConsumerInputCounter untilBlockBarrierConsumer = new
BarrierConsumerInputCounter("until");
+ final BarrierConsumerInputCounter repeatBlockBarrierConsumer = new
BarrierConsumerInputCounter("repeat");
+
+ // If the barrier is respected by the repeat step, we will get 3 then
9.
+ final List<?> data1 = g.
+ withoutStrategies(RepeatUnrollStrategy.class)
+ .V().hasLabel("root").
+ repeat(
+ __.barrier(repeatBlockBarrierConsumer).out()).
+ until(
+
__.barrier(untilBlockBarrierConsumer).out().count().is(P.eq(0))).
+ toList();
+ // Should also try barrier of 1 < barrierSize < count per stage
+ System.out.println("data1: " + data1);
+ System.out.println("untilBlockBarrierConsumer.barrierInputs: " +
untilBlockBarrierConsumer.barrierInputs);
+ System.out.println("repeatBlockBarrierConsumer.barrierInputs: " +
repeatBlockBarrierConsumer.barrierInputs);
+ }
+
+ static class BarrierConsumerInputCounter implements
Consumer<TraverserSet<Object>> {
+ public final List<Integer> barrierInputs = new ArrayList<>();
+ public final String label;
+
+ public BarrierConsumerInputCounter(final String label) {
+ this.label = label;
+ }
+
+ @Override
+ public void accept(TraverserSet<Object> admins) {
+ barrierInputs.add(admins.size());
+ System.out.println(label + "-" + admins.size());
+ // Pass through.
+ }
+ }
+}
