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: when exactly do we evaluate the LHS variable in a tuple assignment? #15620

Open
georgeteo opened this issue May 9, 2016 · 19 comments

Comments

@georgeteo
Copy link

commented May 9, 2016

Please answer these questions before submitting your issue. Thanks!

  1. What version of Go are you using (go version)?
    gccgo version 4.9.3
  2. What operating system and processor architecture are you using (go env)?
    Ubuntu 14.04 on AWS t2.micro
  3. What did you do?
    If possible, provide a recipe for reproducing the error.
    A complete runnable program is good.
    A link on play.golang.org is best.

Deleting from a slice as suggested by https://github.com/golang/go/wiki/SliceTricks, raises an index out of bound error when compiling with gccgo. The following toy program works fine using GC but not with GCCGO:

package main

import "fmt"

func main() {
    xs := []int{0,1,2,3,4}
    i := 2
    xs, xs[len(xs)-1] = append(xs[:i], xs[i+1:]...), 0
    fmt.Println(xs)
}

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

Note: while this toy example is a slice of ints, I'm using the delete code for removing an entry from a slice of pointers. The bug is in xs[len(xs)-1] = 0.

  1. What did you expect to see?

[0 1 3 4]

  1. What did you see instead?
panic: runtime error: index out of range

goroutine 1 [running]:
main.main
    /home/ubuntu/Go/src/bad/remove.go:8

@ianlancetaylor ianlancetaylor added this to the Gccgo milestone May 9, 2016

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

It's not obvious to me that this program is well-defined according to Go's order of evaluation rules.

The rules say that in a tuple assignment all index expressions are evaluated on both the left and right hand sides. Then all the assignments are done in left to right order.

What the rules do not say is precisely when the first xs in the expression xs[len(xs)-1] is evaluated. It's clear that the second xs in that expression is evaluated first. However, the program also expects that the first xs is evaluated before the assignment to xs in the tuple assignment. But I don't see anything in the spec that requires that.

It is at least possible that the precise behavior of this program is not defined by the spec, and that gccgo is implementing it correctly.

CC @griesemer for a second opinion.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

