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.

INVARIANT: In RawBlockTree trunk branches deforested, we must have deforested == deforestRawBlockTree trunk branches.

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.

A check used in some of the handlers, determining whether the first argument is on the chain that ends in the second argument.

REVIEW: Using withinFragmentBounds for this might be cheaper.

TODO: Unify with isAncestorOf which basically does the same thing except not on WithOrigin.

Variant of isAncestorOf that returns False when the two blocks are equal.

TODO: Unify with isStrictAncestorOf which basically does the same thing except not on WithOrigin.

Make a block tree made of only a trunk.

An AnchoredFragment is a list where the last element (the anchor) is a ghost. Here they represent the partial ancestry of a block, where the anchor is either Genesis (start of the chain, not itself an actual block) or the hash of a block. Say we have blocks B1 through B5 (each succeeded by the next) and anchor A. You can think of the chain as growing from left to right like this:

                   A :> B1 :> B2 :> B3 :> B4 :> B5

nonemptyPrefixesOf builds the list of prefixes of an AnchoredFragment with at least one non-anchor entry. The name is a little confusing because the way we usually think of cons-lists these would be suffixes:

           A :> B1     A :> B1 :> B2     A :> B1 :> B2 :> B3
     A :> B1 :> B2 :> B3 :> B4     A :> B1 :> B2 :> B3 :> B4 :> B5

However this is consistent with isPrefixOf.

Check if a block (represented by its header Point) is on the BlockTree 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.