5582722505

pending completion

Build # 5582722505

Build Type

Pull #1002

github

Committed by

web-flow

Commit Message

Merge 98a52d0cb into 81c761339

Pull Request Pull Request #1002: Implement linked-list `LocalChain` and add rpc-chain module/example

Run Details

945 of 945 new or added lines in 10 files covered. (100.0%)

8019 of 10332 relevant lines covered (77.61%)

5036.23 hits per line

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

80.13

/crates/chain/src/indexed_tx_graph.rs

//! Contains the [`IndexedTxGraph`] structure and associated types.
//!
//! This is essentially a [`TxGraph`] combined with an indexer.

use alloc::vec::Vec;
use bitcoin::{OutPoint, Transaction, TxOut};

use crate::{
    keychain::DerivationAdditions,
    tx_graph::{Additions, TxGraph},
    Anchor, Append,
};

/// A struct that combines [`TxGraph`] and an [`Indexer`] implementation.
///
/// This structure ensures that [`TxGraph`] and [`Indexer`] are updated atomically.
#[derive(Debug)]
pub struct IndexedTxGraph<A, I> {
    /// Transaction index.
    pub index: I,
    graph: TxGraph<A>,
}

impl<A, I: Default> Default for IndexedTxGraph<A, I> {
    fn default() -> Self {
        Self {
            graph: Default::default(),
            index: Default::default(),
        }
    }
}

impl<A, I> IndexedTxGraph<A, I> {
    /// Construct a new [`IndexedTxGraph`] with a given `index`.
    pub fn new(index: I) -> Self {
        Self {
            index,
            graph: TxGraph::default(),
        }
    }

    /// Get a reference of the internal transaction graph.
    pub fn graph(&self) -> &TxGraph<A> {
        &self.graph
    }
}

impl<A: Anchor, I: Indexer> IndexedTxGraph<A, I> {
    /// Applies the [`IndexedAdditions`] to the [`IndexedTxGraph`].
    pub fn apply_additions(&mut self, additions: IndexedAdditions<A, I::Additions>) {
        let IndexedAdditions {
            graph_additions,
            index_additions,
        } = additions;

        self.index.apply_additions(index_additions);

        for tx in &graph_additions.txs {
            self.index.index_tx(tx);
        }
        for (&outpoint, txout) in &graph_additions.txouts {
            self.index.index_txout(outpoint, txout);
        }

        self.graph.apply_additions(graph_additions);
    }
}

