edb_engine/analysis/
step.rs

1// EDB - Ethereum Debugger
2// Copyright (C) 2024 Zhuo Zhang and Wuqi Zhang
3//
4// This program is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Affero General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// This program is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Affero General Public License for more details.
13//
14// You should have received a copy of the GNU Affero General Public License
15// along with this program. If not, see <https://www.gnu.org/licenses/>.
16
17use std::{
18    // collections::BTreeMap,
19    sync::Arc,
20};
21
22// use derive_more::{Deref, DerefMut};
23use delegate::delegate;
24use foundry_compilers::artifacts::{
25    ast::SourceLocation,
26    BlockOrStatement,
27    DoWhileStatement,
28    Expression,
29    ForStatement,
30    FunctionCall,
31    FunctionDefinition,
32    IfStatement,
33    ModifierDefinition,
34    Statement,
35    TryStatement,
36    WhileStatement, // SourceUnit,
37};
38use once_cell::sync::OnceCell;
39use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
40use serde::{Deserialize, Serialize};
41
42use crate::analysis::{macros::universal_id, VariableRef, VariableScopeRef, UFID};
43
44universal_id! {
45    /// A Universal Step Identifier (USID) is a unique identifier for a step in contract execution.
46    USID => 0
47}
48
49/// A reference-counted pointer to a Step for efficient sharing across multiple contexts.
50///
51/// This type alias provides thread-safe reference counting for Step instances,
52/// allowing them to be shared between different parts of the analysis system
53/// without copying the entire step data.
54#[derive(Debug, Clone)]
55pub struct StepRef {
56    inner: Arc<RwLock<Step>>,
57    /* cached readonly fields*/
58    usid: OnceCell<USID>,
59    ufid: OnceCell<UFID>,
60    variant: OnceCell<StepVariant>,
61    function_calls: OnceCell<usize>,
62}
63
64impl From<Step> for StepRef {
65    fn from(step: Step) -> Self {
66        Self::new(step)
67    }
68}
69
70impl Serialize for StepRef {
71    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
72    where
73        S: serde::Serializer,
74    {
75        // Serialize the inner Step directly
76        self.inner.read().serialize(serializer)
77    }
78}
79
80impl<'de> Deserialize<'de> for StepRef {
81    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
82    where
83        D: serde::Deserializer<'de>,
84    {
85        // Deserialize as Step and wrap it in StepRef
86        let step = Step::deserialize(deserializer)?;
87        Ok(Self::new(step))
88    }
89}
90
91impl StepRef {
92    /// Creates a new StepRef from a Step.
93    pub fn new(inner: Step) -> Self {
94        Self {
95            inner: Arc::new(RwLock::new(inner)),
96            usid: OnceCell::new(),
97            ufid: OnceCell::new(),
98            variant: OnceCell::new(),
99            function_calls: OnceCell::new(),
100        }
101    }
102
103    pub(crate) fn read(&self) -> RwLockReadGuard<'_, Step> {
104        self.inner.read()
105    }
106
107    pub(crate) fn write(&self) -> RwLockWriteGuard<'_, Step> {
108        self.inner.write()
109    }
110
111    /// Returns the USID of this step.
112    pub fn usid(&self) -> USID {
113        *self.usid.get_or_init(|| self.inner.read().usid)
114    }
115
116    /// Returns the UFID of this step.
117    pub fn ufid(&self) -> UFID {
118        *self.ufid.get_or_init(|| self.inner.read().ufid)
119    }
120
121    /// Returns the variant of this step.
122    pub fn variant(&self) -> &StepVariant {
123        self.variant.get_or_init(|| self.inner.read().variant.clone())
124    }
125
126    /// Returns the number of function calls made in this step.
127    pub fn function_calls(&self) -> usize {
128        // XXX (ZZ): a relatively hacky way to handle corner cases
129        let calls = &self.inner.read().function_calls;
130        let mut function_calls = calls.len();
131
132        // Corner case 1: emit statement(s)
133        // In EmitStatement, an event is also considered as a function call, for which
134        // we need to reduce the count by 1.
135        match self.variant() {
136            StepVariant::Statement(Statement::EmitStatement { .. }) => {
137                function_calls = function_calls.saturating_sub(1);
138            }
139            StepVariant::Statements(ref stmts) => {
140                let emit_n = stmts
141                    .iter()
142                    .filter(|stmt| matches!(stmt, Statement::EmitStatement { .. }))
143                    .count();
144                function_calls = function_calls.saturating_sub(emit_n);
145            }
146            _ => {}
147        }
148
149        // Corner case 2: built-in statements
150        static BUILT_IN_FUNCTIONS: &[&str] =
151            &["require", "assert", "keccak256", "sha256", "ripemd160", "ecrecover", "type"];
152        let built_in_n = calls
153            .iter()
154            .filter(|call| {
155                if let Expression::Identifier(ref id) = call.expression {
156                    BUILT_IN_FUNCTIONS.contains(&id.name.as_str())
157                } else {
158                    false
159                }
160            })
161            .count();
162        function_calls = function_calls.saturating_sub(built_in_n);
163
164        *self.function_calls.get_or_init(|| function_calls)
165    }
166
167    /// Check whether this step is an entry of a function
168    pub fn function_entry(&self) -> Option<UFID> {
169        if let StepVariant::FunctionEntry(_) = self.variant() {
170            Some(self.read().ufid)
171        } else {
172            None
173        }
174    }
175
176    /// Check whether this step is an entry of a modifier
177    pub fn modifier_entry(&self) -> Option<UFID> {
178        if let StepVariant::ModifierEntry(_) = self.variant() {
179            Some(self.read().ufid)
180        } else {
181            None
182        }
183    }
184
185    /// Check whether this step contains return statements
186    pub fn contains_return(&self) -> bool {
187        match self.variant() {
188            StepVariant::Statement(Statement::Return(..)) => true,
189            StepVariant::Statements(stmts) => {
190                stmts.iter().any(|s| matches!(s, Statement::Return(..)))
191            }
192            // Other variants will do tag a return as a single step
193            _ => false,
194        }
195    }
196}
197
198impl StepRef {
199    delegate! {
200        to self.inner.read() {
201        }
202    }
203}
204
205/// Represents a single executable step in Solidity source code.
206///
207/// A Step represents a unit of execution that can be debugged, such as a statement,
208/// expression, or control flow construct. Each step contains information about
209/// its location in the source code and any hooks that should be executed before
210/// or after the step.
211///
212/// # Fields
213///
214/// - `usid`: Unique step identifier for this execution step
215/// - `variant`: The specific type of step (statement, expression, etc.)
216/// - `src`: Source location information (file, line, column)
217/// - `pre_hooks`: Hooks to execute before this step
218/// - `post_hooks`: Hooks to execute after this step
219#[derive(Debug, Clone, Serialize, Deserialize)]
220pub struct Step {
221    /// Unique step identifier for this execution step
222    pub usid: USID,
223    /// The identifier of the function that this step belongs to.
224    pub ufid: UFID,
225    /// The specific type of step (statement, expression, etc.)
226    pub variant: StepVariant,
227    /// Source location information (file, line, column)
228    pub src: SourceLocation,
229    /// Function calls made in this step
230    pub function_calls: Vec<FunctionCall>,
231    /// Variables accessible in this step (excluding those declared in this step)
232    pub accessible_variables: Vec<VariableRef>,
233    /// Variables declared in this step
234    pub declared_variables: Vec<VariableRef>,
235    /// Variables updated in this step
236    pub updated_variables: Vec<VariableRef>,
237    /// The scope of this step
238    pub scope: VariableScopeRef,
239}
240
241impl Step {
242    /// Creates a new Step with the given variant and source location.
243    ///
244    /// # Arguments
245    ///
246    /// * `variant` - The type of step (statement, expression, etc.)
247    /// * `src` - Source location information
248    ///
249    /// # Returns
250    ///
251    /// A new Step instance with a unique USID and default hooks.
252    pub fn new(
253        ufid: UFID,
254        variant: StepVariant,
255        src: SourceLocation,
256        scope: VariableScopeRef,
257        accessible_variables: Vec<VariableRef>,
258    ) -> Self {
259        let usid = USID::next();
260        Self {
261            usid,
262            ufid,
263            variant,
264            src,
265            function_calls: vec![],
266            accessible_variables,
267            declared_variables: vec![],
268            updated_variables: vec![],
269            scope,
270        }
271    }
272}
273
274/// The variant types for source steps.
275#[derive(Debug, Clone, Serialize, Deserialize)]
276#[allow(clippy::large_enum_variant)]
277pub enum StepVariant {
278    /// A function entry step.
279    FunctionEntry(FunctionDefinition),
280    /// A modifier entry step.
281    ModifierEntry(ModifierDefinition),
282    /// A single statement that is executed in a single debug step.
283    Statement(Statement),
284    /// A consecutive list of statements that are executed in a single debug step.
285    Statements(Vec<Statement>),
286    /// The condition of an if statement that is executed in a single debug step.
287    IfCondition(IfStatement),
288    /// The header of a for loop that is executed in a single debug step.
289    ForLoop(ForStatement),
290    /// The condition of a while loop that is executed in a single debug step.
291    WhileLoop(WhileStatement),
292    /// The header of a do-while loop that is executed in a single debug step.
293    DoWhileLoop(DoWhileStatement),
294    /// The try external call
295    Try(TryStatement),
296}
297
298/// Computes the left difference of `a` and `b` (`a \ b`).
299/// It takes the [SourceLocation] within `a` that is not in `b` and smaller than `b`.
300pub fn sloc_ldiff(a: SourceLocation, b: SourceLocation) -> SourceLocation {
301    assert_eq!(a.index, b.index, "The index of `a` and `b` must be the same");
302    let length = b.start.zip(a.start).map(|(end, start)| end.saturating_sub(start));
303    SourceLocation { start: a.start, length, index: a.index }
304}
305
306/// Computes the right difference of `a` and `b` (`a \ b`).
307/// It takes the [SourceLocation] within `a` that is not in `b` and larger than `b`.
308pub fn sloc_rdiff(a: SourceLocation, b: SourceLocation) -> SourceLocation {
309    assert_eq!(a.index, b.index, "The index of `a` and `b` must be the same");
310    let start = b.start.zip(b.length).map(|(start, length)| start + length);
311    let length = a
312        .start
313        .zip(a.length)
314        .map(|(start, length)| start + length)
315        .zip(start)
316        .map(|(end, start)| end.saturating_sub(start));
317    SourceLocation { start, length, index: a.index }
318}
319
320/// Returns the source location of [Statement].
321pub fn stmt_src(stmt: &Statement) -> SourceLocation {
322    match stmt {
323        Statement::Block(block) => block.src,
324        Statement::ExpressionStatement(expression_statement) => expression_statement.src,
325        Statement::Break(break_stmt) => break_stmt.src,
326        Statement::Continue(continue_stmt) => continue_stmt.src,
327        Statement::DoWhileStatement(do_while_statement) => do_while_statement.src,
328        Statement::EmitStatement(emit_statement) => emit_statement.src,
329        Statement::ForStatement(for_statement) => for_statement.src,
330        Statement::IfStatement(if_statement) => if_statement.src,
331        Statement::InlineAssembly(inline_assembly) => inline_assembly.src,
332        Statement::PlaceholderStatement(placeholder_statement) => placeholder_statement.src,
333        Statement::Return(return_stmt) => return_stmt.src,
334        Statement::RevertStatement(revert_statement) => revert_statement.src,
335        Statement::TryStatement(try_statement) => try_statement.src,
336        Statement::UncheckedBlock(unchecked_block) => unchecked_block.src,
337        Statement::VariableDeclarationStatement(variable_declaration_statement) => {
338            variable_declaration_statement.src
339        }
340        Statement::WhileStatement(while_statement) => while_statement.src,
341    }
342}
343
344/// Returns the source location of [BlockOrStatement].
345pub fn block_or_stmt_src(block_or_stmt: &BlockOrStatement) -> SourceLocation {
346    match block_or_stmt {
347        BlockOrStatement::Block(block) => block.src,
348        BlockOrStatement::Statement(statement) => stmt_src(statement),
349    }
350}
351
352#[cfg(test)]
353mod tests {
354    use super::*;
355
356    macro_rules! sloc {
357        ($start:expr, $length:expr, $index:expr) => {
358            SourceLocation { start: Some($start), length: Some($length), index: Some($index) }
359        };
360    }
361
362    #[test]
363    fn test_sloc_ldiff() {
364        let a = sloc!(0, 10, 0);
365        let b = sloc!(5, 5, 0);
366        let c = sloc_ldiff(a, b);
367        assert_eq!(c, sloc!(0, 5, 0));
368
369        let a = sloc!(0, 10, 0);
370        let b = sloc!(0, 10, 0);
371        let c = sloc_ldiff(a, b);
372        assert_eq!(c, sloc!(0, 0, 0));
373
374        let a = sloc!(0, 10, 0);
375        let b = sloc!(10, 10, 0);
376        let c = sloc_ldiff(a, b);
377        assert_eq!(c, sloc!(0, 10, 0));
378
379        let a = sloc!(5, 5, 0);
380        let b = sloc!(0, 10, 0);
381        let c = sloc_ldiff(a, b);
382        assert_eq!(c, sloc!(5, 0, 0));
383    }
384
385    #[test]
386    fn test_sloc_rdiff() {
387        let a = sloc!(0, 10, 0);
388        let b = sloc!(5, 5, 0);
389        let c = sloc_rdiff(a, b);
390        assert_eq!(c, sloc!(10, 0, 0));
391
392        let a = sloc!(0, 10, 0);
393        let b = sloc!(0, 10, 0);
394        let c = sloc_rdiff(a, b);
395        assert_eq!(c, sloc!(10, 0, 0));
396
397        let a = sloc!(0, 10, 0);
398        let b = sloc!(0, 5, 0);
399        let c = sloc_rdiff(a, b);
400        assert_eq!(c, sloc!(5, 5, 0));
401
402        let a = sloc!(5, 5, 0);
403        let b = sloc!(0, 10, 0);
404        let c = sloc_rdiff(a, b);
405        assert_eq!(c, sloc!(10, 0, 0));
406    }
407}
edb_engine/analysis/step.rs

edb_engine/analysis/
step.rs
