all: change from sort functions to slices functions

The sorting functions in the slices package are slightly faster as they
don't use reflection internally.

Change-Id: I3c0ab61336d44c1928ee2a9da12a00d914f5e637
Reviewed-on: https://go-review.googlesource.com/c/mod/+/625635
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>
Reviewed-by: Michael Matloob <matloob@golang.org>
Reviewed-by: Michael Matloob <matloob@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

modfile/rule.go

diff --git a/modfile/rule.go b/modfile/rule.go
index 3e4a1d0..1a6f3ef 100644
--- a/modfile/rule.go
+++ b/modfile/rule.go
@@ -20,10 +20,11 @@
 package modfile
 
 import (
+	"cmp"
 	"errors"
 	"fmt"
 	"path/filepath"
-	"sort"
+	"slices"
 	"strconv"
 	"strings"
 	"unicode"
@@ -1633,15 +1634,13 @@
 		if !ok {
 			continue
 		}
-		less := lineLess
+		less := compareLine
 		if block.Token[0] == "exclude" && useSemanticSortForExclude {
-			less = lineExcludeLess
+			less = compareLineExclude
 		} else if block.Token[0] == "retract" {
-			less = lineRetractLess
+			less = compareLineRetract
 		}
-		sort.SliceStable(block.Line, func(i, j int) bool {
-			return less(block.Line[i], block.Line[j])
-		})
+		slices.SortStableFunc(block.Line, less)
 	}
 }
 
@@ -1746,39 +1745,38 @@
 	syntax.Stmt = stmts
 }
 
