clusterlin: add DepGraph::RemoveTransactions and support for holes in DepGraph

This commits introduces support in DepGraph for the transaction positions to be
non-continuous. Specifically, it adds:
* DepGraph::RemoveTransactions which removes 0 or more positions from a DepGraph.
* DepGraph::Positions() to get a set of which positions are in use.
* DepGraph::PositionRange() to get the highest used position in a DepGraph + 1.

In addition, it extends the DepGraphFormatter format to support holes in a
compatible way (it serializes non-holey DepGraphs identically to the old code,
and deserializes them the same way)

4 files changed, 164 insertions, 52 deletions

diff --git a/src/test/cluster_linearize_tests.cpp b/src/test/cluster_linearize_tests.cpp
index d15e783ea1..cb87dcbffb 100644
--- a/src/test/cluster_linearize_tests.cpp
+++ b/src/test/cluster_linearize_tests.cpp
@@ -18,6 +18,10 @@ using namespace cluster_linearize;
 
 namespace {
 
+/** Special magic value that indicates to TestDepGraphSerialization that a cluster entry represents
+ *  a hole. */
+constexpr std::pair<FeeFrac, TestBitSet> HOLE{FeeFrac{0, 0x3FFFFF}, {}};
+
 template<typename SetType>
 void TestDepGraphSerialization(const Cluster<SetType>& cluster, const std::string& hexenc)
 {
@@ -26,6 +30,13 @@ void TestDepGraphSerialization(const Cluster<SetType>& cluster, const std::strin
     // Run normal sanity and correspondence checks, which includes a round-trip test.
     VerifyDepGraphFromCluster(cluster, depgraph);
 
+    // Remove holes (which are expected to be present as HOLE entries in cluster).
+    SetType holes;
+    for (ClusterIndex i = 0; i < cluster.size(); ++i) {
+        if (cluster[i] == HOLE) holes.Set(i);
+    }
+    depgraph.RemoveTransactions(holes);
+
     // There may be multiple serializations of the same graph, but DepGraphFormatter's serializer
     // only produces one of those. Verify that hexenc matches that canonical serialization.
     std::vector<unsigned char> encoding;
@@ -133,6 +144,34 @@ BOOST_AUTO_TEST_CASE(depgraph_ser_tests)
                 skip insertion C): D,A,B,E,C */
         "00" /* end of graph */
     );
+
+    // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D.
+    // In order: [_, D, _, _, A, _, B, _, _, _, E, _, _, C] (_ being holes). Internally serialized
+    // in order A,B,C,D,E.
+    TestDepGraphSerialization<TestBitSet>(
+        {HOLE, {{1, 3}, {4, 6}}, HOLE, HOLE, {{1, 2}, {}}, HOLE, {{3, 1}, {}}, HOLE, HOLE, HOLE, {{1, 1}, {1}}, HOLE, HOLE, {{2, 1}, {4}}},
+        "02" /* A size */
+        "02" /* A fee */
+        "03" /* A insertion position (3 holes): _, _, _, A */
+        "01" /* B size */
+        "06" /* B fee */
+        "06" /* B insertion position (skip B->A dependency, skip 4 inserts, add 1 hole): _, _, _, A, _, B */
+        "01" /* C size */
+        "04" /* C fee */
+        "01" /* C->A dependency (skip C->B dependency) */
+        "0b" /* C insertion position (skip 6 inserts, add 5 holes): _, _, _, A, _, B, _, _, _, _, _, C */
+        "03" /* D size */
+        "02" /* D fee */
+        "01" /* D->B dependency (skip D->C dependency) */
+        "00" /* D->A dependency (no skips) */
+        "0b" /* D insertion position (skip 11 inserts): _, D, _, _, A, _, B, _, _, _, _, _, C */
+        "01" /* E size */
+        "02" /* E fee */
+        "00" /* E->D dependency (no skips) */
+        "04" /* E insertion position (skip E->C dependency, E->B and E->A are implied, skip 3
+                inserts): _, D, _, _, A, _, B, _, _, _, E, _, _, C */
+        "00" /* end of graph */
+    );
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/feefrac_tests.cpp b/src/test/feefrac_tests.cpp
index 5af3c3d7ed..41c9c0a633 100644
--- a/src/test/feefrac_tests.cpp
+++ b/src/test/feefrac_tests.cpp
@@ -15,7 +15,7 @@ BOOST_AUTO_TEST_CASE(feefrac_operators)
     FeeFrac sum{1500, 400};
     FeeFrac diff{500, -200};
     FeeFrac empty{0, 0};
-    FeeFrac zero_fee{0, 1}; // zero-fee allowed
+    [[maybe_unused]] FeeFrac zero_fee{0, 1}; // zero-fee allowed
 
     BOOST_CHECK(empty == FeeFrac{}); // same as no-args
 
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index bf7db4482c..e75883878e 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -37,7 +37,7 @@ class SimpleCandidateFinder
 public:
     /** Construct an SimpleCandidateFinder for a given graph. */
     SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
-        m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {}
+        m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
 
     /** Remove a set of transactions from the set of to-be-linearized ones. */
     void MarkDone(SetType select) noexcept { m_todo -= select; }
@@ -107,7 +107,7 @@ class ExhaustiveCandidateFinder
 public:
     /** Construct an ExhaustiveCandidateFinder for a given graph. */
     ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
-        m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {}
+        m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
 
     /** Remove a set of transactions from the set of to-be-linearized ones. */
     void MarkDone(SetType select) noexcept { m_todo -= select; }
@@ -153,7 +153,7 @@ std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetTyp
 {
     std::vector<ClusterIndex> linearization;
     SimpleCandidateFinder finder(depgraph);
-    SetType todo = SetType::Fill(depgraph.TxCount());
+    SetType todo = depgraph.Positions();
     bool optimal = true;
     while (todo.Any()) {
         auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
@@ -170,7 +170,7 @@ std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetTyp
 template<typename BS>
 void MakeConnected(DepGraph<BS>& depgraph)
 {
-    auto todo = BS::Fill(depgraph.TxCount());
+    auto todo = depgraph.Positions();
     auto comp = depgraph.FindConnectedComponent(todo);
     Assume(depgraph.IsConnected(comp));
     todo -= comp;
@@ -206,7 +206,7 @@ template<typename BS>
 std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
 {
     std::vector<ClusterIndex> linearization;
-    TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
+    TestBitSet todo = depgraph.Positions();
     // In every iteration one topologically-valid transaction is appended to linearization.
     while (todo.Any()) {
         // Compute the set of transactions with no not-yet-included ancestors.
@@ -327,6 +327,17 @@ FUZZ_TARGET(clusterlin_cluster_serialization)
     // check for the serialization).
     DepGraph depgraph(cluster);
     VerifyDepGraphFromCluster(cluster, depgraph);
+
+    // Remove an arbitrary subset (in order to construct a graph with holes) and verify that it
+    // still sanity checks (incl. round-tripping serialization).
+    uint64_t del = provider.ConsumeIntegralInRange<uint64_t>(1, (uint64_t{1} << TestBitSet::Size()) - 1);
+    TestBitSet setdel;
+    for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) {
+        if (del & 1) setdel.Set(i);
+        del >>= 1;
+    }
+    depgraph.RemoveTransactions(setdel);
+    SanityCheck(depgraph);
 }
 
 FUZZ_TARGET(clusterlin_depgraph_serialization)
@@ -356,7 +367,7 @@ FUZZ_TARGET(clusterlin_components)
         reader >> Using<DepGraphFormatter>(depgraph);
     } catch (const std::ios_base::failure&) {}
 
-    TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
+    TestBitSet todo = depgraph.Positions();
     while (todo.Any()) {
         // Find a connected component inside todo.
         auto component = depgraph.FindConnectedComponent(todo);
@@ -367,7 +378,7 @@ FUZZ_TARGET(clusterlin_components)
 
         // If todo is the entire graph, and the entire graph is connected, then the component must
         // be the entire graph.
-        if (todo == TestBitSet::Fill(depgraph.TxCount())) {
+        if (todo == depgraph.Positions()) {
             assert((component == todo) == depgraph.IsConnected());
         }
 
@@ -404,7 +415,7 @@ FUZZ_TARGET(clusterlin_components)
             reader >> VARINT(subset_bits);
         } catch (const std::ios_base::failure&) {}
         TestBitSet subset;
-        for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
+        for (ClusterIndex i : depgraph.Positions()) {
             if (todo[i]) {
                 if (subset_bits & 1) subset.Set(i);
                 subset_bits >>= 1;
@@ -457,7 +468,7 @@ FUZZ_TARGET(clusterlin_chunking)
     }
 
     // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
-    auto todo = TestBitSet::Fill(depgraph.TxCount());
+    auto todo = depgraph.Positions();
     for (const auto& chunk_feerate : chunking) {
         assert(todo.Any());
         SetInfo<TestBitSet> accumulator, best;
@@ -488,7 +499,7 @@ FUZZ_TARGET(clusterlin_ancestor_finder)
     } catch (const std::ios_base::failure&) {}
 
     AncestorCandidateFinder anc_finder(depgraph);
-    auto todo = TestBitSet::Fill(depgraph.TxCount());
+    auto todo = depgraph.Positions();
     while (todo.Any()) {
         // Call the ancestor finder's FindCandidateSet for what remains of the graph.
         assert(!anc_finder.AllDone());
@@ -553,7 +564,7 @@ FUZZ_TARGET(clusterlin_search_finder)
     ExhaustiveCandidateFinder exh_finder(depgraph);
     AncestorCandidateFinder anc_finder(depgraph);
 
-    auto todo = TestBitSet::Fill(depgraph.TxCount());
+    auto todo = depgraph.Positions();
     while (todo.Any()) {
         assert(!src_finder.AllDone());
         assert(!smp_finder.AllDone());
@@ -657,7 +668,7 @@ FUZZ_TARGET(clusterlin_linearization_chunking)
     } catch (const std::ios_base::failure&) {}
 
     // Retrieve a topologically-valid subset of depgraph.
-    auto todo = TestBitSet::Fill(depgraph.TxCount());
+    auto todo = depgraph.Positions();
     auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
 
     // Retrieve a valid linearization for depgraph.
@@ -840,8 +851,8 @@ FUZZ_TARGET(clusterlin_linearize)
 
         // Only for very small clusters, test every topologically-valid permutation.
         if (depgraph.TxCount() <= 7) {
-            std::vector<ClusterIndex> perm_linearization(depgraph.TxCount());
-            for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) perm_linearization[i] = i;
+            std::vector<ClusterIndex> perm_linearization;
+            for (ClusterIndex i : depgraph.Positions()) perm_linearization.push_back(i);
             // Iterate over all valid permutations.
             do {
                 // Determine whether perm_linearization is topological.
@@ -925,9 +936,17 @@ FUZZ_TARGET(clusterlin_postlinearize_tree)
     // Now construct a new graph, copying the nodes, but leaving only the first parent (even
     // direction) or the first child (odd direction).
     DepGraph<TestBitSet> depgraph_tree;
-    for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
-        depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
+    for (ClusterIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
+        if (depgraph_gen.Positions()[i]) {
+            depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
+        } else {
+            // For holes, add a dummy transaction which is deleted below, so that non-hole
+            // transactions retain their position.
+            depgraph_tree.AddTransaction(FeeFrac{});
+        }
     }
+    depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
+
     if (direction & 1) {
         for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
             auto children = depgraph_gen.GetReducedChildren(i);
diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h
index bec4d41d38..44cd6590d3 100644
--- a/src/test/util/cluster_linearize.h
+++ b/src/test/util/cluster_linearize.h
@@ -27,7 +27,7 @@ using TestBitSet = BitSet<32>;
 template<typename SetType>
 bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept
 {
-    for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
+    for (ClusterIndex i : depgraph.Positions()) {
         if ((depgraph.Ancestors(i) & depgraph.Descendants(i)) != SetType::Singleton(i)) {
             return false;
         }
@@ -57,11 +57,14 @@ bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept
  *   by parent relations that were serialized before it).
  * - The various insertion positions in the cluster, from the very end of the cluster, to the
  *   front.
+ * - The appending of 1, 2, 3, ... holes at the end of the cluster, followed by appending the new
+ *   transaction.
  *
- * Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,G,E,D, but
- * serialized in order A,B,C,D,E,F,G, because that happens to be a topological ordering. By the
- * time G gets serialized, what has been serialized already represents the cluster F,A,C,B,E,D (in
- * that order). G has B and E as direct parents, and E depends on C.
+ * Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,_,G,E,_,D
+ * (where _ represent holes; unused positions within the DepGraph) but serialized in order
+ * A,B,C,D,E,F,G, because that happens to be a topological ordering. By the time G gets serialized,
+ * what has been serialized already represents the cluster F,A,C,B,_,E,_,D (in that order). G has B
+ * and E as direct parents, and E depends on C.
  *
  * In this case, the possibilities are, in order:
  * - [ ] the dependency G->F
@@ -71,17 +74,23 @@ bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept
  * - [ ] the dependency G->A
  * - [ ] put G at the end of the cluster
  * - [ ] put G before D
+ * - [ ] put G before the hole before D
  * - [X] put G before E
+ * - [ ] put G before the hole before E
  * - [ ] put G before B
  * - [ ] put G before C
  * - [ ] put G before A
  * - [ ] put G before F
+ * - [ ] add 1 hole at the end of the cluster, followed by G
+ * - [ ] add 2 holes at the end of the cluster, followed by G
+ * - [ ] add ...
  *
- * The skip values in this case are 1 (G->F), 1 (G->D), 3 (G->A, G at end, G before D). No skip
- * after 3 is needed (or permitted), because there can only be one position for G. Also note that
- * G->C is not included in the list of possibilities, as it is implied by the included G->E and
- * E->C that came before it. On deserialization, if the last skip value was 8 or larger (putting
- * G before the beginning of the cluster), it is interpreted as wrapping around back to the end.
+ * The skip values in this case are 1 (G->F), 1 (G->D), 4 (G->A, G at end, G before D, G before
+ * hole). No skip after 4 is needed (or permitted), because there can only be one position for G.
+ * Also note that G->C is not included in the list of possibilities, as it is implied by the
+ * included G->E and E->C that came before it. On deserialization, if the last skip value was 8 or
+ * larger (putting G before the beginning of the cluster), it is interpreted as wrapping around
+ * back to the end.
  *
  *
  * Rationale:
@@ -125,16 +134,17 @@ struct DepGraphFormatter
     static void Ser(Stream& s, const DepGraph<SetType>& depgraph)
     {
         /** Construct a topological order to serialize the transactions in. */
-        std::vector<ClusterIndex> topo_order(depgraph.TxCount());
-        std::iota(topo_order.begin(), topo_order.end(), ClusterIndex{0});
+        std::vector<ClusterIndex> topo_order;
+        topo_order.reserve(depgraph.TxCount());
+        for (auto i : depgraph.Positions()) topo_order.push_back(i);
         std::sort(topo_order.begin(), topo_order.end(), [&](ClusterIndex a, ClusterIndex b) {
             auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count();
             if (anc_a != anc_b) return anc_a < anc_b;
             return a < b;
         });
 
-        /** Which transactions the deserializer already knows when it has deserialized what has
-         *  been serialized here so far. */
+        /** Which positions (incl. holes) the deserializer already knows when it has deserialized
+         *  what has been serialized here so far. */
         SetType done;
 
         // Loop over the transactions in topological order.
@@ -165,10 +175,19 @@ struct DepGraphFormatter
                 }
             }
             // Write position information.
-            // The new transaction is to be inserted N positions back from the end of the cluster.
-            // Emit N to indicate that that many insertion choices are skipped.
-            auto skips = (done - SetType::Fill(idx)).Count();
-            s << VARINT(diff + skips);
+            auto add_holes = SetType::Fill(idx) - done - depgraph.Positions();
+            if (add_holes.None()) {
+                // The new transaction is to be inserted N positions back from the end of the
+                // cluster. Emit N to indicate that that many insertion choices are skipped.
+                auto skips = (done - SetType::Fill(idx)).Count();
+                s << VARINT(diff + skips);
+            } else {
+                // The new transaction is to be appended at the end of the cluster, after N holes.
+                // Emit current_cluster_size + N, to indicate all insertion choices are skipped,
+                // plus N possibilities for the number of holes.
+                s << VARINT(diff + done.Count() + add_holes.Count());
+                done |= add_holes;
+            }
             done.Set(idx);
         }
 
@@ -185,8 +204,7 @@ struct DepGraphFormatter
         /** Mapping from serialization order to cluster order, used later to reconstruct the
          *  cluster order. */
         std::vector<ClusterIndex> reordering;
-        /** How big the entries vector in the reconstructed depgraph will be (before the
-         *  introduction of holes in a further commit, this always equals reordering.size()). */
+        /** How big the entries vector in the reconstructed depgraph will be (including holes). */
         ClusterIndex total_size{0};
 
         // Read transactions in topological order.
@@ -235,18 +253,43 @@ struct DepGraphFormatter
             assert(reordering.size() < SetType::Size());
             auto topo_idx = topo_depgraph.AddTransaction(new_feerate);
             topo_depgraph.AddDependencies(new_ancestors, topo_idx);
-            diff %= total_size + 1;
-            // Insert the new transaction at distance diff back from the end.
-            for (auto& pos : reordering) {
-                pos += (pos >= total_size - diff);
+            if (total_size < SetType::Size()) {
+                // Normal case.
+                diff %= SetType::Size();
+                if (diff <= total_size) {
+                    // Insert the new transaction at distance diff back from the end.
+                    for (auto& pos : reordering) {
+                        pos += (pos >= total_size - diff);
+                    }
+                    reordering.push_back(total_size++ - diff);
+                } else {
+                    // Append diff - total_size holes at the end, plus the new transaction.
+                    total_size = diff;
+                    reordering.push_back(total_size++);
+                }
+            } else {
+                // In case total_size == SetType::Size, it is not possible to insert the new
+                // transaction without exceeding SetType's size. Instead, interpret diff as an
+                // index into the holes, and overwrite a position there. This branch is never used
+                // when deserializing the output of the serializer, but gives meaning to otherwise
+                // invalid input.
+                diff %= (SetType::Size() - reordering.size());
+                SetType holes = SetType::Fill(SetType::Size());
+                for (auto pos : reordering) holes.Reset(pos);
+                for (auto pos : holes) {
+                    if (diff == 0) {
+                        reordering.push_back(pos);
+                        break;
+                    }
+                    --diff;
+                }
             }
-            reordering.push_back(total_size++ - diff);
             // Stop if a read error was encountered during deserialization.
             if (read_error) break;
         }
 
         // Construct the original cluster order depgraph.
-        depgraph = DepGraph(topo_depgraph, reordering);
+        depgraph = DepGraph(topo_depgraph, reordering, total_size);
     }
 };
 
@@ -254,8 +297,19 @@ struct DepGraphFormatter
 template<typename SetType>
 void SanityCheck(const DepGraph<SetType>& depgraph)
 {
+    // Verify Positions and PositionRange consistency.
+    ClusterIndex num_positions{0};
+    ClusterIndex position_range{0};
+    for (ClusterIndex i : depgraph.Positions()) {
+        ++num_positions;
+        position_range = i + 1;
+    }
+    assert(num_positions == depgraph.TxCount());
+    assert(position_range == depgraph.PositionRange());
+    assert(position_range >= num_positions);
+    assert(position_range <= SetType::Size());
     // Consistency check between ancestors internally.
-    for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
+    for (ClusterIndex i : depgraph.Positions()) {
         // Transactions include themselves as ancestors.
         assert(depgraph.Ancestors(i)[i]);
         // If a is an ancestor of b, then b's ancestors must include all of a's ancestors.
@@ -264,8 +318,8 @@ void SanityCheck(const DepGraph<SetType>& depgraph)
         }
     }
     // Consistency check between ancestors and descendants.
-    for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
-        for (ClusterIndex j = 0; j < depgraph.TxCount(); ++j) {
+    for (ClusterIndex i : depgraph.Positions()) {
+        for (ClusterIndex j : depgraph.Positions()) {
             assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]);
         }
         // No transaction is a parent or child of itself.
@@ -305,12 +359,12 @@ void SanityCheck(const DepGraph<SetType>& depgraph)
 
         // In acyclic graphs, the union of parents with parents of parents etc. yields the
         // full ancestor set (and similar for children and descendants).
-        std::vector<SetType> parents, children;
-        for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
-            parents.push_back(depgraph.GetReducedParents(i));
-            children.push_back(depgraph.GetReducedChildren(i));
+        std::vector<SetType> parents(depgraph.PositionRange()), children(depgraph.PositionRange());
+        for (ClusterIndex i : depgraph.Positions()) {
+            parents[i] = depgraph.GetReducedParents(i);
+            children[i] = depgraph.GetReducedChildren(i);
         }
-        for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
+        for (auto i : depgraph.Positions()) {
             // Initialize the set of ancestors with just the current transaction itself.
             SetType ancestors = SetType::Singleton(i);
             // Iteratively add parents of all transactions in the ancestor set to itself.
@@ -382,7 +436,7 @@ void SanityCheck(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> lin
     TestBitSet done;
     for (auto i : linearization) {
         // Check transaction position is in range.
-        assert(i < depgraph.TxCount());
+        assert(depgraph.Positions()[i]);
         // Check topology and lack of duplicates.
         assert((depgraph.Ancestors(i) - done) == TestBitSet::Singleton(i));
         done.Set(i);