foundry_evm_coverage/
analysis.rs

Help
1use super::{CoverageItem, CoverageItemKind, SourceLocation};
2use alloy_primitives::map::HashMap;
3use foundry_common::TestFunctionExt;
4use foundry_compilers::artifacts::{
5    ast::{self, Ast, Node, NodeType},
6    Source,
7};
8use rayon::prelude::*;
9use std::sync::Arc;
10
11/// A visitor that walks the AST of a single contract and finds coverage items.
12#[derive(Clone, Debug)]
13pub struct ContractVisitor<'a> {
14    /// The source ID of the contract.
15    source_id: u32,
16    /// The source code that contains the AST being walked.
17    source: &'a str,
18
19    /// The name of the contract being walked.
20    contract_name: &'a Arc<str>,
21
22    /// The current branch ID
23    branch_id: u32,
24    /// Stores the last line we put in the items collection to ensure we don't push duplicate lines
25    last_line: u32,
26
27    /// Coverage items
28    pub items: Vec<CoverageItem>,
29}
30
31impl<'a> ContractVisitor<'a> {
32    pub fn new(source_id: usize, source: &'a str, contract_name: &'a Arc<str>) -> Self {
33        Self {
34            source_id: source_id.try_into().expect("too many sources"),
35            source,
36            contract_name,
37            branch_id: 0,
38            last_line: 0,
39            items: Vec::new(),
40        }
41    }
42
43    pub fn visit_contract(&mut self, node: &Node) -> eyre::Result<()> {
44        // Find all functions and walk their AST
45        for node in &node.nodes {
46            match node.node_type {
47                NodeType::FunctionDefinition => {
48                    self.visit_function_definition(node)?;
49                }
50                NodeType::ModifierDefinition => {
51                    self.visit_modifier_or_yul_fn_definition(node)?;
52                }
53                _ => {}
54            }
55        }
56        Ok(())
57    }
58
59    fn visit_function_definition(&mut self, node: &Node) -> eyre::Result<()> {
60        let Some(body) = &node.body else { return Ok(()) };
61
62        let name: String =
63            node.attribute("name").ok_or_else(|| eyre::eyre!("Function has no name"))?;
64        let kind: String =
65            node.attribute("kind").ok_or_else(|| eyre::eyre!("Function has no kind"))?;
66
67        // TODO: We currently can only detect empty bodies in normal functions, not any of the other
68        // kinds: https://github.com/foundry-rs/foundry/issues/9458
69        if kind != "function" && !has_statements(body) {
70            return Ok(());
71        }
72
73        // `fallback`, `receive`, and `constructor` functions have an empty `name`.
74        // Use the `kind` itself as the name.
75        let name = if name.is_empty() { kind } else { name };
76
77        self.push_item_kind(CoverageItemKind::Function { name }, &node.src);
78        self.visit_block(body)
79    }
80
81    fn visit_modifier_or_yul_fn_definition(&mut self, node: &Node) -> eyre::Result<()> {
82        let name: String =
83            node.attribute("name").ok_or_else(|| eyre::eyre!("Modifier has no name"))?;
84
85        match &node.body {
86            Some(body) => {
87                self.push_item_kind(CoverageItemKind::Function { name }, &node.src);
88                self.visit_block(body)
89            }
90            _ => Ok(()),
91        }
92    }
93
94    fn visit_block(&mut self, node: &Node) -> eyre::Result<()> {
95        let statements: Vec<Node> = node.attribute("statements").unwrap_or_default();
96
97        for statement in &statements {
98            self.visit_statement(statement)?;
99        }
100
101        Ok(())
102    }
103
104    fn visit_statement(&mut self, node: &Node) -> eyre::Result<()> {
105        match node.node_type {
106            // Blocks
107            NodeType::Block | NodeType::UncheckedBlock | NodeType::YulBlock => {
108                self.visit_block(node)
109            }
110            // Inline assembly block
111            NodeType::InlineAssembly => self.visit_block(
112                &node
113                    .attribute("AST")
114                    .ok_or_else(|| eyre::eyre!("inline assembly block with no AST attribute"))?,
115            ),
116            // Simple statements
117            NodeType::Break |
118            NodeType::Continue |
119            NodeType::EmitStatement |
120            NodeType::RevertStatement |
121            NodeType::YulAssignment |
122            NodeType::YulBreak |
123            NodeType::YulContinue |
124            NodeType::YulLeave |
125            NodeType::YulVariableDeclaration => {
126                self.push_item_kind(CoverageItemKind::Statement, &node.src);
127                Ok(())
128            }
129            // Skip placeholder statements as they are never referenced in source maps.
130            NodeType::PlaceholderStatement => Ok(()),
131            // Return with eventual subcall
132            NodeType::Return => {
133                self.push_item_kind(CoverageItemKind::Statement, &node.src);
134                if let Some(expr) = node.attribute("expression") {
135                    self.visit_expression(&expr)?;
136                }
137                Ok(())
138            }
139            // Variable declaration
140            NodeType::VariableDeclarationStatement => {
141                self.push_item_kind(CoverageItemKind::Statement, &node.src);
142                if let Some(expr) = node.attribute("initialValue") {
143                    self.visit_expression(&expr)?;
144                }
145                Ok(())
146            }
147            // While loops
148            NodeType::DoWhileStatement | NodeType::WhileStatement => {
149                self.visit_expression(
150                    &node
151                        .attribute("condition")
152                        .ok_or_else(|| eyre::eyre!("while statement had no condition"))?,
153                )?;
154
155                let body = node
156                    .body
157                    .as_deref()
158                    .ok_or_else(|| eyre::eyre!("while statement had no body node"))?;
159                self.visit_block_or_statement(body)
160            }
161            // For loops
162            NodeType::ForStatement => {
163                if let Some(stmt) = node.attribute("initializationExpression") {
164                    self.visit_statement(&stmt)?;
165                }
166                if let Some(expr) = node.attribute("condition") {
167                    self.visit_expression(&expr)?;
168                }
169                if let Some(stmt) = node.attribute("loopExpression") {
170                    self.visit_statement(&stmt)?;
171                }
172
173                let body = node
174                    .body
175                    .as_deref()
176                    .ok_or_else(|| eyre::eyre!("for statement had no body node"))?;
177                self.visit_block_or_statement(body)
178            }
179            // Expression statement
180            NodeType::ExpressionStatement | NodeType::YulExpressionStatement => self
181                .visit_expression(
182                    &node
183                        .attribute("expression")
184                        .ok_or_else(|| eyre::eyre!("expression statement had no expression"))?,
185                ),
186            // If statement
187            NodeType::IfStatement => {
188                self.visit_expression(
189                    &node
190                        .attribute("condition")
191                        .ok_or_else(|| eyre::eyre!("if statement had no condition"))?,
192                )?;
193
194                let true_body: Node = node
195                    .attribute("trueBody")
196                    .ok_or_else(|| eyre::eyre!("if statement had no true body"))?;
197
198                // We need to store the current branch ID here since visiting the body of either of
199                // the if blocks may increase `self.branch_id` in the case of nested if statements.
200                let branch_id = self.branch_id;
201
202                // We increase the branch ID here such that nested branches do not use the same
203                // branch ID as we do.
204                self.branch_id += 1;
205
206                match node.attribute::<Node>("falseBody") {
207                    // Both if/else statements.
208                    Some(false_body) => {
209                        // Add branch coverage items only if one of true/branch bodies contains
210                        // statements.
211                        if has_statements(&true_body) || has_statements(&false_body) {
212                            // The branch instruction is mapped to the first opcode within the true
213                            // body source range.
214                            self.push_item_kind(
215                                CoverageItemKind::Branch {
216                                    branch_id,
217                                    path_id: 0,
218                                    is_first_opcode: true,
219                                },
220                                &true_body.src,
221                            );
222                            // Add the coverage item for branch 1 (false body).
223                            // The relevant source range for the false branch is the `else`
224                            // statement itself and the false body of the else statement.
225                            self.push_item_kind(
226                                CoverageItemKind::Branch {
227                                    branch_id,
228                                    path_id: 1,
229                                    is_first_opcode: false,
230                                },
231                                &ast::LowFidelitySourceLocation {
232                                    start: node.src.start,
233                                    length: false_body.src.length.map(|length| {
234                                        false_body.src.start - true_body.src.start + length
235                                    }),
236                                    index: node.src.index,
237                                },
238                            );
239
240                            // Process the true body.
241                            self.visit_block_or_statement(&true_body)?;
242                            // Process the false body.
243                            self.visit_block_or_statement(&false_body)?;
244                        }
245                    }
246                    None => {
247                        // Add single branch coverage only if it contains statements.
248                        if has_statements(&true_body) {
249                            // Add the coverage item for branch 0 (true body).
250                            self.push_item_kind(
251                                CoverageItemKind::Branch {
252                                    branch_id,
253                                    path_id: 0,
254                                    is_first_opcode: true,
255                                },
256                                &true_body.src,
257                            );
258                            // Process the true body.
259                            self.visit_block_or_statement(&true_body)?;
260                        }
261                    }
262                }
263
264                Ok(())
265            }
266            NodeType::YulIf => {
267                self.visit_expression(
268                    &node
269                        .attribute("condition")
270                        .ok_or_else(|| eyre::eyre!("yul if statement had no condition"))?,
271                )?;
272                let body = node
273                    .body
274                    .as_deref()
275                    .ok_or_else(|| eyre::eyre!("yul if statement had no body"))?;
276
277                // We need to store the current branch ID here since visiting the body of either of
278                // the if blocks may increase `self.branch_id` in the case of nested if statements.
279                let branch_id = self.branch_id;
280
281                // We increase the branch ID here such that nested branches do not use the same
282                // branch ID as we do
283                self.branch_id += 1;
284
285                self.push_item_kind(
286                    CoverageItemKind::Branch { branch_id, path_id: 0, is_first_opcode: false },
287                    &node.src,
288                );
289                self.visit_block(body)?;
290
291                Ok(())
292            }
293            // Try-catch statement. Coverage is reported as branches for catch clauses with
294            // statements.
295            NodeType::TryStatement => {
296                self.visit_expression(
297                    &node
298                        .attribute("externalCall")
299                        .ok_or_else(|| eyre::eyre!("try statement had no call"))?,
300                )?;
301
302                let branch_id = self.branch_id;
303                self.branch_id += 1;
304
305                let mut clauses = node
306                    .attribute::<Vec<Node>>("clauses")
307                    .ok_or_else(|| eyre::eyre!("try statement had no clauses"))?;
308
309                let try_block = clauses
310                    .remove(0)
311                    .attribute::<Node>("block")
312                    .ok_or_else(|| eyre::eyre!("try statement had no block"))?;
313                // Add branch with path id 0 for try (first clause).
314                self.push_item_kind(
315                    CoverageItemKind::Branch { branch_id, path_id: 0, is_first_opcode: true },
316                    &ast::LowFidelitySourceLocation {
317                        start: node.src.start,
318                        length: try_block
319                            .src
320                            .length
321                            .map(|length| try_block.src.start + length - node.src.start),
322                        index: node.src.index,
323                    },
324                );
325                self.visit_block(&try_block)?;
326
327                let mut path_id = 1;
328                for clause in clauses {
329                    if let Some(catch_block) = clause.attribute::<Node>("block") {
330                        if has_statements(&catch_block) {
331                            // Add catch branch if it has statements.
332                            self.push_item_kind(
333                                CoverageItemKind::Branch {
334                                    branch_id,
335                                    path_id,
336                                    is_first_opcode: true,
337                                },
338                                &catch_block.src,
339                            );
340                            self.visit_block(&catch_block)?;
341                            // Increment path id for next branch.
342                            path_id += 1;
343                        } else if clause.attribute::<Node>("parameters").is_some() {
344                            // Add coverage for clause with parameters and empty statements.
345                            // (`catch (bytes memory reason) {}`).
346                            // Catch all clause without statements is ignored (`catch {}`).
347                            self.push_item_kind(CoverageItemKind::Statement, &clause.src);
348                            self.visit_statement(&clause)?;
349                        }
350                    }
351                }
352
353                Ok(())
354            }
355            NodeType::YulSwitch => {
356                // Add coverage for each case statement amd their bodies.
357                for case in node
358                    .attribute::<Vec<Node>>("cases")
359                    .ok_or_else(|| eyre::eyre!("yul switch had no case"))?
360                {
361                    self.push_item_kind(CoverageItemKind::Statement, &case.src);
362                    self.visit_statement(&case)?;
363
364                    if let Some(body) = case.body {
365                        self.push_item_kind(CoverageItemKind::Statement, &body.src);
366                        self.visit_block(&body)?
367                    }
368                }
369                Ok(())
370            }
371            NodeType::YulForLoop => {
372                if let Some(condition) = node.attribute("condition") {
373                    self.visit_expression(&condition)?;
374                }
375                if let Some(pre) = node.attribute::<Node>("pre") {
376                    self.visit_block(&pre)?
377                }
378                if let Some(post) = node.attribute::<Node>("post") {
379                    self.visit_block(&post)?
380                }
381
382                if let Some(body) = &node.body {
383                    self.push_item_kind(CoverageItemKind::Statement, &body.src);
384                    self.visit_block(body)?
385                }
386                Ok(())
387            }
388            NodeType::YulFunctionDefinition => self.visit_modifier_or_yul_fn_definition(node),
389            _ => {
390                warn!("unexpected node type, expected a statement: {:?}", node.node_type);
391                Ok(())
392            }
393        }
394    }
395
396    fn visit_expression(&mut self, node: &Node) -> eyre::Result<()> {
397        match node.node_type {
398            NodeType::Assignment |
399            NodeType::UnaryOperation |
400            NodeType::Conditional |
401            NodeType::YulFunctionCall => {
402                self.push_item_kind(CoverageItemKind::Statement, &node.src);
403                Ok(())
404            }
405            NodeType::FunctionCall => {
406                // Do not count other kinds of calls towards coverage (like `typeConversion`
407                // and `structConstructorCall`).
408                let kind: Option<String> = node.attribute("kind");
409                if let Some("functionCall") = kind.as_deref() {
410                    self.push_item_kind(CoverageItemKind::Statement, &node.src);
411
412                    let expr: Option<Node> = node.attribute("expression");
413                    if let Some(NodeType::Identifier) = expr.as_ref().map(|expr| &expr.node_type) {
414                        // Might be a require call, add branch coverage.
415                        // Asserts should not be considered branches: <https://github.com/foundry-rs/foundry/issues/9460>.
416                        let name: Option<String> = expr.and_then(|expr| expr.attribute("name"));
417                        if let Some("require") = name.as_deref() {
418                            let branch_id = self.branch_id;
419                            self.branch_id += 1;
420                            self.push_item_kind(
421                                CoverageItemKind::Branch {
422                                    branch_id,
423                                    path_id: 0,
424                                    is_first_opcode: false,
425                                },
426                                &node.src,
427                            );
428                            self.push_item_kind(
429                                CoverageItemKind::Branch {
430                                    branch_id,
431                                    path_id: 1,
432                                    is_first_opcode: false,
433                                },
434                                &node.src,
435                            );
436                        }
437                    }
438                }
439
440                Ok(())
441            }
442            NodeType::BinaryOperation => {
443                self.push_item_kind(CoverageItemKind::Statement, &node.src);
444
445                // visit left and right expressions
446                // There could possibly a function call in the left or right expression
447                // e.g: callFunc(a) + callFunc(b)
448                if let Some(expr) = node.attribute("leftExpression") {
449                    self.visit_expression(&expr)?;
450                }
451
452                if let Some(expr) = node.attribute("rightExpression") {
453                    self.visit_expression(&expr)?;
454                }
455
456                Ok(())
457            }
458            // Does not count towards coverage
459            NodeType::FunctionCallOptions |
460            NodeType::Identifier |
461            NodeType::IndexAccess |
462            NodeType::IndexRangeAccess |
463            NodeType::Literal |
464            NodeType::YulLiteralValue |
465            NodeType::YulIdentifier => Ok(()),
466            _ => {
467                warn!("unexpected node type, expected an expression: {:?}", node.node_type);
468                Ok(())
469            }
470        }
471    }
472
473    fn visit_block_or_statement(&mut self, node: &Node) -> eyre::Result<()> {
474        match node.node_type {
475            NodeType::Block => self.visit_block(node),
476            NodeType::Break |
477            NodeType::Continue |
478            NodeType::DoWhileStatement |
479            NodeType::EmitStatement |
480            NodeType::ExpressionStatement |
481            NodeType::ForStatement |
482            NodeType::IfStatement |
483            NodeType::InlineAssembly |
484            NodeType::Return |
485            NodeType::RevertStatement |
486            NodeType::TryStatement |
487            NodeType::VariableDeclarationStatement |
488            NodeType::YulVariableDeclaration |
489            NodeType::WhileStatement => self.visit_statement(node),
490            // Skip placeholder statements as they are never referenced in source maps.
491            NodeType::PlaceholderStatement => Ok(()),
492            _ => {
493                warn!("unexpected node type, expected block or statement: {:?}", node.node_type);
494                Ok(())
495            }
496        }
497    }
498
499    /// Creates a coverage item for a given kind and source location. Pushes item to the internal
500    /// collection (plus additional coverage line if item is a statement).
501    fn push_item_kind(&mut self, kind: CoverageItemKind, src: &ast::LowFidelitySourceLocation) {
502        let item = CoverageItem { kind, loc: self.source_location_for(src), hits: 0 };
503
504        // Push a line item if we haven't already.
505        debug_assert!(!matches!(item.kind, CoverageItemKind::Line));
506        if self.last_line < item.loc.lines.start {
507            self.items.push(CoverageItem {
508                kind: CoverageItemKind::Line,
509                loc: item.loc.clone(),
510                hits: 0,
511            });
512            self.last_line = item.loc.lines.start;
513        }
514
515        self.items.push(item);
516    }
517
518    fn source_location_for(&self, loc: &ast::LowFidelitySourceLocation) -> SourceLocation {
519        let bytes_start = loc.start as u32;
520        let bytes_end = (loc.start + loc.length.unwrap_or(0)) as u32;
521        let bytes = bytes_start..bytes_end;
522
523        let start_line = self.source[..bytes.start as usize].lines().count() as u32;
524        let n_lines = self.source[bytes.start as usize..bytes.end as usize].lines().count() as u32;
525        let lines = start_line..start_line + n_lines;
526        SourceLocation {
527            source_id: self.source_id as usize,
528            contract_name: self.contract_name.clone(),
529            bytes,
530            lines,
531        }
532    }
533}
534
535/// Helper function to check if a given node is or contains any statement.
536fn has_statements(node: &Node) -> bool {
537    match node.node_type {
538        NodeType::DoWhileStatement |
539        NodeType::EmitStatement |
540        NodeType::ExpressionStatement |
541        NodeType::ForStatement |
542        NodeType::IfStatement |
543        NodeType::RevertStatement |
544        NodeType::TryStatement |
545        NodeType::VariableDeclarationStatement |
546        NodeType::WhileStatement => true,
547        _ => node.attribute::<Vec<Node>>("statements").is_some_and(|s| !s.is_empty()),
548    }
549}
550
551/// Coverage source analysis.
552#[derive(Clone, Debug, Default)]
553pub struct SourceAnalysis {
554    /// All the coverage items.
555    all_items: Vec<CoverageItem>,
556    /// Source ID to `(offset, len)` into `all_items`.
557    map: Vec<(u32, u32)>,
558}
559
560impl SourceAnalysis {
561    /// Analyzes contracts in the sources held by the source analyzer.
562    ///
563    /// Coverage items are found by:
564    /// - Walking the AST of each contract (except interfaces)
565    /// - Recording the items of each contract
566    ///
567    /// Each coverage item contains relevant information to find opcodes corresponding to them: the
568    /// source ID the item is in, the source code range of the item, and the contract name the item
569    /// is in.
570    ///
571    /// Note: Source IDs are only unique per compilation job; that is, a code base compiled with
572    /// two different solc versions will produce overlapping source IDs if the compiler version is
573    /// not taken into account.
574    pub fn new(data: &SourceFiles<'_>) -> eyre::Result<Self> {
575        let mut sourced_items = data
576            .sources
577            .par_iter()
578            .flat_map_iter(|(&source_id, SourceFile { source, ast })| {
579                let items = ast.nodes.iter().map(move |node| {
580                    if !matches!(node.node_type, NodeType::ContractDefinition) {
581                        return Ok(vec![]);
582                    }
583
584                    // Skip interfaces which have no function implementations.
585                    let contract_kind: String = node
586                        .attribute("contractKind")
587                        .ok_or_else(|| eyre::eyre!("Contract has no kind"))?;
588                    if contract_kind == "interface" {
589                        return Ok(vec![]);
590                    }
591
592                    let name = node
593                        .attribute("name")
594                        .ok_or_else(|| eyre::eyre!("Contract has no name"))?;
595
596                    let mut visitor = ContractVisitor::new(source_id, &source.content, &name);
597                    visitor.visit_contract(node)?;
598                    let mut items = visitor.items;
599
600                    let is_test = items.iter().any(|item| {
601                        if let CoverageItemKind::Function { name } = &item.kind {
602                            name.is_any_test()
603                        } else {
604                            false
605                        }
606                    });
607                    if is_test {
608                        items.clear();
609                    }
610
611                    Ok(items)
612                });
613                items.map(move |items| items.map(|items| (source_id, items)))
614            })
615            .collect::<eyre::Result<Vec<(usize, Vec<CoverageItem>)>>>()?;
616
617        // Create mapping and merge items.
618        sourced_items.sort_by_key(|(id, items)| (*id, items.first().map(|i| i.loc.bytes.start)));
619        let Some(&(max_idx, _)) = sourced_items.last() else { return Ok(Self::default()) };
620        let len = max_idx + 1;
621        let mut all_items = Vec::new();
622        let mut map = vec![(u32::MAX, 0); len];
623        for (idx, items) in sourced_items {
624            // Assumes that all `idx` items are consecutive, guaranteed by the sort above.
625            if map[idx].0 == u32::MAX {
626                map[idx].0 = all_items.len() as u32;
627            }
628            map[idx].1 += items.len() as u32;
629            all_items.extend(items);
630        }
631
632        Ok(Self { all_items, map })
633    }
634
635    /// Returns all the coverage items.
636    pub fn all_items(&self) -> &[CoverageItem] {
637        &self.all_items
638    }
639
640    /// Returns all the mutable coverage items.
641    pub fn all_items_mut(&mut self) -> &mut Vec<CoverageItem> {
642        &mut self.all_items
643    }
644
645    /// Returns an iterator over the coverage items and their IDs for the given source.
646    pub fn items_for_source_enumerated(
647        &self,
648        source_id: u32,
649    ) -> impl Iterator<Item = (u32, &CoverageItem)> {
650        let (base_id, items) = self.items_for_source(source_id);
651        items.iter().enumerate().map(move |(idx, item)| (base_id + idx as u32, item))
652    }
653
654    /// Returns the base item ID and all the coverage items for the given source.
655    pub fn items_for_source(&self, source_id: u32) -> (u32, &[CoverageItem]) {
656        let (mut offset, len) = self.map.get(source_id as usize).copied().unwrap_or_default();
657        if offset == u32::MAX {
658            offset = 0;
659        }
660        (offset, &self.all_items[offset as usize..][..len as usize])
661    }
662
663    /// Returns the coverage item for the given item ID.
664    #[inline]
665    pub fn get(&self, item_id: u32) -> Option<&CoverageItem> {
666        self.all_items.get(item_id as usize)
667    }
668}
669
670/// A list of versioned sources and their ASTs.
671#[derive(Debug, Default)]
672pub struct SourceFiles<'a> {
673    /// The versioned sources.
674    pub sources: HashMap<usize, SourceFile<'a>>,
675}
676
677/// The source code and AST of a file.
678#[derive(Debug)]
679pub struct SourceFile<'a> {
680    /// The source code.
681    pub source: Source,
682    /// The AST of the source code.
683    pub ast: &'a Ast,
684}
foundry_evm_coverage/analysis.rs

foundry_evm_coverage/
analysis.rs