Per Order of Evaluations (https://tip.golang.org/ref/spec#Order_of_evaluation), functions calls are executed from left to right, and per the example in that section, the len and append function calls are executed as len followed by append. So we can rewrite the assignment as:

n := len(xs)
xs, xs[n-1] = append(xs[:i], xs[i+1:]...), 0

There are no assignments to i and n, so they don't change and we can thus write this code as:

xs, xs[4] = append(xs[:2], xs[3:]...), 0

Per the spec "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. Second, the assignments are carried out in left-to-right order." (https://tip.golang.org/ref/spec#Assignments).

The operand of the index expression on the left is 4 (and it would still be 4 even if we evaluated it only now). Then all the expressions on the right are evaluated. The result of the append call is:

[]int{0, 1, 3, 4}

So we are left with:

xs, xs[4] = []int{0, 1, 3, 4}, 0

Note that the spec says that the operands of index expressions are evaluated first, not the index expressions themselves. Then assignment occurs from left to right. That is, only then are the index expressions evaluated, from left to right as the assignments occur:

xs = []int{0, 1, 3, 4}
xs[4] = 0

After the first assignment, the length of xs is 4, so I would expect the 2nd assignment, and in fact this parallel assignment to panic with an index out of bounds error.

I'd argue that this is a bug in gc and gccgo is correct.

I'd also recommend to not write code like this (correct or not) as it is not easily readable in the first place.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

I think your analysis relies on a rather close reading of the assignments occurring from left to right. In this example, does that really imply an exact order for when we read the variable xs, especially given that in this case xs is actually changing?

In any case I'm glad you agree that gccgo is not wrong.

@ianlancetaylor ianlancetaylor modified the milestones: Unplanned, Gccgo May 9, 2016

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

I removed the questionable example from the wiki page.

@ianlancetaylor ianlancetaylor changed the title Index out of bounds error when deleting from slice on gccgo spec: when exactly do we evaluate the LHS variable in a tuple assignment? May 9, 2016

@griesemer

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

@ianlancetaylor I think a close reading will be required to determine corner-cases such as this one. I don't remember the details of the original discussions, but the spec is careful in distinguishing between evaluation of operands (of index and indirection expressions), and evaluation of entire expressions.

To contrast, if the expressions xs and xs[4] were on the right, in this order, I'd agree that it's not further specified when those expressions are evaluated. But they are on the left and they are influenced by the assignments, which is the point. For instance: https://play.golang.org/p/1rkU6oIsBL

package main

var p *int

func main() {
    p = new(int)
    p, *p = nil, 1
    println(*p)
}

is of similar nature: The assignment of nil to p happens before the assignment of 1 to *p (and thus the evaluation of *p (but not the evaluation of the operand p). The result is a run-time panic. This seems to corroborate my previous claim.

PS: This is of course rubbish. The panic is happening during the println. See comments by @mdempsky below.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

I think the spec is clear. We may want to add an explicit sentence and perhaps add a couple of corner-case examples at best. Not urgent.

@mdempsky

This comment has been minimized.

Copy link
Member

commented May 9, 2016

@griesemer In your last example, the run-time panic is due to the dereference of p in println(*p), not the tuple assignment statement. This program runs without panic though: https://play.golang.org/p/HNJ8aH3eIi

For what it's worth, my reading of the Go spec is that

    xs, xs[len(xs)-1] = append(xs[:i], xs[i+1:]...), 0

should be equivalent to:

// "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."
tmp1 := len(xs)
tmp2 := append(xs[:i], xs[i+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."
tmp3, tmp4, tmp5, tmp6 := xs, tmp1-1, tmp2, 0

// "Second, the assignments are carried out in left-to-right
// order."
xs = tmp5
tmp3[tmp4] = tmp6

Which supports cmd/compile's current behavior: https://play.golang.org/p/bFofYVAqt-

@griesemer

This comment has been minimized.

Copy link
Contributor

commented May 9, 2016

@mdempsky You are correct about the *p panic.

Hm, the indexed expression is also an operand, point taken.

It's probably worthwhile highlighting the subtleties with some specific examples in the spec.

@go101

This comment has been minimized.

Copy link

commented Mar 11, 2018

Is the following description for value evaluation orders in assignments better?

Any assignment statement can be rewritten as the following form finally,
just before the real individual assignments happen.

*L0, *L1, ..., *Ln = R0, R1, ..., Rn

Where each Lx is a scalar address value, and each Rx is a scalar value.
The type of Rx is the base type of the type of Lx.

For example (assume a is a slice which element type is int),

a, a[len(a)-1] = a[:len(a)-1], 2

will be rewritten in the following steps:

t0 := len(a); t1 := t0 - 1
t2 := a[:t1]
t3 := &a; t4 := &a[t1]
*t3, *t4 = t2, 2

If a map element (which is unaddressable) appears at left side,
the new value for it will be stored in an addressable temp value firstly,
then in an extra step, the temp value will be assigned to the map element.

For example (assume m is map and p is a pointer, the map element type
and the base type of p is the same one, T):

m[5] = m[5] + *p

will be rewirtten in the following steps:

t0 := m[5]; t1 := *p; t2 := t0 + t1
var t3 T; t4 := &t3 // t3 is a temp value
*t4 = t2
m[5] = t3 // the extra step

The extra steps may be not the last steps. For example

var m = map[int]int{}
var p *int
m[2], *p = 1, 2

will be rewritten in the following steps:

var t0 int; t1 := &t0
*t1, *p = 1, 2
m[2] = t0

Here, m[2] = t0 happens closely following *t1 = 1, before *p = 2.

@andybons andybons added the NeedsFix label Mar 11, 2018

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 12, 2018

Is the following description for value evaluation orders in assignments better?

Sorry, I'm not sure I understand what you mean by better here. However, I'll point out that I think the rules you described are incomplete, and also stricter than the current spec. If you're suggesting the spec should take this approach, I'm inclined to disagree.

First, your description of how to handle map assignments doesn't handle when to evaluate the map or its index. For example,

m := make(map[int]int)
m, m[0] = nil, 42

should not panic. Your description seems to suggest the assignment will be rewritten as:

t0 := &m
var t1 int; t2 := &t1
*t0, *t2 = nil, 42
m[0] = t1

However, this will panic, because the *t0 = nil assignment now affects the final m[0] = t1 assignment. Additional rewrite rules will be needed to correct this.

Second, the spec currently only partially orders evaluation of subexpressions, and a rewrite ordering like this will impose additional ordering constraints. For example, you suggested the first rewrite for m[5] = m[5] + *p is

t0 := m[5]; t1 := *p; t2 := t0 + t1

which suggests the m[5] index operation must be ordered before the *p dereference operation, but the spec currently allows the opposite to be the case. (Technically, because of #23735, you can't distinguish this specific case anyway, but there are other cases that are distinguishable; for example, we don't specify whether x := f() + g(*p) evaluates *p before or after f().)

@go101

This comment has been minimized.

Copy link

commented Mar 12, 2018

Yes, I admit it has some defects.
But firstly, I would clarify it doesn't change the current evaluation order rules in the early phases.
The steps (before the real assignments happen) in the example in in my last comment is just one possible order.

I think its biggest defect is it treats array/slice and map differently. So here I try to make a revision for it.

Any assignment statement can be rewritten as the following form finally,
just before the real individual solo assignments happen.

	L0, L1, ..., Ln = R0, R1, ..., Rn

Where each Lx is either of a form of *Px, or a form of (Cx, Ix).
Each Px is a pointer value. The corresponding Rx is assignable to *Px.
Each Cx is a container (array, slice or map),
and each Ix is one key value of the container.
The corresponding Rx is assignable to Cx[Ix].
Every Px, Rx, Cx and Ix is a scalar value.

The real solo assignments happen by their appearance order,
from left to right (from the view of the current goroutine).

If a Lx is a form of *Px, the corresponding solo assginment is

	*Px = Rx
	
If a Lx is a form of (Cx, Ix), the corresponding solo assginment is

	Cx[Ix] = Rx

[update]: for array and slice element destinations, they can also be represented as *Px.
The evaluation order rules described above are just for explanation purpose,
an implementation doesn't need to obey the exact orders.

@go101

This comment has been minimized.

Copy link

commented Mar 18, 2018

To make it more consistent with the following description in Go spec:

Each left-hand side operand must be addressable, a map index expression,
or (for = assignments only) the blank identifier.

a new revision is made.

==================

Just after the preparation phase and before the carry-out phase of an assignment, the assignment is rewritten as the following elementary form:

	L0, L1, ..., Ln = R0, R1, ..., Rn

where each Lx may be

  1. the blank identifier _, if the corresponding left side item is also the blank identifier.
  2. a form of (*PMx)[Kx], if the corresponding left side item is a map index expression. PMx is a pointer value of a pointer type which base type is a map type and Kx is a value of the key type of the map type. (Note: if the map itself is not addressable, we can assign it to a temp map firstly instead. Or we can use PMx denotes the really underlying hashtable.)
  3. a form of *Px, if the corresponding left side item is neither a map index expression nor the blank identifier. Px is a value of any pointer type.
  4. a nil pointer, if for any reason, in the third case, an address can't be retrieved.

and, every Px, PMx, Kx and Rx is an elementary value which can't be evaluated further.
They are all hidden temporary values which are only referenced in the elementary form of the assignment.

@go101

This comment has been minimized.

Copy link

commented Mar 18, 2018

edited the last comment.

@mdempsky

This comment has been minimized.

Copy link
Member

commented Mar 20, 2018

The evaluation order rules described above are just for explanation purpose, an implementation doesn't need to obey the exact orders.

I'm still unclear what your goal is with this alternative description of order of evaluation rules. Are you suggesting they could be incorporated into the Go spec?

If so, the Go spec needs to describe the exact rules that programmers and compilers must operate under. An explanation that doesn't cover all admissible implementations isn't very useful. If the language spec allows implementations to not obey it, then how would users know what language behavior to expect?

@go101

This comment has been minimized.

Copy link

commented Mar 21, 2018

That updated line is mainly for the first revision.

The last revision is the most satisfied one currently.

These revision attempts are trying to make the explanations for the evaluations of all left items uniform.
Currently, the description in Go spec is some hard to grasp:

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.

The current description in Go spec is not very helpful to explain the mechanism of exchanging values of two variables:

a, b = b, a

With my second revision, it can be explained as the following steps:

// The preparation phase:
P0 := &a; P1 := &b
R0 := a; R1 := b

// The elementary form: *P0, *P1 = R0, R1

// The carry-out phase:
*P0 = R0
*P1 = R1

And the second revision is good to clear the disputes in this issue thread: #23188

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

// The preparation phase:
P0 := &arr; P1 := &arr[len(arr)-1]
R0 := arr[:len(arr)-1; R1 := 3

// The elementary form: *P0, *P1 = R0, R1

// The carry-out phase:
*P0 = R0
*P1 = R1

Are you suggesting they could be incorporated into the Go spec?

kind of, but the current description of the second revision is no ways perfect now,
so it needs some adjustments, I think.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Mar 21, 2018

In the current spec, the swap a, b = b, a is explained by the rule "first, ... and the expressions on the right are all evaluated in the usual order." Evaluating the expressions on the right means fetching the values from the variables, so the swap becomes (using temporary variables t0 and t1, and adding the rule that the assignments are carried out in left-to-right order):

t0, t1 = b, a // order here is unspecified
a = t0
b = t1
@go101

This comment has been minimized.

Copy link

commented Mar 21, 2018

Yes, this is the cause for the dispute in #23188.

@go101

This comment has been minimized.

Copy link

commented Mar 21, 2018

There is an example in spec

x := []int{1, 2, 3}
i := 0
i, x[i] = 1, 2  // set i = 1, x[0] = 2

which indicates the example in #23188 shouldn't panic

        arr := []int{1, 2}
        arr, arr[len(arr)-1] = arr[:len(arr)-1], 3

[update]
By using my last revision, it is easy to explain both of the two cases.
for i, x[i] = 1, 2 // set i = 1, x[0] = 2:

// The preparation phase:
P0 := &i; P1 := &x[0]
R0 := 1; R1 := 2

// The elementary form: *P0, *P1 = R0, R1

// The carry-out phase:
*P0 = R0
*P1 = R1

The explanation for arr, arr[len(arr)-1] = arr[:len(arr)-1], 3 is in my last comment.

@go101

This comment has been minimized.

Copy link

commented Jun 27, 2018

edit the comment by adding 4th case and modifying the 2nd case.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
6 participants
You can’t perform that action at this time.