diff options
| -rw-r--r-- | src/cluster_linearize.h | 42 | ||||
| -rw-r--r-- | src/test/fuzz/cluster_linearize.cpp | 16 | ||||
| -rw-r--r-- | src/test/util/cluster_linearize.h | 47 |
3 files changed, 90 insertions, 15 deletions
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h index e964849f22..8467f3f08b 100644 --- a/src/cluster_linearize.h +++ b/src/cluster_linearize.h @@ -184,6 +184,48 @@ public: } } + /** Compute the (reduced) set of parents of node i in this graph. + * + * This returns the minimal subset of the parents of i whose ancestors together equal all of + * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not + * store the set of parents; this information is inferred from the ancestor sets. + * + * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()). + */ + SetType GetReducedParents(ClusterIndex i) const noexcept + { + SetType parents = Ancestors(i); + parents.Reset(i); + for (auto parent : parents) { + if (parents[parent]) { + parents -= Ancestors(parent); + parents.Set(parent); + } + } + return parents; + } + + /** Compute the (reduced) set of children of node i in this graph. + * + * This returns the minimal subset of the children of i whose descendants together equal all of + * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not + * store the set of children; this information is inferred from the descendant sets. + * + * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()). + */ + SetType GetReducedChildren(ClusterIndex i) const noexcept + { + SetType children = Descendants(i); + children.Reset(i); + for (auto child : children) { + if (children[child]) { + children -= Descendants(child); + children.Set(child); + } + } + return children; + } + /** Compute the aggregate feerate of a set of nodes in this graph. * * Complexity: O(N) where N=elems.Count(). diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp index d91f85d867..4976afbaad 100644 --- a/src/test/fuzz/cluster_linearize.cpp +++ b/src/test/fuzz/cluster_linearize.cpp @@ -896,24 +896,12 @@ FUZZ_TARGET(clusterlin_postlinearize_tree) } if (direction & 1) { for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { - auto children = depgraph_gen.Descendants(i) - TestBitSet::Singleton(i); - // Remove descendants that are children of other descendants. - for (auto j : children) { - if (!children[j]) continue; - children -= depgraph_gen.Descendants(j); - children.Set(j); - } + auto children = depgraph_gen.GetReducedChildren(i); if (children.Any()) depgraph_tree.AddDependency(i, children.First()); } } else { for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { - auto parents = depgraph_gen.Ancestors(i) - TestBitSet::Singleton(i); - // Remove ancestors that are parents of other ancestors. - for (auto j : parents) { - if (!parents[j]) continue; - parents -= depgraph_gen.Ancestors(j); - parents.Set(j); - } + auto parents = depgraph_gen.GetReducedParents(i); if (parents.Any()) depgraph_tree.AddDependency(parents.First(), i); } } diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h index b86ebcd78b..377bfa19fb 100644 --- a/src/test/util/cluster_linearize.h +++ b/src/test/util/cluster_linearize.h @@ -264,9 +264,23 @@ void SanityCheck(const DepGraph<SetType>& depgraph) for (ClusterIndex j = 0; j < depgraph.TxCount(); ++j) { assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]); } + // No transaction is a parent or child of itself. + auto parents = depgraph.GetReducedParents(i); + auto children = depgraph.GetReducedChildren(i); + assert(!parents[i]); + assert(!children[i]); + // Parents of a transaction do not have ancestors inside those parents (except itself). + // Note that even the transaction itself may be missing (if it is part of a cycle). + for (auto parent : parents) { + assert((depgraph.Ancestors(parent) & parents).IsSubsetOf(SetType::Singleton(parent))); + } + // Similar for children and descendants. + for (auto child : children) { + assert((depgraph.Descendants(child) & children).IsSubsetOf(SetType::Singleton(child))); + } } - // If DepGraph is acyclic, serialize + deserialize must roundtrip. if (IsAcyclic(depgraph)) { + // If DepGraph is acyclic, serialize + deserialize must roundtrip. std::vector<unsigned char> ser; VectorWriter writer(ser, 0); writer << Using<DepGraphFormatter>(depgraph); @@ -284,6 +298,37 @@ void SanityCheck(const DepGraph<SetType>& depgraph) reader >> Using<DepGraphFormatter>(decoded_depgraph); assert(depgraph == decoded_depgraph); assert(reader.empty()); + + // 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)); + } + for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + // 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. + while (true) { + const auto old_ancestors = ancestors; + for (auto j : ancestors) ancestors |= parents[j]; + // Stop when no more changes are being made. + if (old_ancestors == ancestors) break; + } + assert(ancestors == depgraph.Ancestors(i)); + + // Initialize the set of descendants with just the current transaction itself. + SetType descendants = SetType::Singleton(i); + // Iteratively add children of all transactions in the descendant set to itself. + while (true) { + const auto old_descendants = descendants; + for (auto j : descendants) descendants |= children[j]; + // Stop when no more changes are being made. + if (old_descendants == descendants) break; + } + assert(descendants == depgraph.Descendants(i)); + } } } |