reth_transaction_pool/
identifier.rs

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

reth_transaction_pool/
identifier.rs
