And a related question: I see one of the value propositions of PropCheck is that it “shrinks” the counterexamples is finds by traversing the tree of generated examples (somehow). I can take most of this on faith, but I still have trouble understanding how shrinking is measured. What is being minimized when shrinking? What is the figure of merit?
1 Like
If the samplers you already have really do create the full spectrum of valid instances, yes, forwarding to those in generate so that itype works is generally a good idea. See also the docs section on the interfaces to hook into here.
It’s not required though - you can just as well define a generator for your instances based purely on map and filter, which means you don’t need to think about shrinking your type right away because you get those shrinks “for free” from the composition of the existing shrinkers & generators and their generate and shrink. This won’t always give you good shrinks (sometimes you want to shrink into a particular direction, regardless of how the value was generated), but that’s a much more advanced topic that I need to write some docs on 
Measuring shrinking values is a bit difficult - after all, the goal is to create a smaller (to human eyes) instance of the given type. It’s very subjective what that means, but there are some generalities you can apply. For example, a 0.0 is less “complex” of a value than 1234651.3465, so it’s usually considered smaller for shrinking purposes. Similarly, an array with just 2 values is generally considered simpler/smaller than an array with 4123 values, even if both arrays otherwise exhibit the same properties.
Expanding on that - consider checking whether all arrays of positive integers are sorted. Surely, there are lots of counterexamples to that, like [164, 45, 128, 202, 87], [5,3,2,1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], but there’s only one example that’s minimal: [1, 0], the array with minimal values and minimal length.
This is of course not correct for all properties and all value domains; the “minimal counterexample” can look quite different depending on what kind of values you’re mostly interested in. For example, if you’re interested in finding the smallest possible counterexample for arrays of Int8, it’ll be [-127, -128], because the smallest possible counterexample numerically is a negative number with larger absolute value. By default, PropCheck won’t give you that, because a smaller absolute value is usually more desirable for humans to think about; the bitpattern underlying the number is simpler (or shorter, if you remove leading zeros). To have PropCheck give you those smaller numerical shrinks, you simply give e.g. itype a shrinking function producing those values:
julia> using PropCheck
julia> vect = PropCheck.vector(ival(4), itype(Int8, PropCheck.shrinkTowards(typemin(Int8))));
julia> check(issorted, vect)
┌ Info: Found counterexample for 'issorted', beginning shrinking...
│ Counterexample =
│ 4-element Vector{Int8}:
│ -2
│ 58
│ 21
└ -85
[ Info: 32 counterexamples found
2-element Vector{Int8}:
-127
-128
shrinkTowards currently only has definitions for numeric types (<: Integer, <: AbstractFloat, Bool) because shrinking towards a general object is quite a bit harder - e.g. shrinking towards a given string could be an option by working through inserts, deletions & character changes, but I’ll have to think about how to best do that to make sure the full possible space between a given source & target string is generateable.
Circling back around to your question - anything you want, really! With a custom shrinking function (which you can supply to everything that generates a value), YOU get to decide how you want to shrink/minimize things. PropCheck.jl just tries to give you some sane defaults for types from Base (or at least, those I’ve gotten around to implementing generate and shrink for). E.g. in Composing Generators, I use PropCheck.noshrink to make sure some strings don’t shrink when shrinking the object the generator is used in, because looking at a student with a name is nicer than looking at a student with the empty string as a name. This is generally applicable with any custom shrinking function; whichever values you consider to be smaller for the purpose of that shrinking function are what PropCheck.jl considers “smaller” (which is also why it’s important that shrinking functions can’t produce shrinking loops - i.e. a shrinking function must never produce a value that, when shrunk with the same shrinking function again, could lead to the initial value).
3 Likes
This is a wonderful explanation, thank you!
A slightly related follow up question: during the search / fuzzing / shrinking is PropCheck.jl using some form of coverage tracking, or is it just a completely random search?
1 Like
The only guidance PropCheck.jl has at the moment is whatever the shrinking function returns, shuffled to a random order (lazily). In practical tests on my applications, I’ve found that to be usually best. In terms of search, it’s completely random; I guess you could bias it by giving PropCheck.jl a custom AbstractRNG, but I’d much rather give a different interface for that. There’s also an idea floating around in my head about prioritizing some special cases of a type first (e.g., having an integrated shrinker that gives Inf, -Inf, NaN, 1.0, 0.0 first, before generating random floating point values). The interface for that would likely be “more composition of some basic integrated shrinkers” though, instead of a bespoke thing.
There is no coverage tracking/coverage informed generation in PropCheck.jl at the moment, no. I do eventually want something like that though, see this issue. So for now, you’ll have to manually construct integrated shrinkers with map and filter if you want to hit a particular branch. This kind of goes against property based testing though, since it focuses on the particularities of the code, not the properties you would like that code to have - after all, there’s (so far) no guarantee that the code in question is actually good in terms of the properties you want it to have (though of course, in order to check some properties, you need to ensure not to accidentally trigger an error you’re not interested in - that’s a bit orthogonal to code coverage though).
1 Like
There was a Juliacon talk scheduled named “Please steal Hypothesis”, by one of the authors of the quite popular Python package for property-based testing.
I thought it highly relevant for this thread, so wanted to point it out, but it seems to have disappeared? Was it retracted/ cancelled?
Huh, indeed, it’s gone - I was looking forward to that talk! That’s a shame 
EDIT: Looking at the changelog, seems it had to be cancelled, though the reason isn’t shared. It’s unfortunate, but I guess that’s how it goes…
Bummer! You could always ask him directly (www.zhd.dev), maybe the emergence of this package made his talk unnecessary 
(happy/sad), or he has some input on it?
v0.10.0
Well, this has happened faster than I’d have hoped - the first breaking release (but hopefully not too breaking). For a full changelog, please check out the release notes!
Some highlights:
- There are now
FiniteIntegrated, integrated shrinkers that only produce a finite number of values. - New pre-built integrated shrinkers, like
ifloat(producing only non-Inf and non-NaN values),ifloatnan(producing all valid bitpatterns forNaNs),ifloatinf(producing all infinities),ifloatinfnan(the combination of the latter two),iposint(producing positive signed integers) andinegint(producing negative signed integers). IntegratedChain, an integrated shrinker for chaining finite & infinite integrated shrinkers together (very useful for testing some know special cases first, before starting fuzzing in earnest!)
Please do check out the docs on the new features, and don’t hesitate to open issues about bugs you encounter on the issue tracker!
11 Likes
Thank you for this package, I think it’s amazing 
Is there a way to use itype with a trait or similar? I’d like to test if all the functions with a certain trait satisfy a given property. For example, say I want to test an inverse(f::Invertible) implementation, but there are too many invertible functions to test this for every function individually; is there a way to specify this in PropCheck.jl?
There’s no inherent functionality linking some implementation of traits and functions that can take those traits, no. That will depend highly on how the traits are implemented & used in some package.
1 Like