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: maps should format in sorted order #21095

Closed
purpleidea opened this issue Jul 20, 2017 · 33 comments
Closed

fmt: maps should format in sorted order #21095

purpleidea opened this issue Jul 20, 2017 · 33 comments

Comments

@purpleidea
Copy link

@purpleidea purpleidea commented Jul 20, 2017

Please answer these questions before submitting your issue. Thanks!

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

go version go1.8.1 linux/amd64

What operating system and processor architecture are you using (go env)?

GOARCH="amd64"
GOHOSTOS="linux"
GCCGO="gccgo"
CC="gcc"

What did you do?

I ran the attached playground link.

https://play.golang.org/p/EjvBekU87U

What did you expect to see?

I expect the displayed map output to be deterministic.

What did you see instead?

It changes randomly.

I understand that map randomizes the key order, and I actually think this is a cool implementation feature, however I think the displayed text output should be deterministic. It could display by sorted key order for example.

This will make diff-ing logs, and viewing output more consistent, with less flip-flop.

Thanks,
James

@bradfitz bradfitz changed the title map *display* should be deterministic fmt: map should format in sorted order Jul 20, 2017
@bradfitz bradfitz changed the title fmt: map should format in sorted order fmt: mapsshould format in sorted order Jul 20, 2017
@bradfitz bradfitz changed the title fmt: mapsshould format in sorted order fmt: maps should format in sorted order Jul 20, 2017
@bradfitz bradfitz added the Proposal label Jul 20, 2017
@martisch
Copy link
Contributor

@martisch martisch commented Jul 20, 2017

Observation: Even with sorting we will not always get stable output. e.g. NaNs will always be in some random order and sorting them will not help.

If stable output is needed one could dump and sort the map outside of fmt and then output the result. Making fmt always sort the map will always incur time and allocation overhead that can not be avoided even if unstable output is fine.

Maybe we can add a special modifier that will try to make output as stable as possible for printing maps instead of modifying the default unordered behaviour.

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 20, 2017

@martisch Can you elaborate on your NaN comment with an example please?

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 20, 2017

@martisch

If stable output is needed one could dump and sort the map outside of fmt and then output the result.

Actually, this is not possible because golang string representation values are unfortunately not unique. For example look at this map value:

map[answer:42 hello:13]

Is this a map with keys answer & hello which are both ints?
OR
Is it a map with one key named answer which has string: 42 hello:13 ?

They display the same.

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 20, 2017

@martisch

Making fmt always sort the map will always incur time and allocation overhead

You're making the assumption, you didn't test or profile this. Since it would only come out when folks did a fmt: %+v then I don't think it will affect anyone negatively.

@randall77
Copy link
Contributor

@randall77 randall77 commented Jul 20, 2017

Sorting the keys presupposes there is a sort order on the keys. For complicated keys like

struct {
   x int16
   y float64
   z interface{}
   p *int
}

It's not clear how to sort them. Floats don't always sort correctly, and how do you look inside interfaces to sort them?
The obvious sort order for pointers may not be stable across executions of your program.
So, it's complicated. Simple cases like string or int keys may sound tempting, but doing this in general is hard. Maybe not impossible, but I'm not convinced it would be worth the trouble.

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 20, 2017

@cznic
Copy link
Contributor

@cznic cznic commented Jul 20, 2017

Map keys are guaranteed to be comparable, but they're not guaranteed to be ordered - sorting them is not even possible in the general case.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Jul 20, 2017

I've had a long day so maybe I'm missing something

https://play.golang.org/p/RYac90kI-H

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 20, 2017

@martisch
Copy link
Contributor

@martisch martisch commented Jul 20, 2017

Can you elaborate on your NaN comment with an example please?

NaNs can not be ordered and we only get them back random from ranging over a map. So sorting them afterwards we will not get a stable output across calls unless the map itself provides a mechanism to return key, values in stable order.

Actually, this is not possible because golang string representation values are unfortunately not unique.

I did not mean to suggest to sort the string representation but to sort the a slice constructed by collecting all key,value pairs in a slice using the range statement over a map.

You're making the assumption, you didn't test or profile this. Since it would only come out when folks did a fmt: %+v then I don't think it will affect anyone negatively.

I did not know your proposal was to only have ordered output for %+v as the proposal or example did not mention it. Println uses the %v internally. Note that using + also affect how keys and values will be printed for the map and always adds field names.

@martisch
Copy link
Contributor

@martisch martisch commented Jul 20, 2017

Added a correction in previous comment where i confused +v with regular + modifier.

@ericlagergren
Copy link
Contributor

@ericlagergren ericlagergren commented Jul 20, 2017

alternatively: have your map type implement fmt.Formatter

@robpike
Copy link
Contributor

@robpike robpike commented Jul 21, 2017

As observed, if you want your map to print a certain way, you can make that happen with Stringer or Formatter. That is, if you care about the format, you should care enough to write the code to control the format, which will be specific to your problem and not generally applicable. In general what you ask is otherwise impossible.

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 21, 2017

@robpike Isn't making this generally more useful for everyone in a single place (upstream) preferable to having everyone hit this? Making things "batteries included" in this scenario is positive for the language IMO.

Thanks

@robpike
Copy link
Contributor

@robpike robpike commented Jul 21, 2017

@purpleidea Except it can't be done!

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 21, 2017

@ericlagergren
Copy link
Contributor

@ericlagergren ericlagergren commented Jul 21, 2017

I can only recall one time I've ever needed a map to print in a specific order, and it was during a test and a for loop took care of that problem.

Adding non-deterministic printing to fmt seems a bit overkill for a very specific problem that few users encounter, no?

@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jul 21, 2017

@ericlagergren
Copy link
Contributor

@ericlagergren ericlagergren commented Jul 21, 2017

but it's consistently non-deterministic :-)

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Jul 21, 2017

It we really wanted to, we could define that the sorting is based on the stringified output of the map keys & values. That is, we can already stringify everything (that's what fmt does, even regardless of implementing Formatter), and we can already sort strings, so we could do this if we wanted. It sounds like we don't want to.

@dsnet dsnet added this to the Unplanned milestone Sep 1, 2017
@mvdan mvdan modified the milestones: Unplanned, Proposal May 31, 2018
@mvdan
Copy link
Member

@mvdan mvdan commented May 31, 2018

I'm milestoning this as Proposal in the hopes that the proposal review group will make a decision on it soon. It seems to me like there's a decent amount of consensus, anyway.

Speaking of which, I didn't know that issues could have the proposal label, but not the proposal milestone. I've been trying to search what that means on the wiki, but haven't been successful. I assume it means something like "in between NeedsDecision and a full Proposal".

@bradfitz bradfitz changed the title fmt: maps should format in sorted order proposal: fmt: maps should format in sorted order May 31, 2018
@robpike
Copy link
Contributor

@robpike robpike commented Jun 1, 2018

I think this should not be done by fmt. First, a precise complete definition is either unspecifiable or too complex and expensive, like generating the individual strings and then sorting those. Second, as written above, people who really care about printing their maps will probably write their own String method anyway. Third, the right sort will depend on the user's own preferences, which argues for a variety of implementations, not one canonical one. And finally, who prints maps raw anyway? The format is suitable only for debugging.

So write an external package that solves the problem for you and call fmt.Print(myformatter.Map(m)).

@rsc
Copy link
Contributor

@rsc rsc commented Jun 4, 2018

We discussed this at proposal review and it seems like maybe we should consider a rule that fmt displays maps sorted by key when the key is a Go type for which the Go < operator is defined (basic types except bool and complex). We understand that this applies essentially only when debugging, but that's exactly when you might want a little extra help, and the extra work is limited. From a dependency point of view, sort is lower in the hierarchy than fmt. In practice there's already a []reflect.Value pulled from the map, so there would be four possible sorts: by v.String, v.Int, v.Uint, or v.Float64 (or not at all).

/cc @robpike

@robpike
Copy link
Contributor

@robpike robpike commented Jun 4, 2018

I think that will just lead to people wanting more control over the formatting. I strongly prefer just leaving things alone.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Jul 9, 2018

FWIW, I'd still like to see this done (and sorting by the stringified form as a fallback when otherwise tricky).

@rsc
Copy link
Contributor

@rsc rsc commented Jul 10, 2018

@robpike and I talked about this. We realized that text/template already does exactly what I proposed above (order by < operator when available, leave alone otherwise). But probably it is reasonable to finish the job and just define an order on all comparable types for purposes of printing, and then make fmt and text/template both use it, perhaps in a shared internal package. Defining a complete sort order for printing might be something like:

  • ints, floats, and strings sort by <
    • special case: NaN less than non-NaN floats
  • bool sorts false before true
  • complex sorts on real, then imag
  • pointers sort by machine address
  • channel values sort by machine address
  • struct sorts on each field in turn
  • array sorts on each element in turn
  • interface values sort first by reflect.Type describing the concrete type and then within type by value as described in the previous rules

I don't know what "sort by reflect.Type" means. Maybe PkgPath, Name, String, and finally underlying pointer value. That's not perfect but it's probably good enough.

@robpike will look into this for Go 1.12.

@rsc rsc modified the milestones: Proposal, Go1.12 Jul 10, 2018
@rsc rsc changed the title proposal: fmt: maps should format in sorted order fmt: maps should format in sorted order Jul 10, 2018
@gopherbot
Copy link

@gopherbot gopherbot commented Oct 16, 2018

Change https://golang.org/cl/142737 mentions this issue: fmt: print maps in key-sorted order

@gopherbot gopherbot closed this in a440cc0 Oct 18, 2018
@gopherbot
Copy link

@gopherbot gopherbot commented Oct 19, 2018

Change https://golang.org/cl/143178 mentions this issue: text/template: drop unused sortKeys function

gopherbot pushed a commit that referenced this issue Oct 19, 2018
Recent change golang.org/cl/142737 drops the only call site for the
sortKeys function. If it's not in use, it should probably not be there in
the code, lurking and preparing to bite us when someone calls that instead
of the new key sorter in fmtsort, resulting in strange inconsistencies.

Since the function isn't called, this should have no impact.
Related to, but does not fix, #21095.

Change-Id: I4695503ef4d5ce90d989ec952f01ea00cc15c79d
Reviewed-on: https://go-review.googlesource.com/c/143178
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
wking added a commit to wking/go-log that referenced this issue Nov 12, 2018
The PreNest marker allows us to drop the empty-string delimiters from
library callers and still get readable output from fmt.Print-style
renderers.  I've added a new unit test showing that log
implementations that want to detect Markers should use
reflect.DeepEqual or something else that is stricter than ==.

I've also adjusted the expected order of keys in the unit-test map.
Currently this output is unstable, but [1,2,3] will have the order
stabilized in future Go releases.  The change here sets us up for
compatibility with that new logic.

I've also made the Newf and Logf implementations more compact by
turning them into wrappers around New and Log respectively.

[1]: https://go-review.googlesource.com/c/go/+/142737/
[2]: golang/go@a440cc0
[3]: golang/go#21095
@DeedleFake
Copy link

@DeedleFake DeedleFake commented Dec 17, 2018

Would it be possible to get this sorting behavior exposed somewhere, maybe as reflect.Less(v1, v2 interface{}) bool for parity with reflect.DeepEqual()? Could also use it to build a reflect.Lesser() to work with reflect.Swapper().

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Dec 17, 2018

@DeedleFake That should be a separate proposal, this one is closed.

I tend to think that exposing the comparison function would be an attractive nuisance. In particular it doesn't sort pointer values reliably across executions of the same program, and it doesn't sort slices at all.

@robpike
Copy link
Contributor

@robpike robpike commented Dec 18, 2018

@DeedleFake I agree with @ianlancetaylor. It was a deliberate decision to keep this implementation private; the phrase 'attractive nuisance' is good. The code is not fast (it's very hard to do well) and not general (there are cases such as Ian mentioned). Making it more generally available will result in pushback on those problems, which are really not worth worrying about.

@montanaflynn
Copy link

@montanaflynn montanaflynn commented Jan 16, 2019

Looks like this will be added in Go 1.12:

Maps are now printed in key-sorted order to ease testing. ...

https://tip.golang.org/doc/go1.12#fmt

This will be especially useful for writing Example style tests:

func ExampleCounts() {
	d := []float64{1, 2, 3, 4, 4, 4, 4}
	c := Counts(d)
	fmt.Println(c)
	// Output: map[1:2 2:1 3:1 4:4]
}
@purpleidea
Copy link
Author

@purpleidea purpleidea commented Jan 16, 2019

\o/

I guess it was a good idea after all ;)

@golang golang locked and limited conversation to collaborators Jan 16, 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
You can’t perform that action at this time.