Logo von Developer

Suche
preisvergleich_weiss

Recherche in 2.383.371 Produkten

Johannes Dienst 6

Quicksort als Testbeispiel

Unit-Tests gehören bei vielen Entwicklern zur täglichen Arbeit als Schutz vor Regressionen und als lebende Dokumentation. Aber wie lässt sich die Qualität der Tests überprüfen?

Das Mutationstesttool PIT ist für Java spezialisiert. Für andere Programmiersprachen existieren zahlreiche nützliche Tools wie Stryker, Humbug, Mutant und Mucheck.

PIT stand früher für Parallel Isolated Tests und trug damit die Parallelisierung im Namen. Der Autor des Tools hat es dann erweitert, um die spannendere Aufgabenstellung der Mutationstests abzudecken.

PIT hat gegenüber anderen Werkzeugen einige Vorteile: Der Macher entwickelt es aktiv weiter, und es ist im Vergleich zu früheren Generationen von Tools um ein Vielfaches schneller. Dadurch taugt PIT durchaus für den Einsatz in realen Projekten. Weitere Vorzüge sind die leichte Integrierbarkeit in Entwicklungsumgebungen und ein aktiv entwickeltes SonarQube-Plug-in. Außerdem lässt es sich umfangreich konfigurieren, und es unterstützt inkrementelle Analysen. Dadurch eignet es sich für den Einsaz zur Entwicklungszeit in der testgetriebenen Entwicklung.

Als kleine Demonstration dient die Überprüfung der Tests einer Implementierung von Quicksort, die dafür eine kleine Überarbeitung erfahren hat.

static List<Integer> sort(List<Integer> numbers) {
if (numbers.size() <= 1)
return numbers;

int pivot = numbers.size() / 2;
List<Integer> lesser = new ArrayList<>();
List<Integer> greater = new ArrayList<>();
int sameAsPivot = 0;

for (int number : numbers) {
if (number > numbers.get(pivot))
greater.add(number);
else if (number < numbers.get(pivot))
lesser.add(number);
else
sameAsPivot++;
}

lesser = sort(lesser);
for (int i = 0; i < sameAsPivot; i++)
lesser.add(numbers.get(pivot));

greater = sort(greater);
List<Integer> sorted = new ArrayList<>();
for (int number : lesser)
sorted.add(number);
for (int number: greater)
sorted.add(number);

return sorted;
}

Eine auf den ersten Blick vernünftige Testsuite dafür könnte in etwa folgendermaßen aussehen:

public class Quicksort_Test {
@Test public void emptyList() {
assertEquals(true,
sort(Collections.<Integer>emptyList()).
isEmpty());
}

@Test public void oneList() {
assertEquals(false,
sort(Stream.of(42).
collect(Collectors.toList())).isEmpty());
}

@Test public void twoList() {
assertEquals(new Integer(1),
sort(Stream.of(2, 3, 1, 8).
collect(Collectors.toList())).get(0));
}
}

Mit dieser Vorbereitung kann PIT nach einem Durchlauf einen Report erstellen, der in Abbildung 2 zu sehen ist. Aus der Übersicht geht hervor, dass die Suite eine Klasse getestet hat, in der eine Zeilenüberdeckung von 96% vorliegt, und dabei 11 von 16 Mutanten aufgespürt hat. Das bedeutet, dass sie fünf mögliche Regressionen nicht finden kann. Die Übersicht eignet sich dazu, ein generelles Gefühl für den Zustand der Testsuite zu erhalten.

Übersicht des PIT-Reports zum Mutationstest (Abb. 2)
Übersicht des PIT-Reports zum Mutationstest (Abb. 2)

Interessanter ist der Detailreport zur Klasse Quicksort, der ausschnittsweise in Abbildung 3 zu sehen ist. Hellgrün hinterlegte Zeilen bedeuten, dass die Testsuite sie überdeckt. Hellrot zeigt ein Fehlen der Zeilenüberdeckung an. Der Report gibt die möglichen Mutationen für unüberdeckte Zeilen zwar an, aber PIT verzichtet auf das Erstellen der Mutanten, da die Testsuite sie nie finden kann. Damit verhindert das Tool unnötige Arbeit und verringert gleichzeitig die Durchlaufzeit. Dunkelgrüne Zeilen bedeuten, dass von ihnen eine oder mehrere Mutanten erstellt und alle von der Testsuite getötet wurden. Dunkelrote Zeilen zeigen Mutationen auf, die der Testsuite verborgen geblieben sind.

