ouroboros-network-0.1.0.0: A networking layer for the Ouroboros blockchain protocol

Ouroboros.Network.AnchoredFragment

Synopsis

# AnchoredFragment type and fundamental operations

type AnchoredFragment block = AnchoredSeq (WithOrigin SlotNo) (Anchor block) block Source #

An AnchoredFragment is a fragment of a chain that is anchored somewhere in that chain. The Anchor corresponds to the block immediately before the first, leftmost block in the fragment. The block corresponding to the anchor is not present in the fragment. The anchor can be thought of as a left exclusive bound.

For example, the following fragment is anchored at a and contains b1, b2, and b3, which is the head of the fragment.

a ] b1 >: b2 >: b3

The fact that it is an exclusive bound is particularly convenient when dealing with Genesis. Genesis is the start of the chain, but not an actual block, so we cannot use it an inclusive bound. However, there is an Anchor that refers to Genesis (AnchorGenesis), which can be used as the anchor, acting as an exclusive bound.

An AnchoredFragment anchored at Genesis can thus be converted to a Chain (fromAnchoredFragment), containing all blocks starting from Genesis.

Without an anchor point, an empty fragment wouldn't give us much more information: is it empty because the whole chain is empty? Or, did we just get an empty fragment that was split off from some later part of the chain?

data AnchoredSeq v a b where Source #

Generalisation of a Sequence with elements of type b with a custom measure v and an anchor a.

This type is strict in the elements, but not strict in the spine.

For example, an AnchoredSeq can represent a fragment of a chain containing blocks that is anchored at a certain point. It can also represent a history of ledger states with the anchor being the "immutable" ledger state.

NOTE: there might be multiple elements with the same measure, e.g., multiple blocks with the same WithOrigin SlotNo. That is why functions operating on an AnchoredSeq often take a predicate in addition to a measure. At most one element should satisfy that predicate, e.g., the block must have a certain hash. The behaviour is undefined when multiple elements satisfy the predicate.

Bundled Patterns

 pattern Empty ∷ Anchorable v a b ⇒ a → AnchoredSeq v a b $$O(1)$$. Pattern for matching on or creating an empty AnchoredSeq. An empty sequence has/needs an anchor. pattern (:>) ∷ Anchorable v a b ⇒ AnchoredSeq v a b → b → AnchoredSeq v a b infixl 5 $$O(1)$$. Add an element to the right of the anchored sequence. pattern (:<) ∷ Anchorable v a b ⇒ b → AnchoredSeq v a b → AnchoredSeq v a b infixl 5 $$O(1)$$. View the first, leftmost block of the anchored sequence.Note that the anchor shifts, i.e., the anchor of the second argument will correspond to the first argument.This is only a view, not a constructor, as adding a block to the left would change the anchor of the sequence, but we have no information about the predecessor of the block we'd be prepending.

#### Instances

Instances details
 (Eq a, Eq b) ⇒ Eq (AnchoredSeq v a b) Source # Instance detailsDefined in Ouroboros.Network.AnchoredSeq Methods(==) ∷ AnchoredSeq v a b → AnchoredSeq v a b → Bool Source #(/=) ∷ AnchoredSeq v a b → AnchoredSeq v a b → Bool Source # (Show a, Show b) ⇒ Show (AnchoredSeq v a b) Source # Instance detailsDefined in Ouroboros.Network.AnchoredSeq MethodsshowsPrec ∷ Int → AnchoredSeq v a b → ShowS Source #show ∷ AnchoredSeq v a b → String Source #showList ∷ [AnchoredSeq v a b] → ShowS Source # Generic (AnchoredSeq v a b) Source # Instance detailsDefined in Ouroboros.Network.AnchoredSeq Associated Typestype Rep (AnchoredSeq v a b) ∷ Type → Type Source # Methodsfrom ∷ AnchoredSeq v a b → Rep (AnchoredSeq v a b) x Source #to ∷ Rep (AnchoredSeq v a b) x → AnchoredSeq v a b Source # (NoThunks a, NoThunks b) ⇒ NoThunks (AnchoredSeq v a b) Source # Instance detailsDefined in Ouroboros.Network.AnchoredSeq MethodsnoThunks ∷ Context → AnchoredSeq v a b → IO (Maybe ThunkInfo)wNoThunks ∷ Context → AnchoredSeq v a b → IO (Maybe ThunkInfo)showTypeOf ∷ Proxy (AnchoredSeq v a b) → String type Rep (AnchoredSeq v a b) Source # Instance detailsDefined in Ouroboros.Network.AnchoredSeq type Rep (AnchoredSeq v a b)

