Off Just mistakes and mutation checking

Question

In the process of writing the mutation tester "Off By One" for my favorite mutation testing environment ( NinjaTurtles ), I wrote the following code to enable me to verify the correctness of my implementation:

public int SumTo(int max) { int sum = 0; for (var i = 1; i <= max; i++) { sum += i; } return sum; } 

now this seems simple enough, and it didn't seem to me that there would be a problem trying to change all literal integer constants in IL. In the end, only 3 ( 0 , 1 and ++ ).

WRONG!

In the first run, it became apparent that in this particular case it would never work. What for? Since changing the code to

 public int SumTo(int max) { int sum = 0; for (var i = 0; i <= max; i++) { sum += i; } return sum; } 

only adds 0 (zero) to the sum, and this obviously has no effect. A different story if it was a multiple set, but in this case it is not.

Now there is a fairly simple algorithm for calculating the sum of integers

 sum = max * (max + 1) / 2; 

which I could easily knock down mutations, since adding or subtracting 1 from any of the constants will lead to an error. (given that max >= 0 )

So, the problem is solved for this particular case. Although he did not do what I wanted for a mutation test, which was to check what would happen when I lose ++ , a virtually infinite loop. But this is another problem.

So - My Question: Are there any trivial or non-trivial cases when a cycle starting with 0 or 1 can lead to a "mutation from one" error that cannot be reorganized (test code or test) in the same way? (please examples)

Note Mutation tests fail when a test package passes after applying a mutation.

Update: an example of something less trivial, but something that could still be refactored for the test to fail, would be as follows

 public int SumArray(int[] array) { int sum = 0; for (var i = 0; i < array.Length; i++) { sum += array[i]; } return sum; } 

Checking mutations for this code did not work when changing var i=0 to var i=1 if the test input you gave it was new[] {0,1,2,3,4,5,6,7,8,9} . However, change the test input to new[] {9,8,7,6,5,4,3,2,1,0} and mutation testing will fail. Thus, a successful refactor proves testing.

Answer 1

One natural case of “failure of a mutation test” is the matrix transfer algorithm. To make it more suitable for a single for loop, add some limitations to this task: let the matrix be non-square and require that the transpose be in place. These limitations make a one-dimensional array the most suitable place to store the matrix, and a for loop can be used to process it (a loop, usually from the index '1'). If you start it with an index of "0", nothing changes, because the element at the top left of the matrix is ​​always transferred to itself.

For an example of such code, see the answer to another question (not in C #, sorry).

Here the test "mutation off by one" fails, refactoring the test does not change it. I don’t know if the code itself can be reorganized to avoid this. Theoretically, this is possible, but should be too complicated.

---

The code snippet I referenced earlier is not a perfect example. It can still be reorganized if the for loop is replaced by two nested loops (as for rows and columns), and then these rows and columns are recalculated back to a one-dimensional index. Nevertheless, it gives an idea of ​​how to make some algorithm that cannot be reorganized (although not very significant).

Iterating through an array of positive integers in ascending order of indices, for each index calculate its pair as i + i % a[i] , and if it does not go beyond the boundaries, replace these elements:

 for (var i = 1; i < a.Length; i++) { var j = i + i % a[i]; if (j < a.Length) Swap(a[i], a[j]); } 

Here again [0] is "impossible", refactoring the test does not change this, and refactoring the code itself is almost impossible.

---

Another “significant” example. Let an implicit binary heap be implemented. It is usually placed in some array, starting at index "1" (this simplifies many Binary Heap calculations compared to the beginning of index "0"). Now we implement the copy method for this heap. The problem "in turn" in this copying method is not detected, since a zero index is not used, and C # zero initializes all arrays. This is similar to summing an OP array, but cannot be reorganized.

Strictly speaking, you can reorganize the entire class and start with "0". But changing only the “copy” method or test does not prevent the “mutation from one” test. The Binary Heap class can be considered as a motivation for copying an array with an unused first element.

 int[] dst = new int[src.Length]; for (var i = 1; i < src.Length; i++) { dst[i] = src[i]; } 

Answer 2

I think there are two options with this particular method. You either acknowledge that this is not suitable for testing mutations due to this mathematical anomaly, or you are trying to write it in such a way that it is safe for testing mutations, either by refactoring to the form you give, or in some other way (maybe recursive?).

Your question really boils down to the following: is there a real situation when we care about whether element 0 is included or excluded from the loop operation, and for which we cannot write a test around this specific aspect ? My instinct is to say no.

Your trivial example might be an example of the lack of what I called test-drivenness in my blog post about NinjaTurtles . Value if you did not reorganize this method as much as you need.

Answer 3

Yes, there is a lot, assuming I understood your question.

Similar to your case:

 public int MultiplyTo(int max) { int product = 1; for (var i = 1; i <= max; i++) { product *= i; } return product; } 

Here, if it starts at 0, the result will be 0, but if it starts at 1, the result should be correct. (Although he will not tell the difference between 1 and 2!).

Answer 4

Not quite sure what exactly you are looking for, but it seems to me that if you change / change the initial value of the sum from 0 to 1, you should skip the test:

 public int SumTo(int max) { int sum = 1; // Now we are off-by-one from the beginning! for (var i = 0; i <= max; i++) { sum += i; } return sum; } 

Comment Based Update:

The cycle will not fail after the mutation, when the cycle invariant is violated when processing index 0 (or in the absence of it). Most of these special cases can be reorganized from the loop, but consider 1 / x summation:

 for (var i = 1; i <= max; i++) { sum += 1/i; } 

This works fine, but if you mutate the original group from 1 to 0, the test will fail because 1/0 is invalid.