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 f34ac3b..4c976c5 100644 --- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java @@ -1,422 +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) { 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() ? new AllowedEdges(request.getEdges()).reverse() : new AllowedEdges("*")); - SwhUnidirectionalGraph srcGraph = getDirectedGraph(bidirectionalGraph, request.getDirection()); - SwhUnidirectionalGraph dstGraph = getDirectedGraph(bidirectionalGraph, - request.hasDirectionReverse() - ? request.getDirectionReverse() - : reverseDirection(request.getDirection())); + : (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 1ba3538..c183187 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java @@ -1,146 +1,185 @@ 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(), Status.NOT_FOUND); + 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(), Status.NOT_FOUND); + 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()); } } 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 66cbbd9..b95457d 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java @@ -1,128 +1,146 @@ 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 + @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()); + } } 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 274776e..618e65b 100644 --- a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java @@ -1,196 +1,222 @@ 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 + @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); + } } diff --git a/proto/swhgraph.proto b/proto/swhgraph.proto index 192e7ff..435461d 100644 --- a/proto/swhgraph.proto +++ b/proto/swhgraph.proto @@ -1,146 +1,146 @@ syntax = "proto3"; import "google/protobuf/field_mask.proto"; option java_multiple_files = true; option java_package = "org.softwareheritage.graph.rpc"; option java_outer_classname = "GraphService"; package swh.graph; service TraversalService { rpc Traverse (TraversalRequest) returns (stream Node); rpc FindPathTo (FindPathToRequest) returns (Path); rpc FindPathBetween (FindPathBetweenRequest) returns (Path); rpc CountNodes (TraversalRequest) returns (CountResponse); rpc CountEdges (TraversalRequest) returns (CountResponse); rpc Stats (StatsRequest) returns (StatsResponse); rpc GetNode (GetNodeRequest) returns (Node); } enum GraphDirection { FORWARD = 0; BACKWARD = 1; } message TraversalRequest { repeated string src = 1; GraphDirection direction = 2; optional string edges = 3; optional int64 max_edges = 4; optional int64 min_depth = 5; optional int64 max_depth = 6; optional NodeFilter return_nodes = 7; optional google.protobuf.FieldMask mask = 8; } message FindPathToRequest { repeated string src = 1; optional NodeFilter target = 2; GraphDirection direction = 3; optional string edges = 4; optional int64 max_edges = 5; optional int64 max_depth = 6; optional google.protobuf.FieldMask mask = 7; } message FindPathBetweenRequest { repeated string src = 1; repeated string dst = 2; GraphDirection direction = 3; optional GraphDirection direction_reverse = 4; optional string edges = 5; optional string edges_reverse = 6; optional int64 max_edges = 7; optional int64 max_depth = 8; optional google.protobuf.FieldMask mask = 9; } message NodeFilter { optional string types = 1; optional int64 min_traversal_successors = 2; optional int64 max_traversal_successors = 3; } message Node { string swhid = 1; repeated Successor successor = 2; oneof data { ContentData cnt = 3; RevisionData rev = 5; ReleaseData rel = 6; OriginData ori = 8; }; optional int64 num_successors = 9; } message Path { repeated Node node = 1; - optional int64 middle_node_index = 2; + optional int32 middle_node_index = 2; } message Successor { optional string swhid = 1; repeated EdgeLabel label = 2; } message ContentData { optional int64 length = 1; optional bool is_skipped = 2; } message RevisionData { optional int64 author = 1; optional int64 author_date = 2; optional int32 author_date_offset = 3; optional int64 committer = 4; optional int64 committer_date = 5; optional int32 committer_date_offset = 6; optional bytes message = 7; } message ReleaseData { optional int64 author = 1; optional int64 author_date = 2; optional int32 author_date_offset = 3; optional bytes name = 4; optional bytes message = 5; } message OriginData { optional string url = 1; } message EdgeLabel { bytes name = 1; int32 permission = 2; } message CountResponse { int64 count = 1; } message StatsRequest { } message StatsResponse { int64 num_nodes = 1; int64 num_edges = 2; double compression = 3; double bits_per_node = 4; double bits_per_edge = 5; double avg_locality = 6; int64 indegree_min = 7; int64 indegree_max = 8; double indegree_avg = 9; int64 outdegree_min = 10; int64 outdegree_max = 11; double outdegree_avg = 12; } message GetNodeRequest { string swhid = 1; optional google.protobuf.FieldMask mask = 8; }