shithub: hugo

Info  •  Files  •  Log  •  Branches

Merge pull request #6149 from bep/sort-caseinsensitive

Implement lexicographically string sorting

--- 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 @@

 	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

--- /dev/null

+++ b/compare/compare_strings.go

@@ -1,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

+}

--- /dev/null

+++ b/compare/compare_strings_test.go

@@ -1,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)

+

+}

--- a/hugolib/menu_test.go

+++ b/hugolib/menu_test.go

@@ -213,8 +213,8 @@

 	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

--- a/hugolib/taxonomy.go

+++ b/hugolib/taxonomy.go

@@ -18,6 +18,8 @@

 	"path"

 	"sort"

+	"github.com/gohugoio/hugo/compare"

+

 	"github.com/gohugoio/hugo/resources/page"

 	"github.com/gohugoio/hugo/resources/resource"

 )

@@ -73,7 +75,7 @@

 // 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 @@

 		li2 := len(i2.WeightedPages)

 		if li1 == li2 {

-			return i1.Name < i2.Name

+			return compare.LessStrings(i1.Name, i2.Name)

 		}

 		return li1 > li2

 	}

--- a/navigation/menu.go

+++ b/navigation/menu.go

@@ -15,6 +15,7 @@

 import (

 	"github.com/gohugoio/hugo/common/types"

+	"github.com/gohugoio/hugo/compare"

 	"html/template"

 	"sort"

@@ -159,10 +160,11 @@

 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 @@

 // 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)

--- a/resources/page/pagegroup.go

+++ b/resources/page/pagegroup.go

@@ -52,7 +52,7 @@

 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 {

--- a/resources/page/pages_sort.go

+++ b/resources/page/pages_sort.go

@@ -18,6 +18,7 @@

 	"github.com/gohugoio/hugo/resources/resource"

+	"github.com/gohugoio/hugo/compare"

 	"github.com/spf13/cast"

 )

@@ -50,13 +51,14 @@

 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 @@

 	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 @@

 	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 @@

 	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 @@

 		s1 := cast.ToString(v1)

 		s2 := cast.ToString(v2)

-		return s1 < s2

+		return compare.LessStrings(s1, s2)

+

 	}

 	pages, _ := spc.get(key, pageBy(paramsKeyComparator).Sort, p)

--- a/tpl/collections/sort.go

+++ b/tpl/collections/sort.go

@@ -23,7 +23,7 @@

 	"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 @@

 	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

--- a/tpl/collections/sort_test.go

+++ b/tpl/collections/sort_test.go

@@ -45,6 +45,7 @@

 	}{

 		{[]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"}},

--- a/tpl/compare/compare.go

+++ b/tpl/compare/compare.go

@@ -20,18 +20,20 @@

 	"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 @@

 }

 // 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 @@

 	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 {

@@ -225,6 +230,17 @@

 		switch bv.Type() {

 		case timeType:

 			right = float64(toTimeUnix(bv))

+		}

+	}

+

+	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

 		}

 	}

--- a/tpl/compare/compare_test.go

+++ b/tpl/compare/compare_test.go

@@ -83,7 +83,7 @@

 	then := time.Now()

 	now := time.Now()

-	ns := New()

+	ns := New(false)

 	for i, test := range []struct {

 		dflt   interface{}

@@ -139,7 +139,7 @@

 func TestCompare(t *testing.T) {

 	t.Parallel()

-	n := New()

+	n := New(false)

 	for _, test := range []struct {

 		tstCompareType

@@ -233,6 +233,14 @@

 	}

 }

+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 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))

--- a/tpl/compare/init.go

+++ b/tpl/compare/init.go

@@ -22,7 +22,7 @@

 func init() {

 	f := func(d *deps.Deps) *internal.TemplateFuncsNamespace {

-		ctx := New()

+		ctx := New(false)

 		ns := &internal.TemplateFuncsNamespace{

 			Name:    name,

--- a/tpl/compare/truth_test.go

+++ b/tpl/compare/truth_test.go

@@ -23,7 +23,7 @@

 )

 func TestTruth(t *testing.T) {

-	n := New()

+	n := New(false)

 	truthv, falsev := reflect.ValueOf(time.Now()), reflect.ValueOf(false)