Shrinking goes into semi-infinite recursion

[noresttherein]

Here is a commit, for which IteratorExtensionSpec never ends after entering Prop.findFirstFailure: sugar.

This happens fairly often for me; here is another one

Stacktrace:

  java.lang.Thread.State: RUNNABLE
	at scala.collection.Iterator.sameElements(Iterator.scala:843)
	at scala.collection.Iterator.sameElements$(Iterator.scala:840)
	at scala.collection.AbstractIterator.sameElements(Iterator.scala:1300)
	at net.noresttherein.sugar.collections.IteratorExtensionSpec$.prop$2(IteratorExtensionSpec.scala:38)
	at net.noresttherein.sugar.collections.IteratorExtensionSpec$.$anonfun$mappingProperty$10(IteratorExtensionSpec.scala:45)
	at net.noresttherein.sugar.collections.IteratorExtensionSpec$$$Lambda$117/0x0000000801124e38.apply(Unknown Source)
	at scala.Function1.$anonfun$andThen$1(Function1.scala:87)
	at scala.Function1$$Lambda$80/0x000000080110d388.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$forAllShrink$2(Prop.scala:769)
	at org.scalacheck.Prop$$$Lambda$95/0x0000000801114d98.apply(Unknown Source)
	at org.scalacheck.Prop$.secure(Prop.scala:479)
	at org.scalacheck.Prop$.result$1(Prop.scala:769)
	at org.scalacheck.Prop$.$anonfun$forAllShrink$4(Prop.scala:778)
	at org.scalacheck.Prop$$$Lambda$234/0x000000080114ca58.apply(Unknown Source)
	at scala.collection.immutable.Stream.map(Stream.scala:173)
	at org.scalacheck.Prop$.getFirstFailure$1(Prop.scala:778)
	at org.scalacheck.Prop$.shrinker$1(Prop.scala:792)
	at org.scalacheck.Prop$.$anonfun$forAllShrink$1(Prop.scala:813)
	at org.scalacheck.Prop$$$Lambda$81/0x000000080110d740.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Prop.$anonfun$map$1(Prop.scala:52)
	at org.scalacheck.Prop$$Lambda$106/0x000000080111ceb8.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Prop.$anonfun$flatMap$1(Prop.scala:58)
	at org.scalacheck.Prop$$Lambda$85/0x000000080110e6e8.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Prop.$anonfun$flatMap$1(Prop.scala:56)
	at org.scalacheck.Prop$$Lambda$85/0x000000080110e6e8.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Prop$.$anonfun$delay$1(Prop.scala:484)
	at org.scalacheck.Prop$$$Lambda$16/0x000000080102a3e8.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Prop.$anonfun$viewSeed$1(Prop.scala:41)
	at org.scalacheck.Prop$$Lambda$18/0x000000080102ab58.apply(Unknown Source)
	at org.scalacheck.Prop$.$anonfun$apply$1(Prop.scala:309)
	at org.scalacheck.Prop$$$Lambda$17/0x000000080102a7a0.apply(Unknown Source)
	at org.scalacheck.PropFromFun.apply(Prop.scala:22)
	at org.scalacheck.Test$.workerFun$1(Test.scala:474)
	at org.scalacheck.Test$.$anonfun$check$4(Test.scala:506)
	at org.scalacheck.Test$.$anonfun$check$4$adapted(Test.scala:506)
	at org.scalacheck.Test$$$Lambda$29/0x00000008010c27b0.apply(Unknown Source)
	at org.scalacheck.Platform$.runWorkers(Platform.scala:40)
	at org.scalacheck.Test$.check(Test.scala:506)
	at org.scalacheck.Test$.$anonfun$checkProperties$2(Test.scala:547)
	at org.scalacheck.Test$$$Lambda$28/0x00000008010c6d08.apply(Unknown Source)
	at scala.collection.StrictOptimizedIterableOps.map(StrictOptimizedIterableOps.scala:100)
	at scala.collection.StrictOptimizedIterableOps.map$(StrictOptimizedIterableOps.scala:87)
	at scala.collection.mutable.ListBuffer.map(ListBuffer.scala:39)
	at org.scalacheck.Test$.checkProperties(Test.scala:538)
	at org.scalacheck.Properties.main(Properties.scala:77)
	at net.noresttherein.sugar.collections.IteratorExtensionSpec.main(IteratorExtensionSpec.scala)

[emlun]

I encountered this issue too. It seems like it's not actually infinite, just an extremely enormous amount of shrinks being traversed for long sequences. It looks like the shrinker essentially attempts to construct all possible subsequences as shrink candidates:

https://github.com/typelevel/scalacheck/blob/a745072b7009eb605e12e1324121a37303183c5f/core/shared/src/main/scala/org/scalacheck/Shrink.scala#L57-L65 https://github.com/typelevel/scalacheck/blob/a745072b7009eb605e12e1324121a37303183c5f/core/shared/src/main/scala/org/scalacheck/Shrink.scala#L78-L92

and then it looks like it visits all of them? At least that's what it looks like when I print the input to each run of the property check.

This is fine for sequences of at most ~10 elements or so, and when the property check is fast. But already at 10 ms per check, the runtime explodes somewhere around ~20 elements. Here's a minimal example - the "<= 5" and "<= 10" tests finish in a few seconds on my machine, but the "<= 20" test takes about half a minute and the "<= 40" test takes several minutes:

it("length <= 5") {
  forAll(sizeRange(100)) { l: List[Byte] =>
    Thread.sleep(10)
    l.length should be <= 5
  }
}

it("length <= 10") {
  forAll(sizeRange(100)) { l: List[Byte] =>
    Thread.sleep(10)
    l.length should be <= 10
  }
}

it("length <= 20") {
  forAll(sizeRange(100)) { l: List[Byte] =>
    Thread.sleep(10)
    l.length should be <= 20
  }
}

it("length <= 40") {
  forAll(sizeRange(100)) { l: List[Byte] =>
    Thread.sleep(10)
    l.length should be <= 40
  }
}

I encountered this in a test case that takes an arbitrary[Array[Byte]], constructs an X.509 certificate with that as an extension value and tests that a utility function returns correctly for that cert. The failure in this case occurred at length 126 and each property check (which includes constructing and signing the cert) takes on the order of ~30 ms, so the shrink loop ends up practically infinite in this case.