sort_test.go (7250B)
1 // Copyright 2018 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package fmtsort_test
6
7 import (
8 "fmt"
9 "github.com/gohugoio/hugo/tpl/internal/go_templates/fmtsort"
10 "math"
11 "reflect"
12 "sort"
13 "strings"
14 "testing"
15 "unsafe"
16 )
17
18 var compareTests = [][]reflect.Value{
19 ct(reflect.TypeOf(int(0)), -1, 0, 1),
20 ct(reflect.TypeOf(int8(0)), -1, 0, 1),
21 ct(reflect.TypeOf(int16(0)), -1, 0, 1),
22 ct(reflect.TypeOf(int32(0)), -1, 0, 1),
23 ct(reflect.TypeOf(int64(0)), -1, 0, 1),
24 ct(reflect.TypeOf(uint(0)), 0, 1, 5),
25 ct(reflect.TypeOf(uint8(0)), 0, 1, 5),
26 ct(reflect.TypeOf(uint16(0)), 0, 1, 5),
27 ct(reflect.TypeOf(uint32(0)), 0, 1, 5),
28 ct(reflect.TypeOf(uint64(0)), 0, 1, 5),
29 ct(reflect.TypeOf(uintptr(0)), 0, 1, 5),
30 ct(reflect.TypeOf(string("")), "", "a", "ab"),
31 ct(reflect.TypeOf(float32(0)), math.NaN(), math.Inf(-1), -1e10, 0, 1e10, math.Inf(1)),
32 ct(reflect.TypeOf(float64(0)), math.NaN(), math.Inf(-1), -1e10, 0, 1e10, math.Inf(1)),
33 ct(reflect.TypeOf(complex64(0+1i)), -1-1i, -1+0i, -1+1i, 0-1i, 0+0i, 0+1i, 1-1i, 1+0i, 1+1i),
34 ct(reflect.TypeOf(complex128(0+1i)), -1-1i, -1+0i, -1+1i, 0-1i, 0+0i, 0+1i, 1-1i, 1+0i, 1+1i),
35 ct(reflect.TypeOf(false), false, true),
36 ct(reflect.TypeOf(&ints[0]), &ints[0], &ints[1], &ints[2]),
37 ct(reflect.TypeOf(unsafe.Pointer(&ints[0])), unsafe.Pointer(&ints[0]), unsafe.Pointer(&ints[1]), unsafe.Pointer(&ints[2])),
38 ct(reflect.TypeOf(chans[0]), chans[0], chans[1], chans[2]),
39 ct(reflect.TypeOf(toy{}), toy{0, 1}, toy{0, 2}, toy{1, -1}, toy{1, 1}),
40 ct(reflect.TypeOf([2]int{}), [2]int{1, 1}, [2]int{1, 2}, [2]int{2, 0}),
41 ct(reflect.TypeOf(any(any(0))), iFace, 1, 2, 3),
42 }
43
44 var iFace any
45
46 func ct(typ reflect.Type, args ...any) []reflect.Value {
47 value := make([]reflect.Value, len(args))
48 for i, v := range args {
49 x := reflect.ValueOf(v)
50 if !x.IsValid() { // Make it a typed nil.
51 x = reflect.Zero(typ)
52 } else {
53 x = x.Convert(typ)
54 }
55 value[i] = x
56 }
57 return value
58 }
59
60 func TestCompare(t *testing.T) {
61 for _, test := range compareTests {
62 for i, v0 := range test {
63 for j, v1 := range test {
64 c := fmtsort.Compare(v0, v1)
65 var expect int
66 switch {
67 case i == j:
68 expect = 0
69 // NaNs are tricky.
70 if typ := v0.Type(); (typ.Kind() == reflect.Float32 || typ.Kind() == reflect.Float64) && math.IsNaN(v0.Float()) {
71 expect = -1
72 }
73 case i < j:
74 expect = -1
75 case i > j:
76 expect = 1
77 }
78 if c != expect {
79 t.Errorf("%s: compare(%v,%v)=%d; expect %d", v0.Type(), v0, v1, c, expect)
80 }
81 }
82 }
83 }
84 }
85
86 type sortTest struct {
87 data any // Always a map.
88 print string // Printed result using our custom printer.
89 }
90
91 var sortTests = []sortTest{
92 {
93 map[int]string{7: "bar", -3: "foo"},
94 "-3:foo 7:bar",
95 },
96 {
97 map[uint8]string{7: "bar", 3: "foo"},
98 "3:foo 7:bar",
99 },
100 {
101 map[string]string{"7": "bar", "3": "foo"},
102 "3:foo 7:bar",
103 },
104 {
105 map[float64]string{7: "bar", -3: "foo", math.NaN(): "nan", math.Inf(0): "inf"},
106 "NaN:nan -3:foo 7:bar +Inf:inf",
107 },
108 {
109 map[complex128]string{7 + 2i: "bar2", 7 + 1i: "bar", -3: "foo", complex(math.NaN(), 0i): "nan", complex(math.Inf(0), 0i): "inf"},
110 "(NaN+0i):nan (-3+0i):foo (7+1i):bar (7+2i):bar2 (+Inf+0i):inf",
111 },
112 {
113 map[bool]string{true: "true", false: "false"},
114 "false:false true:true",
115 },
116 {
117 chanMap(),
118 "CHAN0:0 CHAN1:1 CHAN2:2",
119 },
120 {
121 pointerMap(),
122 "PTR0:0 PTR1:1 PTR2:2",
123 },
124 {
125 unsafePointerMap(),
126 "UNSAFEPTR0:0 UNSAFEPTR1:1 UNSAFEPTR2:2",
127 },
128 {
129 map[toy]string{{7, 2}: "72", {7, 1}: "71", {3, 4}: "34"},
130 "{3 4}:34 {7 1}:71 {7 2}:72",
131 },
132 {
133 map[[2]int]string{{7, 2}: "72", {7, 1}: "71", {3, 4}: "34"},
134 "[3 4]:34 [7 1]:71 [7 2]:72",
135 },
136 }
137
138 func sprint(data any) string {
139 om := fmtsort.Sort(reflect.ValueOf(data))
140 if om == nil {
141 return "nil"
142 }
143 b := new(strings.Builder)
144 for i, key := range om.Key {
145 if i > 0 {
146 b.WriteRune(' ')
147 }
148 b.WriteString(sprintKey(key))
149 b.WriteRune(':')
150 b.WriteString(fmt.Sprint(om.Value[i]))
151 }
152 return b.String()
153 }
154
155 // sprintKey formats a reflect.Value but gives reproducible values for some
156 // problematic types such as pointers. Note that it only does special handling
157 // for the troublesome types used in the test cases; it is not a general
158 // printer.
159 func sprintKey(key reflect.Value) string {
160 switch str := key.Type().String(); str {
161 case "*int":
162 ptr := key.Interface().(*int)
163 for i := range ints {
164 if ptr == &ints[i] {
165 return fmt.Sprintf("PTR%d", i)
166 }
167 }
168 return "PTR???"
169 case "unsafe.Pointer":
170 ptr := key.Interface().(unsafe.Pointer)
171 for i := range ints {
172 if ptr == unsafe.Pointer(&ints[i]) {
173 return fmt.Sprintf("UNSAFEPTR%d", i)
174 }
175 }
176 return "UNSAFEPTR???"
177 case "chan int":
178 c := key.Interface().(chan int)
179 for i := range chans {
180 if c == chans[i] {
181 return fmt.Sprintf("CHAN%d", i)
182 }
183 }
184 return "CHAN???"
185 default:
186 return fmt.Sprint(key)
187 }
188 }
189
190 var (
191 ints [3]int
192 chans = makeChans()
193 )
194
195 func makeChans() []chan int {
196 cs := []chan int{make(chan int), make(chan int), make(chan int)}
197 // Order channels by address. See issue #49431.
198 // TODO: pin these pointers once pinning is available (#46787).
199 sort.Slice(cs, func(i, j int) bool {
200 return uintptr(reflect.ValueOf(cs[i]).UnsafePointer()) < uintptr(reflect.ValueOf(cs[j]).UnsafePointer())
201 })
202 return cs
203 }
204
205 func pointerMap() map[*int]string {
206 m := make(map[*int]string)
207 for i := 2; i >= 0; i-- {
208 m[&ints[i]] = fmt.Sprint(i)
209 }
210 return m
211 }
212
213 func unsafePointerMap() map[unsafe.Pointer]string {
214 m := make(map[unsafe.Pointer]string)
215 for i := 2; i >= 0; i-- {
216 m[unsafe.Pointer(&ints[i])] = fmt.Sprint(i)
217 }
218 return m
219 }
220
221 func chanMap() map[chan int]string {
222 m := make(map[chan int]string)
223 for i := 2; i >= 0; i-- {
224 m[chans[i]] = fmt.Sprint(i)
225 }
226 return m
227 }
228
229 type toy struct {
230 A int // Exported.
231 b int // Unexported.
232 }
233
234 func TestOrder(t *testing.T) {
235 for _, test := range sortTests {
236 got := sprint(test.data)
237 if got != test.print {
238 t.Errorf("%s: got %q, want %q", reflect.TypeOf(test.data), got, test.print)
239 }
240 }
241 }
242
243 func TestInterface(t *testing.T) {
244 // A map containing multiple concrete types should be sorted by type,
245 // then value. However, the relative ordering of types is unspecified,
246 // so test this by checking the presence of sorted subgroups.
247 m := map[any]string{
248 [2]int{1, 0}: "",
249 [2]int{0, 1}: "",
250 true: "",
251 false: "",
252 3.1: "",
253 2.1: "",
254 1.1: "",
255 math.NaN(): "",
256 3: "",
257 2: "",
258 1: "",
259 "c": "",
260 "b": "",
261 "a": "",
262 struct{ x, y int }{1, 0}: "",
263 struct{ x, y int }{0, 1}: "",
264 }
265 got := sprint(m)
266 typeGroups := []string{
267 "NaN: 1.1: 2.1: 3.1:", // float64
268 "false: true:", // bool
269 "1: 2: 3:", // int
270 "a: b: c:", // string
271 "[0 1]: [1 0]:", // [2]int
272 "{0 1}: {1 0}:", // struct{ x int; y int }
273 }
274 for _, g := range typeGroups {
275 if !strings.Contains(got, g) {
276 t.Errorf("sorted map should contain %q", g)
277 }
278 }
279 }