10529269877

Committed 23 Aug 2024 04:42PM UTC coverage: 82.011% (+0.2%) from 81.848%

Build # 10529269877

Build Type

Pull #1569

github

Committed by

web-flow

Commit Message

Merge c7111023f into 9e6ac72a6

Pull Request Pull Request #1569: `bdk_core` WIP WIP WIP

Run Details

495 of 556 new or added lines in 14 files covered. (89.03%)

5 existing lines in 4 files now uncovered.

11215 of 13675 relevant lines covered (82.01%)

14035.85 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.16

/crates/core/src/checkpoint.rs

use core::ops::RangeBounds;

use alloc::sync::Arc;
use bitcoin::BlockHash;

use crate::BlockId;

/// A checkpoint is a node of a reference-counted linked list of [`BlockId`]s.
///
/// Checkpoints are cheaply cloneable and are useful to find the agreement point between two sparse
/// block chains.
#[derive(Debug, Clone)]
pub struct CheckPoint(Arc<CPInner>);

/// The internal contents of [`CheckPoint`].
#[derive(Debug, Clone)]
struct CPInner {
    /// Block id (hash and height).
    block: BlockId,
    /// Previous checkpoint (if any).
    prev: Option<Arc<CPInner>>,
}

impl PartialEq for CheckPoint {
    fn eq(&self, other: &Self) -> bool {
        let self_cps = self.iter().map(|cp| cp.block_id());
        let other_cps = other.iter().map(|cp| cp.block_id());
        self_cps.eq(other_cps)
    }
}

impl CheckPoint {
    /// Construct a new base block at the front of a linked list.
    pub fn new(block: BlockId) -> Self {
        Self(Arc::new(CPInner { block, prev: None }))
    }

    /// Construct a checkpoint from a list of [`BlockId`]s in ascending height order.
    ///
    /// # Errors
    ///
    /// This method will error if any of the follow occurs:
    ///
    /// - The `blocks` iterator is empty, in which case, the error will be `None`.
    /// - The `blocks` iterator is not in ascending height order.
    /// - The `blocks` iterator contains multiple [`BlockId`]s of the same height.
    ///
    /// The error type is the last successful checkpoint constructed (if any).
    pub fn from_block_ids(
        block_ids: impl IntoIterator<Item = BlockId>,
    ) -> Result<Self, Option<Self>> {
        let mut blocks = block_ids.into_iter();
        let mut acc = CheckPoint::new(blocks.next().ok_or(None)?);
        for id in blocks {
            acc = acc.push(id).map_err(Some)?;
        }
        Ok(acc)
    }

    /// Construct a checkpoint from the given `header` and block `height`.
    ///
    /// If `header` is of the genesis block, the checkpoint won't have a [`prev`] node. Otherwise,
    /// we return a checkpoint linked with the previous block.
    ///
    /// [`prev`]: CheckPoint::prev
    pub fn from_header(header: &bitcoin::block::Header, height: u32) -> Self {
        let hash = header.block_hash();
        let this_block_id = BlockId { height, hash };

        let prev_height = match height.checked_sub(1) {
            Some(h) => h,
            None => return Self::new(this_block_id),
        };

        let prev_block_id = BlockId {
            height: prev_height,
            hash: header.prev_blockhash,
        };

        CheckPoint::new(prev_block_id)
            .push(this_block_id)
            .expect("must construct checkpoint")
    }

    /// Puts another checkpoint onto the linked list representing the blockchain.
    ///
    /// Returns an `Err(self)` if the block you are pushing on is not at a greater height that the one you
    /// are pushing on to.
    pub fn push(self, block: BlockId) -> Result<Self, Self> {
        if self.height() < block.height {
            Ok(Self(Arc::new(CPInner {
                block,
                prev: Some(self.0),
            })))
        } else {
            Err(self)
        }
    }

    /// Extends the checkpoint linked list by a iterator of block ids.
    ///
    /// Returns an `Err(self)` if there is block which does not have a greater height than the
    /// previous one.
    pub fn extend(self, blocks: impl IntoIterator<Item = BlockId>) -> Result<Self, Self> {
        let mut curr = self.clone();
        for block in blocks {
            curr = curr.push(block).map_err(|_| self.clone())?;
        }
        Ok(curr)
    }

    /// Get the [`BlockId`] of the checkpoint.
    pub fn block_id(&self) -> BlockId {
        self.0.block
    }

    /// Get the height of the checkpoint.
    pub fn height(&self) -> u32 {
        self.0.block.height
    }

    /// Get the block hash of the checkpoint.
    pub fn hash(&self) -> BlockHash {
        self.0.block.hash
    }

    /// Get the previous checkpoint in the chain
    pub fn prev(&self) -> Option<CheckPoint> {
        self.0.prev.clone().map(CheckPoint)
    }

    /// Iterate from this checkpoint in descending height.
    pub fn iter(&self) -> CheckPointIter {
        self.clone().into_iter()
    }

    /// Get checkpoint at `height`.
    ///
    /// Returns `None` if checkpoint at `height` does not exist`.
    pub fn get(&self, height: u32) -> Option<Self> {
        self.range(height..=height).next()
    }

    /// Iterate checkpoints over a height range.
    ///
    /// Note that we always iterate checkpoints in reverse height order (iteration starts at tip
    /// height).
    pub fn range<R>(&self, range: R) -> impl Iterator<Item = CheckPoint>
    where
        R: RangeBounds<u32>,
    {
        let start_bound = range.start_bound().cloned();
        let end_bound = range.end_bound().cloned();
        self.iter()
            .skip_while(move |cp| match end_bound {
                core::ops::Bound::Included(inc_bound) => cp.height() > inc_bound,
                core::ops::Bound::Excluded(exc_bound) => cp.height() >= exc_bound,
                core::ops::Bound::Unbounded => false,
            })
            .take_while(move |cp| match start_bound {
                core::ops::Bound::Included(inc_bound) => cp.height() >= inc_bound,
                core::ops::Bound::Excluded(exc_bound) => cp.height() > exc_bound,
                core::ops::Bound::Unbounded => true,
            })
    }

    /// Inserts `block_id` at its height within the chain.
    ///
    /// The effect of `insert` depends on whether a height already exists. If it doesn't the
    /// `block_id` we inserted and all pre-existing blocks higher than it will be re-inserted after
    /// it. If the height already existed and has a conflicting block hash then it will be purged
    /// along with all block followin it. The returned chain will have a tip of the `block_id`
    /// passed in. Of course, if the `block_id` was already present then this just returns `self`.
    #[must_use]
    pub fn insert(self, block_id: BlockId) -> Self {
        assert_ne!(block_id.height, 0, "cannot insert the genesis block");

        let mut cp = self.clone();
        let mut tail = vec![];
        let base = loop {
            if cp.height() == block_id.height {
                if cp.hash() == block_id.hash {
                    return self;
                }
                // if we have a conflict we just return the inserted block because the tail is by
                // implication invalid.
                tail = vec![];
                break cp.prev().expect("can't be called on genesis block");
            }

            if cp.height() < block_id.height {
                break cp;
            }

            tail.push(cp.block_id());
            cp = cp.prev().expect("will break before genesis block");
        };

        base.extend(core::iter::once(block_id).chain(tail.into_iter().rev()))
            .expect("tail is in order")
    }

    /// This method tests for `self` and `other` to have equal internal pointers.
    pub fn eq_ptr(&self, other: &Self) -> bool {
        Arc::as_ptr(&self.0) == Arc::as_ptr(&other.0)
    }
}

/// Iterates over checkpoints backwards.
pub struct CheckPointIter {
    current: Option<Arc<CPInner>>,
}

impl Iterator for CheckPointIter {
    type Item = CheckPoint;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.current.clone()?;
        self.current.clone_from(&current.prev);
        Some(CheckPoint(current))
    }
}

impl IntoIterator for CheckPoint {
    type Item = CheckPoint;
    type IntoIter = CheckPointIter;

    fn into_iter(self) -> Self::IntoIter {
        CheckPointIter {
            current: Some(self.0),
        }
    }
}

