src/internal/fmtsort/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 }