When shrinking, try zero value first as a shortcut

[cmeeren]

A test may have many generated values. These are potentially large and require many shrinks to get to the "simplest" value (e.g. 0). Often, a test failure does not depend on many of the generated values. Still, I often experience these not being shrinked fully to the "simplest" value, because there's a lot to shrink and Hedgehog gives up shrinking after a while.

This could be alleviated if Hedgehog, upon shrinking, first tested the "simplest" value of each generated parameter. If the test still fails, do this for the next, etc. If the test passes, revert and try the next parameter. After having "shortcutted" all possible parameters like this, which takes only as many shrinks as there are generated parameters, proceed with shrinking as normal. (This would also have the benefit of "saving" most of the shrinking capacity to the generated values that actually need proper shrinking.)

Am I making myself understood, or is my explanation hard to follow?

[TysonMN]

...Hedgehog gives up shrinking after a while.

When does Hedgehog give up? Is it after a certain number of shrinks?

[cmeeren]

When does Hedgehog give up? Is it after a certain number of shrinks?

Unsure if that question was for me, but I have no idea.

[TysonMN]

It was for whoever knows the answer ;) :P

[moodmosaic]

@TysonMN, it'll gave up after 100 discards. @cmeeren, how you'd get the simplest value of a complex data structure?

[cmeeren]

@cmeeren, how you'd get the simplest value of a complex data structure?

Are you talking about e.g. this?

let myComplexGen =
  gen {
    let! a = Gen.int ...
    let! b = Gen.string ...
    return { A = a; B = b }
  }

If so, finding the simplest value for the record is simply to find the simplest value for the generators used when making it (a and b). In the end, everything boils down to built-in generators, right?

[TysonMN]

I don't think it is that simple though because you said

I often experience these not being shrinked fully to the "simplest" value, because there's a lot to shrink and Hedgehog gives up shrinking after a while.

@moodmosaic said that Hedgehog (only) gives up after 100 discards, so since you are experiencing Hedgehog give up, your generator must include a filter.

I think the behavior you want exists in the generator I created in #224 (since 0 is the second value tested).

[cmeeren]

your generator must include a filter.

That can't be right.

Here's a DateTimeOffset generator for dates between 2000 and 2100, centering on the current date (the simplest value). There's no filters here. I have often experienced this not shrinking fully, and a re-run produces a value closer to the base value.

let dateTimeOffsetFrom21stCentury =
  gen {
    let min = DateTime(2000, 1, 1)
    let max = DateTime(2100, 1, 1)
    let center = DateTime.Now.Date
    let! dt =
      Gen.int64 (Range.exponentialFrom center.Ticks min.Ticks max.Ticks)
      |> Gen.map DateTime
    let! offset = Gen.int (Range.linearFrom 0 -11 11)
    return DateTimeOffset(dt, TimeSpan.FromHours(float offset))
  }

Also, Hedgehog have given up before 100 shrinks (the test report says "after X tests and Y shrinks" where Y < 100; I can't remember ever seeing it report exactly 100 shrinks).

[TysonMN]

I will try to reproduce

[cmeeren]

Note that in my case, the test failure that caused the shrinking centered on DST changes. Sometimes it would shrink to some DST change in 2040 and thereabouts, whereas other times it would successfully shrink to the DST change closest to the current time.

[TysonMN]

...Hedgehog gives up shrinking after a while.

When does Hedgehog give up? Is it after a certain number of shrinks?

@TysonMN, it'll gave up after 100 discards. @cmeeren, how you'd get the simplest value of a complex data structure?

Hedgehog is hardcoded to give up after 100 discards...

fsharp-hedgehog/src/Hedgehog/Property.fs

Lines 153 to 156 in 81a7502

	elif discards >= 100<discards> then
	{ Tests = tests
	Discards = discards
	Status = GaveUp }

...and by default never gives up on shrinking.

fsharp-hedgehog/src/Hedgehog/PropertyConfig.fs

Lines 11 to 13 in 81a7502

	let defaultConfig : PropertyConfig =
	{ TestLimit = 100<tests>
	ShrinkLimit = None }

@cmeeren, do you recall if your test changed this default shrink limit from None?

---

However, my guess is that the shrink limit is not the issue. Especially since you said:

Also, Hedgehog have given up before 100 shrinks (the test report says "after X tests and Y shrinks" where Y < 100; I can't remember ever seeing it report exactly 100 shrinks).

Hedgehog doesn't always find a smallest failing input.

@cmeeren, do you recall what your test was that used that generator and didn't shrink to the smallest failing input as you expected?

In the tests I added in the recent Hedgehog.Experimential PRs (1, 2, 3), I asserted that the shrunken input was always the minimum input that causes the test to fail. However, this is not possible in general. I am a bit knowledgeable about how Hedgehog does shrinking, so I know that Hedgehog will always find that minimum failing input (as long at the user code doesn't do something like mutation before the last let!/Gen.bind).

---

My guess is that Hedgehog did try the minimal value, but it caused your test to pass. Then after finding a failing input, it shrunk until it got stuck in a "local optima" instead of finding the minimum failing input.

[cmeeren]

@cmeeren, do you recall if your test changed this default shrink limit from None?

It's been a while, but I'm fairly sure I didn't.

@cmeeren, do you recall what your test was that used that generated and didn't shrink to the smallest failing input as you expected?

No idea, sorry.

[TysonMN]

No idea, sorry.

Then I am thinking that we don't have enough information to investigate further.

Ironically though, your description here is rather consistent with the behavior we are seeing in the draft PR hedgehogqa/fsharp-hedgehog-experimental#55.