TxGraph::Trim() builds a rudimentary linearization of the would-be cluster to decide which transactions to remove. For the dependencies inside each involved cluster, it did not use the real ones: it added an implicit dependency between each pair of consecutive transactions in that cluster's linearization. This makes transactions look dependent when they are not, which can merge partitions unnecessarily and cause Trim() to remove more transactions than needed (see #36656).
This PR makes GenericClusterImpl::AppendTrimData() emit the cluster's actual dependencies (only the reduced parents, since the rest follow by transitivity) instead of the implicit chain. As a result, several transactions from the same cluster can be in the heap at the same time. Topological order is still respected, because a transaction only becomes eligible once all of its dependencies are met. The related comments in Trim() and in the fuzz test were updated.
Tests:
- New unit tests
txgraph_trim_no_cascadeandtxgraph_trim_no_overcountin src/test/txgraph_tests.cpp, based on the existing zigzag/flower Trim tests. - The existing
txgraphfuzz target exercises Trim() and checks its invariants.
As noted by instagibbs in the issue, this is low priority since Trim() only runs during reorgs. I have not yet built or run the tests locally, so I'm opening this as a draft to let CI run.
Fixes #36656.