https://kotlinlang.org logo
Title
m

mitch

02/10/2021, 8:02 PM
@sam do you still recall our convo about edgecases missing when there's one arb with empty edgecases? i'd be inclined to look into fixing that in the next few days. would this be the right time for me to start looking at it or do i wait until 4.5?
s

sam

02/10/2021, 8:03 PM
yeah I remember us talking about it but can't remember what the issue was again or what we decided
m

mitch

02/10/2021, 8:12 PM
If we bind 3 arbs, and if one have empty edgecases then the final arb has no edgecases. It was not great but we decided that it's acceptable because the Cartesian product with an empty list is always an empty list. We decided that we can fix it but decided to defer. I proposed that because we were doing the deprecation of the Arb samples that returns sequence. I was thinking it might be a bit much if we bundle those two in the same release.
s

sam

02/10/2021, 8:14 PM
Ok I recall now
what was the fix again, take a random value if edgecases is empty ?
👍 1
So we added that stuff in September according to git log so it would have gone into the 4.3 release in October. I think we could make the change for 4.5.
m

mitch

02/10/2021, 8:22 PM
Awesome. Yeah. That was the proposition. Technically we have the rough sketch of it. https://kotlinlang.slack.com/archives/CT0G9SD7Z/p1598956183036700?thread_ts=1598866831.013300&cid=CT0G9SD7Z I've modified that slightly and i think i got that to work.
s

sam

02/10/2021, 8:24 PM
If you would like to work on this, feel free, I think it's an important enhancement to arbs
m

mitch

02/10/2021, 8:25 PM
Awesome expect a pr up by this weekend
👏🏻 1
Thanks Sam!
@sam thanks for your comments, i’m refactoring the code now. I like the idea of semi-random edges! I’m just trying to digest your idea there, so in terms of implementation, currently i do agree that
EdgeCases.Random
as a sealed class member may raise some eyebrows (mine included). If i understand your comment correctly, is this what you’re thinking?
sealed class EdgeCases<out A> {
   data class Static<A>(val values: NonEmptyList<A>) : EdgeCases<A>()
   data class SemiRandom<A>(val generate: (RandomSource) -> NonEmptyList<A>) : EdgeCases<A>()
}
When we’re operating in
Arb
composition, the challenge is random seed would be provided much later. That means we need to think of a way to model
EdgeCases
with the same principle to harvest
rs
. In other words, if I were to oversimplify this a bit, we’ll probably get
data class EdgeCases<out A>(val generate: (RandomSource) -> NonEmptyList<A>)
but yeah i think you’re also well aware of it, we basically have to have a common input domain, which is random seed
s

sam

