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. 9package fmtsort 10 11import ( 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]. 21type SortedMap struct { 22 Key []reflect.Value 23 Value []reflect.Value 24} 25 26func (o *SortedMap) Len() int { return len(o.Key) } 27func (o *SortedMap) Less(i, j int) bool { return compare(o.Key[i], o.Key[j]) < 0 } 28func (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// 52func 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. 79func 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. 190func 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. 204func 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 218func isNaN(a float64) bool { 219 return a != a 220} 221