pub mod migration;
use std::{sync::Arc, ops::Add, collections::BTreeMap, borrow::{Borrow, BorrowMut}};
use parking_lot::Mutex;
use codec::{Encode, Decode};
use fork_tree::ForkTree;
use sc_client_api::utils::is_descendent_of;
use sp_blockchain::{HeaderMetadata, HeaderBackend, Error as ClientError};
use sp_runtime::traits::{Block as BlockT, NumberFor, One, Zero};
pub trait IsDescendentOfBuilder<Hash> {
type Error: std::error::Error;
type IsDescendentOf: Fn(&Hash, &Hash) -> Result<bool, Self::Error>;
fn build_is_descendent_of(&self, current: Option<(Hash, Hash)>)
-> Self::IsDescendentOf;
}
pub fn descendent_query<H, Block>(client: &H) -> HeaderBackendDescendentBuilder<&H, Block> {
HeaderBackendDescendentBuilder(client, std::marker::PhantomData)
}
pub struct HeaderBackendDescendentBuilder<H, Block>(H, std::marker::PhantomData<Block>);
impl<'a, H, Block> IsDescendentOfBuilder<Block::Hash>
for HeaderBackendDescendentBuilder<&'a H, Block> where
H: HeaderBackend<Block> + HeaderMetadata<Block, Error=ClientError>,
Block: BlockT,
{
type Error = ClientError;
type IsDescendentOf = Box<dyn Fn(&Block::Hash, &Block::Hash) -> Result<bool, ClientError> + 'a>;
fn build_is_descendent_of(&self, current: Option<(Block::Hash, Block::Hash)>)
-> Self::IsDescendentOf
{
Box::new(is_descendent_of(self.0, current))
}
}
pub trait Epoch {
type NextEpochDescriptor;
type Slot: Ord + Copy;
fn start_slot(&self) -> Self::Slot;
fn end_slot(&self) -> Self::Slot;
fn increment(&self, descriptor: Self::NextEpochDescriptor) -> Self;
}
impl<'a, E: Epoch> From<&'a E> for EpochHeader<E> {
fn from(epoch: &'a E) -> EpochHeader<E> {
Self {
start_slot: epoch.start_slot(),
end_slot: epoch.end_slot(),
}
}
}
#[derive(Eq, PartialEq, Encode, Decode, Debug)]
pub struct EpochHeader<E: Epoch> {
pub start_slot: E::Slot,
pub end_slot: E::Slot,
}
impl<E: Epoch> Clone for EpochHeader<E> {
fn clone(&self) -> Self {
Self {
start_slot: self.start_slot,
end_slot: self.end_slot,
}
}
}
#[derive(PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug)]
pub enum EpochIdentifierPosition {
Genesis0,
Genesis1,
Regular,
}
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Debug)]
pub struct EpochIdentifier<Hash, Number> {
pub position: EpochIdentifierPosition,
pub hash: Hash,
pub number: Number,
}
pub enum ViableEpoch<E, ERef = E> {
UnimportedGenesis(E),
Signaled(ERef),
}
impl<E, ERef> AsRef<E> for ViableEpoch<E, ERef> where
ERef: Borrow<E>,
{
fn as_ref(&self) -> &E {
match *self {
ViableEpoch::UnimportedGenesis(ref e) => e,
ViableEpoch::Signaled(ref e) => e.borrow(),
}
}
}
impl<E, ERef> AsMut<E> for ViableEpoch<E, ERef> where
ERef: BorrowMut<E>,
{
fn as_mut(&mut self) -> &mut E {
match *self {
ViableEpoch::UnimportedGenesis(ref mut e) => e,
ViableEpoch::Signaled(ref mut e) => e.borrow_mut(),
}
}
}
impl<E, ERef> ViableEpoch<E, ERef> where
E: Epoch + Clone,
ERef: Borrow<E>,
{
pub fn into_cloned_inner(self) -> E {
match self {
ViableEpoch::UnimportedGenesis(e) => e,
ViableEpoch::Signaled(e) => e.borrow().clone(),
}
}
pub fn into_cloned(self) -> ViableEpoch<E, E> {
match self {
ViableEpoch::UnimportedGenesis(e) =>
ViableEpoch::UnimportedGenesis(e),
ViableEpoch::Signaled(e) => ViableEpoch::Signaled(e.borrow().clone()),
}
}
pub fn increment(
&self,
next_descriptor: E::NextEpochDescriptor
) -> IncrementedEpoch<E> {
let next = self.as_ref().increment(next_descriptor);
let to_persist = match *self {
ViableEpoch::UnimportedGenesis(ref epoch_0) =>
PersistedEpoch::Genesis(epoch_0.clone(), next),
ViableEpoch::Signaled(_) => PersistedEpoch::Regular(next),
};
IncrementedEpoch(to_persist)
}
}
#[derive(PartialEq, Eq, Clone, Debug)]
pub enum ViableEpochDescriptor<Hash, Number, E: Epoch> {
UnimportedGenesis(E::Slot),
Signaled(EpochIdentifier<Hash, Number>, EpochHeader<E>)
}
impl<Hash, Number, E: Epoch> ViableEpochDescriptor<Hash, Number, E> {
pub fn start_slot(&self) -> E::Slot {
match self {
Self::UnimportedGenesis(start_slot) => *start_slot,
Self::Signaled(_, header) => header.start_slot,
}
}
}
#[derive(Clone, Encode, Decode, Debug)]
pub enum PersistedEpoch<E: Epoch> {
Genesis(E, E),
Regular(E),
}
impl<'a, E: Epoch> From<&'a PersistedEpoch<E>> for PersistedEpochHeader<E> {
fn from(epoch: &'a PersistedEpoch<E>) -> Self {
match epoch {
PersistedEpoch::Genesis(ref epoch_0, ref epoch_1) =>
PersistedEpochHeader::Genesis(epoch_0.into(), epoch_1.into()),
PersistedEpoch::Regular(ref epoch_n) =>
PersistedEpochHeader::Regular(epoch_n.into()),
}
}
}
#[derive(Encode, Decode, PartialEq, Eq)]
pub enum PersistedEpochHeader<E: Epoch> {
Genesis(EpochHeader<E>, EpochHeader<E>),
Regular(EpochHeader<E>),
}
impl<E: Epoch> Clone for PersistedEpochHeader<E> {
fn clone(&self) -> Self {
match self {
Self::Genesis(epoch_0, epoch_1) => Self::Genesis(epoch_0.clone(), epoch_1.clone()),
Self::Regular(epoch_n) => Self::Regular(epoch_n.clone()),
}
}
}
#[must_use = "Freshly-incremented epoch must be imported with `EpochChanges::import`"]
pub struct IncrementedEpoch<E: Epoch>(PersistedEpoch<E>);
impl<E: Epoch> AsRef<E> for IncrementedEpoch<E> {
fn as_ref(&self) -> &E {
match self.0 {
PersistedEpoch::Genesis(_, ref epoch_1) => epoch_1,
PersistedEpoch::Regular(ref epoch_n) => epoch_n,
}
}
}
#[derive(Clone, Encode, Decode)]
pub struct EpochChanges<Hash, Number, E: Epoch> {
inner: ForkTree<Hash, Number, PersistedEpochHeader<E>>,
epochs: BTreeMap<(Hash, Number), PersistedEpoch<E>>,
}
fn fake_head_hash<H: AsRef<[u8]> + AsMut<[u8]> + Clone>(parent_hash: &H) -> H {
let mut h = parent_hash.clone();
h.as_mut()[0] ^= 0b10000000;
h
}
impl<Hash, Number, E: Epoch> Default for EpochChanges<Hash, Number, E> where
Hash: PartialEq + Ord,
Number: Ord,
{
fn default() -> Self {
EpochChanges { inner: ForkTree::new(), epochs: BTreeMap::new() }
}
}
impl<Hash, Number, E: Epoch> EpochChanges<Hash, Number, E> where
Hash: PartialEq + Ord + AsRef<[u8]> + AsMut<[u8]> + Copy,
Number: Ord + One + Zero + Add<Output=Number> + Copy,
{
pub fn new() -> Self {
Self::default()
}
pub fn rebalance(&mut self) {
self.inner.rebalance()
}
pub fn map<B, F>(self, mut f: F) -> EpochChanges<Hash, Number, B> where
B: Epoch<Slot=E::Slot>,
F: FnMut(&Hash, &Number, E) -> B,
{
EpochChanges {
inner: self.inner.map(&mut |_, _, header| {
match header {
PersistedEpochHeader::Genesis(epoch_0, epoch_1) => {
PersistedEpochHeader::Genesis(
EpochHeader {
start_slot: epoch_0.start_slot,
end_slot: epoch_0.end_slot,
},
EpochHeader {
start_slot: epoch_1.start_slot,
end_slot: epoch_1.end_slot,
},
)
},
PersistedEpochHeader::Regular(epoch_n) => {
PersistedEpochHeader::Regular(
EpochHeader {
start_slot: epoch_n.start_slot,
end_slot: epoch_n.end_slot,
},
)
},
}
}),
epochs: self.epochs.into_iter().map(|((hash, number), epoch)| {
let bepoch = match epoch {
PersistedEpoch::Genesis(epoch_0, epoch_1) => {
PersistedEpoch::Genesis(
f(&hash, &number, epoch_0),
f(&hash, &number, epoch_1),
)
},
PersistedEpoch::Regular(epoch_n) => {
PersistedEpoch::Regular(
f(&hash, &number, epoch_n)
)
},
};
((hash, number), bepoch)
}).collect(),
}
}
pub fn prune_finalized<D: IsDescendentOfBuilder<Hash>>(
&mut self,
descendent_of_builder: D,
hash: &Hash,
number: Number,
slot: E::Slot,
) -> Result<(), fork_tree::Error<D::Error>> {
let is_descendent_of = descendent_of_builder
.build_is_descendent_of(None);
let predicate = |epoch: &PersistedEpochHeader<E>| match *epoch {
PersistedEpochHeader::Genesis(_, ref epoch_1) =>
slot >= epoch_1.end_slot,
PersistedEpochHeader::Regular(ref epoch_n) =>
slot >= epoch_n.end_slot,
};
let removed = self.inner.prune(
hash,
&number,
&is_descendent_of,
&predicate,
)?;
for (hash, number, _) in removed {
self.epochs.remove(&(hash, number));
}
Ok(())
}
pub fn epoch(&self, id: &EpochIdentifier<Hash, Number>) -> Option<&E> {
self.epochs.get(&(id.hash, id.number))
.and_then(|v| {
match v {
PersistedEpoch::Genesis(ref epoch_0, _)
if id.position == EpochIdentifierPosition::Genesis0 => Some(epoch_0),
PersistedEpoch::Genesis(_, ref epoch_1)
if id.position == EpochIdentifierPosition::Genesis1 => Some(epoch_1),
PersistedEpoch::Regular(ref epoch_n)
if id.position == EpochIdentifierPosition::Regular => Some(epoch_n),
_ => None,
}
})
}
pub fn viable_epoch<G>(
&self,
descriptor: &ViableEpochDescriptor<Hash, Number, E>,
make_genesis: G,
) -> Option<ViableEpoch<E, &E>> where
G: FnOnce(E::Slot) -> E
{
match descriptor {
ViableEpochDescriptor::UnimportedGenesis(slot) => {
Some(ViableEpoch::UnimportedGenesis(make_genesis(*slot)))
},
ViableEpochDescriptor::Signaled(identifier, _) => {
self.epoch(&identifier).map(ViableEpoch::Signaled)
},
}
}
pub fn epoch_mut(&mut self, id: &EpochIdentifier<Hash, Number>) -> Option<&mut E> {
self.epochs.get_mut(&(id.hash, id.number))
.and_then(|v| {
match v {
PersistedEpoch::Genesis(ref mut epoch_0, _)
if id.position == EpochIdentifierPosition::Genesis0 => Some(epoch_0),
PersistedEpoch::Genesis(_, ref mut epoch_1)
if id.position == EpochIdentifierPosition::Genesis1 => Some(epoch_1),
PersistedEpoch::Regular(ref mut epoch_n)
if id.position == EpochIdentifierPosition::Regular => Some(epoch_n),
_ => None,
}
})
}
pub fn viable_epoch_mut<G>(
&mut self,
descriptor: &ViableEpochDescriptor<Hash, Number, E>,
make_genesis: G,
) -> Option<ViableEpoch<E, &mut E>> where
G: FnOnce(E::Slot) -> E
{
match descriptor {
ViableEpochDescriptor::UnimportedGenesis(slot) => {
Some(ViableEpoch::UnimportedGenesis(make_genesis(*slot)))
},
ViableEpochDescriptor::Signaled(identifier, _) => {
self.epoch_mut(&identifier).map(ViableEpoch::Signaled)
},
}
}
pub fn epoch_data<G>(
&self,
descriptor: &ViableEpochDescriptor<Hash, Number, E>,
make_genesis: G
) -> Option<E> where
G: FnOnce(E::Slot) -> E,
E: Clone,
{
match descriptor {
ViableEpochDescriptor::UnimportedGenesis(slot) => {
Some(make_genesis(*slot))
},
ViableEpochDescriptor::Signaled(identifier, _) => {
self.epoch(&identifier).cloned()
},
}
}
pub fn epoch_data_for_child_of<D: IsDescendentOfBuilder<Hash>, G>(
&self,
descendent_of_builder: D,
parent_hash: &Hash,
parent_number: Number,
slot: E::Slot,
make_genesis: G,
) -> Result<Option<E>, fork_tree::Error<D::Error>> where
G: FnOnce(E::Slot) -> E,
E: Clone,
{
let descriptor = self.epoch_descriptor_for_child_of(
descendent_of_builder,
parent_hash,
parent_number,
slot
)?;
Ok(descriptor.and_then(|des| self.epoch_data(&des, make_genesis)))
}
pub fn epoch_descriptor_for_child_of<D: IsDescendentOfBuilder<Hash>>(
&self,
descendent_of_builder: D,
parent_hash: &Hash,
parent_number: Number,
slot: E::Slot,
) -> Result<Option<ViableEpochDescriptor<Hash, Number, E>>, fork_tree::Error<D::Error>> {
let fake_head_hash = fake_head_hash(parent_hash);
let is_descendent_of = descendent_of_builder
.build_is_descendent_of(Some((fake_head_hash, *parent_hash)));
if parent_number == Zero::zero() {
return Ok(Some(ViableEpochDescriptor::UnimportedGenesis(slot)))
}
let predicate = |epoch: &PersistedEpochHeader<E>| match *epoch {
PersistedEpochHeader::Genesis(ref epoch_0, _) =>
epoch_0.start_slot <= slot,
PersistedEpochHeader::Regular(ref epoch_n) =>
epoch_n.start_slot <= slot,
};
self.inner.find_node_where(
&fake_head_hash,
&(parent_number + One::one()),
&is_descendent_of,
&predicate,
)
.map(|n| {
n.map(|node| (match node.data {
PersistedEpochHeader::Genesis(ref epoch_0, ref epoch_1) =>
if epoch_1.start_slot <= slot {
(EpochIdentifierPosition::Genesis1, epoch_1.clone())
} else {
(EpochIdentifierPosition::Genesis0, epoch_0.clone())
},
PersistedEpochHeader::Regular(ref epoch_n) =>
(EpochIdentifierPosition::Regular, epoch_n.clone()),
}, node)).map(|((position, header), node)| {
ViableEpochDescriptor::Signaled(EpochIdentifier {
position,
hash: node.hash,
number: node.number
}, header)
})
})
}
pub fn import<D: IsDescendentOfBuilder<Hash>>(
&mut self,
descendent_of_builder: D,
hash: Hash,
number: Number,
parent_hash: Hash,
epoch: IncrementedEpoch<E>,
) -> Result<(), fork_tree::Error<D::Error>> {
let is_descendent_of = descendent_of_builder
.build_is_descendent_of(Some((hash, parent_hash)));
let header = PersistedEpochHeader::<E>::from(&epoch.0);
let res = self.inner.import(
hash,
number,
header,
&is_descendent_of,
);
match res {
Ok(_) | Err(fork_tree::Error::Duplicate) => {
self.epochs.insert((hash, number), epoch.0);
Ok(())
},
Err(e) => Err(e),
}
}
pub fn tree(&self) -> &ForkTree<Hash, Number, PersistedEpochHeader<E>> {
&self.inner
}
}
pub type EpochChangesFor<Block, Epoch> = EpochChanges<<Block as BlockT>::Hash, NumberFor<Block>, Epoch>;
pub type SharedEpochChanges<Block, Epoch> = Arc<Mutex<EpochChangesFor<Block, Epoch>>>;
#[cfg(test)]
mod tests {
use super::*;
use super::Epoch as EpochT;
#[derive(Debug, PartialEq)]
pub struct TestError;
impl std::fmt::Display for TestError {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "TestError")
}
}
impl std::error::Error for TestError {}
impl<'a, F: 'a , H: 'a + PartialEq + std::fmt::Debug> IsDescendentOfBuilder<H> for &'a F
where F: Fn(&H, &H) -> Result<bool, TestError>
{
type Error = TestError;
type IsDescendentOf = Box<dyn Fn(&H, &H) -> Result<bool, TestError> + 'a>;
fn build_is_descendent_of(&self, current: Option<(H, H)>)
-> Self::IsDescendentOf
{
let f = *self;
Box::new(move |base, head| {
let mut head = head;
if let Some((ref c_head, ref c_parent)) = current {
if head == c_head {
if base == c_parent {
return Ok(true);
} else {
head = c_parent;
}
}
}
f(base, head)
})
}
}
type Hash = [u8; 1];
type Slot = u64;
#[derive(Debug, Clone, Eq, PartialEq)]
struct Epoch {
start_slot: Slot,
duration: Slot,
}
impl EpochT for Epoch {
type NextEpochDescriptor = ();
type Slot = Slot;
fn increment(&self, _: ()) -> Self {
Epoch {
start_slot: self.start_slot + self.duration,
duration: self.duration,
}
}
fn end_slot(&self) -> Slot {
self.start_slot + self.duration
}
fn start_slot(&self) -> Slot {
self.start_slot
}
}
#[test]
fn genesis_epoch_is_created_but_not_imported() {
let is_descendent_of = |base: &Hash, block: &Hash| -> Result<bool, TestError> {
match (base, *block) {
(b"A", b) => Ok(b == *b"B" || b == *b"C" || b == *b"D"),
(b"B", b) | (b"C", b) => Ok(b == *b"D"),
(b"0", _) => Ok(true),
_ => Ok(false),
}
};
let epoch_changes = EpochChanges::<_, _, Epoch>::new();
let genesis_epoch = epoch_changes.epoch_descriptor_for_child_of(
&is_descendent_of,
b"0",
0,
10101,
).unwrap().unwrap();
match genesis_epoch {
ViableEpochDescriptor::UnimportedGenesis(slot) => {
assert_eq!(slot, 10101u64);
},
_ => panic!("should be unimported genesis"),
};
let genesis_epoch_2 = epoch_changes.epoch_descriptor_for_child_of(
&is_descendent_of,
b"0",
0,
10102,
).unwrap().unwrap();
match genesis_epoch_2 {
ViableEpochDescriptor::UnimportedGenesis(slot) => {
assert_eq!(slot, 10102u64);
},
_ => panic!("should be unimported genesis"),
};
}
#[test]
fn epoch_changes_between_blocks() {
let is_descendent_of = |base: &Hash, block: &Hash| -> Result<bool, TestError> {
match (base, *block) {
(b"A", b) => Ok(b == *b"B" || b == *b"C" || b == *b"D"),
(b"B", b) | (b"C", b) => Ok(b == *b"D"),
(b"0", _) => Ok(true),
_ => Ok(false),
}
};
let make_genesis = |slot| Epoch {
start_slot: slot,
duration: 100,
};
let mut epoch_changes = EpochChanges::<_, _, Epoch>::new();
let genesis_epoch = epoch_changes.epoch_descriptor_for_child_of(
&is_descendent_of,
b"0",
0,
100,
).unwrap().unwrap();
assert_eq!(genesis_epoch, ViableEpochDescriptor::UnimportedGenesis(100));
let import_epoch_1 = epoch_changes
.viable_epoch(&genesis_epoch, &make_genesis)
.unwrap()
.increment(());
let epoch_1 = import_epoch_1.as_ref().clone();
epoch_changes.import(
&is_descendent_of,
*b"A",
1,
*b"0",
import_epoch_1,
).unwrap();
let genesis_epoch = epoch_changes.epoch_data(&genesis_epoch, &make_genesis).unwrap();
assert!(is_descendent_of(b"0", b"A").unwrap());
let end_slot = genesis_epoch.end_slot();
assert_eq!(end_slot, epoch_1.start_slot);
{
let x = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"A",
1,
end_slot - 1,
&make_genesis,
).unwrap().unwrap();
assert_eq!(x, genesis_epoch);
}
{
let x = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"A",
1,
end_slot,
&make_genesis,
).unwrap().unwrap();
assert_eq!(x, epoch_1);
}
{
let x = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"A",
1,
epoch_1.end_slot() - 1,
&make_genesis,
).unwrap().unwrap();
assert_eq!(x, epoch_1);
}
}
#[test]
fn two_block_ones_dont_conflict() {
let is_descendent_of = |base: &Hash, block: &Hash| -> Result<bool, TestError> {
match (base, *block) {
(b"A", b) => Ok(b == *b"B"),
(b"X", b) => Ok(b == *b"Y"),
(b"0", _) => Ok(true),
_ => Ok(false),
}
};
let duration = 100;
let make_genesis = |slot| Epoch {
start_slot: slot,
duration,
};
let mut epoch_changes = EpochChanges::new();
let next_descriptor = ();
{
let genesis_epoch_a_descriptor = epoch_changes.epoch_descriptor_for_child_of(
&is_descendent_of,
b"0",
0,
100,
).unwrap().unwrap();
let incremented_epoch = epoch_changes
.viable_epoch(&genesis_epoch_a_descriptor, &make_genesis)
.unwrap()
.increment(next_descriptor.clone());
epoch_changes.import(
&is_descendent_of,
*b"A",
1,
*b"0",
incremented_epoch,
).unwrap();
}
{
let genesis_epoch_x_descriptor = epoch_changes.epoch_descriptor_for_child_of(
&is_descendent_of,
b"0",
0,
1000,
).unwrap().unwrap();
let incremented_epoch = epoch_changes
.viable_epoch(&genesis_epoch_x_descriptor, &make_genesis)
.unwrap()
.increment(next_descriptor.clone());
epoch_changes.import(
&is_descendent_of,
*b"X",
1,
*b"0",
incremented_epoch,
).unwrap();
}
{
let epoch_for_a_child = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"A",
1,
101,
&make_genesis,
).unwrap().unwrap();
assert_eq!(epoch_for_a_child, make_genesis(100));
let epoch_for_x_child = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"X",
1,
1001,
&make_genesis,
).unwrap().unwrap();
assert_eq!(epoch_for_x_child, make_genesis(1000));
let epoch_for_x_child_before_genesis = epoch_changes.epoch_data_for_child_of(
&is_descendent_of,
b"X",
1,
101,
&make_genesis,
).unwrap();
assert!(epoch_for_x_child_before_genesis.is_none());
}
}
}