sort.go

Documentation: github.com/rogpeppe/go-internal/fmtsort

     1  // Copyright 2018 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 fmtsort provides a general stable ordering mechanism
     6  // for maps, on behalf of the fmt and text/template packages.
     7  // It is not guaranteed to be efficient and works only for types
     8  // that are valid map keys.
     9  package fmtsort
    10  
    11  import (
    12  	"reflect"
    13  	"sort"
    14  )
    15  
    16  // Note: Throughout this package we avoid calling reflect.Value.Interface as
    17  // it is not always legal to do so and it's easier to avoid the issue than to face it.
    18  
    19  // SortedMap represents a map's keys and values. The keys and values are
    20  // aligned in index order: Value[i] is the value in the map corresponding to Key[i].
    21  type SortedMap struct {
    22  	Key   []reflect.Value
    23  	Value []reflect.Value
    24  }
    25  
    26  func (o *SortedMap) Len() int           { return len(o.Key) }
    27  func (o *SortedMap) Less(i, j int) bool { return compare(o.Key[i], o.Key[j]) < 0 }
    28  func (o *SortedMap) Swap(i, j int) {
    29  	o.Key[i], o.Key[j] = o.Key[j], o.Key[i]
    30  	o.Value[i], o.Value[j] = o.Value[j], o.Value[i]
    31  }
    32  
    33  // Sort accepts a map and returns a SortedMap that has the same keys and
    34  // values but in a stable sorted order according to the keys, modulo issues
    35  // raised by unorderable key values such as NaNs.
    36  //
    37  // The ordering rules are more general than with Go's < operator:
    38  //
    39  //   - when applicable, nil compares low
    40  //   - ints, floats, and strings order by <
    41  //   - NaN compares less than non-NaN floats
    42  //   - bool compares false before true
    43  //   - complex compares real, then imag
    44  //   - pointers compare by machine address
    45  //   - channel values compare by machine address
    46  //   - structs compare each field in turn
    47  //   - arrays compare each element in turn.
    48  //     Otherwise identical arrays compare by length.
    49  //   - interface values compare first by reflect.Type describing the concrete type
    50  //     and then by concrete value as described in the previous rules.
    51  func Sort(mapValue reflect.Value) *SortedMap {
    52  	if mapValue.Type().Kind() != reflect.Map {
    53  		return nil
    54  	}
    55  	key, value := mapElems(mapValue)
    56  	sorted := &SortedMap{
    57  		Key:   key,
    58  		Value: value,
    59  	}
    60  	sort.Stable(sorted)
    61  	return sorted
    62  }
    63  
    64  // compare compares two values of the same type. It returns -1, 0, 1
    65  // according to whether a > b (1), a == b (0), or a < b (-1).
    66  // If the types differ, it returns -1.
    67  // See the comment on Sort for the comparison rules.
    68  func compare(aVal, bVal reflect.Value) int {
    69  	aType, bType := aVal.Type(), bVal.Type()
    70  	if aType != bType {
    71  		return -1 // No good answer possible, but don't return 0: they're not equal.
    72  	}
    73  	switch aVal.Kind() {
    74  	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
    75  		a, b := aVal.Int(), bVal.Int()
    76  		switch {
    77  		case a < b:
    78  			return -1
    79  		case a > b:
    80  			return 1
    81  		default:
    82  			return 0
    83  		}
    84  	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
    85  		a, b := aVal.Uint(), bVal.Uint()
    86  		switch {
    87  		case a < b:
    88  			return -1
    89  		case a > b:
    90  			return 1
    91  		default:
    92  			return 0
    93  		}
    94  	case reflect.String:
    95  		a, b := aVal.String(), bVal.String()
    96  		switch {
    97  		case a < b:
    98  			return -1
    99  		case a > b:
   100  			return 1
   101  		default:
   102  			return 0
   103  		}
   104  	case reflect.Float32, reflect.Float64:
   105  		return floatCompare(aVal.Float(), bVal.Float())
   106  	case reflect.Complex64, reflect.Complex128:
   107  		a, b := aVal.Complex(), bVal.Complex()
   108  		if c := floatCompare(real(a), real(b)); c != 0 {
   109  			return c
   110  		}
   111  		return floatCompare(imag(a), imag(b))
   112  	case reflect.Bool:
   113  		a, b := aVal.Bool(), bVal.Bool()
   114  		switch {
   115  		case a == b:
   116  			return 0
   117  		case a:
   118  			return 1
   119  		default:
   120  			return -1
   121  		}
   122  	case reflect.Ptr:
   123  		a, b := aVal.Pointer(), bVal.Pointer()
   124  		switch {
   125  		case a < b:
   126  			return -1
   127  		case a > b:
   128  			return 1
   129  		default:
   130  			return 0
   131  		}
   132  	case reflect.Chan:
   133  		if c, ok := nilCompare(aVal, bVal); ok {
   134  			return c
   135  		}
   136  		ap, bp := aVal.Pointer(), bVal.Pointer()
   137  		switch {
   138  		case ap < bp:
   139  			return -1
   140  		case ap > bp:
   141  			return 1
   142  		default:
   143  			return 0
   144  		}
   145  	case reflect.Struct:
   146  		for i := 0; i < aVal.NumField(); i++ {
   147  			if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
   148  				return c
   149  			}
   150  		}
   151  		return 0
   152  	case reflect.Array:
   153  		for i := 0; i < aVal.Len(); i++ {
   154  			if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
   155  				return c
   156  			}
   157  		}
   158  		return 0
   159  	case reflect.Interface:
   160  		if c, ok := nilCompare(aVal, bVal); ok {
   161  			return c
   162  		}
   163  		c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
   164  		if c != 0 {
   165  			return c
   166  		}
   167  		return compare(aVal.Elem(), bVal.Elem())
   168  	default:
   169  		// Certain types cannot appear as keys (maps, funcs, slices), but be explicit.
   170  		panic("bad type in compare: " + aType.String())
   171  	}
   172  }
   173  
   174  // nilCompare checks whether either value is nil. If not, the boolean is false.
   175  // If either value is nil, the boolean is true and the integer is the comparison
   176  // value. The comparison is defined to be 0 if both are nil, otherwise the one
   177  // nil value compares low. Both arguments must represent a chan, func,
   178  // interface, map, pointer, or slice.
   179  func nilCompare(aVal, bVal reflect.Value) (int, bool) {
   180  	if aVal.IsNil() {
   181  		if bVal.IsNil() {
   182  			return 0, true
   183  		}
   184  		return -1, true
   185  	}
   186  	if bVal.IsNil() {
   187  		return 1, true
   188  	}
   189  	return 0, false
   190  }
   191  
   192  // floatCompare compares two floating-point values. NaNs compare low.
   193  func floatCompare(a, b float64) int {
   194  	switch {
   195  	case isNaN(a):
   196  		return -1 // No good answer if b is a NaN so don't bother checking.
   197  	case isNaN(b):
   198  		return 1
   199  	case a < b:
   200  		return -1
   201  	case a > b:
   202  		return 1
   203  	}
   204  	return 0
   205  }
   206  
   207  func isNaN(a float64) bool {
   208  	return a != a
   209  }
   210
View as plain text