Skip to content
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

Improve shrinking algorithm to try removing multiple operations at once #6

Open
nickelization opened this issue Jun 28, 2023 · 0 comments
Labels
enhancement New feature or request

Comments

@nickelization
Copy link
Contributor

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 nickelization added the enhancement New feature or request label Jun 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant