Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | |
| 5 | package value |
| 6 | |
| 7 | import ( |
| 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. |
| 16 | func SortKeys(vs []reflect.Value) []reflect.Value { |
| 17 | if len(vs) == 0 { |
| 18 | return vs |
| 19 | } |
| 20 | |
| 21 | // Sort the map keys. |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 22 | sort.SliceStable(vs, func(i, j int) bool { return isLess(vs[i], vs[j]) }) |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 34 | // isLess is a generic function for sorting arbitrary map keys. |
| 35 | // The inputs must be of the same type and must be comparable. |
| 36 | func 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: |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 45 | // NOTE: This does not sort -0 as less than +0 |
| 46 | // since Go maps treat -0 and +0 as equal keys. |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | } |