search

sageserpent-open / americium

Generation of test case data for Scala and Java, in the spirit of QuickCheck. When your test fails, it gives you a minimised failing test case and a way of reproducing the failure immediately.
MIT License
15 stars 1 forks source link

Premature cutoff of supplied cases. #29

Closed sageserpent-open closed 2 years ago

sageserpent-open commented 2 years ago

Sometimes a trials fails to supply cases, even though the maximum number specified by .withLimit hasn't been exceeded and there are obvious cases that could have been generated but weren't.

This is probably due to the core iterator's ad-hoc determination of case starvation being triggered too early in TrialsImplementation.interpreter. To be honest that code needs an overhaul anyway.

sageserpent-open commented 2 years ago

From debugging cases in the wild, it seems there are at least two reasons for this:

  1. The aforementioned premature declaration of case starvation - I'm fairly certain this is triggered when low values are supplied to .withLimit, 1 being an obvious tricky case.
  2. There is a default complexity limit of 100 that is applied even when shrinkage is not taking place - this was originally put in as a way of stopping stack overflow back when the case generation interpreter called itself recursively to implement alternation. I'm not sure this is required anymore (although shrinkage will still need to set a limit), so it's worth experimenting to see if this can be safely dropped.
sageserpent-open commented 2 years ago

It turns out that in order to allow recursive definition of a Trials instance, the existing codebase uses the default complexity limit to prevent infinite recursion (albeit without stack overflow - it is unwound by trampolining / continuations or suchlike, so we just see endless looping). For now the complexity limit has been increased so as to pass a new test to check on the second possibility above, but we need a more robust strategy...

sageserpent-open commented 2 years ago

Now have a more robust solution that prevents endless looping but allows trials of arbitrarily large specified sizes of collections. Trials of collections of varying size will still stick to smaller sizes that result from the cutoff against endless looping; if the user wants giant collections, they have to ask for them explicitly, possibly flat mapping in a size parameter if the size has to vary.

sageserpent-open commented 2 years ago

The fix for the second of the two problems mentioned in the bug description is slated to go out in release 0.1.21 . The first problem is still a possibility but hasn't been seen much in the wild.

sageserpent-open commented 2 years ago

Release 0.1.23 sees the API extended to support specifying a complexity wall, along with a limit for the number of cases supplied by a trials instance, so for example, if a trials of collections of arbitrary size is synthesised, the complexity can be increased to allow cases of large sized collections to be produced.

By default, the implementation imposes its own internal complexity wall of 100, which is quite low.

Furthermore, when a trials of a fixed-sized collection is requested, there is some special case logic that keeps resetting the complexity for each iterated flat-mapping of a new collection element trials - so while the computation of a trials for a collection element has to stick within the complexity wall (and in the context of the computation that requires the fixed-sized collection trials, to boot). So for trials of fixed-sized collections there is less need to explicitly specify a large complexity wall, although it may still be necessary in some cases where the trials of the collection elements are themselves very complex.

Finally, it is possible to query the complexity in the context of a trials computation (see here: https://github.com/sageserpent-open/americium/blob/2888cf18f0bb18dd0ef8a7f2ca8ef44ef8bd4da2/src/test/scala/com/sageserpent/americium/TrialsSpec.scala#L93) so that the complexity can guide the computation of a trials instance. In that case linked to above, the complexity is used to weight against further recursive definition of a trials instance, thus preventing the trials computation from going into a non-terminating computation as it builds up an ever-growing tree.

sageserpent-open commented 2 years ago

Finally, the first problem of case starvation has been fixed. Tests that reproduce both modes of failure have been added upfront, the failures observed and then fixed to pass the tests. Both fixes are included in release 0.1.24.