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	"cmp"
13	"reflect"
14	"slices"
15)
16
17// Note: Throughout this package we avoid calling reflect.Value.Interface as
18// it is not always legal to do so and it's easier to avoid the issue than to face it.
19
20// SortedMap is a slice of KeyValue pairs that simplifies sorting
21// and iterating over map entries.
22//
23// Each KeyValue pair contains a map key and its corresponding value.
24type SortedMap []KeyValue
25
26// KeyValue holds a single key and value pair found in a map.
27type KeyValue struct {
28	Key, Value reflect.Value
29}
30
31// Sort accepts a map and returns a SortedMap that has the same keys and
32// values but in a stable sorted order according to the keys, modulo issues
33// raised by unorderable key values such as NaNs.
34//
35// The ordering rules are more general than with Go's < operator:
36//
37//   - when applicable, nil compares low
38//   - ints, floats, and strings order by <
39//   - NaN compares less than non-NaN floats
40//   - bool compares false before true
41//   - complex compares real, then imag
42//   - pointers compare by machine address
43//   - channel values compare by machine address
44//   - structs compare each field in turn
45//   - arrays compare each element in turn.
46//     Otherwise identical arrays compare by length.
47//   - interface values compare first by reflect.Type describing the concrete type
48//     and then by concrete value as described in the previous rules.
49func Sort(mapValue reflect.Value) SortedMap {
50	if mapValue.Type().Kind() != reflect.Map {
51		return nil
52	}
53	// Note: this code is arranged to not panic even in the presence
54	// of a concurrent map update. The runtime is responsible for
55	// yelling loudly if that happens. See issue 33275.
56	n := mapValue.Len()
57	sorted := make(SortedMap, 0, n)
58	iter := mapValue.MapRange()
59	for iter.Next() {
60		sorted = append(sorted, KeyValue{iter.Key(), iter.Value()})
61	}
62	slices.SortStableFunc(sorted, func(a, b KeyValue) int {
63		return compare(a.Key, b.Key)
64	})
65	return sorted
66}
67
68// compare compares two values of the same type. It returns -1, 0, 1
69// according to whether a > b (1), a == b (0), or a < b (-1).
70// If the types differ, it returns -1.
71// See the comment on Sort for the comparison rules.
72func compare(aVal, bVal reflect.Value) int {
73	aType, bType := aVal.Type(), bVal.Type()
74	if aType != bType {
75		return -1 // No good answer possible, but don't return 0: they're not equal.
76	}
77	switch aVal.Kind() {
78	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
79		return cmp.Compare(aVal.Int(), bVal.Int())
80	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
81		return cmp.Compare(aVal.Uint(), bVal.Uint())
82	case reflect.String:
83		return cmp.Compare(aVal.String(), bVal.String())
84	case reflect.Float32, reflect.Float64:
85		return cmp.Compare(aVal.Float(), bVal.Float())
86	case reflect.Complex64, reflect.Complex128:
87		a, b := aVal.Complex(), bVal.Complex()
88		if c := cmp.Compare(real(a), real(b)); c != 0 {
89			return c
90		}
91		return cmp.Compare(imag(a), imag(b))
92	case reflect.Bool:
93		a, b := aVal.Bool(), bVal.Bool()
94		switch {
95		case a == b:
96			return 0
97		case a:
98			return 1
99		default:
100			return -1
101		}
102	case reflect.Pointer, reflect.UnsafePointer:
103		return cmp.Compare(aVal.Pointer(), bVal.Pointer())
104	case reflect.Chan:
105		if c, ok := nilCompare(aVal, bVal); ok {
106			return c
107		}
108		return cmp.Compare(aVal.Pointer(), bVal.Pointer())
109	case reflect.Struct:
110		for i := 0; i < aVal.NumField(); i++ {
111			if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
112				return c
113			}
114		}
115		return 0
116	case reflect.Array:
117		for i := 0; i < aVal.Len(); i++ {
118			if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
119				return c
120			}
121		}
122		return 0
123	case reflect.Interface:
124		if c, ok := nilCompare(aVal, bVal); ok {
125			return c
126		}
127		c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
128		if c != 0 {
129			return c
130		}
131		return compare(aVal.Elem(), bVal.Elem())
132	default:
133		// Certain types cannot appear as keys (maps, funcs, slices), but be explicit.
134		panic("bad type in compare: " + aType.String())
135	}
136}
137
138// nilCompare checks whether either value is nil. If not, the boolean is false.
139// If either value is nil, the boolean is true and the integer is the comparison
140// value. The comparison is defined to be 0 if both are nil, otherwise the one
141// nil value compares low. Both arguments must represent a chan, func,
142// interface, map, pointer, or slice.
143func nilCompare(aVal, bVal reflect.Value) (int, bool) {
144	if aVal.IsNil() {
145		if bVal.IsNil() {
146			return 0, true
147		}
148		return -1, true
149	}
150	if bVal.IsNil() {
151		return 1, true
152	}
153	return 0, false
154}
155