sort.go

Documentation: github.com/google/go-cmp/cmp/internal/value

     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 value
     6  
     7  import (
     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.
    16  func 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.
    36  func 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
View as plain text