New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add "generator invariants" #8

Closed
rickynils opened this Issue May 31, 2011 · 16 comments

Comments

Projects
None yet
7 participants
@rickynils
Owner

rickynils commented May 31, 2011

Transferred from http://code.google.com/p/scalacheck/issues/detail?id=85

Make it possible to attach preconditions/invariants to generators so you don't have to add a precondition to the property also.

See http://groups.google.com/group/scalacheck/msg/b563f24c81b22291

@ghost ghost assigned rickynils May 31, 2011

@SethTisue

This comment has been minimized.

Contributor

SethTisue commented Jul 30, 2011

DO WANT

@JHeiner

This comment has been minimized.

JHeiner commented Nov 7, 2011

I stumbled over this issue today, and it took forever to figure out what was going wrong!
Fortunately I enjoy this kind of detective work.

And I think I have a suggestion for an easier fix... But first let me try to add some clarity to what the problem is.

Some apps use collections of a fixed size. For example, an Array of exactly 3 Doubles to represent a coordinate in space. And these apps want to test their methods that use such collections, and in that example Gen.containerOfN[Array,Double](3,Gen.choose(-1000d,1000d)) seems like an obvious choice.

The funny thing is that when the method being tested is actually correct that Gen works perfectly.

But things go horribly wrong when an app's methods are actually failing. The shrinker mistakenly tries to chop down the size of the collection, but the app is going to reject those collections because they are too short: e.g. obviously an Array of length less than 3 isn't an acceptable coordinate.

But the shrinker thinks it has found a simplified input that causes the problem, so the error reported to the user is "when you call this method with a collection that isn't of the correct size it fails". Well, that's not news to the programmer, and it leads to the incorrect conclusion that the custom Gen isn't producing what it ought to, which makes absolutely zero sense because you can sample the Gen and see that it is!

Also note that an app method may take two parameters, one expecting a fixed-length collection, and the other a variable-length (and therefore shrinkable) collection.

So, here's my suggestion:

  1. Add "def shrinkable = true" to Gen with a doc comment to describe the above scenario.
  2. Clone Gen.containerOfN and give it a name like shrinkableOfN, possibly make it private but fix the doc comment to say the size is "at most n" , and have containerOf and containerOf1 delegate to shrinkableofN
  3. Make the result of Gen.containerOfN "override def shrinkable = false" (so it can live up to the promise given in its doc comment)
  4. Teach the shrinker code to leave any Gen that isn't shrinkable alone (i.e. somewhere near line 542 of Prop.scala)

Now, in my scanning of the code I might have missed other Gen instances that might also need to override shrinkable, but even reading thru the previous complaints about this issue didn't reveal any others.

Thanks for the time you spend on this project! Hope this helps!

@rickynils

This comment has been minimized.

Owner

rickynils commented Nov 7, 2011

The "shrinkable = true/false" way could be one (simple) solution, but I think it's a bit too rough. For example, if you use an input array like the one you're describing, in most cases you would still want the values inside the array to be minimized, but that wouldn't happen if you marked the array as "unshrinkable".

If we instead come up with a way to attach "proper" preconditions to generators, then the Gen.containerOfN method could maybe create generators with a "size == n" precondition attached.

@JHeiner

This comment has been minimized.

JHeiner commented Nov 9, 2011

... in most cases you would still want the values inside the array to be minimized, but that wouldn't happen if you marked the array as "unshrinkable".

Well, that depends on the change to the shrinker behavior (i.e. "near line 542 of Prop.scala")... There is no reason it couldn't leave the unshrinkable container unshrunk and still recurse into the elements of said container to attempt to shrink them, right?

Isn't this what happens with Gen.resultOf currently? Those functions are essentially containers of fixed size, and so the shrinker would never imagine turning a 3-ary into a 2- or 1- or 0-ary function. But the arguments are eligible for shrinking... Or at least I assume they are (I only started learning Scalacheck this week, and I haven't had time to grok the shrinker code).

