shrinking-challenge
shrinking-challenge copied to clipboard
jlink
Phrasing issue in "large union list", and perhaps an extension to that problem
Heya, just some minor feedback for this challenge.
In particular, a shrinker cannot hope to normalise this unless it is able to either split or join elements of the larger list. For example, it would have to be able to transform one of
[[0, 1, -1, 2, -2]]and[[0], [1], [-1], [2], [-2]]into the other.
"cannot hope to normalise" is too strongly worded. Correct me if I'm wrong, but it's hinting that a shrinker must split or join a sample in place in order to achieve the minimal counterexample? If so, there are definitely other strategies that exist to allow normalization in this challenge. If I am on the right track, I see some problems that arise from naively splitting/joining, which might trip up some shrinkers. If you're joining/splitting without respecting the constraints that were declared on the original lists, you might find a counterexample that doesn't respect the original generator.
A couple of extensions to the challenge might be:
- The inner lists must have a length of 2 or less - a smallest counterexample might be
[[0], [1, -1], [2, -2]], whilst[[0, 1, -1, 2, -2]]is invalid. - The inner lists must have a length of 2 or more - the smallest counterexample is undoubtedly
[[0, 1, -1, 2, -2]], whilst[[0], [1], [-1], [2], [-2]]is invalid.
FWIW, the property-based testing lib that I'm currently building uses a different strategy to go from something like an initial counterexample split across two lists e.g. [[0, 1, -1], [2, -2]] to the "smallest counterexample" [[0, 1, -1, 2, -2]] (and it normalizes under this challenge).
Each sample from a generator is assigned a complexity metric. And every time an example is shrunk, the result is re-assigned a complexity via a complexity function. The complexity of a primitive (e.g. an integer) is a proportion of the biggest possible sample that a generator might output, e.g. for integers between 0 and 5, 0 has a complexity of 0, 1 has a complexity of 20, 2 has a complexity of 40 etc. The complexity of an array is the sum of the complexities of it's elements, and it also inherits some added complexity relative to it's length. This scoring system favours elements clustered in one big array, rather than many small arrays. The complexity function is super general and also has a meaningful implementation under bind.
The mechanism by which it attempts normalization, is when a property fails, and we have found the smallest shrink for that failure, we will tweak the "size" parameter and run the property again, collecting the smallest shrinks across multiple runs. Then, it will simply pick the example with the lowest complexity.
"cannot hope to normalise" is too strongly worded.
Do you have a more correct formulation in mind?
A couple of extensions to the challenge might be:
* The inner lists must have a length of 2 or less - a smallest counterexample might be `[[0], [1, -1], [2, -2]]`, whilst `[[0, 1, -1, 2, -2]]` is invalid. * The inner lists must have a length of 2 or more - the smallest counterexample is undoubtedly `[[0, 1, -1, 2, -2]]`, whilst `[[0], [1], [-1], [2], [-2]]` is invalid.
I suggest you add those two variants as additional challenges. Changing an existing one would require that all libs would have to change their implementation and reports synchronically. We are happy to accept such a PR.
Each sample from a generator is assigned a complexity metric. And every time an example is shrunk, the result is re- assigned a complexity via a complexity function. [...]
That sounds similiar to what jqwik is doing. In jqwik it's called distance function but the idea is the same.
That sounds similiar to what jqwik is doing. In jqwik it's called distance function but the idea is the same.
"Distance" as in distance from the origin?
Distance from the simplest possible generated value. You can call that „origin“ :-)
Nice, I like that terminology ("distance").
I'll try and submit a reword at some point. I'm just slowly making my way through all the challenges.