Merge pull request #6149 from bep/sort-caseinsensitive

Implement lexicographically string sorting

14 files changed, 246 insertions, 34 deletions

diff --git a/compare/compare.go b/compare/compare.go
index 18c0de777..537a66676 100644
--- a/compare/compare.go
+++ b/compare/compare.go
@@ -1,4 +1,4 @@
-// Copyright 2017-present The Hugo Authors. All rights reserved.
+// Copyright 2019 The Hugo Authors. All rights reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
@@ -20,7 +20,7 @@ type Eqer interface {
 	Eq(other interface{}) bool
 }
 
-// ProbablyEq is an equal check that may return false positives, but never
+// ProbablyEqer is an equal check that may return false positives, but never
 // a false negative.
 type ProbablyEqer interface {
 	ProbablyEq(other interface{}) bool
diff --git a/compare/compare_strings.go b/compare/compare_strings.go
new file mode 100644
index 000000000..1fd954081
--- /dev/null
+++ b/compare/compare_strings.go
@@ -0,0 +1,113 @@
+// Copyright 2019 The Hugo Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package compare
+
+import (
+	"strings"
+	"unicode"
+	"unicode/utf8"
+)
+
+// Strings returns an integer comparing two strings lexicographically.
+func Strings(s, t string) int {
+	c := compareFold(s, t)
+
+	if c == 0 {
+		// "B" and "b" would be the same so we need a tiebreaker.
+		return strings.Compare(s, t)
+	}
+
+	return c
+}
+
+// This function is derived from strings.EqualFold in Go's stdlib.
+// https://github.com/golang/go/blob/ad4a58e31501bce5de2aad90a620eaecdc1eecb8/src/strings/strings.go#L893
+func compareFold(s, t string) int {
+	for s != "" && t != "" {
+		var sr, tr rune
+		if s[0] < utf8.RuneSelf {
+			sr, s = rune(s[0]), s[1:]
+		} else {
+			r, size := utf8.DecodeRuneInString(s)
+			sr, s = r, s[size:]
+		}
+		if t[0] < utf8.RuneSelf {
+			tr, t = rune(t[0]), t[1:]
+		} else {
+			r, size := utf8.DecodeRuneInString(t)
+			tr, t = r, t[size:]
+		}
+
+		if tr == sr {
+			continue
+		}
+
+		c := 1
+		if tr < sr {
+			tr, sr = sr, tr
+			c = -c
+		}
+
+		//  ASCII only.
+		if tr < utf8.RuneSelf {
+			if sr >= 'A' && sr <= 'Z' {
+				if tr <= 'Z' {
+					// Same case.
+					return -c
+				}
+
+				diff := tr - (sr + 'a' - 'A')
+
+				if diff == 0 {
+					continue
+				}
+
+				if diff < 0 {
+					return c
+				}
+
+				if diff > 0 {
+					return -c
+				}
+			}
+		}
+
+		// Unicode.
+		r := unicode.SimpleFold(sr)
+		for r != sr && r < tr {
+			r = unicode.SimpleFold(r)
+		}
+
+		if r == tr {
+			continue
+		}
+
+		return -c
+	}
+
+	if s == "" && t == "" {
+		return 0
+	}
+
+	if s == "" {
+		return -1
+	}
+
+	return 1
+}
+
+// LessStrings returns whether s is less than t lexicographically.
+func LessStrings(s, t string) bool {
+	return Strings(s, t) < 0
+}
diff --git a/compare/compare_strings_test.go b/compare/compare_strings_test.go
new file mode 100644
index 000000000..82132cf11
--- /dev/null
+++ b/compare/compare_strings_test.go
@@ -0,0 +1,66 @@
+// Copyright 2019 The Hugo Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package compare
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+func TestCompare(t *testing.T) {
+	assert := require.New(t)
+	for i, test := range []struct {
+		a string
+		b string
+	}{
+		{"a", "a"},
+		{"A", "a"},
+		{"Ab", "Ac"},
+		{"az", "Za"},
+		{"C", "D"},
+		{"B", "a"},
+		{"C", ""},
+		{"", ""},
+		{"αβδC", "ΑΒΔD"},
+		{"αβδC", "ΑΒΔ"},
+		{"αβδ", "ΑΒΔD"},
+		{"αβδ", "ΑΒΔ"},
+		{"β", "δ"},
+		{"好", strings.ToLower("好")},
+	} {
+
+		expect := strings.Compare(strings.ToLower(test.a), strings.ToLower(test.b))
+		got := compareFold(test.a, test.b)
+
+		assert.Equal(expect, got, fmt.Sprintf("test %d: %d", i, expect))
+
+	}
+}
+
+func TestLexicographicSort(t *testing.T) {
+	assert := require.New(t)
+
+	s := []string{"b", "Bz", "ba", "A", "Ba", "ba"}
+
+	sort.Slice(s, func(i, j int) bool {
+		return LessStrings(s[i], s[j])
+	})
+
+	assert.Equal([]string{"A", "b", "Ba", "ba", "ba", "Bz"}, s)
+
+}
diff --git a/hugolib/menu_test.go b/hugolib/menu_test.go
index 3708173d9..0c366cafb 100644
--- a/hugolib/menu_test.go
+++ b/hugolib/menu_test.go
@@ -213,8 +213,8 @@ menu: "main"
 
 	b.Build(BuildCfg{})
 
-	b.AssertFileContent("public/index.html", "AMP and HTML|/blog/html-amp/|AMP only|/amp/blog/amp/|HTML only|/blog/html/|Home Sweet Home|/|")
-	b.AssertFileContent("public/amp/index.html", "AMP and HTML|/amp/blog/html-amp/|AMP only|/amp/blog/amp/|HTML only|/blog/html/|Home Sweet Home|/amp/|")
+	b.AssertFileContent("public/index.html", "AMP and HTML|/blog/html-amp/|AMP only|/amp/blog/amp/|Home Sweet Home|/|HTML only|/blog/html/|")
+	b.AssertFileContent("public/amp/index.html", "AMP and HTML|/amp/blog/html-amp/|AMP only|/amp/blog/amp/|Home Sweet Home|/amp/|HTML only|/blog/html/|")
 }
 
 // https://github.com/gohugoio/hugo/issues/5989
