sort.go (4920B)
1 // Copyright 2017 The Hugo Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 package collections
15
16 import (
17 "errors"
18 "reflect"
19 "sort"
20 "strings"
21
22 "github.com/gohugoio/hugo/common/maps"
23 "github.com/gohugoio/hugo/langs"
24 "github.com/gohugoio/hugo/tpl/compare"
25 "github.com/spf13/cast"
26 )
27
28 // Sort returns a sorted sequence.
29 func (ns *Namespace) Sort(seq any, args ...any) (any, error) {
30 if seq == nil {
31 return nil, errors.New("sequence must be provided")
32 }
33
34 seqv, isNil := indirect(reflect.ValueOf(seq))
35 if isNil {
36 return nil, errors.New("can't iterate over a nil value")
37 }
38
39 var sliceType reflect.Type
40 switch seqv.Kind() {
41 case reflect.Array, reflect.Slice:
42 sliceType = seqv.Type()
43 case reflect.Map:
44 sliceType = reflect.SliceOf(seqv.Type().Elem())
45 default:
46 return nil, errors.New("can't sort " + reflect.ValueOf(seq).Type().String())
47 }
48
49 collator := langs.GetCollator(ns.deps.Language)
50
51 // Create a list of pairs that will be used to do the sort
52 p := pairList{Collator: collator, sortComp: ns.sortComp, SortAsc: true, SliceType: sliceType}
53 p.Pairs = make([]pair, seqv.Len())
54
55 var sortByField string
56 for i, l := range args {
57 dStr, err := cast.ToStringE(l)
58 switch {
59 case i == 0 && err != nil:
60 sortByField = ""
61 case i == 0 && err == nil:
62 sortByField = dStr
63 case i == 1 && err == nil && dStr == "desc":
64 p.SortAsc = false
65 case i == 1:
66 p.SortAsc = true
67 }
68 }
69 path := strings.Split(strings.Trim(sortByField, "."), ".")
70
71 switch seqv.Kind() {
72 case reflect.Array, reflect.Slice:
73 for i := 0; i < seqv.Len(); i++ {
74 p.Pairs[i].Value = seqv.Index(i)
75 if sortByField == "" || sortByField == "value" {
76 p.Pairs[i].Key = p.Pairs[i].Value
77 } else {
78 v := p.Pairs[i].Value
79 var err error
80 for i, elemName := range path {
81 v, err = evaluateSubElem(v, elemName)
82 if err != nil {
83 return nil, err
84 }
85 if !v.IsValid() {
86 continue
87 }
88 // Special handling of lower cased maps.
89 if params, ok := v.Interface().(maps.Params); ok {
90 v = reflect.ValueOf(params.Get(path[i+1:]...))
91 break
92 }
93 }
94 p.Pairs[i].Key = v
95 }
96 }
97
98 case reflect.Map:
99 keys := seqv.MapKeys()
100 for i := 0; i < seqv.Len(); i++ {
101 p.Pairs[i].Value = seqv.MapIndex(keys[i])
102
103 if sortByField == "" {
104 p.Pairs[i].Key = keys[i]
105 } else if sortByField == "value" {
106 p.Pairs[i].Key = p.Pairs[i].Value
107 } else {
108 v := p.Pairs[i].Value
109 var err error
110 for i, elemName := range path {
111 v, err = evaluateSubElem(v, elemName)
112 if err != nil {
113 return nil, err
114 }
115 if !v.IsValid() {
116 continue
117 }
118 // Special handling of lower cased maps.
119 if params, ok := v.Interface().(maps.Params); ok {
120 v = reflect.ValueOf(params.Get(path[i+1:]...))
121 break
122 }
123 }
124 p.Pairs[i].Key = v
125 }
126 }
127 }
128
129 collator.Lock()
130 defer collator.Unlock()
131
132 return p.sort(), nil
133 }
134
135 // Credit for pair sorting method goes to Andrew Gerrand
136 // https://groups.google.com/forum/#!topic/golang-nuts/FT7cjmcL7gw
137 // A data structure to hold a key/value pair.
138 type pair struct {
139 Key reflect.Value
140 Value reflect.Value
141 }
142
143 // A slice of pairs that implements sort.Interface to sort by Value.
144 type pairList struct {
145 Collator *langs.Collator
146 sortComp *compare.Namespace
147 Pairs []pair
148 SortAsc bool
149 SliceType reflect.Type
150 }
151
152 func (p pairList) Swap(i, j int) { p.Pairs[i], p.Pairs[j] = p.Pairs[j], p.Pairs[i] }
153 func (p pairList) Len() int { return len(p.Pairs) }
154 func (p pairList) Less(i, j int) bool {
155 iv := p.Pairs[i].Key
156 jv := p.Pairs[j].Key
157
158 if iv.IsValid() {
159 if jv.IsValid() {
160 // can only call Interface() on valid reflect Values
161 return p.sortComp.LtCollate(p.Collator, iv.Interface(), jv.Interface())
162 }
163
164 // if j is invalid, test i against i's zero value
165 return p.sortComp.LtCollate(p.Collator, iv.Interface(), reflect.Zero(iv.Type()))
166 }
167
168 if jv.IsValid() {
169 // if i is invalid, test j against j's zero value
170 return p.sortComp.LtCollate(p.Collator, reflect.Zero(jv.Type()), jv.Interface())
171 }
172
173 return false
174 }
175
176 // sorts a pairList and returns a slice of sorted values
177 func (p pairList) sort() any {
178 if p.SortAsc {
179 sort.Stable(p)
180 } else {
181 sort.Stable(sort.Reverse(p))
182 }
183 sorted := reflect.MakeSlice(p.SliceType, len(p.Pairs), len(p.Pairs))
184 for i, v := range p.Pairs {
185 sorted.Index(i).Set(v.Value)
186 }
187
188 return sorted.Interface()
189 }