1	use core::ops::RangeBounds;
2
3	use alloc::sync::Arc;
4	use bitcoin::BlockHash;
5
6	use crate::BlockId;
7
8	/// A checkpoint is a node of a reference-counted linked list of [`BlockId`]s.
9	///
10	/// Checkpoints are cheaply cloneable and are useful to find the agreement point between two sparse
11	/// block chains.
12	#[derive(Debug, Clone)]
13	pub struct CheckPoint(Arc<CPInner>);
14
15	/// The internal contents of [`CheckPoint`].
16	#[derive(Debug, Clone)]
17	struct CPInner {
18	/// Block id (hash and height).
19	block: BlockId,
20	/// Previous checkpoint (if any).
21	prev: Option<Arc<CPInner>>,
22	}
23
24	impl PartialEq for CheckPoint {
25	fn eq(&self, other: &Self) -> bool {	352✔
26	let self_cps = self.iter().map(\|cp\| cp.block_id());	924✔
27	let other_cps = other.iter().map(\|cp\| cp.block_id());	924✔
28	self_cps.eq(other_cps)	352✔
29	}	352✔
30	}
31
32	impl CheckPoint {
33	/// Construct a new base block at the front of a linked list.
34	pub fn new(block: BlockId) -> Self {	17,226✔
35	Self(Arc::new(CPInner { block, prev: None }))	17,226✔
36	}	17,226✔
37
38	/// Construct a checkpoint from a list of [`BlockId`]s in ascending height order.
39	///
40	/// # Errors
41	///
42	/// This method will error if any of the follow occurs:
43	///
44	/// - The `blocks` iterator is empty, in which case, the error will be `None`.
45	/// - The `blocks` iterator is not in ascending height order.
46	/// - The `blocks` iterator contains multiple [`BlockId`]s of the same height.
47	///
48	/// The error type is the last successful checkpoint constructed (if any).
49	pub fn from_block_ids(	446✔
50	block_ids: impl IntoIterator<Item = BlockId>,	446✔
51	) -> Result<Self, Option<Self>> {	446✔
52	let mut blocks = block_ids.into_iter();	446✔
53	let mut acc = CheckPoint::new(blocks.next().ok_or(None)?);	446✔
54	for id in blocks {	267,562✔
55	acc = acc.push(id).map_err(Some)?;	267,119✔
56	}
57	Ok(acc)	443✔
58	}	446✔
59
60	/// Construct a checkpoint from the given `header` and block `height`.
61	///
62	/// If `header` is of the genesis block, the checkpoint won't have a [`prev`] node. Otherwise,
63	/// we return a checkpoint linked with the previous block.
64	///
65	/// [`prev`]: CheckPoint::prev
66	pub fn from_header(header: &bitcoin::block::Header, height: u32) -> Self {	3,938✔
67	let hash = header.block_hash();	3,938✔
68	let this_block_id = BlockId { height, hash };	3,938✔
69
70	let prev_height = match height.checked_sub(1) {	3,938✔
71	Some(h) => h,	3,938✔
NEW 72	None => return Self::new(this_block_id),	×
73	};
74
75	let prev_block_id = BlockId {	3,938✔
76	height: prev_height,	3,938✔
77	hash: header.prev_blockhash,	3,938✔
78	};	3,938✔
79		3,938✔
80	CheckPoint::new(prev_block_id)	3,938✔
81	.push(this_block_id)	3,938✔
82	.expect("must construct checkpoint")	3,938✔
83	}	3,938✔
84
85	/// Puts another checkpoint onto the linked list representing the blockchain.
86	///
87	/// Returns an `Err(self)` if the block you are pushing on is not at a greater height that the one you
88	/// are pushing on to.
89	pub fn push(self, block: BlockId) -> Result<Self, Self> {	5,849,624✔
90	if self.height() < block.height {	5,849,624✔
91	Ok(Self(Arc::new(CPInner {	5,849,580✔
92	block,	5,849,580✔
93	prev: Some(self.0),	5,849,580✔
94	})))	5,849,580✔
95	} else {
96	Err(self)	44✔
97	}
98	}	5,849,624✔
99
100	/// Extends the checkpoint linked list by a iterator of block ids.
101	///
102	/// Returns an `Err(self)` if there is block which does not have a greater height than the
103	/// previous one.
104	pub fn extend(self, blocks: impl IntoIterator<Item = BlockId>) -> Result<Self, Self> {	18,605✔
105	let mut curr = self.clone();	18,605✔
106	for block in blocks {	40,884✔
107	curr = curr.push(block).map_err(\|_\| self.clone())?;	22,279✔
108	}
109	Ok(curr)	18,605✔
110	}	18,605✔
111
112	/// Get the [`BlockId`] of the checkpoint.
113	pub fn block_id(&self) -> BlockId {	50,402✔
114	self.0.block	50,402✔
115	}	50,402✔
116
117	/// Get the height of the checkpoint.
118	pub fn height(&self) -> u32 {	18,010,586✔
119	self.0.block.height	18,010,586✔
120	}	18,010,586✔
121
122	/// Get the block hash of the checkpoint.
123	pub fn hash(&self) -> BlockHash {	183,216✔
124	self.0.block.hash	183,216✔
125	}	183,216✔
126
127	/// Get the previous checkpoint in the chain
128	pub fn prev(&self) -> Option<CheckPoint> {	15,048✔
129	self.0.prev.clone().map(CheckPoint)	15,048✔
130	}	15,048✔
131
132	/// Iterate from this checkpoint in descending height.
133	pub fn iter(&self) -> CheckPointIter {	194,304✔
134	self.clone().into_iter()	194,304✔
135	}	194,304✔
136
137	/// Get checkpoint at `height`.
138	///
139	/// Returns `None` if checkpoint at `height` does not exist`.
140	pub fn get(&self, height: u32) -> Option<Self> {	134,794✔
141	self.range(height..=height).next()	134,794✔
142	}	134,794✔
143
144	/// Iterate checkpoints over a height range.
145	///
146	/// Note that we always iterate checkpoints in reverse height order (iteration starts at tip
147	/// height).
148	pub fn range<R>(&self, range: R) -> impl Iterator<Item = CheckPoint>	135,323✔
149	where	135,323✔
150	R: RangeBounds<u32>,	135,323✔
151	{	135,323✔
152	let start_bound = range.start_bound().cloned();	135,323✔
153	let end_bound = range.end_bound().cloned();	135,323✔
154	self.iter()	135,323✔
155	.skip_while(move \|cp\| match end_bound {	677,250✔
156	core::ops::Bound::Included(inc_bound) => cp.height() > inc_bound,	632,118✔
157	core::ops::Bound::Excluded(exc_bound) => cp.height() >= exc_bound,	44,788✔
158	core::ops::Bound::Unbounded => false,	344✔
159	})	677,250✔
160	.take_while(move \|cp\| match start_bound {	229,736✔
161	core::ops::Bound::Included(inc_bound) => cp.height() >= inc_bound,	162,618✔
162	core::ops::Bound::Excluded(exc_bound) => cp.height() > exc_bound,	24,586✔
163	core::ops::Bound::Unbounded => true,	42,532✔
164	})	229,736✔
165	}	135,323✔
166
167	/// Inserts `block_id` at its height within the chain.
168	///
169	/// The effect of `insert` depends on whether a height already exists. If it doesn't the
170	/// `block_id` we inserted and all pre-existing blocks higher than it will be re-inserted after
171	/// it. If the height already existed and has a conflicting block hash then it will be purged
172	/// along with all block followin it. The returned chain will have a tip of the `block_id`
173	/// passed in. Of course, if the `block_id` was already present then this just returns `self`.
174	#[must_use]
175	pub fn insert(self, block_id: BlockId) -> Self {	8,448✔
176	assert_ne!(block_id.height, 0, "cannot insert the genesis block");	8,448✔
177
178	let mut cp = self.clone();	8,448✔
179	let mut tail = vec![];	8,448✔
180	let base = loop {	5,698✔
181	if cp.height() == block_id.height {	23,364✔
182	if cp.hash() == block_id.hash {	2,794✔
183	return self;	2,750✔
184	}	44✔
185	// if we have a conflict we just return the inserted block because the tail is by	44✔
186	// implication invalid.	44✔
187	tail = vec![];	44✔
188	break cp.prev().expect("can't be called on genesis block");	44✔
189	}	20,570✔
190		20,570✔
191	if cp.height() < block_id.height {	20,570✔
192	break cp;	5,654✔
193	}	14,916✔
194		14,916✔
195	tail.push(cp.block_id());	14,916✔
196	cp = cp.prev().expect("will break before genesis block");	14,916✔
197	};
198
199	base.extend(core::iter::once(block_id).chain(tail.into_iter().rev()))	5,698✔
200	.expect("tail is in order")	5,698✔
201	}	8,448✔
202
203	/// This method tests for `self` and `other` to have equal internal pointers.
204	pub fn eq_ptr(&self, other: &Self) -> bool {	11,044✔
205	Arc::as_ptr(&self.0) == Arc::as_ptr(&other.0)	11,044✔
206	}	11,044✔
207	}
208
209	/// Iterates over checkpoints backwards.
210	pub struct CheckPointIter {
211	current: Option<Arc<CPInner>>,
212	}
213
214	impl Iterator for CheckPointIter {
215	type Item = CheckPoint;
216
217	fn next(&mut self) -> Option<Self::Item> {	10,775,688✔
218	let current = self.current.clone()?;	10,775,688✔
219	self.current.clone_from(&current.prev);	10,757,032✔
220	Some(CheckPoint(current))	10,757,032✔
221	}	10,775,688✔
222	}
223
224	impl IntoIterator for CheckPoint {
225	type Item = CheckPoint;
226	type IntoIter = CheckPointIter;
227
228	fn into_iter(self) -> Self::IntoIter {	194,348✔
229	CheckPointIter {	194,348✔
230	current: Some(self.0),	194,348✔
231	}	194,348✔
232	}	194,348✔
233	}

bitcoindevkit / bdk / 10529269877

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous