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