README
¶
Traversing a Fork
Generally, when traversing a fork (in either direction), there are two distinct blocks:
- the
head
of the fork that should be traversed - the
lowestBlock
in that fork, that should be included in the traversal
The traversal the walks head <--> lowestBlock
(in either direction).
There are a variety of ways to precisely specify head
and lowestBlock
:
- At least one block,
head
orlowestBlock
, must be specified by its ID to unambiguously identify the fork that should be traversed. - The other block an either be specified by ID or height.
- If both
head
andlowestBlock
are specified by their ID, they must both be on the same fork.
Convention
For the core traversal algorithms, we use the following conventions:
- The
head
of the fork that should be traversed is specified by itsID
- The
lowestBlock
is specified by its height:lowestHeightToVisit
. - If
head.Height < lowestHeightToVisit
, no blocks are visited and the traversal returns immediately (without error).
This design is inspired by a for
loop. For example, lets consider the case where we start
at the fork head
and traverse backwards until we reach a block with height lowestHeightToVisit
:
for block := head; block.Height >= lowestHeightToVisit; block = block.Parent {
visit(block)
}
For the core traversal algorithms, the parametrization of head
[type flow.ID
],
lowestHeightToVisit
[type uint64
], and direction is beneficial, as there are no inconsistent parameter sets.
(There is the edge-case of the root block, which we ignore in this high-level discussion)
Terminals
Higher-level algorithms that want to collect specific data from a fork have a variety of different termination conditions, such as:
- walk backwards up to (including) the block with ID
xyz
or excluding the block with IDxyz
To provide higher-level primitives for terminating the fork traversal, we include
Terminals
. Essentially, a Terminal
converts a high-level condition for the lowestBlock
to a suitable parametrization for the core traversal algorithm:
-
The height
lowestHeightToVisit
of the lowest block that should be visited. -
A consistency check
ConfirmTerminalReached
for the lowest visited block. This check is predominantly useful in case bothhead
andlowestBlock
are specified by their ID. It allows to enforce thathead
andlowestBlock
are both on the same fork and error otherwise.However, the precise implementation of
ConfirmTerminalReached
is left to the Terminal. Other, more elaborate conditions are possible.
Documentation
¶
Index ¶
- func TraverseBackward(headers storage.Headers, forkHead flow.Identifier, visitor onVisitBlock, ...) error
- func TraverseForward(headers storage.Headers, forkHead flow.Identifier, visitor onVisitBlock, ...) error
- type ExcludingBlock
- type ExcludingHeight
- type IncludingBlock
- type IncludingHeight
- type Terminal
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func TraverseBackward ¶
func TraverseBackward(headers storage.Headers, forkHead flow.Identifier, visitor onVisitBlock, terminal Terminal) 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 TraverseForward ¶
func TraverseForward(headers storage.Headers, forkHead flow.Identifier, visitor onVisitBlock, terminal Terminal, ) error
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.
Types ¶
type ExcludingBlock ¶
type ExcludingBlock flow.Identifier
ExcludingBlock returns a Terminal implementation where we explicitly specify the ID of the lowest block that should _not_ be visited anymore
func (ExcludingBlock) ConfirmTerminalReached ¶
func (t ExcludingBlock) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
ConfirmTerminalReached is a self-consistency check that the lowest visited block is in fact the expected terminal.
func (ExcludingBlock) LowestHeightToVisit ¶
func (t ExcludingBlock) LowestHeightToVisit(headers storage.Headers) (uint64, error)
LowestHeightToVisit computes the height of the lowest block that should be visited
type ExcludingHeight ¶
type ExcludingHeight uint64
ExcludingHeight returns a Terminal implementation where we specify the Height of the lowest block that should _not_ be visited anymore
func (ExcludingHeight) ConfirmTerminalReached ¶
func (t ExcludingHeight) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
ConfirmTerminalReached is a self-consistency check that the lowest visited block is in fact the expected terminal.
func (ExcludingHeight) LowestHeightToVisit ¶
func (t ExcludingHeight) LowestHeightToVisit(storage.Headers) (uint64, error)
LowestHeightToVisit computes the height of the lowest block that should be visited
type IncludingBlock ¶
type IncludingBlock flow.Identifier
IncludingBlock returns a Terminal implementation where we explicitly specify the ID of the lowest block that should be visited
func (IncludingBlock) ConfirmTerminalReached ¶
func (t IncludingBlock) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
ConfirmTerminalReached is a self-consistency check that the lowest visited block is in fact the expected terminal.
func (IncludingBlock) LowestHeightToVisit ¶
func (t IncludingBlock) LowestHeightToVisit(headers storage.Headers) (uint64, error)
LowestHeightToVisit computes the height of the lowest block that should be visited
type IncludingHeight ¶
type IncludingHeight uint64
IncludingHeight returns a Terminal implementation where we specify the height of the lowest block that should be visited
func (IncludingHeight) ConfirmTerminalReached ¶
func (t IncludingHeight) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
ConfirmTerminalReached is a self-consistency check that the lowest visited block is in fact the expected terminal.
func (IncludingHeight) LowestHeightToVisit ¶
func (t IncludingHeight) LowestHeightToVisit(storage.Headers) (uint64, error)
LowestHeightToVisit computes the height of the lowest block that should be visited
type Terminal ¶
type Terminal interface { // LowestHeightToVisit computes the height of the lowest block that should be visited LowestHeightToVisit(headers storage.Headers) (uint64, error) // ConfirmTerminalReached is a self-consistency check that the lowest visited block is // in fact the expected terminal. ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error }
Terminal specifies the terminal condition for traversing a fork. It abstracts the precise termination condition for `TraverseBackward` and `TraverseForward`. Generally, when traversing a fork (in either direction), there are two distinct blocks:
- the `head` of the fork that should be traversed
- the `lowestBlock` in that fork, which should be included in the traversal
The traversal the walks `head <--> lowestBlock` (in either direction).
There are a variety of ways to precisely specify `head` and `lowestBlock`:
- At least one block, `head` or `lowestBlock`, must be specified by its ID to unambiguously identify the fork that should be traversed.
- The other block an either be specified by ID or height.
- If both `head` and `lowestBlock` are specified by their ID, they must both be on the same fork.
Essentially it converts the termination condition into two statements:
(i) The height of the lowest block that should be visited. (ii) A consistency check `ConfirmTerminalReached` for the lowest visited block. This check is predominantly useful in case both `head` and `lowestBlock` are specified by their ID. It allows to enforce that `head` and `lowestBlock` are both on the same fork and error otherwise. However, the precise implementation of `ConfirmTerminalReached` is left to the Terminal. Other, more elaborate conditions are possible.