proptest-stateful icon indicating copy to clipboard operation
proptest-stateful copied to clipboard

Improve shrinking algorithm to try removing multiple operations at once

Open nickelization opened this issue 1 year ago • 0 comments

The shrinking algorithm we've implemented has worked well for the tests we've written so far, but it's worth noting that it is limited to removing a single test operation at a time during shrinking. (There is one exception to this, which is that we automatically and immediately shrink out all operations that occur after the step that triggered the initial test failure as an optimization, but after that we only attempt to remove one step at a time.) This resulted in a shrinking algorithm that was relatively simple to implement and understand, but it brings two significant downsides:

  1. For tests with many operations, shrinking may be slow, especially if re-running a test case is itself a slow process.
  2. Depending on the preconditions specified, we may fail to shrink all the way to a minimal set of operations.

The latter issue is due to test cases that start with sequences like:

CREATE TABLE readyset;
DROP TABLE readyset;
CREATE TABLE readyset;

If step 3 is legitimately part of a minimal failing case, then we can't shrink it out...but we also can't shrink out step 2 because then the precondition for step 3 will fail (a table can't already exist before we create it), and we can't shrink out step 1 because the precondition for step 2 will fail (a table must exist for us to be able to drop it). So without the ability to try shrinking out multiple steps at once, we're unable to shrink out the first two steps.

All that said, it's not clear what the best alternative shrinking algorithm might look like. More research is needed here, and we'd love to hear from anyone who has any opinions or experience in this area.

nickelization avatar Jun 28 '23 20:06 nickelization