fmt: map printing sort does not deterministically sort differing types

[lukechampine]

What version of Go are you using (go version)?

$ go version
go version go1.12 linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

fmt.Println(map[interface{}]string{
    3: "3",
    "a": "a",
    2: "2",
    "c": "c",
    1: "1",
    "b": "b"
})

What did you expect to see?

1:1 2:2 3:3 a:a b:b c:c

What did you see instead?

Non-deterministic result; differing types always compare to -1, so the result depends on map iteration, which is pseudo-random.

---

It's possible that I'm just misinterpreting the documentation here. The release notes say:

Interface values compare first by reflect.Type describing the concrete type and then by concrete value as described in the previous rules.

I read this as "values compare first lexicographically by type name, then by their concrete value." However, fmtsort.compare instead does:

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))
if c != 0 {
	return c
}

Which results in the *reflect.rtype values being compared by their machine addresses. But since a and b have the same type, their addresses will be equal (not sure if this is always the case), so this compare is ineffectual.

I think the correct code implementation would be something like:

aConcreteType := aVal.Elem().Type().String()
bConcreteType := bVal.Elem().Type().String()
c := compare(reflect.ValueOf(aConcreteType), reflect.ValueOf(bConcreteType))
if c != 0 {
	return c
}

which produces deterministic output. I'm happy to submit a pull request for this if so desired.

[odeke-em]

Thank you @lukechampine for this report!

Kindly paging @robpike @rsc @mvdan.

[mvdan]

What does text/template do in this scenario? If the template package is deterministic and fmt isn't, that's very likely a bug to fix in fmt.

[rhnvrm]

The result of go1.12 run for

package main

import (
	"os"
	"text/template"
)

func main() {
	tmpl := `{{ range $k, $v := . }}Key:{{ $k }}, Value:{{ $v }}, {{ end }}`
	t := template.New("hello")
	mp := map[interface{}]string{
		3:   "3",
		"a": "a",
		2:   "2",
		"c": "c",
		1:   "1",
		"b": "b",
	}

	tt, err := t.Parse(tmpl)
	if err != nil {
		panic(err)
	}

	if err = tt.Execute(os.Stdout, &mp); err != nil {
		panic(err)
	}
}

Key:1, Value:1, Key:2, Value:2, Key:a, Value:a, Key:b, Value:b, Key:c, Value:c, Key:3, Value:3

[gopherbot]

Change https://golang.org/cl/163745 mentions this issue: fmtsort: sort interfaces deterministically

[lukechampine]

@mvdan it looks like text/template just calls out to fmtsort:

go/src/text/template/exec.go

Lines 361 to 369 in b5a68a9

	case reflect.Map:
	if val.Len() == 0 {
	break
	}
	om := fmtsort.Sort(val)
	for i, key := range om.Key {
	oneIteration(key, om.Value[i])
	}
	return

So my proposed fix will also change the behavior of text/template.

[randall77]

@gopherbot, please open a backport issue for 1.12.

[gopherbot]

Backport issue(s) opened: #30484 (for 1.12).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.