This PR (HEAD: f0f560b) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/163745 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

Message from Keith Randall:

Patch Set 1:

(1 comment)

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Keith Randall:

Patch Set 1:

Patch Set 1:

(1 comment)

I think the right fix is to replace

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))

with

c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))

The former always returns 0, because we're comparing two equal interface types.

This line should be comparing the types (aka the *reflect.rtype pointers) of the concrete values stored within that interface.

The only question I have is should we be comparing *reflect.rtype, or reflect.rtype? The former seems more efficient, but could possibly vary from run to run (for reflect-allocated types). I'm not sure the contents of reflect.rtype are any better, though.

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Luke Champine:

Patch Set 1:

Patch Set 1:

Patch Set 1:

(1 comment)

I think the right fix is to replace

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))

with

c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))

The former always returns 0, because we're comparing two equal interface types.

This line should be comparing the types (aka the *reflect.rtype pointers) of the concrete values stored within that interface.

The only question I have is should we be comparing *reflect.rtype, or reflect.rtype? The former seems more efficient, but could possibly vary from run to run (for reflect-allocated types). I'm not sure the contents of reflect.rtype are any better, though.

Comparing rtype might work, since the compare will hit the size, dataptr, and hash fields first, and the hash should reliably distinguish between types with needing to do naive string comparison. I'll try that.

To answer your earlier question, here's a simple reproducer demonstrating nondeterminism: https://play.golang.org/p/h9DVPtzQ1-l

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Luke Champine:

Patch Set 1:

Patch Set 1:

Patch Set 1:

Patch Set 1:

(1 comment)

I think the right fix is to replace

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))

with

c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))

The former always returns 0, because we're comparing two equal interface types.

This line should be comparing the types (aka the *reflect.rtype pointers) of the concrete values stored within that interface.

The only question I have is should we be comparing *reflect.rtype, or reflect.rtype? The former seems more efficient, but could possibly vary from run to run (for reflect-allocated types). I'm not sure the contents of reflect.rtype are any better, though.

Comparing rtype might work, since the compare will hit the size, dataptr, and hash fields first, and the hash should reliably distinguish between types with needing to do naive string comparison. I'll try that.

To answer your earlier question, here's a simple reproducer demonstrating nondeterminism: https://play.golang.org/p/h9DVPtzQ1-l

I tried to test the address behavior of runtime types. Here are the results:

https://play.golang.org/p/kO1nRi-q541

https://play.golang.org/p/48n27SNSDq9

So for types known at compile time, the order of the declarations doesn't affect the relative addresses of the *rtypes. (This may not be true in the general case; can someone more versed in reflection confirm?) But for types constructed at runtime, the order of construction does matter. Which means that if we sort based on address, changing the order in which you construct types can change the behavior of fmtsort for those types. That seems undesirable.

Honestly, though, the amount of code in the wild that constructs new types at runtime is very small. I could only find a few examples in the standard library, and none of them actually returned those types to the caller. The worst-case scenario -- in which reordering type-construction code breaks unrelated code that depends on fmtsort -- seems highly unlikely. So I'm not opposed to comparing pointer addresses if it only breaks in this one scenario.

Personally, I favor comparing the fully-qualified type names. It doesn't suffer from the initialization order problem, and its behavior is less surprising: the developer can predict the output without needing to run the program.

Of course, even if we use names, there are many ways to accidentally break code that relies on the formatting of a map[interface{}]. Adding a field to a struct, renaming a field, or renaming an import could certainly do it. Perhaps the best we can hope for is to achieve deterministic output across multiple runs with the same input types.

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Keith Randall:

Patch Set 1:

Patch Set 1:

Patch Set 1:

Patch Set 1:

Patch Set 1:

(1 comment)

I think the right fix is to replace

c := compare(reflect.ValueOf(aType), reflect.ValueOf(bType))

with

c := compare(reflect.ValueOf(aVal.Elem().Type()), reflect.ValueOf(bVal.Elem().Type()))

The former always returns 0, because we're comparing two equal interface types.

This line should be comparing the types (aka the *reflect.rtype pointers) of the concrete values stored within that interface.

The only question I have is should we be comparing *reflect.rtype, or reflect.rtype? The former seems more efficient, but could possibly vary from run to run (for reflect-allocated types). I'm not sure the contents of reflect.rtype are any better, though.

Comparing rtype might work, since the compare will hit the size, dataptr, and hash fields first, and the hash should reliably distinguish between types with needing to do naive string comparison. I'll try that.

To answer your earlier question, here's a simple reproducer demonstrating nondeterminism: https://play.golang.org/p/h9DVPtzQ1-l

I tried to test the address behavior of runtime types. Here are the results:

https://play.golang.org/p/kO1nRi-q541

https://play.golang.org/p/48n27SNSDq9

So for types known at compile time, the order of the declarations doesn't affect the relative addresses of the *rtypes. (This may not be true in the general case; can someone more versed in reflection confirm?)

That isn't necessarily so. But the compiler and linker produce deterministic output, so given the same source code the *rtypes will all come out in the same order. I think that's all we need. If you reorder declarations in your source, then it seems ok to me that the sort order changes.

But for types constructed at runtime, the order of construction does matter. Which means that if we sort based on address, changing the order in which you construct types can change the behavior of fmtsort for those types. That seems undesirable.

Honestly, though, the amount of code in the wild that constructs new types at runtime is very small. I could only find a few examples in the standard library, and none of them actually returned those types to the caller. The worst-case scenario -- in which reordering type-construction code breaks unrelated code that depends on fmtsort -- seems highly unlikely. So I'm not opposed to comparing pointer addresses if it only breaks in this one scenario.

Personally, I favor comparing the fully-qualified type names. It doesn't suffer from the initialization order problem, and its behavior is less surprising: the developer can predict the output without needing to run the program.

Of course, even if we use names, there are many ways to accidentally break code that relies on the formatting of a map[interface{}]. Adding a field to a struct, renaming a field, or renaming an import could certainly do it. Perhaps the best we can hope for is to achieve deterministic output across multiple runs with the same input types.

I'm ok with sorting on type address. Between runs there could be nondeterminism for runtime-constructed types, but within a single run, and for compile-time types, output will be deterministic.

The only way I see to really make sorting deterministic is structural sorting of types. That would mean comparing structs field by field, etc. That seems like a lot of code for not much gain.

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

This PR (HEAD: 6884194) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/163745 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

Message from Keith Randall:

Patch Set 2:

(1 comment)

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

This PR (HEAD: 1b07f0c) has been imported to Gerrit for code review.

Please visit https://go-review.googlesource.com/c/go/+/163745 to see it.

Tip: You can toggle comments from me using the comments slash command (e.g. /comments off)
See the Wiki page for more info

Message from Luke Champine:

Patch Set 3:

(1 comment)

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Rob Pike:

Patch Set 3: Code-Review+1

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Keith Randall:

Patch Set 3: Code-Review+2

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Keith Randall:

Patch Set 3: Run-TryBot+1

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Gobot Gobot:

Patch Set 3:

TryBots beginning. Status page: https://farmer.golang.org/try?commit=6361fe09

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

Message from Gobot Gobot:

Patch Set 3: TryBot-Result+1

TryBots are happy.

Please don’t reply on this GitHub thread. Visit golang.org/cl/163745.
After addressing review feedback, remember to publish your drafts!

This PR is being closed because golang.org/cl/163745 has been merged.