If my assumption is correct, then you have already implemented the necessary idea and all you need to do is have it apply to the container generators. And if my assumption is incorrect, then there's a bug in the shrinker code that handles functions.

I wish I had time to spend learning the shrinker code so I could be more specific, but I'm really swamped with another project at the moment.

@JHeiner

This comment has been minimized.

JHeiner commented Nov 9, 2011

Hmm... in fact I think we've stumbled across an alternative description of the problem:

Gen.containerOfN[Array,Double](3,Gen.choose(-1000d,1000d))

should behave exactly the same as

Gen.resultOf( (x:Double,y:Double,z:Double)=>Array(x,y,z) )( somethin,somethin,somethin )

The latter can be a workaround, but only for containers of size less than ten, and there's probably something tricky about getting the implicits right.

@rickynils

This comment has been minimized.

Owner

rickynils commented Nov 9, 2011

Gen.resultOf does not generate functions, it generates results. In your example above, the type of both your expressions will be Gen[Array[Double]], that is they will both be generators that produces random array of doubles. To the shrinker, they are equal. The shrinker will just try to shrink the produced arrays. The difference is that, for Gen.resultOf, you have no control over which values are fed to the function. ScalaCheck will just use arbitrary[Double] for the inputs.

I'm not saying that it is impossible to implement "def shrinkable", but at least for the shrinker, I just don't think it is simpler to implement that than full-blown generator preconditions (or rather, postconditions, from the generator's point of view).

@rickynils rickynils closed this Nov 9, 2011

@JHeiner

This comment has been minimized.

JHeiner commented Nov 9, 2011

the type of both your expressions will be Gen[Array[Double]], that is they will both be generators that produces random array of doubles. To the shrinker, they are equal. The shrinker will just try to shrink the produced arrays.

Ah, I see: I really should have learned more about how the shrinker works...

I just don't think it is simpler to implement that than full-blown generator preconditions

I assumed a Boolean flag would be the easiest thing to implement (it so often is), but you would know better than anyone, naturally. It's disappointing when things that sound easy turn out not to be, yes?

Thanks again for the time you put into ScalaCheck: it is a very cool tool!

@rickynils rickynils reopened this Nov 9, 2011

@rickynils

This comment has been minimized.

Owner

rickynils commented Nov 9, 2011

I accidentally closed this issue earlier, reopening it now.

@JHeiner: I'm very happy for your feedback, it's interesting to hear how ScalaCheck is used by "real" users. You gave me some ideas on how to add preconditions automatically to for example containerOfN. I think I will be able to come up with a solution that is close to what you proposed, although more general. To make it work together with the shrinker, I think the "generator" and "property" concepts must be kind of merged. I actually feel that I have built up enough motivation to actually start implementing this soon :) Thanks for that!

@robinp

This comment has been minimized.

robinp commented Jan 31, 2012

I tried to get a grip on this by adding a canGenerate(t: T): Boolean method on Gen. Then the idea would have been to pass the T => Boolean verifier to the Shrink instances for filtering, possibly via forAllShrink.

But then quickly realized that Gen is covariant in T, which renders my efforts useless. Might be able to circumvent via hackery though, since a generator should ever get values of its generated type for checking, if I assume well.

Do you have any feasible solution in mind? I like the idea of Gen and Shrink (UnGen) being in a dual relation.

@rickynils

This comment has been minimized.

Owner

rickynils commented Feb 1, 2012

You can get around that specific problem by defining canGenerate like this: def canGenerate[U >: T](t: U): Boolean.

My latest thought on this issue has been to merge Prop and Gen by making Prop = Gen[Prop.Result]. That would probably make it easy to handle everything as preconditions. It would also make the implementation a bit cleaner, and maybe I could kill the few ugly mutable vars in both Prop and Gen along the way. However, that change is a bit invasive, and I haven't had time to experiment with it yet.

