fork

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 or lowestBlock, must be specified by its ID to unambiguously identify the fork that should be traversed.
• The other block can 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.

Convention

For the core traversal algorithms, we use the following conventions:

1. The head of the fork that should be traversed is specified by its ID
2. The lowestBlock is specified by its height: lowestHeightToVisit.
3. 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 ID xyz

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 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.

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
  • func (t ExcludingBlock) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
  • func (t ExcludingBlock) LowestHeightToVisit(headers storage.Headers) (uint64, error)
• type ExcludingHeight
  • func (t ExcludingHeight) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
  • func (t ExcludingHeight) LowestHeightToVisit(storage.Headers) (uint64, error)
• type IncludingBlock
  • func (t IncludingBlock) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
  • func (t IncludingBlock) LowestHeightToVisit(headers storage.Headers) (uint64, error)
• type IncludingHeight
  • func (t IncludingHeight) ConfirmTerminalReached(headers storage.Headers, lowestVisitedBlock *flow.Header) error
  • func (t IncludingHeight) LowestHeightToVisit(storage.Headers) (uint64, error)
• type Terminal

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 algorithm 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.