// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package fmtsort provides a general stable ordering mechanism // for maps, on behalf of the fmt and text/template packages. // It is not guaranteed to be efficient and works only for types // that are valid map keys.
package fmtsort import ( ) // Note: Throughout this package we avoid calling reflect.Value.Interface as // it is not always legal to do so and it's easier to avoid the issue than to face it. // SortedMap represents a map's keys and values. The keys and values are // aligned in index order: Value[i] is the value in the map corresponding to Key[i]. type SortedMap struct { Key []reflect.Value Value []reflect.Value } func ( *SortedMap) () int { return len(.Key) } func ( *SortedMap) (, int) bool { return compare(.Key[], .Key[]) < 0 } func ( *SortedMap) (, int) { .Key[], .Key[] = .Key[], .Key[] .Value[], .Value[] = .Value[], .Value[] } // Sort accepts a map and returns a SortedMap that has the same keys and // values but in a stable sorted order according to the keys, modulo issues // raised by unorderable key values such as NaNs. // // The ordering rules are more general than with Go's < operator: // // - when applicable, nil compares low // - ints, floats, and strings order by < // - NaN compares less than non-NaN floats // - bool compares false before true // - complex compares real, then imag // - pointers compare by machine address // - channel values compare by machine address // - structs compare each field in turn // - arrays compare each element in turn. // Otherwise identical arrays compare by length. // - interface values compare first by reflect.Type describing the concrete type // and then by concrete value as described in the previous rules. // func ( reflect.Value) *SortedMap { if .Type().Kind() != reflect.Map { return nil } // Note: this code is arranged to not panic even in the presence // of a concurrent map update. The runtime is responsible for // yelling loudly if that happens. See issue 33275. := .Len() := make([]reflect.Value, 0, ) := make([]reflect.Value, 0, ) := .MapRange() for .Next() { = append(, .Key()) = append(, .Value()) } := &SortedMap{ Key: , Value: , } sort.Stable() return } // compare compares two values of the same type. It returns -1, 0, 1 // according to whether a > b (1), a == b (0), or a < b (-1). // If the types differ, it returns -1. // See the comment on Sort for the comparison rules. func compare(, reflect.Value) int { , := .Type(), .Type() if != { return -1 // No good answer possible, but don't return 0: they're not equal. } switch .Kind() { case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64: , := .Int(), .Int() switch { case < : return -1 case > : return 1 default: return 0 } case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr: , := .Uint(), .Uint() switch { case < : return -1 case > : return 1 default: return 0 } case reflect.String: , := .String(), .String() switch { case < : return -1 case > : return 1 default: return 0 } case reflect.Float32, reflect.Float64: return floatCompare(.Float(), .Float()) case reflect.Complex64, reflect.Complex128: , := .Complex(), .Complex() if := floatCompare(real(), real()); != 0 { return } return floatCompare(imag(), imag()) case reflect.Bool: , := .Bool(), .Bool() switch { case == : return 0 case : return 1 default: return -1 } case reflect.Ptr, reflect.UnsafePointer: , := .Pointer(), .Pointer() switch { case < : return -1 case > : return 1 default: return 0 } case reflect.Chan: if , := nilCompare(, ); { return } , := .Pointer(), .Pointer() switch { case < : return -1 case > : return 1 default: return 0 } case reflect.Struct: for := 0; < .NumField(); ++ { if := (.Field(), .Field()); != 0 { return } } return 0 case reflect.Array: for := 0; < .Len(); ++ { if := (.Index(), .Index()); != 0 { return } } return 0 case reflect.Interface: if , := nilCompare(, ); { return } := (reflect.ValueOf(.Elem().Type()), reflect.ValueOf(.Elem().Type())) if != 0 { return } return (.Elem(), .Elem()) default: // Certain types cannot appear as keys (maps, funcs, slices), but be explicit. panic("bad type in compare: " + .String()) } } // nilCompare checks whether either value is nil. If not, the boolean is false. // If either value is nil, the boolean is true and the integer is the comparison // value. The comparison is defined to be 0 if both are nil, otherwise the one // nil value compares low. Both arguments must represent a chan, func, // interface, map, pointer, or slice. func nilCompare(, reflect.Value) (int, bool) { if .IsNil() { if .IsNil() { return 0, true } return -1, true } if .IsNil() { return 1, true } return 0, false } // floatCompare compares two floating-point values. NaNs compare low. func floatCompare(, float64) int { switch { case isNaN(): return -1 // No good answer if b is a NaN so don't bother checking. case isNaN(): return 1 case < : return -1 case > : return 1 } return 0 } func isNaN( float64) bool { return != }