vendor/github.com/google/go-cmp/cmp/internal/value/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 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.Sort(valueSorter(vs))
  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 // TODO: Use sort.Slice once Google AppEngine is on Go1.8 or above.
  35 type valueSorter []reflect.Value
  36
  37 func (vs valueSorter) Len() int           { return len(vs) }
  38 func (vs valueSorter) Less(i, j int) bool { return isLess(vs[i], vs[j]) }
  39 func (vs valueSorter) Swap(i, j int)      { vs[i], vs[j] = vs[j], vs[i] }
  40
  41 // isLess is a generic function for sorting arbitrary map keys.
  42 // The inputs must be of the same type and must be comparable.
  43 func isLess(x, y reflect.Value) bool {
  44         switch x.Type().Kind() {
  45         case reflect.Bool:
  46                 return !x.Bool() && y.Bool()
  47         case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
  48                 return x.Int() < y.Int()
  49         case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
  50                 return x.Uint() < y.Uint()
  51         case reflect.Float32, reflect.Float64:
  52                 fx, fy := x.Float(), y.Float()
  53                 return fx < fy || math.IsNaN(fx) && !math.IsNaN(fy)
  54         case reflect.Complex64, reflect.Complex128:
  55                 cx, cy := x.Complex(), y.Complex()
  56                 rx, ix, ry, iy := real(cx), imag(cx), real(cy), imag(cy)
  57                 if rx == ry || (math.IsNaN(rx) && math.IsNaN(ry)) {
  58                         return ix < iy || math.IsNaN(ix) && !math.IsNaN(iy)
  59                 }
  60                 return rx < ry || math.IsNaN(rx) && !math.IsNaN(ry)
  61         case reflect.Ptr, reflect.UnsafePointer, reflect.Chan:
  62                 return x.Pointer() < y.Pointer()
  63         case reflect.String:
  64                 return x.String() < y.String()
  65         case reflect.Array:
  66                 for i := 0; i < x.Len(); i++ {
  67                         if isLess(x.Index(i), y.Index(i)) {
  68                                 return true
  69                         }
  70                         if isLess(y.Index(i), x.Index(i)) {
  71                                 return false
  72                         }
  73                 }
  74                 return false
  75         case reflect.Struct:
  76                 for i := 0; i < x.NumField(); i++ {
  77                         if isLess(x.Field(i), y.Field(i)) {
  78                                 return true
  79                         }
  80                         if isLess(y.Field(i), x.Field(i)) {
  81                                 return false
  82                         }
  83                 }
  84                 return false
  85         case reflect.Interface:
  86                 vx, vy := x.Elem(), y.Elem()
  87                 if !vx.IsValid() || !vy.IsValid() {
  88                         return !vx.IsValid() && vy.IsValid()
  89                 }
  90                 tx, ty := vx.Type(), vy.Type()
  91                 if tx == ty {
  92                         return isLess(x.Elem(), y.Elem())
  93                 }
  94                 if tx.Kind() != ty.Kind() {
  95                         return vx.Kind() < vy.Kind()
  96                 }
  97                 if tx.String() != ty.String() {
  98                         return tx.String() < ty.String()
  99                 }
 100                 if tx.PkgPath() != ty.PkgPath() {
 101                         return tx.PkgPath() < ty.PkgPath()
 102                 }
 103                 // This can happen in rare situations, so we fallback to just comparing
 104                 // the unique pointer for a reflect.Type. This guarantees deterministic
 105                 // ordering within a program, but it is obviously not stable.
 106                 return reflect.ValueOf(vx.Type()).Pointer() < reflect.ValueOf(vy.Type()).Pointer()
 107         default:
 108                 // Must be Func, Map, or Slice; which are not comparable.
 109                 panic(fmt.Sprintf("%T is not comparable", x.Type()))
 110         }
 111 }