Deterministic sorting for all map key types.
R=dnj@chromium.org
BUG=
Review URL: https://chromiumcodereview.appspot.com/1716443004 .
diff --git a/render/render.go b/render/render.go
index bdb307c..23b7a58 100644
--- a/render/render.go
+++ b/render/render.go
@@ -330,40 +330,148 @@
}
}
+type cmpFn func(a, b reflect.Value) int
+
type sortableValueSlice struct {
- kind reflect.Kind
+ cmp cmpFn
elements []reflect.Value
}
-func (s *sortableValueSlice) Len() int {
+func (s sortableValueSlice) Len() int {
return len(s.elements)
}
-func (s *sortableValueSlice) Less(i, j int) bool {
- switch s.kind {
- case reflect.String:
- return s.elements[i].String() < s.elements[j].String()
-
- case reflect.Int:
- return s.elements[i].Int() < s.elements[j].Int()
-
- default:
- panic(fmt.Errorf("unsupported sort kind: %s", s.kind))
- }
+func (s sortableValueSlice) Less(i, j int) bool {
+ return s.cmp(s.elements[i], s.elements[j]) < 0
}
-func (s *sortableValueSlice) Swap(i, j int) {
+func (s sortableValueSlice) Swap(i, j int) {
s.elements[i], s.elements[j] = s.elements[j], s.elements[i]
}
-func tryAndSortMapKeys(mt reflect.Type, k []reflect.Value) {
- // Try our stock sortable values.
- switch mt.Key().Kind() {
- case reflect.String, reflect.Int:
- vs := &sortableValueSlice{
- kind: mt.Key().Kind(),
- elements: k,
+// cmpForType returns a cmpFn which sorts the data for some type t in the same
+// order that a go-native map key is compared for equality.
+func cmpForType(t reflect.Type) cmpFn {
+ switch t.Kind() {
+ case reflect.String:
+ return func(av, bv reflect.Value) int {
+ a, b := av.String(), bv.String()
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ return 0
}
- sort.Sort(vs)
+
+ case reflect.Bool:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Bool(), bv.Bool()
+ if !a && b {
+ return -1
+ } else if a && !b {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Int(), bv.Int()
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32,
+ reflect.Uint64, reflect.Uintptr, reflect.UnsafePointer:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Uint(), bv.Uint()
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Float32, reflect.Float64:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Float(), bv.Float()
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Interface:
+ return func(av, bv reflect.Value) int {
+ a, b := av.InterfaceData(), bv.InterfaceData()
+ if a[0] < b[0] {
+ return -1
+ } else if a[0] > b[0] {
+ return 1
+ }
+ if a[1] < b[1] {
+ return -1
+ } else if a[1] > b[1] {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Complex64, reflect.Complex128:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Complex(), bv.Complex()
+ if real(a) < real(b) {
+ return -1
+ } else if real(a) > real(b) {
+ return 1
+ }
+ if imag(a) < imag(b) {
+ return -1
+ } else if imag(a) > imag(b) {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Ptr, reflect.Chan:
+ return func(av, bv reflect.Value) int {
+ a, b := av.Pointer(), bv.Pointer()
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ return 0
+ }
+
+ case reflect.Struct:
+ cmpLst := make([]cmpFn, t.NumField())
+ for i := range cmpLst {
+ cmpLst[i] = cmpForType(t.Field(i).Type)
+ }
+ return func(a, b reflect.Value) int {
+ for i, cmp := range cmpLst {
+ if rslt := cmp(a.Field(i), b.Field(i)); rslt != 0 {
+ return rslt
+ }
+ }
+ return 0
+ }
+ }
+
+ return nil
+}
+
+func tryAndSortMapKeys(mt reflect.Type, k []reflect.Value) {
+ if cmp := cmpForType(mt.Key()); cmp != nil {
+ sort.Sort(sortableValueSlice{cmp, k})
}
}
diff --git a/render/render_test.go b/render/render_test.go
index bb2af4b..6e7c92d 100644
--- a/render/render_test.go
+++ b/render/render_test.go
@@ -203,3 +203,71 @@
func sanitizePointer(s string) string {
return pointerRE.ReplaceAllString(s, "(0x600dd065)")
}
+
+type chanList []chan int
+
+func (c chanList) Len() int { return len(c) }
+func (c chanList) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
+func (c chanList) Less(i, j int) bool {
+ return reflect.ValueOf(c[i]).Pointer() < reflect.ValueOf(c[j]).Pointer()
+}
+
+func TestMapSortRendering(t *testing.T) {
+ type namedMapType map[int]struct{ a int }
+ type mapKey struct{ a, b int }
+
+ chans := make(chanList, 5)
+ for i := range chans {
+ chans[i] = make(chan int)
+ }
+
+ tcs := []struct {
+ in interface{}
+ expect string
+ }{
+ {
+ map[uint32]struct{}{1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {}},
+ "map[uint32]struct {}{1:{}, 2:{}, 3:{}, 4:{}, 5:{}, 6:{}, 7:{}, 8:{}}",
+ },
+ {
+ map[int8]struct{}{1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {}},
+ "map[int8]struct {}{1:{}, 2:{}, 3:{}, 4:{}, 5:{}, 6:{}, 7:{}, 8:{}}",
+ },
+ {
+ map[uintptr]struct{}{1: {}, 2: {}, 3: {}, 4: {}, 5: {}, 6: {}, 7: {}, 8: {}},
+ "map[uintptr]struct {}{1:{}, 2:{}, 3:{}, 4:{}, 5:{}, 6:{}, 7:{}, 8:{}}",
+ },
+ {
+ namedMapType{10: struct{ a int }{20}},
+ "render.namedMapType{10:struct { a int }{20}}",
+ },
+ {
+ map[mapKey]struct{}{mapKey{3, 1}: {}, mapKey{1, 3}: {}, mapKey{1, 2}: {}, mapKey{2, 1}: {}},
+ "map[render.mapKey]struct {}{render.mapKey{a:1, b:2}:{}, render.mapKey{a:1, b:3}:{}, render.mapKey{a:2, b:1}:{}, render.mapKey{a:3, b:1}:{}}",
+ },
+ {
+ map[float64]struct{}{10.5: {}, 10.15: {}, 1203: {}, 1: {}, 2: {}},
+ "map[float64]struct {}{1:{}, 2:{}, 10.15:{}, 10.5:{}, 1203:{}}",
+ },
+ {
+ map[bool]struct{}{true: {}, false: {}},
+ "map[bool]struct {}{false:{}, true:{}}",
+ },
+ {
+ map[interface{}]struct{}{1: {}, 2: {}, 3: {}, "foo": {}},
+ `map[interface{}]struct {}{1:{}, 2:{}, 3:{}, "foo":{}}`,
+ },
+ {
+ map[complex64]struct{}{1 + 2i: {}, 2 + 1i: {}, 3 + 1i: {}, 1 + 3i: {}},
+ "map[complex64]struct {}{(1+2i):{}, (1+3i):{}, (2+1i):{}, (3+1i):{}}",
+ },
+ {
+ map[chan int]string{nil: "a", chans[0]: "b", chans[1]: "c", chans[2]: "d", chans[3]: "e", chans[4]: "f"},
+ `map[(chan int)]string{(chan int)(PTR):"a", (chan int)(PTR):"b", (chan int)(PTR):"c", (chan int)(PTR):"d", (chan int)(PTR):"e", (chan int)(PTR):"f"}`,
+ },
+ }
+
+ for _, tc := range tcs {
+ assertRendersLike(t, reflect.TypeOf(tc.in).Name(), tc.in, tc.expect)
+ }
+}
