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