How to test the identity and an associativity constraints of a java-8 custom Collector

Question

I have written a custom Collector for Java 8. Its aggregator is a Map containing a pair of lists:

    @Override
    public Supplier<Map<Boolean, List<Object>>> supplier() {
        return () -> {
            Map<Boolean, List<Object>> map = new HashMap<>(2);
            map.put(false, new ArrayList<>());
            map.put(true, new ArrayList<>());
            return map;
        };
    }

so I think its combiner is this:

    @Override
    public BinaryOperator<Map<Boolean, List<Object>>> combiner() {
        return (a, b) -> {
            a.get(false).addAll(b.get(false));
            a.get(true).addAll(b.get(true));
            return a;
        };
    }

I would like to test the Collector to make sure that if and when it processes a stream in parallel, the result is correct.

How can I write a unit test that exercises this?

Of course I can write a test that calls the combiner directly, but that's not what I want. I want evidence it works in the context of collecting.

The Javadoc for Collector says:

To ensure that sequential and parallel executions produce equivalent results, the collector functions must satisfy an identity and an associativity constraints.

Could I achieve confidence in my Collector by testing these constraints? How?

Answer 1

You are basically asking if List.addAll is associative. Because the identity is trivially solved by Object.equals, which each standard collection (that you use) guarantees to follow.

Associativity

Associativity means the following:

Within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value. Consider the following equations:

(2 + 3) + 4 = 2 + (3 + 4) = 9
2 × (3 × 4) = (2 × 3) × 4 = 24

-- Wikipedia

Yes List.addAlls is associative.

Let's show it by example:

import java.util.*;
public class Main {
  // Give addAll an operator look.
  static <T> List<T> myAddAll(List<T> left, List<T> right) {
    List<T> result = new ArrayList<>(left);
    result.addAll(right);
    return result;
  }
  public static void main(String[] args) {
    List<Integer> a = Arrays.asList(1, 2, 3);
    List<Integer> b = Arrays.asList(4, 5, 6);
    List<Integer> c = Arrays.asList(7, 8, 9);

    // Combine a and b first, then combine the result with c.
    System.out.println(myAddAll(myAddAll(a, b), c)); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

    // Combine b and c first, then combine a with the result.
    System.out.println(myAddAll(a, myAddAll(b, c))); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
  }
}

Testing

The contract for Collector is exactly what you wrote: make sure that the combiner has both the identity and the associativity properties. If you follow that, you won't get any issue (make sure you hint that your Spliterator is ORDERED if required, of course).

The test then boils down to simply test that your combiner has those two properties. The identity part is guaranteed by equals, the associativity part is handled by writing a test similar to the code above. It boils down to that because, as @mrmcgreg said in the comments, you shouldn't test the framework itself: that's the Java authors' responsibility. If you would encounter any trouble after having proved your combiner fulfills the two properties, you should probably file a bug to Java.