anchorAnchoredSeq v a b → a Source #

anchorPointAnchoredFragment block → Point block Source #

Return the Point corresponding to the anchor.

Return the BlocKno corresponding to the anchor.

# Anchor

data Anchor block Source #

Anchor of an AnchoredFragment

Constructors

 AnchorGenesis The fragment is anchored at genesis Anchor !SlotNo !(HeaderHash block) !BlockNo The fragment is anchored after genesisWe don't use the Point type directly as that has its own use of WithOrigin, and we want to enforce here that we have a block number if and only if the point is not Origin.Note that we don't use HeaderFields here because that is a view of a header with lazy fields and thus unfit for long-term in-memory storage.Moreover, we don't reuse the Tip type, because that type is sent across the network, while this type is not. This means we can freely change this type to suit our needs without worrying about binary compatibility.

#### Instances

Instances details
 StandardHash block ⇒ Eq (Anchor block) Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment Methods(==) ∷ Anchor block → Anchor block → Bool Source #(/=) ∷ Anchor block → Anchor block → Bool Source # StandardHash block ⇒ Show (Anchor block) Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment MethodsshowsPrec ∷ Int → Anchor block → ShowS Source #show ∷ Anchor block → String Source #showList ∷ [Anchor block] → ShowS Source # Generic (Anchor block) Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment Associated Typestype Rep (Anchor block) ∷ Type → Type Source # Methodsfrom ∷ Anchor block → Rep (Anchor block) x Source #to ∷ Rep (Anchor block) x → Anchor block Source # StandardHash block ⇒ NoThunks (Anchor block) Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment MethodsnoThunks ∷ Context → Anchor block → IO (Maybe ThunkInfo)wNoThunks ∷ Context → Anchor block → IO (Maybe ThunkInfo)showTypeOf ∷ Proxy (Anchor block) → String HasHeader block ⇒ Anchorable (WithOrigin SlotNo) (Anchor block) block Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment MethodsasAnchor ∷ block → Anchor block Source #getAnchorMeasure ∷ Proxy block → Anchor block → WithOrigin SlotNo Source # type Rep (Anchor block) Source # Instance detailsDefined in Ouroboros.Network.AnchoredFragment type Rep (Anchor block) = D1 ('MetaData "Anchor" "Ouroboros.Network.AnchoredFragment" "ouroboros-network-0.1.0.0-inplace" 'False) (C1 ('MetaCons "AnchorGenesis" 'PrefixI 'False) (U1 ∷ Type → Type) :+: C1 ('MetaCons "Anchor" 'PrefixI 'False) (S1 ('MetaSel ('Nothing ∷ Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 SlotNo) :*: (S1 ('MetaSel ('Nothing ∷ Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 (HeaderHash block)) :*: S1 ('MetaSel ('Nothing ∷ Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 BlockNo))))

anchorFromBlockHasHeader block ⇒ block → Anchor block Source #

Construct anchor from a block

In other words, this would be the block immediately before the other blocks in the fragment.

anchorFromPointPoint block → BlockNoAnchor block Source #

Construct an anchor from a point

In this case, we must also be given the BlockNo. This only makes sense for points that aren't genesis.

anchorToPointAnchor block → Point block Source #

Compute which Point this anchor corresponds to

Extract the SlotNo from the anchor

Extract the BlockNo from the anchor

