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  	"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  //
    52  func Sort(mapValue reflect.Value) *SortedMap {
    53  	if mapValue.Type().Kind() != reflect.Map {
    54  		return nil
    55  	}
    56  	// Note: this code is arranged to not panic even in the presence
    57  	// of a concurrent map update. The runtime is responsible for
    58  	// yelling loudly if that happens. See issue 33275.
    59  	n := mapValue.Len()
    60  	key := make([]reflect.Value, 0, n)
    61  	value := make([]reflect.Value, 0, n)
    62  	iter := mapValue.MapRange()
    63  	for iter.Next() {
    64  		key = append(key, iter.Key())
    65  		value = append(value, iter.Value())
    66  	}
    67  	sorted := &SortedMap{
    68  		Key:   key,
    69  		Value: value,
    70  	}
    71  	sort.Stable(sorted)
    72  	return sorted
    73  }
    74  
    75  // compare compares two values of the same type. It returns -1, 0, 1
    76  // according to whether a > b (1), a == b (0), or a < b (-1).
    77  // If the types differ, it returns -1.
    78  // See the comment on Sort for the comparison rules.
    79  func compare(aVal, bVal reflect.Value) int {
    80  	aType, bType := aVal.Type(), bVal.Type()
    81  	if aType != bType {
    82  		return -1 // No good answer possible, but don't return 0: they're not equal.
    83  	}
    84  	switch aVal.Kind() {
    85  	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
    86  		a, b := aVal.Int(), bVal.Int()
    87  		switch {
    88  		case a < b:
    89  			return -1
    90  		case a > b:
    91  			return 1
    92  		default:
    93  			return 0
    94  		}
    95  	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
    96  		a, b := aVal.Uint(), bVal.Uint()
    97  		switch {
    98  		case a < b:
    99  			return -1
   100  		case a > b:
   101  			return 1
   102  		default:
   103  			return 0
   104  		}
   105  	case reflect.String:
   106  		a, b := aVal.String(), bVal.String()
   107  		switch {
   108  		case a < b:
   109  			return -1
   110  		case a > b:
   111  			return 1
   112  		default:
   113  			return 0
   114  		}
   115  	case reflect.Float32, reflect.Float64:
   116  		return floatCompare(aVal.Float(), bVal.Float())
   117  	case reflect.Complex64, reflect.Complex128:
   118  		a, b := aVal.Complex(), bVal.Complex()
   119  		if c := floatCompare(real(a), real(b)); c != 0 {
   120  			return c
   121  		}
   122  		return floatCompare(imag(a), imag(b))
   123  	case reflect.Bool:
   124  		a, b := aVal.Bool(), bVal.Bool()
   125  		switch {
   126  		case a == b:
   127  			return 0
   128  		case a:
   129  			return 1
   130  		default:
   131  			return -1
   132  		}
   133  	case reflect.Pointer, reflect.UnsafePointer:
   134  		a, b := aVal.Pointer(), bVal.Pointer()
   135  		switch {
   136  		case a < b:
   137  			return -1
   138  		case a > b:
   139  			return 1
   140  		default:
   141  			return 0
   142  		}
   143  	case reflect.Chan:
   144  		if c, ok := nilCompare(aVal, bVal); ok {
   145  			return c
   146  		}
   147  		ap, bp := aVal.Pointer(), bVal.Pointer()
   148  		switch {
   149  		case ap < bp:
   150  			return -1
   151  		case ap > bp:
   152  			return 1
   153  		default:
   154  			return 0
   155  		}
   156  	case reflect.Struct:
   157  		for i := 0; i < aVal.NumField(); i++ {
   158  			if c := compare(aVal.Field(i), bVal.Field(i)); c != 0 {
   159  				return c
   160  			}
   161  		}
   162  		return 0
   163  	case reflect.Array:
   164  		for i := 0; i < aVal.Len(); i++ {
   165  			if c := compare(aVal.Index(i), bVal.Index(i)); c != 0 {
   166  				return c
   167  			}
   168  		}
   169  		return 0
   170  	case reflect.Interface:
   171  		if c, ok := nilCompare(aVal, bVal); ok {
   172  			return c
   173  		}
   174  		c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))
   175  		if c != 0 {
   176  			return c
   177  		}
   178  		return compare(aVal.Elem(), bVal.Elem())
   179  	default:
   180  		// Certain types cannot appear as keys (maps, funcs, slices), but be explicit.
   181  		panic("bad type in compare: " + aType.String())
   182  	}
   183  }
   184  
   185  // nilCompare checks whether either value is nil. If not, the boolean is false.
   186  // If either value is nil, the boolean is true and the integer is the comparison
   187  // value. The comparison is defined to be 0 if both are nil, otherwise the one
   188  // nil value compares low. Both arguments must represent a chan, func,
   189  // interface, map, pointer, or slice.
   190  func nilCompare(aVal, bVal reflect.Value) (int, bool) {
   191  	if aVal.IsNil() {
   192  		if bVal.IsNil() {
   193  			return 0, true
   194  		}
   195  		return -1, true
   196  	}
   197  	if bVal.IsNil() {
   198  		return 1, true
   199  	}
   200  	return 0, false
   201  }
   202  
   203  // floatCompare compares two floating-point values. NaNs compare low.
   204  func floatCompare(a, b float64) int {
   205  	switch {
   206  	case isNaN(a):
   207  		return -1 // No good answer if b is a NaN so don't bother checking.
   208  	case isNaN(b):
   209  		return 1
   210  	case a < b:
   211  		return -1
   212  	case a > b:
   213  		return 1
   214  	}
   215  	return 0
   216  }
   217  
   218  func isNaN(a float64) bool {
   219  	return a != a
   220  }
   221
View as plain text