Изключени от една грешки и тестване на мутации

В процеса на писане на тестер за мутации „Off By One“ за любимата ми рамка за тестване на мутации (NinjaTurtles), аз написа следния код, за да предостави възможност за проверка на коректността на моята реализация:

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

сега това изглежда достатъчно просто и не ми направи впечатление, че ще има проблем при опит за мутиране на всички буквални целочислени константи в IL. В крайна сметка има само 3 (0, 1 и ++).

ГРЕШНО!

При първото изпълнение стана много очевидно, че никога няма да работи в този конкретен случай. Защо? Тъй като промяната на кода на

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

само добавя 0 (нула) към сумата и това очевидно няма ефект. Друга история, ако беше множеството, но в този случай не беше.

Сега има доста лесен алгоритъм за изчисляване на сумата от цели числа

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

което бих могъл лесно да проваля мутациите, тъй като добавянето или изваждането на 1 от която и да е от константите там ще доведе до грешка. (като се има предвид, че max >= 0)

И така, проблемът е решен за този конкретен случай. Въпреки че не направи това, което исках за теста на мутацията, който беше да провери какво ще се случи, когато загубя ++ - на практика безкраен цикъл. Но това е друг проблем.

И така - Моят въпрос: Има ли някакви тривиални или нетривиални случаи, при които цикъл, започващ от 0 или 1, може да доведе до неуспех на теста „мутация изключена с единица“, която не може да бъде преработена (тестван код или тест) по подобен начин? (примери моля)

Забележка: Тестовете за мутация са неуспешни, когато пакетът от тестове премине успешно след прилагане на мутация.

Актуализация: пример за нещо по-малко тривиално, но нещо, което все още може да преработи теста, така че да се провали, ще бъде следното

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

    return sum;
}

Тестът за мутация срещу този код би се провалил при промяна на var i=0 на var i=1, ако тестовият вход, който сте му дали, е new[] {0,1,2,3,4,5,6,7,8,9}. Променете обаче тестовия вход на new[] {9,8,7,6,5,4,3,2,1,0} и тестът за мутация ще се провали. Така че успешният рефактор доказва тестването.


person pms1969    schedule 30.04.2012    source източник


Отговори (4)


Един естествен случай на "неуспешен тест за мутация" е алгоритъм за транспониране на матрица. За да я направите по-подходяща за единичен for-цикъл, добавете някои ограничения към тази задача: оставете матрицата да не е квадратна и да изисква транспонирането да е на място. Тези ограничения правят едномерния масив най-подходящото място за съхраняване на матрицата и for-цикъл (започващ обикновено от индекс '1') може да се използва за обработката му. Ако започнете от индекс '0', нищо не се променя, защото горният ляв елемент на матрицата винаги се транспонира към себе си.

