LCOV - code coverage report
Current view: top level - src/test/fuzz - txgraph.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 99.5 % 662 659
Test Date: 2025-08-01 04:15:35 Functions: 96.0 % 25 24
Branches: 77.4 % 786 608

             Branch data     Line data    Source code
       1                 :             : // Copyright (c) The Bitcoin Core developers
       2                 :             : // Distributed under the MIT software license, see the accompanying
       3                 :             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :             : 
       5                 :             : #include <cluster_linearize.h>
       6                 :             : #include <test/fuzz/FuzzedDataProvider.h>
       7                 :             : #include <test/fuzz/fuzz.h>
       8                 :             : #include <test/util/cluster_linearize.h>
       9                 :             : #include <test/util/random.h>
      10                 :             : #include <txgraph.h>
      11                 :             : #include <util/bitset.h>
      12                 :             : #include <util/feefrac.h>
      13                 :             : 
      14                 :             : #include <algorithm>
      15                 :             : #include <cstdint>
      16                 :             : #include <iterator>
      17                 :             : #include <map>
      18                 :             : #include <memory>
      19                 :             : #include <set>
      20                 :             : #include <utility>
      21                 :             : 
      22                 :             : using namespace cluster_linearize;
      23                 :             : 
      24                 :             : namespace {
      25                 :             : 
      26                 :             : /** Data type representing a naive simulated TxGraph, keeping all transactions (even from
      27                 :             :  *  disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models
      28                 :             :  *  a single graph, and multiple instances are used to simulate main/staging. */
      29                 :             : struct SimTxGraph
      30                 :             : {
      31                 :             :     /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's
      32                 :             :      *  cluster count, so we can exercise situations with more transactions than fit in one
      33                 :             :      *  cluster. */
      34                 :             :     static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2;
      35                 :             :     /** Set type to use in the simulation. */
      36                 :             :     using SetType = BitSet<MAX_TRANSACTIONS>;
      37                 :             :     /** Data type for representing positions within SimTxGraph::graph. */
      38                 :             :     using Pos = DepGraphIndex;
      39                 :             :     /** Constant to mean "missing in this graph". */
      40                 :             :     static constexpr auto MISSING = Pos(-1);
      41                 :             : 
      42                 :             :     /** The dependency graph (for all transactions in the simulation, regardless of
      43                 :             :      *  connectivity/clustering). */
      44                 :             :     DepGraph<SetType> graph;
      45                 :             :     /** For each position in graph, which TxGraph::Ref it corresponds with (if any). Use shared_ptr
      46                 :             :      *  so that a SimTxGraph can be copied to create a staging one, while sharing Refs with
      47                 :             :      *  the main graph. */
      48                 :             :     std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
      49                 :             :     /** For each TxGraph::Ref in graph, the position it corresponds with. */
      50                 :             :     std::map<const TxGraph::Ref*, Pos> simrevmap;
      51                 :             :     /** The set of TxGraph::Ref entries that have been removed, but not yet destroyed. */
      52                 :             :     std::vector<std::shared_ptr<TxGraph::Ref>> removed;
      53                 :             :     /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */
      54                 :             :     std::optional<bool> oversized;
      55                 :             :     /** The configured maximum number of transactions per cluster. */
      56                 :             :     DepGraphIndex max_cluster_count;
      57                 :             :     /** Which transactions have been modified in the graph since creation, either directly or by
      58                 :             :      *  being in a cluster which includes modifications. Only relevant for the staging graph. */
      59                 :             :     SetType modified;
      60                 :             :     /** The configured maximum total size of transactions per cluster. */
      61                 :             :     uint64_t max_cluster_size;
      62                 :             :     /** Whether the corresponding real graph is known to be optimally linearized. */
      63                 :             :     bool real_is_optimal{false};
      64                 :             : 
      65                 :             :     /** Construct a new SimTxGraph with the specified maximum cluster count and size. */
      66                 :        4234 :     explicit SimTxGraph(DepGraphIndex cluster_count, uint64_t cluster_size) :
      67                 :        4234 :         max_cluster_count(cluster_count), max_cluster_size(cluster_size) {}
      68                 :             : 
      69                 :             :     // Permit copying and moving.
      70   [ +  -  +  - ]:        7529 :     SimTxGraph(const SimTxGraph&) noexcept = default;
      71                 :             :     SimTxGraph& operator=(const SimTxGraph&) noexcept = default;
      72                 :           0 :     SimTxGraph(SimTxGraph&&) noexcept = default;
      73                 :        3794 :     SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
      74                 :             : 
      75                 :             :     /** Get the connected components within this simulated transaction graph. */
      76                 :       65831 :     std::vector<SetType> GetComponents()
      77                 :             :     {
      78                 :       65831 :         auto todo = graph.Positions();
      79                 :       65831 :         std::vector<SetType> ret;
      80                 :             :         // Iterate over all connected components of the graph.
      81         [ +  + ]:     2176488 :         while (todo.Any()) {
      82                 :     1022413 :             auto component = graph.FindConnectedComponent(todo);
      83         [ +  - ]:     1022413 :             ret.push_back(component);
      84                 :     1022413 :             todo -= component;
      85                 :             :         }
      86                 :       65831 :         return ret;
      87                 :           0 :     }
      88                 :             : 
      89                 :             :     /** Check whether this graph is oversized (contains a connected component whose number of
      90                 :             :      *  transactions exceeds max_cluster_count. */
      91                 :     4089528 :     bool IsOversized()
      92                 :             :     {
      93         [ +  + ]:     4089528 :         if (!oversized.has_value()) {
      94                 :             :             // Only recompute when oversized isn't already known.
      95                 :       55235 :             oversized = false;
      96         [ +  + ]:      966782 :             for (auto component : GetComponents()) {
      97         [ +  + ]:      911547 :                 if (component.Count() > max_cluster_count) oversized = true;
      98                 :      911547 :                 uint64_t component_size{0};
      99         [ +  + ]:     2084066 :                 for (auto i : component) component_size += graph.FeeRate(i).size;
     100         [ +  + ]:      911547 :                 if (component_size > max_cluster_size) oversized = true;
     101                 :       55235 :             }
     102                 :             :         }
     103                 :     4089528 :         return *oversized;
     104                 :             :     }
     105                 :             : 
     106                 :      296343 :     void MakeModified(DepGraphIndex index)
     107                 :             :     {
     108                 :      296343 :         modified |= graph.GetConnectedComponent(graph.Positions(), index);
     109                 :      296343 :     }
     110                 :             : 
     111                 :             :     /** Determine the number of (non-removed) transactions in the graph. */
     112   [ +  +  +  +  :     2371709 :     DepGraphIndex GetTransactionCount() const { return graph.TxCount(); }
             +  +  +  + ]
     113                 :             : 
     114                 :             :     /** Get the sum of all fees/sizes in the graph. */
     115                 :       11532 :     FeePerWeight SumAll() const
     116                 :             :     {
     117                 :       11532 :         FeePerWeight ret;
     118         [ +  + ]:      222227 :         for (auto i : graph.Positions()) {
     119                 :      210695 :             ret += graph.FeeRate(i);
     120                 :             :         }
     121                 :       11532 :         return ret;
     122                 :             :     }
     123                 :             : 
     124                 :             :     /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */
     125                 :     2465395 :     Pos Find(const TxGraph::Ref* ref) const
     126                 :             :     {
     127                 :     2465395 :         auto it = simrevmap.find(ref);
     128         [ +  + ]:     2465395 :         if (it != simrevmap.end()) return it->second;
     129                 :             :         return MISSING;
     130                 :             :     }
     131                 :             : 
     132                 :             :     /** Given a position in this simulated graph, get the corresponding TxGraph::Ref. */
     133                 :     2181095 :     TxGraph::Ref* GetRef(Pos pos)
     134                 :             :     {
     135         [ -  + ]:     2181095 :         assert(graph.Positions()[pos]);
     136         [ -  + ]:     2181095 :         assert(simmap[pos]);
     137                 :     2181095 :         return simmap[pos].get();
     138                 :             :     }
     139                 :             : 
     140                 :             :     /** Add a new transaction to the simulation. */
     141                 :      165256 :     TxGraph::Ref* AddTransaction(const FeePerWeight& feerate)
     142                 :             :     {
     143         [ -  + ]:      165256 :         assert(graph.TxCount() < MAX_TRANSACTIONS);
     144                 :      165256 :         auto simpos = graph.AddTransaction(feerate);
     145                 :      165256 :         real_is_optimal = false;
     146                 :      165256 :         MakeModified(simpos);
     147         [ -  + ]:      165256 :         assert(graph.Positions()[simpos]);
     148         [ -  + ]:      165256 :         simmap[simpos] = std::make_shared<TxGraph::Ref>();
     149                 :      165256 :         auto ptr = simmap[simpos].get();
     150                 :      165256 :         simrevmap[ptr] = simpos;
     151                 :             :         // This may invalidate our cached oversized value.
     152   [ +  +  +  + ]:      165256 :         if (oversized.has_value() && !*oversized) oversized = std::nullopt;
     153                 :      165256 :         return ptr;
     154                 :             :     }
     155                 :             : 
     156                 :             :     /** Add a dependency between two positions in this graph. */
     157                 :       98654 :     void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child)
     158                 :             :     {
     159                 :       98654 :         auto par_pos = Find(parent);
     160         [ +  + ]:       98654 :         if (par_pos == MISSING) return;
     161                 :       88986 :         auto chl_pos = Find(child);
     162         [ +  + ]:       88986 :         if (chl_pos == MISSING) return;
     163                 :       79465 :         graph.AddDependencies(SetType::Singleton(par_pos), chl_pos);
     164                 :       79465 :         MakeModified(par_pos);
     165                 :       79465 :         real_is_optimal = false;
     166                 :             :         // This may invalidate our cached oversized value.
     167   [ +  +  +  + ]:       79465 :         if (oversized.has_value() && !*oversized) oversized = std::nullopt;
     168                 :             :     }
     169                 :             : 
     170                 :             :     /** Modify the transaction fee of a ref, if it exists. */
     171                 :       12352 :     void SetTransactionFee(TxGraph::Ref* ref, int64_t fee)
     172                 :             :     {
     173                 :       12352 :         auto pos = Find(ref);
     174         [ +  + ]:       12352 :         if (pos == MISSING) return;
     175                 :             :         // No need to invoke MakeModified, because this equally affects main and staging.
     176                 :        9069 :         real_is_optimal = false;
     177                 :        9069 :         graph.FeeRate(pos).fee = fee;
     178                 :             :     }
     179                 :             : 
     180                 :             :     /** Remove the transaction in the specified position from the graph. */
     181                 :       50563 :     void RemoveTransaction(TxGraph::Ref* ref)
     182                 :             :     {
     183                 :       50563 :         auto pos = Find(ref);
     184         [ +  + ]:       50563 :         if (pos == MISSING) return;
     185                 :       37163 :         MakeModified(pos);
     186                 :       37163 :         real_is_optimal = false;
     187                 :       37163 :         graph.RemoveTransactions(SetType::Singleton(pos));
     188                 :       37163 :         simrevmap.erase(simmap[pos].get());
     189                 :             :         // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't
     190                 :             :         // invoked until the simulation explicitly decided to do so.
     191                 :       37163 :         removed.push_back(std::move(simmap[pos]));
     192                 :       37163 :         simmap[pos].reset();
     193                 :             :         // This may invalidate our cached oversized value.
     194   [ +  +  +  + ]:       37163 :         if (oversized.has_value() && *oversized) oversized = std::nullopt;
     195                 :             :     }
     196                 :             : 
     197                 :             :     /** Destroy the transaction from the graph, including from the removed set. This will
     198                 :             :      *  trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized
     199                 :             :      *  value is cleared (destroying does not clear oversizedness in TxGraph of the main
     200                 :             :      *  graph while staging exists). */
     201                 :       21145 :     void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize)
     202                 :             :     {
     203                 :       21145 :         auto pos = Find(ref);
     204         [ +  + ]:       21145 :         if (pos == MISSING) {
     205                 :             :             // Wipe the ref, if it exists, from the removed vector. Use std::partition rather
     206                 :             :             // than std::erase because we don't care about the order of the entries that
     207                 :             :             // remain.
     208   [ +  +  -  + ]:       22758 :             auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; });
     209                 :        6686 :             removed.erase(remove, removed.end());
     210                 :             :         } else {
     211                 :       14459 :             MakeModified(pos);
     212                 :       14459 :             graph.RemoveTransactions(SetType::Singleton(pos));
     213                 :       14459 :             real_is_optimal = false;
     214                 :       14459 :             simrevmap.erase(simmap[pos].get());
     215                 :       14459 :             simmap[pos].reset();
     216                 :             :             // This may invalidate our cached oversized value.
     217   [ +  +  +  +  :       14459 :             if (reset_oversize && oversized.has_value() && *oversized) {
                   +  + ]
     218                 :        2945 :                 oversized = std::nullopt;
     219                 :             :             }
     220                 :             :         }
     221                 :       21145 :     }
     222                 :             : 
     223                 :             :     /** Construct the set with all positions in this graph corresponding to the specified
     224                 :             :      *  TxGraph::Refs. All of them must occur in this graph and not be removed. */
     225                 :      338848 :     SetType MakeSet(std::span<TxGraph::Ref* const> arg)
     226                 :             :     {
     227                 :      338848 :         SetType ret;
     228         [ +  + ]:     1246529 :         for (TxGraph::Ref* ptr : arg) {
     229                 :      907681 :             auto pos = Find(ptr);
     230         [ -  + ]:      907681 :             assert(pos != Pos(-1));
     231                 :      907681 :             ret.Set(pos);
     232                 :             :         }
     233                 :      338848 :         return ret;
     234                 :             :     }
     235                 :             : 
     236                 :             :     /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */
     237                 :       68901 :     SetType GetAncDesc(TxGraph::Ref* arg, bool desc)
     238                 :             :     {
     239                 :       68901 :         auto pos = Find(arg);
     240         [ +  + ]:       68901 :         if (pos == MISSING) return {};
     241         [ +  + ]:       36047 :         return desc ? graph.Descendants(pos) : graph.Ancestors(pos);
     242                 :             :     }
     243                 :             : 
     244                 :             :     /** Given a set of Refs (given as a vector of pointers), expand the set to include all its
     245                 :             :      *  ancestors (desc=false) or all its descendants (desc=true) in this graph. */
     246                 :       43425 :     void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
     247                 :             :     {
     248                 :       43425 :         std::vector<TxGraph::Ref*> ret;
     249         [ +  + ]:       90017 :         for (auto ptr : arg) {
     250                 :       46592 :             auto simpos = Find(ptr);
     251         [ +  + ]:       46592 :             if (simpos != MISSING) {
     252   [ +  +  +  + ]:       63650 :                 for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
     253         [ +  - ]:       37241 :                     ret.push_back(simmap[i].get());
     254                 :             :                 }
     255                 :             :             } else {
     256         [ +  - ]:       20183 :                 ret.push_back(ptr);
     257                 :             :             }
     258                 :             :         }
     259                 :             :         // Construct deduplicated version in input (do not use std::sort/std::unique for
     260                 :             :         // deduplication as it'd rely on non-deterministic pointer comparison).
     261         [ +  - ]:       43425 :         arg.clear();
     262         [ +  + ]:      100849 :         for (auto ptr : ret) {
     263         [ +  + ]:       57424 :             if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
     264         [ +  - ]:       52694 :                 arg.push_back(ptr);
     265                 :             :             }
     266                 :             :         }
     267                 :       43425 :     }
     268                 :             : 
     269                 :             : 
     270                 :             :     /** Verify that set contains transactions from every oversized cluster, and nothing from
     271                 :             :      *  non-oversized ones. */
     272                 :        4479 :     bool MatchesOversizedClusters(const SetType& set)
     273                 :             :     {
     274   [ +  -  +  - ]:        8958 :         if (set.Any() && !IsOversized()) return false;
     275                 :             : 
     276                 :        4479 :         auto todo = graph.Positions();
     277         [ +  - ]:        8958 :         if (!set.IsSubsetOf(todo)) return false;
     278                 :             : 
     279                 :             :         // Walk all clusters, and make sure all of set doesn't come from non-oversized clusters
     280         [ +  + ]:      179802 :         while (todo.Any()) {
     281                 :       85422 :             auto component = graph.FindConnectedComponent(todo);
     282                 :             :             // Determine whether component is oversized, due to either the size or count limit.
     283                 :       85422 :             bool is_oversized = component.Count() > max_cluster_count;
     284                 :       85422 :             uint64_t component_size{0};
     285         [ +  + ]:      210795 :             for (auto i : component) component_size += graph.FeeRate(i).size;
     286                 :       85422 :             is_oversized |= component_size > max_cluster_size;
     287                 :             :             // Check whether overlap with set matches is_oversized.
     288         [ +  - ]:      170844 :             if (is_oversized != set.Overlaps(component)) return false;
     289                 :       85422 :             todo -= component;
     290                 :             :         }
     291                 :             :         return true;
     292                 :             :     }
     293                 :             : };
     294                 :             : 
     295                 :             : } // namespace
     296                 :             : 
     297         [ +  - ]:        4688 : FUZZ_TARGET(txgraph)
     298                 :             : {
     299                 :             :     // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
     300                 :             :     // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
     301                 :             :     // SimTxGraph above), comparing the outcome of functions that return a result, and finally
     302                 :             :     // performing a full comparison between the two.
     303                 :             : 
     304                 :        4234 :     SeedRandomStateForTest(SeedRand::ZEROS);
     305                 :        4234 :     FuzzedDataProvider provider(buffer.data(), buffer.size());
     306                 :             : 
     307                 :             :     /** Internal test RNG, used only for decisions which would require significant amount of data
     308                 :             :      *  to be read from the provider, without realistically impacting test sensitivity, and for
     309                 :             :      *  specialized test cases that are hard to perform more generically. */
     310                 :        4234 :     InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>());
     311                 :             : 
     312                 :             :     /** Variable used whenever an empty TxGraph::Ref is needed. */
     313                 :        4234 :     TxGraph::Ref empty_ref;
     314                 :             : 
     315                 :             :     /** The maximum number of transactions per (non-oversized) cluster we will use in this
     316                 :             :      *  simulation. */
     317                 :        4234 :     auto max_cluster_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
     318                 :             :     /** The maximum total size of transactions in a (non-oversized) cluster. */
     319                 :        4234 :     auto max_cluster_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT);
     320                 :             :     /** The number of iterations to consider a cluster acceptably linearized. */
     321                 :        4234 :     auto acceptable_iters = provider.ConsumeIntegralInRange<uint64_t>(0, 10000);
     322                 :             : 
     323                 :             :     // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
     324                 :        4234 :     auto real = MakeTxGraph(max_cluster_count, max_cluster_size, acceptable_iters);
     325                 :        4234 :     std::vector<SimTxGraph> sims;
     326         [ +  - ]:        4234 :     sims.reserve(2);
     327         [ +  - ]:        4234 :     sims.emplace_back(max_cluster_count, max_cluster_size);
     328                 :             : 
     329                 :             :     /** Struct encapsulating information about a BlockBuilder that's currently live. */
     330                 :       12750 :     struct BlockBuilderData
     331                 :             :     {
     332                 :             :         /** BlockBuilder object from real. */
     333                 :             :         std::unique_ptr<TxGraph::BlockBuilder> builder;
     334                 :             :         /** The set of transactions marked as included in *builder. */
     335                 :             :         SimTxGraph::SetType included;
     336                 :             :         /** The set of transactions marked as included or skipped in *builder. */
     337                 :             :         SimTxGraph::SetType done;
     338                 :             :         /** The last chunk feerate returned by *builder. IsEmpty() if none yet. */
     339                 :             :         FeePerWeight last_feerate;
     340                 :             : 
     341                 :        4913 :         BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
     342                 :             :     };
     343                 :             : 
     344                 :             :     /** Currently active block builders. */
     345                 :        4234 :     std::vector<BlockBuilderData> block_builders;
     346                 :             : 
     347                 :             :     /** Function to pick any Ref (for either sim in sims: from sim.simmap or sim.removed, or the
     348                 :             :      *  empty Ref). */
     349                 :      621684 :     auto pick_fn = [&]() noexcept -> TxGraph::Ref* {
     350         [ +  + ]:      617450 :         size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
     351                 :             :         /** The number of possible choices. */
     352         [ +  + ]:      617450 :         size_t choices = tx_count[0] + sims[0].removed.size() + 1;
     353         [ +  + ]:      617450 :         if (sims.size() == 2) {
     354                 :      232640 :             tx_count[1] = sims[1].GetTransactionCount();
     355                 :      232640 :             choices += tx_count[1] + sims[1].removed.size();
     356                 :             :         }
     357                 :             :         /** Pick one of them. */
     358                 :      617450 :         auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
     359                 :             :         // Consider both main and (if it exists) staging.
     360         [ +  + ]:      849660 :         for (size_t level = 0; level < sims.size(); ++level) {
     361         [ +  + ]:      724767 :             auto& sim = sims[level];
     362         [ +  + ]:      724767 :             if (choice < tx_count[level]) {
     363                 :             :                 // Return from graph.
     364         [ +  - ]:     2884295 :                 for (auto i : sim.graph.Positions()) {
     365         [ +  + ]:     2884295 :                     if (choice == 0) return sim.GetRef(i);
     366                 :     2442570 :                     --choice;
     367                 :             :                 }
     368                 :           0 :                 assert(false);
     369                 :             :             } else {
     370                 :      283042 :                 choice -= tx_count[level];
     371                 :             :             }
     372         [ +  + ]:      283042 :             if (choice < sim.removed.size()) {
     373                 :             :                 // Return from removed.
     374                 :       50832 :                 return sim.removed[choice].get();
     375                 :             :             } else {
     376                 :      232210 :                 choice -= sim.removed.size();
     377                 :             :             }
     378                 :             :         }
     379                 :             :         // Return empty.
     380         [ -  + ]:      124893 :         assert(choice == 0);
     381                 :      124893 :         return &empty_ref;
     382                 :        4234 :     };
     383                 :             : 
     384                 :             :     /** Function to construct the correct fee-size diagram a real graph has based on its graph
     385                 :             :      *  order (as reported by GetCluster(), so it works for both main and staging). */
     386                 :        8371 :     auto get_diagram_fn = [&](bool main_only) -> std::vector<FeeFrac> {
     387         [ +  + ]:        4137 :         int level = main_only ? 0 : sims.size() - 1;
     388                 :        4137 :         auto& sim = sims[level];
     389                 :             :         // For every transaction in the graph, request its cluster, and throw them into a set.
     390                 :        4137 :         std::set<std::vector<TxGraph::Ref*>> clusters;
     391         [ +  + ]:       76675 :         for (auto i : sim.graph.Positions()) {
     392                 :       72538 :             auto ref = sim.GetRef(i);
     393         [ +  - ]:      145076 :             clusters.insert(real->GetCluster(*ref, main_only));
     394                 :             :         }
     395                 :             :         // Compute the chunkings of each (deduplicated) cluster.
     396                 :        4137 :         size_t num_tx{0};
     397                 :        4137 :         std::vector<FeeFrac> chunk_feerates;
     398         [ +  + ]:       61079 :         for (const auto& cluster : clusters) {
     399         [ +  - ]:       56942 :             num_tx += cluster.size();
     400                 :       56942 :             std::vector<SimTxGraph::Pos> linearization;
     401         [ +  - ]:       56942 :             linearization.reserve(cluster.size());
     402   [ +  -  +  + ]:      129480 :             for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
     403         [ +  + ]:      123353 :             for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
     404         [ +  - ]:       66411 :                 chunk_feerates.push_back(chunk_feerate);
     405                 :       56942 :             }
     406                 :       56942 :         }
     407                 :             :         // Verify the number of transactions after deduplicating clusters. This implicitly verifies
     408                 :             :         // that GetCluster on each element of a cluster reports the cluster transactions in the same
     409                 :             :         // order.
     410         [ -  + ]:        4137 :         assert(num_tx == sim.GetTransactionCount());
     411                 :             :         // Sort by feerate only, since violating topological constraints within same-feerate
     412                 :             :         // chunks won't affect diagram comparisons.
     413                 :        4137 :         std::sort(chunk_feerates.begin(), chunk_feerates.end(), std::greater{});
     414                 :        4137 :         return chunk_feerates;
     415                 :        8371 :     };
     416                 :             : 
     417   [ +  +  +  + ]:      546121 :     LIMITED_WHILE(provider.remaining_bytes() > 0, 200) {
     418                 :             :         // Read a one-byte command.
     419                 :      541887 :         int command = provider.ConsumeIntegral<uint8_t>();
     420                 :      541887 :         int orig_command = command;
     421                 :             : 
     422                 :             :         // Treat the lowest bit of a command as a flag (which selects a variant of some of the
     423                 :             :         // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
     424                 :             :         // the rest of the bits in command.
     425                 :      541887 :         bool alt = command & 1;
     426                 :      541887 :         bool use_main = command & 2;
     427                 :      541887 :         command >>= 2;
     428                 :             : 
     429                 :             :         /** Use the bottom 2 bits of command to select an entry in the block_builders vector (if
     430                 :             :          *  any). These use the same bits as alt/use_main, so don't use those in actions below
     431                 :             :          *  where builder_idx is used as well. */
     432         [ +  + ]:      541887 :         int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
     433                 :             : 
     434                 :             :         // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
     435                 :             :         // one for the simulated graph selected based on use_main (for operations that can operate
     436                 :             :         // on both graphs), and one that always refers to the main graph.
     437                 :      541887 :         auto& top_sim = sims.back();
     438         [ +  + ]:      541887 :         auto& sel_sim = use_main ? sims[0] : top_sim;
     439                 :      541887 :         auto& main_sim = sims[0];
     440                 :             : 
     441                 :             :         // Keep decrementing command for each applicable operation, until one is hit. Multiple
     442                 :             :         // iterations may be necessary.
     443                 :      892310 :         while (true) {
     444   [ +  +  +  +  :      892310 :             if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
             +  +  +  + ]
     445                 :             :                 // AddTransaction.
     446                 :      165256 :                 int64_t fee;
     447                 :      165256 :                 int32_t size;
     448         [ +  + ]:      165256 :                 if (alt) {
     449                 :             :                     // If alt is true, pick fee and size from the entire range.
     450                 :        8600 :                     fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
     451                 :        8600 :                     size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
     452                 :             :                 } else {
     453                 :             :                     // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
     454                 :             :                     // these are likely sufficient to trigger all interesting code paths already.
     455                 :      156656 :                     fee = provider.ConsumeIntegral<uint8_t>();
     456                 :      156656 :                     size = provider.ConsumeIntegralInRange<uint32_t>(1, 0xff);
     457                 :             :                 }
     458                 :      165256 :                 FeePerWeight feerate{fee, size};
     459                 :             :                 // Create a real TxGraph::Ref.
     460                 :      165256 :                 auto ref = real->AddTransaction(feerate);
     461                 :             :                 // Create a shared_ptr place in the simulation to put the Ref in.
     462         [ +  - ]:      165256 :                 auto ref_loc = top_sim.AddTransaction(feerate);
     463                 :             :                 // Move it in place.
     464                 :      165256 :                 *ref_loc = std::move(ref);
     465                 :      165256 :                 break;
     466   [ +  +  +  +  :      892310 :             } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
             +  +  +  + ]
     467                 :             :                 // AddDependency.
     468                 :       72166 :                 auto par = pick_fn();
     469                 :       72166 :                 auto chl = pick_fn();
     470                 :       72166 :                 auto pos_par = top_sim.Find(par);
     471                 :       72166 :                 auto pos_chl = top_sim.Find(chl);
     472         [ +  + ]:       72166 :                 if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
     473                 :             :                     // Determine if adding this would introduce a cycle (not allowed by TxGraph),
     474                 :             :                     // and if so, skip.
     475         [ +  + ]:       52977 :                     if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break;
     476                 :             :                 }
     477                 :       61138 :                 top_sim.AddDependency(par, chl);
     478                 :       61138 :                 top_sim.real_is_optimal = false;
     479                 :       61138 :                 real->AddDependency(*par, *chl);
     480                 :       61138 :                 break;
     481   [ +  +  +  +  :      654888 :             } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
             +  +  +  + ]
     482                 :             :                 // RemoveTransaction. Either all its ancestors or all its descendants are also
     483                 :             :                 // removed (if any), to make sure TxGraph's reordering of removals and dependencies
     484                 :             :                 // has no effect.
     485                 :       23911 :                 std::vector<TxGraph::Ref*> to_remove;
     486         [ +  - ]:       23911 :                 to_remove.push_back(pick_fn());
     487         [ +  - ]:       23911 :                 top_sim.IncludeAncDesc(to_remove, alt);
     488                 :             :                 // The order in which these ancestors/descendants are removed should not matter;
     489                 :             :                 // randomly shuffle them.
     490                 :       23911 :                 std::shuffle(to_remove.begin(), to_remove.end(), rng);
     491         [ +  + ]:       51596 :                 for (TxGraph::Ref* ptr : to_remove) {
     492                 :       27685 :                     real->RemoveTransaction(*ptr);
     493         [ +  - ]:       27685 :                     top_sim.RemoveTransaction(ptr);
     494                 :             :                 }
     495                 :       23911 :                 break;
     496   [ +  +  +  + ]:      654888 :             } else if (sel_sim.removed.size() > 0 && command-- == 0) {
     497                 :             :                 // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
     498                 :             :                 // observable effect on the TxGraph it refers to, so this simulation permits doing
     499                 :             :                 // so separately from other actions on TxGraph.
     500                 :             : 
     501                 :             :                 // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur
     502                 :             :                 // in the other graph, and thus not actually trigger ~Ref yet (which is exactly
     503                 :             :                 // what we want, as destroying Refs is only allowed when it does not refer to an
     504                 :             :                 // existing transaction in either graph).
     505                 :        9460 :                 auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1);
     506         [ +  + ]:        9460 :                 if (removed_pos != sel_sim.removed.size() - 1) {
     507                 :        6280 :                     std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
     508                 :             :                 }
     509                 :        9460 :                 sel_sim.removed.pop_back();
     510                 :        9460 :                 break;
     511   [ +  +  +  + ]:      621517 :             } else if (block_builders.empty() && command-- == 0) {
     512                 :             :                 // ~Ref (of any transaction).
     513                 :       14907 :                 std::vector<TxGraph::Ref*> to_destroy;
     514         [ +  - ]:       14907 :                 to_destroy.push_back(pick_fn());
     515                 :       15897 :                 while (true) {
     516                 :             :                     // Keep adding either the ancestors or descendants the already picked
     517                 :             :                     // transactions have in both graphs (main and staging) combined. Destroying
     518                 :             :                     // will trigger deletions in both, so to have consistent TxGraph behavior, the
     519                 :             :                     // set must be closed under ancestors, or descendants, in both graphs.
     520                 :       15897 :                     auto old_size = to_destroy.size();
     521   [ +  -  +  + ]:       35411 :                     for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
     522         [ +  + ]:       15897 :                     if (to_destroy.size() == old_size) break;
     523                 :             :                 }
     524                 :             :                 // The order in which these ancestors/descendants are destroyed should not matter;
     525                 :             :                 // randomly shuffle them.
     526                 :       14907 :                 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
     527         [ +  + ]:       32142 :                 for (TxGraph::Ref* ptr : to_destroy) {
     528         [ +  + ]:       38380 :                     for (size_t level = 0; level < sims.size(); ++level) {
     529                 :       21145 :                         sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
     530                 :             :                     }
     531                 :             :                 }
     532                 :       14907 :                 break;
     533   [ +  +  +  + ]:      621517 :             } else if (block_builders.empty() && command-- == 0) {
     534                 :             :                 // SetTransactionFee.
     535                 :       10997 :                 int64_t fee;
     536         [ +  + ]:       10997 :                 if (alt) {
     537                 :        5413 :                     fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
     538                 :             :                 } else {
     539                 :        5584 :                     fee = provider.ConsumeIntegral<uint8_t>();
     540                 :             :                 }
     541                 :       10997 :                 auto ref = pick_fn();
     542                 :       10997 :                 real->SetTransactionFee(*ref, fee);
     543         [ +  + ]:       23349 :                 for (auto& sim : sims) {
     544                 :       12352 :                     sim.SetTransactionFee(ref, fee);
     545                 :             :                 }
     546                 :             :                 break;
     547         [ +  + ]:      595613 :             } else if (command-- == 0) {
     548                 :             :                 // GetTransactionCount.
     549         [ -  + ]:       36332 :                 assert(real->GetTransactionCount(use_main) == sel_sim.GetTransactionCount());
     550                 :             :                 break;
     551         [ +  + ]:      559281 :             } else if (command-- == 0) {
     552                 :             :                 // Exists.
     553                 :       17904 :                 auto ref = pick_fn();
     554                 :       17904 :                 bool exists = real->Exists(*ref, use_main);
     555                 :       17904 :                 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
     556         [ -  + ]:       17904 :                 assert(exists == should_exist);
     557                 :             :                 break;
     558         [ +  + ]:      541377 :             } else if (command-- == 0) {
     559                 :             :                 // IsOversized.
     560   [ +  -  -  + ]:       16860 :                 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
     561                 :             :                 break;
     562         [ +  + ]:      524517 :             } else if (command-- == 0) {
     563                 :             :                 // GetIndividualFeerate.
     564                 :       16038 :                 auto ref = pick_fn();
     565                 :       16038 :                 auto feerate = real->GetIndividualFeerate(*ref);
     566                 :       16038 :                 bool found{false};
     567         [ +  + ]:       34699 :                 for (auto& sim : sims) {
     568                 :       18661 :                     auto simpos = sim.Find(ref);
     569         [ +  + ]:       18661 :                     if (simpos != SimTxGraph::MISSING) {
     570                 :       10344 :                         found = true;
     571         [ +  - ]:       29005 :                         assert(feerate == sim.graph.FeeRate(simpos));
     572                 :             :                     }
     573                 :             :                 }
     574   [ +  +  -  + ]:       16038 :                 if (!found) assert(feerate.IsEmpty());
     575                 :             :                 break;
     576   [ +  -  +  +  :      508479 :             } else if (!main_sim.IsOversized() && command-- == 0) {
                   +  + ]
     577                 :             :                 // GetMainChunkFeerate.
     578                 :        7982 :                 auto ref = pick_fn();
     579                 :        7982 :                 auto feerate = real->GetMainChunkFeerate(*ref);
     580                 :        7982 :                 auto simpos = main_sim.Find(ref);
     581         [ +  + ]:        7982 :                 if (simpos == SimTxGraph::MISSING) {
     582         [ -  + ]:        3142 :                     assert(feerate.IsEmpty());
     583                 :             :                 } else {
     584                 :             :                     // Just do some quick checks that the reported value is in range. A full
     585                 :             :                     // recomputation of expected chunk feerates is done at the end.
     586         [ -  + ]:        4840 :                     assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
     587         [ -  + ]:        4840 :                     assert(feerate.size <= main_sim.SumAll().size);
     588                 :             :                 }
     589                 :             :                 break;
     590   [ +  -  +  +  :      500497 :             } else if (!sel_sim.IsOversized() && command-- == 0) {
                   +  + ]
     591                 :             :                 // GetAncestors/GetDescendants.
     592                 :       13069 :                 auto ref = pick_fn();
     593         [ +  + ]:       13069 :                 auto result = alt ? real->GetDescendants(*ref, use_main)
     594                 :       13069 :                                   : real->GetAncestors(*ref, use_main);
     595         [ -  + ]:       13069 :                 assert(result.size() <= max_cluster_count);
     596                 :       13069 :                 auto result_set = sel_sim.MakeSet(result);
     597         [ -  + ]:       13069 :                 assert(result.size() == result_set.Count());
     598                 :       13069 :                 auto expect_set = sel_sim.GetAncDesc(ref, alt);
     599         [ -  + ]:       13069 :                 assert(result_set == expect_set);
     600                 :       13069 :                 break;
     601   [ +  -  +  +  :      500497 :             } else if (!sel_sim.IsOversized() && command-- == 0) {
                   +  + ]
     602                 :             :                 // GetAncestorsUnion/GetDescendantsUnion.
     603                 :        8747 :                 std::vector<TxGraph::Ref*> refs;
     604                 :             :                 // Gather a list of up to 15 Ref pointers.
     605                 :        8747 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, 15);
     606         [ +  - ]:        8747 :                 refs.resize(count);
     607         [ +  + ]:       64579 :                 for (size_t i = 0; i < count; ++i) {
     608                 :       55832 :                     refs[i] = pick_fn();
     609                 :             :                 }
     610                 :             :                 // Their order should not matter, shuffle them.
     611                 :        8747 :                 std::shuffle(refs.begin(), refs.end(), rng);
     612                 :             :                 // Invoke the real function, and convert to SimPos set.
     613         [ +  + ]:        8747 :                 auto result = alt ? real->GetDescendantsUnion(refs, use_main)
     614                 :        8747 :                                   : real->GetAncestorsUnion(refs, use_main);
     615                 :        8747 :                 auto result_set = sel_sim.MakeSet(result);
     616         [ -  + ]:        8747 :                 assert(result.size() == result_set.Count());
     617                 :             :                 // Compute the expected result.
     618                 :        8747 :                 SimTxGraph::SetType expect_set;
     619         [ +  + ]:       64579 :                 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
     620                 :             :                 // Compare.
     621         [ -  + ]:        8747 :                 assert(result_set == expect_set);
     622                 :        8747 :                 break;
     623   [ +  -  +  +  :      487428 :             } else if (!sel_sim.IsOversized() && command-- == 0) {
                   +  + ]
     624                 :             :                 // GetCluster.
     625                 :        7867 :                 auto ref = pick_fn();
     626                 :        7867 :                 auto result = real->GetCluster(*ref, use_main);
     627                 :             :                 // Check cluster count limit.
     628         [ -  + ]:        7867 :                 assert(result.size() <= max_cluster_count);
     629                 :             :                 // Require the result to be topologically valid and not contain duplicates.
     630                 :        7867 :                 auto left = sel_sim.graph.Positions();
     631                 :        7867 :                 uint64_t total_size{0};
     632         [ +  + ]:       17676 :                 for (auto refptr : result) {
     633                 :        9809 :                     auto simpos = sel_sim.Find(refptr);
     634         [ -  + ]:        9809 :                     total_size += sel_sim.graph.FeeRate(simpos).size;
     635         [ -  + ]:        9809 :                     assert(simpos != SimTxGraph::MISSING);
     636         [ -  + ]:        9809 :                     assert(left[simpos]);
     637                 :        9809 :                     left.Reset(simpos);
     638         [ -  + ]:       19618 :                     assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
     639                 :             :                 }
     640                 :             :                 // Check cluster size limit.
     641         [ -  + ]:        7867 :                 assert(total_size <= max_cluster_size);
     642                 :             :                 // Require the set to be connected.
     643                 :        7867 :                 auto result_set = sel_sim.MakeSet(result);
     644         [ -  + ]:        7867 :                 assert(sel_sim.graph.IsConnected(result_set));
     645                 :             :                 // If ref exists, the result must contain it. If not, it must be empty.
     646                 :        7867 :                 auto simpos = sel_sim.Find(ref);
     647         [ +  + ]:        7867 :                 if (simpos != SimTxGraph::MISSING) {
     648         [ -  + ]:        4235 :                     assert(result_set[simpos]);
     649                 :             :                 } else {
     650         [ -  + ]:        3632 :                     assert(result_set.None());
     651                 :             :                 }
     652                 :             :                 // Require the set not to have ancestors or descendants outside of it.
     653         [ +  + ]:       17676 :                 for (auto i : result_set) {
     654         [ -  + ]:       19618 :                     assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
     655         [ -  + ]:        9809 :                     assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
     656                 :             :                 }
     657                 :        7867 :                 break;
     658         [ +  + ]:      478681 :             } else if (command-- == 0) {
     659                 :             :                 // HaveStaging.
     660         [ -  + ]:       20767 :                 assert((sims.size() == 2) == real->HaveStaging());
     661                 :             :                 break;
     662   [ +  +  +  + ]:      450047 :             } else if (sims.size() < 2 && command-- == 0) {
     663                 :             :                 // StartStaging.
     664         [ +  - ]:        7529 :                 sims.emplace_back(sims.back());
     665                 :        7529 :                 sims.back().modified = SimTxGraph::SetType{};
     666                 :        7529 :                 real->StartStaging();
     667                 :        7529 :                 break;
     668   [ +  +  +  +  :      442518 :             } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
                   +  + ]
     669                 :             :                 // CommitStaging.
     670                 :        3794 :                 real->CommitStaging();
     671                 :        3794 :                 sims.erase(sims.begin());
     672                 :             :                 break;
     673   [ +  +  +  + ]:      438724 :             } else if (sims.size() > 1 && command-- == 0) {
     674                 :             :                 // AbortStaging.
     675                 :        2089 :                 real->AbortStaging();
     676                 :        2089 :                 sims.pop_back();
     677                 :             :                 // Reset the cached oversized value (if TxGraph::Ref destructions triggered
     678                 :             :                 // removals of main transactions while staging was active, then aborting will
     679                 :             :                 // cause it to be re-evaluated in TxGraph).
     680         [ +  - ]:      543976 :                 sims.back().oversized = std::nullopt;
     681                 :             :                 break;
     682   [ +  -  +  +  :      436635 :             } else if (!main_sim.IsOversized() && command-- == 0) {
                   +  + ]
     683                 :             :                 // CompareMainOrder.
     684                 :        9272 :                 auto ref_a = pick_fn();
     685                 :        9272 :                 auto ref_b = pick_fn();
     686                 :        9272 :                 auto sim_a = main_sim.Find(ref_a);
     687                 :        9272 :                 auto sim_b = main_sim.Find(ref_b);
     688                 :             :                 // Both transactions must exist in the main graph.
     689         [ +  + ]:        9272 :                 if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break;
     690                 :        3949 :                 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
     691                 :             :                 // Distinct transactions have distinct places.
     692   [ +  +  -  + ]:        3949 :                 if (sim_a != sim_b) assert(cmp != 0);
     693                 :             :                 // Ancestors go before descendants.
     694   [ +  +  -  + ]:        3949 :                 if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0);
     695   [ +  +  -  + ]:        3949 :                 if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0);
     696                 :             :                 // Do not verify consistency with chunk feerates, as we cannot easily determine
     697                 :             :                 // these here without making more calls to real, which could affect its internal
     698                 :             :                 // state. A full comparison is done at the end.
     699                 :             :                 break;
     700   [ +  -  +  +  :      427363 :             } else if (!sel_sim.IsOversized() && command-- == 0) {
                   +  + ]
     701                 :             :                 // CountDistinctClusters.
     702                 :        9295 :                 std::vector<TxGraph::Ref*> refs;
     703                 :             :                 // Gather a list of up to 15 (or up to 255) Ref pointers.
     704         [ +  + ]:       15094 :                 auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15);
     705         [ +  - ]:        9295 :                 refs.resize(count);
     706         [ +  + ]:      295362 :                 for (size_t i = 0; i < count; ++i) {
     707                 :      286067 :                     refs[i] = pick_fn();
     708                 :             :                 }
     709                 :             :                 // Their order should not matter, shuffle them.
     710                 :        9295 :                 std::shuffle(refs.begin(), refs.end(), rng);
     711                 :             :                 // Invoke the real function.
     712                 :        9295 :                 auto result = real->CountDistinctClusters(refs, use_main);
     713                 :             :                 // Build a set with representatives of the clusters the Refs occur in in the
     714                 :             :                 // simulated graph. For each, remember the lowest-index transaction SimPos in the
     715                 :             :                 // cluster.
     716                 :        9295 :                 SimTxGraph::SetType sim_reps;
     717         [ +  + ]:      295362 :                 for (auto ref : refs) {
     718                 :             :                     // Skip Refs that do not occur in the simulated graph.
     719                 :      286067 :                     auto simpos = sel_sim.Find(ref);
     720         [ +  + ]:      286067 :                     if (simpos == SimTxGraph::MISSING) continue;
     721                 :             :                     // Find the component that includes ref.
     722                 :      181869 :                     auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
     723                 :             :                     // Remember the lowest-index SimPos in component, as a representative for it.
     724         [ -  + ]:      363738 :                     assert(component.Any());
     725                 :      181869 :                     sim_reps.Set(component.First());
     726                 :             :                 }
     727                 :             :                 // Compare the number of deduplicated representatives with the value returned by
     728                 :             :                 // the real function.
     729         [ -  + ]:        9295 :                 assert(result == sim_reps.Count());
     730                 :        9295 :                 break;
     731         [ +  + ]:      427363 :             } else if (command-- == 0) {
     732                 :             :                 // DoWork.
     733         [ +  + ]:       27069 :                 uint64_t iters = provider.ConsumeIntegralInRange<uint64_t>(0, alt ? 10000 : 255);
     734                 :       16811 :                 bool ret = real->DoWork(iters);
     735                 :       16811 :                 uint64_t iters_for_optimal{0};
     736         [ +  + ]:       39000 :                 for (unsigned level = 0; level < sims.size(); ++level) {
     737                 :             :                     // DoWork() will not optimize oversized levels, or the main level if a builder
     738                 :             :                     // is present. Note that this impacts the DoWork() return value, as true means
     739                 :             :                     // that non-optimal clusters may remain within such oversized or builder-having
     740                 :             :                     // levels.
     741   [ +  -  +  + ]:       22189 :                     if (sims[level].IsOversized()) continue;
     742   [ +  +  +  + ]:       13821 :                     if (level == 0 && !block_builders.empty()) continue;
     743                 :             :                     // If neither of the two above conditions holds, and DoWork() returned true,
     744                 :             :                     // then the level is optimal.
     745         [ +  + ]:        9283 :                     if (ret) {
     746                 :        9065 :                         sims[level].real_is_optimal = true;
     747                 :             :                     }
     748                 :             :                     // Compute how many iterations would be needed to make everything optimal.
     749   [ +  -  +  + ]:       94018 :                     for (auto component : sims[level].GetComponents()) {
     750                 :       84735 :                         auto iters_opt_this_cluster = MaxOptimalLinearizationIters(component.Count());
     751         [ +  + ]:       84735 :                         if (iters_opt_this_cluster > acceptable_iters) {
     752                 :             :                             // If the number of iterations required to linearize this cluster
     753                 :             :                             // optimally exceeds acceptable_iters, DoWork() may process it in two
     754                 :             :                             // stages: once to acceptable, and once to optimal.
     755                 :       19341 :                             iters_for_optimal += iters_opt_this_cluster + acceptable_iters;
     756                 :             :                         } else {
     757                 :       65394 :                             iters_for_optimal += iters_opt_this_cluster;
     758                 :             :                         }
     759                 :        9283 :                     }
     760                 :             :                 }
     761         [ +  + ]:       16811 :                 if (!ret) {
     762                 :             :                     // DoWork can only have more work left if the requested number of iterations
     763                 :             :                     // was insufficient to linearize everything optimally within the levels it is
     764                 :             :                     // allowed to touch.
     765         [ -  + ]:         191 :                     assert(iters <= iters_for_optimal);
     766                 :             :                 }
     767                 :             :                 break;
     768   [ +  +  +  -  :      401257 :             } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
          +  +  +  -  +  
                +  +  + ]
     769                 :             :                 // GetMainStagingDiagrams()
     770                 :        3346 :                 auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
     771                 :        3346 :                 auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});
     772                 :        3346 :                 auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});
     773                 :        3346 :                 auto real_gain = real_sum_staged - real_sum_main;
     774         [ +  - ]:        3346 :                 auto sim_gain = sims[1].SumAll() - sims[0].SumAll();
     775                 :             :                 // Just check that the total fee gained/lost and size gained/lost according to the
     776                 :             :                 // diagram matches the difference in these values in the simulated graph. A more
     777                 :             :                 // complete check of the GetMainStagingDiagrams result is performed at the end.
     778         [ +  - ]:        3346 :                 assert(sim_gain == real_gain);
     779                 :             :                 // Check that the feerates in each diagram are monotonically decreasing.
     780         [ +  + ]:       13748 :                 for (size_t i = 1; i < real_main_diagram.size(); ++i) {
     781         [ -  + ]:       10402 :                     assert(FeeRateCompare(real_main_diagram[i], real_main_diagram[i - 1]) <= 0);
     782                 :             :                 }
     783         [ +  + ]:       34971 :                 for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
     784         [ -  + ]:       31625 :                     assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
     785                 :             :                 }
     786                 :        3346 :                 break;
     787   [ +  +  +  -  :      401257 :             } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
             +  +  +  + ]
     788                 :             :                 // GetBlockBuilder.
     789         [ +  - ]:        4913 :                 block_builders.emplace_back(real->GetBlockBuilder());
     790                 :        4913 :                 break;
     791   [ +  +  +  + ]:      392998 :             } else if (!block_builders.empty() && command-- == 0) {
     792                 :             :                 // ~BlockBuilder.
     793                 :        2050 :                 block_builders.erase(block_builders.begin() + builder_idx);
     794                 :             :                 break;
     795   [ +  +  +  + ]:      390948 :             } else if (!block_builders.empty() && command-- == 0) {
     796                 :             :                 // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
     797                 :        8125 :                 auto& builder_data = block_builders[builder_idx];
     798                 :        8125 :                 auto new_included = builder_data.included;
     799                 :        8125 :                 auto new_done = builder_data.done;
     800                 :        8125 :                 auto chunk = builder_data.builder->GetCurrentChunk();
     801         [ +  + ]:        8125 :                 if (chunk) {
     802                 :             :                     // Chunk feerates must be monotonously decreasing.
     803         [ +  + ]:        3846 :                     if (!builder_data.last_feerate.IsEmpty()) {
     804         [ -  + ]:        2543 :                         assert(!(chunk->second >> builder_data.last_feerate));
     805                 :             :                     }
     806                 :        3846 :                     builder_data.last_feerate = chunk->second;
     807                 :             :                     // Verify the contents of GetCurrentChunk.
     808                 :        3846 :                     FeePerWeight sum_feerate;
     809         [ +  + ]:        8108 :                     for (TxGraph::Ref* ref : chunk->first) {
     810                 :             :                         // Each transaction in the chunk must exist in the main graph.
     811                 :        4262 :                         auto simpos = main_sim.Find(ref);
     812         [ -  + ]:        4262 :                         assert(simpos != SimTxGraph::MISSING);
     813                 :             :                         // Verify the claimed chunk feerate.
     814                 :        4262 :                         sum_feerate += main_sim.graph.FeeRate(simpos);
     815                 :             :                         // Make sure no transaction is reported twice.
     816         [ -  + ]:        4262 :                         assert(!new_done[simpos]);
     817                 :        4262 :                         new_done.Set(simpos);
     818                 :             :                         // The concatenation of all included transactions must be topologically valid.
     819                 :        4262 :                         new_included.Set(simpos);
     820         [ -  + ]:        8524 :                         assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
     821                 :             :                     }
     822         [ +  - ]:        3846 :                     assert(sum_feerate == chunk->second);
     823                 :             :                 } else {
     824                 :             :                     // When we reach the end, if nothing was skipped, the entire graph should have
     825                 :             :                     // been reported.
     826         [ +  + ]:        4279 :                     if (builder_data.done == builder_data.included) {
     827         [ -  + ]:        3570 :                         assert(builder_data.done.Count() == main_sim.GetTransactionCount());
     828                 :             :                     }
     829                 :             :                 }
     830                 :             :                 // Possibly invoke GetCurrentChunk() again, which should give the same result.
     831         [ +  + ]:        8125 :                 if ((orig_command % 7) >= 5) {
     832                 :        1289 :                     auto chunk2 = builder_data.builder->GetCurrentChunk();
     833         [ -  + ]:        1289 :                     assert(chunk == chunk2);
     834                 :        1289 :                 }
     835                 :             :                 // Skip or include.
     836         [ +  + ]:        8125 :                 if ((orig_command % 5) >= 3) {
     837                 :             :                     // Skip.
     838                 :        2009 :                     builder_data.builder->Skip();
     839                 :             :                 } else {
     840                 :             :                     // Include.
     841                 :        6116 :                     builder_data.builder->Include();
     842                 :        6116 :                     builder_data.included = new_included;
     843                 :             :                 }
     844                 :        8125 :                 builder_data.done = new_done;
     845                 :        8125 :                 break;
     846   [ +  -  +  +  :      390948 :             } else if (!main_sim.IsOversized() && command-- == 0) {
                   +  + ]
     847                 :             :                 // GetWorstMainChunk.
     848         [ +  + ]:       16451 :                 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
     849                 :             :                 // Just do some sanity checks here. Consistency with GetBlockBuilder is checked
     850                 :             :                 // below.
     851         [ +  + ]:       16451 :                 if (main_sim.GetTransactionCount() == 0) {
     852         [ -  + ]:        3796 :                     assert(worst_chunk.empty());
     853         [ -  + ]:        3796 :                     assert(worst_chunk_feerate.IsEmpty());
     854                 :             :                 } else {
     855         [ -  + ]:       12655 :                     assert(!worst_chunk.empty());
     856                 :       12655 :                     SimTxGraph::SetType done;
     857                 :       12655 :                     FeePerWeight sum;
     858         [ +  + ]:       28530 :                     for (TxGraph::Ref* ref : worst_chunk) {
     859                 :             :                         // Each transaction in the chunk must exist in the main graph.
     860                 :       15875 :                         auto simpos = main_sim.Find(ref);
     861         [ -  + ]:       15875 :                         assert(simpos != SimTxGraph::MISSING);
     862                 :       15875 :                         sum += main_sim.graph.FeeRate(simpos);
     863                 :             :                         // Make sure the chunk contains no duplicate transactions.
     864         [ -  + ]:       15875 :                         assert(!done[simpos]);
     865                 :       15875 :                         done.Set(simpos);
     866                 :             :                         // All elements are preceded by all their descendants.
     867         [ -  + ]:       31750 :                         assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
     868                 :             :                     }
     869         [ +  - ]:       12655 :                     assert(sum == worst_chunk_feerate);
     870                 :             :                 }
     871                 :       16451 :                 break;
     872   [ +  +  +  +  :      382823 :             } else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) {
                   +  + ]
     873                 :             :                 // Trim.
     874         [ +  - ]:       14636 :                 bool was_oversized = top_sim.IsOversized();
     875                 :       14636 :                 auto removed = real->Trim();
     876                 :             :                 // Verify that something was removed if and only if there was an oversized cluster.
     877         [ -  + ]:       14636 :                 assert(was_oversized == !removed.empty());
     878         [ +  + ]:       14636 :                 if (!was_oversized) break;
     879                 :        3166 :                 auto removed_set = top_sim.MakeSet(removed);
     880                 :             :                 // The removed set must contain all its own descendants.
     881         [ +  + ]:       17992 :                 for (auto simpos : removed_set) {
     882         [ -  + ]:       29652 :                     assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
     883                 :             :                 }
     884                 :             :                 // Something from every oversized cluster should have been removed, and nothing
     885                 :             :                 // else.
     886   [ +  -  -  + ]:        3166 :                 assert(top_sim.MatchesOversizedClusters(removed_set));
     887                 :             : 
     888                 :             :                 // Apply all removals to the simulation, and verify the result is no longer
     889                 :             :                 // oversized. Don't query the real graph for oversizedness; it is compared
     890                 :             :                 // against the simulation anyway later.
     891         [ +  + ]:       17992 :                 for (auto simpos : removed_set) {
     892         [ +  - ]:       14826 :                     top_sim.RemoveTransaction(top_sim.GetRef(simpos));
     893                 :             :                 }
     894   [ +  -  -  + ]:        3166 :                 assert(!top_sim.IsOversized());
     895                 :             :                 break;
     896   [ +  +  +  + ]:      413972 :             } else if ((block_builders.empty() || sims.size() > 1) &&
     897   [ +  +  +  +  :      399336 :                        top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) {
          +  -  +  +  +  
                      + ]
     898                 :             :                 // Trim (special case which avoids apparent cycles in the implicit approximate
     899                 :             :                 // dependency graph constructed inside the Trim() implementation). This is worth
     900                 :             :                 // testing separately, because such cycles cannot occur in realistic scenarios,
     901                 :             :                 // but this is hard to replicate in general in this fuzz test.
     902                 :             : 
     903                 :             :                 // First, we need to have dependencies applied and linearizations fixed to avoid
     904                 :             :                 // circular dependencies in implied graph; trigger it via whatever means.
     905                 :        1313 :                 real->CountDistinctClusters({}, false);
     906                 :             : 
     907                 :             :                 // Gather the current clusters.
     908         [ +  - ]:        1313 :                 auto clusters = top_sim.GetComponents();
     909                 :             : 
     910                 :             :                 // Merge clusters randomly until at least one oversized one appears.
     911                 :        1313 :                 bool made_oversized = false;
     912                 :        1313 :                 auto merges_left = clusters.size() - 1;
     913         [ +  + ]:       20135 :                 while (merges_left > 0) {
     914                 :       18822 :                     --merges_left;
     915                 :             :                     // Find positions of clusters in the clusters vector to merge together.
     916                 :       18822 :                     auto par_cl = rng.randrange(clusters.size());
     917                 :       18822 :                     auto chl_cl = rng.randrange(clusters.size() - 1);
     918                 :       18822 :                     chl_cl += (chl_cl >= par_cl);
     919         [ +  - ]:       18822 :                     Assume(chl_cl != par_cl);
     920                 :             :                     // Add between 1 and 3 dependencies between them. As all are in the same
     921                 :             :                     // direction (from the child cluster to parent cluster), no cycles are possible,
     922                 :             :                     // regardless of what internal topology Trim() uses as approximation within the
     923                 :             :                     // clusters.
     924                 :       18822 :                     int num_deps = rng.randrange(3) + 1;
     925         [ +  + ]:       56338 :                     for (int i = 0; i < num_deps; ++i) {
     926                 :             :                         // Find a parent transaction in the parent cluster.
     927                 :       37516 :                         auto par_idx = rng.randrange(clusters[par_cl].Count());
     928                 :       37516 :                         SimTxGraph::Pos par_pos = 0;
     929         [ +  - ]:       80203 :                         for (auto j : clusters[par_cl]) {
     930         [ +  + ]:       80203 :                             if (par_idx == 0) {
     931                 :             :                                 par_pos = j;
     932                 :             :                                 break;
     933                 :             :                             }
     934                 :       42687 :                             --par_idx;
     935                 :             :                         }
     936                 :             :                         // Find a child transaction in the child cluster.
     937                 :       37516 :                         auto chl_idx = rng.randrange(clusters[chl_cl].Count());
     938                 :       37516 :                         SimTxGraph::Pos chl_pos = 0;
     939         [ +  - ]:       79564 :                         for (auto j : clusters[chl_cl]) {
     940         [ +  + ]:       79564 :                             if (chl_idx == 0) {
     941                 :             :                                 chl_pos = j;
     942                 :             :                                 break;
     943                 :             :                             }
     944                 :       42048 :                             --chl_idx;
     945                 :             :                         }
     946                 :             :                         // Add dependency to both simulation and real TxGraph.
     947                 :       37516 :                         auto par_ref = top_sim.GetRef(par_pos);
     948                 :       37516 :                         auto chl_ref = top_sim.GetRef(chl_pos);
     949                 :       37516 :                         top_sim.AddDependency(par_ref, chl_ref);
     950                 :       37516 :                         real->AddDependency(*par_ref, *chl_ref);
     951                 :             :                     }
     952                 :             :                     // Compute the combined cluster.
     953                 :       18822 :                     auto par_cluster = clusters[par_cl];
     954                 :       18822 :                     auto chl_cluster = clusters[chl_cl];
     955                 :       18822 :                     auto new_cluster = par_cluster | chl_cluster;
     956                 :             :                     // Remove the parent and child cluster from clusters.
     957   [ +  +  +  + ]:      486507 :                     std::erase_if(clusters, [&](const auto& cl) noexcept { return cl == par_cluster || cl == chl_cluster; });
     958                 :             :                     // Add the combined cluster.
     959         [ +  - ]:       18822 :                     clusters.push_back(new_cluster);
     960                 :             :                     // If this is the first merge that causes an oversized cluster to appear, pick
     961                 :             :                     // a random number of further merges to appear.
     962         [ +  + ]:       18822 :                     if (!made_oversized) {
     963                 :       12848 :                         made_oversized = new_cluster.Count() > max_cluster_count;
     964         [ +  + ]:       12848 :                         if (!made_oversized) {
     965                 :       11549 :                             FeeFrac total;
     966         [ +  + ]:       80721 :                             for (auto i : new_cluster) total += top_sim.graph.FeeRate(i);
     967         [ +  + ]:       11549 :                             if (uint32_t(total.size) > max_cluster_size) made_oversized = true;
     968                 :             :                         }
     969         [ +  + ]:       12848 :                         if (made_oversized) merges_left = rng.randrange(clusters.size());
     970                 :             :                     }
     971                 :             :                 }
     972                 :             : 
     973                 :             :                 // Determine an upper bound on how many transactions are removed.
     974                 :        1313 :                 uint32_t max_removed = 0;
     975         [ +  + ]:        8622 :                 for (auto& cluster : clusters) {
     976                 :             :                     // Gather all transaction sizes in the to-be-combined cluster.
     977                 :        7309 :                     std::vector<uint32_t> sizes;
     978   [ +  -  +  + ]:       42399 :                     for (auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size);
     979                 :        7309 :                     auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0});
     980                 :             :                     // Sort from large to small.
     981                 :        7309 :                     std::sort(sizes.begin(), sizes.end(), std::greater{});
     982                 :             :                     // In the worst case, only the smallest transactions are removed.
     983   [ +  +  +  + ]:       17434 :                     while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) {
     984                 :       10125 :                         sum_sizes -= sizes.back();
     985                 :       10125 :                         sizes.pop_back();
     986                 :       10125 :                         ++max_removed;
     987                 :             :                     }
     988                 :        7309 :                 }
     989                 :             : 
     990                 :             :                 // Invoke Trim now on the definitely-oversized txgraph.
     991                 :        1313 :                 auto removed = real->Trim();
     992                 :             :                 // Verify that the number of removals is within range.
     993         [ -  + ]:        1313 :                 assert(removed.size() >= 1);
     994         [ -  + ]:        1313 :                 assert(removed.size() <= max_removed);
     995                 :             :                 // The removed set must contain all its own descendants.
     996                 :        1313 :                 auto removed_set = top_sim.MakeSet(removed);
     997         [ +  + ]:        9365 :                 for (auto simpos : removed_set) {
     998         [ -  + ]:       16104 :                     assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
     999                 :             :                 }
    1000                 :             :                 // Something from every oversized cluster should have been removed, and nothing
    1001                 :             :                 // else.
    1002   [ +  -  -  + ]:        1313 :                 assert(top_sim.MatchesOversizedClusters(removed_set));
    1003                 :             : 
    1004                 :             :                 // Apply all removals to the simulation, and verify the result is no longer
    1005                 :             :                 // oversized. Don't query the real graph for oversizedness; it is compared
    1006                 :             :                 // against the simulation anyway later.
    1007         [ +  + ]:        9365 :                 for (auto simpos : removed_set) {
    1008         [ +  - ]:        8052 :                     top_sim.RemoveTransaction(top_sim.GetRef(simpos));
    1009                 :             :                 }
    1010   [ +  -  -  + ]:        1313 :                 assert(!top_sim.IsOversized());
    1011                 :        1313 :                 break;
    1012                 :        1313 :             }
    1013                 :             :         }
    1014                 :             :     }
    1015                 :             : 
    1016                 :             :     // After running all modifications, perform an internal sanity check (before invoking
    1017                 :             :     // inspectors that may modify the internal state).
    1018         [ +  - ]:        4234 :     real->SanityCheck();
    1019                 :             : 
    1020   [ +  -  +  + ]:        4234 :     if (!sims[0].IsOversized()) {
    1021                 :             :         // If the main graph is not oversized, verify the total ordering implied by
    1022                 :             :         // CompareMainOrder.
    1023                 :             :         // First construct two distinct randomized permutations of the positions in sims[0].
    1024                 :        3069 :         std::vector<SimTxGraph::Pos> vec1;
    1025   [ +  -  +  + ]:       48741 :         for (auto i : sims[0].graph.Positions()) vec1.push_back(i);
    1026                 :        3069 :         std::shuffle(vec1.begin(), vec1.end(), rng);
    1027         [ +  - ]:        3069 :         auto vec2 = vec1;
    1028                 :        3069 :         std::shuffle(vec2.begin(), vec2.end(), rng);
    1029         [ +  + ]:        3069 :         if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
    1030                 :             :         // Sort both according to CompareMainOrder. By having randomized starting points, the order
    1031                 :             :         // of CompareMainOrder invocations is somewhat randomized as well.
    1032                 :      518518 :         auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {
    1033                 :      515449 :             return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
    1034                 :        3069 :         };
    1035                 :        3069 :         std::sort(vec1.begin(), vec1.end(), cmp);
    1036                 :        3069 :         std::sort(vec2.begin(), vec2.end(), cmp);
    1037                 :             : 
    1038                 :             :         // Verify the resulting orderings are identical. This could only fail if the ordering was
    1039                 :             :         // not total.
    1040         [ -  + ]:        3069 :         assert(vec1 == vec2);
    1041                 :             : 
    1042                 :             :         // Verify that the ordering is topological.
    1043                 :        3069 :         auto todo = sims[0].graph.Positions();
    1044         [ +  + ]:       48741 :         for (auto i : vec1) {
    1045                 :       45672 :             todo.Reset(i);
    1046         [ -  + ]:       91344 :             assert(!sims[0].graph.Ancestors(i).Overlaps(todo));
    1047                 :             :         }
    1048         [ -  + ]:        3069 :         assert(todo.None());
    1049                 :             : 
    1050                 :             :         // If the real graph claims to be optimal (the last DoWork() call returned true), verify
    1051                 :             :         // that calling Linearize on it does not improve it further.
    1052         [ +  + ]:        3069 :         if (sims[0].real_is_optimal) {
    1053                 :         247 :             auto real_diagram = ChunkLinearization(sims[0].graph, vec1);
    1054                 :         247 :             auto [sim_lin, _optimal, _cost] = Linearize(sims[0].graph, 300000, rng.rand64(), vec1);
    1055                 :         247 :             auto sim_diagram = ChunkLinearization(sims[0].graph, sim_lin);
    1056         [ +  - ]:         247 :             auto cmp = CompareChunks(real_diagram, sim_diagram);
    1057         [ -  + ]:         247 :             assert(cmp == 0);
    1058                 :         247 :         }
    1059                 :             : 
    1060                 :             :         // For every transaction in the total ordering, find a random one before it and after it,
    1061                 :             :         // and compare their chunk feerates, which must be consistent with the ordering.
    1062         [ +  + ]:       48741 :         for (size_t pos = 0; pos < vec1.size(); ++pos) {
    1063                 :       45672 :             auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
    1064         [ +  + ]:       45672 :             if (pos > 0) {
    1065                 :       43052 :                 size_t before = rng.randrange<size_t>(pos);
    1066                 :       43052 :                 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
    1067         [ -  + ]:       43052 :                 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
    1068                 :             :             }
    1069         [ +  + ]:       45672 :             if (pos + 1 < vec1.size()) {
    1070                 :       43052 :                 size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);
    1071                 :       43052 :                 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
    1072         [ -  + ]:       43052 :                 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
    1073                 :             :             }
    1074                 :             :         }
    1075                 :             : 
    1076                 :             :         // The same order should be obtained through a BlockBuilder as implied by CompareMainOrder,
    1077                 :             :         // if nothing is skipped.
    1078                 :        3069 :         auto builder = real->GetBlockBuilder();
    1079                 :        3069 :         std::vector<SimTxGraph::Pos> vec_builder;
    1080                 :        3069 :         std::vector<TxGraph::Ref*> last_chunk;
    1081                 :        3069 :         FeePerWeight last_chunk_feerate;
    1082         [ +  + ]:       88239 :         while (auto chunk = builder->GetCurrentChunk()) {
    1083                 :       42585 :             FeePerWeight sum;
    1084         [ +  + ]:       88257 :             for (TxGraph::Ref* ref : chunk->first) {
    1085                 :             :                 // The reported chunk feerate must match the chunk feerate obtained by asking
    1086                 :             :                 // it for each of the chunk's transactions individually.
    1087         [ +  - ]:       45672 :                 assert(real->GetMainChunkFeerate(*ref) == chunk->second);
    1088                 :             :                 // Verify the chunk feerate matches the sum of the reported individual feerates.
    1089                 :       45672 :                 sum += real->GetIndividualFeerate(*ref);
    1090                 :             :                 // Chunks must contain transactions that exist in the graph.
    1091                 :       45672 :                 auto simpos = sims[0].Find(ref);
    1092         [ -  + ]:       45672 :                 assert(simpos != SimTxGraph::MISSING);
    1093         [ +  - ]:       45672 :                 vec_builder.push_back(simpos);
    1094                 :             :             }
    1095         [ +  - ]:       42585 :             assert(sum == chunk->second);
    1096                 :       42585 :             last_chunk = std::move(chunk->first);
    1097                 :       42585 :             last_chunk_feerate = chunk->second;
    1098                 :       42585 :             builder->Include();
    1099                 :       42585 :         }
    1100         [ -  + ]:        3069 :         assert(vec_builder == vec1);
    1101                 :             : 
    1102                 :             :         // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse.
    1103                 :        3069 :         std::reverse(last_chunk.begin(), last_chunk.end());
    1104         [ -  + ]:        3069 :         auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
    1105         [ -  + ]:        3069 :         assert(last_chunk == worst_chunk);
    1106         [ +  - ]:        3069 :         assert(last_chunk_feerate == worst_chunk_feerate);
    1107                 :             : 
    1108                 :             :         // Check that the implied ordering gives rise to a combined diagram that matches the
    1109                 :             :         // diagram constructed from the individual cluster linearization chunkings.
    1110         [ +  - ]:        3069 :         auto main_real_diagram = get_diagram_fn(/*main_only=*/true);
    1111                 :        3069 :         auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1);
    1112   [ +  -  -  + ]:        3069 :         assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0);
    1113                 :             : 
    1114   [ +  +  +  -  :        3069 :         if (sims.size() >= 2 && !sims[1].IsOversized()) {
                   +  + ]
    1115                 :             :             // When the staging graph is not oversized as well, call GetMainStagingDiagrams, and
    1116                 :             :             // fully verify the result.
    1117                 :        1068 :             auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
    1118                 :             :             // Check that the feerates in each diagram are monotonically decreasing.
    1119         [ +  + ]:        6115 :             for (size_t i = 1; i < main_cmp_diagram.size(); ++i) {
    1120         [ -  + ]:        5047 :                 assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
    1121                 :             :             }
    1122         [ +  + ]:       15713 :             for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
    1123         [ -  + ]:       14645 :                 assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
    1124                 :             :             }
    1125                 :             :             // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that
    1126                 :             :             // std::set_difference can be used on them below. The exact ordering does not matter
    1127                 :             :             // here, but it has to be consistent with the one used in main_real_diagram and
    1128                 :             :             // stage_real_diagram).
    1129                 :        1068 :             std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
    1130                 :        1068 :             std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});
    1131                 :             :             // Find the chunks that appear in main_diagram but are missing from main_cmp_diagram.
    1132                 :             :             // This is allowed, because GetMainStagingDiagrams omits clusters in main unaffected
    1133                 :             :             // by staging.
    1134                 :        1068 :             std::vector<FeeFrac> missing_main_cmp;
    1135         [ +  - ]:        1068 :             std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
    1136                 :             :                                 main_cmp_diagram.begin(), main_cmp_diagram.end(),
    1137                 :             :                                 std::inserter(missing_main_cmp, missing_main_cmp.end()),
    1138                 :             :                                 std::greater{});
    1139         [ -  + ]:        1068 :             assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
    1140                 :             :             // Do the same for chunks in stage_diagram missing from stage_cmp_diagram.
    1141         [ +  - ]:        1068 :             auto stage_real_diagram = get_diagram_fn(/*main_only=*/false);
    1142                 :        1068 :             std::vector<FeeFrac> missing_stage_cmp;
    1143         [ +  - ]:        1068 :             std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
    1144                 :             :                                 stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
    1145                 :             :                                 std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
    1146                 :             :                                 std::greater{});
    1147         [ -  + ]:        1068 :             assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
    1148                 :             :             // The missing chunks must be equal across main & staging (otherwise they couldn't have
    1149                 :             :             // been omitted).
    1150         [ -  + ]:        1068 :             assert(missing_main_cmp == missing_stage_cmp);
    1151                 :             : 
    1152                 :             :             // The missing part must include at least all transactions in staging which have not been
    1153                 :             :             // modified, or been in a cluster together with modified transactions, since they were
    1154                 :             :             // copied from main. Note that due to the reordering of removals w.r.t. dependency
    1155                 :             :             // additions, it is possible that the real implementation found more unaffected things.
    1156                 :        1068 :             FeeFrac missing_real;
    1157         [ +  + ]:        9295 :             for (const auto& feerate : missing_main_cmp) missing_real += feerate;
    1158                 :        1068 :             FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
    1159                 :             :             // Note that missing_real.fee < missing_expected.fee is possible to due the presence of
    1160                 :             :             // negative-fee transactions.
    1161         [ -  + ]:        1068 :             assert(missing_real.size >= missing_expected.size);
    1162                 :        2136 :         }
    1163                 :        3069 :     }
    1164                 :             : 
    1165         [ -  + ]:        4234 :     assert(real->HaveStaging() == (sims.size() > 1));
    1166                 :             : 
    1167                 :             :     // Try to run a full comparison, for both main_only=false and main_only=true in TxGraph
    1168                 :             :     // inspector functions that support both.
    1169         [ +  + ]:       12702 :     for (int main_only = 0; main_only < 2; ++main_only) {
    1170         [ +  + ]:        8468 :         auto& sim = main_only ? sims[0] : sims.back();
    1171                 :             :         // Compare simple properties of the graph with the simulation.
    1172   [ +  -  -  + ]:        8468 :         assert(real->IsOversized(main_only) == sim.IsOversized());
    1173         [ -  + ]:        8468 :         assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
    1174                 :             :         // If the graph (and the simulation) are not oversized, perform a full comparison.
    1175   [ +  -  +  + ]:        8468 :         if (!sim.IsOversized()) {
    1176                 :        6031 :             auto todo = sim.graph.Positions();
    1177                 :             :             // Iterate over all connected components of the resulting (simulated) graph, each of which
    1178                 :             :             // should correspond to a cluster in the real one.
    1179         [ +  + ]:      174684 :             while (todo.Any()) {
    1180                 :       81311 :                 auto component = sim.graph.FindConnectedComponent(todo);
    1181                 :       81311 :                 todo -= component;
    1182                 :             :                 // Iterate over the transactions in that component.
    1183         [ +  + ]:      182873 :                 for (auto i : component) {
    1184                 :             :                     // Check its individual feerate against simulation.
    1185         [ +  - ]:      101562 :                     assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
    1186                 :             :                     // Check its ancestors against simulation.
    1187                 :      101562 :                     auto expect_anc = sim.graph.Ancestors(i);
    1188                 :      101562 :                     auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
    1189         [ -  + ]:      101562 :                     assert(anc.Count() <= max_cluster_count);
    1190         [ -  + ]:      101562 :                     assert(anc == expect_anc);
    1191                 :             :                     // Check its descendants against simulation.
    1192                 :      101562 :                     auto expect_desc = sim.graph.Descendants(i);
    1193                 :      101562 :                     auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
    1194         [ -  + ]:      101562 :                     assert(desc.Count() <= max_cluster_count);
    1195         [ -  + ]:      101562 :                     assert(desc == expect_desc);
    1196                 :             :                     // Check the cluster the transaction is part of.
    1197                 :      101562 :                     auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
    1198         [ -  + ]:      101562 :                     assert(cluster.size() <= max_cluster_count);
    1199         [ -  + ]:      101562 :                     assert(sim.MakeSet(cluster) == component);
    1200                 :             :                     // Check that the cluster is reported in a valid topological order (its
    1201                 :             :                     // linearization).
    1202                 :      101562 :                     std::vector<DepGraphIndex> simlin;
    1203                 :      101562 :                     SimTxGraph::SetType done;
    1204                 :      101562 :                     uint64_t total_size{0};
    1205         [ +  + ]:      622570 :                     for (TxGraph::Ref* ptr : cluster) {
    1206                 :      521008 :                         auto simpos = sim.Find(ptr);
    1207         [ -  + ]:     1042016 :                         assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
    1208                 :      521008 :                         done.Set(simpos);
    1209         [ -  + ]:     1042016 :                         assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
    1210         [ +  - ]:      521008 :                         simlin.push_back(simpos);
    1211                 :      521008 :                         total_size += sim.graph.FeeRate(simpos).size;
    1212                 :             :                     }
    1213                 :             :                     // Check cluster size.
    1214         [ -  + ]:      101562 :                     assert(total_size <= max_cluster_size);
    1215                 :             :                     // Construct a chunking object for the simulated graph, using the reported cluster
    1216                 :             :                     // linearization as ordering, and compare it against the reported chunk feerates.
    1217   [ +  +  +  + ]:      101562 :                     if (sims.size() == 1 || main_only) {
    1218                 :       73440 :                         cluster_linearize::LinearizationChunking simlinchunk(sim.graph, simlin);
    1219                 :       73440 :                         DepGraphIndex idx{0};
    1220         [ +  + ]:      288935 :                         for (unsigned chunknum = 0; chunknum < simlinchunk.NumChunksLeft(); ++chunknum) {
    1221                 :      215495 :                             auto chunk = simlinchunk.GetChunk(chunknum);
    1222                 :             :                             // Require that the chunks of cluster linearizations are connected (this must
    1223                 :             :                             // be the case as all linearizations inside are PostLinearized).
    1224         [ -  + ]:      215495 :                             assert(sim.graph.IsConnected(chunk.transactions));
    1225                 :             :                             // Check the chunk feerates of all transactions in the cluster.
    1226         [ +  + ]:     1059178 :                             while (chunk.transactions.Any()) {
    1227         [ -  + ]:      314094 :                                 assert(chunk.transactions[simlin[idx]]);
    1228                 :      314094 :                                 chunk.transactions.Reset(simlin[idx]);
    1229         [ +  - ]:      314094 :                                 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
    1230                 :      314094 :                                 ++idx;
    1231                 :             :                             }
    1232                 :             :                         }
    1233                 :       73440 :                     }
    1234                 :      101562 :                 }
    1235                 :             :             }
    1236                 :             :         }
    1237                 :             :     }
    1238                 :             : 
    1239                 :             :     // Sanity check again (because invoking inspectors may modify internal unobservable state).
    1240         [ +  - ]:        4234 :     real->SanityCheck();
    1241                 :             : 
    1242                 :             :     // Kill the block builders.
    1243                 :        4234 :     block_builders.clear();
    1244                 :             :     // Kill the TxGraph object.
    1245         [ +  - ]:        4234 :     real.reset();
    1246                 :             :     // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs
    1247                 :             :     // can outlive the TxGraph that created them.
    1248                 :        4234 :     sims.clear();
    1249                 :        4234 : }
        

Generated by: LCOV version 2.0-1