sort_test.go

     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  	"cmp"
     9  	"fmt"
    10  	"internal/fmtsort"
    11  	"math"
    12  	"reflect"
    13  	"runtime"
    14  	"slices"
    15  	"strings"
    16  	"testing"
    17  	"unsafe"
    18  )
    19  
    20  var 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  
    46  var iFace any
    47  
    48  func 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  
    62  func 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  
    84  type sortTest struct {
    85  	data  any    // Always a map.
    86  	print string // Printed result using our custom printer.
    87  }
    88  
    89  var 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  
   136  func 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.
   157  func 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  
   188  var (
   189  	ints  [3]int
   190  	chans = makeChans()
   191  	pin   runtime.Pinner
   192  )
   193  
   194  func 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  
   206  func 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  
   214  func 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  
   222  func 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  
   230  type toy struct {
   231  	A int // Exported.
   232  	b int // Unexported.
   233  }
   234  
   235  func 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  
   244  func 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
View as plain text