fmt: print maps in key-sorted order

For easier testing, change the way maps are printed so they
appear in a consistent order between runs. Do this by printing
them in key-sorted order.

To do this, we add a package at the root, internal/fmtsort,
that implements a general mechanism for sorting map keys
regardless of their type. This is a little messy and probably
slow, but formatted printing of maps has never been fast and
is already always reflection-driven.

The rules are:

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.
 - interface values compare first by reflect.Type describing the concrete type
   and then by concrete value as described in the previous rules.

The new package is internal because we really do not want
everyone using this to sort things. It is slow, not general, and
only suitable for the subset of types that can be map keys.

Also use the package in text/template, which already had a
weaker version of this mechanism.

This change requires adding a dependency on sort to the fmt
package, but that isn't disruptive to the dependency tree.

Fixes #21095

Change-Id: Ia602115c7de5d95993dbd609611d8bd96e054157
Reviewed-on: https://go-review.googlesource.com/c/142737
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>

1 files changed, 5 insertions, 4 deletions

diff --git a/src/fmt/print.go b/src/fmt/print.go
index 32743d0712..22dc52ccdc 100644
--- a/src/fmt/print.go
+++ b/src/fmt/print.go
@@ -6,6 +6,7 @@ package fmt
 
 import (
 	"errors"
+	"internal/fmtsort"
 	"io"
 	"os"
 	"reflect"
@@ -753,8 +754,8 @@ func (p *pp) printValue(value reflect.Value, verb rune, depth int) {
 		} else {
 			p.buf.WriteString(mapString)
 		}
-		iter := f.MapRange()
-		for i := 0; iter.Next(); i++ {
+		sorted := fmtsort.Sort(f)
+		for i, key := range sorted.Key {
 			if i > 0 {
 				if p.fmt.sharpV {
 					p.buf.WriteString(commaSpaceString)
@@ -762,9 +763,9 @@ func (p *pp) printValue(value reflect.Value, verb rune, depth int) {
 					p.buf.WriteByte(' ')
 				}
 			}
-			p.printValue(iter.Key(), verb, depth+1)
+			p.printValue(key, verb, depth+1)
 			p.buf.WriteByte(':')
-			p.printValue(iter.Value(), verb, depth+1)
+			p.printValue(sorted.Value[i], verb, depth+1)
 		}
 		if p.fmt.sharpV {
 			p.buf.WriteByte('}')