reth_transaction_pool/
identifier.rs

1//! Identifier types for transactions and senders.
2use alloy_primitives::{map::HashMap, Address};
3use rustc_hash::FxHashMap;
4
5/// An internal mapping of addresses.
6///
7/// This assigns a _unique_ [`SenderId`] for a new [`Address`].
8/// It has capacity for 2^64 unique addresses.
9#[derive(Debug, Default)]
10pub struct SenderIdentifiers {
11    /// The identifier to use next.
12    id: u64,
13    /// Assigned [`SenderId`] for an [`Address`].
14    address_to_id: HashMap<Address, SenderId>,
15    /// Reverse mapping of [`SenderId`] to [`Address`].
16    sender_to_address: FxHashMap<SenderId, Address>,
17}
18
19impl SenderIdentifiers {
20    /// Returns the address for the given identifier.
21    pub fn address(&self, id: &SenderId) -> Option<&Address> {
22        self.sender_to_address.get(id)
23    }
24
25    /// Returns the [`SenderId`] that belongs to the given address, if it exists
26    pub fn sender_id(&self, addr: &Address) -> Option<SenderId> {
27        self.address_to_id.get(addr).copied()
28    }
29
30    /// Returns the existing [`SenderId`] or assigns a new one if it's missing
31    pub fn sender_id_or_create(&mut self, addr: Address) -> SenderId {
32        self.sender_id(&addr).unwrap_or_else(|| {
33            let id = self.next_id();
34            self.address_to_id.insert(addr, id);
35            self.sender_to_address.insert(id, addr);
36            id
37        })
38    }
39
40    /// Returns the existing [`SenderId`] or assigns a new one if it's missing
41    pub fn sender_ids_or_create(
42        &mut self,
43        addrs: impl IntoIterator<Item = Address>,
44    ) -> Vec<SenderId> {
45        addrs.into_iter().map(|addr| self.sender_id_or_create(addr)).collect()
46    }
47
48    /// Returns the current identifier and increments the counter.
49    fn next_id(&mut self) -> SenderId {
50        let id = self.id;
51        self.id = self.id.wrapping_add(1);
52        id.into()
53    }
54}
55
56/// A _unique_ identifier for a sender of an address.
57///
58/// This is the identifier of an internal `address` mapping that is valid in the context of this
59/// program.
60#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
61pub struct SenderId(u64);
62
63impl SenderId {
64    /// Returns a `Bound` for [`TransactionId`] starting with nonce `0`
65    pub const fn start_bound(self) -> std::ops::Bound<TransactionId> {
66        std::ops::Bound::Included(TransactionId::new(self, 0))
67    }
68
69    /// Converts the sender to a [`TransactionId`] with the given nonce.
70    pub const fn into_transaction_id(self, nonce: u64) -> TransactionId {
71        TransactionId::new(self, nonce)
72    }
73}
74
75impl From<u64> for SenderId {
76    fn from(value: u64) -> Self {
77        Self(value)
78    }
79}
80
81/// A unique identifier of a transaction of a Sender.
82///
83/// This serves as an identifier for dependencies of a transaction:
84/// A transaction with a nonce higher than the current state nonce depends on `tx.nonce - 1`.
85#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
86pub struct TransactionId {
87    /// Sender of this transaction
88    pub sender: SenderId,
89    /// Nonce of this transaction
90    pub nonce: u64,
91}
92
93impl TransactionId {
94    /// Create a new identifier pair
95    pub const fn new(sender: SenderId, nonce: u64) -> Self {
96        Self { sender, nonce }
97    }
98
99    /// Returns the [`TransactionId`] this transaction depends on.
100    ///
101    /// This returns `transaction_nonce - 1` if `transaction_nonce` is higher than the
102    /// `on_chain_nonce`
103    pub fn ancestor(transaction_nonce: u64, on_chain_nonce: u64, sender: SenderId) -> Option<Self> {
104        // SAFETY: transaction_nonce > on_chain_nonce ⇒ transaction_nonce >= 1
105        (transaction_nonce > on_chain_nonce).then(|| Self::new(sender, transaction_nonce - 1))
106    }
107
108    /// Returns the [`TransactionId`] that would come before this transaction.
109    pub fn unchecked_ancestor(&self) -> Option<Self> {
110        // SAFETY: self.nonce != 0 ⇒ self.nonce >= 1
111        (self.nonce != 0).then(|| Self::new(self.sender, self.nonce - 1))
112    }
113
114    /// Returns the [`TransactionId`] that directly follows this transaction: `self.nonce + 1`
115    pub const fn descendant(&self) -> Self {
116        Self::new(self.sender, self.next_nonce())
117    }
118
119    /// Returns the nonce that follows immediately after this one.
120    #[inline]
121    pub const fn next_nonce(&self) -> u64 {
122        self.nonce + 1
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129    use std::collections::BTreeSet;
130
131    #[test]
132    fn test_transaction_id_new() {
133        let sender = SenderId(1);
134        let tx_id = TransactionId::new(sender, 5);
135        assert_eq!(tx_id.sender, sender);
136        assert_eq!(tx_id.nonce, 5);
137    }
138
139    #[test]
140    fn test_transaction_id_ancestor() {
141        let sender = SenderId(1);
142
143        // Special case with nonce 0 and higher on-chain nonce
144        let tx_id = TransactionId::ancestor(0, 1, sender);
145        assert_eq!(tx_id, None);
146
147        // Special case with nonce 0 and same on-chain nonce
148        let tx_id = TransactionId::ancestor(0, 0, sender);
149        assert_eq!(tx_id, None);
150
151        // Ancestor is the previous nonce if the transaction nonce is higher than the on-chain nonce
152        let tx_id = TransactionId::ancestor(5, 0, sender);
153        assert_eq!(tx_id, Some(TransactionId::new(sender, 4)));
154
155        // No ancestor if the transaction nonce is the same as the on-chain nonce
156        let tx_id = TransactionId::ancestor(5, 5, sender);
157        assert_eq!(tx_id, None);
158
159        // No ancestor if the transaction nonce is lower than the on-chain nonce
160        let tx_id = TransactionId::ancestor(5, 15, sender);
161        assert_eq!(tx_id, None);
162    }
163
164    #[test]
165    fn test_transaction_id_unchecked_ancestor() {
166        let sender = SenderId(1);
167
168        // Ancestor is the previous nonce if transaction nonce is higher than 0
169        let tx_id = TransactionId::new(sender, 5);
170        assert_eq!(tx_id.unchecked_ancestor(), Some(TransactionId::new(sender, 4)));
171
172        // No ancestor if transaction nonce is 0
173        let tx_id = TransactionId::new(sender, 0);
174        assert_eq!(tx_id.unchecked_ancestor(), None);
175    }
176
177    #[test]
178    fn test_transaction_id_descendant() {
179        let sender = SenderId(1);
180        let tx_id = TransactionId::new(sender, 5);
181        let descendant = tx_id.descendant();
182        assert_eq!(descendant, TransactionId::new(sender, 6));
183    }
184
185    #[test]
186    fn test_transaction_id_next_nonce() {
187        let sender = SenderId(1);
188        let tx_id = TransactionId::new(sender, 5);
189        assert_eq!(tx_id.next_nonce(), 6);
190    }
191
192    #[test]
193    fn test_transaction_id_ord_eq_sender() {
194        let tx1 = TransactionId::new(100u64.into(), 0u64);
195        let tx2 = TransactionId::new(100u64.into(), 1u64);
196        assert!(tx2 > tx1);
197        let set = BTreeSet::from([tx1, tx2]);
198        assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![tx1, tx2]);
199    }
200
201    #[test]
202    fn test_transaction_id_ord() {
203        let tx1 = TransactionId::new(99u64.into(), 0u64);
204        let tx2 = TransactionId::new(100u64.into(), 1u64);
205        assert!(tx2 > tx1);
206        let set = BTreeSet::from([tx1, tx2]);
207        assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![tx1, tx2]);
208    }
209
210    #[test]
211    fn test_address_retrieval() {
212        let mut identifiers = SenderIdentifiers::default();
213        let address = Address::new([1; 20]);
214        let id = identifiers.sender_id_or_create(address);
215        assert_eq!(identifiers.address(&id), Some(&address));
216    }
217
218    #[test]
219    fn test_sender_id_retrieval() {
220        let mut identifiers = SenderIdentifiers::default();
221        let address = Address::new([1; 20]);
222        let id = identifiers.sender_id_or_create(address);
223        assert_eq!(identifiers.sender_id(&address), Some(id));
224    }
225
226    #[test]
227    fn test_sender_id_or_create_existing() {
228        let mut identifiers = SenderIdentifiers::default();
229        let address = Address::new([1; 20]);
230        let id1 = identifiers.sender_id_or_create(address);
231        let id2 = identifiers.sender_id_or_create(address);
232        assert_eq!(id1, id2);
233    }
234
235    #[test]
236    fn test_sender_id_or_create_new() {
237        let mut identifiers = SenderIdentifiers::default();
238        let address1 = Address::new([1; 20]);
239        let address2 = Address::new([2; 20]);
240        let id1 = identifiers.sender_id_or_create(address1);
241        let id2 = identifiers.sender_id_or_create(address2);
242        assert_ne!(id1, id2);
243    }
244
245    #[test]
246    fn test_next_id_wrapping() {
247        let mut identifiers = SenderIdentifiers { id: u64::MAX, ..Default::default() };
248
249        // The current ID is `u64::MAX`, the next ID should wrap around to 0.
250        let id1 = identifiers.next_id();
251        assert_eq!(id1, SenderId(u64::MAX));
252
253        // The next ID should now be 0 because of wrapping.
254        let id2 = identifiers.next_id();
255        assert_eq!(id2, SenderId(0));
256
257        // And then 1, continuing incrementing.
258        let id3 = identifiers.next_id();
259        assert_eq!(id3, SenderId(1));
260    }
261
262    #[test]
263    fn test_sender_id_start_bound() {
264        let sender = SenderId(1);
265        let start_bound = sender.start_bound();
266        if let std::ops::Bound::Included(tx_id) = start_bound {
267            assert_eq!(tx_id, TransactionId::new(sender, 0));
268        } else {
269            panic!("Expected included bound");
270        }
271    }
272}