Skip to main content

forge/mutation/
type_analysis.rs

1//! Type-aware filtering for operator mutations.
2//!
3//! This module records replacements that are type-invalid. It deliberately does not filter
4//! replacements merely because they return the same value for every input: different operators can
5//! still compile to gas-distinct bytecode.
6
7use std::{
8    collections::{HashMap, HashSet},
9    ops::ControlFlow,
10    path::{Path, PathBuf},
11};
12
13use eyre::Result;
14use foundry_cli::opts::configure_pcx_from_compile_output;
15use foundry_compilers::{ProjectCompileOutput, compilers::multi::MultiCompiler};
16use foundry_config::Config;
17use solar::{
18    ast::{BinOpKind, UnOpKind},
19    interface::{Session, source_map::FileName},
20    sema::{
21        Compiler, CompilerRef, Gcx,
22        hir::{self, ElementaryType, ExprKind, Visit},
23        ty::TyKind,
24    },
25};
26
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
28enum ReplacementOperator {
29    Assignment(AssignmentReplacement),
30    Binary(BinOpKind),
31    Unary(UnOpKind),
32}
33
34#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
35pub enum AssignmentReplacement {
36    Zero,
37    Negate,
38}
39
40#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
41pub struct MutationExclusion {
42    lo: u32,
43    hi: u32,
44    new_op: ReplacementOperator,
45}
46
47impl MutationExclusion {
48    pub fn assignment(span: solar::ast::Span, replacement: AssignmentReplacement) -> Self {
49        Self {
50            lo: span.lo().0,
51            hi: span.hi().0,
52            new_op: ReplacementOperator::Assignment(replacement),
53        }
54    }
55
56    pub fn binary(span: solar::ast::Span, new_op: BinOpKind) -> Self {
57        Self { lo: span.lo().0, hi: span.hi().0, new_op: ReplacementOperator::Binary(new_op) }
58    }
59
60    pub fn unary(span: solar::ast::Span, new_op: UnOpKind) -> Self {
61        Self { lo: span.lo().0, hi: span.hi().0, new_op: ReplacementOperator::Unary(new_op) }
62    }
63}
64
65pub type MutationExclusionSet = HashSet<MutationExclusion>;
66pub type MutationExclusionsByPath = HashMap<PathBuf, MutationExclusionSet>;
67
68pub fn collect_mutation_exclusions(
69    config: &Config,
70    output: &ProjectCompileOutput<MultiCompiler>,
71) -> Result<MutationExclusionsByPath> {
72    let mut compiler = Compiler::new(Session::builder().with_silent_emitter(None).build());
73    compiler.enter_mut(|compiler| {
74        let mut pcx = compiler.parse();
75        configure_pcx_from_compile_output(&mut pcx, config, output, None)?;
76        pcx.parse();
77
78        let Ok(ControlFlow::Continue(())) = compiler.lower_asts() else {
79            return Ok(MutationExclusionsByPath::new());
80        };
81        Ok(analyze_and_collect(compiler))
82    })
83}
84
85fn analyze_and_collect(compiler: &CompilerRef<'_>) -> MutationExclusionsByPath {
86    let Ok(ControlFlow::Continue(())) = compiler.analysis() else {
87        return MutationExclusionsByPath::new();
88    };
89    if compiler.dcx().has_errors().is_err() {
90        return MutationExclusionsByPath::new();
91    }
92    collect_from_gcx(compiler.gcx())
93}
94
95fn collect_from_gcx<'gcx>(gcx: Gcx<'gcx>) -> MutationExclusionsByPath {
96    let mut by_path = MutationExclusionsByPath::new();
97    for source_id in gcx.hir.source_ids() {
98        let source = gcx.hir.source(source_id);
99        let FileName::Real(path) = &source.file.name else { continue };
100        let mut collector = MutationExclusionCollector {
101            gcx,
102            // HIR uses offsets in the compiler-wide source map, while the mutation visitor parses
103            // each target independently and uses offsets relative to that file.
104            source_start: source.file.start_pos.0,
105            mutations: MutationExclusionSet::new(),
106        };
107        let _ = collector.visit_nested_source(source_id);
108        if !collector.mutations.is_empty() {
109            by_path.insert(normalize_path(path), collector.mutations);
110        }
111    }
112    by_path
113}
114
115pub fn normalize_path(path: &Path) -> PathBuf {
116    path.canonicalize().unwrap_or_else(|_| path.to_path_buf())
117}
118
119struct MutationExclusionCollector<'hir> {
120    gcx: Gcx<'hir>,
121    source_start: u32,
122    mutations: MutationExclusionSet,
123}
124
125impl<'hir> Visit<'hir> for MutationExclusionCollector<'hir> {
126    type BreakValue = ();
127
128    fn hir(&self) -> &'hir hir::Hir<'hir> {
129        &self.gcx.hir
130    }
131
132    fn visit_expr(&mut self, expr: &'hir hir::Expr<'hir>) -> ControlFlow<Self::BreakValue> {
133        if let ExprKind::Assign(destination, None, value) = &expr.kind
134            && let Some(ty) = self.gcx.type_of_expr(destination.id)
135        {
136            self.collect_assignment(value, ty);
137        }
138        if let ExprKind::Binary(left, op, right) = &expr.kind
139            && (op.kind.is_cmp() || matches!(op.kind, BinOpKind::And | BinOpKind::Or))
140        {
141            self.collect_comparison(expr, left, op.kind, right);
142        }
143        if let ExprKind::Unary(_, operand) = &expr.kind
144            && is_unsigned(self.gcx, operand)
145            && let Some(span) = self.local_span(expr.span)
146        {
147            self.mutations.insert(MutationExclusion::unary(span, UnOpKind::Neg));
148        }
149        if let ExprKind::Unary(_, operand) = &expr.kind
150            && is_non_storage_push_call(self.gcx, operand)
151            && let Some(span) = self.local_span(expr.span)
152        {
153            for op in [UnOpKind::PreInc, UnOpKind::PreDec, UnOpKind::PostInc, UnOpKind::PostDec] {
154                self.mutations.insert(MutationExclusion::unary(span, op));
155            }
156        }
157        self.walk_expr(expr)
158    }
159
160    fn visit_var(&mut self, var: &'hir hir::Variable<'hir>) -> ControlFlow<Self::BreakValue> {
161        if let Some(value) = var.initializer {
162            self.collect_assignment(value, self.gcx.type_of_hir_ty(&var.ty));
163        }
164        self.walk_var(var)
165    }
166}
167
168impl MutationExclusionCollector<'_> {
169    fn collect_assignment(&mut self, value: &hir::Expr<'_>, destination: solar::sema::ty::Ty<'_>) {
170        let Some(span) = self.local_span(value.span) else { return };
171        let Some(kind) = assignment_destination_kind(destination) else { return };
172
173        if !kind.accepts_zero() {
174            self.mutations.insert(MutationExclusion::assignment(span, AssignmentReplacement::Zero));
175        }
176        if !kind.accepts_negation() {
177            self.mutations
178                .insert(MutationExclusion::assignment(span, AssignmentReplacement::Negate));
179        }
180    }
181
182    fn collect_comparison(
183        &mut self,
184        expr: &hir::Expr<'_>,
185        left: &hir::Expr<'_>,
186        original: BinOpKind,
187        right: &hir::Expr<'_>,
188    ) {
189        let Some(span) = self.local_span(expr.span) else { return };
190
191        for candidate in [
192            BinOpKind::Lt,
193            BinOpKind::Le,
194            BinOpKind::Gt,
195            BinOpKind::Ge,
196            BinOpKind::Eq,
197            BinOpKind::Ne,
198            BinOpKind::Or,
199            BinOpKind::And,
200        ] {
201            if candidate != original
202                && is_type_invalid_replacement(self.gcx, left, original, right, candidate)
203            {
204                self.mutations.insert(MutationExclusion::binary(span, candidate));
205            }
206        }
207    }
208
209    fn local_span(&self, span: solar::ast::Span) -> Option<solar::ast::Span> {
210        let lo = span.lo().0.checked_sub(self.source_start)?;
211        let hi = span.hi().0.checked_sub(self.source_start)?;
212        Some(solar::ast::Span::new(solar::interface::BytePos(lo), solar::interface::BytePos(hi)))
213    }
214}
215
216#[derive(Clone, Copy)]
217enum AssignmentDestinationKind {
218    SignedNumber,
219    UnsignedNumber,
220    FixedBytes,
221    Other,
222}
223
224impl AssignmentDestinationKind {
225    const fn accepts_zero(self) -> bool {
226        !matches!(self, Self::Other)
227    }
228
229    const fn accepts_negation(self) -> bool {
230        matches!(self, Self::SignedNumber)
231    }
232}
233
234fn assignment_destination_kind(ty: solar::sema::ty::Ty<'_>) -> Option<AssignmentDestinationKind> {
235    match ty.peel_refs().kind {
236        TyKind::Elementary(ElementaryType::Int(_) | ElementaryType::Fixed(..)) => {
237            Some(AssignmentDestinationKind::SignedNumber)
238        }
239        TyKind::Elementary(ElementaryType::UInt(_) | ElementaryType::UFixed(..)) => {
240            Some(AssignmentDestinationKind::UnsignedNumber)
241        }
242        TyKind::Elementary(ElementaryType::FixedBytes(_)) => {
243            Some(AssignmentDestinationKind::FixedBytes)
244        }
245        TyKind::Udvt(..) | TyKind::Err(_) => None,
246        _ => Some(AssignmentDestinationKind::Other),
247    }
248}
249
250fn is_type_invalid_replacement(
251    gcx: Gcx<'_>,
252    left: &hir::Expr<'_>,
253    original: BinOpKind,
254    right: &hir::Expr<'_>,
255    candidate: BinOpKind,
256) -> bool {
257    match candidate {
258        BinOpKind::And | BinOpKind::Or => matches!(
259            comparison_operand_kind(gcx, left, right),
260            Some(ComparisonOperandKind::Function | ComparisonOperandKind::Other)
261        ),
262        BinOpKind::Lt | BinOpKind::Le | BinOpKind::Gt | BinOpKind::Ge => {
263            matches!(original, BinOpKind::And | BinOpKind::Or)
264                || matches!(
265                    comparison_operand_kind(gcx, left, right),
266                    Some(ComparisonOperandKind::Bool | ComparisonOperandKind::Function)
267                )
268        }
269        _ => false,
270    }
271}
272
273#[derive(Clone, Copy, Debug, PartialEq, Eq)]
274enum ComparisonOperandKind {
275    Bool,
276    Function,
277    Other,
278}
279
280fn comparison_operand_kind(
281    gcx: Gcx<'_>,
282    left: &hir::Expr<'_>,
283    right: &hir::Expr<'_>,
284) -> Option<ComparisonOperandKind> {
285    let left = gcx.type_of_expr(left.id)?;
286    let right = gcx.type_of_expr(right.id)?;
287    match (left.peel_refs().kind, right.peel_refs().kind) {
288        (TyKind::Elementary(ElementaryType::Bool), TyKind::Elementary(ElementaryType::Bool)) => {
289            Some(ComparisonOperandKind::Bool)
290        }
291        (TyKind::Fn(_), TyKind::Fn(_)) => Some(ComparisonOperandKind::Function),
292        (TyKind::Err(_), _) | (_, TyKind::Err(_)) => None,
293        _ => Some(ComparisonOperandKind::Other),
294    }
295}
296
297fn is_unsigned(gcx: Gcx<'_>, expr: &hir::Expr<'_>) -> bool {
298    gcx.type_of_expr(expr.peel_parens().id).is_some_and(|ty| {
299        matches!(ty.peel_refs().kind, TyKind::Elementary(ElementaryType::UInt(_)))
300    })
301}
302
303fn is_non_storage_push_call(gcx: Gcx<'_>, expr: &hir::Expr<'_>) -> bool {
304    let ExprKind::Call(callee, args, _) = &expr.peel_parens().kind else { return false };
305    let ExprKind::Member(receiver, member) = &callee.peel_parens().kind else { return false };
306    if member.as_str() != "push" || !args.is_empty() {
307        return false;
308    }
309
310    !gcx.type_of_expr(receiver.id).is_some_and(|ty| {
311        matches!(
312            ty.kind,
313            TyKind::Ref(inner, location)
314                if location.is_storage()
315                    && matches!(
316                        inner.kind,
317                        TyKind::DynArray(_) | TyKind::Elementary(ElementaryType::Bytes)
318                    )
319        )
320    })
321}
322
323#[cfg(test)]
324mod tests {
325    use super::*;
326    use solar::interface::BytePos;
327
328    fn collect(source: &str) -> MutationExclusionSet {
329        let path = PathBuf::from("Test.sol");
330        let mut compiler = Compiler::new(Session::builder().with_silent_emitter(None).build());
331        compiler.enter_mut(|compiler| {
332            let mut pcx = compiler.parse();
333            let file =
334                pcx.sess.source_map().new_source_file(path.clone(), source).expect("source file");
335            pcx.add_file(file);
336            pcx.parse();
337            assert!(matches!(compiler.lower_asts(), Ok(ControlFlow::Continue(()))));
338            analyze_and_collect(compiler).remove(&path).unwrap_or_default()
339        })
340    }
341
342    fn mutation(source: &str, expression: &str, new_op: BinOpKind) -> MutationExclusion {
343        let lo = source.find(expression).expect("expression") as u32;
344        MutationExclusion::binary(
345            solar::ast::Span::new(BytePos(lo), BytePos(lo + expression.len() as u32)),
346            new_op,
347        )
348    }
349
350    fn unary_mutation(source: &str, expression: &str, new_op: UnOpKind) -> MutationExclusion {
351        let lo = source.find(expression).expect("expression") as u32;
352        MutationExclusion::unary(
353            solar::ast::Span::new(BytePos(lo), BytePos(lo + expression.len() as u32)),
354            new_op,
355        )
356    }
357
358    fn assignment_mutation(
359        source: &str,
360        value: &str,
361        replacement: AssignmentReplacement,
362    ) -> MutationExclusion {
363        let lo = source.rfind(value).expect("value") as u32;
364        MutationExclusion::assignment(
365            solar::ast::Span::new(BytePos(lo), BytePos(lo + value.len() as u32)),
366            replacement,
367        )
368    }
369
370    #[test]
371    fn excludes_assignments_invalid_for_destination_type() {
372        let source = r#"
373enum Choice { A, B }
374
375contract Test {
376    function check(address account, bool flag, uint256 unsigned, Choice choice) external pure {
377        address accountCopy = account;
378        bool flagCopy = flag;
379        uint256 unsignedCopy = unsigned;
380        Choice choiceCopy = choice;
381    }
382}
383"#;
384        let mutations = collect(source);
385
386        for value in ["account", "flag", "choice"] {
387            assert!(mutations.contains(&assignment_mutation(
388                source,
389                value,
390                AssignmentReplacement::Zero,
391            )));
392            assert!(mutations.contains(&assignment_mutation(
393                source,
394                value,
395                AssignmentReplacement::Negate,
396            )));
397        }
398        assert!(!mutations.contains(&assignment_mutation(
399            source,
400            "unsigned",
401            AssignmentReplacement::Zero,
402        )));
403        assert!(mutations.contains(&assignment_mutation(
404            source,
405            "unsigned",
406            AssignmentReplacement::Negate,
407        )));
408    }
409
410    #[test]
411    fn uses_lhs_type_for_assignments() {
412        let source = r#"
413contract Test {
414    function check(address account, bool flag) external pure {
415        account = account;
416        flag = flag;
417    }
418}
419"#;
420        let mutations = collect(source);
421
422        for value in ["account", "flag"] {
423            assert!(mutations.contains(&assignment_mutation(
424                source,
425                value,
426                AssignmentReplacement::Zero,
427            )));
428            assert!(mutations.contains(&assignment_mutation(
429                source,
430                value,
431                AssignmentReplacement::Negate,
432            )));
433        }
434    }
435
436    #[test]
437    fn preserves_valid_signed_and_fixed_bytes_assignments() {
438        let source = r#"
439contract Test {
440    function check(int256 signed, bytes32 word) external pure {
441        int256 signedCopy = signed;
442        bytes32 wordCopy = word;
443    }
444}
445"#;
446        let mutations = collect(source);
447
448        for replacement in [AssignmentReplacement::Zero, AssignmentReplacement::Negate] {
449            assert!(!mutations.contains(&assignment_mutation(source, "signed", replacement)));
450        }
451        assert!(!mutations.contains(&assignment_mutation(
452            source,
453            "word",
454            AssignmentReplacement::Zero,
455        )));
456        assert!(mutations.contains(&assignment_mutation(
457            source,
458            "word",
459            AssignmentReplacement::Negate,
460        )));
461    }
462
463    #[test]
464    fn preserves_udvt_assignments() {
465        let source = r#"
466type Amount is uint256;
467
468contract Test {
469    function check(Amount amount) external pure {
470        Amount copy = amount;
471    }
472}
473"#;
474        let mutations = collect(source);
475
476        for replacement in [AssignmentReplacement::Zero, AssignmentReplacement::Negate] {
477            assert!(!mutations.contains(&assignment_mutation(source, "amount", replacement)));
478        }
479    }
480
481    #[test]
482    fn preserves_all_mutations_when_analysis_has_errors() {
483        let source = r#"
484contract Test {
485    function check(address account) external pure {
486        address copy = account;
487        unresolved = unresolved;
488    }
489}
490"#;
491
492        assert!(collect(source).is_empty());
493    }
494
495    #[test]
496    fn preserves_gas_distinct_unsigned_boundary_mutations() {
497        let source = r#"
498contract Test {
499    function check(uint256 x) external pure returns (bool) {
500        return x == 0;
501    }
502}
503"#;
504        let mutations = collect(source);
505
506        assert!(!mutations.contains(&mutation(source, "x == 0", BinOpKind::Le)));
507        assert!(!mutations.contains(&mutation(source, "x == 0", BinOpKind::Lt)));
508    }
509
510    #[test]
511    fn excludes_negation_only_for_unsigned_unary_operands() {
512        let source = r#"
513contract Test {
514    function check(uint256 unsigned, int256 signed) external pure {
515        unsigned++;
516        ++unsigned;
517        signed++;
518    }
519}
520"#;
521        let mutations = collect(source);
522
523        assert!(mutations.contains(&unary_mutation(source, "unsigned++", UnOpKind::Neg)));
524        assert!(mutations.contains(&unary_mutation(source, "++unsigned", UnOpKind::Neg)));
525        assert!(!mutations.contains(&unary_mutation(source, "signed++", UnOpKind::Neg)));
526    }
527
528    #[test]
529    fn excludes_lvalue_mutations_for_user_defined_push() {
530        let source = r#"
531contract Test {
532    function push() external pure returns (int256) {
533        return 1;
534    }
535
536    function check() external view returns (int256) {
537        return -this.push();
538    }
539}
540"#;
541        let mutations = collect(source);
542
543        for op in [UnOpKind::PreInc, UnOpKind::PreDec, UnOpKind::PostInc, UnOpKind::PostDec] {
544            assert!(mutations.contains(&unary_mutation(source, "-this.push()", op)));
545        }
546    }
547
548    #[test]
549    fn preserves_lvalue_mutations_for_storage_push() {
550        let source = r#"
551contract Test {
552    int256[] values;
553
554    function check() external returns (int256) {
555        return -values.push();
556    }
557}
558"#;
559        let mutations = collect(source);
560
561        for op in [UnOpKind::PreInc, UnOpKind::PreDec, UnOpKind::PostInc, UnOpKind::PostDec] {
562            assert!(!mutations.contains(&unary_mutation(source, "-values.push()", op)));
563        }
564    }
565
566    #[test]
567    fn preserves_overloaded_negation_for_unsigned_udvt() {
568        let source = r#"
569type Amount is uint256;
570
571function negate(Amount amount) pure returns (Amount) {
572    return Amount.wrap(type(uint256).max - Amount.unwrap(amount));
573}
574
575function complement(Amount amount) pure returns (Amount) {
576    return Amount.wrap(~Amount.unwrap(amount));
577}
578
579using {negate as -, complement as ~} for Amount global;
580
581contract Test {
582    function check(Amount amount) external pure returns (Amount) {
583        return ~amount;
584    }
585}
586"#;
587        let mutations = collect(source);
588
589        assert!(!mutations.contains(&unary_mutation(source, "~amount", UnOpKind::Neg)));
590    }
591
592    #[test]
593    fn preserves_negation_for_unresolved_operand() {
594        let source = r#"
595contract Test {
596    function check() external pure {
597        unresolved++;
598    }
599}
600"#;
601        let mutations = collect(source);
602
603        assert!(!mutations.contains(&unary_mutation(source, "unresolved++", UnOpKind::Neg)));
604    }
605
606    #[test]
607    fn excludes_logical_replacements_for_numeric_comparisons() {
608        let source = r#"
609contract Test {
610    function check(uint256 left, uint256 right) external pure returns (bool) {
611        return left == right;
612    }
613}
614"#;
615        let mutations = collect(source);
616
617        assert!(mutations.contains(&mutation(source, "left == right", BinOpKind::And)));
618        assert!(mutations.contains(&mutation(source, "left == right", BinOpKind::Or)));
619        assert!(!mutations.contains(&mutation(source, "left == right", BinOpKind::Lt)));
620        assert!(!mutations.contains(&mutation(source, "left == right", BinOpKind::Ne)));
621    }
622
623    #[test]
624    fn excludes_ordered_replacements_for_boolean_equality() {
625        let source = r#"
626contract Test {
627    function check(bool left, bool right) external pure returns (bool) {
628        return left == right;
629    }
630}
631"#;
632        let mutations = collect(source);
633
634        for candidate in [BinOpKind::Lt, BinOpKind::Le, BinOpKind::Gt, BinOpKind::Ge] {
635            assert!(mutations.contains(&mutation(source, "left == right", candidate)));
636        }
637        for candidate in [BinOpKind::Ne, BinOpKind::And, BinOpKind::Or] {
638            assert!(!mutations.contains(&mutation(source, "left == right", candidate)));
639        }
640    }
641
642    #[test]
643    fn excludes_ordered_replacements_for_logical_operations() {
644        let source = r#"
645contract Test {
646    function check(bool left, bool right) external pure returns (bool) {
647        return left && right;
648    }
649}
650"#;
651        let mutations = collect(source);
652
653        for candidate in [BinOpKind::Lt, BinOpKind::Le, BinOpKind::Gt, BinOpKind::Ge] {
654            assert!(mutations.contains(&mutation(source, "left && right", candidate)));
655        }
656        for candidate in [BinOpKind::Eq, BinOpKind::Ne, BinOpKind::Or] {
657            assert!(!mutations.contains(&mutation(source, "left && right", candidate)));
658        }
659    }
660
661    #[test]
662    fn excludes_non_equality_replacements_for_function_comparisons() {
663        let source = r#"
664contract Test {
665    function check(
666        function() external left,
667        function() external right
668    ) external pure returns (bool) {
669        return left == right;
670    }
671}
672"#;
673        let mutations = collect(source);
674
675        for candidate in [
676            BinOpKind::Lt,
677            BinOpKind::Le,
678            BinOpKind::Gt,
679            BinOpKind::Ge,
680            BinOpKind::And,
681            BinOpKind::Or,
682        ] {
683            assert!(mutations.contains(&mutation(source, "left == right", candidate)));
684        }
685        assert!(!mutations.contains(&mutation(source, "left == right", BinOpKind::Ne)));
686    }
687
688    #[test]
689    fn preserves_reversed_and_upper_boundary_mutations() {
690        let source = r#"
691contract Test {
692    function lower(uint256 x) external pure returns (bool) {
693        return 0 == x;
694    }
695
696    function upper(uint8 x) external pure returns (bool) {
697        return x == type(uint8).max;
698    }
699}
700"#;
701        let mutations = collect(source);
702
703        assert!(!mutations.contains(&mutation(source, "0 == x", BinOpKind::Ge)));
704        assert!(!mutations.contains(&mutation(source, "0 == x", BinOpKind::Gt)));
705        assert!(!mutations.contains(&mutation(source, "x == type(uint8).max", BinOpKind::Ge)));
706    }
707
708    #[test]
709    fn preserves_member_and_typed_constant_boundary_mutations() {
710        let source = r#"
711contract Test {
712    function empty(bytes memory value) external pure returns (bool) {
713        return value.length == 0;
714    }
715
716    function zero(address value) external pure returns (bool) {
717        return value == address(0);
718    }
719}
720"#;
721        let mutations = collect(source);
722
723        assert!(!mutations.contains(&mutation(source, "value.length == 0", BinOpKind::Le)));
724        assert!(!mutations.contains(&mutation(source, "value == address(0)", BinOpKind::Le)));
725    }
726}