sort_test.go

Documentation: internal/fmtsort

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