Incorrect shrinking (mutable objects in generator)

[cmeeren]

In Hedgehog.Experimental I have this:

/// Shuffles the case of the given string.
let shuffleCase (s: string) =
  gen {
    let sb = Text.StringBuilder()
    for i = 0 to s.Length - 1 do
      let! b = Gen.bool
      let f = if b then Char.ToUpperInvariant else Char.ToLowerInvariant
      sb.Append (f s.[i]) |> ignore
    return sb.ToString()
  }

Let's try to sample this:

shuffleCase "abc" |> Gen.printSample

Yields:

=== Outcome ===
"abc"
=== Shrinks ===
.
=== Outcome ===
"aBC"
=== Shrinks ===
"aBCb"
"aBCbc"
.
=== Outcome ===
"ABc"
=== Shrinks ===
"ABca"
"ABcab"
.
=== Outcome ===
"abC"
=== Shrinks ===
"abCc"
.
=== Outcome ===
"abc"
=== Shrinks ===
.

As you can see, there's something weird going on with shrinking. Additional characters are added.

If I instead implement it in an immutable way, it works. For example:

let shuffleCase (s: string) =
  let rec inner (i: int) (soFar: string) =
    gen {
      if i = s.Length then return soFar
      else
        let c = s.[i]
        let! b = Gen.bool
        let f = if b then Char.ToUpperInvariant else Char.ToLowerInvariant
        return! inner (i + 1) (soFar + string (f c))
    }
  inner 0 ""

Why does the first one fail? Is it a general rule that using (locally defined) mutable objects in a generator will cause issues for shrinking?

[cmeeren]

Might be related to (and possible duplicate of) #157.

[moodmosaic]

Yep, seems like a dupe of #157 which we've never get into it. I think what's happening is that everything above let! will execute once, and then the shrinking occurs below.

I'd be tempted to compare these results with the haskell version, because we had a similar issue reported there in hedgehogqa/haskell-hedgehog#122.

[cmeeren]

I see. The Hedgehog.Experimental library contains more generators that use mutable state. Do you think you'd be able to have a look at this in the foreseeable future, or should I prioritize implementing them without immutability? (That might impact performance, so I'd rather not.)

Or as a temporary workaround, I can generate a throwaway value using let! first thing in the CEs that use mutable state. What's the cheapest thing to generate?

[moodmosaic]

I'm planning to take a look this the soonest possible. It'd be interesting to see if your idea will work, using a let! with a gen like Gen.constant.

[cmeeren]

Unfortunately, using Gen.constant (or Gen.int) first in the CE did not have any effect.

[moodmosaic]

gen __For and Random replicate look suspicious to me, then. I should be able to tell more once I get into it, hopefully this week. I'll ping @jacobstanley too, in case he has an idea in the meantime.

[moodmosaic]

As I'm looking at this, here's a minimal working example I've been using based on the above gen(s)

open System
open System.Text

open Hedgehog

let shuffleCase_mut (s : string) : Gen<string> =
    let sb = StringBuilder ()
    gen {
        for i = 0 to s.Length - 1 do
            let! b = Gen.bool
            let fn =
                if b then
                    Char.ToUpperInvariant
                else
                    Char.ToLowerInvariant
            sb.Append (fn s.[i]) |> ignore
        return sb.ToString ()
    }

let shuffleCase_rec (s : string) : Gen<string> =
    let rec go i c =
        gen {
            if i <> s.Length then
                let! b = Gen.bool
                let fn =
                    if b then
                        Char.ToUpperInvariant
                    else
                        Char.ToLowerInvariant
                return! go (i + 1) (c + string (fn s.[i]))
            else
                return c
        }
    go 0 ""

[<EntryPoint>]
let main _ =
    printfn
       "shuffleCase_mut"
    for __ = 0 to 3 do
        shuffleCase_mut "ab" |> Gen.generateTree |> printfn "%A"

    printfn
       "shuffleCase_rec"
    for __ = 0 to 3 do
        shuffleCase_rec "ab" |> Gen.generateTree |> printfn "%A"

    0

shuffleCase_mut

Node ("AB",seq [Node ("ABa",seq []); Node ("ABab",seq [])])
Node ("AB",seq [Node ("ABa",seq []); Node ("ABab",seq [])])
Node ("aB",seq [Node ("aBb",seq [])])
Node ("ab",seq [])


shuffleCase_rec

Node ("AB",seq [Node ("aB",seq [Node ("ab",seq [])]); Node ("Ab",seq [])])
Node ("ab",seq [])
Node ("Ab",seq [Node ("ab",seq [])])
Node ("Ab",seq [Node ("ab",seq [])])

These are the generated rose trees, with the outcome and all the ways in which they can be made smaller.

[TysonMN]

I looked into this a bit, but it is complicated. Hopefully things will be simpler when PR #238 is completed. I will investigate more after the PR is complete.

[dharmaturtle]

If Tyson's comment here is correct, one way to avoid overflow in ListGen.traverse is to do things iteratively. As that'll involve mutation, we may revisit ListGen.traverse once this is solved.

[TysonMN]

PR hedgehogqa/fsharp-hedgehog-experimental#53 implements a workaround in "client code" for the motivating example in the OP of this issue.

I think this issue can be closed. The issue about mutation in generators can continue to be tracked via #157.

[cmeeren]

Actually, I'll leave it to the maintainers of this repo to decide whether to close this.

[ghost]

Closing in favor of #157.