reth_transaction_pool/
identifier.rs

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

reth_transaction_pool/
identifier.rs
