solar_codegen/backend/evm/stack/
model.rs

1//! Stack model for tracking EVM stack state.
2//!
3//! The StackModel maps MIR ValueIds to stack positions and provides operations
4//! for manipulating the stack (DUP, SWAP, POP).
5
6use crate::mir::ValueId;
7use smallvec::SmallVec;
8
9/// Maximum stack depth accessible via DUP/SWAP (DUP16, SWAP16).
10#[allow(dead_code)]
11pub(crate) const MAX_STACK_ACCESS: usize = 16;
12
13/// Maximum total stack depth for EVM.
14#[allow(dead_code)]
15pub(crate) const MAX_STACK_DEPTH: usize = 1024;
16
17/// Represents the current state of the EVM stack.
18///
19/// Stack positions are 0-indexed from the top:
20/// - Position 0 = top of stack
21/// - Position 1 = second from top
22/// - etc.
23#[derive(Clone, Debug)]
24pub struct StackModel {
25    /// The stack, with index 0 being the top.
26    /// Each entry is either a known ValueId or None (for unknown/spilled values).
27    stack: SmallVec<[Option<ValueId>; 16]>,
28}
29
30impl StackModel {
31    /// Creates a new empty stack model.
32    #[must_use]
33    pub fn new() -> Self {
34        Self { stack: SmallVec::new() }
35    }
36
37    /// Returns the current stack depth.
38    #[must_use]
39    pub fn depth(&self) -> usize {
40        self.stack.len()
41    }
42
43    /// Returns true if the stack is empty.
44    #[must_use]
45    pub fn is_empty(&self) -> bool {
46        self.stack.is_empty()
47    }
48
49    /// Pushes a value onto the stack.
50    pub fn push(&mut self, value: ValueId) {
51        self.stack.insert(0, Some(value));
52    }
53
54    /// Pushes an unknown/anonymous value onto the stack.
55    pub fn push_unknown(&mut self) {
56        self.stack.insert(0, None);
57    }
58
59    /// Pops the top value from the stack.
60    /// Returns the value that was at the top, if known.
61    pub fn pop(&mut self) -> Option<ValueId> {
62        debug_assert!(!self.stack.is_empty(), "Stack underflow");
63        if self.stack.is_empty() { None } else { self.stack.remove(0) }
64    }
65
66    /// Returns the value at the given stack depth (0 = top).
67    #[must_use]
68    pub fn peek(&self, depth: usize) -> Option<ValueId> {
69        self.stack.get(depth).copied().flatten()
70    }
71
72    /// Returns the value at the top of the stack.
73    #[must_use]
74    pub fn top(&self) -> Option<ValueId> {
75        self.peek(0)
76    }
77
78    /// Finds the depth of a value on the stack.
79    /// Returns None if the value is not on the stack.
80    #[must_use]
81    pub fn find(&self, value: ValueId) -> Option<usize> {
82        self.stack.iter().position(|&v| v == Some(value))
83    }
84
85    /// Returns true if the value is on the stack.
86    #[must_use]
87    pub fn contains(&self, value: ValueId) -> bool {
88        self.find(value).is_some()
89    }
90
91    /// Counts how many times a value appears on the stack.
92    #[must_use]
93    pub fn count(&self, value: ValueId) -> usize {
94        self.stack.iter().filter(|&&v| v == Some(value)).count()
95    }
96
97    /// Returns true if the value is at the top of the stack.
98    #[must_use]
99    pub fn is_on_top(&self, value: ValueId) -> bool {
100        self.peek(0) == Some(value)
101    }
102
103    /// Returns true if the value is accessible via DUP (depth < 16).
104    #[must_use]
105    pub fn is_accessible(&self, value: ValueId) -> bool {
106        self.find(value).is_some_and(|d| d < MAX_STACK_ACCESS)
107    }
108
109    /// Simulates a DUP operation.
110    /// `n` is 1-indexed (DUP1 = duplicate top, DUP2 = duplicate second from top).
111    pub fn dup(&mut self, n: u8) {
112        debug_assert!((1..=16).contains(&n), "DUP depth out of range: DUP{n} (valid: 1-16)");
113        let depth = (n - 1) as usize;
114        debug_assert!(
115            depth < self.stack.len(),
116            "DUP{} attempted but stack only has {} elements",
117            n,
118            self.stack.len()
119        );
120        if let Some(&value) = self.stack.get(depth) {
121            self.stack.insert(0, value);
122        }
123    }
124
125    /// Simulates a SWAP operation.
126    /// `n` is 1-indexed (SWAP1 = swap top with second, SWAP2 = swap top with third).
127    pub fn swap(&mut self, n: u8) {
128        debug_assert!((1..=16).contains(&n), "SWAP depth out of range: SWAP{n} (valid: 1-16)");
129        let depth = n as usize;
130        debug_assert!(
131            depth < self.stack.len(),
132            "SWAP{} attempted but stack only has {} elements",
133            n,
134            self.stack.len()
135        );
136        if depth < self.stack.len() {
137            self.stack.swap(0, depth);
138        }
139    }
140
141    /// Removes a value from the stack at any position.
142    /// Used when we know a value is dead and we want to track its removal.
143    pub fn remove(&mut self, value: ValueId) -> bool {
144        if let Some(pos) = self.find(value) {
145            self.stack.remove(pos);
146            true
147        } else {
148            false
149        }
150    }
151
152    /// Clears the stack.
153    pub fn clear(&mut self) {
154        self.stack.clear();
155    }
156
157    /// Returns an iterator over all values on the stack (top to bottom).
158    pub fn iter(&self) -> impl Iterator<Item = Option<ValueId>> + '_ {
159        self.stack.iter().copied()
160    }
161
162    /// Returns the stack contents as a slice (top to bottom).
163    #[must_use]
164    pub fn as_slice(&self) -> &[Option<ValueId>] {
165        &self.stack
166    }
167}
168
169impl Default for StackModel {
170    fn default() -> Self {
171        Self::new()
172    }
173}
174
175/// Operations to emit for stack manipulation.
176#[derive(Clone, Copy, Debug, PartialEq, Eq)]
177pub enum StackOp {
178    /// DUP1-DUP16: Duplicate the nth stack element.
179    Dup(u8),
180    /// SWAP1-SWAP16: Swap top with the nth stack element.
181    Swap(u8),
182    /// POP: Remove top of stack.
183    Pop,
184}
185
186impl StackOp {
187    /// Returns the opcode byte for this operation.
188    #[must_use]
189    pub const fn opcode(self) -> u8 {
190        match self {
191            Self::Dup(n) => 0x80 + n - 1,  // DUP1 = 0x80
192            Self::Swap(n) => 0x90 + n - 1, // SWAP1 = 0x90
193            Self::Pop => 0x50,
194        }
195    }
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201
202    #[test]
203    fn test_push_pop() {
204        let mut model = StackModel::new();
205        let v0 = ValueId::from_usize(0);
206        let v1 = ValueId::from_usize(1);
207
208        model.push(v0);
209        model.push(v1);
210
211        assert_eq!(model.depth(), 2);
212        assert_eq!(model.top(), Some(v1));
213        assert_eq!(model.pop(), Some(v1));
214        assert_eq!(model.pop(), Some(v0));
215        assert!(model.is_empty());
216    }
217
218    #[test]
219    fn test_find() {
220        let mut model = StackModel::new();
221        let v0 = ValueId::from_usize(0);
222        let v1 = ValueId::from_usize(1);
223        let v2 = ValueId::from_usize(2);
224
225        model.push(v0);
226        model.push(v1);
227        model.push(v2);
228
229        assert_eq!(model.find(v2), Some(0)); // Top
230        assert_eq!(model.find(v1), Some(1));
231        assert_eq!(model.find(v0), Some(2));
232        assert_eq!(model.find(ValueId::from_usize(99)), None);
233    }
234
235    #[test]
236    fn test_dup() {
237        let mut model = StackModel::new();
238        let v0 = ValueId::from_usize(0);
239        let v1 = ValueId::from_usize(1);
240
241        model.push(v0);
242        model.push(v1);
243        // Stack: [v1, v0]
244
245        model.dup(1); // DUP1 - duplicate top
246        // Stack: [v1, v1, v0]
247
248        assert_eq!(model.depth(), 3);
249        assert_eq!(model.peek(0), Some(v1));
250        assert_eq!(model.peek(1), Some(v1));
251        assert_eq!(model.peek(2), Some(v0));
252    }
253
254    #[test]
255    fn test_swap() {
256        let mut model = StackModel::new();
257        let v0 = ValueId::from_usize(0);
258        let v1 = ValueId::from_usize(1);
259        let v2 = ValueId::from_usize(2);
260
261        model.push(v0);
262        model.push(v1);
263        model.push(v2);
264        // Stack: [v2, v1, v0]
265
266        model.swap(1); // SWAP1 - swap top with second
267        // Stack: [v1, v2, v0]
268
269        assert_eq!(model.peek(0), Some(v1));
270        assert_eq!(model.peek(1), Some(v2));
271        assert_eq!(model.peek(2), Some(v0));
272    }
273}
solar_codegen/backend/evm/stack/model.rs

solar_codegen/backend/evm/stack/
model.rs
