Repository: bitcoin/bitcoin
File: src/wallet/test/coinselector_tests.cpp (C++)

Code before:
                                                    const node::NodeContext& m_node,
                                                    int max_selection_weight,
                                                    std::function<CoinsResult(CWallet&)> coin_setup)
{
    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
    CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors
    Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups;
    return SelectCoinsSRD(group.positive_group, target, cs_params.m_change_fee, cs_params.rng_fast, max_selection_weight);
}

BOOST_AUTO_TEST_CASE(srd_tests)
{
    // Test SRD:
    // 1) Insufficient funds, select all provided coins and fail.
    // 2) Exceeded max weight, coin selection always surpasses the max allowed weight.
    // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not)

    FastRandomContext rand;
    CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag.
            rand,
            /*change_output_size=*/34,
            /*change_spend_size=*/68,
            /*min_change_target=*/CENT,
            /*effective_feerate=*/CFeeRate(0),
            /*long_term_feerate=*/CFeeRate(0),
            /*discard_feerate=*/CFeeRate(0),
            /*tx_noinputs_size=*/10 + 34, // static header size + output size
            /*avoid_partial=*/false,
    };

    {
        // #########################################################
        // 1) Insufficient funds, select all provided coins and fail
        // #########################################################
        CAmount target = 49.5L * COIN;
        int max_selection_weight = 10000; // high enough to not fail for this reason.
        const auto& res = SelectCoinsSRD(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
            CoinsResult available_coins;
            for (int j = 0; j < 10; ++j) {
                add_coin(available_coins, wallet, CAmount(1 * COIN));
                add_coin(available_coins, wallet, CAmount(2 * COIN));
            }
            return available_coins;
        });
        BOOST_CHECK(!res);
        BOOST_CHECK(util::ErrorString(res).empty()); // empty means "insufficient funds"
    }

    {
        // ###########################
        // 2) Test max weight exceeded

Review comment (suggestion):
I was pondering what the first eligible solution would be and expect that it would be (notation is **amount, vsize**):

1.0000'0011, 107
1.0000'0006, 102
1.0000'0005, 101
1.0000'0004, 100
1.0000'0003, 99
1.0000'0002, 98
1.0000'0001, 97
1.0000'0000, 96

Printing the final `curr_selection` on the bailout due to exceeding the permitted tries, I got this instead, which is clearly still far off from the eligible selection:

100000016, 112
100000015, 111
100000011, 107
100000010, 106
100000007, 103
100000004, 100
100000002, 98
100000001, 97

Code after:
        // #################################################################################################################
        CAmount target = 8 * COIN;
        int max_selection_weight = 3200; // WU
        dummy_params.m_min_change_target = 0;
        const auto& result_a = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
            CoinsResult doppelgangers;
            for (int i = 0; i < 18; ++i) {
                add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
            }
            return doppelgangers;
        });
        BOOST_CHECK(result_a);
        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
        for (int i = 0; i < 8; ++i) {
          add_coin(1 * COIN + i, 0, expected_result);
        }
        BOOST_CHECK(EquivalentResult(expected_result, *result_a));
        // Demonstrate a solution is found before the attempts limit is reached.
        size_t expected_attempts = 87'525;
        BOOST_CHECK_MESSAGE(result_a->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result_a->GetSelectionsEvaluated()));

        // Adding one more doppelganger causes the attempt limit to be reached before finding a solution.
        const auto& result_b = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
            CoinsResult doppelgangers;
            for (int i = 0; i < 19; ++i) {
                add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
            }
            return doppelgangers;
        });
        BOOST_CHECK(!result_b);
    }
}

static util::Result<SelectionResult> SelectCoinsSRD(const CAmount& target,
                                                    const CoinSelectionParams& cs_params,
                                                    const node::NodeContext& m_node,
                                                    int max_selection_weight,
                                                    std::function<CoinsResult(CWallet&)> coin_setup)
{
    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
    CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors
    Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups;
    return SelectCoinsSRD(group.positive_group, target, cs_params.m_change_fee, cs_params.rng_fast, max_selection_weight);
}

BOOST_AUTO_TEST_CASE(srd_tests)
{
    // Test SRD:
    // 1) Insufficient funds, select all provided coins and fail.
    // 2) Exceeded max weight, coin selection always surpasses the max allowed weight.
    // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not)