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