diff --git a/hugolib/taxonomy.go b/hugolib/taxonomy.go
index e6c80161a..a7965ec26 100644
--- a/hugolib/taxonomy.go
+++ b/hugolib/taxonomy.go
@@ -18,6 +18,8 @@ import (
 	"path"
 	"sort"
 
+	"github.com/gohugoio/hugo/compare"
+
 	"github.com/gohugoio/hugo/resources/page"
 	"github.com/gohugoio/hugo/resources/resource"
 )
@@ -73,7 +75,7 @@ func (i Taxonomy) TaxonomyArray() OrderedTaxonomy {
 // Alphabetical returns an ordered taxonomy sorted by key name.
 func (i Taxonomy) Alphabetical() OrderedTaxonomy {
 	name := func(i1, i2 *OrderedTaxonomyEntry) bool {
-		return i1.Name < i2.Name
+		return compare.LessStrings(i1.Name, i2.Name)
 	}
 
 	ia := i.TaxonomyArray()
@@ -89,7 +91,7 @@ func (i Taxonomy) ByCount() OrderedTaxonomy {
 		li2 := len(i2.WeightedPages)
 
 		if li1 == li2 {
-			return i1.Name < i2.Name
+			return compare.LessStrings(i1.Name, i2.Name)
 		}
 		return li1 > li2
 	}
diff --git a/navigation/menu.go b/navigation/menu.go
index 47d40a3c7..2cf9722e9 100644
--- a/navigation/menu.go
+++ b/navigation/menu.go
@@ -15,6 +15,7 @@ package navigation
 
 import (
 	"github.com/gohugoio/hugo/common/types"
+	"github.com/gohugoio/hugo/compare"
 
 	"html/template"
 	"sort"
@@ -159,10 +160,11 @@ func (by menuEntryBy) Sort(menu Menu) {
 
 var defaultMenuEntrySort = func(m1, m2 *MenuEntry) bool {
 	if m1.Weight == m2.Weight {
-		if m1.Name == m2.Name {
+		c := compare.Strings(m1.Name, m2.Name)
+		if c == 0 {
 			return m1.Identifier < m2.Identifier
 		}
-		return m1.Name < m2.Name
+		return c < 0
 	}
 
 	if m2.Weight == 0 {
@@ -205,7 +207,7 @@ func (m Menu) ByWeight() Menu {
 // ByName sorts the menu by the name defined in the menu configuration.
 func (m Menu) ByName() Menu {
 	title := func(m1, m2 *MenuEntry) bool {
-		return m1.Name < m2.Name
+		return compare.LessStrings(m1.Name, m2.Name)
 	}
 
 	menuEntryBy(title).Sort(m)
diff --git a/resources/page/pagegroup.go b/resources/page/pagegroup.go
index 3d87d9014..fbb6e7e53 100644
--- a/resources/page/pagegroup.go
+++ b/resources/page/pagegroup.go
@@ -52,7 +52,7 @@ func (s mapKeyByInt) Less(i, j int) bool { return s.mapKeyValues[i].Int() < s.ma
 type mapKeyByStr struct{ mapKeyValues }
 
 func (s mapKeyByStr) Less(i, j int) bool {
-	return s.mapKeyValues[i].String() < s.mapKeyValues[j].String()
+	return compare.LessStrings(s.mapKeyValues[i].String(), s.mapKeyValues[j].String())
 }
 
 func sortKeys(v []reflect.Value, order string) []reflect.Value {
diff --git a/resources/page/pages_sort.go b/resources/page/pages_sort.go
index 7b2a34a6a..b32d56ed8 100644
--- a/resources/page/pages_sort.go
+++ b/resources/page/pages_sort.go
@@ -18,6 +18,7 @@ import (
 
 	"github.com/gohugoio/hugo/resources/resource"
 
+	"github.com/gohugoio/hugo/compare"
 	"github.com/spf13/cast"
 )
 
@@ -50,13 +51,14 @@ func (by pageBy) Sort(pages Pages) {
 var DefaultPageSort = func(p1, p2 Page) bool {
 	if p1.Weight() == p2.Weight() {
 		if p1.Date().Unix() == p2.Date().Unix() {
-			if p1.LinkTitle() == p2.LinkTitle() {
+			c := compare.Strings(p1.LinkTitle(), p2.LinkTitle())
+			if c == 0 {
 				if p1.File().IsZero() || p2.File().IsZero() {
 					return p1.File().IsZero()
 				}
-				return p1.File().Filename() < p2.File().Filename()
+				return compare.LessStrings(p1.File().Filename(), p2.File().Filename())
 			}
-			return (p1.LinkTitle() < p2.LinkTitle())
+			return c < 0
 		}
 		return p1.Date().Unix() > p2.Date().Unix()
 	}
@@ -76,12 +78,13 @@ var languagePageSort = func(p1, p2 Page) bool {
 
 	if p1.Language().Weight == p2.Language().Weight {
 		if p1.Date().Unix() == p2.Date().Unix() {
-			if p1.LinkTitle() == p2.LinkTitle() {
+			c := compare.Strings(p1.LinkTitle(), p2.LinkTitle())
+			if c == 0 {
 				if !p1.File().IsZero() && !p2.File().IsZero() {
-					return p1.File().Filename() < p2.File().Filename()
+					return compare.LessStrings(p1.File().Filename(), p2.File().Filename())
 				}
 			}
-			return (p1.LinkTitle() < p2.LinkTitle())
+			return c < 0
 		}
 		return p1.Date().Unix() > p2.Date().Unix()
 	}
@@ -137,7 +140,7 @@ func (p Pages) ByTitle() Pages {
 	const key = "pageSort.ByTitle"
 
 	title := func(p1, p2 Page) bool {
-		return p1.Title() < p2.Title()
+		return compare.LessStrings(p1.Title(), p2.Title())
 	}
 
 	pages, _ := spc.get(key, pageBy(title).Sort, p)
@@ -154,7 +157,7 @@ func (p Pages) ByLinkTitle() Pages {
 	const key = "pageSort.ByLinkTitle"
 
 	linkTitle := func(p1, p2 Page) bool {
-		return p1.LinkTitle() < p2.LinkTitle()
+		return compare.LessStrings(p1.LinkTitle(), p2.LinkTitle())
 	}
 
 	pages, _ := spc.get(key, pageBy(linkTitle).Sort, p)
@@ -339,7 +342,8 @@ func (p Pages) ByParam(paramsKey interface{}) Pages {
 		s1 := cast.ToString(v1)
 		s2 := cast.ToString(v2)
 
-		return s1 < s2
+		return compare.LessStrings(s1, s2)
+
 	}
 
 	pages, _ := spc.get(key, pageBy(paramsKeyComparator).Sort, p)
diff --git a/tpl/collections/sort.go b/tpl/collections/sort.go
index 1ab4409b6..9639fe1d0 100644
--- a/tpl/collections/sort.go
+++ b/tpl/collections/sort.go
@@ -23,7 +23,7 @@ import (
 	"github.com/spf13/cast"
 )
 
-var comp = compare.New()
+var sortComp = compare.New(true)
 
 // Sort returns a sorted sequence.
 func (ns *Namespace) Sort(seq interface{}, args ...interface{}) (interface{}, error) {
@@ -133,15 +133,15 @@ func (p pairList) Less(i, j int) bool {
 	if iv.IsValid() {
 		if jv.IsValid() {
 			// can only call Interface() on valid reflect Values
-			return comp.Lt(iv.Interface(), jv.Interface())
+			return sortComp.Lt(iv.Interface(), jv.Interface())
 		}
 		// if j is invalid, test i against i's zero value
-		return comp.Lt(iv.Interface(), reflect.Zero(iv.Type()))
+		return sortComp.Lt(iv.Interface(), reflect.Zero(iv.Type()))
 	}
 
 	if jv.IsValid() {
 		// if i is invalid, test j against j's zero value
-		return comp.Lt(reflect.Zero(jv.Type()), jv.Interface())
+		return sortComp.Lt(reflect.Zero(jv.Type()), jv.Interface())
 	}
 
 	return false
diff --git a/tpl/collections/sort_test.go b/tpl/collections/sort_test.go
index f5f291f0b..612a928cb 100644
--- a/tpl/collections/sort_test.go
+++ b/tpl/collections/sort_test.go
@@ -45,6 +45,7 @@ func TestSort(t *testing.T) {
 	}{
 		{[]string{"class1", "class2", "class3"}, nil, "asc", []string{"class1", "class2", "class3"}},
 		{[]string{"class3", "class1", "class2"}, nil, "asc", []string{"class1", "class2", "class3"}},
+		{[]string{"CLASS3", "class1", "class2"}, nil, "asc", []string{"class1", "class2", "CLASS3"}},
 		// Issue 6023
 		{stringsSlice{"class3", "class1", "class2"}, nil, "asc", stringsSlice{"class1", "class2", "class3"}},
 
diff --git a/tpl/compare/compare.go b/tpl/compare/compare.go
index 251b3d13b..ec228822c 100644
--- a/tpl/compare/compare.go
+++ b/tpl/compare/compare.go
@@ -20,18 +20,20 @@ import (
 	"strconv"
 	"time"
 
-	"github.com/gohugoio/hugo/common/types"
-
 	"github.com/gohugoio/hugo/compare"
+
+	"github.com/gohugoio/hugo/common/types"
 )
 
 // New returns a new instance of the compare-namespaced template functions.
-func New() *Namespace {
-	return &Namespace{}
+func New(caseInsensitive bool) *Namespace {
+	return &Namespace{caseInsensitive: caseInsensitive}
 }
 
 // Namespace provides template functions for the "compare" namespace.
 type Namespace struct {
+	// Enable to do case insensitive string compares.
+	caseInsensitive bool
 }
 
 // Default checks whether a given value is set and returns a default value if it
@@ -89,7 +91,10 @@ func (*Namespace) Default(dflt interface{}, given ...interface{}) (interface{},
 }
 
 // Eq returns the boolean truth of arg1 == arg2.
-func (*Namespace) Eq(x, y interface{}) bool {
+func (ns *Namespace) Eq(x, y interface{}) bool {
+	if ns.caseInsensitive {
+		panic("caseInsensitive not implemented for Eq")
+	}
 	if e, ok := x.(compare.Eqer); ok {
 		return e.Eq(y)
 	}
@@ -157,7 +162,7 @@ func (n *Namespace) Conditional(condition bool, a, b interface{}) interface{} {
 	return b
 }
 
-func (*Namespace) compareGet(a interface{}, b interface{}) (float64, float64) {
+func (ns *Namespace) compareGet(a interface{}, b interface{}) (float64, float64) {
 	if ac, ok := a.(compare.Comparer); ok {
 		c := ac.Compare(b)
 		if c < 0 {
@@ -228,6 +233,17 @@ func (*Namespace) compareGet(a interface{}, b interface{}) (float64, float64) {
 		}
 	}
 
+	if ns.caseInsensitive && leftStr != nil && rightStr != nil {
+		c := compare.Strings(*leftStr, *rightStr)
+		if c < 0 {
+			return 0, 1
+		} else if c > 0 {
+			return 1, 0
+		} else {
+			return 0, 0
+		}
+	}
+
 	switch {
 	case leftStr == nil || rightStr == nil:
 	case *leftStr < *rightStr:
diff --git a/tpl/compare/compare_test.go b/tpl/compare/compare_test.go
index 6c4be7e50..a7b1e54a6 100644
--- a/tpl/compare/compare_test.go
+++ b/tpl/compare/compare_test.go
@@ -83,7 +83,7 @@ func TestDefaultFunc(t *testing.T) {
 
 	then := time.Now()
 	now := time.Now()
-	ns := New()
+	ns := New(false)
 
 	for i, test := range []struct {
 		dflt   interface{}
@@ -139,7 +139,7 @@ func TestDefaultFunc(t *testing.T) {
 func TestCompare(t *testing.T) {
 	t.Parallel()
 
-	n := New()
+	n := New(false)
 
 	for _, test := range []struct {
 		tstCompareType
@@ -233,6 +233,14 @@ func doTestCompare(t *testing.T, tp tstCompareType, funcUnderTest func(a, b inte
 	}
 }
 
+func TestCase(t *testing.T) {
+	assert := require.New(t)
+	n := New(true)
+
+	assert.True(n.Lt("az", "Za"))
+	assert.True(n.Gt("ab", "Ab"))
+}
+
 func TestTimeUnix(t *testing.T) {
 	t.Parallel()
 	var sec int64 = 1234567890
@@ -258,7 +266,7 @@ func TestTimeUnix(t *testing.T) {
 
 func TestConditional(t *testing.T) {
 	assert := require.New(t)
-	n := New()
+	n := New(false)
 	a, b := "a", "b"
 
 	assert.Equal(a, n.Conditional(true, a, b))
diff --git a/tpl/compare/init.go b/tpl/compare/init.go
index 619293203..2e536ff04 100644
--- a/tpl/compare/init.go
+++ b/tpl/compare/init.go
@@ -22,7 +22,7 @@ const name = "compare"
 
 func init() {
 	f := func(d *deps.Deps) *internal.TemplateFuncsNamespace {
-		ctx := New()
+		ctx := New(false)
 
 		ns := &internal.TemplateFuncsNamespace{
 			Name:    name,
diff --git a/tpl/compare/truth_test.go b/tpl/compare/truth_test.go
index 04d897212..7a9d03442 100644
--- a/tpl/compare/truth_test.go
+++ b/tpl/compare/truth_test.go
@@ -23,7 +23,7 @@ import (
 )
 
 func TestTruth(t *testing.T) {
-	n := New()
+	n := New(false)
 
 	truthv, falsev := reflect.ValueOf(time.Now()), reflect.ValueOf(false)