Recursive shrinking

[viluon]

Please describe the feature you'd like to see including any solutions in mind if you have any

At the moment, shrinkers for e.g. Arb.list are unable to shrink the list's elements. I was wondering whether that's a limitation of the underlying gen used by Arb.list, but providing an inner Arb with a custom shrinker showed that the inner shrinker is never called.

I wanted to implement my own variant of Arb.list that shrinks recursively (preferring to try smaller lists first, then mapping the inner shrinker over values). I believe this is how other libraries work, like QuickCheck in Haskell or quickcheck in Rust. Unfortunately, kotest's architecture seems to associate shrinkers with individual samples, rather than with an entire Arb. A shrinker for a collection doesn't have access to the samples used to build it and therefore can't invoke inner shrinkers recursively. Since I'm used to other property-based testing libraries, this seems like a major limitation that makes shrinking almost useless. A single level of indirection is enough to turn minimal counterexamples into complex, unshrinkable, unreadable data.

Please correct my interpretation where necessary. I'm not entirely confident in my understanding of kotest's property-based testing architecture as documentation on custom generators is somewhat scarce — it only covers very basic examples and doesn't explain the underlying abstractions and algorithms.

Possible solutions

Changing

fun interface Shrinker<A> {
   fun shrink(value: A): List<A>
}

into

fun interface Shrinker<A> {
   fun shrink(value: Sample<A>): List<Sample<A>>
}

and making Samples carry extra info is one option, if shrinker-per-sample is the right mindset. It honestly might be, depending on how are shrinkers used in the wild.

Another approach would be maintaining the shrinker hierarchy parallel to the Arb hierarchy, exposing shrinkers explicitly in Arbs, similarly to classifiers. AFAICT doing so is common in other libraries.

[TiddoLangerak]

A similar problem pops up with pretty much any custom generator. E.g. if I have:

data class Point(x: Int, y: Int);

fun points(): Arb<Point> = arbitrary(pointShrinker) {
    Point(x = Arb.int().bind(), y = Arb.int().bind())
}

then in my pointShrinker I want to delegate to the shrinkers for x and y. In it's most basic form, I'd want to do something like this:

val pointShrinker = Shrinker<Point> { point ->
    shrink(point.x) { newX -> point.copy(x = newX) } +
        shrink(point.y) { newY -> point.copy(y = newY) }
}

This is not currently possible as far as I can tell.

Ideally, kotest would even provide a bind() implementation for this as well, such that I could do:

val pointShrinker = Shrinker<Point> { point ->
    shrink {
        Point(
            x = shrink(point.x).bind(), 
            y = shrink(point.y).bind()
        )
    }
}

And a recursive list shrinker could then be implemented something like this:

val recursiveListShrinker = Shrinker<List<T>> { list ->
    listOf(
        list.drop(1),
        list.dropLast(1),
    ) + shrink {
        list.map({ shrink(it).bind() })
    }
}

In fact, I think if we take the pointShrinker to it's logical conclusion, kotest should even be able to automatically "implement" this shrinker for us, as the shrinker is now just the generator but with all Arb.bind() replaced with shrink(sample).bind().