sort.go

Documentation: github.com/google/go-cmp/cmp/cmpopts

     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  
     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 [cmp.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 [cmp.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 [cmp.Comparer] options 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  }
   148
View as plain text