sort.go

     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  	"cmp"
    13  	"reflect"
    14  	"slices"
    15  )
    16  
    17  // Note: Throughout this package we avoid calling reflect.Value.Interface as
    18  // it is not always legal to do so and it's easier to avoid the issue than to face it.
    19  
    20  // SortedMap is a slice of KeyValue pairs that simplifies sorting
    21  // and iterating over map entries.
    22  //
    23  // Each KeyValue pair contains a map key and its corresponding value.
    24  type SortedMap []KeyValue
    25  
    26  // KeyValue holds a single key and value pair found in a map.
    27  type KeyValue struct {
    28  	Key, Value reflect.Value
    29  }
    30  
    31  // Sort accepts a map and returns a SortedMap that has the same keys and
    32  // values but in a stable sorted order according to the keys, modulo issues
    33  // raised by unorderable key values such as NaNs.
    34  //
    35  // The ordering rules are more general than with Go's < operator:
    36  //
    37  //   - when applicable, nil compares low
    38  //   - ints, floats, and strings order by <
    39  //   - NaN compares less than non-NaN floats
    40  //   - bool compares false before true
    41  //   - complex compares real, then imag
    42  //   - pointers compare by machine address
    43  //   - channel values compare by machine address
    44  //   - structs compare each field in turn
    45  //   - arrays compare each element in turn.
    46  //     Otherwise identical arrays compare by length.
    47  //   - interface values compare first by reflect.Type describing the concrete type
    48  //     and then by concrete value as described in the previous rules.
    49  func Sort(mapValue reflect.Value) SortedMap {
    50  	if mapValue.Type().Kind() != reflect.Map {
    51  		return nil
    52  	}
    53  	// Note: this code is arranged to not panic even in the presence
    54  	// of a concurrent map update. The runtime is responsible for
    55  	// yelling loudly if that happens. See issue 33275.
    56  	n := mapValue.Len()
    57  	sorted := make(SortedMap, 0, n)
    58  	iter := mapValue.MapRange()
    59  	for iter.Next() {
    60  		sorted = append(sorted, KeyValue{iter.Key(), iter.Value()})
    61  	}
    62  	slices.SortStableFunc(sorted, func(a, b KeyValue) int {
    63  		return compare(a.Key, b.Key)
    64  	})
    65  	return sorted
    66  }
    67  
    68  // compare compares two values of the same type. It returns -1, 0, 1
    69  // according to whether a > b (1), a == b (0), or a < b (-1).
    70  // If the types differ, it returns -1.
    71  // See the comment on Sort for the comparison rules.
    72  func compare(aVal, bVal reflect.Value) int {
    73  	aType, bType := aVal.Type(), bVal.Type()
    74  	if aType != bType {
    75  		return -1 // No good answer possible, but don't return 0: they're not equal.
    76  	}
    77  	switch aVal.Kind() {
    78  	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
    79  		return cmp.Compare(aVal.Int(), bVal.Int())
    80  	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
    81  		return cmp.Compare(aVal.Uint(), bVal.Uint())
    82  	case reflect.String:
    83  		return cmp.Compare(aVal.String(), bVal.String())
    84  	case reflect.Float32, reflect.Float64:
    85  		return cmp.Compare(aVal.Float(), bVal.Float())
    86  	case reflect.Complex64, reflect.Complex128:
    87  		a, b := aVal.Complex(), bVal.Complex()
    88  		if c := cmp.Compare(real(a), real(b)); c != 0 {
    89  			return c
    90  		}
    91  		return cmp.Compare(imag(a), imag(b))
    92  	case reflect.Bool:
    93  		a, b := aVal.Bool(), bVal.Bool()
    94  		switch {
    95  		case a == b:
    96  			return 0
    97  		case a:
    98  			return 1
    99  		default:
   100  			return -1
   101  		}
   102  	case reflect.Pointer, reflect.UnsafePointer:
   103  		return cmp.Compare(aVal.Pointer(), bVal.Pointer())
   104  	case reflect.Chan:
   105  		if c, ok := nilCompare(aVal, bVal); ok {
   106  			return c
   107  		}
   108  		return cmp.Compare(aVal.Pointer(), bVal.Pointer())
   109  	case reflect.Struct:
   110  		for i := 0; i < aVal.NumField(); i++ {
   111  			if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
   112  				return c
   113  			}
   114  		}
   115  		return 0
   116  	case reflect.Array:
   117  		for i := 0; i < aVal.Len(); i++ {
   118  			if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
   119  				return c
   120  			}
   121  		}
   122  		return 0
   123  	case reflect.Interface:
   124  		if c, ok := nilCompare(aVal, bVal); ok {
   125  			return c
   126  		}
   127  		c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
   128  		if c != 0 {
   129  			return c
   130  		}
   131  		return compare(aVal.Elem(), bVal.Elem())
   132  	default:
   133  		// Certain types cannot appear as keys (maps, funcs, slices), but be explicit.
   134  		panic("bad type in compare: " + aType.String())
   135  	}
   136  }
   137  
   138  // nilCompare checks whether either value is nil. If not, the boolean is false.
   139  // If either value is nil, the boolean is true and the integer is the comparison
   140  // value. The comparison is defined to be 0 if both are nil, otherwise the one
   141  // nil value compares low. Both arguments must represent a chan, func,
   142  // interface, map, pointer, or slice.
   143  func nilCompare(aVal, bVal reflect.Value) (int, bool) {
   144  	if aVal.IsNil() {
   145  		if bVal.IsNil() {
   146  			return 0, true
   147  		}
   148  		return -1, true
   149  	}
   150  	if bVal.IsNil() {
   151  		return 1, true
   152  	}
   153  	return 0, false
   154  }
   155
View as plain text