clusterlin: add MergeLinearizations function + fuzz test + benchmark

1 files changed, 26 insertions, 0 deletions

diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index 2412db5c1b..2dfdfbb41d 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -929,3 +929,29 @@ FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
     auto cmp = CompareChunks(new_chunking, old_chunking);
     assert(cmp >= 0);
 }
+
+FUZZ_TARGET(clusterlin_merge)
+{
+    // Construct an arbitrary graph from the fuzz input.
+    SpanReader reader(buffer);
+    DepGraph<TestBitSet> depgraph;
+    try {
+        reader >> Using<DepGraphFormatter>(depgraph);
+    } catch (const std::ios_base::failure&) {}
+
+    // Retrieve two linearizations from the fuzz input.
+    auto lin1 = ReadLinearization(depgraph, reader);
+    auto lin2 = ReadLinearization(depgraph, reader);
+
+    // Merge the two.
+    auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
+
+    // Compute chunkings and compare.
+    auto chunking1 = ChunkLinearization(depgraph, lin1);
+    auto chunking2 = ChunkLinearization(depgraph, lin2);
+    auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
+    auto cmp1 = CompareChunks(chunking_merged, chunking1);
+    assert(cmp1 >= 0);
+    auto cmp2 = CompareChunks(chunking_merged, chunking2);
+    assert(cmp2 >= 0);
+}