Function TestOptimalLinearization

src/test/cluster_linearize_tests.cpp:57–121

}

void TestOptimalLinearization(std::span<const uint8_t> enc, std::initializer_list<DepGraphIndex> optimal_linearization)
{
    DepGraphIndex tx_count = 0;
    FastRandomContext rng;

    auto test_fn = [&]<typename SetType>() {
        DepGraph<SetType> depgraph;
        SpanReader reader(enc);
        reader >> Using<DepGraphFormatter>(depgraph);
        SanityCheck(depgraph);
        std::vector<DepGraphIndex> lin;
        for (int iter = 0; iter < 200; ++iter) {
            bool opt;
            uint64_t cost{0};
            bool is_topological{true};
            switch (rng.randrange(4)) {
            case 0:
                // Use empty input linearization.
                lin.clear();
                break;
            case 1:
                // Reuse previous optimal linearization as input.
                break;
            case 2:
                // Construct random valid input linearization.
                std::shuffle(lin.begin(), lin.end(), rng);
                std::sort(lin.begin(), lin.end(), [&](auto a, auto b) { return depgraph.Ancestors(a).Count() < depgraph.Ancestors(b).Count(); });
                break;
            case 3:
                // Construct random potentially invalid input linearization.
                std::shuffle(lin.begin(), lin.end(), rng);
                is_topological = false;
                break;
            }
            std::tie(lin, opt, cost) = Linearize(
                /*depgraph=*/depgraph,
                /*max_cost=*/1000000000000,
                /*rng_seed=*/rng.rand64(),
                /*fallback_order=*/IndexTxOrder{},
                /*old_linearization=*/lin,
                /*is_topological=*/is_topological);
            BOOST_CHECK(opt);
            BOOST_CHECK(cost <= MaxOptimalLinearizationCost(depgraph.TxCount()));
            SanityCheck(depgraph, lin);
            BOOST_CHECK(std::ranges::equal(lin, optimal_linearization));
        }
        tx_count = depgraph.PositionRange();
    };

    // Always run with 64-bit set types
    // - The native one that will be used on this platform.
    test_fn.template operator()<BitSet<64>>();
    // - The one used on 32-bit platforms.
    test_fn.template operator()<bitset_detail::MultiIntBitSet<uint32_t, 2>>();
    // - An 8-bit one, which is maximally different in terms of bitset behavior.
    test_fn.template operator()<bitset_detail::MultiIntBitSet<uint8_t, 8>>();

    // Also run with 32-bit set types if the cluster doesn't use indexes above 31.