diff options
Diffstat (limited to 'vendor/github.com/google/go-cmp/cmp/internal/value/sort.go')
-rw-r--r-- | vendor/github.com/google/go-cmp/cmp/internal/value/sort.go | 111 |
1 files changed, 111 insertions, 0 deletions
diff --git a/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go b/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go new file mode 100644 index 0000000..fe8aa27 --- /dev/null +++ b/vendor/github.com/google/go-cmp/cmp/internal/value/sort.go | |||
@@ -0,0 +1,111 @@ | |||
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. | ||
22 | sort.Sort(valueSorter(vs)) | ||
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 | // TODO: Use sort.Slice once Google AppEngine is on Go1.8 or above. | ||
35 | type valueSorter []reflect.Value | ||
36 | |||
37 | func (vs valueSorter) Len() int { return len(vs) } | ||
38 | func (vs valueSorter) Less(i, j int) bool { return isLess(vs[i], vs[j]) } | ||
39 | func (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. | ||
43 | func 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 | } | ||