cluster_linearize_tests.cpp
1 // Copyright (c) The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <cluster_linearize.h> 6 #include <test/util/cluster_linearize.h> 7 #include <test/util/setup_common.h> 8 #include <util/bitset.h> 9 #include <util/strencodings.h> 10 11 #include <vector> 12 13 #include <boost/test/unit_test.hpp> 14 15 BOOST_FIXTURE_TEST_SUITE(cluster_linearize_tests, BasicTestingSetup) 16 17 using namespace cluster_linearize; 18 19 namespace { 20 21 /** Special magic value that indicates to TestDepGraphSerialization that a cluster entry represents 22 * a hole. */ 23 constexpr std::pair<FeeFrac, TestBitSet> HOLE{FeeFrac{0, 0x3FFFFF}, {}}; 24 25 template<typename SetType> 26 void TestDepGraphSerialization(const std::vector<std::pair<FeeFrac, SetType>>& cluster, const std::string& hexenc) 27 { 28 // Construct DepGraph from cluster argument. 29 DepGraph<SetType> depgraph; 30 SetType holes; 31 for (DepGraphIndex i = 0; i < cluster.size(); ++i) { 32 depgraph.AddTransaction(cluster[i].first); 33 if (cluster[i] == HOLE) holes.Set(i); 34 } 35 for (DepGraphIndex i = 0; i < cluster.size(); ++i) { 36 depgraph.AddDependencies(cluster[i].second, i); 37 } 38 depgraph.RemoveTransactions(holes); 39 40 // There may be multiple serializations of the same graph, but DepGraphFormatter's serializer 41 // only produces one of those. Verify that hexenc matches that canonical serialization. 42 std::vector<unsigned char> encoding; 43 VectorWriter writer(encoding, 0); 44 writer << Using<DepGraphFormatter>(depgraph); 45 BOOST_CHECK_EQUAL(HexStr(encoding), hexenc); 46 47 // Test that deserializing that encoding yields depgraph. This is effectively already implied 48 // by the round-trip test above (if depgraph is acyclic), but verify it explicitly again here. 49 SpanReader reader(encoding); 50 DepGraph<SetType> depgraph_read; 51 reader >> Using<DepGraphFormatter>(depgraph_read); 52 BOOST_CHECK(depgraph == depgraph_read); 53 } 54 55 } // namespace 56 57 BOOST_AUTO_TEST_CASE(depgraph_ser_tests) 58 { 59 // Empty cluster. 60 TestDepGraphSerialization<TestBitSet>( 61 {}, 62 "00" /* end of graph */); 63 64 // Transactions: A(fee=0,size=1). 65 TestDepGraphSerialization<TestBitSet>( 66 {{{0, 1}, {}}}, 67 "01" /* A size */ 68 "00" /* A fee */ 69 "00" /* A insertion position (no skips): A */ 70 "00" /* end of graph */); 71 72 // Transactions: A(fee=42,size=11), B(fee=-13,size=7), B depends on A. 73 TestDepGraphSerialization<TestBitSet>( 74 {{{42, 11}, {}}, {{-13, 7}, {0}}}, 75 "0b" /* A size */ 76 "54" /* A fee */ 77 "00" /* A insertion position (no skips): A */ 78 "07" /* B size */ 79 "19" /* B fee */ 80 "00" /* B->A dependency (no skips) */ 81 "00" /* B insertion position (no skips): A,B */ 82 "00" /* end of graph */); 83 84 // Transactions: A(64,128), B(128,256), C(1,1), C depends on A and B. 85 TestDepGraphSerialization<TestBitSet>( 86 {{{64, 128}, {}}, {{128, 256}, {}}, {{1, 1}, {0, 1}}}, 87 "8000" /* A size */ 88 "8000" /* A fee */ 89 "00" /* A insertion position (no skips): A */ 90 "8100" /* B size */ 91 "8100" /* B fee */ 92 "01" /* B insertion position (skip B->A dependency): A,B */ 93 "01" /* C size */ 94 "02" /* C fee */ 95 "00" /* C->B dependency (no skips) */ 96 "00" /* C->A dependency (no skips) */ 97 "00" /* C insertion position (no skips): A,B,C */ 98 "00" /* end of graph */); 99 100 // Transactions: A(-57,113), B(57,114), C(-58,115), D(58,116). Deps: B->A, C->A, D->C, in order 101 // [B,A,C,D]. This exercises non-topological ordering (internally serialized as A,B,C,D). 102 TestDepGraphSerialization<TestBitSet>( 103 {{{57, 114}, {1}}, {{-57, 113}, {}}, {{-58, 115}, {1}}, {{58, 116}, {2}}}, 104 "71" /* A size */ 105 "71" /* A fee */ 106 "00" /* A insertion position (no skips): A */ 107 "72" /* B size */ 108 "72" /* B fee */ 109 "00" /* B->A dependency (no skips) */ 110 "01" /* B insertion position (skip A): B,A */ 111 "73" /* C size */ 112 "73" /* C fee */ 113 "01" /* C->A dependency (skip C->B dependency) */ 114 "00" /* C insertion position (no skips): B,A,C */ 115 "74" /* D size */ 116 "74" /* D fee */ 117 "00" /* D->C dependency (no skips) */ 118 "01" /* D insertion position (skip D->B dependency, D->A is implied): B,A,C,D */ 119 "00" /* end of graph */); 120 121 // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D. 122 // In order: [D,A,B,E,C]. Internally serialized in order A,B,C,D,E. 123 TestDepGraphSerialization<TestBitSet>( 124 {{{1, 3}, {1, 2}}, {{1, 2}, {}}, {{3, 1}, {}}, {{1, 1}, {0}}, {{2, 1}, {1}}}, 125 "02" /* A size */ 126 "02" /* A fee */ 127 "00" /* A insertion position (no skips): A */ 128 "01" /* B size */ 129 "06" /* B fee */ 130 "01" /* B insertion position (skip B->A dependency): A,B */ 131 "01" /* C size */ 132 "04" /* C fee */ 133 "01" /* C->A dependency (skip C->B dependency) */ 134 "00" /* C insertion position (no skips): A,B,C */ 135 "03" /* D size */ 136 "02" /* D fee */ 137 "01" /* D->B dependency (skip D->C dependency) */ 138 "00" /* D->A dependency (no skips) */ 139 "03" /* D insertion position (skip C,B,A): D,A,B,C */ 140 "01" /* E size */ 141 "02" /* E fee */ 142 "00" /* E->D dependency (no skips) */ 143 "02" /* E insertion position (skip E->C dependency, E->B and E->A are implied, 144 skip insertion C): D,A,B,E,C */ 145 "00" /* end of graph */ 146 ); 147 148 // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D. 149 // In order: [_, D, _, _, A, _, B, _, _, _, E, _, _, C] (_ being holes). Internally serialized 150 // in order A,B,C,D,E. 151 TestDepGraphSerialization<TestBitSet>( 152 {HOLE, {{1, 3}, {4, 6}}, HOLE, HOLE, {{1, 2}, {}}, HOLE, {{3, 1}, {}}, HOLE, HOLE, HOLE, {{1, 1}, {1}}, HOLE, HOLE, {{2, 1}, {4}}}, 153 "02" /* A size */ 154 "02" /* A fee */ 155 "03" /* A insertion position (3 holes): _, _, _, A */ 156 "01" /* B size */ 157 "06" /* B fee */ 158 "06" /* B insertion position (skip B->A dependency, skip 4 inserts, add 1 hole): _, _, _, A, _, B */ 159 "01" /* C size */ 160 "04" /* C fee */ 161 "01" /* C->A dependency (skip C->B dependency) */ 162 "0b" /* C insertion position (skip 6 inserts, add 5 holes): _, _, _, A, _, B, _, _, _, _, _, C */ 163 "03" /* D size */ 164 "02" /* D fee */ 165 "01" /* D->B dependency (skip D->C dependency) */ 166 "00" /* D->A dependency (no skips) */ 167 "0b" /* D insertion position (skip 11 inserts): _, D, _, _, A, _, B, _, _, _, _, _, C */ 168 "01" /* E size */ 169 "02" /* E fee */ 170 "00" /* E->D dependency (no skips) */ 171 "04" /* E insertion position (skip E->C dependency, E->B and E->A are implied, skip 3 172 inserts): _, D, _, _, A, _, B, _, _, _, E, _, _, C */ 173 "00" /* end of graph */ 174 ); 175 } 176 177 BOOST_AUTO_TEST_SUITE_END()