diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java index 4c976c5..3eb9c58 100644 --- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java @@ -1,429 +1,429 @@ package org.softwareheritage.graph.rpc; import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; import it.unimi.dsi.big.webgraph.labelling.Label; import org.softwareheritage.graph.*; import java.util.*; public class Traversal { private static ArcLabelledNodeIterator.LabelledArcIterator filterLabelledSuccessors(SwhUnidirectionalGraph g, long nodeId, AllowedEdges allowedEdges) { if (allowedEdges.restrictedTo == null) { // All edges are allowed, bypass edge check return g.labelledSuccessors(nodeId); } else { ArcLabelledNodeIterator.LabelledArcIterator allSuccessors = g.labelledSuccessors(nodeId); return new ArcLabelledNodeIterator.LabelledArcIterator() { @Override public Label label() { return allSuccessors.label(); } @Override public long nextLong() { long neighbor; while ((neighbor = allSuccessors.nextLong()) != -1) { if (allowedEdges.isAllowed(g.getNodeType(nodeId), g.getNodeType(neighbor))) { return neighbor; } } return -1; } @Override public long skip(final long n) { long i = 0; while (i < n && nextLong() != -1) i++; return i; } }; } } private static class NodeFilterChecker { private final SwhUnidirectionalGraph g; private final NodeFilter filter; private final AllowedNodes allowedNodes; private NodeFilterChecker(SwhUnidirectionalGraph graph, NodeFilter filter) { this.g = graph; this.filter = filter; this.allowedNodes = new AllowedNodes(filter.hasTypes() ? filter.getTypes() : "*"); } public boolean allowed(long nodeId) { if (filter == null) { return true; } if (!this.allowedNodes.isAllowed(g.getNodeType(nodeId))) { return false; } return true; } } public static SwhUnidirectionalGraph getDirectedGraph(SwhBidirectionalGraph g, GraphDirection direction) { switch (direction) { case FORWARD: return g.getForwardGraph(); case BACKWARD: return g.getBackwardGraph(); /* * TODO: add support for BOTH case BOTH: return new SwhUnidirectionalGraph(g.symmetrize(), * g.getProperties()); */ default : throw new IllegalArgumentException("Unknown direction: " + direction); } } public static GraphDirection reverseDirection(GraphDirection direction) { switch (direction) { case FORWARD: return GraphDirection.BACKWARD; case BACKWARD: return GraphDirection.FORWARD; /* * TODO: add support for BOTH case BOTH: return GraphDirection.BOTH; */ default : throw new IllegalArgumentException("Unknown direction: " + direction); } } static class StopTraversalException extends RuntimeException { } static class BFSVisitor { protected final SwhUnidirectionalGraph g; protected long depth = 0; protected long traversalSuccessors = 0; protected long edgesAccessed = 0; protected HashMap parents = new HashMap<>(); protected ArrayDeque queue = new ArrayDeque<>(); private long maxDepth = -1; private long maxEdges = -1; BFSVisitor(SwhUnidirectionalGraph g) { this.g = g; } public void addSource(long nodeId) { queue.add(nodeId); parents.put(nodeId, -1L); } public void setMaxDepth(long depth) { maxDepth = depth; } public void setMaxEdges(long edges) { maxEdges = edges; } public void visitSetup() { edgesAccessed = 0; depth = 0; queue.add(-1L); // depth sentinel } public void visit() { visitSetup(); while (!queue.isEmpty()) { visitStep(); } } public void visitStep() { try { assert !queue.isEmpty(); long curr = queue.poll(); if (curr == -1L) { ++depth; if (!queue.isEmpty()) { queue.add(-1L); visitStep(); } return; } if (maxDepth >= 0 && depth > maxDepth) { throw new StopTraversalException(); } edgesAccessed += g.outdegree(curr); - if (maxEdges >= 0 && edgesAccessed >= maxEdges) { + if (maxEdges >= 0 && edgesAccessed > maxEdges) { throw new StopTraversalException(); } visitNode(curr); } catch (StopTraversalException e) { // Traversal is over, clear the to-do queue. queue.clear(); } } protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return g.labelledSuccessors(nodeId); } protected void visitNode(long node) { ArcLabelledNodeIterator.LabelledArcIterator it = getSuccessors(node); traversalSuccessors = 0; for (long succ; (succ = it.nextLong()) != -1;) { traversalSuccessors++; visitEdge(node, succ, it.label()); } } protected void visitEdge(long src, long dst, Label label) { if (!parents.containsKey(dst)) { queue.add(dst); parents.put(dst, src); } } } static class SimpleTraversal extends BFSVisitor { private final NodeFilterChecker nodeReturnChecker; private final AllowedEdges allowedEdges; private final TraversalRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final NodeObserver nodeObserver; private Node.Builder nodeBuilder; SimpleTraversal(SwhBidirectionalGraph bidirectionalGraph, TraversalRequest request, NodeObserver nodeObserver) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.nodeObserver = nodeObserver; this.nodeReturnChecker = new NodeFilterChecker(g, request.getReturnNodes()); this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); addSource(srcNodeId); }); if (request.hasMaxDepth()) { setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { setMaxEdges(request.getMaxEdges()); } } @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdges); } @Override public void visitNode(long node) { nodeBuilder = null; if (nodeReturnChecker.allowed(node) && (!request.hasMinDepth() || depth >= request.getMinDepth())) { nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, node); } super.visitNode(node); if (request.getReturnNodes().hasMinTraversalSuccessors() && traversalSuccessors < request.getReturnNodes().getMinTraversalSuccessors() || request.getReturnNodes().hasMaxTraversalSuccessors() && traversalSuccessors > request.getReturnNodes().getMaxTraversalSuccessors()) { nodeBuilder = null; } if (nodeBuilder != null) { nodeObserver.onNext(nodeBuilder.build()); } } @Override protected void visitEdge(long src, long dst, Label label) { super.visitEdge(src, dst, label); NodePropertyBuilder.buildSuccessorProperties(g, nodeDataMask, nodeBuilder, src, dst, label); } } static class FindPathTo extends BFSVisitor { private final AllowedEdges allowedEdges; private final FindPathToRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final NodeFilterChecker targetChecker; private Long targetNode = null; FindPathTo(SwhBidirectionalGraph bidirectionalGraph, FindPathToRequest request) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.targetChecker = new NodeFilterChecker(g, request.getTarget()); this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); this.allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); if (request.hasMaxDepth()) { setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { setMaxEdges(request.getMaxEdges()); } request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); addSource(srcNodeId); }); } @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdges); } @Override public void visitNode(long node) { if (targetChecker.allowed(node)) { targetNode = node; throw new StopTraversalException(); } super.visitNode(node); } public Path getPath() { if (targetNode == null) { return null; } Path.Builder pathBuilder = Path.newBuilder(); long curNode = targetNode; ArrayList path = new ArrayList<>(); while (curNode != -1) { path.add(curNode); curNode = parents.get(curNode); } Collections.reverse(path); for (long nodeId : path) { Node.Builder nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId); pathBuilder.addNode(nodeBuilder.build()); } return pathBuilder.build(); } } static class FindPathBetween extends BFSVisitor { private final FindPathBetweenRequest request; private final NodePropertyBuilder.NodeDataMask nodeDataMask; private final AllowedEdges allowedEdgesSrc; private final AllowedEdges allowedEdgesDst; private final BFSVisitor srcVisitor; private final BFSVisitor dstVisitor; private Long middleNode = null; FindPathBetween(SwhBidirectionalGraph bidirectionalGraph, FindPathBetweenRequest request) { super(getDirectedGraph(bidirectionalGraph, request.getDirection())); this.request = request; this.nodeDataMask = new NodePropertyBuilder.NodeDataMask(request.hasMask() ? request.getMask() : null); this.allowedEdgesSrc = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); GraphDirection direction = request.getDirection(); GraphDirection directionReverse = request.hasDirectionReverse() ? request.getDirectionReverse() : reverseDirection(request.getDirection()); SwhUnidirectionalGraph srcGraph = getDirectedGraph(bidirectionalGraph, direction); SwhUnidirectionalGraph dstGraph = getDirectedGraph(bidirectionalGraph, directionReverse); this.allowedEdgesDst = request.hasEdgesReverse() ? new AllowedEdges(request.getEdgesReverse()) : (request.hasEdges() ? (direction == directionReverse ? new AllowedEdges(request.getEdges()) : new AllowedEdges(request.getEdges()).reverse()) : new AllowedEdges("*")); this.srcVisitor = new BFSVisitor(srcGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesSrc); } @Override public void visitNode(long node) { if (dstVisitor.parents.containsKey(node)) { middleNode = node; throw new StopTraversalException(); } super.visitNode(node); } }; this.dstVisitor = new BFSVisitor(dstGraph) { @Override protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) { return filterLabelledSuccessors(g, nodeId, allowedEdgesDst); } @Override public void visitNode(long node) { if (srcVisitor.parents.containsKey(node)) { middleNode = node; throw new StopTraversalException(); } super.visitNode(node); } }; if (request.hasMaxDepth()) { this.srcVisitor.setMaxDepth(request.getMaxDepth()); this.dstVisitor.setMaxDepth(request.getMaxDepth()); } if (request.hasMaxEdges()) { this.srcVisitor.setMaxEdges(request.getMaxEdges()); this.dstVisitor.setMaxEdges(request.getMaxEdges()); } request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); srcVisitor.addSource(srcNodeId); }); request.getDstList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); dstVisitor.addSource(srcNodeId); }); } @Override public void visit() { srcVisitor.visitSetup(); dstVisitor.visitSetup(); while (!srcVisitor.queue.isEmpty() || !dstVisitor.queue.isEmpty()) { if (!srcVisitor.queue.isEmpty()) { srcVisitor.visitStep(); } if (!dstVisitor.queue.isEmpty()) { dstVisitor.visitStep(); } } } public Path getPath() { if (middleNode == null) { return null; } Path.Builder pathBuilder = Path.newBuilder(); ArrayList path = new ArrayList<>(); long curNode = middleNode; while (curNode != -1) { path.add(curNode); curNode = srcVisitor.parents.get(curNode); } pathBuilder.setMiddleNodeIndex(path.size() - 1); Collections.reverse(path); curNode = dstVisitor.parents.get(middleNode); while (curNode != -1) { path.add(curNode); curNode = dstVisitor.parents.get(curNode); } for (long nodeId : path) { Node.Builder nodeBuilder = Node.newBuilder(); NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId); pathBuilder.addNode(nodeBuilder.build()); } return pathBuilder.build(); } } public interface NodeObserver { void onNext(Node nodeId); } } diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java index c183187..7a7b682 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java @@ -1,185 +1,203 @@ package org.softwareheritage.graph.rpc; import io.grpc.Status; import io.grpc.StatusRuntimeException; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; import org.softwareheritage.graph.SWHID; import java.util.ArrayList; import java.util.List; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertThrows; public class FindPathBetweenTest extends TraversalServiceTest { private FindPathBetweenRequest.Builder getRequestBuilder(SWHID src, SWHID dst) { return FindPathBetweenRequest.newBuilder().addSrc(src.toString()).addDst(dst.toString()); } @Test public void testSwhidErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client .findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(TEST_ORIGIN_ID) .addDst("swh:1:cnt:000000000000000000000000000000000000000z").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } @Test public void testEdgeErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest .newBuilder().addSrc(TEST_ORIGIN_ID).addDst(TEST_ORIGIN_ID).setEdges("batracien:reptile").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } // Test path between ori 1 and cnt 4 (forward graph) @Test public void forwardRootToLeaf() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 4)).build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9), fakeSWHID("dir", 8), fakeSWHID("dir", 6), fakeSWHID("cnt", 4)); Assertions.assertEquals(expected, actual); } // Test path between rev 18 and rev 3 (forward graph) @Test public void forwardRevToRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 18), fakeSWHID("rev", 3)).build())); List expected = List.of(fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("rev", 9), fakeSWHID("rev", 3)); Assertions.assertEquals(expected, actual); } // Test path between rev 3 and rev 18 (backward graph) @Test public void backwardRevToRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 3), fakeSWHID("rev", 18)) .setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13), fakeSWHID("rev", 18)); Assertions.assertEquals(expected, actual); } // Test path between cnt 4 and itself (forward graph) @Test public void forwardCntToItself() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 4)).build())); List expected = List.of(fakeSWHID("cnt", 4)); Assertions.assertEquals(expected, actual); } // Start from ori and rel 19 and find cnt 14 or cnt 7 (forward graph) @Test public void forwardMultipleSourcesDest() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 14)) .addSrc(TEST_ORIGIN_ID).addDst(fakeSWHID("cnt", 7).toString()).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("cnt", 14)); } // Start from cnt 4 and cnt 11 and find rev 13 or rev 9 (backward graph) @Test public void backwardMultipleSourcesDest() { ArrayList actual = getSWHIDs(client.findPathBetween( getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 13)).setDirection(GraphDirection.BACKWARD) .addSrc(fakeSWHID("cnt", 11).toString()).addDst(fakeSWHID("rev", 9).toString()).build())); List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13)); Assertions.assertEquals(expected, actual); } // Start from all directories and find the origin (backward graph) @Test public void backwardMultipleSourcesAllDirToOri() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("dir", 2), new SWHID(TEST_ORIGIN_ID)) .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString()) .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString()) .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20), new SWHID(TEST_ORIGIN_ID)); Assertions.assertEquals(expected, actual); } // Start from cnt 4 and find any rev (backward graph) @Test public void backwardCntToAnyRev() { ArrayList actual = getSWHIDs( client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 3)) .addDst(fakeSWHID("rev", 9).toString()).addDst(fakeSWHID("rev", 13).toString()) .addDst(fakeSWHID("rev", 18).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("cnt", 4), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("rev", 9)); Assertions.assertEquals(expected, actual); } // Impossible path between rev 9 and cnt 14 @Test public void forwardImpossiblePath() { StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 9), fakeSWHID("cnt", 14)).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); // Reverse direction thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 14), fakeSWHID("rev", 9)) .setDirection(GraphDirection.BACKWARD).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } // Common ancestor between cnt 4 and cnt 15 : rev 18 @Test public void commonAncestorBackwardBackward() { Path p = client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 15)) .setDirection(GraphDirection.BACKWARD).setDirectionReverse(GraphDirection.BACKWARD).build()); ArrayList actual = getSWHIDs(p); SWHID expected = fakeSWHID("rev", 18); Assertions.assertEquals(expected, actual.get(p.getMiddleNodeIndex())); } // Common descendant between rev 13 and rev 3 : cnt 1 (with rev:dir,dir:dir,dir:cnt) @Test public void commonDescendantForwardForward() { Path p = client.findPathBetween( getRequestBuilder(fakeSWHID("rev", 13), fakeSWHID("rev", 3)).setDirection(GraphDirection.FORWARD) .setDirectionReverse(GraphDirection.FORWARD).setEdges("rev:dir,dir:dir,dir:cnt").build()); ArrayList actual = getSWHIDs(p); SWHID expected = fakeSWHID("cnt", 1); Assertions.assertEquals(expected, actual.get(p.getMiddleNodeIndex())); } // Path between rel 19 and cnt 15 with various max depths @Test public void maxDepth() { // Works with max_depth = 2 ArrayList actual = getSWHIDs(client .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(2).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("dir", 16), fakeSWHID("cnt", 15)); Assertions.assertEquals(expected, actual); // Check that it throws NOT_FOUND with max depth = 1 StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathBetween( getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(1).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } + + // Path between rel 19 and cnt 15 with various max edges + @Test + public void maxEdges() { + // Works with max_edges = 3 + ArrayList actual = getSWHIDs(client + .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(3).build())); + List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), + fakeSWHID("dir", 16), fakeSWHID("cnt", 15)); + Assertions.assertEquals(expected, actual); + + // Check that it throws NOT_FOUND with max_edges = 2 + StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { + client.findPathBetween( + getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(2).build()); + }); + Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); + } } diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java index b95457d..ebec7fc 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java @@ -1,146 +1,162 @@ package org.softwareheritage.graph.rpc; import io.grpc.Status; import io.grpc.StatusRuntimeException; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; import org.softwareheritage.graph.SWHID; import java.util.ArrayList; import java.util.List; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertThrows; public class FindPathToTest extends TraversalServiceTest { private FindPathToRequest.Builder getRequestBuilder(SWHID src, String allowedNodes) { return FindPathToRequest.newBuilder().addSrc(src.toString()) .setTarget(NodeFilter.newBuilder().setTypes(allowedNodes).build()); } @Test public void testSrcErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client .findPathTo(FindPathToRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo( FindPathToRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo( FindPathToRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } @Test public void testEdgeErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo( FindPathToRequest.newBuilder().addSrc(TEST_ORIGIN_ID).setEdges("batracien:reptile").build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } @Test public void testTargetErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo(FindPathToRequest.newBuilder().addSrc(TEST_ORIGIN_ID) .setTarget(NodeFilter.newBuilder().setTypes("argoumante,eglomatique").build()).build())); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } // Test path between ori 1 and any dir (forward graph) @Test public void forwardOriToFirstDir() { ArrayList actual = getSWHIDs( client.findPathTo(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), "dir").build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9), fakeSWHID("dir", 8)); Assertions.assertEquals(expected, actual); } // Test path between rel 19 and any cnt (forward graph) @Test public void forwardRelToFirstCnt() { ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("rel", 19), "cnt").build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("cnt", 14)); Assertions.assertEquals(expected, actual); } // Test path between dir 16 and any rel (backward graph) @Test public void backwardDirToFirstRel() { ArrayList actual = getSWHIDs(client.findPathTo( getRequestBuilder(fakeSWHID("dir", 16), "rel").setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("dir", 16), fakeSWHID("dir", 17), fakeSWHID("rev", 18), fakeSWHID("rel", 19)); Assertions.assertEquals(expected, actual); } // Test path between cnt 4 and itself (forward graph) @Test public void forwardCntToItself() { ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 4), "cnt").build())); List expected = List.of(fakeSWHID("cnt", 4)); Assertions.assertEquals(expected, actual); } // Start from ori and rel 19 and find any cnt (forward graph) @Test public void forwardMultipleSources() { ArrayList actual = getSWHIDs( client.findPathTo(getRequestBuilder(fakeSWHID("rel", 19), "cnt").addSrc(TEST_ORIGIN_ID).build())); List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17), fakeSWHID("cnt", 14)); } // Start from cnt 4 and cnt 11 and find any rev (backward graph) @Test public void backwardMultipleSources() { ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 4), "rev") .addSrc(fakeSWHID("cnt", 11).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13)); Assertions.assertEquals(expected, actual); } // Start from all directories and find any origin (backward graph) @Test public void backwardMultipleSourcesAllDirToOri() { ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("dir", 2), "ori") .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString()) .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString()) .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20), new SWHID(TEST_ORIGIN_ID)); Assertions.assertEquals(expected, actual); } // Impossible path between rev 9 and any release (forward graph) @Test public void forwardImpossiblePath() { // Check that the return is STATUS.NOT_FOUND StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathTo(getRequestBuilder(fakeSWHID("rev", 9), "rel").build()); }); Assertions.assertEquals(thrown.getStatus(), Status.NOT_FOUND); } - // Path between rel 19 and cnt 15 with various max depths + // Path from cnt 15 to any rel with various max depths @Test public void maxDepth() { // Works with max_depth = 2 ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel") .setDirection(GraphDirection.BACKWARD).setMaxDepth(4).build())); List expected = List.of(fakeSWHID("cnt", 15), fakeSWHID("dir", 16), fakeSWHID("dir", 17), fakeSWHID("rev", 18), fakeSWHID("rel", 19)); Assertions.assertEquals(expected, actual); // Check that it throws NOT_FOUND with max depth = 1 StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel").setDirection(GraphDirection.BACKWARD) .setMaxDepth(3).build()); }); Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); } + + // Path from cnt 15 to any rel with various max edges + @Test + public void maxEdges() { + ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel") + .setDirection(GraphDirection.BACKWARD).setMaxEdges(4).build())); + List expected = List.of(fakeSWHID("cnt", 15), fakeSWHID("dir", 16), fakeSWHID("dir", 17), + fakeSWHID("rev", 18), fakeSWHID("rel", 19)); + Assertions.assertEquals(expected, actual); + + StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> { + client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel").setDirection(GraphDirection.BACKWARD) + .setMaxEdges(3).build()); + }); + Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode()); + } } diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java index 618e65b..7865f36 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java @@ -1,222 +1,250 @@ package org.softwareheritage.graph.rpc; import io.grpc.Status; import io.grpc.StatusRuntimeException; import org.junit.jupiter.api.Test; import org.softwareheritage.graph.GraphTest; import org.softwareheritage.graph.SWHID; import java.util.ArrayList; import java.util.List; import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertThrows; public class TraverseNodesTest extends TraversalServiceTest { private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) { return TraversalRequest.newBuilder().addSrc(src.toString()); } @Test public void testSrcErrors() { StatusRuntimeException thrown; thrown = assertThrows(StatusRuntimeException.class, () -> client.traverse(TraversalRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()) .forEachRemaining((n) -> { })); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client .traverse(TraversalRequest.newBuilder() .addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()) .forEachRemaining((n) -> { })); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); thrown = assertThrows(StatusRuntimeException.class, () -> client .traverse(TraversalRequest.newBuilder() .addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()) .forEachRemaining((n) -> { })); assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode()); } @Test public void forwardFromRoot() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build())); List expected = List.of(fakeSWHID("cnt", 1), fakeSWHID("cnt", 4), fakeSWHID("cnt", 5), fakeSWHID("cnt", 7), fakeSWHID("dir", 2), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("rel", 10), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("snp", 20), new SWHID(TEST_ORIGIN_ID)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardFromMiddle() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build())); List expected = List.of(fakeSWHID("cnt", 1), fakeSWHID("cnt", 4), fakeSWHID("cnt", 5), fakeSWHID("cnt", 7), fakeSWHID("cnt", 11), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("dir", 12)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardRelRev() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build())); List expected = List.of(fakeSWHID("rel", 10), fakeSWHID("rev", 9), fakeSWHID("rev", 3)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardFilterReturnedNodesDir() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("rel", 10)) .setReturnNodes(NodeFilter.newBuilder().setTypes("dir").build()).build())); List expected = List.of(fakeSWHID("dir", 2), fakeSWHID("dir", 8), fakeSWHID("dir", 6)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardFromRoot() { ArrayList actual = getSWHIDs(client.traverse( getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardFromMiddle() { ArrayList actual = getSWHIDs(client.traverse( getTraversalRequestBuilder(fakeSWHID("dir", 12)).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("dir", 12), fakeSWHID("rel", 19), fakeSWHID("rev", 13), fakeSWHID("rev", 18)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardFromLeaf() { ArrayList actual = getSWHIDs(client.traverse( getTraversalRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 4), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("dir", 12), fakeSWHID("rel", 10), fakeSWHID("rel", 19), fakeSWHID("rev", 9), fakeSWHID("rev", 13), fakeSWHID("rev", 18), fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardSnpToRev() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("snp", 20)).setEdges("snp:rev").build())); List expected = List.of(fakeSWHID("rev", 9), fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardRelToRevRevToRev() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build())); List expected = List.of(fakeSWHID("rel", 10), fakeSWHID("rev", 3), fakeSWHID("rev", 9)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardRevToAllDirToAll() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("rev", 13)).setEdges("rev:*,dir:*").build())); List expected = List.of(fakeSWHID("cnt", 1), fakeSWHID("cnt", 4), fakeSWHID("cnt", 5), fakeSWHID("cnt", 7), fakeSWHID("cnt", 11), fakeSWHID("dir", 2), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("dir", 12), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardSnpToAllRevToAll() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("snp", 20)).setEdges("snp:*,rev:*").build())); List expected = List.of(fakeSWHID("dir", 2), fakeSWHID("dir", 8), fakeSWHID("rel", 10), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardNoEdges() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(fakeSWHID("snp", 20)).setEdges("").build())); List expected = List.of(fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardRevToRevRevToRel() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("rev", 3)) .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("rel", 10), fakeSWHID("rel", 19), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13), fakeSWHID("rev", 18)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardFromRootNodesOnly() { ArrayList actual = getSWHIDs( client.traverse(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build())); List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 1), fakeSWHID("cnt", 4), fakeSWHID("cnt", 5), fakeSWHID("cnt", 7), fakeSWHID("dir", 2), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("rel", 10), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardRevToAllNodesOnly() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("rev", 3)) .setDirection(GraphDirection.BACKWARD).setEdges("rev:*").build())); List expected = List.of(fakeSWHID("rel", 10), fakeSWHID("rel", 19), fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13), fakeSWHID("rev", 18), fakeSWHID("snp", 20)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void forwardMultipleSources() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("snp", 20)) .addSrc(fakeSWHID("rel", 19).toString()).setMaxDepth(1).build())); List expected = List.of(fakeSWHID("snp", 20), fakeSWHID("rel", 19), fakeSWHID("rel", 10), fakeSWHID("rev", 9), fakeSWHID("rev", 18)); GraphTest.assertEqualsAnyOrder(expected, actual); } @Test public void backwardMultipleSources() { ArrayList actual = getSWHIDs(client.traverse(getTraversalRequestBuilder(fakeSWHID("cnt", 5)) .addSrc(fakeSWHID("dir", 16).toString()).setMaxDepth(2).setDirection(GraphDirection.BACKWARD).build())); List expected = List.of(fakeSWHID("cnt", 5), fakeSWHID("dir", 16), fakeSWHID("dir", 6), fakeSWHID("dir", 8), fakeSWHID("dir", 17), fakeSWHID("rev", 18)); GraphTest.assertEqualsAnyOrder(expected, actual); } - // Go back from cnt 15 with various max depths + // Go from rel 19 with various max depths @Test public void maxDepth() { TraversalRequest.Builder builder = getTraversalRequestBuilder(fakeSWHID("rel", 19)); ArrayList actual; List expected; actual = getSWHIDs(client.traverse(builder.setMaxDepth(0).build())); expected = List.of(fakeSWHID("rel", 19)); GraphTest.assertEqualsAnyOrder(expected, actual); actual = getSWHIDs(client.traverse(builder.setMaxDepth(1).build())); expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18)); GraphTest.assertEqualsAnyOrder(expected, actual); actual = getSWHIDs(client.traverse(builder.setMaxDepth(2).build())); expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("dir", 17)); GraphTest.assertEqualsAnyOrder(expected, actual); actual = getSWHIDs(client.traverse(builder.setMaxDepth(3).build())); expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("dir", 17), fakeSWHID("rev", 9), fakeSWHID("dir", 12), fakeSWHID("dir", 16), fakeSWHID("cnt", 14)); GraphTest.assertEqualsAnyOrder(expected, actual); } + + // Go from rel 19 with various max edges + @Test + public void maxEdges() { + TraversalRequest.Builder builder = getTraversalRequestBuilder(fakeSWHID("rel", 19)); + + ArrayList actual; + List expected; + + actual = getSWHIDs(client.traverse(builder.setMaxEdges(1).build())); + expected = List.of(fakeSWHID("rel", 19)); + GraphTest.assertEqualsAnyOrder(expected, actual); + + actual = getSWHIDs(client.traverse(builder.setMaxEdges(3).build())); + expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18)); + GraphTest.assertEqualsAnyOrder(expected, actual); + + actual = getSWHIDs(client.traverse(builder.setMaxEdges(7).build())); + expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("dir", 17), + fakeSWHID("cnt", 14)); + GraphTest.assertEqualsAnyOrder(expected, actual); + + actual = getSWHIDs(client.traverse(builder.setMaxEdges(12).build())); + expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("dir", 17), + fakeSWHID("rev", 9), fakeSWHID("dir", 12), fakeSWHID("dir", 16), fakeSWHID("cnt", 14), + fakeSWHID("cnt", 15)); + GraphTest.assertEqualsAnyOrder(expected, actual); + } }