-// lineLess returns whether li should be sorted before lj. It sorts
-// lexicographically without assigning any special meaning to tokens.
-func lineLess(li, lj *Line) bool {
+// compareLine compares li and lj. It sorts lexicographically without assigning
+// any special meaning to tokens.
+func compareLine(li, lj *Line) int {
 	for k := 0; k < len(li.Token) && k < len(lj.Token); k++ {
 		if li.Token[k] != lj.Token[k] {
-			return li.Token[k] < lj.Token[k]
+			return cmp.Compare(li.Token[k], lj.Token[k])
 		}
 	}
-	return len(li.Token) < len(lj.Token)
+	return cmp.Compare(len(li.Token), len(lj.Token))
 }
 
-// lineExcludeLess reports whether li should be sorted before lj for lines in
-// an "exclude" block.
-func lineExcludeLess(li, lj *Line) bool {
+// compareLineExclude compares li and lj for lines in an "exclude" block.
+func compareLineExclude(li, lj *Line) int {
 	if len(li.Token) != 2 || len(lj.Token) != 2 {
 		// Not a known exclude specification.
 		// Fall back to sorting lexicographically.
-		return lineLess(li, lj)
+		return compareLine(li, lj)
 	}
 	// An exclude specification has two tokens: ModulePath and Version.
 	// Compare module path by string order and version by semver rules.
 	if pi, pj := li.Token[0], lj.Token[0]; pi != pj {
-		return pi < pj
+		return cmp.Compare(pi, pj)
 	}
-	return semver.Compare(li.Token[1], lj.Token[1]) < 0
+	return semver.Compare(li.Token[1], lj.Token[1])
 }
 
-// lineRetractLess returns whether li should be sorted before lj for lines in
-// a "retract" block. It treats each line as a version interval. Single versions
-// are compared as if they were intervals with the same low and high version.
+// compareLineRetract compares li and lj for lines in a "retract" block.
+// It treats each line as a version interval. Single versions are compared as
+// if they were intervals with the same low and high version.
 // Intervals are sorted in descending order, first by low version, then by
-// high version, using semver.Compare.
-func lineRetractLess(li, lj *Line) bool {
+// high version, using [semver.Compare].
+func compareLineRetract(li, lj *Line) int {
 	interval := func(l *Line) VersionInterval {
 		if len(l.Token) == 1 {
 			return VersionInterval{Low: l.Token[0], High: l.Token[0]}
@@ -1792,9 +1790,9 @@
 	vii := interval(li)
 	vij := interval(lj)
 	if cmp := semver.Compare(vii.Low, vij.Low); cmp != 0 {
-		return cmp > 0
+		return -cmp
 	}
-	return semver.Compare(vii.High, vij.High) > 0
+	return -semver.Compare(vii.High, vij.High)
 }
 
 // checkCanonicalVersion returns a non-nil error if vers is not a canonical

modfile/work.go

diff --git a/modfile/work.go b/modfile/work.go
index 5387d0c..6f92644 100644
--- a/modfile/work.go
+++ b/modfile/work.go
@@ -6,7 +6,7 @@
 
 import (
 	"fmt"
-	"sort"
+	"slices"
 	"strings"
 )
 
@@ -315,9 +315,7 @@
 		if !ok {
 			continue
 		}
-		sort.SliceStable(block.Line, func(i, j int) bool {
-			return lineLess(block.Line[i], block.Line[j])
-		})
+		slices.SortStableFunc(block.Line, compareLine)
 	}
 }
 

module/module.go

diff --git a/module/module.go b/module/module.go
index 2a364b2..16e1aa7 100644
--- a/module/module.go
+++ b/module/module.go
@@ -96,10 +96,11 @@
 // Changes to the semantics in this file require approval from rsc.
 
 import (
+	"cmp"
 	"errors"
 	"fmt"
 	"path"
-	"sort"
+	"slices"
 	"strings"
 	"unicode"
 	"unicode/utf8"
@@ -657,17 +658,15 @@
 // optionally followed by a tie-breaking suffix introduced by a slash character,
 // like in "v0.0.1/go.mod".
 func Sort(list []Version) {
-	sort.Slice(list, func(i, j int) bool {
-		mi := list[i]
-		mj := list[j]
-		if mi.Path != mj.Path {
-			return mi.Path < mj.Path
+	slices.SortFunc(list, func(i, j Version) int {
+		if i.Path != j.Path {
+			return strings.Compare(i.Path, j.Path)
 		}
 		// To help go.sum formatting, allow version/file.
 		// Compare semver prefix by semver rules,
 		// file by string order.
-		vi := mi.Version
-		vj := mj.Version
+		vi := i.Version
+		vj := j.Version
 		var fi, fj string
 		if k := strings.Index(vi, "/"); k >= 0 {
 			vi, fi = vi[:k], vi[k:]
@@ -676,9 +675,9 @@
 			vj, fj = vj[:k], vj[k:]
 		}
 		if vi != vj {
-			return semver.Compare(vi, vj) < 0
+			return semver.Compare(vi, vj)
 		}
-		return fi < fj
+		return cmp.Compare(fi, fj)
 	})
 }
 

semver/semver.go

diff --git a/semver/semver.go b/semver/semver.go
index 9a2dfd3..628f8fd 100644
--- a/semver/semver.go
+++ b/semver/semver.go
@@ -22,7 +22,10 @@
 // as shorthands for vMAJOR.0.0 and vMAJOR.MINOR.0.
 package semver
 
-import "sort"
+import (
+	"slices"
+	"strings"
+)
 
 // parsed returns the parsed form of a semantic version string.
 type parsed struct {
@@ -154,19 +157,22 @@
 // ByVersion implements [sort.Interface] for sorting semantic version strings.
 type ByVersion []string
 
-func (vs ByVersion) Len() int      { return len(vs) }
-func (vs ByVersion) Swap(i, j int) { vs[i], vs[j] = vs[j], vs[i] }
-func (vs ByVersion) Less(i, j int) bool {
-	cmp := Compare(vs[i], vs[j])
-	if cmp != 0 {
-		return cmp < 0
-	}
-	return vs[i] < vs[j]
+func (vs ByVersion) Len() int           { return len(vs) }
+func (vs ByVersion) Swap(i, j int)      { vs[i], vs[j] = vs[j], vs[i] }
+func (vs ByVersion) Less(i, j int) bool { return compareVersion(vs[i], vs[j]) < 0 }
+
+// Sort sorts a list of semantic version strings using [Compare] and falls back
+// to use [strings.Compare] if both versions are considered equal.
+func Sort(list []string) {
+	slices.SortFunc(list, compareVersion)
 }
 
-// Sort sorts a list of semantic version strings using [ByVersion].
-func Sort(list []string) {
-	sort.Sort(ByVersion(list))
+func compareVersion(a, b string) int {
+	cmp := Compare(a, b)
+	if cmp != 0 {
+		return cmp
+	}
+	return strings.Compare(a, b)
 }
 
 func parse(v string) (p parsed, ok bool) {

semver/semver_test.go

diff --git a/semver/semver_test.go b/semver/semver_test.go
index 937e18e..56739ad 100644
--- a/semver/semver_test.go
+++ b/semver/semver_test.go
@@ -6,6 +6,7 @@
 
 import (
 	"math/rand"
+	"slices"
 	"sort"
 	"strings"
 	"testing"
@@ -166,6 +167,44 @@
 	if !sort.IsSorted(ByVersion(versions)) {
 		t.Errorf("list is not sorted:\n%s", strings.Join(versions, "\n"))
 	}
+
+	golden := []string{
+		"bad",
+		"v1+meta",
+		"v1-alpha.beta.gamma",
+		"v1-pre",
+		"v1-pre+meta",
+		"v1.2+meta",
+		"v1.2-pre",
+		"v1.2-pre+meta",
+		"v1.0.0-alpha",
+		"v1.0.0-alpha.1",
+		"v1.0.0-alpha.beta",
+		"v1.0.0-beta",
+		"v1.0.0-beta.2",
+		"v1.0.0-beta.11",
+		"v1.0.0-rc.1",
+		"v1",
+		"v1.0",
+		"v1.0.0",
+		"v1.2",
+		"v1.2.0",
+		"v1.2.3-456",
+		"v1.2.3-456.789",
+		"v1.2.3-456-789",
+		"v1.2.3-456a",
+		"v1.2.3-pre",
+		"v1.2.3-pre+meta",
+		"v1.2.3-pre.1",
+		"v1.2.3-zzz",
+		"v1.2.3",
+		"v1.2.3+meta",
+		"v1.2.3+meta-pre",
+		"v1.2.3+meta-pre.sha.256a",
+	}
+	if !slices.Equal(versions, golden) {
+		t.Errorf("list is not sorted correctly\ngot:\n%v\nwant:\n%v", versions, golden)
+	}
 }
 
 func TestMax(t *testing.T) {

sumdb/dirhash/hash.go

diff --git a/sumdb/dirhash/hash.go b/sumdb/dirhash/hash.go
index 51ec4db..117985a 100644
--- a/sumdb/dirhash/hash.go
+++ b/sumdb/dirhash/hash.go
@@ -16,7 +16,7 @@
 	"io"
 	"os"
 	"path/filepath"
-	"sort"
+	"slices"
 	"strings"
 )
 
@@ -36,7 +36,7 @@
 //	sha256sum $(find . -type f | sort) | sha256sum
 //
 // More precisely, the hashed summary contains a single line for each file in the list,
-// ordered by sort.Strings applied to the file names, where each line consists of
+// ordered by [slices.Sort] applied to the file names, where each line consists of
 // the hexadecimal SHA-256 hash of the file content,
 // two spaces (U+0020), the file name, and a newline (U+000A).
 //
@@ -44,7 +44,7 @@
 func Hash1(files []string, open func(string) (io.ReadCloser, error)) (string, error) {
 	h := sha256.New()
 	files = append([]string(nil), files...)
-	sort.Strings(files)
+	slices.Sort(files)
 	for _, file := range files {
 		if strings.Contains(file, "\n") {
 			return "", errors.New("dirhash: filenames with newlines are not supported")