Detailreport über die Mutationsüberdeckung von Quicksort (Abb. 3)
Detailreport über die Mutationsüberdeckung von Quicksort (Abb. 3)

Der Report gibt nicht nur Auskunft über das Einfügen von Mutationen. Ein Überfahren der Zahl auf der linken Seite mit der Maus verrät zudem, was PIT verändert hat. Die Zahl gibt an, wie viele Mutationen in der jeweiligen Zeile möglich sind. In Abbildung 4 zeigt der Mouseover, dass von der for-Schleife drei Mutanten existieren. Die Mutationen eins und drei führen zu Regressionen. Leider wird von der Testsuite nur die dritte gefunden, bei der das Pivot-Element nicht in der Ergebnisliste auftaucht. Mutation eins führt zu einem doppelten Auftreten des Pivot-Elements in der Ergebnisliste und wird nicht getötet.

Ein Blick in die Testsuite zeigt, dass sie im dritten Test lediglich das erste Element überprüft. Das Erweitern des Test auf alle Elemente oder das zusätzliche Prüfen der Listenlänge tötet auch die dritte Mutation.

Der Report zeigt für jede Zeile an, welche Mutanten erstellt wurden und ob sie überlebt haben. TIMED_OUT steht für Mutanten, die Endlosschleifen erzeugen (Abb. 4).
Der Report zeigt für jede Zeile an, welche Mutanten erstellt wurden und ob sie überlebt haben. TIMED_OUT steht für Mutanten, die Endlosschleifen erzeugen (Abb. 4).

Mutationstests in realen Projekten

Reale Projekte lassen sich nicht so leicht einem Mutationstest unterziehen wie das überschaubare Quicksort-Beispiel. Schon bei mehreren tausend Zeilen Code und einer entsprechenden Testüberdeckung von über 80 % entsteht eine große Anzahl von erzeugten Mutanten. In einem realen Projekt des Autors mit einem Modul von etwa 3000 Zeilen Umfang und 100 % Testüberdeckung entstanden mehrere Hundert.

Alle Mutanten zu töten und damit eine perfekte Testsuite zu erreichen, ist nicht praktikabel. Es lohnt sich daher, den Fokus auf besonders kritische Stellen zu setzen. PIT bietet außerdem einige Konfigurationsmöglichkeiten an, um eine graduelle Einführung von Mutationstests in ein Projekt zu gewährleisten.

Die Mutationserstellung lässt sich unter anderem gezielt auf einzelne Packages oder Klassen beschränken, was die Ausführungsgeschwindigkeit deutlich erhöht. Das ist insbesondere zur Entwicklungszeit interessant. Außerdem können Tester die Anzahl der Mutationen pro Klasse begrenzen. In Kombination mit der Einschränkung der aktiven Mutatoren reduziert sich die Anzahl der zu tötenden Mutationen.

Für das Erzeugen und Testen aller Mutanten bei einem initialen Lauf von PIT bietet sich die inkrementelle Analyse an. PIT legt dazu eine Datei an, in der es die Ergebnisse und den Ablauf der Analyse speichert. Bei nachfolgenden Läufen mutiert und testet es nur Stellen, an denen sich entweder der Code oder die dazugehörigen Tests verändert haben. Die Ausführungsgeschwindigkeit erhöht sich dadurch deutlich im Vergleich zum initialen Lauf.

Teams, die auf testgetriebene Entwicklung setzen, können Mutationstests ohne erheblichen Zeitaufwand in Kombination mit der inkrementellen Analyse einsetzen. Die Feedbackschleife reduziert sich dadurch auf ein Minimum, und die Testsuite ist von Anfang an gegen Regressionen geschützt.

6 Kommentare

Themen: