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

gccgo: incorrect order of evaluation according to spec #23188

Closed
ianlancetaylor opened this Issue Dec 20, 2017 · 31 comments

Comments

Projects
None yet
8 participants
@ianlancetaylor
Contributor

ianlancetaylor commented Dec 20, 2017

Consider this program:

package main
 
import "fmt"
 
func main() {
        arr := []int{1, 2}
        arr, arr[len(arr)-1] = arr[:len(arr)-1], 3
        fmt.Println(arr)
}

This currently prints [1], and in fact it prints [1] with all versions of Go since Go 1.

According to the spec, when evaluating an assignment statement, all function calls are evaluated in lexical left to right order. Also, all index expressions on the left are evaluated, and then the assignments are done in left to right order.

len is a function call, so all the calls to len should be evaluated before any assignments. This, the second assignment statement should be equivalent to

        arr, arr[2-1] = arr[:2-1], 3

so we have

        arr, arr[1] = arr[:1], 3

So the first assignment in this pair will set arr to [1]. Then the second assignment will set arr[1], but of course there is no such element, so that should panic.

I do not understand why this prints [1] with cmd/compile. With gccgo it panics as I expect with an index out of range error.

CC @griesemer @mdempsky @randall77

@j7b

This comment has been minimized.

j7b commented Jan 25, 2018

Isn't arr what it was initialized to until after the entire tuple assignment is evaluated?

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 25, 2018

@j7b That's a fair question. In the statement arr, arr[1] = arr[:1], 3 the spec is clear that we first assign to arr and then assign to arr[1], but the spec is not clear exactly when the variable arr in the expression arr[1] is evaluated. If the compiler is permitted to evaluate the arr in arr[1] before the assignment to arr, then gc's current behavior would be a valid choice. In that case this behavior of this statement would be implementation defined, with gc and gccgo making different choices.

@j7b

This comment has been minimized.

j7b commented Jan 25, 2018

Isn't the indexing a primary expression so is evaluated before (while arr is size 2)?

Edit: size

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 25, 2018

@j7b I don't see words in the spec that require that to happen. The spec says that the operands of index expressions are evaluated first, but for a[i] I have always taken that to mean that i is evaluated first, not that a is evaluated.

@j7b

This comment has been minimized.

j7b commented Jan 25, 2018

I think the spec intends for a to be evaluated based on the Operators section, m := map[string]string{} ; m,m["a"] = nil,"b" is consistent, for example.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 25, 2018

I'm sorry, I don't see the text to which you are referring. I don't see any m, m["a"] in the spec.

In any case, CC @griesemer in case he has an opinion.

@j7b

This comment has been minimized.

j7b commented Jan 25, 2018

Apologies, that was a bit unclear, the m bit was intended to be interpreted as source https://play.golang.org/p/Zn7e7TJXcij to demonstrate the index expression is evaluated first and the spec bit is https://golang.org/ref/spec#Operators I read as slicing, indexing etc are themselves expressions that are evaluated with unary expressions (including primaries) having the highest precedence.

@griesemer

This comment has been minimized.

Contributor

griesemer commented Jan 29, 2018

Here's a (manual) translation into the relevant steps as specified by the spec:

package main

import "fmt"

func main() {
	arr := []int{1, 2}

	// arr, arr[len(arr)-1] = arr[:len(arr)-1], 3

	// https://tip.golang.org/ref/spec#Assignments
	// 1) First, the operands of index expressions and pointer indirections
	// (including implicit pointer indirections in selectors) on the left
	// and the expressions on the right are all evaluated in the usual order.

	// https://tip.golang.org/ref/spec#Order_of_evaluation
	// 2) Otherwise, when evaluating the operands of an expression, assignment,
	// or return statement, all function calls, method calls, and communication
	// operations are evaluated in lexical left-to-right order.

	// set of operands of index expressions and pointer indirections on left,
	// and expressions on right:
	// len(arr)-1
	// arr[:len(arr)-1], 3

	// evaluation of these expressions in usual order
	l1 := len(arr)
	r1 := len(arr)
	r2 := arr[:r1-1]
	r3 := 3

	// https://tip.golang.org/ref/spec#Assignments
	// 3) Second, the assignments are carried out in left-to-right order.

	arr = r2
	arr[l1-1] = r3

	fmt.Println(arr)
}

which leads to the index out of range panic.

However, the spec also says in https://tip.golang.org/ref/spec#Order_of_evaluation, referring to the example in that section:

However, the order of those events compared to the evaluation and indexing of x and the evaluation of y is not specified.

Thus, if the indexing of arr[l1-1] happens before the assignment, effectively leading to the swap of the last 2 assignments, we get the printed result [1].

Which seems to imply that both interpretations are valid.

cc: @mdempsky for comments.

@mdempsky

This comment has been minimized.

Member

mdempsky commented Jan 29, 2018

In the assignment, the indexee operand arr in arr[len(arr)-1] is evaluated before the assignment too, so it evaluates to the full 2-length slice.

See also #15620 and #23017.

@j7b

This comment has been minimized.

j7b commented Jan 30, 2018

I'm finding myself disagreeing with all due respect and humility with the premise advanced in #15620 by @griesemer which is indeed related. Based on "Index" as defined at https://golang.org/ref/spec#Primary_expressions for a[i] i is an "Expression," so it follows the operand is a. In #15620 xs[4], 4 is referred to as the operand, but for all intents and purposes numeric constants are expressions as defined in the spec, and I can't resolve the notion of a numeric constant being an operand for any definition of that term.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 30, 2018

@mdempsky Are you saying that the language requires that arr be evaluated before the assignment? Or are you saying that the language permits that?

@griesemer

This comment has been minimized.

Contributor

griesemer commented Jan 30, 2018

@j7b You are correct that a is also an operand, but so is i. In short, in a[i], both a and i are operands (because the elementary values that flow into any expression are operands ( https://tip.golang.org/ref/spec#Operands ). You are right that the i is an Expression in the syntax for index expressions, but that Expression eventually resolves to an Operand (which then resolves to the Identifier i). I agree with you that I missed that point (that the array is also an operand) here and in #15620. A numeric constant is a literal ( https://tip.golang.org/ref/spec#Literal ), and thus also an operand (since an operand may be a literal). So the 4 in xs[4] of issue #15620 would also be an operand. This is what @mdempsky is saying there as well.

@ianlancetaylor I believe the point @mdempsky is making is that arr is also an operand of the index expression, and thus the language requires that arr be evaluated before the assignment. Which would mean that this code should not panic.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 30, 2018

@ianlancetaylor I believe the point @mdempsky is making is that arr is also an operand of the index expression, and thus the language requires that arr be evaluated before the assignment. Which would mean that this code should not panic.

That has never been my reading of the spec: I've never thought that the spec specified exactly when to read a value out of a variable. We can go that way if we like. I'm concerned that we are making the order of evaluation rules more and more complex without ever fully specifying the order. Do we want to leave room for compiler optimization or not? If we want to leave room, then we should not specify exactly when to read a value from a variable. If we do not want to leave scope, then we should fully specify the order rather than continuing with this ambiguous state. For example, why should we evaluate the variable in an index operation but not in a mathematical operation? I don't think any sensible program would both set and use the same variable in a single statement, so I don't think this matters for sensible programs; it's purely a question of how much compiler optimization the language should permit. I'm OK either way, but I'm not really OK with the fact that we can't agree on the meaning of a simple statement like the one discussed here.

@griesemer

This comment has been minimized.

Contributor

griesemer commented Jan 30, 2018

@ianlancetaylor Agreed. At the very least, the wording in the spec is not precise enough: We talk about "operands" and sometimes we literally mean anything that can be reduced to an operand syntactically; and sometimes (in other interpretations) we don't. We need to clarify the spec so we don't end up here every time.

If we don't evaluate the array here, then we probably shouldn't in #15620.

@j7b

This comment has been minimized.

j7b commented Jan 30, 2018

@griesemer as near as I can tell the only place a constant is an operand in the spec is in a constant expression, in which case a numeric constant is not one, but let's say for the sake of an argument i is an operand, by the definition of "Index expression" it is also an expression, a (the slice variable) is the only part of a[i] that is unambiguously an operand only, therefore it is the most likely to be the operand referred to in the "first phase" of the tuple assignment specification. Also if the order is the "unspecified" order of the single-assignment form, why have 2 phases and specify to do the indexing and pointer dereferencing on the left hand side first?

I'd suggest @ianlancetaylor that for the most part the spec is excellent and unambiguous and a reference implementation existing before the spec did doesn't leave much room to argue. I'm also pretty sure now that https://play.golang.org/p/LhSkogGI6bf is "bad" and spec might actually be saying the panic should occur before phase 2 starts, preferably before it evaluates the rhs at all. In any event there's nothing optimal about what happens now from a user code perspective which I'd hope trumps compiler optimization. Your original example at https://gopherjs.github.io/playground/#/SmnbAuf_mj gives us yet another hard-to-reason-about result. Maybe to expedite things the way cmd/compile does things now should be treated as a de facto standard and a test added to so enforce it on other toolchains.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 30, 2018

@j7b Minor point, but it's not accurate to say that a reference implementation existed before the spec. The spec and two different implementations were developed simultaneously. In the early days the spec was always first.

We definitely should not treat cmd/compile as the de facto standard. cmd/compile has been wrong in the past, and it may still be wrong in some ways.

@griesemer

This comment has been minimized.

Contributor

griesemer commented Jan 30, 2018

@j7b There is no syntactic production for "constant expression". An operand may be a literal, and a Literal may be (among other things) a basic literal, which in turn may be a floating-point literal, i.e., a floating point constant. That is, a numeric constant is an operand, there's no doubt about that. The section on constant expressions also says that in prose ( "Untyped boolean, numeric, and string constants may be used as operands ... "). Specifically, a constant expression may be a single numeric constant, and a numeric constant is a (simple) constant expression.

But this doesn't even matter in this case: constant evaluation is side-effect free, so it is irrelevant when they are evaluated. So let's not get distracted with the constants here.

The reason for the two phases is to provide "some order" (left to right), while also explaining the semantics of the "parallel assignment" . There's different ways this could be done, but the hope here was to provide both order (for the programmer) and some freedom of evaluation (for the compiler, e.g. for better code). Maybe what we have is too complicated, or perhaps not precise enough. It's important to keep in mind that these questions only arise in corner-case scenarios; I'd usually recommend to write the code more explicitly because it will be much more readable. Still, the spec needs to cover these cases, of course.

FWIW, there was no "reference implementation" that existed before the spec. The spec is the reference, and we have gone through great lengths and many years to make the compilers compliant with the spec (and only more recently we have adjusted the spec to match the compilers because we cannot make changes that might break a lot of code).

@dchenk

This comment has been minimized.

Contributor

dchenk commented Jan 30, 2018

Check out the links to the GitHub repo and Travis CI test results here: https://groups.google.com/d/msg/golang-nuts/rijNzxDE3-M/VIAJm_GfBAAJ
(btw the failed builds are just timed out)

@dchenk

This comment has been minimized.

Contributor

dchenk commented Jan 30, 2018

The spec says, "For slices, the upper index bound is the slice capacity cap(a) rather than the length" under https://golang.org/ref/spec#Slice_expressions. So @ianlancetaylor ("the second assignment will set arr[1], but of course there is no such element, so that should panic"), according to the spec nothing should panic (gccgo should not be panicking). In your example, the second element is simply no longer accessible for reading, but it's value is set to 3 anyway; here: https://play.golang.org/p/T12li3u7VTp

I think the interesting questions is when the slice that's being written to is changed by the function called inside the brackets, as in:

mySlice[growForWrite(mySlice)] = 45 // growForWrite returns the index at which to write

Here we want the guarantee that growForWrite is called first and is able to change what mySlice points to.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 30, 2018

The spec says, "For slices, the upper index bound is the slice capacity cap(a) rather than the length" under https://golang.org/ref/spec#Slice_expressions.

@dchenk You are quoting the language for slice expressions, but this is an index expression.

@dchenk

This comment has been minimized.

Contributor

dchenk commented Jan 30, 2018

@ianlancetaylor ("You are quoting the language for slice expressions"), ok I see the difference, thank you. To confirm, is it correct that this

var mySlice []int
mySlice[growForWrite(&mySlice)] = 45 // growForWrite grows mySlice and returns len(mySlice)

will always write to the correct instance of mySlice even if the call growForWrite(&mySlice) changes the underlying array (expanding it may move it to another place in memory). That is, is it correct that mySlice will not be stale in the assignment?

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jan 31, 2018

@dchenk I don't know. In a way that is one aspect of what this issue is about.

tamird added a commit to tamird/cockroach that referenced this issue Feb 2, 2018

tamird added a commit to tamird/cockroach that referenced this issue Feb 2, 2018

tamird added a commit to tamird/cockroach that referenced this issue Feb 2, 2018

tamird added a commit to tamird/cockroach that referenced this issue Feb 5, 2018

tamird added a commit to tamird/cockroach that referenced this issue Feb 5, 2018

tamird added a commit to tamird/cockroach that referenced this issue Feb 5, 2018

@go101

This comment has been minimized.

go101 commented Mar 19, 2018

I created a new issue for the problem mentioned by @tamird
#24448

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented May 28, 2018

Another related issue in #25609.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented May 28, 2018

I'm sort of inclined to change the spec to say that if a single statement both refers directly to a variable and changes that variable, either through a direct assignment or a function call, that the result is implementation defined. It shouldn't be undefined--something plausible should always happens--but we shouldn't specify the exact ordering of the variable read and write. Then I think we should try to write a vet check for this case.

The argument in favor of this is that no reasonable program should do this. Even if we fully specify the order, anybody reading the program will struggle to understand how it is supposed to work. That doesn't seem useful. Better to say explicitly that it won't work reliably, and catch it in vet if we can.

@Quasilyte

This comment has been minimized.

Contributor

Quasilyte commented Jun 23, 2018

Original message example can be simplified to more minimal form:

package main

func main() {
	xs := []int{1, 2, 3}
	ys := []int{1, 2}
	xs, xs[2] = ys, 10
}

Here, no function calls at all, yet it still leads to panic vs no panic result.

@ianlancetaylor

This comment has been minimized.

Contributor

ianlancetaylor commented Jul 10, 2018

I've come around to believing that when the spec requires that index operations be evaluated in left-to-right order, that that implies that both operands of the index operation be evaluated. So on that interpretation, the original program in this issue is fully defined, and gccgo gets it wrong.

@ianlancetaylor ianlancetaylor changed the title from cmd/compile: incorrect order of evaluation according to spec to gccgo: incorrect order of evaluation according to spec Jul 10, 2018

@ianlancetaylor ianlancetaylor modified the milestones: Go1.11, Gccgo Jul 10, 2018

@gopherbot

This comment has been minimized.

gopherbot commented Jul 10, 2018

Change https://golang.org/cl/123115 mentions this issue: test: add order of evaluation test case that gccgo got wrong

@gopherbot

This comment has been minimized.

gopherbot commented Jul 10, 2018

Change https://golang.org/cl/123155 mentions this issue: compiler: fix evaluation order of LHS index expressions

gopherbot pushed a commit that referenced this issue Jul 10, 2018

test: add order of evaluation test case that gccgo got wrong
Updates #23188

Change-Id: Idc5567546d1c4c592f997a4cebbbf483b85331e0
Reviewed-on: https://go-review.googlesource.com/123115
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>

hubot pushed a commit to gcc-mirror/gcc that referenced this issue Jul 11, 2018

ian
compiler: fix evaluation order of LHS index expressions
    
    The spec says that when an index expression appears on the left hand
    side of an assignment, the operands should be evaluated. The
    gofrontend code was assuming that that only referred to the index
    operand. But discussion of https://golang.org/issue/23188 has
    clarified that this means both the slice/map/string operand and the
    index operand. Adjust the gofrontend code accordingly.
    
    Fixes golang/go#23188
    
    Reviewed-on: https://go-review.googlesource.com/123155


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@262554 138bc75d-0d04-0410-961f-82ee72b054a4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment