Repository: bitcoin/bitcoin
File: src/test/fuzz/cluster_linearize.cpp (C++)

Code before:

        // If picked was provided, the component must include it.
        if (picked) assert(component[*picked]);

        // If todo is the entire graph, and the entire graph is connected, then the component must
        // be the entire graph.
        if (todo == depgraph.Positions()) {
            assert((component == todo) == depgraph.IsConnected());
        }

        // If subset is connected, then component must match subset.
        assert((component == todo) == depgraph.IsConnected(todo));

        // The component cannot have any ancestors or descendants outside of component but in todo.
        for (auto i : component) {
            assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
            assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
        }

        // Starting from any component element, we must be able to reach every element.
        for (auto i : component) {
            // Start with just i as reachable.
            TestBitSet reachable = TestBitSet::Singleton(i);
            // Add in-todo descendants and ancestors to reachable until it does not change anymore.
            while (true) {
                TestBitSet new_reachable = reachable;
                for (auto j : new_reachable) {
                    new_reachable |= depgraph.Ancestors(j) & todo;
                    new_reachable |= depgraph.Descendants(j) & todo;
                }
                if (new_reachable == reachable) break;
                reachable = new_reachable;
            }
            // Verify that the result is the entire component.
            assert(component == reachable);
        }

        // Construct an arbitrary subset of todo.
        uint64_t subset_bits{0};
        try {
            reader >> VARINT(subset_bits);
        } catch (const std::ios_base::failure&) {}
        TestBitSet subset;
        for (DepGraphIndex i : depgraph.Positions()) {
            if (todo[i]) {
                if (subset_bits & 1) subset.Set(i);
                subset_bits >>= 1;
            }
        }
        // Which must be non-empty.
        if (subset.None()) subset = TestBitSet::Singleton(todo.First());

Review comment (suggestion):
Maybe indicate that we only compare `SimpleCandidateFinder` with `ExhaustiveCandidateFinder` when we optimally found a subset and the cluster size is small.

Code after:
            continue;
        }
        if ((command % 3) <= 1 && num_tx_sim > 0) {
            // AddDependencies.
            DepGraphIndex child = idx_fn();
            auto parents = subset_fn();
            // Apply to DepGraph.
            real.AddDependencies(parents, child);
            // Apply to sim.
            sim[child]->second |= parents;
            continue;
        }
        if (num_tx_sim > 0) {
            // Remove transactions.
            auto del = set_fn();
            // Propagate all ancestry information before deleting anything in the simulation (as
            // intermediary transactions may be deleted which impact connectivity).
            anc_update_fn();
            // Compare the state of the transactions being deleted.
            for (auto i : del) check_fn(i);
            // Apply to DepGraph.
            real.RemoveTransactions(del);
            // Apply to sim.
            for (DepGraphIndex i = 0; i < sim.size(); ++i) {
                if (sim[i].has_value()) {
                    if (del[i]) {
                        --num_tx_sim;
                        sim[i] = std::nullopt;
                    } else {
                        sim[i]->second -= del;
                    }
                }
            }
            continue;
        }
        // This should be unreachable (one of the 3 above actions should always be possible).
        assert(false);
    }

    // Compare the real obtained depgraph against the simulation.
    anc_update_fn();
    for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
    assert(real.TxCount() == num_tx_sim);
    // Sanity check the result (which includes round-tripping serialization, if applicable).
    SanityCheck(real);
}

FUZZ_TARGET(clusterlin_depgraph_serialization)
{
    // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.