За пример на такъв код вижте отговор на друг въпрос (не в C#, съжалявам).

Тук тестът "изключване на мутация с един" е неуспешен, рефакторингът на теста не го променя. Не знам дали самият код може да бъде преработен, за да се избегне това. На теория може да е възможно, но трябва да е твърде трудно.


Кодовият фрагмент, който споменах по-рано, не е перфектен пример. Все още може да бъде преработено, ако цикълът for е заменен с два вложени цикъла (като за редове и колони) и след това тези редове и колони се преизчисляват обратно към едномерен индекс. Все пак дава идея как да се направи някакъв алгоритъм, който не може да се преработи (макар и не много смислен).

Преминете през масив от положителни цели числа в реда на увеличаване на индексите, за всеки индекс изчислете неговата двойка като i + i % a[i] и ако не е извън границите, разменете тези елементи:

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

Тук отново a[0] е "неподвижен", рефакторингът на теста не променя това и рефакторингът на самия код е практически невъзможен.


Още един "смислен" пример. Нека имплементираме имплицитна двоична купчина. Обикновено се поставя в някакъв масив, като се започне от индекс '1' (това опростява много изчисления на двоична купчина, в сравнение със започването от индекс '0'). Сега внедрите метод за копиране за тази купчина. Проблемът "Off-by-one" в този метод на копиране е неоткриваем, тъй като нулевият индекс не се използва и C# нула-инициализира всички масиви. Това е подобно на сумирането на масива на OP, но не може да се преработи.

Строго погледнато, можете да преработите целия клас и да започнете всичко от '0'. Но промяната само на метода „копиране“ или на теста не предотвратява неуспеха на теста „изключване на мутация с едно“. Класът Binary Heap може да се третира просто като мотивация за копиране на масив с неизползван първи елемент.

int[] dst = new int[src.Length];
for (var i = 1; i < src.Length; i++)
{
    dst[i] = src[i];
}
person Evgeny Kluev    schedule 03.05.2012
comment
И така, смислена кодова задача, при която започването от индекс 0 или 1 има същия ефект, защото, както в случая на сумиране, операцията върху индекс 0 няма ефект. И в този случай, без да се прибягва до външна библиотека за матрични изчисления, няма рефактор - ако приемем, че приемате за даденост използването на едномерен масив. Интересно - размишлявам върху това. - person David M; 03.05.2012
comment
@evgeny - Току-що се запознах с оригиналния ти пост. Но си струваше. Взех C++, направих го C# и си играех. Първоначално бях напълно объркан как да преработя, за да постигна резултат, който може да бъде доказуем чрез тестване на мутации. В крайна сметка имах своя момент на електрическа крушка и това се отнася и за този пример. Прилагането на известна неизменност към метода тук върши чудеса. Така че вместо void, върнете char[] и имате някакъв доказуем код и вероятно метод, който е изключително по-добър за опита. - person pms1969; 04.05.2012
comment
@pms1969, нали, неизменността помага тук. Но премахва ограничението на място за алгоритмите. Не мисля, че е възможно алгоритъм, модифициран по този начин, да се третира като същия алгоритъм. За матрично транспониране има много прост алгоритъм не на място, но всички алгоритми на място са доста напреднали. Между другото, току-що добавих още един пример, който вече е неизменен. - person Evgeny Kluev; 04.05.2012
comment
И бих се съгласил с коментара за ограничението на място, но може би ще трябва да се запитаме защо го има това ограничение, когато пишем собствен код? По-простият код е по-лесен за поддръжка и преработване. И фактът, че тестването на мутации не може да докаже алгоритъма на място, може да ви накара да преразгледате своя дизайн (кралския ви там). Единственият път, когато мога да се сетя къде ограничението може да е валидно, е да работя върху огромни набори от данни, които могат да взривят паметта ви, ако бъдат копирани. - person pms1969; 04.05.2012
comment
ДОБРЕ. Добавен е кодът за самото копиране. Надяваме се, че не е необходимо писане на реализация на целия клас. Не използвах Array.Copy, защото в този случай няма какво да тествам. Що се отнася до ограничението на място, единственото нещо, което има значение за транспонирането на матрицата, е огромният набор от данни. За други алгоритми ограничението на място може да има други предимства. По-добре е да промените 10% от набора от данни, отколкото да го копирате целия. (Поне това е вярно за императивните езици; функционалните езици използват свързани структури, където неизменността е по-удобна). - person Evgeny Kluev; 04.05.2012
comment
Благодаря за това Евгени. Мисля, че успяхте да демонстрирате някои нетривиални примери, което всъщност преследвахме Пол и аз. Мислете, че сте спечелили бонуса. :) - person David M; 09.05.2012
comment
абсолютно. Много оценявам. - person pms1969; 11.05.2012

Мисля, че с този конкретен метод има два избора. Вие или признавате, че не е подходящ за тестване на мутации поради тази математическа аномалия, или се опитвате да го напишете по начин, който го прави безопасен за тестване на мутации, или чрез преработване на формата, която давате, или по някакъв друг начин (вероятно рекурсивен? ).

Вашият въпрос всъщност се свежда до следното: има ли ситуация в реалния живот, в която ни интересува дали елемент 0 е включен или изключен от операцията на цикъл, и за която не можем да напишем тест около този конкретен аспект< /strong>? Инстинктът ми е да кажа не.

Вашият тривиален пример може да е пример за липса на това, което нарекох тестово управление в моя блог, пиша за NinjaTurtles. Това означава в случай, че не сте преработили този метод доколкото трябва.

person David M    schedule 30.04.2012
comment
Точно. Моят инстинкт също е не. Един нетривиален пример винаги трябва да се провали, ако промените началната константа на for цикъл, и подозирам, че моят измислен пример е само един от шепата действителни случаи, които няма да се провалят, когато се промени. Предполагам, че дори един тривиален пример, който не може да бъде преработен, би представлявал интерес. Ще променя въпроса. - person pms1969; 30.04.2012

Да, има много, ако приемем, че съм разбрал въпроса ви.

Един подобен на вашия случай е:

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

Тук, ако започне от 0, резултатът ще бъде 0, но ако започне от 1, резултатът трябва да е правилен. (Въпреки че няма да направи разликата между 1 и 2!).

person Justin    schedule 30.04.2012
comment
Мисля, че OP е след нетривиален пример, който се проваля при тестване за мутация - този преминава, защото начало на цикъл от i = 0 дава резултат 0, а начало на цикъл от i = 1 дава ненулев резултат. - person David M; 30.04.2012
comment
Това има повече смисъл...Така че неговият въпрос наистина казва, Ето един пример за това, което търся, но има ли друг случай, който е по-малко тривиален? - person Justin; 30.04.2012
comment
добре, всъщност, като го погледнем, мутацията на var i = 1 до var i = 2 ще се провали, тъй като умножението по 1 няма ефект върху отговора. Все пак доста измислен отговор. Има ли рефактор, който може да работи тук? - person pms1969; 30.04.2012
comment
Да, има рефактор, който може да работи тук. Направете метода рекурсивен. - person David M; 02.05.2012

Не съм съвсем сигурен какво точно търсите, но ми се струва, че ако промените/мутирате първоначалната стойност на sum от 0 на 1, трябва да се провалите на теста:

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

Актуализация въз основа на коментари:

Цикълът няма да се провали само след мутация, когато инвариантът на цикъла е нарушен при обработката на индекс 0 (или при липсата му). Повечето такива специални случаи могат да бъдат преработени извън цикъла, но помислете за сумиране от 1/x:

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

Това работи добре, но ако промените първоначалния пакет от 1 на 0, тестът ще се провали, тъй като 1/0 е невалидна операция.

person Attila    schedule 30.04.2012
comment
Да, така ще, но това е for цикълът, който ме интересува тук. - person pms1969; 30.04.2012
comment
Доколкото разбирам въпроса ви, ако всички операции в рамките на цикъла са валидни, тогава няма разлика между започване от 0 или 1 (резултатът очевидно може да е различен, но инвариантът (с модифицираните граници) ще се запази). Можете ли да направите i <= max+0? Ако това е ОК, мутирането му на i<=max+1 може да е невалидно (напр. свръхиндексиране на масив) - person Attila; 30.04.2012
comment
така че константите тук са нещата, които мутират и сте прав, прекомерното индексиране може да причини неуспех (но не мисля, че можем да го гарантираме с примера за сумата. Ще редактирам публикацията, за да дам пример за нещо, което е по-малко тривиално и би се провалило с определени входни данни. Самият тест може да бъде преработен, така че входните данни след това да се провалят на теста, и по този начин се постига добро покритие/тестване. - person pms1969; 30.04.2012
comment
Друга възможност е, че цикълът изисква да започнете от 0 (напр. стъпка 0 е някакъв вид инициализация), тогава мутацията ще доведе до неуспех на теста - person Attila; 30.04.2012
comment
които след това могат да бъдат преработени, за да направят инициализацията извън цикъла. Освен ако не можете да си представите пример, че не може? - person pms1969; 30.04.2012
comment
Ако вашият инвариант на цикъла е такъв, че се поддържа както когато започнете от 0, така и когато започнете от 1, няма начин да се провалите с вашата мутация off-by-one. Ако цикълът е такъв, че се поддържа само ако започвате от 0 (еквивалентно: само ако стартирате форма 1), тогава вашата мутация няма да премине теста. Наличието на специален случай при стойност 0, който трябва (еквивалент: не трябва) да обработвате, ще доведе до това, което търсите. Друг специален случай: сума от реципрочни числа: 1/0 не трябва да се изчислява, но 1/i i=[1,...n] е ОК. - person Attila; 30.04.2012
comment