NOTE: When the Anchor is AnchorGenesis, this returns Origin. It does not return genesisBlockNo, which is badly named, and is instead the block number of the first block on the chain (i.e., genesisPoint and genesisBlockNo don't go hand in hand!)

anchorToHashAnchor block → ChainHash block Source #

Extract the hash from the anchor

Returns GenesisHash if the anchor is AnchorGenesis.

anchorIsGenesisAnchor block → Bool Source #

Does this anchor represent genesis (i.e., empty chain)?

Translate Anchor to Tip

Right now this is in fact an isomorphism, but these two types are logically independent.

The equivalent of castPoint for Anchor

validHasFullHeader block ⇒ AnchoredFragment block → Bool Source #

$$O(n)$$.

validExtensionHasFullHeader block ⇒ AnchoredFragment block → block → Bool Source #

$$O(1)$$.

## Block re-exports

class (StandardHash b, Typeable b) ⇒ HasHeader b where Source #

Abstract over the shape of blocks (or indeed just block headers)

Methods

#### Instances

Instances details
 Source # Instance detailsDefined in Ouroboros.Network.Testing.ConcreteBlock Methods Source # Instance detailsDefined in Ouroboros.Network.Testing.ConcreteBlock Methods Source # Instance detailsDefined in Ouroboros.Network.Block Methods

newtype Point block Source #

A point on the chain is identified by its Slot and HeaderHash.

The Slot tells us where to look and the HeaderHash either simply serves as a check, or in some contexts it disambiguates blocks from different forks that were in the same slot.

It's a newtype rather than a type synonym, because using a type synonym would lead to ambiguity, since HeaderHash is a non-injective type family.

Constructors

 Point FieldsgetPoint ∷ WithOrigin (Block SlotNo (HeaderHash block))

#### Instances

Instances details
 StandardHash block ⇒ Eq (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block Methods(==) ∷ Point block → Point block → Bool Source #(/=) ∷ Point block → Point block → Bool Source # StandardHash block ⇒ Ord (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block Methodscompare ∷ Point block → Point block → Ordering Source #(<) ∷ Point block → Point block → Bool Source #(<=) ∷ Point block → Point block → Bool Source #(>) ∷ Point block → Point block → Bool Source #(>=) ∷ Point block → Point block → Bool Source #max ∷ Point block → Point block → Point block Source #min ∷ Point block → Point block → Point block Source # StandardHash block ⇒ Show (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block MethodsshowsPrec ∷ Int → Point block → ShowS Source #show ∷ Point block → String Source #showList ∷ [Point block] → ShowS Source # Generic (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block Associated Typestype Rep (Point block) ∷ Type → Type Source # Methodsfrom ∷ Point block → Rep (Point block) x Source #to ∷ Rep (Point block) x → Point block Source # Serialise (HeaderHash block) ⇒ Serialise (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block Methodsencode ∷ Point block → Encoding #decode ∷ Decoder s (Point block) #encodeList ∷ [Point block] → Encoding #decodeList ∷ Decoder s [Point block] # StandardHash block ⇒ NoThunks (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block MethodsnoThunks ∷ Context → Point block → IO (Maybe ThunkInfo)wNoThunks ∷ Context → Point block → IO (Maybe ThunkInfo)showTypeOf ∷ Proxy (Point block) → String ShowProxy block ⇒ ShowProxy (Point block ∷ Type) Source # Instance detailsDefined in Ouroboros.Network.Block MethodsshowProxy ∷ Proxy (Point block) → String Source # type Rep (Point block) Source # Instance detailsDefined in Ouroboros.Network.Block type Rep (Point block) = D1 ('MetaData "Point" "Ouroboros.Network.Block" "ouroboros-network-0.1.0.0-inplace" 'True) (C1 ('MetaCons "Point" 'PrefixI 'True) (S1 ('MetaSel ('Just "getPoint") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (WithOrigin (Block SlotNo (HeaderHash block))))))

blockPointHasHeader block ⇒ block → Point block Source #

# AnchoredFragment construction and inspection

$$O(1)$$. When the fragment is empty, the anchor point is returned.

headAnchor ∷ ∀ v a b. Anchorable v a b ⇒ AnchoredSeq v a b → a Source #

$$O(1)$$. The anchor corresponding to the most recently added element (i.e., the anchor that would be needed for a sequence starting after this). When the anchored sequence is empty, the anchor is returned.

$$O(1)$$. When the fragment is empty, the slot of the anchor point is returned, which may be origin (no slot).

$$O(1)$$. When the fragment is empty, the hash of the anchor point is returned.

$$O(1)$$. When the fragment is empty, the block number of the anchor point is returned.

## Basic operations

headAnchorable v a b ⇒ AnchoredSeq v a b → Either a b Source #

$$O(1)$$. When the sequence is empty, return the anchor, otherwise the most recently added element.

lastAnchorable v a b ⇒ AnchoredSeq v a b → Either a b Source #

$$O(1)$$. When the sequence is empty, return the anchor, otherwise the leftmost element.

lastPointHasHeader block ⇒ AnchoredFragment block → Point block Source #

$$O(1)$$. When the fragment is empty, the anchor point is returned.

lastSlotHasHeader block ⇒ AnchoredFragment block → WithOrigin SlotNo Source #

$$O(1)$$. When the fragment is empty, the slot of the anchor point is returned, which may be the origin and therefore have no slot.

toNewestFirstAnchoredSeq v a b → [b] Source #

$$O(n)$$. Return the elements in the AnchoredSeq in newest-to-oldest order.

toOldestFirstAnchoredSeq v a b → [b] Source #

$$O(n)$$. Return the elements in the AnchoredSeq in oldest-to-newest order.

fromNewestFirstAnchorable v a b ⇒ a → [b] → AnchoredSeq v a b Source #

$$O(n)$$. Make an AnchoredSeq from a list of elements in newest-to-oldest order. The last element in the list will be the one after the given anchor.

fromOldestFirstAnchorable v a b ⇒ a → [b] → AnchoredSeq v a b Source #

$$O(n)$$. Make an AnchoredSeq from a list of elements in oldest-to-newest order. The first element in the list will be the one after the given anchor.

splitAtAnchorable v a b ⇒ IntAnchoredSeq v a b → (AnchoredSeq v a b, AnchoredSeq v a b) Source #

$$O(\log(\min(i,n-i))$$. Split the AnchoredSeq at a given position.

POSTCONDITION: (before, after) = splitAt i s, then: * anchor before == anchor s * headAnchor before == anchor after * headAnchor after == headAnchor s * join before after == Just s

dropNewestAnchorable v a b ⇒ IntAnchoredSeq v a b → AnchoredSeq v a b Source #

$$O(\log(\min(i,n-i))$$. Drop the newest n elements from the AnchoredSeq. The anchor does not change.

takeOldestAnchorable v a b ⇒ IntAnchoredSeq v a b → AnchoredSeq v a b Source #

$$O(\log(\min(i,n-i))$$. Take the oldest n elements from the AnchoredSeq. The anchor does not change.

dropWhileNewestAnchorable v a b ⇒ (b → Bool) → AnchoredSeq v a b → AnchoredSeq v a b Source #

$$O(n)$$. Drop the newest elements that satisfy the predicate, keeping the remainder. The anchor does not change.

takeWhileOldestAnchorable v a b ⇒ (b → Bool) → AnchoredSeq v a b → AnchoredSeq v a b Source #

$$O(n)$$. Take the oldest elements that satisfy the predicate. The anchor does not change.

lengthAnchorable v a b ⇒ AnchoredSeq v a b → Int Source #

$$O(1)$$. Return the number of elements. The anchor is not counted.

nullAnchoredSeq v a b → Bool Source #

$$O(1)$$. The anchor is not counted.

## Update type and operations

data ChainUpdate block a Source #

A representation of two actions to update a chain: add a block or roll back to a previous point.

The type parameter a is there to allow a Functor instance. Typically, it will be instantiated with block itself.

Constructors

#### Instances

Instances details
 Functor (ChainUpdate block) Source # Instance detailsDefined in Ouroboros.Network.Block Methodsfmap ∷ (a → b) → ChainUpdate block a → ChainUpdate block b Source #(<\$) ∷ a → ChainUpdate block b → ChainUpdate block a Source # Foldable (ChainUpdate block) Source # Instance detailsDefined in Ouroboros.Network.Block Methodsfold ∷ Monoid m ⇒ ChainUpdate block m → m Source #foldMap ∷ Monoid m ⇒ (a → m) → ChainUpdate block a → m Source #foldMap' ∷ Monoid m ⇒ (a → m) → ChainUpdate block a → m Source #foldr ∷ (a → b → b) → b → ChainUpdate block a → b Source #foldr' ∷ (a → b → b) → b → ChainUpdate block a → b Source #foldl ∷ (b → a → b) → b → ChainUpdate block a → b Source #foldl' ∷ (b → a → b) → b → ChainUpdate block a → b Source #foldr1 ∷ (a → a → a) → ChainUpdate block a → a Source #foldl1 ∷ (a → a → a) → ChainUpdate block a → a Source #toList ∷ ChainUpdate block a → [a] Source #null ∷ ChainUpdate block a → Bool Source #length ∷ ChainUpdate block a → Int Source #elem ∷ Eq a ⇒ a → ChainUpdate block a → Bool Source #maximum ∷ Ord a ⇒ ChainUpdate block a → a Source #minimum ∷ Ord a ⇒ ChainUpdate block a → a Source #sum ∷ Num a ⇒ ChainUpdate block a → a Source #product ∷ Num a ⇒ ChainUpdate block a → a Source # Traversable (ChainUpdate block) Source # Instance detailsDefined in Ouroboros.Network.Block Methodstraverse ∷ Applicative f ⇒ (a → f b) → ChainUpdate block a → f (ChainUpdate block b) Source #sequenceA ∷ Applicative f ⇒ ChainUpdate block (f a) → f (ChainUpdate block a) Source #mapM ∷ Monad m ⇒ (a → m b) → ChainUpdate block a → m (ChainUpdate block b) Source #sequence ∷ Monad m ⇒ ChainUpdate block (m a) → m (ChainUpdate block a) Source # (StandardHash block, Eq a) ⇒ Eq (ChainUpdate block a) Source # Instance detailsDefined in Ouroboros.Network.Block Methods(==) ∷ ChainUpdate block a → ChainUpdate block a → Bool Source #(/=) ∷ ChainUpdate block a → ChainUpdate block a → Bool Source # (StandardHash block, Show a) ⇒ Show (ChainUpdate block a) Source # Instance detailsDefined in Ouroboros.Network.Block MethodsshowsPrec ∷ Int → ChainUpdate block a → ShowS Source #show ∷ ChainUpdate block a → String Source #showList ∷ [ChainUpdate block a] → ShowS Source #

addBlockHasHeader block ⇒ block → AnchoredFragment block → AnchoredFragment block Source #

$$O(1)$$. Add a block to the right of the anchored fragment.

Synonym for :>.

rollbackHasHeader block ⇒ Point block → AnchoredFragment block → Maybe (AnchoredFragment block) Source #

$$O(\log(\min(i,n-i))$$. If the Point is within the bounds of the AnchoredFragment (see withinFragmentBounds), roll back the anchored fragment such that its head is the given point. In case the given point was the anchor point, the returned anchored fragment will be empty.

In other words, remove blocks from the end of the AnchoredFragment until the given Point is the head. If the given Point is not within the bounds of the AnchoredFragment, return Nothing.

applyChainUpdateHasHeader block ⇒ ChainUpdate block block → AnchoredFragment block → Maybe (AnchoredFragment block) Source #

applyChainUpdatesHasHeader block ⇒ [ChainUpdate block block] → AnchoredFragment block → Maybe (AnchoredFragment block) Source #

# Special operations

pointOnFragmentHasHeader block ⇒ Point block → AnchoredFragment block → Bool Source #

$$O(\log(\min(i,n-i))$$. Does the fragment contain a block with the given point? The anchor point is ignored.

withinFragmentBoundsHasHeader block ⇒ Point block → AnchoredFragment block → Bool Source #

$$O(\log(\min(i,n-i))$$. Is the point within the fragment bounds? Either the point is the anchor point, or it corresponds to a block "on" the fragment.

findFirstPointHasHeader block ⇒ [Point block] → AnchoredFragment block → Maybe (Point block) Source #

$$O(p \log(\min(i,n-i))$$. Find the first Point in the list of points that is within the fragment bounds. Return Nothing if none of them are.

successorBlockHasHeader block ⇒ Point block → AnchoredFragment block → Maybe block Source #

$$O(\log(\min(i,n-i))$$. Find the block after the given point. If the given point is the anchor point, then the first block is returned (if there is one).

selectPoints ∷ ∀ block. HasHeader block ⇒ [Int] → AnchoredFragment block → [Point block] Source #

$$O(o \log(\min(i,n-i)))$$. Select a bunch of Points based on offsets from the head of the anchored fragment. This is used in the chain consumer protocol as part of finding the intersection between a local and remote chain.

The list of offsets must be increasing monotonically.

The typical pattern is to use a selection of offsets covering the last K blocks, biased towards more recent blocks. For example:

selectPoints (0 : [ fib n | n <- [1 .. 17] ])

Only for offsets within the bounds of the anchored fragment will there be points in the returned list.

Note: offset n, where n equals the length of the anchored fragment, corresponds to the anchor point. When the fragment is empty, offset 0 will thus correspond to the anchor point.

isPrefixOf ∷ ∀ v a b. (Eq a, Eq b) ⇒ AnchoredSeq v a b → AnchoredSeq v a b → Bool Source #

$$O(\max(n_1, n_2))$$. Check whether the first anchored sequence is a prefix of the second. Comparisons are done based on the Eq instances.

The two AnchoredSeqs must have the same anchor, otherwise the first cannot be a prefix of the second.

splitAfterPoint ∷ ∀ block1 block2. (HasHeader block1, HeaderHash block1 ~ HeaderHash block2) ⇒ AnchoredFragment block1 → Point block2 → Maybe (AnchoredFragment block1, AnchoredFragment block1) Source #

$$O(\log(\min(i,n-i))$$. Split the AnchoredFragment after the given Point. Return Nothing if given Point is not within the fragment bounds (withinFragmentBounds).

The given Point may be the anchor point of the fragment, in which case the empty fragment with the given anchor point and the original fragment are returned.

POSTCONDITION: when Just (before, after) = splitAfterPoint f pt, then: * anchorPoint before == anchorPoint f * headPoint before == pt * anchorPoint after == pt * headPoint after == headPoint f * join before after == Just f

splitBeforePoint ∷ ∀ block1 block2. (HasHeader block1, HeaderHash block1 ~ HeaderHash block2) ⇒ AnchoredFragment block1 → Point block2 → Maybe (AnchoredFragment block1, AnchoredFragment block1) Source #

$$O(\log(\min(i,n-i))$$. Split the AnchoredFragment before the given Point. Return Nothing if given Point is not on the fragment (pointOnFragment).

This means that Nothing is returned if the given Point is the anchor point of the fragment.

POSTCONDITION: joining (join) the two fragments gives back the original fragment.

POSTCONDITION: the last block (oldest) on the second fragment corresponds to the given point.

sliceRangeHasHeader block ⇒ AnchoredFragment block → Point block → Point block → Maybe (AnchoredFragment block) Source #

Select a slice of an anchored fragment between two points, inclusive.

Both points must exist on the chain, in order, or the result is Nothing.

joinHasHeader block ⇒ AnchoredFragment block → AnchoredFragment block → Maybe (AnchoredFragment block) Source #

$$O(\log(\min(n_1, n_2)))$$. Join two anchored fragments if the anchor of the second fragment is the head (newest block) of the first fragment.

If the first fragment is empty, it can be joined if its anchor is the same as the second fragment's anchor.

The returned fragment will have the same anchor as the first fragment.

intersect ∷ ∀ block1 block2. (HasHeader block1, HasHeader block2, HeaderHash block1 ~ HeaderHash block2) ⇒ AnchoredFragment block1 → AnchoredFragment block2 → Maybe (AnchoredFragment block1, AnchoredFragment block2, AnchoredFragment block1, AnchoredFragment block2) Source #

$$O(n_2 \log(n_1))$$. Look for the most recent intersection of two AnchoredFragments c1 and c2.

The fragments need not have the same anchor point.

If they intersect, i.e., share a common Point (possibly the anchor point), then return a tuple of:

• p1: the prefix of the first fragment
• p2: the prefix of the second fragment
• s1: the suffix of the first fragment
• s2: the suffix of the second fragment

p1 and p2 will have the same head (possibly an anchor point), namely the intersection point i. The original chain c1 can be obtained by putting s1 after p1, similarly for c2: by putting s2 after p2:

Just c1 = join p1 s1
Just c2 = join p2 s2


Take for example the following two fragments that share blocks 4 and 5. The two fragments are fragments of the same chain, but don't contain all blocks of the original chain. The anchor points of the fragments are indicated with an asterisk (*). The -A and -B suffixes denote that blocks are part of a fork of the chain.


┆ 1*┆
├───┤
│ 2 │     ┆ 2*┆
├───┤     ├───┤
│ 4 │     │ 4 │
├───┤     ├───┤
│ 5 │     │ 5 │
────┼───┼─────┼───┼───
│ 6A│     │ 6B│
└───┘     ├───┤
│ 8B│
└───┘
c1        c2

The intersection of c1 and c2 is block 5 (the last Point the two fragments have in common) and we return the following fragments:


┆ 1*┆
├───┤
│ 2 │     ┆ 2*┆
├───┤     ├───┤
│ 4 │     │ 4 │
├───┤     ├───┤
│ 5 │     │ 5 │      ┆ 5*┆     ┆ 5*┆
────┴───┴─────┴───┴──────┼───┼─────┼───┼──
│ 6A│     │ 6B│
└───┘     ├───┤
│ 8B│
└───┘
Just (p1,       p2,        s1,       s2)

The intersection point will be the anchor point of fragments s1 and s2. Fragment p1 will have the same anchor as c1 and p2 will have the same anchor as c2.

Note that an empty fragment can still intersect another fragment, as its anchor point can still intersect the other fragment. In that case the respective prefix and suffix are both equal to original empty fragment. Additionally, two empty fragments intersect if their anchor points are equal, in which case all prefixes and suffixes are equal to the empty fragment with the anchor point in question.

intersectionPoint ∷ (HasHeader block1, HasHeader block2, HeaderHash block1 ~ HeaderHash block2) ⇒ AnchoredFragment block1 → AnchoredFragment block2 → Maybe (Point block1) Source #

$$O(n_2 \log(n_1))$$. Look for the most recent intersection point of two AnchoredFragments

The fragments need not have the same anchor point.

Reusing the example in the docstring of intersect: this function will return the anchor point 5*.

mapAnchoredFragment ∷ (HasHeader block2, HeaderHash block1 ~ HeaderHash block2) ⇒ (block1 → block2) → AnchoredFragment block1 → AnchoredFragment block2 Source #

$$O(n)$$. Maps over the chain's blocks. This is not allowed to change the block Points, or it would create an invalid chain. The anchorPoint is not affected.

Arguments

 ∷ ∀ v a b. Anchorable v a b ⇒ Word64 n → AnchoredSeq v a b → AnchoredSeq v a b

Take the n newest elements from the anchored sequence.

WARNING: this may change the anchor

When the anchored sequence contains fewer than n elements, the anchored sequence will be returned unmodified.

Arguments

 ∷ ∀ v a b. Anchorable v a b ⇒ (b → Bool) Filtering predicate → AnchoredSeq v a b → [AnchoredSeq v a b]

$$O\(n$$ ). Variation on filterWithStop without a stop condition.

Arguments

 ∷ ∀ v a b. Anchorable v a b ⇒ (b → Bool) Filtering predicate → (b → Bool) Stop condition → AnchoredSeq v a b → [AnchoredSeq v a b]

$$O(n + r * \log(\min(i,n-i))$$ where r is the number of consecutive ranges of elements to be included in the result.

Filter out elements that don't match the predicate.

As filtering removes elements the result is a sequence of disconnected sequences. The sequences are in the original order and are of maximum size.

As soon as the stop condition is true, the filtering stops and the remaining sequence (starting with the first element for which the stop condition is true) is the final sequence in the returned list.

The stop condition wins from the filtering predicate: if the stop condition is true for an element, but the filter predicate not, then the element still ends up in final sequence.

For example, given the sequence containing [0: 1, 2, 3, 4, 5, 6] where the anchor is separated from the elements by ::

filter         odd        -> [[0: 1], [2: 3], [4: 5]]
filterWithStop odd (>= 4) -> [[0: 1], [2: 3], [3: 4, 5, 6]]

# Helper functions

prettyPrintString → (Point block → String) → (block → String) → AnchoredFragment block → String Source #

# Reference implementations for testing

pointOnFragmentSpecHasHeader block ⇒ Point block → AnchoredFragment block → Bool Source #

$$O(n)$$. Specification of pointOnFragment.

Use pointOnFragment, as it should be faster.

This function is used to verify whether pointOnFragment behaves as expected.

selectPointsSpecHasHeader block ⇒ [Int] → AnchoredFragment block → [Point block] Source #

$$O(o * n)$$. Specification of selectPoints.

Use selectPoints, as it should be faster.

This function is used to verify whether selectPoints behaves as expected.

Arguments

 ∷ ∀ v a b. Anchorable v a b ⇒ (b → Bool) Filtering predicate → (b → Bool) Stop condition → AnchoredSeq v a b → [AnchoredSeq v a b]

$$O\(n$$ ). Naive reference implementation of filterWithStop.

While the asymptotic complexity of this function is better than that of filterWithStop, the allocation cost is high. This function deconstructs and reconstructs the anchored sequence (until the stop condition is reached), even when no elements are removed.