Skip to content

Recursive bisect strategy

gitlab-qa-bot requested to merge github/fork/urbanautomaton/recursive-bisect-strategy into master

Created by: urbanautomaton

Hi,

First, thank you very much for the new --bisect feature - it's already saved me and a colleague hours of painstaking manual debugging, and it doesn't get much better than that. :)

While looking at the implementation recently, I came across a way I think it might be possible to improve the bisection strategy in ExampleMinimizer. Presently a round-based approach is used, which attempts to find ~50% of the current residual candidates to ignore in each round. It first searches for contiguous blocks of candidates to ignore, then for more complex combinations of the candidate set. If it can't find ~50% of the candidate set to ignore at any stage, it concludes that the run is irreducible.

In the case where there is a single, singly-dependent failure (i.e. when there is a single expected failure, which depends upon a single preceding example), I believe the current strategy is optimal.

However, when there are multiple preceding examples that combine to cause the expected failure, then there are cases that the current strategy fails to reduce, and cases that it successfully reduces, but could reduce in fewer steps.

Examples

Since the problem cases involve expected failures that depend on multiple preceding examples, I first expanded the FakeBisectRunner class to support simulating multiply-dependent failures.

I then added failing test cases:

The rounds-based strategy will not reduce the case C C C C C C C I F (where C = culprit, I = innocent, and F = expected failure), as the first round fails to remove 50% of the candidates.

Also, the rounds-based strategy takes 70 runs to infer that the following is irreducible: C C C C C C C C F. With a recursive strategy, I believe this should be possible in 1 + 2 + 4 + 8 = 15 runs:

  • 1 run to determine that at least one of the candidates is responsible
  • 2 runs to determine that both halves of the candidates are responsible
  • 4 runs to determine that all quarters of the candidates are responsible
  • 8 runs to determine that all of the candidates are responsible

(My test case originally had 14 runs, because I hadn't accounted for the first step.)

Recursive strategy

Instead of searching amongst combinations of the candidate set, the recursive algorithm always splits its candidate set into two slices. Informally:

  1. Is the candidate set a single example?
    • yes: return it as the culprit
    • no:
      1. Divide the candidate set in two
      2. Run each slice with the expected failure
      3. Can either set be eliminated?
        • yes: recurse on other set
        • no: recurse on both sets, retaining other set as "fixed" for each run

(Where "fixed" means while reducing one set, the other set is always included as part of each run.)

In case my lousy prose description makes no sense, here is a visual representation of a simple case where there are two culprit examples, one in each half of the candidate set:

I've implemented the above strategy in this PR, and the additional test cases now pass.

Formatter

There remain some failures elsewhere in the suite, however, because the formatter output no longer matches the previous algorithm's, and because the recursive strategy doesn't proceed in rounds, it's difficult to restore these tests without changing the bisection output.

So, before I tackle that: is this something you'd be interested in merging? I'm happy to modify anything that's unclear. :)

Cheers, Simon

Merge request reports