res;
- Traversal t = new Traversal(graph, direction, edgesFmt, maxEdges, returnTypes);
- if (dst.matches("ori|snp|rel|rev|dir|cnt")) {
- Node.Type dstType = Node.Type.fromStr(dst);
- res = t.randomWalk(srcNodeId, dstType, retries);
- } else {
- long dstNodeId = graph.getNodeId(new SWHID(dst));
- res = t.randomWalk(srcNodeId, dstNodeId, retries);
- }
- for (Long nodeId : res) {
- writeNode(graph.getSWHID(nodeId));
- }
- close();
- }
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/Stats.java b/java/src/main/java/org/softwareheritage/graph/Stats.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/Stats.java
+++ /dev/null
@@ -1,67 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.io.FileInputStream;
-import java.io.IOException;
-import java.util.Properties;
-
-/**
- * Statistics on the compressed graph.
- *
- * These statistics are not computed but directly read from
- * WebGraph generated .stats and .properties files.
- *
- * @author The Software Heritage developers
- */
-
-public class Stats {
- public Counts counts;
- public Ratios ratios;
- public Degree indegree;
- public Degree outdegree;
- /**
- * Constructor.
- *
- * @param graphPath path and basename of compressed graph
- */
- public Stats(String graphPath) throws IOException {
- Properties properties = new Properties();
- properties.load(new FileInputStream(graphPath + ".properties"));
- properties.load(new FileInputStream(graphPath + ".stats"));
-
- this.counts = new Counts();
- this.ratios = new Ratios();
- this.indegree = new Degree();
- this.outdegree = new Degree();
-
- this.counts.nodes = Long.parseLong(properties.getProperty("nodes"));
- this.counts.edges = Long.parseLong(properties.getProperty("arcs"));
- this.ratios.compression = Double.parseDouble(properties.getProperty("compratio"));
- this.ratios.bitsPerNode = Double.parseDouble(properties.getProperty("bitspernode"));
- this.ratios.bitsPerEdge = Double.parseDouble(properties.getProperty("bitsperlink"));
- this.ratios.avgLocality = Double.parseDouble(properties.getProperty("avglocality"));
- this.indegree.min = Long.parseLong(properties.getProperty("minindegree"));
- this.indegree.max = Long.parseLong(properties.getProperty("maxindegree"));
- this.indegree.avg = Double.parseDouble(properties.getProperty("avgindegree"));
- this.outdegree.min = Long.parseLong(properties.getProperty("minoutdegree"));
- this.outdegree.max = Long.parseLong(properties.getProperty("maxoutdegree"));
- this.outdegree.avg = Double.parseDouble(properties.getProperty("avgoutdegree"));
- }
-
- public static class Counts {
- public long nodes;
- public long edges;
- }
-
- public static class Ratios {
- public double compression;
- public double bitsPerNode;
- public double bitsPerEdge;
- public double avgLocality;
- }
-
- public static class Degree {
- public long min;
- public long max;
- public double avg;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhBidirectionalGraph.java
@@ -64,8 +64,8 @@
private SwhBidirectionalGraph(BidirectionalImmutableGraph graph, SwhGraphProperties properties) {
super(graph.forward, graph.backward);
- this.forwardGraph = (SwhUnidirectionalGraph) graph.forward;
- this.backwardGraph = (SwhUnidirectionalGraph) graph.backward;
+ this.forwardGraph = new SwhUnidirectionalGraph(graph.forward, properties);
+ this.backwardGraph = new SwhUnidirectionalGraph(graph.backward, properties);
this.properties = properties;
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhGraph.java
@@ -113,12 +113,12 @@
}
/** @see SwhGraphProperties#getMessage(long) */
- default byte[] getMessage(long nodeId) throws IOException {
+ default byte[] getMessage(long nodeId) {
return getProperties().getMessage(nodeId);
}
/** @see SwhGraphProperties#getUrl(long) */
- default String getUrl(long nodeId) throws IOException {
+ default String getUrl(long nodeId) {
return getProperties().getUrl(nodeId);
}
@@ -128,7 +128,7 @@
}
/** @see SwhGraphProperties#getTagName(long) */
- default byte[] getTagName(long nodeId) throws IOException {
+ default byte[] getTagName(long nodeId) {
return getProperties().getTagName(nodeId);
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhGraphProperties.java
@@ -69,7 +69,6 @@
* Cleans up resources after use.
*/
public void close() throws IOException {
- nodeIdMap.close();
edgeLabelNames.close();
}
@@ -267,7 +266,7 @@
}
/** Get the message of the given revision or release node */
- public byte[] getMessage(long nodeId) throws IOException {
+ public byte[] getMessage(long nodeId) {
if (messageBuffer == null || messageOffsets == null) {
throw new IllegalStateException("Messages not loaded");
}
@@ -279,7 +278,7 @@
}
/** Get the URL of the given origin node */
- public String getUrl(long nodeId) throws IOException {
+ public String getUrl(long nodeId) {
byte[] url = getMessage(nodeId);
return (url != null) ? new String(url) : null;
}
@@ -291,7 +290,7 @@
}
/** Get the name of the given release node */
- public byte[] getTagName(long nodeId) throws IOException {
+ public byte[] getTagName(long nodeId) {
if (tagNameBuffer == null || tagNameOffsets == null) {
throw new IllegalStateException("Tag names not loaded");
}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhPath.java b/java/src/main/java/org/softwareheritage/graph/SwhPath.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/SwhPath.java
+++ /dev/null
@@ -1,122 +0,0 @@
-package org.softwareheritage.graph;
-
-import com.fasterxml.jackson.annotation.JsonValue;
-
-import java.util.ArrayList;
-
-/**
- * Wrapper class to store a list of {@link SWHID}.
- *
- * @author The Software Heritage developers
- * @see SWHID
- */
-
-public class SwhPath {
- /** Internal list of {@link SWHID} */
- ArrayList path;
-
- /**
- * Constructor.
- */
- public SwhPath() {
- this.path = new ArrayList<>();
- }
-
- /**
- * Constructor.
- *
- * @param swhids variable number of string SWHIDs to initialize this path with
- */
- public SwhPath(String... swhids) {
- this();
- for (String swhid : swhids) {
- add(new SWHID(swhid));
- }
- }
-
- /**
- * Constructor.
- *
- * @param swhids variable number of {@link SWHID} to initialize this path with
- * @see SWHID
- */
- public SwhPath(SWHID... swhids) {
- this();
- for (SWHID swhid : swhids) {
- add(swhid);
- }
- }
-
- /**
- * Returns this path as a list of {@link SWHID}.
- *
- * @return list of {@link SWHID} constituting the path
- * @see SWHID
- */
- @JsonValue
- public ArrayList getPath() {
- return path;
- }
-
- /**
- * Adds a {@link SWHID} to this path.
- *
- * @param swhid {@link SWHID} to add to this path
- * @see SWHID
- */
- public void add(SWHID swhid) {
- path.add(swhid);
- }
-
- /**
- * Returns the {@link SWHID} at the specified position in this path.
- *
- * @param index position of the {@link SWHID} to return
- * @return {@link SWHID} at the specified position
- * @see SWHID
- */
- public SWHID get(int index) {
- return path.get(index);
- }
-
- /**
- * Returns the number of elements in this path.
- *
- * @return number of elements in this path
- */
- public int size() {
- return path.size();
- }
-
- @Override
- public boolean equals(Object otherObj) {
- if (otherObj == this)
- return true;
- if (!(otherObj instanceof SwhPath))
- return false;
-
- SwhPath other = (SwhPath) otherObj;
- if (size() != other.size()) {
- return false;
- }
-
- for (int i = 0; i < size(); i++) {
- SWHID thisSWHID = get(i);
- SWHID otherSWHID = other.get(i);
- if (!thisSWHID.equals(otherSWHID)) {
- return false;
- }
- }
-
- return true;
- }
-
- @Override
- public String toString() {
- StringBuilder str = new StringBuilder();
- for (SWHID swhid : path) {
- str.append(swhid).append("/");
- }
- return str.toString();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
--- a/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
+++ b/java/src/main/java/org/softwareheritage/graph/SwhUnidirectionalGraph.java
@@ -34,7 +34,7 @@
/** Property data of the graph (id/type mappings etc.) */
public SwhGraphProperties properties;
- protected SwhUnidirectionalGraph(ImmutableGraph graph, SwhGraphProperties properties) {
+ public SwhUnidirectionalGraph(ImmutableGraph graph, SwhGraphProperties properties) {
this.graph = graph;
this.properties = properties;
}
diff --git a/java/src/main/java/org/softwareheritage/graph/Traversal.java b/java/src/main/java/org/softwareheritage/graph/Traversal.java
--- a/java/src/main/java/org/softwareheritage/graph/Traversal.java
+++ b/java/src/main/java/org/softwareheritage/graph/Traversal.java
@@ -13,18 +13,13 @@
import java.util.function.Consumer;
import java.util.function.LongConsumer;
-import org.softwareheritage.graph.server.Endpoint;
-
import it.unimi.dsi.big.webgraph.LazyLongIterator;
/**
* Traversal algorithms on the compressed graph.
*
- * Internal implementation of the traversal API endpoints. These methods only input/output internal
- * long ids, which are converted in the {@link Endpoint} higher-level class to {@link SWHID}.
*
* @author The Software Heritage developers
- * @see Endpoint
*/
public class Traversal {
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java b/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.benchmark.utils.Statistics;
-import org.softwareheritage.graph.benchmark.utils.Timing;
-
-import java.io.IOException;
-import java.util.ArrayList;
-
-/**
- * Benchmark to time edge access time.
- *
- * @author The Software Heritage developers
- */
-
-public class AccessEdge {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- ArrayList timings = new ArrayList<>();
- for (long nodeId : nodeIds) {
- long startTime = Timing.start();
- LazyLongIterator neighbors = graph.successors(nodeId);
- long firstNeighbor = neighbors.nextLong();
- double duration = Timing.stop(startTime);
- timings.add(duration);
- }
-
- System.out.println("Used " + bench.args.nbNodes + " random edges (results are in seconds):");
- Statistics stats = new Statistics(timings);
- stats.printAll();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java b/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/BFS.java
+++ /dev/null
@@ -1,107 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.google.common.primitives.Longs;
-import com.martiansoftware.jsap.*;
-import it.unimi.dsi.big.webgraph.ImmutableGraph;
-import it.unimi.dsi.big.webgraph.LazyLongIterator;
-import it.unimi.dsi.bits.LongArrayBitVector;
-import it.unimi.dsi.fastutil.Arrays;
-import it.unimi.dsi.io.ByteDiskQueue;
-import it.unimi.dsi.logging.ProgressLogger;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-
-import java.io.File;
-import java.io.IOException;
-
-public class BFS {
- private final static Logger LOGGER = LoggerFactory.getLogger(BFS.class);
- private final ImmutableGraph graph;
-
- public BFS(ImmutableGraph graph) {
- this.graph = graph;
- }
-
- private static JSAPResult parse_args(String[] args) {
- JSAPResult config = null;
- try {
- SimpleJSAP jsap = new SimpleJSAP(BFS.class.getName(), "",
- new Parameter[]{
- new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
- "graph", "Basename of the compressed graph"),
-
- new FlaggedOption("useTransposed", JSAP.BOOLEAN_PARSER, "false", JSAP.NOT_REQUIRED, 'T',
- "transposed", "Use transposed graph (default: false)"),});
-
- config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
- } catch (JSAPException e) {
- e.printStackTrace();
- }
- return config;
- }
-
- public static void main(String[] args) throws IOException {
- JSAPResult config = parse_args(args);
- String graphPath = config.getString("graphPath");
- boolean useTransposed = config.getBoolean("useTransposed");
-
- System.err.println("Loading graph " + graphPath + " ...");
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath);
- System.err.println("Graph loaded.");
-
- if (useTransposed)
- graph = graph.transpose();
-
- BFS bfs = new BFS(graph);
- bfs.bfsperm();
- }
-
- // Partly inlined from it.unimi.dsi.law.big.graph.BFS
- private void bfsperm() throws IOException {
- final long n = graph.numNodes();
- // Allow enough memory to behave like in-memory queue
- int bufferSize = (int) Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n);
-
- // Use a disk based queue to store BFS frontier
- final File queueFile = File.createTempFile(BFS.class.getSimpleName(), "queue");
- final ByteDiskQueue queue = ByteDiskQueue.createNew(queueFile, bufferSize, true);
- final byte[] byteBuf = new byte[Long.BYTES];
- // WARNING: no 64-bit version of this data-structure, but it can support
- // indices up to 2^37
- final LongArrayBitVector visited = LongArrayBitVector.ofLength(n);
- final ProgressLogger pl = new ProgressLogger(LOGGER);
- pl.expectedUpdates = n;
- pl.itemsName = "nodes";
- pl.start("Starting breadth-first visit...");
-
- for (long i = 0; i < n; i++) {
- if (visited.getBoolean(i))
- continue;
- queue.enqueue(Longs.toByteArray(i));
- visited.set(i);
-
- while (!queue.isEmpty()) {
- queue.dequeue(byteBuf);
- final long currentNode = Longs.fromByteArray(byteBuf);
-
- final LazyLongIterator iterator = graph.successors(currentNode);
- long succ;
- while ((succ = iterator.nextLong()) != -1) {
- if (!visited.getBoolean(succ)) {
- visited.set(succ);
- queue.enqueue(Longs.toByteArray(succ));
- }
- }
-
- pl.update();
- }
- }
-
- pl.done();
- queue.close();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Benchmark.java
+++ /dev/null
@@ -1,154 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.*;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.SWHID;
-import org.softwareheritage.graph.benchmark.utils.Random;
-import org.softwareheritage.graph.benchmark.utils.Statistics;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.BufferedWriter;
-import java.io.FileWriter;
-import java.io.IOException;
-import java.io.Writer;
-import java.util.ArrayList;
-import java.util.StringJoiner;
-import java.util.function.Function;
-
-/**
- * Benchmark common utility functions.
- *
- * @author The Software Heritage developers
- */
-
-public class Benchmark {
- /** CSV separator for log file */
- final String CSV_SEPARATOR = ";";
- /** Command line arguments */
- public Args args;
- /**
- * Constructor.
- */
- public Benchmark() {
- this.args = new Args();
- }
-
- /**
- * Parses benchmark command line arguments.
- *
- * @param args command line arguments
- */
- public void parseCommandLineArgs(String[] args) throws JSAPException {
- SimpleJSAP jsap = new SimpleJSAP(Benchmark.class.getName(),
- "Benchmark tool for Software Heritage use-cases scenarios.",
- new Parameter[]{
- new UnflaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED,
- JSAP.NOT_GREEDY, "The basename of the compressed graph."),
- new FlaggedOption("nbNodes", JSAP.INTEGER_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'n',
- "nb-nodes", "Number of random nodes used to do the benchmark."),
- new FlaggedOption("logFile", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'l',
- "log-file", "File name to output CSV format benchmark log."),
- new FlaggedOption("seed", JSAP.LONG_PARSER, JSAP.NO_DEFAULT, JSAP.NOT_REQUIRED, 's', "seed",
- "Random generator seed."),});
-
- JSAPResult config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
-
- this.args.graphPath = config.getString("graphPath");
- this.args.nbNodes = config.getInt("nbNodes");
- this.args.logFile = config.getString("logFile");
- this.args.random = config.contains("seed") ? new Random(config.getLong("seed")) : new Random();
- }
-
- /**
- * Creates CSV file for log output.
- */
- public void createCSVLogFile() throws IOException {
- try (Writer csvLog = new BufferedWriter(new FileWriter(args.logFile))) {
- StringJoiner csvHeader = new StringJoiner(CSV_SEPARATOR);
- csvHeader.add("use case name").add("SWHID").add("number of edges accessed").add("traversal timing")
- .add("swhid2node timing").add("node2swhid timing");
- csvLog.write(csvHeader.toString() + "\n");
- }
- }
-
- /**
- * Times a specific endpoint and outputs individual datapoints along with aggregated statistics.
- *
- * @param useCaseName benchmark use-case name
- * @param graph compressed graph used in the benchmark
- * @param nodeIds node ids to use as starting point for the endpoint traversal
- * @param operation endpoint function to benchmark
- * @param dstFmt destination formatted string as described in the
- * API
- * @param algorithm traversal algorithm used in endpoint call (either "dfs" or "bfs")
- */
- public void timeEndpoint(String useCaseName, SwhBidirectionalGraph graph, long[] nodeIds,
- Function operation, String dstFmt, String algorithm) throws IOException {
- ArrayList timings = new ArrayList<>();
- ArrayList timingsNormalized = new ArrayList<>();
- ArrayList nbEdgesAccessed = new ArrayList<>();
-
- final boolean append = true;
- try (Writer csvLog = new BufferedWriter(new FileWriter(args.logFile, append))) {
- for (long nodeId : nodeIds) {
- SWHID swhid = graph.getSWHID(nodeId);
-
- Endpoint.Output output = (dstFmt == null)
- ? operation.apply(new Endpoint.Input(swhid))
- : operation.apply(new Endpoint.Input(swhid, dstFmt, algorithm));
-
- StringJoiner csvLine = new StringJoiner(CSV_SEPARATOR);
- csvLine.add(useCaseName).add(swhid.toString()).add(Long.toString(output.meta.nbEdgesAccessed))
- .add(Double.toString(output.meta.timings.traversal))
- .add(Double.toString(output.meta.timings.swhid2node))
- .add(Double.toString(output.meta.timings.node2swhid));
- csvLog.write(csvLine.toString() + "\n");
-
- timings.add(output.meta.timings.traversal);
- nbEdgesAccessed.add((double) output.meta.nbEdgesAccessed);
- if (output.meta.nbEdgesAccessed != 0) {
- timingsNormalized.add(output.meta.timings.traversal / output.meta.nbEdgesAccessed);
- }
- }
- }
-
- System.out.println("\n" + useCaseName + " use-case:");
-
- System.out.println("timings:");
- Statistics stats = new Statistics(timings);
- stats.printAll();
-
- System.out.println("timings normalized:");
- Statistics statsNormalized = new Statistics(timingsNormalized);
- statsNormalized.printAll();
-
- System.out.println("nb edges accessed:");
- Statistics statsNbEdgesAccessed = new Statistics(nbEdgesAccessed);
- statsNbEdgesAccessed.printAll();
- }
-
- /**
- * Same as {@link #timeEndpoint} but without destination or algorithm specified to endpoint call.
- */
- public void timeEndpoint(String useCaseName, SwhBidirectionalGraph graph, long[] nodeIds,
- Function operation) throws IOException {
- timeEndpoint(useCaseName, graph, nodeIds, operation, null, null);
- }
-
- /**
- * Input arguments.
- */
- public class Args {
- /** Basename of the compressed graph */
- public String graphPath;
- /** Number of random nodes to use for the benchmark */
- public int nbNodes;
- /** File name for CSV format benchmark log */
- public String logFile;
- /** Random generator */
- public Random random;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Browsing.java
+++ /dev/null
@@ -1,42 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * browsing
- * use-cases scenarios.
- *
- * @author The Software Heritage developers
- */
-
-public class Browsing {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] dirNodeIds = bench.args.random.generateNodeIdsOfType(graph, bench.args.nbNodes, Node.Type.DIR);
- long[] revNodeIds = bench.args.random.generateNodeIdsOfType(graph, bench.args.nbNodes, Node.Type.REV);
-
- Endpoint dirEndpoint = new Endpoint(graph, "forward", "dir:cnt,dir:dir");
- Endpoint revEndpoint = new Endpoint(graph, "forward", "rev:rev");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
- bench.timeEndpoint("ls", graph, dirNodeIds, dirEndpoint::neighbors);
- bench.timeEndpoint("ls -R", graph, dirNodeIds, dirEndpoint::visitPaths);
- bench.timeEndpoint("git log", graph, revNodeIds, revEndpoint::visitNodes);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Provenance.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * provenance
- * use-cases scenarios.
- *
- * @author The Software Heritage developers
- */
-
-public class Provenance {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- Endpoint commitProvenanceEndpoint = new Endpoint(graph, "backward", "dir:dir,cnt:dir,dir:rev");
- Endpoint originProvenanceEndpoint = new Endpoint(graph, "backward", "*");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
-
- bench.timeEndpoint("commit provenance (dfs)", graph, nodeIds, commitProvenanceEndpoint::walk, "rev", "dfs");
- bench.timeEndpoint("commit provenance (bfs)", graph, nodeIds, commitProvenanceEndpoint::walk, "rev", "bfs");
- bench.timeEndpoint("complete commit provenance", graph, nodeIds, commitProvenanceEndpoint::leaves);
-
- bench.timeEndpoint("origin provenance (dfs)", graph, nodeIds, originProvenanceEndpoint::walk, "ori", "dfs");
- bench.timeEndpoint("origin provenance (bfs)", graph, nodeIds, originProvenanceEndpoint::walk, "ori", "bfs");
- bench.timeEndpoint("complete origin provenance", graph, nodeIds, originProvenanceEndpoint::leaves);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java b/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/Vault.java
+++ /dev/null
@@ -1,37 +0,0 @@
-package org.softwareheritage.graph.benchmark;
-
-import com.martiansoftware.jsap.JSAPException;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.server.Endpoint;
-
-import java.io.IOException;
-
-/**
- * Benchmark Software Heritage
- * vault use-case
- * scenario.
- *
- * @author The Software Heritage developers
- */
-
-public class Vault {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- Benchmark bench = new Benchmark();
- bench.parseCommandLineArgs(args);
-
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(bench.args.graphPath);
-
- long[] nodeIds = bench.args.random.generateNodeIds(graph, bench.args.nbNodes);
-
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
-
- System.out.println("Used " + bench.args.nbNodes + " random nodes (results are in seconds):");
- bench.createCSVLogFile();
- bench.timeEndpoint("git bundle", graph, nodeIds, endpoint::visitNodes);
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Random.java
+++ /dev/null
@@ -1,67 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Node;
-
-import java.util.PrimitiveIterator;
-
-/**
- * Random related utility class.
- *
- * @author The Software Heritage developers
- */
-
-public class Random {
- /** Internal pseudorandom generator */
- java.util.Random random;
-
- /**
- * Constructor.
- */
- public Random() {
- this.random = new java.util.Random();
- }
-
- /**
- * Constructor.
- *
- * @param seed random generator seed
- */
- public Random(long seed) {
- this.random = new java.util.Random(seed);
- }
-
- /**
- * Generates random node ids.
- *
- * @param graph graph used to pick node ids
- * @param nbNodes number of node ids to generate
- * @return an array of random node ids
- */
- public long[] generateNodeIds(SwhBidirectionalGraph graph, int nbNodes) {
- return random.longs(nbNodes, 0, graph.numNodes()).toArray();
- }
-
- /**
- * Generates random node ids with a specific type.
- *
- * @param graph graph used to pick node ids
- * @param nbNodes number of node ids to generate
- * @param expectedType specific node type to pick
- * @return an array of random node ids
- */
- public long[] generateNodeIdsOfType(SwhBidirectionalGraph graph, int nbNodes, Node.Type expectedType) {
- PrimitiveIterator.OfLong nodes = random.longs(0, graph.numNodes()).iterator();
- long[] nodeIds = new long[nbNodes];
-
- long nextId;
- for (int i = 0; i < nbNodes; i++) {
- do {
- nextId = nodes.nextLong();
- } while (graph.getNodeType(nextId) != expectedType);
- nodeIds[i] = nextId;
- }
-
- return nodeIds;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Statistics.java
+++ /dev/null
@@ -1,104 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-import java.util.ArrayList;
-import java.util.Collections;
-
-/**
- * Compute various statistics on a list of values.
- *
- * @author The Software Heritage developers
- */
-
-public class Statistics {
- /** Input values */
- ArrayList values;
-
- /**
- * Constructor.
- *
- * @param values input values
- */
- public Statistics(ArrayList values) {
- this.values = values;
- }
-
- /**
- * Returns the minimum value.
- *
- * @return minimum value
- */
- public double getMin() {
- double min = Double.POSITIVE_INFINITY;
- for (double v : values) {
- min = Math.min(min, v);
- }
- return min;
- }
-
- /**
- * Returns the maximum value.
- *
- * @return maximum value
- */
- public double getMax() {
- double max = Double.NEGATIVE_INFINITY;
- for (double v : values) {
- max = Math.max(max, v);
- }
- return max;
- }
-
- /**
- * Computes the average.
- *
- * @return average value
- */
- public double getAverage() {
- double sum = 0;
- for (double v : values) {
- sum += v;
- }
- return sum / (double) values.size();
- }
-
- /**
- * Returns the median value.
- *
- * @return median value
- */
- public double getMedian() {
- Collections.sort(values);
- int length = values.size();
- if (length % 2 == 0) {
- return (values.get(length / 2) + values.get(length / 2 - 1)) / 2;
- } else {
- return values.get(length / 2);
- }
- }
-
- /**
- * Computes the standard deviation.
- *
- * @return standard deviation value
- */
- public double getStandardDeviation() {
- double average = getAverage();
- double variance = 0;
- for (double v : values) {
- variance += (v - average) * (v - average);
- }
- variance /= (double) values.size();
- return Math.sqrt(variance);
- }
-
- /**
- * Computes and prints all statistical values.
- */
- public void printAll() {
- System.out.println("min value: " + getMin());
- System.out.println("max value: " + getMax());
- System.out.println("average: " + getAverage());
- System.out.println("median: " + getMedian());
- System.out.println("standard deviation: " + getStandardDeviation());
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java b/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/benchmark/utils/Timing.java
+++ /dev/null
@@ -1,30 +0,0 @@
-package org.softwareheritage.graph.benchmark.utils;
-
-/**
- * Time measurement utility class.
- *
- * @author The Software Heritage developers
- */
-
-public class Timing {
- /**
- * Returns measurement starting timestamp.
- *
- * @return timestamp used for time measurement
- */
- public static long start() {
- return System.nanoTime();
- }
-
- /**
- * Ends timing measurement and returns total duration in seconds.
- *
- * @param startTime measurement starting timestamp
- * @return time in seconds elapsed since starting point
- */
- public static double stop(long startTime) {
- long endTime = System.nanoTime();
- double duration = (double) (endTime - startTime) / 1_000_000_000;
- return duration;
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java b/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java
--- a/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java
+++ b/java/src/main/java/org/softwareheritage/graph/experiments/multiplicationfactor/GenDistribution.java
@@ -4,7 +4,6 @@
import org.softwareheritage.graph.SwhBidirectionalGraph;
import org.softwareheritage.graph.Node;
import org.softwareheritage.graph.Traversal;
-import org.softwareheritage.graph.benchmark.utils.Timing;
import java.io.IOException;
import java.util.Scanner;
@@ -106,13 +105,14 @@
Traversal t = new Traversal(thread_graph, "backward", edgesFmt);
int[] count = {0};
- startTime = Timing.start();
+ startTime = System.nanoTime();
t.visitNodesVisitor(node, (curnode) -> {
if (tp.graph.getNodeType(curnode) == dstType) {
count[0]++;
}
});
- totalTime = Timing.stop(startTime);
+ long endTime = System.nanoTime();
+ totalTime = (double) (endTime - startTime) / 1e9;
System.out.format("%d %d %d %d %f\n", node, count[0], t.getNbNodesAccessed(),
t.getNbEdgesAccessed(), totalTime);
}
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java b/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/maps/MapFile.java
+++ /dev/null
@@ -1,66 +0,0 @@
-package org.softwareheritage.graph.maps;
-
-import it.unimi.dsi.io.ByteBufferInputStream;
-
-import java.io.File;
-import java.io.IOException;
-import java.io.RandomAccessFile;
-import java.nio.channels.FileChannel;
-
-/**
- * Wrapper class around very big mmap()-ed file.
- *
- * Java has a limit for mmap()-ed files because of unsupported 64-bit indexing. The
- * dsiutils ByteBufferInputStream is used to overcome
- * this Java limit.
- *
- * @author The Software Heritage developers
- */
-
-public class MapFile {
- /** Memory-mapped file buffer */
- ByteBufferInputStream bufferMap;
- /** Fixed line length of the mmap()-ed file */
- int lineLength;
-
- /**
- * Constructor.
- *
- * @param path file path to mmap()
- * @param lineLength fixed length of a line in the file
- */
- public MapFile(String path, int lineLength) throws IOException {
- this.bufferMap = null;
- this.lineLength = lineLength;
-
- try (RandomAccessFile mapFile = new RandomAccessFile(new File(path), "r")) {
- FileChannel fileChannel = mapFile.getChannel();
- bufferMap = ByteBufferInputStream.map(fileChannel, FileChannel.MapMode.READ_ONLY);
- }
- }
-
- /**
- * Returns a specific line in the file.
- *
- * @param lineIndex line number in the file
- * @return the line at the specified position
- */
- public byte[] readAtLine(long lineIndex) {
- byte[] buffer = new byte[lineLength];
- long position = lineIndex * (long) lineLength;
- bufferMap.position(position);
- bufferMap.read(buffer, 0, lineLength);
- return buffer;
- }
-
- public long size() {
- return bufferMap.length() / (long) lineLength;
- }
-
- /**
- * Closes the mmap()-ed file.
- */
- public void close() throws IOException {
- bufferMap.close();
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
--- a/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
+++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeIdMap.java
@@ -1,17 +1,18 @@
package org.softwareheritage.graph.maps;
import it.unimi.dsi.fastutil.Size64;
+import it.unimi.dsi.fastutil.bytes.ByteBigList;
+import it.unimi.dsi.fastutil.bytes.ByteMappedBigList;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.fastutil.longs.LongBigList;
+import it.unimi.dsi.fastutil.longs.LongMappedBigList;
import it.unimi.dsi.fastutil.objects.Object2LongFunction;
-import it.unimi.dsi.util.ByteBufferLongBigList;
import org.softwareheritage.graph.SWHID;
import org.softwareheritage.graph.compress.NodeMapBuilder;
import java.io.File;
import java.io.IOException;
import java.io.RandomAccessFile;
-import java.nio.channels.FileChannel;
import java.nio.charset.StandardCharsets;
/**
@@ -38,7 +39,7 @@
String graphPath;
/** mmap()-ed NODE_TO_SWHID file */
- MapFile nodeToSwhMap;
+ ByteBigList nodeToSwhMap;
/** Minimal perfect hash (MPH) function SWHID -> initial order */
Object2LongFunction mph;
@@ -54,14 +55,14 @@
this.graphPath = graphPath;
// node -> SWHID
- this.nodeToSwhMap = new MapFile(graphPath + NODE_TO_SWHID, SWHID_BIN_SIZE);
+ try (RandomAccessFile raf = new RandomAccessFile(graphPath + NODE_TO_SWHID, "r")) {
+ this.nodeToSwhMap = ByteMappedBigList.map(raf.getChannel());
+ }
// SWHID -> node
this.mph = loadMph(graphPath + ".mph");
-
try (RandomAccessFile mapFile = new RandomAccessFile(new File(graphPath + ".order"), "r")) {
- FileChannel fileChannel = mapFile.getChannel();
- this.orderMap = ByteBufferLongBigList.map(fileChannel);
+ this.orderMap = LongMappedBigList.map(mapFile.getChannel());
}
}
@@ -95,6 +96,7 @@
return legacyFunction.getLong(new String(bi, StandardCharsets.UTF_8));
}
+ @SuppressWarnings("deprecation")
@Override
public int size() {
return legacyFunction.size();
@@ -169,23 +171,19 @@
* Each line in NODE_TO_SWHID is formatted as: swhid The file is ordered by nodeId, meaning node0's
* swhid is at line 0, hence we can read the nodeId-th line to get corresponding swhid
*/
- if (nodeId < 0 || nodeId >= nodeToSwhMap.size()) {
- throw new IllegalArgumentException("Node id " + nodeId + " should be between 0 and " + nodeToSwhMap.size());
+ if (nodeId < 0 || nodeId >= nodeToSwhMap.size64()) {
+ throw new IllegalArgumentException(
+ "Node id " + nodeId + " should be between 0 and " + nodeToSwhMap.size64());
}
- return SWHID.fromBytes(nodeToSwhMap.readAtLine(nodeId));
- }
-
- /**
- * Closes the mapping files.
- */
- public void close() throws IOException {
- nodeToSwhMap.close();
+ byte[] swhid = new byte[SWHID_BIN_SIZE];
+ nodeToSwhMap.getElements(nodeId * SWHID_BIN_SIZE, swhid, 0, SWHID_BIN_SIZE);
+ return SWHID.fromBytes(swhid);
}
/** Return the number of nodes in the map. */
@Override
public long size64() {
- return nodeToSwhMap.size();
+ return nodeToSwhMap.size64();
}
}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/GraphServer.java
@@ -0,0 +1,293 @@
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import com.martiansoftware.jsap.*;
+import io.grpc.Server;
+import io.grpc.Status;
+import io.grpc.netty.shaded.io.grpc.netty.NettyServerBuilder;
+import io.grpc.netty.shaded.io.netty.channel.ChannelOption;
+import io.grpc.stub.StreamObserver;
+import io.grpc.protobuf.services.ProtoReflectionService;
+import it.unimi.dsi.logging.ProgressLogger;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.softwareheritage.graph.SWHID;
+import org.softwareheritage.graph.SwhBidirectionalGraph;
+import org.softwareheritage.graph.compress.LabelMapBuilder;
+
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.util.Properties;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicLong;
+
+/**
+ * Server that manages startup/shutdown of a {@code Greeter} server.
+ */
+public class GraphServer {
+ private final static Logger logger = LoggerFactory.getLogger(GraphServer.class);
+
+ private final SwhBidirectionalGraph graph;
+ private final int port;
+ private final int threads;
+ private Server server;
+
+ /**
+ * @param graphBasename the basename of the SWH graph to load
+ * @param port the port on which the GRPC server will listen
+ * @param threads the number of threads to use in the server threadpool
+ */
+ public GraphServer(String graphBasename, int port, int threads) throws IOException {
+ this.graph = loadGraph(graphBasename);
+ this.port = port;
+ this.threads = threads;
+ }
+
+ /** Load a graph and all its properties. */
+ public static SwhBidirectionalGraph loadGraph(String basename) throws IOException {
+ // TODO: use loadLabelledMapped() when https://github.com/vigna/webgraph-big/pull/5 is merged
+ SwhBidirectionalGraph g = SwhBidirectionalGraph.loadLabelled(basename, new ProgressLogger(logger));
+ g.loadContentLength();
+ g.loadContentIsSkipped();
+ g.loadPersonIds();
+ g.loadAuthorTimestamps();
+ g.loadCommitterTimestamps();
+ g.loadMessages();
+ g.loadTagNames();
+ g.loadLabelNames();
+ return g;
+ }
+
+ /** Start the RPC server. */
+ private void start() throws IOException {
+ server = NettyServerBuilder.forPort(port).withChildOption(ChannelOption.SO_REUSEADDR, true)
+ .executor(Executors.newFixedThreadPool(threads)).addService(new TraversalService(graph))
+ .addService(ProtoReflectionService.newInstance()).build().start();
+ logger.info("Server started, listening on " + port);
+ Runtime.getRuntime().addShutdownHook(new Thread(() -> {
+ try {
+ GraphServer.this.stop();
+ } catch (InterruptedException e) {
+ e.printStackTrace(System.err);
+ }
+ }));
+ }
+
+ private void stop() throws InterruptedException {
+ if (server != null) {
+ server.shutdown().awaitTermination(30, TimeUnit.SECONDS);
+ }
+ }
+
+ /**
+ * Await termination on the main thread since the grpc library uses daemon threads.
+ */
+ private void blockUntilShutdown() throws InterruptedException {
+ if (server != null) {
+ server.awaitTermination();
+ }
+ }
+
+ private static JSAPResult parseArgs(String[] args) {
+ JSAPResult config = null;
+ try {
+ SimpleJSAP jsap = new SimpleJSAP(LabelMapBuilder.class.getName(), "",
+ new Parameter[]{
+ new FlaggedOption("port", JSAP.INTEGER_PARSER, "50091", JSAP.NOT_REQUIRED, 'p', "port",
+ "The port on which the server should listen."),
+ new FlaggedOption("threads", JSAP.INTEGER_PARSER, "1", JSAP.NOT_REQUIRED, 't', "threads",
+ "The number of concurrent threads. 0 = number of cores."),
+ new UnflaggedOption("graphBasename", JSAP.STRING_PARSER, JSAP.REQUIRED,
+ "Basename of the output graph")});
+
+ config = jsap.parse(args);
+ if (jsap.messagePrinted()) {
+ System.exit(1);
+ }
+ } catch (JSAPException e) {
+ e.printStackTrace();
+ }
+ return config;
+ }
+
+ /** Main launches the server from the command line. */
+ public static void main(String[] args) throws IOException, InterruptedException {
+ JSAPResult config = parseArgs(args);
+ String graphBasename = config.getString("graphBasename");
+ int port = config.getInt("port");
+ int threads = config.getInt("threads");
+ if (threads == 0) {
+ threads = Runtime.getRuntime().availableProcessors();
+ }
+
+ final GraphServer server = new GraphServer(graphBasename, port, threads);
+ server.start();
+ server.blockUntilShutdown();
+ }
+
+ /** Implementation of the Traversal service, which contains all the graph querying endpoints. */
+ static class TraversalService extends TraversalServiceGrpc.TraversalServiceImplBase {
+ SwhBidirectionalGraph graph;
+
+ public TraversalService(SwhBidirectionalGraph graph) {
+ this.graph = graph;
+ }
+
+ /** Return various statistics on the overall graph. */
+ @Override
+ public void stats(StatsRequest request, StreamObserver responseObserver) {
+ StatsResponse.Builder response = StatsResponse.newBuilder();
+ response.setNumNodes(graph.numNodes());
+ response.setNumEdges(graph.numArcs());
+
+ Properties properties = new Properties();
+ try {
+ properties.load(new FileInputStream(graph.getPath() + ".properties"));
+ properties.load(new FileInputStream(graph.getPath() + ".stats"));
+ } catch (IOException e) {
+ throw new RuntimeException(e);
+ }
+ response.setCompressionRatio(Double.parseDouble(properties.getProperty("compratio")));
+ response.setBitsPerNode(Double.parseDouble(properties.getProperty("bitspernode")));
+ response.setBitsPerEdge(Double.parseDouble(properties.getProperty("bitsperlink")));
+ response.setAvgLocality(Double.parseDouble(properties.getProperty("avglocality")));
+ response.setIndegreeMin(Long.parseLong(properties.getProperty("minindegree")));
+ response.setIndegreeMax(Long.parseLong(properties.getProperty("maxindegree")));
+ response.setIndegreeAvg(Double.parseDouble(properties.getProperty("avgindegree")));
+ response.setOutdegreeMin(Long.parseLong(properties.getProperty("minoutdegree")));
+ response.setOutdegreeMax(Long.parseLong(properties.getProperty("maxoutdegree")));
+ response.setOutdegreeAvg(Double.parseDouble(properties.getProperty("avgoutdegree")));
+ responseObserver.onNext(response.build());
+ responseObserver.onCompleted();
+ }
+
+ /** Return a single node and its properties. */
+ @Override
+ public void getNode(GetNodeRequest request, StreamObserver responseObserver) {
+ long nodeId;
+ try {
+ nodeId = graph.getNodeId(new SWHID(request.getSwhid()));
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ Node.Builder builder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(graph.getForwardGraph(),
+ request.hasMask() ? request.getMask() : null, builder, nodeId);
+ responseObserver.onNext(builder.build());
+ responseObserver.onCompleted();
+ }
+
+ /** Perform a BFS traversal from a set of source nodes and stream the nodes encountered. */
+ @Override
+ public void traverse(TraversalRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, request, responseObserver::onNext);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ responseObserver.onCompleted();
+ }
+
+ /**
+ * Find the shortest path between a set of source nodes and a node that matches a given criteria
+ * using a BFS.
+ */
+ @Override
+ public void findPathTo(FindPathToRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.FindPathTo t;
+ try {
+ t = new Traversal.FindPathTo(g, request);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ Path path = t.getPath();
+ if (path == null) {
+ responseObserver.onError(Status.NOT_FOUND.asException());
+ } else {
+ responseObserver.onNext(path);
+ responseObserver.onCompleted();
+ }
+ }
+
+ /**
+ * Find the shortest path between a set of source nodes and a set of destination nodes using a
+ * bidirectional BFS.
+ */
+ @Override
+ public void findPathBetween(FindPathBetweenRequest request, StreamObserver responseObserver) {
+ SwhBidirectionalGraph g = graph.copy();
+ Traversal.FindPathBetween t;
+ try {
+ t = new Traversal.FindPathBetween(g, request);
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ Path path = t.getPath();
+ if (path == null) {
+ responseObserver.onError(Status.NOT_FOUND.asException());
+ } else {
+ responseObserver.onNext(path);
+ responseObserver.onCompleted();
+ }
+ }
+
+ /** Return the number of nodes traversed by a BFS traversal. */
+ @Override
+ public void countNodes(TraversalRequest request, StreamObserver responseObserver) {
+ AtomicLong count = new AtomicLong(0);
+ SwhBidirectionalGraph g = graph.copy();
+ TraversalRequest fixedReq = TraversalRequest.newBuilder(request)
+ // Ignore return fields, just count nodes
+ .setMask(FieldMask.getDefaultInstance()).build();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.incrementAndGet());
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ CountResponse response = CountResponse.newBuilder().setCount(count.get()).build();
+ responseObserver.onNext(response);
+ responseObserver.onCompleted();
+ }
+
+ /** Return the number of edges traversed by a BFS traversal. */
+ @Override
+ public void countEdges(TraversalRequest request, StreamObserver responseObserver) {
+ AtomicLong count = new AtomicLong(0);
+ SwhBidirectionalGraph g = graph.copy();
+ TraversalRequest fixedReq = TraversalRequest.newBuilder(request)
+ // Force return empty successors to count the edges
+ .setMask(FieldMask.newBuilder().addPaths("num_successors").build()).build();
+ Traversal.SimpleTraversal t;
+ try {
+ t = new Traversal.SimpleTraversal(g, fixedReq, n -> count.addAndGet(n.getNumSuccessors()));
+ } catch (IllegalArgumentException e) {
+ responseObserver
+ .onError(Status.INVALID_ARGUMENT.withDescription(e.getMessage()).withCause(e).asException());
+ return;
+ }
+ t.visit();
+ CountResponse response = CountResponse.newBuilder().setCount(count.get()).build();
+ responseObserver.onNext(response);
+ responseObserver.onCompleted();
+ }
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java b/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/NodePropertyBuilder.java
@@ -0,0 +1,210 @@
+/*
+ * Copyright (c) 2022 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
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.ByteString;
+import com.google.protobuf.FieldMask;
+import com.google.protobuf.util.FieldMaskUtil;
+import it.unimi.dsi.big.webgraph.labelling.Label;
+import org.softwareheritage.graph.SwhUnidirectionalGraph;
+import org.softwareheritage.graph.labels.DirEntry;
+
+import java.util.*;
+
+/**
+ * NodePropertyBuilder is a helper class to enrich {@link Node} messages with node and edge
+ * properties. It is used by {@link GraphServer.TraversalService} to build the response messages or
+ * streams. Because property access is disk-based and slow, particular care is taken to avoid
+ * loading unnecessary properties. We use a FieldMask object to check which properties are requested
+ * by the client, and only load these.
+ */
+public class NodePropertyBuilder {
+ /**
+ * NodeDataMask caches a FieldMask into a more efficient representation (booleans). This avoids the
+ * need of parsing the FieldMask for each node in the stream.
+ */
+ public static class NodeDataMask {
+ public boolean swhid;
+ public boolean successor;
+ public boolean successorSwhid;
+ public boolean successorLabel;
+ public boolean numSuccessors;
+ public boolean cntLength;
+ public boolean cntIsSkipped;
+ public boolean revAuthor;
+ public boolean revAuthorDate;
+ public boolean revAuthorDateOffset;
+ public boolean revCommitter;
+ public boolean revCommitterDate;
+ public boolean revCommitterDateOffset;
+ public boolean revMessage;
+ public boolean relAuthor;
+ public boolean relAuthorDate;
+ public boolean relAuthorDateOffset;
+ public boolean relName;
+ public boolean relMessage;
+ public boolean oriUrl;
+
+ public NodeDataMask(FieldMask mask) {
+ Set allowedFields = null;
+ if (mask != null) {
+ mask = FieldMaskUtil.normalize(mask);
+ allowedFields = new HashSet<>(mask.getPathsList());
+ }
+ this.swhid = allowedFields == null || allowedFields.contains("swhid");
+ this.successorSwhid = allowedFields == null || allowedFields.contains("successor")
+ || allowedFields.contains("successor.swhid");
+ this.successorLabel = allowedFields == null || allowedFields.contains("successor")
+ || allowedFields.contains("successor.label");
+ this.successor = this.successorSwhid || this.successorLabel;
+ this.numSuccessors = allowedFields == null || allowedFields.contains("num_successors");
+ this.cntLength = allowedFields == null || allowedFields.contains("cnt.length");
+ this.cntIsSkipped = allowedFields == null || allowedFields.contains("cnt.is_skipped");
+ this.revAuthor = allowedFields == null || allowedFields.contains("rev.author");
+ this.revAuthorDate = allowedFields == null || allowedFields.contains("rev.author_date");
+ this.revAuthorDateOffset = allowedFields == null || allowedFields.contains("rev.author_date_offset");
+ this.revCommitter = allowedFields == null || allowedFields.contains("rev.committer");
+ this.revCommitterDate = allowedFields == null || allowedFields.contains("rev.committer_date");
+ this.revCommitterDateOffset = allowedFields == null || allowedFields.contains("rev.committer_date_offset");
+ this.revMessage = allowedFields == null || allowedFields.contains("rev.message");
+ this.relAuthor = allowedFields == null || allowedFields.contains("rel.author");
+ this.relAuthorDate = allowedFields == null || allowedFields.contains("rel.author_date");
+ this.relAuthorDateOffset = allowedFields == null || allowedFields.contains("rel.author_date_offset");
+ this.relName = allowedFields == null || allowedFields.contains("rel.name");
+ this.relMessage = allowedFields == null || allowedFields.contains("rel.message");
+ this.oriUrl = allowedFields == null || allowedFields.contains("ori.url");
+ }
+ }
+
+ /** Enrich a Node message with node properties requested in the NodeDataMask. */
+ public static void buildNodeProperties(SwhUnidirectionalGraph graph, NodeDataMask mask, Node.Builder nodeBuilder,
+ long node) {
+ if (mask.swhid) {
+ nodeBuilder.setSwhid(graph.getSWHID(node).toString());
+ }
+
+ switch (graph.getNodeType(node)) {
+ case CNT:
+ ContentData.Builder cntBuilder = ContentData.newBuilder();
+ if (mask.cntLength) {
+ cntBuilder.setLength(graph.getContentLength(node));
+ }
+ if (mask.cntIsSkipped) {
+ cntBuilder.setIsSkipped(graph.isContentSkipped(node));
+ }
+ nodeBuilder.setCnt(cntBuilder.build());
+ break;
+ case REV:
+ RevisionData.Builder revBuilder = RevisionData.newBuilder();
+ if (mask.revAuthor) {
+ revBuilder.setAuthor(graph.getAuthorId(node));
+ }
+ if (mask.revAuthorDate) {
+ revBuilder.setAuthorDate(graph.getAuthorTimestamp(node));
+ }
+ if (mask.revAuthorDateOffset) {
+ revBuilder.setAuthorDateOffset(graph.getAuthorTimestampOffset(node));
+ }
+ if (mask.revCommitter) {
+ revBuilder.setCommitter(graph.getCommitterId(node));
+ }
+ if (mask.revCommitterDate) {
+ revBuilder.setCommitterDate(graph.getCommitterTimestamp(node));
+ }
+ if (mask.revCommitterDateOffset) {
+ revBuilder.setCommitterDateOffset(graph.getCommitterTimestampOffset(node));
+ }
+ if (mask.revMessage) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ revBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ nodeBuilder.setRev(revBuilder.build());
+ break;
+ case REL:
+ ReleaseData.Builder relBuilder = ReleaseData.newBuilder();
+ if (mask.relAuthor) {
+ relBuilder.setAuthor(graph.getAuthorId(node));
+ }
+ if (mask.relAuthorDate) {
+ relBuilder.setAuthorDate(graph.getAuthorTimestamp(node));
+ }
+ if (mask.relAuthorDateOffset) {
+ relBuilder.setAuthorDateOffset(graph.getAuthorTimestampOffset(node));
+ }
+ if (mask.relName) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ relBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ if (mask.relMessage) {
+ byte[] msg = graph.getMessage(node);
+ if (msg != null) {
+ relBuilder.setMessage(ByteString.copyFrom(msg));
+ }
+ }
+ nodeBuilder.setRel(relBuilder.build());
+ break;
+ case ORI:
+ OriginData.Builder oriBuilder = OriginData.newBuilder();
+ if (mask.oriUrl) {
+ String url = graph.getUrl(node);
+ if (url != null) {
+ oriBuilder.setUrl(url);
+ }
+ }
+ nodeBuilder.setOri(oriBuilder.build());
+ }
+ }
+
+ /** Enrich a Node message with node properties requested in the FieldMask. */
+ public static void buildNodeProperties(SwhUnidirectionalGraph graph, FieldMask mask, Node.Builder nodeBuilder,
+ long node) {
+ NodeDataMask nodeMask = new NodeDataMask(mask);
+ buildNodeProperties(graph, nodeMask, nodeBuilder, node);
+ }
+
+ /**
+ * Enrich a Node message with edge properties requested in the NodeDataMask, for a specific edge.
+ */
+ public static void buildSuccessorProperties(SwhUnidirectionalGraph graph, NodeDataMask mask,
+ Node.Builder nodeBuilder, long src, long dst, Label label) {
+ if (nodeBuilder != null) {
+ Successor.Builder successorBuilder = Successor.newBuilder();
+ if (mask.successorSwhid) {
+ successorBuilder.setSwhid(graph.getSWHID(dst).toString());
+ }
+ if (mask.successorLabel) {
+ 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());
+ }
+ }
+ Successor successor = successorBuilder.build();
+ if (successor != Successor.getDefaultInstance()) {
+ nodeBuilder.addSuccessor(successor);
+ }
+
+ if (mask.numSuccessors) {
+ nodeBuilder.setNumSuccessors(nodeBuilder.getNumSuccessors() + 1);
+ }
+ }
+ }
+
+ /** Enrich a Node message with edge properties requested in the FieldMask, for a specific edge. */
+ public static void buildSuccessorProperties(SwhUnidirectionalGraph graph, FieldMask mask, Node.Builder nodeBuilder,
+ long src, long dst, Label label) {
+ NodeDataMask nodeMask = new NodeDataMask(mask);
+ buildSuccessorProperties(graph, nodeMask, nodeBuilder, src, dst, label);
+ }
+}
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
new file mode 100644
--- /dev/null
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
@@ -0,0 +1,526 @@
+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.*;
+
+/** Traversal contains all the algorithms used for graph traversals */
+public class Traversal {
+ /**
+ * Wrapper around g.successors(), only follows edges that are allowed by the given
+ * {@link AllowedEdges} object.
+ */
+ 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;
+ }
+ };
+ }
+ }
+
+ /** Helper class to check that a given node is "valid" for some given {@link NodeFilter} */
+ 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;
+ }
+ }
+
+ /** Returns the unidirectional graph from a bidirectional graph and a {@link GraphDirection}. */
+ 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);
+ }
+ }
+
+ /** Returns the opposite of a given {@link GraphDirection} (equivalent to a graph transposition). */
+ 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);
+ }
+ }
+
+ /** Dummy exception to short-circuit and interrupt a graph traversal. */
+ static class StopTraversalException extends RuntimeException {
+ }
+
+ /** Generic BFS traversal algorithm. */
+ static class BFSVisitor {
+ /** The graph to traverse. */
+ protected final SwhUnidirectionalGraph g;
+ /** Depth of the node currently being visited */
+ protected long depth = 0;
+ /**
+ * Number of traversal successors (i.e., successors that will be considered by the traversal) of the
+ * node currently being visited
+ */
+ protected long traversalSuccessors = 0;
+ /** Number of edges accessed since the beginning of the traversal */
+ protected long edgesAccessed = 0;
+
+ /**
+ * Map from a node ID to its parent node ID. The key set can be used as the set of all visited
+ * nodes.
+ */
+ protected HashMap parents = new HashMap<>();
+ /** Queue of nodes to visit (also called "frontier", "open set", "wavefront" etc.) */
+ protected ArrayDeque queue = new ArrayDeque<>();
+ /** If > 0, the maximum depth of the traversal. */
+ private long maxDepth = -1;
+ /** If > 0, the maximum number of edges to traverse. */
+ private long maxEdges = -1;
+
+ BFSVisitor(SwhUnidirectionalGraph g) {
+ this.g = g;
+ }
+
+ /** Add a new source node to the initial queue. */
+ public void addSource(long nodeId) {
+ queue.add(nodeId);
+ parents.put(nodeId, -1L);
+ }
+
+ /** Set the maximum depth of the traversal. */
+ public void setMaxDepth(long depth) {
+ maxDepth = depth;
+ }
+
+ /** Set the maximum number of edges to traverse. */
+ public void setMaxEdges(long edges) {
+ maxEdges = edges;
+ }
+
+ /** Setup the visit counters and depth sentinel. */
+ public void visitSetup() {
+ edgesAccessed = 0;
+ depth = 0;
+ queue.add(-1L); // depth sentinel
+ }
+
+ /** Perform the visit */
+ public void visit() {
+ visitSetup();
+ while (!queue.isEmpty()) {
+ visitStep();
+ }
+ }
+
+ /** Single "step" of a visit. Advance the frontier of exactly one node. */
+ 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();
+ }
+ }
+
+ /**
+ * Get the successors of a node. Override this function if you want to filter which successors are
+ * considered during the traversal.
+ */
+ protected ArcLabelledNodeIterator.LabelledArcIterator getSuccessors(long nodeId) {
+ return g.labelledSuccessors(nodeId);
+ }
+
+ /** Visit a node. Override to do additional processing on the node. */
+ 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());
+ }
+ }
+
+ /** Visit an edge. Override to do additional processing on the edge. */
+ protected void visitEdge(long src, long dst, Label label) {
+ if (!parents.containsKey(dst)) {
+ queue.add(dst);
+ parents.put(dst, src);
+ }
+ }
+ }
+
+ /**
+ * SimpleTraversal is used by the Traverse endpoint. It extends BFSVisitor with additional
+ * processing, notably related to graph properties and filters.
+ */
+ 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);
+ }
+ }
+
+ /**
+ * FindPathTo searches for a path from a source node to a node matching a given criteria It extends
+ * BFSVisitor with additional processing, and makes the traversal stop as soon as a node matching
+ * the given criteria is found.
+ */
+ 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);
+ }
+
+ /**
+ * Once the visit has been performed and a matching node has been found, return the shortest path
+ * from the source set to that node. To do so, we need to backtrack the parents of the node until we
+ * find one of the source nodes (whose parent is -1).
+ */
+ public Path getPath() {
+ if (targetNode == null) {
+ return null; // No path found.
+ }
+
+ /* Backtrack from targetNode to a source node */
+ long curNode = targetNode;
+ ArrayList path = new ArrayList<>();
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = parents.get(curNode);
+ }
+ Collections.reverse(path);
+
+ /* Enrich path with node properties */
+ Path.Builder pathBuilder = Path.newBuilder();
+ for (long nodeId : path) {
+ Node.Builder nodeBuilder = Node.newBuilder();
+ NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, nodeId);
+ pathBuilder.addNode(nodeBuilder.build());
+ }
+ return pathBuilder.build();
+ }
+ }
+
+ /**
+ * FindPathBetween searches for a shortest path between a set of source nodes and a set of
+ * destination nodes.
+ *
+ * It does so by performing a *bidirectional breadth-first search*, i.e., two parallel breadth-first
+ * searches, one from the source set ("src-BFS") and one from the destination set ("dst-BFS"), until
+ * both searches find a common node that joins their visited sets. This node is called the "midpoint
+ * node". The path returned is the path src -> ... -> midpoint -> ... -> dst, which is always a
+ * shortest path between src and dst.
+ *
+ * The graph direction of both BFS can be configured separately. By default, the dst-BFS will use
+ * the graph in the opposite direction than the src-BFS (if direction = FORWARD, by default
+ * direction_reverse = BACKWARD, and vice-versa). The default behavior is thus to search for a
+ * shortest path between two nodes in a given direction. However, one can also specify FORWARD or
+ * BACKWARD for *both* the src-BFS and the dst-BFS. This will search for a common descendant or a
+ * common ancestor between the two sets, respectively. These will be the midpoints of the returned
+ * path.
+ */
+ 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);
+
+ GraphDirection direction = request.getDirection();
+ // if direction_reverse is not specified, use the opposite direction of direction
+ GraphDirection directionReverse = request.hasDirectionReverse()
+ ? request.getDirectionReverse()
+ : reverseDirection(request.getDirection());
+ SwhUnidirectionalGraph srcGraph = getDirectedGraph(bidirectionalGraph, direction);
+ SwhUnidirectionalGraph dstGraph = getDirectedGraph(bidirectionalGraph, directionReverse);
+
+ this.allowedEdgesSrc = new AllowedEdges(request.hasEdges() ? request.getEdges() : "*");
+ /*
+ * If edges_reverse is not specified: - If `edges` is not specified either, defaults to "*" - If
+ * direction == direction_reverse, defaults to `edges` - If direction != direction_reverse, defaults
+ * to the reverse of `edges` (e.g. "rev:dir" becomes "dir:rev").
+ */
+ this.allowedEdgesDst = request.hasEdgesReverse()
+ ? new AllowedEdges(request.getEdgesReverse())
+ : (request.hasEdges()
+ ? (direction == directionReverse
+ ? new AllowedEdges(request.getEdges())
+ : new AllowedEdges(request.getEdges()).reverse())
+ : new AllowedEdges("*"));
+
+ /*
+ * Source sub-visitor. Aborts as soon as it finds a node already visited by the destination
+ * sub-visitor.
+ */
+ 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);
+ }
+ };
+
+ /*
+ * Destination sub-visitor. Aborts as soon as it finds a node already visited by the source
+ * sub-visitor.
+ */
+ 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() {
+ /*
+ * Bidirectional BFS: maintain two sub-visitors, and alternately run a visit step in each of them.
+ */
+ 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; // No path found.
+ }
+ Path.Builder pathBuilder = Path.newBuilder();
+ ArrayList path = new ArrayList<>();
+
+ /* First section of the path: src -> midpoint */
+ long curNode = middleNode;
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = srcVisitor.parents.get(curNode);
+ }
+ pathBuilder.setMidpointIndex(path.size() - 1);
+ Collections.reverse(path);
+
+ /* Second section of the path: midpoint -> dst */
+ curNode = dstVisitor.parents.get(middleNode);
+ while (curNode != -1) {
+ path.add(curNode);
+ curNode = dstVisitor.parents.get(curNode);
+ }
+
+ /* Enrich path with node properties */
+ 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/main/java/org/softwareheritage/graph/server/App.java b/java/src/main/java/org/softwareheritage/graph/server/App.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/server/App.java
+++ /dev/null
@@ -1,196 +0,0 @@
-package org.softwareheritage.graph.server;
-
-import com.fasterxml.jackson.databind.ObjectMapper;
-import com.fasterxml.jackson.databind.PropertyNamingStrategy;
-import com.martiansoftware.jsap.*;
-import io.javalin.Javalin;
-import io.javalin.http.Context;
-import io.javalin.plugin.json.JavalinJackson;
-import org.softwareheritage.graph.SwhBidirectionalGraph;
-import org.softwareheritage.graph.Stats;
-import org.softwareheritage.graph.SWHID;
-
-import java.io.IOException;
-import java.util.List;
-import java.util.Map;
-
-/**
- * Web framework of the swh-graph server RPC API.
- *
- * @author The Software Heritage developers
- */
-
-public class App {
- /**
- * Main entrypoint.
- *
- * @param args command line arguments
- */
- public static void main(String[] args) throws IOException, JSAPException {
- SimpleJSAP jsap = new SimpleJSAP(App.class.getName(),
- "Server to load and query a compressed graph representation of Software Heritage archive.",
- new Parameter[]{
- new FlaggedOption("port", JSAP.INTEGER_PARSER, "5009", JSAP.NOT_REQUIRED, 'p', "port",
- "Binding port of the server."),
- new UnflaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED,
- JSAP.NOT_GREEDY, "The basename of the compressed graph."),
- new Switch("timings", 't', "timings", "Show timings in API result metadata."),});
-
- JSAPResult config = jsap.parse(args);
- if (jsap.messagePrinted()) {
- System.exit(1);
- }
-
- String graphPath = config.getString("graphPath");
- int port = config.getInt("port");
- boolean showTimings = config.getBoolean("timings");
-
- startServer(graphPath, port, showTimings);
- }
-
- /**
- * Loads compressed graph and starts the web server to query it.
- *
- * @param graphPath basename of the compressed graph
- * @param port binding port of the server
- * @param showTimings true if timings should be in results metadata, false otherwise
- */
- private static void startServer(String graphPath, int port, boolean showTimings) throws IOException {
- SwhBidirectionalGraph graph = SwhBidirectionalGraph.loadMapped(graphPath);
- Stats stats = new Stats(graphPath);
-
- // Clean up on exit
- Runtime.getRuntime().addShutdownHook(new Thread() {
- public void run() {
- try {
- graph.close();
- } catch (IOException e) {
- System.out.println("Could not clean up graph on exit: " + e);
- }
- }
- });
-
- // Configure Jackson JSON to use snake case naming style
- ObjectMapper objectMapper = JavalinJackson.getObjectMapper();
- objectMapper.setPropertyNamingStrategy(PropertyNamingStrategy.SNAKE_CASE);
- JavalinJackson.configure(objectMapper);
-
- Javalin app = Javalin.create().start(port);
-
- app.before("/stats/*", ctx -> {
- checkQueryStrings(ctx, "");
- });
- app.before("/leaves/*", ctx -> {
- checkQueryStrings(ctx, "direction|edges");
- });
- app.before("/neighbors/*", ctx -> {
- checkQueryStrings(ctx, "direction|edges");
- });
- app.before("/visit/*", ctx -> {
- checkQueryStrings(ctx, "direction|edges");
- });
- app.before("/walk/*", ctx -> {
- checkQueryStrings(ctx, "direction|edges|traversal");
- });
-
- app.get("/stats/", ctx -> {
- ctx.json(stats);
- });
-
- // Graph traversal endpoints
- // By default the traversal is a forward DFS using all edges
-
- app.get("/leaves/:src", ctx -> {
- SWHID src = new SWHID(ctx.pathParam("src"));
- String direction = ctx.queryParam("direction", "forward");
- String edgesFmt = ctx.queryParam("edges", "*");
-
- Endpoint endpoint = new Endpoint(graph, direction, edgesFmt);
- Endpoint.Output output = endpoint.leaves(new Endpoint.Input(src));
- ctx.json(formatEndpointOutput(output, showTimings));
- });
-
- app.get("/neighbors/:src", ctx -> {
- SWHID src = new SWHID(ctx.pathParam("src"));
- String direction = ctx.queryParam("direction", "forward");
- String edgesFmt = ctx.queryParam("edges", "*");
-
- Endpoint endpoint = new Endpoint(graph, direction, edgesFmt);
- Endpoint.Output output = endpoint.neighbors(new Endpoint.Input(src));
- ctx.json(formatEndpointOutput(output, showTimings));
- });
-
- app.get("/visit/nodes/:src", ctx -> {
- SWHID src = new SWHID(ctx.pathParam("src"));
- String direction = ctx.queryParam("direction", "forward");
- String edgesFmt = ctx.queryParam("edges", "*");
-
- Endpoint endpoint = new Endpoint(graph, direction, edgesFmt);
- Endpoint.Output output = endpoint.visitNodes(new Endpoint.Input(src));
- ctx.json(formatEndpointOutput(output, showTimings));
- });
-
- app.get("/visit/paths/:src", ctx -> {
- SWHID src = new SWHID(ctx.pathParam("src"));
- String direction = ctx.queryParam("direction", "forward");
- String edgesFmt = ctx.queryParam("edges", "*");
-
- Endpoint endpoint = new Endpoint(graph, direction, edgesFmt);
- Endpoint.Output output = endpoint.visitPaths(new Endpoint.Input(src));
- ctx.json(formatEndpointOutput(output, showTimings));
- });
-
- app.get("/walk/:src/:dst", ctx -> {
- SWHID src = new SWHID(ctx.pathParam("src"));
- String dstFmt = ctx.pathParam("dst");
- String direction = ctx.queryParam("direction", "forward");
- String edgesFmt = ctx.queryParam("edges", "*");
- String algorithm = ctx.queryParam("traversal", "dfs");
-
- Endpoint endpoint = new Endpoint(graph, direction, edgesFmt);
- Endpoint.Output output = endpoint.walk(new Endpoint.Input(src, dstFmt, algorithm));
- ctx.json(formatEndpointOutput(output, showTimings));
- });
-
- app.exception(IllegalArgumentException.class, (e, ctx) -> {
- ctx.status(400);
- ctx.result(e.getMessage());
- });
- }
-
- /**
- * Checks query strings names provided to the RPC API.
- *
- * @param ctx Javalin HTTP request context
- * @param allowedFmt a regular expression describing allowed query strings names
- * @throws IllegalArgumentException unknown query string provided
- */
- private static void checkQueryStrings(Context ctx, String allowedFmt) {
- Map> queryParamMap = ctx.queryParamMap();
- for (String key : queryParamMap.keySet()) {
- if (!key.matches(allowedFmt)) {
- throw new IllegalArgumentException("Unknown query string: " + key);
- }
- }
- }
-
- /**
- * Formats endpoint result into final JSON for the RPC API.
- *
- * Removes unwanted information if necessary, such as timings (to prevent use of side channels
- * attacks).
- *
- * @param output endpoint operation output which needs formatting
- * @param showTimings true if timings should be in results metadata, false otherwise
- * @return final Object with desired JSON format
- */
- private static Object formatEndpointOutput(Endpoint.Output output, boolean showTimings) {
- if (showTimings) {
- return output;
- } else {
- Map metaNoTimings = Map.of("nb_edges_accessed", output.meta.nbEdgesAccessed);
- Map outputNoTimings = Map.of("result", output.result, "meta", metaNoTimings);
- return outputNoTimings;
- }
- }
-}
diff --git a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java b/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java
deleted file mode 100644
--- a/java/src/main/java/org/softwareheritage/graph/server/Endpoint.java
+++ /dev/null
@@ -1,309 +0,0 @@
-package org.softwareheritage.graph.server;
-
-import org.softwareheritage.graph.*;
-import org.softwareheritage.graph.benchmark.utils.Timing;
-
-import java.util.ArrayList;
-
-/**
- * RPC API endpoints wrapper functions.
- *
- * Graph operations are segmented between high-level class (this one) and the low-level class
- * ({@link Traversal}). The {@link Endpoint} class creates wrappers for each endpoints by performing
- * all the input/output node ids conversions and logging timings.
- *
- * @author The Software Heritage developers
- * @see Traversal
- */
-
-public class Endpoint {
- /** Graph where traversal endpoint is performed */
- SwhBidirectionalGraph graph;
- /** Internal traversal API */
- Traversal traversal;
-
- /**
- * Constructor.
- *
- * @param graph the graph used for traversal endpoint
- * @param direction a string (either "forward" or "backward") specifying edge orientation
- * @param edgesFmt a formatted string describing allowed
- * edges
- */
- public Endpoint(SwhBidirectionalGraph graph, String direction, String edgesFmt) {
- this.graph = graph;
- this.traversal = new Traversal(graph, direction, edgesFmt);
- }
-
- /**
- * Converts a list of (internal) long node ids to a list of corresponding (external) SWHIDs.
- *
- * @param nodeIds the list of long node ids
- * @return a list of corresponding SWHIDs
- */
- private ArrayList convertNodesToSWHIDs(ArrayList nodeIds) {
- ArrayList swhids = new ArrayList<>();
- for (long nodeId : nodeIds) {
- swhids.add(graph.getSWHID(nodeId));
- }
- return swhids;
- }
-
- /**
- * Converts a list of (internal) long node ids to the corresponding {@link SwhPath}.
- *
- * @param nodeIds the list of long node ids
- * @return the corresponding {@link SwhPath}
- * @see org.softwareheritage.graph.SwhPath
- */
- private SwhPath convertNodesToSwhPath(ArrayList nodeIds) {
- SwhPath path = new SwhPath();
- for (long nodeId : nodeIds) {
- path.add(graph.getSWHID(nodeId));
- }
- return path;
- }
-
- /**
- * Converts a list of paths made of (internal) long node ids to one made of {@link SwhPath}-s.
- *
- * @param pathsNodeId the list of paths with long node ids
- * @return a list of corresponding {@link SwhPath}
- * @see org.softwareheritage.graph.SwhPath
- */
- private ArrayList convertPathsToSWHIDs(ArrayList> pathsNodeId) {
- ArrayList paths = new ArrayList<>();
- for (ArrayList path : pathsNodeId) {
- paths.add(convertNodesToSwhPath(path));
- }
- return paths;
- }
-
- /**
- * Leaves endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @return the resulting list of {@link SWHID} from endpoint call and operation metadata
- * @see SWHID
- * @see Traversal#leaves(long)
- */
- public Output leaves(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.swhid2node = Timing.stop(startTime);
-
- startTime = Timing.start();
- ArrayList nodeIds = traversal.leaves(srcNodeId);
- output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
-
- startTime = Timing.start();
- output.result = convertNodesToSWHIDs(nodeIds);
- output.meta.timings.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * Neighbors endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @return the resulting list of {@link SWHID} from endpoint call and operation metadata
- * @see SWHID
- * @see Traversal#neighbors(long)
- */
- public Output neighbors(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.swhid2node = Timing.stop(startTime);
-
- startTime = Timing.start();
- ArrayList nodeIds = traversal.neighbors(srcNodeId);
- output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
-
- startTime = Timing.start();
- output.result = convertNodesToSWHIDs(nodeIds);
- output.meta.timings.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * Walk endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @return the resulting {@link SwhPath} from endpoint call and operation metadata
- * @see SWHID
- * @see org.softwareheritage.graph.SwhPath
- * @see Traversal#walk
- */
- public Output walk(Input input) {
- Output output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.swhid2node = Timing.stop(startTime);
-
- ArrayList nodeIds = new ArrayList();
-
- // Destination is either a SWHID or a node type
- try {
- SWHID dstSWHID = new SWHID(input.dstFmt);
- long dstNodeId = graph.getNodeId(dstSWHID);
-
- startTime = Timing.start();
- nodeIds = traversal.walk(srcNodeId, dstNodeId, input.algorithm);
- output.meta.timings.traversal = Timing.stop(startTime);
- } catch (IllegalArgumentException ignored1) {
- try {
- Node.Type dstType = Node.Type.fromStr(input.dstFmt);
-
- startTime = Timing.start();
- nodeIds = traversal.walk(srcNodeId, dstType, input.algorithm);
- output.meta.timings.traversal = Timing.stop(startTime);
- } catch (IllegalArgumentException ignored2) {
- }
- }
-
- output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
-
- startTime = Timing.start();
- output.result = convertNodesToSwhPath(nodeIds);
- output.meta.timings.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * VisitNodes endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @return the resulting list of {@link SWHID} from endpoint call and operation metadata
- * @see SWHID
- * @see Traversal#visitNodes(long)
- */
- public Output visitNodes(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.swhid2node = Timing.stop(startTime);
-
- startTime = Timing.start();
- ArrayList nodeIds = traversal.visitNodes(srcNodeId);
- output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
-
- startTime = Timing.start();
- output.result = convertNodesToSWHIDs(nodeIds);
- output.meta.timings.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * VisitPaths endpoint wrapper.
- *
- * @param input input parameters for the underlying endpoint call
- * @return the resulting list of {@link SwhPath} from endpoint call and operation metadata
- * @see SWHID
- * @see org.softwareheritage.graph.SwhPath
- * @see Traversal#visitPaths(long)
- */
- public Output visitPaths(Input input) {
- Output> output = new Output<>();
- long startTime;
-
- startTime = Timing.start();
- long srcNodeId = graph.getNodeId(input.src);
- output.meta.timings.swhid2node = Timing.stop(startTime);
-
- startTime = Timing.start();
- ArrayList> paths = traversal.visitPaths(srcNodeId);
- output.meta.timings.traversal = Timing.stop(startTime);
- output.meta.nbEdgesAccessed = traversal.getNbEdgesAccessed();
-
- startTime = Timing.start();
- output.result = convertPathsToSWHIDs(paths);
- output.meta.timings.node2swhid = Timing.stop(startTime);
-
- return output;
- }
-
- /**
- * Wrapper class to unify traversal methods input signatures.
- */
- public static class Input {
- /** Source node of endpoint call specified as a {@link SWHID} */
- public SWHID src;
- /**
- * Destination formatted string as described in the
- * API
- */
- public String dstFmt;
- /** Traversal algorithm used in endpoint call (either "dfs" or "bfs") */
- public String algorithm;
-
- public Input(SWHID src) {
- this.src = src;
- }
-
- public Input(SWHID src, String dstFmt, String algorithm) {
- this.src = src;
- this.dstFmt = dstFmt;
- this.algorithm = algorithm;
- }
- }
-
- /**
- * Wrapper class to return both the endpoint result and metadata (such as timings).
- */
- public static class Output {
- /** The result content itself */
- public T result;
- /** Various metadata about the result */
- public Meta meta;
-
- public Output() {
- this.result = null;
- this.meta = new Meta();
- }
-
- /**
- * Endpoint result metadata.
- */
- public class Meta {
- /** Operations timings */
- public Timings timings;
- /** Number of edges accessed during traversal */
- public long nbEdgesAccessed;
-
- public Meta() {
- this.timings = new Timings();
- this.nbEdgesAccessed = 0;
- }
-
- /**
- * Wrapper class for JSON output format.
- */
- public class Timings {
- /** Time in seconds to do the traversal */
- public double traversal;
- /** Time in seconds to convert input SWHID to node id */
- public double swhid2node;
- /** Time in seconds to convert output node ids to SWHIDs */
- public double node2swhid;
- }
- }
- }
-}
diff --git a/java/src/main/proto b/java/src/main/proto
new file mode 120000
--- /dev/null
+++ b/java/src/main/proto
@@ -0,0 +1 @@
+../../../proto
\ No newline at end of file
diff --git a/java/src/test/java/org/softwareheritage/graph/GraphTest.java b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
--- a/java/src/test/java/org/softwareheritage/graph/GraphTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
@@ -6,15 +6,15 @@
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Comparator;
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;
+import static org.junit.Assert.assertEquals;
public class GraphTest {
static SwhBidirectionalGraph graph;
@@ -23,11 +23,14 @@
@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;
}
@@ -35,8 +38,12 @@
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 void assertEqualsAnyOrder(Collection expected, Collection actual) {
+ ArrayList expectedList = new ArrayList<>(expected);
+ ArrayList actualList = new ArrayList<>(actual);
+ expectedList.sort(Comparator.comparing(Object::toString));
+ actualList.sort(Comparator.comparing(Object::toString));
+ assertEquals(expectedList, actualList);
}
public static ArrayList lazyLongIteratorToList(LazyLongIterator input) {
diff --git a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java b/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/NeighborsTest.java
+++ /dev/null
@@ -1,141 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.ArrayList;
-
-import org.junit.jupiter.api.Test;
-import org.softwareheritage.graph.server.Endpoint;
-
-// Avoid warnings concerning Endpoint.Output.result manual cast
-@SuppressWarnings("unchecked")
-public class NeighborsTest extends GraphTest {
- @Test
- public void zeroNeighbor() {
- SwhBidirectionalGraph graph = getGraph();
- ArrayList expectedNodes = new ArrayList<>();
-
- SWHID src1 = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals1);
-
- SWHID src2 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals2);
-
- SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015");
- Endpoint endpoint3 = new Endpoint(graph, "forward", "*");
- ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals3);
-
- SWHID src4 = new SWHID("swh:1:rel:0000000000000000000000000000000000000019");
- Endpoint endpoint4 = new Endpoint(graph, "backward", "*");
- ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals4);
-
- SWHID src5 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint5 = new Endpoint(graph, "forward", "snp:*,rev:*,rel:*");
- ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes, actuals5);
- }
-
- @Test
- public void oneNeighbor() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList expectedNodes1 = new ArrayList<>();
- expectedNodes1.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002"));
- ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1);
-
- SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000017");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt");
- ArrayList expectedNodes2 = new ArrayList<>();
- expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000014"));
- ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2);
-
- SWHID src3 = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint3 = new Endpoint(graph, "backward", "*");
- ArrayList expectedNodes3 = new ArrayList<>();
- expectedNodes3.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013"));
- ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3);
-
- SWHID src4 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:rev");
- ArrayList expectedNodes4 = new ArrayList<>();
- expectedNodes4.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013"));
- ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4);
-
- SWHID src5 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint5 = new Endpoint(graph, "backward", "*");
- ArrayList expectedNodes5 = new ArrayList<>();
- expectedNodes5.add(new SWHID(TEST_ORIGIN_ID));
- ArrayList actuals5 = (ArrayList) endpoint5.neighbors(new Endpoint.Input(src5)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes5, actuals5);
- }
-
- @Test
- public void twoNeighbors() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList expectedNodes1 = new ArrayList<>();
- expectedNodes1.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010"));
- expectedNodes1.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009"));
- ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1);
-
- SWHID src2 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint2 = new Endpoint(graph, "forward", "dir:cnt");
- ArrayList expectedNodes2 = new ArrayList<>();
- expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedNodes2.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"));
- ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2);
-
- SWHID src3 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001");
- Endpoint endpoint3 = new Endpoint(graph, "backward", "*");
- ArrayList expectedNodes3 = new ArrayList<>();
- expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000008"));
- expectedNodes3.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002"));
- ArrayList actuals3 = (ArrayList) endpoint3.neighbors(new Endpoint.Input(src3)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes3, actuals3);
-
- SWHID src4 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- Endpoint endpoint4 = new Endpoint(graph, "backward", "rev:snp,rev:rel");
- ArrayList expectedNodes4 = new ArrayList<>();
- expectedNodes4.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020"));
- expectedNodes4.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010"));
- ArrayList actuals4 = (ArrayList) endpoint4.neighbors(new Endpoint.Input(src4)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes4, actuals4);
- }
-
- @Test
- public void threeNeighbors() {
- SwhBidirectionalGraph graph = getGraph();
-
- SWHID src1 = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- 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"));
- ArrayList actuals1 = (ArrayList) endpoint1.neighbors(new Endpoint.Input(src1)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes1, actuals1);
-
- SWHID src2 = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- 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"));
- ArrayList actuals2 = (ArrayList) endpoint2.neighbors(new Endpoint.Input(src2)).result;
- GraphTest.assertEqualsAnyOrder(expectedNodes2, actuals2);
- }
-}
diff --git a/java/src/test/java/org/softwareheritage/graph/VisitTest.java b/java/src/test/java/org/softwareheritage/graph/VisitTest.java
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/VisitTest.java
+++ /dev/null
@@ -1,408 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.ArrayList;
-import java.util.Set;
-import java.util.HashSet;
-
-import org.junit.jupiter.api.Test;
-import org.softwareheritage.graph.server.Endpoint;
-
-// Avoid warnings concerning Endpoint.Output.result manual cast
-@SuppressWarnings("unchecked")
-public class VisitTest extends GraphTest {
- private void assertSameNodesFromPaths(ArrayList paths, ArrayList nodes) {
- Set expectedNodes = new HashSet();
- for (SwhPath path : paths) {
- expectedNodes.addAll(path.getPath());
- }
- GraphTest.assertEqualsAnyOrder(expectedNodes, nodes);
- }
-
- @Test
- public void forwardFromRoot() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID, "swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardFromMiddle() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:cnt:0000000000000000000000000000000000000011"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardFromLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:cnt:0000000000000000000000000000000000000004"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void backwardFromRoot() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath(TEST_ORIGIN_ID));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void backwardFromMiddle() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:dir:0000000000000000000000000000000000000012");
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rel:0000000000000000000000000000000000000019"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void backwardFromLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:cnt:0000000000000000000000000000000000000004",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rel:0000000000000000000000000000000000000019"));
- expectedPaths.add(new SwhPath("swh:1:cnt:0000000000000000000000000000000000000004",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rel:0000000000000000000000000000000000000019"));
- expectedPaths.add(new SwhPath("swh:1:cnt:0000000000000000000000000000000000000004",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:snp:0000000000000000000000000000000000000020", TEST_ORIGIN_ID));
- expectedPaths.add(new SwhPath("swh:1:cnt:0000000000000000000000000000000000000004",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:snp:0000000000000000000000000000000000000020", TEST_ORIGIN_ID));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardSnpToRev() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:rev");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "snp:rev");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardRelToRevRevToRev() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rel:0000000000000000000000000000000000000010");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "rel:rev,rev:rev");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "rel:rev,rev:rev");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardRevToAllDirToAll() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000013");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:*,dir:*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:*,dir:*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:cnt:0000000000000000000000000000000000000011"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:dir:0000000000000000000000000000000000000012",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardSnpToAllRevToAll() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "snp:*,rev:*");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "snp:*,rev:*");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002"));
- expectedPaths.add(new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008"));
- expectedPaths.add(new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardNoEdges() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint1 = new Endpoint(graph, "forward", "");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:snp:0000000000000000000000000000000000000020"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void backwardRevToRevRevToRel() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- Endpoint endpoint1 = new Endpoint(graph, "backward", "rev:rev,rev:rel");
- ArrayList paths = (ArrayList) endpoint1.visitPaths(new Endpoint.Input(swhid)).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "rev:rev,rev:rel");
- ArrayList nodes = (ArrayList) endpoint2.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedPaths = new ArrayList();
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rel:0000000000000000000000000000000000000019"));
- expectedPaths.add(new SwhPath("swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rel:0000000000000000000000000000000000000010"));
-
- GraphTest.assertEqualsAnyOrder(expectedPaths, paths);
- assertSameNodesFromPaths(expectedPaths, nodes);
- }
-
- @Test
- public void forwardFromRootNodesOnly() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID(TEST_ORIGIN_ID);
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
- ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedNodes = new ArrayList();
- expectedNodes.add(new SWHID(TEST_ORIGIN_ID));
- expectedNodes.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020"));
- expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010"));
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009"));
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003"));
- expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000002"));
- expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"));
- expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000008"));
- expectedNodes.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000006"));
- expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"));
- expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005"));
- expectedNodes.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"));
-
- GraphTest.assertEqualsAnyOrder(expectedNodes, nodes);
- }
-
- @Test
- public void backwardRevToAllNodesOnly() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID swhid = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- Endpoint endpoint = new Endpoint(graph, "backward", "rev:*");
- ArrayList nodes = (ArrayList) endpoint.visitNodes(new Endpoint.Input(swhid)).result;
-
- ArrayList expectedNodes = new ArrayList();
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000003"));
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000009"));
- expectedNodes.add(new SWHID("swh:1:snp:0000000000000000000000000000000000000020"));
- expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000010"));
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000013"));
- expectedNodes.add(new SWHID("swh:1:rev:0000000000000000000000000000000000000018"));
- expectedNodes.add(new SWHID("swh:1:rel:0000000000000000000000000000000000000019"));
-
- GraphTest.assertEqualsAnyOrder(expectedNodes, nodes);
- }
-}
diff --git a/java/src/test/java/org/softwareheritage/graph/WalkTest.java b/java/src/test/java/org/softwareheritage/graph/WalkTest.java
deleted file mode 100644
--- a/java/src/test/java/org/softwareheritage/graph/WalkTest.java
+++ /dev/null
@@ -1,187 +0,0 @@
-package org.softwareheritage.graph;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.junit.jupiter.api.Assertions;
-import org.junit.jupiter.api.Test;
-import org.softwareheritage.graph.server.Endpoint;
-
-public class WalkTest extends GraphTest {
- @Test
- public void forwardRootToLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- String dstFmt = "swh:1:cnt:0000000000000000000000000000000000000005";
-
- SwhPath solution1 = new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005");
- SwhPath solution2 = new SwhPath("swh:1:snp:0000000000000000000000000000000000000020",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005");
-
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- List possibleSolutions = Arrays.asList(solution1, solution2);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void forwardLeafToLeaf() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000007");
- String dstFmt = "cnt";
-
- SwhPath expectedPath = new SwhPath("swh:1:cnt:0000000000000000000000000000000000000007");
-
- Endpoint endpoint1 = new Endpoint(graph, "forward", "*");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "*");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void forwardRevToRev() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018");
- String dstFmt = "swh:1:rev:0000000000000000000000000000000000000003";
-
- SwhPath expectedPath = new SwhPath("swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003");
-
- Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:rev");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:rev");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void backwardRevToRev() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000003");
- String dstFmt = "swh:1:rev:0000000000000000000000000000000000000018";
-
- SwhPath expectedPath = new SwhPath("swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000013",
- "swh:1:rev:0000000000000000000000000000000000000018");
-
- Endpoint endpoint1 = new Endpoint(graph, "backward", "rev:rev");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "rev:rev");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-
- @Test
- public void backwardCntToFirstSnp() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000001");
- String dstFmt = "snp";
-
- SwhPath solution1 = new SwhPath("swh:1:cnt:0000000000000000000000000000000000000001",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:snp:0000000000000000000000000000000000000020");
- SwhPath solution2 = new SwhPath("swh:1:cnt:0000000000000000000000000000000000000001",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:snp:0000000000000000000000000000000000000020");
- SwhPath solution3 = new SwhPath("swh:1:cnt:0000000000000000000000000000000000000001",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:snp:0000000000000000000000000000000000000020");
- SwhPath solution4 = new SwhPath("swh:1:cnt:0000000000000000000000000000000000000001",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rel:0000000000000000000000000000000000000010",
- "swh:1:snp:0000000000000000000000000000000000000020");
-
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- List possibleSolutions = Arrays.asList(solution1, solution2, solution3, solution4);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void forwardRevToFirstCnt() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000009");
- String dstFmt = "cnt";
-
- SwhPath solution1 = new SwhPath("swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000007");
- SwhPath solution2 = new SwhPath("swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000005");
- SwhPath solution3 = new SwhPath("swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:dir:0000000000000000000000000000000000000006",
- "swh:1:cnt:0000000000000000000000000000000000000004");
- SwhPath solution4 = new SwhPath("swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:dir:0000000000000000000000000000000000000008",
- "swh:1:cnt:0000000000000000000000000000000000000001");
- SwhPath solution5 = new SwhPath("swh:1:rev:0000000000000000000000000000000000000009",
- "swh:1:rev:0000000000000000000000000000000000000003",
- "swh:1:dir:0000000000000000000000000000000000000002",
- "swh:1:cnt:0000000000000000000000000000000000000001");
-
- Endpoint endpoint1 = new Endpoint(graph, "forward", "rev:*,dir:*");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "forward", "rev:*,dir:*");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- List possibleSolutions = Arrays.asList(solution1, solution2, solution3, solution4, solution5);
- Assertions.assertTrue(possibleSolutions.contains(dfsPath));
- Assertions.assertTrue(possibleSolutions.contains(bfsPath));
- }
-
- @Test
- public void backwardDirToFirstRel() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000016");
- String dstFmt = "rel";
-
- SwhPath expectedPath = new SwhPath("swh:1:dir:0000000000000000000000000000000000000016",
- "swh:1:dir:0000000000000000000000000000000000000017",
- "swh:1:rev:0000000000000000000000000000000000000018",
- "swh:1:rel:0000000000000000000000000000000000000019");
-
- Endpoint endpoint1 = new Endpoint(graph, "backward", "dir:dir,dir:rev,rev:*");
- SwhPath dfsPath = (SwhPath) endpoint1.walk(new Endpoint.Input(src, dstFmt, "dfs")).result;
- Endpoint endpoint2 = new Endpoint(graph, "backward", "dir:dir,dir:rev,rev:*");
- SwhPath bfsPath = (SwhPath) endpoint2.walk(new Endpoint.Input(src, dstFmt, "bfs")).result;
-
- Assertions.assertEquals(dfsPath, expectedPath);
- Assertions.assertEquals(bfsPath, expectedPath);
- }
-}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2022 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
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class CountEdgesTest extends TraversalServiceTest {
+ private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
+ return TraversalRequest.newBuilder().addSrc(src.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .countEdges(TraversalRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countEdges(
+ TraversalRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countEdges(
+ TraversalRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void forwardFromRoot() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build());
+ assertEquals(13, actual.getCount());
+ }
+
+ @Test
+ public void forwardFromMiddle() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
+ assertEquals(7, actual.getCount());
+ }
+
+ @Test
+ public void forwardRelRev() {
+ CountResponse actual = client
+ .countEdges(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build());
+ assertEquals(2, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromMiddle() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(3, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromLeaf() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(12, actual.getCount());
+ }
+
+ @Test
+ public void backwardRevToRevRevToRel() {
+ CountResponse actual = client.countEdges(getTraversalRequestBuilder(fakeSWHID("rev", 3))
+ .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(5, actual.getCount());
+ }
+
+ @Test
+ public void testWithEmptyMask() {
+ CountResponse actual = client.countEdges(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setMask(FieldMask.getDefaultInstance()).build());
+ assertEquals(7, actual.getCount());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2022 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
+ */
+
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.FieldMask;
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class CountNodesTest extends TraversalServiceTest {
+ private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
+ return TraversalRequest.newBuilder().addSrc(src.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .countNodes(TraversalRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countNodes(
+ TraversalRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.countNodes(
+ TraversalRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void forwardFromRoot() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).build());
+ assertEquals(12, actual.getCount());
+ }
+
+ @Test
+ public void forwardFromMiddle() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
+ assertEquals(8, actual.getCount());
+ }
+
+ @Test
+ public void forwardRelRev() {
+ CountResponse actual = client
+ .countNodes(getTraversalRequestBuilder(fakeSWHID("rel", 10)).setEdges("rel:rev,rev:rev").build());
+ assertEquals(3, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromMiddle() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(4, actual.getCount());
+ }
+
+ @Test
+ public void backwardFromLeaf() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("cnt", 4)).setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(11, actual.getCount());
+ }
+
+ @Test
+ public void backwardRevToRevRevToRel() {
+ CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("rev", 3))
+ .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).build());
+ assertEquals(6, actual.getCount());
+ }
+
+ @Test
+ public void testWithEmptyMask() {
+ CountResponse actual = client.countNodes(
+ getTraversalRequestBuilder(fakeSWHID("dir", 12)).setMask(FieldMask.getDefaultInstance()).build());
+ assertEquals(8, actual.getCount());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathBetweenTest.java
@@ -0,0 +1,203 @@
+package org.softwareheritage.graph.rpc;
+
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class FindPathBetweenTest extends TraversalServiceTest {
+ private FindPathBetweenRequest.Builder getRequestBuilder(SWHID src, SWHID dst) {
+ return FindPathBetweenRequest.newBuilder().addSrc(src.toString()).addDst(dst.toString());
+ }
+
+ @Test
+ public void testSwhidErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class,
+ () -> client.findPathBetween(FindPathBetweenRequest.newBuilder().addSrc(TEST_ORIGIN_ID)
+ .addDst("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testEdgeErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathBetween(FindPathBetweenRequest
+ .newBuilder().addSrc(TEST_ORIGIN_ID).addDst(TEST_ORIGIN_ID).setEdges("batracien:reptile").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ // Test path between ori 1 and cnt 4 (forward graph)
+ @Test
+ public void forwardRootToLeaf() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), fakeSWHID("cnt", 4)).build()));
+ List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9),
+ fakeSWHID("dir", 8), fakeSWHID("dir", 6), fakeSWHID("cnt", 4));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between rev 18 and rev 3 (forward graph)
+ @Test
+ public void forwardRevToRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 18), fakeSWHID("rev", 3)).build()));
+ List expected = List.of(fakeSWHID("rev", 18), fakeSWHID("rev", 13), fakeSWHID("rev", 9),
+ fakeSWHID("rev", 3));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between rev 3 and rev 18 (backward graph)
+ @Test
+ public void backwardRevToRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 3), fakeSWHID("rev", 18))
+ .setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("rev", 3), fakeSWHID("rev", 9), fakeSWHID("rev", 13),
+ fakeSWHID("rev", 18));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between cnt 4 and itself (forward graph)
+ @Test
+ public void forwardCntToItself() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 4)).build()));
+ List expected = List.of(fakeSWHID("cnt", 4));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from ori and rel 19 and find cnt 14 or cnt 7 (forward graph)
+ @Test
+ public void forwardMultipleSourcesDest() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 14))
+ .addSrc(TEST_ORIGIN_ID).addDst(fakeSWHID("cnt", 7).toString()).build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("cnt", 14));
+ }
+
+ // Start from cnt 4 and cnt 11 and find rev 13 or rev 9 (backward graph)
+ @Test
+ public void backwardMultipleSourcesDest() {
+ ArrayList actual = getSWHIDs(client.findPathBetween(
+ getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 13)).setDirection(GraphDirection.BACKWARD)
+ .addSrc(fakeSWHID("cnt", 11).toString()).addDst(fakeSWHID("rev", 9).toString()).build()));
+ List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from all directories and find the origin (backward graph)
+ @Test
+ public void backwardMultipleSourcesAllDirToOri() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("dir", 2), new SWHID(TEST_ORIGIN_ID))
+ .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString())
+ .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString())
+ .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20),
+ new SWHID(TEST_ORIGIN_ID));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from cnt 4 and find any rev (backward graph)
+ @Test
+ public void backwardCntToAnyRev() {
+ ArrayList actual = getSWHIDs(
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("rev", 3))
+ .addDst(fakeSWHID("rev", 9).toString()).addDst(fakeSWHID("rev", 13).toString())
+ .addDst(fakeSWHID("rev", 18).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("cnt", 4), fakeSWHID("dir", 6), fakeSWHID("dir", 8),
+ fakeSWHID("rev", 9));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Impossible path between rev 9 and cnt 14
+ @Test
+ public void forwardImpossiblePath() {
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(getRequestBuilder(fakeSWHID("rev", 9), fakeSWHID("cnt", 14)).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+
+ // Reverse direction
+ thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 14), fakeSWHID("rev", 9))
+ .setDirection(GraphDirection.BACKWARD).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+
+ // Common ancestor between cnt 4 and cnt 15 : rev 18
+ @Test
+ public void commonAncestorBackwardBackward() {
+ Path p = client.findPathBetween(getRequestBuilder(fakeSWHID("cnt", 4), fakeSWHID("cnt", 15))
+ .setDirection(GraphDirection.BACKWARD).setDirectionReverse(GraphDirection.BACKWARD).build());
+ ArrayList actual = getSWHIDs(p);
+ SWHID expected = fakeSWHID("rev", 18);
+ Assertions.assertEquals(expected, actual.get(p.getMidpointIndex()));
+ }
+
+ // 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.getMidpointIndex()));
+ }
+
+ // Path between rel 19 and cnt 15 with various max depths
+ @Test
+ public void maxDepth() {
+ // Works with max_depth = 2
+ ArrayList actual = getSWHIDs(client
+ .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(2).build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("dir", 16), fakeSWHID("cnt", 15));
+ Assertions.assertEquals(expected, actual);
+
+ // Check that it throws NOT_FOUND with max depth = 1
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(
+ getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxDepth(1).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+
+ // Path between rel 19 and cnt 15 with various max edges
+ @Test
+ public void maxEdges() {
+ // Works with max_edges = 3
+ ArrayList actual = getSWHIDs(client
+ .findPathBetween(getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(3).build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("dir", 16), fakeSWHID("cnt", 15));
+ Assertions.assertEquals(expected, actual);
+
+ // Check that it throws NOT_FOUND with max_edges = 2
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathBetween(
+ getRequestBuilder(fakeSWHID("rel", 19), fakeSWHID("cnt", 15)).setMaxEdges(2).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/FindPathToTest.java
@@ -0,0 +1,162 @@
+package org.softwareheritage.graph.rpc;
+
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+public class FindPathToTest extends TraversalServiceTest {
+ private FindPathToRequest.Builder getRequestBuilder(SWHID src, String allowedNodes) {
+ return FindPathToRequest.newBuilder().addSrc(src.toString())
+ .setTarget(NodeFilter.newBuilder().setTypes(allowedNodes).build());
+ }
+
+ @Test
+ public void testSrcErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client
+ .findPathTo(FindPathToRequest.newBuilder().addSrc(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo(
+ FindPathToRequest.newBuilder().addSrc("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo(
+ FindPathToRequest.newBuilder().addSrc("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testEdgeErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.findPathTo(
+ FindPathToRequest.newBuilder().addSrc(TEST_ORIGIN_ID).setEdges("batracien:reptile").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testTargetErrors() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class,
+ () -> client.findPathTo(FindPathToRequest.newBuilder().addSrc(TEST_ORIGIN_ID)
+ .setTarget(NodeFilter.newBuilder().setTypes("argoumante,eglomatique").build()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ // Test path between ori 1 and any dir (forward graph)
+ @Test
+ public void forwardOriToFirstDir() {
+ ArrayList actual = getSWHIDs(
+ client.findPathTo(getRequestBuilder(new SWHID(TEST_ORIGIN_ID), "dir").build()));
+ List expected = List.of(new SWHID(TEST_ORIGIN_ID), fakeSWHID("snp", 20), fakeSWHID("rev", 9),
+ fakeSWHID("dir", 8));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between rel 19 and any cnt (forward graph)
+ @Test
+ public void forwardRelToFirstCnt() {
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("rel", 19), "cnt").build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("cnt", 14));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between dir 16 and any rel (backward graph)
+ @Test
+ public void backwardDirToFirstRel() {
+ ArrayList actual = getSWHIDs(client.findPathTo(
+ getRequestBuilder(fakeSWHID("dir", 16), "rel").setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("dir", 16), fakeSWHID("dir", 17), fakeSWHID("rev", 18),
+ fakeSWHID("rel", 19));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Test path between cnt 4 and itself (forward graph)
+ @Test
+ public void forwardCntToItself() {
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 4), "cnt").build()));
+ List expected = List.of(fakeSWHID("cnt", 4));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from ori and rel 19 and find any cnt (forward graph)
+ @Test
+ public void forwardMultipleSources() {
+ ArrayList actual = getSWHIDs(
+ client.findPathTo(getRequestBuilder(fakeSWHID("rel", 19), "cnt").addSrc(TEST_ORIGIN_ID).build()));
+ List expected = List.of(fakeSWHID("rel", 19), fakeSWHID("rev", 18), fakeSWHID("dir", 17),
+ fakeSWHID("cnt", 14));
+ }
+
+ // Start from cnt 4 and cnt 11 and find any rev (backward graph)
+ @Test
+ public void backwardMultipleSources() {
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 4), "rev")
+ .addSrc(fakeSWHID("cnt", 11).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("cnt", 11), fakeSWHID("dir", 12), fakeSWHID("rev", 13));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Start from all directories and find any origin (backward graph)
+ @Test
+ public void backwardMultipleSourcesAllDirToOri() {
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("dir", 2), "ori")
+ .addSrc(fakeSWHID("dir", 6).toString()).addSrc(fakeSWHID("dir", 8).toString())
+ .addSrc(fakeSWHID("dir", 12).toString()).addSrc(fakeSWHID("dir", 16).toString())
+ .addSrc(fakeSWHID("dir", 17).toString()).setDirection(GraphDirection.BACKWARD).build()));
+ List expected = List.of(fakeSWHID("dir", 8), fakeSWHID("rev", 9), fakeSWHID("snp", 20),
+ new SWHID(TEST_ORIGIN_ID));
+ Assertions.assertEquals(expected, actual);
+ }
+
+ // Impossible path between rev 9 and any release (forward graph)
+ @Test
+ public void forwardImpossiblePath() {
+ // Check that the return is STATUS.NOT_FOUND
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathTo(getRequestBuilder(fakeSWHID("rev", 9), "rel").build());
+ });
+ Assertions.assertEquals(thrown.getStatus(), Status.NOT_FOUND);
+ }
+
+ // Path from cnt 15 to any rel with various max depths
+ @Test
+ public void maxDepth() {
+ // Works with max_depth = 2
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel")
+ .setDirection(GraphDirection.BACKWARD).setMaxDepth(4).build()));
+ List expected = List.of(fakeSWHID("cnt", 15), fakeSWHID("dir", 16), fakeSWHID("dir", 17),
+ fakeSWHID("rev", 18), fakeSWHID("rel", 19));
+ Assertions.assertEquals(expected, actual);
+
+ // Check that it throws NOT_FOUND with max depth = 1
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel").setDirection(GraphDirection.BACKWARD)
+ .setMaxDepth(3).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+
+ // Path from cnt 15 to any rel with various max edges
+ @Test
+ public void maxEdges() {
+ ArrayList actual = getSWHIDs(client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel")
+ .setDirection(GraphDirection.BACKWARD).setMaxEdges(4).build()));
+ List expected = List.of(fakeSWHID("cnt", 15), fakeSWHID("dir", 16), fakeSWHID("dir", 17),
+ fakeSWHID("rev", 18), fakeSWHID("rel", 19));
+ Assertions.assertEquals(expected, actual);
+
+ StatusRuntimeException thrown = Assertions.assertThrows(StatusRuntimeException.class, () -> {
+ client.findPathTo(getRequestBuilder(fakeSWHID("cnt", 15), "rel").setDirection(GraphDirection.BACKWARD)
+ .setMaxEdges(3).build());
+ });
+ Assertions.assertEquals(thrown.getStatus().getCode(), Status.NOT_FOUND.getCode());
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/GetNodeTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/GetNodeTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/GetNodeTest.java
@@ -0,0 +1,284 @@
+package org.softwareheritage.graph.rpc;
+
+import com.google.protobuf.Descriptors;
+import com.google.protobuf.FieldMask;
+import io.grpc.Status;
+import io.grpc.StatusRuntimeException;
+import org.junit.jupiter.api.Test;
+import org.softwareheritage.graph.SWHID;
+
+import java.util.*;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class GetNodeTest extends TraversalServiceTest {
+ @Test
+ public void testNotFound() {
+ StatusRuntimeException thrown = assertThrows(StatusRuntimeException.class,
+ () -> client.getNode(GetNodeRequest.newBuilder().setSwhid(fakeSWHID("cnt", 404).toString()).build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testInvalidSwhid() {
+ StatusRuntimeException thrown;
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.getNode(
+ GetNodeRequest.newBuilder().setSwhid("swh:1:lol:0000000000000000000000000000000000000001").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ thrown = assertThrows(StatusRuntimeException.class, () -> client.getNode(
+ GetNodeRequest.newBuilder().setSwhid("swh:1:cnt:000000000000000000000000000000000000000z").build()));
+ assertEquals(Status.INVALID_ARGUMENT.getCode(), thrown.getStatus().getCode());
+ }
+
+ @Test
+ public void testContents() {
+ List expectedCnts = List.of(1, 4, 5, 7, 11, 14, 15);
+ Map expectedLengths = Map.of(1, 42, 4, 404, 5, 1337, 7, 666, 11, 313, 14, 14, 15, 404);
+ Set expectedSkipped = Set.of(15);
+
+ for (Integer cntId : expectedCnts) {
+ Node n = client.getNode(GetNodeRequest.newBuilder().setSwhid(fakeSWHID("cnt", cntId).toString()).build());
+ assertTrue(n.hasCnt());
+ assertTrue(n.getCnt().hasLength());
+ assertEquals((long) expectedLengths.get(cntId), n.getCnt().getLength());
+ assertTrue(n.getCnt().hasIsSkipped());
+ assertEquals(expectedSkipped.contains(cntId), n.getCnt().getIsSkipped());
+ }
+ }
+
+ @Test
+ public void testRevisions() {
+ List expectedRevs = List.of(3, 9, 13, 18);
+ Map expectedMessages = Map.of(3, "Initial commit", 9, "Add parser", 13, "Add tests", 18,
+ "Refactor codebase");
+
+ Map expectedAuthors = Map.of(3, "foo", 9, "bar", 13, "foo", 18, "baz");
+ Map expectedCommitters = Map.of(3, "foo", 9, "bar", 13, "bar", 18, "foo");
+
+ Map expectedAuthorTimestamps = Map.of(3, 1111122220L, 9, 1111144440L, 13, 1111166660L, 18,
+ 1111177770L);
+ Map expectedCommitterTimestamps = Map.of(3, 1111122220L, 9, 1111155550L, 13, 1111166660L, 18,
+ 1111177770L);
+ Map expectedAuthorTimestampOffsets = Map.of(3, 120, 9, 120, 13, 120, 18, 0);
+ Map expectedCommitterTimestampOffsets = Map.of(3, 120, 9, 120, 13, 120, 18, 0);
+
+ HashMap personMapping = new HashMap<>();
+ for (Integer revId : expectedRevs) {
+ Node n = client.getNode(GetNodeRequest.newBuilder().setSwhid(fakeSWHID("rev", revId).toString()).build());
+ assertTrue(n.hasRev());
+ assertTrue(n.getRev().hasMessage());
+ assertEquals(expectedMessages.get(revId), n.getRev().getMessage().toStringUtf8());
+
+ // Persons are anonymized, we just need to check that the mapping is self-consistent
+ assertTrue(n.getRev().hasAuthor());
+ assertTrue(n.getRev().hasCommitter());
+ int[] actualPersons = new int[]{(int) n.getRev().getAuthor(), (int) n.getRev().getCommitter()};
+ String[] expectedPersons = new String[]{expectedAuthors.get(revId), expectedCommitters.get(revId)};
+ for (int i = 0; i < actualPersons.length; i++) {
+ int actualPerson = actualPersons[i];
+ String expectedPerson = expectedPersons[i];
+ assertTrue(actualPerson >= 0);
+ if (personMapping.containsKey(actualPerson)) {
+ assertEquals(personMapping.get(actualPerson), expectedPerson);
+ } else {
+ personMapping.put(actualPerson, expectedPerson);
+ }
+ }
+
+ assertTrue(n.getRev().hasAuthorDate());
+ assertTrue(n.getRev().hasAuthorDateOffset());
+ assertTrue(n.getRev().hasCommitterDate());
+ assertTrue(n.getRev().hasCommitterDateOffset());
+
+ // FIXME: all the timestamps are one hour off?!
+ // System.err.println(revId + " " + n.getRev().getAuthorDate() + " " +
+ // n.getRev().getAuthorDateOffset());
+ // System.err.println(revId + " " + n.getRev().getCommitterDate() + " " +
+ // n.getRev().getCommitterDateOffset());
+
+ // assertEquals(expectedAuthorTimestamps.get(revId), n.getRev().getAuthorDate());
+ assertEquals(expectedAuthorTimestampOffsets.get(revId), n.getRev().getAuthorDateOffset());
+ // assertEquals(expectedCommitterTimestamps.get(revId), n.getRev().getAuthorDate());
+ assertEquals(expectedCommitterTimestampOffsets.get(revId), n.getRev().getAuthorDateOffset());
+ }
+ }
+
+ @Test
+ public void testReleases() {
+ List expectedRels = List.of(10, 19);
+ Map expectedMessages = Map.of(10, "Version 1.0", 19, "Version 2.0");
+ Map expectedNames = Map.of(10, "v1.0", 19, "v2.0");
+
+ Map expectedAuthors = Map.of(10, "foo", 19, "bar");
+
+ Map expectedAuthorTimestamps = Map.of(10, 1234567890L);
+ Map expectedAuthorTimestampOffsets = Map.of(3, 120);
+
+ HashMap personMapping = new HashMap<>();
+ for (Integer relId : expectedRels) {
+ Node n = client.getNode(GetNodeRequest.newBuilder().setSwhid(fakeSWHID("rel", relId).toString()).build());
+ assertTrue(n.hasRel());
+ assertTrue(n.getRel().hasMessage());
+ assertEquals(expectedMessages.get(relId), n.getRel().getMessage().toStringUtf8());
+ // FIXME: names are always empty?!
+ // System.err.println(relId + " " + n.getRel().getName());
+ // assertEquals(expectedNames.get(relId), n.getRel().getName().toStringUtf8());
+
+ // Persons are anonymized, we just need to check that the mapping is self-consistent
+ assertTrue(n.getRel().hasAuthor());
+ int actualPerson = (int) n.getRel().getAuthor();
+ String expectedPerson = expectedAuthors.get(relId);
+ assertTrue(actualPerson >= 0);
+ if (personMapping.containsKey(actualPerson)) {
+ assertEquals(personMapping.get(actualPerson), expectedPerson);
+ } else {
+ personMapping.put(actualPerson, expectedPerson);
+ }
+
+ assertTrue(n.getRel().hasAuthorDate());
+ assertTrue(n.getRel().hasAuthorDateOffset());
+
+ // FIXME: all the timestamps are one hour off?!
+ // if (expectedAuthorTimestamps.containsKey(relId)) {
+ // assertEquals(expectedAuthorTimestamps.get(revId), n.getRev().getAuthorDate());
+ // }
+ if (expectedAuthorTimestampOffsets.containsKey(relId)) {
+ assertEquals(expectedAuthorTimestampOffsets.get(relId), n.getRev().getAuthorDateOffset());
+ }
+ }
+ }
+
+ @Test
+ public void testOrigins() {
+ List expectedOris = List.of(new SWHID(TEST_ORIGIN_ID));
+ Map expectedUrls = Map.of(new SWHID(TEST_ORIGIN_ID), "https://example.com/swh/graph");
+
+ for (SWHID oriSwhid : expectedOris) {
+ Node n = client.getNode(GetNodeRequest.newBuilder().setSwhid(oriSwhid.toString()).build());
+ assertTrue(n.hasOri());
+ assertTrue(n.getOri().hasUrl());
+ assertEquals(expectedUrls.get(oriSwhid), n.getOri().getUrl());
+ }
+ }
+
+ @Test
+ public void testCntMask() {
+ Node n;
+ String swhid = fakeSWHID("cnt", 1).toString();
+
+ // No mask, all fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).build());
+ assertTrue(n.hasCnt());
+ assertTrue(n.getCnt().hasLength());
+ assertEquals(42, n.getCnt().getLength());
+ assertTrue(n.getCnt().hasIsSkipped());
+ assertFalse(n.getCnt().getIsSkipped());
+
+ // Empty mask, no fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).setMask(FieldMask.getDefaultInstance()).build());
+ assertFalse(n.getCnt().hasLength());
+ assertFalse(n.getCnt().hasIsSkipped());
+
+ // Mask with length, no isSkipped
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid)
+ .setMask(FieldMask.newBuilder().addPaths("cnt.length").build()).build());
+ assertTrue(n.getCnt().hasLength());
+ assertFalse(n.getCnt().hasIsSkipped());
+
+ // Mask with isSkipped, no length
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid)
+ .setMask(FieldMask.newBuilder().addPaths("cnt.is_skipped").build()).build());
+ assertFalse(n.getCnt().hasLength());
+ assertTrue(n.getCnt().hasIsSkipped());
+ }
+
+ @Test
+ public void testRevMask() {
+ Node n;
+ String swhid = fakeSWHID("rev", 3).toString();
+
+ // No mask, all fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).build());
+ assertTrue(n.hasRev());
+ assertTrue(n.getRev().hasMessage());
+ assertTrue(n.getRev().hasAuthor());
+ assertTrue(n.getRev().hasAuthorDate());
+ assertTrue(n.getRev().hasAuthorDateOffset());
+ assertTrue(n.getRev().hasCommitter());
+ assertTrue(n.getRev().hasCommitterDate());
+ assertTrue(n.getRev().hasCommitterDateOffset());
+
+ // Empty mask, no fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).setMask(FieldMask.getDefaultInstance()).build());
+ assertFalse(n.getRev().hasMessage());
+ assertFalse(n.getRev().hasAuthor());
+ assertFalse(n.getRev().hasAuthorDate());
+ assertFalse(n.getRev().hasAuthorDateOffset());
+ assertFalse(n.getRev().hasCommitter());
+ assertFalse(n.getRev().hasCommitterDate());
+ assertFalse(n.getRev().hasCommitterDateOffset());
+
+ // Test all masks with single fields
+ for (Descriptors.FieldDescriptor includedField : RevisionData.getDefaultInstance().getAllFields().keySet()) {
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid)
+ .setMask(FieldMask.newBuilder().addPaths("rev." + includedField.getName()).build()).build());
+ for (Descriptors.FieldDescriptor f : n.getRev().getDescriptorForType().getFields()) {
+ assertEquals(n.getRev().hasField(f), f.getName().equals(includedField.getName()));
+ }
+ }
+ }
+
+ @Test
+ public void testRelMask() {
+ Node n;
+ String swhid = fakeSWHID("rel", 19).toString();
+
+ // No mask, all fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).build());
+ assertTrue(n.hasRel());
+ assertTrue(n.getRel().hasMessage());
+ assertTrue(n.getRel().hasAuthor());
+ assertTrue(n.getRel().hasAuthorDate());
+ assertTrue(n.getRel().hasAuthorDateOffset());
+
+ // Empty mask, no fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).setMask(FieldMask.getDefaultInstance()).build());
+ assertFalse(n.getRel().hasMessage());
+ assertFalse(n.getRel().hasAuthor());
+ assertFalse(n.getRel().hasAuthorDate());
+ assertFalse(n.getRel().hasAuthorDateOffset());
+
+ // Test all masks with single fields
+ for (Descriptors.FieldDescriptor includedField : ReleaseData.getDefaultInstance().getAllFields().keySet()) {
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid)
+ .setMask(FieldMask.newBuilder().addPaths("rel." + includedField.getName()).build()).build());
+ for (Descriptors.FieldDescriptor f : n.getRel().getDescriptorForType().getFields()) {
+ assertEquals(n.getRel().hasField(f), f.getName().equals(includedField.getName()));
+ }
+ }
+ }
+
+ @Test
+ public void testOriMask() {
+ Node n;
+ String swhid = TEST_ORIGIN_ID;
+
+ // No mask, all fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).build());
+ assertTrue(n.hasOri());
+ assertTrue(n.getOri().hasUrl());
+
+ // Empty mask, no fields present
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid).setMask(FieldMask.getDefaultInstance()).build());
+ assertFalse(n.getOri().hasUrl());
+
+ // Test all masks with single fields
+ for (Descriptors.FieldDescriptor includedField : OriginData.getDefaultInstance().getAllFields().keySet()) {
+ n = client.getNode(GetNodeRequest.newBuilder().setSwhid(swhid)
+ .setMask(FieldMask.newBuilder().addPaths("ori." + includedField.getName()).build()).build());
+ for (Descriptors.FieldDescriptor f : n.getOri().getDescriptorForType().getFields()) {
+ assertEquals(n.getOri().hasField(f), f.getName().equals(includedField.getName()));
+ }
+ }
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/StatsTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/StatsTest.java
new file mode 100644
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/StatsTest.java
@@ -0,0 +1,18 @@
+package org.softwareheritage.graph.rpc;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class StatsTest extends TraversalServiceTest {
+ @Test
+ public void testStats() {
+ StatsResponse stats = client.stats(StatsRequest.getDefaultInstance());
+ assertEquals(stats.getNumNodes(), 21);
+ assertEquals(stats.getNumEdges(), 23);
+ assertEquals(stats.getIndegreeMin(), 0);
+ assertEquals(stats.getIndegreeMax(), 3);
+ assertEquals(stats.getOutdegreeMin(), 0);
+ assertEquals(stats.getOutdegreeMax(), 3);
+ }
+}
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
--- /dev/null
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraversalServiceTest.java
@@ -0,0 +1,58 @@
+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 org.softwareheritage.graph.SwhBidirectionalGraph;
+
+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 SwhBidirectionalGraph g;
+ protected static TraversalServiceGrpc.TraversalServiceBlockingStub client;
+
+ @BeforeAll
+ static void setup() throws Exception {
+ String serverName = InProcessServerBuilder.generateName();
+ g = GraphServer.loadGraph(getGraphPath().toString());
+ server = InProcessServerBuilder.forName(serverName).directExecutor()
+ .addService(new GraphServer.TraversalService(g.copy())).build().start();
+ channel = InProcessChannelBuilder.forName(serverName).directExecutor().build();
+ client = TraversalServiceGrpc.newBlockingStub(channel);
+ }
+
+ @AfterAll
+ static void teardown() {
+ channel.shutdownNow();
+ server.shutdownNow();
+ }
+
+ public ArrayList getSWHIDs(Iterator it) {
+ ArrayList res = new ArrayList<>();
+ it.forEachRemaining((Node n) -> {
+ res.add(new SWHID(n.getSwhid()));
+ });
+ return res;
+ }
+
+ public ArrayList getSWHIDs(Path p) {
+ ArrayList res = new ArrayList<>();
+ p.getNodeList().forEach((Node n) -> {
+ res.add(new SWHID(n.getSwhid()));
+ });
+ return res;
+ }
+}
diff --git a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
rename from java/src/test/java/org/softwareheritage/graph/LeavesTest.java
rename to java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/LeavesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
@@ -1,18 +1,20 @@
-package org.softwareheritage.graph;
+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 org.junit.jupiter.api.Test;
-import org.softwareheritage.graph.server.Endpoint;
+public class TraverseLeavesTest extends TraversalServiceTest {
+ private TraversalRequest.Builder getLeavesRequestBuilder(SWHID src) {
+ return TraversalRequest.newBuilder().addSrc(src.toString())
+ .setReturnNodes(NodeFilter.newBuilder().setMaxTraversalSuccessors(0).build());
+ }
-// Avoid warnings concerning Endpoint.Output.result manual cast
-@SuppressWarnings("unchecked")
-public class LeavesTest extends GraphTest {
@Test
public void forwardFromSnp() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:snp:0000000000000000000000000000000000000020");
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
+ TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("snp", 20)).build();
ArrayList expectedLeaves = new ArrayList<>();
expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"));
@@ -20,16 +22,14 @@
expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005"));
expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"));
- ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result;
+ ArrayList actualLeaves = getSWHIDs(client.traverse(request));
GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
}
@Test
public void forwardFromRel() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:rel:0000000000000000000000000000000000000019");
- Endpoint endpoint = new Endpoint(graph, "forward", "*");
-
+ 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"));
@@ -39,69 +39,55 @@
expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"));
expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000011"));
- ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result;
GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
}
@Test
public void backwardFromLeaf() {
- SwhBidirectionalGraph graph = getGraph();
-
- Endpoint endpoint1 = new Endpoint(graph, "backward", "*");
- SWHID src1 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000015");
+ 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"));
- ArrayList actualLeaves1 = (ArrayList) endpoint1.leaves(new Endpoint.Input(src1)).result;
GraphTest.assertEqualsAnyOrder(expectedLeaves1, actualLeaves1);
- Endpoint endpoint2 = new Endpoint(graph, "backward", "*");
- SWHID src2 = new SWHID("swh:1:cnt:0000000000000000000000000000000000000004");
+ 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"));
- ArrayList actualLeaves2 = (ArrayList) endpoint2.leaves(new Endpoint.Input(src2)).result;
GraphTest.assertEqualsAnyOrder(expectedLeaves2, actualLeaves2);
}
@Test
public void forwardRevToRevOnly() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:rev:0000000000000000000000000000000000000018");
- Endpoint endpoint = new Endpoint(graph, "forward", "rev:rev");
-
+ 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"));
-
- ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result;
GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
}
@Test
public void forwardDirToAll() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:dir:0000000000000000000000000000000000000008");
- Endpoint endpoint = new Endpoint(graph, "forward", "dir:*");
-
+ 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"));
-
- ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result;
GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
}
@Test
public void backwardCntToDirDirToDir() {
- SwhBidirectionalGraph graph = getGraph();
- SWHID src = new SWHID("swh:1:cnt:0000000000000000000000000000000000000005");
- Endpoint endpoint = new Endpoint(graph, "backward", "cnt:dir,dir:dir");
-
+ 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"));
-
- ArrayList actualLeaves = (ArrayList) endpoint.leaves(new Endpoint.Input(src)).result;
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
--- /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