-
Notifications
You must be signed in to change notification settings - Fork 175
/
traversal.go
115 lines (100 loc) · 3.77 KB
/
traversal.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package fork
import (
"fmt"
"github.com/onflow/flow-go/model/flow"
"github.com/onflow/flow-go/storage"
)
// functor that will be called on each block header when traversing blocks.
type onVisitBlock = func(header *flow.Header) error
// TraverseBackward traverses the given fork (specified by block ID `forkHead`)
// in the order of decreasing height. The `terminal` defines when the traversal
// stops. The `visitor` callback is called for each block in this segment.
func TraverseBackward(headers storage.Headers, forkHead flow.Identifier, visitor onVisitBlock, terminal Terminal) error {
startBlock, err := headers.ByBlockID(forkHead)
if err != nil {
return fmt.Errorf("could not retrieve fork head with id %x: %w", forkHead, err)
}
lowestHeightToVisit, err := terminal.LowestHeightToVisit(headers)
if err != nil {
return fmt.Errorf("error determinging terminal height: %w", err)
}
if startBlock.Height < lowestHeightToVisit {
return nil
}
lowestBlock, err := unsafeTraverse(headers, startBlock, visitor, lowestHeightToVisit)
if err != nil {
return fmt.Errorf("traversing fork aborted: %w", err)
}
err = terminal.ConfirmTerminalReached(headers, lowestBlock)
if err != nil {
return fmt.Errorf("lowest visited block at height %d failed sanity check: %w", lowestHeightToVisit, err)
}
return nil
}
// TraverseForward traverses the given fork (specified by block ID `forkHead`)
// in the order of increasing height. The `terminal` defines when the traversal
// begins. The `visitor` callback is called for each block in this segment.
func TraverseForward(headers storage.Headers,
forkHead flow.Identifier,
visitor onVisitBlock,
terminal Terminal,
) error {
startBlock, err := headers.ByBlockID(forkHead)
if err != nil {
return fmt.Errorf("could not retrieve fork head with id %x: %w", forkHead, err)
}
lowestHeightToVisit, err := terminal.LowestHeightToVisit(headers)
if err != nil {
return fmt.Errorf("error determinging terminal height: %w", err)
}
if startBlock.Height < lowestHeightToVisit {
return nil
}
blocks := make([]*flow.Header, 0, startBlock.Height-lowestHeightToVisit+1)
lowestBlock, err := unsafeTraverse(headers,
startBlock,
func(header *flow.Header) error {
blocks = append(blocks, header)
return nil
},
lowestHeightToVisit,
)
if err != nil {
return fmt.Errorf("traversing fork aborted: %w", err)
}
err = terminal.ConfirmTerminalReached(headers, lowestBlock)
if err != nil {
return fmt.Errorf("lowest visited block at height %d failed sanity check: %w", lowestHeightToVisit, err)
}
for i := len(blocks) - 1; i >= 0; i-- {
block := blocks[i]
err = visitor(block)
if err != nil {
return fmt.Errorf("visitor errored on block %x at height %d: %w", block.ID(), block.Height, err)
}
}
return nil
}
// unsafeTraverse implements the fork traversal in the order of decreasing height.
// It is unsafe because:
// it assumes the stop condition for the for-loop has been pre-checked,
// which is `startBlock.Height < lowestHeightToVisit`. With the pre-check,
// it is guaranteed the for loop will stop eventually.
// In other words, this unsafe function should only be called after the pre-check.
// The `TraverseBackward` and `TraverseForward` are "safe" functions since they
// do the pre-check before calling the `unsafeTraverse`
func unsafeTraverse(headers storage.Headers, block *flow.Header, visitor onVisitBlock, lowestHeightToVisit uint64) (*flow.Header, error) {
for {
err := visitor(block)
if err != nil {
return nil, fmt.Errorf("visitor errored on block %x at height %d: %w", block.ID(), block.Height, err)
}
if block.Height == lowestHeightToVisit {
return block, nil
}
block, err = headers.ByBlockID(block.ParentID)
if err != nil {
return nil, fmt.Errorf("failed to revtrieve block header %x: %w", block.ParentID, err)
}
}
}