use std::{cmp::Ord, fmt::Debug, ops::Add};
use codec::{Decode, Encode};
use finality_grandpa::voter_set::VoterSet;
use fork_tree::{FilterAction, ForkTree};
use log::debug;
use parking_lot::MappedMutexGuard;
use sc_consensus::shared_data::{SharedData, SharedDataLocked};
use sc_telemetry::{telemetry, TelemetryHandle, CONSENSUS_INFO};
use sp_consensus_grandpa::{AuthorityId, AuthorityList};
use crate::{SetId, LOG_TARGET};
#[derive(Debug, thiserror::Error)]
pub enum Error<N, E> {
#[error("Invalid authority set, either empty or with an authority weight set to 0.")]
InvalidAuthoritySet,
#[error("Client error during ancestry lookup: {0}")]
Client(E),
#[error("Duplicate authority set change.")]
DuplicateAuthoritySetChange,
#[error("Multiple pending forced authority set changes are not allowed.")]
MultiplePendingForcedAuthoritySetChanges,
#[error(
"A pending forced authority set change could not be applied since it must be applied \
after the pending standard change at #{0}"
)]
ForcedAuthoritySetChangeDependencyUnsatisfied(N),
#[error("Invalid operation in the pending changes tree: {0}")]
ForkTree(fork_tree::Error<E>),
}
impl<N, E> From<fork_tree::Error<E>> for Error<N, E> {
fn from(err: fork_tree::Error<E>) -> Error<N, E> {
match err {
fork_tree::Error::Client(err) => Error::Client(err),
fork_tree::Error::Duplicate => Error::DuplicateAuthoritySetChange,
err => Error::ForkTree(err),
}
}
}
impl<N, E: std::error::Error> From<E> for Error<N, E> {
fn from(err: E) -> Error<N, E> {
Error::Client(err)
}
}
pub struct SharedAuthoritySet<H, N> {
inner: SharedData<AuthoritySet<H, N>>,
}
impl<H, N> Clone for SharedAuthoritySet<H, N> {
fn clone(&self) -> Self {
SharedAuthoritySet { inner: self.inner.clone() }
}
}
impl<H, N> SharedAuthoritySet<H, N> {
pub(crate) fn inner(&self) -> MappedMutexGuard<AuthoritySet<H, N>> {
self.inner.shared_data()
}
pub(crate) fn inner_locked(&self) -> SharedDataLocked<AuthoritySet<H, N>> {
self.inner.shared_data_locked()
}
}
impl<H: Eq, N> SharedAuthoritySet<H, N>
where
N: Add<Output = N> + Ord + Clone + Debug,
H: Clone + Debug,
{
pub(crate) fn current_limit(&self, min: N) -> Option<N> {
self.inner().current_limit(min)
}
pub fn set_id(&self) -> u64 {
self.inner().set_id
}
pub fn current_authorities(&self) -> VoterSet<AuthorityId> {
VoterSet::new(self.inner().current_authorities.iter().cloned()).expect(
"current_authorities is non-empty and weights are non-zero; \
constructor and all mutating operations on `AuthoritySet` ensure this; \
qed.",
)
}
pub fn clone_inner(&self) -> AuthoritySet<H, N> {
self.inner().clone()
}
pub fn authority_set_changes(&self) -> AuthoritySetChanges<N> {
self.inner().authority_set_changes.clone()
}
}
impl<H, N> From<AuthoritySet<H, N>> for SharedAuthoritySet<H, N> {
fn from(set: AuthoritySet<H, N>) -> Self {
SharedAuthoritySet { inner: SharedData::new(set) }
}
}
#[derive(Debug)]
pub(crate) struct Status<H, N> {
pub(crate) changed: bool,
pub(crate) new_set_block: Option<(H, N)>,
}
#[derive(Debug, Clone, Encode, Decode, PartialEq)]
pub struct AuthoritySet<H, N> {
pub(crate) current_authorities: AuthorityList,
pub(crate) set_id: u64,
pub(crate) pending_standard_changes: ForkTree<H, N, PendingChange<H, N>>,
pending_forced_changes: Vec<PendingChange<H, N>>,
pub(crate) authority_set_changes: AuthoritySetChanges<N>,
}
impl<H, N> AuthoritySet<H, N>
where
H: PartialEq,
N: Ord + Clone,
{
fn invalid_authority_list(authorities: &AuthorityList) -> bool {
authorities.is_empty() || authorities.iter().any(|(_, w)| *w == 0)
}
pub(crate) fn genesis(initial: AuthorityList) -> Option<Self> {
if Self::invalid_authority_list(&initial) {
return None
}
Some(AuthoritySet {
current_authorities: initial,
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
})
}
pub(crate) fn new(
authorities: AuthorityList,
set_id: u64,
pending_standard_changes: ForkTree<H, N, PendingChange<H, N>>,
pending_forced_changes: Vec<PendingChange<H, N>>,
authority_set_changes: AuthoritySetChanges<N>,
) -> Option<Self> {
if Self::invalid_authority_list(&authorities) {
return None
}
Some(AuthoritySet {
current_authorities: authorities,
set_id,
pending_standard_changes,
pending_forced_changes,
authority_set_changes,
})
}
pub(crate) fn current(&self) -> (u64, &[(AuthorityId, u64)]) {
(self.set_id, &self.current_authorities[..])
}
pub(crate) fn revert<F, E>(&mut self, hash: H, number: N, is_descendent_of: &F)
where
F: Fn(&H, &H) -> Result<bool, E>,
{
let filter = |node_hash: &H, node_num: &N, _: &PendingChange<H, N>| {
if number >= *node_num &&
(is_descendent_of(node_hash, &hash).unwrap_or_default() || *node_hash == hash)
{
FilterAction::KeepNode
} else if number < *node_num && is_descendent_of(&hash, node_hash).unwrap_or_default() {
FilterAction::Remove
} else {
FilterAction::KeepTree
}
};
let _ = self.pending_standard_changes.drain_filter(&filter);
self.pending_forced_changes
.retain(|change| !is_descendent_of(&hash, &change.canon_hash).unwrap_or_default());
}
}
impl<H: Eq, N> AuthoritySet<H, N>
where
N: Add<Output = N> + Ord + Clone + Debug,
H: Clone + Debug,
{
pub(crate) fn next_change<F, E>(
&self,
best_hash: &H,
is_descendent_of: &F,
) -> Result<Option<(H, N)>, Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
let mut forced = None;
for change in &self.pending_forced_changes {
if is_descendent_of(&change.canon_hash, best_hash)? {
forced = Some((change.canon_hash.clone(), change.canon_height.clone()));
break
}
}
let mut standard = None;
for (_, _, change) in self.pending_standard_changes.roots() {
if is_descendent_of(&change.canon_hash, best_hash)? {
standard = Some((change.canon_hash.clone(), change.canon_height.clone()));
break
}
}
let earliest = match (forced, standard) {
(Some(forced), Some(standard)) =>
Some(if forced.1 < standard.1 { forced } else { standard }),
(Some(forced), None) => Some(forced),
(None, Some(standard)) => Some(standard),
(None, None) => None,
};
Ok(earliest)
}
fn add_standard_change<F, E>(
&mut self,
pending: PendingChange<H, N>,
is_descendent_of: &F,
) -> Result<(), Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
let hash = pending.canon_hash.clone();
let number = pending.canon_height.clone();
debug!(
target: LOG_TARGET,
"Inserting potential standard set change signaled at block {:?} (delayed by {:?} blocks).",
(&number, &hash),
pending.delay,
);
self.pending_standard_changes.import(hash, number, pending, is_descendent_of)?;
debug!(
target: LOG_TARGET,
"There are now {} alternatives for the next pending standard change (roots), and a \
total of {} pending standard changes (across all forks).",
self.pending_standard_changes.roots().count(),
self.pending_standard_changes.iter().count(),
);
Ok(())
}
fn add_forced_change<F, E>(
&mut self,
pending: PendingChange<H, N>,
is_descendent_of: &F,
) -> Result<(), Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
for change in &self.pending_forced_changes {
if change.canon_hash == pending.canon_hash {
return Err(Error::DuplicateAuthoritySetChange)
}
if is_descendent_of(&change.canon_hash, &pending.canon_hash)? {
return Err(Error::MultiplePendingForcedAuthoritySetChanges)
}
}
let key = (pending.effective_number(), pending.canon_height.clone());
let idx = self
.pending_forced_changes
.binary_search_by_key(&key, |change| {
(change.effective_number(), change.canon_height.clone())
})
.unwrap_or_else(|i| i);
debug!(
target: LOG_TARGET,
"Inserting potential forced set change at block {:?} (delayed by {:?} blocks).",
(&pending.canon_height, &pending.canon_hash),
pending.delay,
);
self.pending_forced_changes.insert(idx, pending);
debug!(
target: LOG_TARGET,
"There are now {} pending forced changes.",
self.pending_forced_changes.len()
);
Ok(())
}
pub(crate) fn add_pending_change<F, E>(
&mut self,
pending: PendingChange<H, N>,
is_descendent_of: &F,
) -> Result<(), Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
if Self::invalid_authority_list(&pending.next_authorities) {
return Err(Error::InvalidAuthoritySet)
}
match pending.delay_kind {
DelayKind::Best { .. } => self.add_forced_change(pending, is_descendent_of),
DelayKind::Finalized => self.add_standard_change(pending, is_descendent_of),
}
}
pub(crate) fn pending_changes(&self) -> impl Iterator<Item = &PendingChange<H, N>> {
self.pending_standard_changes
.iter()
.map(|(_, _, c)| c)
.chain(self.pending_forced_changes.iter())
}
pub(crate) fn current_limit(&self, min: N) -> Option<N> {
self.pending_standard_changes
.roots()
.filter(|&(_, _, c)| c.effective_number() >= min)
.min_by_key(|&(_, _, c)| c.effective_number())
.map(|(_, _, c)| c.effective_number())
}
pub(crate) fn apply_forced_changes<F, E>(
&self,
best_hash: H,
best_number: N,
is_descendent_of: &F,
initial_sync: bool,
telemetry: Option<TelemetryHandle>,
) -> Result<Option<(N, Self)>, Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
let mut new_set = None;
for change in self
.pending_forced_changes
.iter()
.take_while(|c| c.effective_number() <= best_number) .filter(|c| c.effective_number() == best_number)
{
if change.canon_hash == best_hash || is_descendent_of(&change.canon_hash, &best_hash)? {
let median_last_finalized = match change.delay_kind {
DelayKind::Best { ref median_last_finalized } => median_last_finalized.clone(),
_ => unreachable!(
"pending_forced_changes only contains forced changes; forced changes have delay kind Best; qed."
),
};
for (_, _, standard_change) in self.pending_standard_changes.roots() {
if standard_change.effective_number() <= median_last_finalized &&
is_descendent_of(&standard_change.canon_hash, &change.canon_hash)?
{
log::info!(target: LOG_TARGET,
"Not applying authority set change forced at block #{:?}, due to pending standard change at block #{:?}",
change.canon_height,
standard_change.effective_number(),
);
return Err(Error::ForcedAuthoritySetChangeDependencyUnsatisfied(
standard_change.effective_number(),
))
}
}
grandpa_log!(
initial_sync,
"๐ด Applying authority set change forced at block #{:?}",
change.canon_height,
);
telemetry!(
telemetry;
CONSENSUS_INFO;
"afg.applying_forced_authority_set_change";
"block" => ?change.canon_height
);
let mut authority_set_changes = self.authority_set_changes.clone();
authority_set_changes.append(self.set_id, median_last_finalized.clone());
new_set = Some((
median_last_finalized,
AuthoritySet {
current_authorities: change.next_authorities.clone(),
set_id: self.set_id + 1,
pending_standard_changes: ForkTree::new(), pending_forced_changes: Vec::new(),
authority_set_changes,
},
));
break
}
}
Ok(new_set)
}
pub(crate) fn apply_standard_changes<F, E>(
&mut self,
finalized_hash: H,
finalized_number: N,
is_descendent_of: &F,
initial_sync: bool,
telemetry: Option<&TelemetryHandle>,
) -> Result<Status<H, N>, Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
let mut status = Status { changed: false, new_set_block: None };
match self.pending_standard_changes.finalize_with_descendent_if(
&finalized_hash,
finalized_number.clone(),
is_descendent_of,
|change| change.effective_number() <= finalized_number,
)? {
fork_tree::FinalizationResult::Changed(change) => {
status.changed = true;
let pending_forced_changes = std::mem::take(&mut self.pending_forced_changes);
for change in pending_forced_changes {
if change.effective_number() > finalized_number &&
is_descendent_of(&finalized_hash, &change.canon_hash)?
{
self.pending_forced_changes.push(change)
}
}
if let Some(change) = change {
grandpa_log!(
initial_sync,
"๐ด Applying authority set change scheduled at block #{:?}",
change.canon_height,
);
telemetry!(
telemetry;
CONSENSUS_INFO;
"afg.applying_scheduled_authority_set_change";
"block" => ?change.canon_height
);
self.authority_set_changes.append(self.set_id, finalized_number.clone());
self.current_authorities = change.next_authorities;
self.set_id += 1;
status.new_set_block = Some((finalized_hash, finalized_number));
}
},
fork_tree::FinalizationResult::Unchanged => {},
}
Ok(status)
}
pub fn enacts_standard_change<F, E>(
&self,
finalized_hash: H,
finalized_number: N,
is_descendent_of: &F,
) -> Result<Option<bool>, Error<N, E>>
where
F: Fn(&H, &H) -> Result<bool, E>,
E: std::error::Error,
{
self.pending_standard_changes
.finalizes_any_with_descendent_if(
&finalized_hash,
finalized_number.clone(),
is_descendent_of,
|change| change.effective_number() == finalized_number,
)
.map_err(Error::ForkTree)
}
}
#[derive(Debug, Clone, Encode, Decode, PartialEq)]
pub enum DelayKind<N> {
Finalized,
Best { median_last_finalized: N },
}
#[derive(Debug, Clone, Encode, PartialEq)]
pub struct PendingChange<H, N> {
pub(crate) next_authorities: AuthorityList,
pub(crate) delay: N,
pub(crate) canon_height: N,
pub(crate) canon_hash: H,
pub(crate) delay_kind: DelayKind<N>,
}
impl<H: Decode, N: Decode> Decode for PendingChange<H, N> {
fn decode<I: codec::Input>(value: &mut I) -> Result<Self, codec::Error> {
let next_authorities = Decode::decode(value)?;
let delay = Decode::decode(value)?;
let canon_height = Decode::decode(value)?;
let canon_hash = Decode::decode(value)?;
let delay_kind = DelayKind::decode(value).unwrap_or(DelayKind::Finalized);
Ok(PendingChange { next_authorities, delay, canon_height, canon_hash, delay_kind })
}
}
impl<H, N: Add<Output = N> + Clone> PendingChange<H, N> {
pub fn effective_number(&self) -> N {
self.canon_height.clone() + self.delay.clone()
}
}
#[derive(Debug, Encode, Decode, Clone, PartialEq)]
pub struct AuthoritySetChanges<N>(Vec<(u64, N)>);
#[derive(Debug, PartialEq)]
pub enum AuthoritySetChangeId<N> {
Latest,
Set(SetId, N),
Unknown,
}
impl<N> From<Vec<(u64, N)>> for AuthoritySetChanges<N> {
fn from(changes: Vec<(u64, N)>) -> AuthoritySetChanges<N> {
AuthoritySetChanges(changes)
}
}
impl<N: Ord + Clone> AuthoritySetChanges<N> {
pub(crate) fn empty() -> Self {
Self(Default::default())
}
pub(crate) fn append(&mut self, set_id: u64, block_number: N) {
self.0.push((set_id, block_number));
}
pub(crate) fn get_set_id(&self, block_number: N) -> AuthoritySetChangeId<N> {
if self
.0
.last()
.map(|last_auth_change| last_auth_change.1 < block_number)
.unwrap_or(false)
{
return AuthoritySetChangeId::Latest
}
let idx = self
.0
.binary_search_by_key(&block_number, |(_, n)| n.clone())
.unwrap_or_else(|b| b);
if idx < self.0.len() {
let (set_id, block_number) = self.0[idx].clone();
if idx == 0 && set_id != 0 {
return AuthoritySetChangeId::Unknown
}
AuthoritySetChangeId::Set(set_id, block_number)
} else {
AuthoritySetChangeId::Unknown
}
}
pub(crate) fn insert(&mut self, block_number: N) {
let idx = self
.0
.binary_search_by_key(&block_number, |(_, n)| n.clone())
.unwrap_or_else(|b| b);
let set_id = if idx == 0 { 0 } else { self.0[idx - 1].0 + 1 };
assert!(idx == self.0.len() || self.0[idx].0 != set_id);
self.0.insert(idx, (set_id, block_number));
}
pub fn iter_from(&self, block_number: N) -> Option<impl Iterator<Item = &(u64, N)>> {
let idx = self
.0
.binary_search_by_key(&block_number, |(_, n)| n.clone())
.map(|n| n + 1)
.unwrap_or_else(|b| b);
if idx < self.0.len() {
let (set_id, _) = self.0[idx].clone();
if idx == 0 && set_id != 0 {
return None
}
}
Some(self.0[idx..].iter())
}
}
#[cfg(test)]
mod tests {
use super::*;
use sp_core::crypto::{ByteArray, UncheckedFrom};
fn static_is_descendent_of<A>(value: bool) -> impl Fn(&A, &A) -> Result<bool, std::io::Error> {
move |_, _| Ok(value)
}
fn is_descendent_of<A, F>(f: F) -> impl Fn(&A, &A) -> Result<bool, std::io::Error>
where
F: Fn(&A, &A) -> bool,
{
move |base, hash| Ok(f(base, hash))
}
#[test]
fn current_limit_filters_min() {
let current_authorities = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 1)];
let mut authorities = AuthoritySet {
current_authorities: current_authorities.clone(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let change = |height| PendingChange {
next_authorities: current_authorities.clone(),
delay: 0,
canon_height: height,
canon_hash: height.to_string(),
delay_kind: DelayKind::Finalized,
};
let is_descendent_of = static_is_descendent_of(false);
authorities.add_pending_change(change(1), &is_descendent_of).unwrap();
authorities.add_pending_change(change(2), &is_descendent_of).unwrap();
assert_eq!(authorities.current_limit(0), Some(1));
assert_eq!(authorities.current_limit(1), Some(1));
assert_eq!(authorities.current_limit(2), Some(2));
assert_eq!(authorities.current_limit(3), None);
}
#[test]
fn changes_iterated_in_pre_order() {
let current_authorities = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 1)];
let mut authorities = AuthoritySet {
current_authorities: current_authorities.clone(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let change_a = PendingChange {
next_authorities: current_authorities.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Finalized,
};
let change_b = PendingChange {
next_authorities: current_authorities.clone(),
delay: 0,
canon_height: 5,
canon_hash: "hash_b",
delay_kind: DelayKind::Finalized,
};
let change_c = PendingChange {
next_authorities: current_authorities.clone(),
delay: 5,
canon_height: 10,
canon_hash: "hash_c",
delay_kind: DelayKind::Finalized,
};
authorities
.add_pending_change(change_a.clone(), &static_is_descendent_of(false))
.unwrap();
authorities
.add_pending_change(change_b.clone(), &static_is_descendent_of(false))
.unwrap();
authorities
.add_pending_change(
change_c.clone(),
&is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a", "hash_c") => true,
("hash_b", "hash_c") => false,
_ => unreachable!(),
}),
)
.unwrap();
let change_d = PendingChange {
next_authorities: current_authorities.clone(),
delay: 2,
canon_height: 1,
canon_hash: "hash_d",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
let change_e = PendingChange {
next_authorities: current_authorities.clone(),
delay: 2,
canon_height: 0,
canon_hash: "hash_e",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
authorities
.add_pending_change(change_d.clone(), &static_is_descendent_of(false))
.unwrap();
authorities
.add_pending_change(change_e.clone(), &static_is_descendent_of(false))
.unwrap();
assert_eq!(
authorities.pending_changes().collect::<Vec<_>>(),
vec![&change_a, &change_c, &change_b, &change_e, &change_d],
);
}
#[test]
fn apply_change() {
let mut authorities = AuthoritySet {
current_authorities: Vec::new(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 5)];
let set_b = vec![(AuthorityId::from_slice(&[2; 32]).unwrap(), 5)];
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Finalized,
};
let change_b = PendingChange {
next_authorities: set_b.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_b",
delay_kind: DelayKind::Finalized,
};
authorities
.add_pending_change(change_a.clone(), &static_is_descendent_of(true))
.unwrap();
authorities
.add_pending_change(change_b.clone(), &static_is_descendent_of(true))
.unwrap();
assert_eq!(authorities.pending_changes().collect::<Vec<_>>(), vec![&change_a, &change_b]);
let status = authorities
.apply_standard_changes(
"hash_c",
11,
&is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a", "hash_c") => true,
("hash_b", "hash_c") => false,
_ => unreachable!(),
}),
false,
None,
)
.unwrap();
assert!(status.changed);
assert_eq!(status.new_set_block, None);
assert_eq!(authorities.pending_changes().collect::<Vec<_>>(), vec![&change_a]);
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges::empty());
let status = authorities
.apply_standard_changes(
"hash_d",
15,
&is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a", "hash_d") => true,
_ => unreachable!(),
}),
false,
None,
)
.unwrap();
assert!(status.changed);
assert_eq!(status.new_set_block, Some(("hash_d", 15)));
assert_eq!(authorities.current_authorities, set_a);
assert_eq!(authorities.set_id, 1);
assert_eq!(authorities.pending_changes().count(), 0);
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15)]));
}
#[test]
fn disallow_multiple_changes_being_finalized_at_once() {
let mut authorities = AuthoritySet {
current_authorities: Vec::new(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 5)];
let set_c = vec![(AuthorityId::from_slice(&[2; 32]).unwrap(), 5)];
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Finalized,
};
let change_c = PendingChange {
next_authorities: set_c.clone(),
delay: 10,
canon_height: 30,
canon_hash: "hash_c",
delay_kind: DelayKind::Finalized,
};
authorities
.add_pending_change(change_a.clone(), &static_is_descendent_of(true))
.unwrap();
authorities
.add_pending_change(change_c.clone(), &static_is_descendent_of(true))
.unwrap();
let is_descendent_of = is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a", "hash_b") => true,
("hash_a", "hash_c") => true,
("hash_a", "hash_d") => true,
("hash_c", "hash_b") => false,
("hash_c", "hash_d") => true,
("hash_b", "hash_c") => true,
_ => unreachable!(),
});
assert!(matches!(
authorities.apply_standard_changes("hash_d", 40, &is_descendent_of, false, None),
Err(Error::ForkTree(fork_tree::Error::UnfinalizedAncestor))
));
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges::empty());
let status = authorities
.apply_standard_changes("hash_b", 15, &is_descendent_of, false, None)
.unwrap();
assert!(status.changed);
assert_eq!(status.new_set_block, Some(("hash_b", 15)));
assert_eq!(authorities.current_authorities, set_a);
assert_eq!(authorities.set_id, 1);
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15)]));
let status = authorities
.apply_standard_changes("hash_d", 40, &is_descendent_of, false, None)
.unwrap();
assert!(status.changed);
assert_eq!(status.new_set_block, Some(("hash_d", 40)));
assert_eq!(authorities.current_authorities, set_c);
assert_eq!(authorities.set_id, 2);
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15), (1, 40)]));
}
#[test]
fn enacts_standard_change_works() {
let mut authorities = AuthoritySet {
current_authorities: Vec::new(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 5)];
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Finalized,
};
let change_b = PendingChange {
next_authorities: set_a.clone(),
delay: 10,
canon_height: 20,
canon_hash: "hash_b",
delay_kind: DelayKind::Finalized,
};
authorities
.add_pending_change(change_a.clone(), &static_is_descendent_of(false))
.unwrap();
authorities
.add_pending_change(change_b.clone(), &static_is_descendent_of(true))
.unwrap();
let is_descendent_of = is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a", "hash_d") => true,
("hash_a", "hash_e") => true,
("hash_b", "hash_d") => true,
("hash_b", "hash_e") => true,
("hash_a", "hash_c") => false,
("hash_b", "hash_c") => false,
_ => unreachable!(),
});
assert_eq!(
authorities.enacts_standard_change("hash_c", 15, &is_descendent_of).unwrap(),
None,
);
assert_eq!(
authorities.enacts_standard_change("hash_d", 14, &is_descendent_of).unwrap(),
None,
);
assert_eq!(
authorities.enacts_standard_change("hash_d", 15, &is_descendent_of).unwrap(),
Some(true),
);
assert_eq!(
authorities.enacts_standard_change("hash_e", 30, &is_descendent_of).unwrap(),
Some(false),
);
}
#[test]
fn forced_changes() {
let mut authorities = AuthoritySet {
current_authorities: Vec::new(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 5)];
let set_b = vec![(AuthorityId::from_slice(&[2; 32]).unwrap(), 5)];
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Best { median_last_finalized: 42 },
};
let change_b = PendingChange {
next_authorities: set_b.clone(),
delay: 10,
canon_height: 5,
canon_hash: "hash_b",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
authorities
.add_pending_change(change_a, &static_is_descendent_of(false))
.unwrap();
authorities
.add_pending_change(change_b.clone(), &static_is_descendent_of(false))
.unwrap();
assert!(matches!(
authorities.add_pending_change(change_b, &static_is_descendent_of(false)),
Err(Error::DuplicateAuthoritySetChange)
));
assert_eq!(
authorities
.enacts_standard_change("hash_c", 15, &static_is_descendent_of(true))
.unwrap(),
None,
);
let change_c = PendingChange {
next_authorities: set_b.clone(),
delay: 3,
canon_height: 8,
canon_hash: "hash_a8",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
let is_descendent_of_a = is_descendent_of(|base: &&str, _| base.starts_with("hash_a"));
assert!(matches!(
authorities.add_pending_change(change_c, &is_descendent_of_a),
Err(Error::MultiplePendingForcedAuthoritySetChanges)
));
assert!(authorities
.apply_forced_changes("hash_a10", 10, &static_is_descendent_of(true), false, None)
.unwrap()
.is_none());
assert!(authorities
.apply_forced_changes("hash_a16", 16, &is_descendent_of_a, false, None)
.unwrap()
.is_none());
assert_eq!(
authorities
.apply_forced_changes("hash_a15", 15, &is_descendent_of_a, false, None)
.unwrap()
.unwrap(),
(
42,
AuthoritySet {
current_authorities: set_a,
set_id: 1,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges(vec![(0, 42)]),
},
)
);
}
#[test]
fn forced_changes_with_no_delay() {
let mut authorities = AuthoritySet {
current_authorities: Vec::new(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 5)];
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 0,
canon_height: 5,
canon_hash: "hash_a",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
authorities
.add_pending_change(change_a, &static_is_descendent_of(false))
.unwrap();
assert!(authorities
.apply_forced_changes("hash_a", 5, &static_is_descendent_of(false), false, None)
.unwrap()
.is_some());
}
#[test]
fn forced_changes_blocked_by_standard_changes() {
let set_a = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 1)];
let mut authorities = AuthoritySet {
current_authorities: set_a.clone(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let change_a = PendingChange {
next_authorities: set_a.clone(),
delay: 5,
canon_height: 10,
canon_hash: "hash_a",
delay_kind: DelayKind::Finalized,
};
let change_b = PendingChange {
next_authorities: set_a.clone(),
delay: 0,
canon_height: 20,
canon_hash: "hash_b",
delay_kind: DelayKind::Finalized,
};
let change_c = PendingChange {
next_authorities: set_a.clone(),
delay: 5,
canon_height: 30,
canon_hash: "hash_c",
delay_kind: DelayKind::Finalized,
};
authorities
.add_pending_change(change_a, &static_is_descendent_of(true))
.unwrap();
authorities
.add_pending_change(change_b, &static_is_descendent_of(true))
.unwrap();
authorities
.add_pending_change(change_c, &static_is_descendent_of(true))
.unwrap();
let change_d = PendingChange {
next_authorities: set_a.clone(),
delay: 5,
canon_height: 40,
canon_hash: "hash_d",
delay_kind: DelayKind::Best { median_last_finalized: 31 },
};
authorities
.add_pending_change(change_d, &static_is_descendent_of(true))
.unwrap();
assert!(matches!(
authorities.apply_forced_changes(
"hash_d45",
45,
&static_is_descendent_of(true),
false,
None
),
Err(Error::ForcedAuthoritySetChangeDependencyUnsatisfied(15))
));
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges::empty());
authorities
.apply_standard_changes("hash_a15", 15, &static_is_descendent_of(true), false, None)
.unwrap();
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15)]));
assert!(matches!(
authorities.apply_forced_changes(
"hash_d",
45,
&static_is_descendent_of(true),
false,
None
),
Err(Error::ForcedAuthoritySetChangeDependencyUnsatisfied(20))
));
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15)]));
authorities
.apply_standard_changes("hash_b", 20, &static_is_descendent_of(true), false, None)
.unwrap();
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15), (1, 20)]));
assert_eq!(
authorities
.apply_forced_changes("hash_d", 45, &static_is_descendent_of(true), false, None)
.unwrap()
.unwrap(),
(
31,
AuthoritySet {
current_authorities: set_a.clone(),
set_id: 3,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges(vec![(0, 15), (1, 20), (2, 31)]),
}
),
);
assert_eq!(authorities.authority_set_changes, AuthoritySetChanges(vec![(0, 15), (1, 20)]));
}
#[test]
fn next_change_works() {
let current_authorities = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 1)];
let mut authorities = AuthoritySet {
current_authorities: current_authorities.clone(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let new_set = current_authorities.clone();
let change_a0 = PendingChange {
next_authorities: new_set.clone(),
delay: 0,
canon_height: 5,
canon_hash: "hash_a0",
delay_kind: DelayKind::Finalized,
};
let change_a1 = PendingChange {
next_authorities: new_set.clone(),
delay: 0,
canon_height: 10,
canon_hash: "hash_a1",
delay_kind: DelayKind::Finalized,
};
let change_b = PendingChange {
next_authorities: new_set.clone(),
delay: 0,
canon_height: 4,
canon_hash: "hash_b",
delay_kind: DelayKind::Finalized,
};
let is_descendent_of = is_descendent_of(|base, hash| match (*base, *hash) {
("hash_a0", "hash_a1") => true,
("hash_a0", "best_a") => true,
("hash_a1", "best_a") => true,
("hash_a10", "best_a") => true,
("hash_b", "best_b") => true,
_ => false,
});
authorities.add_pending_change(change_b, &is_descendent_of).unwrap();
authorities.add_pending_change(change_a0, &is_descendent_of).unwrap();
authorities.add_pending_change(change_a1, &is_descendent_of).unwrap();
assert_eq!(
authorities.next_change(&"best_a", &is_descendent_of).unwrap(),
Some(("hash_a0", 5)),
);
assert_eq!(
authorities.next_change(&"best_b", &is_descendent_of).unwrap(),
Some(("hash_b", 4)),
);
authorities
.apply_standard_changes("hash_a0", 5, &is_descendent_of, false, None)
.unwrap();
assert_eq!(
authorities.next_change(&"best_a", &is_descendent_of).unwrap(),
Some(("hash_a1", 10)),
);
assert_eq!(authorities.next_change(&"best_b", &is_descendent_of).unwrap(), None);
let change_a10 = PendingChange {
next_authorities: new_set.clone(),
delay: 0,
canon_height: 8,
canon_hash: "hash_a10",
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
authorities
.add_pending_change(change_a10, &static_is_descendent_of(false))
.unwrap();
assert_eq!(
authorities.next_change(&"best_a", &is_descendent_of).unwrap(),
Some(("hash_a10", 8)),
);
}
#[test]
fn maintains_authority_list_invariants() {
assert_eq!(AuthoritySet::<(), ()>::genesis(vec![]), None);
assert_eq!(
AuthoritySet::<(), ()>::new(
vec![],
0,
ForkTree::new(),
Vec::new(),
AuthoritySetChanges::empty(),
),
None,
);
let invalid_authorities_weight = vec![
(AuthorityId::from_slice(&[1; 32]).unwrap(), 5),
(AuthorityId::from_slice(&[2; 32]).unwrap(), 0),
];
assert_eq!(AuthoritySet::<(), ()>::genesis(invalid_authorities_weight.clone()), None);
assert_eq!(
AuthoritySet::<(), ()>::new(
invalid_authorities_weight.clone(),
0,
ForkTree::new(),
Vec::new(),
AuthoritySetChanges::empty(),
),
None,
);
let mut authority_set =
AuthoritySet::<(), u64>::genesis(vec![(AuthorityId::unchecked_from([1; 32]), 5)])
.unwrap();
let invalid_change_empty_authorities = PendingChange {
next_authorities: vec![],
delay: 10,
canon_height: 5,
canon_hash: (),
delay_kind: DelayKind::Finalized,
};
assert!(matches!(
authority_set.add_pending_change(
invalid_change_empty_authorities.clone(),
&static_is_descendent_of(false)
),
Err(Error::InvalidAuthoritySet)
));
let invalid_change_authorities_weight = PendingChange {
next_authorities: invalid_authorities_weight,
delay: 10,
canon_height: 5,
canon_hash: (),
delay_kind: DelayKind::Best { median_last_finalized: 0 },
};
assert!(matches!(
authority_set.add_pending_change(
invalid_change_authorities_weight,
&static_is_descendent_of(false)
),
Err(Error::InvalidAuthoritySet)
));
}
#[test]
fn cleans_up_stale_forced_changes_when_applying_standard_change() {
let current_authorities = vec![(AuthorityId::from_slice(&[1; 32]).unwrap(), 1)];
let mut authorities = AuthoritySet {
current_authorities: current_authorities.clone(),
set_id: 0,
pending_standard_changes: ForkTree::new(),
pending_forced_changes: Vec::new(),
authority_set_changes: AuthoritySetChanges::empty(),
};
let new_set = current_authorities.clone();
let is_descendent_of = {
let hashes = vec!["B", "C0", "C1", "C2", "C3", "D"];
is_descendent_of(move |base, hash| match (*base, *hash) {
("B", "B") => false, ("A", b) | ("B", b) => hashes.iter().any(|h| *h == b),
("C0", "D") => true,
_ => false,
})
};
let mut add_pending_change = |canon_height, canon_hash, forced| {
let change = PendingChange {
next_authorities: new_set.clone(),
delay: 0,
canon_height,
canon_hash,
delay_kind: if forced {
DelayKind::Best { median_last_finalized: 0 }
} else {
DelayKind::Finalized
},
};
authorities.add_pending_change(change, &is_descendent_of).unwrap();
};
add_pending_change(5, "A", false);
add_pending_change(10, "B", false);
add_pending_change(15, "C0", false);
add_pending_change(15, "C1", true);
add_pending_change(15, "C2", false);
add_pending_change(15, "C3", true);
add_pending_change(20, "D", true);
authorities
.apply_standard_changes("A", 5, &is_descendent_of, false, None)
.unwrap();
assert_eq!(authorities.pending_changes().count(), 6);
authorities
.apply_standard_changes("B", 10, &is_descendent_of, false, None)
.unwrap();
assert_eq!(authorities.pending_changes().count(), 5);
let authorities2 = authorities.clone();
authorities
.apply_standard_changes("C2", 15, &is_descendent_of, false, None)
.unwrap();
assert_eq!(authorities.pending_forced_changes.len(), 0);
let mut authorities = authorities2;
authorities
.apply_standard_changes("C0", 15, &is_descendent_of, false, None)
.unwrap();
assert_eq!(authorities.pending_forced_changes.len(), 1);
assert_eq!(authorities.pending_forced_changes.first().unwrap().canon_hash, "D");
}
#[test]
fn authority_set_changes_insert() {
let mut authority_set_changes = AuthoritySetChanges::empty();
authority_set_changes.append(0, 41);
authority_set_changes.append(1, 81);
authority_set_changes.append(4, 121);
authority_set_changes.insert(101);
assert_eq!(authority_set_changes.get_set_id(100), AuthoritySetChangeId::Set(2, 101));
assert_eq!(authority_set_changes.get_set_id(101), AuthoritySetChangeId::Set(2, 101));
}
#[test]
fn authority_set_changes_for_complete_data() {
let mut authority_set_changes = AuthoritySetChanges::empty();
authority_set_changes.append(0, 41);
authority_set_changes.append(1, 81);
authority_set_changes.append(2, 121);
assert_eq!(authority_set_changes.get_set_id(20), AuthoritySetChangeId::Set(0, 41));
assert_eq!(authority_set_changes.get_set_id(40), AuthoritySetChangeId::Set(0, 41));
assert_eq!(authority_set_changes.get_set_id(41), AuthoritySetChangeId::Set(0, 41));
assert_eq!(authority_set_changes.get_set_id(42), AuthoritySetChangeId::Set(1, 81));
assert_eq!(authority_set_changes.get_set_id(141), AuthoritySetChangeId::Latest);
}
#[test]
fn authority_set_changes_for_incomplete_data() {
let mut authority_set_changes = AuthoritySetChanges::empty();
authority_set_changes.append(2, 41);
authority_set_changes.append(3, 81);
authority_set_changes.append(4, 121);
assert_eq!(authority_set_changes.get_set_id(20), AuthoritySetChangeId::Unknown);
assert_eq!(authority_set_changes.get_set_id(40), AuthoritySetChangeId::Unknown);
assert_eq!(authority_set_changes.get_set_id(41), AuthoritySetChangeId::Unknown);
assert_eq!(authority_set_changes.get_set_id(42), AuthoritySetChangeId::Set(3, 81));
assert_eq!(authority_set_changes.get_set_id(141), AuthoritySetChangeId::Latest);
}
#[test]
fn iter_from_works() {
let mut authority_set_changes = AuthoritySetChanges::empty();
authority_set_changes.append(1, 41);
authority_set_changes.append(2, 81);
assert_eq!(None, authority_set_changes.iter_from(40).map(|it| it.collect::<Vec<_>>()));
let mut authority_set_changes = AuthoritySetChanges::empty();
authority_set_changes.append(0, 21);
authority_set_changes.append(1, 41);
authority_set_changes.append(2, 81);
authority_set_changes.append(3, 121);
assert_eq!(
Some(vec![(1, 41), (2, 81), (3, 121)]),
authority_set_changes.iter_from(40).map(|it| it.cloned().collect::<Vec<_>>()),
);
assert_eq!(
Some(vec![(2, 81), (3, 121)]),
authority_set_changes.iter_from(41).map(|it| it.cloned().collect::<Vec<_>>()),
);
assert_eq!(0, authority_set_changes.iter_from(121).unwrap().count());
assert_eq!(0, authority_set_changes.iter_from(200).unwrap().count());
}
}