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

Code before:
            // For holes, add a dummy transaction which is deleted below, so that non-hole
            // transactions retain their position.
            depgraph_tree.AddTransaction(FeeFrac{});
        }
    }
    depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());

    if (direction & 1) {
        for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
            auto children = depgraph_gen.GetReducedChildren(i);
            if (children.Any()) {
                depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
            }
         }
    } else {
        for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
            auto parents = depgraph_gen.GetReducedParents(i);
            if (parents.Any()) {
                depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
            }
        }
    }

    // Retrieve a linearization from the fuzz input.
    std::vector<DepGraphIndex> linearization;
    linearization = ReadLinearization(depgraph_tree, reader);
    SanityCheck(depgraph_tree, linearization);

    // Produce a postlinearized version.
    auto post_linearization = linearization;
    PostLinearize(depgraph_tree, post_linearization);
    SanityCheck(depgraph_tree, post_linearization);

    // Compare diagrams.
    auto chunking = ChunkLinearization(depgraph_tree, linearization);
    auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
    auto cmp = CompareChunks(post_chunking, chunking);
    assert(cmp >= 0);

    // Verify that post-linearizing again does not change the diagram. The result must be identical
    // as post_linearization ought to be optimal already with a tree-structured graph.
    auto post_post_linearization = post_linearization;
    PostLinearize(depgraph_tree, post_linearization);
    SanityCheck(depgraph_tree, post_linearization);
    auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
    auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
    assert(cmp_post == 0);

    // Try to find an even better linearization directly. This must not change the diagram for the
    // same reason.
    auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);

Review comment (suggestion):
Should we also do more comparison when both are optimal, that the chunking matches, 
Edit disregard we do it below 👍🏾 

Code after:
        assert(optimal);
    }
    // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
    // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
    // bound for a whole linearization (summing for k=1..n) using the Python expression
    // [sum((k+3)//4 + int(math.sqrt(2**k)) + 1 for k in range(1, n + 1)) + (n**2 + 63) // 64 for n in range(0, 35)]:
    static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
        0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
        3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
        316629, 447712
    };
    if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
        Assume(optimal);
    }

    // If Linearize claims optimal result, run quality tests.
    if (optimal) {
        // It must be as good as SimpleLinearize.
        auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
        SanityCheck(depgraph, simple_linearization);
        auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
        auto cmp = CompareChunks(chunking, simple_chunking);
        assert(cmp >= 0);
        // If SimpleLinearize finds the optimal result too, they must be equal (if not,
        // SimpleLinearize is broken).
        if (simple_optimal) assert(cmp == 0);
        // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
        // chunking is claimed to be optimal, which implies minimal chunks).
        if (cmp == 0) assert(chunking.size() >= simple_chunking.size());

        // Compare with a linearization read from the fuzz input.
        auto read = ReadLinearization(depgraph, reader);
        auto read_chunking = ChunkLinearization(depgraph, read);
        auto cmp_read = CompareChunks(chunking, read_chunking);
        assert(cmp_read >= 0);
    }
}

FUZZ_TARGET(clusterlin_postlinearize)
{
    // Verify expected properties of PostLinearize() on arbitrary linearizations.

    // Retrieve a depgraph from the fuzz input.
    SpanReader reader(buffer);
    DepGraph<TestBitSet> depgraph;
    try {
        reader >> Using<DepGraphFormatter>(depgraph);
    } catch (const std::ios_base::failure&) {}

    // Retrieve a linearization from the fuzz input.
    std::vector<DepGraphIndex> linearization;