Test case minimizer #456

Closed
opened 2025-07-01 10:54:58 +02:00 by wetneb · 2 comments
Owner

When we have an example of a bad merge (or any other test case, for instance one that triggers a panic), it is often useful to minimize it, so that we can more easily debug it, and potentially add it to our test suite once the bug is fixed.

It's generally not too hard to do it manually, but it would still be interesting to have a helper to automatically minimize those examples. Such sorts of heuristics are often used in combination with fuzzers (#450).

I'm thinking something like this could work. It would take as inputs:

  • A directory containing a test case in the form of base, left and right revisions, not necessarily with an expected output
  • A shell command to run on the test case. The command would take as only argument the path to the directory, which will contain a test case of the above form (potentially reduced by the utility)
  • Optionally, an expected return code for the command
  • Optionally, a numeric seed to control the random parts of the algorithm

And then it would repeatedly

  • Match the three files with the same matching algorithm we use in structured merging (with pre-matching induced by a line-based merge)
  • Randomly pick a syntax element (or a range of consecutive syntax elements) with an exact match in all three revisions
  • Generate new syntax trees where this element is omitted in all three revisions
  • Pretty-print those trees and check that they parse again, and that the corresponding parse tree is isomorphic to the one we meant
  • Write out those new trees to a directory and run the supplied command on them, checking that it has the expected status code
  • Start the process again with those new reduced files

And it would stop when it doesn't progress anymore (say, reaches a threshold of unsuccessful reduction attempts on the current test case).

When we have an example of a bad merge (or any other test case, for instance one that triggers a panic), it is often useful to minimize it, so that we can more easily debug it, and potentially add it to our test suite once the bug is fixed. It's generally not too hard to do it manually, but it would still be interesting to have a helper to automatically minimize those examples. Such sorts of heuristics are often used in combination with fuzzers (#450). I'm thinking something like this could work. It would take as inputs: * A directory containing a test case in the form of base, left and right revisions, not necessarily with an expected output * A shell command to run on the test case. The command would take as only argument the path to the directory, which will contain a test case of the above form (potentially reduced by the utility) * Optionally, an expected return code for the command * Optionally, a numeric seed to control the random parts of the algorithm And then it would repeatedly * Match the three files with the same matching algorithm we use in structured merging (with pre-matching induced by a line-based merge) * Randomly pick a syntax element (or a range of consecutive syntax elements) with an exact match in all three revisions * Generate new syntax trees where this element is omitted in all three revisions * Pretty-print those trees and check that they parse again, and that the corresponding parse tree is isomorphic to the one we meant * Write out those new trees to a directory and run the supplied command on them, checking that it has the expected status code * Start the process again with those new reduced files And it would stop when it doesn't progress anymore (say, reaches a threshold of unsuccessful reduction attempts on the current test case).
Owner

Oh this would be amazing! I'd argue that manual minimization is actually pretty daunting at times, because of how easy it is to slip from a conflict that requires structural resolution (which is what reproduces the big at hand) to one that's solvable by a line-based merge

Oh this would be amazing! I'd argue that manual minimization is actually pretty daunting at times, because of how easy it is to slip from a conflict that requires structural resolution (which is what reproduces the big at hand) to one that's solvable by a line-based merge
Author
Owner

I had a go at it… I'm not sure how useful it will be in practice outside of fuzzing contexts, because the work of manually minimizing gets replaced by the work of writing a script which defines the conditions under which we want to minimize the test case, which can get non-trivial I would say.

I had a go at it… I'm not sure how useful it will be in practice outside of fuzzing contexts, because the work of manually minimizing gets replaced by the work of writing a script which defines the conditions under which we want to minimize the test case, which can get non-trivial I would say.
wetneb self-assigned this 2025-07-04 12:41:13 +02:00
Sign in to join this conversation.
No milestone
No project
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: mergiraf/mergiraf#456
No description provided.