foundry_common/
mapping_slots.rs1use alloy_primitives::{
2 Address, B256, U256,
3 map::{AddressHashMap, B256HashMap},
4};
5use evm2::{
6 EvmTypesHost,
7 interpreter::{Interpreter, op},
8};
9use std::collections::BTreeMap;
10
11#[derive(Clone, Debug, PartialEq, Eq)]
13pub struct MappingProvenance {
14 pub root_slot: B256,
16 pub keys: Vec<B256>,
18}
19
20#[derive(Clone, Debug, Default)]
22pub struct MappingSlots {
23 pub parent_slots: B256HashMap<B256>,
25
26 pub keys: B256HashMap<B256>,
28
29 pub children: B256HashMap<Vec<B256>>,
31
32 pub seen_sha3: B256HashMap<(B256, B256)>,
37
38 pub seen_word_sha3: BTreeMap<U256, B256>,
43}
44
45impl MappingSlots {
46 pub fn record_hash(&mut self, result: B256, key: B256, parent: B256) {
48 self.seen_sha3.insert(result, (key, parent));
49 }
50
51 pub fn record_word_hash(&mut self, result: B256, word: B256) {
53 self.seen_word_sha3.insert(result.into(), word);
54 }
55
56 pub fn resolve(&self, slot: B256) -> Option<MappingProvenance> {
58 let mut current = slot;
59 let mut keys = Vec::new();
60 while let Some((key, parent)) = self.seen_sha3.get(¤t).copied() {
61 keys.push(key);
62 current = parent;
63 if keys.len() > self.seen_sha3.len() {
64 return None;
65 }
66 }
67 if keys.is_empty() {
68 return None;
69 }
70 keys.reverse();
71 Some(MappingProvenance { root_slot: current, keys })
72 }
73
74 pub fn insert(&mut self, slot: B256) -> bool {
76 match self.seen_sha3.get(&slot).copied() {
77 Some((key, parent)) => {
78 if self.keys.insert(slot, key).is_some() {
79 return false;
80 }
81 self.parent_slots.insert(slot, parent);
82 self.children.entry(parent).or_default().push(slot);
83 self.insert(parent);
84 true
85 }
86 None => false,
87 }
88 }
89}
90
91#[derive(Clone, Copy, Debug)]
93pub struct PendingMappingHash {
94 pub address: Address,
96 pub offset: usize,
98 pub size: usize,
100}
101
102pub fn capture_hash<T: EvmTypesHost>(
104 interp: &Interpreter<'_, '_, T>,
105) -> Option<PendingMappingHash> {
106 let stack = interp.stack();
107 if interp.opcode() != op::KECCAK256 {
108 return None;
109 }
110 let size = stack.peek(1)?;
111 if size != U256::from(0x20) && size != U256::from(0x40) {
112 return None;
113 }
114 Some(PendingMappingHash {
115 address: interp.message().destination,
116 offset: stack.peek(0)?.try_into().ok()?,
117 size: size.to(),
118 })
119}
120
121pub fn record_hash<T: EvmTypesHost>(
123 mapping_slots: &mut AddressHashMap<MappingSlots>,
124 interp: &Interpreter<'_, '_, T>,
125 pending: PendingMappingHash,
126) {
127 if interp.result().is_err() {
128 return;
129 }
130 let Some(result) = interp.stack().peek(0) else { return };
131 let data = interp.memory().slice(pending.offset, pending.size);
132 let slots = mapping_slots.entry(pending.address).or_default();
133 if pending.size == 0x20 {
134 slots.record_word_hash(result.into(), B256::from_slice(data));
135 } else {
136 let key = B256::from_slice(&data[..0x20]);
137 let parent = B256::from_slice(&data[0x20..]);
138 slots.record_hash(result.into(), key, parent);
139 }
140}
141
142#[cold]
144pub fn step<T: EvmTypesHost>(
145 mapping_slots: &mut AddressHashMap<MappingSlots>,
146 interp: &Interpreter<'_, '_, T>,
147) {
148 if interp.opcode() == op::SSTORE
149 && let Some(mapping_slots) = mapping_slots.get_mut(&interp.message().destination)
150 && let Some(slot) = interp.stack().peek(0)
151 {
152 mapping_slots.insert(slot.into());
153 }
154}
155
156#[cfg(test)]
157mod tests {
158 use super::*;
159 use alloy_primitives::keccak256;
160
161 #[test]
162 fn resolves_mapping_keys_from_root_to_leaf() {
163 let root = B256::with_last_byte(1);
164 let owner = B256::with_last_byte(2);
165 let spender = B256::with_last_byte(3);
166 let inner = keccak256([owner.as_slice(), root.as_slice()].concat());
167 let slot = keccak256([spender.as_slice(), inner.as_slice()].concat());
168 let mut slots = MappingSlots::default();
169 slots.record_hash(inner, owner, root);
170 slots.record_hash(slot, spender, inner);
171
172 assert_eq!(
173 slots.resolve(slot),
174 Some(MappingProvenance { root_slot: root, keys: vec![owner, spender] })
175 );
176 }
177
178 #[test]
179 fn rejects_plain_slots_offsets_and_cycles() {
180 let root = B256::with_last_byte(1);
181 let key = B256::with_last_byte(2);
182 let slot = keccak256([key.as_slice(), root.as_slice()].concat());
183 let mut slots = MappingSlots::default();
184 slots.record_hash(slot, key, root);
185
186 assert!(slots.resolve(root).is_none());
187 assert!(slots.resolve(B256::from(Into::<U256>::into(slot) + U256::ONE)).is_none());
188
189 slots.record_hash(root, key, slot);
190 assert!(slots.resolve(slot).is_none());
191 }
192}