Improve list shrinking?

[jockbert]

Is there a way to guide/force/improve the shrinking of lists, using the QuickTheories API?

In my test case, I execute a series of commands to an API. The test case usually finds a series of commands that make the API fail. However it is usually only one or two commands that is the root cause, but the list generator seem to have trouble shrinking the command list in a effective way. The shrinking get stuck on lists with a certain length while there still is a lot more of the list that can be shrunk. It might not be a problem on lists of length < 10 but on list lengths > 100 it is a problem.

I get output like this (relatively short list):

java.lang.AssertionError: Property falsified after 16 example(s) 
Smallest found falsifying value(s) :-
[CmdA, CmdA, CmdA, CmdA, CmdA, CmdA, FailingCmdB]

while it would fail with a single [FailingCmdB].

Abbreviated test code:

  @Test
  public void probeApi()
  {
    qt()
      .withExamples(100)
      .withShrinkCycles(10000)
      .forAll(commandListGen()))
      .checkAssert(commands -> ... );
  }

  private Gen<List<ICommand>> commandListGen()
  {
    Gen<ICommand> cmdGen = arbitrary().pick(allPossibleCommandsList());
    return lists().of(cmdGen).ofSizeBetween(0, 200);
  }

[hcoles]

It should be possible to improve the shrinking, the strategy at the moment is fairly simple.

https://github.com/ncredinburgh/QuickTheories/blob/master/core/src/main/java/org/quicktheories/impl/SimpleShrink.java

The input array (from which all types are generated) is shrunk by picking a random long and reducing it. If it is unable to do so then two bytes are reduced.

By convention the first generated long is used to pick the size of an array/collection/string etc, so a tweak to the strategy that increased the probability of the first long being reduced should result in shorter lists.

Experimentation would be required.

[jockbert]

Ok, noted. Looked in SimpleShrink.java earler, but did not understand much. The shrinking strategy differs from e.g. ScalaCheck where you explicitly can define how to shrink something.

Clarification for other readers, regarding the earlier mentioned example. CmdA is in the example the first element in allPossibleCommandsList(), so it seems that arbitrary().pick(List<T>) shrinks in respect to order in given list.

A workaround for bad list shrinking is to add a fake "no operation item" (NOOP) as first element in list to choose from, in my case in allPossibleCommandsList(). For long lists, the shrinking phase spend an awful lot of time to shrink list items down to NOOP, but these can at least be filtered out in test report using describedAs, like this:

  @Test
  public void probeApi()
  {
    qt()
      .withExamples(100)
      .withShrinkCycles(10000)
      .forAll(commandListGen()))
      .describedAs(filterOutNoopDescription())
      .checkAssert(commands -> ... );
  }

[hcoles]

Pick will shrink towards the first element supplied. You can use the clumbsily named org.quicktheories.generators.Generate.pickWithNoShrinkPoint to pick without any assumed order.

Shrinking in quicktheories is fundamentally different than in scalacheck as it is not tied to (or aware of) types. This has the advantage that generators can be composed together and shrinking will magically work (we avoid this type of problem https://github.com/rickynils/scalacheck/issues/317), but it does mean it is difficult to optimise for specific cases.

[ANorwell]

There's currently no mechanism to inject an alternative ShrinkStrategy.

[jockbert]

Thanks for all the answers. Since list shrinking by removing all unnecessary elements in list was essential for solving the problem at hand, I had to abandon QuickTheories and instead roll my own Java-based PBT-tool for those commands-against-API-testing scenarios. QuickTheories is still kept for all other PBT-testing ;-)

From my point of view, this is not a problem any more and I'll close this issue.

Side notes: The company I did this work on is unfortunately not big on sharing code and no, using ScalaCheck straight up in testing would have been too much of a leap for my co-workers (I think).

[jlink]

Thanks for all the answers. Since list shrinking by removing all unnecessary elements in list was essential for solving the problem at hand, I had to abandon QuickTheories and instead roll my own Java-based PBT-tool for those commands-against-API-testing scenarios. QuickTheories is still kept for all other PBT-testing ;-)

Did you look at the other existing Java-based PBT libs before rolling your own? https://jqwik.net und junit-quickcheck are probably most relevant.

[jockbert]

@jlink, I thought that I in 2018 had a good grasp on the PBT-library landscape in Java, and it would surprise me if I did not do some survey on it. However, I don't remember why I didn't go for any of the two. Maybe it was the integration with JUnit5 that sorted out Jqwik at the time. At a glance, both look like good alternatives today.