3.3.1. Mutation Testing Principles¶

• Reminder: To cover a branch under MT, you must do TWO things:

  • Execute the branch.

  • Check that the execution is correct. This means there must be some test that FAILS due to a mutation causing that branch to execute.

  if (a < b)
    Branch 1
  else
    Branch 2
  

  • One mutation causes Branch 1 to execute when it SHOULD NOT. A test must recognize that (and fail).

  • Another mutation causes Branch 2 to execute when it SHOULD NOT. A test must recognize that (and fail).

3.3.2. Example: Sorted list Optimization¶

// Return true iff there is a matching index.
// Assume the list is sorted by indices
Boolean findIndex(listNode start, int index) {
  while (start != null) {
    if (start.index == index)
      return true;
    if (start.index > index) // QUIT EARLY
      return false;
    start = start.next;
  }
  return false; // Not there
}

• Can you cover this? No.

  • If start.index > index is replaced with false, the method still correctly returns false because the value is never found.

• Is it really an optimization? Not as much as you might hope.

  • Save (on average) half the work at the cost of a test.

  • The test costs a dereference and a comparison.

  • The work is 2 dereferences, 2 comparisons and an assignment.

3.3.3. Example: BST Range Query¶

• Only visit the right child if the root value is less than the range max.

• Only visit the left child if the root value is greater than or equal to the range min.

• This is an optimization to avoid looking at extra nodes.

• There is no way to test that this gives the wrong answer in terms of what record is found, because optimization has nothing to do with that.

• Optimization in this case is about how many nodes are looked at. So, that is what must be tested.

3.3.4. Example: BigNum Exponents¶

public int exponentiate(int base, int exponent) {
  if (exponent == 0) {
    return 1;
  }
  else if (exponent == 1) {
    return base;
  }
  else if (exponent % 2 == 0) {
    return exponentiate(base * base, exponent / 2);
  } else {
    return base * exponentiate(base, exponent - 1);
  }
}

• Fundamental problem: 4 branches, but 3 outcomes.

• Example input: exponentiate(8, 2)

• Consider: else if (exponent == 1).

  • If MT sets this to TRUE, this fails. OK. But if MT sets this to FALSE, then it gets picked up later by the odd condition.

  • One solution: Simply remove the whole branch for exponent == 1

3.3.5. Hash Table Expansion (1)¶

 private void localInsertIncorrect(Record inH) throws IOException {
   // these should be after the expansion
   int home = h(inH.key());
   int h2 = h2(inH.key());
   int slot = home;
   if (numElements >= table.length / 2) {
     expand();
   }
   while ((table[slot] != null) && !isTombStone(table[slot])) {
     slot = (slot + h2) % table.length;
   }
   table[slot] = inH;
   numElements++;
}

• A test that only inserts into the first half of the table will give mutation coverage, but won’t catch the bug.

• So, the code is coverable, and the bug would be catchable. The problem is that the test is inadequate. But MT won’t point that out to you.

3.3.6. Hash Table Expansion (2)¶

private void localInsertCorrect(Record inH) throws IOException {
  if (numElements >= table.length / 2) {
    expand();
  }
  int home = h(inH.key());
  int h2 = h2(inH.key());
  int slot = home;
  while ((table[slot] != null) && !isTombStone(table[slot])) {
    slot = (slot + h2) % table.length;
  }
  table[slot] = inH;
  numElements++;
}