sort.go

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