1// Copyright 2017, 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
5package value
6
7import (
8	"fmt"
9	"math"
10	"reflect"
11	"sort"
12)
13
14// SortKeys sorts a list of map keys, deduplicating keys if necessary.
15// The type of each value must be comparable.
16func SortKeys(vs []reflect.Value) []reflect.Value {
17	if len(vs) == 0 {
18		return vs
19	}
20
21	// Sort the map keys.
22	sort.SliceStable(vs, func(i, j int) bool { return isLess(vs[i], vs[j]) })
23
24	// Deduplicate keys (fails for NaNs).
25	vs2 := vs[:1]
26	for _, v := range vs[1:] {
27		if isLess(vs2[len(vs2)-1], v) {
28			vs2 = append(vs2, v)
29		}
30	}
31	return vs2
32}
33
34// isLess is a generic function for sorting arbitrary map keys.
35// The inputs must be of the same type and must be comparable.
36func isLess(x, y reflect.Value) bool {
37	switch x.Type().Kind() {
38	case reflect.Bool:
39		return !x.Bool() && y.Bool()
40	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
41		return x.Int() < y.Int()
42	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
43		return x.Uint() < y.Uint()
44	case reflect.Float32, reflect.Float64:
45		// NOTE: This does not sort -0 as less than +0
46		// since Go maps treat -0 and +0 as equal keys.
47		fx, fy := x.Float(), y.Float()
48		return fx < fy || math.IsNaN(fx) && !math.IsNaN(fy)
49	case reflect.Complex64, reflect.Complex128:
50		cx, cy := x.Complex(), y.Complex()
51		rx, ix, ry, iy := real(cx), imag(cx), real(cy), imag(cy)
52		if rx == ry || (math.IsNaN(rx) && math.IsNaN(ry)) {
53			return ix < iy || math.IsNaN(ix) && !math.IsNaN(iy)
54		}
55		return rx < ry || math.IsNaN(rx) && !math.IsNaN(ry)
56	case reflect.Ptr, reflect.UnsafePointer, reflect.Chan:
57		return x.Pointer() < y.Pointer()
58	case reflect.String:
59		return x.String() < y.String()
60	case reflect.Array:
61		for i := 0; i < x.Len(); i++ {
62			if isLess(x.Index(i), y.Index(i)) {
63				return true
64			}
65			if isLess(y.Index(i), x.Index(i)) {
66				return false
67			}
68		}
69		return false
70	case reflect.Struct:
71		for i := 0; i < x.NumField(); i++ {
72			if isLess(x.Field(i), y.Field(i)) {
73				return true
74			}
75			if isLess(y.Field(i), x.Field(i)) {
76				return false
77			}
78		}
79		return false
80	case reflect.Interface:
81		vx, vy := x.Elem(), y.Elem()
82		if !vx.IsValid() || !vy.IsValid() {
83			return !vx.IsValid() && vy.IsValid()
84		}
85		tx, ty := vx.Type(), vy.Type()
86		if tx == ty {
87			return isLess(x.Elem(), y.Elem())
88		}
89		if tx.Kind() != ty.Kind() {
90			return vx.Kind() < vy.Kind()
91		}
92		if tx.String() != ty.String() {
93			return tx.String() < ty.String()
94		}
95		if tx.PkgPath() != ty.PkgPath() {
96			return tx.PkgPath() < ty.PkgPath()
97		}
98		// This can happen in rare situations, so we fallback to just comparing
99		// the unique pointer for a reflect.Type. This guarantees deterministic
100		// ordering within a program, but it is obviously not stable.
101		return reflect.ValueOf(vx.Type()).Pointer() < reflect.ValueOf(vy.Type()).Pointer()
102	default:
103		// Must be Func, Map, or Slice; which are not comparable.
104		panic(fmt.Sprintf("%T is not comparable", x.Type()))
105	}
106}
107