sidechain_block_search/
lib.rs

1//! Binary search queries for Partner Chain slots and epochs
2//!
3//! # Purpose of this crate
4//!
5//! Standard Substrate block storage allows for retrieving blocks based on their number and hash.
6//! However, Partner Chains toolkit introduces two new categories that are not supported by this
7//! lookup: slot and epoch. This crate provides a mechanism to quickly query for blocks based on
8//! their Partner Chain epoch or slot by applying a binary search over historical blocks.
9//!
10//! # Usage
11//!
12//! The binary search feature is provided via the [FindSidechainBlock] trait. This trait is
13//! implemented for any runtime client that implements the [GetSidechainStatus] runtime API.
14//! To query the blockchain, a predicate must be passed to the query that defines the searched
15//! block. Some predefined targets are defined in the [predicates] module, otherwise a new target
16//! type can be defined by implementing the [CompareStrategy] trait.
17//!
18//! Given a runtime client that satisfies the trait bounds, the blockchain can be queried like this:
19//!
20//! ```rust
21//! use sidechain_block_search::predicates::AnyBlockInEpoch;
22//! use sidechain_block_search::{ FindSidechainBlock, Client };
23//! use sidechain_domain::*;
24//! use sp_api::ProvideRuntimeApi;
25//! use sp_runtime::traits::{ Block as BlockT, NumberFor };
26//! use sp_sidechain::GetSidechainStatus;
27//!
28//! fn query_example<B, C>(client: C)
29//! where
30//!     B: BlockT,
31//!     NumberFor<B>: From<u32> + Into<u32>,
32//!     C: ProvideRuntimeApi<B> + Client<B> + Send + Sync + 'static,
33//!     C::Api: GetSidechainStatus<B>
34//! {
35//!     let search_target = AnyBlockInEpoch {
36//!         epoch: ScEpochNumber(42)
37//!     };
38//!     let result = client.find_block(search_target);
39//! }
40//! ```
41
42#![deny(missing_docs)]
43
44mod binary_search;
45mod impl_block_info;
46mod impl_compare_strategy;
47mod impl_find_block;
48
49pub use binary_search::binary_search_by;
50
51use sidechain_domain::{ScEpochNumber, ScSlotNumber};
52use sp_api::ProvideRuntimeApi;
53use sp_blockchain::HeaderBackend;
54use sp_runtime::traits::Block as BlockT;
55use sp_runtime::traits::NumberFor;
56#[allow(deprecated)]
57use sp_sidechain::GetSidechainStatus;
58use std::cmp::Ordering;
59use std::ops::Range;
60
61#[cfg(test)]
62mod tests;
63
64/// Types of binary search queries over Partner Chain blocks
65pub mod predicates {
66	use super::*;
67
68	/// Query for any block in given Partner Chain epoch
69	pub struct AnyBlockInEpoch {
70		/// Queried Partner Chain epoch
71		pub epoch: ScEpochNumber,
72	}
73
74	/// Query for the first block in given Partner Chain epoch
75	pub struct FirstBlockInEpoch {
76		/// Queried Partner Chain epoch
77		pub epoch: ScEpochNumber,
78	}
79
80	/// Query for the last block in given Partner Chain epoch
81	pub struct LastBlockInEpoch {
82		/// Queried Partner Chain epoch
83		pub epoch: ScEpochNumber,
84	}
85
86	/// Query for any block in given slot range
87	pub struct AnyBlockInSlotRange {
88		/// Queried slot range. Left-inclusive, right-exclusive
89		pub slot_range: Range<ScSlotNumber>,
90	}
91
92	/// Query for the last block in given slot range with upper block number bound
93	pub struct LatestBlockInSlotRange<Block: BlockT> {
94		/// Queried slot range. Left-inclusive, right-exclusive
95		pub slot_range: Range<ScSlotNumber>,
96		/// Upper bound for the number of returned block
97		pub latest_block: NumberFor<Block>,
98	}
99}
100use predicates::*;
101
102/// Runtime API client used by the block queries in this crate
103pub trait Client<Block: BlockT>: HeaderBackend<Block> + ProvideRuntimeApi<Block> {}
104
105impl<C: HeaderBackend<Block> + ProvideRuntimeApi<Block>, Block: BlockT> Client<Block> for C {}
106
107/// Interface for retrieving information about slot and epoch of Partner Chain blocks
108pub trait SidechainInfo<Block: BlockT>: Client<Block> {
109	/// Error type
110	type Error: std::error::Error;
111
112	/// Finds the Partner Chain slot number for a given block number
113	fn get_slot_of_block(
114		&self,
115		block_number: NumberFor<Block>,
116	) -> Result<ScSlotNumber, Self::Error>;
117
118	/// Finds the Partner Chain eopch number for a given block number
119	fn get_epoch_of_block(
120		&self,
121		block_number: NumberFor<Block>,
122	) -> Result<ScEpochNumber, Self::Error>;
123}
124
125/// Comparator used for binary searching the block history
126///
127/// Types implementing this trait represent some _search target_, which is to be found through
128/// binary search over block history. Note that this search target can be a single block defined
129/// by its _slot_ or some other monotonically increasing block property, or a _range_ of blocks
130/// defined by a range of slots or other property.
131pub trait CompareStrategy<Block: BlockT, BlockInfo: Client<Block>> {
132	/// Error type
133	type Error: std::error::Error;
134
135	/// Compares a block against a search target.
136	///
137	/// # Returns
138	/// - `Ok(Ordering::Less)` if the block is below the target
139	/// - `Ok(Ordering::Equal)` if the block is at target
140	/// - `Ok(Ordering::Greater)` if the block is above the target
141	/// - `Err` if an error occured
142	fn compare_block(
143		&self,
144		block: NumberFor<Block>,
145		block_info: &BlockInfo,
146	) -> Result<Ordering, Self::Error>;
147}
148
149/// Runtime client capable of finding Partner Chain blocks via binary search using some [CompareStrategy].
150pub trait FindSidechainBlock<Block: BlockT, CS: CompareStrategy<Block, Self>>:
151	Client<Block> + Sized
152{
153	/// Error type
154	type Error: std::error::Error;
155
156	/// Finds the number of the block satisfying `compare_strategy`
157	fn find_block_number(&self, compare_strategy: CS) -> Result<NumberFor<Block>, Self::Error>;
158
159	/// Finds the hash of the block satisfying `compare_strategy`
160	fn find_block(&self, compare_strategy: CS) -> Result<Block::Hash, Self::Error>;
161}
sidechain_block_search/lib.rs

sidechain_block_search/
lib.rs
