Hi,
Whilst optimizing the DropStep in Sqlg I came across RepeatStep plus
DropStep in a traversal going into a infinite loop.
To test Sqlg I tested on TinkerPop's ComplexTest.playlistPath() changing
the gremlin to have a drop()
@Test
public void testDropPlaylist() {
final TinkerGraph g = TinkerGraph.open();
Io.Builder<GraphSONIo> builder =
GraphSONIo.build(GraphSONVersion.V3_0);
final GraphReader reader = g.io(builder).reader().create();
try (final InputStream stream =
AbstractGremlinTest.class.getResourceAsStream("/grateful-dead-v3d0.json")) {
reader.readGraph(stream, g);
} catch (IOException e) {
Assert.fail(e.getMessage());
}
Traversal<Vertex, Vertex> playListTraversal = getPlaylistPaths(g);
System.out.println(playListTraversal.toString());
List<Vertex> vertices = playListTraversal.toList();
Assert.assertEquals(100, vertices.size());
System.out.println("counted");
Traversal<Vertex, Vertex> dropTraversal =
getPlaylistPaths(g).drop().drop().iterate();
System.out.println("done");
}
public GraphTraversal<Vertex, Vertex> getPlaylistPaths(Graph graph) {
return graph.traversal().V().has("name",
"Bob_Dylan").in("sungBy").as("a").
repeat(__.out().order().by(Order.shuffle).simplePath().from("a")).
until(__.out("writtenBy").has("name",
"Johnny_Cash")).limit(1).as("b").
repeat(__.out().order().by(Order.shuffle).as("c").simplePath().from("b").to("c")).
until(__.out("sungBy").has("name",
"Grateful_Dead")).limit(100);
}
The second dropTraversal goes into an infinite loop.
A simpler scenario illustrating the infinite loop,
@Test
public void testRepeatDrop() {
final TinkerGraph g = TinkerGraph.open();
Vertex a1 = g.addVertex(T.label, "A");
Vertex b1 = g.addVertex(T.label, "B");
Vertex c1 = g.addVertex(T.label, "C");
a1.addEdge("ab", b1);
b1.addEdge("ba", a1);
b1.addEdge("bc", c1);
Vertex a2 = g.addVertex(T.label, "A");
Vertex b2 = g.addVertex(T.label, "B");
Vertex c2 = g.addVertex(T.label, "C");
a2.addEdge("ab", b2);
b2.addEdge("ba", a2);
b2.addEdge("bc", c2);
a1.addEdge("ac", c1);
a1.addEdge("ac", c2);
List<Vertex> vertices =
g.traversal().withoutStrategies(LazyBarrierStrategy.class)
.V().hasLabel("A")
.repeat(__.out("ab", "ba"))
.until(__.out("bc"))
.out("bc")
.in("ac")
.out("ac")
.toList();
Assert.assertEquals(4, vertices.size());
g.traversal().withoutStrategies(LazyBarrierStrategy.class)
.V().hasLabel("A")
.repeat(__.out("ab", "ba"))
.until(__.out("bc"))
.out("bc")
.in("ac")
.out("ac")
.drop()
.iterate();
System.out.println("asdasdasd");
}
Adding a BarrierStep before drop() resolves the issue but probably this
should happen automatically in a strategy?
Afraid I can not quite tell what the scenarios are that would cause this
issue so not sure if a BarrierStep should always be added or only sometimes.
Cheers
Pieter