vendor/github.com/btcsuite/btcd/blockchain/chainview_test.go

   1 // Copyright (c) 2017 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package blockchain
   6
   7 import (
   8         "fmt"
   9         "math/rand"
  10         "reflect"
  11         "testing"
  12
  13         "github.com/btcsuite/btcd/wire"
  14 )
  15
  16 // testNoncePrng provides a deterministic prng for the nonce in generated fake
  17 // nodes.  The ensures that the node have unique hashes.
  18 var testNoncePrng = rand.New(rand.NewSource(0))
  19
  20 // chainedNodes returns the specified number of nodes constructed such that each
  21 // subsequent node points to the previous one to create a chain.  The first node
  22 // will point to the passed parent which can be nil if desired.
  23 func chainedNodes(parent *blockNode, numNodes int) []*blockNode {
  24         nodes := make([]*blockNode, numNodes)
  25         tip := parent
  26         for i := 0; i < numNodes; i++ {
  27                 // This is invalid, but all that is needed is enough to get the
  28                 // synthetic tests to work.
  29                 header := wire.BlockHeader{Nonce: testNoncePrng.Uint32()}
  30                 height := int32(0)
  31                 if tip != nil {
  32                         header.PrevBlock = tip.hash
  33                         height = tip.height + 1
  34                 }
  35                 node := newBlockNode(&header, height)
  36                 node.parent = tip
  37                 tip = node
  38
  39                 nodes[i] = node
  40         }
  41         return nodes
  42 }
  43
  44 // String returns the block node as a human-readable name.
  45 func (node blockNode) String() string {
  46         return fmt.Sprintf("%s(%d)", node.hash, node.height)
  47 }
  48
  49 // tstTip is a convenience function to grab the tip of a chain of block nodes
  50 // created via chainedNodes.
  51 func tstTip(nodes []*blockNode) *blockNode {
  52         return nodes[len(nodes)-1]
  53 }
  54
  55 // locatorHashes is a convenience function that returns the hashes for all of
  56 // the passed indexes of the provided nodes.  It is used to construct expected
  57 // block locators in the tests.
  58 func locatorHashes(nodes []*blockNode, indexes ...int) BlockLocator {
  59         hashes := make(BlockLocator, 0, len(indexes))
  60         for _, idx := range indexes {
  61                 hashes = append(hashes, &nodes[idx].hash)
  62         }
  63         return hashes
  64 }
  65
  66 // zipLocators is a convenience function that returns a single block locator
  67 // given a variable number of them and is used in the tests.
  68 func zipLocators(locators ...BlockLocator) BlockLocator {
  69         var hashes BlockLocator
  70         for _, locator := range locators {
  71                 hashes = append(hashes, locator...)
  72         }
  73         return hashes
  74 }
  75
  76 // TestChainView ensures all of the exported functionality of chain views works
  77 // as intended with the expection of some special cases which are handled in
  78 // other tests.
  79 func TestChainView(t *testing.T) {
  80         // Construct a synthetic block index consisting of the following
  81         // structure.
  82         // 0 -> 1 -> 2  -> 3  -> 4
  83         //       \-> 2a -> 3a -> 4a  -> 5a -> 6a -> 7a -> ... -> 26a
  84         //             \-> 3a'-> 4a' -> 5a'
  85         branch0Nodes := chainedNodes(nil, 5)
  86         branch1Nodes := chainedNodes(branch0Nodes[1], 25)
  87         branch2Nodes := chainedNodes(branch1Nodes[0], 3)
  88
  89         tip := tstTip
  90         tests := []struct {
  91                 name       string
  92                 view       *chainView   // active view
  93                 genesis    *blockNode   // expected genesis block of active view
  94                 tip        *blockNode   // expected tip of active view
  95                 side       *chainView   // side chain view
  96                 sideTip    *blockNode   // expected tip of side chain view
  97                 fork       *blockNode   // expected fork node
  98                 contains   []*blockNode // expected nodes in active view
  99                 noContains []*blockNode // expected nodes NOT in active view
 100                 equal      *chainView   // view expected equal to active view
 101                 unequal    *chainView   // view expected NOT equal to active
 102                 locator    BlockLocator // expected locator for active view tip
 103         }{
 104                 {
 105                         // Create a view for branch 0 as the active chain and
 106                         // another view for branch 1 as the side chain.
 107                         name:       "chain0-chain1",
 108                         view:       newChainView(tip(branch0Nodes)),
 109                         genesis:    branch0Nodes[0],
 110                         tip:        tip(branch0Nodes),
 111                         side:       newChainView(tip(branch1Nodes)),
 112                         sideTip:    tip(branch1Nodes),
 113                         fork:       branch0Nodes[1],
 114                         contains:   branch0Nodes,
 115                         noContains: branch1Nodes,
 116                         equal:      newChainView(tip(branch0Nodes)),
 117                         unequal:    newChainView(tip(branch1Nodes)),
 118                         locator:    locatorHashes(branch0Nodes, 4, 3, 2, 1, 0),
 119                 },
 120                 {
 121                         // Create a view for branch 1 as the active chain and
 122                         // another view for branch 2 as the side chain.
 123                         name:       "chain1-chain2",
 124                         view:       newChainView(tip(branch1Nodes)),
 125                         genesis:    branch0Nodes[0],
 126                         tip:        tip(branch1Nodes),
 127                         side:       newChainView(tip(branch2Nodes)),
 128                         sideTip:    tip(branch2Nodes),
 129                         fork:       branch1Nodes[0],
 130                         contains:   branch1Nodes,
 131                         noContains: branch2Nodes,
 132                         equal:      newChainView(tip(branch1Nodes)),
 133                         unequal:    newChainView(tip(branch2Nodes)),
 134                         locator: zipLocators(
 135                                 locatorHashes(branch1Nodes, 24, 23, 22, 21, 20,
 136                                         19, 18, 17, 16, 15, 14, 13, 11, 7),
 137                                 locatorHashes(branch0Nodes, 1, 0)),
 138                 },
 139                 {
 140                         // Create a view for branch 2 as the active chain and
 141                         // another view for branch 0 as the side chain.
 142                         name:       "chain2-chain0",
 143                         view:       newChainView(tip(branch2Nodes)),
 144                         genesis:    branch0Nodes[0],
 145                         tip:        tip(branch2Nodes),
 146                         side:       newChainView(tip(branch0Nodes)),
 147                         sideTip:    tip(branch0Nodes),
 148                         fork:       branch0Nodes[1],
 149                         contains:   branch2Nodes,
 150                         noContains: branch0Nodes[2:],
 151                         equal:      newChainView(tip(branch2Nodes)),
 152                         unequal:    newChainView(tip(branch0Nodes)),
 153                         locator: zipLocators(
 154                                 locatorHashes(branch2Nodes, 2, 1, 0),
 155                                 locatorHashes(branch1Nodes, 0),
 156                                 locatorHashes(branch0Nodes, 1, 0)),
 157                 },
 158         }
 159 testLoop:
 160         for _, test := range tests {
 161                 // Ensure the active and side chain heights are the expected
 162                 // values.
 163                 if test.view.Height() != test.tip.height {
 164                         t.Errorf("%s: unexpected active view height -- got "+
 165                                 "%d, want %d", test.name, test.view.Height(),
 166                                 test.tip.height)
 167                         continue
 168                 }
 169                 if test.side.Height() != test.sideTip.height {
 170                         t.Errorf("%s: unexpected side view height -- got %d, "+
 171                                 "want %d", test.name, test.side.Height(),
 172                                 test.sideTip.height)
 173                         continue
 174                 }
 175
 176                 // Ensure the active and side chain genesis block is the
 177                 // expected value.
 178                 if test.view.Genesis() != test.genesis {
 179                         t.Errorf("%s: unexpected active view genesis -- got "+
 180                                 "%v, want %v", test.name, test.view.Genesis(),
 181                                 test.genesis)
 182                         continue
 183                 }
 184                 if test.side.Genesis() != test.genesis {
 185                         t.Errorf("%s: unexpected side view genesis -- got %v, "+
 186                                 "want %v", test.name, test.view.Genesis(),
 187                                 test.genesis)
 188                         continue
 189                 }
 190
 191                 // Ensure the active and side chain tips are the expected nodes.
 192                 if test.view.Tip() != test.tip {
 193                         t.Errorf("%s: unexpected active view tip -- got %v, "+
 194                                 "want %v", test.name, test.view.Tip(), test.tip)
 195                         continue
 196                 }
 197                 if test.side.Tip() != test.sideTip {
 198                         t.Errorf("%s: unexpected active view tip -- got %v, "+
 199                                 "want %v", test.name, test.side.Tip(),
 200                                 test.sideTip)
 201                         continue
 202                 }
 203
 204                 // Ensure that regardless of the order the two chains are
 205                 // compared they both return the expected fork point.
 206                 forkNode := test.view.FindFork(test.side.Tip())
 207                 if forkNode != test.fork {
 208                         t.Errorf("%s: unexpected fork node (view, side) -- "+
 209                                 "got %v, want %v", test.name, forkNode,
 210                                 test.fork)
 211                         continue
 212                 }
 213                 forkNode = test.side.FindFork(test.view.Tip())
 214                 if forkNode != test.fork {
 215                         t.Errorf("%s: unexpected fork node (side, view) -- "+
 216                                 "got %v, want %v", test.name, forkNode,
 217                                 test.fork)
 218                         continue
 219                 }
 220
 221                 // Ensure that the fork point for a node that is already part
 222                 // of the chain view is the node itself.
 223                 forkNode = test.view.FindFork(test.view.Tip())
 224                 if forkNode != test.view.Tip() {
 225                         t.Errorf("%s: unexpected fork node (view, tip) -- "+
 226                                 "got %v, want %v", test.name, forkNode,
 227                                 test.view.Tip())
 228                         continue
 229                 }
 230
 231                 // Ensure all expected nodes are contained in the active view.
 232                 for _, node := range test.contains {
 233                         if !test.view.Contains(node) {
 234                                 t.Errorf("%s: expected %v in active view",
 235                                         test.name, node)
 236                                 continue testLoop
 237                         }
 238                 }
 239
 240                 // Ensure all nodes from side chain view are NOT contained in
 241                 // the active view.
 242                 for _, node := range test.noContains {
 243                         if test.view.Contains(node) {
 244                                 t.Errorf("%s: unexpected %v in active view",
 245                                         test.name, node)
 246                                 continue testLoop
 247                         }
 248                 }
 249
 250                 // Ensure equality of different views into the same chain works
 251                 // as intended.
 252                 if !test.view.Equals(test.equal) {
 253                         t.Errorf("%s: unexpected unequal views", test.name)
 254                         continue
 255                 }
 256                 if test.view.Equals(test.unequal) {
 257                         t.Errorf("%s: unexpected equal views", test.name)
 258                         continue
 259                 }
 260
 261                 // Ensure all nodes contained in the view return the expected
 262                 // next node.
 263                 for i, node := range test.contains {
 264                         // Final node expects nil for the next node.
 265                         var expected *blockNode
 266                         if i < len(test.contains)-1 {
 267                                 expected = test.contains[i+1]
 268                         }
 269                         if next := test.view.Next(node); next != expected {
 270                                 t.Errorf("%s: unexpected next node -- got %v, "+
 271                                         "want %v", test.name, next, expected)
 272                                 continue testLoop
 273                         }
 274                 }
 275
 276                 // Ensure nodes that are not contained in the view do not
 277                 // produce a successor node.
 278                 for _, node := range test.noContains {
 279                         if next := test.view.Next(node); next != nil {
 280                                 t.Errorf("%s: unexpected next node -- got %v, "+
 281                                         "want nil", test.name, next)
 282                                 continue testLoop
 283                         }
 284                 }
 285
 286                 // Ensure all nodes contained in the view can be retrieved by
 287                 // height.
 288                 for _, wantNode := range test.contains {
 289                         node := test.view.NodeByHeight(wantNode.height)
 290                         if node != wantNode {
 291                                 t.Errorf("%s: unexpected node for height %d -- "+
 292                                         "got %v, want %v", test.name,
 293                                         wantNode.height, node, wantNode)
 294                                 continue testLoop
 295                         }
 296                 }
 297
 298                 // Ensure the block locator for the tip of the active view
 299                 // consists of the expected hashes.
 300                 locator := test.view.BlockLocator(test.view.tip())
 301                 if !reflect.DeepEqual(locator, test.locator) {
 302                         t.Errorf("%s: unexpected locator -- got %v, want %v",
 303                                 test.name, locator, test.locator)
 304                         continue
 305                 }
 306         }
 307 }
 308
 309 // TestChainViewForkCorners ensures that finding the fork between two chains
 310 // works in some corner cases such as when the two chains have completely
 311 // unrelated histories.
 312 func TestChainViewForkCorners(t *testing.T) {
 313         // Construct two unrelated single branch synthetic block indexes.
 314         branchNodes := chainedNodes(nil, 5)
 315         unrelatedBranchNodes := chainedNodes(nil, 7)
 316
 317         // Create chain views for the two unrelated histories.
 318         view1 := newChainView(tstTip(branchNodes))
 319         view2 := newChainView(tstTip(unrelatedBranchNodes))
 320
 321         // Ensure attempting to find a fork point with a node that doesn't exist
 322         // doesn't produce a node.
 323         if fork := view1.FindFork(nil); fork != nil {
 324                 t.Fatalf("FindFork: unexpected fork -- got %v, want nil", fork)
 325         }
 326
 327         // Ensure attempting to find a fork point in two chain views with
 328         // totally unrelated histories doesn't produce a node.
 329         for _, node := range branchNodes {
 330                 if fork := view2.FindFork(node); fork != nil {
 331                         t.Fatalf("FindFork: unexpected fork -- got %v, want nil",
 332                                 fork)
 333                 }
 334         }
 335         for _, node := range unrelatedBranchNodes {
 336                 if fork := view1.FindFork(node); fork != nil {
 337                         t.Fatalf("FindFork: unexpected fork -- got %v, want nil",
 338                                 fork)
 339                 }
 340         }
 341 }
 342
 343 // TestChainViewSetTip ensures changing the tip works as intended including
 344 // capacity changes.
 345 func TestChainViewSetTip(t *testing.T) {
 346         // Construct a synthetic block index consisting of the following
 347         // structure.
 348         // 0 -> 1 -> 2  -> 3  -> 4
 349         //       \-> 2a -> 3a -> 4a  -> 5a -> 6a -> 7a -> ... -> 26a
 350         branch0Nodes := chainedNodes(nil, 5)
 351         branch1Nodes := chainedNodes(branch0Nodes[1], 25)
 352
 353         tip := tstTip
 354         tests := []struct {
 355                 name     string
 356                 view     *chainView     // active view
 357                 tips     []*blockNode   // tips to set
 358                 contains [][]*blockNode // expected nodes in view for each tip
 359         }{
 360                 {
 361                         // Create an empty view and set the tip to increasingly
 362                         // longer chains.
 363                         name:     "increasing",
 364                         view:     newChainView(nil),
 365                         tips:     []*blockNode{tip(branch0Nodes), tip(branch1Nodes)},
 366                         contains: [][]*blockNode{branch0Nodes, branch1Nodes},
 367                 },
 368                 {
 369                         // Create a view with a longer chain and set the tip to
 370                         // increasingly shorter chains.
 371                         name:     "decreasing",
 372                         view:     newChainView(tip(branch1Nodes)),
 373                         tips:     []*blockNode{tip(branch0Nodes), nil},
 374                         contains: [][]*blockNode{branch0Nodes, nil},
 375                 },
 376                 {
 377                         // Create a view with a shorter chain and set the tip to
 378                         // a longer chain followed by setting it back to the
 379                         // shorter chain.
 380                         name:     "small-large-small",
 381                         view:     newChainView(tip(branch0Nodes)),
 382                         tips:     []*blockNode{tip(branch1Nodes), tip(branch0Nodes)},
 383                         contains: [][]*blockNode{branch1Nodes, branch0Nodes},
 384                 },
 385                 {
 386                         // Create a view with a longer chain and set the tip to
 387                         // a smaller chain followed by setting it back to the
 388                         // longer chain.
 389                         name:     "large-small-large",
 390                         view:     newChainView(tip(branch1Nodes)),
 391                         tips:     []*blockNode{tip(branch0Nodes), tip(branch1Nodes)},
 392                         contains: [][]*blockNode{branch0Nodes, branch1Nodes},
 393                 },
 394         }
 395
 396 testLoop:
 397         for _, test := range tests {
 398                 for i, tip := range test.tips {
 399                         // Ensure the view tip is the expected node.
 400                         test.view.SetTip(tip)
 401                         if test.view.Tip() != tip {
 402                                 t.Errorf("%s: unexpected view tip -- got %v, "+
 403                                         "want %v", test.name, test.view.Tip(),
 404                                         tip)
 405                                 continue testLoop
 406                         }
 407
 408                         // Ensure all expected nodes are contained in the view.
 409                         for _, node := range test.contains[i] {
 410                                 if !test.view.Contains(node) {
 411                                         t.Errorf("%s: expected %v in active view",
 412                                                 test.name, node)
 413                                         continue testLoop
 414                                 }
 415                         }
 416
 417                 }
 418         }
 419 }
 420
 421 // TestChainViewNil ensures that creating and accessing a nil chain view behaves
 422 // as expected.
 423 func TestChainViewNil(t *testing.T) {
 424         // Ensure two unininitialized views are considered equal.
 425         view := newChainView(nil)
 426         if !view.Equals(newChainView(nil)) {
 427                 t.Fatal("uninitialized nil views unequal")
 428         }
 429
 430         // Ensure the genesis of an uninitialized view does not produce a node.
 431         if genesis := view.Genesis(); genesis != nil {
 432                 t.Fatalf("Genesis: unexpected genesis -- got %v, want nil",
 433                         genesis)
 434         }
 435
 436         // Ensure the tip of an uninitialized view does not produce a node.
 437         if tip := view.Tip(); tip != nil {
 438                 t.Fatalf("Tip: unexpected tip -- got %v, want nil", tip)
 439         }
 440
 441         // Ensure the height of an uninitialized view is the expected value.
 442         if height := view.Height(); height != -1 {
 443                 t.Fatalf("Height: unexpected height -- got %d, want -1", height)
 444         }
 445
 446         // Ensure attempting to get a node for a height that does not exist does
 447         // not produce a node.
 448         if node := view.NodeByHeight(10); node != nil {
 449                 t.Fatalf("NodeByHeight: unexpected node -- got %v, want nil", node)
 450         }
 451
 452         // Ensure an uninitialized view does not report it contains nodes.
 453         fakeNode := chainedNodes(nil, 1)[0]
 454         if view.Contains(fakeNode) {
 455                 t.Fatalf("Contains: view claims it contains node %v", fakeNode)
 456         }
 457
 458         // Ensure the next node for a node that does not exist does not produce
 459         // a node.
 460         if next := view.Next(nil); next != nil {
 461                 t.Fatalf("Next: unexpected next node -- got %v, want nil", next)
 462         }
 463
 464         // Ensure the next node for a node that exists does not produce a node.
 465         if next := view.Next(fakeNode); next != nil {
 466                 t.Fatalf("Next: unexpected next node -- got %v, want nil", next)
 467         }
 468
 469         // Ensure attempting to find a fork point with a node that doesn't exist
 470         // doesn't produce a node.
 471         if fork := view.FindFork(nil); fork != nil {
 472                 t.Fatalf("FindFork: unexpected fork -- got %v, want nil", fork)
 473         }
 474
 475         // Ensure attempting to get a block locator for the tip doesn't produce
 476         // one since the tip is nil.
 477         if locator := view.BlockLocator(nil); locator != nil {
 478                 t.Fatalf("BlockLocator: unexpected locator -- got %v, want nil",
 479                         locator)
 480         }
 481
 482         // Ensure attempting to get a block locator for a node that exists still
 483         // works as intended.
 484         branchNodes := chainedNodes(nil, 50)
 485         wantLocator := locatorHashes(branchNodes, 49, 48, 47, 46, 45, 44, 43,
 486                 42, 41, 40, 39, 38, 36, 32, 24, 8, 0)
 487         locator := view.BlockLocator(tstTip(branchNodes))
 488         if !reflect.DeepEqual(locator, wantLocator) {
 489                 t.Fatalf("BlockLocator: unexpected locator -- got %v, want %v",
 490                         locator, wantLocator)
 491         }
 492 }