More granular FnValue mutations

[john-h-kastner]

This idea is an extension to the current function value replacement mutations. In brief: instead of replacing whole function bodies cargo-mutants would replace one branch at a time to obtain more granular mutants. I've implemented and been trying out these changes on a local build already, so I can polish everything and put up a PR pretty quickly if you like the idea.

Motivating Example

A function recursively visiting a data structure will often look something like this.

fn eval(e: Expr) -> i32 {
  match e {
      Num(n) => n,
      Plus(l, r) => eval(l) + eval(r),
      Minus(l, r) => eval(l) - eval(r),
  }
}

The current function value mutation replace the whole function body.

fn eval(e: Expr) -> i32 {
-  match e {
-      Num(n) => n,
-      Plus(l, r) => eval(l) + eval(r),
-      Minus(l, r) => eval(l) - eval(r),
-  }
+ 0
}

Killing this mutant doesn't tell us if our tests exercise all the branches. With this idea, cargo-mutants would instead find and replace each expression in "return position". In this function, it would mutate each branch of the match independently, so we could be confident that every branch is exercised by our tests.

For example, cargo-mutants would generate a mutant replacing the expression in the Minus branch. Detecting this mutant requires at least one test case properly exercising Minus while the original mutant would be detected by any test properly exercising the eval function, even if it never constructed a Minus.

fn eval(e: Expr) -> i32 {
  match e {
      Num(n) => n,
      Plus(l, r) => eval(l) + eval(r),
-     Minus(l, r) => eval(l) - eval(r),
+     Minus(l, r) => 0,
  }
}

Details

Extend function value rewriting is a recursive procedure with the following cases:

• For a parenthesized expression, we recursively generate mutants for the inner expression.
• For a block expression, we recursively generate mutants for the last expression in the block.
• For an if expression, we recursively generate mutants for both branches, but do not rewrite the condition.
• For a match expression we recursively generate mutants for all match arms, but do not rewrite the matched expression.
• For all other expressions, we stop recursion and generate mutants to replace the expression using the existing return_type_replacements procedure.

In the following example, the block and if cases work together to allow replacing just the final else branch without touching anything else. Note that the then branch uses the local b, which we have left untouched.

fn foo(a: i32) -> i32 {
  let b = a - 1;
  let c = b - 1;
  if a == 0 {
    b
  } else {
-  c
+  0
  }
}

Implemented as a separate pass, cargo-mutants should also find explicit return statements and and mutates the returned value. I expect that early returns tend to handle uncommon cases and error conditions, so it is important that they are exercised by a test-suit. Implementing this properly requires some additional book-keeping to track if the visitor is inside a closure.

fn foo(i: i32, j: i32) -> Option<i32> {
  if j == 0 {
-   return None;
+   return Some(0);
  }
  Some(i / j)
}

Drawbacks

There are some cases where the more granular mutation breaks type inference for local variable bindings. In the following function, Rust cannot infer a collection type for s if it is not returned. The whole body function mutation deletes s, so type inference is not an issue.

fn foo(i : impl IntoIterator<Item = i32>) -> HashSet<i32> {
  let s = i.into_iter().collect();
- s
+ HashSet::new()
}

[sourcefrog]

Yep, this sounds like a great extension, and a patch or series of patches to do it would be welcome.