pholser/junit-quickcheck

IntegralGenerator shrinker or shrinking implementation seems wrong

sir4ur0n opened this issue · 9 comments

sir4ur0n commented

I think there is a bug either in the IntegralGenerator, or in the shrinking implementation. Example:

@Property(maxShrinks = 100000, maxShrinkTime = 60_000_000, maxShrinkDepth = 5000)
public void testShrink(@When(seed = -4493071121312539862L) int number) {
  assertThat(number).isLessThan(8);
}

The starting point is 849426243 and it never shrinks lower than 424713121 (i.e. more or less divided by 2).
I think this is a bug: given enough time, shrinks and shrink depth (the difference between those 2 is hard to understand by the way), the generator should succeed to identify the smallest value that doesn't pass the property is 8 and not 424713121.

pholser commented

@sir4ur0n What version of junit-quickcheck are you using? When I run your test from the head of 0.8-branch, I get:

java.lang.AssertionError: Property named 'testShrink' failed (
Expected: a value less than <8>
     but: <14> was greater than <8>):
With arguments: [14]
Original failure message: 
Expected: a value less than <8>
     but: <1960355080> was greater than <8>
First arguments found to also provoke a failure: [1960355080]
Seeds for reproduction: [-4493071121312539862]
	at org.hamcrest.MatcherAssert.assertThat(MatcherAssert.java:20)
    ...
sir4ur0n commented

Tested with both 0.8.1 and 0.8.2, I get this:

java.lang.AssertionError: Property named 'testShrink' failed (
Expecting:
 <424713121>
to be less than:
 <8> ):
With arguments: [424713121]
Original failure message: 
Expecting:
 <849426243>
to be less than:
 <8> 
First arguments found to also provoke a failure: [849426243]
Seeds for reproduction: [-4493071121312539862]

	at com.github.sir4ur0n.generator.VavrListGeneratorTest.testShrink(VavrListGeneratorTest.java:51)
	at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier$2.evaluate(PropertyVerifier.java:106)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier$1.evaluate(PropertyVerifier.java:77)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier.verify(PropertyVerifier.java:69)
	at com.pholser.junit.quickcheck.runner.ShrinkNode.verifyProperty(ShrinkNode.java:108)
	at com.pholser.junit.quickcheck.runner.Shrinker.shrink(Shrinker.java:80)
	at com.pholser.junit.quickcheck.runner.PropertyStatement.shrink(PropertyStatement.java:174)
	at com.pholser.junit.quickcheck.runner.PropertyStatement.lambda$property$52(PropertyStatement.java:151)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier$1.evaluate(PropertyVerifier.java:88)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier.verify(PropertyVerifier.java:69)
	at com.pholser.junit.quickcheck.runner.PropertyStatement.evaluate(PropertyStatement.java:111)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
	at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:68)
	at com.intellij.rt.execution.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:47)
	at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:242)
	at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:70)
Caused by: java.lang.AssertionError: 
Expecting:
 <849426243>
to be less than:
 <8> 
	at com.github.sir4ur0n.generator.VavrListGeneratorTest.testShrink(VavrListGeneratorTest.java:51)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier$2.evaluate(PropertyVerifier.java:106)
	at com.pholser.junit.quickcheck.runner.PropertyVerifier$1.evaluate(PropertyVerifier.java:77)
	... 16 more


Process finished with exit code 255

Has there been any fix since 0.8.2 release?

sir4ur0n commented

I have created a repo to showcase the issue: https://github.com/Sir4ur0n/junit-quickcheck-bug-shrinker

$ gradle build
> Task :test FAILED

com.github.sir4ur0n.BugTest STANDARD_ERROR
    SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
    SLF4J: Defaulting to no-operation (NOP) logger implementation
    SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.