impl<A: Anchor, I: Indexer> IndexedTxGraph<A, I>
where
    I::Additions: Default + Append,
{
    /// Apply an `update` directly.
    ///
    /// `update` is a [`TxGraph<A>`] and the resultant changes is returned as [`IndexedAdditions`].
    pub fn apply_update(&mut self, update: TxGraph<A>) -> IndexedAdditions<A, I::Additions> {
        let graph_additions = self.graph.apply_update(update);

        let mut index_additions = I::Additions::default();
        for added_tx in &graph_additions.txs {
            index_additions.append(self.index.index_tx(added_tx));
        }
        for (&added_outpoint, added_txout) in &graph_additions.txouts {
            index_additions.append(self.index.index_txout(added_outpoint, added_txout));
        }

        IndexedAdditions {
            graph_additions,
            index_additions,
        }
    }

    /// Apply `update`, but filters out irrelevant transactions.
    ///
    /// Relevancy is determined by the [`Indexer::is_tx_relevant`] implementation of `I`.
    pub fn prune_and_apply_update(
        &mut self,
        update: TxGraph<A>,
    ) -> IndexedAdditions<A, I::Additions> {
        let mut additions = IndexedAdditions::<A, I::Additions>::default();

        // index all transactions first
        for tx_node in update.full_txs() {
            additions
                .index_additions
                .append(self.index.index_tx(&tx_node));
        }

        let update = update
            .full_txs()
            .filter(|tx_node| self.index.is_tx_relevant(tx_node))
            .fold(TxGraph::default(), |mut g, tx_node| -> TxGraph<A> {
                let _ = g.insert_tx(tx_node.tx.clone());
                for anchor in tx_node.anchors {
                    let _ = g.insert_anchor(tx_node.txid, anchor.clone());
                }
                let _ = g.insert_seen_at(tx_node.txid, tx_node.last_seen_unconfirmed);
                g
            });

        additions.append(self.apply_update(update));
        additions
    }

    /// Insert a floating `txout` of given `outpoint`.
    pub fn insert_txout(
        &mut self,
        outpoint: OutPoint,
        txout: &TxOut,
    ) -> IndexedAdditions<A, I::Additions> {
        let mut update = TxGraph::<A>::default();
        let _ = update.insert_txout(outpoint, txout.clone());
        self.apply_update(update)
    }

    /// Insert and index a transaction into the graph.
    ///
    /// `anchors` can be provided to anchor the transaction to various blocks. `seen_at` is a
    /// unix timestamp of when the transaction is last seen.
    pub fn insert_tx(
        &mut self,
        tx: &Transaction,
        anchors: impl IntoIterator<Item = A>,
        seen_at: Option<u64>,
    ) -> IndexedAdditions<A, I::Additions> {
        let txid = tx.txid();

        let mut update = TxGraph::<A>::default();
        if self.graph.get_tx(txid).is_none() {
            let _ = update.insert_tx(tx.clone());
        }
        for anchor in anchors.into_iter() {
            let _ = update.insert_anchor(txid, anchor);
        }
        if let Some(seen_at) = seen_at {
            let _ = update.insert_seen_at(txid, seen_at);
        }

        self.apply_update(update)
    }

    /// Insert relevant transactions from the given `txs` iterator.
    ///
    /// Relevancy is determined by the [`Indexer::is_tx_relevant`] implementation of `I`. Irrelevant
    /// transactions in `txs` will be ignored. `txs` do not need to be in topological order.
    ///
    /// `anchors` can be provided to anchor the transactions to blocks. `seen_at` is a unix
    /// timestamp of when the transactions are last seen.
    pub fn insert_relevant_txs<'t>(
        &mut self,
        txs: impl IntoIterator<Item = (&'t Transaction, impl IntoIterator<Item = A>)>,
        seen_at: Option<u64>,
    ) -> IndexedAdditions<A, I::Additions> {
        // The algorithm below allows for non-topologically ordered transactions by using two loops.
        // This is achieved by:
        // 1. insert all txs into the index. If they are irrelevant then that's fine it will just
        //    not store anything about them.
        // 2. decide whether to insert them into the graph depending on whether `is_tx_relevant`
        //    returns true or not. (in a second loop).
        let mut additions = IndexedAdditions::<A, I::Additions>::default();
        let txs = txs
            .into_iter()
            .inspect(|(tx, _)| additions.index_additions.append(self.index.index_tx(tx)))
            .collect::<Vec<_>>();
        additions.append(
            txs.into_iter()
                .filter_map(|(tx, anchors)| match self.index.is_tx_relevant(tx) {
                    true => Some(self.insert_tx(tx, anchors, seen_at)),
                    false => None,
                })
                .fold(Default::default(), |mut acc, other| {
                    acc.append(other);
                    acc
                }),
        );
        additions
    }
}

/// A structure that represents changes to an [`IndexedTxGraph`].
#[derive(Clone, Debug, PartialEq)]
#[cfg_attr(
    feature = "serde",
    derive(serde::Deserialize, serde::Serialize),
    serde(
        crate = "serde_crate",
        bound(
            deserialize = "A: Ord + serde::Deserialize<'de>, IA: serde::Deserialize<'de>",
            serialize = "A: Ord + serde::Serialize, IA: serde::Serialize"
        )
    )
)]
#[must_use]
pub struct IndexedAdditions<A, IA> {
    /// [`TxGraph`] additions.
    pub graph_additions: Additions<A>,
    /// [`Indexer`] additions.
    pub index_additions: IA,
}

impl<A, IA: Default> Default for IndexedAdditions<A, IA> {
    fn default() -> Self {
        Self {
            graph_additions: Default::default(),
            index_additions: Default::default(),
        }
    }
}

impl<A: Anchor, IA: Append> Append for IndexedAdditions<A, IA> {
    fn append(&mut self, other: Self) {
        self.graph_additions.append(other.graph_additions);
        self.index_additions.append(other.index_additions);
    }

    fn is_empty(&self) -> bool {
        self.graph_additions.is_empty() && self.index_additions.is_empty()
    }
}

