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 cmpopts
6
7import (
8	"fmt"
9	"reflect"
10	"sort"
11
12	"github.com/google/go-cmp/cmp"
13	"github.com/google/go-cmp/cmp/internal/function"
14)
15
16// SortSlices returns a Transformer option that sorts all []V.
17// The less function must be of the form "func(T, T) bool" which is used to
18// sort any slice with element type V that is assignable to T.
19//
20// The less function must be:
21//	• Deterministic: less(x, y) == less(x, y)
22//	• Irreflexive: !less(x, x)
23//	• Transitive: if !less(x, y) and !less(y, z), then !less(x, z)
24//
25// The less function does not have to be "total". That is, if !less(x, y) and
26// !less(y, x) for two elements x and y, their relative order is maintained.
27//
28// SortSlices can be used in conjunction with EquateEmpty.
29func SortSlices(lessFunc interface{}) cmp.Option {
30	vf := reflect.ValueOf(lessFunc)
31	if !function.IsType(vf.Type(), function.Less) || vf.IsNil() {
32		panic(fmt.Sprintf("invalid less function: %T", lessFunc))
33	}
34	ss := sliceSorter{vf.Type().In(0), vf}
35	return cmp.FilterValues(ss.filter, cmp.Transformer("cmpopts.SortSlices", ss.sort))
36}
37
38type sliceSorter struct {
39	in  reflect.Type  // T
40	fnc reflect.Value // func(T, T) bool
41}
42
43func (ss sliceSorter) filter(x, y interface{}) bool {
44	vx, vy := reflect.ValueOf(x), reflect.ValueOf(y)
45	if !(x != nil && y != nil && vx.Type() == vy.Type()) ||
46		!(vx.Kind() == reflect.Slice && vx.Type().Elem().AssignableTo(ss.in)) ||
47		(vx.Len() <= 1 && vy.Len() <= 1) {
48		return false
49	}
50	// Check whether the slices are already sorted to avoid an infinite
51	// recursion cycle applying the same transform to itself.
52	ok1 := sort.SliceIsSorted(x, func(i, j int) bool { return ss.less(vx, i, j) })
53	ok2 := sort.SliceIsSorted(y, func(i, j int) bool { return ss.less(vy, i, j) })
54	return !ok1 || !ok2
55}
56func (ss sliceSorter) sort(x interface{}) interface{} {
57	src := reflect.ValueOf(x)
58	dst := reflect.MakeSlice(src.Type(), src.Len(), src.Len())
59	for i := 0; i < src.Len(); i++ {
60		dst.Index(i).Set(src.Index(i))
61	}
62	sort.SliceStable(dst.Interface(), func(i, j int) bool { return ss.less(dst, i, j) })
63	ss.checkSort(dst)
64	return dst.Interface()
65}
66func (ss sliceSorter) checkSort(v reflect.Value) {
67	start := -1 // Start of a sequence of equal elements.
68	for i := 1; i < v.Len(); i++ {
69		if ss.less(v, i-1, i) {
70			// Check that first and last elements in v[start:i] are equal.
71			if start >= 0 && (ss.less(v, start, i-1) || ss.less(v, i-1, start)) {
72				panic(fmt.Sprintf("incomparable values detected: want equal elements: %v", v.Slice(start, i)))
73			}
74			start = -1
75		} else if start == -1 {
76			start = i
77		}
78	}
79}
80func (ss sliceSorter) less(v reflect.Value, i, j int) bool {
81	vx, vy := v.Index(i), v.Index(j)
82	return ss.fnc.Call([]reflect.Value{vx, vy})[0].Bool()
83}
84
85// SortMaps returns a Transformer option that flattens map[K]V types to be a
86// sorted []struct{K, V}. The less function must be of the form
87// "func(T, T) bool" which is used to sort any map with key K that is
88// assignable to T.
89//
90// Flattening the map into a slice has the property that cmp.Equal is able to
91// use Comparers on K or the K.Equal method if it exists.
92//
93// The less function must be:
94//	• Deterministic: less(x, y) == less(x, y)
95//	• Irreflexive: !less(x, x)
96//	• Transitive: if !less(x, y) and !less(y, z), then !less(x, z)
97//	• Total: if x != y, then either less(x, y) or less(y, x)
98//
99// SortMaps can be used in conjunction with EquateEmpty.
100func SortMaps(lessFunc interface{}) cmp.Option {
101	vf := reflect.ValueOf(lessFunc)
102	if !function.IsType(vf.Type(), function.Less) || vf.IsNil() {
103		panic(fmt.Sprintf("invalid less function: %T", lessFunc))
104	}
105	ms := mapSorter{vf.Type().In(0), vf}
106	return cmp.FilterValues(ms.filter, cmp.Transformer("cmpopts.SortMaps", ms.sort))
107}
108
109type mapSorter struct {
110	in  reflect.Type  // T
111	fnc reflect.Value // func(T, T) bool
112}
113
114func (ms mapSorter) filter(x, y interface{}) bool {
115	vx, vy := reflect.ValueOf(x), reflect.ValueOf(y)
116	return (x != nil && y != nil && vx.Type() == vy.Type()) &&
117		(vx.Kind() == reflect.Map && vx.Type().Key().AssignableTo(ms.in)) &&
118		(vx.Len() != 0 || vy.Len() != 0)
119}
120func (ms mapSorter) sort(x interface{}) interface{} {
121	src := reflect.ValueOf(x)
122	outType := reflect.StructOf([]reflect.StructField{
123		{Name: "K", Type: src.Type().Key()},
124		{Name: "V", Type: src.Type().Elem()},
125	})
126	dst := reflect.MakeSlice(reflect.SliceOf(outType), src.Len(), src.Len())
127	for i, k := range src.MapKeys() {
128		v := reflect.New(outType).Elem()
129		v.Field(0).Set(k)
130		v.Field(1).Set(src.MapIndex(k))
131		dst.Index(i).Set(v)
132	}
133	sort.Slice(dst.Interface(), func(i, j int) bool { return ms.less(dst, i, j) })
134	ms.checkSort(dst)
135	return dst.Interface()
136}
137func (ms mapSorter) checkSort(v reflect.Value) {
138	for i := 1; i < v.Len(); i++ {
139		if !ms.less(v, i-1, i) {
140			panic(fmt.Sprintf("partial order detected: want %v < %v", v.Index(i-1), v.Index(i)))
141		}
142	}
143}
144func (ms mapSorter) less(v reflect.Value, i, j int) bool {
145	vx, vy := v.Index(i).Field(0), v.Index(j).Field(0)
146	return ms.fnc.Call([]reflect.Value{vx, vy})[0].Bool()
147}
148