search

jqwik-team / jqwik

Property-Based Testing on the JUnit Platform
http://jqwik.net
Eclipse Public License 2.0
578 stars 64 forks source link

severalStepsToList_withReversedOrderOfSuppliers sometimes runs into StackOverflowError #431

Open vlsi opened 1 year ago

vlsi commented 1 year ago

Testing Problem

See https://github.com/jlink/jqwik/actions/runs/3693074859/jobs/6252643488#step:5:211

java.lang.StackOverflowError
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:[234]
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)
      at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
      at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
      at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
      at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
      at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:921)
      at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
      at java.base/java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:657)
      at net.jqwik.api.ShrinkingDistance.combine(ShrinkingDistance.java:38)
      at net.jqwik.engine.properties.shrinking.CombinedShrinkable.distance(CombinedShrinkable.java:54)
      at net.jqwik.engine.properties.shrinking.LazyOfShrinkable.distance(LazyOfShrinkable.java:39)

Suggested Solution

  1. Refrain from Stream API in net.jqwik.api.ShrinkingDistance#combine and net.jqwik.api.ShrinkingDistance#forCollection so the stacktrace is shorter and easier to understand.

  2. Limit the depth of the lazy in tests somehow. I'm not sure it is realistic to test thousands of nested combine calls. As I replaced Stream API with a for loop, I got the following failure, which does not seem to have a trivial solution:

java.lang.StackOverflowError
    at net.jqwik.engine.properties.shrinking.ShrinkableBigInteger.checkValueInRange(ShrinkableBigInteger.java:73)
    at net.jqwik.engine.properties.shrinking.ShrinkableBigInteger.<init>(ShrinkableBigInteger.java:19)
    at net.jqwik.engine.properties.arbitraries.randomized.RandomIntegralGenerators.lambda$bigIntegers$1(RandomIntegralGenerators.java:32)
    at net.jqwik.api.RandomGenerator.lambda$mapShrinkable$1(RandomGenerator.java:57)
    at net.jqwik.engine.properties.arbitraries.randomized.ContainerGenerator.nextUntilAccepted(ContainerGenerator.java:108)
    at net.jqwik.engine.properties.arbitraries.randomized.ContainerGenerator.next(ContainerGenerator.java:70)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.generateCurrent(LazyOfArbitrary.java:107)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.lambda$generator$1(LazyOfArbitrary.java:58)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.generateShrinkables(CombineArbitrary.java:108)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.lambda$combineGenerator$1(CombineArbitrary.java:85)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.generateCurrent(LazyOfArbitrary.java:107)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.lambda$generator$1(LazyOfArbitrary.java:58)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.generateShrinkables(CombineArbitrary.java:108)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.lambda$combineGenerator$1(CombineArbitrary.java:85)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.generateCurrent(LazyOfArbitrary.java:107)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.lambda$generator$1(LazyOfArbitrary.java:58)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.generateShrinkables(CombineArbitrary.java:108)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.lambda$combineGenerator$1(CombineArbitrary.java:85)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.generateCurrent(LazyOfArbitrary.java:107)
    at net.jqwik.engine.properties.arbitraries.LazyOfArbitrary.lambda$generator$1(LazyOfArbitrary.java:58)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.generateShrinkables(CombineArbitrary.java:108)
    at net.jqwik.engine.properties.arbitraries.combinations.CombineArbitrary.lambda$combineGenerator$1(CombineArbitrary.java:85)
jlink commented 1 year ago

In CI the SOE seems to occur only on Java 18. Bad. Tried to circumvent it temporarily by fixing seed of test.

vlsi commented 1 year ago

In any case, stacktrace without streams is way easier to read

jlink commented 1 year ago

In any case, stacktrace without streams is way easier to read

The code is so much more involved, though, that I'd like to leave it unchanged until tackling the underlying problem.

vlsi commented 1 year ago

I agree shortening the stacktrace does not really solve the root cause.