impl<A, IA: Default> From<Additions<A>> for IndexedAdditions<A, IA> {
    fn from(graph_additions: Additions<A>) -> Self {
        Self {
            graph_additions,
            ..Default::default()
        }
    }
}

impl<A, K> From<DerivationAdditions<K>> for IndexedAdditions<A, DerivationAdditions<K>> {
    fn from(index_additions: DerivationAdditions<K>) -> Self {
        Self {
            graph_additions: Default::default(),
            index_additions,
        }
    }
}

/// Represents a structure that can index transaction data.
pub trait Indexer {
    /// The resultant "additions" when new transaction data is indexed.
    type Additions;

    /// Scan and index the given `outpoint` and `txout`.
    fn index_txout(&mut self, outpoint: OutPoint, txout: &TxOut) -> Self::Additions;

    /// Scan and index the given transaction.
    fn index_tx(&mut self, tx: &Transaction) -> Self::Additions;

    /// Apply additions to itself.
    fn apply_additions(&mut self, additions: Self::Additions);

    /// Determines whether the transaction should be included in the index.
    fn is_tx_relevant(&self, tx: &Transaction) -> bool;
}

1	//! Contains the [`IndexedTxGraph`] structure and associated types.
2	//!
3	//! This is essentially a [`TxGraph`] combined with an indexer.
4
5	use alloc::vec::Vec;
6	use bitcoin::{OutPoint, Transaction, TxOut};
7
8	use crate::{
9	keychain::DerivationAdditions,
10	tx_graph::{Additions, TxGraph},
11	Anchor, Append,
12	};
13
14	/// A struct that combines [`TxGraph`] and an [`Indexer`] implementation.
15	///
16	/// This structure ensures that [`TxGraph`] and [`Indexer`] are updated atomically.
17	#[derive(Debug)]	×
18	pub struct IndexedTxGraph<A, I> {
19	/// Transaction index.
20	pub index: I,
21	graph: TxGraph<A>,
22	}
23
24	impl<A, I: Default> Default for IndexedTxGraph<A, I> {
25	fn default() -> Self {	141✔
26	Self {	141✔
27	graph: Default::default(),	141✔
28	index: Default::default(),	141✔
29	}	141✔
30	}	141✔
31	}
32
33	impl<A, I> IndexedTxGraph<A, I> {
34	/// Construct a new [`IndexedTxGraph`] with a given `index`.
35	pub fn new(index: I) -> Self {	×
36	Self {	×
37	index,	×
38	graph: TxGraph::default(),	×
39	}	×
40	}	×
41
42	/// Get a reference of the internal transaction graph.
43	pub fn graph(&self) -> &TxGraph<A> {	5,076✔
44	&self.graph	5,076✔
45	}	5,076✔
46	}
47
48	impl<A: Anchor, I: Indexer> IndexedTxGraph<A, I> {
49	/// Applies the [`IndexedAdditions`] to the [`IndexedTxGraph`].
50	pub fn apply_additions(&mut self, additions: IndexedAdditions<A, I::Additions>) {	138✔
51	let IndexedAdditions {	138✔
52	graph_additions,	138✔
53	index_additions,	138✔
54	} = additions;	138✔
55		138✔
56	self.index.apply_additions(index_additions);	138✔
57
58	for tx in &graph_additions.txs {	138✔
59	self.index.index_tx(tx);	×
60	}	×
61	for (&outpoint, txout) in &graph_additions.txouts {	138✔
62	self.index.index_txout(outpoint, txout);	×
63	}	×
64
65	self.graph.apply_additions(graph_additions);	138✔
66	}	138✔
67	}
68
69	impl<A: Anchor, I: Indexer> IndexedTxGraph<A, I>
70	where
71	I::Additions: Default + Append,
72	{
73	/// Apply an `update` directly.
74	///
75	/// `update` is a [`TxGraph<A>`] and the resultant changes is returned as [`IndexedAdditions`].
76	pub fn apply_update(&mut self, update: TxGraph<A>) -> IndexedAdditions<A, I::Additions> {	170✔
77	let graph_additions = self.graph.apply_update(update);	170✔
78		170✔
79	let mut index_additions = I::Additions::default();	170✔
80	for added_tx in &graph_additions.txs {	341✔
81	index_additions.append(self.index.index_tx(added_tx));	171✔
82	}	171✔
83	for (&added_outpoint, added_txout) in &graph_additions.txouts {	170✔
84	index_additions.append(self.index.index_txout(added_outpoint, added_txout));	×
85	}	×
86
87	IndexedAdditions {	170✔
88	graph_additions,	170✔
89	index_additions,	170✔
90	}	170✔
91	}	170✔
92
93	/// Apply `update`, but filters out irrelevant transactions.
94	///
95	/// Relevancy is determined by the [`Indexer::is_tx_relevant`] implementation of `I`.
96	pub fn prune_and_apply_update(	1✔
97	&mut self,	1✔
98	update: TxGraph<A>,	1✔
99	) -> IndexedAdditions<A, I::Additions> {	1✔
100	let mut additions = IndexedAdditions::<A, I::Additions>::default();	1✔
101
102	// index all transactions first
103	for tx_node in update.full_txs() {	3✔
104	additions	3✔
105	.index_additions	3✔
106	.append(self.index.index_tx(&tx_node));	3✔
107	}	3✔
108
109	let update = update	1✔
110	.full_txs()	1✔
111	.filter(\|tx_node\| self.index.is_tx_relevant(tx_node))	3✔
112	.fold(TxGraph::default(), \|mut g, tx_node\| -> TxGraph<A> {	2✔
113	let _ = g.insert_tx(tx_node.tx.clone());	2✔
114	for anchor in tx_node.anchors {	2✔
115	let _ = g.insert_anchor(tx_node.txid, anchor.clone());	×
116	}	×
117	let _ = g.insert_seen_at(tx_node.txid, tx_node.last_seen_unconfirmed);	2✔
118	g	2✔
119	});	2✔
120		1✔
121	additions.append(self.apply_update(update));	1✔
122	additions	1✔
123	}	1✔
124
125	/// Insert a floating `txout` of given `outpoint`.
126	pub fn insert_txout(	×
127	&mut self,	×
128	outpoint: OutPoint,	×
129	txout: &TxOut,	×
130	) -> IndexedAdditions<A, I::Additions> {	×
131	let mut update = TxGraph::<A>::default();	×
132	let _ = update.insert_txout(outpoint, txout.clone());	×
133	self.apply_update(update)	×
134	}	×
135
136	/// Insert and index a transaction into the graph.
137	///
138	/// `anchors` can be provided to anchor the transaction to various blocks. `seen_at` is a
139	/// unix timestamp of when the transaction is last seen.
140	pub fn insert_tx(	169✔
141	&mut self,	169✔
142	tx: &Transaction,	169✔
143	anchors: impl IntoIterator<Item = A>,	169✔
144	seen_at: Option<u64>,	169✔
145	) -> IndexedAdditions<A, I::Additions> {	169✔
146	let txid = tx.txid();	169✔
147		169✔
148	let mut update = TxGraph::<A>::default();	169✔
149	if self.graph.get_tx(txid).is_none() {	169✔
150	let _ = update.insert_tx(tx.clone());	169✔
151	}	169✔
152	for anchor in anchors.into_iter() {	169✔
153	let _ = update.insert_anchor(txid, anchor);	141✔
154	}	141✔
155	if let Some(seen_at) = seen_at {	169✔
156	let _ = update.insert_seen_at(txid, seen_at);	25✔
157	}	144✔
158
159	self.apply_update(update)	169✔
160	}	169✔
161
162	/// Insert relevant transactions from the given `txs` iterator.
163	///
164	/// Relevancy is determined by the [`Indexer::is_tx_relevant`] implementation of `I`. Irrelevant
165	/// transactions in `txs` will be ignored. `txs` do not need to be in topological order.
166	///
167	/// `anchors` can be provided to anchor the transactions to blocks. `seen_at` is a unix
168	/// timestamp of when the transactions are last seen.
169	pub fn insert_relevant_txs<'t>(	3✔
170	&mut self,	3✔
171	txs: impl IntoIterator<Item = (&'t Transaction, impl IntoIterator<Item = A>)>,	3✔
172	seen_at: Option<u64>,	3✔
173	) -> IndexedAdditions<A, I::Additions> {	3✔
174	// The algorithm below allows for non-topologically ordered transactions by using two loops.	3✔
175	// This is achieved by:	3✔
176	// 1. insert all txs into the index. If they are irrelevant then that's fine it will just	3✔
177	// not store anything about them.	3✔
178	// 2. decide whether to insert them into the graph depending on whether `is_tx_relevant`	3✔
179	// returns true or not. (in a second loop).	3✔
180	let mut additions = IndexedAdditions::<A, I::Additions>::default();	3✔
181	let txs = txs	3✔
182	.into_iter()	3✔
183	.inspect(\|(tx, _)\| additions.index_additions.append(self.index.index_tx(tx)))	9✔
184	.collect::<Vec<_>>();	3✔
185	additions.append(	3✔
186	txs.into_iter()	3✔
187	.filter_map(\|(tx, anchors)\| match self.index.is_tx_relevant(tx) {	9✔
188	true => Some(self.insert_tx(tx, anchors, seen_at)),	8✔
189	false => None,	1✔
190	})	9✔
191	.fold(Default::default(), \|mut acc, other\| {	8✔
192	acc.append(other);	8✔
193	acc	8✔
194	}),	8✔
195	);	3✔
196	additions	3✔
197	}	3✔
198	}
199
200	/// A structure that represents changes to an [`IndexedTxGraph`].
201	#[derive(Clone, Debug, PartialEq)]	2✔
202	#[cfg_attr(
203	feature = "serde",
204	derive(serde::Deserialize, serde::Serialize),	×
205	serde(
206	crate = "serde_crate",
207	bound(
208	deserialize = "A: Ord + serde::Deserialize<'de>, IA: serde::Deserialize<'de>",
209	serialize = "A: Ord + serde::Serialize, IA: serde::Serialize"
210	)
211	)
212	)]
213	#[must_use]
214	pub struct IndexedAdditions<A, IA> {
215	/// [`TxGraph`] additions.
216	pub graph_additions: Additions<A>,
217	/// [`Indexer`] additions.
218	pub index_additions: IA,
219	}
220
221	impl<A, IA: Default> Default for IndexedAdditions<A, IA> {
222	fn default() -> Self {	1,171✔
223	Self {	1,171✔
224	graph_additions: Default::default(),	1,171✔
225	index_additions: Default::default(),	1,171✔
226	}	1,171✔
227	}	1,171✔
228	}
229
230	impl<A: Anchor, IA: Append> Append for IndexedAdditions<A, IA> {
231	fn append(&mut self, other: Self) {	626✔
232	self.graph_additions.append(other.graph_additions);	626✔
233	self.index_additions.append(other.index_additions);	626✔
234	}	626✔
235
236	fn is_empty(&self) -> bool {	374✔
237	self.graph_additions.is_empty() && self.index_additions.is_empty()	374✔
238	}	374✔
239	}
240
241	impl<A, IA: Default> From<Additions<A>> for IndexedAdditions<A, IA> {
242	fn from(graph_additions: Additions<A>) -> Self {	×
243	Self {	×
244	graph_additions,	×
245	..Default::default()	×
246	}	×
247	}	×
248	}
249
250	impl<A, K> From<DerivationAdditions<K>> for IndexedAdditions<A, DerivationAdditions<K>> {
251	fn from(index_additions: DerivationAdditions<K>) -> Self {	324✔
252	Self {	324✔
253	graph_additions: Default::default(),	324✔
254	index_additions,	324✔
255	}	324✔
256	}	324✔
257	}
258
259	/// Represents a structure that can index transaction data.
260	pub trait Indexer {
261	/// The resultant "additions" when new transaction data is indexed.
262	type Additions;
263
264	/// Scan and index the given `outpoint` and `txout`.
265	fn index_txout(&mut self, outpoint: OutPoint, txout: &TxOut) -> Self::Additions;
266
267	/// Scan and index the given transaction.
268	fn index_tx(&mut self, tx: &Transaction) -> Self::Additions;
269
270	/// Apply additions to itself.
271	fn apply_additions(&mut self, additions: Self::Additions);
272
273	/// Determines whether the transaction should be included in the index.
274	fn is_tx_relevant(&self, tx: &Transaction) -> bool;
275	}

bitcoindevkit / bdk / 5582722505

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