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