pkg/bisect: test a subset of releases

For older bugs (or for bugs on stable trees), our cause bisection
strategy times out while trying to iterate over all reachable tags.

Try to be smarter and only take a subset of them, thus limiting the time
we spend detecting the bug-free release.

Closes #3376.

2 files changed, 116 insertions, 4 deletions

diff --git a/pkg/bisect/bisect.go b/pkg/bisect/bisect.go
index 9ea5a6c04..8d83b0737 100644
--- a/pkg/bisect/bisect.go
+++ b/pkg/bisect/bisect.go
@@ -518,9 +518,12 @@ func (env *env) commitRangeForCause() (*vcs.Commit, *vcs.Commit, []*testResult,
 	if len(tags) == 0 {
 		return nil, nil, nil, fmt.Errorf("no release tags before this commit")
 	}
+	pickedTags := pickReleaseTags(tags)
+	env.log("picked %d out of %d release tags", pickedTags)
+
 	lastBad := env.commit
 	var results []*testResult
-	for _, tag := range tags {
+	for _, tag := range pickedTags {
 		env.log("testing release %v", tag)
 		com, err := env.repo.SwitchCommit(tag)
 		if err != nil {
@@ -1034,3 +1037,56 @@ func checkConfig(cfg *Config) error {
 func (env *env) log(msg string, args ...interface{}) {
 	env.cfg.Trace.Log(msg, args...)
 }
+
+// pickReleaseTags() picks a subset of revisions to test.
+// `all` is an ordered list of tags (from newer to older).
+func pickReleaseTags(all []string) []string {
+	if len(all) == 0 {
+		return nil
+	}
+	// First split into x.y.z, x.y.z-1, ... and x.y, x.y-1, ...
+	var subReleases, releases []string
+	releaseBegin := false
+	for _, tag := range all {
+		v1, _, rc, v3 := vcs.ParseReleaseTag(tag)
+		if v1 < 0 || rc < 0 && v3 < 0 {
+			releaseBegin = true
+			releases = append(releases, tag)
+		}
+		if !releaseBegin {
+			subReleases = append(subReleases, tag)
+		}
+	}
+	var ret []string
+	// Take 2 latest sub releases.
+	takeSubReleases := minInts(2, len(subReleases))
+	ret = append(ret, subReleases[:takeSubReleases]...)
+	// If there are a lot of sub releases, also take the middle one.
+	if len(subReleases) > 5 {
+		ret = append(ret, subReleases[len(subReleases)/2])
+	}
+	for i := 0; i < len(releases); i++ {
+		// Gradually increase step.
+		step := 1
+		if i >= 3 {
+			step = 2
+		}
+		if i >= 11 {
+			step = 3
+		}
+		if i%step == 0 || i == len(releases)-1 {
+			ret = append(ret, releases[i])
+		}
+	}
+	return ret
+}
+
+func minInts(vals ...int) int {
+	ret := vals[0]
+	for i := 1; i < len(vals); i++ {
+		if vals[i] < ret {
+			ret = vals[i]
+		}
+	}
+	return ret
+}
diff --git a/pkg/bisect/bisect_test.go b/pkg/bisect/bisect_test.go
index 600a68b60..d44532fe0 100644
--- a/pkg/bisect/bisect_test.go
+++ b/pkg/bisect/bisect_test.go
@@ -353,9 +353,9 @@ var bisectionTests = []BisectionTest{
 		introduced:  "605",
 		extraTest: func(t *testing.T, res *Result) {
 			// False negative probability of each run is ~35%.
-			// We get two "good" results, so our accumulated confidence is ~42%.
-			assert.Less(t, res.Confidence, 0.5)
-			assert.Greater(t, res.Confidence, 0.4)
+			// We get three "good" results, so our accumulated confidence is ~27%.
+			assert.Less(t, res.Confidence, 0.3)
+			assert.Greater(t, res.Confidence, 0.2)
 		},
 	},
 	// Test bisection returns correct cause with different baseline/config combinations.
@@ -955,3 +955,59 @@ func TestMostFrequentReport(t *testing.T) {
 		})
 	}
 }
+
+func TestPickReleaseTags(t *testing.T) {
+	tests := []struct {
+		name string
+		tags []string
+		ret  []string
+	}{
+		{
+			name: "upstream-clang",
+			tags: []string{
+				"v6.5", "v6.4", "v6.3", "v6.2", "v6.1", "v6.0", "v5.19",
+				"v5.18", "v5.17", "v5.16", "v5.15", "v5.14", "v5.13",
+				"v5.12", "v5.11", "v5.10", "v5.9", "v5.8", "v5.7", "v5.6",
+				"v5.5", "v5.4",
+			},
+			ret: []string{
+				"v6.5", "v6.4", "v6.3", "v6.1", "v5.19", "v5.17", "v5.15",
+				"v5.13", "v5.10", "v5.7", "v5.4",
+			},
+		},
+		{
+			name: "upstream-gcc",
+			tags: []string{
+				"v6.5", "v6.4", "v6.3", "v6.2", "v6.1", "v6.0", "v5.19",
+				"v5.18", "v5.17", "v5.16", "v5.15", "v5.14", "v5.13",
+				"v5.12", "v5.11", "v5.10", "v5.9", "v5.8", "v5.7", "v5.6",
+				"v5.5", "v5.4", "v5.3", "v5.2", "v5.1", "v5.0", "v4.20", "v4.19",
+				"v4.18",
+			},
+			ret: []string{
+				"v6.5", "v6.4", "v6.3", "v6.1", "v5.19", "v5.17", "v5.15",
+				"v5.13", "v5.10", "v5.7", "v5.4", "v5.1", "v4.19", "v4.18",
+			},
+		},
+		{
+			name: "lts",
+			tags: []string{
+				"v5.15.10", "v5.15.9", "v5.15.8", "v5.15.7", "v5.15.6",
+				"v5.15.5", "v5.15.4", "v5.15.3", "v5.15.2", "v5.15.1",
+				"v5.15", "v5.14", "v5.13", "v5.12", "v5.11", "v5.10",
+				"v5.9", "v5.8", "v5.7", "v5.6", "v5.5", "v5.4",
+			},
+			ret: []string{
+				"v5.15.10", "v5.15.9", "v5.15.5", "v5.15", "v5.14", "v5.13",
+				"v5.11", "v5.9", "v5.7", "v5.5", "v5.4",
+			},
+		},
+	}
+	for _, test := range tests {
+		test := test
+		t.Run(test.name, func(t *testing.T) {
+			ret := pickReleaseTags(append([]string{}, test.tags...))
+			assert.Equal(t, test.ret, ret)
+		})
+	}
+}