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