Repository: chainguard-dev/apko (go)

Issue:
Solver does not consider provided package version in provides entries
Consider the following repository:

- `a-1-r0`
- `b-2-r0`, provides `a=0.9`

If a user requests package `a`, `b` will be selected instead of `a` as it provides `a` (at version `0.9`) but has a higher package version (`2`).  Instead, `a` should be selected as it provides `a` at version `1`.

Pull request description:
handle versioning in provides
Fixes #632 

As described in #632, the solver found all packages that either were named with the target (e.g. `a`) and then sorted them. The sorting algorithm, when it came to version order, used the _package_ version. But if the package is there just because it provides something, it should use the _provides_ version.

This fixes it.

Patch:
diff --git a/pkg/apk/impl/repo.go b/pkg/apk/impl/repo.go
index da7fdac..908d86d 100644
--- a/pkg/apk/impl/repo.go
+++ b/pkg/apk/impl/repo.go
@@ -345,14 +345,14 @@ func (p *PkgResolver) ResolvePackage(pkgName string) (pkgs []*repository.Reposit
 		if len(packages) == 0 {
 			return nil, fmt.Errorf("could not find package %s in indexes: %w", pkgName, err)
 		}
-		sortPackages(packages, nil, nil, pin)
+		sortPackages(packages, nil, name, nil, pin)
 	} else {
 		providers, ok := p.providesMap[name]
 		if !ok || len(providers) == 0 {
 			return nil, fmt.Errorf("could not find package, alias or a package that provides %s in indexes", pkgName)
 		}
 		// we are going to do this in reverse order
-		sortPackages(providers, nil, nil, "")
+		sortPackages(providers, nil, name, nil, "")
 		packages = providers
 	}
 	for _, pkg := range packages {
@@ -450,7 +450,7 @@ func (p *PkgResolver) getPackageDependencies(pkg *repository.RepositoryPackage,
 			if len(pkgs) == 0 {
 				return nil, nil, fmt.Errorf("could not find package %s in indexes", dep)
 			}
-			sortPackages(pkgs, nil, existing, "")
+			sortPackages(pkgs, nil, name, existing, "")
 			depPkg = pkgs[0].RepositoryPackage
 		} else {
 			// it was not the name of a package, see if some package provides this
@@ -481,7 +481,7 @@ func (p *PkgResolver) getPackageDependencies(pkg *repository.RepositoryPackage,
 				continue
 			}
 			// we are going to do this in reverse order
-			sortPackages(providers, pkg, existing, "")
+			sortPackages(providers, pkg, name, existing, "")
 			depPkg = providers[0].RepositoryPackage
 		}
 		// and then recurse to its children
@@ -511,7 +511,12 @@ func (p *PkgResolver) getPackageDependencies(pkg *repository.RepositoryPackage,
 // matching origin to a provided comparison package, whether or not one of the packages
 // already is installed, the versions, and whether an origin already exists.
 // The pin is for preference only; prefer a package that matches the pin over one that does not.
-func sortPackages(pkgs []*repositoryPackage, compare *repository.RepositoryPackage, existing map[string]*repository.RepositoryPackage, pin string) {
+// If a name is provided, then this is indicated as the name of the package we are looking for.
+// This may affect the sort order, as not all packages may have the same name.
+// For example, if the original search was for package "a", then pkgs may contain some that
+// are named "a", but others that provided "a". In that case, we should look not at the
+// version of the package, but the version of "a" that the package provides.
+func sortPackages(pkgs []*repositoryPackage, compare *repository.RepositoryPackage, name string, existing map[string]*repository.RepositoryPackage, pin string) {
 	// get existing origins
 	existingOrigins := map[string]bool{}
 	for _, pkg := range existing {
@@ -520,6 +525,9 @@ func sortPackages(pkgs []*repositoryPackage, compare *repository.RepositoryPacka
 		}
 	}
 	sort.Slice(pkgs, func(i, j int) bool {
+		// determine versions
+		iVersionStr := getDepVersionForName(pkgs[i], name)
+		jVersionStr := getDepVersionForName(pkgs[j], name)
 		if compare != nil {
 			// matching repository
 			pkgRepo := compare.Repository().Uri
@@ -572,11 +580,11 @@ func sortPackages(pkgs []*repositoryPackage, compare *repository.RepositoryPacka
 		}
 		// both matched or both did not, so just compare versions
 		// version priority
-		iVersion, err := parseVersion(pkgs[i].Version)
+		iVersion, err := parseVersion(iVersionStr)
 		if err != nil {
 			return false
 		}
-		jVersion, err := parseVersion(pkgs[j].Version)
+		jVersion, err := parseVersion(jVersionStr)
 		if err != nil {
 			return false
 		}
@@ -584,7 +592,47 @@ func sortPackages(pkgs []*repositoryPackage, compare *repository.RepositoryPacka
 		if versions != equal {
 			return versions == greater
 		}
+		// if versions are equal, they might not be the same as the package versions
+		if iVersionStr != pkgs[i].Version || jVersionStr != pkgs[j].Version {
+			iVersion, err := parseVersion(pkgs[i].Version)
+			if err != nil {
+				return false
+			}
+			jVersion, err := parseVersion(pkgs[j].Version)
+			if err != nil {
+				return false
+			}
+			versions := compareVersions(iVersion, jVersion)
+			if versions != equal {
+				return versions == greater
+			}
+		}
 		// if versions are equal, compare names
 		return pkgs[i].Name < pkgs[j].Name
 	})
 }
+
+// getDepVersionForName get the version of the package that provides the given name.
+// If the name matches the package name, then the version of the package is used;
+// if it does not, then the version of the provides is used.
+//
+// For example, if pkg foo v2.3 provides bar=1.2, and we look for name=bar then it returns
+// 1.2 (from the provides); else it return 2.3 (from the package itself).
+//
+// Note that the calling function might decide to ignore this and use the package
+// version anyways.
+func getDepVersionForName(pkg *repositoryPackage, name string) string {
+	if name == "" || name == pkg.Name {
+		return pkg.Version
+	}
+	for _, prov := range pkg.Provides {
+		pName, pVersion, _, _ := resolvePackageNameVersionPin(prov)
+		if pVersion == "" {
+			pVersion = pkg.Version
+		}
+		if pName == name {
+			return pVersion
+		}
+	}
+	return ""
+}


Test patch:
diff --git a/pkg/apk/impl/repo_test.go b/pkg/apk/impl/repo_test.go
index d1ebb1d..b784f27 100644
--- a/pkg/apk/impl/repo_test.go
+++ b/pkg/apk/impl/repo_test.go
@@ -141,6 +141,8 @@ func testGetPackagesAndIndex() ([]*repository.RepositoryPackage, []*repository.R
 			{Name: "package5", Version: "2.0.0"},
 			{Name: "package6", Version: "1.5.1"},
 			{Name: "package6", Version: "2.0.0", Dependencies: []string{"package6", "package5"}},
+			{Name: "package7", Version: "1"},
+			{Name: "package8", Version: "2", Provides: []string{"package7=0.9"}},
 		}
 		repoPackages = make([]*repository.RepositoryPackage, 0, len(packages))
 	)
@@ -279,6 +281,17 @@ func TestResolvePackage(t *testing.T) {
 		// first version should be highest match
 		require.Equal(t, "2.0.0", pkgs[0].Version)
 	})
+	t.Run("with provides", func(t *testing.T) {
+		// getPackageDependencies does not get the same dependencies twice.
+		_, index := testGetPackagesAndIndex()
+
+		resolver := NewPkgResolver(testNamedRepositoryFromIndexes(index))
+		pkgs, err := resolver.ResolvePackage("package7")
+		require.NoError(t, err)
+		require.Len(t, pkgs, 2)
+		// first version should be highest match
+		require.Equal(t, "1", pkgs[0].Version)
+	})
 }
 
 // Make sure that all versions exist
@@ -378,7 +391,7 @@ func TestSortPackages(t *testing.T) {
 				existing[pkg.pkg.Name] = repository.NewRepositoryPackage(pkg.pkg, &repository.RepositoryWithIndex{Repository: &repository.Repository{Uri: pkg.repo}})
 			}
 			namedPkgs := testNamedPackageFromPackages(pkgs)
-			sortPackages(namedPkgs, pkg, existing, "")
+			sortPackages(namedPkgs, pkg, "", existing, "")
 			for i, pkg := range namedPkgs {
 				require.Equal(t, int(pkg.InstalledSize), i, "position matches")
 			}
diff --git a/pkg/apk/impl/version_test.go b/pkg/apk/impl/version_test.go
index 2732f3f..91ec364 100644
--- a/pkg/apk/impl/version_test.go
+++ b/pkg/apk/impl/version_test.go
@@ -124,7 +124,7 @@ func TestResolveVersion(t *testing.T) {
 	for _, tt := range tests {
 		t.Run(tt.description, func(t *testing.T) {
 			found := filterPackages(pkgs, withVersion(tt.version, tt.compare), withPreferPin(tt.pin))
-			sortPackages(found, nil, nil, tt.pin)
+			sortPackages(found, nil, "", nil, tt.pin)
 			if tt.want == "" {
 				require.Nil(t, found, "version resolver should not find a package")
 			} else {