sort.go (5974B)
1 // Copyright 2018 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
5 // Package fmtsort provides a general stable ordering mechanism
6 // for maps, on behalf of the fmt and text/template packages.
7 // It is not guaranteed to be efficient and works only for types
8 // that are valid map keys.
9 package fmtsort
10
11 import (
12 "reflect"
13 "sort"
14 )
15
16 // Note: Throughout this package we avoid calling reflect.Value.Interface as
17 // it is not always legal to do so and it's easier to avoid the issue than to face it.
18
19 // SortedMap represents a map's keys and values. The keys and values are
20 // aligned in index order: Value[i] is the value in the map corresponding to Key[i].
21 type SortedMap struct {
22 Key []reflect.Value
23 Value []reflect.Value
24 }
25
26 func (o *SortedMap) Len() int { return len(o.Key) }
27 func (o *SortedMap) Less(i, j int) bool { return compare(o.Key[i], o.Key[j]) < 0 }
28 func (o *SortedMap) Swap(i, j int) {
29 o.Key[i], o.Key[j] = o.Key[j], o.Key[i]
30 o.Value[i], o.Value[j] = o.Value[j], o.Value[i]
31 }
32
33 // Sort accepts a map and returns a SortedMap that has the same keys and
34 // values but in a stable sorted order according to the keys, modulo issues
35 // raised by unorderable key values such as NaNs.
36 //
37 // The ordering rules are more general than with Go's < operator:
38 //
39 // - when applicable, nil compares low
40 // - ints, floats, and strings order by <
41 // - NaN compares less than non-NaN floats
42 // - bool compares false before true
43 // - complex compares real, then imag
44 // - pointers compare by machine address
45 // - channel values compare by machine address
46 // - structs compare each field in turn
47 // - arrays compare each element in turn.
48 // Otherwise identical arrays compare by length.
49 // - interface values compare first by reflect.Type describing the concrete type
50 // and then by concrete value as described in the previous rules.
51 //
52 func Sort(mapValue reflect.Value) *SortedMap {
53 if mapValue.Type().Kind() != reflect.Map {
54 return nil
55 }
56 // Note: this code is arranged to not panic even in the presence
57 // of a concurrent map update. The runtime is responsible for
58 // yelling loudly if that happens. See issue 33275.
59 n := mapValue.Len()
60 key := make([]reflect.Value, 0, n)
61 value := make([]reflect.Value, 0, n)
62 iter := mapValue.MapRange()
63 for iter.Next() {
64 key = append(key, iter.Key())
65 value = append(value, iter.Value())
66 }
67 sorted := &SortedMap{
68 Key: key,
69 Value: value,
70 }
71 sort.Stable(sorted)
72 return sorted
73 }
74
75 // compare compares two values of the same type. It returns -1, 0, 1
76 // according to whether a > b (1), a == b (0), or a < b (-1).
77 // If the types differ, it returns -1.
78 // See the comment on Sort for the comparison rules.
79 func compare(aVal, bVal reflect.Value) int {
80 aType, bType := aVal.Type(), bVal.Type()
81 if aType != bType {
82 return -1 // No good answer possible, but don't return 0: they're not equal.
83 }
84 switch aVal.Kind() {
85 case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
86 a, b := aVal.Int(), bVal.Int()
87 switch {
88 case a < b:
89 return -1
90 case a > b:
91 return 1
92 default:
93 return 0
94 }
95 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
96 a, b := aVal.Uint(), bVal.Uint()
97 switch {
98 case a < b:
99 return -1
100 case a > b:
101 return 1
102 default:
103 return 0
104 }
105 case reflect.String:
106 a, b := aVal.String(), bVal.String()
107 switch {
108 case a < b:
109 return -1
110 case a > b:
111 return 1
112 default:
113 return 0
114 }
115 case reflect.Float32, reflect.Float64:
116 return floatCompare(aVal.Float(), bVal.Float())
117 case reflect.Complex64, reflect.Complex128:
118 a, b := aVal.Complex(), bVal.Complex()
119 if c := floatCompare(real(a), real(b)); c != 0 {
120 return c
121 }
122 return floatCompare(imag(a), imag(b))
123 case reflect.Bool:
124 a, b := aVal.Bool(), bVal.Bool()
125 switch {
126 case a == b:
127 return 0
128 case a:
129 return 1
130 default:
131 return -1
132 }
133 case reflect.Pointer, reflect.UnsafePointer:
134 a, b := aVal.Pointer(), bVal.Pointer()
135 switch {
136 case a < b:
137 return -1
138 case a > b:
139 return 1
140 default:
141 return 0
142 }
143 case reflect.Chan:
144 if c, ok := nilCompare(aVal, bVal); ok {
145 return c
146 }
147 ap, bp := aVal.Pointer(), bVal.Pointer()
148 switch {
149 case ap < bp:
150 return -1
151 case ap > bp:
152 return 1
153 default:
154 return 0
155 }
156 case reflect.Struct:
157 for i := 0; i < aVal.NumField(); i++ {
158 if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
159 return c
160 }
161 }
162 return 0
163 case reflect.Array:
164 for i := 0; i < aVal.Len(); i++ {
165 if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
166 return c
167 }
168 }
169 return 0
170 case reflect.Interface:
171 if c, ok := nilCompare(aVal, bVal); ok {
172 return c
173 }
174 c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
175 if c != 0 {
176 return c
177 }
178 return compare(aVal.Elem(), bVal.Elem())
179 default:
180 // Certain types cannot appear as keys (maps, funcs, slices), but be explicit.
181 panic("bad type in compare: " + aType.String())
182 }
183 }
184
185 // nilCompare checks whether either value is nil. If not, the boolean is false.
186 // If either value is nil, the boolean is true and the integer is the comparison
187 // value. The comparison is defined to be 0 if both are nil, otherwise the one
188 // nil value compares low. Both arguments must represent a chan, func,
189 // interface, map, pointer, or slice.
190 func nilCompare(aVal, bVal reflect.Value) (int, bool) {
191 if aVal.IsNil() {
192 if bVal.IsNil() {
193 return 0, true
194 }
195 return -1, true
196 }
197 if bVal.IsNil() {
198 return 1, true
199 }
200 return 0, false
201 }
202
203 // floatCompare compares two floating-point values. NaNs compare low.
204 func floatCompare(a, b float64) int {
205 switch {
206 case isNaN(a):
207 return -1 // No good answer if b is a NaN so don't bother checking.
208 case isNaN(b):
209 return 1
210 case a < b:
211 return -1
212 case a > b:
213 return 1
214 }
215 return 0
216 }
217
218 func isNaN(a float64) bool {
219 return a != a
220 }