02/13/2021, 11:07 PM
I was just throwing some thoughts out there to see what stuck
So one thing would be to change
fun edgecases(): ...
to
fun edgecases(rs: RandomSource):...
and then it's up to the arb if they want to return a static list or not
Another thing would be to introduce 3 levels,
fun edges()
fun semiedges()
kind of thing (not sure if that's too much)
another way would be to return a function that accepts the RS and then returns, so
fun edges() : (RandomSource) -> List<A>
which defaults to just
= { edgecases() }
I'm not in the code right now so some of that may be nonsense 🙂
I think the easiest way would be to pass the random source into the edgecases method, and then Arb.bind can use that RS to call .sample on whatever it needs
m

mitch

02/13/2021, 11:12 PM
So one thing would be to change 
fun edgecases(): ...
 to 
fun edgecases(rs: RandomSource):...
 and then it’s up to the arb if they want to return a static list or not,
another way would be to return a function that accepts the RS and then returns, so 
fun edges() : (RandomSource) -> List<A>
 which defaults to just 
= { edgecases() }
I think the easiest way would be to pass the random source into the edgecases method, and then Arb.bind can use that RS to call .sample on whatever it needs
yeah i do agree, that’s actually converging to this:
data class EdgeCases<out A>(val generate: (RandomSource) -> NonEmptyList<A>)
except that we push the responsibility of conjuring edgecases to the arb implementation. That will work from the types perspective, implementation details can follow.
s

sam

02/13/2021, 11:12 PM
I don't think we even need the data class in this case ?
It's just wrapping a function
m

mitch

02/13/2021, 11:13 PM
yeah that’s right
excellent, so I’ll refactor the code to boil this into arb, see how this goes. to confirm:
Arb<A> {
   fun edges(rs: RandomSource): NonEmptyList<A>
}
We can also use List<A> with a
check
that edgecases needs to be nonempty at generation time.. But i prefer that check done at compile time
s

sam

02/13/2021, 11:18 PM
I don't think edge cases should be non empty
there's plenty of arbs that won't have edge cases
but the RS should be supplied for cases where the arb can make an edge case with a random value
data class Person(val name: String)
what's the edge case for an Arb that generates that
m

mitch

02/13/2021, 11:21 PM
ah right so you’re mentioning to push that defaulting to random at flatMap or bind. can do. I was thinking about types in here, so if we have this in
Arb<A>
implementers can override edges to
emptyList()
but yeah that’s legal as well. given we can guard it in flatMap that’s okay.
awesome
s

sam

02/13/2021, 11:22 PM
Yes exactly, I mean if you think we can do better, we can try, but just that edgecases(rs) should allow empty list for arbs where there are no sensible edgecase
can you call it
fun edgecases(rs: RandomSource)
so it matches the other one ?
m

mitch

02/13/2021, 11:22 PM
sounds good
s

sam

02/13/2021, 11:22 PM
the bind impl might need to change too, currently bindN delegates to bindN-1
m

mitch

02/13/2021, 11:28 PM
so:
Arb<A> {
   fun edgecases(rs: RandomSource): List<A>
}
bind will
bind(arbA, arbB): Arb<B> {
   fun edgecases(rs: RandomSource): List<A> = // find out if any of the A or B edgecases is empty and default accordingly
}
flatmap will also work
Arb<A>.flatMap(fn: (A) -> Arb<B>): Arb<B> {
   fun edgecases(rs: RandomSource): List<B> = this@flatMap.edgecases(rs).flatMap { a -> fn(a) // resolve edges here }
}
s

sam

02/13/2021, 11:28 PM
yea
m

mitch

02/13/2021, 11:28 PM
the bind impl might need to change too, currently bindN delegates to bindN-1
what do you mean here?
s

sam

02/13/2021, 11:28 PM
genA.bind(genB).bind(genC).bind(genD).bind(genE).bind(genF).bind(genG).map { (abcdef, g) ->
   val (abcde, f) = abcdef
   val (abcd, e) = abcde
   val (abc, d) = abcd
   val (ab, c) = abc
   val (a, b) = ab
   bindFn(a, b, c, d, e, f, g)
seems an odd way to do it
maybe it doesn't need to change, just talking out loud
m

mitch

02/13/2021, 11:30 PM
ahh, yeah that was applicative right. we basically want product.
Applicative[F[_]] {
   product(a: F[A], b: F[B]): F[(A, B)]
}
and then the rest will work by recursively applying product
👍🏻 1
i think they call it ap or something
s

sam

02/13/2021, 11:31 PM
ap inside applicative yes
m

mitch

02/14/2021, 12:52 AM
qq do we need
Arb<A>.withEdgecases(fn: (RandomSeed) -> List<A>): Arb<A>
and
Arb<A>.modifyEdgecases(fn: (initial: List<A>, rs: RandomSeed) -> List<A>): Arb<A>
s

sam

02/14/2021, 12:53 AM
yeah probably
👍 1
m

mitch

02/14/2021, 1:21 AM
😢
Overload resolution ambiguity. All these functions match.
public fun <A> Arb<TypeVariable(A)>.modifyEdgecases(f: (initial: List<TypeVariable(A)>, randomSource: RandomSource) → List<TypeVariable(A)>): Arb<TypeVariable(A)> defined in io.kotest.property.arbitrary in file arbs.kt

public fun <A> Arb<TypeVariable(A)>.modifyEdgecases(f: (List<TypeVariable(A)>) → List<TypeVariable(A)>): Arb<TypeVariable(A)> defined in io.kotest.property.arbitrary in file arbs.kt
kotlin can’t resolve pick up lambda types, I think i need to hack this to use RandomSource as receiver type if we were to maintain backward compatibilty
fun <A> Arb<A>.modifyEdgecases(f: RandomSource.(List<A>) -> List<A>): Arb<A> =
   arbitrary({ rs -> f(rs, this@modifyEdgecases.edgecases(rs)) }, { this.next(it) })
sam any suggestion on naming here, that hack is just awkward to use
s

sam

02/14/2021, 1:27 AM
can you paste in the two functions that clash
m

mitch

02/14/2021, 1:28 AM
fun <A> Arb<A>.modifyEdgecases(f: (List<A>) -> List<A>): Arb<A> = TODO()
fun <A> Arb<A>.modifyEdgecases(f: (List<A>, RandomSource) -> List<A>): Arb<A> = TODO()
s

sam

02/14/2021, 1:28 AM
fun <A> Arb<A>.modifyEdgecases(f: (List<A>) -> List<A>): Arb<A> = TODO()

@JvmName("modifyEdgecasesRandom")
fun <A> Arb<A>.modifyEdgecases(f: (List<A>, RandomSource) -> List<A>): Arb<A> = TODO()
Does that work ?
m

mitch

02/14/2021, 1:29 AM
trying
nope, the call site can’t figure it out
s

sam

02/14/2021, 1:31 AM
you could try
listOf(2,3) + it
You could also just rename the second one to modifyEdgecasesWithRandom or something
(not as nice I know)
m

mitch

02/14/2021, 1:32 AM
listOf(2,3) + it
 
nope kotlin gave up here too
s

sam

02/14/2021, 1:33 AM
its wierd it fails, because only one of the functions has a single parameter
m

mitch

02/14/2021, 1:33 AM
yeah
s

sam

02/14/2021, 1:33 AM
and you didn't declare parmaeters in the lamba
m

mitch

02/14/2021, 1:34 AM
yeah i mean theoretically it should work, but apparently it can’t, let me search in youtrack if there’s a workaround for this
s

sam

02/14/2021, 1:35 AM
it works if you do
a -> a + listOf(2,3)
but that's not very user friendly
m

mitch

02/14/2021, 1:35 AM
yeah not really, i bet lots of users will complain
s

sam

02/14/2021, 1:35 AM
or just get stuck and ask us
so we want to avoid that
m

mitch

02/14/2021, 1:36 AM
and we do have that in our codebase, so if we do that our build will fail and we need to refactor lots
s

sam

02/14/2021, 1:36 AM
true
I think a different name is the best we can do
m

mitch

02/14/2021, 2:36 AM
ok, so this doesn’t work. because i need to know whether that the edges is static / semi-random. list doesn’t have that information..
Arb<A> {
   fun edgecases(rs: RandomSource): List<A>
}
s

sam

02/14/2021, 2:36 AM
you're just going to provide a seed and get back some edge cases right
and if the edge cases is empty, bind will go over to sample(rs)
m

mitch

02/14/2021, 2:37 AM
so for instance this code:
"Arb.bind(a,b,c,d) should compute the cartesian product of edges" {
   val arbA = Arb.string(1)
   val arbB = Arb.string().withEdgecases("a", "b")
   val arbC = Arb.string(1)
   val arbD = Arb.string().withEdgecases("a", "b")
   val arb = Arb.bind(arbA, arbB, arbC, arbD) { a, b, c, d -> a + b + c + d }
   arb.edgecases(RandomSource.seeded(1234L)) shouldContainExactlyInAnyOrder listOf(
      "Uaka", "%bca", "?aCb", "KbGb"
   )
}
instead of generating
["Uaka", "%bca", "?aCb", "KbGb"]
it generates
["Uaka", "Uakb", "%bca", "%bcb"]
because essentially when list is created, it’ll preserve its value instead of keep generating a new one
s

sam

02/14/2021, 2:38 AM
can you post up the bind code
m

mitch

02/14/2021, 2:39 AM
private fun <A, B, C> Gen<A>.bind(other: Gen<B>, fn: (A, B) -> C): Arb<C> {
   val thisArb = when (this) {
      is Arb -> this
      is Exhaustive -> this.toArb()
   }

   val otherArb = when (other) {
      is Arb -> other
      is Exhaustive -> other.toArb()
   }

   val arb = thisArb.flatMap { a -> otherArb.map { b -> fn(a, b) } }

   return object : Arb<C>() {
      override fun edgecases(): List<C> = arb.edgecases()
      override fun edgecases(rs: RandomSource): List<C> {
         val maybeEdgesA = NonEmptyList.fromList(thisArb.edgecases(rs))
         val maybeEdgesB = NonEmptyList.fromList(otherArb.edgecases(rs))
         return maybeEdgesA.fold(
            ifEmpty = {
               maybeEdgesB.fold(
                  ifEmpty = {
                     fn(thisArb.single(rs), otherArb.single(rs)).nel()
                  },
                  ifDefined = { edgesB ->
                     edgesB.map { b ->
                        val a = thisArb.single(rs)
                        fn(a, b)
                     }
                  }
               )
            },
            ifDefined = { edgesA ->
               maybeEdgesB.fold(
                  ifEmpty = {
                     edgesA.map { a: A ->
                        val b = otherArb.single(rs)
                        fn(a, b)
                     }
                  },
                  ifDefined = { edgesB ->
                     edgesA.flatMap { a: A ->
                        edgesB.map { b: B ->
                           fn(a, b)
                        }
                     }
                  }
               )
            }
         ).all
      }

      override fun sample(rs: RandomSource): Sample<C> = arb.sample(rs)

      override fun values(rs: RandomSource): Sequence<Sample<C>> = arb.values(rs)
   }
}
s

sam

02/14/2021, 2:40 AM
is this on a branch ?
actually doesn't matter
m

mitch

02/14/2021, 2:41 AM
oh no it’s not - it’s on my local but this will work
Arb<A> {
   fun edgecases(): (rs: RandomSource) -> List<A>
}
s

sam

02/14/2021, 2:41 AM
ok
m

mitch

02/14/2021, 2:41 AM
or at least i have a feeling that it will
actually, now that i think about it, i don’t think that’ll work either that may work, because
(rs: RandomSource) -> List<A>
is a kleisli
let me try that out first
s

sam

02/14/2021, 2:48 AM
What about something like this
fun <A> edgesOrSample(edges: List<A>, gen: Gen<A>, rs: RandomSource): List<A> =
   if (edges.isEmpty()) listOf(gen.generate(rs).first().value) else edges

fun <A, B, C> Gen<A>.bind(other: Gen<B>, fn: (A, B) -> C): Arb<C> {

   val thisArb = when (this) {
      is Arb -> this
      is Exhaustive -> this.toArb()
   }

   val otherArb = when (other) {
      is Arb -> other
      is Exhaustive -> other.toArb()
   }

   return object : Arb<C>() {

      override fun edgecases(): List<C> = TODO() // previous cartesian combination
      override fun edgecases(rs: RandomSource): List<C> {
         val maybeEdgesA = thisArb.edgecases(rs)
         val maybeEdgesB = otherArb.edgecases(rs)
         // we don't create edges is none of the bound gens have edge cases
         return if (maybeEdgesA.isEmpty() && maybeEdgesB.isEmpty())
            emptyList()
         else
            edgesOrSample(maybeEdgesA, this@bind, rs).flatMap { a ->
               edgesOrSample(maybeEdgesB, other, rs).map { b ->
                  fn(a, b)
               }
            }
      }

      override fun sample(rs: RandomSource): Sample<C> = arb.sample(rs)
   }
}
m

mitch

02/14/2021, 2:55 AM
I think that's going to run into a similar issue sam, because
edgesOrSample
returns a concrete list
s

sam

02/14/2021, 2:55 AM
recap the issue ?
s

sam

02/14/2021, 2:56 AM
edgesOrSample is just a helper method that goes to sample(rs) if the edge cases are empty
it's not defined in arb
m

mitch

02/14/2021, 2:57 AM
Yeah i know. The issue is around when the generation happen
With List, you have a concretely sampled item, so observe the second result vs the first one
The first is trully random because we have a lazily generated list.
s

sam

02/14/2021, 3:00 AM
in your example, what do you expect the edge cases to be, it's hard to work out from %bca etc what you expect to be there
Maybe shrink it down to 2 arbs to simply the example
m

mitch

02/14/2021, 3:05 AM
yep so the expectation is:
r1 a r2 a
r3 a r4 b
r5 b r6 a
r7 b r8 b
Instead we get
r1 a r2 a
r1 a r2 b
r3 b r4 a
r3 b r4 b
notice how r1 and r2 as well as r3 and r4 are repeated because of concrete list
s

sam

02/14/2021, 3:05 AM
Ok, what's r ?
m

mitch

02/14/2021, 3:05 AM
random
s

sam

02/14/2021, 3:06 AM
ok, strings have edge cases already
Ok I guess when minsize = maxsize they don't
m

mitch

02/14/2021, 3:07 AM
yeah that’s not the issue. we kinda want a
List<Edge<A>>
instead of
List<A>
s

sam

02/14/2021, 3:07 AM
I don't know why what I pasted wouldn't work. Each time you invoke edgecases(rs) you're going to get a new random element.
m

mitch

02/14/2021, 3:07 AM
this way we can interpret
Edge<A> -> A
on every iteration
the issue is here
val list = edgesOrSample(maybeEdgesA, this@bind, rs) // e.g. a, b
val anotherList = edgesOrSample(maybeEdgesB, this@bind, rs) // e.g. r1, r2

list.flatMap { first -> anotherList.map { second -> first to second } }
// a -> r1
// a -> r2
// b -> r1
// b -> r2
s

sam

02/14/2021, 3:11 AM
But you don't pull edges or sample out
I didn't do that in the example, I invoked it each time in the flat map
edgesOrSample(maybeEdgesA, this@bind, rs).flatMap { a ->
  edgesOrSample(maybeEdgesB, other, rs).map { b ->
    fn(a, b)
  }  
}
m

mitch

02/14/2021, 3:12 AM
oh yeah you did
s

sam

02/14/2021, 3:12 AM
If the maybeEdgesX are empty, they'll get a new random element each time
m

mitch

02/14/2021, 3:13 AM
ah yeah! i made a silly mistake there
s

sam

02/14/2021, 3:13 AM
which to be honest, I'm not even sure if my (right?) way is right. Should the empty edge case be random each time, or just fixed. I mean is edge cases just becoming another non-edge case at this point.
m

mitch

02/14/2021, 3:13 AM
i shouldn’t have assigned that to a val
s

sam

02/14/2021, 3:14 AM
if you have 4 arbs, 3 of which have edge cases, should be the 4th parameter be fixed while the other 3 cycle (obviously it would be random across different invocations of the test suite)
What I pasted works like what you wanted I think, but maybe we should consider if that's the right behavior
m

mitch

02/14/2021, 3:16 AM
i think your right way is right (i hope this doesn’t confuse you even more). because essentially
a, *
should work for any *
i.e. this should work
1, x === 1, 1 or 1, 0
if we’re talking about boolean algebra
s

sam

02/14/2021, 3:17 AM
val arbA = Arb.string().withEdgecases("a", "b")
val arbB = Arb.string().withEdgecases("c", "d")
val arbC = Arb.string().withEdgecases("e", "f")
val arbD = Arb.string(1)
In that scenario, I would probably expect (a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z) and so on. Z being a random, but fixed element.
after all, we're just trying to fill in the bind with a missing edge case
m

mitch

02/14/2021, 3:26 AM
In that scenario, I would probably expect (a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z) and so on. Z being a random, but fixed element.
yeah ok so using the code sample you gave me i got the above behaviour, because of
list.flatMap
s

sam

02/14/2021, 3:27 AM
I think the code I pasted would fix the first element and randomize the other one, pulling it out to vals would fix all parameters.
If you agree with me that any "missing" edge cases args should be a single fixed element for all edge cases generated in that run, then declare it all as vals before your flat map. If you think each missing edge case args should be random completely, then my code would work. While I think the former makes more sense, it's just a personal preference, I'm happy if you do whatever.
Either way, do you have enough to become unblocked ?
m

mitch

02/14/2021, 3:32 AM
hmm.. the code that you pasted is good for monadic bind (flatMap) but i don’t think that’s going to work for (applicative) bind i think i gave you a wrong example. Here is the issue: imagine if we flip the situation
fun list() = edgesOrSample(maybeEdgesA, this@bind, rs) // e.g. r1, r2
fun anotherList() = edgesOrSample(maybeEdgesB, this@bind, rs) // e.g. a, b
list.flatMap { first -> anotherList.map { second -> first to second } }
// r1 -> a
// r1 -> b
// r2 -> a
// r2 -> b
so this is the behaviour that you are after with
(a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z)
s

sam

02/14/2021, 3:33 AM
Our bind isn't really applicative though is it, it's more like zip or mapN
🤔 1
I'm off to bed as I'm too old to rock n roll 🙂 I've invited you into the kotest org, so why don't you put up some test cases on a branch, with the work so far, and I'll have a play in the morning, because I think this is a lot more simple than we're making it sound here. And if I'm wrong, and am not fully understanding the issue, then at least I'll understand the issue when I run into the same problem 🙂
m

mitch

02/14/2021, 3:36 AM
haha
sounds good
s

sam

02/14/2021, 3:37 AM
great thanks, appreciate you looking at this stuff.
m

mitch

02/15/2021, 12:30 PM
@sam you’ve convinced me. my original idea was a bit too much to implement. 😆
i managed to solve that but i ended up creating a recursive type so that i can inject the rs after. I needed to create an
Eval
type for trampolining etc. and I’m still in the middle of implementing flatmap and doing all the type gymnastics. it wasn’t worth it.
s

sam

02/15/2021, 12:33 PM
ok so it's coming along ok ?
m

mitch

02/15/2021, 12:34 PM
haha yeah i’ve pushed that to the original branch, kept the bind to a monadic, so you’d get this behaviour
(a, c, e, Z), (b, c, e, Z), (a, d, e, Z), (b, d, e, Z)
s

sam

02/15/2021, 12:35 PM
I think that's good enough right
m

mitch

02/15/2021, 12:36 PM
yeah
i can share my findings on the other one when i finished it just for fun somewhere here, it was a good exercise.
s

sam

02/15/2021, 12:37 PM
ok would be interested in seeing that
If you put the PR up I will merge when master becomes 4.5
m

mitch

02/15/2021, 12:39 PM
i pushed it to the original branch, https://github.com/kotest/kotest/pull/2096/files we can iterate there. there’s quite a bit of changes, but should be pretty straightforward to review
thanks for your support @sam !
👍🏻 1
@sam sorry for the slow updates on the PR, things are pretty hectic on my side! The latest code should be ready for review in case you missed it.