// Copyright (c) 2021-2022 The Bitcoin Core developers

// Distributed under the MIT software license, see the accompanying

// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <policy/packages.h>

#include <policy/policy.h>

#include <primitives/transaction.h>

#include <uint256.h>

#include <util/check.h>

#include <algorithm>

#include <cassert>

#include <iterator>

#include <memory>

#include <numeric>

/** IsTopoSortedPackage where a set of txids has been pre-populated. The set is assumed to be correct and

 * is mutated within this function (even if return value is false). */

bool IsTopoSortedPackage(const Package& txns, std::unordered_set<uint256, SaltedTxidHasher>& later_txids)

{

    // Avoid misusing this function: later_txids should contain the txids of txns.

    Assume(txns.size() == later_txids.size());

    // later_txids always contains the txids of this transaction and the ones that come later in

    // txns. If any transaction's input spends a tx in that set, we've found a parent placed later

    // than its child.

    for (const auto& tx : txns) {

  Branch (27:25): [True: 8.87k, False: 4.43k]

        for (const auto& input : tx->vin) {

  Branch (28:32): [True: 19.9k, False: 8.87k]

            if (later_txids.find(input.prevout.hash) != later_txids.end()) {

  Branch (29:17): [True: 0, False: 19.9k]

                // The parent is a subsequent transaction in the package.

                return false;

            }

        }

        // Avoid misusing this function: later_txids must contain every tx.

        Assume(later_txids.erase(tx->GetHash()) == 1);

    }

    // Avoid misusing this function: later_txids should have contained the txids of txns.

    Assume(later_txids.empty());

    return true;

}

bool IsTopoSortedPackage(const Package& txns)

{

    std::unordered_set<uint256, SaltedTxidHasher> later_txids;

    std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),

                   [](const auto& tx) { return tx->GetHash(); });

    return IsTopoSortedPackage(txns, later_txids);

}

bool IsConsistentPackage(const Package& txns)

{

    // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.

    std::unordered_set<COutPoint, SaltedOutpointHasher> inputs_seen;

    for (const auto& tx : txns) {

  Branch (56:25): [True: 8.87k, False: 4.42k]

        if (tx->vin.empty()) {

  Branch (57:13): [True: 0, False: 8.87k]

            // This function checks consistency based on inputs, and we can't do that if there are

            // no inputs. Duplicate empty transactions are also not consistent with one another.

            // This doesn't create false negatives, as unconfirmed transactions are not allowed to

            // have no inputs.

            return false;

        }

        for (const auto& input : tx->vin) {

  Branch (64:32): [True: 19.8k, False: 8.86k]

            if (inputs_seen.find(input.prevout) != inputs_seen.end()) {

  Branch (65:17): [True: 12, False: 19.8k]

                // This input is also present in another tx in the package.

                return false;

            }

        }

        // Batch-add all the inputs for a tx at a time. If we added them 1 at a time, we could

        // catch duplicate inputs within a single tx.  This is a more severe, consensus error,

        // and we want to report that from CheckTransaction instead.

        std::transform(tx->vin.cbegin(), tx->vin.cend(), std::inserter(inputs_seen, inputs_seen.end()),

                       [](const auto& input) { return input.prevout; });

    }

    return true;

}

bool IsWellFormedPackage(const Package& txns, PackageValidationState& state, bool require_sorted)

