tempo_transaction_pool/
best.rs

1//! An iterator over the best transactions in the tempo pool.
2
3use crate::transaction::TempoPooledTransaction;
4use alloy_primitives::{Address, U256, map::HashMap};
5use reth_evm::block::TxResult;
6use reth_primitives_traits::transaction::error::InvalidTransactionError;
7use reth_transaction_pool::{
8    BestTransactions, CoinbaseTipOrdering, Priority, TransactionOrdering, ValidPoolTransaction,
9    error::InvalidPoolTransactionError,
10};
11use std::sync::Arc;
12use tempo_evm::TempoTxResult;
13use tempo_precompiles::tip20::is_tip20_prefix;
14
15/// An extension trait for [`BestTransactions`] that in addition to the transaction also yields the priority value.
16pub trait BestPriorityTransactions<T: TransactionOrdering>: BestTransactions {
17    /// Returns the next best transaction and its priority value.
18    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<T::PriorityValue>)>;
19}
20
21impl<T: TransactionOrdering> BestPriorityTransactions<T>
22    for reth_transaction_pool::pool::BestTransactions<T>
23{
24    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<T::PriorityValue>)> {
25        Self::next_tx_and_priority(self)
26    }
27}
28impl BestPriorityTransactions<CoinbaseTipOrdering<TempoPooledTransaction>>
29    for crate::tt_2d_pool::BestAA2dTransactions
30{
31    fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<u128>)> {
32        Self::next_tx_and_priority(self)
33    }
34}
35
36/// Tracks which side of a [`MergeBestTransactions`] yielded the last transaction.
37#[derive(Debug, Clone, Copy)]
38enum MergeSource {
39    Left,
40    Right,
41}
42
43/// A [`BestTransactions`] iterator that merges two individual implementations and always yields the next best item from either of the iterators.
44pub struct MergeBestTransactions<L, R, T>
45where
46    L: BestPriorityTransactions<T>,
47    R: BestPriorityTransactions<T, Item = L::Item>,
48    T: TransactionOrdering,
49{
50    left: L,
51    right: R,
52    next_left: Option<(L::Item, Priority<T::PriorityValue>)>,
53    next_right: Option<(L::Item, Priority<T::PriorityValue>)>,
54    last_source: Option<MergeSource>,
55}
56
57impl<L, R, T> MergeBestTransactions<L, R, T>
58where
59    L: BestPriorityTransactions<T>,
60    R: BestPriorityTransactions<T, Item = L::Item>,
61    T: TransactionOrdering,
62{
63    /// Creates a new iterator over the given iterators.
64    pub fn new(left: L, right: R) -> Self {
65        Self {
66            left,
67            right,
68            next_left: None,
69            next_right: None,
70            last_source: None,
71        }
72    }
73}
74
75impl<L, R, T> MergeBestTransactions<L, R, T>
76where
77    L: BestPriorityTransactions<T>,
78    R: BestPriorityTransactions<T, Item = L::Item>,
79    T: TransactionOrdering,
80{
81    /// Returns the next transaction from either the left or the right iterator with the higher priority.
82    fn next_best(&mut self) -> Option<(L::Item, Priority<T::PriorityValue>)> {
83        if self.next_left.is_none() {
84            self.next_left = self.left.next_tx_and_priority();
85        }
86        if self.next_right.is_none() {
87            self.next_right = self.right.next_tx_and_priority();
88        }
89
90        match (&mut self.next_left, &mut self.next_right) {
91            (None, None) => {
92                // both iters are done
93                None
94            }
95            // Only left has an item - take it
96            (Some(_), None) => {
97                self.last_source = Some(MergeSource::Left);
98                let (item, priority) = self.next_left.take()?;
99                Some((item, priority))
100            }
101            // Only right has an item - take it
102            (None, Some(_)) => {
103                self.last_source = Some(MergeSource::Right);
104                let (item, priority) = self.next_right.take()?;
105                Some((item, priority))
106            }
107            // Both sides have items - compare priorities and take the higher one
108            (Some((_, left_priority)), Some((_, right_priority))) => {
109                // Higher priority value is better
110                if left_priority >= right_priority {
111                    self.last_source = Some(MergeSource::Left);
112                    let (item, priority) = self.next_left.take()?;
113                    Some((item, priority))
114                } else {
115                    self.last_source = Some(MergeSource::Right);
116                    let (item, priority) = self.next_right.take()?;
117                    Some((item, priority))
118                }
119            }
120        }
121    }
122}
123
124impl<L, R, T> Iterator for MergeBestTransactions<L, R, T>
125where
126    L: BestPriorityTransactions<T>,
127    R: BestPriorityTransactions<T, Item = L::Item>,
128    T: TransactionOrdering,
129{
130    type Item = L::Item;
131
132    fn next(&mut self) -> Option<Self::Item> {
133        self.next_best().map(|(tx, _)| tx)
134    }
135}
136
137impl<L, R, T> BestTransactions for MergeBestTransactions<L, R, T>
138where
139    L: BestPriorityTransactions<T, Item: Send> + Send,
140    R: BestPriorityTransactions<T, Item = L::Item> + Send,
141    T: TransactionOrdering,
142{
143    fn mark_invalid(&mut self, transaction: &Self::Item, kind: &InvalidPoolTransactionError) {
144        match self.last_source {
145            Some(MergeSource::Left) => self.left.mark_invalid(transaction, kind),
146            Some(MergeSource::Right) => self.right.mark_invalid(transaction, kind),
147            None => {
148                self.left.mark_invalid(transaction, kind);
149                self.right.mark_invalid(transaction, kind);
150            }
151        }
152    }
153
154    fn no_updates(&mut self) {
155        self.left.no_updates();
156        self.right.no_updates();
157    }
158
159    fn set_skip_blobs(&mut self, skip_blobs: bool) {
160        self.left.set_skip_blobs(skip_blobs);
161        self.right.set_skip_blobs(skip_blobs);
162    }
163}
164
165/// A [`BestTransactions`] wrapper that tracks execution state changes and skips
166/// transactions that would fail due to state mutations from previously
167/// included transactions.
168pub struct StateAwareBestTransactions<I> {
169    inner: I,
170    /// Tracks decreased TIP20 balance slots: `(token_address, slot) -> new_balance`.
171    /// Updated after each executed transaction. Used to check if a candidate
172    /// transaction's fee payer can still cover its fee cost.
173    decreased_balances: HashMap<(Address, U256), U256>,
174}
175
176impl<I> StateAwareBestTransactions<I>
177where
178    I: BestTransactions<Item = Arc<ValidPoolTransaction<TempoPooledTransaction>>>,
179{
180    /// Wraps an existing [`BestTransactions`] iterator.
181    pub fn new(inner: I) -> Self {
182        Self {
183            inner,
184            decreased_balances: HashMap::default(),
185        }
186    }
187
188    /// Processes a new transaction execution result and collects any relevant
189    /// state changes that might affect other transactions validity.
190    pub fn on_new_result(&mut self, result: &TempoTxResult) {
191        for (&address, account) in &result.result().state {
192            if !is_tip20_prefix(address) {
193                continue;
194            }
195
196            for (&slot, storage_slot) in &account.storage {
197                if storage_slot.present_value < storage_slot.original_value {
198                    self.decreased_balances
199                        .insert((address, slot), storage_slot.present_value);
200                }
201            }
202        }
203    }
204}
205
206impl<I> Iterator for StateAwareBestTransactions<I>
207where
208    I: BestTransactions<Item = Arc<ValidPoolTransaction<TempoPooledTransaction>>>,
209{
210    type Item = Arc<ValidPoolTransaction<TempoPooledTransaction>>;
211
212    fn next(&mut self) -> Option<Self::Item> {
213        loop {
214            let tx = self.inner.next()?;
215
216            let Some(key) = tx.transaction.fee_balance_slot() else {
217                debug_assert!(false, "pool transaction must have cached fee_balance_slot");
218                continue;
219            };
220
221            if let Some(&balance) = self.decreased_balances.get(&key)
222                && balance < tx.transaction.fee_token_cost()
223            {
224                self.inner.mark_invalid(
225                    &tx,
226                    &InvalidPoolTransactionError::Consensus(
227                        InvalidTransactionError::InsufficientFunds(
228                            (balance, tx.transaction.fee_token_cost()).into(),
229                        ),
230                    ),
231                );
232                continue;
233            }
234
235            return Some(tx);
236        }
237    }
238}
239
240impl<I> BestTransactions for StateAwareBestTransactions<I>
241where
242    I: BestTransactions<Item = Arc<ValidPoolTransaction<TempoPooledTransaction>>> + Send,
243{
244    fn mark_invalid(&mut self, transaction: &Self::Item, kind: &InvalidPoolTransactionError) {
245        self.inner.mark_invalid(transaction, kind);
246    }
247
248    fn no_updates(&mut self) {
249        self.inner.no_updates();
250    }
251
252    fn set_skip_blobs(&mut self, skip_blobs: bool) {
253        self.inner.set_skip_blobs(skip_blobs);
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260    use reth_primitives_traits::transaction::error::InvalidTransactionError;
261    use std::sync::{Arc, Mutex};
262
263    /// A simple mock iterator for testing that yields items with priorities
264    struct MockBestTransactions<T> {
265        items: Vec<(T, Priority<u128>)>,
266        index: usize,
267        invalidated: Arc<Mutex<Vec<T>>>,
268    }
269
270    impl<T> MockBestTransactions<T> {
271        fn new(items: Vec<(T, u128)>) -> Self {
272            let items = items
273                .into_iter()
274                .map(|(item, priority)| (item, Priority::Value(priority)))
275                .collect();
276            Self {
277                items,
278                index: 0,
279                invalidated: Arc::new(Mutex::new(Vec::new())),
280            }
281        }
282
283        fn invalidated(&self) -> Arc<Mutex<Vec<T>>> {
284            self.invalidated.clone()
285        }
286    }
287
288    impl<T: Clone> Iterator for MockBestTransactions<T> {
289        type Item = T;
290
291        fn next(&mut self) -> Option<Self::Item> {
292            if self.index < self.items.len() {
293                let item = self.items[self.index].0.clone();
294                self.index += 1;
295                Some(item)
296            } else {
297                None
298            }
299        }
300    }
301
302    impl<T: Clone + Send>
303        BestPriorityTransactions<CoinbaseTipOrdering<crate::transaction::TempoPooledTransaction>>
304        for MockBestTransactions<T>
305    {
306        fn next_tx_and_priority(&mut self) -> Option<(Self::Item, Priority<u128>)> {
307            if self.index < self.items.len() {
308                let (item, priority) = &self.items[self.index];
309                let result = (item.clone(), priority.clone());
310                self.index += 1;
311                Some(result)
312            } else {
313                None
314            }
315        }
316    }
317
318    impl<T: Clone + Send> BestTransactions for MockBestTransactions<T> {
319        fn mark_invalid(&mut self, transaction: &Self::Item, _kind: &InvalidPoolTransactionError) {
320            self.invalidated.lock().unwrap().push(transaction.clone());
321        }
322
323        fn no_updates(&mut self) {
324            // No-op for mock
325        }
326
327        fn set_skip_blobs(&mut self, _skip_blobs: bool) {
328            // No-op for mock
329        }
330    }
331
332    #[test]
333    fn test_merge_best_transactions_basic() {
334        // Create two mock iterators with different priorities
335        // Left: priorities [10, 5, 3]
336        // Right: priorities [8, 4, 1]
337        // Expected order: [10, 8, 5, 4, 3, 1]
338        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5), ("tx_c", 3)]);
339        let right = MockBestTransactions::new(vec![("tx_d", 8), ("tx_e", 4), ("tx_f", 1)]);
340
341        let mut merged = MergeBestTransactions::new(left, right);
342
343        assert_eq!(merged.next(), Some("tx_a")); // priority 10
344        assert_eq!(merged.next(), Some("tx_d")); // priority 8
345        assert_eq!(merged.next(), Some("tx_b")); // priority 5
346        assert_eq!(merged.next(), Some("tx_e")); // priority 4
347        assert_eq!(merged.next(), Some("tx_c")); // priority 3
348        assert_eq!(merged.next(), Some("tx_f")); // priority 1
349        assert_eq!(merged.next(), None);
350    }
351
352    #[test]
353    fn test_merge_best_transactions_empty_left() {
354        // Left iterator is empty
355        let left = MockBestTransactions::new(vec![]);
356        let right = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
357
358        let mut merged = MergeBestTransactions::new(left, right);
359
360        assert_eq!(merged.next(), Some("tx_a"));
361        assert_eq!(merged.next(), Some("tx_b"));
362        assert_eq!(merged.next(), None);
363    }
364
365    #[test]
366    fn test_merge_best_transactions_empty_right() {
367        // Right iterator is empty
368        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
369        let right = MockBestTransactions::new(vec![]);
370
371        let mut merged = MergeBestTransactions::new(left, right);
372
373        assert_eq!(merged.next(), Some("tx_a"));
374        assert_eq!(merged.next(), Some("tx_b"));
375        assert_eq!(merged.next(), None);
376    }
377
378    #[test]
379    fn test_merge_best_transactions_both_empty() {
380        let left: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
381        let right: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
382
383        let mut merged = MergeBestTransactions::new(left, right);
384
385        assert_eq!(merged.next(), None);
386    }
387
388    #[test]
389    fn test_merge_best_transactions_equal_priorities() {
390        // When priorities are equal, left should be preferred (based on >= comparison)
391        let left = MockBestTransactions::new(vec![("tx_a", 10), ("tx_b", 5)]);
392        let right = MockBestTransactions::new(vec![("tx_c", 10), ("tx_d", 5)]);
393
394        let mut merged = MergeBestTransactions::new(left, right);
395
396        assert_eq!(merged.next(), Some("tx_a")); // equal priority, left preferred
397        assert_eq!(merged.next(), Some("tx_c"));
398        assert_eq!(merged.next(), Some("tx_b")); // equal priority, left preferred
399        assert_eq!(merged.next(), Some("tx_d"));
400        assert_eq!(merged.next(), None);
401    }
402
403    // ============================================
404    // Single item tests
405    // ============================================
406
407    #[test]
408    fn test_merge_best_transactions_single_left() {
409        let left = MockBestTransactions::new(vec![("tx_a", 10)]);
410        let right: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
411
412        let mut merged = MergeBestTransactions::new(left, right);
413
414        assert_eq!(merged.next(), Some("tx_a"));
415        assert_eq!(merged.next(), None);
416    }
417
418    #[test]
419    fn test_merge_best_transactions_single_right() {
420        let left: MockBestTransactions<&str> = MockBestTransactions::new(vec![]);
421        let right = MockBestTransactions::new(vec![("tx_a", 10)]);
422
423        let mut merged = MergeBestTransactions::new(left, right);
424
425        assert_eq!(merged.next(), Some("tx_a"));
426        assert_eq!(merged.next(), None);
427    }
428
429    // ============================================
430    // Interleaved priority tests
431    // ============================================
432
433    #[test]
434    fn test_merge_best_transactions_interleaved() {
435        // Left has higher odd positions, right has higher even positions
436        let left = MockBestTransactions::new(vec![("L1", 9), ("L2", 7), ("L3", 5)]);
437        let right = MockBestTransactions::new(vec![("R1", 10), ("R2", 6), ("R3", 4)]);
438
439        let mut merged = MergeBestTransactions::new(left, right);
440
441        assert_eq!(merged.next(), Some("R1")); // 10
442        assert_eq!(merged.next(), Some("L1")); // 9
443        assert_eq!(merged.next(), Some("L2")); // 7
444        assert_eq!(merged.next(), Some("R2")); // 6
445        assert_eq!(merged.next(), Some("L3")); // 5
446        assert_eq!(merged.next(), Some("R3")); // 4
447        assert_eq!(merged.next(), None);
448    }
449
450    #[test]
451    fn test_mark_invalid_only_forwards_to_source_pool() {
452        // Invalidating a right-side (AA-2D) tx must NOT propagate to the
453        // left-side (protocol) pool.
454        let left = MockBestTransactions::new(vec![("L1", 5), ("L2", 3)]);
455        let right = MockBestTransactions::new(vec![("R1", 10)]);
456
457        let left_invalidated = left.invalidated();
458        let right_invalidated = right.invalidated();
459
460        let mut merged = MergeBestTransactions::new(left, right);
461
462        // Right has highest priority, so R1 is yielded first
463        let first = merged.next().unwrap();
464        assert_eq!(first, "R1");
465
466        // Simulate payload builder marking R1 as invalid
467        let kind =
468            InvalidPoolTransactionError::Consensus(InvalidTransactionError::TxTypeNotSupported);
469        merged.mark_invalid(&first, &kind);
470
471        // Only the right (source) pool should have received the invalidation
472        assert!(
473            left_invalidated.lock().unwrap().is_empty(),
474            "left pool must NOT be invalidated when a right-side tx fails"
475        );
476        assert_eq!(
477            *right_invalidated.lock().unwrap(),
478            vec!["R1"],
479            "right pool must receive the invalidation"
480        );
481
482        // Remaining left-side txs must still be yielded
483        assert_eq!(merged.next(), Some("L1"));
484        assert_eq!(merged.next(), Some("L2"));
485        assert_eq!(merged.next(), None);
486    }
487}
tempo_transaction_pool/best.rs

tempo_transaction_pool/
best.rs
