diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml index 1817a76..5bf56ae 100644 --- a/.pre-commit-config.yaml +++ b/.pre-commit-config.yaml @@ -1,52 +1,52 @@ repos: - repo: https://github.com/pre-commit/pre-commit-hooks rev: v4.1.0 hooks: - id: trailing-whitespace - id: check-json - id: check-yaml - repo: https://gitlab.com/pycqa/flake8 rev: 4.0.1 hooks: - id: flake8 additional_dependencies: [flake8-bugbear==22.3.23] - repo: https://github.com/codespell-project/codespell rev: v2.1.0 hooks: - id: codespell name: Check source code spelling - args: ["-L te,wth,alledges"] + args: ["-L te,wth,alledges,afterall"] stages: [commit] - repo: local hooks: - id: mypy name: mypy entry: mypy args: [swh] pass_filenames: false language: system types: [python] - repo: https://github.com/PyCQA/isort rev: 5.10.1 hooks: - id: isort - repo: https://github.com/python/black rev: 22.3.0 hooks: - id: black - repo: local hooks: - id: java-coding-style name: java style entry: mvn args: ["-f", "java/pom.xml", "spotless:apply"] pass_filenames: false language: system exclude: ^swh/graph/rpc/ diff --git a/java/pom.xml b/java/pom.xml index 234b3b9..3c2ab60 100644 --- a/java/pom.xml +++ b/java/pom.xml @@ -1,420 +1,429 @@ 4.0.0 org.softwareheritage.graph swh-graph ${git.closest.tag.name} swh-graph https://forge.softwareheritage.org/source/swh-graph/ UTF-8 11 3.20.1 1.46.0 ch.qos.logback logback-classic 1.2.3 org.junit.jupiter junit-jupiter-api 5.7.0 test org.junit.vintage junit-vintage-engine 5.7.0 junit junit 4.12 org.junit.jupiter junit-jupiter-engine 5.7.0 test org.hamcrest hamcrest 2.2 test io.javalin javalin 3.0.0 org.slf4j slf4j-simple 1.7.26 com.fasterxml.jackson.core jackson-databind 2.13.0 it.unimi.dsi webgraph-big 3.6.7 it.unimi.dsi fastutil 8.5.8 it.unimi.dsi dsiutils 2.7.1 it.unimi.dsi sux4j 5.3.1 it.unimi.dsi law 2.7.2 org.apache.hadoop hadoop-common org.umlgraph umlgraph org.eclipse.jetty.aggregate jetty-all it.unimi.di mg4j it.unimi.di mg4j-big com.martiansoftware jsap 2.1 net.sf.py4j py4j 0.10.9.3 commons-codec commons-codec 1.15 com.github.luben zstd-jni 1.5.1-1 org.apache.orc orc-core 1.7.1 org.apache.hadoop hadoop-common 3.3.1 org.apache.hadoop hadoop-client-runtime 3.3.1 com.google.protobuf protobuf-java ${protobuf.version} io.grpc grpc-netty-shaded ${grpc.version} io.grpc grpc-protobuf ${grpc.version} io.grpc grpc-stub ${grpc.version} io.grpc grpc-services ${grpc.version} + + io.grpc + grpc-testing + ${grpc.version} + javax.annotation javax.annotation-api 1.3.2 maven-clean-plugin 3.1.0 maven-resources-plugin 3.0.2 maven-compiler-plugin 3.8.0 11 11 -verbose -Xlint:all maven-surefire-plugin 2.22.2 maven-failsafe-plugin 2.22.2 maven-jar-plugin 3.0.2 maven-install-plugin 2.5.2 maven-deploy-plugin 2.8.2 maven-site-plugin 3.7.1 maven-project-info-reports-plugin 3.0.0 + + maven-dependency-plugin + 3.1.2 + maven-assembly-plugin 3.3.0 org.softwareheritage.graph.server.App jar-with-dependencies false make-assembly package single com.diffplug.spotless spotless-maven-plugin 2.22.1 *.md .gitignore true 4 4.16.0 .coding-style.xml pl.project13.maven git-commit-id-plugin 3.0.1 get-the-git-infos revision initialize true true true true v* git.closest.tag.name ^v true maven-source-plugin 2.1.1 bundle-sources package jar-no-fork test-jar-no-fork org.apache.maven.plugins maven-javadoc-plugin 3.3.1 resource-bundles package resource-bundle test-resource-bundle false javadoc-jar package jar true it.unimi.dsi:webgraph-big:* https://webgraph.di.unimi.it/docs-big/ https://dsiutils.di.unimi.it/docs/ https://fastutil.di.unimi.it/docs/ https://law.di.unimi.it/software/law-docs/ implSpec a Implementation Requirements: implNote a Implementation Note: org.xolstice.maven.plugins protobuf-maven-plugin 0.6.1 com.google.protobuf:protoc:${protobuf.version}:exe:${os.detected.classifier} grpc-java io.grpc:protoc-gen-grpc-java:${grpc.version}:exe:${os.detected.classifier} compile compile-custom test-compile test-compile-custom kr.motd.maven os-maven-plugin 1.6.2 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 e696d06..e7e9000 100644 --- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java +++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java @@ -1,275 +1,275 @@ package org.softwareheritage.graph.rpc; import com.google.protobuf.ByteString; import it.unimi.dsi.big.webgraph.LazyLongIterator; import it.unimi.dsi.big.webgraph.labelling.ArcLabelledNodeIterator; import it.unimi.dsi.big.webgraph.labelling.Label; import org.softwareheritage.graph.*; import org.softwareheritage.graph.labels.DirEntry; import java.util.*; public class Traversal { private static LazyLongIterator filterSuccessors(SwhUnidirectionalGraph g, long nodeId, AllowedEdges allowedEdges) { if (allowedEdges.restrictedTo == null) { // All edges are allowed, bypass edge check return g.successors(nodeId); } else { LazyLongIterator allSuccessors = g.successors(nodeId); return new LazyLongIterator() { @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 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; } - long outdegree = g.outdegree(nodeId); - if (filter.hasMinTraversalSuccessors() && outdegree < filter.getMinTraversalSuccessors()) { - return false; - } - if (filter.hasMaxTraversalSuccessors() && outdegree > filter.getMaxTraversalSuccessors()) { - return false; - } - return true; } } public static SwhUnidirectionalGraph getDirectedGraph(SwhBidirectionalGraph g, TraversalRequest request) { switch (request.getDirection()) { case FORWARD: return g.getForwardGraph(); case BACKWARD: return g.getBackwardGraph(); case BOTH: return new SwhUnidirectionalGraph(g.symmetrize(), g.getProperties()); } throw new IllegalArgumentException("Unknown direction: " + request.getDirection()); } public static void simpleTraversal(SwhBidirectionalGraph bidirectionalGraph, TraversalRequest request, NodeObserver nodeObserver) { SwhUnidirectionalGraph g = getDirectedGraph(bidirectionalGraph, request); NodeFilterChecker nodeReturnChecker = new NodeFilterChecker(g, request.getReturnNodes()); AllowedEdges allowedEdges = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*"); Queue queue = new ArrayDeque<>(); HashSet visited = new HashSet<>(); request.getSrcList().forEach(srcSwhid -> { long srcNodeId = g.getNodeId(new SWHID(srcSwhid)); queue.add(srcNodeId); visited.add(srcNodeId); }); queue.add(-1L); // Depth sentinel long edgesAccessed = 0; long currentDepth = 0; while (!queue.isEmpty()) { long curr = queue.poll(); if (curr == -1L) { ++currentDepth; if (!queue.isEmpty()) { queue.add(-1L); } continue; } if (request.hasMaxDepth() && currentDepth > request.getMaxDepth()) { break; } edgesAccessed += g.outdegree(curr); if (request.hasMaxEdges() && edgesAccessed >= request.getMaxEdges()) { break; } Node.Builder nodeBuilder = null; if (nodeReturnChecker.allowed(curr) && (!request.hasMinDepth() || currentDepth >= request.getMinDepth())) { nodeBuilder = Node.newBuilder(); buildNodeProperties(g, request.getReturnFields(), nodeBuilder, curr); } ArcLabelledNodeIterator.LabelledArcIterator it = filterLabelledSuccessors(g, curr, allowedEdges); + long traversalSuccessors = 0; for (long succ; (succ = it.nextLong()) != -1;) { + traversalSuccessors++; if (!visited.contains(succ)) { queue.add(succ); visited.add(succ); } buildSuccessorProperties(g, request.getReturnFields(), nodeBuilder, curr, succ, it.label()); } + if (request.getReturnNodes().hasMinTraversalSuccessors() + && traversalSuccessors < request.getReturnNodes().getMinTraversalSuccessors() + || request.getReturnNodes().hasMaxTraversalSuccessors() + && traversalSuccessors > request.getReturnNodes().getMaxTraversalSuccessors()) { + nodeBuilder = null; + } if (nodeBuilder != null) { nodeObserver.onNext(nodeBuilder.build()); } } } private static void buildNodeProperties(SwhUnidirectionalGraph graph, NodeFields fields, Node.Builder nodeBuilder, long node) { if (fields == null || !fields.hasSwhid() || fields.getSwhid()) { nodeBuilder.setSwhid(graph.getSWHID(node).toString()); } if (fields == null) { return; } switch (graph.getNodeType(node)) { case CNT: if (fields.hasCntLength()) { nodeBuilder.setCntLength(graph.getContentLength(node)); } if (fields.hasCntIsSkipped()) { nodeBuilder.setCntIsSkipped(graph.isContentSkipped(node)); } break; case REV: if (fields.getRevAuthor()) { nodeBuilder.setRevAuthor(graph.getAuthorId(node)); } if (fields.getRevCommitter()) { nodeBuilder.setRevAuthor(graph.getCommitterId(node)); } if (fields.getRevAuthorDate()) { nodeBuilder.setRevAuthorDate(graph.getAuthorTimestamp(node)); } if (fields.getRevAuthorDateOffset()) { nodeBuilder.setRevAuthorDateOffset(graph.getAuthorTimestampOffset(node)); } if (fields.getRevCommitterDate()) { nodeBuilder.setRevCommitterDate(graph.getCommitterTimestamp(node)); } if (fields.getRevCommitterDateOffset()) { nodeBuilder.setRevCommitterDateOffset(graph.getCommitterTimestampOffset(node)); } if (fields.getRevMessage()) { byte[] msg = graph.getMessage(node); if (msg != null) { nodeBuilder.setRevMessage(ByteString.copyFrom(msg)); } } break; case REL: if (fields.getRelAuthor()) { nodeBuilder.setRelAuthor(graph.getAuthorId(node)); } if (fields.getRelAuthorDate()) { nodeBuilder.setRelAuthorDate(graph.getAuthorTimestamp(node)); } if (fields.getRelAuthorDateOffset()) { nodeBuilder.setRelAuthorDateOffset(graph.getAuthorTimestampOffset(node)); } if (fields.getRelName()) { byte[] msg = graph.getTagName(node); if (msg != null) { nodeBuilder.setRelName(ByteString.copyFrom(msg)); } } if (fields.getRelMessage()) { byte[] msg = graph.getMessage(node); if (msg != null) { nodeBuilder.setRelMessage(ByteString.copyFrom(msg)); } } break; case ORI: if (fields.getOriUrl()) { String url = graph.getUrl(node); if (url != null) { nodeBuilder.setOriUrl(url); } } } } private static void buildSuccessorProperties(SwhUnidirectionalGraph graph, NodeFields fields, Node.Builder nodeBuilder, long src, long dst, Label label) { if (nodeBuilder != null && fields != null && fields.getSuccessor()) { Successor.Builder successorBuilder = Successor.newBuilder(); if (!fields.hasSuccessorSwhid() || fields.getSuccessorSwhid()) { successorBuilder.setSwhid(graph.getSWHID(dst).toString()); } if (fields.getSuccessorLabel()) { DirEntry[] entries = (DirEntry[]) label.get(); for (DirEntry entry : entries) { EdgeLabel.Builder builder = EdgeLabel.newBuilder(); builder.setName(ByteString.copyFrom(graph.getLabelName(entry.filenameId))); builder.setPermission(entry.permission); successorBuilder.addLabel(builder.build()); } } nodeBuilder.addSuccessor(successorBuilder.build()); } } public interface NodeObserver { void onNext(Node nodeId); } } diff --git a/java/src/test/java/org/softwareheritage/graph/GraphTest.java b/java/src/test/java/org/softwareheritage/graph/GraphTest.java index 9b7a64b..e047f68 100644 --- a/java/src/test/java/org/softwareheritage/graph/GraphTest.java +++ b/java/src/test/java/org/softwareheritage/graph/GraphTest.java @@ -1,53 +1,56 @@ package org.softwareheritage.graph; import java.io.FileInputStream; import java.io.IOException; import java.nio.file.Path; import java.nio.file.Paths; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import com.github.luben.zstd.ZstdInputStream; import it.unimi.dsi.big.webgraph.LazyLongIterator; import it.unimi.dsi.big.webgraph.LazyLongIterators; import org.hamcrest.MatcherAssert; import org.junit.jupiter.api.BeforeAll; import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder; public class GraphTest { static SwhBidirectionalGraph graph; final protected String TEST_ORIGIN_ID = "swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054"; @BeforeAll public static void setUp() throws IOException { - Path graphPath = Paths.get("..", "swh", "graph", "tests", "dataset", "compressed", "example"); - graph = SwhBidirectionalGraph.loadMapped(graphPath.toString()); + graph = SwhBidirectionalGraph.loadLabelled(getGraphPath().toString()); } - public SwhBidirectionalGraph getGraph() { + public static Path getGraphPath() { + return Paths.get("..", "swh", "graph", "tests", "dataset", "compressed", "example"); + } + + public static SwhBidirectionalGraph getGraph() { return graph; } public static SWHID fakeSWHID(String type, int num) { return new SWHID(String.format("swh:1:%s:%040d", type, num)); } public static void assertEqualsAnyOrder(Collection expecteds, Collection actuals) { MatcherAssert.assertThat(expecteds, containsInAnyOrder(actuals.toArray())); } public static ArrayList lazyLongIteratorToList(LazyLongIterator input) { ArrayList inputList = new ArrayList<>(); Iterator inputIt = LazyLongIterators.eager(input); inputIt.forEachRemaining(inputList::add); return inputList; } public static String[] readZstFile(Path zstFile) throws IOException { ZstdInputStream zis = new ZstdInputStream(new FileInputStream(zstFile.toFile())); return (new String(zis.readAllBytes())).split("\n"); } } diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraversalServiceTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraversalServiceTest.java new file mode 100644 index 0000000..464675a --- /dev/null +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraversalServiceTest.java @@ -0,0 +1,48 @@ +package org.softwareheritage.graph.rpc; + +import io.grpc.ManagedChannel; +import io.grpc.Server; +import io.grpc.inprocess.InProcessChannelBuilder; +import io.grpc.inprocess.InProcessServerBuilder; +import io.grpc.testing.GrpcCleanupRule; +import org.junit.Rule; +import org.junit.jupiter.api.AfterAll; +import org.junit.jupiter.api.BeforeAll; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SWHID; + +import java.util.ArrayList; +import java.util.Iterator; + +public class TraversalServiceTest extends GraphTest { + @Rule + public final GrpcCleanupRule grpcCleanup = new GrpcCleanupRule(); + + private static Server server; + private static ManagedChannel channel; + protected static TraversalServiceGrpc.TraversalServiceBlockingStub client; + + @BeforeAll + static void setup() throws Exception { + String serverName = InProcessServerBuilder.generateName(); + assert getGraph() != null; + server = InProcessServerBuilder.forName(serverName).directExecutor() + .addService(new GraphServer.TraversalService(getGraph())).build().start(); + channel = InProcessChannelBuilder.forName(serverName).directExecutor().build(); + client = TraversalServiceGrpc.newBlockingStub(channel); + } + + @AfterAll + static void teardown() throws Exception { + channel.shutdownNow(); + server.shutdownNow(); + } + + public ArrayList getSWHIDs(Iterator it) { + ArrayList actualLeaves = new ArrayList<>(); + it.forEachRemaining((Node n) -> { + actualLeaves.add(new SWHID(n.getSwhid())); + }); + return actualLeaves; + } +} diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java new file mode 100644 index 0000000..907aec9 --- /dev/null +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java @@ -0,0 +1,93 @@ +package org.softwareheritage.graph.rpc; + +import org.junit.jupiter.api.Test; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SWHID; + +import java.util.ArrayList; + +public class TraverseLeavesTest extends TraversalServiceTest { + private TraversalRequest.Builder getLeavesRequestBuilder(SWHID src) { + return TraversalRequest.newBuilder().addSrc(src.toString()) + .setReturnNodes(NodeFilter.newBuilder().setMaxTraversalSuccessors(0).build()); + } + + @Test + public void forwardFromSnp() { + TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("snp", 20)).build(); + + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + + ArrayList actualLeaves = getSWHIDs(client.traverse(request)); + GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); + } + + @Test + public void forwardFromRel() { + TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("rel", 19)).build(); + ArrayList actualLeaves = getSWHIDs(client.traverse(request)); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000015")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000014")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000011")); + + GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); + } + + @Test + public void backwardFromLeaf() { + TraversalRequest request1 = getLeavesRequestBuilder(fakeSWHID("cnt", 15)).setDirection(GraphDirection.BACKWARD) + .build(); + ArrayList actualLeaves1 = getSWHIDs(client.traverse(request1)); + ArrayList expectedLeaves1 = new ArrayList<>(); + expectedLeaves1.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019")); + GraphTest.assertEqualsAnyOrder(expectedLeaves1, actualLeaves1); + + TraversalRequest request2 = getLeavesRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD) + .build(); + ArrayList actualLeaves2 = getSWHIDs(client.traverse(request2)); + ArrayList expectedLeaves2 = new ArrayList<>(); + expectedLeaves2.add(new SWHID(TEST_ORIGIN_ID)); + expectedLeaves2.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019")); + GraphTest.assertEqualsAnyOrder(expectedLeaves2, actualLeaves2); + } + + @Test + public void forwardRevToRevOnly() { + TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("rev", 18)).setEdges("rev:rev").build(); + ArrayList actualLeaves = getSWHIDs(client.traverse(request)); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003")); + GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); + } + + @Test + public void forwardDirToAll() { + TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("dir", 8)).setEdges("dir:*").build(); + ArrayList actualLeaves = getSWHIDs(client.traverse(request)); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); + } + + @Test + public void backwardCntToDirDirToDir() { + TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("cnt", 5)).setEdges("cnt:dir,dir:dir") + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actualLeaves = getSWHIDs(client.traverse(request)); + ArrayList expectedLeaves = new ArrayList<>(); + expectedLeaves.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000012")); + GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves); + } +} diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNeighborsTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNeighborsTest.java new file mode 100644 index 0000000..bb43920 --- /dev/null +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNeighborsTest.java @@ -0,0 +1,130 @@ +package org.softwareheritage.graph.rpc; + +import org.junit.jupiter.api.Test; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SWHID; + +import java.util.ArrayList; + +public class TraverseNeighborsTest extends TraversalServiceTest { + private TraversalRequest.Builder getNeighborsRequestBuilder(SWHID src) { + return TraversalRequest.newBuilder().addSrc(src.toString()).setMinDepth(1).setMaxDepth(1); + } + + @Test + public void zeroNeighbor() { + ArrayList expectedNodes = new ArrayList<>(); + + TraversalRequest request1 = getNeighborsRequestBuilder(new SWHID(TEST_ORIGIN_ID)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals1 = getSWHIDs(client.traverse(request1)); + GraphTest.assertEqualsAnyOrder(expectedNodes, actuals1); + + TraversalRequest request2 = getNeighborsRequestBuilder(fakeSWHID("cnt", 4)).build(); + ArrayList actuals2 = getSWHIDs(client.traverse(request2)); + GraphTest.assertEqualsAnyOrder(expectedNodes, actuals2); + + TraversalRequest request3 = getNeighborsRequestBuilder(fakeSWHID("cnt", 15)).build(); + ArrayList actuals3 = getSWHIDs(client.traverse(request3)); + GraphTest.assertEqualsAnyOrder(expectedNodes, actuals3); + + TraversalRequest request4 = getNeighborsRequestBuilder(fakeSWHID("rel", 19)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals4 = getSWHIDs(client.traverse(request4)); + GraphTest.assertEqualsAnyOrder(expectedNodes, actuals4); + + TraversalRequest request5 = getNeighborsRequestBuilder(fakeSWHID("dir", 8)).setEdges("snp:*,rev:*,rel:*") + .build(); + ArrayList actuals5 = getSWHIDs(client.traverse(request5)); + GraphTest.assertEqualsAnyOrder(expectedNodes, actuals5); + } + + @Test + public void oneNeighbor() { + TraversalRequest request1 = getNeighborsRequestBuilder(fakeSWHID("rev", 3)).build(); + ArrayList actuals1 = getSWHIDs(client.traverse(request1)); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002")); + GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); + + TraversalRequest request2 = getNeighborsRequestBuilder(fakeSWHID("dir", 17)).setEdges("dir:cnt").build(); + ArrayList actuals2 = getSWHIDs(client.traverse(request2)); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000014")); + GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); + + TraversalRequest request3 = getNeighborsRequestBuilder(fakeSWHID("dir", 12)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals3 = getSWHIDs(client.traverse(request3)); + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3); + + TraversalRequest request4 = getNeighborsRequestBuilder(fakeSWHID("rev", 9)) + .setDirection(GraphDirection.BACKWARD).setEdges("rev:rev").build(); + ArrayList actuals4 = getSWHIDs(client.traverse(request4)); + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4); + + TraversalRequest request5 = getNeighborsRequestBuilder(fakeSWHID("snp", 20)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals5 = getSWHIDs(client.traverse(request5)); + ArrayList expectedNodes5 = new ArrayList<>(); + expectedNodes5.add(new SWHID(TEST_ORIGIN_ID)); + GraphTest.assertEqualsAnyOrder(expectedNodes5, actuals5); + } + + @Test + public void twoNeighbors() { + TraversalRequest request1 = getNeighborsRequestBuilder(fakeSWHID("snp", 20)).build(); + ArrayList actuals1 = getSWHIDs(client.traverse(request1)); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes1.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009")); + GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); + + TraversalRequest request2 = getNeighborsRequestBuilder(fakeSWHID("dir", 8)).setEdges("dir:cnt").build(); + ArrayList actuals2 = getSWHIDs(client.traverse(request2)); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); + + TraversalRequest request3 = getNeighborsRequestBuilder(fakeSWHID("cnt", 1)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals3 = getSWHIDs(client.traverse(request3)); + ArrayList expectedNodes3 = new ArrayList<>(); + expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000008")); + expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002")); + GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3); + + TraversalRequest request4 = getNeighborsRequestBuilder(fakeSWHID("rev", 9)) + .setDirection(GraphDirection.BACKWARD).setEdges("rev:snp,rev:rel").build(); + ArrayList actuals4 = getSWHIDs(client.traverse(request4)); + ArrayList expectedNodes4 = new ArrayList<>(); + expectedNodes4.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes4.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4); + } + + @Test + public void threeNeighbors() { + TraversalRequest request1 = getNeighborsRequestBuilder(fakeSWHID("dir", 8)).build(); + ArrayList actuals1 = getSWHIDs(client.traverse(request1)); + ArrayList expectedNodes1 = new ArrayList<>(); + expectedNodes1.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000006")); + expectedNodes1.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001")); + expectedNodes1.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007")); + GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1); + + TraversalRequest request2 = getNeighborsRequestBuilder(fakeSWHID("rev", 9)) + .setDirection(GraphDirection.BACKWARD).build(); + ArrayList actuals2 = getSWHIDs(client.traverse(request2)); + ArrayList expectedNodes2 = new ArrayList<>(); + expectedNodes2.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020")); + expectedNodes2.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010")); + expectedNodes2.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013")); + GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2); + } +} diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java new file mode 100644 index 0000000..0554ae1 --- /dev/null +++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseNodesTest.java @@ -0,0 +1,149 @@ +package org.softwareheritage.graph.rpc; + +import org.junit.jupiter.api.Test; +import org.softwareheritage.graph.GraphTest; +import org.softwareheritage.graph.SWHID; + +import java.util.ArrayList; +import java.util.List; + +public class TraverseNodesTest extends TraversalServiceTest { + private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) { + return TraversalRequest.newBuilder().addSrc(src.toString()); + } + + @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); + } +} diff --git a/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2Test.java b/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2Test.java index aab87ad..d368b03 100644 --- a/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2Test.java +++ b/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinBigQuickSort2Test.java @@ -1,96 +1,86 @@ package org.softwareheritage.graph.utils; import it.unimi.dsi.fastutil.BigArrays; import it.unimi.dsi.fastutil.longs.LongArrays; import org.junit.jupiter.api.Test; import java.util.Random; import static org.junit.jupiter.api.Assertions.assertTrue; public class ForkJoinBigQuickSort2Test { private static long[] identity(final int n) { final long[] perm = new long[n]; for (int i = perm.length; i-- != 0;) perm[i] = i; return perm; } private static void checkArraySorted(long[] x, long[] y) { checkArraySorted(x, y, 0, x.length); } private static void checkArraySorted(long[] x, long[] y, int from, int to) { for (int i = to - 1; i-- != from;) assertTrue(x[i] < x[i + 1] || x[i] == x[i + 1] && (y[i] < y[i + 1] || y[i] == y[i + 1]), String.format("%d: <%d, %d>, <%d, %d>", i, x[i], y[i], x[i + 1], y[i + 1])); } private static void sortBig2(long[] x, long[] y, long from, long to) { ForkJoinBigQuickSort2.parallelQuickSort(BigArrays.wrap(x), BigArrays.wrap(y), from, to); } private static void sortBig2(long[] x, long[] y) { sortBig2(x, y, 0, x.length); } @Test public void testParallelQuickSort3() { final long[][] d = new long[2][]; d[0] = new long[10]; for (int i = d[0].length; i-- != 0;) d[0][i] = 3 - i % 3; d[1] = LongArrays.shuffle(identity(10), new Random(0)); sortBig2(d[0], d[1]); checkArraySorted(d[0], d[1]); d[0] = new long[100000]; for (int i = d[0].length; i-- != 0;) d[0][i] = 100 - i % 100; d[1] = LongArrays.shuffle(identity(100000), new Random(6)); sortBig2(d[0], d[1]); checkArraySorted(d[0], d[1]); d[0] = new long[10]; for (int i = d[0].length; i-- != 0;) d[0][i] = i % 3 - 2; Random random = new Random(0); d[1] = new long[d[0].length]; for (int i = d[1].length; i-- != 0;) d[1][i] = random.nextInt(); sortBig2(d[0], d[1]); checkArraySorted(d[0], d[1]); d[0] = new long[100000]; d[1] = new long[100000]; sortBig2(d[0], d[1]); checkArraySorted(d[0], d[1]); d[0] = new long[100000]; random = new Random(0); for (int i = d[0].length; i-- != 0;) d[0][i] = random.nextInt(); d[1] = new long[d[0].length]; for (int i = d[1].length; i-- != 0;) d[1][i] = random.nextInt(); sortBig2(d[0], d[1]); checkArraySorted(d[0], d[1]); for (int i = 100; i-- != 10;) d[0][i] = random.nextInt(); for (int i = 100; i-- != 10;) d[1][i] = random.nextInt(); sortBig2(d[0], d[1], 10, 100); checkArraySorted(d[0], d[1], 10, 100); - - d[0] = new long[10000000]; - random = new Random(0); - for (int i = d[0].length; i-- != 0;) - d[0][i] = random.nextInt(); - d[1] = new long[d[0].length]; - for (int i = d[1].length; i-- != 0;) - d[1][i] = random.nextInt(); - sortBig2(d[0], d[1]); - checkArraySorted(d[0], d[1]); } } diff --git a/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3Test.java b/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3Test.java index cc83baf..a559b4a 100644 --- a/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3Test.java +++ b/java/src/test/java/org/softwareheritage/graph/utils/ForkJoinQuickSort3Test.java @@ -1,103 +1,90 @@ package org.softwareheritage.graph.utils; import it.unimi.dsi.fastutil.longs.LongArrays; import org.junit.jupiter.api.Test; import java.util.Random; import static org.junit.jupiter.api.Assertions.assertTrue; public class ForkJoinQuickSort3Test { private static long[] identity(final int n) { final long[] perm = new long[n]; for (int i = perm.length; i-- != 0;) perm[i] = i; return perm; } private static void checkArraySorted(long[] x, long[] y, long[] z) { checkArraySorted(x, y, z, 0, x.length); } private static void checkArraySorted(long[] x, long[] y, long[] z, int from, int to) { for (int i = to - 1; i-- != from;) assertTrue(x[i] < x[i + 1] || x[i] == x[i + 1] && (y[i] < y[i + 1] || y[i] == y[i + 1] && z[i] <= z[i + 1]), String.format("%d: <%d, %d, %d>, <%d, %d, %d>", i, x[i], y[i], z[i], x[i + 1], y[i + 1], z[i + 1])); } @Test public void testParallelQuickSort3() { final long[][] d = new long[3][]; d[0] = new long[10]; for (int i = d[0].length; i-- != 0;) d[0][i] = 3 - i % 3; d[1] = LongArrays.shuffle(identity(10), new Random(0)); d[2] = LongArrays.shuffle(identity(10), new Random(1)); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); checkArraySorted(d[0], d[1], d[2]); d[0] = new long[100000]; for (int i = d[0].length; i-- != 0;) d[0][i] = 100 - i % 100; d[1] = LongArrays.shuffle(identity(100000), new Random(6)); d[2] = LongArrays.shuffle(identity(100000), new Random(7)); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); checkArraySorted(d[0], d[1], d[2]); d[0] = new long[10]; for (int i = d[0].length; i-- != 0;) d[0][i] = i % 3 - 2; Random random = new Random(0); d[1] = new long[d[0].length]; for (int i = d[1].length; i-- != 0;) d[1][i] = random.nextInt(); d[2] = new long[d[0].length]; for (int i = d[2].length; i-- != 0;) d[2][i] = random.nextInt(); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); checkArraySorted(d[0], d[1], d[2]); d[0] = new long[100000]; d[1] = new long[100000]; d[2] = new long[100000]; for (int i = d[0].length; i-- != 0;) d[2][i] = random.nextInt(); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); checkArraySorted(d[0], d[1], d[2]); d[0] = new long[100000]; random = new Random(0); for (int i = d[0].length; i-- != 0;) d[0][i] = random.nextInt(); d[1] = new long[d[0].length]; for (int i = d[1].length; i-- != 0;) d[1][i] = random.nextInt(); d[2] = new long[d[0].length]; for (int i = d[2].length; i-- != 0;) d[2][i] = random.nextInt(); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); checkArraySorted(d[0], d[1], d[2]); for (int i = 100; i-- != 10;) d[0][i] = random.nextInt(); for (int i = 100; i-- != 10;) d[1][i] = random.nextInt(); for (int i = 100; i-- != 10;) d[2][i] = random.nextInt(); ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2], 10, 100); checkArraySorted(d[0], d[1], d[2], 10, 100); - - d[0] = new long[10000000]; - random = new Random(0); - for (int i = d[0].length; i-- != 0;) - d[0][i] = random.nextInt(); - d[1] = new long[d[0].length]; - for (int i = d[1].length; i-- != 0;) - d[1][i] = random.nextInt(); - d[2] = new long[d[0].length]; - for (int i = d[2].length; i-- != 0;) - d[2][i] = random.nextInt(); - ForkJoinQuickSort3.parallelQuickSort(d[0], d[1], d[2]); - checkArraySorted(d[0], d[1], d[2]); } } diff --git a/swh/graph/naive_client.py b/swh/graph/naive_client.py index bf4733b..1b58f6d 100644 --- a/swh/graph/naive_client.py +++ b/swh/graph/naive_client.py @@ -1,395 +1,395 @@ # Copyright (C) 2021 The Software Heritage developers # See the AUTHORS file at the top-level directory of this distribution # License: GNU General Public License version 3, or any later version # See top-level LICENSE file for more information import functools import inspect import re import statistics from typing import ( Callable, Dict, Iterable, Iterator, List, Optional, Set, Tuple, TypeVar, Union, ) from swh.model.swhids import CoreSWHID, ExtendedSWHID, ValidationError from .client import GraphArgumentException _NODE_TYPES = "ori|snp|rel|rev|dir|cnt" NODES_RE = re.compile(rf"(\*|{_NODE_TYPES})") EDGES_RE = re.compile(rf"(\*|{_NODE_TYPES}):(\*|{_NODE_TYPES})") T = TypeVar("T", bound=Callable) SWHIDlike = Union[CoreSWHID, ExtendedSWHID, str] def check_arguments(f: T) -> T: """Decorator for generic argument checking for methods of NaiveClient. Checks ``src`` is a valid and known SWHID, and ``edges`` has the right format.""" signature = inspect.signature(f) @functools.wraps(f) def newf(*args, **kwargs): __tracebackhide__ = True # for pytest try: bound_args = signature.bind(*args, **kwargs) except TypeError as e: # rethrow the exception from here so pytest doesn't flood the terminal # with signature.bind's call stack. raise TypeError(*e.args) from None self = bound_args.arguments["self"] src = bound_args.arguments.get("src") if src: self._check_swhid(src) edges = bound_args.arguments.get("edges") if edges: if edges != "*" and not EDGES_RE.match(edges): raise GraphArgumentException(f"invalid edge restriction: {edges}") return_types = bound_args.arguments.get("return_types") if return_types: if not NODES_RE.match(return_types): raise GraphArgumentException( f"invalid return_types restriction: {return_types}" ) return f(*args, **kwargs) return newf # type: ignore def filter_node_types(node_types: str, nodes: Iterable[str]) -> Iterator[str]: if node_types == "*": yield from nodes else: prefixes = tuple(f"swh:1:{type_}:" for type_ in node_types.split(",")) for node in nodes: if node.startswith(prefixes): yield node class NaiveClient: - """An alternative implementation of :class:`swh.graph.backend.Backend`, - written in pure-python and meant for simulating it in other components' test - cases; constructed from a list of nodes and (directed) edges, both - represented as SWHIDs. + """An alternative implementation of the graph server, written in + pure-python and meant for simulating it in other components' test cases; + constructed from a list of nodes and (directed) edges, both represented as + SWHIDs. It is NOT meant to be efficient in any way; only to be a very simple implementation that provides the same behavior. >>> nodes = [ ... "swh:1:rev:1111111111111111111111111111111111111111", ... "swh:1:rev:2222222222222222222222222222222222222222", ... "swh:1:rev:3333333333333333333333333333333333333333", ... ] >>> edges = [ ... ( ... "swh:1:rev:1111111111111111111111111111111111111111", ... "swh:1:rev:2222222222222222222222222222222222222222", ... ), ... ( ... "swh:1:rev:2222222222222222222222222222222222222222", ... "swh:1:rev:3333333333333333333333333333333333333333", ... ), ... ] >>> c = NaiveClient(nodes=nodes, edges=edges) >>> list(c.leaves("swh:1:rev:1111111111111111111111111111111111111111")) ['swh:1:rev:3333333333333333333333333333333333333333'] """ def __init__( self, *, nodes: List[SWHIDlike], edges: List[Tuple[SWHIDlike, SWHIDlike]] ): self.graph = Graph(nodes, edges) def _check_swhid(self, swhid): try: ExtendedSWHID.from_string(swhid) except ValidationError as e: raise GraphArgumentException(*e.args) from None if swhid not in self.graph.nodes: raise GraphArgumentException(f"SWHID not found: {swhid}") def stats(self) -> Dict: return { "num_nodes": len(self.graph.nodes), "num_edges": sum(map(len, self.graph.forward_edges.values())), "compression": 1.0, "bits_per_edge": 100.0, "bits_per_node": 100.0, "avg_locality": 0.0, "indegree_min": min(map(len, self.graph.backward_edges.values())), "indegree_max": max(map(len, self.graph.backward_edges.values())), "indegree_avg": statistics.mean( map(len, self.graph.backward_edges.values()) ), "outdegree_min": min(map(len, self.graph.forward_edges.values())), "outdegree_max": max(map(len, self.graph.forward_edges.values())), "outdegree_avg": statistics.mean( map(len, self.graph.forward_edges.values()) ), } @check_arguments def leaves( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, [ node for node in self.graph.get_subgraph(src, edges, direction) if not self.graph.get_filtered_neighbors(node, edges, direction) ], ) @check_arguments def neighbors( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, self.graph.get_filtered_neighbors(src, edges, direction) ) @check_arguments def visit_nodes( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0, return_types: str = "*", ) -> Iterator[str]: # TODO: max_edges yield from filter_node_types( return_types, self.graph.get_subgraph(src, edges, direction) ) @check_arguments def visit_edges( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0 ) -> Iterator[Tuple[str, str]]: if max_edges == 0: max_edges = None # type: ignore else: max_edges -= 1 yield from list(self.graph.iter_edges_dfs(direction, edges, src))[:max_edges] @check_arguments def visit_paths( self, src: str, edges: str = "*", direction: str = "forward", max_edges: int = 0 ) -> Iterator[List[str]]: # TODO: max_edges for path in self.graph.iter_paths_dfs(direction, edges, src): if path[-1] in self.leaves(src, edges, direction): yield list(path) @check_arguments def walk( self, src: str, dst: str, edges: str = "*", traversal: str = "dfs", direction: str = "forward", limit: Optional[int] = None, ) -> Iterator[str]: # TODO: implement algo="bfs" # TODO: limit match_path: Callable[[str], bool] if ":" in dst: match_path = dst.__eq__ self._check_swhid(dst) else: match_path = lambda node: node.startswith(f"swh:1:{dst}:") # noqa for path in self.graph.iter_paths_dfs(direction, edges, src): if match_path(path[-1]): if not limit: # 0 or None yield from path elif limit > 0: yield from path[0:limit] else: yield from path[limit:] @check_arguments def random_walk( self, src: str, dst: str, edges: str = "*", direction: str = "forward", limit: Optional[int] = None, ): # TODO: limit yield from self.walk(src, dst, edges, "dfs", direction, limit) @check_arguments def count_leaves( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(list(self.leaves(src, edges, direction))) @check_arguments def count_neighbors( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(self.graph.get_filtered_neighbors(src, edges, direction)) @check_arguments def count_visit_nodes( self, src: str, edges: str = "*", direction: str = "forward" ) -> int: return len(self.graph.get_subgraph(src, edges, direction)) class Graph: def __init__( self, nodes: List[SWHIDlike], edges: List[Tuple[SWHIDlike, SWHIDlike]] ): self.nodes = [str(node) for node in nodes] self.forward_edges: Dict[str, List[str]] = {} self.backward_edges: Dict[str, List[str]] = {} for node in nodes: self.forward_edges[str(node)] = [] self.backward_edges[str(node)] = [] for (src, dst) in edges: self.forward_edges[str(src)].append(str(dst)) self.backward_edges[str(dst)].append(str(src)) def get_filtered_neighbors( self, src: str, edges_fmt: str, direction: str, ) -> Set[str]: if direction == "forward": edges = self.forward_edges elif direction == "backward": edges = self.backward_edges else: raise GraphArgumentException(f"invalid direction: {direction}") neighbors = edges.get(src, []) if edges_fmt == "*": return set(neighbors) else: filtered_neighbors: Set[str] = set() for edges_fmt_item in edges_fmt.split(","): (src_fmt, dst_fmt) = edges_fmt_item.split(":") if src_fmt != "*" and not src.startswith(f"swh:1:{src_fmt}:"): continue if dst_fmt == "*": filtered_neighbors.update(neighbors) else: prefix = f"swh:1:{dst_fmt}:" filtered_neighbors.update( n for n in neighbors if n.startswith(prefix) ) return filtered_neighbors def get_subgraph(self, src: str, edges_fmt: str, direction: str) -> Set[str]: seen = set() to_visit = {src} while to_visit: node = to_visit.pop() seen.add(node) neighbors = set(self.get_filtered_neighbors(node, edges_fmt, direction)) new_nodes = neighbors - seen to_visit.update(new_nodes) return seen def iter_paths_dfs( self, direction: str, edges_fmt: str, src: str ) -> Iterator[Tuple[str, ...]]: for (path, node) in DfsSubgraphIterator(self, direction, edges_fmt, src): yield path + (node,) def iter_edges_dfs( self, direction: str, edges_fmt: str, src: str ) -> Iterator[Tuple[str, str]]: for (path, node) in DfsSubgraphIterator(self, direction, edges_fmt, src): if len(path) > 0: yield (path[-1], node) class SubgraphIterator(Iterator[Tuple[Tuple[str, ...], str]]): def __init__(self, graph: Graph, direction: str, edges_fmt: str, src: str): self.graph = graph self.direction = direction self.edges_fmt = edges_fmt self.seen: Set[str] = set() self.src = src def more_work(self) -> bool: raise NotImplementedError() def pop(self) -> Tuple[Tuple[str, ...], str]: raise NotImplementedError() def push(self, new_path: Tuple[str, ...], neighbor: str) -> None: raise NotImplementedError() def __next__(self) -> Tuple[Tuple[str, ...], str]: # Stores (path, next_node) if not self.more_work(): raise StopIteration() (path, node) = self.pop() new_path = path + (node,) if node not in self.seen: neighbors = self.graph.get_filtered_neighbors( node, self.edges_fmt, self.direction ) # We want to visit the first neighbor first, and to_visit is a stack; # so we need to reversed() the list of neighbors to get it on top # of the stack. for neighbor in reversed(list(neighbors)): self.push(new_path, neighbor) self.seen.add(node) return (path, node) class DfsSubgraphIterator(SubgraphIterator): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.to_visit: List[Tuple[Tuple[str, ...], str]] = [((), self.src)] def more_work(self) -> bool: return bool(self.to_visit) def pop(self) -> Tuple[Tuple[str, ...], str]: return self.to_visit.pop() def push(self, new_path: Tuple[str, ...], neighbor: str) -> None: self.to_visit.append((new_path, neighbor))