Property-based Testing mit JUnit QuickCheck

Algorithmen mit PBT testen

Property-based Testing hört sich nach einer interessanten Alternative zu klassischen Tests mit Beispielwerten an, aber in der Praxis stellt man fest, dass sich nicht alle Algorithmen für diesen Ansatz eignen. Unter anderem stellt sich die Frage, wie sich Funktionen wie die zuvor verwendete Operation isPrime() testen lassen, die nur true oder false liefert? Und welche allgemeinen Eigenschaften sollen Entwickler an den Primzahlen prüfen, ohne den produktiven Algorithmus im Test nachzuprogrammieren? Im Folgenden werden fünf Ansätze gezeigt, um Property-based Tests zu entwickeln, wenn die Antwort nicht offensichtlich ist.

Hin und wieder zurück

Immer wenn es für einen Algorithmus eine passende Gegenoperation gibt, eignet sich der Algorithmus hervorragend für PBT. Der Test kann die eigentliche Operation ausführen und mit dem Ergebnis die Gegenoperation starten. Deren Ergebnis sollte wieder dem Startwert entsprechen. Und das sollte für alle zufälligen Eingangswerte gelten.

Operationen mit passenden Gegenoperationen lassen sich gut testen (Abb. 2).

Als Praxisbeispiel sei eine JSON-Serialisierung genannt, die aus Objekten ein JSON-Dokument erstellt. Der passende Deserialisierer sollte nun aus der JSON-Darstellung wieder das Ursprungsobjekt erzeugen. Ein Beispiel für einen solchen Test zeigt folgender Code:

@Property
public void allNamesShouldBeSerializable(String str)
{
JsonSerializer sut = new JsonSerializer();
JsonDeserializer de = new JsonDeserializer();
Name name = new Name(str);
assertThat(de.fromJson(sut.toJson(name)))
.isEqualTo(name);
}

Verschiedene Pfade zum gleichen Ziel

Wenn sich mehrere Algorithmen in beliebiger Reihenfolge verketten lassen, können Tester die Ergebnisse der unterschiedlichen Pfade miteinander vergleichen. Beispielsweise sollte beim Filtern einer Liste die Reihenfolge der angewendeten Filter für das Endergebnis irrelevant sein.

Verschiedene Wege zum gleichen Ziel lassen sich vergleichen (Abb. 3).

Filtert ein Codeausschnitt eine Liste mit Personen zuerst nach deren Geschlecht und im Anschluss nach ihrem Alter, sollte die Ergebnisliste genauso aussehen wie eine zuerst nach Alter und anschließend nach Geschlecht gefilterte Liste. Folgender Code erzeugt die Person-Objekte mit einem eigenen Generator, der lediglich eine Methode überschreibt, um Personen mit zufälligen Namen und Altern zu erzeugen:

@Property
public void applyingFiltersShouldBeCommutative(
List<@From(PersonGenerator.class) Person> people)
{
assertThat(
people.stream()
.filter(p -> p.getAge() < 20)
.filter(p -> p.getGender() == Gender.Male)
.collect(Collectors.toList()))
.isEqualTo(
people.stream()
.filter(p -> p.getGender() == Gender.Male)
.filter(p -> p.getAge() < 20)
.collect(Collectors.toList()));
}

Unveränderbar: Invarianten

Einige Algorithmen geben Eigenschaften vor, die jedes Ergebnis haben muss. Unabhängig vom konkreten Ergebnis des Algorithmus, müssen bestimmte Eigenschaften der Ergebnisse immer gelten. Das sind die sogenannten Invarianten, die sich hervorragend mit PBT testen lassen.

Invariante Eigenschaften aller Ergebnisse lassen sich gut testen (Abb. 4).

Ein mögliches Beispiel ist ein Hashing-Algorithmus wie SHA256. Für jeden Eingangswert muss der Algorithmus einen komplett unterschiedlichen Hash erzeugen. Allerdings müssen alle Hashes exakt 64 Hexadezimalzeichen lang sein. Diese Eigenschaften überprüft folgender Code:

@Property
public void sha256HashesMustAlwaysBe64HexCharactersLong(
String text)
{
String hash = new Hasher().hashWithSha256(text);
assertThat(hash.length()).isEqualTo(64);
assertThat(hash).matches("[0-9A-F]+");
}

Idempotente Operationen

Einige Operationen lassen sich beliebig oft hintereinander aufrufen, ohne das Endergebnis zu verändern. Damit gelten sie als idempotent. Tester können gut PBT verwenden, indem sie mehrere Aufrufe desselben Algorithmus mit dem Ergebnis des ersten Aufrufs vergleichen.

Idempotente Operationen lassen sich gut testen (Abb. 5).

Als Beispiel dient die Sortierung einer Liste. Unabhängig davon, wie oft der Algorithmus zum Einsatz kommt: Die einmal sortierte Liste bleibt sortiert. Folgender Code zeigt einen Test dieser Eigenschaft:

@Property
public void sortedListsShouldStaySorted(
List<@From(PersonGenerator.class) Person> people)
{
assertThat(sort(people))
.isEqualTo(sort(sort(people)));
}

Vergleich unterschiedlicher Implementierungen

Wenn für einen zu entwickelnden Algorithmus eine alternative Implementierung existiert, können Entwickler den eigenen Algorithmus mit der existierenden Referenzimplementierung vergleichen.

Mehrere Implementierungen des gleichen Algorithmus können miteinander verglichen werden (Abb. 6).

Soll ein Codeausschnitt beispielsweise zu zwei Zahlen den größten gemeinsamen Teiler ermitteln, kann er auf die Primfaktorzerlegung setzen, deren Implementierung allerdings relativ langsam ist. Liegt sie aber korrekt programmiert vor, können Entwickler sie als Referenz für die Umsetzung des euklidischen Algorithmus nutzen. Dessen Ergebnisse müssen mit der funktionierenden Variante der Primfaktorzerlegung übereinstimmen. Auf die Weise lässt sich sicherstellen, dass die neue Implementierung ebenso funktioniert wie die vorhandene:

@Property
public void euklidAndPrimeFactorsShouldYieldSameResult(
@InRange(min = "2", max = "999999999999") long a,
@InRange(min = "2", max = "999999999999") long b)
{
GreatestCommonDivisorCalculator sut = new GreatestCommonDivisorCalculator();
assertThat(sut.euklid(a, b))
.isEqualTo(sut.primeFactors(a, b));
}