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

spec: define that structs are compared field-by-field as listed in source code #8606

Closed
mdempsky opened this issue Aug 28, 2014 · 54 comments · Fixed by ferrmin/go#516
Closed

Comments

@mdempsky
Copy link
Member

gc handles struct/array comparisons by short-circuiting if it finds any unequal
fields/elements, and this behavior is noticeable because the Go spec requires
comparisons to panic in some cases; e.g., see http://play.golang.org/p/5jqSUAT1xC

However, unlike short-circuiting for evaluating "a && b", it doesn't
seem that short-circuiting of field/element comparisons is specified by the spec. 
Arguably, the spec currently requires that instead both comparisons in the above program
should panic.

Not a major issue, but thought I'd file an issue to note it.  A couple possible ways to
address it:

1. Ignore it since it probably doesn't matter in practice.
2. Specify gc's behavior since it's intuitive and easy to explain.
3. Specify a set of allowable behaviors (e.g., allow short-circuiting or not; and/or
allow any particular ordering for element/field comparisons).
4. Change gc to not (visibly) short-circuit comparisons that involve comparing interface
types; e.g., comparing two [512]int arrays can still short-circuit, but comparing two
struct{a int; b, c interface{}; d int} structs would need to always compare the b and c
fields, and a and d could be compared conditionally.
@ianlancetaylor
Copy link
Contributor

Comment 1:

Labels changed: added repo-main, release-none.

@griesemer
Copy link
Contributor

Comment 2:

Labels changed: added documentation.

Owner changed to @griesemer.

Status changed to Accepted.

@bradfitz
Copy link
Contributor

@griesemer, @ianlancetaylor, I closed #38676 as a duplicate of this one but it'd be nice to get a decision here for https://go-review.googlesource.com/c/go/+/230207 ("cmd/compile: improve generated eq algs for structs containing interfaces").

/cc @josharian @mdempsky @randall77

@mdempsky
Copy link
Member Author

I'm inclined to say the spec should explicitly say the order of field/element comparison is unspecified, and a struct/array with both unequal and incomparable fields/elements may either compare false or panic.

I'd say go ahead with CL 230207.

@ianlancetaylor
Copy link
Contributor

I agree with @mdempsky.

If we ever decide to implement more struct order of evaluation, this would be another place where we ought to specify the order.

@josharian
Copy link
Contributor

If we go that route (which I support), and we wanted to prevent people from accidentally relying on short-circuiting behavior, we could generate always-panic implementations in -race mode (or under a new flag).

@griesemer
Copy link
Contributor

I'd also agree with @mdempsky.

More generally, a principle I like is to assume that anything that is not explicitly defined by the language spec is in is in fact unspecified even if we don't say so explicitly, and thus should no be relied upon.

@go101
Copy link

go101 commented Apr 27, 2020

Isn't one of the goals of Go is to reduce unspecified cases as few as possible?

@griesemer
Copy link
Contributor

We want to reduce dependence on unspecified behavior as much as possible. That is not quite the same as saying something is unspecified in the spec.

(For instance, map iteration order is not specified, and by making it random, people cannot rely upon some implementation-dependent iteration order.)

@ianlancetaylor
Copy link
Contributor

I would not say that it is a goal of Go to reduce unspecified cases as much as possible. I don't think we're opposed to reducing unspecified cases, but it's not a goal.

If reducing unspecified cases were a goal we would have exact rules of order of evaluation, exact rules for map iteration, etc.

@josharian
Copy link
Contributor

If we go that route (which I support), and we wanted to prevent people from accidentally relying on short-circuiting behavior, we could generate always-panic implementations in -race mode (or under a new flag).

I started implementing this and it got complicated and ugly, so I stopped. If folks actively want it, I can try again. Otherwise, I'm going to throw in the hat.

@go101
Copy link

go101 commented Apr 28, 2020

@griesemer @ianlancetaylor
I understand there are some good reasons of why map iteration orders and expression evaluation orders in some statements are unspecified. But are there any obstacles and disadvantages to keep the current implementation (by field and element orders)?

@mdempsky
Copy link
Member Author

But are there any obstacles and disadvantages to keep the current implementation (by field and element orders)?

The immediate one is it would prevent optimization CLs like 230207, which users seem more likely to benefit from than to be harmed by it.

More generally, we reserve the right to make changes in behavior as long as they still conform to the language spec.

@go101
Copy link

go101 commented Apr 28, 2020

OK, get it. But I think, from general user point view, predicable behaviors would be better.

@ianlancetaylor
Copy link
Contributor

Some users want predictable behavior, some users want faster code. We have to make our best guess as to which is most important for each specific case.

@rsc
Copy link
Contributor

rsc commented May 6, 2020

The spec says that structs are equal if all the fields are equal. It also says
"A comparison of two interface values with identical dynamic types causes a run-time panic if values of that type are not comparable."
This doesn't sound ambiguous to me: it sounds like the panic is required.

We could relax the rules and say the panic may or may not happen depending on other struct field values, but if we did that, different implementations would behave differently. Moving code from one system to another might mean a panic appears where it never did before, making people think the new system has a bug.

The spec doesn't say what order fields are compared, but it implies that they are all compared. If there are two different interface fields that cause panics in a particular comparison, it doesn't matter much which one happens, but one has to happen (not zero).

A compiler that wants to short-circuit field comparisons just has to do all the interfaces before it starts being clever.

Moving into proposal process to make sure discussion terminates.

@rsc rsc changed the title spec: ambiguity in comparing array/structs with interface fields/elements proposal: spec: decide ambiguity in comparing array/structs with interface fields/elements May 6, 2020
@rsc rsc removed the Documentation label May 6, 2020
@randall77
Copy link
Contributor

I can't get any ordering violations with CL 230207 reapplied.
No hurry, we can reapply if it is safe for 1.16.

@josharian
Copy link
Contributor

OK. Are you using structs with > 4 fields? That might be necessary, since we inline “small” comparisons, and that goes through a different code generation path. (I recently filed an issue to unify them, but can’t find it on my phone.)

@martisch
Copy link
Contributor

martisch commented Jun 5, 2020

(I recently filed an issue to unify them, but can’t find it on my phone.)

cmd/compile: unify and improve struct/array equality comparisons #38674

@rsc rsc changed the title proposal: spec: decide ambiguity in comparing array/structs with interface fields/elements proposal: spec: define that structs are compared field-by-field as listed in source code Jun 10, 2020
@rsc
Copy link
Contributor

rsc commented Jun 10, 2020

Retitled.
No change in consensus, so accepted.

@rsc rsc moved this from Likely Accept to Accepted in Proposals (old) Jun 10, 2020
@mdempsky
Copy link
Member Author

@rsc The previous title mentioned arrays. Did you intentionally omit that from retitling? I think if we're specifying that structs are compared field-by-field in source order, then arrays should also be compared element-by-element in index order.

@rsc rsc modified the milestones: Proposal, Backlog Jun 10, 2020
@rsc rsc changed the title proposal: spec: define that structs are compared field-by-field as listed in source code spec: define that structs are compared field-by-field as listed in source code Jun 10, 2020
@gopherbot
Copy link

Change https://golang.org/cl/237919 mentions this issue: cmd/compile: fix ordering problems in struct equality

gopherbot pushed a commit that referenced this issue Jun 15, 2020
Make sure that if a field comparison might panic, we evaluate
(and short circuit if not equal) all previous fields, and don't
evaluate any subsequent fields.

Add a bunch more tests to the equality+panic checker.

Update #8606

Change-Id: I6a159bbc8da5b2b7ee835c0cd1fc565575b58c46
Reviewed-on: https://go-review.googlesource.com/c/go/+/237919
Run-TryBot: Keith Randall <khr@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@gopherbot
Copy link

Change https://golang.org/cl/237921 mentions this issue: cmd/compile: clean up equality generation

bradfitz referenced this issue in inetaf/netaddr Jul 2, 2020
gopherbot pushed a commit that referenced this issue Aug 27, 2020
We're using sort.SliceStable, so no need to keep track of indexes as well.

Use a more robust test for whether a node is a call.

Add a test that we're actually reordering comparisons. This test fails
without the alg.go changes in this CL because eqstring uses OCALLFUNC
instead of OCALL for its data comparisons.

Update #8606

Change-Id: Ieeec33434c72e3aa328deb11cc415cfda05632e2
Reviewed-on: https://go-review.googlesource.com/c/go/+/237921
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
@ianlancetaylor
Copy link
Contributor

Just a note that I think that we made a decision here: we compare structs for equality by comparing field by field, and exiting early when two fields are unequal. But I don't think that decision was ever added to the spec. (@griesemer)

@mdempsky
Copy link
Member Author

mdempsky commented Nov 4, 2022

To nag again, this issue affects array comparison order too, and it remains unconfirmed whether arrays were intentionally dropped from the accepted retitling on June 10, 2020.

@griesemer
Copy link
Contributor

It seems to me that the same problems that might occur with unspecified struct field comparison order would apply to array comparisons. I'll send out a CL specifying both, in the spirit of this issue. We can discuss on the issue if we want to keep the clarification for arrays.

@gopherbot
Copy link

Change https://go.dev/cl/449536 mentions this issue: spec: clarify struct field and array element comparison order

@mdempsky
Copy link
Member Author

It seems to me that the same problems that might occur with unspecified struct field comparison order would apply to array comparisons.

I feel like my comments aren't being heard.

My original issue report from 2014 mentions structs and arrays equally: they were both mentioned in the issue title and the very first sentence of the issue body. Whenever I replied mentioning structs, I wrote "struct/array" (1, 2, 3).

@rsc retitled it in June 2020 to remove the mention of arrays. I explicitly asked that same day if that was intentional, and never got a response.

I asked again 6 days ago after @ianlancetaylor pinged the issues, and still I'm not getting any acknowledgement.

@ianlancetaylor
Copy link
Contributor

I agree with @griesemer that this should apply to arrays as well as structs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
No open projects
Development

Successfully merging a pull request may close this issue.