Sort repository tree entries in natural way (#2506)

* Sort repository tree entries in natural way

* Fix sort for different length strings with first parts equal

* Improve test case

* Refactor return statements

* Update gitea/git dependency

2 files changed, 113 insertions, 0 deletions

diff --git a/modules/base/natural_sort.go b/modules/base/natural_sort.go
new file mode 100644
index 0000000000..60db363df0
--- /dev/null
+++ b/modules/base/natural_sort.go
@@ -0,0 +1,89 @@
+// Copyright 2017 The Gitea Authors. All rights reserved.
+// Use of this source code is governed by a MIT-style
+// license that can be found in the LICENSE file.
+
+package base
+
+import (
+	"math/big"
+	"unicode/utf8"
+)
+
+// NaturalSortLess compares two strings so that they could be sorted in natural order
+func NaturalSortLess(s1, s2 string) bool {
+	var i1, i2 int
+	for {
+		rune1, j1, end1 := getNextRune(s1, i1)
+		rune2, j2, end2 := getNextRune(s2, i2)
+		if end1 || end2 {
+			return end1 != end2 && end1
+		}
+		dec1 := isDecimal(rune1)
+		dec2 := isDecimal(rune2)
+		var less, equal bool
+		if dec1 && dec2 {
+			i1, i2, less, equal = compareByNumbers(s1, i1, s2, i2)
+		} else if !dec1 && !dec2 {
+			equal = rune1 == rune2
+			less = rune1 < rune2
+			i1 = j1
+			i2 = j2
+		} else {
+			return rune1 < rune2
+		}
+		if !equal {
+			return less
+		}
+	}
+}
+
+func getNextRune(str string, pos int) (rune, int, bool) {
+	if pos < len(str) {
+		r, w := utf8.DecodeRuneInString(str[pos:])
+		// Fallback to ascii
+		if r == utf8.RuneError {
+			r = rune(str[pos])
+			w = 1
+		}
+		return r, pos + w, false
+	}
+	return 0, pos, true
+}
+
+func isDecimal(r rune) bool {
+	return '0' <= r && r <= '9'
+}
+
+func compareByNumbers(str1 string, pos1 int, str2 string, pos2 int) (i1, i2 int, less, equal bool) {
+	var d1, d2 bool = true, true
+	var dec1, dec2 string
+	for d1 || d2 {
+		if d1 {
+			r, j, end := getNextRune(str1, pos1)
+			if !end && isDecimal(r) {
+				dec1 += string(r)
+				pos1 = j
+			} else {
+				d1 = false
+			}
+		}
+		if d2 {
+			r, j, end := getNextRune(str2, pos2)
+			if !end && isDecimal(r) {
+				dec2 += string(r)
+				pos2 = j
+			} else {
+				d2 = false
+			}
+		}
+	}
+	less, equal = compareBigNumbers(dec1, dec2)
+	return pos1, pos2, less, equal
+}
+
+func compareBigNumbers(dec1, dec2 string) (less, equal bool) {
+	d1, _ := big.NewInt(0).SetString(dec1, 10)
+	d2, _ := big.NewInt(0).SetString(dec2, 10)
+	cmp := d1.Cmp(d2)
+	return cmp < 0, cmp == 0
+}
diff --git a/modules/base/natural_sort_test.go b/modules/base/natural_sort_test.go
new file mode 100644
index 0000000000..b8d45e4ec0
--- /dev/null
+++ b/modules/base/natural_sort_test.go
@@ -0,0 +1,24 @@
+// Copyright 2017 The Gitea Authors. All rights reserved.
+// Use of this source code is governed by a MIT-style
+// license that can be found in the LICENSE file.
+
+package base
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func TestNaturalSortLess(t *testing.T) {
+	test := func(s1, s2 string, less bool) {
+		assert.Equal(t, less, NaturalSortLess(s1, s2))
+	}
+	test("v1.20.0", "v1.2.0", false)
+	test("v1.20.0", "v1.29.0", true)
+	test("v1.20.0", "v1.20.0", false)
+	test("abc", "bcd", "abc" < "bcd")
+	test("a-1-a", "a-1-b", true)
+	test("2", "12", true)
+	test("a", "ab", "a" < "ab")
+}