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

Code before:
            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
            for (int j = 0; j < 100; ++j) {
                // make a 100 unique coins only differing by one sat
                add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110);
            }
            return available_coins;
        });
        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
        add_coin(1 * COIN, 1, expected_result);
        add_coin(1 * COIN, 2, expected_result);
        BOOST_CHECK(EquivalentResult(expected_result, *res));
        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
        size_t expected_attempts = 7;
        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
    }
}

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)

    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,
    };

    {

Review comment (suggestion):
Maybe it'd be better to use `res_a`/`res_b` instead of `result_a`/`result_b` and `available_coins` instead of `doppelgangers` for naming consistency.

Code after:
            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
            for (int j = 0; j < 100; ++j) {
                // make a 100 unique coins only differing by one sat
                add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110);
            }
            return available_coins;
        });
        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
        add_coin(1 * COIN, 1, expected_result);
        add_coin(1 * COIN, 2, expected_result);
        BOOST_CHECK(EquivalentResult(expected_result, *res));
        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
        size_t expected_attempts = 7;
        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
    }

    {
        // #################################################################################################################
        // 8) Test input set that has a solution will not find a solution before reaching the attempt limit
        // #################################################################################################################
        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);
    }