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:

scalacheck/core/shared/src/main/scala/org/scalacheck/Shrink.scala

Lines 57 to 65 in a745072

	implicit def shrinkContainer[C[_], T](implicit
	v: C[T] => Traversable[T],
	s: Shrink[T],
	b: Buildable[T, C[T]]
	): Shrink[C[T]] = Shrink { (xs: C[T]) =>
	val ys = v(xs)
	val zs = ys.toStream
	removeChunks(ys.size, zs).append(shrinkOne(zs)).map(b.fromIterable)
	}

scalacheck/core/shared/src/main/scala/org/scalacheck/Shrink.scala

Lines 78 to 92 in a745072

	private def removeChunks[T](n: Int, xs: Stream[T]): Stream[Stream[T]] =
	if (xs.isEmpty) empty
	else if (xs.tail.isEmpty) cons(empty, empty)
	else {
	val n1 = n / 2
	val n2 = n - n1
	lazy val xs1 = xs.take(n1)
	lazy val xs2 = xs.drop(n1)
	lazy val xs3 =
	for (ys1 <- removeChunks(n1, xs1) if !ys1.isEmpty) yield ys1 append xs2
	lazy val xs4 =
	for (ys2 <- removeChunks(n2, xs2) if !ys2.isEmpty) yield xs1 append ys2
	cons(xs1, cons(xs2, interleave(xs3, xs4)))
	}

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.