Documentation

Represent a block tree with a main trunk and branches leaving from the trunk in question. All the branches are represented by their prefix to and suffix from the intersection point.

INVARIANT: The branches' prefixes share the same anchor as the trunk and are fully contained in the trunk.

INVARIANT: The branches' suffixes are anchored in the trunk and do not contain any blocks in common with the trunk.

INVARIANT: The branches' suffixes do not contain any block in common with one another.

INVARIANT: for all BlockTreeBranch{..} in the tree, btTrunk == fromJust $ AF.join btbPrefix btbTrunkSuffix.

REVIEW: Find another name so as not to clash with BlockTree from `unstable-consensus-testlibTestUtil/TestBlock.hs`.

Represent a branch of a block tree by a prefix and a suffix. The full fragment (the prefix and suffix catenated) and the trunk suffix (the rest of the trunk after the branch forks off) are provided for practicality.

INVARIANT: the head of btbPrefix is the anchor of btbSuffix.

INVARIANT: btbFull == fromJust $ AF.join btbPrefix btbSuffix.

See findPath.

Add a branch to an existing block tree.

Yields Nothing if the given fragment does not intersect with the trunk or its anchor.

FIXME: we should enforce that the branch's prefix shares the same anchor as the trunk.

FIXME: we should enforce that the new branch' suffix does not contain any block in common with an existing branch.

Same as addBranch but calls to error if the former yields Nothing.

Return all the full fragments from the root of the tree.

Look for a point in the block tree and return a fragment going from the root of the tree to the point in question.

findPath source target blockTree finds a path from the source point to the target point in the blockTree and returns it as an anchored fragment It returns Nothing when either of source are target are not in the BlockTree. There are two interesting properties on this fragment:

1. Whether the returned fragment is anchored at the source.
2. Whether the returned fragment is empty.

Together, those two properties form four interesting cases:

a. If the fragment is anchored at the source and is empty, then source == target.

b. If the fragment is anchored at the source and is not empty, then source is an ancestor of target and the fragment contains all the blocks between them, target included.

c. If the fragment is not anchored at the source and is empty, then target is an ancestor of source.

d. If the fragment is not anchored at the source and is not empty, then it is anchored at the youngest common ancestor of both source and target and contains all the blocks between that ancestor and target.

Make a block tree made of only a trunk.

Pretty prints a block tree for human readability. For instance:

slots: 0 1 2 3 4 5 6 7 8 9 trunk: 0─────1──2──3──4─────5──6──7 ╰─────3──4─────5

Returns a list of strings intended to be catenated with a newline.