Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fmt: map printing sort does not deterministically sort differing types #30398

Closed
lukechampine opened this issue Feb 26, 2019 · 7 comments
Closed

fmt: map printing sort does not deterministically sort differing types #30398

lukechampine opened this issue Feb 26, 2019 · 7 comments

Comments

@lukechampine
Copy link
Contributor

@lukechampine lukechampine commented Feb 26, 2019

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 odeke-em changed the title fmtsort does not deterministically sort differing types fmt: map printing sort does not deterministically sort differing types Feb 26, 2019
@odeke-em
Copy link
Member

@odeke-em odeke-em commented Feb 26, 2019

Thank you @lukechampine for this report!

Kindly paging @robpike @rsc @mvdan.

@mvdan
Copy link
Member

@mvdan mvdan commented Feb 26, 2019

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
Copy link
Contributor

@rhnvrm rhnvrm commented Feb 26, 2019

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

@ianlancetaylor ianlancetaylor added this to the Go1.12.1 milestone Feb 26, 2019
lukechampine added a commit to lukechampine/go that referenced this issue Feb 26, 2019
Previously, the result of sorting a map[interface{}] containing
multiple concrete types was non-deterministic. To ensure consistent
results, sort first by type name, then by concrete value.

Fixes golang#30398
@gopherbot
Copy link

@gopherbot gopherbot commented Feb 26, 2019

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

@lukechampine
Copy link
Contributor Author

@lukechampine lukechampine commented Feb 26, 2019

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

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.

lukechampine added a commit to lukechampine/go that referenced this issue Feb 27, 2019
Previously, the result of sorting a map[interface{}] containing
multiple concrete types was non-deterministic. To ensure consistent
results, sort first by the machine address of the value's type, then
by the value itself.

Sorting based on machine address results in unpredictable output, but
will at least be deterministic across runs of the same program.

Fixes golang#30398
lukechampine added a commit to lukechampine/go that referenced this issue Feb 28, 2019
Previously, the result of sorting a map[interface{}] containing
multiple concrete types was non-deterministic. To ensure consistent
results, sort first by the machine address of the value's type, then
by the value itself.

Sorting based on machine address results in unpredictable output, but
will at least be deterministic across runs of the same program.

Fixes golang#30398
@gopherbot gopherbot closed this in 9d40fad Feb 28, 2019
@randall77
Copy link
Contributor

@randall77 randall77 commented Feb 28, 2019

@gopherbot, please open a backport issue for 1.12.

@gopherbot
Copy link

@gopherbot gopherbot commented Feb 28, 2019

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.

@golang golang locked and limited conversation to collaborators Feb 28, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.