1// Copyright 2017, 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 5package value 6 7import ( 8 "fmt" 9 "math" 10 "reflect" 11 "sort" 12) 13 14// SortKeys sorts a list of map keys, deduplicating keys if necessary. 15// The type of each value must be comparable. 16func SortKeys(vs []reflect.Value) []reflect.Value { 17 if len(vs) == 0 { 18 return vs 19 } 20 21 // Sort the map keys. 22 sort.SliceStable(vs, func(i, j int) bool { return isLess(vs[i], vs[j]) }) 23 24 // Deduplicate keys (fails for NaNs). 25 vs2 := vs[:1] 26 for _, v := range vs[1:] { 27 if isLess(vs2[len(vs2)-1], v) { 28 vs2 = append(vs2, v) 29 } 30 } 31 return vs2 32} 33 34// isLess is a generic function for sorting arbitrary map keys. 35// The inputs must be of the same type and must be comparable. 36func isLess(x, y reflect.Value) bool { 37 switch x.Type().Kind() { 38 case reflect.Bool: 39 return !x.Bool() && y.Bool() 40 case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: 41 return x.Int() < y.Int() 42 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: 43 return x.Uint() < y.Uint() 44 case reflect.Float32, reflect.Float64: 45 // NOTE: This does not sort -0 as less than +0 46 // since Go maps treat -0 and +0 as equal keys. 47 fx, fy := x.Float(), y.Float() 48 return fx < fy || math.IsNaN(fx) && !math.IsNaN(fy) 49 case reflect.Complex64, reflect.Complex128: 50 cx, cy := x.Complex(), y.Complex() 51 rx, ix, ry, iy := real(cx), imag(cx), real(cy), imag(cy) 52 if rx == ry || (math.IsNaN(rx) && math.IsNaN(ry)) { 53 return ix < iy || math.IsNaN(ix) && !math.IsNaN(iy) 54 } 55 return rx < ry || math.IsNaN(rx) && !math.IsNaN(ry) 56 case reflect.Ptr, reflect.UnsafePointer, reflect.Chan: 57 return x.Pointer() < y.Pointer() 58 case reflect.String: 59 return x.String() < y.String() 60 case reflect.Array: 61 for i := 0; i < x.Len(); i++ { 62 if isLess(x.Index(i), y.Index(i)) { 63 return true 64 } 65 if isLess(y.Index(i), x.Index(i)) { 66 return false 67 } 68 } 69 return false 70 case reflect.Struct: 71 for i := 0; i < x.NumField(); i++ { 72 if isLess(x.Field(i), y.Field(i)) { 73 return true 74 } 75 if isLess(y.Field(i), x.Field(i)) { 76 return false 77 } 78 } 79 return false 80 case reflect.Interface: 81 vx, vy := x.Elem(), y.Elem() 82 if !vx.IsValid() || !vy.IsValid() { 83 return !vx.IsValid() && vy.IsValid() 84 } 85 tx, ty := vx.Type(), vy.Type() 86 if tx == ty { 87 return isLess(x.Elem(), y.Elem()) 88 } 89 if tx.Kind() != ty.Kind() { 90 return vx.Kind() < vy.Kind() 91 } 92 if tx.String() != ty.String() { 93 return tx.String() < ty.String() 94 } 95 if tx.PkgPath() != ty.PkgPath() { 96 return tx.PkgPath() < ty.PkgPath() 97 } 98 // This can happen in rare situations, so we fallback to just comparing 99 // the unique pointer for a reflect.Type. This guarantees deterministic 100 // ordering within a program, but it is obviously not stable. 101 return reflect.ValueOf(vx.Type()).Pointer() < reflect.ValueOf(vy.Type()).Pointer() 102 default: 103 // Must be Func, Map, or Slice; which are not comparable. 104 panic(fmt.Sprintf("%T is not comparable", x.Type())) 105 } 106} 107