#kotest-contributors
Title
# kotest-contributors
m

mitch

09/23/2021, 11:35 AM
@Emil Kantis by the way, on the approach on computing cartesian product for shrinks, can we discuss this a little bit? https://kotlinlang.slack.com/archives/CSYLDDZUY/p1632354439096200 this can cause problems on combinatorial explosion if we’re not careful. That was an issue @sam and I needed to urgently fix a while back https://github.com/kotest/kotest/issues/2112
e

Emil Kantis

09/23/2021, 11:37 AM
Yeah, I agree, it can explode very quickly.. 14 arbs with 3 children each -> 5 million items 😄 thought about that as well
m

mitch

09/23/2021, 11:37 AM
yeah..
e

Emil Kantis

09/23/2021, 11:37 AM
do you have any thoughts on how to approach it?
Could working with sequences be a workaround, so each item is computed as they are iterated upon?
m

mitch

09/23/2021, 11:42 AM
i’m currently thinking of zipping them with fills with length, something like so
Copy code
``````#.     value shrinks
arb1 -> v    5 3 1 0
arb2 -> v.   v v v v (that has no shrinks)
arb3 -> v.   a b b b (2 shrinks pad last entry)
arb4 -> v.   0 0 0 0 (1 shrink, pad last entry)``````
that’ll reduce the space and computational complexity from exponential O(n^k) to linear O(n) now i’m quite sure that is correct, but let me look into some references first
that also solves a subtle bug with flatmap where the initial list can’t be empty otherwise the rest of the shrinks will be empty:
Copy code
``[].flatMap [a, b, c] --> []``
let me do some scouting on how scalacheck does it
👍 1
check this out
Copy code
``````/** Shrink instance of 4-tuple */
implicit def shrinkTuple4[
T1:Shrink, T2:Shrink, T3:Shrink, T4:Shrink
]: Shrink[(T1,T2,T3,T4)] =
Shrink { case (t1,t2,t3,t4) =>
shrink(t1).map((_, t2, t3, t4)) append
shrink(t2).map((t1, _, t3, t4)) append
shrink(t3).map((t1, t2, _, t4)) append
shrink(t4).map((t1, t2, t3, _))
}``````
what that means incoming arb
Copy code
``````#.     value shrinks
arb1 -> v1   5 3 1 0
arb2 -> v2   (no shrinks)
arb3 -> v3   a b
arb4 -> v4   0``````
you’d get 4 lists of shrinks
Copy code
``````#1
[
bindFn(5, v2, v3, v4),
bindFn(3, v2, v3, v4),
bindFn(1, v2, v3, v4),
bindFn(0, v2, v3, v4)
]

#2
[] // empty because of emptyList<>.map(...) == emptylist

#3
[
bindFn(v1, a, v3, v4),
bindFn(v1, b, v3, v4),
]

#4
[
bindFn(v1, v2, v3, 0)
]

finalShrinks = shrinks1 + shrinks2 + shrinks3 + shrinks4``````
s

sam

09/23/2021, 12:12 PM
So they're just shrinking each part in turn
Which makes sense. Trying to find the one bit that fails rather than shrinking everything
m

mitch

09/23/2021, 12:14 PM
yeah, exactly. there’s an interesting comment in fastcheck that signals they might have encountered a similar problem at some point
Copy code
``````// shrinking one by one is the not the most comprehensive
// but allows a reasonable number of entries in the shrink``````
s

sam

09/23/2021, 12:15 PM
Ah yeah
e

Emil Kantis

09/23/2021, 9:38 PM
Thanks for the excellent research @mitch, was a bit hard for me to engage during work hours. I implemented shrinking the way you suggested now: https://github.com/kotest/kotest/commit/a5e5c08e9859fa1b7a0c864b303944ab0cdb8e07
🙌 1
m

mitch

09/24/2021, 3:31 AM
thats awesome! let’s get that in
s

sam

09/24/2021, 3:39 AM
If you guys are happy just merge it in
6 Views