.config/coc/extensions/coc-go-data/tools/pkg/mod/github.com/google/go-cmp@v0.5.1/cmp/cmpopts/sort.go

   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.md file.
   4
   5 package cmpopts
   6
   7 import (
   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.
  29 func 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
  38 type sliceSorter struct {
  39         in  reflect.Type  // T
  40         fnc reflect.Value // func(T, T) bool
  41 }
  42
  43 func (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 }
  56 func (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 }
  66 func (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 }
  80 func (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.
 100 func 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
 109 type mapSorter struct {
 110         in  reflect.Type  // T
 111         fnc reflect.Value // func(T, T) bool
 112 }
 113
 114 func (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 }
 120 func (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 }
 137 func (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 }
 144 func (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 }