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