Building a wallet payment

501                });
502
503        const Txid& truc_txid = highest_value_truc_tx->first;
504        for (const auto& [type, output] : unconfirmed_truc_coins) {
505            if (output.outpoint.hash == truc_txid) {
506                    result.Add(type, output);
507            }
508        }
509    }
510
511    if (feerate.has_value()) {
512        std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().calculateIndividualBumpFees(outpoints, feerate.value());
513
514        for (auto& [_, outputs] : result.coins) {
515            for (auto& output : outputs) {
516                output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint));
517            }
518        }
519    }
520
521    return result;
522}
523
524const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const COutPoint& outpoint)
525{
526    AssertLockHeld(wallet.cs_wallet);
527    const CWalletTx* wtx{Assert(wallet.GetWalletTx(outpoint.hash))};
528
529    const CTransaction* ptx = wtx->GetTx().get();
530    int n = outpoint.n;
531    while (OutputIsChange(wallet, ptx->vout[n]) && ptx->vin.size() > 0) {
532        const COutPoint& prevout = ptx->vin[0].prevout;
533        const CWalletTx* it = wallet.GetWalletTx(prevout.hash);
534        if (!it || it->GetTx()->vout.size() <= prevout.n ||
535            !wallet.IsMine(it->GetTx()->vout[prevout.n])) {
536            break;
537        }
538        ptx = it->GetTx().get();
539        n = prevout.n;
540    }
541    return ptx->vout[n];
542}
543
544std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet)
545{
546    AssertLockHeld(wallet.cs_wallet);
547
548    std::map<CTxDestination, std::vector<COutput>> result;
549
550    CCoinControl coin_control;
551    CoinFilterParams coins_params;
552    coins_params.skip_locked = false;
553    for (const COutput& coin : AvailableCoins(wallet, &coin_control, /*feerate=*/std::nullopt, coins_params).All()) {
554        CTxDestination address;
555        if (!ExtractDestination(FindNonChangeParentOutput(wallet, coin.outpoint).scriptPubKey, address)) {
556            // For backwards compatibility, we convert P2PK output scripts into PKHash destinations
557            if (auto pk_dest = std::get_if<PubKeyDestination>(&address)) {
558                address = PKHash(pk_dest->GetPubKey());
559            } else {
560                continue;
561            }
562        }
563        result[address].emplace_back(coin);
564    }
565    return result;
566}
567
568FilteredOutputGroups GroupOutputs(const CWallet& wallet,
569                          const CoinsResult& coins,
570                          const CoinSelectionParams& coin_sel_params,
571                          const std::vector<SelectionFilter>& filters,
572                          std::vector<OutputGroup>& ret_discarded_groups)
573{
574    FilteredOutputGroups filtered_groups;
575
576    if (!coin_sel_params.m_avoid_partial_spends) {
577        // Allowing partial spends means no grouping. Each COutput gets its own OutputGroup
578        for (const auto& [type, outputs] : coins.coins) {
579            for (const COutput& output : outputs) {
580                // Get mempool info
581                size_t ancestors, cluster_count;
582                wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, cluster_count);
583
584                // Create a new group per output and add it to the all groups vector
585                OutputGroup group(coin_sel_params);
586                group.Insert(std::make_shared<COutput>(output), ancestors, cluster_count);
587
588                // Each filter maps to a different set of groups
589                bool accepted = false;
590                for (const auto& sel_filter : filters) {
591                    const auto& filter = sel_filter.filter;
592                    if (!group.EligibleForSpending(filter)) continue;
593                    filtered_groups[filter].Push(group, type, /*insert_positive=*/true, /*insert_mixed=*/true);
594                    accepted = true;
595                }
596                if (!accepted) ret_discarded_groups.emplace_back(group);
597            }
598        }
599        return filtered_groups;
600    }
601
602    // We want to combine COutputs that have the same scriptPubKey into single OutputGroups
603    // except when there are more than OUTPUT_GROUP_MAX_ENTRIES COutputs grouped in an OutputGroup.
604    // To do this, we maintain a map where the key is the scriptPubKey and the value is a vector of OutputGroups.
605    // For each COutput, we check if the scriptPubKey is in the map, and if it is, the COutput is added
606    // to the last OutputGroup in the vector for the scriptPubKey. When the last OutputGroup has
607    // OUTPUT_GROUP_MAX_ENTRIES COutputs, a new OutputGroup is added to the end of the vector.
608    typedef std::map<std::pair<CScript, OutputType>, std::vector<OutputGroup>> ScriptPubKeyToOutgroup;
609    const auto& insert_output = [&](
610            const std::shared_ptr<COutput>& output, OutputType type, size_t ancestors, size_t cluster_count,
611            ScriptPubKeyToOutgroup& groups_map) {
612        std::vector<OutputGroup>& groups = groups_map[std::make_pair(output->txout.scriptPubKey,type)];
613
614        if (groups.size() == 0) {
615            // No OutputGroups for this scriptPubKey yet, add one
616            groups.emplace_back(coin_sel_params);
617        }
618
619        // Get the last OutputGroup in the vector so that we can add the COutput to it
620        // A pointer is used here so that group can be reassigned later if it is full.
621        OutputGroup* group = &groups.back();
622
623        // Check if this OutputGroup is full. We limit to OUTPUT_GROUP_MAX_ENTRIES when using -avoidpartialspends
624        // to avoid surprising users with very high fees.
625        if (group->m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {
626            // The last output group is full, add a new group to the vector and use that group for the insertion
627            groups.emplace_back(coin_sel_params);
628            group = &groups.back();
629        }
630
631        group->Insert(output, ancestors, cluster_count);
632    };
633
634    ScriptPubKeyToOutgroup spk_to_groups_map;
635    ScriptPubKeyToOutgroup spk_to_positive_groups_map;
636    for (const auto& [type, outs] : coins.coins) {
637        for (const COutput& output : outs) {
638            size_t ancestors, cluster_count;
639            wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, cluster_count);
640
641            const auto& shared_output = std::make_shared<COutput>(output);
642            // Filter for positive only before adding the output
643            if (output.GetEffectiveValue() > 0) {
644                insert_output(shared_output, type, ancestors, cluster_count, spk_to_positive_groups_map);
645            }
646
647            // 'All' groups
648            insert_output(shared_output, type, ancestors, cluster_count, spk_to_groups_map);
649        }
650    }
651
652    // Now we go through the entire maps and pull out the OutputGroups
653    const auto& push_output_groups = [&](const ScriptPubKeyToOutgroup& groups_map, bool positive_only) {
654        for (const auto& [script, groups] : groups_map) {
655            // Go through the vector backwards. This allows for the first item we deal with being the partial group.
656            for (auto group_it = groups.rbegin(); group_it != groups.rend(); group_it++) {
657                const OutputGroup& group = *group_it;
658
659                // Each filter maps to a different set of groups
660                bool accepted = false;
661                for (const auto& sel_filter : filters) {
662                    const auto& filter = sel_filter.filter;
663                    if (!group.EligibleForSpending(filter)) continue;
664
665                    // Don't include partial groups if there are full groups too and we don't want partial groups
666                    if (group_it == groups.rbegin() && groups.size() > 1 && !filter.m_include_partial_groups) {
667                        continue;
668                    }
669
670                    OutputType type = script.second;
671                    // Either insert the group into the positive-only groups or the mixed ones.
672                    filtered_groups[filter].Push(group, type, positive_only, /*insert_mixed=*/!positive_only);
673                    accepted = true;
674                }
675                if (!accepted) ret_discarded_groups.emplace_back(group);
676            }
677        }
678    };
679
680    push_output_groups(spk_to_groups_map, /*positive_only=*/ false);
681    push_output_groups(spk_to_positive_groups_map, /*positive_only=*/ true);
682
683    return filtered_groups;
684}
685
686FilteredOutputGroups GroupOutputs(const CWallet& wallet,
687                                  const CoinsResult& coins,
688                                  const CoinSelectionParams& params,
689                                  const std::vector<SelectionFilter>& filters)
690{
691    std::vector<OutputGroup> unused;
692    return GroupOutputs(wallet, coins, params, filters, unused);
693}
694
695// Returns true if the result contains an error and the message is not empty
696static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
697
698util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups,
699                               const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types)
700{
701    // Run coin selection on each OutputType and compute the Waste Metric
702    std::vector<SelectionResult> results;
703    for (auto& [type, group] : groups.groups_by_type) {
704        auto result{ChooseSelectionResult(chain, nTargetValue, group, coin_selection_params)};
705        // If any specific error message appears here, then something particularly wrong happened.
706        if (HasErrorMsg(result)) return result; // So let's return the specific error.
707        // Append the favorable result.
708        if (result) results.push_back(*result);
709    }
710    // If we have at least one solution for funding the transaction without mixing, choose the minimum one according to waste metric
711    // and return the result
712    if (results.size() > 0) return *std::min_element(results.begin(), results.end());
713
714    // If we can't fund the transaction from any individual OutputType, run coin selection one last time
715    // over all available coins, which would allow mixing.
716    // If TypesCount() <= 1, there is nothing to mix.
717    if (allow_mixed_output_types && groups.TypesCount() > 1) {
718        return ChooseSelectionResult(chain, nTargetValue, groups.all_groups, coin_selection_params);
719    }
720    // Either mixing is not allowed and we couldn't find a solution from any single OutputType, or mixing was allowed and we still couldn't
721    // find a solution using all available coins
722    return util::Error();
723};
724
725util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params)
726{
727    // Vector of results. We will choose the best one based on waste.
728    std::vector<SelectionResult> results;
729    std::vector<util::Result<SelectionResult>> errors;
730    auto append_error = [&] (util::Result<SelectionResult>&& result) {
731        // If any specific error message appears here, then something different from a simple "no selection found" happened.
732        // Let's save it, so it can be retrieved to the user if no other selection algorithm succeeded.
733        if (HasErrorMsg(result)) {
734            errors.emplace_back(std::move(result));
735        }
736    };
737
738    // Maximum allowed weight for selected coins.
739    int max_transaction_weight = coin_selection_params.m_max_tx_weight.value_or(MAX_STANDARD_TX_WEIGHT);
740    int tx_weight_no_input = coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR;
741    int max_selection_weight = max_transaction_weight - tx_weight_no_input;
742    if (max_selection_weight <= 0) {
743        return util::Error{_("Maximum transaction weight is less than transaction weight without inputs")};
744    }
745
746    // SFFO frequently causes issues in the context of changeless input sets: skip BnB when SFFO is active
747    if (!coin_selection_params.m_subtract_fee_outputs) {
748        if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change, max_selection_weight)}) {
749            results.push_back(*bnb_result);
750        } else append_error(std::move(bnb_result));