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 key, value := mapElems(mapValue) 57 sorted := &SortedMap{ 58 Key: key, 59 Value: value, 60 } 61 sort.Stable(sorted) 62 return sorted 63} 64 65// compare compares two values of the same type. It returns -1, 0, 1 66// according to whether a > b (1), a == b (0), or a < b (-1). 67// If the types differ, it returns -1. 68// See the comment on Sort for the comparison rules. 69func compare(aVal, bVal reflect.Value) int { 70 aType, bType := aVal.Type(), bVal.Type() 71 if aType != bType { 72 return -1 // No good answer possible, but don't return 0: they're not equal. 73 } 74 switch aVal.Kind() { 75 case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: 76 a, b := aVal.Int(), bVal.Int() 77 switch { 78 case a < b: 79 return -1 80 case a > b: 81 return 1 82 default: 83 return 0 84 } 85 case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: 86 a, b := aVal.Uint(), bVal.Uint() 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.String: 96 a, b := aVal.String(), bVal.String() 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.Float32, reflect.Float64: 106 return floatCompare(aVal.Float(), bVal.Float()) 107 case reflect.Complex64, reflect.Complex128: 108 a, b := aVal.Complex(), bVal.Complex() 109 if c := floatCompare(real(a), real(b)); c != 0 { 110 return c 111 } 112 return floatCompare(imag(a), imag(b)) 113 case reflect.Bool: 114 a, b := aVal.Bool(), bVal.Bool() 115 switch { 116 case a == b: 117 return 0 118 case a: 119 return 1 120 default: 121 return -1 122 } 123 case reflect.Ptr: 124 a, b := aVal.Pointer(), bVal.Pointer() 125 switch { 126 case a < b: 127 return -1 128 case a > b: 129 return 1 130 default: 131 return 0 132 } 133 case reflect.Chan: 134 if c, ok := nilCompare(aVal, bVal); ok { 135 return c 136 } 137 ap, bp := aVal.Pointer(), bVal.Pointer() 138 switch { 139 case ap < bp: 140 return -1 141 case ap > bp: 142 return 1 143 default: 144 return 0 145 } 146 case reflect.Struct: 147 for i := 0; i < aVal.NumField(); i++ { 148 if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 { 149 return c 150 } 151 } 152 return 0 153 case reflect.Array: 154 for i := 0; i < aVal.Len(); i++ { 155 if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 { 156 return c 157 } 158 } 159 return 0 160 case reflect.Interface: 161 if c, ok := nilCompare(aVal, bVal); ok { 162 return c 163 } 164 c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type())) 165 if c != 0 { 166 return c 167 } 168 return compare(aVal.Elem(), bVal.Elem()) 169 default: 170 // Certain types cannot appear as keys (maps, funcs, slices), but be explicit. 171 panic("bad type in compare: " + aType.String()) 172 } 173} 174 175// nilCompare checks whether either value is nil. If not, the boolean is false. 176// If either value is nil, the boolean is true and the integer is the comparison 177// value. The comparison is defined to be 0 if both are nil, otherwise the one 178// nil value compares low. Both arguments must represent a chan, func, 179// interface, map, pointer, or slice. 180func nilCompare(aVal, bVal reflect.Value) (int, bool) { 181 if aVal.IsNil() { 182 if bVal.IsNil() { 183 return 0, true 184 } 185 return -1, true 186 } 187 if bVal.IsNil() { 188 return 1, true 189 } 190 return 0, false 191} 192 193// floatCompare compares two floating-point values. NaNs compare low. 194func floatCompare(a, b float64) int { 195 switch { 196 case isNaN(a): 197 return -1 // No good answer if b is a NaN so don't bother checking. 198 case isNaN(b): 199 return 1 200 case a < b: 201 return -1 202 case a > b: 203 return 1 204 } 205 return 0 206} 207 208func isNaN(a float64) bool { 209 return a != a 210} 211