Property based testing for a custom ordered list in Java

Question

Given the following ordering requirement:

All strings starting with "foo" should be first.

All string starting with "bar" should be last.

Strings that do not start with "foo" or "bar" can also be present in the list.

How can one use Property-Based Testing to test an implementation of the above requirements without getting a headache?

Is there some thing more elegant then the following:

List<String> strings = Arrays.asList("foo", "bar", "bar1", "jar");
Collections.shuffle(strings);
assertListStartWith(strings, "foo");
assertListEndsWith(strings, "bar", "bar1");
assertThat(strings, hasItem( "jar"));

Answer 1

I assume that you have some sorter function with signature

List<String> sortFooBar(List<String> list)

I see at least five properties that sortFooBar(list) should fulfill:

1. Keep all items - and only those - in the list
2. No item before first "foo"
3. No other items between first and last "foo"
4. No item after last "bar"
5. No other item between first and last "bar"

In a real functional language those properties are all rather easy to formulate in Java it requires a bit of code. So here's my take on the problem using jqwik as PBT framework and AssertJ for assertions:

import java.util.*;
import java.util.function.*;
import org.assertj.core.api.*;
import net.jqwik.api.*;

class MySorterProperties {
    
    @Property
    void allItemsAreKept(@ForAll List<@From("withFooBars") String> list) {
        List<String> sorted = MySorter.sortFooBar(list);
        Assertions.assertThat(sorted).containsExactlyInAnyOrderElementsOf(list);
    }
    
    @Property
    void noItemBeforeFoo(@ForAll List<@From("withFooBars") String> list) {
        List<String> sorted = MySorter.sortFooBar(list);
        int firstFoo = findFirst(sorted, item -> item.startsWith("foo"));
        if (firstFoo < 0) return;
        Assertions.assertThat(sorted.stream().limit(firstFoo)).isEmpty();
    }
    
    @Property
    void noItemBetweenFoos(@ForAll List<@From("withFooBars") String> list) {
        List<String> sorted = MySorter.sortFooBar(list);
        int firstFoo = findFirst(sorted, item -> item.startsWith("foo"));
        int lastFoo = findLast(sorted, item -> item.startsWith("foo"));
        if (firstFoo < 0 && lastFoo < 0) return;
        List<String> allFoos = sorted.subList(
            Math.max(firstFoo, 0),
            lastFoo >= 0 ? lastFoo + 1 : sorted.size()
        );
        Assertions.assertThat(allFoos).allMatch(item -> item.startsWith("foo"));
    }
    
    @Property
    void noItemAfterBar(@ForAll List<@From("withFooBars") String> list) {
        List<String> sorted = MySorter.sortFooBar(list);
        int lastBar = findLast(sorted, item -> item.startsWith("bar"));
        if (lastBar < 0) return;
        Assertions.assertThat(sorted.stream().skip(lastBar + 1)).isEmpty();
    }
    
    @Property
    void noItemBetweenBars(@ForAll List<@From("withFooBars") String> list) {
        List<String> sorted = MySorter.sortFooBar(list);
        int firstBar = findFirst(sorted, item -> item.startsWith("bar"));
        int lastBar = findLast(sorted, item -> item.startsWith("bar"));
        if (firstBar < 0 && lastBar < 0) return;
        List<String> allFoos = sorted.subList(
            Math.max(firstBar, 0),
            lastBar >= 0 ? lastBar + 1 : sorted.size()
        );
        Assertions.assertThat(allFoos).allMatch(item -> item.startsWith("bar"));
    }
    
    @Provide
    Arbitrary<String> withFooBars() {
        Arbitrary<String> postFix = Arbitraries.strings().alpha().ofMaxLength(10);
        return Arbitraries.oneOf(
            postFix, postFix.map(post -> "foo" + post), postFix.map(post -> "bar" + post)
        );
    }
    
    int findFirst(List<String> list, Predicate<String> condition) {
        for (int i = 0; i < list.size(); i++) {
            String item = list.get(i);
            if (condition.test(item)) {
                return i;
            }
        }
        return -1;
    }
    
    int findLast(List<String> list, Predicate<String> condition) {
        for (int i = list.size() - 1; i >= 0; i--) {
            String item = list.get(i);
            if (condition.test(item)) {
                return i;
            }
        }
        return -1;
    }
}

And this is a naive implementation that is consistent with the spec:

class MySorter {
    static List<String> sortFooBar(List<String> in) {
        ArrayList<String> result = new ArrayList<>();
        int countFoos = 0;
        for (String item : in) {
            if (item.startsWith("foo")) {
                result.add(0, item);
                countFoos++;
            } else if (item.startsWith("bar")) {
                result.add(result.size(), item);
            } else {
                result.add(countFoos, item);
            }
        }
        return result;
    }
}

In this example the code for the properties exceeds the amount of code for the implementation. This might be good or bad depending on how tricky the desired behaviour is.