chain_tests.cpp raw
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 <boost/test/unit_test.hpp>
6
7 #include <chain.h>
8 #include <test/util/setup_common.h>
9
10 #include <array>
11 #include <memory>
12
13 BOOST_FIXTURE_TEST_SUITE(chain_tests, BasicTestingSetup)
14
15 namespace {
16
17 const CBlockIndex* NaiveGetAncestor(const CBlockIndex* a, int height)
18 {
19 while (a->nHeight > height) {
20 a = a->pprev;
21 }
22 BOOST_REQUIRE_EQUAL(a->nHeight, height);
23 return a;
24 }
25
26 const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockIndex* b)
27 {
28 while (a->nHeight > b->nHeight) {
29 a = a->pprev;
30 }
31 while (b->nHeight > a->nHeight) {
32 b = b->pprev;
33 }
34 while (a != b) {
35 BOOST_REQUIRE_EQUAL(a->nHeight, b->nHeight);
36 a = a->pprev;
37 b = b->pprev;
38 }
39 BOOST_REQUIRE_EQUAL(a, b);
40 return a;
41 }
42
43 } // namespace
44
45 BOOST_AUTO_TEST_CASE(basic_tests)
46 {
47 // An empty chain
48 const CChain chain_0;
49 // A chain with 2 blocks
50 CChain chain_2;
51
52 CBlockIndex genesis;
53 genesis.nHeight = 0;
54 chain_2.SetTip(genesis);
55
56 CBlockIndex bi1;
57 bi1.pprev = &genesis;
58 bi1.nHeight = 1;
59 chain_2.SetTip(bi1);
60
61 BOOST_CHECK_EQUAL(chain_0.Height(), -1);
62 BOOST_CHECK_EQUAL(chain_2.Height(), 1);
63
64 BOOST_CHECK_EQUAL(chain_0.Tip(), nullptr);
65 BOOST_CHECK_EQUAL(chain_2.Tip(), &bi1);
66
67 // Indexer accessor: call with valid and invalid (low & high) values
68 BOOST_CHECK_EQUAL(chain_2[-1], nullptr);
69 BOOST_CHECK_EQUAL(chain_2[0], &genesis);
70 BOOST_CHECK_EQUAL(chain_2[1], &bi1);
71 BOOST_CHECK_EQUAL(chain_2[2], nullptr);
72
73 // Contains: call with contained & non-contained blocks
74 BOOST_CHECK(chain_2.Contains(genesis));
75 BOOST_CHECK(chain_2.Contains(bi1));
76 BOOST_CHECK(!chain_0.Contains(genesis));
77
78 // Call with non-tip & tip blocks
79 BOOST_CHECK_EQUAL(chain_2.Next(genesis), &bi1);
80 BOOST_CHECK_EQUAL(chain_2.Next(bi1), nullptr);
81 BOOST_CHECK_EQUAL(chain_0.Next(genesis), nullptr);
82
83 BOOST_CHECK_EQUAL(chain_2.Genesis(), &genesis);
84 BOOST_CHECK_EQUAL(chain_0.Genesis(), nullptr);
85 }
86
87 BOOST_AUTO_TEST_CASE(findfork_tests)
88 {
89 // Create a forking chain
90 const auto init_branch{[](auto& blocks, CBlockIndex* parent, int start_height) {
91 for (size_t i{0}; i < blocks.size(); ++i) {
92 blocks[i].pprev = i == 0 ? parent : &blocks[i - 1];
93 blocks[i].nHeight = start_height + i;
94 }
95 }};
96
97 const auto check_same{[](const CChain& chain, const auto& blocks) {
98 for (const auto& block : blocks) {
99 BOOST_CHECK_EQUAL(chain.FindFork(block), &block);
100 }
101 }};
102
103 const auto check_fork_point{[](const CChain& chain, const auto& blocks, const CBlockIndex& fork_point) {
104 for (const auto& block : blocks) {
105 BOOST_CHECK_EQUAL(chain.FindFork(block), &fork_point);
106 }
107 }};
108
109 std::array<CBlockIndex, 10> blocks_common;
110 init_branch(blocks_common, nullptr, 0);
111
112 std::array<CBlockIndex, 10> blocks_long;
113 init_branch(blocks_long, &blocks_common.back(), blocks_common.size());
114
115 std::array<CBlockIndex, 5> blocks_short;
116 init_branch(blocks_short, &blocks_common.back(), blocks_common.size());
117
118 // Create a chain with the longer fork
119 CChain chain_long;
120 chain_long.SetTip(blocks_long.back());
121 BOOST_CHECK_EQUAL(chain_long.Height(), 10 + 10 - 1);
122 // Test the blocks in the common part -> result should be the same
123 check_same(chain_long, blocks_common);
124 // Test the blocks on the longer fork -> result should be the same
125 check_same(chain_long, blocks_long);
126 // Test the blocks on the other shorter fork -> result should be the fork point
127 check_fork_point(chain_long, blocks_short, blocks_common.back());
128
129 // Create a chain with the shorter fork
130 CChain chain_short;
131 chain_short.SetTip(blocks_short.back());
132 BOOST_CHECK_EQUAL(chain_short.Height(), 10 + 5 - 1);
133 // Test the blocks in the common part -> result should be the same
134 check_same(chain_short, blocks_common);
135 // Test the blocks on the shorter fork -> result should be the same
136 check_same(chain_short, blocks_short);
137 // Test the blocks on the other longer fork -> result should be the fork point
138 check_fork_point(chain_short, blocks_long, blocks_common.back());
139
140 // Invalid test case. Mixing chains is not supported
141 CBlockIndex block_on_unrelated_chain;
142 BOOST_CHECK_EQUAL(chain_long.FindFork(block_on_unrelated_chain), nullptr);
143 }
144
145 BOOST_AUTO_TEST_CASE(chain_test)
146 {
147 FastRandomContext ctx;
148 std::vector<std::unique_ptr<CBlockIndex>> block_index;
149 // Run 10 iterations of the whole test.
150 for (int i = 0; i < 10; ++i) {
151 block_index.clear();
152 // Create genesis block.
153 auto genesis = std::make_unique<CBlockIndex>();
154 genesis->nHeight = 0;
155 block_index.push_back(std::move(genesis));
156 // Create 10000 more blocks.
157 for (int b = 0; b < 10000; ++b) {
158 auto new_index = std::make_unique<CBlockIndex>();
159 // 95% of blocks build on top of the last block; the others fork off randomly.
160 if (ctx.randrange(20) != 0) {
161 new_index->pprev = block_index.back().get();
162 } else {
163 new_index->pprev = block_index[ctx.randrange(block_index.size())].get();
164 }
165 new_index->nHeight = new_index->pprev->nHeight + 1;
166 new_index->BuildSkip();
167 block_index.push_back(std::move(new_index));
168 }
169 // Run 10000 random GetAncestor queries.
170 for (int q = 0; q < 10000; ++q) {
171 const CBlockIndex* block = block_index[ctx.randrange(block_index.size())].get();
172 unsigned height = ctx.randrange<unsigned>(block->nHeight + 1);
173 const CBlockIndex* result = block->GetAncestor(height);
174 BOOST_CHECK(result == NaiveGetAncestor(block, height));
175 }
176 // Run 10000 random LastCommonAncestor queries.
177 for (int q = 0; q < 10000; ++q) {
178 const CBlockIndex* block1 = block_index[ctx.randrange(block_index.size())].get();
179 const CBlockIndex* block2 = block_index[ctx.randrange(block_index.size())].get();
180 const CBlockIndex* result = LastCommonAncestor(block1, block2);
181 BOOST_CHECK(result == NaiveLastCommonAncestor(block1, block2));
182 }
183 }
184 }
185
186 BOOST_AUTO_TEST_SUITE_END()
187