Skip to main content

foundry_common/
mapping_slots.rs

1use 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/// Provenance recovered for a Solidity mapping storage slot.
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub struct MappingProvenance {
14    /// The terminal mapping root slot.
15    pub root_slot: B256,
16    /// Mapping keys ordered from the root mapping to the accessed value.
17    pub keys: Vec<B256>,
18}
19
20/// Recorded mapping slots.
21#[derive(Clone, Debug, Default)]
22pub struct MappingSlots {
23    /// Holds mapping parent (slots => slots)
24    pub parent_slots: B256HashMap<B256>,
25
26    /// Holds mapping key (slots => key)
27    pub keys: B256HashMap<B256>,
28
29    /// Holds mapping child (slots => slots[])
30    pub children: B256HashMap<Vec<B256>>,
31
32    /// Holds the last sha3 result `sha3_result => (data_low, data_high)`, this would only record
33    /// when sha3 is called with `size == 0x40`, and the lower 256 bits would be stored in
34    /// `data_low`, higher 256 bits in `data_high`.
35    /// This is needed for mapping_key detect if the slot is for some mapping and record that.
36    pub seen_sha3: B256HashMap<(B256, B256)>,
37
38    /// Holds the input of each 32-byte sha3 `sha3_result => data`. A dynamic array's elements
39    /// start at the hash of its slot, so this locates arrays whose slot is itself computed, e.g.
40    /// a mapping value or an element of another array. Ordered to find the nearest hash at or
41    /// below a slot.
42    pub seen_word_sha3: BTreeMap<U256, B256>,
43}
44
45impl MappingSlots {
46    /// Records the result and two input words of a 64-byte `KECCAK256` operation.
47    pub fn record_hash(&mut self, result: B256, key: B256, parent: B256) {
48        self.seen_sha3.insert(result, (key, parent));
49    }
50
51    /// Records the result and input word of a 32-byte `KECCAK256` operation.
52    pub fn record_word_hash(&mut self, result: B256, word: B256) {
53        self.seen_word_sha3.insert(result.into(), word);
54    }
55
56    /// Resolves a computed slot to its terminal mapping root and root-to-leaf keys.
57    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(&current).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    /// Tries to insert a mapping slot. Returns true if it was inserted.
75    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/// A pending 32- or 64-byte Keccak operation captured before execution.
92#[derive(Clone, Copy, Debug)]
93pub struct PendingMappingHash {
94    /// The effective storage address of the executing frame.
95    pub address: Address,
96    /// The memory offset containing the Keccak preimage.
97    pub offset: usize,
98    /// The preimage size: 32 for a dynamic array's data slot, 64 for a mapping entry.
99    pub size: usize,
100}
101
102/// Captures a 32- or 64-byte Keccak operation before execution.
103pub 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
121/// Records a successfully executed 32- or 64-byte Keccak operation after memory expansion.
122pub 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/// Function to be used in `Inspector::step` to record mapping slots.
143#[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}