Repository: bazelbuild/bazelisk
Pull request #357 (2022-09-05 15:40:46)

Fix performance issue for floating version values
Using a floating version such as "5.x" previously meant that Bazelisk would send O(LTS releases) requests to GCS, thus resulting in noticeable lag.

This commit changes the code so that floating versions exploit a "stop early" optimization similar to the "last N" use case, thus resulting in significantly fewer GCS requests (from 106 down to two).

Fixes https://github.com/bazelbuild/bazelisk/issues/339


Patch:
diff --git a/core/repositories.go b/core/repositories.go
index 8a2919c..45bbbe9 100644
--- a/core/repositories.go
+++ b/core/repositories.go
@@ -18,10 +18,27 @@ const (
 // DownloadFunc downloads a specific Bazel binary to the given location and returns the absolute path.
 type DownloadFunc func(destDir, destFile string) (string, error)
 
+type ReleaseFilter func(matchesSoFar int, currentVersion string) bool
+
+func lastNReleases(max int) ReleaseFilter {
+	return func(matchesSoFar int, currentVersion string) bool {
+		return max < 1 || matchesSoFar < max
+	} 
+}
+
+// filterReleasesByTrack only works reliably if iterating on Bazel versions in descending order.
+func filterReleasesByTrack(track int) ReleaseFilter {
+	prefix := fmt.Sprintf("%d.", track)
+	return func(matchesSoFar int, currentVersion string) bool {
+		return matchesSoFar == 0 && strings.HasPrefix(currentVersion, prefix)
+	}
+}
+
 // ReleaseRepo represents a repository that stores LTS Bazel releases.
 type ReleaseRepo interface {
-	// GetReleaseVersions returns a list of all available release versions. If lastN is smaller than 1, all available versions are being returned.
-	GetReleaseVersions(bazeliskHome string, lastN int) ([]string, error)
+	// GetReleaseVersions returns a list of all available release versions that match the given filter function.
+	// Warning: the filter only works reliably if the versions are processed in descending order!
+	GetReleaseVersions(bazeliskHome string, filter ReleaseFilter) ([]string, error)
 
 	// DownloadRelease downloads the given Bazel version into the specified location and returns the absolute path.
 	DownloadRelease(version, destDir, destFile string) (string, error)
@@ -117,13 +134,15 @@ func (r *Repositories) resolveFork(bazeliskHome string, vi *versions.Info) (stri
 
 func (r *Repositories) resolveRelease(bazeliskHome string, vi *versions.Info) (string, DownloadFunc, error) {
 	lister := func(bazeliskHome string) ([]string, error) {
-		var lastN int
-		// Optimization: only fetch last (x+1) releases if the version is "latest-x".
-		// This does not work if the version is "4.x", i.e. if TrackRestriction is set.
-		if vi.TrackRestriction == 0 {
-			lastN = vi.LatestOffset + 1
+		var filter ReleaseFilter
+		if vi.TrackRestriction > 0 {
+			// Optimization: only fetch matching releases if an LTS track is specified.
+			filter = filterReleasesByTrack(vi.TrackRestriction)
+		} else {
+			// Optimization: only fetch last (x+1) releases if the version is "latest-x".
+			filter = lastNReleases(vi.LatestOffset + 1)
 		}
-		return r.Releases.GetReleaseVersions(bazeliskHome, lastN)
+		return r.Releases.GetReleaseVersions(bazeliskHome, filter)
 	}
 	version, err := resolvePotentiallyRelativeVersion(bazeliskHome, lister, vi)
 	if err != nil {
@@ -187,29 +206,14 @@ func resolvePotentiallyRelativeVersion(bazeliskHome string, lister listVersionsF
 		return "", fmt.Errorf("unable to determine latest version: %v", err)
 	}
 
-	if vi.TrackRestriction > 0 {
-		available = restrictToTrack(available, vi.TrackRestriction)
-	}
-
 	index := len(available) - 1 - vi.LatestOffset
 	if index < 0 {
-		return "", fmt.Errorf("cannot resolve version \"%s\": There are only %d Bazel versions", vi.Value, len(available))
+		return "", fmt.Errorf("cannot resolve version \"%s\": There are not enough matching Bazel releases (%d)", vi.Value, len(available))
 	}
 	sorted := versions.GetInAscendingOrder(available)
 	return sorted[index], nil
 }
 
-func restrictToTrack(versions []string, track int) []string {
-	filtered := make([]string, 0)
-	prefix := fmt.Sprintf("%d.", track)
-	for _, v := range versions {
-		if strings.HasPrefix(v, prefix) {
-			filtered = append(filtered, v)
-		}
-	}
-	return filtered
-}
-
 // DownloadFromBaseURL can download Bazel binaries from a specific URL while ignoring the predefined repositories.
 func (r *Repositories) DownloadFromBaseURL(baseURL, version, destDir, destFile string) (string, error) {
 	if !r.supportsBaseURL {
@@ -271,7 +275,7 @@ type noReleaseRepo struct {
 	err error
 }
 
-func (nrr *noReleaseRepo) GetReleaseVersions(bazeliskHome string, lastN int) ([]string, error) {
+func (nrr *noReleaseRepo) GetReleaseVersions(bazeliskHome string, filter ReleaseFilter) ([]string, error) {
 	return nil, nrr.err
 }
 
diff --git a/repositories/BUILD b/repositories/BUILD
index 7747adf..c612bf4 100644
--- a/repositories/BUILD
+++ b/repositories/BUILD
@@ -9,6 +9,7 @@ go_library(
     importpath = "github.com/bazelbuild/bazelisk/repositories",
     visibility = ["//visibility:public"],
     deps = [
+        "//core:go_default_library",
         "//httputil:go_default_library",
         "//platforms:go_default_library",
         "//versions:go_default_library",
diff --git a/repositories/gcs.go b/repositories/gcs.go
index 3054429..0d9c7a0 100644
--- a/repositories/gcs.go
+++ b/repositories/gcs.go
@@ -10,6 +10,7 @@ import (
 	"log"
 	"strings"
 
+	"github.com/bazelbuild/bazelisk/core"
 	"github.com/bazelbuild/bazelisk/httputil"
 	"github.com/bazelbuild/bazelisk/platforms"
 	"github.com/bazelbuild/bazelisk/versions"
@@ -35,13 +36,13 @@ type GCSRepo struct{}
 
 // ReleaseRepo
 
-// GetReleaseVersions returns the versions of all available Bazel releases in this repository.
-func (gcs *GCSRepo) GetReleaseVersions(bazeliskHome string, lastN int) ([]string, error) {
+// GetReleaseVersions returns the versions of all available Bazel releases in this repository that match the given filter.
+func (gcs *GCSRepo) GetReleaseVersions(bazeliskHome string, filter core.ReleaseFilter) ([]string, error) {
 	history, err := getVersionHistoryFromGCS()
 	if err != nil {
 		return []string{}, err
 	}
-	releases, err := gcs.removeCandidates(history, lastN)
+	releases, err := gcs.removeCandidates(history, filter)
 	if err != nil {
 		return []string{}, err
 	}
@@ -130,17 +131,31 @@ func (gcs *GCSRepo) DownloadRelease(version, destDir, destFile string) (string,
 	return httputil.DownloadBinary(url, destDir, destFile)
 }
 
-func (gcs *GCSRepo) removeCandidates(history []string, lastN int) ([]string, error) {
-	var resolvedLimit int
-	if lastN < 1 {
-		resolvedLimit = len(history)
-	} else {
-		resolvedLimit = lastN
-	}
-
+func (gcs *GCSRepo) removeCandidates(history []string, filter core.ReleaseFilter) ([]string, error) {
 	descendingReleases := make([]string, 0)
-	for hpos := len(history) - 1; hpos >= 0 && len(descendingReleases) < resolvedLimit; hpos-- {
+	filterPassed := false
+	// Iteration in descending order is important:
+	// - ReleaseFilter won't work correctly otherwise
+	// - It makes more sense in the "latest-n" use case 
+	for hpos := len(history) - 1; hpos >= 0; hpos-- {
 		latestVersion := history[hpos]
+		pass := filter(len(descendingReleases), latestVersion)
+		if pass {
+			filterPassed = true
+		} else {
+			// Underlying assumption: all matching versions are in a single continuous sequence.
+			// Consequently, if the filter returns false, this means:
+			if filterPassed {
+				// a) "break" if we've seen a match before (because all future version won't match either)
+				break
+			} else {
+				// b) "continue looking" if we've never seen a match before
+				continue
+			}
+		}
+		// Obviously this only works for the existing filters (lastN and track-based) and
+		// because versions in history are sorted.
+
 		_, isRelease, err := listDirectoriesInReleaseBucket(latestVersion + "/release/")
 		if err != nil {
 			return []string{}, fmt.Errorf("could not list available releases for %v: %v", latestVersion, err)
@@ -149,10 +164,6 @@ func (gcs *GCSRepo) removeCandidates(history []string, lastN int) ([]string, err
 			descendingReleases = append(descendingReleases, latestVersion)
 		}
 	}
-
-	if lastN > 0 && len(descendingReleases) < lastN {
-		return []string{}, fmt.Errorf("requested %d latest releases, but only found %d", lastN, len(descendingReleases))
-	}
 	return reverseInPlace(descendingReleases), nil
 }
 


Test patch:
diff --git a/bazelisk_version_test.go b/bazelisk_version_test.go
index bd83cf7..7e41b96 100644
--- a/bazelisk_version_test.go
+++ b/bazelisk_version_test.go
@@ -166,7 +166,7 @@ func TestResolveLatestVersion_ShouldFailIfNotEnoughReleases(t *testing.T) {
 	if err == nil {
 		t.Fatal("Expected ResolveVersion() to fail.")
 	}
-	expectedError := "unable to determine latest version: requested 2 latest releases, but only found 1"
+	expectedError := "cannot resolve version \"latest-1\": There are not enough matching Bazel releases (1)"
 	if err.Error() != expectedError {
 		t.Fatalf("Expected error message %q, but got '%v'", expectedError, err)
 	}