com.github.sir4ur0n.BugTest > testShrink FAILED
    java.lang.AssertionError: Property named 'testShrink' failed (
    Expecting:
     <424713121>
    to be less than:
     <8> ):
    With arguments: [424713121]
    Original failure message: 
    Expecting:
     <849426243>
    to be less than:
     <8> 
    First arguments found to also provoke a failure: [849426243]
    Seeds for reproduction: [-4493071121312539862]
        at com.github.sir4ur0n.BugTest.testShrink(BugTest.java:15)

        Caused by:
        java.lang.AssertionError: 
        Expecting:
         <849426243>
        to be less than:
         <8> 
            at com.github.sir4ur0n.BugTest.testShrink(BugTest.java:15)

1 test completed, 1 failed

FAILURE: Build failed with an exception.
pholser commented

Yes, something's a bit squirrely with integral shrinking. Investigating...

sir4ur0n commented

I just debugged and I don't get how this is supposed to converge quickly, would you mind explaining please?
From what I saw:

  • In IntegralGenerator, we build a list of shrinks. The first element is a value close to the original value (e.g. if the input is 849426243 then the first next value tested is 849400320), the second before last is original divided by 2 (424713121) and the last is 0.
  • In Shrinker l.73 we add all those shrinks to the ShrinkNodeQueue. But because of its implementation, and because the last element of the shrinks is 0, the maxMagnitude is modified to 0 when adding the last shrink.
  • In Shrinker l.80 we test in the list order (so we test first 849400320). If this doesn't pass (which it doesn't), it becomes the new smallest and we build again the shrinks, for 849400320 this time. However the method addAll on line 85 will do nothing because the ShrinkNodeQueue maxMagnitude is already 0.

So overall, the ShrinkNodeQueue is never modified after the first 15 shrinks. And that's why it stops at half the original value, i.e. 424713121.

Which makes me wonder again: is there any reason why the shrinking process goes from biggest to smallest (stopping as soon as one passes), instead of smallest to biggest, stopping as soon as one doesn't pass?

Going from small to big would ensure a quick convergence, and let users provide aggressive shrinkers.

Bonus point: QuickCheck (in Haskell) goes from smallest to biggest too, so that would actually make more sense to align with it.

pholser commented

@sir4ur0n I agree; there's no particular reason why junit-quickcheck's shrinking implies must go from largest to smallest. If anything, I'd like to align with Haskell QuickCheck's behavior.

I think it's even more ganked than I originally thought. My goal was to go from max to min by halves, but I think that it may in some cases be going from max to 2 * min.

sir4ur0n commented

I did a quick trial as such:

  • In IntegralGenerator#doShrink I removed the Collections.reverse(results) call in and added the least magnitude at the beginning, not end, using results.add(0, leastMagnitude()). This correctly yields a list of shrinks, smallest to biggest.
  • In Shrinker#shrink, I replaced your custom ShrinkNodeQueue with a basic ArrayDeque
  • Replaced nodes.addAll(smallest.shrinks()); inside the while loop with nodes = new ArrayDeque<>(smallest.shrinks()); (i.e. as soon as we found a counter example, going from smallest to biggest, then drop all shrinks, and build a new queue of shrinks, and start again from here inside the while loop).

This seems to work for my test :o

java.lang.AssertionError: Property named 'testShrink' failed:
With arguments: [8]
First arguments found to also provoke a failure: [849426243]
Seeds for reproduction: [-4493071121312539862]

Of course this is quite a change, because the order of all shrinkers must now be reversed (i.e. not backward-compatible, probably deserves a new major release), but I think this is much better for the library.

What's your opinion/idea of the next move?

pholser commented

@sir4ur0n I think this sounds reasonable. Would you mind to issue a PR?

Because junit-quickcheck is at a version < 1, I think this would be worth a new pre-1 minor release (0.9), with plenty of caveat to developers via the Google group.

pholser commented

I agree that abandoning prior shrinks when a smaller counterexample is found sounds reasonable. If I can get it to where the shrinks are produced lazily rather than a (potentially) big list at a time, so much the better.