From 03d9c195daed8fca30b642783f35657aa7e32209 Mon Sep 17 00:00:00 2001
From: Aleksandr Nogikh <nogikh@google.com>
Date: Thu, 24 Aug 2023 18:24:04 +0200
Subject: 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.
---
 pkg/bisect/bisect.go | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 57 insertions(+), 1 deletion(-)

(limited to 'pkg/bisect/bisect.go')

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
+}
-- 
cgit mrf-deployment