tempo_transaction_pool/
best.rs

1//! An iterator over the best transactions in the tempo pool.
2
3use crate::transaction::TempoPooledTransaction;
4use reth_transaction_pool::{
5    BestTransactions, CoinbaseTipOrdering, Priority, TransactionOrdering,
6    error::InvalidPoolTransactionError,
7};
8
9/// An extension trait for [`BestTransactions`] that in addition to the transaction also yields the priority value.
10pub trait BestPriorityTransactions<T: TransactionOrdering>: BestTransactions {
11    /// Returns the next best transaction and its priority value.
12    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<T::PriorityValue>)>;
13}
14
15impl<T: TransactionOrdering> BestPriorityTransactions<T>
16    for reth_transaction_pool::pool::BestTransactions<T>
17{
18    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<T::PriorityValue>)> {
19        Self::next_tx_and_priority(self)
20    }
21}
22impl BestPriorityTransactions<CoinbaseTipOrdering<TempoPooledTransaction>>
23    for crate::tt_2d_pool::BestAA2dTransactions
24{
25    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<u128>)> {
26        Self::next_tx_and_priority(self)
27    }
28}
29
30/// A [`BestTransactions`] iterator that merges two individual implementations and always yields the next best item from either of the iterators.
31pub struct MergeBestTransactions<L, R, T>
32where
33    L: BestPriorityTransactions<T>,
34    R: BestPriorityTransactions<T, Item = L::Item>,
35    T: TransactionOrdering,
36{
37    left: L,
38    right: R,
39    next_left: Option<(L::Item, Priority<T::PriorityValue>)>,
40    next_right: Option<(L::Item, Priority<T::PriorityValue>)>,
41}
42
43impl<L, R, T> MergeBestTransactions<L, R, T>
44where
45    L: BestPriorityTransactions<T>,
46    R: BestPriorityTransactions<T, Item = L::Item>,
47    T: TransactionOrdering,
48{
49    /// Creates a new iterator over the given iterators.
50    pub fn new(left: L, right: R) -> Self {
51        Self {
52            left,
53            right,
54            next_left: None,
55            next_right: None,
56        }
57    }
58}
59
60impl<L, R, T> MergeBestTransactions<L, R, T>
61where
62    L: BestPriorityTransactions<T>,
63    R: BestPriorityTransactions<T, Item = L::Item>,
64    T: TransactionOrdering,
65{
66    /// Returns the next transaction from either the left or the right iterator with the higher priority.
67    fn next_best(&mut self) -> Option<(L::Item, Priority<T::PriorityValue>)> {
68        if self.next_left.is_none() {
69            self.next_left = self.left.next_tx_and_priority();
70        }
71        if self.next_right.is_none() {
72            self.next_right = self.right.next_tx_and_priority();
73        }
74
75        match (&mut self.next_left, &mut self.next_right) {
76            (None, None) => {
77                // both iters are done
78                None
79            }
80            // Only left has an item - take it
81            (Some(_), None) => {
82                let (item, priority) = self.next_left.take()?;
83                Some((item, priority))
84            }
85            // Only right has an item - take it
86            (None, Some(_)) => {
87                let (item, priority) = self.next_right.take()?;
88                Some((item, priority))
89            }
90            // Both sides have items - compare priorities and take the higher one
91            (Some((_, left_priority)), Some((_, right_priority))) => {
92                // Higher priority value is better
93                if left_priority >= right_priority {
94                    let (item, priority) = self.next_left.take()?;
95                    Some((item, priority))
96                } else {
97                    let (item, priority) = self.next_right.take()?;
98                    Some((item, priority))
99                }
100            }
101        }
102    }
103}
104
105impl<L, R, T> Iterator for MergeBestTransactions<L, R, T>
106where
107    L: BestPriorityTransactions<T>,
108    R: BestPriorityTransactions<T, Item = L::Item>,
109    T: TransactionOrdering,
110{
111    type Item = L::Item;
112
113    fn next(&mut self) -> Option<Self::Item> {
114        self.next_best().map(|(tx, _)| tx)
115    }
116}
117
118impl<L, R, T> BestTransactions for MergeBestTransactions<L, R, T>
119where
120    L: BestPriorityTransactions<T, Item: Send> + Send,
121    R: BestPriorityTransactions<T, Item = L::Item> + Send,
122    T: TransactionOrdering,
123{
124    fn mark_invalid(&mut self, transaction: &Self::Item, kind: &InvalidPoolTransactionError) {
125        self.left.mark_invalid(transaction, kind);
126        self.right.mark_invalid(transaction, kind);
127    }
128
129    fn no_updates(&mut self) {
130        self.left.no_updates();
131        self.right.no_updates();
132    }
133
134    fn set_skip_blobs(&mut self, skip_blobs: bool) {
135        self.left.set_skip_blobs(skip_blobs);
136        self.right.set_skip_blobs(skip_blobs);
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143
144    /// A simple mock iterator for testing that yields items with priorities
145    struct MockBestTransactions<T> {
146        items: Vec<(T, Priority<u128>)>,
147        index: usize,
148    }
149
150    impl<T> MockBestTransactions<T> {
151        fn new(items: Vec<(T, u128)>) -> Self {
152            let items = items
153                .into_iter()
154                .map(|(item, priority)| (item, Priority::Value(priority)))
155                .collect();
156            Self { items, index: 0 }
157        }
158    }
159
160    impl<T: Clone> Iterator for MockBestTransactions<T> {
161        type Item = T;
162
163        fn next(&mut self) -> Option<Self::Item> {
164            if self.index < self.items.len() {
165                let item = self.items[self.index].0.clone();
166                self.index += 1;
167                Some(item)
168            } else {
169                None
170            }
171        }
172    }
173
174    impl<T: Clone + Send>
175        BestPriorityTransactions<CoinbaseTipOrdering<crate::transaction::TempoPooledTransaction>>
176        for MockBestTransactions<T>
177    {
178        fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<u128>)> {
179            if self.index < self.items.len() {
180                let (item, priority) = &self.items[self.index];
181                let result = (item.clone(), priority.clone());
182                self.index += 1;
183                Some(result)
184            } else {
185                None
186            }
187        }
188    }
189
190    impl<T: Clone + Send> BestTransactions for MockBestTransactions<T> {
191        fn mark_invalid(&mut self, _transaction: &Self::Item, _kind: &InvalidPoolTransactionError) {
192            // No-op for mock
193        }
194
195        fn no_updates(&mut self) {
196            // No-op for mock
197        }
198
199        fn set_skip_blobs(&mut self, _skip_blobs: bool) {
200            // No-op for mock
201        }
202    }
203
204    #[test]
205    fn test_merge_best_transactions_basic() {
206        // Create two mock iterators with different priorities
207        // Left: priorities [10, 5, 3]
208        // Right: priorities [8, 4, 1]
209        // Expected order: [10, 8, 5, 4, 3, 1]
210        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5), ("tx_c", 3)]);
211        let right = MockBestTransactions::new(vec![("tx_d", 8), ("tx_e", 4), ("tx_f", 1)]);
212
213        let mut merged = MergeBestTransactions::new(left, right);
214
215        assert_eq!(merged.next(), Some("tx_a")); // priority 10
216        assert_eq!(merged.next(), Some("tx_d")); // priority 8
217        assert_eq!(merged.next(), Some("tx_b")); // priority 5
218        assert_eq!(merged.next(), Some("tx_e")); // priority 4
219        assert_eq!(merged.next(), Some("tx_c")); // priority 3
220        assert_eq!(merged.next(), Some("tx_f")); // priority 1
221        assert_eq!(merged.next(), None);
222    }
223
224    #[test]
225    fn test_merge_best_transactions_empty_left() {
226        // Left iterator is empty
227        let left = MockBestTransactions::new(vec![]);
228        let right = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
229
230        let mut merged = MergeBestTransactions::new(left, right);
231
232        assert_eq!(merged.next(), Some("tx_a"));
233        assert_eq!(merged.next(), Some("tx_b"));
234        assert_eq!(merged.next(), None);
235    }
236
237    #[test]
238    fn test_merge_best_transactions_empty_right() {
239        // Right iterator is empty
240        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
241        let right = MockBestTransactions::new(vec![]);
242
243        let mut merged = MergeBestTransactions::new(left, right);
244
245        assert_eq!(merged.next(), Some("tx_a"));
246        assert_eq!(merged.next(), Some("tx_b"));
247        assert_eq!(merged.next(), None);
248    }
249
250    #[test]
251    fn test_merge_best_transactions_both_empty() {
252        let left: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
253        let right: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
254
255        let mut merged = MergeBestTransactions::new(left, right);
256
257        assert_eq!(merged.next(), None);
258    }
259
260    #[test]
261    fn test_merge_best_transactions_equal_priorities() {
262        // When priorities are equal, left should be preferred (based on >= comparison)
263        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
264        let right = MockBestTransactions::new(vec![("tx_c", 10), ("tx_d", 5)]);
265
266        let mut merged = MergeBestTransactions::new(left, right);
267
268        assert_eq!(merged.next(), Some("tx_a")); // equal priority, left preferred
269        assert_eq!(merged.next(), Some("tx_c"));
270        assert_eq!(merged.next(), Some("tx_b")); // equal priority, left preferred
271        assert_eq!(merged.next(), Some("tx_d"));
272        assert_eq!(merged.next(), None);
273    }
274}
tempo_transaction_pool/best.rs

tempo_transaction_pool/
best.rs
