Safe Haskell | None |
---|---|
Language | Haskell2010 |
Ouroboros.Network.AnchoredFragment
Synopsis
- type AnchoredFragment block = AnchoredSeq ( WithOrigin SlotNo ) ( Anchor block) block
-
data
AnchoredSeq
v a b
where
- pattern Empty :: Anchorable v a b => a -> AnchoredSeq v a b
- pattern (:>) :: Anchorable v a b => AnchoredSeq v a b -> b -> AnchoredSeq v a b
- pattern (:<) :: Anchorable v a b => b -> AnchoredSeq v a b -> AnchoredSeq v a b
- anchor :: AnchoredSeq v a b -> a
- anchorPoint :: AnchoredFragment block -> Point block
- anchorBlockNo :: AnchoredFragment block -> WithOrigin BlockNo
-
data
Anchor
block
- = AnchorGenesis
- | Anchor ! SlotNo !( HeaderHash block) ! BlockNo
- anchorFromBlock :: HasHeader block => block -> Anchor block
- anchorFromPoint :: Point block -> BlockNo -> Anchor block
- anchorToPoint :: Anchor block -> Point block
- anchorToSlotNo :: Anchor block -> WithOrigin SlotNo
- anchorToBlockNo :: Anchor block -> WithOrigin BlockNo
- anchorToHash :: Anchor block -> ChainHash block
- anchorIsGenesis :: Anchor block -> Bool
- anchorToHeaderFields :: Anchor block -> WithOrigin ( HeaderFields block)
- anchorToTip :: HeaderHash a ~ HeaderHash b => Anchor a -> Tip b
- castAnchor :: HeaderHash a ~ HeaderHash b => Anchor a -> Anchor b
- valid :: HasFullHeader block => AnchoredFragment block -> Bool
- validExtension :: HasFullHeader block => AnchoredFragment block -> block -> Bool
-
class
(
StandardHash
b,
Typeable
b) =>
HasHeader
b
where
- getHeaderFields :: b -> HeaderFields b
-
newtype
Point
block =
Point
{
- getPoint :: WithOrigin ( Block SlotNo ( HeaderHash block))
- castPoint :: Coercible ( HeaderHash b) ( HeaderHash b') => Point b -> Point b'
- blockPoint :: HasHeader block => block -> Point block
- headPoint :: HasHeader block => AnchoredFragment block -> Point block
- headAnchor :: forall v a b. Anchorable v a b => AnchoredSeq v a b -> a
- headSlot :: HasHeader block => AnchoredFragment block -> WithOrigin SlotNo
- headHash :: HasHeader block => AnchoredFragment block -> ChainHash block
- headBlockNo :: HasHeader block => AnchoredFragment block -> WithOrigin BlockNo
- head :: Anchorable v a b => AnchoredSeq v a b -> Either a b
- last :: Anchorable v a b => AnchoredSeq v a b -> Either a b
- lastPoint :: HasHeader block => AnchoredFragment block -> Point block
- lastSlot :: HasHeader block => AnchoredFragment block -> WithOrigin SlotNo
- toNewestFirst :: AnchoredSeq v a b -> [b]
- toOldestFirst :: AnchoredSeq v a b -> [b]
- fromNewestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b
- fromOldestFirst :: Anchorable v a b => a -> [b] -> AnchoredSeq v a b
- splitAt :: Anchorable v a b => Int -> AnchoredSeq v a b -> ( AnchoredSeq v a b, AnchoredSeq v a b)
- dropNewest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b
- takeOldest :: Anchorable v a b => Int -> AnchoredSeq v a b -> AnchoredSeq v a b
- dropWhileNewest :: Anchorable v a b => (b -> Bool ) -> AnchoredSeq v a b -> AnchoredSeq v a b
- takeWhileOldest :: Anchorable v a b => (b -> Bool ) -> AnchoredSeq v a b -> AnchoredSeq v a b
- length :: Anchorable v a b => AnchoredSeq v a b -> Int
- null :: AnchoredSeq v a b -> Bool
- data ChainUpdate block a
- addBlock :: HasHeader block => block -> AnchoredFragment block -> AnchoredFragment block
- rollback :: HasHeader block => Point block -> AnchoredFragment block -> Maybe ( AnchoredFragment block)
- applyChainUpdate :: HasHeader block => ChainUpdate block block -> AnchoredFragment block -> Maybe ( AnchoredFragment block)
- applyChainUpdates :: HasHeader block => [ ChainUpdate block block] -> AnchoredFragment block -> Maybe ( AnchoredFragment block)
- pointOnFragment :: HasHeader block => Point block -> AnchoredFragment block -> Bool
- withinFragmentBounds :: HasHeader block => Point block -> AnchoredFragment block -> Bool
- findFirstPoint :: HasHeader block => [ Point block] -> AnchoredFragment block -> Maybe ( Point block)
- successorBlock :: HasHeader block => Point block -> AnchoredFragment block -> Maybe block
- selectPoints :: forall block. HasHeader block => [ Int ] -> AnchoredFragment block -> [ Point block]
- isPrefixOf :: forall v a b. ( Eq a, Eq b) => AnchoredSeq v a b -> AnchoredSeq v a b -> Bool
- splitAfterPoint :: forall block1 block2. ( HasHeader block1, HeaderHash block1 ~ HeaderHash block2) => AnchoredFragment block1 -> Point block2 -> Maybe ( AnchoredFragment block1, AnchoredFragment block1)
- splitBeforePoint :: forall block1 block2. ( HasHeader block1, HeaderHash block1 ~ HeaderHash block2) => AnchoredFragment block1 -> Point block2 -> Maybe ( AnchoredFragment block1, AnchoredFragment block1)
- sliceRange :: HasHeader block => AnchoredFragment block -> Point block -> Point block -> Maybe ( AnchoredFragment block)
- join :: HasHeader block => AnchoredFragment block -> AnchoredFragment block -> Maybe ( AnchoredFragment block)
- intersect :: forall block1 block2. ( HasHeader block1, HasHeader block2, HeaderHash block1 ~ HeaderHash block2) => AnchoredFragment block1 -> AnchoredFragment block2 -> Maybe ( AnchoredFragment block1, AnchoredFragment block2, AnchoredFragment block1, AnchoredFragment block2)
- intersectionPoint :: ( HasHeader block1, HasHeader block2, HeaderHash block1 ~ HeaderHash block2) => AnchoredFragment block1 -> AnchoredFragment block2 -> Maybe ( Point block1)
- mapAnchoredFragment :: ( HasHeader block2, HeaderHash block1 ~ HeaderHash block2) => (block1 -> block2) -> AnchoredFragment block1 -> AnchoredFragment block2
- anchorNewest :: forall v a b. Anchorable v a b => Word64 -> AnchoredSeq v a b -> AnchoredSeq v a b
- filter :: forall v a b. Anchorable v a b => (b -> Bool ) -> AnchoredSeq v a b -> [ AnchoredSeq v a b]
- filterWithStop :: forall v a b. Anchorable v a b => (b -> Bool ) -> (b -> Bool ) -> AnchoredSeq v a b -> [ AnchoredSeq v a b]
- prettyPrint :: String -> ( Point block -> String ) -> (block -> String ) -> AnchoredFragment block -> String
- pointOnFragmentSpec :: HasHeader block => Point block -> AnchoredFragment block -> Bool
- selectPointsSpec :: HasHeader block => [ Int ] -> AnchoredFragment block -> [ Point block]
- filterWithStopSpec :: forall v a b. Anchorable v a b => (b -> Bool ) -> (b -> Bool ) -> AnchoredSeq v a b -> [ AnchoredSeq v a b]
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
|
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
( Eq a, Eq b) => Eq ( AnchoredSeq v a b) Source # | |
Defined 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 # | |
Defined in Ouroboros.Network.AnchoredSeq |
|
Generic ( AnchoredSeq v a b) Source # | |
Defined in Ouroboros.Network.AnchoredSeq Methods from :: 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 # | |
Defined in Ouroboros.Network.AnchoredSeq |
|
type Rep ( AnchoredSeq v a b) Source # | |
Defined in Ouroboros.Network.AnchoredSeq |
anchor :: AnchoredSeq v a b -> a Source #
anchorPoint :: AnchoredFragment block -> Point block Source #
Return the
Point
corresponding to the anchor.
anchorBlockNo :: AnchoredFragment block -> WithOrigin BlockNo Source #
Return the
BlocKno
corresponding to the anchor.
Anchor
Anchor of an
AnchoredFragment
Constructors
AnchorGenesis |
The fragment is anchored at genesis |
Anchor ! SlotNo !( HeaderHash block) ! BlockNo |
The fragment is anchored after genesis
We don't use the
Note that we don't use
Moreover, we don't reuse the
|
Instances
anchorFromBlock :: HasHeader 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.
anchorFromPoint :: Point block -> BlockNo -> Anchor 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.
anchorToPoint :: Anchor block -> Point block Source #
Compute which
Point
this anchor corresponds to
anchorToSlotNo :: Anchor block -> WithOrigin SlotNo Source #
Extract the
SlotNo
from the anchor
anchorToBlockNo :: Anchor block -> WithOrigin BlockNo Source #
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!)
anchorToHash :: Anchor block -> ChainHash block Source #
Extract the hash from the anchor
Returns
GenesisHash
if the anchor is
AnchorGenesis
.
anchorIsGenesis :: Anchor block -> Bool Source #
Does this anchor represent genesis (i.e., empty chain)?
anchorToHeaderFields :: Anchor block -> WithOrigin ( HeaderFields block) Source #
anchorToTip :: HeaderHash a ~ HeaderHash b => Anchor a -> Tip b Source #
castAnchor :: HeaderHash a ~ HeaderHash b => Anchor a -> Anchor b Source #
valid :: HasFullHeader block => AnchoredFragment block -> Bool Source #
\( O(n) \) .
validExtension :: HasFullHeader 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
getHeaderFields :: b -> HeaderFields b Source #
Instances
HasHeader BlockHeader Source # | |
Defined in Ouroboros.Network.Testing.ConcreteBlock Methods getHeaderFields :: BlockHeader -> HeaderFields BlockHeader Source # |
|
HasHeader Block Source # | |
Defined in Ouroboros.Network.Testing.ConcreteBlock Methods getHeaderFields :: Block -> HeaderFields Block Source # |
|
( StandardHash b, Typeable b) => HasHeader ( HeaderFields b) Source # | |
Defined in Ouroboros.Network.Block Methods getHeaderFields :: HeaderFields b -> HeaderFields ( HeaderFields b) 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 | |
Fields
|
Instances
StandardHash block => Eq ( Point block) Source # | |
StandardHash block => Ord ( Point block) Source # | |
Defined in Ouroboros.Network.Block Methods compare :: 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 # |
|
StandardHash block => Show ( Point block) Source # | |
Generic ( Point block) Source # | |
StandardHash block => NoThunks ( Point block) Source # | |
Serialise ( HeaderHash block) => Serialise ( Point block) Source # | |
ShowProxy block => ShowProxy ( Point block :: Type ) Source # | |
type Rep ( Point block) Source # | |
Defined in Ouroboros.Network.Block
type
Rep
(
Point
block) =
D1
('
MetaData
"Point" "Ouroboros.Network.Block" "ouroboros-network-0.1.0.1-2UgqzRSdBh49QYumtriFSI" '
True
) (
C1
('
MetaCons
"Point" '
PrefixI
'
True
) (
S1
('
MetaSel
('
Just
"getPoint") '
NoSourceUnpackedness
'
NoSourceStrictness
'
DecidedLazy
) (
Rec0
(
WithOrigin
(
Block
SlotNo
(
HeaderHash
block))))))
|
castPoint :: Coercible ( HeaderHash b) ( HeaderHash b') => Point b -> Point b' Source #
blockPoint :: HasHeader block => block -> Point block Source #
AnchoredFragment construction and inspection
Head inspection
headPoint :: HasHeader block => AnchoredFragment block -> Point block Source #
\( O(1) \) . When the fragment is empty, the anchor point is returned.
headAnchor :: forall 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.
headSlot :: HasHeader block => AnchoredFragment block -> WithOrigin SlotNo Source #
\( O(1) \) . When the fragment is empty, the slot of the anchor point is returned, which may be origin (no slot).
headHash :: HasHeader block => AnchoredFragment block -> ChainHash block Source #
\( O(1) \) . When the fragment is empty, the hash of the anchor point is returned.
headBlockNo :: HasHeader block => AnchoredFragment block -> WithOrigin BlockNo Source #
\( O(1) \) . When the fragment is empty, the block number of the anchor point is returned.
Basic operations
head :: Anchorable 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.
last :: Anchorable 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.
lastPoint :: HasHeader block => AnchoredFragment block -> Point block Source #
\( O(1) \) . When the fragment is empty, the anchor point is returned.
lastSlot :: HasHeader 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.
toNewestFirst :: AnchoredSeq v a b -> [b] Source #
\( O(n) \)
. Return the elements in the
AnchoredSeq
in newest-to-oldest
order.
toOldestFirst :: AnchoredSeq v a b -> [b] Source #
\( O(n) \)
. Return the elements in the
AnchoredSeq
in oldest-to-newest
order.
fromNewestFirst :: Anchorable 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.
fromOldestFirst :: Anchorable 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.
splitAt :: Anchorable v a b => Int -> AnchoredSeq 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
dropNewest :: Anchorable v a b => Int -> AnchoredSeq 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.
takeOldest :: Anchorable v a b => Int -> AnchoredSeq 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.
dropWhileNewest :: Anchorable 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.
takeWhileOldest :: Anchorable 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.
length :: Anchorable v a b => AnchoredSeq v a b -> Int Source #
\( O(1) \) . Return the number of elements. The anchor is not counted.
null :: AnchoredSeq 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.
Instances
Functor ( ChainUpdate block) Source # | |
Defined in Ouroboros.Network.Block Methods fmap :: (a -> b) -> ChainUpdate block a -> ChainUpdate block b Source # (<$) :: a -> ChainUpdate block b -> ChainUpdate block a Source # |
|
Foldable ( ChainUpdate block) Source # | |
Defined in Ouroboros.Network.Block Methods fold :: 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 # | |
Defined in Ouroboros.Network.Block Methods traverse :: 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 # | |
Defined 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 # | |
Defined in Ouroboros.Network.Block |
addBlock :: HasHeader block => block -> AnchoredFragment block -> AnchoredFragment block Source #
\( O(1) \) . Add a block to the right of the anchored fragment.
Synonym for
:>
.
rollback :: HasHeader 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
.
applyChainUpdate :: HasHeader block => ChainUpdate block block -> AnchoredFragment block -> Maybe ( AnchoredFragment block) Source #
applyChainUpdates :: HasHeader block => [ ChainUpdate block block] -> AnchoredFragment block -> Maybe ( AnchoredFragment block) Source #
Special operations
pointOnFragment :: HasHeader 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.
withinFragmentBounds :: HasHeader 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.
findFirstPoint :: HasHeader block => [ Point block] -> AnchoredFragment block -> Maybe ( Point block) Source #
successorBlock :: HasHeader 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 :: forall block. HasHeader block => [ Int ] -> AnchoredFragment block -> [ Point block] Source #
\( O(o \log(\min(i,n-i))) \)
. Select a bunch of
Point
s 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 :: forall 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
AnchoredSeq
s must have the same anchor, otherwise the first cannot
be a prefix of the second.
splitAfterPoint :: forall 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 :: forall 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.
sliceRange :: HasHeader 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
.
join :: HasHeader 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 :: forall 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
AnchoredFragment
s
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
AnchoredFragment
s
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
Point
s, or it would create an invalid chain. The
anchorPoint
is not
affected.
Arguments
:: forall 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
:: forall 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
:: forall 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
prettyPrint :: String -> ( Point block -> String ) -> (block -> String ) -> AnchoredFragment block -> String Source #
Reference implementations for testing
pointOnFragmentSpec :: HasHeader 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.
selectPointsSpec :: HasHeader 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
:: forall 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.