[refactor] move package checks into helper functions

This allows IsSorted() and IsConsistent() to be used by themselves.
IsSorted() with a precomputed set is used so that we don't create this
set multiple times.

2 files changed, 94 insertions, 29 deletions

diff --git a/src/policy/packages.cpp b/src/policy/packages.cpp
index 47a9274a31..3660995bc8 100644
--- a/src/policy/packages.cpp
+++ b/src/policy/packages.cpp
@@ -6,16 +6,77 @@
 #include <policy/policy.h>
 #include <primitives/transaction.h>
 #include <uint256.h>
-#include <util/hasher.h>
+#include <util/check.h>
 
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <memory>
 #include <numeric>
-#include <unordered_set>
 
-bool CheckPackage(const Package& txns, PackageValidationState& state)
+/** 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) {
+        for (const auto& input : tx->vin) {
+            if (later_txids.find(input.prevout.hash) != later_txids.end()) {
+                // 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) {
+        if (tx->vin.empty()) {
+            // 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) {
+            if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
+                // 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 CheckPackage(const Package& txns, PackageValidationState& state, bool require_sorted)
 {
     const unsigned int package_count = txns.size();
 
@@ -30,10 +91,6 @@ bool CheckPackage(const Package& txns, PackageValidationState& state)
         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-too-large");
     }
 
-    // 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).
     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(); });
@@ -44,30 +101,17 @@ bool CheckPackage(const Package& txns, PackageValidationState& state)
         return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-contains-duplicates");
     }
 
-    for (const auto& tx : txns) {
-        for (const auto& input : tx->vin) {
-            if (later_txids.find(input.prevout.hash) != later_txids.end()) {
-                // The parent is a subsequent transaction in the package.
-                return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
-            }
-        }
-        later_txids.erase(tx->GetHash());
+    // 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)) {
+        return state.Invalid(PackageValidationResult::PCKG_POLICY, "package-not-sorted");
     }
 
     // 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) {
-        for (const auto& input : tx->vin) {
-            if (inputs_seen.find(input.prevout) != inputs_seen.end()) {
-                // This input is also present in another tx in the package.
-                return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
-            }
-        }
-        // 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; });
+    if (!IsConsistentPackage(txns)) {
+        return state.Invalid(PackageValidationResult::PCKG_POLICY, "conflict-in-package");
     }
     return true;
 }
diff --git a/src/policy/packages.h b/src/policy/packages.h
index cf37857e4b..1ca1a962ba 100644
--- a/src/policy/packages.h
+++ b/src/policy/packages.h
@@ -9,8 +9,10 @@
 #include <consensus/validation.h>
 #include <policy/policy.h>
 #include <primitives/transaction.h>
+#include <util/hasher.h>
 
 #include <cstdint>
+#include <unordered_set>
 #include <vector>
 
 /** Default maximum number of transactions in a package. */
@@ -49,13 +51,32 @@ using Package = std::vector<CTransactionRef>;
 
 class PackageValidationState : public ValidationState<PackageValidationResult> {};
 
+/** If any direct dependencies exist between transactions (i.e. a child spending the output of a
+ * parent), checks that all parents appear somewhere in the list before their respective children.
+ * No other ordering is enforced. This function cannot detect indirect dependencies (e.g. a
+ * transaction's grandparent if its parent is not present).
+ * @returns true if sorted. False if any tx spends the output of a tx that appears later in txns.
+ */
+bool IsTopoSortedPackage(const Package& txns);
+
+/** Checks that these transactions don't conflict, i.e., spend the same prevout. This includes
+ * checking that there are no duplicate transactions. Since these checks require looking at the inputs
+ * of a transaction, returns false immediately if any transactions have empty vin.
+ *
+ * Does not check consistency of a transaction with oneself; does not check if a transaction spends
+ * the same prevout multiple times (see bad-txns-inputs-duplicate in CheckTransaction()).
+ *
+ * @returns true if there are no conflicts. False if any two transactions spend the same prevout.
+ * */
+bool IsConsistentPackage(const Package& txns);
+
 /** Context-free package policy checks:
  * 1. The number of transactions cannot exceed MAX_PACKAGE_COUNT.
  * 2. The total weight cannot exceed MAX_PACKAGE_WEIGHT.
  * 3. If any dependencies exist between transactions, parents must appear before children.
  * 4. Transactions cannot conflict, i.e., spend the same inputs.
  */
-bool CheckPackage(const Package& txns, PackageValidationState& state);
+bool CheckPackage(const Package& txns, PackageValidationState& state, bool require_sorted);
 
 /** Context-free check that a package is exactly one child and its parents; not all parents need to
  * be present, but the package must not contain any transactions that are not the child's parents.