A canGenerate method that is checked each time shrinking is applied might be a simpler way, and maybe that is a better idea. However, since Shrink today is totally unaware of Gen, you either have to introduce the dual relation (which sounds like an attractive concept), or do the check in forAllShrink and other relevant places. If you come up with some code, I'd be happy to look at it.

@robinp

This comment has been minimized.

robinp commented Feb 1, 2012

Thank you - I was aware of the bound trick, but felt that downcasting the received U to T is a bit dirty (still feel it). Should work given the semantic constraints nevertheless.

You can check out https://github.com/robinp/scalacheck/tree/fenced-shrink, a good place to start is the ShrinkGuardSpecification. Its properties all fail, the interesting thing is that the returned evidence respects the Gen guards. Except for mapped Generators, since we would need a bijection to unmap and verify the values.

object Gen.apply now takes an optional T => Boolean. I added a sample bimap method on Gen, and as an example added fencing by default to some variants of choose (the Int variant now uses bimap to get back to the Long variant), suchThat, and listOfN.

Only the T1 => P variant of forAll transforms the shrinker to use the guard yet.

Results more or less satisfy me, however passing down the guard functions may be a bit cumbersome. Also it is worth thinking if a different design is possible to scale better. Polluting the Buildable also seems a bit rude, etc. What do you think?

Edit

Now that I check the multi-generator forAlls I see that they reduce to the single-generator case, so they also use the shrinker fencing.

Edit

I'm working on an other branch (sized-fences) recently to work out guards with sized and flatMap. The topic isn't as simple as seemed on the first try.

@nightscape

This comment has been minimized.

nightscape commented Apr 10, 2013

Sorry for bugging, but does anyone still work on this? I just tripped over this and it took me quite a while to figure out what was going on.

@rickynils

This comment has been minimized.

Owner

rickynils commented Apr 27, 2013

@nightscape: My ScalaCheck time is a bit limited nowadays, but my plan is to get around to do something about this, sometime, yes :) Don't feel sorry for bugging me, I need it...

@eriksoe

This comment has been minimized.

eriksoe commented Aug 26, 2013

Then I'll pipe up, too. I was a bit disappointed to learn that scalacheck had this shortcoming, me coming from the Erlang versions which don't (but which might have an easier time, given that they don't have to play by type system rules... otoh, they can never have "arbitrary[T]").
In any case, I hope you'll be able to find the time. Scalacheck is a good hammer to have.

rickynils added a commit that referenced this issue Sep 17, 2013

rickynils added a commit that referenced this issue Sep 20, 2013

New generator implementation, that should solve issue #8.
Gen now attaches the suchThat-filter to the generator result,
usable by Prop. Therefore, any shrinked values can be filtered
with the original generator filter.

For this to work, it is required that the various generators
uses suchThat to attach a "post-condition" to themselves. For
example, the Gen.oneOf implementation looks like this now:

  def oneOf[T](xs: Seq[T]): Gen[T] =
    choose(0, xs.size-1).map(xs(_)).suchThat(xs.contains)

All in all, the new implementation seems to work fine, and should
hopefully cause less confusion.
@rickynils

This comment has been minimized.

Owner

rickynils commented Sep 20, 2013

2d92eb6 introduces a new Gen implementation, that should solve this long-standing limitation. Prop is now able to use the filter attached with Gen.suchThat to sort out any invalid shrinked values. All the core generators now use suchThat to attach "generator invariants". This mean that, for example, forAll(choose(10,20)) { n => ... } never will be tested with any values below 10 or above 20, even if shrinking occurs.

If you write your own generator, you can just add a suchThat condition (but if you use the built-in generators you might not need to)

@rickynils rickynils closed this Sep 20, 2013

@reiddraper

This comment has been minimized.

reiddraper commented Nov 19, 2013

Seems like this solution is working nicely, but for what it's worth, I've proposed a different solution on the Haskell QuickCheck mailing list, as Haskell QC suffers the same issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment