This is an automated email from the ASF dual-hosted git repository. colegreer pushed a commit to branch repeatLimit in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 2fd547bb40ba92c675a9c3a6b93b452283694b3c Author: Andrea Child <[email protected]> AuthorDate: Fri Aug 29 16:15:56 2025 -0700 Account for traversals with varying path lengths. --- .../process/traversal/step/branch/RepeatStep.java | 9 +- .../traversal/step/filter/RangeGlobalStep.java | 22 ++++- .../traverser/B_LP_NL_O_P_S_SE_SL_Traverser.java | 1 + .../traverser/B_NL_O_S_SE_SL_Traverser.java | 1 + .../tinkergraph/structure/TinkerGraphPlayTest.java | 106 +++++++++++++-------- 5 files changed, 96 insertions(+), 43 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 3f27e71e54..b37d51ab3c 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 @@ -238,7 +238,14 @@ public final class RepeatStep<S> extends ComputerAwareStep<S, S> implements Trav return this.repeatTraversal.getEndStep(); } else { final Traverser.Admin<S> start = this.starts.next(); - start.initialiseLoops(this.getId(), this.loopName); + String ln; + if (this.loopName != null) { + ln = this.getId(); + } else { + ln = this.loopName; + } + + start.initialiseLoops(this.getId(), ln); if (doUntil(start, true)) { start.resetLoops(); return IteratorUtils.of(start); diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/RangeGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/RangeGlobalStep.java index c0c0c86e35..e02c572c3c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/RangeGlobalStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/RangeGlobalStep.java @@ -28,11 +28,13 @@ import java.util.Set; import java.util.concurrent.atomic.AtomicLong; import java.util.function.BinaryOperator; import org.apache.tinkerpop.gremlin.process.computer.MemoryComputeKey; +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.Bypassing; import org.apache.tinkerpop.gremlin.process.traversal.step.FilteringBarrier; import org.apache.tinkerpop.gremlin.process.traversal.step.Ranging; +import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; 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; @@ -71,16 +73,29 @@ public final class RangeGlobalStep<S> extends FilterStep<S> implements Ranging, // Determine which counter to use AtomicLong currentCounter = this.counter; if (usePerIterationCounters) { + + + StringBuilder sb = new StringBuilder(); + Traversal.Admin t = this.traversal; + while (!t.isRoot()) { + TraversalParent pt = t.getParent(); + Step<?, ?> ps = pt.asStep(); + String pid = ps.getId(); + sb.append(pid).append(":"); + sb.append(traverser.loops(pid)).append(":"); + t = ps.getTraversal(); + } + sb.append(this.getId()).append(":").append(traverser.loops()); + // Create counter key that isolates between different repeat step contexts - String pathStructure = String.valueOf(traverser.path().size()); - // consider removing the stepId from the key - String iterationKey = this.getId() + ":" + traverser.loops() + ":" + pathStructure; + String iterationKey = sb.toString(); Object vId = ((Vertex) traverser.get()).property("id").value(); currentCounter = perIterationCounters.computeIfAbsent(iterationKey, k -> new AtomicLong(0L)); System.out.printf("IterationKey: %s Traverser: %s Path: %s Counter: %s High: %s%n", iterationKey, vId, traverser.path(), currentCounter.get(), this.high); } if (this.high != -1 && currentCounter.get() >= this.high) { + System.out.printf("FastNoSuchElementException for Traverser: %s Counter: %d%n", traverser.path(), currentCounter.get()); throw FastNoSuchElementException.instance(); } @@ -88,6 +103,7 @@ public final class RangeGlobalStep<S> extends FilterStep<S> implements Ranging, if (currentCounter.get() + avail <= this.low) { // Will not surpass the low w/ this traverser. Skip and filter the whole thing. currentCounter.getAndAdd(avail); + System.out.printf("False for Traverser: %s Counter: %d%n", traverser.path(), currentCounter.get()); return false; } diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_NL_O_P_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_NL_O_P_S_SE_SL_Traverser.java index 1af9dbefef..70e827630d 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_NL_O_P_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_NL_O_P_S_SE_SL_Traverser.java @@ -62,6 +62,7 @@ public class B_LP_NL_O_P_S_SE_SL_Traverser<T> extends B_LP_O_P_S_SE_SL_Traverser if (this.nestedLoops.empty() || !this.nestedLoops.peek().hasLabel(stepLabel)) { final LabelledCounter lc = new LabelledCounter(stepLabel, (short) 0); this.nestedLoops.push(lc); + this.loopNames.put(stepLabel, lc); if (loopName != null) this.loopNames.put(loopName, lc); } diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_NL_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_NL_O_S_SE_SL_Traverser.java index 6e18d12a61..cb05a7559e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_NL_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_NL_O_S_SE_SL_Traverser.java @@ -61,6 +61,7 @@ public class B_NL_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { if (this.nestedLoops.empty() || !this.nestedLoops.peek().hasLabel(stepLabel)) { final LabelledCounter lc = new LabelledCounter(stepLabel, (short) 0); this.nestedLoops.push(lc); + this.loopNames.put(stepLabel, lc); if (loopName != null) this.loopNames.put(loopName, lc); } diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index 82d72c69a5..e6ccff6d8d 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -39,6 +39,7 @@ import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.VertexProperty; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; import org.apache.tinkerpop.gremlin.util.TimeUtil; +import org.junit.BeforeClass; import org.junit.Ignore; import org.junit.Test; import org.slf4j.Logger; @@ -57,48 +58,56 @@ import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.sack; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.union; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.valueMap; +import static org.junit.Assert.assertEquals; /** * @author Stephen Mallette (http://stephen.genoprime.com); */ public class TinkerGraphPlayTest { private static final Logger logger = LoggerFactory.getLogger(TinkerGraphPlayTest.class); - - @Test - @Ignore - public void testIterationScopedRangeGlobalInRepeat() { - GraphTraversalSource g = TinkerGraph.open().traversal().withoutStrategies(RepeatUnrollStrategy.class); + private static GraphTraversalSource g; + + @BeforeClass + public static void setup() { + g = TinkerGraph.open().traversal().withoutStrategies(RepeatUnrollStrategy.class); load(g); + } + + @Test + public void testBasicRepeatLimit() { GraphTraversal<Vertex, Path> basic = g.V().has("id", "l1-0") .repeat(__.limit(1).out("knows")) .times(2).path().by("id"); - toListAndPrint("basic", basic); GraphTraversal<Vertex, Path> basicUnfolded = g.V().has("id", "l1-0") .limit(1).out("knows") .limit(1).out("knows") .path().by("id"); - toListAndPrint("basicUnfolded", basicUnfolded); + assertEquals(toListAndPrint("basic", basic), toListAndPrint("basicUnfolded", basicUnfolded)); + } + @Test + public void testChainedRepeatLimit() { GraphTraversal<Vertex, Path> chained = g.V().has("id", "l2-0") .repeat(__.limit(1).out("knows")).times(2) .repeat(__.limit(1).in("knows")).times(2) .path().by("id"); - toListAndPrint("chained", chained); GraphTraversal<Vertex, Path> chainedUnfolded = g.V().has("id", "l2-0") .limit(1).out("knows") .limit(1).out("knows") .limit(1).in("knows") .limit(1).in("knows") .path().by("id"); - toListAndPrint("chainedUnfolded", chainedUnfolded); + assertEquals(toListAndPrint("chained", chained), toListAndPrint("chainedUnfolded", chainedUnfolded)); + } + @Test + public void testNestedRepeatLimit() { GraphTraversal<Vertex, Path> nested = g.V().has("id", "l3-0") .repeat(__.limit(1).out("knows") .repeat(__.limit(1).in("knows")) .times(2)) .times(2) .path().by("id"); - toListAndPrint("nested", nested); GraphTraversal<Vertex, Path> nestedUnfolded = g.V().has("id", "l3-0") .limit(1).out("knows") .limit(1).in("knows") @@ -107,8 +116,27 @@ public class TinkerGraphPlayTest { .limit(1).in("knows") .limit(1).in("knows") .path().by("id"); - toListAndPrint("nestedUnfolded", nestedUnfolded); + assertEquals(toListAndPrint("nested", nested), toListAndPrint("nestedUnfolded", nestedUnfolded)); + GraphTraversal<Vertex, Path> nested2 = g.V().has("id", "l3-0").out("knows"). + repeat(__.limit(1).out("knows") + .repeat(__.limit(1).in("knows")) + .times(2)). + times(2) + .path().by("id"); + GraphTraversal<Vertex, Path> nested2Unfolded = g.V().has("id", "l3-0").out("knows") + .limit(1).out("knows") + .limit(1).in("knows") + .limit(1).in("knows") + .limit(1).out("knows") + .limit(1).in("knows") + .limit(1).in("knows") + .path().by("id"); + assertEquals(toListAndPrint("nested2", nested2), toListAndPrint("nested2Unfolded", nested2Unfolded)); + } + + @Test + public void testTripleNestedRepeatLimit() { GraphTraversal<Vertex, Path> tripleNested = g.V().has("id", "l1-0") .repeat(__.limit(1).out("knows") .repeat(__.limit(1).in("knows") @@ -117,7 +145,6 @@ public class TinkerGraphPlayTest { .times(2)) .times(2) .path().by("id"); - toListAndPrint("tripleNested", tripleNested); GraphTraversal<Vertex, Path> tripleNestedUnfolded = g.V().has("id", "l1-0") .limit(1).out("knows") .limit(1).in("knows") @@ -134,46 +161,46 @@ public class TinkerGraphPlayTest { .limit(1).out("knows") .limit(1).out("knows") .path().by("id"); - toListAndPrint("tripleNestedUnfolded", tripleNestedUnfolded); + assertEquals(toListAndPrint("tripleNested", tripleNested), toListAndPrint("tripleNestedUnfolded", tripleNestedUnfolded)); + } - GraphTraversal<Vertex, Path> nested2 = g.V().has("id", "l3-0").out("knows"). - repeat(__.limit(1).out("knows") - .repeat(__.limit(1).in("knows")) - .times(2)). - times(2) - .path().by("id"); - toListAndPrint("nested2", nested2); - GraphTraversal<Vertex, Path> nested2Unfolded = g.V().has("id", "l3-0").out("knows") - .limit(1).out("knows") - .limit(1).in("knows") - .limit(1).in("knows") - .limit(1).out("knows") - .limit(1).in("knows") - .limit(1).in("knows") - .path().by("id"); - toListAndPrint("nested2Unfolded", nested2Unfolded); - GraphTraversal<Vertex, Object> aggregate = g.V().has("id", "l1-0").repeat(__.limit(1).out("knows").aggregate("x")).times(2).cap("x"); - toListAndPrint("aggregate", aggregate); + @Test + public void testAggregateRepeatLimit() { + GraphTraversal<Vertex, Object> aggregate = g.V().has("id", "l1-0") + .repeat(__.limit(1).out("knows").aggregate("x")) + .times(2) + .cap("x"); + GraphTraversal<Vertex, Object> aggregateUnfolded = g.V().has("id", "l1-0") + .limit(1).out("knows").aggregate("x") + .limit(1).out("knows").aggregate("x") + .cap("x"); + assertEquals(toListAndPrint("aggregate", aggregate), toListAndPrint("aggregateUnfolded", aggregateUnfolded)); + } - GraphTraversal<Vertex, Path> test = g.V().has("id", "l1-0") + @Test + public void testUnionRepeatLimit() { + GraphTraversal<Vertex, Path> union = g.V().has("id", "l1-0") + .union(out().limit(1), out().out().limit(1)) + .repeat(__.limit(1)).times(1) + .path().by("id"); + GraphTraversal<Vertex, Path> unionUnfolded = g.V().has("id", "l1-0") .union(out().limit(1), out().out().limit(1)) - .repeat(__.limit(1)) - .times(1).path().by("id"); - toListAndPrint("test", test); - GraphTraversal<Vertex, Path> test2 = g.V().has("id", "l1-0").union(out().limit(1), out().out().limit(1)).limit(1).path().by("id"); - toListAndPrint("test2", test2); + .limit(1) + .path().by("id"); + assertEquals(toListAndPrint("union", union), toListAndPrint("unionUnfolded", unionUnfolded)); } - private void toListAndPrint(String header, GraphTraversal t) { + private List toListAndPrint(String header, GraphTraversal t) { System.out.println("=====" + header + "==================================="); System.out.println(t); List<?> list = t.toList(); for (Object o : list) { System.out.println(o); } + return list; } - private void load(GraphTraversalSource g) { + private static void load(GraphTraversalSource g) { g.V().drop(); g.addV("node").property("id","l1-0").iterate(); @@ -659,6 +686,7 @@ public class TinkerGraphPlayTest { } @Test + @Ignore public void testPlay6() throws Exception { final Graph graph = TinkerGraph.open(); final GraphTraversalSource g = graph.traversal();
