Off By One errors and Mutation Testing

Question

En el proceso de escribir un probador de mutaciones "Off By One" para mi marco favorito de pruebas de mutaciones (NinjaTurtles), escribí el siguiente código para brindar la oportunidad de verificar la corrección de mi implementación:

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

ahora esto parece bastante simple, y no me dio la impresión de que no habría un problema al intentar mutar todas las constantes enteras literales en la IL. Después de todo, solo hay 3 (0, 1 y ++).

¡INCORRECTO!

Se hizo muy evidente en la primera ejecución que nunca iba a funcionar en esta instancia en particular. ¿Por qué? Porque al cambiar el código para

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

solamente añade 0 (cero) a la suma, y ​​esto, evidentemente, no tiene ningún efecto. Una historia diferente si fue el conjunto múltiple, pero en este caso no fue así.

Ahora hay un algoritmo bastante fácil para la elaboración de la suma de los números enteros

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

que podría haber fallan las mutaciones fácilmente, ya que sumando o restando 1 de cualquiera de las constantes habrá resultado un error. (dado que max >= 0)

Por lo tanto, problema resuelto para este caso en particular. Aunque no hizo lo que quería para la prueba de la mutación, que era comprobar lo que sucedería cuando perdiera el ++, un bucle infinito. Pero ese es otro problema.

Por lo tanto - Mi Pregunta: ¿Hay casos triviales o no triviales en un bucle a partir de 0 o 1 puede resultar en una falla de la prueba "mutación fuera por uno" que no puede ser reprogramado (código bajo prueba o pruebas) ¿En una forma similar? (ejemplos, por favor)

Nota: Las pruebas de mutación fallan cuando el banco de pruebas pasa después de que se haya aplicado una mutación.

Actualización: un ejemplo de algo menos trivial, pero algo que todavía podría haber la prueba refactorizado de modo que no sería la siguiente prueba

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

    return sum; 
} 

mutación en contra de este código podría fallar al cambiar el var i=0 a var i=1 si la entrada de prueba que le diste fue new[] {0,1,2,3,4,5,6,7,8,9}. Sin embargo, cambie la entrada de prueba a new[] {9,8,7,6,5,4,3,2,1,0}, y la prueba de mutación fallará. Entonces, un refactor exitoso prueba las pruebas.

Answer 1

Un caso natural de "error de prueba de mutación" es un algoritmo para la transposición de matrices. Para hacerlo más adecuado para un bucle for, agregue algunas restricciones a esta tarea: deje que la matriz sea no cuadrada y exija que la transposición esté en su lugar. Estas restricciones hacen que una matriz unidimensional sea el lugar más adecuado para almacenar la matriz y se puede usar un bucle for (comenzando, usualmente, desde el índice '1') para procesarlo. Si lo comienza desde el índice '0', nada cambia, porque el elemento superior izquierdo de la matriz siempre se transpone a sí mismo.

Para obtener un ejemplo de dicho código, consulte answer to other question (no en C#, lo siento).

Aquí falla la prueba de "mutación por uno", la refacturación de la prueba no la modifica. No sé si el código en sí puede ser refactorizado para evitar esto. En teoría, puede ser posible, pero debería ser muy difícil.

---

El fragmento de código al que me he referido anteriormente no es un ejemplo perfecto. Todavía se puede refactorizar si el bucle for se sustituye por dos bucles anidados (como si se tratara de filas y columnas) y luego estas filas y columnas se vuelven a calcular en un índice unidimensional. Aún así, da una idea de cómo hacer un algoritmo, que no se puede refactorizar (aunque no es muy significativo).

iterar a través de una matriz de enteros positivos en el orden creciente de los índices, para cada índice calcular su par como i + i % a[i], y si no es fuera de los límites, intercambiar estos elementos:

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

Aquí de nuevo un [ 0] es "inamovible", refactorizar la prueba no cambia esto, y la refacturación del código en sí es prácticamente imposible.

---

Un ejemplo más "significativo". Implementemos un Montículo Binario implícito. Por lo general, se coloca en una matriz, comenzando desde el índice '1' (esto simplifica muchos cálculos Binarios Heap, en comparación con partir del índice '0'). Ahora implementa un método de copia para este montón. El problema de "uno a uno" en este método de copia es indetectable porque el índice cero no se utiliza y C# inicia todas las matrices. Esto es similar a la suma de arreglos de OP, pero no se puede refactorizar.

Estrictamente hablando, puede refactorizar toda la clase y comenzar todo desde '0'. Pero cambiar solo el método de "copia" o la prueba no previene la falla de la prueba de "mutación desactivada por uno". La clase Binary Heap se puede tratar simplemente como una motivación para copiar una matriz con el primer elemento no utilizado.

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

Answer 2

Sí, hay muchos, suponiendo que haya entendido su pregunta.

Uno similar a su caso es:

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

Aquí, si se parte de 0, el resultado será 0, pero si se empieza con 1 el resultado debe ser correcta. (¡Aunque no indicará la diferencia entre 1 y 2!).

Answer 3

No del todo seguro de lo que busca exactamente, pero me parece que si cambia/mutar el valor inicial de la suma de 0 a 1, que no supera la prueba:

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; 
} 

Actualización según en comentarios:

El bucle solo no fallará después de la mutación cuando se infringe el bucle invariante en el procesamiento del índice 0 (o en ausencia de este). La mayoría de estos casos especiales se pueden refactorizan fuera del circuito, pero tenga en cuenta la suma de 1/x:

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

Esto funciona bien, pero si mutar el bundary inicial de 1 a 0, la prueba fallará como 1/0 es una operación inválida.

Answer 4

Creo que con este método particular, hay dos opciones. Usted admite que no es adecuado para la prueba de mutaciones debido a esta anomalía matemática, o trata de escribirlo de manera que sea seguro para las pruebas de mutaciones, ya sea refactorizando a la forma que le da, o de alguna otra manera (¿posiblemente recursivo?)

Su pregunta realmente se reduce a esto: ¿hay una situación de la vida real donde nos importa si el elemento 0 está incluido o excluido de la operación de un bucle, y para el cual no podemos escribir una prueba sobre ese específico aspecto? Mi instinto es decir que no.

Su ejemplo trivial puede ser un ejemplo de falta de lo que me refería como prueba de conducción en my blog, escribiendo sobre NinjaTurtles. Es decir, en el caso de que no haya refactorizado este método tanto como debería.