Repository: chainguard-dev/apko (go)

Issue:
native apk implementation: does not solve for highest constrained version
Previously, the apk solver would choose the first package it encountered which met the constraints.  @jdolitsky changed this in #468 to use the highest version encountered as an interim improvement, but ultimately the solver should pick the highest version which meets the constraint.

Consider the following repository:

- `Package{Name: 'foo', Version: '1.2.3-r0'}`
- `Package{Name: 'foo', Version: '1.3.6-r0'}`
- `Package{Name: 'foo', Version: '1.2.8-r0'}`
- `Package{Name: 'foo', Version: '1.7.1-r0'}`
- `Package{Name: 'foo', Version: '1.7.1-r1'}`
- `Package{Name: 'foo', Version: '2.0.6-r0'}`

If we specify in our config `foo>2.0`, then `foo-2.0.6-r0` should be selected.
If we specify in our config `foo~1.7`, then `foo-1.7.1-r1` should be selected.
If we specify in our config `foo<1.7`, then `foo-1.3.6-r0` should be selected.
If we specify in our config `foo<1.3`, then `foo-1.2.8-r0` should be selected.
If we specify in our config `foo<1.2.8`, then `foo-1.2.3-r0` should be selected.

Pull request description:
add versions with constraints
Fixes #470 

@kaniini can you validate that this actually resolves what you were looking for? Specifically, look at the test case for version resolution [here](https://github.com/chainguard-dev/apko/pull/473/files#diff-0fe948ffc19f6666deee62dfea127804fc3033d1c7ad2971b1178715a50735bdR94).

Patch:
diff --git a/pkg/apk/impl/repo.go b/pkg/apk/impl/repo.go
index ecdf61f..1cc3b2d 100644
--- a/pkg/apk/impl/repo.go
+++ b/pkg/apk/impl/repo.go
@@ -204,46 +204,42 @@ func (a *APKImplementation) getRepositoryIndexes(ignoreSignatures bool) ([]*repo
 // If the indexes change, you should generate a new pkgResolver.
 type PkgResolver struct {
 	indexes     []*repository.RepositoryWithIndex
-	nameMap     map[string]*repository.RepositoryPackage
+	nameMap     map[string]map[string]*repository.RepositoryPackage
 	providesMap map[string]string
 }
 
 // NewPkgResolver creates a new pkgResolver from a list of indexes.
 func NewPkgResolver(indexes []*repository.RepositoryWithIndex) *PkgResolver {
 	var (
-		pkgNameMap     = map[string]*repository.RepositoryPackage{}
+		pkgNameMap     = map[string]map[string]*repository.RepositoryPackage{}
 		pkgProvidesMap = map[string]string{}
 	)
 	p := &PkgResolver{
 		indexes: indexes,
 	}
-	// create a map of every package to its RepositoryPackage
+	// create a map of every package by name and version to its RepositoryPackage
 	for _, index := range indexes {
 		for _, pkg := range index.Packages() {
 			existingPkg, ok := pkgNameMap[pkg.Name]
 			if !ok {
-				pkgNameMap[pkg.Name] = pkg
-				continue
-			}
-			// If the map already has an existing package by this name,
-			// keep checking in case there is a newer version
-			oldVersion, _ := parseVersion(existingPkg.Version)
-			newVersion, _ := parseVersion(pkg.Version)
-			if compareVersions(newVersion, oldVersion) == greater {
-				pkgNameMap[pkg.Name] = pkg
+				existingPkg = map[string]*repository.RepositoryPackage{}
+				pkgNameMap[pkg.Name] = existingPkg
 			}
+			existingPkg[pkg.Version] = pkg
 		}
 	}
 	// create a map of every provided file to its package
-	for _, pkg := range pkgNameMap {
-		for _, provide := range pkg.Provides {
-			name, _, compare := resolvePackageNameVersion(provide)
-			if _, ok := pkgProvidesMap[name]; !ok {
-				pkgProvidesMap[name] = pkg.Name
-			}
-			if compare != versionNone {
-				if _, ok := pkgProvidesMap[provide]; !ok {
-					pkgProvidesMap[provide] = pkg.Name
+	for pkgName, pkgVersions := range pkgNameMap {
+		for _, pkg := range pkgVersions {
+			for _, provide := range pkg.Provides {
+				name, _, compare := resolvePackageNameVersion(provide)
+				if _, ok := pkgProvidesMap[name]; !ok {
+					pkgProvidesMap[name] = pkgName
+				}
+				if compare != versionNone {
+					if _, ok := pkgProvidesMap[provide]; !ok {
+						pkgProvidesMap[provide] = pkg.Name
+					}
 				}
 			}
 		}
@@ -260,35 +256,7 @@ func (p *PkgResolver) GetPackagesWithDependencies(packages []string) (toInstall
 		dependenciesMap = map[string]bool{}
 	)
 	for _, pkgName := range packages {
-		// this package might be pinned to a version
-		name, version, compare := resolvePackageNameVersion(pkgName)
-		pkg, ok := p.nameMap[name]
-		if !ok {
-			trueName, ok := p.providesMap[name]
-			if !ok {
-				return nil, nil, fmt.Errorf("could not find package %s in indexes", pkgName)
-			}
-			pkg, ok = p.nameMap[trueName]
-			if !ok {
-				return nil, nil, fmt.Errorf("could not find package %s in indexes", pkgName)
-			}
-		}
-
-		if compare != versionNone {
-			actualVersion, err := parseVersion(pkg.Version)
-			if err != nil {
-				return nil, nil, fmt.Errorf("could not parse version %s for actual package %s: %w", pkg.Version, pkgName, err)
-			}
-			requiredVersion, err := parseVersion(version)
-			if err != nil {
-				return nil, nil, fmt.Errorf("could not parse version %s for required package %s: %w", version, pkgName, err)
-			}
-			versionRelationship := compareVersions(actualVersion, requiredVersion)
-			if !compare.satisfies(versionRelationship) {
-				return nil, nil, fmt.Errorf("mismatched version for package %s in indexes: %w", pkgName, err)
-			}
-		}
-		deps, confs, err := p.GetPackageDependencies(name)
+		pkg, deps, confs, err := p.GetPackageWithDependencies(pkgName)
 		if err != nil {
 			return nil, nil, err
 		}
@@ -298,9 +266,9 @@ func (p *PkgResolver) GetPackagesWithDependencies(packages []string) (toInstall
 				dependenciesMap[dep.Name] = true
 			}
 		}
-		if _, ok := dependenciesMap[pkg.Name]; !ok {
+		if _, ok := dependenciesMap[pkgName]; !ok {
 			toInstall = append(toInstall, pkg)
-			dependenciesMap[pkg.Name] = true
+			dependenciesMap[pkgName] = true
 		}
 		conflicts = append(conflicts, confs...)
 	}
@@ -310,10 +278,37 @@ func (p *PkgResolver) GetPackagesWithDependencies(packages []string) (toInstall
 	return toInstall, conflicts, nil
 }
 
-// GetPackageDependencies get all of the dependencies for a single package based on the
-// indexes.
-func (p *PkgResolver) GetPackageDependencies(pkg string) (dependencies []*repository.RepositoryPackage, conflicts []string, err error) {
+// GetPackageDependencies get all of the dependencies for a single package as well as looking
+// up the package itself and resolving its version, based on the indexes.
+func (p *PkgResolver) GetPackageWithDependencies(pkgName string) (pkg *repository.RepositoryPackage, dependencies []*repository.RepositoryPackage, conflicts []string, err error) {
 	parents := make(map[string]bool)
+
+	name, version, compare := resolvePackageNameVersion(pkgName)
+	pkgsWithVersions, ok := p.nameMap[name]
+
+	if !ok {
+		trueName, ok := p.providesMap[name]
+		if !ok {
+			return nil, nil, nil, fmt.Errorf("could not find package, alias or a package that provides %s in indexes", pkgName)
+		}
+		pkgsWithVersions, ok = p.nameMap[trueName]
+		if !ok {
+			return nil, nil, nil, fmt.Errorf("looking for %s, found provided by %s, but could not find %s in indexes", pkgName, trueName, trueName)
+		}
+	}
+
+	// pkgsWithVersions contains a map of all versions of the package
+	// get the one that most matches what was requested
+	versions := make([]string, 0, 10)
+	for version := range pkgsWithVersions {
+		versions = append(versions, version)
+	}
+	targetVersion := getBestVersion(versions, version, compare)
+	if targetVersion == "" {
+		return nil, nil, nil, fmt.Errorf("could not find package %s in indexes: %w", pkgName, err)
+	}
+	pkg = pkgsWithVersions[targetVersion]
+
 	deps, conflicts, err := p.getPackageDependencies(pkg, parents)
 	if err != nil {
 		return
@@ -357,27 +352,16 @@ func (p *PkgResolver) GetPackageDependencies(pkg string) (dependencies []*reposi
 // It might change the order of install.
 // In other words, this _should_ be a DAG (acyclical), but because the packages
 // are just listing dependencies in text, it might be cyclical. We need to be careful of that.
-func (p *PkgResolver) getPackageDependencies(pkg string, parents map[string]bool) (dependencies []*repository.RepositoryPackage, conflicts []string, err error) {
+func (p *PkgResolver) getPackageDependencies(pkg *repository.RepositoryPackage, parents map[string]bool) (dependencies []*repository.RepositoryPackage, conflicts []string, err error) {
 	// check if the package we are checking is one of our parents, avoid cyclical graphs
-	if _, ok := parents[pkg]; ok {
+	if _, ok := parents[pkg.Name]; ok {
 		return nil, nil, nil
 	}
-	ref, ok := p.nameMap[pkg]
-	if !ok {
-		trueName, ok := p.providesMap[pkg]
-		if !ok {
-			return nil, nil, fmt.Errorf("package %s not found in indexes", pkg)
-		}
-		ref, ok = p.nameMap[trueName]
-		if !ok {
-			return nil, nil, fmt.Errorf("package %s not found in indexes", pkg)
-		}
-	}
 
 	// each dependency has only one of two possibilities:
 	// - !name     - "I cannot be installed along with the package <name>"
 	// - name      - "I need package 'name'" -OR- "I need the package that provides <name>"
-	for _, dep := range ref.Dependencies {
+	for _, dep := range pkg.Dependencies {
 		var (
 			depPkg *repository.RepositoryPackage
 			ok     bool
@@ -393,37 +377,34 @@ func (p *PkgResolver) getPackageDependencies(pkg string, parents map[string]bool
 		// this package might be pinned to a version
 		name, version, compare := resolvePackageNameVersion(dep)
 		// first see if it is a name of a package
-		depPkg, ok = p.nameMap[name]
+		depPkgWithVersions, ok := p.nameMap[name]
 		if !ok {
 			// it was not the name of a package, see if some package provides this
 			provider, ok := p.providesMap[name]
 			if !ok {
 				// no one provides it, return an error
-				return nil, nil, fmt.Errorf("could not find package either named %s or that provides %s for %s", dep, dep, pkg)
+				return nil, nil, fmt.Errorf("could not find package either named %s or that provides %s for %s", dep, dep, pkg.Name)
 			}
-			depPkg, ok = p.nameMap[provider]
+			depPkgWithVersions, ok = p.nameMap[provider]
 			if !ok {
 				return nil, nil, fmt.Errorf("required dependency %s is provided by package %s, which could not be found", name, provider)
 			}
+			name = provider
 		}
-		if depPkg.Name == pkg {
+		if name == pkg.Name {
 			continue
 		}
-		// we found the targeted package; validate version requirements, if any
-		if compare != versionNone {
-			actualVersion, err := parseVersion(depPkg.Version)
-			if err != nil {
-				return nil, nil, fmt.Errorf("could not parse version %s for actual package %s: %w", depPkg.Version, depPkg.Name, err)
-			}
-			requiredVersion, err := parseVersion(version)
-			if err != nil {
-				return nil, nil, fmt.Errorf("could not parse version %s for required package %s: %w", version, depPkg.Name, err)
-			}
-			versionRelationship := compareVersions(actualVersion, requiredVersion)
-			if !compare.satisfies(versionRelationship) {
-				return nil, nil, fmt.Errorf("mismatched version for package %s in indexes: %w", depPkg.Name, err)
-			}
+		// pkgsWithVersions contains a map of all versions of the package
+		// get the one that most matches what was requested
+		var versions []string
+		for version := range depPkgWithVersions {
+			versions = append(versions, version)
+		}
+		targetVersion := getBestVersion(versions, version, compare)
+		if targetVersion == "" {
+			return nil, nil, fmt.Errorf("could not find package %s in indexes: %w", dep, err)
 		}
+		depPkg = depPkgWithVersions[targetVersion]
 		// and then recurse to its children
 		// each child gets the parental chain, but should not affect any others,
 		// so we duplicate the map for the child
@@ -431,8 +412,8 @@ func (p *PkgResolver) getPackageDependencies(pkg string, parents map[string]bool
 		for k := range parents {
 			childParents[k] = true
 		}
-		childParents[pkg] = true
-		subDeps, confs, err := p.getPackageDependencies(depPkg.Name, childParents)
+		childParents[pkg.Name] = true
+		subDeps, confs, err := p.getPackageDependencies(depPkg, childParents)
 		if err != nil {
 			return nil, nil, err
 		}
diff --git a/pkg/apk/impl/version.go b/pkg/apk/impl/version.go
index f4caebe..2f8e2a7 100644
--- a/pkg/apk/impl/version.go
+++ b/pkg/apk/impl/version.go
@@ -17,6 +17,7 @@ package impl
 import (
 	"fmt"
 	"regexp"
+	"sort"
 	"strconv"
 	"strings"
 )
@@ -313,3 +314,48 @@ func resolvePackageNameVersion(name string) (string, string, versionDependency)
 	// we have no =, < or >, so we just return the name
 	return name, "", versionNone
 }
+
+func getBestVersion(versions []string, version string, compare versionDependency) string {
+	// go through all potential versions, save the ones that meet the constraints,
+	// then take the highest
+	var passed []string
+	for _, v := range versions {
+		if compare == versionNone {
+			passed = append(passed, v)
+			continue
+		}
+		actualVersion, err := parseVersion(v)
+		// skip invalid ones
+		if err != nil {
+			continue
+		}
+		requiredVersion, err := parseVersion(version)
+		// if the required version is invalid, we can't compare, so we return no matches
+		if err != nil {
+			return ""
+		}
+		versionRelationship := compareVersions(actualVersion, requiredVersion)
+		if compare.satisfies(versionRelationship) {
+			passed = append(passed, v)
+		}
+	}
+	if len(passed) == 0 {
+		return ""
+	}
+	if len(passed) == 1 {
+		return passed[0]
+	}
+
+	sort.Slice(passed, func(i, j int) bool {
+		actualVersion, err := parseVersion(passed[i])
+		if err != nil {
+			return false
+		}
+		requiredVersion, err := parseVersion(passed[j])
+		if err != nil {
+			return false
+		}
+		return compareVersions(actualVersion, requiredVersion) == greater
+	})
+	return passed[0]
+}


Test patch:
diff --git a/pkg/apk/impl/repo_test.go b/pkg/apk/impl/repo_test.go
index eae8c9b..5c95412 100644
--- a/pkg/apk/impl/repo_test.go
+++ b/pkg/apk/impl/repo_test.go
@@ -116,21 +116,21 @@ func testGetPackagesAndIndex() ([]*repository.RepositoryPackage, []*repository.R
 	// dep4, dep5, dep1, dep6, foo, libq, dep3, busybox, dep2
 	var (
 		packages = []*repository.Package{
-			{Name: "package1", Dependencies: []string{"dep1", "dep2", "dep3"}},
-			{Name: "dep1", Dependencies: []string{"dep4", "dep5"}},
-			{Name: "dep2", Dependencies: []string{"dep3", "/bin/sh"}},
-			{Name: "dep3", Dependencies: []string{"dep6", "cmd:/bin/foo", "so:libq.so.1"}},
-			{Name: "dep4", Dependencies: []string{}},
-			{Name: "dep5", Dependencies: []string{}},
-			{Name: "dep6", Dependencies: []string{}},
-			{Name: "dep7", Dependencies: []string{}},
-			{Name: "dep8", Dependencies: []string{"dep8"}},
-			{Name: "libq", Dependencies: []string{}, Provides: []string{"so:libq.so.1"}},
-			{Name: "foo", Dependencies: []string{}, Provides: []string{"cmd:/bin/foo"}},
-			{Name: "busybox", Dependencies: []string{}},
-			{Name: "unused", Dependencies: []string{}},
-			{Name: "package2", Dependencies: []string{"dep2", "dep7"}},
-			{Name: "package3", Dependencies: []string{"dep8"}},
+			{Name: "package1", Version: "1.0.0", Dependencies: []string{"dep1", "dep2", "dep3"}},
+			{Name: "dep1", Version: "1.0.0", Dependencies: []string{"dep4", "dep5"}},
+			{Name: "dep2", Version: "1.0.0", Dependencies: []string{"dep3", "/bin/sh"}},
+			{Name: "dep3", Version: "1.0.0", Dependencies: []string{"dep6", "cmd:/bin/foo", "so:libq.so.1"}},
+			{Name: "dep4", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "dep5", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "dep6", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "dep7", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "dep8", Version: "1.0.0", Dependencies: []string{"dep8"}},
+			{Name: "libq", Version: "1.0.0", Dependencies: []string{}, Provides: []string{"so:libq.so.1"}},
+			{Name: "foo", Version: "1.0.0", Dependencies: []string{}, Provides: []string{"cmd:/bin/foo"}},
+			{Name: "busybox", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "unused", Version: "1.0.0", Dependencies: []string{}},
+			{Name: "package2", Version: "1.0.0", Dependencies: []string{"dep2", "dep7"}},
+			{Name: "package3", Version: "1.0.0", Dependencies: []string{"dep8"}},
 		}
 		repoPackages = make([]*repository.RepositoryPackage, 0, len(packages))
 	)
@@ -174,7 +174,7 @@ func TestGetPackageDependencies(t *testing.T) {
 		_, index := testGetPackagesAndIndex()
 
 		resolver := NewPkgResolver(index)
-		pkgs, _, err := resolver.GetPackageDependencies("package1")
+		_, pkgs, _, err := resolver.GetPackageWithDependencies("package1")
 		require.NoErrorf(t, err, "unable to get dependencies")
 
 		var actual = make([]string, 0, len(pkgs))
@@ -189,7 +189,7 @@ func TestGetPackageDependencies(t *testing.T) {
 		_, index := testGetPackagesAndIndex()
 
 		resolver := NewPkgResolver(index)
-		pkgs, _, err := resolver.GetPackageDependencies("package3")
+		_, pkgs, _, err := resolver.GetPackageWithDependencies("package3")
 		require.NoErrorf(t, err, "unable to get dependencies")
 
 		var actual = make([]string, 0, len(pkgs))
@@ -200,20 +200,24 @@ func TestGetPackageDependencies(t *testing.T) {
 	})
 }
 
-// Make sure that higher semver versions rise to the top
-func TestVersionHieracrchy(t *testing.T) {
+// Make sure that all versions exist
+func TestVersionHierarchy(t *testing.T) {
 	repo := repository.Repository{}
 	index := repo.WithIndex(&repository.ApkIndex{
 		Packages: []*repository.Package{
-			{Name: "multi-versioner", Version: "1.2.9"},
-			{Name: "multi-versioner", Version: "1.1.4"},
-			{Name: "multi-versioner", Version: "1.2.5"},
-			{Name: "multi-versioner", Version: "1.3.0"},
-			{Name: "multi-versioner", Version: "1.2.4"},
+			{Name: "multi-versioner", Version: "1.2.3-r0"},
+			{Name: "multi-versioner", Version: "1.3.6-r0"},
+			{Name: "multi-versioner", Version: "1.2.8-r0"},
+			{Name: "multi-versioner", Version: "1.7.1-r0"},
+			{Name: "multi-versioner", Version: "1.7.1-r1"},
+			{Name: "multi-versioner", Version: "2.0.6-r0"},
 		},
 	})
 	resolver := NewPkgResolver([]*repository.RepositoryWithIndex{index})
-	pkg, ok := resolver.nameMap["multi-versioner"]
+	pkgWithVersions, ok := resolver.nameMap["multi-versioner"]
 	require.True(t, ok, "found multi-versioner in nameMap")
-	require.Equal(t, "1.3.0", pkg.Version, "multi-versioner has correct version")
+	for version, pkg := range pkgWithVersions {
+		require.True(t, pkg.Version != "", "multi-versioner has version")
+		require.Equal(t, version, pkg.Version, "multi-versioner has correct version")
+	}
 }
diff --git a/pkg/apk/impl/version_test.go b/pkg/apk/impl/version_test.go
index 25e661b..6b0dd74 100644
--- a/pkg/apk/impl/version_test.go
+++ b/pkg/apk/impl/version_test.go
@@ -90,3 +90,24 @@ func TestParseVersion(t *testing.T) {
 		}
 	})
 }
+
+func TestResolveVersion(t *testing.T) {
+	versions := []string{"1.2.3-r0", "1.3.6-r0", "1.2.8-r0", "1.7.1-r0", "1.7.1-r1", "2.0.6-r0"}
+	tests := []struct {
+		version     string
+		compare     versionDependency
+		want        string
+		description string
+	}{
+		{"1.2.3-r0", versionEqual, "1.2.3-r0", "exact version match"},
+		{"1.2.3-r10000", versionEqual, "", "exact version no match"},
+		{"2.0.0", versionGreater, "2.0.6-r0", "greater than version match"},
+		{"2.0.0", versionGreaterEqual, "2.0.6-r0", "greater than or equal to version match"},
+		{"3.0.0", versionGreaterEqual, "", "greater than or equal to version no match"},
+		{"", versionNone, "2.0.6-r0", "no requirement should get highest version"},
+	}
+	for _, tt := range tests {
+		found := getBestVersion(versions, tt.version, tt.compare)
+		require.Equal(t, found, tt.want, "version resolver gets correct version")
+	}
+}