{

    const unsigned int package_count = txns.size();

    if (package_count > MAX_PACKAGE_COUNT) {

  Branch (83:9): [True: 0, False: 4.46k]

        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-many-transactions");

    }

    const int64_t total_weight = std::accumulate(txns.cbegin(), txns.cend(), 0,

                               [](int64_t sum, const auto& tx) { return sum + GetTransactionWeight(*tx); });

    // If the package only contains 1 tx, it's better to report the policy violation on individual tx weight.

    if (package_count > 1 && total_weight > MAX_PACKAGE_WEIGHT) {

  Branch (90:9): [True: 4.46k, False: 0]
  Branch (90:30): [True: 29, False: 4.43k]

        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");

    }

    std::unordered_set<uint256, SaltedTxidHasher> later_txids;

    std::transform(txns.cbegin(), txns.cend(), std::inserter(later_txids, later_txids.end()),

                   [](const auto& tx) { return tx->GetHash(); });

    // Package must not contain any duplicate transactions, which is checked by txid. This also

    // includes transactions with duplicate wtxids and same-txid-different-witness transactions.

    if (later_txids.size() != txns.size()) {

  Branch (100:9): [True: 0, False: 4.43k]

        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");

    }

    // Require the package to be sorted in order of dependency, i.e. parents appear before children.

    // An unsorted package will fail anyway on missing-inputs, but it's better to quit earlier and

    // fail on something less ambiguous (missing-inputs could also be an orphan or trying to

    // spend nonexistent coins).

    if (require_sorted && !IsTopoSortedPackage(txns, later_txids)) {

  Branch (108:9): [True: 4.43k, False: 0]
  Branch (108:27): [True: 0, False: 4.43k]

        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");

    }

    // Don't allow any conflicting transactions, i.e. spending the same inputs, in a package.

    if (!IsConsistentPackage(txns)) {

  Branch (113:9): [True: 12, False: 4.42k]

        return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");

    }

    return true;

}

bool IsChildWithParents(const Package& package)

{

    assert(std::all_of(package.cbegin(), package.cend(), [](const auto& tx){return tx != nullptr;}));

  Branch (121:5): [True: 3.54k, False: 0]

    if (package.size() < 2) return false;

  Branch (122:9): [True: 0, False: 3.54k]

    // The package is expected to be sorted, so the last transaction is the child.

    const auto& child = package.back();

    std::unordered_set<uint256, SaltedTxidHasher> input_txids;

    std::transform(child->vin.cbegin(), child->vin.cend(),

                   std::inserter(input_txids, input_txids.end()),

                   [](const auto& input) { return input.prevout.hash; });

    // Every transaction must be a parent of the last transaction in the package.

    return std::all_of(package.cbegin(), package.cend() - 1,

                       [&input_txids](const auto& ptx) { return input_txids.count(ptx->GetHash()) > 0; });

}

bool IsChildWithParentsTree(const Package& package)

{

    if (!IsChildWithParents(package)) return false;

  Branch (138:9): [True: 0, False: 0]

    std::unordered_set<uint256, SaltedTxidHasher> parent_txids;

    std::transform(package.cbegin(), package.cend() - 1, std::inserter(parent_txids, parent_txids.end()),

                   [](const auto& ptx) { return ptx->GetHash(); });

    // Each parent must not have an input who is one of the other parents.

    return std::all_of(package.cbegin(), package.cend() - 1, [&](const auto& ptx) {

        for (const auto& input : ptx->vin) {

  Branch (144:32): [True: 0, False: 0]

            if (parent_txids.count(input.prevout.hash) > 0) return false;

  Branch (145:17): [True: 0, False: 0]

        }

        return true;

    });

}

uint256 GetPackageHash(const std::vector<CTransactionRef>& transactions)

{

    // Create a vector of the wtxids.

    std::vector<Wtxid> wtxids_copy;

    std::transform(transactions.cbegin(), transactions.cend(), std::back_inserter(wtxids_copy),

        [](const auto& tx){ return tx->GetWitnessHash(); });

    // Sort in ascending order

    std::sort(wtxids_copy.begin(), wtxids_copy.end(), [](const auto& lhs, const auto& rhs) {

        return std::lexicographical_compare(std::make_reverse_iterator(lhs.end()), std::make_reverse_iterator(lhs.begin()),

                                            std::make_reverse_iterator(rhs.end()), std::make_reverse_iterator(rhs.begin()));

    });

    // Get sha256 hash of the wtxids concatenated in this order

    HashWriter hashwriter;

    for (const auto& wtxid : wtxids_copy) {

  Branch (166:28): [True: 10.6k, False: 5.34k]

        hashwriter << wtxid;

    }

    return hashwriter.GetSHA256();

}